13.1 Functionality

\(\Frand \) is the smallest functionality in this paper and the right one to read first. It hands out uniform \(n\)-bit strings, remembers what it handed out, lets a party forget an entry, and leaks what it still remembers. Chapter 1 named it and owed no code; here is the code.

Two things make it worth its own chapter rather than a footnote. It places no call at all — not on the clock, not on the adversary — so it is the one example where nothing at all is left to the slot, and Chapter 9 has nothing to price. And its property, unlike every other in this paper, is not attained at \(0\): randomness is unpredictable up to a probability the bound has to name, which is where the \(\varepsilon \) of Definition 5.8 stops being decorative.

The fields.  \(\Fsig \)’s pattern. \(\PID \), \(\Ps \) and \(\admits \) are parameters, one instance per session, \(\admits \) naming the protocol served in the local pattern of Chapter 1. \(\uses := \emptyset \), there being no call to make. \(\pars := n\), the width of the strings, which \(\opl {Rnd}\) reads at line 5.

Erasure is what the leak is for.  \(\op {Leak}\) returns \(\V {L}\) entire, so a corrupt party’s whole history of draws is the adversary’s. That is not a defect but the point of having \(\opl {Erase}\) beside it: a protocol that draws randomness it must not retain erases the entry, and what has been erased cannot leak. Read that way \(\Frand \) is a model of secure erasure as much as of sampling, and the pair is why the store of Chapter 14 is shaped the same way. One consequence is worth stating plainly, since it is easy to state wrongly: while nothing is erased, the number of entries in \(\V {L}\) is the number of times \(\op {Rnd}\) was called, so the leak reports the count as well as the values; erasing is exactly what takes an entry out of that count.

Three remarks on the code. The operation \(\op {Rnd}\) answers with the index it wrote as well as the string. A caller that means to erase a draw must be able to name it, and \(\V {ctr}\) is the functionality’s state and not the caller’s, so without line 7 the \(\op {Erase}\) beside it could only be used by a caller willing to guess — the protocol of Section 21.2 erases every coin it draws, and this is what lets it. Entries are indexed by a counter and never rewritten, so \(\op {Erase}\) needs no companion to \(\Fstore \)’s distinction between never-written and erased: an index \(\op {Rnd}\) has passed is never reused, and \(\unset \) at an index below \(\V {ctr}\) says the entry was erased while \(\unset \) above it says the counter has not reached there. And the counter is shared across parties, as any functionality’s state is: two parties drawing from one instance draw distinct entries, which is what makes \(\Frand \) a source rather than a per-party generator.