The scheme chosen by Google is the New Hope scheme. It was proposed in a research paper relatively recently, although there have been two other papers that have appeared in conferences such as Crypto 2016 are also worth reading as they support the original work:

both of which I've covered before in this blog as I did for another paper which is important in this work Frodo: Take oﬀ the ring! Practical, Quantum-Secure Key Exchange from LWE

The work builds on that published just over a year ago into the use of Learning With Errors (LWE) algorithms for public key exchange, especially in TLS. This earlier work can be found in these papers:

- Post-quantum key exchange for the TLS protocol from the ring learning with errors problem
- On Ideal Lattices and Learning with Errors Over Rings

Ring Learning With Errors Key Exchange (RLWE-KEX) is an area that will be new to many but it is part of the field of lattice based cryptography which so many have predicted would be the best source of quantum resistant crypto schemes. As with other schemes it is important to understand the number theory behind it.

Starting with a prime integer q, the Ring-LWE key exchange works in the ring of polynomials modulo a polynomial Φ(x) with coefficients in the field of integers mod q (i.e. the ring Z

a(x) = a

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

Knowing the number theory it is easier to then understand the key exchange algorithm which proceeds as follows:

You can find details of how this can be implemented here. This is particularly useful as it is a patch for OpenSSL with which many will be familiar. There is also code publicly available here.

Which brings us back to where I started this blog entry: New Hope. This uses paramenters that are slightly different to those originally suggested as the authors believe it is more resistant to certain lattice attacks, but the basics are the same. Code for this New Hope implementation can be found here.

All of this detail is freely available (although often spread around on the web) and I would encourage those involved in public key cryptography to start to look at it as it is coming to an infrastructure near you in the very near future.

_{q}[x]/Φ(x) ). Multiplication and addition of polynomials will work in the usual fashion with results of a multiplication reduced mod Φ(x).a(x) = a

_{0}+ a_{1}x + a_{2}x^{2}+ ... + a_{n-3}x^{n-3}+ a_{n-2}x^{n-2}+ a_{n-1}x^{n-1}^{}a_{i}'s, are integers mod q and when n is a power of 2 then Φ(x) = x^{n}+1.^{}The algorithm's security depends 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_{n-1}, ..., s_{0}) 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). 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 σ.

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

Knowing the number theory it is easier to then understand the key exchange algorithm which proceeds as follows:

**Initiator's First Steps:**- Generate two small polynomials s
_{I}(x) and e_{I}(x) by sampling from the distribution D. - Compute t
_{I}(x) = a(x)·s_{I}(x) + e_{I}(x). - The initiator sends the polynomial t
_{I}(x) to the Responder.

**Respondent'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) - The distribution of the coefficients of v(x) are smoothed by looping through the coefficients and randomly adjusting certain values. For j = 0 to n-1:
- If v
_{j}= 0, draw a random bit (b). If b = 0 then v_{j}= 0 otherwise v_{j}= q-1 - If v
_{j}= (q-1)/4, draw a random bit (b). If b = 0 then v_{j}= (q-1)/4 otherwise v_{j}= (q+3)/4

- If v
- Two n-long bit streams, cj, and uj, are formed from the coefficients of v(x), (v
_{n-1}, ... , v_{0}), via "Cross Rounding" and "Modular Rounding" respectively. - Form the key (k) as the concatenation of u
_{n-1}, ..., u_{0}. - Form an n-long "reconciliation" bit string (c) as the concatenation of c
_{n-1}, ..., c_{0}. - Compute t
_{R}(x) = a(x)·s_{R}(x) + e_{R}(x). - The Respondent sends t
_{R}(x) and c to the Initiator.

**Initiators Final Steps:**- Receive t
_{R}(x) and c from the Responder - Compute w(x) = t
_{R}(x)·s_{I}(x) + e_{I}(x) = a(x)s_{I}(x)s_{R}(x) + e_{R}(x)s_{I}(x) + e_{I}(x) - An n-long bit stream (uj) is formed by looping through the coefficients of w(x) and performing "Key Reconciliation." For j = 0 to n-1:
- If c
_{j}= 0 and -q/8 ≤ w_{j}< 3q/8 then u_{j}= 0 otherwise u_{j}= 1 - If c
_{j}= 1 and -3q/8 ≤ w_{j}< q/8 then u_{j}= 0 otherwise u_{j}= 1

- If c
- Form the key (k) as the concatenation of u
_{n-1}, ..., u_{0}

_{n-1}, ..., u_{0}and the respondent's string: u_{n-1}, ..., u_{0}will, with a high degree of probability, be the same.You can find details of how this can be implemented here. This is particularly useful as it is a patch for OpenSSL with which many will be familiar. There is also code publicly available here.

Which brings us back to where I started this blog entry: New Hope. This uses paramenters that are slightly different to those originally suggested as the authors believe it is more resistant to certain lattice attacks, but the basics are the same. Code for this New Hope implementation can be found here.

All of this detail is freely available (although often spread around on the web) and I would encourage those involved in public key cryptography to start to look at it as it is coming to an infrastructure near you in the very near future.