# Web-log

## Newhope's Reconciliation Mechanism Explained

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.