I'm trying to understand why is this, in my opinion, counter intuitive construction secure. ECDSA is a tuple of two numbers (r, s) whose validity can be verified by public key. However I don't see the reason why the only way to forge the signature is breaking the DLog problem on the EC. I spent many hours thinking about it and still don't comprehend where is the bottleneck. How do we know that there is no other algorithm for generating (r, s) without the knowledge of private key?

  • $\begingroup$ See my comment below on recent work on the provable security of (EC)DSA. $\endgroup$
    – DrLecter
    Oct 27, 2017 at 19:48

1 Answer 1


We don't. As far as I know there is no proof of security for ECDSA in any model. There is, however, almost 2 decades of usage in the wild, including by Bitcoin and Ethereum, which would allow any would-be attacker to make a tremendous amount of profit. The fact that this appears to have never happened is good empirical evidence for its security.

I've also spent a while exploring this problem. I believe that if you model the mapping from a curvepoint to its x-coordinate as a random oracle function you can use a forking lemma argument to prove the signature secure. This is unrealistic but it implies that any forger would need to find a meaningful relationship between points and their x-coordinates, and it's hard to imagine such a thing that wouldn't also solve the discrete log problem.

  • 6
    $\begingroup$ Actually, there is a proof in the generic group model and a recent one in the bijective random oracle model. See here: dl.acm.org/citation.cfm?doid=2976749.2978413 $\endgroup$
    – DrLecter
    Oct 27, 2017 at 19:47
  • $\begingroup$ There is a proof that it is critically vulnerable to nonce reutilization. $\endgroup$
    – LatinSuD
    May 24 at 12:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.