3
$\begingroup$

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?

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

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.

| improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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