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

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

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

Определение

править

Зафиксируем параметр  , модуль   и распределение вероятности «ошибки»   на  . Пусть   — распределение вероятности на  , полученное выбором вектора   равномерно случайно, выбором ошибки   в соответствии с   и полученным выражением  , где   и сложение производится по модулю  .

Говорят[3], что алгоритм решает задачу  , если для любого  , имея произвольное полиномиальное число независимых соотношений из   он с высокой вероятностью выдаст  .

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

править

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

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

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

править

Рассмотрим типичную задачу LWE[3]: необходимо восстановить вектор  , имея последовательность приближенных линейных уравнений по x. Например:

 

где каждое соотношение верно с некоторой маленькой дополнительной ошибкой, скажем, ± , и наша цель восстановить  (в данном примере  ). Без ошибки найти   было бы просто: например, за полиномиальное время, используя метод Гаусса. Учёт же ошибки делает задачу значительно более трудной, поскольку с каждой итерацией ошибка возрастает и в конечном итоге достигает неуправляемых значений[3].

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

править

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

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

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

править

Рассмотрим простой пример криптосистемы на открытых ключах, предложенной Регевом[1]. Она опирается на сложность решения задачи LWE. Система описывается следующими числами:  -секретный параметр,  -размерность,  -модуль и распределением вероятности . Для гарантии безопасности и корректности системы следует выбрать следующие параметры:

  •  , простое число между   и  
  •   для произвольной константы  
  •  

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

  • Секретный ключ: Секретный ключ это   выбранный произвольно.
  • Открытый ключ: Выберем   векторов   произвольно и независимо. Выберем допустимые ошибки   независимо в соответствии с распределением  . Открытый ключ состоит из  
  • Шифрование: Шифрование бита   производится так: выбирается случайное подмножество   из   и определяется шифр   как  
  • Расшифрование: Расшифровка   это   в случае если   ближе к  , чем  , и   в противном случае.

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

Примечания

править
  1. 1 2 3 4 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. 1 2 D. Micciancio and O. Regev. Lattice-based cryptography. In D. J.Bernstein and J. Buch-mann, editors,Post-quantum Cryprography. Springer, 2008
  3. 1 2 3 4 5 Oded Regev, «The Learning with Errors Problem» http://www.cims.nyu.edu/~regev/papers/lwesurvey.pdf Архивная копия от 23 сентября 2015 на Wayback Machine
  4. 1 2 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
  5. 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. 1 2 O. Regev. New lattice-based cryptographic constructions. Journal of the ACM, 51(6):899-942, 2004. Preliminary version in STOC’03
  7. 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
  8. V. Lyubashevsky and D. Micciancio. On bounded distance decoding, unique shortest vectors, and the minimum distance problem. In CRYPTO, pages 577—594. 2009.
  9. C. Peikert, V. Vaikuntanathan, and B. Waters. A framework for efficient and compos-able oblivious transfer. In CRYPTO, pages 554—571. 2008
  10. V. Lyubashevsky, C. Peikert, and O. Regev. On ideal lattices and learning with errors over rings. In EUROCRYPT. 2010.
  11. 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.

См. также

править