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

Используя данный алгоритм[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}$ является идеальной решёткой.

Устойчивая к коллизиям хеш-функция — это функция заданная отображением ${\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}}$