What does existential unforgeability mean in a digital signature scheme?

Question

In a digital signature scheme (Gen, Sign, Verfiy) that satisfies correctness and existential unforgeability, can you assume that the outputs of Sign() are computationally indistinguishable from random?

Answer 1

What does existential unforgeability mean in a digital signature scheme?

"Existential unforgeability" alone means adversaries can't create signatures that verify for messages they have not already a signature for. Strictly speaking, breaking existential unforgeability may only mean adversaries end up with a message and signature that verify, but the message is gibberish void of any use for the adversaries.

There is also "strong existential unforgeability", which additionally means adversaries can't create new signatures that verify, against any message. ECDSA is an example of scheme with existential unforgeability, but not strong existential unforgeability. That's because if $(r,s)$ is a valid signature for some message, then the different $(r,n-s)$ also is valid for the same message.

The "existential" adjective opposes to the more difficult goal for adversaries of signing a message they choose, in whole ("selective forgery") or part (e.g. choosing a prefix of the document), to have a meaning useful for some nefarious goal against the system using digital signature. "Existential" refers to the fact "there exists" a (message, signature) pair with new message (or/and new signature) that pass verification in what the adversaries produce.

"Existential unforgeability" is often followed by "under chosen message attack", meaning adversaries are assumed to be able to obtain signatures for messages of their choice. The messages they submit for signature are discounted from those that count as successful forgery. In strong existential forgery, the signatures they obtain this way are similarly discounted. Chosen message attack opposes to known (message, signature) pair(s), and no-message attack.

It's common that an existential forgery can be extended to meaningful messages or exploited in some devious way (like a buffer overflow, denial of service or code injection). It's also common that adversaries can influence enough the messages that get signed to make an attack possible even though it does not qualify as a full-fledged chosen message attack. There's also the danger of adversaries merely pretending other adversaries have ruined the security, breaking trust in the system. Therefore, it has become the baseline to require Existential UnForgeability under chosen message attack (EUF-CMA). This adequately protects against message alteration without approval of the holder of a public key.

I refer to this answer for a more formal taxonomy of UF variants.

Best practice for modern signature schemes is strong EUF-CMA, plus Signature Collision Resistance, and Universal Exclusive Ownership. See Dennis Jackson, Cas Cremers, Katriel Cohn-Gordon and Ralf Sasse: Seems Legit: Automated Analysis of Subtle Attacks on Protocols that Use Signatures, in Cryptology ePrint Archive, Report 2019/779, originally in proceedings of ACM CCS 2019.

---

In a digital signature scheme (Gen, Sign, Verfiy) that satisfies correctness and existential unforgeability, can you assume that the outputs of Sign() are computationally indistinguishable from random?

No. For example RSASSA-PSS is provably sEUF-CMA, yet it's signatures are distinguishable from random (by examining the high-order bit of the first byte of the undecorated signature, which is biased towards 0 unless the public key has many high-order bits at 1, or/and something in the signature procedure is crafted to make such bias less detectable; which is easy, but uncommon). That's even without the public key or message. Obviously, if the public key and message is known, no correct signature scheme can have it's signature indistinguishable from random; the verifier is a distinguisher!

Answer 2

Informally, it is the inability of an attacker to forge a signature for any message, not signed by a legitimate signer. Now to assess existential unforgeability (EU) of a signature scheme, we need an adversary with an attack model.

1. Key Only attack (EU-KOA) : Informally the adversary only has a public key and is allowed to choose any message for forge signature on after getting the public key

$(pk,sk)\leftarrow Gen$

Run adversary $A(pk,1^n)$

Obtain response $(m,s) $ as message signature pair for adversary

2. Known message attack (EU-KMA): Informally, the adversary has access to many message, signature pairs along with the public key before which she can use as information to forge the signature on any other message

$(pk,sk)\leftarrow Gen$

Run adversary $A(pk,1^n)$

Generate $m_1,m_2...m_k$ messages and sign them all. Send message-signature pairs $(m_1,s_1),(m_2,s_2)...(m_k,s_k)$

Obtain response $(m,s) $ as message signature pair for adversary where $m \notin {m_1,m_2..m_k}$

3. Chosen message attack (CMA): Informally, the adversary can obtain signatures for messages of her choice. We model this by giving the adversary an access to a signing oracle. $(pk,sk)\leftarrow Gen$

Run adversary $A(pk,1^n,O^{sk})$ Here $O^{sk}$ is signing oracle

Adversary queries $m_1,m_2...m_k$ messages to $O^{sk}$ and obtain signatures. The messages can be chosen adoptively. Adversary obtains message-signature pairs $(m_1,s_1),(m_2,s_2)...(m_k,s_k)$

Obtain response $(m,s) $ as message signature pair for adversary where $m \notin {m_1,m_2..m_k}$

Needless to say, the number and length of messages are of polynomial function of some security parameter as well as any calculation that an adversary performs is polynomial time. The signature scheme is not existentially unforgeable under any attack model if the adversary succeeds with responding with a valid message signature pair with a non-negligible probability

It is different from selective forgery where the attacker cannot choose the message freely to forge signature for after the attack commences, and from universal forgery where the message to forge signature for is provided to the adversary (implying that with this the attacker can forge signature for any message even provided by someone else).