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.
No comments:
Post a Comment