Ring learning with errors key exchange: Difference between revisions

Revision as of 18:09, 29 May 2015

Revision as of 21:27, 29 May 2015

Line 7:

There are a variety of cryptographic algorithms which work using the Ring-LWE paradigm. There are public key encryption algorithms, [[homomorphic encryption]] algorithms, and digital signatures in addition to the public key, key exchange algorithm presented in this article

A [[key exchange algorithm]] is a type of public key algorithm which establishes a shared secret key between to communicants on a communications link. The classic example of a key exchange is the [[Diffie–Hellman key exchange|Diffie-Hellman]] key exchange. The exchange consists of one transmission from one end of the line and one transmission from the other end of the link. [[Diffie–Hellman key exchange|Diffie-Hellman]] and [[Elliptic curve Diffie–Hellman|Elliptic Curve Diffie-Hellman]] are the two most popular key exchange algorithms.

=== Introduction ===

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.

=== Introduction ===

TheFor an integer, n, the Ring-LWE key exchange works in the ring of polynomials of degree n-1 or less modulo a polynomial Fg(x) with coefficients in the field of integers mod q, F_q. (i.e. the ring ZF_q[x]/Fg(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 Fg(x). This article will closely follow the Ring-LWE work of Peikert in "Lattice Cryptography for the Internet" as further explained by Singh <ref name=":0">{{Cite book|title = Lattice Cryptography for the Internet|url = http://link.springer.com/chapter/10.1007/978-3-319-11659-4_12|publisher = Springer International Publishing|date = 2014|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:

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

The coefficients of this polynomial, the a_i's, are integers mod q where q is a prime number.

This cryptographic algorithm 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 considered as integers in (Z vice Z/pZ). The algorithm will generate random polynomials which are small with respect to the infinity norm. We do this by randomly generating the coefficients of the polynomial (p_n-1, ..., p₀) which are guaranteed or very likely to be small. There are two common ways to do this:

ThisThe cryptographicRing-LWE algorithmkey 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/pZqZ). The algorithm's security will depend on an ability to generate random polynomials which are small with respect to the infinity norm. WeThis dois thisdone simply by randomly generating the coefficients offor thea polynomial (ps_n-1, ..., ps₀) 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).

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

=== The Key Exchange ===

The key exchange will take place between two devices. There will be an initiator for the key exchange designated as (I) and a responder designated as (R). Both I and R know, q, n, a(x), and have the ability to generate small polynomials according to the distribution '''D'''. The description which follows does not contain any explanation of why the key exchange beginsresults within the initiatorsame (I)key doingat both ends of a link. Rather it succinctly specifies the followingsteps to be taken. For further understanding the reader should look at the referenced works by Peikert and Singh.<ref name=":0" /><ref name=":1" />

The key exchange begins with the initiator (I) doing the following:

'''Initiator's First Steps:'''

Line 26 ⟶ 32:

# Compute t_I(x) = a(x)·s_I(x) + e_I(x).

# The initiator sends the polynomial t_I(x) to the Responder.

'''ResponserResponder's Steps:'''

# Generate two small polynomials s_R(x) and e_R(x) by sampling from the distribution D.

# Compute v(x) = t_I(x)·s_R(x) + e_R(x) Note that this equals: a(x)s_I(x)s_R(x) + e_I(x)s_R(x) + e_R(x) and that e_I(x)s_R(x) will also be small relative to the infinity norm on q.

Line 48 ⟶ 54:

## If c_j = 1 and q/8 ≤ w_j < 5q/8 then u_j = 0 otherwise u_j = 1

# Form the key (k) as the concatenation of u_n-1, ..., u₀

If the key exchange worked properly, the initiator's string: u_n-1, ..., u₀ and the responder's string: u_n-1, ..., u₀ will be the same.

Depending on the specifics of the parameters chosen n, q, σ, or b, there is an extremely small probability that this key exchange will fail to produce the same key. Implementors of the scheme might want to introduce a key validation step before ciphertext is produced.