Proof of Theorem 6, §C.3.1, p. 41 — bookend products reduce to (∏α)·s*(∏A)t* and (∏α′)·⟨s*′,t*′⟩
ProvedGGHRSW.ColoredMatrix.bookend_identitycryptographylinear-algebraobfuscationp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be prime and a length- branching program, and fix any sample of . For every choice of bits ,
and
Here the products of matrices are taken in step order and denotes the permutation matrix.
The randomizing matrices cancel, and the zero patterns of and remove every random diagonal entry, so the value of a "bookend" product depends only on the bundling scalars, the permutation matrices and the 5-vectors. This is the starting point of the analysis of mixed-input attacks in the proof of Theorem 6.
Formalization Note. Steps are 0-based in Lean; the identity is stated for every sample, as the page's "corresponds to" is a deterministic identity.
Preamble
import Mathlib import Definitions.Def_GGHRSW_ColoredMatrix_Model
Formal statement
namespace GGHRSW.ColoredMatrix
open Matrix
theorem bookend_identity (p : ℕ) [Fact p.Prime] (bp : BP) (ω : Sample p bp)
(b : Fin bp.n → Bool) :
(sTil ω * (List.ofFn fun i => DTil ω i (b i)).prod * tTil ω) 0 0 =
(∏ i, alpha bp ω.γ i (b i)) *
(ω.sStar ⬝ᵥ
((List.ofFn fun i => (bp.A i (b i)).permMatrix (ZMod p)).prod *ᵥ ω.tStar)) ∧
(s'Til ω * (List.ofFn fun i => D'Til ω i (b i)).prod * t'Til ω) 0 0 =
(∏ i, alpha' bp ω.γ i (b i)) * (ω.s'Star ⬝ᵥ ω.t'Star) := 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), p. 41, proof of Theorem 6, §C.3.1, case LC = 0 and RC = n + 2, second paragraph
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.