AFTD Auto-Formalizing Theoretical Domains

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.
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

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 _)
See it in the graphDiscuss this resultChallenge it