Aether Catalog definitions — Cryptography_WeilPairingDeterminant
DefinitionCryptography_WeilPairingDeterminantaether-catalogcryptography
Definition bundle for the Aether Catalog module Cryptography.WeilPairingDeterminant, transplanted by skeleton subtraction; supplies the types and constants the catalog's theorems import.
Definition code
-- Def bundle generated from Cryptography/WeilPairingDeterminant.lean by skeleton subtraction
import Mathlib
import Definitions.Def_Cryptography_WeilPairingBLS
/-!
# The determinant model of the Weil pairing: construction, classification, existence
The catalog file `Cryptography.WeilPairingBLS` *axiomatises* a Weil pairing on the
`n`-torsion of a Weierstrass curve (bilinear, alternating, `n`-torsion valued,
nondegenerate). This file removes the axiom in the only place where it can be removed
by pure algebra, and classifies all possible pairings.
Main results.
* `AltPairing` : the bare alternating bi-additive interface, extracted from a
`WeilPairing` by `WeilPairing.toAltPairing`.
* `AltPairing.pair_zsmul_left/right`, `AltPairing.skew` : full `ℤ`-bilinearity and
skew-symmetry from alternation alone.
* `AltPairing.pair_coords` : **classification.** On a group generated by two elements
`e₁, e₂`, every alternating pairing is the `ζ`-th power of the determinant form,
`e(a e₁ + b e₂, c e₁ + d e₂) = ζ ^ (ad - bc)` with `ζ = e(e₁,e₂)`. In particular two
alternating pairings that agree on a basis agree everywhere
(`AltPairing.ext_of_basis`).
* `detPairing` : the explicit determinant pairing on `(ZMod n)²` with values in
`Multiplicative (ZMod n)`, proved alternating, `n`-torsion and **nondegenerate**.
* `weilPairingOfEquiv` : **existence.** Any Weierstrass curve whose `n`-torsion is
isomorphic to `(ZMod n)²` carries a Weil pairing in the sense of the catalog
structure. Together with `detPairing_nondegenerate` this shows that the axioms of
`WeilPairing` are consistent and non-vacuous.
* `AltPairing.orderOf_root_of_nondegenerate` : conversely, a nondegenerate alternating
pairing on `(ZMod n)²` forces its root of unity `ζ` to have exact order `n`.
-/
open scoped BigOperators
namespace Cryptography.WeilBLS
universe u v w
/-! ## The bare alternating pairing interface -/
/-- An alternating bi-additive pairing from an additive abelian group to a
commutative group. This is the algebraic core shared by all Weil pairings. -/
structure AltPairing (A : Type u) [AddCommGroup A] (μ : Type v) [CommGroup μ] where
/-- The underlying bi-additive map. -/
hom : A →+ A →+ Additive μ
/-- Alternation. -/
alternating : ∀ P : A, hom P P = 0
namespace AltPairing
variable {A : Type u} [AddCommGroup A] {μ : Type v} [CommGroup μ] (E : AltPairing A μ)
/-- Multiplicative notation for an alternating pairing. -/
def pair (x y : A) : μ := Additive.toMul (E.hom x y)
end AltPairing
variable {F : Type u} [Field F] [DecidableEq F]
/-- Every Weil pairing is in particular an alternating pairing. -/
def WeilPairing.toAltPairing {W : WeierstrassCurve F} {n : ℕ} {μ : Type v} [CommGroup μ]
(e : WeilPairing W n μ) : AltPairing (torsionPoints W n) μ where
hom := e.hom
alternating := e.alternating
/-! ## The explicit determinant pairing on `(ZMod n)²` -/
/-- The determinant form on `(ZMod n)²`. -/
def detForm (n : ℕ) (v w : ZMod n × ZMod n) : ZMod n := v.1 * w.2 - v.2 * w.1
/-- The determinant form, as an additive homomorphism in the second variable. -/
def detFormRight (n : ℕ) (v : ZMod n × ZMod n) : (ZMod n × ZMod n) →+ ZMod n where
toFun w := detForm n v w
map_zero' := by simp [detForm]
map_add' w w' := by simp only [detForm, Prod.fst_add, Prod.snd_add]; ring
/-- The determinant form, as a bi-additive map. -/
def detBihom (n : ℕ) : (ZMod n × ZMod n) →+ ((ZMod n × ZMod n) →+ ZMod n) where
toFun v := detFormRight n v
map_zero' := by ext w; simp [detFormRight, detForm]
map_add' v v' := by
ext w
simp only [detFormRight, detForm, AddMonoidHom.coe_mk, ZeroHom.coe_mk,
AddMonoidHom.add_apply, Prod.fst_add, Prod.snd_add]
ring
/-- Every element of `Multiplicative (ZMod n)` is an `n`-th root of unity: this is the
canonical model of `μₙ` used below. -/
theorem multiplicative_zmod_pow_self (n : ℕ) (z : Multiplicative (ZMod n)) : z ^ n = 1 := by
have : z ^ n = Multiplicative.ofAdd (n • Multiplicative.toAdd z) := by
rw [ofAdd_nsmul]; rfl
rw [this, nsmul_eq_mul, ZMod.natCast_self, zero_mul]
rfl
/-- The determinant pairing on `(ZMod n)²` with values in `Multiplicative (ZMod n)`,
the canonical model of the group of `n`-th roots of unity. -/
def detPairing (n : ℕ) : AltPairing (ZMod n × ZMod n) (Multiplicative (ZMod n)) where
hom := detBihom n
alternating := by
intro v
show detForm n v v = 0
simp [detForm, mul_comm]
@[simp] theorem detPairing_apply (n : ℕ) (v w : ZMod n × ZMod n) :
(detPairing n).pair v w = Multiplicative.ofAdd (detForm n v w) := rfl
/-- **Nondegeneracy of the determinant pairing.** -/
theorem detPairing_nondegenerate_left {n : ℕ} (v : ZMod n × ZMod n)
(h : ∀ w, (detPairing n).pair v w = 1) : v = 0 := by
have h1 := h ((0 : ZMod n), (1 : ZMod n))
have h2 := h ((1 : ZMod n), (0 : ZMod n))
simp only [detPairing_apply, detForm, ofAdd_eq_one] at h1 h2
have hv1 : v.1 = 0 := by simpa using h1
have hv2 : v.2 = 0 := by
have : -v.2 = 0 := by simpa using h2
simpa using neg_eq_zero.mp this
exact Prod.ext hv1 hv2
/-! ## Transporting pairings and the existence theorem -/
/-- Pull back a bi-additive map along an additive homomorphism. -/
def bihomComp {A B M : Type*} [AddCommGroup A] [AddCommGroup B] [AddCommGroup M]
(f : B →+ B →+ M) (g : A →+ B) : A →+ A →+ M where
toFun a := (f (g a)).comp g
map_zero' := by ext b; simp
map_add' a a' := by ext b; simp
/-- Transport an alternating pairing along an additive homomorphism. -/
def AltPairing.comap {A B : Type*} [AddCommGroup A] [AddCommGroup B] {μ : Type v}
[CommGroup μ] (E : AltPairing B μ) (g : A →+ B) : AltPairing A μ where
hom := bihomComp E.hom g
alternating P := E.alternating (g P)
end Cryptography.WeilBLS