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

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

Идеальные решетки также составляют основу устойчивой к атакам квантовых компьютеров криптографии, основанной на кольцевом обучении с ошибками. Эти криптосистемы доказуемо безопасны при условии, что задача кратчайшего вектора (SVP) сложна в этих идеальных решетках.

Введение

В общих чертах идеальные решетки — это решетки, соответствующие идеалам в кольцах вида $\mathbb {Z} [x]/\langle f\rangle$ для некоторого неприводимого многочлена $f$ степени $n$. Все определения идеальных решеток из предыдущих работ являются примерами следующего общего понятия: пусть $R$ кольцо , которого группа изоморфна ​ аддитивная $\mathbb {Z} ^{n}$ (т.е. это бесплатно $\mathbb {Z}$-модуль ранга ​ $n$), и пусть $\sigma$ — аддитивное изоморфизма отображение $R$ к какой-то решетке $\sigma (R)$ в $n$-мерное реальное векторное пространство (например, $\mathbb {R} ^{n}$). Семейство идеальных решеток кольца $R$ под вложением $\sigma$ множество всех решеток $\sigma (I)$, где $I$ является идеалом в $R.$

Определение

Обозначения

Позволять $f\in \mathbb {Z} [x]$ быть моническим многочленом степени $n$и рассмотрим факторкольцо $\mathbb {Z} [x]/\langle f\rangle$.

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

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

Связанные свойства

Оказывается, соответствующие свойства $f$ чтобы результирующая функция была устойчивой к коллизиям:

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

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

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

Дин и Линднер доказал, что отличить идеальные решетки от общих можно за полиномиальное время, и показал, что на практике случайно выбранные решетки никогда не бывают идеальными. Они рассматривали только случай, когда решетка имеет полный ранг, т.е. базис состоит из $n$ линейные независимые векторы . Это не фундаментальное ограничение, поскольку Любашевский и Миччанчо показали, что если решетка идеальна относительно неприводимого монического полинома, то она имеет полный ранг, как указано в лемме выше.

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

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

1. Трансформировать $B$ в HNF
2. Рассчитать $A={\rm {adj}}(B)$, $d=\det(B)$, и $z=B_{(n,n)}$
3. Рассчитать продукт $P=AMB{\bmod {d}}$
4. если только последний столбец P ненулевой, то
5. набор $c=P_{(\centerdot ,n)}$ чтобы сравняться с этим столбцом
6. иначе верните ложь
7. если $z\mid c_{i}$ для $i=1,\ldots ,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&\cdot &\cdot &\cdot &0\\&&&&\cdot \\&&&&\cdot \\I_{n-1}&&&&\cdot \\&&&&0\end{pmatrix}}$

Используя этот алгоритм, можно увидеть, что многие решетки не являются идеальными . Например, пусть $n=2$ и $k\in \mathbb {Z} \smallsetminus \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, матрица 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$ будет охватывать идеальную решетку .

Использование в криптографии

Маленький мальчик ввел класс структурированных циклических решеток, соответствующих идеалам в кольцах полиномов. $\mathbb {Z} [x]/(x^{n}-1)$и представил первую доказуемо безопасную одностороннюю функцию, основанную на жесткости ограничения Poly( n )-SVP в наихудшем случае на циклические решетки. (Задача γ -СВП состоит в вычислении ненулевого вектора заданной решетки, норма которого не более чем в γ раз превышает норму кратчайшего ненулевого вектора решетки.) В то же время благодаря своей алгебраической структура, эта односторонняя функция имеет высокую эффективность, сравнимую со NTRU . схемой ${\tilde {O}}(n)$ время оценки и стоимость хранения). Впоследствии Любашевский и Миччанчо и независимо Пейкерт и Розен показал, как изменить функцию Миччанчо, чтобы построить эффективную и доказуемо безопасную устойчивую к коллизиям хеш-функцию, . Для этого они ввели более общий класс идеальных решеток , соответствующих идеалам в кольцах полиномов. $\mathbb {Z} [x]/f(x)$. Устойчивость к столкновению зависит от жесткости ограничения Poly(n)-SVP идеальными решетками (называемыми Poly( n )-Ideal-SVP). Задача поиска коллизий в среднем случае — это естественная вычислительная задача, называемая Ideal-SIS, которая, как было показано, столь же сложна, как и экземпляры Ideal-SVP для наихудшего случая. доказуемо безопасные и эффективные схемы подписи на основе идеальных решеток . Также были предложены но построение эффективного доказуемо безопасного шифрования с открытым ключом на основе идеальных решеток было интересной открытой проблемой .

