Scott Fluhrer edited untitled.tex  over 8 years ago

Commit id: 5e0d6e56937ed70d51b24f562008fb468f70b597

deletions | additions      

       

\begin{itemize}  \item Alice and Bob agree on a random 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 doesn't does not  actually need the value of $e$) are Alice's private secret. \item Alice computes the value $b = as + e$; 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 Both sides then use the error-reconciliation vector $c$ to convert their $v, v'$ into a shared secret  \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.  The idea behind this protocol is that Alice computes $v = ass' + se'$, while Bob computes $v' = ass' + s'e$, they differ by $se' - s'e$, as $s, s', e, e'$ are small elements, this is (with high probability) also small, and so each element of $v$ is "close" to the corresponding element of $v'$.  ...  \section{Key Recovery Attack 1}