A signature scheme is a triple of algorithms \(\DS = (\op {Gen},\op {Sign},\op {Ver})\) over a key space \(\Keys \), a message space \(\Msgs \), a signature space \(\Sigs \) and a coin space \(\{0,1\}^{n}\), with \(\op {Gen}\) and \(\op {Sign}\) taking their coins explicitly:
\(\op {Ver}\) deterministic. The coins are arguments rather than an implicit tape because \(\psig \) below draws them through \(\Frand \), and a scheme whose randomness is hidden inside it could not be wired to a randomness functionality at all.
Its three security notions are games in the ordinary property-based sense, each played by an adversary \(\mathcal {B}\) against \(\DS \) alone — no framework, no execution, the notions a cryptographer would write down anyway, unforgeability under chosen-message attack chief among them [10]. One shell, one signing oracle, shared by all three in the same idiom the paper’s own game systems share a shell across several finalizations (Definition 5.1): \(\mathcal {B}\) receives \(\vk \), queries \(\op {Sign}\) as it likes, then halts by calling exactly one of the three procedures below, which decides whether it wins.
Game for a signature scheme \(\DS \): the shell
Finalizations of the game, one per notion; the shell above is shared
\(\op {Cor}(\msg )\) (correctness)
\(\op {Uf}(\msg ,\sigma )\) (unforgeability)
\(\op {Col}(\msg ,\msg ',\sigma )\) (collision resistance)
Write \(\varepsilon _{\op {cor}}(\mathcal {B})\), \(\varepsilon _{\op {uf}}(\mathcal {B})\) and \(\varepsilon _{\op {col}}(\mathcal {B})\) for the probabilities that \(\op {Cor}\), \(\op {Uf}\) and \(\op {Col}\) return \(1\). Perfect correctness is \(\varepsilon _{\op {cor}} = 0\), which most schemes have and none of what follows needs. Unforgeability is strong [1]: line 9 excludes the pair the oracle returned rather than the message alone, matching \(\opl {FinUF}\)’s reading in Section 15.2. Collision resistance is not standard and is not implied by the other two; Section 21.4 is where it earns its place.