Lemma 7 — (K, P, V) has perfect soundness
ProvedGOSNIZK.CircuitSound.lemma_7Let a homomorphic proof commitment scheme have message space with , and assume the homomorphic property, perfect binding and perfect soundness of the 0/1 proof. Then the Circuit SAT proof of Figure 3 has perfect soundness: for every output by , every NAND circuit that has no satisfying assignment and every purported proof ,
Soundness holds against unbounded provers, so the protocol is a proof, not only an argument, on binding keys.
Formalization Note The paper's for all adversaries is stated for every key in the support of and every . The order bound is the paper's standing choice on p. 14; for the protocol of Figure 3 is not sound (the all-zero assignment passes every gate check).
import Mathlib import Definitions.Def_GOSNIZK_CircuitSound_Protocol
namespace GOSNIZK.CircuitSound
/-- Lemma 7 (Groth, Ostrovsky, Sahai, *New Techniques for Noninteractive Zero-Knowledge*, J. ACM
59(3) (2012), authors' version of March 7, 2011, p. 15): the protocol of Figure 3 has perfect
soundness, for a homomorphic, perfectly binding commitment whose 0/1 proof is perfectly sound and
whose message space has order at least 4. -/
theorem lemma_7 {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) :
S.CircuitPerfectSoundness := by sorry
end GOSNIZK.CircuitSound
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.