Content deleted Content added
Carvalho1988 (talk | contribs) →Ring Learning with Errors Homomorphic Encryption (RLWE-HOM): Added link to various proposals for RLWE signatures and Key Exchanges |
→Security Reduction: added clarification of misleading parameter. |
||
Line 43:
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{Z}_q[x]/\Phi(x)</math>.
The α-SVP in regular lattices is known to be [[NP-hard]] due to work by Daniele Micciancio in 2001, although not for values of α required for a reduction to general Learning With Errors problem.<ref name=":1">{{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" />
Regarding the difficulty of Shortest Vector Problems in Ideal Lattices, researcher Michael Schneider writes, ''"So far there is no SVP algorithm making use of the special structure of ideal lattices. It is widely believed that solving SVP (and all other lattice problems) in ideal lattices is as hard as in regular lattices."''<ref>{{Cite journal|title = Sieving for Shortest Vectors in Ideal Lattices|url = http://eprint.iacr.org/2011/458|date = 2011|first = Michael|last = Schneider}}</ref> The difficulty of these problems on regular lattices is provably [[NP-hard]].<ref name=":1" /> There are, however, a minority of researchers who do not believe that ideal lattices share the same security properties as regular lattices.<ref>{{Cite web|title = cr.yp.to: 2014.02.13: A subfield-logarithm attack against ideal lattices|url = http://blog.cr.yp.to/20140213-ideal.html|website = blog.cr.yp.to|accessdate = 2015-07-03}}</ref>
| |||