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

Зафиксируем параметр ${\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}$.

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

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

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

Рассмотрим типичную задачу LWE^[3]: необходимо восстановить вектор ${\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}$ было бы просто: например, за полиномиальное время, используя метод Гаусса. Учёт же ошибки делает задачу значительно более трудной, поскольку с каждой итерацией ошибка возрастает и в конечном итоге достигает неуправляемых значений^[3].

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

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

Рассмотрим простой пример криптосистемы на открытых ключах, предложенной Регевом^[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][3] Одед Регев доказал корректность и защищенность данной криптосистемы при соответствующем выборе параметров.