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

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

Введение

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

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

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

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

Файл:Two-dimensional lattice with two bases.png

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

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

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

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

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

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

Лемма

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

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

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

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

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

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

$M=\left(\begin{array}{ccccc}0& .& .& .& 0\\ & & & & .\\ & & & & .\\ I_{n-1}& & & & .\\ & & & & 0\end{array}\right)$

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

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

$B_1=\left(\begin{array}{cc}k& 0\\ 0& 1\end{array}\right)$

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

$B_2=\left(\begin{array}{cc}1& 0\\ 0& k\end{array}\right)$

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

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

$A=\left(\begin{array}{cc}2& 0\\ 0& 1\end{array}\right)$

$M=\left(\begin{array}{cc}0& 0\\ 1& 0\end{array}\right)$

и наконец, произведение матриц $P=AMBmodd$ есть

$P=\left(\begin{array}{cc}0& 0\\ 1& 0\end{array}\right).$

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

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

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

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

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

Устойчивая к коллизиям хеш-функция — это функция заданная отображением $h_k$$:D\to 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\cdot b_i$, где $m$ есть выборка случайных элементов из $a_1,\dots ,a_m\in R={\mathbb{Z}}_p[x]/⟨f⟩$, $b=(b_1,...,b_m)\in D^m$ .

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

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

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

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

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

Построение таких цифровых подписей основано на стандартном преобразовании одноразовых подписей (то есть подписей, которые позволяют надёжно подписывать одно сообщение) в общие схемы подписи вместе с новой конструкцией одноразовой подписи на основе решётки, безопасность которой, в конечном счёте, основана на наихудшей жёсткости аппроксимации кратчайшего вектора во всех решётках, соответствующий идеалам в кольце $\mathbb{Z}[x]/⟨f⟩$ для любого неприводимого многочлена $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 \{0,\dots ,d-1{\}}^n$.
• Выход: вектор $\sum _{i=1}^{m/n}{\tilde{a}}^{(i)}\odot (\mathbf{\text{W}}{y}^{(i)})\in {\mathbb{Z}}_q^n$, где $\odot$ — компонентное векторное произведение, а $\mathbf{\text{W}}\in {\mathbb{Z}}_q^{n\times n}$ — обратимой матрицей над ${\mathbb{Z}}_q$

См. также

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

Литература

• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Книга

Ссылки

• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья