EUF-CMA and SUF-CMA

There are two common formal definitions for the security of a digital signature scheme. Each of these definitions is presented as a “game”, or an experiment that is run between an attacker and some honest challenger.

Informally, the EUF-CMA (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. Note that these queries and responses can be made adaptively and interactively — they are not all made in one burst.
  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.

The scheme is considered secure if no (efficient) adversary has a non-negligible advantage in satisfying the conditions above. Normally the number of messages q is bounded only by the attacker’s running time — however, for the special case of one-time signatures, the adversary is limited to asking for only one signature in step (2).

This definition is fairly strong, but not as strong as possible. A slightly stronger definition is the SUF-CMA definition.

Informally, the SUF-CMA (Strong Existential Unforgeability under Chosen Message Attack) experiment works like this:

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

The attacker wins if she satisfies the conditions above.

The main difference here is that this stronger definition ensures that the attacker cannot “maul” the signature. For example, a scheme where the attacker can re-randomize a valid signature so that it’s still valid, but looks different than the original value, would not satisfy SUF-CMA. 

This might seem like a silly requirement, but it matters in some protocols. For example, this sort of malleability is possible in the ECDSA signature scheme, and has led to many problems in Bitcoin.