Loading AI tools
Из Википедии, свободной энциклопедии
Обучение с ошибками (англ. 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] Одед Регев доказал корректность и защищенность данной криптосистемы при соответствующем выборе параметров.
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.