Почему RLWE легче, чем LWE, и почему мы можем выбрать $a_i$ как перестановку $a_1$ в RLWE, но не LWE?

В LWE мы имеем

$$<a_1,s> + e + \mu_1\in \mathbb{Z}_q$$

для секретного ключа $s\in \{0,1\}^n$ и $a_1\in\mathbb{Z}_q^n$

Это шифрование числа $\mu_1$. Если мы хотим зашифровать $n$ разные $\mu_i$, нам нужно $n$ разные $a_i$. С $n$ ценности $а_{11}, ..., а_{1n}$ мы смогли зашифровать один единственный $\mu_1$.

Для RLWE имеем

$$a*s +e + m \in \mathbb{Z}_q[X]^n$$

за $a\in \mathbb{Z}_q[X]^n, e\in \mathbb{Z}_q[X]^n, m \in \mathbb{Z}_q[X]^n$, и $*$ является полиномиальным умножением по модулю $х^п+1$. Это шифрование полинома $м$ и, таким образом, шифрование $n$ числа $m_1,...,m_n$. С $n$ ценности $a_1, ..., a_n$ мы смогли зашифровать $n$ числа.

Я думаю, что этот ответ означал объяснить: https://crypto.stackexchange.com/a/47602. Для шифрования $n$ значения в LWE, нам нужен размер ключа, кратный $n^2$ из-за $а$с. Для RLWE нам нужно всего лишь $n$. Тем не менее, все еще для RLWE, на странице 5 PDF он связал, он говорит, что если мы хотим зашифровать $n$ векторов, мы можем просто выбрать $a_1\in\mathbb{Z}_q[X]^n$ и другие $a_i$ как функции $a_1$ как это: $$\vec{a_i} = (a_i, ..., a_n, -a_1, ..., -a_{i-1}).$$ Прежде всего, почему это можно сделать для RLWE, но не для LWE? Для LWE у нас есть своего рода система линейных уравнений:

$$a_{i1}s_1 + a_{i2}s_2 + ... + a_{in}s_n + e_i = bi \mbox{ mod q}$$

это должно быть трудно решить. Если мы сделаем так, чтобы $а_{я}$ является перестановкой $a_1$ тогда я думаю, что проблема уже не сложная. Я прав? Но почему на RLWE все еще тяжело? Это только потому, что в RLWE у нас нет системы уравнений? У нас есть

$$a_i*s +e_i + m_i = b_i \mbox{ mod $x^n$ + 1}$$

может быть $a_i$ являющийся перестановкой $a_1$ здесь все еще выходит проблема трудно, я предполагаю.

Во-первых, Регев описывает, что RLWE можно рассматривать как некий «структурированный» экземпляр LWE. Это потому что

1. вы можете описать полиномы с точки зрения векторов в $\mathbb{Z}_q^n$,
2. ты можешь описать добавление полиномов в терминах добавление векторов в $\mathbb{Z}_q^n$, и
3. ты можешь описать умножение полиномов $\bмод (х^n+1)$ в терминах «забавных скалярных произведений» векторов в $\mathbb{Z}_q^n$.

Последний шаг — единственный действительно нетривиальный. Я не буду выводить все это здесь, но можно показать, что $я$й коэффициент полиномиального произведения $a(x)b(x)\bmod (q, x^n+1)$ имеет форму $\langle \vec b, \mathsf{негациклический}^{\circ i}(\vec a)\rangle$, куда $\mathsf{негациклический}^{\circ i}(\vec a)$ это $я$-кратное применение операции кругового сдвига $\vec $ (влево или вправо, я всегда забываю), и умножает коэффициенты на $-1$ когда они «оборачивают». Конкретно, это $я$-кратное повторение операции

$$(a_0,\dots,a_{n-1})\mapsto (-a_{n-1},a_0,\dots,a_{n-2}).$$

Это значит, что можно точно описать экземпляр RLWE $(а(х), а(х)s(х) + е(х))$ переписывая вещи в терминах целочисленных векторов. В частности, если установить $А$ быть следующей матрицей (где $[а,б,в]$ это матрица с столбцы $а,б,с$)

$$A = [\mathsf{негациклический}^{\circ 0}(\vec a),\mathsf{негациклический}^{\circ 1}(\vec a),\dots, \mathsf{негациклический}^{\ circ (n-1)}(\vec a)],$$

затем вышеупомянутый экземпляр RLWE точно соответствует экземпляру LWE $(А, As + e)$. Как упоминает Регев, это $А$ больше не является равномерно случайным $\mathbb{Z}_q^{n\times n}$, как есть полностью указано $ О (п) $ элементы.

Прежде всего, почему это можно сделать для RLWE, но не для LWE?

Чтобы уточнить, что делается рассмотрение RLWE как структурированной формы LWE. Кто-то идет на компромисс с некоторыми предположениями о структуре в $А$ для некоторой экономии в эффективности. Поскольку LWE является «неструктурированной» версией, нельзя предполагать структуру в «неструктурированном» объекте.

