Proof of Theorem 2 — the BGN commitment is homomorphic on either type of key
ProvedGOSNIZK.BGNCommit.com_homomorphiccommitment-schemescryptographyp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be a BGN bilinear group with , and let be a perfectly binding key (, ) or a perfectly hiding key (, ). Then for all messages and randomizers ,
This is the homomorphic property of a homomorphic proof commitment, the property that lets the Circuit-SAT proofs of the paper combine commitments to wire values.
Formalization Note Messages are taken in (see the definition of the scheme).
Preamble
import Mathlib import Definitions.Def_GOSNIZK_BGNCommit_BGNSetup import Definitions.Def_GOSNIZK_BGNCommit_Scheme
Formal statement
namespace GOSNIZK.BGNCommit
theorem com_homomorphic {G GT : Type*} [CommGroup G] [Fintype G] [CommGroup GT] [Fintype GT]
(S : BGNSetup G GT) (h : G) (hkey : S.IsBindingKey h ∨ ∃ x, S.IsHidingKey h x)
(m₁ r₁ m₂ r₂ : ZMod S.n) :
S.com h (m₁ + m₂) (r₁ + r₂) = S.com h m₁ r₁ * S.com h m₂ r₂ := by sorry
end GOSNIZK.BGNCommit
Source
Groth, Ostrovsky, Sahai, New Techniques for Noninteractive Zero-Knowledge, J. ACM 59(3) (2012), authors' version of March 7, 2011, p. 9, proof of Theorem 2
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.