Ring learning with errors signature: Difference between revisions

Revision as of 22:17, 17 May 2015

Revision as of 22:28, 17 May 2015

Line 16:

# 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 Discrete Gaussian Sampling - For an odd value for q, the coefficients 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.

For the rest of this article, the random small polynomials will be sampled according do a distribution which is simply be specified as '''D'''. Further q will be an odd prime such that q is congruent to 1 mod 4. TheAll maximumthe degreepolynomials ofwill thehave polynomialsdegree less than (n). n will be a power of 2. This follows the work of Singh.<ref name=":1" /> The other cases for q and n are thoroughly discussed in the referenced paper by Peikert.<ref name=":0" /> A fixed public polynomial ( a(x) ) shared by all users of the network. It is deterministically generated from a cryptographically secure source.

=== The Key Exchange ===