Proof of Theorem 6, App. C.3 — for , functionally equivalent assignments have the same identically-equal expressions
ProvedGGHRSW.ColoredMatrix.theorem_6_identity_invarianceLet be a prime, a branching program of length over input bits, and let and be functionally equivalent partial assignments, . There is an absolute constant such that, whenever , for any two formal query expressions of the same shape,
where means that the values of and for the database agree for every sample of .
In words: which pairs of formal expressions are identically equal depends on the assignment only through the restricted function . This is the statement that the simulator in the proof of Theorem 6 can answer every equality query of the adversary with access to alone, so that its output is the same for functionally equivalent assignments.
Formalization Note. Expressions, shapes and identical equality are those of Definitions.Def_GGHRSW_ColoredMatrix_Simulator; an expression refers to handles, so the same expression denotes the matrices of in one database and of in the other. The hypothesis excludes small fields, where a nonzero polynomial expression in the random entries may vanish as a function on ; for those the bound of Theorem 6 exceeds and nothing needs to be simulated.
Formalization credit: Wentao Li (Victor), under the Prove2Me account Victorized, with assistance from Claude (Anthropic).
import Mathlib import Definitions.Def_GGHRSW_ColoredMatrix_Model import Definitions.Def_GGHRSW_ColoredMatrix_Simulator
namespace GGHRSW.ColoredMatrix
theorem theorem_6_identity_invariance : ∃ C : ℕ, ∀ (p : ℕ) [Fact p.Prime] (bp : BP)
(J : Finset (Fin bp.ℓ)) (σ σ' : Fin bp.ℓ → Bool), FunctionallyEquivalent bp J σ σ' →
C * (bp.n + 1) < p → ∀ (e e' : QExpr p) (s : Shape),
e.shape bp J = some s → e'.shape bp J = some s →
(IdenticallyEqual bp J σ e e' ↔ IdenticallyEqual bp J σ' e e') := by sorry
end GGHRSW.ColoredMatrix