4
$\begingroup$

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?

$\endgroup$

1 Answer 1

2
$\begingroup$

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.

$\endgroup$
4
  • 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$ Oct 30, 2018 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.Solei
    Apr 28, 2020 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, 2020 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.Solei
    Oct 1, 2020 at 13:40

Your Answer

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

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