Expert technical analysis on quantum computing, post-quantum cryptography, and quantum-safe infrastructure for Ireland and the EU.
Post-Quantum Cryptography | Lattice Mathematics | Ireland
Meta Description: Lattice-based cryptography explained in depth by Michael English, Irish CTO. The mathematics behind ML-KEM, ML-DSA, and why lattice problems resist quantum attacks. Technical guide for Ireland/EU.
Target Keywords: lattice-based cryptography explained, lattice cryptography Ireland, LWE problem post-quantum, quantum-safe lattice mathematics, lattice cryptography EU, Michael English lattice cryptography
When the dust settled on NIST's eight-year post-quantum cryptography competition, one mathematical structure dominated: lattices. Of the four finalised and forthcoming standards — ML-KEM (FIPS 203), ML-DSA (FIPS 204), SLH-DSA (FIPS 205), and FALCON (FN-DSA, FIPS 206) — three are lattice-based. The fourth, SLH-DSA, uses hash functions whose collision resistance is itself provably related to certain lattice properties.
Understanding why lattices are the go-to foundation for post-quantum cryptography requires understanding both the mathematics of lattices and why the hard problems they give rise to resist quantum speedup.
A lattice (in the cryptographic sense) is a discrete subgroup of ℝ^n — an infinite, regularly-spaced grid of points in n-dimensional space.
Formally, given n linearly independent vectors b₁, b₂, ..., bₙ ∈ ℝ^n (called basis vectors), the lattice Λ is:
Λ(b₁,...,bₙ) = { Σᵢ xᵢbᵢ : xᵢ ∈ ℤ }
All integer linear combinations of the basis vectors.
In two dimensions, this looks like a tilted, stretched grid. In 512 dimensions (as used in ML-KEM-768), this is a 512-dimensional grid of points in 512-dimensional space — geometric intuition fails, but the algebraic structure remains precise and computationally tractable.
Shortest Vector Problem (SVP): Given a lattice Λ, find the shortest non-zero vector in Λ.
SVP: find v ∈ Λ \ {0} such that ||v|| is minimised
In two dimensions this is trivial. In n dimensions with large n, it becomes exponentially hard. The best classical algorithms (LLL lattice basis reduction, BKZ) have complexity approximately O(2^(n/30)) for exact SVP — exponential but with a small constant.
Closest Vector Problem (CVP): Given a lattice Λ and a target point t ∈ ℝ^n, find the lattice point closest to t.
CVP: find v ∈ Λ such that ||v - t|| is minimised
CVP is at least as hard as SVP and is generally considered the harder problem. Most lattice cryptographic constructions reduce security to approximate versions of CVP and SVP.
The most important lattice problem for cryptography is Learning With Errors (LWE), introduced by Oded Regev in his landmark 2005 paper.
Choose:
Compute: b = As + e mod q
Decision LWE: Distinguish (A, b) from (A, u) where u is uniformly random.
Search LWE: Given (A, b), find s.
Regev proved that solving LWE (even with quantum computers) is at least as hard as solving worst-case instances of certain lattice problems in n dimensions — specifically, Shortest Independent Vectors Problem (SIVP_γ) for super-polynomial approximation factors γ.
This is a remarkable hardness guarantee: if you can solve LWE, you can solve the hardest possible n-dimensional lattice problems. No efficient quantum algorithm is known for these lattice problems.
The error vector e "smears" the product As across a small neighbourhood. Without knowing s, distinguishing this smeared structure from random noise requires solving a problem equivalent to finding very short vectors in a high-dimensional lattice — something even quantum computers cannot do efficiently.
Standard LWE uses matrices over ℤ_q. For efficiency, ML-KEM and ML-DSA use Module LWE (MLWE), which operates over polynomial rings.
Define Rq = ℤq[x] / (x^n + 1) — polynomials of degree < n with coefficients in ℤ_q, where arithmetic is modulo the polynomial x^n + 1.
For ML-KEM-768: n = 256, q = 3329, k = 3 (module rank)
The module lattice uses matrices and vectors of polynomials rather than integers. A single polynomial multiplication in R_q can be computed in O(n log n) using Number Theoretic Transform (NTT) — much faster than the O(n²) required for direct polynomial multiplication.
The Number Theoretic Transform (analogous to Fast Fourier Transform but over finite fields) enables:
NTT multiplication of degree-256 polynomials:
Direct: ~65,536 multiplications
NTT: ~4,096 multiplications + 2×256 NTT operations ≈ 2,048 total
This ~30× speedup is why lattice-based cryptography achieves the practical performance necessary for deployment (67 microseconds for ML-KEM-768 key generation).
ML-DSA (for signatures) relies on an additional lattice problem: Module Short Integer Solution (MSIS).
Given a random matrix A ∈ R_q^{k×ℓ}, find a short non-zero vector z such that Az = 0 mod q.
The "short" constraint is crucial — without it, solutions trivially exist. With it, finding z is equivalent to finding short vectors in a high-dimensional module lattice.
ML-DSA uses a signature scheme based on Fiat-Shamir with Aborts:
The abort step is crucial for security — without it, the response z = y + cs would reveal information about the secret s through statistical analysis of multiple signatures. The rejection sampling ensures all signature responses are statistically independent of s.
Before LWE-based constructions, NTRU (N-th degree TRUncated polynomial ring) was the leading lattice-based encryption scheme. NTRU was proposed by Hoffstein, Pipher, and Silverman in 1996 and has been studied for nearly 30 years.
FALCON (the forthcoming FIPS 206 standard) is based on NTRU lattices, specifically the GPV framework applied to NTRU. FALCON offers significantly smaller signatures than ML-DSA by exploiting the rich algebraic structure of NTRU lattices for tight parameter selection.
FALCON trade-off: Smaller signatures but more complex, precision-sensitive implementation. The Gaussian sampling required in FALCON signing must be implemented with extreme care to avoid side-channel attacks from floating-point timing differences.
The key question: why can't Shor's algorithm or Grover's algorithm break lattice problems efficiently?
Shor's algorithm exploits the hidden subgroup problem (HSP) structure in RSA and ECC. Specifically:
Lattice problems do NOT have this structure. SVP and CVP do not reduce to abelian HSP. The best quantum algorithm for SVP/CVP (using quantum speedup in the BKZ algorithm's sieving subroutine) provides at most a quadratic speedup — reducing complexity from O(2^(n)) to O(2^(n/2)).
For ML-KEM-768, which targets 2^128 quantum security, the module lattice dimension is chosen so that the best quantum SVP attack requires approximately 2^161 operations — a substantial margin above the security target even accounting for quantum speedup.
Grover's algorithm provides quadratic speedup for unstructured search but lattice problems are not unstructured. The algebraic structure of lattice problems does not yield to Grover in any known way.
Not all lattice problems are equally well-understood. Here is the hardness hierarchy relevant to ML-KEM and ML-DSA:
Worst-case SVP/SIVP (hardest)
↓ (Regev reduction, 2005)
Search LWE
↓ (public-key encryption)
ML-KEM security
↓ (implies)
Decision LWE
↓ (direct construction)
Pseudorandom generators
The chain means: breaking ML-KEM requires solving LWE, which requires solving worst-case lattice problems. This is a much stronger security guarantee than RSA, where breaking RSA requires only solving random-instance factoring (not worst-case).
For most Irish business applications, use ML-KEM-768 (Level 3). Only select Level 5 for:
All lattice cryptography must be implemented in constant time to prevent timing side-channels:
Use vetted implementations: The CRYSTALS team's reference implementation at pq-crystals.org and the Open Quantum Safe project's liboqs are audited and constant-time. Do not roll your own.
ML-KEM uses a compact binary serialisation format. Public keys are not self-describing — context must specify which parameter set (ML-KEM-512, 768, or 1024) a key belongs to. Design key management systems to explicitly encode algorithm parameters.
Deploying lattice-based cryptography in blockchain contexts presents unique challenges:
EVM gas costs for ML-DSA verification: Verifying an ML-DSA-65 signature on-chain would cost approximately 50-100× more gas than ECDSA P-256, due to the larger signature size and polynomial arithmetic required. We evaluate on-chain verification of ML-DSA as impractical until ZK-proof-based aggregation reduces costs.
Off-chain signature chains: We use ML-DSA-65 for signing carbon credit certificates and audit trail entries in our off-chain data pipeline. The signed records are hashed and anchored on-chain via ERC-4337 user operations, providing quantum-safe authenticity for the underlying documents without on-chain ML-DSA verification overhead.
Account abstraction as quantum bridge: ERC-4337's abstract validation logic enables us to deploy smart contract wallets that accept ML-DSA signatures today, with migration to full on-chain ML-DSA verification as Ethereum protocol-level PQC support matures.
Lattice-based cryptography represents one of the deepest intersections of pure mathematics and applied security engineering in the history of cryptography. The hard problems on high-dimensional lattices — SVP, CVP, LWE, MSIS — provide security guarantees that have survived decades of classical and quantum cryptanalytic scrutiny.
ML-KEM and ML-DSA translate these mathematical foundations into practical, efficient, standardised algorithms that Irish and EU organisations can deploy today. The performance is excellent, the security margins are generous, and the open-source ecosystem is mature.
Lattice mathematics isn't just the future of cryptography — it's the present. The question for Irish businesses is not whether lattice-based cryptography will protect their systems but whether they'll deploy it proactively or be forced into it reactively by regulatory requirements.
Michael English is Co-Founder & CTO of IMPT.io. He has deployed post-quantum cryptography in production blockchain infrastructure serving EU carbon markets. Based in Clonmel, Co. Tipperary, Ireland.
Keywords: lattice-based cryptography Ireland, LWE problem post-quantum, ML-KEM mathematics explained, lattice cryptography EU, quantum-safe lattice problems, CRYSTALS cryptography Ireland, Michael English lattice post-quantum