Proof of Theorem 2 — if has order 1 or then or
ProvedGOSNIZK.BGNCommit.soundness_order_stepcryptographygroup-theorynumber-theoryp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be a BGN bilinear group with and let . If has order or , that is,
then or .
This is the step of the soundness proof where the hypothesis that generates is used: a degenerate pairing would make the conclusion fail.
Formalization Note "Has order 1 or " is stated as "its -th power is ", which is equivalent since is prime. The exponent is computed in .
Preamble
import Mathlib import Definitions.Def_GOSNIZK_BGNCommit_BGNSetup import Definitions.Def_GOSNIZK_BGNCommit_Scheme
Formal statement
namespace GOSNIZK.BGNCommit
theorem soundness_order_step {G GT : Type*} [CommGroup G] [Fintype G] [CommGroup GT]
[Fintype GT] (S : BGNSetup G GT) (m : ZMod S.n)
(hord : (S.e S.g S.g ^ (m * (m - 1)).val) ^ S.q = 1) :
S.toZp m = 0 ∨ S.toZp m = 1 := 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)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.