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

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

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

Введение [ править ]

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

Определение [ править ]

Обозначение [ править ]

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

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

Идеальная решетка представляет собой целое число решетки таким образом, что в течение некоторого унитарного многочлена степени и идеала .${\displaystyle {\mathcal {L}}(B)\subseteq \mathbb {Z} ^{n}}$${\displaystyle B=\lbrace g{\bmod {f}}:g\in I\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 \mathbb {Z} [x]/\langle f\rangle }$${\displaystyle \mathbb {Z} ^{n}}$

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

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

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

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

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

где матрица M равна

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

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

не является. с примером, приведенным Любашевским и Миччанчио. ^[5]${\displaystyle B_{2}}$${\displaystyle k=2}$

Выполняя алгоритм на нем и ссылаясь на базис как B, матрица 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}$

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

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

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

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

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

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

Основываясь на работе Любашевского и Миччанчио в 2006 году, Миччанчио и Регев ^[12] определили следующий алгоритм хеш-функций, основанный на идеальных решетках :

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

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

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

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

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

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

Цифровые подписи [ править ]

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

«ОТКАЗАТЬ», в противном случае.

Хэш-функция SWIFFT [ править ]

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

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

• Параметры: целые числа , равные степени 2, простому числу и .${\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},\ldots ,{\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 }$

Обучение с ошибками (LWE) [ править ]

Ring-LWE [ править ]

Проблема обучения с ошибками (LWE) оказалась такой же сложной, как и задачи решетки наихудшего случая, и послужила основой для многих криптографических приложений. Однако эти приложения неэффективны из-за неотъемлемых квадратичных накладных расходов при использовании LWE . Чтобы получить действительно эффективные приложения LWE , Любашевский, Пайкерт и Регев ^[3] определили подходящую версию задачи LWE в широком классе колец и доказали ее трудность при предположениях наихудшего случая об идеальных решетках в этих кольцах. Они назвали свою версию LWE ring-LWE.

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

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

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

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

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

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

Ideal-LWE [ править ]

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

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

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

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

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

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

учитывая , и ,${\displaystyle PK,SK\leftarrow {\mathsf {KeyGen}}(1^{\lambda })}$${\displaystyle y={\mathsf {Encrypt}}(PK,x)}$${\displaystyle y'={\mathsf {Eval}}(PK,C,y)}$

он держит это .${\displaystyle {\mathsf {Decrypt}}(SK,y')=C(x)}$

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

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

См. Также [ править ]

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

Ссылки [ править ]