Меню Главная Случайная статья Настройки Идеальная решётка Материал из https://ru.wikipedia.org Идеальная решётка — определённая математическая структура, которая используется для уменьшения числа параметров, необходимых для описания решёток (представляющих собой свободные коммутативные группы конечного ранга). Данный вид решёток часто встречается во многих областях математики, в частности, в разделе теории чисел. Таким образом идеальные решётки более эффективны в применении, чем другие решётки, применяющихся в криптографии. Идеальные решётки используются в криптографических системах с открытым ключом NTRUEncrypt и NTRUSign для построения эффективных криптографических примитивов. Также идеальные решётки составляют фундаментальную основу квантовой криптографии, которая защищает от атак, связанных с квантовыми компьютерами. Содержание 1 Введение 2 Базовые понятия 3 Математическое определение идеальной решётки 4 Алгоритм идентификации идеальных решёток с базисами полного ранга 4.1 Пример использования алгоритма идентификации идеальных решёток с базисами полного ранга 5 Распространённые задачи теории решёток 6 Применение идеальных решёток 6.1 Хэш-функции, устойчивые к коллизиям 6.2 Цифровые подписи 6.3 Хэш-функция SWIFT 7 См. также 8 Примечания 9 Литература 10 Ссылки Введение Схемы 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}$, тогда правда, иначе ложь привести ${\displaystyle B}$ к эрмитовой форме ${\displaystyle A={\rm {adj}}(B)}$, то есть ${\displaystyle B}$ — присоединённая матрица, ${\displaystyle d=\det(B)}$ — детерминант и ${\displaystyle z=B_{(n,n)}}$ ${\displaystyle P=AMB{\bmod {\ }}d}$ если все столбцы ${\displaystyle P}$ кроме последнего нулевые тогда положить в ${\displaystyle c=P_{(\centerdot ,n)}}$ ненулевой столбец (а именно, последний столбец ${\displaystyle P}$) иначе вернуть ложь если ${\displaystyle z\mid c_{i}}$, то есть множество элементов z, удовлетворяющих ${\displaystyle c_{i}}$ для всех ${\displaystyle i=1,\dots ,n}$ тогда применить китайскую теорему об остатках для нахождения ${\displaystyle q^{\ast }\equiv \ (c/z){\bmod {\ }}(d/z)}$ и ${\displaystyle q^{\ast }\equiv 0{\bmod {\ }}z}$ иначе вернуть ложь если ${\displaystyle Bq^{\ast }\equiv 0{\bmod {\ }}(d/z)}$ тогда вернуть правду, ${\displaystyle q=Bq^{\ast }/d}$ иначе вернуть ложь Дополнение: матрица ${\displaystyle M}$ принимает вид ${\displaystyle M={\begin{pmatrix}0&.&.&.&0\\&&&&.\\&&&&.\\I_{n-1}&&&&.\\&&&&0\end{pmatrix}}}$