Signatures: Generalities

In this chapter, we define the syntax of a signature scheme and explore security definitions, asking ourselves: what makes a signature scheme secure?

Syntax

A signature scheme consists of four algorithms:

• a $\mathsf{Setup}$ algorithm which takes as input the security parameter $1^{\lambda }$ and returns public parameters $par;$
• a key generation algorithm $\mathsf{KeyGen}$ which takes as input parameters $par$ and returns a secret key $sk$ and a public key $pk;$
• a signature algorithm $\mathsf{Sign}$ which takes as input parameters $par,$ a secret key $sk,$ and a message $m$ and returns a signature $\sigma ;$
• a verification algorithm $\mathsf{Verif}$ which takes as input parameters $par,$ a public key $pk,$ a message $m,$ and a signature $\sigma$ and returns $1$ if the signature is valid for the pair $(pk,m)$ and $0$ otherwise.

The scheme is correct if for every security parameter $\lambda$ and every message $m,$ the following game capturing the nominal execution of algorithms returns true with probability one:

$$\boxed{\begin{array}{rl}& par\leftarrow \mathsf{Setup}(1^{\lambda })\\ & (sk,pk)\leftarrow \mathsf{KeyGen}(par)\\ & \sigma \leftarrow \mathsf{Sign}(par,sk,m)\\ & b\leftarrow \mathsf{Verif}(par,pk,m,\sigma )\\ & \mathbf{assert}(b=1)\end{array}}$$

This syntax considers that the message space is $\{0,1{\}}^{\ast },$ meaning that the signing algorithm takes any string as input message. In practice, this is never the case: quite often, the signing algorithm starts with hashing the input message with a hash function that has a finite message space. More generally, the message space could depend on the public parameters returned by the setup algorithm (e.g., the public parameters could specify a group and admissible messages could be restricted to group elements.) This can be accommodated by adapting the syntax as follows: on input $(par,sk,m),$ the $\mathsf{Sign}$ algorithms returns either a signature $\sigma$ or a distinguished error symbol $\perp$ indicating the message is invalid (i.e., cannot be signed). Correctness must be modified to require that $b=1$ only if $\sigma \ne \perp .$ Other variables ($par,$ $sk,$ $pk,$ and $\sigma )$ usually have a specific format depending on the security parameter. Similarly, we assume that $\mathsf{KeyGen},$ $\mathsf{Sign},$ and $\mathsf{Verif}$ return an error symbol in case any input does not abide to the expected format.

EUF-CMA, the Standard Security Notion

The standard security notion for a signature scheme is existential unforgeability against chosen message attacks (EUF-CMA): no polynomial-time adversary, being given a target public key $p{k}^{\ast }$ and having access to a signature oracle for the corresponding secret key $s{k}^{\ast },$ should be able to compute a valid signature for a message it has not queried to the signature oracle, except with negligible probability. This is formally captured by the following security game:

$$\boxed{\begin{array}{cc}\begin{array}{l}\text{Game EUF-CMA:}\\ par\leftarrow \mathsf{Setup}(1^{\lambda })\\ (s{k}^{\ast },p{k}^{\ast })\leftarrow \mathsf{KeyGen}(par)\\ \mathcal{Q}:=\varnothing \\ (m^{\ast },{\sigma }^{\ast })\leftarrow {\mathsf{A}}^{\text{Sign}}(par,p{k}^{\ast })\\ \mathbf{assert}(m^{\ast }\notin \mathcal{Q})\\ \mathbf{assert}(\mathsf{Verif}(par,p{k}^{\ast },m^{\ast },{\sigma }^{\ast })=1)\end{array}& \begin{array}{l}\text{Oracle Sign(m):}\\ \sigma \leftarrow \mathsf{Sign}(par,s{k}^{\ast },m)\\ \mathcal{Q}\leftarrow \mathcal{Q}\cup \{m\}\\ \mathbf{return}\sigma \\ \\ \\ \end{array}\end{array}}$$

Here, chosen message attack means that the adversary can query the signature oracle on messages of its choice, while existential unforgeability means that the adversary wins if it returns a forgery on any message that has not been queried to the signature oracle (there exists some message $m^{\ast }$ for which the adversary can forge a signature).

One can weaken this security definition in two directions. One one hand, one can restrict how the adversary can access the signature oracle. For example, in a no message attack, the adversary does not have access to the signature oracle. In a known message attack, the adversary cannot choose the message when querying the signature oracle (the message is randomly drawn according to some specific probability distribution). On the other hand, one can modify how the adversary can choose the message for which it forges its message. For example, selective unforgeability requires the adversary to commit to the message for which it will forge at the beginning of the game, before receiving the target public key and making any query to the signature oracle. For universal unforgeability, the message is imposed by the game rather than chosen by the adversary (typically, it is drawn at random by the game according to some specific distribution).

All these weaker notions are mostly of theoretical interest (for example, there exists generic conversion methods to construct signature schemes that are EUF-CMA-secure from schemes that are only meet selective unforgeability against chosen message attacks). In practice, a signature scheme must be EUF-CMA-secure to be deployed (more precisely, conjectured EUF-CMA-secure, preferably supported by a security proof).

Strong EUF-CMA and Non-malleability

Binding