Фундаментальная идея использования LWE и Ring LWE для обмена ключами была предложена и подана в Университете Цинциннати в 2011 году Джинтаем Дином и предоставила современное описание квантовоустойчивого обмена ключами с использованием Ring LWE . Бумага появился в 2012 году после подачи предварительной заявки на патент в 2012 году. В 2014 году Пейкерт представила ключевую транспортную схему, следующую той же базовой идее, что и Дин, где также используется новая идея отправки дополнительного сигнала для округления в конструкции Дина. Цифровая подпись с использованием тех же концепций была сделана несколькими годами ранее Вадимом Любашевским в книге «Решетчатые подписи без лазеек». Совместная работа Пейкерта и Любашевского представляет собой набор алгоритмов защиты от квантовых атак на основе Ring-LWE с таким же снижением безопасности.

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

Основная польза идеальных решеток в криптографии связана с тем, что очень эффективные и практичные устойчивые к коллизиям, хэш-функции, могут быть построены на основе сложности поиска приближенного кратчайшего вектора в таких решетках. Независимо созданные устойчивые к коллизиям хэш-функции . Пейкертом и Розеном а также Любашевский и Миччанчо, основанные на идеальных решетках (обобщение циклических решеток) и обеспечившие быструю и практическую реализацию. Эти результаты проложили путь к другим эффективным криптографическим конструкциям, включая схемы идентификации и подписи.

Любашевский и Миччанчо предоставил конструкции эффективных, устойчивых к коллизиям хеш-функций , безопасность которых может быть доказана на основе сложности наихудшего случая задачи кратчайшего вектора для идеальных решеток . Они определили семейства хэш-функций следующим образом: Учитывая кольцо $R=\mathbb {Z} _{p}[x]/\langle f\rangle$, где $f\in \mathbb {Z} _{p}[x]$ — унитарный неприводимый полином степени $n$ и $p$ это целое число примерно порядка $n^{2}$, генерировать $m$ случайные элементы $a_{1},\dots ,a_{m}\in R$, где $m$ является константой. Заказанный $m$-кортеж $h=(a_{1},\ldots ,a_{m})\in R^{m}$ определяет хеш-функцию. Он будет отображать элементы в $D^{m}$, где $D$ представляет собой стратегически выбранное подмножество $R$, к $R$. Для элемента $b=(b_{1},\ldots ,b_{m})\in D^{m}$, хэш $h(b)=\sum _{i=1}^{m}\alpha _{i}\centerdot b_{i}$. Здесь размер ключа ( хеш-функции ) равен $O(mn\log p)=O(n\log n)$, и операция $\alpha _{i}\centerdot b_{i}$ можно сделать вовремя $O(n\log n\log \log n)$ с помощью быстрого преобразования Фурье (БПФ) , при соответствующем выборе полинома $f$. С $m$ является константой,хеширование требует времени $O(n\log n\log \log n)$. Они доказали, что хеш-функций семейство устойчиво к коллизиям , показав, что если существует алгоритм с полиномиальным временем , который с немалой вероятностью успешно находит $b\neq b'\in D^{m}$ такой, что $h(b)=h(b')$, для случайно выбранной хэш-функции $h\in R^{m}$, то определенный называемая « задача о кратчайшем векторе », разрешима за полиномиальное время для любого идеала кольца задача , $\mathbb {Z} [x]/\langle f\rangle$.

На основе работы Любашевского и Миччанчо 2006 года, Миччанчо и Регев. определил следующий алгоритм хэш-функций на основе идеальных решеток :

