Content deleted Content added
→Background: Reworded for accuracy, replacing “sub-ring” with “quotient ring”. The quotient ring is not a sub-ring, and cannot be since repeated multiplication of $x$ eventually repeats after, say, $N$ iterations. This is not true in the polynomial ring, which implies that no homomorphic injection can be defined, as $x$ would have to map to both $x$ and $x^N$. The description of the previously misnamed ring is that of the quotient ring. To this end, I replaced “sub-ring” with “quotient r... Tags: Mobile edit Mobile web edit |
→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 |
||
Line 20:
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 [[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 provide 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}}</ref>
| |||