LeanProofs.Crypto.CentralSimplicity
DefinitionGrade4_LeanProofs_Crypto_CentralSimplicityclifford-algebraleanproofs-grade4rosetta
Foundational definitions and structural lemmas from LeanProofs.Crypto.CentralSimplicity, required by the selected LeanProofs theorem graph.
Definition code
/-
Central simplicity and conjugacy search security.
## The core security question
The security of NA-PDE-Sig rests on conjugacy search hardness in
Cl⁺(n,0). If the even subalgebra decomposes as A ⊕ B, conjugacy
search splits into independent subproblems — each potentially easy.
This file establishes the algebraic framework:
## Proved here (abstract ring theory, 0 sorry):
1. **Central element splitting** (`central_elem_splits_conj`):
If z commutes with all elements, then z·(M·X·M⁻¹) = M·(z·X)·M⁻¹.
Conjugation respects any central decomposition.
2. **Complementary splitting** (`one_sub_central`, `complement_splits_conj`):
If z is central, so is (1-z). Both components are independent CS instances.
3. **Full CS decomposition** (`cs_decomposes_via_central_idempotent`):
A CS instance (X, M·X·M⁻¹) over an algebra with central idempotent z
splits into two independent CS instances: one in z·A, one in (1-z)·A.
4. **Central involution yields idempotents** (`involution_idempotent_sq`,
`involution_idempotent_orthogonal`, `involution_idempotent_complete`):
If Z² = 1 and Z is central, then (1+Z)/2 and (1-Z)/2 are orthogonal
central idempotents decomposing A. (Requires char ≠ 2.)
## Algebraic facts (used as hypotheses in the security argument):
**Cl⁺(5,0) ≅ Cl(0,4) ≅ M₄(F_p)** — central-simple, center = F_p.
- Cl⁺(n+1, 0) ≅ Cl(0, n) by the standard even-subalgebra isomorphism
(Mathlib: `CliffordAlgebra.equivEven`)
- Cl(0, 4) has even dimension (n=4): pseudoscalar I₄ anticommutes with
generators, so I₄ is NOT in the center of the full algebra
- Center = F_p (scalars only), no decomposition possible
- Security: conjugacy search is ONE monolithic problem in a 16-dim algebra
**Cl⁺(4,0) ≅ Cl(0,3) ≅ M₂(F_p) ⊕ M₂(F_p)** — NOT central-simple.
- Cl(0, 3) has odd dimension (n=3): pseudoscalar I₃ commutes with
all elements, I₃ ∈ center, and I₃² = 1
- Center = F_p[I₃] ≅ F_p × F_p (2-dimensional)
- Idempotents (1±I₃)/2 decompose the algebra into two copies of M₂(F_p)
- Attack: conjugacy search splits into TWO independent 4-dim problems,
each solvable in O(log p) via Jordan normal form
**Cl⁺(6,0) ≅ Cl(0,5)** — center = F_p[I₅] with I₅² = -1.
- Odd dimension (n=5): I₅ commutes with all elements, I₅² = -1
- Center = F_p[√-1], which is either F_{p²} or F_p × F_p depending on
whether -1 is a square mod p
- For p ≡ 3 mod 4 (includes Mersenne31): center = F_{p²}, algebra is
central-simple over F_{p²} but NOT over F_p
## Dimension parity rule
The center of Cl⁺(n+1, 0) ≅ Cl(0, n) is:
- F_p (trivial center) when n is even → SAFE for conjugacy search
- F_p[I_n] (non-trivial) when n is odd → may decompose, UNSAFE
So Cl(5,0) (n=4, even) is secure and Cl(4,0) (n=3, odd) is broken.
This is the algebraic reason the protocol uses Cl(5,0).
-/
import Definitions.Def_Grade4_LeanProofs_Crypto_Cl60EvenClosure
import Definitions.Def_Grade4_LeanProofs_Foundations_Cl60BasisIndependence
import Mathlib.RingTheory.SimpleRing.Matrix
import Mathlib.RingTheory.SimpleRing.Field
namespace LeanProofsGrade4P2M
noncomputable section
namespace Cl60Conj
/-! ## Section 1: Central elements split conjugation
The fundamental algebraic fact: if z commutes with all ring elements,
it commutes through any conjugation. This is pure ring theory — no
Clifford algebra structure needed. -/
/-! ## Section 2: CS decomposition via central idempotent
If z is a central idempotent (z² = z, z central, z ≠ 0, z ≠ 1), the
algebra decomposes as zA ⊕ (1-z)A and conjugacy search decomposes
correspondingly. Each component is an independent CS instance. -/
/-! ## Section 3: Central involution yields idempotents (abstract fact)
If Z is a central element with Z² = 1 (a "central involution") in
a ring of characteristic ≠ 2, then e₊ = (1+Z)/2 and e₋ = (1-Z)/2
are orthogonal central idempotents:
- e₊² = e₊, e₋² = e₋
- e₊ · e₋ = 0
- e₊ + e₋ = 1
- e₊, e₋ are central (since Z is)
This is the concrete mechanism for the Cl⁺(4,0) attack: the
pseudoscalar I₄ satisfies I₄² = 1 and is central, giving the
decomposition Cl⁺(4,0) ≅ M₂(F_p) ⊕ M₂(F_p).
For Cl⁺(5,0): the even subalgebra has center = F_p (scalars only),
so no such involution Z ≠ ±1 exists, and the algebra is indecomposable.
We prove the key algebraic identity that the idempotent decomposition
respects multiplication, which is what makes each summand a subalgebra. -/
/-! ## Section 4: Instantiation for conjBy (Cl(6,0) algebra) -/
/-! ## Section 5: Concrete center computation in Cl(6,0)
The pseudoscalar I₆ = e₀₁ · e₂₃ · e₄₅ is central in Cl⁺(6,0)
and squares to -1. This demonstrates the non-trivial center that
exists for even-dimensional Clifford algebras.
For Cl(6,0): center(Cl⁺(6,0)) ⊇ ℝ[I₆] ≅ ℂ (since I₆² = -1).
This is the Cl(6,0) analog of the Cl(4,0) decomposition issue. -/
open Cl60Even
/-- Extract commutativity from vanishing cl6Comm. -/
theorem comm_of_cl6Comm_zero {A B : Cl60} (h : cl6Comm A B = 0) :
A * B = B * A := by
unfold cl6Comm at h; exact sub_eq_zero.mp h
/-- The three bivector factors of pseudoscalar60 pairwise commute
(disjoint index pairs {0,1}, {2,3}, {4,5}). -/
theorem ps60_factors_commute :
e6Prod (0 : Fin 6) 1 * e6Prod 2 3 = e6Prod 2 3 * e6Prod 0 1 ∧
e6Prod (0 : Fin 6) 1 * e6Prod 4 5 = e6Prod 4 5 * e6Prod 0 1 ∧
e6Prod (2 : Fin 6) 3 * e6Prod 4 5 = e6Prod 4 5 * e6Prod 2 3 := by
exact ⟨
comm_of_cl6Comm_zero (cl6_comm_no_shared
(by decide) (by decide) (by decide) (by decide) (by decide) (by decide)),
comm_of_cl6Comm_zero (cl6_comm_no_shared
(by decide) (by decide) (by decide) (by decide) (by decide) (by decide)),
comm_of_cl6Comm_zero (cl6_comm_no_shared
(by decide) (by decide) (by decide) (by decide) (by decide) (by decide))⟩
/-- **I₆² = -1 in Cl(6,0).**
The pseudoscalar squares to -1 because it is a product of three
pairwise-commuting bivectors, each squaring to -1:
I₆² = (e₀₁ · e₂₃ · e₄₅)² = e₀₁² · e₂₃² · e₄₅² = (-1)³ = -1.
Compare: in Cl(4,0), I₄² = +1 (two factors), giving decomposition.
In Cl(5,0), I₅ has odd grade and is NOT in Cl⁺(5,0). -/
theorem pseudoscalar60_sq : pseudoscalar60 * pseudoscalar60 = -1 := by
unfold pseudoscalar60
set A := e6Prod (0 : Fin 6) 1
set B := e6Prod (2 : Fin 6) 3
set C := e6Prod (4 : Fin 6) 5
obtain ⟨hAB, hAC, hBC⟩ := ps60_factors_commute
have hA2 : A * A = -1 := e6Prod_sq (by decide : (0 : Fin 6) ≠ 1)
have hB2 : B * B = -1 := e6Prod_sq (by decide : (2 : Fin 6) ≠ 3)
have hC2 : C * C = -1 := e6Prod_sq (by decide : (4 : Fin 6) ≠ 5)
-- (ABC)² = A²B²C² because A,B,C pairwise commute.
-- Rearrange using commutativity to group same factors.
calc A * B * C * (A * B * C)
-- Reassociate: all equal modulo associativity
= A * B * (C * A) * (B * C) := by simp only [mul_assoc]
_ = A * B * (A * C) * (B * C) := by rw [← hAC]
_ = A * (B * A) * C * (B * C) := by simp only [mul_assoc]
_ = A * (A * B) * C * (B * C) := by rw [← hAB]
_ = A * A * B * C * (B * C) := by simp only [mul_assoc]
_ = A * A * B * (C * B) * C := by simp only [mul_assoc]
_ = A * A * B * (B * C) * C := by rw [← hBC]
_ = A * A * (B * B) * (C * C) := by simp only [mul_assoc]
_ = (-1) * (-1) * (-1) := by rw [hA2, hB2, hC2]
_ = -1 := by norm_num
/-! ## Section 6: Keygen safety — central seeds must be rejected
If the public seed C is central (commutes with all elements), then
rotor conjugation fixes it: `rotorConj R C = C` for every rotor R.
This means the public key `pk = PDE^k(rotorConj R C) = PDE^k(C)` is
deterministic from public information — revealing NOTHING about R.
Design constraint: keygen MUST reject any C that is central. In
Cl⁺(6,0), the center is {a·1 + b·I₆}, so this is an explicit
algebraic check (no scalar + pseudoscalar components).
In Cl⁺(5,0) (center = scalars only), this check reduces to
"C is not a scalar multiple of 1" — much easier. -/
/-! ## Section 7: The pseudoscalar is a non-trivial central element
Together with `pseudoscalar60_sq : I₆² = -1`, the following shows
that `center(Cl⁺(6,0)) ⊇ {a·1 + b·I₆ | a, b ∈ ℝ}` — strictly larger
than the scalars.
This is the algebraic fact that distinguishes Cl(6,0) from Cl(5,0):
in Cl(5,0), there is NO analog of I₆ inside the even subalgebra,
so the center is just the scalars. -/
/-! ## Section 8: Rotor group structure
The set of rotors `{R : IsRotor60 R}` forms a group under multiplication
(Spin(6)). This closure property is needed to reason about composite
rotors in signature and key exchange protocols. -/
/-! ## Section 9: Dangerous seed characterization
The most dangerous public seed is one that is BOTH central AND a
fixed point of PDE. Such a seed makes the public key exactly equal
to the seed itself — completely trivializing the scheme. -/
/-! ## Section 10: Non-abelian witness (CS hardness foundation)
Conjugacy search hardness requires the underlying group to be
non-abelian. If Cl⁺(6,0) were commutative, conjugacy would be
trivial (M · C · M⁻¹ = C for all M).
Here we provide concrete witnesses that Cl(6,0) and its even
subalgebra are non-commutative: bivectors sharing an index do
not commute. -/
/-! ## Section 11: Matrix algebra central-simplicity
The security argument for Cl⁺(5,0) rests on the fact that
Cl⁺(5,0) ≅ M_4(F_p) and M_4(F_p) is central-simple. Here we
machine-check the latter fact using Mathlib's structure theory:
for any field F, M_n(F) is a simple ring.
This leaves the isomorphism Cl⁺(5,0) ≅ M_4(F_p) as the only
remaining algebraic hypothesis — and that is standard Artin-
Wedderburn structure theory. -/
/-! ## Section 12: Mersenne31 safety for Cl(6,0)
The Cl(6,0) production keys at Mersenne31 are NOT structurally broken
by the discovery that I₆ ∈ center(Cl⁺(6,0)), even though I₆ is a
non-trivial central element.
The reason: the Cl(4,0) attack requires a central involution Z with
**Z² = +1**, which yields the orthogonal idempotents (1±Z)/2. In
Cl⁺(6,0), the central element I₆ has **I₆² = -1** instead.
Over a field where -1 is NOT a square (e.g., F_p with p ≡ 3 mod 4),
the subalgebra F[I₆]/(I₆²+1) is a genuine quadratic field extension
F_{p²}, NOT a product F × F. Fields have only trivial idempotents.
Mersenne31 = 2³¹ - 1 = 2147483647, and 2147483647 ≡ 3 mod 4. So
√-1 ∉ F_{Mersenne31}, and the Cl(6,0) keys are structurally sound.
The migration to Cl(5,0) was correct for size/cleanliness, not
because Cl(6,0) was broken. -/
end Cl60Conj
end
end LeanProofsGrade4P2M
Source