Proof of Theorem 6 — with perfect extractability, the wire values extracted from an accepted proof satisfy the circuit
ProvedGOSNIZK.CircuitSound.knowledge_extractioncircuit-satcryptographyp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1zero-knowledge
Let a homomorphic proof commitment scheme have message space with , and assume the homomorphic property, perfect binding, perfect soundness of the 0/1 proof and perfect extractability. Let and let set iff . Then for every output by , every NAND circuit and every proof with ,
So the protocol of Figure 3 is a perfect proof of knowledge.
Formalization Note The extractor is fixed to the one in the paper's proof; an unspecified extractor would make the claim follow from soundness by exhaustive search, which is not what the paper proves.
Preamble
import Mathlib import Definitions.Def_GOSNIZK_CircuitSound_Protocol
Formal statement
namespace GOSNIZK.CircuitSound
/-- Perfect knowledge extraction (Groth, Ostrovsky, Sahai, *New Techniques for Noninteractive
Zero-Knowledge*, J. ACM 59(3) (2012), authors' version of March 7, 2011, proof of Theorem 6, p. 15):
if the commitment scheme is perfectly extractable, the wire values extracted from the commitments of
an accepted proof satisfy the circuit, on every binding key. -/
theorem knowledge_extraction {N : ℕ} {R C CK XK TK Rp Prf : Type} [AddCommGroup R] [Fintype R] [CommGroup C] [Fintype C]
[Fintype Rp] [Nonempty Rp] (S : Scheme N R C CK XK TK Rp Prf)
(hN : 4 ≤ N) (hhom : S.Homomorphic) (hbind : S.PerfectBinding)
(hsound01 : S.PerfectSoundness01) (hext : S.PerfectExtractability) :
S.CircuitPerfectKnowledgeExtraction := by sorry
end GOSNIZK.CircuitSound
Source
Groth, Ostrovsky, Sahai, New Techniques for Noninteractive Zero-Knowledge, J. ACM 59(3) (2012), authors' version of March 7, 2011, p. 15, proof of Theorem 6 (second paragraph)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.