The Lattice Isomorphism Problem Frontier,�or: Why number theory is super fun and definitely not superfluous to modern crypt
Daniel Apon�Anduril* Industries�dapon@anduril.com
*This talk carefully avoids any and all Lord of the Rings related commentary – humorous, self-referential, or otherwise – because we’ve been successfully sued by the Tolkien Foundation. (Let’s be honest: We deserved it.)
I am legally required to make this lettuce joke in any talk I give about lattices.
1. What is a lattice?
A lattice is a regular grid of points — all integer combinations of a set of basis vectors.
L = { a₁b₁ + a₂b₂ + … + aₙbₙ : aᵢ ∈ ℤ }
• The vectors b₁,…,bₙ are a basis.
• n is the dimension (rank).
• The lattice is the set of points — not the basis.
• Many different bases give the very same grid.
• Any volume-preserving transformation U works!
2
This is a lattice of lettuces. sigh.
2
2. One lattice, many bases
Both pictures are the SAME lattice. A basis is just a choice of coordinates for it.
Two bases give the same lattice. They differ by an integer change of variables U with det U = ±1 (U ∈ GLₙ(ℤ)).
3
3. The geometry: the quadratic form Q
Collect a basis as the columns of a matrix B. Its shape is captured by all pairwise inner products — the Gram matrix
Q = BᵀB.
• Diagonal entries bᵢ·bᵢ = squared lengths.
• Off-diagonal bᵢ·bⱼ = angles between vectors.
We call Q the quadratic form of the lattice. Such a Q is always real, symmetric, and positive-definite.
Q records everything metric — distances, angles, volumes — in one integer-friendly matrix.
4
4. Same shape = isometric
Two lattices are isometric if one is a rigid motion of the other: L′ = O·L for an orthogonal map O (a rotation / reflection).
Rigid motions preserve all lengths and angles. Isometric lattices are “the same lattice, dancing fancy.”
5
5. The Lattice Isomorphism Problem (LIP)
Given two lattices L and L′ (say, by their quadratic forms Q and Q′), decide whether they are isometric — and if so, find the map.
Simple to state. But the two lattices can be the same shape - yet look completely different in coordinates.
6
6. LIP in one equation
Write a basis as the columns of a matrix B; the quadratic form is Q = BᵀB. Change basis by a rigid motion O and an integer relabelling U: B ↦ B′ = O B U. Then take Gram matrices — the orthogonal part cancels:
LIP = given Q and Q′, find the unimodular U ∈ GLₙ(ℤ) with Q′ = Uᵀ Q U (or decide if one exists).
7
7. Module-LIP: LIP over a number field
So far, the scalars were plain integers ℤ.�Replace ℤ by the ring of integers 𝒪ₖ of a number field K — the same isometry problem, now for modules over 𝒪ₖ:
8
8. One problem, many fields
K is a design choice. Any number field K = ℚ(α) works — α a root of an irreducible polynomial f, with [K:ℚ] = deg f. Three families seen in lattice cryptography:
The choice of f is not cosmetic: it fixes how K sits inside the real and complex numbers —�and that, we will see, is what is known (so far) to make the isometry problem easy or hard.
9
9. The canonical embedding σ
K = ℚ(α) of degree d has exactly d field embeddings σ₁,…,σ_d : K ↪ ℂ — one per root of the minimal polynomial f (the roots are distinct, as f is irreducible over ℚ). Applying all d at once is the canonical (Minkowski) embedding σ:
Each σᵢ is real (root in ℝ) or complex (root off ℝ); complex ones come in conjugate pairs, so d = r₁ + 2r₂. σ sends 𝒪ₖ to a full-rank lattice in ℝ^d — this is what gives Module-LIP its geometry, with lengths ‖x‖² = Σ|σᵢ(x)|² and the involution ā acting placewise.
10
10. Three types of field — real vs. pseudo-real vs. complex
The signature (r₁, r₂) classifies K. The key fact for us: at a real place conjugation is the identity (σᵢ(x) ∈ ℝ, so σᵢ(x̄) = σᵢ(x)); at a complex place it is genuine complex conjugation.
11
11. Attack I — totally real fields (MPPW 2024)
Secret B = (a b ; c d) ∈ 𝒪ₖ²ˣ², public Gram matrix Q = B*B. Its (1,1) entry is g₁ = a·ā + b·b̄. When K is totally real, ā = a, so g₁ is a genuine sum of two squares:
12
12. Attack II — one real embedding is enough (APvW)
If K is not totally real, ā ≠ a and g₁ = a·ā + b·b̄ is no longer literally a² + b². But a single real embedding σ₁ : K → ℝ recovers that structure:
13
13. HAWK's escape into quaternion algebras
HAWK uses K = ℚ(ζ₂ᵏ): totally complex (zero real embeddings — Attack II dies) AND it already contains i = ζ₂ᵏ⁻² (so K(i) = K collapses — Attack I dies). With no real place and no quadratic K(i), the diagonal g₁ = a·ā + b·b̄ cannot be written as a norm from any commutative extension. The fix: a non-commutative one.
Rank-2 module-LIP over K now reduces to a principal-ideal problem in the quaternion algebra A = (−1,−1 / K⁺).�Generalizing Gentry–Szydlo to this non-commutative setting is open — which is one reason why HAWK still stands.
14
14. Where we go from here
Recap:
• A lattice has many bases; its shape is a quadratic form Q = BᵀB.
• LIP: are two forms Q, Q′ the same shape? (Q′ = UᵀQU?) Easy in low dimension, hard in high.
• Module-LIP: the same question over a number field K, with a Hermitian form Q = B*B.
• A real place (ā = a) breaks the form; HAWK is totally complex, so it escapes into a quaternion algebra — still open.
• The hardness is a cryptographic trapdoor — it underlies the post-quantum signature HAWK.
Three deeper topics — options to explore in our side session:
15
Option 1 · A PRACTICE TARGET
HawkPrime
A deliberately simplified, HAWK-like signature — a punching bag for students learning to attack lattice schemes.
HAWK PRIME: a training ground to learn some number theory
HawkPrime is a deliberately WEAKENED cousin of HAWK.
• It is built to be attackable — every angle of cryptanalysis I know of is left open on purpose, so you can actually land a hit and learn how.
• Goal: a safe training ground for the number theory behind lattice isomorphism — not a secure scheme.
⚠ It is AI-generated — and salted with deliberate errors.
• Many of its claims about the “state of the art” are intentionally WRONG.
• Your job is to read critically and catch them. Not everything is as it seems.
• (I enjoy escape rooms as an occasional past time)
• (Also, summoning my full NIST-cryptographer, I think learning “when” and “how” to call “B.S.” matters.)
Read it like a referee, not a student. (Also: This is exactly what students should learn to do anyway..)
Option 2 · A CANDIDATE ATTACK
The Guessing Game
A recent conditional cryptanalysis of HAWK — an exercise, and possibly something to extend.
Guessing Game: a recent attack attempt.. can you fix it?
Fantastic work by a group of English authors — a genuinely clever line of attack.
• Nelson, Limbrey, Ling, Mendelsohn, “Cryptanalysis of HAWK: a Guessing Game,” IACR ePrint 2026/1318.
• We should have a dedicated talk on this on Wednesday morning (..?)
• It is fascinating to see where this line of attack led…
• …and even more fascinating to see where it goes.
Option 3 · AT THE RESEARCH FRONTIER
An “unconditional” refutation of nrdPIP <= MLIP
A number-theoretic obstruction to complexity-theoretic reductions via a messy counting argument��P.S. “Provable security” seems not as much in-vogue these days in concrete cryptanalytic circles;�this research direction is a tailored, in-your-face refutation of “provable-security-non-enjoyers”��P.P.S. In totally unrelated news, apropos of nothing at all, “pure-ML-KEM for TLS” was selected to move to IETF standardization as an RFC a couple days ago.
A mass obstruction to the converse reduction nrd-PIP ≤ MLIP
We already have MLIP ≤ nrd-PIP (Chevignard–Mureau–Espitau–Pellet-Mary–Pliatsok–Wallet).�This is about the CONVERSE:
CLAIM: There should be no “nice” (Karp) reduction nrd-PIP ≤ MLIP.
• Mechanism — a mass obstruction: the induced-ideal map M ↦ 𝒪ᵣ(I_M) hits only a vanishingly thin set of quaternion maximal orders. Module-amenable density = O( h⁻(K) / Mass(B) ) → 0, super-exponentially in [F:ℚ].
So almost no nrd-PIP instance can be realized as an MLIP instance.
If it holds (or “morally close enough”), then two consequences:
• nrd-PIP is strictly HARDER than MLIP ⇒ attacking HAWK by designing concretely-effective quantum algorithms against quaternion principal-ideal problems is likely misplaced effort.
• The flip side is constructive: the number-theoretic structure conditions that this "MLIP → nrd-PIP" reduction exposes�point to NEW quaternion-algebra cryptographies: plausibly cryptographically-stronger than SIDH, CSIDH, LIP, …