Content deleted Content added
No edit summary |
started rlwe cryptography |
||
Line 38:
In that quote, The ring R is <math>Z[x]/\Phi(x)</math> and the ring R<sub>q</sub> is <math>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.<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
"There is a mathematical proof that the ''only'' way to break the cryptosystem (within some formal attack model) on its random instances is by being able to solve the underlying lattice problem in the ''worst case''."<ref>{{Cite web|title = What does GCHQ's “cautionary tale” mean for lattice cryptography?|url = http://www.cc.gatech.edu/~cpeikert/soliloquy.html|website = www.cc.gatech.edu|accessdate = 2015-07-03}}</ref>▼
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>
▲These security equivalences make the RLWE problem a good basis for future cryptography. Chris Peikert, one of the authors of the proof of this security reduction, states the following: "There is a mathematical proof that the ''only'' way to break the cryptosystem (within some formal attack model) on its random instances is by being able to solve the underlying lattice problem in the ''worst case"'' (emphasis in the original).
▲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 ===
Cryptography based on the RLWE problem is very efficient both when compared with cryptography based on its parent problem, [[Learning with errors|Learning with Errors]], and compared with current public key algorithms like the [[RSA (cryptosystem)|RSA]], [[Diffie–Hellman key exchange|Diffie-Hellman]] and [[Elliptic curve Diffie–Hellman|Elliptic Curve Diffie-Hellman]] algorithms.
__NOINDEX__
| |||