Ring learning with errors: Difference between revisions

Revision as of 07:37, 23 July 2015

Revision as of 21:27, 26 July 2015

Line 17:

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[x]/\Phi(x)</math> and the generation of "small" polynomials . A random Thispolynomial is easily donegenerated by simply randomly sampling the n coefficients of the polynomial from <math>F_q</math> where <math>F_q</math> is typically represented as the set:<math>(-(q-1)/2, ..., -1, 0, 1, ..., (q-1)/2)</math>.

ToRandomly randomly generategenerating a "small" polynomial wedone selectby agenerating boundthe forcoefficients of the infinitypolynomial norm,from <math>b<<qF_q</math> and thenin randomlya sampleway thethat neither coefficientsguarantees fromor themakes set:very <math>(-b,likely ..., -1, 0, 1,small coefficients..., b)</math>. A typical value for <math>b</math> is 1, so the coefficientsThere are simplytwo chosencommon fromways to -1,do 0, and 1.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-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 ==