Content deleted Content added
Carvalho1988 (talk | contribs) changed sub-ring to quotient ring |
"In the first component we give a quantum reduction from approximate SVP (in the worst case) on ideal lattices in R to the search version of ring-LWE, where the goal is to recover the secret s ∈ Rq (with high probability, for any s) from arbitrarily many noisy products" is the correct quote (changed F_q to R_q) |
||
Line 36:
In cases where the polynomial <math>\Phi(x)</math> is a [[cyclotomic polynomial]], the difficulty of solving the search version of RLWE problem is equivalent to finding a short vector (but not necessarily the shortest vector) in an ideal lattice formed from elements of <math>\mathbf{Z}[x]/\Phi(x)</math> represented as integer vectors.<ref name=":0">{{Cite journal|title = On Ideal Lattices and Learning with Errors Over Rings|url = http://eprint.iacr.org/2012/230|date = 2012|first = Vadim|last = Lyubashevsky|first2 = Chris|last2 = Peikert|first3 = Oded|last3 = Regev}}</ref> This problem is commonly known as the [[Shortest vector problem|Approximate Shortest Vector Problem (α-SVP)]] and it is the problem of finding a vector shorter than α times the shortest vector. The authors of the proof for this equivalence write:
:''"... we give a quantum reduction from approximate SVP (in the worst case) on ideal lattices in <math>\mathbf{R}</math> to the search version of ring-LWE, where the goal is to recover the secret <math>s \in \mathbf{
In that quote, The ring <math>\mathbf{R}</math> is <math>\mathbf{Z}[x]/\Phi(x)</math> and the ring <math>\mathbf{R}_q</math> is <math>\mathbf{F}_q[x]/\Phi(x)</math>.
| |||