• Параметры: Целые числа $q,n,m,d$ с $n\mid m$, и вектор f $\in \mathbb {Z} ^{n}$.
• Ключ: $m/n$ векторы $a_{1},\ldots ,a_{m/n}$ выбираются независимо и равномерно случайным образом в $\mathbb {Z} _{q}^{n}$.
• Хэш-функция: $f_{A}:\lbrace 0,\ldots ,d-1\rbrace ^{m}\longrightarrow \mathbb {Z} _{q}^{n}$ данный $f_{A}(y)=[F\ast a_{1}|\ldots |F\ast a_{m/n}]y{\bmod {\ }}q$.

Здесь $n,m,q,d$ — параметры, f — вектор в $\mathbb {Z} ^{n}$ и $A$ представляет собой блок-матрицу со структурированными блоками $A^{(i)}=F\ast a^{(i)}$.

Нахождение коротких векторов в $\Lambda _{q}^{\perp }([F\ast a_{1}|\ldots |F\ast a_{m/n}])$ в среднем (даже при использовании только обратного полиномавероятность) так же сложно, как и решение различных решеточных задач (таких как приближенное SVP и SIVP) в худшем случае.случай над идеальными решетками при условии, что вектор f удовлетворяет следующим двум свойствам:

• Для любых двух единичных векторов u , v вектор [F∗u]v имеет малый (скажем, полиномиальный от $n$, обычно $O({\sqrt {n}}))$ норма.
• Полином $f(x)=x^{n}+f_{n}x^{n-1}+\cdots +f_{1}\in \mathbb {Z} [x]$ неприводимо . по целым числам, т. е. не учитывается в произведении целых многочленов меньшей степени

Первому свойству удовлетворяет вектор $\mathbf {F} =(-1,0,\ldots ,0)$ соответствующие циркулянтным матрицам ,поскольку все координаты [F∗u]v ограничены единицей и, следовательно, $\lVert [{\textbf {F}}\ast {\textbf {u}}]{\textbf {v}}\rVert \leq {\sqrt {n}}$. Однако полином $x^{n}-1$ соответствующий $\mathbf {f} =(-1,0,\ldots ,0)$ не является неприводимым, поскольку он учитывает $(x-1)(x^{n-1}+x^{n-2}+\cdots +x+1)$, и именно поэтому коллизии можно эффективно обнаруживать. Так, $\mathbf {f} =(-1,0,\ldots ,0)$ не является хорошим выбором для получения устойчивых к коллизиям хеш-функций , но возможны многие другие варианты. Например, некоторые варианты f , для которых удовлетворяются оба свойства (и, следовательно, приводят к устойчивым к коллизиям хеш-функциям с гарантиями безопасности в наихудшем случае):

• $\mathbf {f} =(1,\ldots ,1)\in \mathbb {Z} ^{n}$ где $n+1$ является простым, и
• $\mathbf {f} =(1,0,\ldots ,0)\in \mathbb {Z} ^{n}$ для $n$ равна степени 2.

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

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

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

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

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

Алгоритм генерации ключей: Входные данные : $1^{n}$, неприводимый полином $f\in \mathbb {Z}$ степени $n$.

1. Набор $p\longleftarrow (\varphi n)^{3}$, $m\longleftarrow \lceil \log n\rceil$, $R\longleftarrow \mathbb {Z} _{p}[x]/\langle f\rangle$
2. За все позитивное $i$, пусть наборы $DK_{i}$ и $DL_{i}$ быть определен как:

$DK_{i}=\lbrace {\hat {y}}\in R^{m}$ такой, что $\lVert {\hat {y}}\rVert _{\infty }\leq 5ip^{1/m}\rbrace$

$DL_{i}=\lbrace {\hat {y}}\in R^{m}$ такой, что $\lVert {\hat {y}}\rVert _{\infty }\leq 5in\varphi p^{1/m}\rbrace$

1. Выбирайте равномерно случайный $h\in {\mathcal {H}}_{R,m}$
2. Выберите равномерно случайную строку $r\in \lbrace 0,1\rbrace ^{\lfloor \log ^{2}n\rfloor }$
3. Если $r=0^{\lfloor \log ^{2}n\rfloor }$ затем
4. Набор $j=\lfloor \log ^{2}n\rfloor$
5. еще
6. Набор $j$ на позицию первой единицы в строке $r$
7. конец, если
8. Выбирать ${\hat {k}},{\hat {l}}$ независимо и равномерно случайным образом от $DK_{j}$ и $DL_{j}$ соответственно
9. Ключ подписи: $({\hat {k}},{\hat {l}})$. Ключ проверки: $(h,h({\hat {k}}),h({\hat {l}}))$

