A Digital Signature scheme $\system$ for message space $\msgspace{}$ is a tuple $(\keygen, \sign, \verify)$ with:

• $\keygen(1^n) \to (pk, sk):$ Probabilistic key generation algorithm which on input $1^n$ returns key pair $(pk, sk)$. $pk$ is the public key and $sk$ is the secret key.
• $\sign(sk, m) \to \sigma$: Sign algorithm, takes as input a secret key $sk$ and a message $m \in \msgspace$, returns a signature $\sigma$.
• $\verify(pk, m, \sigma) \to \{0, 1\}$: Deterministic verification algorithm, takes as input public key $pk$, message $m$, and signature $\sigma$, returns $1$ if $m, \sigma$ is a valid message signature pair for $pk$.