Обучение с ошибками - Learning with errors

Обучение с ошибками (LWE) это вычислительная проблема вывода линейного ${\displaystyle n}$-арная функция ${\displaystyle f}$ над конечным кольцом из заданных выборок ${\displaystyle y_{i}=f(\mathbf {x} _{i})}$ некоторые из которых могут быть ошибочными. Предполагается, что проблему LWE трудно решить,^[1] и таким образом быть полезным в криптография.

Точнее, проблема LWE определяется следующим образом. Позволять ${\displaystyle \mathbb {Z} _{q}}$ обозначим кольцо целых чисел по модулю ${\displaystyle q}$ и разреши${\displaystyle \mathbb {Z} _{q}^{n}}$ обозначим множество ${\displaystyle n}$-векторов над ${\displaystyle \mathbb {Z} _{q}}$. Существует некая неизвестная линейная функция ${\displaystyle f:\mathbb {Z} _{q}^{n}\rightarrow \mathbb {Z} _{q}}$, а входом в задачу LWE является выборка пар ${\displaystyle (\mathbf {x} ,y)}$, где ${\displaystyle \mathbf {x} \in \mathbb {Z} _{q}^{n}}$ и ${\displaystyle y\in \mathbb {Z} _{q}}$, так что с большой вероятностью ${\displaystyle y=f(\mathbf {x} )}$. Кроме того, отклонение от равенства соответствует некоторой известной модели шума. Проблема требует найти функцию ${\displaystyle f}$или какое-то его близкое приближение с большой вероятностью.

Проблема LWE была введена Одед Регев в 2005 году^[2] (кто выиграл 2018 Премия Гёделя для данной работы), это обобщение паритетное обучение проблема. Регев показал, что проблему LWE так же сложно решить, как несколько худших случаев. проблемы решетки. Впоследствии проблема LWE использовалась как предположение твердости создать криптосистемы с открытым ключом,^[2][3] такой как кольцевое обучение с ошибками обмен ключами пользователя Peikert.^[4]

Определение

Обозначим через ${\displaystyle \mathbb {T} =\mathbb {R} /\mathbb {Z} }$ то аддитивная группа на вещественных числах по модулю единицы. Позволять ${\displaystyle \mathbf {s} \in \mathbb {Z} _{q}^{n}}$ фиксированный вектор. ${\displaystyle \phi }$ фиксированное распределение вероятностей по ${\displaystyle \mathbb {T} }$.Обозначить ${\displaystyle A_{\mathbf {s} ,\phi }}$ распределение на ${\displaystyle \mathbb {Z} _{q}^{n}\times \mathbb {T} }$ получается следующим образом.