Алгоритм подписания:

Ввод: Сообщение $z\in R$ такой, что $\lVert z\rVert _{\infty }\leq 1$; ключ подписи $({\hat {k}},{\hat {l}})$

Выход: ${\hat {s}}\longleftarrow {\hat {k}}z+{\hat {l}}$

Алгоритм проверки:

Ввод: Сообщение $z$; подпись ${\hat {s}}$; ключ проверки $(h,h({\hat {k}}),h({\hat {l}}))$

Вывод: «ПРИНЯТЬ», если $\lVert {\hat {s}}\rVert _{\infty }\leq 10\varphi p^{1/m}n\log ^{2}n$ и ${\hat {s}}={\hat {k}}z+{\hat {l}}$

«ОТКЛОНИТЬ», иначе.

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

Хэш -функция весьма эффективна и может быть вычислена асимптотически в ${\tilde {O}}(m)$ время с помощью быстрого преобразования Фурье (БПФ) над комплексными числами . Однако на практике это влечет за собой значительные накладные расходы. Семейство , SWIFFT хэш-функций определенное Мичиансио и Регевом. по сути, это высокооптимизированный вариант приведенной выше хэш-функции с использованием (БПФ) в $\mathbb {Z} _{q}$. Вектор f имеет значение $(1,0,\dots ,0)\in \mathbb {Z} ^{n}$ для $n$ равен степени 2, так что соответствующий полином $x^{n}+1$ является нередуцируемым .Позволять $q$ быть простым числом таким, что $2n$ делит $q-1$, и пусть ${\textbf {W}}\in \mathbb {Z} _{q}^{n\times n}$ быть обратимой матрицей над $\mathbb {Z} _{q}$ будет выбран позже. SWIFFT отображает Хэш-функция ключ ${\tilde {a}}^{(1)},\ldots ,{\tilde {a}}^{(m/n)}$ состоящий из $m/n$ векторы выбираются равномерно из $\mathbb {Z} _{q}^{n}$ и вход $y\in \lbrace 0,\ldots ,d-1\rbrace ^{m}$ к ${\textbf {W}}^{\centerdot }f_{A}(y){\bmod {\ }}q$ где ${\textbf {A}}=[{\textbf {F}}\ast \alpha ^{(1)},\ldots ,{\textbf {F}}\ast \alpha ^{(m/n)}]$ все как прежде и $\alpha ^{(i)}={\textbf {W}}^{-1}{\tilde {a}}^{(i)}{\bmod {q}}$.Умножение на обратимую матрицу ${\textbf {W}}^{-1}$ отображает равномерно выбранный ${\tilde {a}}\in \mathbb {Z} _{q}^{n}$ к единообразно выбранному $\alpha \in \mathbb {Z} _{q}^{n}$. Более того, ${\textbf {W}}^{\centerdot }f_{A}(y)={\textbf {W}}^{\centerdot }f_{A}(y'){\pmod {q}}$ тогда и только тогда, когда $f_{A}(y)=f_{A}(y'){\pmod {q}}$.Вместе эти два факта устанавливают, что обнаружение столкновений в SWIFFT эквивалентно обнаружению столкновений в базовой идеальной решеточной функции. $f_{A}$, а заявленное по сопротивлению столкновению свойство SWIFFT подтверждается связью с задачами наихудшего случая на идеальных решетках .

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

