deletions | additions       diff --git a/untitled.tex b/untitled.tex  index 1cae48b..174ae2f 100644  --- a/untitled.tex  +++ b/untitled.tex 
...
This paper will show that ring-LWE based key agreement protocols are not safe in this mode; if Alice uses the same private value repeatedly, then Eve (by sending a series of messages, and seeing how Alice responds) is able to recover Alice's private value (and if Alice used that same static value to generate the keys used to communicate to Bob, Eve can then listen into that conversation).  \section{Ring-LWE Key Exchange}  The Ring-LWE problem\cite{Lyubashevsky_2013} works in the Ring $\mathbb{Z}[x]/(x^N+1, p)$, for integers $N$ and $p$, and $p$. A member of this ring can be viewed as consisting of $N$ integers (coefficients) each in $[0, p)$. It  has been proposed as the basis  for a number of cryptographical systems. These include a number of key agreement protocols, including such as  \cite{Ding_2012}, \cite{Peikert_2014}, \cite{Alkim_2015}, and \cite{Singh_2015}. While these protocols differ in the details, they all follow the same basic paradigm.  \begin{itemize}  \item Alice and Bob agree on a random an  element $A$; it may be a global parameter, or it may be based on a seed provided by Alice \item Alice selects "small" elements $S$ and $E$; these values (actually, $S$; Alice the value $S$ (Alice  doesn't actually need to remember the value of $E$) are is  Alice's private secret. \item Alice computes the value $B = AS + E$; E$ (where the multiplication and addition are done using the ring primitives);  this value is Alice's public key share, which she sends to Bob \item Bob also selects small elements $S'$ and $E'$; he computes the value $U = AS' + E'$ and the value $V' = BS'$.  \item Bob then uses $V'$ to compute an error-reconcilation vector $C$; he sends $U, C$ to Alice  \item Alice computes the value $V = US$  \item Both sides then use the error-reconciliation vector $C$ to convert their $V, V'$ into a shared secret, converting each coefficient of $V, V'$ into one bit.  \end{itemize}   Some versions of the key agreement add additional error vectors at some places; as the attack can be modified to account for this, we will ignore it. it for now.  The idea behind this protocol is that Alice computes $V = SS'A + SE'$, while Bob computes $V' = SSA' + S'E$, they differ by $SE' - S'E$, as $S, S', E, E'$ are small elements, this is (with high probability) also small, small (in that each coefficient is close to 0),  and so each element of $V$ is "close" to the corresponding element of $V'$. Of course, being close doesn't mean that they're identical; if while they are close, they aren't identical. If  we used any fixed mapping of the coefficients of $V, V'$ to the shared secrets would mean that we would have some probability that an element of $V$ would be on one side of the boundary, while the same element of $V'$ would be on the other. That's where the error-reconciliation vector comes in. We logically split up the possible coefficient values into four quadrants; quadrant I ($[0, p/4)$), quadrant II ($[p/4, p/2)$), quadrant III ($[p/2, 3p/4)$), and quadrant IV ($[3p/4, p-1]$)  There is a bit within the error-reconciliation vector  that corresponds to each coefficient; it determines whether quadrants I and II are considered the same (e.g. values there would may  map to a 0 bit, while values in quadrants III and IV would map to a 1 bit); or whether quadrants I and IV are considered the same (e.g. values there would may  map to a 0 bit, while values in quadrants II and III would map to a 1 bit). The intention is that Bob would, for each coefficient value of $V'$, determine the value of the error-reconcilation bit that would give the largest possible leeway for errors. As long as the absolute value of  any error coefficient of $SE' - S'E$  is no more than $p/8$, it will always be possible for Alice and Bob to agree on the shared secret. By choosing the size of the small values for $S, S', E, E'$, we can make this happen with extremely high probability.  \section{The Attack}