Идеальная решётка

Идеальная решётка — определённая математическая структура, которая используется для уменьшения числа параметров, необходимых для описания решёток (представляющих собой свободные коммутативные группы конечного ранга). Данный вид решёток часто встречается во многих областях математики, в частности, в разделе теории чисел. Таким образом идеальные решётки более эффективны в применении, чем другие решётки, применяющихся в криптографии. Идеальные решётки используются в криптографических системах с открытым ключом NTRUEncrypt и NTRUSign для построения эффективных криптографических примитивов. Также идеальные решётки составляют фундаментальную основу квантовой криптографии, которая защищает от атак, связанных с квантовыми компьютерами.

Введение

Схемы RSA и ECC, основанные либо на сложности факторизации, либо на сложности проблемы дискретного логарифма, являются самыми популярными асимметричными криптосистемами, которые для шифрования информации и её последующего расшифровывания используют различные ключи. Несмотря на преобладание схем RSA и ECC, они, как известно, подвержены атакам с использованием квантовых компьютеров. Кроме того, RSA и ECC довольно неэффективны на очень небольших и ограниченных устройствах, таких как 8-битные микроконтроллеры AVR, использующиеся по сей день в различных областях, таких как робототехника, энергетика, спутниковые системы связи и многие другие. Возможной альтернативой упомянутых схем являются асимметричные криптосистемы, основанные на жёстких задачах в идеальных решётках. Специальная алгебраическая структура идеальных решёток позволяет значительно уменьшить размеры ключа и шифротекста, обеспечивая при этом эффективную арифметику с использованием теоретико-числового преобразования. Таким образом благодаря использованию идеальных решёток повышается степень защиты зашифрованной информации.

Базовые понятия

Решётка для двух разных норм квадратичной формы

Теория решёток может быть описана с помощью линейной алгебры. Решётка обычно рассматривается как любая равномерно распределённая сетка точек в n-мерном реальном линейном пространстве [math]\displaystyle{ R^n }[/math] со всеми координатами, являющимися целыми числами. Это множество образует группу при сложении по координатам и является дискретным, что означает, что для каждой точки в множестве есть открытый шар вокруг неё, который не содержит никакой другой точки множества, таким образом решёткой называется множество всех целочисленных линейных комбинаций заданного набора линейно независимых точек в [math]\displaystyle{ Z^n }[/math]. Решётки — являются группами, а идеальные решётки идеалами.

Двумерная решётка с двумя базисами

В частности, идеальные решётки соответствуют кольцам вида [math]\displaystyle{ \mathbb{Z}[x]/\langle f \rangle }[/math] для некоторого неприводимого многочлена [math]\displaystyle{ f }[/math] степени [math]\displaystyle{ n }[/math]. Основная операция в идеальной решёточной криптографии — полиномиальное умножение.

Математическое определение идеальной решётки

Идеальная решётка — это целочисленная решётка [math]\displaystyle{ \mathcal{L}(I)\subseteq \mathbb{Z}^n }[/math] такая, что для некоторого заданного базиса [math]\displaystyle{ B \in \mathbb{Z}^{(n,n)} }[/math] такого, что [math]\displaystyle{ B = }[/math] [math]\displaystyle{ \lbrace(g\ \bmod\ \ f) : g \in \mathbb{Z}[x] \rbrace }[/math] и для некоторого приведённого многочлена [math]\displaystyle{ f }[/math] степени [math]\displaystyle{ n }[/math] существует идеал [math]\displaystyle{ I \subseteq \mathbb{Z}[x]/\langle f \rangle }[/math]

Ограничения, накладываемые на [math]\displaystyle{ f }[/math]:

• [math]\displaystyle{ f }[/math] — должен быть неприводимым
• норма кольца [math]\displaystyle{ \lVert g \rVert_f }[/math] не должна быть больше, чем норма [math]\displaystyle{ \lVert g \rVert_\infty }[/math] для любого многочлена [math]\displaystyle{ g }[/math]

