Why RLWE is lighter than LWE and why we can pick $a_i$ as a permutation of $a_1$ in RLWE but not LWE?

In LWE, we have

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

for a secret key $s\in \{0,1\}^n$ and $a_1\in \mathbb{Z}_q^n$

This is an encryption of a number $\mu_1$. If we want to encrypt $n$ different $\mu_i$, we need $n$ different $a_i$. With $n$ values $a_{11}, ..., a_{1n}$ we were able to encrypt one single $\mu_1$.

For RLWE, we have

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

for $a\in \mathbb{Z}_q[X]^n, e\in \mathbb{Z}_q[X]^n, m \in \mathbb{Z}_q[X]^n$, and $*$ is the polynomial multiplication modulo $x^n+1$. This is an encryption of a polynomial $m$ and thus the encryption of $n$ numbers $m_1,...,m_n$. With $n$ values $a_1, ..., a_n$ we were able to encrypt $n$ numbers.

I think this is what this answer meant to explain: https://crypto.stackexchange.com/a/47602. For encrypting $n$ values in LWE, we need a key size multiple of $n^2$ because of the $a$'s. For RLWE, we need just $n$. However, still for RLWE, on page 5 of the PDF he linked, he says that if we want to encrypt $n$ vectors, we can simply pick the $a_1\in \mathbb{Z}_q[X]^n$ and the others $a_i$ as functions of $a_1$ like this: $$\vec{a_i} = (a_i, ..., a_n, -a_1, ..., -a_{i-1}).$$ First of all, why this can be done for RLWE but not LWE? For LWE, we have a kind of system of linear equations:

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

that is supposed to be hard to solve. If we make it such that $a_{i}$ is a permutation of $a_1$ then I think the problem is not hard anymore. Am I right? But why it is still hard on RLWE? Is it just because on RLWE we don't have a system of equations? We have

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

maybe $a_i$ being a permutation of $a_1$ here still leaves the problem hard, I guess.

First, Regev is describing that RLWE can be viewed as a certain "structured" instance of LWE. This is because

1. you can describe polynomials in terms of vectors in $\mathbb{Z}_q^n$,
2. you can describe addition of polynomials in terms of addition of vectors in $\mathbb{Z}_q^n$, and
3. you can describe multiplication of polynomials $\bmod (x^n+1)$ in terms of "funny scalar products" of vectors in $\mathbb{Z}_q^n$.

The last step is the only really non-trivial one. I won't derive it all here, but one can show that the $i$th coefficient of the polynomial product $a(x)b(x)\bmod (q, x^n+1)$ is of the form $\langle \vec b, \mathsf{negacyclic}^{\circ i}(\vec a)\rangle$, where $\mathsf{negacyclic}^{\circ i}(\vec a)$ is the $i$-fold application of the operation that circularly shifts $\vec a$ (to the left or right, I always forget), and multiplies coefficients by $-1$ when they "wrap around". Concretely, it is the $i$-fold iteration of the operation

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

This is to say one can exactly describe a RLWE instance $(a(x), a(x)s(x) + e(x))$ by rewriting things in terms of integer vectors. In particular, if you set $A$ to be the following matrix (where $[a,b,c]$ is a matrix with columns $a,b,c$)

$$A = [\mathsf{negacyclic}^{\circ 0}(\vec a),\mathsf{negacyclic}^{\circ 1}(\vec a),\dots, \mathsf{negacyclic}^{\circ (n-1)}(\vec a)],$$

then the aforementioned RLWE instance exactly corresponds to the LWE instance $(A, As + e)$. As Regev mentions, this $A$ is no longer uniformly random over $\mathbb{Z}_q^{n\times n}$, as it is entirely specified by $O(n)$ elements.

First of all, why this can be done for RLWE but not LWE?

To clarify, what is being done is viewing RLWE as a structured form of LWE. One tradeoffs some assumptions of structure in the $A$ for some savings in efficiency. As LWE is the "unstructured" version, one can't assume structure in an "unstructured" object.

