F-Rand — Randomness source with erasure

F-Rand (Randomness source with erasure) is part of Idealized Setup and Resources in the UC functionality encyclopedia. Status: an idealized setup assumption or shared resource.

A source of uniform bits shared across the parties it serves, paired with an erasure interface: it hands out \(n\)-bit strings, remembers what it has handed out so a corrupt party’s whole draw history can be read off, and lets a party erase a specific draw so that it can no longer leak. Entries are indexed by an ever-growing counter and never reused, so an erased index stays erased. It places no calls of its own — nothing is delegated to the clock or to the adversary — which makes it the one functionality in its source whose real-world/ideal-world gap can be argued without any absorption machinery at all.

Functionality

Reading the box: the header line fixes the process id, the served parties \(\mathbf{P}\), the admitted callers \(\mathbf{N}\), the used slots \(\mathbf{U}\) (none: the source draws on nothing outside itself) and the parameter \(\mathit{par} := n\), the width of a draw. Inside, \(\square\) marks an entry the table has no value at — either never reached by the counter, or erased.

Functionality \(\mathcal{F}_{\mathsf{Rand}}\)
\(\mathit{pid}\),   \(\mathbf{P}\),   \(\mathbf{N}\),   \(\mathbf{U} := \varnothing\),   \(\mathit{par} := n\)
Initialize():
  1. \(\mathtt{ctr} \gets 0\)
  2. \(\mathtt{L} : \mathbb{N} \to \{0,1\}^{n} \cup \{\square\}\)
  3. \(\mathtt{L}[*] \gets \square\)
id.Rnd()from id′
  1. \(\mathtt{ctr} \gets \mathtt{ctr} + 1\)
  2. \(r \gets_{\$} \{0,1\}^{n}\)// the one sampling in the paper
  3. \(\mathtt{L}[\mathtt{ctr}] \gets r\)
  4. \(\textbf{return}\ (\mathtt{ctr},\, r)\)// the index, so a caller may erase
id.Erase(i)from id′
  1. \(\mathtt{L}[i] \gets \square\)
  2. \(\textbf{return}\) ok
id.Leak()from id′
  1. \(\textbf{return}\ \mathtt{L}\)

The box is transcribed from UC for Gamers (§13.1, p. 136), line numbering and all.

Three things the code does without saying why. Rnd returns the index alongside the value (line 7) because otherwise a caller could never name a draw again, and Erase would have nothing to take. The counter is shared across every party the instance serves, so two parties drawing from the same instance draw distinct entries — that is what makes this a shared source rather than a per-party generator, and what a protocol relies on to keep two draws from colliding. And since \(\mathtt{ctr}\) only ever climbs, an index is never reused: erasure is permanent rather than a freed slot, which is the whole point of having it.

Leak hands back the table entire, so what the adversary sees at a corrupt party is exactly every draw not yet erased — erasure is the only difference between the two.

Known realizations

A perfectly uniform, unbounded randomness source is an idealization; nothing computational realizes it exactly. In practice it stands in for a party’s own local coin tosses, discarded once used — the erasure interface exists so that a protocol drawing coins it must not retain (e.g. signing randomness) can model “these bits are gone” rather than assuming a real machine’s memory is inspectable only up to what it chooses to keep.

Properties

Unpredictability. No environment can name, in advance, a value a later draw will return. Concretely: if an environment places at most \(q_g\) calls that go on record as guesses and at most \(q_r\) calls to Rnd, then for every occupant of the adversary slot, the probability the environment wins the unpredictability game is at most \(q_g \cdot q_r \cdot 2^{-n}\).

This is the one functionality of its kind whose guaranteed bound is not exactly \(0\): unlike (say) a signature functionality’s correctness, unpredictability is a genuinely probabilistic guarantee, bounded by a union bound over guesses against draws, each individually off by a factor \(2^{-n}\). The bound holds against every adversary directly, with no reduction to a canonical (“dummy”) adversary needed, precisely because the functionality places no calls of its own for an adversary to interfere with.

Formal artifacts

No machine-checked formalization yet.

References:

  • UC for Gamers, this site’s own book draft on composable security. Chapter “Randomness” gives the functionality above and its unpredictability bound in full.