Scott Fluhrer edited untitled.tex  over 8 years ago

Commit id: 1450eb0d84fde193b1a13876512b6bfb3b6c430a

deletions | additions      

       

To make a query, Eve mostly follows the protocol; she selects small $s', e'$ values (albeit not randomly), she computes $v'$, and generates the error-reconcilation vector $c$ honestly, except for one location.  She deliberately selects $s', e'$ so that coefficient 0 of Alice's computation of $us$ is near 0; for coefficient 0, Eve sets it so that the values in $[0, p/2]$ are mapped to 0, while values in $[p/2, p-1]$ are mapped to 1. As Eve is able to compute correctly all the other bits of the shared secret (as she is performing the rest of the protocol honestly), this gives her a way to test the sign of that one intermediate value.  \subsection{Finding a probe value}  The first step in the attack for Eve is to find a lightweight value $s'$ where $(ass')[0] = \pm 1$  ...