The EdDSA signature scheme is a deterministic scheme. So could it be proven provable security in Random oracle model?

  • 1
    $\begingroup$ @kelaka The above link is not an answer. EdDSA is essentially Schnorr and not DSA/ECDSA. $\endgroup$ – Yehuda Lindell Feb 26 '20 at 10:16
  • $\begingroup$ @YehudaLindell uh that is hard to write a nickname. ups EdDSA, I should be more careful. $\endgroup$ – kelalaka Feb 26 '20 at 21:06
  • $\begingroup$ @kelalaka What does your answer mean? $\endgroup$ – votunglinh Feb 28 '20 at 2:43

EdDSA is Schnorr signatures over the Edwards curve, with an additional twist that it is made deterministic. The basic Schnorr scheme can be proven secure under the discrete log assumption in the random oracle model. Furthermore, any probabilistic signature scheme can be made deterministic by applying a PRF (with a key that is part of the private key) to the message in order to derive the randomness used. This is essentially what EdDSA does. Thus, yes, it is provably secure in the random oracle model, assuming that the discrete log problem is hard in that group.

  • $\begingroup$ Lindel thanks for your answer. But in my opinion, EdDSA's empheral secret generation process is deterministic, so it is hard to apply random oracle model on this scheme. Can you explain more clearly? $\endgroup$ – votunglinh Feb 28 '20 at 2:25
  • $\begingroup$ Note that the difference between deterministic secret generation for EdDSA and regular Schnorr relates to the first step of choosing the random $k$ or $r$ (however you like to denote it). This does not use a random oracle, but rather I would look at it as a PRF based on a hash function. The replacement of the verifier message in the sigma protocol is what uses the random oracle, and this is the same for both. Another way to look at it is to say that if it is a secure signature scheme when choosing the value randomly, then it remains secure when using a PRF. $\endgroup$ – Yehuda Lindell Feb 28 '20 at 6:05

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.