Ring learning with errors: Difference between revisions

Revision as of 20:10, 24 June 2019

Revision as of 20:15, 13 July 2019

Line 3:

== Background ==

The security of modern cryptography, in particular [[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. The classic example that has been used since the 1970s is the [[integer factorization]] problem. 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.<ref>{{cite conference |url=https://ieeexplore.ieee.org/document/365700 |title=Algorithms for quantum computation: discrete logarithms and factoring |first=Peter |last=Shor |date=20 November 1994 |conference=35th Annual Symposium on Foundations of Computer Science |publisher=IEEE |archive-date=6 August 2002 |___location=Santa Fe |isbn=0-8186-6580-7 |doi=10.1109/SFCS.1994.365700 |access-date=8 January 2019 |quote="This paper gives Las Vegas algorithms for finding discrete logarithms and factoring integers on a quantum computer that take a number of steps which is polynomial in the input size, e.g., the number of digits of the integer to be factored. These two problems are generally considered hard on a classical computer and have been used as the basis of several proposed cryptosystems."}}</ref> 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.

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

The α-SVP in regular lattices is known to be [[NP-hard]] due to work by Daniele Micciancio in 2001, although not for values of α required for a reduction to general learning with errors problem.<ref name=":1">{{Cite journal|title = The Shortest Vector in a Lattice is Hard to Approximate to within Some Constant|journal = SIAM Journal on Computing|date = January 1, 2001|issn = 0097-5397|pages = 2008–2035|volume = 30|issue = 6|doi = 10.1137/S0097539700373039|first = D.|last = Micciancio|citeseerx = 10.1.1.93.6646}}</ref> However, there is not yet a proof to show that the difficulty of the α-SVP for ideal lattices is equivalent to the average α-SVP. Rather we have a proof that if there are ''any'' α-SVP instances that are hard to solve in ideal lattices then the RLWE Problem will be hard in random instances.<ref name=":0" />

Regarding the difficulty of Shortest Vector Problems in Ideal Lattices, researcher Michael Schneider writes, ''"So far there is no SVP algorithm making use of the special structure of ideal lattices. It is widely believed that solving SVP (and all other lattice problems) in ideal lattices is as hard as in regular lattices."''<ref>{{Cite journal|title = Sieving for Shortest Vectors in Ideal Lattices|url = http://eprint.iacr.org/2011/458|date = 2011|first = Michael|last = Schneider}}</ref> The difficulty of these problems on regular lattices is provably [[NP-hard]].<ref name=":1" /> There are, however, a minority of researchers who do not believe that ideal lattices share the same security properties as regular lattices.<ref>{{Cite web|title = cr.yp.to: 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://web.eecs.umich.edu/~cpeikert/soliloquy.html |website = www.eecs.umich.edu|accessdate = 2016-01-05 |archiveurl = https://web.archive.org/web/20160317165656/http://web.eecs.umich.edu/~cpeikert/soliloquy.html |archivedate = 2016-03-17}}</ref>

== RLWE Cryptography ==

A major advantage that RLWE based cryptography has over the original 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" />{{failed verification|date=August 2016}} 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 size]]s of 3072 bits and 256 bits, respectively, to achieve a 128-bit level of security. 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 55:

The fundamental idea of using LWE and Ring LWE for key exchange was proposed and filed at the University of Cincinnati in 2011 by Jintai Ding. The basic idea comes from the associativity of matrix multiplications, and the errors are used to provide the security. The paper<ref>{{Cite journal|last=Ding|first=Jintai|last2=Xie|first2=Xiang|last3=Lin|first3=Xiaodong|date=2012-01-01|title=A Simple Provably Secure Key Exchange Scheme Based on the Learning with Errors Problem|url=http://eprint.iacr.org/2012/688|journal=|volume=|issue=|doi=|pmid=|access-date=|via=}}</ref> appeared in 2012 after a provisional patent application was filed in 2012.

In 2014, Peikert<ref>{{Cite journal|last=Peikert|first=Chris|date=2014-01-01|title=Lattice Cryptography for the Internet|url=http://eprint.iacr.org/2014/070|journal=|volume=|issue=|doi=|pmid=|access-date=|via=}}</ref> presented a key transport scheme following the same basic idea of Ding's, where the new idea of sending additional 1 bit signal for rounding in Ding's construction is also utilized. 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 (RLWE-SIG) ===