TY - JOUR

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

AU - Nguyen, Phong Q.

AU - Shparlinski, Igor E.

PY - 2003/9

Y1 - 2003/9

N2 - 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).

AB - 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).

UR - http://www.scopus.com/inward/record.url?scp=0141889703&partnerID=8YFLogxK

U2 - 10.1023/A:1025436905711

DO - 10.1023/A:1025436905711

M3 - Article

VL - 30

SP - 201

EP - 217

JO - Designs, Codes and Cryptography

JF - Designs, Codes and Cryptography

SN - 0925-1022

IS - 2

ER -