Content deleted Content added
Carvalho1988 (talk | contribs) Changed the notation to be consistent with F_q being the label for the field of integers mod a prime number q. As noted some people write this as Z_q . This however is the standard way of labelling the q-adic numbers. If someone wants to change it back please make sure the change is done consistently |
m Remove title case |
||
| (32 intermediate revisions by 21 users not shown) | |||
Line 1:
{{short description|Computational problem possibly useful for post-quantum cryptography}}
In [[post-quantum cryptography]], '''
RLWE is more properly called == 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
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 9 ⟶ 11:
:<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>). The RLWE context works with a finite
If the degree of the polynomial <math>\Phi(x)</math> is <math display="inline">n</math>, the
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 (also called the [[uniform norm]]). 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>.
Line 17 ⟶ 19:
The final concept necessary to understand the RLWE problem is the generation of random polynomials in <math>\mathbf{F}_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>.
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.
# 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 [[
== 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 33 ⟶ 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{
In that quote, The ring <math>\mathbf{R}</math> is <math>\mathbf{Z}[x]/\Phi(x)</math> and the ring <math>\mathbf{R}_q</math> is <math>\mathbf{F}_q[x]/\Phi(x)</math>.
Line 42 ⟶ 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
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|
== 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
Three groups of RLWE cryptographic algorithms exist:
Line 53 ⟶ 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|
In 2014, Peikert<ref>{{Cite journal|last=Peikert|first=Chris|date=2014-01-01|title=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|
=== 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 79 ⟶ 74:
[[Category:Computational problems]]
[[Category:Computational hardness assumptions]]
[[Category:Post-quantum cryptography]]
[[Category:Lattice-based cryptography]]
| |||