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

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

Введение

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

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

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

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

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

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

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

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

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

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

Лемма

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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