Обучение с ошибками
Обучение с ошибками (англ. Learning with errors, LWE) — задача нахождения многочлена с коэффициентами из определённого кольца вычетов, для которого дана система линейных уравнений, в которой есть ошибки (что делает простую вычислительную задачу сложной).
Представленная[1] Одедом Регев в 2005 году LWE оказалась удивительно универсальной основой для криптографических конструкций, в частности, для создания постквантовых криптографических алгоритмов[1][2].
Вариант задачи обучения с ошибками, в котором многочлены рассматривается в факторкольце многочленов по определённому многочлену, называется обучение с ошибками в кольце.
Определение
Зафиксируем параметр [math]\displaystyle{ n \geqslant 1 }[/math], модуль [math]\displaystyle{ q \geqslant 2 }[/math] и распределение вероятности «ошибки» [math]\displaystyle{ \chi }[/math] на [math]\displaystyle{ {Z}_q }[/math]. Пусть [math]\displaystyle{ A_{\mathbf{s},\chi} }[/math] — распределение вероятности на [math]\displaystyle{ \mathbb{Z}_q^n \times \mathbb{Z}_q }[/math], полученное выбором вектора [math]\displaystyle{ \mathbf{a}\in \mathbb{Z}_q^n }[/math] равномерно случайно, выбором ошибки [math]\displaystyle{ \mathbf{e} \in \mathbb{Z}_q }[/math] в соответствии с [math]\displaystyle{ \chi }[/math] и полученным выражением [math]\displaystyle{ (\mathbf{a},\langle \mathbf{a},\mathbf{s} \rangle + e) }[/math], где [math]\displaystyle{ \textstyle \langle \mathbf{a},\mathbf{s} \rangle = \sum_{i=1}^n a_i s_i }[/math] и сложение производится по модулю [math]\displaystyle{ q }[/math].
Говорят[3], что алгоритм решает задачу [math]\displaystyle{ \mathrm{LWE}_{q,\chi} }[/math], если для любого [math]\displaystyle{ \mathbf{s} \in \mathbb{Z}_q^n }[/math], имея произвольное полиномиальное число независимых соотношений из [math]\displaystyle{ A_{\mathbf{s},\chi} }[/math] он с высокой вероятностью выдаст [math]\displaystyle{ s }[/math].
История появления
Возникновение концепции LWE отслеживается в работах Миклоша Айтаи и Синтии Дворк[4]. Они описали первую криптосистему на открытых ключах, использующую криптографию на решётках, и последующие её улучшения и модификации[5]. LWE не была в явном виде представлена в этих работах, однако тщательное исследование конструкции Айтаи—Дворк, упрощённой в работе Регева[6], показывает[3], что идеи LWE неявно возникают в этой работе.
Стоит отметить, что ранние исследования в этой области[4][6] опирались на недостаточно хорошо изученную задачу нахождения уникального кратчайшего вектора. Долгое время было непонятно, можно ли заменить её более стандартными задачами на решётках. Позднее Крис Пейкерт[7] и Вадим Любашевский с Даниэле Миччанчо выяснили[8], что задача нахождения уникального кратчайшего вектора на самом деле является эквивалентом стандартной задачи на решетках GapSVP, что привело к более ясной картине в данной области.
Пример задачи
Рассмотрим типичную задачу LWE[3]: необходимо восстановить вектор [math]\displaystyle{ x\in \mathbb{Z}_q^n }[/math], имея последовательность приближенных линейных уравнений по x. Например:
- [math]\displaystyle{ \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]\displaystyle{ 1 }[/math], и наша цель восстановить [math]\displaystyle{ x }[/math](в данном примере [math]\displaystyle{ x= (0, 13, 9, 11) }[/math]). Без ошибки найти [math]\displaystyle{ x }[/math] было бы просто: например, за полиномиальное время, используя метод Гаусса. Учёт же ошибки делает задачу значительно более трудной, поскольку с каждой итерацией ошибка возрастает и в конечном итоге достигает неуправляемых значений[3].
Криптографические приложения
Диапазон криптографических приложений LWE становится в последнее время достаточно широким. Кроме приведенного ниже примера криптосистемы, существуют и более эффективные схемы[2][9]. Более того, использование Ring-LWE может сделать систему реально применимой[10].
Стоит особенно отметить, что LWE может использоваться как основа для создания криптографических схем, предоставляющих полностью гоморфное шифрование. Например, она использовалась в реализации открытой для общественного пользования библиотеки FHEW[11].
Система на открытых ключах
Рассмотрим простой пример криптосистемы на открытых ключах, предложенной Регевом[1]. Она опирается на сложность решения задачи LWE. Система описывается следующими числами: [math]\displaystyle{ n }[/math]-секретный параметр, [math]\displaystyle{ m }[/math]-размерность, [math]\displaystyle{ q }[/math]-модуль и распределением вероятности[math]\displaystyle{ \chi \in \mathbb{Z}_q }[/math]. Для гарантии безопасности и корректности системы следует выбрать следующие параметры:
- [math]\displaystyle{ q \geq 2 }[/math], простое число между [math]\displaystyle{ n^2 }[/math] и [math]\displaystyle{ 2n^2 }[/math]
- [math]\displaystyle{ m=(1+\epsilon)(n+1) \log{q} }[/math] для произвольной константы [math]\displaystyle{ \epsilon }[/math]
- [math]\displaystyle{ \alpha(n) = 1/\sqrt{n}\log^2{n} }[/math]
Тогда криптосистемы определяется следующим образом:
- Секретный ключ: Секретный ключ это [math]\displaystyle{ \mathbf{s}\in \mathbb{Z}^n_q }[/math] выбранный произвольно.
- Открытый ключ: Выберем [math]\displaystyle{ m }[/math] векторов [math]\displaystyle{ a_1,\ldots,a_m \in \mathbb{Z}^n_q }[/math] произвольно и независимо. Выберем допустимые ошибки [math]\displaystyle{ e_1,\ldots,e_m \in \mathbb{Z}_q }[/math] независимо в соответствии с распределением [math]\displaystyle{ \chi }[/math]. Открытый ключ состоит из [math]\displaystyle{ (a_i,b_i=\langle a_i,\mathbf{s} \rangle/q + e_i)^m_{i=1} }[/math]
- Шифрование: Шифрование бита [math]\displaystyle{ x \in \{0,1\} }[/math] производится так: выбирается случайное подмножество [math]\displaystyle{ S }[/math] из [math]\displaystyle{ [m] }[/math] и определяется шифр [math]\displaystyle{ Enc(x) }[/math] как [math]\displaystyle{ (\sum_{i \in S} a_i, x/2 + \sum_{i \in S} b_i) }[/math]
- Расшифрование: Расшифровка [math]\displaystyle{ (a,b) }[/math] это [math]\displaystyle{ 0 }[/math] в случае если [math]\displaystyle{ b-\langle a, \mathbf{s} \rangle/q }[/math] ближе к [math]\displaystyle{ 0 }[/math], чем [math]\displaystyle{ \frac{1}{2} }[/math], и [math]\displaystyle{ 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 Архивная копия от 23 сентября 2015 на Wayback Machine
- ↑ 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.
- ↑ Leo Ducas, Daniele Micciancio. FHEW: A Fully Homomorphic Encryption library . Дата обращения: 31 декабря 2014. Архивировано 21 мая 2016 года.
Литература
- 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.