Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Proof of Theorem 6, App. C.3 — the view is determined by the coins and F∣σF|_\sigmaF∣σ​ except with probability O(nT2/p)O(nT^2/p)O(nT2/p)

Proved
GGHRSW.ColoredMatrix.theorem_6_simulation

by Victorized · Nov 3, 2026 · Mathlib 0df444a (Lean v4.33.1)

cryptographygeneric-modelobfuscationsimulationstatistical-distance

Let ppp be a prime, BPBPBP an oblivious branching program of length n≥1n\ge 1n≥1 over ℓ\ellℓ input bits, J⊆[ℓ]J\subseteq[\ell]J⊆[ℓ] a set of input positions, and A\mathcal AA an adversary in the generic colored matrix model with random coins ccc that makes qqq adaptive queries. For a partial assignment σ\sigmaσ of the bits in JJJ, write

  1. F∣σF|_\sigmaF∣σ​ for the restricted function x↦BP(x with the bits in J set by σ)x\mapsto BP(x \text{ with the bits in } J \text{ set by } \sigma)x↦BP(x with the bits in J set by σ) on {0,1}ℓ\{0,1\}^\ell{0,1}ℓ;
  2. viewA(c,ω;σ)\mathsf{view}_{\mathcal A}(c,\omega;\sigma)viewA​(c,ω;σ) for the sequence of replies that A\mathcal AA, run with coins ccc, receives from the representation oracle initialized with DB(p,BP,(J,σ))DB(p,BP,(J,\sigma))DB(p,BP,(J,σ)), built from the sample ω\omegaω of RNDp(BP)\mathcal{RND}_p(BP)RNDp​(BP);
  3. T=∣DB∣+qT=|DB|+qT=∣DB∣+q for the bound on the number of handles A\mathcal AA receives.

Then there is an absolute constant CCC, independent of ppp, BPBPBP, JJJ and A\mathcal AA, with the following property. For every ppp, BPBPBP, JJJ and A\mathcal AA there is a simulator S\mathcal SS, a map that takes a Boolean function fff on {0,1}ℓ\{0,1\}^\ell{0,1}ℓ and coins ccc and outputs a reply sequence, such that for every assignment σ\sigmaσ of the bits in JJJ

Pr⁡c, ω[viewA(c,ω;σ)≠S(F∣σ, c)]  ≤  C n T2p.\Pr_{c,\,\omega}\Big[\mathsf{view}_{\mathcal A}(c,\omega;\sigma)\neq \mathcal S\big(F|_\sigma,\,c\big)\Big]\;\le\;\frac{C\,n\,T^2}{p}.c,ωPr​[viewA​(c,ω;σ)=S(F∣σ​,c)]≤pCnT2​.

In words: except with probability O(nT2/p)O(nT^2/p)O(nT2/p), everything the adversary learns from the oracle is a deterministic function of its own coins and of the restricted function F∣σF|_\sigmaF∣σ​; the randomized matrices reveal nothing beyond F∣σF|_\sigmaF∣σ​. Since functionally equivalent assignments satisfy F∣σ=F∣σ′F|_\sigma=F|_{\sigma'}F∣σ​=F∣σ′​, 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 Fin K\mathrm{Fin}\,KFinK 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 O(⋅)O(\cdot)O(⋅) means. The hypothesis n≥1n\ge 1n≥1 is necessary: for n=0n=0n=0 the right-hand side is 000, while the view is still random (whether ⟨s∗,t∗⟩=0\langle\mathbf s^*,\mathbf t^*\rangle=0⟨s∗,t∗⟩=0 is visible to the adversary and has probability about 1/p1/p1/p). Theorem 6 for n=0n=0n=0 needs no simulation, because then the database does not depend on σ\sigmaσ.

Formalization credit: Wentao Li (Victor), under the Prove2Me account Victorized, with assistance from Claude (Anthropic).

Preamble
import Mathlib
import Definitions.Def_GGHRSW_ColoredMatrix_Model
Formal statement
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
Source
Garg, Gentry, Halevi, Raykova, Sahai and Waters, Candidate Indistinguishability Obfuscation and Functional Encryption for All Circuits, SIAM J. Comput. 45(3), 2016 (authors' version of July 21, 2013), App. C.3, proof of Theorem 6, pp. 38–43 (simulation step behind Theorem 6, p. 38)

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me