Content deleted Content added
PotatoNinja (talk | contribs) m PotatoNinja moved page Draft:Ring Learning with Errors to Ring Learning with Errors: Publishing accepted Articles for creation submission (AFCH 0.9) |
PotatoNinja (talk | contribs) Cleaning up accepted Articles for creation submission (AFCH 0.9) |
||
Line 1:
Ring Learning with Errors (RLWE) is a [[computational problem]] which serves as the foundation of new cryptographic algorithms designed to protect against cryptanalysis by [[quantum computers]] and also to provide the basis for [[homomorphic encryption]]. RLWE is more properly called Learning with Errors over Rings and is simply the larger [[Learning with errors|Learning with Errors]] problem specialized to [[polynomial rings]] over finite fields.<ref name=":0" /> Because of the presumed difficulty of solving the RLWE problem even on a quantum computer, RLWE based cryptography may form the fundamental base for [[Public-key cryptography|public key cryptography]] in the future just as the [[integer factorization]] and [[discrete logarithm]] problem have served as the base for public key cryptography since the early 1980's.<ref name=":2">{{Cite book|title = Lattice Cryptography for the Internet|url = http://link.springer.com/chapter/10.1007/978-3-319-11659-4_12|publisher = Springer International Publishing|isbn = 978-3-319-11658-7|pages = 197-219|series = Lecture Notes in Computer Science|language = en|first = Chris|last = Peikert|editor-first = Michele|editor-last = Mosca}}</ref> An important feature of basing cryptography on the Ring Learning with Errors problem is the fact that the solution to the RLWE problem may be reducible to the [[NP-hard|NP-Hard]] [[Shortest vector problem|Shortest Vector Problem]] (SVP) in a Lattice.<ref name=":0" />
Line 43 ⟶ 42:
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>
Peikert believes that these security equivalences make the RLWE problem a good basis for future cryptography. He writes: ''"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).<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>
=== RLWE Cryptography ===
| |||