Ring learning with errors key exchange: Difference between revisions

Revision as of 15:27, 14 June 2015

Revision as of 23:25, 26 June 2015

Line 25:

# Using [[Gaussian distribution|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 and 1 mod 2n. The maximum degree of the polynomials (n) will be a power of 2. This follows the work of Singh.<ref name=":1" /> Other cases for q and n are thoroughly discussed in "A Toolkit for Ring-LWE Cryptography."<ref name=":2" /> A fixed public polynomial, a(x), shared by all users of the network. It is deterministically generated from a cryptographically secure source.

Given a(x) as stated, we can randomly choose small polynomials s(x) and e(x) to be the "private key" in a public key exchange. The corresponding public key will be the polynomial t(x) = a(x)s(x) + e(x). The security of the key exchange that follows is based the difficulty of finding a pair of small polynomials s'(x) and e'(x) such that for a given t(x), a(x)s'(x) + e'(x) = t(x).

== The Key Exchange ==