AFTD Auto-Formalizing Theoretical Domains

schnorr_soundness_affine_related_keys

theoremverifiedoriginal

Let 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 α, β in ZMod q define a related witness w₂ = α * w₁ + β with public key pk₂ = g^(w₂.val). Suppose an identical commitment a in G is used in two transcripts (a, c₁, s₁) and (a, c₂, s₂) that satisfy Schnorr.Verify for pk₁ and pk₂ respectively. If c₁ ≠ α * c₂, then (s₁ - s₂ + β * c₂) / (c₁ - α * c₂) = w₁ in ZMod q.

Statement

theorem schnorr_soundness_affine_related_keys
    {G : Type*} [CommGroup G] {q : ℕ} [Fact q.Prime] (g : G)
    (hg : orderOf g = q) (w₁ α β : ZMod q) (a : G)
    (c₁ c₂ s₁ s₂ : ZMod q) (hne : c₁ ≠ α * c₂)
    (h₁ : Schnorr.Verify g (g ^ w₁.val) a c₁ s₁)
    (h₂ : Schnorr.Verify g (g ^ (α * w₁ + β).val) a c₂ s₂) :
    (s₁ - s₂ + β * c₂) / (c₁ - α * c₂) = w₁
Related work
Goldreich, Foundations of Cryptography, vol. 1, Sec. 4.4
Verified
20 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 prime number $q$, given: - an element $g \in G$ such that the order of $g$ in $G$ is $q$ (orderOf g = q), - elements $w_1, \alpha, \beta \in \mathbb{Z}/q\mathbb{Z}$, - a group element $a \in G$, - elements $c_1, c_2, s_1, s_2 \in \mathbb{Z}/q\mathbb{Z}$, assuming that: 1. $c_1 \neq \alpha \cdot c_2$ in $\mathbb{Z}/q\mathbb{Z}$, 2. Schnorr.Verify g (g ^ w₁.val) a c₁ s₁ holds, and 3. Schnorr.Verify g (g ^ (α * w₁ + β).val) a c₂ s₂ holds, then in the field $\mathbb{Z}/q\mathbb{Z}$: $$(s_1 - s_2 + \beta \cdot c_2) / (c_1 - \alpha \cdot c_2) = w_1$$

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 extracts the primary secret witness w₁ from two Schnorr transcripts sharing the same commitment a across affine-related keys w₂ = α * w₁ + β. Cross-multiplying the two verification equations eliminates the shared commitment a, yielding an equality between powers of the generator g. Because g has order q, this implies a linear congruence on the exponents modulo q, which translates to a linear equation over ZMod q; since c₁ ≠ α * c₂, the coefficient of w₁ is invertible, directly giving the explicit witness extraction formula.

  1. Cross-multiplying the verification equations eliminates the commitment a, giving g ^ s₁.val * (g ^ (α * w₁ + β).val) ^ c₂.val = g ^ s₂.val * (g ^ w₁.val) ^ c₁.val.

    Unfolding the definition of Schnorr.Verify reveals that g ^ s₁.val = a * pk₁ ^ c₁.val and g ^ s₂.val = a * pk₂ ^ c₂.val. Substituting these into both sides, the commitment a cancels because multiplication in the commutative group G satisfies (a * x) * y = (a * y) * x (mul_right_comm).

    lines 9–12

    uses mul_right_comm

      simp only [Schnorr.Verify] at h₁ h₂
      have key1 : g ^ s₁.val * (g ^ (α * w₁ + β).val) ^ c₂.val
          = g ^ s₂.val * (g ^ w₁.val) ^ c₁.val := by
        rw [h₁, h₂, mul_right_comm]
  2. The exponents satisfy s₁.val + (α * w₁ + β).val * c₂.val ≡ s₂.val + w₁.val * c₁.val [MOD q].

    Applying exponent rules for products (pow_add) and powers (pow_mul) combines both sides into single powers of g. Because g has order q (hg), equality of powers g ^ m = g ^ n is equivalent to congruence of the exponents modulo q (pow_eq_pow_iff_modEq).

    lines 13–14

    uses pow_mul, pow_add, pow_eq_pow_iff_modEq

      rw [← pow_mul, ← pow_mul, ← pow_add, ← pow_add,
          pow_eq_pow_iff_modEq, hg] at key1
  3. In ZMod q, s₁ + (α * w₁ + β) * c₂ = s₂ + w₁ * c₁.

    Modular equivalence of natural numbers modulo q is equivalent to equality of their canonical projections in ZMod q (ZMod.natCast_eq_natCast_iff). Projecting both sides into ZMod q yields the identity in the ring ZMod q.

    lines 15–16

    uses ZMod.natCast_eq_natCast_iff

      have hZ : s₁ + (α * w₁ + β) * c₂ = s₂ + w₁ * c₁ := by
        simpa using (ZMod.natCast_eq_natCast_iff _ _ q).mpr key1
  4. In ZMod q, s₁ - s₂ + β * c₂ = w₁ * (c₁ - α * c₂).

    Expanding the product (α * w₁ + β) * c₂ = α * w₁ * c₂ + β * c₂ and rearranging terms groups all terms containing the secret witness w₁ on the right-hand side as w₁ * (c₁ - α * c₂).

    lines 17–18

      have hsub : s₁ - s₂ + β * c₂ = w₁ * (c₁ - α * c₂) := by
        linear_combination hZ
  5. (s₁ - s₂ + β * c₂) / (c₁ - α * c₂) = w₁ in ZMod q.

    Since c₁ ≠ α * c₂ (hne), the difference c₁ - α * c₂ is nonzero (sub_ne_zero.mpr). In the field ZMod q, dividing both sides by this nonzero factor (div_eq_iff) isolates the witness w₁.

    lines 19–21

    uses sub_ne_zero.mpr, div_eq_iff

      have hc_ne : c₁ - α * c₂ ≠ 0 := sub_ne_zero.mpr hne
      rw [div_eq_iff hc_ne]
      exact hsub
