LeanProofs.Crypto.HardHomogeneousSpace
DefinitionGrade4_LeanProofs_Crypto_HardHomogeneousSpaceclifford-algebraleanproofs-grade4rosetta
Foundational definitions and structural lemmas from LeanProofs.Crypto.HardHomogeneousSpace, required by the selected LeanProofs theorem graph.
Definition code
/-
Hard homogeneous space structure and DHKE commutativity.
A hard homogeneous space (informal): a set X with a group G acting
on it, such that:
- Computing the action g·x is easy.
- Vectorization (given x and g·x, find g) is hard.
- Parallelization ((g·x, h·x) → (gh)·x) is hard without knowing g or h.
When G is abelian, parallelization specialises to the Diffie-Hellman
shared-secret identity g·(h·x) = h·(g·x), which is what this file
formalizes algebraically. The "hardness" half of the definition is
cryptanalytic and not formalized — see the file header comments
in `Cl60Conjugation.lean`.
Two key results:
- `DHKE_commutes` : pure Cl(6,0) statement that commuting rotors
yield the same shared secret regardless of application order.
- `cl60HHS` : a concrete `HardHomogeneousSpace` instance whose group
is the abelian one-parameter subgroup generated by `B0 = e6Prod 0 1`.
Protocol constraint (worth flagging explicitly): the construction
is secure only when both parties use the SAME generator bivector.
Different generators (e.g. Alice with `e6Prod 0 1` and Bob with
`e6Prod 2 3`) give rotors that may not commute, breaking the
shared-secret identity. The `cl60HHS` instance bakes in B₀; any
generalisation must preserve same-generator usage.
-/
import Definitions.Def_Grade4_LeanProofs_Crypto_Cl60Exponential
namespace LeanProofsGrade4P2M
namespace Cl60Conj
end Cl60Conj
namespace HardHomogeneousSpace
end HardHomogeneousSpace
end LeanProofsGrade4P2M
Source