Content deleted Content added
→Background: Added condition to example methods to avoid confusion. When <math>q=p^n</math>, the elements of <math>F_q</math>, are not necessarily residues of integers. In such a circumstance ordering them linearly doesn’t make sense, and the iterative notation of the example means of generating “small” coefficients is incoherent. By adding the condition that <math>q</math> is a prime integer, that incoherence is excluded from consideration. Tags: Mobile edit Mobile web edit |
m Remove title case |
||
| (13 intermediate revisions by 10 users not shown) | |||
Line 1:
{{short description|Computational problem possibly useful for post-quantum cryptography}}
In [[post-quantum cryptography]], '''ring learning with errors''' ('''RLWE''') is a [[computational problem]] which serves as the foundation of new cryptographic [[algorithm]]s, such as [[NewHope]], designed to protect against [[cryptanalysis]] by [[quantum computers]] and also to provide the basis for [[homomorphic encryption]]. [[Public-key cryptography]] relies on construction of mathematical problems that are believed to be hard to solve if no further information is available, but are easy to solve if some information used in the problem construction is known. Some problems of this sort that are currently used in cryptography are at risk of attack if sufficiently large quantum computers can ever be built, so resistant problems are sought
▲In [[post-quantum cryptography]], '''ring learning with errors''' ('''RLWE''') is a [[computational problem]] which serves as the foundation of new cryptographic [[algorithm]]s, such as [[NewHope]], designed to protect against [[cryptanalysis]] by [[quantum computers]] and also to provide the basis for [[homomorphic encryption]]. [[Public-key cryptography]] relies on construction of mathematical problems that are believed to be hard to solve if no further information is available, but are easy to solve if some information used in the problem construction is known. Some problems of this sort that are currently used in cryptography are at risk of attack if sufficiently large quantum computers can ever be built, so resistant problems are sought. Homomorphic encryption is a form of encryption that allows computation on ciphertext, such as arithmetic on numeric values stored in an encrypted database.
RLWE is more properly called ''learning with errors over rings'' and is simply the larger [[learning with errors]] (LWE) problem specialized to [[polynomial
== Background ==
Line 22 ⟶ 21:
Randomly generating a "small" polynomial is done by generating the coefficients of the polynomial from <math>\mathbf{F}_q</math> in a way that either guarantees or makes very likely small coefficients. When <math>q</math> is a prime integer, 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|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, \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
== The RLWE
The RLWE problem can be stated in two different ways: a "search" version and a "decision" version. Both begin with the same construction. Let
* <math>a_i(x)</math> be a set of random but '''known''' polynomials from <math>\mathbf{F}_q[x]/\Phi(x)</math> with coefficients from all of <math>\mathbf{F}_q</math>.
Line 36 ⟶ 35:
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>\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>\mathbf{F}_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
:''"... 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}_q</math> (with high probability, for any <math>s</math>) from arbitrarily many noisy products."''<ref name=":0" />
Line 45 ⟶ 44:
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| journal=Cryptology ePrint Archive }}</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|access-date = 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|access-date = 2016-01-05 |archive-url = https://web.archive.org/web/20160317165656/http://web.eecs.umich.edu/~cpeikert/soliloquy.html |archive-date = 2016-03-17}}</ref>
== RLWE
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| journal=Cryptology ePrint Archive }}</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| journal=Cryptology ePrint Archive }}</ref>
Three groups of RLWE cryptographic algorithms exist:
Line 56 ⟶ 55:
=== Ring learning with errors key exchanges (RLWE-KEX) ===
{{main|Ring learning with errors key exchange}}
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|last1=Ding|first1=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|journal=Cryptology ePrint Archive |url=http://eprint.iacr.org/2012/688}}</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|journal=Cryptology ePrint Archive |url=http://eprint.iacr.org/2014/070}}</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|first1 = Jiang|last1 = Zhang|first2 = Zhenfeng|last2 = Zhang|first3 = Jintai|last3 = Ding|first4 = Michael|last4 = Snook|first5 = Özgür|last5 = Dagdelen| journal=Cryptology ePrint Archive }}</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) ===
{{main|Ring learning with errors signature}}
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| journal=Cryptology ePrint Archive }}</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|publisher = Springer Berlin Heidelberg|date = 2012|isbn = 978-3-642-33026-1|pages = 530–547|series = Lecture Notes in Computer Science|first1 = Tim|last1 = Güneysu|first2 = Vadim|last2 = Lyubashevsky|first3 = Thomas|last3 = Pöppelmann|editor-first = Emmanuel|editor-last = Prouff|editor-first2 = Patrick|editor-last2 = Schaumont|doi = 10.1007/978-3-642-33027-8_31}}</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|access-date = 2015-07-04}}</ref>
=== Ring learning with errors homomorphic encryption (RLWE-HOM) ===
{{main|Homomorphic encryption}}
Homomorphic encryption is type of encryption that allows computations to be performed on encrypted data without first having to decrypt it. The purpose of
==References==
Line 75 ⟶ 74:
[[Category:Computational problems]]
[[Category:Computational hardness assumptions]]
[[Category:Post-quantum cryptography]]
[[Category:Lattice-based cryptography]]
| |||