What I see that their difference is that in EUF-CMA experiment, the adversary needs to produce a valid signature for a message of its choosing, where the message has not been queried before (i.e., a message for which the adversary hasn't made queries to the oracle).
Whereas in the sEUF-CMA experiment, similar thing happens, though now the adversary needs to make sure that it hasn't queried the oracle with the forged (message, signature) pair. So, simply the signature also enters into the equation in sEUF-CMA.
Right. The point of EUF-CMA is the forger simply can't find a signature on any message it didn't send to the oracle. With sEUF-CMA, the forger can't find a message/signature pair it didn't get from the oracle—not even a second signature on a message it did send to the oracle.
- The part that I don't understand is why the sEUF-CMA actually constitutes a stronger definition than regular EUF-CMA definition? Why does including the signature makes it stronger?
- Can you forge signatures for messages not previously seen in an sEUF-CMA signature scheme, or can you prove that that's not possible? What does that imply about whether an sEUF-CMA signature scheme is necessarily EUF-CMA?
- Can you find a signature scheme that satisfies EUF-CMA but not sEUF-CMA? (Hint: you already did!) What does that imply about whether an EUC-CMA signature scheme is necessarily sEUF-CMA?
‘Strong’ just mean it implies other properties which don't necessarily imply it conversely. Most protocols don't rely on strong unforgeability. While Bitcoin doesn't rely on strong unforgeability, the first Bitcoin exchange, MtGox, did; it was exploited, because ECDSA does not provide strong unforgeability, and the subsequent demise of MtGox was later blamed on transaction malleability, whether rightly or not (paywall-free).
Another relevant property is signature uniqueness where even the signer can't come up with a second signature for a message—for this you may even want a VRF, a verifiably pseudorandom function, which is a PRF to anyone who doesn't know the key and is a signature to anyone who does and gives a verifiable proof of uniqueness.
Also, for example in ECDSA, for a message $m$ and a valid signature $\sigma = (r,s)$, the signature $\sigma' = (r, -s \bmod N)$ is also valid. So, in a sense you get a new signature $\sigma'$, but, actually the signed message is the same $m$.
So, this seems to me that it does violate sEUF-CMA as, although the message is the same one, the signature is different, so adversary wins. Whereas, this cannot violate EUF-CMA, while there we care only for the message, so we don't care if adversary can produce a forgery for an already queried message. So, it achieves EUF-CMA security, but not sEUF-CMA, right?.
- I think the situation is also different in textbook RSA, where it has homomorphic properties, so given a valid $(m, \sigma)$ pair, using the homomorphic properties one can produce a valid signature $\sigma'$ for a new message $m'$, and it seem does not satisfy any of the provided security definitions, is that right?
Textbook RSA signature is, indeed, completely broken. RSA was the first idea for how to make a signature scheme, but it was completely insecure; the first secure signature scheme was Rabin's in 1979.
The crucial insight of Rabin was that hashing is an integral part of a signature scheme. Some textbooks will confusingly describe hashing as an afterthought to compress long messages, and talk of hash-then-sign, which is a dangerously wrong idea that can lead people to make mistakes that destroy security.
The computation of a hash and the computation of fancy math can be done separately, but only when they are combined into a verification equation like $\sigma^e \equiv H(m) \pmod n$ do you get a secure signature scheme.