Thursday, July 28, 2016

A New Hope

There is new hope, new hope for a feasible algorithm that survives Quantum Computer attacks and will give us secure cryptographic key agreements in the future. It is based on Ring-LWE, where LWE is the abbreviation for Learning With Errors and Ring simply means, that you are working over some ring structure. Roughly you can put LWE in the corner of lattice based cryptography, which is one of the contestants for post-quantum cryptography. The other contestants are multivariate equations and coding based cryptography (i.e. McEliece and Niederreiter). In the meantime, one major application of LWE is also fully homomorphic encryption [4].

The underlying scheme for the $\text{NewHope}$ algorithm was proposed by Jintai Ding, Xiang Xie and Xiaodong Lin [1] in 2012, then got improved by Peikert in 2014 [2]. Joppe W. Bos, Craig Costello, Michael Naehrig and Douglas Stebila [3] presented an implementation in 2015. The next major improvement by Erdem Alkim, Léo Ducas, Thomas Pöppelmann and Peter Schwabe [4] finally led to the $\text{NewHope}$ algorithm.


Let me first describe Ring-LWE in a short, rather informal manner. Assume you have a system of equations, with unknowns $s_0,s_1,\ldots,s_{n-1}$.
\begin{align*}
c_{0,0}s_0 + c_{0,1}s_1 + \ldots + c_{0,n-1}s_{n-1} & = b_0 \\
c_{1,0}s_0 + c_{1,1}s_1 + \ldots + c_{1,n-1}s_{n-1} & = b_1 \\
\ldots \\
c_{m-1,0}s_0 + c_{m-1,1}s_1 + \ldots + c_{m-1,n-1}s_{n-1} & = b_{m-1} \\
\end{align*} where usually $m > n$. Given this system of equations, pick $n$ equations and solve for $s_i$, which could be done using the folklore Gaussian elimination algorithm. For LWE, this system of equation is slightly changed. Instead of given a system of equations as above, you have:
\begin{align*}
c_{0,0}s_0 + c_{0,1}s_1 + \ldots + c_{0,n-1}s_{n-1} & \approx b_0 \\
c_{1,0}s_0 + c_{1,1}s_1 + \ldots + c_{1,n-1}s_{n-1} & \approx b_1 \\
\ldots \\
c_{m-1,0}s_0 + c_{m-1,1}s_1 + \ldots + c_{m-1,n-1}s_{n-1} & \approx b_{m-1} \\
\end{align*} You only know the approximate value of each equation. To be a little bit more precise, we can write:
\begin{align*}
c_{0,0}s_0 + c_{0,1}s_1 + \ldots + c_{0,n-1}s_{n-1} & = b_0 + e_0 \\
c_{1,0}s_0 + c_{1,1}s_1 + \ldots + c_{1,n-1}s_{n-1} & = b_1 + e_1 \\
\ldots \\
c_{m-1,0}s_0 + c_{m-1,1}s_1 + \ldots + c_{m-1,n-1}s_{n-1} & = b_{m-1} + e_{m-1} \\
\end{align*} where the $e_i$ are the small error terms that are sampled from a certain distribution. Solving this system of equations (of course with unknown $e_i$) is roughly speaking the Learning with Error problem. If you work over a ring, e.g. $\mathbb{Z}_q[x]/(f(x))$ you get Ring-LWE (some details are missing here, but this should illustrate the concept). The believe in its hardness stems from the fact Regev [6] proved that the LWE problem is as hard as to solve several worst-case lattice problems, which again are known to resist quantum computer attacks.

The question is: How can this be turned into key exchange protocol?