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\).