Figure 1 — extraction: and recovers on a binding key
ProvedGOSNIZK.BGNCommit.extractioncommitment-schemescryptographyp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be a BGN bilinear group with and let , , be a perfectly binding key. For every message and randomizer , the commitment satisfies
and the extractor of Figure 1 (exhaustive search for the exponent of in base ) returns .
This is the extraction step behind the perfect extractability of the scheme: knowing suffices to read the message (up to its residue modulo ) out of a commitment.
Formalization Note The extractor returns the least with , read in . The statement holds for every message, not only for ; the perfect extractability conjunct of Theorem 2 is its restriction to .
Preamble
import Mathlib import Definitions.Def_GOSNIZK_BGNCommit_BGNSetup import Definitions.Def_GOSNIZK_BGNCommit_Scheme
Formal statement
namespace GOSNIZK.BGNCommit
theorem extraction {G GT : Type*} [CommGroup G] [Fintype G] [CommGroup GT] [Fintype GT]
(S : BGNSetup G GT) (h : G) (hkey : S.IsBindingKey h) (m r : ZMod S.n) :
S.com h m r ^ S.q = (S.g ^ S.q) ^ m.val ∧ S.Ext (S.com h m r) = 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. 10, Figure 1 (Extraction); p. 9, proof of Theorem 2
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.