Lemma 5 — in a cyclic group of order ≥ 4, b₂ = ¬(b₀ ∧ b₁) iff b₀ + b₁ + 2b₂ − 2 ∈ {0, 1}
ProvedGOSNIZK.CircuitSound.lemma_5circuit-satcryptographyp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1zmod
Let be a finite cyclic group with neutral element and generator , and let , read as elements of .
- If the order of is at least , then
- If the order of is , then
The lemma turns a NAND gate into a statement that a single message lies in , which a homomorphic proof commitment can prove. For order the first condition alone does not suffice: gives .
Formalization Note is ZMod N (a finite cyclic group with generator is isomorphic to it, ); "order at least 4" is 4 ≤ N and "order 3" is N = 3. Bits are booleans mapped to .
Preamble
import Mathlib import Definitions.Def_GOSNIZK_CircuitSound_Scheme
Formal statement
namespace GOSNIZK.CircuitSound
/-- Lemma 5 (Groth, Ostrovsky, Sahai, *New Techniques for Noninteractive Zero-Knowledge*, J. ACM
59(3) (2012), authors' version of March 7, 2011, p. 14). The finite cyclic group `M` with generator
`1` is `ZMod N`; bits are read as `0, 1 ∈ ZMod N` via `ofBit`. If the order is at least 4,
`b₂ = ¬(b₀ ∧ b₁)` iff `b₀ + b₁ + 2b₂ − 2 ∈ {0, 1}`; if the order is 3, iff in addition
`b₀ + b₁ + b₂ − 1 ∈ {0, 1}`. -/
theorem lemma_5 (N : ℕ) (b₀ b₁ b₂ : Bool) :
(4 ≤ N →
(b₂ = !(b₀ && b₁) ↔
(ofBit b₀ + ofBit b₁ + 2 * ofBit b₂ - 2 : ZMod N) ∈ ({0, 1} : Set (ZMod N)))) ∧
(N = 3 →
(b₂ = !(b₀ && b₁) ↔
(ofBit b₀ + ofBit b₁ + 2 * ofBit b₂ - 2 : ZMod N) ∈ ({0, 1} : Set (ZMod N)) ∧
(ofBit b₀ + ofBit b₁ + ofBit b₂ - 1 : ZMod N) ∈ ({0, 1} : Set (ZMod N)))) := 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, Lemma 5
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.