AFTD Auto-Formalizing Theoretical Domains

Schnorr.Verify

defimported Lean

The 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 the exponents are taken via the canonical lifts 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
def Schnorr.Verify (pk a : G) (c s : ZMod q) : Prop
Defined in
TCSlib, `Schnorr.Verify`
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
none listed
Used by 6
  • schnorr_linear_batch_soundness_boundLet G be a commutative group, q a prime, and g in G an element of order q. Let pk, a₁, a₂ in Subgroup.zpowers g. For any challenges c₁, c₂…
  • Schnorr.schnorr_completenessCompleteness of the Schnorr identification protocol. Let $q$ be a prime, let $G$ be a commutative group, and let $g \in G$ be an element…
  • schnorr_soundness_correlated_commitmentsSpecial soundness of the Schnorr protocol with affine-correlated commitments: let G be a commutative group, q a prime, and g in G an…
  • Schnorr.schnorr_soundnessSpecial soundness of the Schnorr protocol. Special soundness. Let $q$ be prime, let $g$ be an element of order $q$ in a commutative group…
  • schnorr_response_uniqueIn the Schnorr identification protocol, accepting responses are unique: let G be a commutative group, q a prime, and g in G an element of…
  • schnorr_soundness_affine_related_keysLet G be a commutative group, q a prime, and g in G an element of order q. Let w₁ in ZMod q be a secret witness and pk₁ = g^(w₁.val). Let…

Lean source view module on GitHub

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
/-- Verifier's accept predicate: `g ^ s = a · pk ^ c`. -/
def Schnorr.Verify (pk a : G) (c s : ZMod q) : Prop :=
  g ^ s.val = a * pk ^ c.val
See it in the graphDiscuss this resultChallenge it