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

Представленная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. Одедом Регевым в 2005 году LWE оказалась удивительно универсальной основой для криптографических конструкций, в частности, для создания постквантовых криптографических алгоритмовRegev, O. (2005). On lattices, learning with errors, random linear codes, and cryptography. Journal of the ACM..

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

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

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

История появления Возникновение концепции LWE отслеживается в работах и Синтии Дворк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/. LWE не была в явном виде представлена в этих работах, однако тщательное исследование конструкции Айтаи—Дворк, упрощённой в работе РегеваO. Regev. New lattice-based cryptographic constructions. Journal of the ACM, 51(6):899-942, 2004. Preliminary version in STOC’03, показывает, что идеи LWE неявно возникают в этой работе.

Ранние исследования в этой области опирались на недостаточно хорошо изученную задачу нахождения уникального кратчайшего вектора. Долгое время было непонятно, можно ли заменить её более стандартными задачами на решётках. Позднее Крис Пейкерт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., что задача нахождения уникального кратчайшего вектора на самом деле является эквивалентом стандартной задачи на решетках GapSVP, что привело к более ясной картине в данной области.

Пример задачи Рассмотрим типичную задачу LWEOded Regev, «The Learning with Errors Problem» http://www.cims.nyu.edu/~regev/papers/lwesurvey.pdf : необходимо восстановить вектор , имея последовательность приближенных линейных уравнений по x. Например:

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

Криптографические приложения Диапазон криптографических приложений LWE становится в последнее время достаточно широким. Кроме приведенного ниже примера криптосистемы, существуют и более эффективные схемыD. Micciancio and O. Regev. Lattice-based cryptography. In D. J.Bernstein and J. Buch-mann, editors,Post-quantum Cryprography. Springer, 2008C. Peikert, V. Vaikuntanathan, and B. Waters. A framework for efficient and compos-able oblivious transfer. In CRYPTO, pages 554—571. 2008. Более того, использование Ring-LWE может сделать систему реально применимойV. Lyubashevsky, C. Peikert, and O. Regev. On ideal lattices and learning with errors over rings. In EUROCRYPT. 2010..

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

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

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

Примечания

Литература

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

Категория:Машинное обучение Категория:Криптография