Theorem 6, p. 38 — equivalent partial assignments give O(nT²/p)-close views in the generic colored matrix model
ProvedGGHRSW.ColoredMatrix.theorem_6Let be a prime, a length- branching program over input bits, and , two partial input assignments on the same set of positions that are functionally equivalent: . Let be an adversary in the generic colored matrix model that makes adaptive queries to the representation oracle initialized with , respectively , built from a fresh sample of . Let bound the number of handles it receives. Then there is an absolute constant , independent of , , the assignments and , such that
Equivalently, the statistical distance between the views and is .
This is the paper's unconditional evidence for its Equivalent Program Indistinguishability assumption (Assumption 1): no attack that only adds, scales and multiplies the garbled matrices in an order respecting their colours can tell two functionally equivalent input fixings apart, except with probability .
Formalization Note. The constant is quantified before everything else, which is what means here; no value is fixed. The statistical distance is expressed as the largest acceptance gap: the adversary includes its final decision, so quantifying over every adversary covers every distinguisher of the views (coins included). The page's counts all handles sent, initial ones included; a -query adversary receives at most handles, the value used. The bundling scalars follow the -procedure of p. 42, and the output convention is "identity means 1"; see the definitions file. The sentence before the theorem says ; the theorem's is used.
import Mathlib import Definitions.Def_GGHRSW_ColoredMatrix_Model
namespace GGHRSW.ColoredMatrix
theorem theorem_6 : ∃ C : ℝ, ∀ (p : ℕ) [Fact p.Prime] (bp : BP) (J : Finset (Fin bp.ℓ))
(σ σ' : Fin bp.ℓ → Bool), FunctionallyEquivalent bp J σ σ' →
∀ A : Adversary p,
|acceptProb p bp J σ A - acceptProb p bp J σ' A| ≤
C * bp.n * ((dbSize bp J + A.q : ℕ) : ℝ) ^ 2 / p := by sorry
end GGHRSW.ColoredMatrix
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.