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

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

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

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

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

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

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

• ${\displaystyle f}$ — должен быть неприводимым
• норма кольца ${\displaystyle \lVert g\rVert _{f}}$ не должна быть больше, чем норма ${\displaystyle \lVert g\rVert _{\infty }}$ для любого многочлена ${\displaystyle g}$

Лемма

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

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

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

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

${\displaystyle M={\begin{pmatrix}0&.&.&.&0\\&&&&.\\&&&&.\\I_{n-1}&&&&.\\&&&&0\end{pmatrix}}}$

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

${\displaystyle B_{1}={\begin{pmatrix}k&0\\0&1\end{pmatrix}}}$

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

${\displaystyle B_{2}={\begin{pmatrix}1&0\\0&k\end{pmatrix}}}$

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

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

${\displaystyle A={\begin{pmatrix}2&0\\0&1\end{pmatrix}}}$

${\displaystyle M={\begin{pmatrix}0&0\\1&0\end{pmatrix}}}$

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

${\displaystyle P={\begin{pmatrix}0&0\\1&0\end{pmatrix}}.}$

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

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

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

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

${\displaystyle h(b)=\sum _{i=1}^{m}\alpha _{i}\centerdot b_{i}}$, где ${\displaystyle m}$ есть выборка случайных элементов из ${\displaystyle a_{1},\dots ,a_{m}\in R=\mathbb {Z} _{p}[x]/\langle f\rangle }$, ${\displaystyle b=(b_{1},...,b_{m})\in D^{m}}$ .

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

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

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

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

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

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

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

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

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

• 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.