*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:

- The game runs $\mathsf{KG}$ to get (pk,sk)$
- 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$
- $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.