Ring learning with errors: Difference between revisions

Revision as of 19:30, 19 July 2016

Revision as of 07:54, 20 July 2016

Line 4:

== Background ==

The security of modern cryptography, in particular [[Public-key cryptography|Public Key Cryptography]], is based on the assumed intractability of solving certain computational problems 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 1970s 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 <math display="inline">a(x)</math> is expressed as:

Line 10:

:<math>a(x) = a_0 + a_1x + a_2x^2 + \ldots + a_{n-2}x^{n-2} + a_{n-1}x^{n-1}</math>

Polynomials can be added and multiplied in the usual fashion. In the RLWE context the coefficients of the polynomials and all operations involving those coefficients will be done in a finite field, typically the field <math display="inline">\mathbf{Z}/q\mathbf{Z} = \mathbf{F}_q</math> for a prime integer <math display="inline">q</math>. The set of polynomials over a finite field with the operations of addition and multiplication forms an infinite [[polynomial ring]] (<math display="inline">\mathbf{F}_q[x]</math>).<ref>{{Cite journal|title = Polynomial ring|url = https://en.wikipedia.org/w/index.php?title=Polynomial_ring&oldid=661646453|date = 2015}}</ref> The RLWE context works with a finite sub-ring of this infinite ring. The sub-ring is typically the finite [[Quotient ring|quotient (factor) ring]] formed by reducing all of the polynomials in <math display="inline">\mathbf{F}_q[x]</math> modulo an [[irreducible polynomial]] <math display="inline">\Phi(x)</math>. This finite quotient ring can be written as <math>\mathbf{F}_q[x]/\Phi(x)</math> though many authors write <math>\mathbf{Z}_q[x]/\Phi(x)</math> .<ref name=":0" />

If the degree polynomial <math>\Phi(x)</math> is <math display="inline">n</math>, the sub-ring becomes the ring of polynomials of degree less than n modulo <math>\Phi(x)</math> with coefficients from <math>F_q</math>. The values <math display="inline">n</math>, <math display="inline">q</math>, together with the polynomial <math>\Phi(x)</math> partially define the mathematical context for the RLWE problem.

Another concept necessary for the RLWE problem is the idea of "small" polynomials with respect to some norm. The typical norm used in the RLWE problem is known as the [[infinity norm]].<ref>{{Cite journal|title = Norm (mathematics)|url = https://en.wikipedia.org/w/index.php?title=Norm_(mathematics)&oldid=667112150|date = 2015}}</ref> The infinity norm of a polynomial is simply the largest coefficient of the polynomial when these coefficients are viewed as integers. Hence, <math>||a(x)||_\infty = b</math> states that the [[infinity norm]] of the polynomial <math>a(x)</math> is <math>b</math>. Thus <math>b</math> is the largest coefficient of <math>a(x)</math>.

The final concept necessary to understand the RLWE problem is the generation of random polynomials in <math>\mathbf{Z}_q[x]/\Phi(x)</math> and the generation of "small" polynomials . A random polynomial is easily generated by simply randomly sampling the <math>n</math> coefficients of the polynomial from <math>\mathbf{F}_q</math>, where <math>\mathbf{F}_q</math> is typically represented as the set <math>\{-(q-1)/2, ..., -1, 0, 1, ..., (q-1)/2\}</math>.

Line 51:

== 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 sizessize]]s 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:

Line 57:

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

Line 65:

=== [[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}}</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|first = Zvika|last = Brakerski|first2 = Vinod|last2 = Vaikuntanathan|editor-first = Phillip|editor-last = Rogaway}}</ref>

The various sets of parameters that have been proposed by different groups of researchers for Ring Learning with Errors Key Exchange and Signatures are found at the Ring Learning with Errors information site ([http://www.ringlwe.info/parameters-for-rlwe.html ringlwe.info])<ref>{{Cite web