Лемма

Если [math]\displaystyle{ f }[/math] является нормированным неприводимым целочисленным многочленом степени [math]\displaystyle{ n }[/math], то любой идеал есть изоморфная решётка полного ранга в [math]\displaystyle{ \mathbb{Z}^n }[/math],то есть базис состоит из [math]\displaystyle{ n }[/math] линейно независимых векторов, координаты которых и являются коэффициентам многочлена [math]\displaystyle{ f }[/math] степени [math]\displaystyle{ n }[/math]

Алгоритм идентификации идеальных решёток с базисами полного ранга

Алгоритм идентификации идеальных решёток с базисами полного

Пусть задан базис [math]\displaystyle{ B \in \mathbb{Z}^{(n,n)} }[/math]
Условие: если [math]\displaystyle{ B }[/math] охватывает идеальную решётку относительно параметра [math]\displaystyle{ q }[/math], тогда правда, иначе ложь

1. привести [math]\displaystyle{ B }[/math] к эрмитовой форме
2. [math]\displaystyle{ A = {\rm adj}(B) }[/math], то есть [math]\displaystyle{ B }[/math] — присоединённая матрица, [math]\displaystyle{ d = \det(B) }[/math] — детерминант и [math]\displaystyle{ z = B_{(n,n)} }[/math]
3. [math]\displaystyle{ P = AMB \bmod \ d }[/math]
4. если все столбцы [math]\displaystyle{ P }[/math] кроме последнего нулевые тогда
5. положить в [math]\displaystyle{ c = P_{(\centerdot,n)} }[/math] ненулевой столбец (а именно, последний столбец [math]\displaystyle{ P }[/math])
6. иначе вернуть ложь
7. если [math]\displaystyle{ z \mid c_i }[/math], то есть множество элементов z, удовлетворяющих [math]\displaystyle{ c_i }[/math] для всех [math]\displaystyle{ i = 1, \dots , n }[/math] тогда
8. применить китайскую теорему об остатках для нахождения [math]\displaystyle{ q^ \ast \equiv \ (c/z) \bmod \ (d/z) }[/math] и [math]\displaystyle{ q^ \ast \equiv 0 \bmod \ z }[/math]
9. иначе вернуть ложь
10. если [math]\displaystyle{ Bq^ \ast \equiv 0 \bmod \ (d/z) }[/math] тогда
11. вернуть правду, [math]\displaystyle{ q = Bq^ \ast /d }[/math]
12. иначе вернуть ложь

Дополнение: матрица [math]\displaystyle{ M }[/math] принимает вид

[math]\displaystyle{ M = \begin{pmatrix} 0 & . & . & . & 0 \\ & & & & . \\ & & & & . \\ I_{n-1} & & & & . \\ & & & & 0 \end{pmatrix} }[/math]

Пример использования алгоритма идентификации идеальных решёток с базисами полного ранга

Используя данный алгоритм, можно убедиться в том, что немногие решётки являются идеальными решётками.
Рассмотрим пример: Пусть [math]\displaystyle{ n = 2 }[/math] и [math]\displaystyle{ k \in \mathbb{Z} \setminus \lbrace 0, \pm 1 \rbrace }[/math], тогда

[math]\displaystyle{ B_1 = \begin{pmatrix} k & 0 \\ 0 & 1 \end{pmatrix} }[/math]

является идеальной, в отличие от

[math]\displaystyle{ B_2 = \begin{pmatrix} 1 & 0 \\ 0 & k \end{pmatrix} }[/math]

[math]\displaystyle{ B_2 }[/math] с [math]\displaystyle{ k = 2 }[/math] пример, придуманным Любашевским В. и Миссиансио Д.

Для использования данного алгоритма, матрица [math]\displaystyle{ B }[/math] обязана являться эрмитовой нормальной формой, таким образом первый шаг алгоритма обязателен к выполнению. Детерминант равен[math]\displaystyle{ d = 2 }[/math], а присоединённая матрица

