Monday, 11 July 2016

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:
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:
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 Zq[x]/Φ(x) ). Multiplication and addition of polynomials will work in the usual fashion with results of a multiplication reduced mod Φ(x).

a(x) = a0 + a1x + a2x2 + ... + an-3xn-3 + an-2xn-2 + an-1xn-1

ai's, are integers mod q and when n is a power of 2 then Φ(x) = xn +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 (sn-1, ..., s0) 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 sI(x) and eI(x) by sampling from the distribution D.
  2. Compute tI(x) = a(x)·sI(x) + eI(x).
  3. The initiator sends the polynomial tI(x) to the Responder.
Respondent's Steps:
  1. Generate two small polynomials sR(x) and eR(x) by sampling from the distribution D.
  2. Compute v(x) = tI(x)·sR(x) + eR(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 vj = 0, draw a random bit (b). If b = 0 then vj = 0 otherwise vj = q-1
    • If vj = (q-1)/4, draw a random bit (b). If b = 0 then vj = (q-1)/4 otherwise vj = (q+3)/4
  4. Two n-long bit streams, cj, and uj, are formed from the coefficients of v(x), (vn-1, ... , v0 ), via "Cross Rounding" and "Modular Rounding" respectively.
  5. Form the key (k) as the concatenation of un-1, ..., u0.
  6. Form an n-long "reconciliation" bit string (c) as the concatenation of cn-1, ..., c0.
  7. Compute tR(x) = a(x)·sR(x) + eR(x).
  8. The Respondent sends tR(x) and c to the Initiator.
Initiators Final Steps:
  1. Receive tR(x) and c from the Responder
  2. Compute w(x) = tR(x)·sI(x) + eI(x) = a(x)sI(x)sR(x) + eR(x)sI(x) + eI(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 cj = 0 and -q/8 ≤ wj < 3q/8 then uj = 0 otherwise uj = 1
    • If cj = 1 and -3q/8 ≤ wj < q/8 then uj = 0 otherwise uj = 1
  4. Form the key (k) as the concatenation of un-1, ..., u0
If the key exchange worked properly, the initiator's string: un-1, ..., u0 and the respondent's string: un-1, ..., u0 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.