If we make it such that $\vec a_i$ is a permutation of $\vec a_1$ then I think the problem is not hard anymore.

As we are simply rewriting our RLWE instance in a different language, the "structured LWE" version is hard iff the RLWE version is hard. So, RLWE can be viewed as saying that (for appropriate permutations) that the problem is still hard.

Note that not all permutations work. This quickly becomes technical, but $\mathbb{Z}_q[x]/(x^n-1)$ was initially considered (by Micciancio, for a Ring variant of the SIS problem). This polynomial is not irreducible (it has a root at $x = 1$). There is then a homomorphism (corresponding to evaluating polynomials at 1) that maps $a(x) \in\mathbb{Z}_q[x]/(x^n-1)\to \mathbb{Z}_q$, which leads to attacks. Anyway, this is relevant because the multiplication on $\mathbb{Z}_q[x]/(x^n-1)$ corresponds to cyclic permutations of the $\vec a$ (rather than the negacyclic ones described above).

This all means that the set of all RLWE instances can be viewed as a subset of the set of all LWE instances. From this perspective, RLWE can be no harder than LWE --- any algorithm breaking LWE equally breaks RLWE. One may wonder how much easier the "RLWE subset" is --- there are some known lattice problems where things get much easier when you assume structure (I believe SIVP is the main example). For the RLWE problem, there are additionally examples where if parameterized wrong things get easier, for example when you use $x^n-1$ an irreducible polynomial. There are also some non-trivial quantum attacks on a close variant of the SVP problem for RLWE instances (I believe it is the short principle generator problem).

None of the above implies (for polynomials such as $x^{2^k}+1$, that are commonly used) better attacks against RLWE than exist for LWE though. There are some authors (namely Bernstein) who believe the extra structure helps [1], but nothing has concretely been shown yet.

[1] He believes something more nuanced related to the size of Galois groups of the chosen polynomial $f(x)$ used in RLWE. The polynomial $x^{2^k}+1$ has a small Galois group, of size $O(\deg f)$. The size of the maximal galois group is $O((\deg f)!)$, much larger. Larger galois groups occur for random polynomials w.h.p., and are therefore "less structured". There are not known attacks utilizing the small Galois group of $x^{2^k}+1$.

"we can simply pick $a_i \in \mathbb{Z}_q[X]^n$" => I think it should be just $\mathbb{Z}_q^n$.

What you have to understand of this paragraph is the fact that encrypting

$\mu_0, \dots, \mu_{n-1}$ seen as a polynomial $\mu = \sum \mu_i X^i$ with RLWE and the polynomial $\sum a_i X^i$, is equivalent to encrypt each coordinate $\mu_j$ with LWE and the vector $\vec{a_j}=(a_{j}, a_{j+1}, \dots, a_{n-1}, -a_{1}, \dots, -a_{j-1})$.

Why is it true? Because if we look the coefficient of $X^j$ in $a*s +e + \mu \in \mathbb{Z}_q[X]^n$, we obtain exactly

$<a_j,s> + e_j + \mu_j$ (with $e_j$ the coefficient of $X^j$ for the polynomial $e$).

About the hardness of the assumptions: RLWE is a distinct (and easier) assumption than LWE. Its security has been studied independently. About the assumption you propose, but I only remark:

• You do not capture RLWE (because of the $-$).

• For some permutations, the problem becomes much easier:

For example, if $\sigma = (1,2)(3,4)\dots(n-1, n).$ (with your notation it's $i_j = i_j + 1$ if $i_j$ is odd, and $i_j -1$ if it's not).

Then we have $c_1= <a,s> + e_1 + \mu_1$, and $c_2 = \sum^{n/2}_{j=1} (a_{2j}s_{2j-1} + a_{2j-1}s_{2j}) + e_2 + \mu_2.$

Then $c_1 + c_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 + (\mu_1+ \mu_2).$

Then we have reduce the dimension of a factor $2$.

I would be tempted to generalise, and to say with a permutation of order $k$, you can reduce the dimension of a factor $k$ (then it's probably not secure).