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?
Below you see the protocol as defined by [3] (so not the actually $\text{NewHope}$ variant), with $R_q =\mathbb{Z}_q[x]/(X^n+1)$\begin{array}{l c l}
\hline
\textbf{Public params} \\
\hline
q,n,\chi & & \\
a \stackrel{\$}{\leftarrow}\mathcal{U}(R_q) & &\\
\hline
\textbf{Alice}& &\textbf{Bob} \\
\hline
\textbf{A.1) } s, e \stackrel{\$}{\leftarrow} \chi & & \textbf{B.1) } s', e' \stackrel{\$}{\leftarrow} \chi \\
\textbf{A.2) } b \leftarrow as+e\in R_q & \stackrel{b}{\rightarrow} & \textbf{B.2) } b' \leftarrow as'+e'\in R_q \\
& & \textbf{B.3) } e'' \stackrel{\$}{\leftarrow} \chi\\
& & \textbf{B.4) } v \leftarrow bs' + e'' \in R_q\\
& & \textbf{B.5) } \overline{v} \stackrel{\$}{\leftarrow} \text{dbl}(v) \in R_{2q}\\
& \stackrel{b',c}{\leftarrow}& \textbf{B.6) } c \leftarrow \langle \overline{v} \rangle_{2q,2} \in \{0,1\}^{n}\\
\textbf{A.3) } k_A \leftarrow \text{rec}(2b's,c)\in \{0,1\}^n & & \textbf{B.7) } k_B \leftarrow \lfloor \overline{v}\rceil_{2q,2} \in \{0,1\}^n \\
\end{array}
To understand the protocol, lets go through it step by step and illustrating it using a small toy example. We set $n=4$ and $q=1009$, so we work over $\mathbb{Z}_{1009}[x]/(X^4+1)$ with the random monic polynomial
\begin{equation}
a(X) = 523X^3+7X^2+18X+137 = a_3X^3+a_2X^2+a_1X+a_0
\end{equation}
Notation: We write $a$ if we only refer to the coefficient vector of the ring element, and $a(X)$ to refer to the actual polynomial.
$\textbf{A.1}$ and $\textbf{B.1}$: Here the secrets $s,s'$ and the error vectors $e,e'$ are sampled from the distribution $\chi$. Note that here the secret $s$ is also sampled from the error distribution $\chi$ and not uniformly at random, but it has been proved, that this does not change the security. Suppose we sampled: $s = (s_3,s_2,s_1,s_0) = (1,0,3,2), s' = (0,3,2,2), e = (2,0,3,1), e' = (1,2,1,1)$
$\textbf{A.2}$ and $\textbf{B.2}$: Here, Alice and Bob construct the LWE instance. At a first glance, this seems odd. Why does $as+e$ represent a system of equations as described above? There are only $n$ coefficients instead of the $n^2$ coefficients that would be necessary for the construction. The reason for this is efficiency. Of course, one could indeed build a protocol that submits $n^2$ coefficients via $n$ different vectors $a_i$. However, in order to gain efficiency the requirement of $n^2$ totally independent coefficients is dropped and all further $n^2-n$ coefficients are computed using this $n$ coefficients. If the first vector is $(a_0,a_1,\ldots,a_{n-1})$ all further vectors are generated by:
\begin{align*}
(a_1,a_2,\ldots,a_{n-1},-a_0) \\
(a_2,a_3,\ldots,a_{n-1},-a_0,-a_1) \\
\ldots \\
(a_{n-1},-a_0,\ldots,-a_{n-4},-a_{n-3},-a_{n-2}) \\
\end{align*}
This procedure takes implicitly place when computing in $\mathbb{Z}_q/(X^n+1)$: Just assume that $s(X) = s_3X^3+s_2X^2+s_1X+s_0$ and $e(X) = e_3X^3+e_2X^2+e_1X+e_0$ then
$a(X)s(X)+e(X)$ yields:
\begin{align*}as(X)+e(X) & \equiv a_3s_0X^3 + a_2s_0X^2 + a_1s_0X + a_0s_0 + e_3X^3\\
& - a_3s_1 + a_2s_1X^3 + a_1s_1X^2 + a_0s_1X\\
& - a_3s_2X - a_2s_2 + a_1s_2X^3 + a_0s_2X^2\\
& - a_3s_3X^2 - a_2s_3X - a_1s_3 + a_0s_3X^3\\
& \equiv b_3X^3 + b_2X^2 + b_1X + b_0 \pmod{X^4+1}
\end{align*}
Rewriting this according to the coefficients for each monomial $X^i$ yields:
\begin{array}{c c c c c c c}
X^3: &a_3s_0 & + a_2s_1 & + a_1s_2 & + a_0s_3 & + e_3 & = b_3\\
X^2: &a_2s_0 & + a_1s_1 & + a_0s_2 & - a_3s_3 & + e_2 & = b_2\\
X^1: &a_1s_0 & + a_0s_1 & - a_3s_2 & - a_2s_3 & + e_1 & = b_1\\
X^0: &a_0s_0 & - a_3s_1 & - a_2s_2 & - a_1s_3 & + e_0 & = b_0\\
\end{array}
which is the system of equations lying underneath the R-LWE scheme. Since $a$ is public and $b$ is send over the communication channel, the attacker is forced to solve this system of equation in order to learn $s$ and/or $e$. In our example case, we get
\begin{align*}
& (523X^3+7X^2+18X+137)(X^3+3X+2) + (2X^3+3X+1) \\
& = 197X^3 + 554X^2 + 443X + 706 = b \\
&(523X^3+7X^2+18X+137)(3X^2+2X+2) + (X^3+2X^2+X+1) \\
& = 106X^3 + 463X^2 + 760X + 217 = b'
\end{align*}
$\textbf{B.3}$: Bob samples another vector $e''$ from $\chi$, assume this is $e'' = (3,5,0,2)$.
$\textbf{B.4}$: Bob generates another system of equations, but this time using the received polynomial $b(X)$ which he got from Alice. He computes
\begin{align*}
&b(X)s'(X) + e''(X) \\
& = (197X^3 + 554X^2 + 443X + 706)(3X^2+2X+2) + (3X^3+5X^2+2) \\
& = 816X^3 + 81X^2 + 698X + 367 = v
\end{align*}
Observe that $v$ can be written as $$v = bs'+e'' = (as+e)s'+e'' = ass'+es'+e''$$
$\textbf{B.5}$: To understand this, we need to know how the function $\text{dbl}$ is defined:\begin{align*}
\text{dbl}: &\;\mathbb{Z}_q \rightarrow \mathbb{Z}_{2q} \\
& x \mapsto \text{dbl}(x) := 2x - r
\end{align*}
whereof $r$ is sampled from $\{-1,0,1\}$ with the probabilities:
\begin{equation*}
\text{Pr}(r = -1) = \text{Pr}(r = 1) = 1/4; \text{Pr}(r = 0) = 1/2
\end{equation*}
If $\text{dbl}$ is applied to a coefficient vector or polynomial, it is executed coefficient wise. In our example, we have to apply this to $v(X) = 816X^3 + 81X^2 + 698X + 367$. I sampled $r = -1$, $r = 1$, $r = 0$, $r = 0$ in the four rounds, which yields
\begin{equation}
\overline{v}(X) = 1632X^3+162X^2+1395X+734
\end{equation}
$\textbf{B.6}$: The definition of the $\langle \cdot \rangle$ function is:
\begin{align*}
\langle \cdot \rangle: &\;\mathbb{Z}_q \rightarrow \mathbb{Z}_{2} \\
& x \mapsto \langle x \rangle_{q,2} = \left\lfloor \frac{4}{q}x \right\rfloor \pmod{2}
\end{align*}
and again, if applied to a polynomial or coefficient vector, it is executed coefficient wise. The application of $\langle \cdot \rangle_{2q,2}$ to $\overline{v}$ yields:
\begin{align*}
\langle 1632 \rangle_{2018,2} & = \lfloor \frac{4}{2018}1632 \rfloor \pmod{2}
= \lfloor 3.234... \rfloor = 3 \equiv 1 \pmod{2} \\
\langle 162 \rangle_{2018,2} & = \lfloor \frac{4}{2018}162 \rfloor \pmod{2}
= \lfloor 0.321... \rfloor = 0 \equiv 0 \pmod{2} \\
\langle 1395 \rangle_{2018,2} & = \lfloor \frac{4}{2018}1395 \rfloor \pmod{2}
= \lfloor 2.765... \rfloor = 2 \equiv 0 \pmod{2} \\
\langle 734 \rangle_{2018,2} & = \lfloor \frac{4}{2018}734 \rfloor \pmod{2}
= \lfloor 1.454... \rfloor = 1 \equiv 1 \pmod{2} \\
\end{align*}
Hence $c = (1,0,0,1)$, i.e., $c(X) = X^3+1$.
$\textbf{B.7}$: The definition of the $\lfloor \cdot \rceil$ function is similar:
\begin{align*}\lfloor \cdot \rceil: &\;\mathbb{Z}_q \rightarrow \mathbb{Z}_{2} \\
& x \mapsto \lfloor x \rceil_{q,2} = \left\lfloor \frac{2}{q}x \right\rceil \pmod{2}
\end{align*}
The application of $\lfloor \cdot \rceil_{2q,2}$ to the coefficient vector $\overline{v}$ yields:
\begin{align*}
\lfloor 1632 \rceil_{2018,2} & = \lfloor \frac{2}{2018}1632 \rceil \pmod{2}
= \lfloor 1.617... \rceil = 2 \equiv 0 \pmod{2} \\
\lfloor 162 \rceil_{2018,2} & = \lfloor \frac{2}{2018}162 \rceil \pmod{2}
= \lfloor 0.160... \rceil = 0 \equiv 0 \pmod{2} \\
\lfloor 1395 \rceil_{2018,2} & = \lfloor \frac{2}{2018}1395 \rceil \pmod{2}
= \lfloor 1.382... \rceil = 1 \equiv 1 \pmod{2} \\
\lfloor 734 \rceil_{2018,2} & = \lfloor \frac{2}{2018}734 \rceil \pmod{2}
= \lfloor 0.727... \rceil = 1 \equiv 1 \pmod{2} \\
\end{align*} So the key Bob computes is $$\text{key}_\text{Bob} = (0,0,1,1)$$.
$\textbf{A.3}$: Now Alice receives $b'$ and $c$. We now define the three intervals: $I_0 = \{0,1,\ldots,\lfloor q/2 \rceil -1\}$, $I_1 = \{-\lfloor q/2 \rfloor, \ldots, -1\}$ and $E = \left[-q/4,q/4\right)$. Then the reconciliation function $\text{rec}$ is defined as:
\begin{align*}
\text{rec}: &\;\mathbb{Z}_{2q}\times \mathbb{Z}_2 \rightarrow \mathbb{Z}_{2} \\
\text{rec}(w,b) & =
\begin{cases}
0,\;\text{if }w\in I_b + E \pmod{2q} \\
1,\;\text{otherwise}
\end{cases}
\end{align*}
Note that the first component is evaluated in $R_{2q}$, hence in our example we get:
\begin{align*}
& 2b'(X)s(X) = 2(106X^3 + 463X^2 + 760X + 217)(X^3+3X+2) \\
& = 1618X^3 + 146X^2 + 1398X + 730
\end{align*} then Alice computes $\text{rec}((1618, 146, 1398, 730),(1,0,0,1))$, which is\begin{align*}
&(1618,1) \equiv (-400,1): -400 \in I_1 + E = [-756,\ldots, 251] \rightarrow 0 \\
&(146,0): 146 \in I_0 + E = [-252,\ldots, 756] \rightarrow 0 \\
&(1398,0) \equiv (-620,0): -620 \not\in I_0 + E = [-252,\ldots, 756] \rightarrow 1 \\
&(730,1): 730 \not\in I_1 + E = [-756,\ldots, 251] \rightarrow 1 \\
\end{align*} Hence Alice computes $$\text{key}_\text{Alice} = (0,0,1,1)$$ which is the same as $\text{key}_\text{Bob}$.
Note that the scheme guarantees $\text{key}_\text{Bob} = \text{key}_\text{Alice}$ only with some error probability. So there might be a failed key exchange, but the error probability is negligible.
But why does this actually work? That means, why does $$\lfloor \overline{v} \rceil_{2q,2} = \text{rec}(2b's,\langle \overline{v} \rangle_{2q,2})$$ (almost always) hold? Therefore, observe that
\begin{align*}
2b's & = 2(as'+e)s \\
& = 2as's+2es\\
\text{and}\\
\overline{v} & = 2v - r = 2(bs'+e'') - r \\
& = 2((as+e)s' + e'') - r \\
& = 2ass' + 2es' + 2e'' - r
\end{align*}
Hence $\overline{v}$ and $2b's$ differ by $D = 2es - 2es' - 2e'' + r$ (the $r$ comes from the $\text{dbl}$ function), i.e. $$2bs' = \overline{v} + D$$ If all terms are sufficient small (which they actually are), such that $-q/4 \leq D < q/4$, the following Lemma holds:
Lemma. If $w = v + e \pmod{2q}$ and $e \in \left[-q/4,q/4\right)$, then $$\text{rec}(w,\langle v \rangle_{2q,2}) = \lfloor v \rceil_{2q,2}$$
Proof. Since $\text{rec}$, $\lfloor \cdot \rceil_{2q,2}$ and $\langle \cdot \rangle_{2q,2}$ work component wise, it is enough to prove the lemma for one component, hence we pick the first one $w_0 = v_0 + e_0$. It is $\langle v_0\rangle_{2q,2} \in \{0,1\}$, i.e. $$\left\lfloor \frac{4}{2q}v_0 \right\rfloor = \left\lfloor \frac{2}{q}v_0 \right\rfloor \pmod{2}$$ Since $0 \leq v_0 < 2q$, $\left\lfloor \frac{2}{q}v_0 \right\rfloor$ is either $0,1,2$ or $3$ according to which of the quarters $(0,q/2],(q/2,q],(q,3q/2]$ or $(3q/2,2q]$ contains $v_0$. The reduction of $1,2,3,4$ modulo two yields $0,1,0,1$. On the other hand, the $\lfloor \cdot \rceil$ function is $$\left\lfloor \frac{2}{2q}v_0 \right\rceil = \left\lfloor \frac{1}{q}v_0 \right\rceil \pmod{2}$$ Likewise, the result depends on the quarter that contains $v_0$. But due to the different rounding method, the reduction modulo two this time yields $0,1,1,0$. So $\langle\cdot\rangle$ and $\lfloor\cdot\rceil$ are equal for $v_0 < q$ and inverse for $v_0 > q$.
We can conclude, that the $\langle v_0 \rangle_{2q,2}$ value given as the second parameter of $\text{rec}$, reduces the four possibilities for a quarter down to two. For a further reduction down to one, we can use the first parameter $w_0 = v_0+e_0$. Note that this is easy, since $w_0$ is actually already almost equal to $v_0$ up to an error of $e$ less than $q/4$. Hence $w_0$ is sufficient to choose the correct quarter which allows to deduce the value $\lfloor v_0 \rceil_{2q,2}$.
To rephrase this a little bit more concrete, observe that the $\text{rec}$ function looks at the intervals $I_0 = \{0,1,\ldots,\lfloor q/2 \rceil -1\}$ and $I_1 = \{-\lfloor q/2 \rfloor, \ldots, -1\}$ and adds space for the error term by the addition of $E = (-q/4,q/4]$, so we have $$I_0 + E = (-q/4, \ldots, \lfloor q/2 \rceil-1+q/4]$$ and $$I_1 + E = (-\lfloor q/2 \rfloor-q/4, \ldots, -1+q/4]$$ There are four cases, but we only look at the first, since the other ones are analogous:
1) Assume $\lfloor v_0 \rceil_{2q,2} = 0$, hence either $0 \leq v_0 < q/2$ or $3q/2 \leq v_0 < 2q$.
2) Assume $\langle v_0 \rangle_{2q,2} = 0$, hence either $0 \leq v_0 < q/2$ or $q \leq v_0 < 3q/2$.
If both values would be available, this would immediatelly allow to determine the correct quarter $(0,q/2]$. But $\langle v_0 \rangle_{2q,2}$ together with the value $w$ is already sufficient, since $$w_0 = v_0 + e_0$$ and $|e| < q/4$. Assume $w_0 = v_0 + e \in I_0 + E \in (-q/4, \ldots, \lfloor q/2 \rceil-1+q/4]$. Then it follows $0 \leq v_0 < q/2$, hence the first quarter is the correct one. But for each element $h \in [0,q/2)$ it holds $\lfloor h \rceil_{2q,2} = 0$, hence $\lfloor v_0 \rceil_{2q,2} = 0$, which is the first key bit.
Q.e.d.
[1] Jintai Ding, Xiang Xie, Xiaodong Lin, A Simple Provably Secure Key Exchange Scheme Based on the Learning with Errors Problem,Cryptology ePrint Archive, Report 2012/688, 2012
[2] Peikert, Chris. Mosca, Michele, ed. Lattice Cryptography for the Internet. Lecture Notes in Computer Science. Springer International Publishing. pp. 197–219.
[3] Joppe W. Bos and Craig Costello and Michael Naehrig and Douglas Stebila, Post-quantum key exchange for the TLS protocol from the ring learning with errors problem, Cryptology ePrint Archive, Report 2014/599, 2014. Published at IEEE Security & Privacy 2015
[4] Erdem Alkim and Léo Ducas and Thomas Pöppelmann and Peter Schwabe,Post-quantum key exchange - a new hope, Cryptology ePrint Archive, Report 2015/1092, 2015, Published at Usenix Security 2016
[5] Brakerski, Zvika; Vaikuntanathan, Vinod (2011). Rogaway, Phillip, ed. Fully Homomorphic Encryption from Ring-LWE and Security for Key Dependent Messages. Lecture Notes in Computer Science. Springer Berlin Heidelberg. pp. 505–524.
[6] Oded Regev, “On lattices, learning with errors, random linear codes, and cryptography,” in Proceedings of the thirty-seventh annual ACM symposium on Theory of computing (Baltimore, MD, USA: ACM, 2005), 84-93,
\begin{align*}
& (523X^3+7X^2+18X+137)(X^3+3X+2) + (2X^3+3X+1) \\
& = 197X^3 + 554X^2 + 443X + 706 = b \\
&(523X^3+7X^2+18X+137)(3X^2+2X+2) + (X^3+2X^2+X+1) \\
& = 106X^3 + 463X^2 + 760X + 217 = b'
\end{align*}
$\textbf{B.3}$: Bob samples another vector $e''$ from $\chi$, assume this is $e'' = (3,5,0,2)$.
$\textbf{B.4}$: Bob generates another system of equations, but this time using the received polynomial $b(X)$ which he got from Alice. He computes
\begin{align*}
&b(X)s'(X) + e''(X) \\
& = (197X^3 + 554X^2 + 443X + 706)(3X^2+2X+2) + (3X^3+5X^2+2) \\
& = 816X^3 + 81X^2 + 698X + 367 = v
\end{align*}
Observe that $v$ can be written as $$v = bs'+e'' = (as+e)s'+e'' = ass'+es'+e''$$
$\textbf{B.5}$: To understand this, we need to know how the function $\text{dbl}$ is defined:\begin{align*}
\text{dbl}: &\;\mathbb{Z}_q \rightarrow \mathbb{Z}_{2q} \\
& x \mapsto \text{dbl}(x) := 2x - r
\end{align*}
whereof $r$ is sampled from $\{-1,0,1\}$ with the probabilities:
\begin{equation*}
\text{Pr}(r = -1) = \text{Pr}(r = 1) = 1/4; \text{Pr}(r = 0) = 1/2
\end{equation*}
If $\text{dbl}$ is applied to a coefficient vector or polynomial, it is executed coefficient wise. In our example, we have to apply this to $v(X) = 816X^3 + 81X^2 + 698X + 367$. I sampled $r = -1$, $r = 1$, $r = 0$, $r = 0$ in the four rounds, which yields
\begin{equation}
\overline{v}(X) = 1632X^3+162X^2+1395X+734
\end{equation}
$\textbf{B.6}$: The definition of the $\langle \cdot \rangle$ function is:
\begin{align*}
\langle \cdot \rangle: &\;\mathbb{Z}_q \rightarrow \mathbb{Z}_{2} \\
& x \mapsto \langle x \rangle_{q,2} = \left\lfloor \frac{4}{q}x \right\rfloor \pmod{2}
\end{align*}
and again, if applied to a polynomial or coefficient vector, it is executed coefficient wise. The application of $\langle \cdot \rangle_{2q,2}$ to $\overline{v}$ yields:
\begin{align*}
\langle 1632 \rangle_{2018,2} & = \lfloor \frac{4}{2018}1632 \rfloor \pmod{2}
= \lfloor 3.234... \rfloor = 3 \equiv 1 \pmod{2} \\
\langle 162 \rangle_{2018,2} & = \lfloor \frac{4}{2018}162 \rfloor \pmod{2}
= \lfloor 0.321... \rfloor = 0 \equiv 0 \pmod{2} \\
\langle 1395 \rangle_{2018,2} & = \lfloor \frac{4}{2018}1395 \rfloor \pmod{2}
= \lfloor 2.765... \rfloor = 2 \equiv 0 \pmod{2} \\
\langle 734 \rangle_{2018,2} & = \lfloor \frac{4}{2018}734 \rfloor \pmod{2}
= \lfloor 1.454... \rfloor = 1 \equiv 1 \pmod{2} \\
\end{align*}
Hence $c = (1,0,0,1)$, i.e., $c(X) = X^3+1$.
$\textbf{B.7}$: The definition of the $\lfloor \cdot \rceil$ function is similar:
\begin{align*}\lfloor \cdot \rceil: &\;\mathbb{Z}_q \rightarrow \mathbb{Z}_{2} \\
& x \mapsto \lfloor x \rceil_{q,2} = \left\lfloor \frac{2}{q}x \right\rceil \pmod{2}
\end{align*}
The application of $\lfloor \cdot \rceil_{2q,2}$ to the coefficient vector $\overline{v}$ yields:
\begin{align*}
\lfloor 1632 \rceil_{2018,2} & = \lfloor \frac{2}{2018}1632 \rceil \pmod{2}
= \lfloor 1.617... \rceil = 2 \equiv 0 \pmod{2} \\
\lfloor 162 \rceil_{2018,2} & = \lfloor \frac{2}{2018}162 \rceil \pmod{2}
= \lfloor 0.160... \rceil = 0 \equiv 0 \pmod{2} \\
\lfloor 1395 \rceil_{2018,2} & = \lfloor \frac{2}{2018}1395 \rceil \pmod{2}
= \lfloor 1.382... \rceil = 1 \equiv 1 \pmod{2} \\
\lfloor 734 \rceil_{2018,2} & = \lfloor \frac{2}{2018}734 \rceil \pmod{2}
= \lfloor 0.727... \rceil = 1 \equiv 1 \pmod{2} \\
\end{align*} So the key Bob computes is $$\text{key}_\text{Bob} = (0,0,1,1)$$.
$\textbf{A.3}$: Now Alice receives $b'$ and $c$. We now define the three intervals: $I_0 = \{0,1,\ldots,\lfloor q/2 \rceil -1\}$, $I_1 = \{-\lfloor q/2 \rfloor, \ldots, -1\}$ and $E = \left[-q/4,q/4\right)$. Then the reconciliation function $\text{rec}$ is defined as:
\begin{align*}
\text{rec}: &\;\mathbb{Z}_{2q}\times \mathbb{Z}_2 \rightarrow \mathbb{Z}_{2} \\
\text{rec}(w,b) & =
\begin{cases}
0,\;\text{if }w\in I_b + E \pmod{2q} \\
1,\;\text{otherwise}
\end{cases}
\end{align*}
Note that the first component is evaluated in $R_{2q}$, hence in our example we get:
\begin{align*}
& 2b'(X)s(X) = 2(106X^3 + 463X^2 + 760X + 217)(X^3+3X+2) \\
& = 1618X^3 + 146X^2 + 1398X + 730
\end{align*} then Alice computes $\text{rec}((1618, 146, 1398, 730),(1,0,0,1))$, which is\begin{align*}
&(1618,1) \equiv (-400,1): -400 \in I_1 + E = [-756,\ldots, 251] \rightarrow 0 \\
&(146,0): 146 \in I_0 + E = [-252,\ldots, 756] \rightarrow 0 \\
&(1398,0) \equiv (-620,0): -620 \not\in I_0 + E = [-252,\ldots, 756] \rightarrow 1 \\
&(730,1): 730 \not\in I_1 + E = [-756,\ldots, 251] \rightarrow 1 \\
\end{align*} Hence Alice computes $$\text{key}_\text{Alice} = (0,0,1,1)$$ which is the same as $\text{key}_\text{Bob}$.
Note that the scheme guarantees $\text{key}_\text{Bob} = \text{key}_\text{Alice}$ only with some error probability. So there might be a failed key exchange, but the error probability is negligible.
# # #
But why does this actually work? That means, why does $$\lfloor \overline{v} \rceil_{2q,2} = \text{rec}(2b's,\langle \overline{v} \rangle_{2q,2})$$ (almost always) hold? Therefore, observe that
\begin{align*}
2b's & = 2(as'+e)s \\
& = 2as's+2es\\
\text{and}\\
\overline{v} & = 2v - r = 2(bs'+e'') - r \\
& = 2((as+e)s' + e'') - r \\
& = 2ass' + 2es' + 2e'' - r
\end{align*}
Hence $\overline{v}$ and $2b's$ differ by $D = 2es - 2es' - 2e'' + r$ (the $r$ comes from the $\text{dbl}$ function), i.e. $$2bs' = \overline{v} + D$$ If all terms are sufficient small (which they actually are), such that $-q/4 \leq D < q/4$, the following Lemma holds:
Lemma. If $w = v + e \pmod{2q}$ and $e \in \left[-q/4,q/4\right)$, then $$\text{rec}(w,\langle v \rangle_{2q,2}) = \lfloor v \rceil_{2q,2}$$
Proof. Since $\text{rec}$, $\lfloor \cdot \rceil_{2q,2}$ and $\langle \cdot \rangle_{2q,2}$ work component wise, it is enough to prove the lemma for one component, hence we pick the first one $w_0 = v_0 + e_0$. It is $\langle v_0\rangle_{2q,2} \in \{0,1\}$, i.e. $$\left\lfloor \frac{4}{2q}v_0 \right\rfloor = \left\lfloor \frac{2}{q}v_0 \right\rfloor \pmod{2}$$ Since $0 \leq v_0 < 2q$, $\left\lfloor \frac{2}{q}v_0 \right\rfloor$ is either $0,1,2$ or $3$ according to which of the quarters $(0,q/2],(q/2,q],(q,3q/2]$ or $(3q/2,2q]$ contains $v_0$. The reduction of $1,2,3,4$ modulo two yields $0,1,0,1$. On the other hand, the $\lfloor \cdot \rceil$ function is $$\left\lfloor \frac{2}{2q}v_0 \right\rceil = \left\lfloor \frac{1}{q}v_0 \right\rceil \pmod{2}$$ Likewise, the result depends on the quarter that contains $v_0$. But due to the different rounding method, the reduction modulo two this time yields $0,1,1,0$. So $\langle\cdot\rangle$ and $\lfloor\cdot\rceil$ are equal for $v_0 < q$ and inverse for $v_0 > q$.
We can conclude, that the $\langle v_0 \rangle_{2q,2}$ value given as the second parameter of $\text{rec}$, reduces the four possibilities for a quarter down to two. For a further reduction down to one, we can use the first parameter $w_0 = v_0+e_0$. Note that this is easy, since $w_0$ is actually already almost equal to $v_0$ up to an error of $e$ less than $q/4$. Hence $w_0$ is sufficient to choose the correct quarter which allows to deduce the value $\lfloor v_0 \rceil_{2q,2}$.
To rephrase this a little bit more concrete, observe that the $\text{rec}$ function looks at the intervals $I_0 = \{0,1,\ldots,\lfloor q/2 \rceil -1\}$ and $I_1 = \{-\lfloor q/2 \rfloor, \ldots, -1\}$ and adds space for the error term by the addition of $E = (-q/4,q/4]$, so we have $$I_0 + E = (-q/4, \ldots, \lfloor q/2 \rceil-1+q/4]$$ and $$I_1 + E = (-\lfloor q/2 \rfloor-q/4, \ldots, -1+q/4]$$ There are four cases, but we only look at the first, since the other ones are analogous:
1) Assume $\lfloor v_0 \rceil_{2q,2} = 0$, hence either $0 \leq v_0 < q/2$ or $3q/2 \leq v_0 < 2q$.
2) Assume $\langle v_0 \rangle_{2q,2} = 0$, hence either $0 \leq v_0 < q/2$ or $q \leq v_0 < 3q/2$.
If both values would be available, this would immediatelly allow to determine the correct quarter $(0,q/2]$. But $\langle v_0 \rangle_{2q,2}$ together with the value $w$ is already sufficient, since $$w_0 = v_0 + e_0$$ and $|e| < q/4$. Assume $w_0 = v_0 + e \in I_0 + E \in (-q/4, \ldots, \lfloor q/2 \rceil-1+q/4]$. Then it follows $0 \leq v_0 < q/2$, hence the first quarter is the correct one. But for each element $h \in [0,q/2)$ it holds $\lfloor h \rceil_{2q,2} = 0$, hence $\lfloor v_0 \rceil_{2q,2} = 0$, which is the first key bit.
Q.e.d.
[1] Jintai Ding, Xiang Xie, Xiaodong Lin, A Simple Provably Secure Key Exchange Scheme Based on the Learning with Errors Problem,Cryptology ePrint Archive, Report 2012/688, 2012
[2] Peikert, Chris. Mosca, Michele, ed. Lattice Cryptography for the Internet. Lecture Notes in Computer Science. Springer International Publishing. pp. 197–219.
[3] Joppe W. Bos and Craig Costello and Michael Naehrig and Douglas Stebila, Post-quantum key exchange for the TLS protocol from the ring learning with errors problem, Cryptology ePrint Archive, Report 2014/599, 2014. Published at IEEE Security & Privacy 2015
[4] Erdem Alkim and Léo Ducas and Thomas Pöppelmann and Peter Schwabe,Post-quantum key exchange - a new hope, Cryptology ePrint Archive, Report 2015/1092, 2015, Published at Usenix Security 2016
[5] Brakerski, Zvika; Vaikuntanathan, Vinod (2011). Rogaway, Phillip, ed. Fully Homomorphic Encryption from Ring-LWE and Security for Key Dependent Messages. Lecture Notes in Computer Science. Springer Berlin Heidelberg. pp. 505–524.
[6] Oded Regev, “On lattices, learning with errors, random linear codes, and cryptography,” in Proceedings of the thirty-seventh annual ACM symposium on Theory of computing (Baltimore, MD, USA: ACM, 2005), 84-93,
No comments:
Post a Comment