The insecurity of the elliptic curve digital signature algorithm with partially known nonces (Q1412249)

This paper contains the first provable polynomial-time attack against the elliptic curve digital signature algorithm, when the nonces are partially known. The ``nonces'' are the random integers used to disguise the contribution of the secret key in the digital signature. \textit{N. Howgrave-Graham} and \textit{N. Smart} [Des. Codes Cryptography 23, 283--290 (2001; Zbl 1006.94022)] proposed several heuristic attacks against DSA assuming that a certain (not too small) number of bits of the nonces are known. \textit{P. Q. Nguyen} and \textit{I. E. Shparlinski} [J. Cryptology 15, 151--176 (2002; Zbl 1009.94011)] obtained provable polynomial-time attacks to DSA when the nonces are partially known, based on a generalization of the work of Boneh-Venkatesan on the hidden number problem. In this paper these ideas are extended to the case of ECDSA, building on results on the distribution of ECDSA signatures, based on bounds of exponential sums valuated on \(x\)-coordinates of elliptic curves over finite fields.