One property, \(\opl {FinUnp}\), unpredictability: no environment names in advance a value a later draw returns. It takes the search reading of Definition 5.8. The game is played over \(\gamma := \{\Gm \} \cup \{\Frand \}\) with \(\Frand .\admits := \{\Gm .\PID \}\) pinned and \(\Frand .\Ps \subseteq \Gm .\Ps \), Section 15.2’s tightness argument once more, and for its reason: a draw the game does not see is a draw the verdict cannot rule on.
The shell carries one interface that is not a relay. The operation \(\opl {Guess}\) places no call and touches \(\Frand \) not at all; it exists so that the environment can go on record, and the trace being a sequence is what lets the verdict ask whether it went on record first. That is Section 17.2’s use of order, borrowed for a different purpose: steadiness read the order of answers, unpredictability reads the order of a claim against an answer.
Game shell over \(\Frand \); the finalization follows
\(\PID := (\Gm .F,0,0)\), \(\Ps := \Frand .\Ps \cup \{Z\}\), \(\admits := \Zpid \), \(\uses := \{(\Frand ,\serves _{\Gm })\}\), \(\pars := \none \)
\(\op {Initialize}()\):
\(\id .\opdef {Rnd}()\) from \(\id '\)
\(\id .\opdef {Erase}(i)\) from \(\id '\)
auto
\(\id .\opdef {Guess}(y)\) from \(\id '\)
\(\id .\op {Leak}()\) from \(\id '\)
The finalization of \(\Gm \); the shell over \(\Frand \) is shared
\(\id .\opdef {FinUnp}()\) from \(\id '\) (unpredictability)
Two things about the code. The relays refuse the root and \(\op {Guess}\) does not, and the asymmetry is exactly Section 17.2’s: a relay at the root would address a party \(\Frand \) does not serve, be answered \(\rej \) at line 1, and append \((\atom {rnd},Z,\rej )\) to the trace — whereupon an environment that guessed \(\rej \) would win outright, having predicted nothing. Refused at the relay, nothing is appended, and every \(\atom {rnd}\) entry carries a string \(\Frand \) actually drew. The operation \(\op {Guess}\) places no call, so it has nothing to be refused for and is served everywhere, the root included. And the verdict asks honesty of nobody: at a corrupt party the game’s own wrapper intercepts before the core runs (Remark 5.4), so every entry in \(\V {tr}\) is an honest core’s already, exactly as in Section 17.2.
Proposition 13.1 (\(\Frand \) is unpredictable). Let \(\Zenv \) place at most \(q_{\op {g}}\) calls on \(\op {Guess}\) and at most \(q_{\op {r}}\) on \(\op {Rnd}\). Then for every occupant \(\mathcal {X}\) of the adversary slot,
So \(\{\Frand \}\) has unpredictability within \(q_{\op {g}} q_{\op {r}} 2^{-n}\) against \(\bigl (\ZenvSet ,\Xset \bigr )\) for \(\ZenvSet \) any class meeting those counts and \(\Xset \) the class of all occupants.
Proof. Fix \(k\) with \(e_k = (\atom {rnd},\cdot ,r)\). By tightness no caller but \(\Gm \) reaches \(\Frand \), and \(\Gm \) reaches it only through the shell’s \(\op {Rnd}\) relay (line 5), so \(r\) is the value \(\Frand \)’s own \(\op {Rnd}\) drew at line 5: uniform on \(\{0,1\}^{n}\) and independent of everything the execution did before it, \(\Frand \) placing no call and reading no state to draw it.
Condition on the execution up to the moment before that draw. Every \(\atom {guess}\) entry with \(j < k\) is determined by that history, and there are at most \(q_{\op {g}}\) of them, so the probability that \(r\) equals any of their values is at most \(q_{\op {g}} 2^{-n}\). There are at most \(q_{\op {r}}\) choices of \(k\), and the verdict at line 21 returns \(1\) only if some pair \((j,k)\) matches, so a union bound over \(k\) gives \(q_{\op {g}} q_{\op {r}} 2^{-n}\).
Two details the bound rests on. The occupant of the slot does not appear: \(\Frand \)’s cores place no call, so nothing \(\mathcal {X}\) does reaches the sampling, and the same bound holds against every occupant without an absorption argument. And a guess made after a draw is worthless by construction, the verdict asking \(j < k\); an environment that reads \(r\) and then guesses it has predicted nothing, which is what makes the trace’s order the content of this verdict. □
The bound is the first in this paper that is not \(0\), and it is worth saying what that changes. Corollary 5.11 reads the same either way: a system \(\pi \) put in place of \(\{\Frand \}\) has unpredictability within \(q_{\op {g}} q_{\op {r}} 2^{-n} + \varepsilon \) under the search reading, the ideal bound and the emulation error simply adding. What it changes is that the ideal side is no longer free — a realization inherits a bound that was already nontrivial, and the two terms are of different kinds: one is the sampling’s own, and no protocol does better than it, while the other is what the realization costs. Transfer itself is as cheap as it gets: \(\Frand \)’s cores place no call, responsive or otherwise, so Remark 9.4’s caveat never arises and Theorem 4.29 is untouched, exactly as for \(\Gpki \) (Section 16.2).