Если мы сделаем так, чтобы $\vec a_i$ является перестановкой $\vec a_1$ тогда я думаю, что проблема уже не сложная.

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

Обратите внимание, что не все перестановки работают. Это быстро становится техническим, но $\mathbb{Z}_q[x]/(x^n-1)$ первоначально считалось (по Миччанчио для кольцевого варианта задачи SIS). Этот многочлен не является неприводимым (у него есть корень в $х = 1$). Тогда существует гомоморфизм (соответствующий оценке многочленов в 1), который отображает $a(x) \in\mathbb{Z}_q[x]/(x^n-1)\to \mathbb{Z}_q$, что приводит к атакам. Во всяком случае, это важно, потому что умножение на $\mathbb{Z}_q[x]/(x^n-1)$ соответствует циклический перестановки $\vec $ (а не негациклический описанные выше).

Все это означает, что набор всех экземпляров RLWE можно рассматривать как подмножество набора всех экземпляров LWE. С этой точки зрения RLWE не может быть сложнее, чем LWE — любой алгоритм, нарушающий LWE, в равной степени нарушает RLWE. Можно задаться вопросом, насколько проще "подмножество RLWE" --- есть некоторые известные проблемы с решеткой, в которых все становится иначе. много легче, когда вы предполагаете структуру (я считаю, что SIVP является основным примером). Для задачи RLWE есть дополнительные примеры, когда если неправильно параметризован все становится проще, например, когда вы используете $х^n-1$ неприводимый полином. Есть также некоторые нетривиальные квантовые атаки на близкий вариант проблемы SVP для экземпляров RLWE (я полагаю, что это проблема генератора коротких принципов).

Ни одно из вышеперечисленных не подразумевает (для многочленов, таких как $х^{2^к}+1$, которые обычно используются) лучше атакуют RLWE, чем существуют для LWE. Некоторые авторы (в частности, Бернстайн) считают, что дополнительная структура помогает [1], но пока ничего конкретного не показано.

[1] Он считает, что есть нечто более тонкое, связанное с размером групп Галуа выбранного многочлена. $ф(х)$ используется в RLWE. Полином $х^{2^к}+1$ имеет небольшую группу Галуа размером $ О (\ градус ж) $. Размер максимальной группы Галуа равен $O((\degf)!)$, намного больше. Большие группы Галуа встречаются для случайных многочленов whp и поэтому являются «менее структурированными». О нападениях с использованием небольшой группы Галуа не известно. $х^{2^к}+1$.

"мы можем просто выбрать $a_i \in\mathbb{Z}_q[X]^n$" => Я думаю, что это должно быть просто $\mathbb{Z}_q^n$.

Что вы должны понять из этого абзаца, так это то, что шифрование

$\mu_0, \dots, \mu_{n-1}$ рассматривается как многочлен $\mu = \сумма \mu_i X^i$ с RLWE и полиномом $\сумма a_i X^i$, эквивалентно шифрованию каждой координаты $\mu_j$ с LWE и вектором $\vec{a_j}=(a_{j}, a_{j+1}, \dots, a_{n-1}, -a_{1}, \dots, -a_{j-1})$.

Почему это правда? Потому что, если мы посмотрим на коэффициент $Х^j$ в $a*s +e + \mu \in\mathbb{Z}_q[X]^n$, получаем ровно

$<a_j,s> + e_j + \mu_j$ (с $e_j$ коэффициент $Х^j$ для многочлена $e$).

О твердости предположений: RLWE — это отличное (и более простое) предположение, чем LWE. Его безопасность была изучена независимо. Насчет предположения вы предлагаете, а я только замечу:

• Вы не захватываете RLWE (из-за $-$).

• Для некоторых перестановок задача становится намного проще:

Например, если $\sigma = (1,2)(3,4)\dots(n-1, n).$ (с вашим обозначением это $i_j = i_j + 1$ если $i_j$ странно, и $i_j -1$ если это не так).

Тогда у нас есть $c_1= <a,s> + e_1 + \mu_1$, и $c_2 = \sum^{n/2}_{j=1} (a_{2j}s_{2j-1} + a_{2j-1}s_{2j}) + e_2 + \mu_2.$

затем $с_1 + с_2 = \sum^{n/2}_{j=1} (a_{2j}s_{2j-1} + a_{2j-1}s_{2j} + a_{2j}s_{2j} + a_{2j-1}s_{2j-1}) + e_1+ e_2 + \mu_1+ \mu_2.$

$=\sum^{n/2}_{j=1} (a_{2j} + a_{2j-1})(s_{2j-1} + s_{2j-1}) + e_1+ e_2 + (\ мю_1+ \мю_2).$

Тогда мы уменьшили размерность фактора $2$.

У меня возникло бы искушение обобщить и сказать, изменяя порядок $к$, вы можете уменьшить размерность фактора $к$ (тогда это, вероятно, небезопасно).