README.md

Distance and distinguishers

This folder holds the transcript distance of random systems and the ways to bound it: probabilistic distinguishers and their behaviors, with the transcript distance as the largest advantage; absorption of converters and systems into distinguishers; couplings; restriction to a smaller domain; the H-coefficient bound; and the identical-until-bad bound. The systems, PDSs and converters it uses are those of RandomSystems. Citations refer to the numbered references of THEORY.md.

Distance and distinguishers

The transcript distance takes the supremum over environments $E$ compatible with the domain and bounded to $n$ queries; a probabilistic distinguisher $P$ [1, Definition 9] has an advantage:

$$\Delta(R, S) = \sup_{E,\, n}\ \delta\big(\mathrm{tr}(R, E, n),\ \mathrm{tr}(S, E, n)\big), \qquad \mathrm{Adv}_P(R, S) = \big\lvert \Pr[P(R) = 1] - \Pr[P(S) = 1] \big\rvert .$$

A probabilistic distinguisher is a distribution over deterministic distinguishers compatible with the domain, and its probability of outputting 1 averages their decision probabilities. For each $P$, $\mathrm{Adv}_P$ is a pseudo-distance: it is zero on equal systems, symmetric, and satisfies the triangle inequality. The transcript distance is the largest advantage, $\Delta(R, S) = \sup_P \mathrm{Adv}_P(R, S)$, so every advantage is at most the distance.

The behavior of a probabilistic distinguisher is its probability of outputting 1 on each system, as the behavior of a PDC is its random system; the transcript distance is also the largest advantage of a behavior. A behavior has an advantage, which is zero on equal systems, symmetric, satisfies the triangle inequality, and is at most the distance.

Couplings

The transcript $\mathrm{tr}(s, E, n)$ of a deterministic system $s$ with an environment $E$ within $n$ rounds is the sequence of their query–reply pairs [1, Definition 7]. For an environment compatible with the random system $R$ of a PDS $P$, the transcript law of $R$ is the transformation of $P$ by $\mathrm{tr}(\cdot, E, n)$ [1, Definition 4 and footnote 9]. A coupling $J$ of $P$ and a PDS $Q$ with random system $S$ therefore bounds the distance of the transcript laws by the probability that the transcripts differ, and the transcript distance by the probability that the systems differ:

$$\delta\big(\mathrm{tr}(R, E, n),\ \mathrm{tr}(S, E, n)\big) \le \Pr_{(s, t) \sim J}\big[\mathrm{tr}(s, E, n) \ne \mathrm{tr}(t, E, n)\big], \qquad \Delta(R, S) \le \Pr_{(s, t) \sim J}[s \ne t] .$$

The second bound holds for every coupling; [1, Theorem 2] states in addition that some presentations of $R$ and $S$ have a coupling attaining it.

Absorption

Absorbing a PDC $\alpha$ into a behavior $d$ gives $d \circ \alpha$, which decides on a system as $d$ decides on $\alpha$ attached to it, $\Pr[(d \circ \alpha)(R) = 1] = \Pr[d(\alpha R) = 1]$. Absorbing a serial composition absorbs its PDCs in turn, $d \circ (\beta \circ \alpha) = (d \circ \beta) \circ \alpha$. On deterministic distinguishers absorption connects the distinguisher to the converter's outside; absorbing a converter into a probabilistic distinguisher gives a probabilistic distinguisher, so $d \circ \alpha$ is a behavior, and so does absorbing a system run beside.

Restriction

The restriction $R \restriction D'$ of a random system on $D$ to a smaller domain $D' \subseteq D$ keeps the masses of the transcripts $D'$ admits and is zero elsewhere. Restrictions compose, and an environment compatible with $D'$ sees the transcript law of the system itself, so restriction does not increase the distance, $\Delta(R \restriction D', S \restriction D') \le \Delta(R, S)$.

The H-coefficient bound

Under an environment $E$, the transcript law of $R$ gives each transcript $h$ that $E$ produces the probability $R(h)$, and the others zero; the restriction is the same for $S$, so a ratio of the two systems' probabilities on the good transcripts is a ratio of their transcript laws. For $R$ and $S$ replying at the queried label, the H-coefficient technique then bounds the distance by the error $\varepsilon_1$ of the ratio and the bound $\varepsilon_2$ on the bad transcripts under $S$:

$$(1 - \varepsilon_1)\, S(h) \le R(h) \ \text{ for } h \notin \mathrm{Bad}, \quad \Pr_{\mathrm{tr}(S, E, n)}[\mathrm{Bad}] \le \varepsilon_2 \ \text{ for all } E, n \quad \Longrightarrow \quad \Delta(R, S) \le \varepsilon_1 + \varepsilon_2 .$$

Identical until bad

Two random systems $R_1$ and $R_2$ have transcript probabilities that both lie above a common part $g$ with $g([]) = 1$. A step from a possible transcript $h$ by an admitted query $x$ loses $g(h) - \sum_y g(h, x, y)$ of the common part. If each step loses at most $\beta(h, x)\, R_1(h)$, and the cost of each possible transcript, the sum of $\beta$ over its steps, is at most $\varepsilon$, then by the union bound over the steps every compatible environment stays in the common part with probability at least $1 - \varepsilon$, and the two systems are within $\varepsilon$ of each other:

$$g(h) - \sum_y g(h, x, y) \le \beta(h, x)\, R_1(h), \qquad \sum_{k < |h|} \beta(h_1 \cdots h_k,\ x_{k+1}) \le \varepsilon \quad \Longrightarrow \quad \Delta(R_1, R_2) \le \varepsilon .$$

Games build on this bound: see Game.