Ring learning with errors: Difference between revisions

Revision as of 20:43, 13 November 2024

Latest revision as of 19:28, 17 May 2025

(One intermediate revision by one other user not shown)

Line 23:

# 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 provides an overview of this problem.<ref>{{Cite journal|title = Sampling from discrete Gaussians for lattice-based cryptography on a constrained device|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|first1 = Nagarjun C.|last1 = Dwarakanath|first2 = Steven D.|last2 = Galbraith|s2cid = 13718364|citeseerx = 10.1.1.716.376}}</ref>

== The RLWE Problemproblem ==

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 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 Reductionreduction ==

In cases where the polynomial <math>\Phi(x)</math> is a [[cyclotomic polynomial]], theThe 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|first1 = Vadim|last1 = Lyubashevsky|first2 = Chris|last2 = Peikert|first3 = Oded|last3 = Regev| journal=Cryptology ePrint Archive }}</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}_q</math> (with high probability, for any <math>s</math>) from arbitrarily many noisy products."''<ref name=":0" />

Line 48:

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 Cryptographycryptography ==

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>