The gate commitment c₀ · c₁ · c₂² · com(−2; 0) commits to b₀ + b₁ + 2b₂ − 2, and a 0/1 proof for it shows b₂ = ¬(b₀ ∧ b₁)
ProvedGOSNIZK.CircuitSound.gate_commitmentcircuit-satcommitment-schemescryptographyp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1
Let a homomorphic proof commitment scheme have message space with , and assume the homomorphic property, perfect binding and perfect soundness of the 0/1 proof.
- For every key of either mode, all messages and randomizers ,
- For every output by , all bits , randomizers and every : if
then .
This is the gate check of Figure 3: the verifier can test a NAND gate on committed wires with one 0/1 proof.
Formalization Note Part 2 is the paper's sentence "A proof that this commitment contains 0 or 1 shows that ", made precise: the proof is accepted on a binding key, and perfect binding identifies the message it certifies with , to which Lemma 5 applies.
Preamble
import Mathlib import Definitions.Def_GOSNIZK_CircuitSound_Protocol
Formal statement
namespace GOSNIZK.CircuitSound
/-- The gate commitment (Groth, Ostrovsky, Sahai, *New Techniques for Noninteractive
Zero-Knowledge*, J. ACM 59(3) (2012), authors' version of March 7, 2011, p. 14, after Lemma 5).
(1) Under the homomorphic property, on every key of either mode,
`com(b₀; r₀) · com(b₁; r₁) · com(b₂; r₂)² · com(−2; 0) = com(b₀ + b₁ + 2b₂ − 2; r₀ + r₁ + 2r₂)`.
(2) On a binding key, with message space of order at least 4, perfect binding and perfect soundness
of the 0/1 proof, an accepted 0/1 proof for this commitment, where `b₀, b₁, b₂` are bits, shows
`b₂ = ¬(b₀ ∧ b₁)`. -/
theorem gate_commitment {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) :
(∀ ck : CK, S.IsKey ck → ∀ (m₀ m₁ m₂ : ZMod N) (r₀ r₁ r₂ : R),
S.gateCom ck (S.com ck m₀ r₀) (S.com ck m₁ r₁) (S.com ck m₂ r₂) =
S.com ck (m₀ + m₁ + 2 * m₂ - 2) (r₀ + r₁ + 2 • r₂)) ∧
(∀ (ck : CK) (xk : XK), (ck, xk) ∈ S.Kbind.support →
∀ (b₀ b₁ b₂ : Bool) (r₀ r₁ r₂ : R) (π : Prf),
S.V01 ck (S.gateCom ck (S.com ck (ofBit b₀) r₀) (S.com ck (ofBit b₁) r₁)
(S.com ck (ofBit b₂) r₂)) π = true →
b₂ = !(b₀ && b₁)) := 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. 14, paragraph after Lemma 5
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.