Theorem 6 (exact part) — the Circuit SAT proof is perfectly complete, perfectly sound and a perfect proof of knowledge
ProvedGOSNIZK.CircuitSound.theorem_6Let be a homomorphic proof commitment scheme whose message space is cyclic of order , with the homomorphic property, perfect binding, and perfectly complete and perfectly sound proofs that a commitment contains or . Then the Circuit SAT proof of Figure 3, with common reference string for :
- has perfect completeness, on keys output by and on keys output by ;
- has perfect soundness: on every key output by , no proof for an unsatisfiable circuit is accepted;
- is a perfect proof of knowledge if the scheme also has perfect extractability: on every output by , the wires extracted from any accepted proof satisfy the circuit.
Theorem 6 is the paper's NIZK proof for Circuit SAT; instantiated with the commitments of Sections 4 and 5 it gives the perfectly sound NIZK proofs for Circuit SAT of Corollaries 9 and 10.
Formalization Note Only the exact clauses of Theorem 6 are stated. "Computational zero-knowledge" and "computational non-erasure zero-knowledge" are dropped: they rest on the computational indistinguishability of binding and hiding keys; their exact core, perfect zero-knowledge on hiding keys (Lemma 8), is a separate mission. Every "for all adversaries, / " is stated for every key in the support of the generator and every choice of the adversary. Perfect completeness is stated on keys of both modes; on binding keys it is Theorem 6's, on hiding keys Theorem 11's. is ZMod N and 4 ≤ N is the paper's restriction on p. 14 ("we focus on the case where the message space ... has order at least 4").
import Mathlib import Definitions.Def_GOSNIZK_CircuitSound_Protocol
namespace GOSNIZK.CircuitSound
/-- Theorem 6, exact part (Groth, Ostrovsky, Sahai, *New Techniques for Noninteractive
Zero-Knowledge*, J. ACM 59(3) (2012), authors' version of March 7, 2011, p. 14). For a homomorphic
proof commitment scheme with message space of order at least 4, perfect binding, and perfectly
complete and perfectly sound 0/1 proofs, the protocol of Figure 3 has perfect completeness (on keys
of either mode) and perfect soundness; if the scheme also has perfect extractability, it is a
perfect proof of knowledge. The computational zero-knowledge clauses are not formalized. -/
theorem theorem_6 {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)
(hcomp01 : S.PerfectCompleteness01) (hsound01 : S.PerfectSoundness01) :
S.CircuitPerfectCompleteness ∧ S.CircuitPerfectSoundness ∧
(S.PerfectExtractability → S.CircuitPerfectKnowledgeExtraction) := by sorry
end GOSNIZK.CircuitSound
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.