Ring learning with errors: Difference between revisions

Revision as of 21:27, 26 July 2015

Revision as of 03:59, 29 July 2015

Line 1:

{{Orphan|date=July 2015}}

'''Ring Learning with Errors (RLWE)''' is a [[computational problem]] which serves as the foundation of new cryptographic algorithms designed to protect against cryptanalysis by [[quantum computers]] and also to provide the basis for [[homomorphic encryption]]. RLWE is more properly called Learning with Errors over Rings and is simply the larger [[Learning with errors|Learning with Errors]] problem specialized to [[polynomial rings]] over finite fields.<ref name=":0" /> Because of the presumed difficulty of solving the RLWE problem even on a quantum computer, RLWE based cryptography may form the fundamental base for [[Public-key cryptography|public key cryptography]] in the future just as the [[integer factorization]] and [[discrete logarithm]] problem have served as the base for public key cryptography since the early 1980's.<ref name=":2">{{Cite book|title = Lattice Cryptography for the Internet|url = http://link.springer.com/chapter/10.1007/978-3-319-11659-4_12|publisher = Springer International Publishing|isbn = 978-3-319-11658-7|pages = 197–219|series = Lecture Notes in Computer Science|first = Chris|last = Peikert|editor-first = Michele|editor-last = Mosca}}</ref> An important feature of basing cryptography on the Ring Learning with Errors problem is the fact that the solution to the RLWE problem may be reducible to the [[NP-hard|NP-Hard]] [[Shortest vector problem|Shortest Vector Problem]] (SVP) in a Lattice.<ref name=":0" />

Line 21 ⟶ 19:

Randomly generating a "small" polynomial done by generating the coefficients of the polynomial from <math>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 b be an integer that is much less than q. If we randomly choose coefficients from the set: { -b, -b+1, -b+2. ... -2, -1, 0, 1, 2, ... , b-2, b-1, b} the polynomial will be small with respect to the bound (b).

# Using [[Gaussian function|Discrete Gaussian Sampling]] - For an odd value for q, the coefficients of the polynomial are randomly chosen by sampling from the set { -(q-1)/2 to (q-1)/2 } according to a discrete Gaussian distribution with mean 0 and distribution parameter σ. 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-180159–180|volume = 25|issue = 3|doi = 10.1007/s00200-014-0218-3|language = en|first = Nagarjun C.|last = Dwarakanath|first2 = Steven D.|last2 = Galbraith}}</ref>

== The RLWE Problem ==