Content deleted Content added
No edit summary |
added reference regarding Dan Bernstein's criticism of the security of the RLWE problem |
||
Line 40:
The α-SVP in regular lattices is known to be [[NP-hard]] due to work by Daniele Micciancio in 2001.<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 difficult 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>
=== RLWE Cryptography ===
| |||