Ring learning with errors: Difference between revisions

Revision as of 18:19, 2 February 2016

Revision as of 18:52, 2 February 2016

Line 6:

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:

:<math>a(x) = a_0 + a_1x + a_2x^2 + ... + 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}/qZq\mathbf{Z} = F_q\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">F_q\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">F_q\mathbf{F}_q[x]</math> modulo an [[irreducible polynomial]] <math display="inline">\Phi(x)</math>. This finite quotient ring can be written as <math>F_q\mathbf{F}_q[x]/\Phi(x)</math> though many authors write <math>Z_q\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>Z_q\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>F_q\mathbf{F}_q</math>, where <math>F_q\mathbf{F}_q</math> is typically represented as the set: <math>(\{-(q-1)/2, ..., -1, 0, 1, ..., (q-1)/2)\}</math>.

Randomly generating a "small" polynomial done by generating the coefficients of the polynomial from <math>F_q\mathbf{F}_q</math> in a way that either guarantees or makes very likely small coefficients. There are two common ways to do this:

# Using Uniform Sampling -– The coefficients of the small polynomial are uniformly sampled from a set of small coefficients. Let <math display="inline">b</math> be an integer that is much less than <math display="inline">q</math>. If we randomly choose coefficients from the set: <math display="inline">\{ -b, -b+1, -b+2., ...\ldots , -2, -1, 0, 1, 2, ...\ldots , b-2, b-1, b \}</math> the polynomial will be small with respect to the bound (<math display="inline">b</math>).

# Using [[Gaussian function|Discrete Gaussian Sampling]] - – For an odd value for <math display="inline">q</math>, the coefficients of the polynomial are randomly chosen by sampling from the set <math display="inline"> \{ -(q-1)/2, to\ldots , (q-1)/2 \} </math> according to a discrete Gaussian distribution with mean <math>0</math> and distribution parameter σ<math display="inline">\sigma</math>. The references describe in full detail how this can be accomplished. It is more complicated than uniform sampling but it allows for a proof of security of the algorithm. The paper, "Sampling from Discrete Gaussians for Lattice-Based Cryptography on a Constrained Device," by Dwarakanath and Galbraith provide an overview of this problem.<ref>{{Cite journal|title = Sampling from discrete Gaussians for lattice-based cryptography on a constrained device|url = http://link.springer.com/article/10.1007/s00200-014-0218-3|journal = Applicable Algebra in Engineering, Communication and Computing|date = 2014-03-18|issn = 0938-1279|pages = 159–180|volume = 25|issue = 3|doi = 10.1007/s00200-014-0218-3|first = Nagarjun C.|last = Dwarakanath|first2 = Steven D.|last2 = Galbraith}}</ref>

== 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\mathbf{Z}_q[x]/\Phi(x)</math> with coefficients from all of <math>F_q\mathbf{F}_q</math>.

* <math>e_i(x)</math> be a set of small random and '''unknown''' polynomials relative to a bound <math>b</math> in the ring <math>Z_q\mathbf{Z}_q[x]/\Phi(x)</math>

* <math>s(x)</math> be a small '''unknown''' polynomial relative to a bound <math>b</math> in the ring <math>Z_q\mathbf{Z}_q[x]/\Phi(x)</math>.

* <math>b_i(x) = (a_i(x)\cdot s(x)) + e_i(x)</math>

Given the list of polynomial pairs <math>( a_i(x), b_i(x) )</math> find the unknown polynomial <math>s(x)</math>

Using the same definitions, the Decision version of the problem can be stated as follows. Given a list of polynomial pairs <math>( a_i(x), b_i(x) )</math> determine whether the <math>b_i(x)</math> polynomials were constructed as <math>b_i(x) = (a_i(x)\cdot s(x)) + e_i(x)</math> or were generated randomly from <math>Z_q\mathbf{Z}_q[x]/\Phi(x)</math> with coefficients from all of <math>F_q\mathbf{F}_q</math>.

The difficulty of this problem is parameterized by the choice of the quotient polynomial ( <math>\Phi(x)</math> ), its degree (<math>n</math>), the field (<math>F_q\mathbf{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\mathbf{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>\mathbf{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:

:''"... we give a quantum reduction from approximate SVP (in the worst case) on ideal lattices in <math>\mathbf{R}</math> to the search version of ring-LWE, where the goal is to recover the secret <math>s ∈\in \mathbf{R<sub>q}_q</submath> (with high probability, for any <math>s</math>) from arbitrarily many noisy products."''<ref name=":0" />

In that quote, The ring <math>\mathbf{R}</math> is <math>\mathbf{Z}[x]/\Phi(x)</math> and the ring R<submath>q\mathbf{R}_q</submath> is <math>Z_q\mathbf{Z}_q[x]/\Phi(x)</math>.

The α-SVP in regular lattices is known to be [[NP-hard]] due to work by Daniele Micciancio in 2001.<ref name=":1">{{Cite journal|title = The Shortest Vector in a Lattice is Hard to Approximate to within Some Constant|url = http://epubs.siam.org/doi/abs/10.1137/S0097539700373039|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}}</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'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://www.cc.gatech.edu/~cpeikert/soliloquy.html|website = www.cc.gatech.edu|accessdate = 2015-07-03}}</ref>

Line 61:

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