Skip to content

README.md

Latest commit

 

History

History
241 lines (201 loc) · 13.2 KB

README.md

File metadata and controls

241 lines (201 loc) · 13.2 KB
Raw

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 at the end; [1] is that of THEORY.md.

Distance and distinguishers

The transcript distance takes the supremum over environments $E$ compatible with the domain and bounded to $n$ queries. For systems replying at the queried interface, the observation horizon and global query bound can both be fixed to $b = \mathcal D.\mathrm{bound}$ (RandomSystem.transcriptDistance_eq_iSup_domainBound in Decision):

$$\Delta(R,S) = \sup_{\substack{E\text{ compatible with }\mathcal D\\ E\text{ bounded by }b}} \delta\bigl(\mathrm{tr}(R,E,b),\mathrm{tr}(S,E,b)\bigr).$$

For compatible $E$ bounded by $n$ and $E' = E{\restriction}b$ (DDE.limitQueries in DDE), each term of the supremum is a term at $b$, by exact equalities:

$$\mathrm{tr}(R,E,n) \overset{(1)}{=} \mathrm{tr}(R,E,b) \overset{(2)}{=} \mathrm{tr}(R,E',b).$$

(1) RandomSystem.sLaw_eq_domainBound: compatibility admits possible queries only below $b$. (2) RandomSystem.sLaw_limitQueries: $E'$ asks $E$'s queries before $b$ replies and stops at $b$ on every reply history, including impossible ones; it remains compatible. The global stopping condition stays explicit, and the formula has the shape of [1, Definition 11, printed p. 15]: "the supremum is over all compatible (Y, X)-DDE."

A probabilistic distinguisher $P$ [1, Definition 9] has advantage

$$\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.

Initially sampled systems

Choose a component with law $P$ and retain it throughout the interaction. For a fixed compatible distinguisher $D$, the decision probability is an average:

$$\Pr[D(\operatorname{sample}(P, R)) = 1] = \sum_k P(k)\,\Pr[D(R_k) = 1].$$

RandomSystem.decisionProbability_mix proves this for a deterministic distinguisher by taking the decision event's mass in the transcript mixture. Domain.Distinguisher.probability_mix then averages over the distinguisher's independent random choice.

For two families on the same interface, the typed transcriptDistance_sample_le derives $\Delta(\operatorname{sample}(P, R), \operatorname{sample}(P, S)) \le \varepsilon$ from $\Delta(R_k, S_k) \le \varepsilon$ for every $k$. For each distinguisher, the averaging lemma abs_average_sub_le in Transcript preserves the bound on its component advantages, using nonnegative weights summing to one. The law may be nonuniform, but it must be the same in both mixtures. Sampling itself does not reveal the component index.

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 [2, Corollary 2.2.2] 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 .$$

More generally, observation laws may use any alphabet $W$ and a common projection $\pi : W \to H$ to public histories. If $\pi_*\mu_R^{E,n}=R.\mathrm{sLaw}(E,n)$ and $\pi_*\mu_S^{E,n}=S.\mathrm{sLaw}(E,n)$, then RandomSystem.transcriptDistance_le_iSup_observation gives

$$\Delta(R,S) \le \sup_{E,n}\delta(\mu_R^{E,n},\mu_S^{E,n}).$$

The supremum ranges over compatible environments stopping within $n$ queries, and the normalized laws need only exist for those experiments; $W$ is an arbitrary type. With a nonnegative loss $\varepsilon$, possibly exceeding one, RandomSystem.transcriptDistance_le_of_observation_ratio derives $\Delta(R,S)\le b$ from $(1-\varepsilon(w))\mu_S^{E,n}(w)\le\mu_R^{E,n}(w)$ at every $w$ and a uniform ideal expected loss $\mathbb E_{\mu_S^{E,n}}[\varepsilon]\le b$, by the expectation method [2, Lemma 2.2.1]. Conditional completions instantiate this theorem with pairs $(h,z)$ and $\pi(h,z)=h$; the real and ideal record kernels may differ.

For sampled presentations with records and multiple transcript classes, use RandomSystem.HCoefficient. Supply the real mixture, its deterministic reveal, the ideal conditional reveal law, the finite classification, the pointwise ratio, and the expected class-error bound. Its transcriptDistance_le_nnreal theorem gives the same distance; the instance-layer Interface.distance_le_of_hCoefficient gives the CC distance. ofGoodBad assigns error one to the bad class and the ratio error to the good class.

The reveal laws have the original transcript laws as marginals. kernelLaw_mass_eq_expect turns a revealed bad-event mass into the expectation of its conditional probability. The reveal and the partition remain explicit; no security choice is made by automation.

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.

References

  1. D. Lanzenberger and U. Maurer. Coupling of Random Systems. In Theory of Cryptography (TCC 2020), Springer, 2020. Cryptology ePrint Archive, Paper 2020/1187.
  2. A. Jha. Provable Security of Symmetric-key Cryptographic Schemes. Doctoral thesis, Indian Statistical Institute, 2020. https://digitalcommons.isical.ac.in/doctoral-theses/456/.