2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – user6584 Dec 3 '17 at 19:04
3
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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