Proof of Theorem 2 — perfect binding when has order
ProvedGOSNIZK.BGNCommit.perfect_bindingcommitment-schemescryptographyp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be a BGN bilinear group with and let with be a perfectly binding key. If two openings give the same commitment,
then .
Since the message space of the scheme is , this says that a commitment under a binding key determines its message: no two openings carry different messages.
Formalization Note Messages are represented in and compared after reduction modulo ; this is the paper's statement for the message space .
Preamble
import Mathlib import Definitions.Def_GOSNIZK_BGNCommit_BGNSetup import Definitions.Def_GOSNIZK_BGNCommit_Scheme
Formal statement
namespace GOSNIZK.BGNCommit
theorem perfect_binding {G GT : Type*} [CommGroup G] [Fintype G] [CommGroup GT] [Fintype GT]
(S : BGNSetup G GT) (h : G) (hkey : S.IsBindingKey h)
(m₁ r₁ m₂ r₂ : ZMod S.n) (hc : S.com h m₁ r₁ = S.com h m₂ r₂) :
S.toZp m₁ = S.toZp m₂ := 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; p. 7, Perfect binding
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.