Schnorr.schnorr_completeness
theoremverifiedformalizationimported Lean
Completeness of the Schnorr identification protocol. Let $q$ be a prime, let $G$ be a commutative group, and let $g \in G$ be an element of order $q$. For any witness $w$, randomness $r$, and challenge $c$ in $\mathbb{Z}_q$, the honest transcript — commitment $a = g^{r}$, challenge $c$, and response $s = r + c\,w$ — is accepted by the verifier against the public key $\mathit{pk} = g^{w}$; that is, \[ g^{\,s} \;=\; a \cdot \mathit{pk}^{\,c}, \] where each exponent is taken via the canonical lift of the corresponding element of $\mathbb{Z}_q$ to $\mathbb{N}$.
Statement
set_option relaxedAutoImplicit false in set_option autoImplicit false in variable {G : Type*} [CommGroup G] in variable {q : ℕ} [Fact q.Prime] in variable (g : G) in theorem Schnorr.schnorr_completeness (hg : orderOf g = q) (w r c : ZMod q) : Verify g (g ^ w.val) (commit g r) c (respond w r c)
- Formalizes
- Completeness of the Schnorr identification protocol, as formalized in TCSlib (`Schnorr.schnorr_completeness`)
- Lean proof
- By Hydroxyi (from the file's git history), from github.com/Shilun-Allan-Li/tcslib at
c8a02591b1e5(Apache-2.0). Compiled here against leanprover/lean4:v4.33.1, Mathlib v4.33.1; written for leanprover/lean4:v4.25.0.Schnorr.schnorr_completeness← Schnorr.schnorr_completeness (TCSlib/Cryptography/SchnorrProtocol.lean:69): verbatim
- Verified
- 07 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- Schnorr.VerifyThe verifier accepts a transcript $(a, c, s)$ with respect to public key $\mathit{pk} \in G$ when $g^s = a \cdot \mathit{pk}^{c}$, where…
- Schnorr.respondGiven witness $w$, randomness $r$, and challenge $c$ in $\mathbb{Z}_q$, the response is $s := r + c \cdot w \in \mathbb{Z}_q$.
- Schnorr.commitGiven randomness $r \in \mathbb{Z}_q$ and a generator $g \in G$, the commitment is $a := g^{r}$, where the exponent is taken via the…
- Used by 1
- Schnorr.schnorr_hvzkHonest-verifier zero knowledge of the Schnorr protocol. Let $G$ be a commutative group, let $q$ be prime, and let $g \in G$ be an element…
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
set_option relaxedAutoImplicit false inset_option autoImplicit false invariable {G : Type*} [CommGroup G] invariable {q : ℕ} [Fact q.Prime] invariable (g : G) in/-- **Completeness**: for any witness `w`, randomness `r`, and challenge `c` in `ZMod q`, with generator `g` of order `q`, the honest transcript `(g^r, c, r + c·w)` satisfies the verifier equation `g ^ (r + c·w).val = g^r.val * (g^w.val)^c.val`. -/theorem Schnorr.schnorr_completeness (hg : orderOf g = q) (w r c : ZMod q) : Verify g (g ^ w.val) (commit g r) c (respond w r c) := by simp only [Verify, commit, respond] rw [← pow_mul, ← pow_add, pow_eq_pow_iff_modEq, hg] have h1 : (r + c * w).val ≡ r.val + (c * w).val [MOD q] := by rw [ZMod.val_add] exact Nat.mod_modEq _ _ have h2 : (c * w).val ≡ w.val * c.val [MOD q] := by rw [ZMod.val_mul, mul_comm] exact Nat.mod_modEq _ _ exact h1.trans (h2.add_left _)