Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Proof of Theorem 6, §C.3.1, pp. 41–43 — formal expressions that are not identically equal collide with probability O((n+1)/p)O((n+1)/p)O((n+1)/p)

Proved
GGHRSW.ColoredMatrix.theorem_6_collision_bound

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

cryptographygeneric-modelobfuscationsimulation

Let ppp be a prime, BPBPBP a branching program of length nnn over ℓ\ellℓ input bits, and (J,σ)(J,\sigma)(J,σ) a partial assignment. Let e,e′e,e'e,e′ be two formal query expressions over the handles of DB(p,BP,(J,σ))DB(p,BP,(J,\sigma))DB(p,BP,(J,σ)) that have the same shape (same dimensions and colours) and are not identically equal, i.e. their values differ for at least one sample of RNDp(BP)\mathcal{RND}_p(BP)RNDp​(BP). Then

Pr⁡ω←RNDp(BP)[e(ω)=e′(ω)]  ≤  C (n+1)p,\Pr_{\omega\leftarrow\mathcal{RND}_p(BP)}\big[e(\omega)=e'(\omega)\big]\;\le\;\frac{C\,(n+1)}{p},ω←RNDp​(BP)Pr​[e(ω)=e′(ω)]≤pC(n+1)​,

where CCC is an absolute constant, independent of ppp, BPBPBP, (J,σ)(J,\sigma)(J,σ), eee and e′e'e′.

This is the per-query estimate of the proof of Theorem 6 (§C.3.1). In every colour case, partial evaluations with LC=i>0LC=i>0LC=i>0 or RC=j<n+2RC=j<n+2RC=j<n+2 as well as full evaluations from colour 000 to colour n+2n+2n+2, a new matrix coincides with an earlier one only with probability O(n/p)O(n/p)O(n/p), unless the two expressions agree for every sample. Summed over the at most T2T^2T2 pairs of handles of an execution, this gives the O(nT2/p)O(nT^2/p)O(nT2/p) of Theorem 6.

Formalization Note. Expressions, shapes, values and identical equality are those of Definitions.Def_GGHRSW_ColoredMatrix_Simulator. The probability is over the uniform sample of the finite sample space. The bound is written with n+1n+1n+1 so that it also covers programs with no steps, where only the bookend vectors are available. The constant is quantified first.

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

Preamble
import Mathlib
import Definitions.Def_GGHRSW_ColoredMatrix_Model
import Definitions.Def_GGHRSW_ColoredMatrix_Simulator
Formal statement
namespace GGHRSW.ColoredMatrix

open Classical in
theorem theorem_6_collision_bound : ∃ C : ℝ, ∀ (p : ℕ) [Fact p.Prime] (bp : BP)
    (J : Finset (Fin bp.ℓ)) (σ : Fin bp.ℓ → Bool) (e e' : QExpr p) (s : Shape),
    e.shape bp J = some s → e'.shape bp J = some s → ¬ IdenticallyEqual bp J σ e e' →
      ((Finset.univ.filter fun ω : Sample p bp =>
          e.eval (initDB bp J σ ω) = e'.eval (initDB bp J σ ω)).card : ℝ) /
        Fintype.card (Sample p bp) ≤ C * (bp.n + 1) / 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.1, proof of Theorem 6, pp. 41–43 (the per-query collision bounds)

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