3
$\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
$\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$
  • 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 Vítor Lima Pereira Oct 30 '18 at 11:56

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.