\(\psig \) carries \(\Fsig \)’s three interfaces and holds nothing of its own: every coin is drawn through \(\Frand \) and every value that outlives an invocation sits in \(\Fstore \), which is Section 3.2’s leakage-well-formed shape and the first protocol in this paper written to it. That is not decoration. Leakage is gated on the party being corrupt (line 4) but a functionality’s \(\opl {Leak}\) hands over its state entire, so a single \(\Frand \) shared across parties would surrender every party’s coins the moment any one party was corrupted, and with them every signing key — no unforgeability could survive it. The protocol \(\psig \) therefore addresses one instance of each per party, \(\Frand ^{P}\) and \(\Fstore ^{P}\) with \(\Ps = \{P\}\), which Remark 5.5 already allows and the guard’s blindness to the instance number already reaches. And it erases each coin the moment it has been used, which is what \(\Frand \)’s \(\op {Erase}\) was put there for (Section 13.1): what has been erased cannot leak, so a corrupt party surrenders its own signing key and nothing else — not even its own past coins.
Protocol \(\psig \) over \(\{\Frand ^{P},\Fstore ^{P}\}_{P \in \Ps }\)
\(\PID \), \(\Ps \), \(\admits \), \(\uses := \{(\Frand ,\serves ),(\Fstore ,\serves )\}\), \(\pars := \DS \)
\(\id .\op {Gen}()\) from \(\id '\)
\(\id .\op {Verify}(\vk ,\msg ,\sigma )\) from \(\id '\)
auto
\(\id .\op {Sign}(\msg )\) from \(\id '\)
\(\id .\op {Leak}()\) from \(\id '\)
The draws come back as pairs because \(\Frand \)’s \(\op {Rnd}\) answers with the index it wrote beside the string (line 7), which is what lets \(\psig \) name the entry it then erases; \(\op {FinUnp}\) reads the strings and is indifferent to the index travelling beside them.
Three remarks. \(\psig \)’s own \(\opl {Leak}\) returns \(\none \) because it has no state to give: the key is \(\Fstore ^{P}\)’s, and a corrupt party’s adversary reads it there, which is precisely what leakage-well-formedness asks — the leak is where the state is, and nowhere else. The operation \(\op {Verify}\) places no call at all, \(\op {Ver}\) being deterministic, so a verification is local and neither draws nor stores; that is why \(\psig \) is the one protocol here whose \(\op {Verify}\) cannot be distinguished from \(\Fsig \)’s by the token’s movement. And the key is fetched from the store rather than cached in \(\psig \), which is what makes “one key per party” a fact about \(\Fstore \)’s per-slot fixity (Section 14.2, \(\opl {FinKeep}\)) rather than a promise \(\psig \) makes about itself.
Proposition 21.1 (\(\psig \) inherits the two properties). Let \(\gamma := \{\Gm \} \cup \psig \cup \{\Frand ^{P},\Fstore ^{P}\}_{P}\) be a game system in the sense of Definition 5.1, with \(\Gm \) the shell of Section 15.2. For every \(\Zenv \in \ZenvSet _{\gamma ,\gamma }\) placing at most \(q\) calls on the relays and every occupant \(\mathcal {X}\) of the adversary slot there are adversaries \(\mathcal {B}_{\op {cor}}\) and \(\mathcal {B}_{\op {uf}}\) against \(\DS \), each running \(\Zenv \) and \(\mathcal {X}\) once with \(O(q)\) overhead, such that
Proof. One preliminary paragraph and two reductions. The preliminary collects what the subroutines already give: tightness makes every trace entry an answer \(\psig \)’s own core gave at an honest party, Proposition 14.1 makes the store fixed and faithful so one key is issued per party for good, and Proposition 13.1 makes the coins uniform and, being erased, unreadable. Each property then reduces to the scheme’s own game by the same move: assume the verdict fires, identify the triple it names as a failure of \(\DS \) outright, and have the reduction guess in advance which of the at most \(q\) calls is the failing one — which is where the factor \(q\) comes from, in both bounds. By tightness no caller but \(\Gm \) reaches \(\psig \), so every \(\atom {gen}\), \(\atom {sign}\) and \(\atom {ver}\) entry of \(\V {tr}\) is an answer \(\psig \)’s own core gave at an honest party — at a corrupt one the game’s wrapper intercepts and records nothing (Remark 5.4). By Proposition 14.1 the store is fixed and faithful: the \(\vk \) and \(\V {sk}\) a party puts are what it later gets, and \(\op {Gen}\)’s guard on line 1 therefore issues one key per party for good. By Proposition 13.1 the coins are uniform and, being erased at line 6 and its counterpart in \(\op {Sign}\), are read by nobody: \(\Frand ^{P}\)’s leak is empty of them and \(\Frand ^{P}\) serves \(P\) alone, so no corruption of another party reaches them.
For correctness, suppose line 20 fires: honest \(P\), \(Q\), a \((\atom {gen},P,\vk )\), a \((\atom {sign},P,\msg ,\sigma )\) with \(\sigma \in \Sigs \), and a \((\atom {ver},Q,\vk ,\msg ,\sigma ,0)\). The verification is \(\DS .\op {Ver}(\vk ,\msg ,\sigma )\) by line 10, and the signature is \(\DS .\op {Sign}(\V {sk},\msg ;r)\) under the \(\V {sk}\) paired with that very \(\vk \) by line 5, on coins uniform by the paragraph above. So the triple is a correctness failure of \(\DS \) outright. The adversary \(\mathcal {B}_{\op {cor}}\) runs the execution, guesses in advance which of the at most \(q\) signing calls is the failing one, and outputs its message; it wins whenever the game does and the guess is right, which is the factor \(q\).
For unforgeability, suppose line 28 fires: honest \(P\), \(Q\), \((\atom {gen},P,\vk )\), \((\atom {ver},Q,\vk ,\msg ,\sigma ,1)\) and no \((\atom {sign},P,\msg ,\sigma )\). Two cases. Either \(\vk \) is the key \(\op {Gen}\) issued to \(P\), and then \(\op {Ver}(\vk ,\msg ,\sigma ) = 1\) with \((\msg ,\sigma )\) returned by no \(\op {Sign}\) at \(P\) — a strong forgery, which \(\mathcal {B}_{\op {uf}}\) harvests by planting its challenge key at a guessed one of the at most \(q\) generating parties and answering that party’s signing calls from its oracle, every other party it runs itself; or \(\vk \) is another honest party’s key that happens to equal \(P\)’s, and then two independent \(\op {Gen}(r)\) draws on uniform \(n\)-bit coins collided, which over at most \(q\) generations is at most \(q^{2}2^{-n}\). Note where the erasure is spent: without it, corrupting any party would hand \(\mathcal {X}\) the coins of \(P\)’s own \(\op {Gen}\) and \(\op {Sign}\), and \(\mathcal {B}_{\op {uf}}\) could not answer with an oracle it does not have the coins for. □
This is the first bound in the paper that is neither \(0\) nor information-theoretic, and it is worth saying what has changed. The functionality \(\Fsig \) has its properties because it was written to (Proposition 15.1); \(\psig \) has them because \(\DS \) does, and the two \(q\)-factors are the ordinary price of a guessing reduction. Corollary 5.11 is what makes the exchange legitimate in the other direction — a property of \(\Fsig \) descends to any realization of it — and this proposition is the same statement approached from the realization’s side, proved directly because \(\psig \) is not obtained from \(\Fsig \) by emulation but built from a scheme.