Is the EdDSA signature scheme provable security? The EdDSA signature scheme is a deterministic scheme. So could it be proven provable security in Random oracle model?
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.