Proof of Theorem 6 — the protocol of Figure 3 has perfect completeness
ProvedGOSNIZK.CircuitSound.completenesscircuit-satcryptographyp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1zero-knowledge
Let a homomorphic proof commitment scheme satisfy the homomorphic property and perfect completeness of the 0/1 proof. Then the Circuit SAT proof of Figure 3 has perfect completeness on keys of either mode: for every key output by or , every NAND circuit , every with and every choice of the prover's randomness,
Completeness on hiding keys is the completeness clause of Theorem 11 (p. 16), which refers back to the proof of Theorem 6.
Formalization Note No order bound on is needed: for a satisfied gate the gate message equals in every .
Preamble
import Mathlib import Definitions.Def_GOSNIZK_CircuitSound_Protocol
Formal statement
namespace GOSNIZK.CircuitSound
/-- Perfect completeness of the protocol of Figure 3 (Groth, Ostrovsky, Sahai, *New Techniques for
Noninteractive Zero-Knowledge*, J. ACM 59(3) (2012), authors' version of March 7, 2011, proof of
Theorem 6, pp. 14–15): it follows from the homomorphic property and the perfect completeness of the
0/1 proofs, and holds on keys of either mode. -/
theorem completeness {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)
(hhom : S.Homomorphic) (hcomp01 : S.PerfectCompleteness01) :
S.CircuitPerfectCompleteness := 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, pp. 14–15, proof of Theorem 6 (first paragraph); p. 16, Theorem 11
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.