Обучение с ошибками

Эта статья может быть слишком технической, чтобы ее могло понять большинство читателей . Пожалуйста, помогите улучшить его, чтобы он был понятен неспециалистам , не удаляя технические детали. ( Октябрь 2018 г. ) ( Узнайте, как и когда удалить этот шаблон сообщения )

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

Точнее, проблема LWE определяется следующим образом. Позвольте обозначить кольцо целых чисел по модулю и обозначить множество - векторов над . Существует некоторая неизвестная линейная функция , и входом в задачу 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}}$${\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 }}$

Для каждого обозначим одномерным гауссианом с нулевым средним и дисперсией , то есть функция плотности есть где , и пусть будет распределением на, полученным с учетом модуля один. Версия LWE, рассматриваемая в большинстве результатов, будет${\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 }}$${\displaystyle \mathrm {LWE} _{q,\Psi _{\alpha }}}$

Версия решения [ править ]

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

Решающее решение, предполагающее поиск [ править ]

Интуитивно понятно, что если у нас есть процедура для задачи поиска, вариант решения может быть легко решен: просто передайте входные образцы для задачи решения решающей программе для задачи поиска. Обозначим данные образцы значком . Если решатель возвращает кандидата , для всех , рассчитайте . Если выборки взяты из распределения LWE, то результаты этого расчета будут распределены согласно , но если выборки являются равномерно случайными, эти количества также будут распределены равномерно.${\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}\}}$${\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}$

После получения проделываем аналогичную процедуру для друг друга координаты . А именно, мы преобразуем наши образцы таким же образом и преобразуем наши образцы, вычисляя , где находится в координате. ^[2]${\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}}}$

Пайкерт ^[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 }}$

Итак, предположим , что существует некоторое множество такое , что и для распределений с , DLWE было легко.${\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}}}$

Тогда был бы какой-нибудь отличитель , который по выборкам мог бы сказать, являются ли они равномерно случайными или от них . Если нам нужно отличить равномерно случайные выборки из , где выбирается равномерно случайным образом из , мы могли бы просто попробовать разные значения, выбранные равномерно случайным образом из , вычислить и передать эти образцы в . Поскольку включает большую фракцию , с высокой вероятностью, если мы выберем полиномиальное число значений , мы найдем один такой , что и будет успешно различать образцы.${\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}}}$

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

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

Результат Регева [ править ]

Для n- мерной решетки пусть параметр сглаживания обозначает наименьший такой, что где - двойное к и расширяется до множеств путем суммирования значений функций на каждом элементе в множестве. Обозначим через дискретное гауссово распределение по ширине для решетки и вещественного . Вероятность каждого пропорциональна .${\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)}$

Затем Регев показывает, что существует эффективный квантовый алгоритм для данного доступа к оракулу для целых и таких, что . Это подразумевает твердость для LWE. Хотя доказательство этого утверждения работает для любого , для создания криптосистемы он должен быть полиномиальным от .${\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}}}$${\displaystyle q}$${\displaystyle q}$${\displaystyle n}$

Результат Пайкерта [ править ]

Peikert доказывает ^[3] , что существует вероятностное полиномиальное сокращение времени от задачи в худшем случае к решению с использованием образцов для параметров , , и . GapSVP ζ , γ {\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 жестко предполагает квантовую трудность решеточных задач ( как указано выше) и с ). В 2009 г. Пайкерт ^[3] доказал аналогичный результат, предполагая только классическую трудность родственной задачи . Недостатком результата Пайкерта является то, что он основан на нестандартной версии более простой (по сравнению с SIVP) задачи GapSVP.${\displaystyle \mathrm {GapSVP} _{\gamma }}$${\displaystyle \gamma }$${\displaystyle \mathrm {SIVP} _{t}}$${\displaystyle t=O(n/\alpha )}$ G a p S V P ζ , γ {\displaystyle \mathrm {GapSVP} _{\zeta ,\gamma }}

Криптосистема с открытым ключом [ править ]

Регев ^[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-безопасная криптосистема [ править ]

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

Обмен ключами [ править ]

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

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

См. Также [ править ]

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

Ссылки [ править ]