Proof of Theorem 6, App. C.3 — the view is determined by the coins and except with probability
ProvedGGHRSW.ColoredMatrix.theorem_6_simulationLet be a prime, an oblivious branching program of length over input bits, a set of input positions, and an adversary in the generic colored matrix model with random coins that makes adaptive queries. For a partial assignment of the bits in , write
- for the restricted function on ;
- for the sequence of replies that , run with coins , receives from the representation oracle initialized with , built from the sample of ;
- for the bound on the number of handles receives.
Then there is an absolute constant , independent of , , and , with the following property. For every , , and there is a simulator , a map that takes a Boolean function on and coins and outputs a reply sequence, such that for every assignment of the bits in
In words: except with probability , everything the adversary learns from the oracle is a deterministic function of its own coins and of the restricted function ; the randomized matrices reveal nothing beyond . Since functionally equivalent assignments satisfy , this is the simulation statement behind Theorem 6 (p. 38). It isolates the collision analysis of the proof in App. C.3 from the final averaging step, and it is the natural target for that analysis.
Formalization Note. The probability is over uniform coins in and a uniform sample of the finite sample space, as in acceptProb. The simulator receives the restricted function as a whole rather than oracle access to it, and its efficiency is not tracked; the statement is information-theoretic, as Theorem 6 is. The constant is quantified first, which is what means. The hypothesis is necessary: for the right-hand side is , while the view is still random (whether is visible to the adversary and has probability about ). Theorem 6 for needs no simulation, because then the database does not depend on .
Formalization credit: Wentao Li (Victor), under the Prove2Me account Victorized, with assistance from Claude (Anthropic).
import Mathlib import Definitions.Def_GGHRSW_ColoredMatrix_Model
namespace GGHRSW.ColoredMatrix
theorem theorem_6_simulation : ∃ C : ℝ, ∀ (p : ℕ) [Fact p.Prime] (bp : BP), 0 < bp.n →
∀ (J : Finset (Fin bp.ℓ)) (A : Adversary p),
∃ Sim : ((Fin bp.ℓ → Bool) → Bool) → Fin A.K → List (Option ℕ),
∀ σ : Fin bp.ℓ → Bool,
((Finset.univ.filter fun x : Fin A.K × Sample p bp =>
view bp J σ A x.1 x.2 ≠ Sim (fun χ => bp.eval (fix J σ χ)) x.1).card : ℝ) /
Fintype.card (Fin A.K × Sample p bp) ≤
C * bp.n * ((dbSize bp J + A.q : ℕ) : ℝ) ^ 2 / p := by sorry
end GGHRSW.ColoredMatrix