1. Выберите вектор ${\displaystyle \mathbf {a} \in \mathbb {Z} _{q}^{n}}$ от распределения униформы по ${\displaystyle \mathbf {a} \in \mathbb {Z} _{q}^{n}}$,
2. Выберите номер ${\displaystyle e\in \mathbb {T} }$ из раздачи ${\displaystyle \phi }$,
3. Оценить ${\displaystyle t=\langle \mathbf {a} ,\mathbf {s} \rangle /q+e}$, где ${\displaystyle \textstyle \langle \mathbf {a} ,\mathbf {s} \rangle =\sum _{i=1}^{n}a_{i}s_{i}}$ стандартный внутренний продукт в ${\displaystyle \mathbb {Z} _{q}^{n}}$, деление производится в поле реалов (или более формально это «деление на ${\displaystyle q}$"- обозначение группового гомоморфизма ${\displaystyle \mathbb {Z} _{q}\longrightarrow \mathbb {T} }$ отображение ${\displaystyle 1\in \mathbb {Z} _{q}}$ к ${\displaystyle 1/q+\mathbb {Z} \in \mathbb {T} }$), а последнее добавление находится в ${\displaystyle \mathbb {T} }$.
4. Выведите пару ${\displaystyle (\mathbf {a} ,t)}$.

В проблема обучения с ошибками ${\displaystyle \mathrm {LWE} _{q,\phi }}$ найти ${\displaystyle \mathbf {s} \in \mathbb {Z} _{q}^{n}}$, имея доступ к полиномиально множеству выборок из ${\displaystyle A_{\mathbf {s} ,\phi }}$.

Для каждого ${\displaystyle \alpha >0}$, обозначим через ${\displaystyle D_{\alpha }}$ одномерный Гауссовский с нулевым средним и дисперсией${\displaystyle \alpha ^{2}/(2\pi )}$, то есть функция плотности равна ${\displaystyle D_{\alpha }(x)=\rho _{\alpha }(x)/\alpha }$ где ${\displaystyle \rho _{\alpha }(x)=e^{-\pi (|x|/\alpha )^{2}}}$, и разреши ${\displaystyle \Psi _{\alpha }}$ быть распределением на ${\displaystyle \mathbb {T} }$ полученный с учетом ${\displaystyle D_{\alpha }}$ по модулю один. Версия LWE, рассматриваемая в большинстве результатов, будет ${\displaystyle \mathrm {LWE} _{q,\Psi _{\alpha }}}$

Версия решения

В LWE проблема, описанная выше, заключается в поиск версия проблемы. в решение версия (DLWE) цель состоит в том, чтобы различать зашумленные внутренние продукты и равномерно случайные выборки из ${\displaystyle \mathbb {Z} _{q}^{n}\times \mathbb {T} }$ (практически, некая его дискретная версия). Регев^[2] показал, что решение и поиск версии эквивалентны, когда ${\displaystyle q}$ является простым числом, ограниченным некоторым многочленом от ${\displaystyle n}$.

Решающее решение, предполагающее поиск

Интуитивно понятно, что если у нас есть процедура для задачи поиска, вариант решения может быть легко решен: просто передайте входные образцы для задачи решения решающей программе для задачи поиска. Обозначим данные образцы через ${\displaystyle \{(\mathbf {a} _{i},\mathbf {b} _{i})\}\subset \mathbb {Z} _{q}^{n}\times \mathbb {T} }$. Если решатель возвращает кандидата ${\displaystyle \mathbf {s} }$, для всех ${\displaystyle i}$рассчитать ${\displaystyle \{\langle \mathbf {a} _{i},\mathbf {s} \rangle -\mathbf {b} _{i}\}}$. Если образцы взяты из распределения LWE, то результаты этого расчета будут распределены в соответствии с ${\displaystyle \chi }$, но если выборки равномерно случайны, эти количества также будут равномерно распределены.

Решение поиска, предполагающее решение

Для другого направления, если имеется решатель проблемы решения, поисковая версия может быть решена следующим образом: Восстановить ${\displaystyle \mathbf {s} }$ по одной координате за раз. Чтобы получить первую координату, ${\displaystyle \mathbf {s} _{1}}$, Угадай ${\displaystyle k\in Z_{q}}$, и сделайте следующее. Выберите номер ${\displaystyle r\in \mathbb {Z} _{q}}$ равномерно наугад. Преобразуйте данные образцы ${\displaystyle \{(\mathbf {a} _{i},\mathbf {b} _{i})\}\subset \mathbb {Z} _{q}^{n}\times \mathbb {T} }$ следующим образом. Рассчитать ${\displaystyle \{(\mathbf {a} _{i}+(r,0,\ldots ,0),\mathbf {b} _{i}+(rk)/q)\}}$. Отправьте преобразованные образцы в решающую программу.

Если предположение ${\displaystyle k}$ правильно, преобразование принимает распределение ${\displaystyle A_{\mathbf {s} ,\chi }}$ себе, и в противном случае, поскольку ${\displaystyle q}$ простое, переводит его к равномерному распределению. Итак, учитывая полиномиальный решатель для проблемы решения, которая дает ошибку с очень малой вероятностью, поскольку ${\displaystyle q}$ ограничена некоторым полиномом от ${\displaystyle n}$, требуется лишь полиномиальное время, чтобы угадать все возможные значения для ${\displaystyle k}$ и используйте решающую программу, чтобы увидеть, какой из них правильный.

После получения ${\displaystyle \mathbf {s} _{1}}$, проделаем аналогичную процедуру для каждой другой координаты ${\displaystyle \mathbf {s} _{j}}$. А именно трансформируем наши ${\displaystyle \mathbf {b} _{i}}$ образцы таким же образом и преобразовать наши ${\displaystyle \mathbf {a} _{i}}$ образцы путем расчета ${\displaystyle \mathbf {a} _{i}+(0,\ldots ,r,\ldots ,0)}$, где ${\displaystyle r}$ находится в ${\displaystyle j^{\text{th}}}$ координировать.^[2]

Peikert^[3] показал, что это сокращение с небольшой модификацией работает для любых ${\displaystyle q}$ это произведение различных малых (многочленов от ${\displaystyle n}$) простые числа. Основная идея - если ${\displaystyle q=q_{1}q_{2}\cdots q_{t}}$, для каждого ${\displaystyle q_{\ell }}$, угадайте и проверьте, ${\displaystyle \mathbf {s} _{j}}$ конгруэнтно ${\displaystyle 0\mod q_{\ell }}$, а затем используйте Китайская теорема об остатках восстановить ${\displaystyle \mathbf {s} _{j}}$.

Средняя твердость корпуса

Регев^[2] показал случайная самовосстановление из LWE и DLWE проблемы для произвольных ${\displaystyle q}$ и ${\displaystyle \chi }$. Данные образцы ${\displaystyle \{(\mathbf {a} _{i},\mathbf {b} _{i})\}}$ от ${\displaystyle A_{\mathbf {s} ,\chi }}$, легко увидеть, что ${\displaystyle \{(\mathbf {a} _{i},\mathbf {b} _{i}+\langle \mathbf {a} _{i},\mathbf {t} \rangle )/q\}}$ образцы из ${\displaystyle A_{\mathbf {s} +\mathbf {t} ,\chi }}$.

Итак, предположим, что был какой-то набор ${\displaystyle {\mathcal {S}}\subset \mathbb {Z} _{q}^{n}}$ такой, что ${\displaystyle |{\mathcal {S}}|/|\mathbb {Z} _{q}^{n}|=1/\operatorname {poly} (n)}$, а для дистрибутивов ${\displaystyle A_{\mathbf {s} ',\chi }}$, с участием ${\displaystyle \mathbf {s} '\leftarrow {\mathcal {S}}}$, DLWE было легко.

Тогда был бы какой-нибудь отличитель ${\displaystyle {\mathcal {A}}}$, кто дал образцы ${\displaystyle \{(\mathbf {a} _{i},\mathbf {b} _{i})\}}$, можно было сказать, были ли они случайными или ${\displaystyle A_{\mathbf {s} ',\chi }}$. Если нам нужно отличать равномерно случайные выборки от ${\displaystyle A_{\mathbf {s} ,\chi }}$, где ${\displaystyle \mathbf {s} }$ выбирается равномерно случайным образом из ${\displaystyle \mathbb {Z} _{q}^{n}}$, мы могли бы просто попробовать разные значения ${\displaystyle \mathbf {t} }$ отобранные равномерно случайным образом из ${\displaystyle \mathbb {Z} _{q}^{n}}$рассчитать ${\displaystyle \{(\mathbf {a} _{i},\mathbf {b} _{i}+\langle \mathbf {a} _{i},\mathbf {t} \rangle )/q\}}$ и скормить эти образцы ${\displaystyle {\mathcal {A}}}$. поскольку ${\displaystyle {\mathcal {S}}}$ состоит из большой части ${\displaystyle \mathbb {Z} _{q}^{n}}$, с большой вероятностью, если выбрать полиномиальное количество значений для ${\displaystyle \mathbf {t} }$, мы найдем такой, что ${\displaystyle \mathbf {s} +\mathbf {t} \in {\mathcal {S}}}$, и ${\displaystyle {\mathcal {A}}}$ успешно различит образцы.

Таким образом, таких ${\displaystyle {\mathcal {S}}}$ может существовать, что означает LWE и DLWE являются (с точностью до полиномиального множителя) такими же сложными в среднем случае, как и в худшем случае.

Результаты твердости

Результат Регева

Для п-мерная решетка ${\displaystyle L}$, позволять параметр сглаживания ${\displaystyle \eta _{\varepsilon }(L)}$ обозначить наименьший ${\displaystyle s}$ такой, что ${\displaystyle \rho _{1/s}(L^{*}\setminus \{\mathbf {0} \})\leq \varepsilon }$ где ${\displaystyle L^{*}}$ является двойником ${\displaystyle L}$ и ${\displaystyle \rho _{\alpha }(x)=e^{-\pi (|x|/\alpha )^{2}}}$ расширяется до наборов путем суммирования значений функций в каждом элементе набора. Позволять ${\displaystyle D_{L,r}}$ обозначим дискретное гауссово распределение на ${\displaystyle L}$ ширины ${\displaystyle r}$ для решетки ${\displaystyle L}$ и настоящий ${\displaystyle r>0}$. Вероятность каждого ${\displaystyle x\in L}$ пропорционально ${\displaystyle \rho _{r}(x)}$.

В задача дискретной гауссовой выборки(DGS) определяется следующим образом: Экземпляр ${\displaystyle DGS_{\phi }}$ дается ${\displaystyle n}$-мерная решетка ${\displaystyle L}$ и ряд ${\displaystyle r\geq \phi (L)}$. Цель состоит в том, чтобы вывести образец из ${\displaystyle D_{L,r}}$. Регев показывает, что есть сокращение от ${\displaystyle \operatorname {GapSVP} _{100{\sqrt {n}}\gamma (n)}}$ к ${\displaystyle DGS_{{\sqrt {n}}\gamma (n)/\lambda (L^{*})}}$ для любой функции ${\displaystyle \gamma (n)}$.

Затем Регев показывает, что существует эффективный квантовый алгоритм для ${\displaystyle DGS_{{\sqrt {2n}}\eta _{\varepsilon }(L)/\alpha }}$ предоставлен доступ к оракулу для ${\displaystyle \mathrm {LWE} _{q,\Psi _{\alpha }}}$ для целого числа ${\displaystyle q}$ и ${\displaystyle \alpha \in (0,1)}$ такой, что ${\displaystyle \alpha q>2{\sqrt {n}}}$. Это подразумевает твердость для LWE. Хотя доказательство этого утверждения работает для любых ${\displaystyle q}$, для создания криптосистемы ${\displaystyle q}$ должен быть полиномиальным от ${\displaystyle n}$.

Результат Пайкерта

Пайкерт доказывает^[3] что существует вероятностное полиномиальное сокращение времени от ${\displaystyle \operatorname {GapSVP} _{\zeta ,\gamma }}$ проблема в худшем случае к решению ${\displaystyle \mathrm {LWE} _{q,\Psi _{\alpha }}}$ с помощью ${\displaystyle \operatorname {poly} (n)}$ образцы для параметров ${\displaystyle \alpha \in (0,1)}$, ${\displaystyle \gamma (n)\geq n/(\alpha {\sqrt {\log n}})}$, ${\displaystyle \zeta (n)\geq \gamma (n)}$ и ${\displaystyle q\geq (\zeta /{\sqrt {n}})\omega {\sqrt {\log n}})}$.

Использование в криптографии

В LWE Задача служит разносторонней задачей, используемой при строительстве нескольких^[2][3][5][6] криптосистемы. В 2005 году Регев^[2] показали, что решающая версия LWE жестко предполагает квантовую твердость проблемы решетки ${\displaystyle \mathrm {GapSVP} _{\gamma }}$ (для ${\displaystyle \gamma }$ как указано выше) и ${\displaystyle \mathrm {SIVP} _{t}}$ с участием ${\displaystyle t=O(n/\alpha )}$). В 2009 году Пайкерт^[3] доказал аналогичный результат, предполагая только классическую трудность родственной задачи ${\displaystyle \mathrm {GapSVP} _{\zeta ,\gamma }}$. Недостатком результата Пайкерта является то, что он основан на нестандартной версии более простой (по сравнению с SIVP) задачи GapSVP.

Криптосистема с открытым ключом

Регев^[2] предложил криптосистема с открытым ключом на основе твердости LWE проблема. Криптосистема, а также доказательства безопасности и корректности полностью классические. Система характеризуется ${\displaystyle m,q}$ и распределение вероятностей ${\displaystyle \chi }$ на ${\displaystyle \mathbb {T} }$. Настройка параметров, используемых в доказательствах правильности и безопасности, является

• ${\displaystyle q\geq 2}$, обычно простое число между ${\displaystyle n^{2}}$ и ${\displaystyle 2n^{2}}$.
• ${\displaystyle m=(1+\varepsilon )(n+1)\log q}$ для произвольной постоянной ${\displaystyle \varepsilon }$
• ${\displaystyle \chi =\Psi _{\alpha (n)}}$ для ${\displaystyle \alpha (n)\in o(1/{\sqrt {n}}\log n)}$, где ${\displaystyle \Psi _{\beta }}$ распределение вероятностей, полученное путем выборки нормальной переменной со средним ${\displaystyle 0}$ и стандартная вариация ${\displaystyle {\frac {\beta }{\sqrt {2\pi }}}}$ и уменьшая результат по модулю ${\displaystyle 1}$.

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

• Закрытый ключ: Закрытый ключ - это ${\displaystyle \mathbf {s} \in \mathbb {Z} _{q}^{n}}$ выбран равномерно случайно.
• Открытый ключ: Выберите ${\displaystyle m}$ векторов ${\displaystyle \mathbf {a} _{1},\ldots ,\mathbf {a} _{m}\in \mathbb {Z} _{q}^{n}}$ равномерно и независимо. Выберите смещения ошибок ${\displaystyle e_{1},\ldots ,e_{m}\in \mathbb {T} }$ независимо согласно ${\displaystyle \chi }$. Открытый ключ состоит из ${\displaystyle (\mathbf {a} _{i},b_{i}=\langle \mathbf {a} _{i},\mathbf {s} \rangle /q+e_{i})_{i=1}^{m}}$
• Шифрование: Шифрование бит ${\displaystyle x\in \{0,1\}}$ выполняется путем выбора случайного подмножества ${\displaystyle S}$ из ${\displaystyle [m]}$ а затем определение ${\displaystyle \operatorname {Enc} (x)}$ так как

${\displaystyle \left(\sum _{i\in S}\mathbf {a} _{i},{\frac {x}{2}}+\sum _{i\in S}b_{i}\right)}$

• Расшифровка: Расшифровка ${\displaystyle (\mathbf {a} ,b)}$ является ${\displaystyle 0}$ если ${\displaystyle b-\langle \mathbf {a} ,\mathbf {s} \rangle /q}$ ближе к ${\displaystyle 0}$ чем ${\displaystyle {\frac {1}{2}}}$, и ${\displaystyle 1}$ в противном случае.

Доказательство правильности следует из выбора параметров и некоторого вероятностного анализа. Доказательство безопасности сводится к версии решения LWE: алгоритм различения шифров (с указанными выше параметрами) ${\displaystyle 0}$ и ${\displaystyle 1}$ можно использовать для различения ${\displaystyle A_{s,\chi }}$ и равномерное распределение по ${\displaystyle \mathbb {Z} _{q}^{n}\times \mathbb {T} }$

CCA-безопасная криптосистема

Peikert^[3] предложили систему, которая защищена даже от любых атака по выбранному зашифрованному тексту.

Обмен ключами

Основная статья: Кольцевое обучение с ошибками обмен ключами

Идея использования LWE и Ring LWE для обмена ключами была предложена и подана в Университет Цинциннати в 2011 году Джинтаем Дингом. Идея исходит из ассоциативности умножения матриц, а ошибки используются для обеспечения безопасности. Бумага^[7] появился в 2012 г. после подачи предварительной заявки на патент в 2012 г.

Безопасность протокола доказана на основе сложности решения проблемы LWE. В 2014 году Пайкерт представил ключевую транспортную схему.^[8] следуя той же базовой идее Динга, где также используется новая идея отправки дополнительного 1-битного сигнала для округления в конструкции Динга. Реализация «новой надежды»^[9] выбран для постквантового эксперимента Google,^[10] использует схему Пайкерта с вариацией распределения ошибок.

Смотрите также

• Постквантовая криптография
• Криптография на основе решеток
• Кольцевое обучение с ошибками обмен ключами
• Задача короткого целочисленного решения (SIS)

использованная литература

1. Регев, Одед (2009). «На решетках, обучение с ошибками, случайные линейные коды и криптография». Журнал ACM. 56 (6): 1–40. Дои:10.1145/1568318.1568324.
2. Одед Регев, «О решетках, обучении с ошибками, случайных линейных кодах и криптографии», в материалах тридцать седьмого ежегодного симпозиума ACM по теории вычислений (Балтимор, Мэриленд, США: ACM, 2005), 84–93, http://portal.acm.org/citation.cfm?id=1060590.1060603.
3. Крис Пайкерт, «Криптосистемы с открытым ключом из задачи кратчайшего вектора наихудшего случая: расширенная аннотация», в материалах 41-го ежегодного симпозиума ACM по теории вычислений (Bethesda, MD, США: ACM, 2009), 333–342, http://portal.acm.org/citation.cfm?id=1536414.1536461.
4. Пайкерт, Крис (2014-10-01). «Решеточная криптография для Интернета». В Моска, Микеле (ред.). Постквантовая криптография. Конспект лекций по информатике. 8772. Издательство Springer International. С. 197–219. CiteSeerX  10.1.1.800.4743. Дои:10.1007/978-3-319-11659-4_12. ISBN  978-3-319-11658-7.
5. Крис Пайкерт и Брент Уотерс, «Потерянные функции-лазейки и их приложения», в материалах 40-го ежегодного симпозиума ACM по теории вычислений (Виктория, Британская Колумбия, Канада: ACM, 2008), 187–196, http://portal.acm.org/citation.cfm?id=1374406.
6. Крейг Джентри, Крис Пайкерт и Винод Вайкунтанатан, «Люки для жестких решеток и новых криптографических конструкций», в материалах 40-го ежегодного симпозиума ACM по теории вычислений (Виктория, Британская Колумбия, Канада: ACM, 2008), 197-206, http://portal.acm.org/citation.cfm?id=1374407.
7. Линь, Цзиньтай Дин, Сян Се, Сяодун (01.01.2012). «Простая и надежно защищенная схема обмена ключами, основанная на проблеме обучения с ошибками».
8. Пайкерт, Крис (01.01.2014). «Решеточная криптография для Интернета».
9. Алким, Эрдем; Дукас, Лео; Пёппельманн, Томас; Швабе, Питер (01.01.2015). «Постквантовый обмен ключами - новая надежда».
10. «Эксперименты с постквантовой криптографией». Блог Google Online Security. Получено 2017-02-08.