52 Things: Number 29: What is the UF-CMA security definition for digital signatures?

This is the latest in a series of blog posts to address the list of '52 Things Every PhD Student Should Know To Do Cryptography': a set of questions compiled to give PhD candidates a sense of what they should know by the end of their first year. In this week we look at the security definition for signatures.

So Number 16 gave the details of the DSA, Schnorr and RSA-FDH signature schemes, but what is a signature scheme and what security properties should it achieve?

A signature scheme $\mathsf{S}$ is a tuple of algorithms $(\mathsf{KG},\mathsf{Sign},\mathsf{VRFY})$ such that:

• $\mathsf{KG}$ is a randomised algorithm which outputs a secret key $sk$ and a public key $pk$.
• $\mathsf{Sign}$ is a  (possibly) randomised algorithm which on input $sk$ and a message $m$ it outputs a signature $\sigma$
• $\mathsf{VRFY}$ is a deterministic (non-stateful) algorithm which takes in the public key $pk$, a message $m$ and a signature $\sigma$ and returns 1 if $\sigma$ is a signature on $m$ and 0 otherwise

Signature schemes are used to prove the origin of a message. If a message has a signature on it, signed by Alice's secret key then it must have come from Alice. The advantage of using a signature scheme over a MAC (assuming good public key infrastructure) is that it can be verified by anyone and does not need any shared secrets.

Now for the signature to prove the origin of a message, it needs to be the case that someone without the secret key can not create a valid signature on a message he has not seen signed before. This is called UF-CMA security.

The game works as follows:

1. The game runs $\mathsf{KG}$ to get (pk,sk)$
2. The adversary $A$ is given $pk$ and can then send messages $m_i$ to the game and get back signatures $\sigma_i$ under the secret key $sk$
3. $A$ must output a pair $(m^*,\sigma^*)$

$A$ is said to win the game if $\sigma^*$ is a valid signature on $m^*$ and $m^*$ is not the same as any of the $m_i$'s which $A$ asked the game to be signed. The advantage of the adversary in the UF-CMA game is defined as the probability that $A$ wins the game. The signature scheme $\mathsf{S}$ is said to be UF-CMA secure if the advantage is suitably small.