'''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's1980s.<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|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" />
== Background ==
The security of modern cryptography, in particular [[Public-key cryptography|Public Key Cryptography]], is based on the difficulty of solving computational problems believed to be intractable if the size of the problem is large enough and the instance of the problem to be solved is chosen randomly.<ref>{{Cite journal|title = Public-key cryptography|url = https://en.wikipedia.org/w/index.php?title=Public-key_cryptography&oldid=670016308|date = 2015}}</ref> The classic example that has been used since the 1970's1970s is the [[integer factorization]] problem.<ref>{{Cite journal|title = RSA (cryptosystem)|url = https://en.wikipedia.org/w/index.php?title=RSA_(cryptosystem)&oldid=669826149|date = 2015}}</ref> It is believed that it is computationally intractable to factor the product of two prime numbers if those prime numbers are large enough and chosen at random. As of 2015 research has led to the factorization of the product of two 384-bit primes but not the product of two 512-bit primes. Integer factorization forms the basis of the widely used [[RSA (cryptosystem)|RSA]] cryptographic algorithm.<ref>{{Cite journal|title = Integer factorization records|url = https://en.wikipedia.org/w/index.php?title=Integer_factorization_records&oldid=669003206|date = 2015}}</ref>
The Ring Learning with Errors (RLWE) problem is built on the arithmetic of [[polynomials]] with coefficients from a [[finite field]].<ref name=":0" /> A typical polynomial a(x) is expressed as:
Line 50:
== 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.<ref name=":0" /> 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}}</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>
Three groups of RLWE cryptographic algorithms exist:
