Abstract:
Nguyen and Shparlinski have recently presented a polynomial-time algorithm
that provably recovers the
signer's secret DSA key when a few consecutive bits of the random nonces k
(used at each signature generation) are known for a number of DSA signatures
at most linear in \log q (q denoting as usual the small prime of DSA),
under a reasonable assumption on the hash function
used in DSA. The number of required bits is about \log^{1/2} q,
but can be decreased to \log \log q with a running time q^{O(1/\log \log
q)}
subexponential in \log q, and even further to 2 in polynomial time
if one assumes access to ideal lattice basis reduction,
namely an oracle for the lattice
closest vector problem for the infinity norm.
All previously known results were only heuristic,
including those of Howgrave-Graham and Smart who introduced the
topic. Here, we obtain similar results
for the elliptic curve variant of DSA (ECDSA).