In collaboration with Erdem Alkim, Thomas Pöppelmann and Peter Schwabe, we recently designed a practical scheme, Newhope for key Post-Quantum exchange.
It is a practice oriented version Ring-LWE key exchange protocol of Ding, Xie, and Lin as tweaked by Chris Peikert. We also built upon the previous instantiation proposed by Joppe W. Bos, Craig Costello, Michael Naehrig, Douglas Stebila, paving the way for integration into TLS. Our variant introduces a few new tricks to enhance the performances even further.
Adam Langley (Google), recently wrote a blog entry about Newhope.
One remark of Adam, that I have also heard from others, is that our new reconciliation mechanism is quite obscure. In this post, I wish to address this issue and explain its design. The reason we redesigned it is that the original protocols would yield too many bits for a key agreement: 1024 bits would be outputted, while only 256 bits are needed. Instead of discarding 3/4 of the output, uses this extra space to improves the scheme (precisely increasing its tolerance to errors, allowing to improve compactness and security).
This requires geometric considerations in 4 dimensions, but we will take a intermediate step in 1 and 2 dimensions, where we can indulge ourselves with a few pictures.
From approximate key-exchange to exact key-exchange
The very concept of the LWE and Ring-LWE problems is to introduce errors, that are easy to eliminate knowing the appropriate secret, but very hard without it. After using their secrets, the parties are left with a decoding-like task. Here we may forget about the discrete nature of the problem: the task is an analog error-correction task. In a continuous space, how to recover a point (a codeword) from a discrete set knowing just a noisy version of that point ? The problem is also modular, simply because LWE works modulo q (by scaling we will work with real numbers modulo 1).
The analog decoding theory applies directly for the decryption step of LWE-based encryption. But for the Diffie-Hellman-like key exchange there is an extra technicality. In an encoding/decoding protocol, on party chooses a codeword x, and the other one has a noisy version x+e of it, and that he can decode. For key exchange, Alice has a random x, Bob x+e, but x is not necessarly a codeword. If they both decode it independently, they may not always decode to the same codeword. Some extra information needs to be transmitted to ensure they will both choose the same codeword.
a/ 1 bit out of 1 dimension
As already explain in Adam's post, the naive strategy of splitting the circle (the 1-dimensional torus R/Z) in two halves doesn't works directly. If the point of Alice is two close to the frontier, there is no guarantee than Bob will decode to the same bit, as shown below.
Alice's dilemma: is Bob going to round the same way I do ?
To avoid this situation, a reconciliation information is sent from Alice to Bob, a single bit indicating if a shift should be applied: yes, shift 90 degrees counter-clockwise (+ .25 mod 1), or no, don't shift. This is more or less the mechanism described by Chris Peikert.
If Alice's point is close to the frontier, apply the shift (y). After the shift, Alice's point is in the yellow region, Bob's point in the green-and-yellow region.
After this shift, the point of Alice is far from the frontier (at least 45 degrees i.e. 0.125 mod 1), so both Alice and Bob will agree on the same bit (in this case: 0).
Note that the reconciliation information (y or n) does not help an attacker: by symmetry each outcome 0 or 1 has the same probability even knowing the reconciliation message y or n. Well, this is true at least in the continuous case, but if Alice points is in fact discrete and q is odd, there is a slight imbalance, that Peikert addresses with his randomized doubling function.
b/ 2 bit out of 2 dimensions
So now, let us try to visualize what happens if apply this technique independently to two dimensions. We are now working on the torus R2/Z2. We shall represent the torus as a square, keeping in mind that the top border is glued to the bottom one, and the left border to the right one.
The same protocol applied in two dimensions independently. After the shift, Alice's point is in the yellow region, Bob's point in the green-and-yellow region.
Note that the error between Alice and Bob's point tends to be spherically distributed, this makes the green area a square with rounded edges.
c/ 1 bit out of 2 dimensions : the non-optimal way
A first idea to get only one bit out of two dimension could be to start from the previous 2-out-of-2 strategy, and eliminate half of the possibility, using an extra reconciliation bit. This would look as follows.
A tentative tweak with an extra reconciliation bit.
Ok, so we've spend one extra bit of reconciliation (3 in total), but we've gain a bit of error tolerance: the green portion could be a bit bigger. Nevertheless, the shape of the yellow region does not fit well in those newly diamond shaped regions. It would be much better if those yellow shapes were also diamonds.
d/ 1 bit out of 2 dimensions: the optimal way
To achieve the optimal reconciliation, we need to design directly with diamond shapes. We divide each of the two final diamonds into 4 diamonds, and for each we provide the reconciliation information: move to the Top, The Bottom, the Left or the Right (encoded into two bits).
The optimal 1-out-of-2 reconciliation protocol.
So this time, we have only spend two reconciliation bits, and significantly improved error tolerance.
Formalization
We now provide a common formalism for cases a), b) and d). Before choosing the reconciliation mechanism, we need to choose a set of codewords for the decoding step. In fact, each time we are going to choose a set C of codewords that is a (modular) lattice C = L/Zd.
a/ C = {0,.5} or equivalently the lattice L = .5 Z b/ C = {(0,0),(0,.5),(.5,0),(.5,.5)} or equivalently the modular lattice L = .5 Z2 d/ C = {(0,0),(.5,.5)} or equivalently the modular lattice L = D2, the lattice generated by {(0,1),(.5,.5)}
The reconciliation mechanism is built as follows
1/ Double the lattice consider L' = .5 L (e.g. in a/, consider L = .25 Z, with 4 points on the circle)
2/ Find the Shift Compute* c = CVP(x, L'). This splits the torus Zd into t = #(L'/Z) many tiles (case a: t=4, b: t=16, d: t=8).
3/ HelpRec(x) Define z = HelpRec(x) = c mod L.**
The size of quotient L'/L is 2d HelpRec(x) needs d bits.
4/ Decoding: k = Rec(x, z)
Apply the shift and decode: Rec(x,z) = CVP(x - z, L) mod Z^d. If all goes well Rec(x,z) = Rec(x+e,z).
5/ Count the possible k The number p of possible keys is #(L/Zd) (a:p=2, b:p=4, d:p=2)
*: CVP: Closest Vector Problem. For nicely crafted lattices, this is very fast.
**: How to represent z = c mod L ? Let B be a basis of L, B' = .5 B is a basis of L'. Express z in basis B': z = B'·r, and give away the coordinates of z modulo 2.
The case of Newhope
The Newhope reconciliation mechanism follows exactly the general algorithm described above, with a small extension: instead of just doubling the lattice in step 1/, we quadruple it. More generally, if we multiply it by 2k (that is take L' = 1/2k L), then the step 3/ now requires rd bits, and coordinates of r are now modulo 2k. We shall choose a 4-dimensional lattice, with two constraints:
- L is a 1-modular lattice, that is Z4 is a sub-lattice of L - The size of the quotient #(L/Z4) is exactly 2: we want to agree on 1 bit
There are not that many possible choices, and one of them, the lattice D4, is known to have the best packing density among four-dimensional lattice: it should be optimal for our task!
Analyzing the success probability of the key agreement requires knowing the shape of the Voronoi cell of that lattice. In all our previous examples, those cells were squares or diamonds. For the lattice D4, the shape is more involved (an icositetrachoron, a.k.a. the regular 24-cells). Despite being a 4-dimensional object, it remains easy to handle: it is the intersection of an hypercube and an hyperdiamond. This description make it quite convenient for the error analysis.
The icositetrachoron, stereographic projection on the 3-dimensional euclidean space.
Public Domain image from Wikipedia (Fritz Obermeyer).
Further generalizations
The use of lattices to decode errors over analog channel is a very well studied topic, and there is for sure a lot to learn from this field of research. The exact same ideas can be applied at the final step of (Ring-) LWE decryption or key agreement. The lattice D4 already offered improvements, with reasonable algorithmic simplicity, and fitting extremely well to the 4-dim to 1-bit problem at hand.
Nevertheless, in more general contexts this lattice may not be our best choice. For example, the Leech lattice (a very remarkable lattice in dimension 24) is known to offer extremely good coding gains, and found broad use in communication protocols, for example in the IEEE 802.11a WLAN standard. Can the Leech lattice bring similar improvements in cryptography? This is a question currently under investigated.
Edits
Published on January 2016
Edited on Oct 31, 2016: Appropriate attribution to Ding Xie and Lin for the first reconciliation mechanism
