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

Обучение с ошибками (англ. Learning with errors, LWE) — задача нахождения многочлена с коэффициентами из определённого кольца вычетов, для которого дана система линейных уравнений, в которой есть ошибки (что делает простую вычислительную задачу сложной).

Представленная^[1] Одедом Регевым в 2005 году LWE оказалась удивительно универсальной основой для криптографических конструкций, в частности, для создания постквантовых криптографических алгоритмов^[1][2][3].

Вариант задачи обучения с ошибками, в котором многочлены рассматриваются в фактор-кольце по модулю заданного многочлена, называется обучение с ошибками в кольце.

Зафиксируем параметр ${\displaystyle n\geqslant 1}$, модуль ${\displaystyle q\geqslant 2}$ и распределение вероятности «ошибки» ${\displaystyle \chi }$ на ${\displaystyle {Z}_{q}}$. Пусть ${\displaystyle A_{\mathbf {s} ,\chi }}$ — распределение вероятности на ${\displaystyle \mathbb {Z} _{q}^{n}\times \mathbb {Z} _{q}}$, полученное выбором вектора ${\displaystyle \mathbf {a} \in \mathbb {Z} _{q}^{n}}$ равномерно случайно, выбором ошибки ${\displaystyle \mathbf {e} \in \mathbb {Z} _{q}}$ в соответствии с ${\displaystyle \chi }$ и полученным выражением ${\displaystyle (\mathbf {a} ,\langle \mathbf {a} ,\mathbf {s} \rangle +e)}$, где ${\displaystyle \textstyle \langle \mathbf {a} ,\mathbf {s} \rangle =\sum _{i=1}^{n}a_{i}s_{i}}$ и сложение производится по модулю ${\displaystyle q}$.

Говорят^[4], что алгоритм решает задачу ${\displaystyle \mathrm {LWE} _{q,\chi }}$, если для любого ${\displaystyle \mathbf {s} \in \mathbb {Z} _{q}^{n}}$, имея произвольное полиномиальное число независимых соотношений из ${\displaystyle A_{\mathbf {s} ,\chi }}$ он с высокой вероятностью выдаст ${\displaystyle s}$.

Возникновение концепции LWE отслеживается в работах Миклоша Айтаи^[англ.] и Синтии Дворк^[5]. Они описали первую криптосистему на открытых ключах, использующую криптографию на решётках, и последующие её улучшения и модификации^[6]. LWE не была в явном виде представлена в этих работах, однако тщательное исследование конструкции Айтаи—Дворк, упрощённой в работе Регева^[7], показывает^[4], что идеи LWE неявно возникают в этой работе.

Ранние исследования в этой области^[5][7] опирались на недостаточно хорошо изученную задачу нахождения уникального кратчайшего вектора. Долгое время было непонятно, можно ли заменить её более стандартными задачами на решётках. Позднее Крис Пейкерт^[8] и Вадим Любашевский с Даниэле Миччанчо выяснили^[9], что задача нахождения уникального кратчайшего вектора на самом деле является эквивалентом стандартной задачи на решетках GapSVP, что привело к более ясной картине в данной области.

Рассмотрим типичную задачу LWE^[4]: необходимо восстановить вектор ${\displaystyle x\in \mathbb {Z} _{q}^{n}}$, имея последовательность приближенных линейных уравнений по x. Например:

${\displaystyle {\begin{cases}14x_{1}+15x_{2}+5x_{3}+2x_{4}=8(mod17)\\13x_{1}+14x_{2}+14x_{3}+6x_{4}=16(mod17)\\\dots \\6x_{1}+7x_{2}+16x_{3}+2x_{4}=3(mod17),\\\end{cases}}}$

