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}||<q/\mathcal{O}(\sqrt{n\log q})$) 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.

| improve this answer | |
  • 2
    $\begingroup$ 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>$. $\endgroup$ – Hilder Vitor Lima Pereira Oct 30 '18 at 11:56
  • $\begingroup$ 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. $\endgroup$ – A.Soleimani Apr 28 at 11:17
  • $\begingroup$ I think point 1 should be instead interpreted as "$A$ is indistinguishable from a uniformly chosen polynomial" when adapted to ring setting. @A.Soleimani $\endgroup$ – DannyNiu Apr 29 at 1:08
  • $\begingroup$ 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? $\endgroup$ – A.Soleimani Oct 1 at 13:40

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.