[math]\displaystyle{ A = \begin{pmatrix} 2 & 0 \\ 0 & 1 \end{pmatrix} }[/math]

[math]\displaystyle{ M = \begin{pmatrix} 0 & 0 \\ 1 & 0 \end{pmatrix} }[/math]

и наконец, произведение матриц [math]\displaystyle{ P = AMB \bmod d }[/math] есть

[math]\displaystyle{ P = \begin{pmatrix} 0 & 0 \\ 1 & 0 \end{pmatrix}. }[/math]

На этом этапе алгоритм останавливается, потому что все столбцы [math]\displaystyle{ P }[/math] кроме последнего, должны быть равны нулю, если [math]\displaystyle{ B }[/math] является идеальной решёткой.

Распространённые задачи теории решёток

Основная статья: Задачи теории решёток

• поиск кратчайшего вектора — поиск кратчайшего ненулевого вектора, по представленной произвольными базисными векторами решётке. В действительности, обычно рассматривается приближённый вариант задачи поиска кратчайшего вектора, целью которой — получение вектора в решётке, длина которого не превосходит длину кратчайшего ненулевого вектора в μ(n)-раз, где μ(n)- коэффициент приближения, а [math]\displaystyle{ n }[/math]- размерность решётки.
• поиск ближайшего вектора — обобщение задачи поиска кратчайшего вектора
• поиск кратчайших независимых векторов.

Применение идеальных решёток

Хэш-функции, устойчивые к коллизиям

Устойчивая к коллизиям хеш-функция — это функция заданная отображением [math]\displaystyle{ h_k }[/math][math]\displaystyle{ : D\rightarrow R }[/math] так, что мощность множества (области некоторого числового пространства) [math]\displaystyle{ D }[/math] больше мощности множества [math]\displaystyle{ R }[/math], [math]\displaystyle{ |R| }[/math][math]\displaystyle{ \ll }[/math][math]\displaystyle{ |D| }[/math], тем самым затрудняя нахождение коллизии, то есть пару [math]\displaystyle{ x_1, x_2 \in D, h(x_1)=h(x_2) }[/math]. Таким образом, по случайно выбранному [math]\displaystyle{ k }[/math] ни один злоумышленник не сможет эффективно (за разумное время) найти коллизии в [math]\displaystyle{ h_k }[/math], даже несмотря на тот факт, что коллизии присутствуют. Основное использование идеальных решёток в криптографии связано с тем, что достаточно эффективные и практичные коллизионные хэш-функции могут быть построены на основе твёрдости нахождения приближённого кратчайшего вектора в таких решётках. Группы учёных, изучающие идеальные криптографические решётки, исследовали коллизионные устойчивые хэш-функции, построенные на основе идеальных решёток, а именно Пейкрет К. и Розен С.. Эти результаты проложили путь для других эффективных криптографических конструкций, включая схемы идентификации и подписи.

Лобашевский В. и Миссиансио Д. предложили конструкции эффективных и устойчивых к коллизиям хэш-функций, которые могут быть доказаны на основе наихудшей жёсткости задачи о кратчайшем векторе для идеальных решёток. Тем самым были определены рассматриваемые семейства хэш-функции для элементов:

[math]\displaystyle{ h(b) = \sum_{i=1}^{m}\alpha_i \centerdot b_i }[/math], где [math]\displaystyle{ m }[/math] есть выборка случайных элементов из [math]\displaystyle{ a_1, \dots , a_m \in R = \mathbb{Z}_p[x]/\langle f \rangle }[/math], [math]\displaystyle{ b = (b_1, . . . , b_m) \in D^m }[/math] .

