Post Quantum Crypto Goes Mainstream?

Although people such as me have been talking about the threat to public key cryptography from quantum computers for years, and the alternatives that could be used, it seems that when Google announced that they were experimenting with a post quantum crypto scheme in Chrome it caught people's imagination.  Perhaps this marks the beginning of post quantum crypto entering the mainstream?

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:

• Efficient algorithms for supersingular isogeny Diffie-Hellman
• NTRU Prime

both of which I've covered before in this blog as I did for another paper which is important in this work Frodo: Take off 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_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₀ + a₁x + a₂x² + ... + a_n-3x^n-3 + a_n-2x^n-2 + a_n-1x^n-1

a_i's, are integers mod q and when n is a power of 2 then Φ(x) = xⁿ +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₀) which are guaranteed or very likely to be small. There are two common ways to do this:

1. 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 }.
2. 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 σ.

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. The choice of q and n are thoroughly discussed in "A Toolkit for Ring-LWE Cryptography" and "Even More Practical Key Exchange for the Internet using Lattice Cryptography."

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:

1. Generate two small polynomials s_I(x) and e_I(x) by sampling from the distribution D.
2. Compute t_I(x) = a(x)·s_I(x) + e_I(x).
3. The initiator sends the polynomial t_I(x) to the Responder.

Respondent's Steps:

1. Generate two small polynomials s_R(x) and e_R(x) by sampling from the distribution D.
2. Compute v(x) = t_I(x)·s_R(x) + e_R(x)
3. 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
4. Two n-long bit streams, cj, and uj, are formed from the coefficients of v(x), (v_n-1, ... , v₀ ), via "Cross Rounding" and "Modular Rounding" respectively.
5. Form the key (k) as the concatenation of u_n-1, ..., u₀.
6. Form an n-long "reconciliation" bit string (c) as the concatenation of c_n-1, ..., c₀.
7. Compute t_R(x) = a(x)·s_R(x) + e_R(x).
8. The Respondent sends t_R(x) and c to the Initiator.

Initiators Final Steps:

1. Receive t_R(x) and c from the Responder
2. 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)
3. 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
4. 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 respondent's string: u_n-1, ..., u₀ 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.