Ring learning with errors key exchange: Difference between revisions

Revision as of 16:21, 26 May 2015

Revision as of 16:25, 26 May 2015

Line 10:

The Ring-LWE Key Exchange is designed to be a "quantum safe" replacement for the widely used [[Diffie-Hellman]] and [[Elliptic Curve Diffie-Hellman]] key exchanges that are used to secure the establishment of secret keys over untrusted communications channels.

The Ring-LWE key exchange works in the ring of polynomials of degree n-1 or less modulo a polynomial F(x) (i.e. the ring Z_q[x]/F(x) for an integer q). The coefficients of the polynomials in this ring are the integers mod q. Multiplication and addition of polynomials will work in the usual fashion with results of a multiplication reduced mod F(x). This article will closely follow the work of Peikert as further explained by Singh <ref name=":0">{{Cite journalbook|title = Lattice Cryptography for the Internet|url = http://eprintlink.iacrspringer.orgcom/2014chapter/07010.1007/978-3-319-11659-4_12|publisher = Springer International Publishing|date = 2014/10/01|isbn = 978-3-319-11658-7|pages = 197-219|series = Lecture Notes in Computer Science|language = en|first = Chris|last = Peikert|editor-first = Michele|editor-last = Mosca}}</ref><ref name=":1">{{Cite journal|title = A Practical Key Exchange for the Internet using Lattice Cryptography|url = http://eprint.iacr.org/2015/138|date = 2015|first = Vikram|last = Singh}}</ref>. For this presentation a typical polynomial is expressed as:

p(x) = p₀ + p₁x + p₂x² + ... + p_n-3x^n-3 + p_n-2x^n-2 + p_n-1x^n-1

Line 17:

# 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. 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.<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 ===