**Generic Groups, Collision Resistance, and ECDSA**

*Daniel R. L. Brown*

**Abstract: **Proved here is the sufficiency of certain conditions to ensure the
Elliptic Curve Digital Signature Algorithm (ECDSA) existentially
unforgeable by adaptive chosen-message attacks. The sufficient
conditions include (i) a uniformity property and collision-resistance
for the underlying hash function, (ii) pseudo-randomness in the
private key space for the ephemeral private key generator, (iii)
generic treatment of the underlying group, and (iv) a further
condition on how the ephemeral public keys are mapped into the private
key space. For completeness, a brief survey of necessary security
conditions is also given. Some of the necessary conditions are weaker
than the corresponding sufficient conditions used in the security
proofs here, but others are identical. Despite the similarity between
DSA and ECDSA, the main result is not appropriate for DSA, because the
fourth condition above seems to fail for DSA. (The corresponding
necessary condition is plausible for DSA, but is not proved here nor
is the security of DSA proved assuming this weaker condition.)
Brickell et al., Jakobsson et al. and Pointcheval et al. only consider
signature schemes that include the ephemeral public key in the hash
input, which ECDSA does not do, and moreover, assume a condition on
the hash function stronger than the first condition above. This work
seems to be the first advance in the provable security of ECDSA.

**Category / Keywords: **public-key cryptography / ECDSA, provable security, hash function

**Date: **received 27 Feb 2002

**Contact author: **dbrown at certicom com

**Available format(s): **Postscript (PS) | Compressed Postscript (PS.GZ) | BibTeX Citation

**Note: **This paper is a revision of an earlier draft
"The Exact Security of ECDSA" that was submitted to
the IEEE P1363 working group and to the CACR, U. of Waterloo.

**Version: **20020227:183237 (All versions of this report)

**Short URL: **ia.cr/2002/026

**Discussion forum: **Show discussion | Start new discussion

[ Cryptology ePrint archive ]