AFTD Auto-Formalizing Theoretical Domains

schnorr_response_unique

theoremverifiedformalization

In the Schnorr identification protocol, accepting responses are unique: let G be a commutative group, q a prime, and g in G an element of order q. For any public key pk in G, commitment a in G, and challenge c in ZMod q, if responses s₁, s₂ in ZMod q both satisfy Schnorr.Verify g pk a c s₁ and Schnorr.Verify g pk a c s₂, then s₁ = s₂.

Statement

theorem schnorr_response_unique {G : Type*} [CommGroup G] {q : ℕ} [Fact q.Prime] (g : G)
    (hg : orderOf g = q) (pk a : G) (c s₁ s₂ : ZMod q)
    (h₁ : Schnorr.Verify g pk a c s₁) (h₂ : Schnorr.Verify g pk a c s₂) :
    s₁ = s₂
Formalizes
Schnorr (1991); Katz & Lindell (2020), Section 12.5.1
Verified
11 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
  • 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…

Read back from the Lean

For any commutative group $G$ and any natural number $q$ that is prime, and for any element $g \in G$ whose order in $G$ equals $q$, any elements $pk, a \in G$, and any elements $c, s_1, s_2 \in \mathbb{Z}/q\mathbb{Z}$: if both Schnorr.Verify g pk a c s₁ and Schnorr.Verify g pk a c s₂ hold, then $s_1 = s_2$.

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

The proof, explained

The proof establishes uniqueness by comparing the verification equations for the two responses s₁ and s₂. Since both satisfy verification for the same commitment and challenge, g ^ s₁.val and g ^ s₂.val both equal a * pk ^ c.val, so g ^ s₁.val = g ^ s₂.val. Because g has order q, the exponents must be congruent modulo q. Finally, because the representatives s₁.val and s₂.val are both strictly less than q, congruence modulo q forces them to be equal, and injectivity of the representative map yields s₁ = s₂.

  1. q is non-zero (recorded as an instance of NeZero q)

    Because q is prime (extracted from Fact q.Prime via Fact.out), Nat.Prime.ne_zero implies q ≠ 0, establishing NeZero q.

    line 6

    uses Nat.Prime.ne_zero, Fact.out

      have : NeZero q := ⟨Nat.Prime.ne_zero Fact.out⟩
  2. g ^ s₁.val = g ^ s₂.val

    Unfolding the definition of Schnorr.Verify in hypotheses h₁ and h₂ reveals that both g ^ s₁.val and g ^ s₂.val equal the identical quantity a * pk ^ c.val. Equating the two expressions gives g ^ s₁.val = g ^ s₂.val.

    lines 7–10

      have h_pow : g ^ s₁.val = g ^ s₂.val := by
        change g ^ s₁.val = a * pk ^ c.val at h₁
        change g ^ s₂.val = a * pk ^ c.val at h₂
        rw [h₁, h₂]
  3. s₁.val ≡ s₂.val [MOD q]

    By pow_eq_pow_iff_modEq, equality of powers g ^ s₁.val = g ^ s₂.val is equivalent to congruence of the exponents modulo orderOf g. Rewriting with the hypothesis hg (orderOf g = q) yields s₁.val ≡ s₂.val [MOD q].

    line 11

    uses pow_eq_pow_iff_modEq

      rw [pow_eq_pow_iff_modEq, hg] at h_pow
  4. s₁.val = s₂.val

    The canonical natural representations of s₁ and s₂ in ZMod q satisfy s₁.val < q and s₂.val < q (by ZMod.val_lt). The modular congruence means s₁.val % q = s₂.val % q. Since both values are strictly less than q, Nat.mod_eq_of_lt reduces this congruence directly to s₁.val = s₂.val.

    lines 12–16

    uses ZMod.val_lt, Nat.mod_eq_of_lt

      have h_val : s₁.val = s₂.val := by
        have hs₁ := ZMod.val_lt s₁
        have hs₂ := ZMod.val_lt s₂
        change s₁.val % q = s₂.val % q at h_pow
        rwa [Nat.mod_eq_of_lt hs₁, Nat.mod_eq_of_lt hs₂] at h_pow
  5. s₁ = s₂

    Because the representative map from ZMod q to ℕ is injective (ZMod.val_injective), the equality s₁.val = s₂.val implies s₁ = s₂.

    line 17

    uses ZMod.val_injective

      exact ZMod.val_injective q h_val
Nat.Prime.ne_zero
A prime natural number is non-zero.
Fact.out
Extracts the underlying proposition from a Fact typeclass instance (here, that q is prime).
pow_eq_pow_iff_modEq
In a cancellative monoid, two natural powers of an element are equal if and only if the exponents are congruent modulo the order of that element.
ZMod.val_lt
For n ≠ 0, the canonical natural representative of any element in ZMod n is strictly less than n.
Nat.mod_eq_of_lt
If a natural number a is strictly less than b, then a % b = a.
ZMod.val_injective
For n ≠ 0, the canonical representation map from ZMod n to ℕ is injective.

Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.

Lean source view module on GitHub

/-- For a fixed commitment and challenge, the Schnorr verifier accepts at most one response. -/theorem schnorr_response_unique {G : Type*} [CommGroup G] {q : ℕ} [Fact q.Prime] (g : G)    (hg : orderOf g = q) (pk a : G) (c s₁ s₂ : ZMod q)    (h₁ : Schnorr.Verify g pk a c s₁) (h₂ : Schnorr.Verify g pk a c s₂) :    s₁ = s₂ := by  have : NeZero q := ⟨Nat.Prime.ne_zero Fact.out⟩  have h_pow : g ^ s₁.val = g ^ s₂.val := by    change g ^ s₁.val = a * pk ^ c.val at h₁    change g ^ s₂.val = a * pk ^ c.val at h₂    rw [h₁, h₂]  rw [pow_eq_pow_iff_modEq, hg] at h_pow  have h_val : s₁.val = s₂.val := by    have hs₁ := ZMod.val_lt s₁    have hs₂ := ZMod.val_lt s₂    change s₁.val % q = s₂.val % q at h_pow    rwa [Nat.mod_eq_of_lt hs₁, Nat.mod_eq_of_lt hs₂] at h_pow  exact ZMod.val_injective q h_val
See it in the graphDiscuss this resultChallenge it