Ring learning with errors: Difference between revisions

Revision as of 07:11, 22 July 2015

Revision as of 04:05, 23 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|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|language = en}}</ref> The classic example that has been used since the 1970's 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|language = en}}</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|language = en}}</ref>

Line 18 ⟶ 19:

To randomly generate a "small" polynomial we select a bound for the infinity norm, <math>b<<q</math> and then randomly sample the n coefficients from the set: <math>(-b, ..., -1, 0, 1, ..., b)</math>. A typical value for <math>b</math> is 1, so the coefficients are simply chosen from -1, 0, and 1.

=== The RLWE Problem ===

The RLWE problem can be stated in two different ways. One is called the "Search" version and the other is the "Decision" version. The Search can be stated as follows. Let

* <math>a_i(x)</math> be a set of random but '''known''' polynomials from <math>Z_q[x]/\Phi(x)</math> with coefficients from all of <math>F_q</math>.

Line 30 ⟶ 32:

The difficulty of this problem is parameterized by the choice of the quotient polynomial ( <math>\Phi(x)</math> ), its degree (n), the field (<math>F_q</math>), and the smallness bound (<math>b</math>). In many RLWE based public key algorithms the private key will be a pair of small polynomials <math>s(x)</math> and <math>e(x)</math>. The corresponding public key will be a pair of polynomials <math>a(x)</math>, selected randomly from <math>Z_q[x]/\Phi(x)</math>, and the polynomial <math>t(x)= (a(x)\cdot s(x)) + e(x)</math>. Given <math>a(x)</math> and <math>t(x)</math>, it should be computationally infeasible to recover the polynomial <math>s(x)</math>

=== Security Reduction ===

In cases where the polynomial <math>\Phi(x)</math> is a cyclotomic polynomial, the difficulty of solving the search version of RLWE problem is equivalent to finding a short vector (but not necessarily the shortest) vector in an ideal lattice formed from elements of <math>Z[x]/\Phi(x)</math> represented as integer vectors.<ref name=":0">{{Cite journal|title = On Ideal Lattices and Learning with Errors Over Rings|url = http://eprint.iacr.org/2012/230|date = 2012|first = Vadim|last = Lyubashevsky|first2 = Chris|last2 = Peikert|first3 = Oded|last3 = Regev}}</ref> This problem is commonly known as the [[Shortest vector problem|Approximate Shortest Vector Problem (α-SVP)]] and it is the problem of finding a vector shorter than α times the shortest vector. The authors of the proof for this equivalence write:

Line 44 ⟶ 47:

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 ===

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|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>

Three groups of RLWE cryptographic algorithms exist:

==== [[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 signature|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) ====

The purpose of [[homomorphic encryption]] is to allow the computations on sensitive data to occur on computing devices that should not be trusted with the data. These computing devices are allowed to process the ciphertext which is output from a homomorphic encryption.<ref>{{Cite journal|title = Homomorphic encryption|url = https://en.wikipedia.org/w/index.php?title=Homomorphic_encryption&oldid=668290551|date = 2015-06-23|language = en}}</ref> In 2011, Brakersky and Vaikuntanathan, published "Fully Homomorphic Encryption from Ring-LWE and Security for Key Dependent Messages" which builds a homomorphic encryption scheme directly on the RLWE problem.<ref>{{Cite book|title = Fully Homomorphic Encryption from Ring-LWE and Security for Key Dependent Messages|url = http://link.springer.com/chapter/10.1007/978-3-642-22792-9_29|publisher = Springer Berlin Heidelberg|date = 2011|isbn = 978-3-642-22791-2|pages = 505-524|series = Lecture Notes in Computer Science|language = en|first = Zvika|last = Brakerski|first2 = Vinod|last2 = Vaikuntanathan|editor-first = Phillip|editor-last = Rogaway}}</ref>