# Understanding RLWE Encryption

LWE Encryption Scheme by Regev is inefficient due to its public key sizes in $$O(n^2)$$. This led to the variant problem RLWE, defined in this paper :

Let $$n$$ be a power of two, and q a prime satisfying $$q = 1 \mod 2n$$. We define $$R_q = (\mathbb{Z}/q\mathbb{Z})[X] / (X^N+1)$$, which is the polynomials with coefficients in $$\mathbb{Z}/q\mathbb{Z}$$ considered modulus $$X^N+1$$ ($$X^N = -1$$). We choose $$s \in R_q$$ our secret, and $$\chi_{R_q}$$ an error distribution. A sample from the LWE distribution is :

$$(a,b) = (a, a\cdot s + e)$$

with $$a \overset{\\\}{\leftarrow} \mathcal{U}(R_q)$$ and $$e \overset{\\\}{\leftarrow} \chi_{R_q}$$.

In the same paper, the RLWE-based encryption has $$(a,b)$$ as a public key, and the encryption for $$m \in \{0,1\}^n$$ is $$c=(u,v)$$ with :

$$u = a \cdot r + e_1 \mod q \qquad v = b \cdot r + e_2 + \lfloor q/2 \rfloor m \mod q$$

with $$r$$ chosen randomly in $$R_q$$ and $$e_1,e_2$$ errors in $$R_q$$.

However, I've seen in various papers, like this one, that the advantage comes from choosing a single sample $$A_1 = (a_1,\cdots,a_n)$$ and construct the other vectors $$A_i = (a_i,\cdots,a_n,-a_1,\cdots,-a_{i-1})$$ because we only need to store $$A_1$$, so the key size is $$O(n)$$. I don't see what role these vectors $$(A_i)_{2 \leq i \leq n}$$ play in the encryption considering that it seems we only need $$a$$.

These vectors represent the elements of $$R_q$$ given by $$a,aX,\ldots aX^{n-1}$$. Specifically if we write $$a=a_1X^{n-1}+a_2X^{n-2}+\cdots a_{n-1}X+a_n$$, where the $$a_j$$ are elements pf $$\mathbb Z/q\mathbb Z$$, then $$aX^{i-1}=a_iX^{n-1}+a_{i+1}X^{n-2}+\cdots+a_nX^i-a_1X^{i-1}-\cdots-a_{i-1}.$$
If we similarly write $$s=s_1+s_2X+\cdots+s_nX^{n-1}$$ then to multiply $$a$$ by $$s$$ we can compute $$\sum_{i=1}^n aX^{i-1}s_i$$. The coefficients of the polynomial given by this sum can then be calculated by $$A{\mathbf s}$$ where $$A$$ is the matrix with rows $$A_i$$ and $$\mathbf s$$ is a column vector with entries $$s_n,s_{n-1},\ldots, s_1$$.
• So essentially, this matrix $A$ is used to speed up multiplication, like when you compute $a \cdot r$ in the encryption ? This is its only purpose ? Mar 7 at 15:04
• @rerouille $A$ is just a formal notation whose only purpose is to show that RLWE is a special case of LWE. Mar 7 at 15:12