Учимся с (подписанными) ошибками

$\underline{\bf Background}$

В 2005 году Регев [1] представил проблему «Обучение с ошибками» (LWE) - обобщение проблемы «Обучение с ошибками». Предположение о сложности этой задачи для определенных вариантов параметров теперь лежит в основе доказательств безопасности для множества постквантовых криптосистем в области решеточной криптографии. «Канонические» версии LWE описаны ниже.

Отборочные:

Позволять $\mathbb{T} = \mathbb{R}/\mathbb{Z}$ быть аддитивной группой вещественных чисел по модулю 1, т.е. принимать значения в $[0, 1)$, Для натуральных чисел$n$ а также $2 \le q \le poly(n)$"секретный" вектор ${\bf s} \in \mathbb{Z}_q^n$, распределение вероятностей $\phi$ на $\mathbb{R}$, позволять $A_{{\bf s}, \phi}$ быть распределением по $\mathbb{Z}_q^n \times \mathbb{T}$ получается при выборе ${\bf a} \in \mathbb{Z}_q^n$ равномерно наугад, выводит термин ошибки $x \leftarrow \phi$и вывод $({\bf a}, b' = \langle{\bf a}, s\rangle/q + x) \in \mathbb{Z}_q^n \times \mathbb{T}$,

Позволять $A_{{\bf s}, \overline{\phi}}$ быть "дискретизацией" $A_{{\bf s}, \phi}$, То есть сначала мы рисуем образец$({\bf a}, b')$ от $A_{{\bf s}, \phi}$ а затем вывести $({\bf a}, b) = ({\bf a}, \lfloor b'\cdot q\rceil) \in \mathbb{Z}_q^n \times \mathbb{Z}_q$, Вот$\lfloor\circ\rceil$ обозначает округление $\circ$ до ближайшего интегрального значения, поэтому мы можем просмотреть $({\bf a}, b)$ в виде $({\bf a}, b= \langle {\bf a}, {\bf s} \rangle + \lfloor q\cdot x\rceil)$,

В канонической постановке мы берем распределение ошибок $\phi$быть гауссианом. Для любой$\alpha > 0$, функция плотности одномерного гауссовского распределения вероятностей по $\mathbb{R}$ дан кем-то $D_{\alpha}(x)=e^{-\pi(x/\alpha)^2}/\alpha$, Мы пишем$A_{{\bf s}, \alpha}$ как сокращение для дискретизации $A_{{\bf s}, D_\alpha}$

LWE Определение:

В поисковой версии $LWE_{n, q, \alpha}$ нам дают $N = poly(n)$ образцы из $A_{{\bf s}, \alpha}$, который мы можем рассматривать как «шумные» линейные уравнения (Примечание: ${\bf a}_i, {\bf s} \in \mathbb{Z}_q^n, b_i \in \mathbb{Z}_q$):

$$\langle{\bf a}_1, {\bf s}\rangle \approx_\chi b_1\mod q$$ $$\vdots$$ $$\langle{\bf a}_N, {\bf s}\rangle \approx_\chi b_N\mod q$$

где ошибка в каждом уравнении независимо получается из (центрированного) дискретного гауссиана ширины . Наша цель - восстановить . (Заметьте, что без ошибок мы можем решить эту проблему с помощью исключения по Гауссу, но при наличии этой ошибки устранение по Гауссу дает сбой.)$\alpha q$${\bf s}$

В версии решения нам предоставляется доступ к оракулу который возвращает образцы при запросе. Нам обещают, что все сэмплы происходят из или из равномерного распределения . Наша цель - определить, что именно так.$DLWE_{n, q, \alpha}$$\mathcal{O}_{\bf s}$$({\bf a}, b)$$A_{{\bf s}, \alpha}$$U(\mathbb{Z}_q^n)\times U(\mathbb{Z}_q)$

Обе проблемы считаются когда .$hard$$\alpha q > 2\sqrt n$

Связь с теорией сложности:

Известно (подробности см. В [1], [2]), что LWE соответствует решению задачи декодирования с ограниченным расстоянием (BDD) на двойной решетке экземпляра GapSVP. Алгоритм полиномиального времени для LWE подразумевал бы алгоритм полиномиального времени для аппроксимации некоторых задач решетки, таких как SIVP и SVP, в пределах где - небольшой множитель полинома (скажем, ).$\tilde O(n/\alpha)$$1/\alpha$$n^2$

Текущие алгоритмические ограничения

Когда для строго меньше 1/2, Arora и Ge [3] дают алгоритм субэкспоненциального времени для LWE. Идея состоит в том, что из хорошо известных свойств гауссовского выражения, выражение ошибки ошибки, это малое вписывается в настройку «структурированного шума» за исключением экспоненциально низкой вероятности. Интуитивно в этой настройке, каждый раз, когда мы получили бы 1 выборку, мы получаем блок из выборок с обещанием, что только некоторая постоянная дробь содержит ошибку. Они используют это наблюдение, чтобы «линеаризовать» проблему и перечислить пространство ошибок.$\alpha q \le n^\epsilon$$\epsilon$$m$

$\underline{\bf Question}$

Предположим, что вместо этого у нас есть доступ к оракулу . При запросе сначала запрашивает чтобы получить образец . Если было взято из , то возвращает образец где представляет "направление" (или -значный "знак") термина ошибки , Если было нарисовано случайно, то возвращает$\mathcal{O}_{\bf s}^+$$\mathcal{O}_{\bf s}^+$$\mathcal{O}_{\bf s}$$({\bf a}, b)$$({\bf a}, b)$$A_{{\bf s}, \alpha}$$\mathcal{O}_{\bf s}^+$$({\bf a}, b, d) \in \mathbb{Z}_q^n \times \mathbb{Z}_q \times \mathbb{Z}_2$$d$$\pm$$({\bf a}, b)$$\mathcal{O}_{\bf s}^+$$({\bf a}, b, d) \leftarrow U(\mathbb{Z}_q^n)\times U(\mathbb{Z}_q)\times U(\mathbb{Z}_2)$ . (В качестве альтернативы мы могли бы рассмотреть случай, когда бит выбирается состязательно, когда рисуется равномерно случайным образом.)$d$$b$

Пусть будет как прежде, за исключением того, что теперь для достаточно большой константы , скажем. (Это необходимо для того, чтобы гарантировать, что абсолютная ошибка в каждом уравнении не будет затронута.) Определите проблемы обучения с использованием знаковой ошибки (LWSE) и как и раньше, за исключением того, что Теперь у нас есть дополнительный совет для каждого знака ошибки.$n, q, \alpha$$\alpha q > c\sqrt n$$c$$LWSE_{n, q, \alpha}$$DLWSE_{n, q, \alpha}$

Являются ли обе версии LWSE значительно проще, чем их аналоги LWE?

Например

1. Существует ли алгоритм субэкспоненциального времени для LWSE?

2. Как насчет алгоритма полиномиального времени, основанного, скажем, на линейном программировании?

В дополнение к вышеприведенному обсуждению, моя мотивация заключается в интересе к изучению алгоритмических опций для LWE (из которых в настоящее время у нас относительно мало выбора). В частности, единственное известное ограничение, обеспечивающее хорошие алгоритмы для этой проблемы, связано с величиной ошибок. Здесь величина остается неизменной, но диапазон ошибок в каждом уравнении теперь определенным образом «монотонный». (Заключительный комментарий: мне неизвестна эта формулировка проблемы, появляющейся в литературе; она кажется оригинальной.)

Ссылки:

[1] Регев, Одед. «О решетках, обучении с ошибками, случайных линейных кодах и криптографии» в JACM 2009 (первоначально на STOC 2005) ( PDF )

[2] Регев, Одед. «Проблема обучения с ошибками», приглашенный опрос на CCC 2010 ( PDF )

[3] Arora, Sanjeev and Ge, Rong. «Новые алгоритмы обучения при наличии ошибок» на ICALP 2011 ( PDF )

(вау! через три года прошло, теперь легко ответить. Забавно, как это получается! - Даниэль)

Эта проблема «Обучение с (подписанными) ошибками» ( LWSE ), как я изобрел и заявил выше (три года назад), тривиально снимается с проблемы Расширенного обучения с ошибками ( eLWE ), впервые представленной в работе Bi-Deniable Public. -Ключное шифрование от О'Нила, Пайкерта и Уотерса на CRYPTO 2011.

Задача eLWE определяется аналогично «стандартному» LWE (т. Е. [ Regev2005 ]), за исключением того, что отличительному распределителю (эффективному) дополнительно даются «подсказки» на вектор ошибок выборки LWE в виде ( возможно шумные) внутренние произведения с произвольным вектором . (В приложениях часто является вектором ключа дешифрования некоторой криптосистемы.)$\vec{x}$$\vec{z}$$\vec{z}$

Формально описывается следующим образом:$\mathsf{eLWE}_{n,m,q,\chi,\beta}$

---

Для целого числа и распределения ошибок над задача расширенного обучения с ошибками состоит в том, чтобы различать следующие пары распределений: где и и где$q = q(n) \ge 2$$\chi = \chi(n)$$\mathbb{Z}_q$

$$\{\mathbf{A}, \vec{b} = \mathbf{A}^T\vec{s}+\vec{x}, \vec{z}, \langle\vec{z}, \vec{x}\rangle + x' \},$$ $$\{\mathbf{A}, \vec{u}, \vec{z}, \langle\vec{z}, \vec{x}\rangle + x' \},$$ $\mathbf{A}\leftarrow \mathbb{Z}_q^{n\times m}, \vec{s}\leftarrow\mathbb{Z}_q^n, \vec{u}\leftarrow\mathbb{Z}_q^m, \vec{x}, \vec{z}\leftarrow\chi^m,$$x'\leftarrow\mathcal{D}_{\beta q}$$\mathcal{D}_\alpha$является (1-мерным) дискретным распределением Гаусса с шириной .$\alpha$

---

Легко видеть, что eLWE отражает «дух» LWSE , хотя формальное сокращение может быть продемонстрировано с не слишком большими дополнительными усилиями.

Основные идеи для понимания проблемы Extended-LWE разработаны в работах:

• Циркулярная и KDM-безопасность для основанного на идентичности шифрования Alperin-Sheriff и Peikert
• Классическая сложность обучения с ошибками по Бракерскому, Ланглуа, Пейкерту, Регеву и Стеле

В зависимости от того, находится ли ваш секретный ключ в или является двоичным (и от характера выбора других параметров), вы можете использовать сокращения первой или второй статьи, чтобы в конечном счете квантово / классически уменьшить значение с коэффициентом приближения для LWSE .$\mathbb{Z}_q$$\mathsf{GapSVP}_\alpha$$\alpha \ge \Omega(n^{1.5})$