# Parameters for ring-LWE

I see on eprint that there are many papers suggesting ways to compute parameters for LWE. How can those be used to compute parameters for ring-LWE (assuming that known algorithms solving LWE are the best for solving ring-LWE)?

Specifically, consider the ring $R_q = \mathbb{Z}_q[X]/(X^n + 1)$. How can an R-LWE instance $(a, as+e)$ in that ring be transformed into an LWE instance $(A, As+e)$? I am missing in particular how to get $m > n$ linear equations from what appear to be only $n$ linear constraints in the original system.

• Just as a followup to my original question: an RLWE instance does indeed give only n linear constraints. And so if s is unconstrained then there are many solutions. So RLWE is only interested when (1) there is an added constraint that s is "short" or (2) there is more than one equation involving s. – user6584 Dec 3 '17 at 19:04

As mentioned by Peikert in [Pei16]:

*) Ring-LWE is parametrized by a ring $R$ of degree $n$ over $\mathbb{Z}$, a positive integer modulus $q$ defining the quotient ring $R_q=R/qR$, and an error distribution $\mathcal{X}$ over $R$.

**) Left-multiplication by any fixed $a\in R_q$ is a $\mathbb{Z}$-linear function from $R$ to $R_q$, so it can be represented by a square matrix $\mathbf{A}_a \in \mathbb{Z}_q^{n \times n}$, which maps $\mathbb{Z}^n$ to $\mathbb{Z}_q^n$.

For example, for $R=\mathbb{Z}[X]/(X^3+1)$ and $R_5=\mathbb{Z}_5[X]/(X^3+1)$, fix $a=3+2X+4X^2 \in R_5$. For $z=1+10X^2 \in R$, we have: $$a.z = 4X^2+2X+3 \in R_5$$ Now, consider the matrix representation of $a$ and $z$: $$\mathbf{A}=\begin{bmatrix} 3 & -4 & -2\\ 2 & 3 & -4 \\ 4 & 2 & 3 \end{bmatrix} = \begin{bmatrix} 3 & 1 & 3\\ 2 & 3 & 1 \\ 4 & 2 & 3 \end{bmatrix} \in \mathbb{Z}_5^3 \qquad ; \qquad \mathbf{z}=\begin{bmatrix} 1\\ 0 \\ 10 \end{bmatrix}$$ We have: $$\mathbf{A.z}=\begin{bmatrix} 3 & 1 & 3\\ 2 & 3 & 1 \\ 4 & 2 & 3 \end{bmatrix}\begin{bmatrix} 1\\ 0 \\ 10 \end{bmatrix}=\begin{bmatrix} 33\\ 12 \\ 34 \end{bmatrix}=\begin{bmatrix} 3\\ 2 \\ 4 \end{bmatrix} \in \mathbb{Z}_5^3$$ which is the matrix representation of $a.z$.

Now from these results, it is easy to see that each random element $a\in R_q$ corresponds to $n$ $\textit{related}$ (non-independent) vectors $\mathbf{a}\in \mathbb{Z}_q^n$, where $n$ is the degree of the ring $R$ over $\mathbb{Z}$.