В данном случае размер ключа, то есть хэш-функции определяется как [math]\displaystyle{ O(mn \log p) = O(n \log n) }[/math], используя алгоритм быстрого преобразования Фурье, для подходящего [math]\displaystyle{ f }[/math], операция [math]\displaystyle{ \alpha_i \centerdot b_i }[/math] может быть выполнена за время [math]\displaystyle{ O(n \log n \log \log n) }[/math]. Поскольку [math]\displaystyle{ m }[/math] есть константой, то для хеширования требуется конечное время [math]\displaystyle{ O(n \log n \log \log n) }[/math].[math]\displaystyle{ }[/math]

Цифровые подписи

Схемы цифровых подписей относятся к числу наиболее важных криптографических примитивов. Они могут быть получены с помощью односторонних функций, основанных на наихудшей жёсткости решёточных задач, однако являются непрактичными. С момента использования проблемы обучения с ошибками в криптографическом контексте был разработан ряд новых схем цифровой подписи, основанных на обучении с ошибками и кольцевом обучении с ошибками.

Прямое построение цифровых подписей основано на сложности аппроксимации кратчайшего вектора в идеальных решётках. Схема Любашёвского В. и Миссиансио Д., основанная на идеальных решётках, имеет гарантии безопасности даже в худшем случае и является наиболее асимптотически эффективной конструкцией, известной на сегодняшний день, также позволяющей генерировать сигнатуры и проверять алгоритмы, работающие за почти линейное время.

Одна из главных открытых проблем, которые были подняты в описанных выше работах, заключается в создании одноразовой подписи с аналогичной эффективностью, но основанной на более слабом допущении твёрдости. Например, было бы здорово обеспечить однократную подпись с защитой, основанную на сложности аппроксимации задачи кротчайшего вектора (SVP) (в идеальных решётках) с точностью до [math]\displaystyle{ \tilde{O}(n) }[/math].

Построение таких цифровых подписей основано на стандартном преобразовании одноразовых подписей (то есть подписей, которые позволяют надёжно подписывать одно сообщение) в общие схемы подписи вместе с новой конструкцией одноразовой подписи на основе решётки, безопасность которой, в конечном счёте, основана на наихудшей жёсткости аппроксимации кратчайшего вектора во всех решётках, соответствующий идеалам в кольце [math]\displaystyle{ \mathbb{Z}[x]/\langle f \rangle }[/math] для любого неприводимого многочлена [math]\displaystyle{ f }[/math].

Хэш-функция SWIFT

Хэш-функция достаточно эффективна и может быть вычислена асимптотически за [math]\displaystyle{ \tilde{O}(m) }[/math] время с использованием быстрого преобразования Фурье по комплексным числам. Однако на практике это несёт значительные накладные расходы. Набор криптографических хеш-функций с доказанной стойкостью SWIFFT, определённый Миссиансио Д. и Регевом, по сути, высоко оптимизированный вариант хэш-функции, описанной выше с использованием быстрого преобразования Фурье в [math]\displaystyle{ \mathbb{Z}_q }[/math]. Вектор f определён в [math]\displaystyle{ (1, 0,\dots , 0) \in \mathbb{Z}^n }[/math] для [math]\displaystyle{ n }[/math] равного степени 2, так что соответствующий полином [math]\displaystyle{ x^n + 1 }[/math] является неприводимым многочленом. Обнаружение коллизий функций SWIFFT равносильно нахождению коллизиций в базовой функции идеальной решётки[math]\displaystyle{ f_A }[/math]. Заявленное свойство коллизий SWIFFT поддерживается при наихудшем случае в задачах на идеальных решётках.

Алгоритм хэш-функции SWIFFT :