mul_right_comm
In a commutative semigroup, (a * b) * c = (a * c) * b.
pow_mul
In a monoid, a ^ (m * n) = (a ^ m) ^ n.
pow_add
In a monoid, a ^ (m + n) = a ^ m * a ^ n.
pow_eq_pow_iff_modEq
In a left-cancellative monoid, powers x ^ n and x ^ m are equal if and only if n ≡ m modulo the order of x.
ZMod.natCast_eq_natCast_iff
Two natural numbers have equal images in ZMod c if and only if they are congruent modulo c.
sub_ne_zero.mpr
If a ≠ b, then a - b ≠ 0.
div_eq_iff
For b ≠ 0 in a group with zero (such as a field), a / b = c is equivalent to a = c * b.

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

/-- Special soundness of the Schnorr protocol with affine-related keys: nonce reuse across related keys extracts the primary witness. -/theorem schnorr_soundness_affine_related_keys    {G : Type*} [CommGroup G] {q : ℕ} [Fact q.Prime] (g : G)    (hg : orderOf g = q) (w₁ α β : ZMod q) (a : G)    (c₁ c₂ s₁ s₂ : ZMod q) (hne : c₁ ≠ α * c₂)    (h₁ : Schnorr.Verify g (g ^ w₁.val) a c₁ s₁)    (h₂ : Schnorr.Verify g (g ^ (α * w₁ + β).val) a c₂ s₂) :    (s₁ - s₂ + β * c₂) / (c₁ - α * c₂) = w₁ := by  simp only [Schnorr.Verify] at h₁ h₂  have key1 : g ^ s₁.val * (g ^ (α * w₁ + β).val) ^ c₂.val      = g ^ s₂.val * (g ^ w₁.val) ^ c₁.val := by    rw [h₁, h₂, mul_right_comm]  rw [← pow_mul, ← pow_mul, ← pow_add, ← pow_add,      pow_eq_pow_iff_modEq, hg] at key1  have hZ : s₁ + (α * w₁ + β) * c₂ = s₂ + w₁ * c₁ := by    simpa using (ZMod.natCast_eq_natCast_iff _ _ q).mpr key1  have hsub : s₁ - s₂ + β * c₂ = w₁ * (c₁ - α * c₂) := by    linear_combination hZ  have hc_ne : c₁ - α * c₂ ≠ 0 := sub_ne_zero.mpr hne  rw [div_eq_iff hc_ne]  exact hsub
See it in the graphDiscuss this resultChallenge it