Is Ed25519 is EUF-CMA secure?

Question

Is the signature scheme of shelley (Ed25519) is EUF-CMA secure? The Existential Unforgeability under Chosen Message Attack experiment works like this:

1. The challenger generates a valid keypair (pk, sk) and gives pk to the attacker.

2. The attacker may now repeatedly ask for signatures on chosen messages $(M_1, \dots, M_q)$ of its choosing, and receives the valid signatures $(\sigma_1, \dots, \sigma_q)$ in response.

3. At the conclusion of the experiment, the attacker must output a message and signature $M^$, $\sigma^$ such that (1) the message $M^*$ was not one of the messages requested in the previous step, and (2) the message/signature verifies correctly under the public key (Ref).

Now I guess the used signature scheme by Shelley is EUF-CMA secure since by assuming the contrary it would break the blockchain?

---

EDIT

The only problem I see with assuming the contraposition of the statement is that the messages $(M_1,\dots, M_q)$ are chosen by the adversary. This is not the case in a public ledger though it could be extracted?

Answer 1

Yes, Ed25519 provides the existential unforgeability property. There is a nice work that studies the different variants of Ed25519 signatures

https://eprint.iacr.org/2020/823.pdf

As specified in that document, the different variants of ed25519 provide different security properties, but all are existentially unforgeable under chosen message attacks.

Indeed, as you point out, if an adversary could forge valid signatures to messages not signed by the key owner, the security of the blockchain could be compromised.