The Insecurity of the Elliptic Curve Digital Signature Algorithm with Partially Known Nonces

Phong Q. Nguyen*, Igor E. Shparlinski

*Corresponding author for this work

Research output: Contribution to journalArticle

101 Citations (Scopus)

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 log1/2 q, but can be decreased to log log q with a running time qo(1/loglogq) subexponential in log q, and even further to two 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).

Original languageEnglish
Pages (from-to)201-217
Number of pages17
JournalDesigns, Codes and Cryptography
Volume30
Issue number2
DOIs
Publication statusPublished - Sep 2003

Fingerprint Dive into the research topics of 'The Insecurity of the Elliptic Curve Digital Signature Algorithm with Partially Known Nonces'. Together they form a unique fingerprint.

Cite this