Understanding RLWE Encryption

Question

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$.

Answer 1

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$.