Русская Википедия:Обучение с ошибками
Обучение с ошибками (Шаблон:Lang-en) — задача нахождения многочлена с коэффициентами из определённого кольца вычетов, для которого дана система линейных уравнений, в которой есть ошибки (что делает простую вычислительную задачу сложной).
Представленная[1] Одедом Регев в 2005 году LWE оказалась удивительно универсальной основой для криптографических конструкций, в частности, для создания постквантовых криптографических алгоритмов[1][2].
Вариант задачи обучения с ошибками, в котором многочлены рассматривается в факторкольце многочленов по определённому многочлену, называется обучение с ошибками в кольце.
Определение
Зафиксируем параметр <math>n \geqslant 1</math>, модуль <math>q \geqslant 2</math> и распределение вероятности «ошибки» <math>\chi</math> на <math>{Z}_q </math>. Пусть <math>A_{\mathbf{s},\chi}</math> — распределение вероятности на <math>\mathbb{Z}_q^n \times \mathbb{Z}_q</math>, полученное выбором вектора <math>\mathbf{a}\in \mathbb{Z}_q^n</math> равномерно случайно, выбором ошибки <math>\mathbf{e} \in \mathbb{Z}_q</math> в соответствии с <math>\chi</math> и полученным выражением <math>(\mathbf{a},\langle \mathbf{a},\mathbf{s} \rangle + e)</math>, где <math>\textstyle \langle \mathbf{a},\mathbf{s} \rangle = \sum_{i=1}^n a_i s_i</math> и сложение производится по модулю <math>q</math>.
Говорят[3], что алгоритм решает задачу <math>\mathrm{LWE}_{q,\chi}</math>, если для любого <math>\mathbf{s} \in \mathbb{Z}_q^n</math>, имея произвольное полиномиальное число независимых соотношений из <math>A_{\mathbf{s},\chi}</math> он с высокой вероятностью выдаст <math>s</math>.
История появления
Возникновение концепции LWE отслеживается в работах Миклоша Айтаи и Синтии Дворк[4]. Они описали первую криптосистему на открытых ключах, использующую криптографию на решётках, и последующие её улучшения и модификации[5]. LWE не была в явном виде представлена в этих работах, однако тщательное исследование конструкции Айтаи—Дворк, упрощённой в работе Регева[6], показывает[3], что идеи LWE неявно возникают в этой работе.
Стоит отметить, что ранние исследования в этой области[4][6] опирались на недостаточно хорошо изученную задачу нахождения уникального кратчайшего вектора. Долгое время было непонятно, можно ли заменить её более стандартными задачами на решётках. Позднее Крис Пейкерт[7] и Вадим Любашевский с Даниэле Миччанчо выяснили[8], что задача нахождения уникального кратчайшего вектора на самом деле является эквивалентом стандартной задачи на решетках GapSVP, что привело к более ясной картине в данной области.
Пример задачи
Рассмотрим типичную задачу LWE[3]: необходимо восстановить вектор <math>x\in \mathbb{Z}_q^n</math>, имея последовательность приближенных линейных уравнений по x. Например:
- <math>
\begin{cases}
14x_1 + 15x_2 + 5x_3 + 2x_4 = 8 (mod 17)\\ 13x_1 + 14x_2 + 14x_3 + 6x_4 = 16 (mod 17)\\ \dots\\ 6x_1 + 7x_2 + 16x_3 + 2x_4 = 3 (mod 17),\\
\end{cases} </math> где каждое соотношение верно с некоторой маленькой дополнительной ошибкой, скажем, ±<math>1</math>, и наша цель восстановить <math>x</math>(в данном примере <math>x= (0, 13, 9, 11)</math>). Без ошибки найти <math>x</math> было бы просто: например, за полиномиальное время, используя метод Гаусса. Учёт же ошибки делает задачу значительно более трудной, поскольку с каждой итерацией ошибка возрастает и в конечном итоге достигает неуправляемых значений[3].
Криптографические приложения
Диапазон криптографических приложений LWE становится в последнее время достаточно широким. Кроме приведенного ниже примера криптосистемы, существуют и более эффективные схемы[2][9]. Более того, использование Ring-LWE может сделать систему реально применимой[10].
Стоит особенно отметить, что LWE может использоваться как основа для создания криптографических схем, предоставляющих полностью гоморфное шифрование. Например, она использовалась в реализации открытой для общественного пользования библиотеки FHEW[11].
Система на открытых ключах
Рассмотрим простой пример криптосистемы на открытых ключах, предложенной Регевом[1]. Она опирается на сложность решения задачи LWE. Система описывается следующими числами: <math>n</math>-секретный параметр, <math>m</math>-размерность, <math>q</math>-модуль и распределением вероятности<math>\chi \in \mathbb{Z}_q</math>. Для гарантии безопасности и корректности системы следует выбрать следующие параметры:
- <math>q \geq 2 </math>, простое число между <math>n^2</math> и <math>2n^2</math>
- <math>m=(1+\epsilon)(n+1) \log{q}</math> для произвольной константы <math>\epsilon</math>
- <math>\alpha(n) = 1/\sqrt{n}\log^2{n}</math>
Тогда криптосистемы определяется следующим образом:
- Секретный ключ: Секретный ключ это <math>\mathbf{s}\in \mathbb{Z}^n_q</math> выбранный произвольно.
- Открытый ключ: Выберем <math>m</math> векторов <math>a_1,\ldots,a_m \in \mathbb{Z}^n_q</math> произвольно и независимо. Выберем допустимые ошибки <math>e_1,\ldots,e_m \in \mathbb{Z}_q</math> независимо в соответствии с распределением <math>\chi</math>. Открытый ключ состоит из <math>(a_i,b_i=\langle a_i,\mathbf{s} \rangle/q + e_i)^m_{i=1}</math>
- Шифрование: Шифрование бита <math>x \in \{0,1\}</math> производится так: выбирается случайное подмножество <math>S</math> из <math>[m]</math> и определяется шифр <math>Enc(x)</math> как <math>(\sum_{i \in S} a_i, x/2 + \sum_{i \in S} b_i)</math>
- Расшифрование: Расшифровка <math>(a,b)</math> это <math>0</math> в случае если <math>b-\langle a, \mathbf{s} \rangle/q</math> ближе к <math>0</math>, чем <math>\frac{1}{2}</math>, и <math>1</math> в противном случае.
В своих работах[1][3] Одед Регев доказал корректность и защищенность данной криптосистемы при соответствующем выборе параметров.
Примечания
Литература
См. также
- ↑ 1,0 1,1 1,2 1,3 Oded Regev «On lattices, learning with errors, random linear codes, and cryptography», in Proceedings of the thirty-seventh annual ACM symposium on Theory of computing (Baltimore, MD, USA: ACM, 2005), 84-93, http://portal.acm.org/citation.cfm?id=1060590.1060603.
- ↑ 2,0 2,1 D. Micciancio and O. Regev. Lattice-based cryptography. In D. J.Bernstein and J. Buch-mann, editors,Post-quantum Cryprography. Springer, 2008
- ↑ 3,0 3,1 3,2 3,3 3,4 Oded Regev, «The Learning with Errors Problem» http://www.cims.nyu.edu/~regev/papers/lwesurvey.pdf Шаблон:Wayback
- ↑ 4,0 4,1 M. Ajtai and C. Dwork. A public-key cryptosystem with worst-case/average-case equivalence. In Proc. 29th Annual ACM Symp. on Theory of Computing (STOC), pages 284—293. 1997
- ↑ M. Ajtai and C. Dwork. The first and fourth public-key cryptosystems with worst-case/average-case equivalence, 2007. Available from ECCC at http://www.uni-trier.de/eccc/Шаблон:Недоступная ссылка
- ↑ 6,0 6,1 O. Regev. New lattice-based cryptographic constructions. Journal of the ACM, 51(6):899-942, 2004. Preliminary version in STOC’03
- ↑ C. Peikert. Public-key cryptosystems from the worst-case shortest vector problem. In Proc. 41st ACM Symp. on Theory of Computing (STOC), pages 333—342. 2009
- ↑ V. Lyubashevsky and D. Micciancio. On bounded distance decoding, unique shortest vectors, and the minimum distance problem. In CRYPTO, pages 577—594. 2009.
- ↑ C. Peikert, V. Vaikuntanathan, and B. Waters. A framework for efficient and compos-able oblivious transfer. In CRYPTO, pages 554—571. 2008
- ↑ V. Lyubashevsky, C. Peikert, and O. Regev. On ideal lattices and learning with errors over rings. In EUROCRYPT. 2010.
- ↑ Шаблон:Cite web