Content deleted Content added
Improved language on Ring-LWE problem |
Improved wording |
||
Line 16:
a(x) = a<sub>0</sub> + a<sub>1</sub>x + a<sub>2</sub>x<sup>2</sup> + ... + a<sub>n-3</sub>x<sup>n-3</sup> + a<sub>n-2</sub>x<sup>n-2</sup> + a<sub>n-1</sub>x<sup>n-1</sup>
The coefficients of this polynomial, the a<sub>i</sub>'s, are integers mod q. The polynomial g(x) will be g(x) = x<sup>n</sup> +1 where n is a power of 2 (nominally 256, 512, or 1024).
The Ring-LWE key exchange uses polynomials which are considered "small" with respect to a measure called the "[[infinity norm]]." The infinity norm for a polynomial is simply the value of the largest coefficient of the polynomial when the coefficients are considered as integers in (Z vice Z/qZ). The algorithm's security will depend on an ability to generate random polynomials which are small with respect to the infinity norm. This is done simply by randomly generating the coefficients for a polynomial (s<sub>n-1</sub>, ..., s<sub>0</sub>) which are guaranteed or very likely to be small. 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). Singh suggest using b = 5.<ref name=":1" /> Thus coefficients would be chosen from the set { q-5, q-4, q-3, q-2, q-1, 0 , 1, 2, 3, 4, 5 }.
# 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. An overview of gaussian sampling is found in a presentation by Peikert.<ref>{{Cite web|title = http://www.cc.gatech.edu/~cpeikert/pubs/slides-pargauss.pdf|url = http://www.cc.gatech.edu/~cpeikert/pubs/slides-pargauss.pdf|website = www.cc.gatech.edu|accessdate = 2015-05-29}}</ref>
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. The maximum degree of the polynomials (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. A fixed public polynomial, a(x), shared by all users of the network. It is deterministically generated from a cryptographically secure source.
| |||