Lattice-Based Cryptography: How Learning With Errors Powers the Post-Quantum Future

A system of linear equations over integers has well-known efficient solutions — Gaussian elimination, for example. The LWE problem makes this system hard by adding a small random error to each equation. Without the error, the system is easy to solve. With it, recovering the secret vector becomes computationally intractable even for polynomial-time quantum algorithms.

Formal security reductions show that breaking LWE with high probability is at least as hard as solving worst-case instances of certain lattice problems, specifically the Shortest Vector Problem (SVP) on random lattices. No known algorithm — classical or quantum — solves these problems efficiently in high dimensions. The lattice-based survey by Khan et al. notes that this dual grounding — both quantum resistance and provable hardness reductions — is why lattice-based schemes dominate the NIST standardization outcomes over competing families such as code-based, multivariate, and isogeny-based cryptography.

Module-LWE, the variant used in ML-KEM and ML-DSA, operates over polynomial rings structured as modules, giving a balance between the high security of plain LWE and the compact key sizes needed for practical deployment. ML-KEM-768, the recommended parameter set for most applications, produces public keys of 1,184 bytes and ciphertexts of 1,088 bytes — larger than RSA-2048 (256-byte keys) but manageable for most protocols.

ML-KEM, specified in FIPS 203, is a key encapsulation mechanism built on a public-key encryption scheme that is then transformed using the Fujisaki-Okamoto (FO) transform to achieve chosen-ciphertext security. The key generation procedure samples small random polynomials, computes a matrix-vector product over the polynomial ring, and adds LWE-style noise. The resulting public key and a corresponding secret key allow the holder of the public key to encapsulate a random session key, producing a ciphertext that only the secret-key holder can decapsulate.

The design choice that drives both performance and security risk is polynomial multiplication. Rather than multiplying polynomials coefficient by coefficient — an O(n²) operation — ML-KEM uses the Number Theoretic Transform to perform multiplication in O(n log n). In both software and hardware, the NTT accounts for the dominant portion of execution time and energy consumption.

The Number Theoretic Transform is a finite-field analogue of the fast Fourier transform. For a degree-n polynomial over the integers modulo a prime q — in ML-KEM, n = 256 and q = 3329 — the NTT converts a polynomial into its pointwise representation, enabling coefficient-wise multiplication, before an inverse NTT converts back. This is the inner loop that runs in every key generation, encapsulation, and decapsulation.

From a performance standpoint, the NTT is the primary optimization target across all platforms. A 2025 FPGA architecture paper demonstrated a fully parallelized NTT for ML-DSA and ML-KEM achieving up to 24× speedup over prior FPGA implementations by eliminating RAM bottlenecks and feeding all polynomial coefficients simultaneously. A 22nm ASIC implementation of ML-KEM achieved over 1.3 million key operations per second — a throughput level sufficient for large-scale server deployments.

From a security standpoint, the NTT is the primary side-channel leakage surface. The pointwise multiplications and additions in the NTT correlate with secret key material, and correlation power analysis (CPA) attacks on the NTT have been demonstrated against CRYSTALS-Kyber on ARM Cortex-M4 microcontrollers using as few as 200 power traces. This is not a theoretical concern: it is an active research area with demonstrated attacks, and any embedded or IoT deployment of ML-KEM must account for it in its threat model.

A comprehensive survey of lattice-based PQC implementation work across platforms finds that each offers distinct trade-offs. On CPUs, AVX2 and ARM Neon SIMD intrinsics are used to vectorize the NTT butterfly operations, with the reference C implementation already performing adequately for most server workloads. On GPUs, the parallel structure of the NTT maps well to SIMD execution, but the memory-bandwidth requirements and launch overhead mean the benefit is primarily in batch-processing scenarios.

FPGAs offer reconfigurability and low latency, making them attractive for TLS terminators, hardware security modules, and infrastructure that must support multiple parameter sets. ASIC implementations sacrifice flexibility for throughput and energy efficiency, and are appropriate for high-volume embedded applications, network appliances, or smart-card deployments where the algorithm is unlikely to change.

The survey concludes that performance and scalability barriers remain for constrained environments — IoT devices, microcontrollers, and low-power edge nodes — and that side-channel hardening adds overhead that further strains constrained targets. Hardware/software co-design, where the NTT and rejection sampling are offloaded to dedicated logic, is the approach most likely to close that gap.

Evaluate your NTT execution environment. If you are deploying ML-KEM or ML-DSA on a constrained device — embedded controller, smart card, IoT node — the NTT's power and timing behaviour is a security surface, not just a performance metric. Constant-time implementations and masking countermeasures are not optional in these environments.

Match implementation platform to throughput requirements. Software on a modern server CPU is sufficient for most application-layer workloads. Hardware acceleration becomes necessary at network-appliance scale or in latency-sensitive real-time protocols.

Plan for side-channel hardening in sensitive deployments. Power analysis attacks on ML-KEM have been demonstrated. Any deployment where an adversary can measure power consumption or electromagnetic radiation — which includes most unshielded embedded hardware — requires countermeasures beyond the algorithm specification.

Do not treat the algorithm as finished. The NTT-based lattice family is eight years old as a competition entry. The cryptanalytic community's attention is intensifying. Crypto-agility, the ability to swap algorithms without re-architecting systems, is a design requirement, not a feature.