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

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

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

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

Определение

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

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

История появления

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

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

Пример задачи

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

${\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}}$

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

Криптографические приложения

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

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

Система на открытых ключах

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

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

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

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

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

Литература

• 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.

См. также

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