Ring learning with errors: Difference between revisions

Revision as of 18:44, 3 July 2015

Revision as of 18:55, 3 July 2015

Line 38:

Their ring R is <math>Z[x]/\Phi(x)</math> and their R_q is <math>Z_q[x]/\Phi(x)</math>.

The average α-SVP is known to be NP-hard due to work by Daniele Micciancio in 2001.<ref>{{Cite journal|title = The Shortest Vector in a Lattice is Hard to Approximate to within Some Constant|url = http://epubs.siam.org/doi/abs/10.1137/S0097539700373039|journal = SIAM Journal on Computing|date = January 1, 2001|issn = 0097-5397|pages = 2008-2035|volume = 30|issue = 6|doi = 10.1137/S0097539700373039|first = D.|last = Micciancio}}</ref> However, there is not yet a proof to show that the difficulty of the α-SVP for ideal lattices is equivalent to the average α-SVP. Rather we have a proof that if there are '''ANY''' α-SVP instances that are hard to solve in ideal lattices then the RLWE Problem will be hard in random instances. <ref name=":0" />

In particular it is related to the difficulty of finding a vector shorter than an integer α times the length of the shortest vector in the lattice where α is constrained to be a polynomial function of the degree n. This is known as the "Approximate Shortest Vector Problem."

Researchers have shown that if the Approximate Shortest Vector Problem is hard to solve in the worst case then the decision version of the Ring Learning with Errors problem will be hard to solve in an average case. In other words, if any instance of the Approximate Short Vector Problem is hard in the lattice, then the RLWE will be hard for random instances of the problem.

=== RLWE Cryptography ===