Proof of Theorem 2 — perfect soundness of the 0/1 proof on binding keys
ProvedGOSNIZK.BGNCommit.perfect_soundnessbilinear-pairingscryptographyp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1zero-knowledge
Let be a BGN bilinear group with and let , , be a perfectly binding key. If pass verification,
then is a commitment to or to : there are and with .
This is the perfect soundness of the non-interactive proof that a commitment contains or ; it holds for every pair , so against every adversary, however powerful.
Formalization Note The paper's probability-one statement over and an adversary's output is stated for every key in the support of and every ; for unbounded adversaries the two are equivalent.
Preamble
import Mathlib import Definitions.Def_GOSNIZK_BGNCommit_BGNSetup import Definitions.Def_GOSNIZK_BGNCommit_Scheme
Formal statement
namespace GOSNIZK.BGNCommit
theorem perfect_soundness {G GT : Type*} [CommGroup G] [Fintype G] [CommGroup GT] [Fintype GT]
(S : BGNSetup G GT) (h : G) (hkey : S.IsBindingKey h) (c π : G) (hv : S.V01 h c π) :
∃ m r : ZMod S.n, (m = 0 ∨ m = 1) ∧ c = 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 (perfect soundness); p. 7, Perfect soundness
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.