где каждое соотношение верно с некоторой маленькой дополнительной ошибкой, скажем, ±${\displaystyle 1}$, и наша цель восстановить ${\displaystyle x}$(в данном примере ${\displaystyle x=(0,13,9,11)}$). Без ошибки найти ${\displaystyle x}$ было бы просто: например, за полиномиальное время, используя метод Гаусса. Учёт же ошибки делает задачу значительно более трудной, поскольку с каждой итерацией ошибка возрастает и в конечном итоге достигает неуправляемых значений^[4].

Диапазон криптографических приложений LWE становится в последнее время достаточно широким. Кроме приведенного ниже примера криптосистемы, существуют и более эффективные схемы^[2][10]. Более того, использование Ring-LWE может сделать систему реально применимой^[11].

LWE может использоваться как основа для создания криптографических схем, предоставляющих полностью гоморфное шифрование. Например, она использовалась в реализации открытой для общественного пользования библиотеки FHEW^[12].

Рассмотрим простой пример криптосистемы на открытых ключах, предложенной Регевом^[1]. Она опирается на сложность решения задачи LWE. Система описывается следующими числами: ${\displaystyle n}$-секретный параметр, ${\displaystyle m}$-размерность, ${\displaystyle q}$-модуль и распределением вероятности${\displaystyle \chi \in \mathbb {Z} _{q}}$. Для гарантии безопасности и корректности системы следует выбрать следующие параметры:

• ${\displaystyle q\geq 2}$, простое число между ${\displaystyle n^{2}}$ и ${\displaystyle 2n^{2}}$
• ${\displaystyle m=(1+\epsilon )(n+1)\log {q}}$ для произвольной константы ${\displaystyle \epsilon }$
• ${\displaystyle \alpha (n)=1/{\sqrt {n}}\log ^{2}{n}}$

Тогда криптосистемы определяется следующим образом:

• Секретный ключ: Секретный ключ это ${\displaystyle \mathbf {s} \in \mathbb {Z} _{q}^{n}}$ выбранный произвольно.
• Открытый ключ: Выберем ${\displaystyle m}$ векторов ${\displaystyle a_{1},\ldots ,a_{m}\in \mathbb {Z} _{q}^{n}}$ произвольно и независимо. Выберем допустимые ошибки ${\displaystyle e_{1},\ldots ,e_{m}\in \mathbb {Z} _{q}}$ независимо в соответствии с распределением ${\displaystyle \chi }$. Открытый ключ состоит из ${\displaystyle (a_{i},b_{i}=\langle a_{i},\mathbf {s} \rangle /q+e_{i})_{i=1}^{m}}$
• Шифрование: Шифрование бита ${\displaystyle x\in \{0,1\}}$ производится так: выбирается случайное подмножество ${\displaystyle S}$ из ${\displaystyle [m]}$ и определяется шифр ${\displaystyle Enc(x)}$ как ${\displaystyle (\sum _{i\in S}a_{i},x/2+\sum _{i\in S}b_{i})}$
• Расшифрование: Расшифровка ${\displaystyle (a,b)}$ это ${\displaystyle 0}$ в случае если ${\displaystyle b-\langle a,\mathbf {s} \rangle /q}$ ближе к ${\displaystyle 0}$, чем ${\displaystyle {\frac {1}{2}}}$, и ${\displaystyle 1}$ в противном случае.

В своих работах^[1][4] Одед Регев доказал корректность и защищенность данной криптосистемы при соответствующем выборе параметров.

• Post-Quantum Cryptography (неопр.). — Springer, 2008. — С. 245. — ISBN 978-3540887010.
• Peikert, Chris. Lattice Cryptography for the Internet (неопр.) / Mosca, Michele. — Springer International Publishing, 2014. — С. 197—219. — (Lecture Notes in Computer Science). — ISBN 978-3-319-11658-7.
• Chen, Yuanmi; Phong Q., Nguyen. BKZ 2.0: Better Lattice Security Estimates (англ.). — Springer Berlin Heidelberg, 2011. — P. 1—20.

• Обмен ключами при обучении с ошибками
• Постквантовая криптография
• Криптография на решётках