Ring learning with errors: Difference between revisions

Revision as of 15:54, 4 July 2015

Revision as of 20:49, 4 July 2015

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 [[Shortest vector problem|Shortest Vector Problem]] (SVP) in a Lattice.<ref name=":0" />

=== Background ===

Line 46:

=== RLWE Cryptography ===

A major advantage that RLWE based cryptography has over the original [[Learning with errors|Learning With Errors]] (LWE) based cryptography is found in the size of the public and private keys. RLWE keys are roughly the square root of keys in LWE.<ref name=":0" /> For 128-bits of security an RLWE cryptographic algorithm would use public keys around 7000 bits in length.<ref>{{Cite journal|title = A Practical Key Exchange for the Internet using Lattice Cryptography|url = http://eprint.iacr.org/2015/138|date = 2015|first = Vikram|last = Singh}}</ref> The corresponding LWE scheme would require public keys of 49 million bits for the same level of security. On the other hand, RLWE keys are larger than the keys sizes for currently used public key algorithms like RSA and Elliptic Curve Diffie-Hellman which require public key sizes of 3072 bits and 256 bits, respectively, to achieve a 128-bit level of security.<ref>{{Cite journal|title = Key size|url = https://en.wikipedia.org/w/index.php?title=Key_size&oldid=668301843|date = 2015|language = en}}</ref> From a computational standpoint, however, RLWE algorithms have been shown to be the equal of or better than existing public key systems.<ref>{{Cite journal|title = Efficient Software Implementation of Ring-LWE Encryption|url = http://eprint.iacr.org/2014/725|date = 2014|first = Ruan de Clercq, Sujoy Sinha Roy, Frederik Vercauteren, Ingrid|last = Verbauwhede}}</ref>

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.

While there are a large number of different RLWE cryptographic algorithms that have been invented since their first appearance in 2012 but three classes of algorithms are noteworthy:

==== [[Ring learning with errors key exchange|Ring Learning with Errors Key Exchanges]] (RLWE-KEX) ====

A RLWE version of the classic Diffie-Hellman key exchange was designed by Peikert and published in early 2014.<ref name=":2" /> An RLWE version of the classic MQV variant of a Diffie-Hellman key exchange was later published by Zhang et. al.<ref>{{Cite journal|title = Authenticated Key Exchange from Ideal Lattices|url = http://eprint.iacr.org/2014/589|date = 2014|first = Jiang|last = Zhang|first2 = Zhenfeng|last2 = Zhang|first3 = Jintai|last3 = Ding|first4 = Michael|last4 = Snook|first5 = Özgür|last5 = Dagdelen}}</ref> The security of both key exchanges is directly related to the problem of finding approximate short vectors in an ideal lattice.

==== Ring Learning with Errors Signatures (RLWE-SIG) ====

A RLWE version of the classic [[Feige–Fiat–Shamir identification scheme|Feige-Fiat-Shamir Identification protocol]] was created and converted to a digital signature in 2011 by Lyubashevsky.<ref>{{Cite journal|title = Lattice Signatures Without Trapdoors|url = http://eprint.iacr.org/2011/537|date = 2011|first = Vadim|last = Lyubashevsky}}</ref> The details of this signature were extended in 2012 by Gunesyu, Lyubashevsky, and Popplemann in 2012 and published in their paper "Practical Lattice Based Cryptography - A Signature Scheme for Embedded Systems."<ref>{{Cite book|title = Practical Lattice-Based Cryptography: A Signature Scheme for Embedded Systems|url = http://link.springer.com/chapter/10.1007/978-3-642-33027-8_31|publisher = Springer Berlin Heidelberg|date = 2012|isbn = 978-3-642-33026-1|pages = 530-547|series = Lecture Notes in Computer Science|language = en|first = Tim|last = Güneysu|first2 = Vadim|last2 = Lyubashevsky|first3 = Thomas|last3 = Pöppelmann|editor-first = Emmanuel|editor-last = Prouff|editor-first2 = Patrick|editor-last2 = Schaumont}}</ref> These papers laid the groundwork for a variety of recent signature algorithms some based directly on the Ring Learning with Errors problem and some which are not tied to the same hard RLWE problems.<ref>{{Cite web|title = BLISS Signature Scheme|url = http://bliss.di.ens.fr/|website = bliss.di.ens.fr|accessdate = 2015-07-04}}</ref>

==== [[Homomorphic encryption|Ring Learning with Errors Homomorphic Encryption]] (RLWE-HOM) ====

security key sizes for RLWE cryptography

__NOINDEX__