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

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

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

Определение

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

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

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

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

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

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

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

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

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

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

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

Рассмотрим простой пример криптосистемы на открытых ключах , предложенной Регевом . Она опирается на сложность решения задачи 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}$ в противном случае.

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

Примечания

Литература

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

См. также

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