Paper 2002/026

Generic Groups, Collision Resistance, and ECDSA

Daniel R. L. Brown


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.

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.

Available format(s)
Public-key cryptography
Publication info
Published elsewhere. Unknown where it was published
ECDSAprovable securityhash function
Contact author(s)
dbrown @ certicom com
2002-02-27: last of 3 revisions
2002-02-26: received
See all versions
Short URL
Creative Commons Attribution


      author = {Daniel R.  L.  Brown},
      title = {Generic Groups, Collision Resistance, and {ECDSA}},
      howpublished = {Cryptology ePrint Archive, Paper 2002/026},
      year = {2002},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.