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


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

  • $\begingroup$ 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 ? $\endgroup$
    – rerouille
    Mar 7 at 15:04
  • $\begingroup$ @rerouille $A$ is just a formal notation whose only purpose is to show that RLWE is a special case of LWE. $\endgroup$
    – Daniel S
    Mar 7 at 15:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.