• Параметры: Натуральные числа [math]\displaystyle{ n, m, q, d }[/math] такие, что [math]\displaystyle{ n }[/math] степень двойки, [math]\displaystyle{ q }[/math] простое, [math]\displaystyle{ 2n \mid (q-1) }[/math] и [math]\displaystyle{ n \mid m }[/math].
• Ключ: [math]\displaystyle{ m/n }[/math] векторы [math]\displaystyle{ \tilde{a}_1, ... , \tilde{a}_{m/n} }[/math] выбраны независимо и случайным образом в [math]\displaystyle{ \mathbb{Z}_q^n }[/math].
• Вход: [math]\displaystyle{ m/n }[/math] вектора [math]\displaystyle{ y^{(1)}, \dots , y^{(m/n)} \in \lbrace 0, \dots , d-1 \rbrace ^n }[/math].
• Выход: вектор [math]\displaystyle{ \sum_{i=1}^{m/n} \tilde{a}^{(i)} \odot (\textbf{W}y^{(i)}) \in \mathbb{Z}_q^n }[/math], где [math]\displaystyle{ \odot }[/math] — компонентное векторное произведение, а [math]\displaystyle{ \textbf{W} \in \mathbb{Z}^{n \times n}_{q} }[/math] — обратимой матрицей над [math]\displaystyle{ \mathbb{Z}_q }[/math]

См. также

• Криптография на решётках
• Постквантовая криптография
• Задачи теории решёток

Литература

• J. Hoffstein, N. Howgrave-Graham, J. Pipher, J. H. Silverman, W. Whyte. Topics in Cryptology — CT-RSA 2003. — 2003. — С. 122—140.
• J. Hoffstein, J. Pipher, and J.H. Silverman. NTRU: A ring-based public key cryptosystem. — 1998. — С. 267—288.
• V. Lyubashevsky and D. Micciancio. Generalized Compact Knapsacks Are Collision Resistant. — 2006. — С. 144—155.
• Peikert, C., Rosen, A. Efficient Collision-Resistant Hashing from Worst-Case Assumptions on Cyclic Lattices. — 2006. — С. 145—166.
• Craig Gentry. Fully homomorphic encryption using ideal lattices. — 2009. — С. 169—178.
• Phong Q. Nguyen, Jacques Stern. Lattice Reduction in Cryptology: An Update // Proceedings of the 4th International Symposium on Algorithmic Number Theory. — Springer-Verlag, 2000. — С. 85–112. — ISBN 3-540-67695-3.

Ссылки

• Agrell E., Eriksson T., Vardy A., Zeger K. Closest Point Search in Lattices // IEEE Trans. Inform. Theory. — 2002. — Т. 48, вып. 8.
• Daniele Micciancio. The Shortest Vector Problem is {NP}-hard to approximate to within some constant // SIAM Journal on Computing. — 2001. — Т. 30, вып. 6. — С. 2008—2035.
• Lyubashevsky, V., Micciancio, D. Generalized compact knapsacks are collision resistant. — 2006. — С. 1—27.
• Lyubashevsky, V., Micciancio, D. Asymptotically efficient lattice-based digital signatures. — 2008.
• Lyubashevsky V. Lattice-Based Identification Schemes Secure Under Active Attacks. — 2008. — С. 1—18.
• Vadim Lyubashevsky, Chris Peikert and Oded Regev. On Ideal Lattices and Learning with Errors over Rings. — 2010. — С. 1—27.
• Léo Ducas. Advances on quantum cryptanalysis of ideal lattices. — 2017. — С. 184—189.
• Eva Bayer-Fluckiger. Ideal Lattices. — 2017. — С. 1—17.
• Identifying Ideal Lattices. Jintai Ding and Richard Lindner. — 2007. — С. 1—12.
• Jintai Ding, Xiang Xie, Xiaodong Lin. A Simple Provably Secure Key Exchange Scheme Based on the Learning with Errors Problem. — 2012. — С. 1—15.
• C. Peikert. Lattice Cryptography for the Internet. — 2014. — С. 1—25.
• V. Lyubashevsky. Lattice Signatures Without Trapdoors. — 2014. — С. 1—24.
• Damien Stehlé, Ron Steinfeld, Keisuke Tanaka and Keita Xagawa. Efficient public key encryption based on ideal lattices. — 2009. — С. 1—19.