# Adapting LWE Trapdoors for Ring-LWE

In the paper Trapdoors for Lattices: Simpler, Tighter, Faster, Smaller by Micciancio and Peikert, they present the following theorem about the existence of trapdoor for LWE.

Theorem 5.1: There is an algorithm $$\mathsf{GenTrap}(1^n,1^m,q)$$ that, given any $$n\geq 1, q\geq 2$$ and $$m=\mathcal{O}(n\log q)$$, outputs a matrix $$\mathbf{A}\in\mathbb{Z}^{n\times m}_q$$ and a trapdoor $$\mathbf{R}$$ such that:

1. $$\mathbf{A}$$ is indistinguishable from a uniformly chosen matrix; and
2. there is an algorithm $$\mathsf{Invert}$$ that, given $$\mathbf{b}=\mathbf{A}\mathbf{s}+\mathbf{e}$$ (with $$\mathbf{s}\in\mathbb{Z}^{n}_q$$, $$\mathbf{e}\in\mathbb{Z}^m$$ and $$||\mathbf{e}||) and a trapdoor $$\mathbf{R}$$, outputs $$\mathbf{s}$$ and $$\mathbf{e}.$$

They mention that the results in the paper can be straightforwardly adapted to the ring setting (Ring-LWE), however, they don't give details on that. What would be an equivalent result to this one in the ring setting?

Instead of plain matrix, a matrix similar this (but bigger):

+a -h -g -f -e -d -c -b
+b +a -h -g -f -e -d -c
+c +b +a -h -g -f -e -d
+d +c +b +a -h -g -f -e
+e +d +c +b +a -h -g -f
+f +e +d +c +b +a -h -g
+g +f +e +d +c +b +a -h
+h +g +f +e +d +c +b +a


which one can deduce it's equivalant in addition and multiplication to a polynomial reduced by $$X^8+1$$. And here, the polynomial is the "Ring".

And instead of plain matrix of $$n$$ x $$m$$, we use a $$1$$ x $$2$$ matrix of polynomials.

Note: the arithmetical difference between matrix-represented polynomial rings and plain matrices, is that the former is commutative in multiplication, while the latter is not.

• I think that the matrix $\textbf A$ should actually be replaced by a vector of independently sampled polynomials. The matrix you wrote here is actually the basis of the ideal lattice generated by the polynomial $f(x) = a + bx + cx^2 + ... + hx^7$ over the ring $\mathbb{Z}[x] / <x^8 + 1>$. – Hilder Vitor Lima Pereira Oct 30 '18 at 11:56
• Ok if we replace $A$ with another equivalent form for polynomial-case, then why the resulting matrix is close to uniform? I am not sure for the RLWE we can say case 1 of the above theorem is satisfied. – A.Soleimani Apr 28 '20 at 11:17
• I think point 1 should be instead interpreted as "$A$ is indistinguishable from a uniformly chosen polynomial" when adapted to ring setting. @A.Soleimani – DannyNiu Apr 29 '20 at 1:08
• for the product of two polynomials $a.b$ over the ring, we can represent it as a matrix multiplication $A\mathbf{b}$ where $A$ is similar to what you have written above and $\mathbf{b}$ is the vector representation of $b$. My question is that why $A$ has such structure? where can I find how $A$ is computed? I think it should be due to Chineas reminder. Do you have any reference? – A.Soleimani Oct 1 '20 at 13:40