nucleation

CLAIM-302: Equivalence under feasible tests can be much coarser than statistical equivalence: there are ensembles almost disjoint from uniform that no polynomial-size test tells apart from it, and efficiently samplable ensembles of this kind exist if pseudorandom generators do

3 min read

Properties8
StatusActive
Rolethesis
Warrantdemonstrated
Tagsmathematics, information-theory, epistemology
Lineformal-apparatus
GroundsCASE-083 — A pseudorandom generator's output against uniform strings: almost disjoint in total variation, indistinguishable to every efficient test if the generator is secure, THEORY-357 — Computational indistinguishability is strictly coarser than statistical closeness: without any assumption there are ensembles on at most 2^(n/2) strings that no circuit of size 2^(n/8) tells from uniform, though none of them is efficiently samplable, and an efficiently samplable pair of this kind exists if a pseudorandom generator does, since its output covers at most 2^n of the 2^l(n) strings; all of it is about ensembles indexed by n, not single pairs of distributions, THEORY-352 — A pseudorandom generator exists if and only if a one-way function exists, where both are secure against uniform adversaries and every reduction is an oracle Turing machine, as statements about ensembles indexed by n; the construction from an arbitrary one-way function is only weak-preserving, so security at one length is bought at a much greater one
SupportsCLAIM-304 — A rendering can keep a distinction recoverable in principle and make it infeasible to recover: if pseudorandom generators exist, a uniformly random bit can be encoded so that an unbounded receiver recovers it except with probability at most 2⁻⁽ⁿ⁺¹⁾, while no efficient receiver does non-negligibly better than chance
ComplementsCLAIM-264 — Two objects can agree on every probe in a restricted family without being isomorphic, so equivalence under a probe family is coarser than identity unless the family is rich enough

Graph View

The claim

A15 §1: for observation channels K_x, K_x′ and a test family F_r, let d_r(x, x′) = sup over f in F_r of |E[f | x] − E[f | x′]|. Over all tests this is total variation. Restricting the family cannot increase it, and nested families give a distance that grows with r. “The conclusion is not that the states became different. It’s that a new distinction became operationally observable.”

“Efficient” and “negligible” mean something only for ensembles, sequences of distributions indexed by n (Goldreich, Definition 3.2 in the 1995 draft). For any fixed n a large enough finite test separates any two different distributions. The claim is about ensembles.

Unconditionally. Goldreich’s Proposition 3.3, credited to Goldreich and Krawczyk after Yao, proves by a Chernoff and union bound that some ensemble X with X_n supported on at most 2^(n/2) strings fools every circuit of size 2^(n/8) with gap below 2^(−n/8). Its total variation from uniform is at least 1 − 2^(−n/2). The book: the separating test “is (necessarily) impossible to compute in polynomial-time.” That X cannot be sampled efficiently: “One of the two ensembles is not constructible in polynomial-time.”

Efficiently samplable, if pseudorandom generators exist. The witness A15 gave (CASE-083). Let G: {0,1}ⁿ → {0,1}²ⁿ be a secure pseudorandom generator (Goldreich’s Definition 3.9 with l(n) = 2n), P_n = G(Uₙ), Q_n = U₂ₙ. G has at most 2ⁿ outputs, so TV(P_n, Q_n) ≥ 1 − 2⁻ⁿ, checked here (the book states the bound only as ½, and its “statistical difference” omits the factor ½ of total variation). Every probabilistic polynomial-time test has negligible advantage, by definition. The book cites Goldreich (1990) for the sharper fact, not read here, that an efficiently samplable pair of this kind exists if and only if one-way functions do. That note (LIT-1053) could not be fetched. Håstad, Impagliazzo, Levin and Luby (LIT-1051, read in NOTE-880) settle the attribution: they credit Goldreich’s note with the equivalence to pseudorandom generators, and prove that pseudorandom generators exist if and only if one-way functions do (their Theorem 6.2.2, with uniform reductions). The book’s “one-way functions” combines the two. This claim’s condition “if pseudorandom generators exist” can be read “if one-way functions exist”.

Postprocessing. A15 added the invariance that keeps this from being arbitrary: an efficient transformation applied to both ensembles preserves indistinguishability, since a distinguisher for the outputs composed with the transformation would distinguish the inputs. Goldreich sets this as an exercise (§3.8.4, Exercise 1), and the one-line composition is its proof.

Why it is Active

The unconditional half is a theorem of the source, read in the author’s 1995 draft (LIT-1061); the samplable half is the definition of a secure generator plus a counting bound checked here, and is conditional, as the title says. Neither was checked against the printed 2001 volume.

What it does not say

  • Not that a distinction no efficient test sees is unreal. A15: “The distributions are not identical.”
  • Not that it depends on the objects alone. It is relative to the computational model, the encoding and any auxiliary information; an expensively computed label makes the same ensembles trivially distinguishable (A15 §3). Goldreich’s §3.8.4 Exercise 11 asks the same of a permutation that is not efficiently computable.
  • Not quantum contextuality, ontological identity or pragmatic equivalence. A14: “Each stronger interpretation requires its own arguments and tests.”

Backlinks