• Параметры: Целые числа $n,m,q,d$ такой, что $n$ это степень 2, $q$ является простым, $2n\mid (q-1)$ и $n\mid m$.
• Ключ: $m/n$ векторы ${\tilde {a}}_{1},\ldots ,{\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$ — покомпонентное векторное произведение.

Обучение с ошибками (LWE)

Кольцо-LWE

Было показано, что проблема обучения с ошибками (LWE) столь же сложна, как и проблемы решетки в худшем случае, и послужила основой для многих криптографических приложений. Однако эти приложения неэффективны из-за присущих использованию LWE квадратичных накладных расходов . Чтобы получить по-настоящему эффективные приложения LWE , Любашевский, Пейкерт и Регев определил подходящую версию проблемы ЛВЕ в широком классе колец и доказал ее трудность при предположениях наихудшего случая об идеальных решетках в этих кольцах. они назвали Свою версию LWE Ring-LWE.

Позволять $f(x)=x^{n}+1\in \mathbb {Z} [x]$, где параметр безопасности $n$ является степенью 2, что делает $f(x)$ несводимое к рациональным. (Этот конкретный $f(x)$ происходит из семейства круговых многочленов , которые играют особую роль в данной работе).

Позволять $R=\mathbb {Z} [x]/\langle f(x)\rangle$ — кольцо целых многочленов по модулю $f(x)$. Элементы $R$ (т.е. остатки образуют $f(x)$) обычно представляются целыми полиномами степени меньше $n$. Позволять $q\equiv 1{\bmod {2}}n$ быть достаточно большим общедоступным простым модулем (ограниченным многочленом от $n$), и пусть $R_{q}=R/\langle q\rangle =\mathbb {Z} _{q}[x]/\langle f(x)\rangle$ — кольцо целых многочленов по модулю обоих $f(x)$ и $q$. Элементы $R_{q}$ могут быть представлены полиномами степени меньше $n$-коэффициенты которого взяты из $\lbrace 0,\dots ,q-1\rbrace$.

В описанном выше кольце проблема R-LWE может быть описана следующим образом.Позволять $s=s(x)\in R_{q}$ быть равномерно случайным элементом кольца, который хранится в секрете. Аналогично стандартному LWE, цель злоумышленника состоит в том, чтобы отличить произвольное количество (независимых) «случайных шумных кольцевых уравнений» от действительно однородных. Более конкретно, зашумленные уравнения имеют вид $(a,b\approx a\centerdot s)\in R_{q}\times R_{q}$, где a — равномерно случайное произведение $a\centerdot s$ возмущен некоторой «маленькой» случайной ошибкой, выбранной из определенного распределения по $R$.

Они дали квантовую редукцию от приближенного СВП (в худшем случае) на идеальных решетках в $R$ к поисковой версии Ring-LWE, целью которой является восстановление секрета $s\in R_{q}$ (с большой вероятностью для любого $s$) от сколь угодно большого количества шумных изделий. Этот результат следует общей схеме итерационной квантовой редукции Регева для общих решеток: но идеальные решетки создают несколько новых технических препятствий как в «алгебраическом», так и в «геометрическом» компонентах редукции. Они использовал алгебраическую теорию чисел, в частности, каноническое вложение числового поля и китайскую теорему об остатках, чтобы преодолеть эти препятствия. Они получили следующую теорему:

Теорема. Пусть $K$ — произвольное числовое поле степени $n$. Позволять $\alpha =\alpha (n)\in (0,1)$ произволен, и пусть (рациональный) целочисленный модуль $q=q(n)\geq 2$ быть таким, что $\alpha \centerdot q\geq \omega ({\sqrt {\log n}})$. Существует вероятностное полиномиальное квантовое сокращение от $K$- $DGS_{\gamma }$ к ${\mathcal {O}}_{K}$- $LWE_{q,\Psi \leq \alpha }$, где $\gamma =\eta _{\epsilon }(I)\centerdot \omega ({\sqrt {\log n}})/\alpha$.

В 2013 году Гунейсу, Любашевский и Попплман предложили схему цифровой подписи, основанную на задаче кольцевого обучения с ошибками. В 2014 году Пейкерт представил кольцевое обучение с обменом ключами с ошибками (RLWE-KEX) в своей статье «Решетчатая криптография для Интернета». Дальнейшее развитие это получило в работах Сингха.

Идеал-LWE

Штеле, Штайнфельд, Танака и Хагава определил структурированный вариант проблемы LWE (Ideal-LWE) для описания эффективной схемы шифрования с открытым ключом, основанной на наихудшей сложности приближенного SVP в идеальных решетках. Это первая схема шифрования с открытым ключом, защищенная CPA, безопасность которой зависит от стойкости наихудших случаев шифрования. ${\tilde {O}}(n^{2})$-Идеал-СВП против субэкспоненциальных квантовых атак. Он достигает асимптотически оптимальной эффективности: длина открытого/закрытого ключа равна ${\tilde {O}}(n)$ бит, а амортизированная стоимость шифрования/дешифрования равна ${\tilde {O}}(1)$ битовые операции на бит сообщения (шифрование ${\tilde {\Omega }}(n)$ бит сразу, за раз ${\tilde {O}}(n)$ расходы). Предположение безопасности здесь заключается в том, что ${\tilde {O}}(n^{2})$-Идеальная-СВП не может быть решена ни одним субэкспоненциальным квантовым алгоритмом. Примечательно, что это сильнее, чем стандартные предположения о безопасности криптографии с открытым ключом . С другой стороны, в отличие от большей части криптографии с открытым ключом , криптография на основе решетки обеспечивает защиту от субэкспоненциальных квантовых атак.

Большинство криптосистем, основанных на общих решетках, полагаются на среднюю сложность обучения с ошибками (LWE) . Их схема основана на структурированном варианте LWE, который они называют Ideal-LWE. Им нужно было внедрить некоторые методы, позволяющие обойти две основные трудности, возникающие из-за ограничения идеальными решетками. Во-первых, все предыдущие криптосистемы, основанные на неструктурированных решетках, используют классическую редукцию Регева от наихудшего случая к среднему случаю от задачи декодирования на ограниченном расстоянии (BDD) к LWE (это классический шаг квантовой редукции от SVP к LWE ). Это сокращение использует неструктурированность рассматриваемых решеток и, похоже, не распространяется на структурированные решетки, участвующие в Ideal-LWE. В частности, вероятностная независимость строк матриц LWE позволяет рассматривать одну строку. Во-вторых, другой ингредиент, использовавшийся в предыдущих криптосистемах, а именно сведение Регева от вычислительного варианта LWE к варианту принятия решений, также, похоже, не работает для Ideal-LWE: он опирается на вероятностную независимость столбцов LWE- матрицы.

Чтобы преодолеть эти трудности, они избегали классического этапа редукции. Вместо этого они использовали квантовый шаг для создания новой квантовой редукции среднего случая от SIS (задача поиска столкновений в среднем случае) к LWE . Он также работает от Ideal-SIS до Ideal-LWE. В сочетании с сокращением от идеального SVP наихудшего случая до идеального SIS среднего случая они получили квантовое сокращение от идеального SVP до идеального LWE. Это показывает сложность вычислительного варианта Ideal-LWE. Поскольку им не удалось достичь уровня сложности варианта принятия решения, они использовали общую хардкорную функцию для получения псевдослучайных битов для шифрования. Вот почему им нужно было принять экспоненциальную жесткость СВП .

Полностью гомоморфное шифрование

Схема полностью гомоморфного шифрования (FHE) — это схема, которая позволяет выполнять вычисления над зашифрованными данными без необходимости предварительной расшифровки. Проблема построения полностью гомоморфной схемы шифрования была впервые поставлена ​​Ривестом, Адлеманом и Дертузосом. в 1978 году, вскоре после изобретения RSA Ривестом, Адлеманом и Шамиром.

Схема шифрования $\varepsilon =({\mathsf {KeyGen}},{\mathsf {Encrypt}},{\mathsf {Decrypt}},{\mathsf {Eval}})$ гомоморфен схемам из ${\mathcal {C}}$ если для любой схемы $C\in {\mathcal {C}}$,

данный $PK,SK\leftarrow {\mathsf {KeyGen}}(1^{\lambda })$, $y={\mathsf {Encrypt}}(PK,x)$, и $y'={\mathsf {Eval}}(PK,C,y)$,

он утверждает, что ${\mathsf {Decrypt}}(SK,y')=C(x)$.

$\varepsilon$ полностью гомоморфен, если он гомоморфен всем схемам размера $\operatorname {poly} (\lambda )$ где $\lambda$ — параметр безопасности схемы.

В 2009 году Джентри предложил первое решение проблемы построения полностью гомоморфной схемы шифрования. Его схема основывалась на идеальных решетках.

См. также

• Решеточная криптография
• Гомоморфное шифрование
• Кольцевое обучение с ошибками обмена ключами
• Постквантовая криптография
• Задача о коротком целочисленном решении