Lattice Cryptography Beyond FHE

Lattice-based cryptography is not a single algorithm. It is a family of mathematical constructions built on the difficulty of finding short vectors in high-dimensional lattices -- a problem that has resisted solution for centuries in mathematics and decades in computer science. When NIST selected its post-quantum cryptography standards in 2024, lattice-based schemes dominated: ML-KEM (FIPS 203) for key encapsulation, ML-DSA (FIPS 204) for digital signatures, and FALCON as an additional signature standard. A fourth standard, SLH-DSA (FIPS 205), uses hash functions rather than lattices specifically to provide diversity. The overwhelming selection of lattice schemes was not coincidence. It was the result of three decades of cryptanalytic effort that has failed to find efficient attacks against well-parameterized lattice problems.

Most discussions of lattice cryptography focus on fully homomorphic encryption. This is understandable -- FHE is the most dramatic application, allowing computation on encrypted data. But lattice problems underpin far more of the modern cryptographic landscape than FHE alone. Key encapsulation mechanisms, digital signatures, identity-based encryption, attribute-based encryption, and functional encryption all build on lattice hardness assumptions. Understanding the lattice landscape is essential for any organization planning its post-quantum cryptographic architecture, because the choice of which lattice problem to rely on determines the security guarantees, performance characteristics, and failure modes of the entire system.

This article maps the lattice cryptography landscape as it exists in 2026: which problems underpin which standards, how the problems relate to each other, where the reduction chains are strong and where they are not, and why H33 uses three independent hardness assumptions rather than relying on any single lattice construction.

The Core Problem: Learning With Errors

The Learning With Errors (LWE) problem, introduced by Oded Regev in 2005, is the foundation on which most modern lattice cryptography is built. The problem is deceptively simple to state: given a matrix A, a secret vector s, and a vector b = As + e where e is a small error vector, recover s. Without the error term, this is just linear algebra -- Gaussian elimination solves it immediately. The error term makes the problem hard. The noise obscures the linear relationship between A, s, and b, and the best known algorithms for recovering s run in exponential time as the dimension increases.

LWE has a critical property that most other hardness assumptions lack: a worst-case to average-case reduction. Regev showed that solving LWE on average (for random instances) is at least as hard as solving certain worst-case lattice problems (like the Shortest Vector Problem, or SVP). This means an algorithm that solves LWE efficiently would automatically solve the hardest lattice instances, which decades of mathematical effort have failed to accomplish. This reduction is what gives the cryptographic community confidence in LWE-based security: it connects to deep mathematical structure, not just empirical difficulty.

Ring-LWE and Module-LWE

Plain LWE has a practical limitation: the public key contains the matrix A, which is large (quadratic in the security parameter). Ring-LWE (RLWE) addresses this by replacing the unstructured matrix with a structured object defined over a polynomial ring. The structure reduces key sizes by a factor equal to the ring dimension while maintaining security under the Ring-LWE assumption. Module-LWE (MLWE) is a generalization that sits between LWE and RLWE. Instead of a single polynomial ring element, MLWE uses a small module (a matrix of ring elements). MLWE provides a smooth tradeoff between security and efficiency: increasing the module rank increases security at a linear cost.

NIST's ML-KEM and ML-DSA are both based on MLWE, which is why their parameter sets are specified as (k, n) pairs where k is the module rank and n is the ring dimension. H33's FHE implementations (BFV and CKKS) use RLWE directly. The polynomial ring structure enables the SIMD encoding that packs 4,096 plaintext values into a single ciphertext. The digital signature ML-DSA-65, used in H33's three-key signer, is based on MLWE with module rank k=6. These are different instantiations of related but not identical lattice problems.

NTRU: A Different Lattice Structure

NTRU, first proposed by Hoffstein, Pipher, and Silverman in 1996, predates LWE by nearly a decade. It is based on a different lattice structure: the NTRU lattice, which arises from the relationship between two short polynomials in a polynomial ring. The hardness assumption is that given a public key h = f/g (where f and g are short polynomials and the division is in the polynomial ring), it is hard to recover f and g. This is related to the Shortest Vector Problem in the NTRU lattice, but the reduction chain is different from the one connecting LWE to lattice problems.

FALCON, the NIST additional signature standard, is based on NTRU. FALCON uses a hash-and-sign paradigm with a trapdoor based on NTRU lattice structure, combined with a fast Fourier sampling technique for producing signatures. FALCON signatures are shorter than ML-DSA signatures (690 bytes vs 3,309 bytes for comparable security), but the signing algorithm requires careful constant-time floating-point arithmetic, which makes implementation more challenging and more prone to side-channel vulnerabilities if not implemented correctly.

The critical point about NTRU is that it rests on a different hardness assumption than MLWE. While both are lattice problems, and both are believed to be hard, they are not known to be equivalent. A breakthrough in solving MLWE problems would not automatically break NTRU, and vice versa. This independence is what makes the combination of ML-DSA (MLWE) and FALCON (NTRU) stronger than using either alone.

Lattice Problems in FHE

Fully homomorphic encryption schemes use lattice problems differently than signature and key encapsulation schemes. In FHE, the lattice structure enables the homomorphic property: the noise added for security grows with each computation, and the lattice geometry determines how many operations you can perform before the noise overwhelms the signal. BFV and CKKS are based on RLWE, where the ring structure provides both the SIMD encoding capability and the noise management framework.

The security of FHE ciphertexts is based on the hardness of RLWE: an adversary who sees the ciphertext cannot distinguish it from random, and therefore cannot extract any information about the plaintext. The parameters are chosen so that the best known lattice attacks require more computation than the target security level allows. H33's production parameters use N=4096 with a 56-bit modulus Q, which provides 128-bit security against both classical and quantum attackers.

TFHE uses a different lattice structure: TLWE (Torus LWE), which is LWE defined over the real torus. The programmable bootstrapping operation in TFHE involves a lattice-based blind rotation that simultaneously refreshes noise and applies a lookup table function. The security of TFHE rests on TLWE hardness, which is related to but not identical to standard LWE.

The Reduction Landscape

The relationships between lattice problems form a hierarchy of reductions. At the bottom are worst-case problems like SVP (Shortest Vector Problem) and SIVP (Shortest Independent Vectors Problem), which are known to be NP-hard for exact solutions. LWE reduces to these worst-case problems: solving average-case LWE implies solving worst-case lattice problems. RLWE has a reduction to worst-case problems in ideal lattices, though the reduction is somewhat weaker because it relies on the structure of specific number fields. MLWE sits between LWE and RLWE in the reduction hierarchy.

NTRU does not have a clean worst-case reduction like LWE; its security is based on the assumption that the specific lattice problems arising from NTRU key generation are hard, supported by decades of cryptanalytic effort but not by a formal reduction to a worst-case problem. This reduction landscape matters for long-term security planning. If a quantum algorithm exploits ideal lattice structure (breaking RLWE), it would not automatically break MLWE or NTRU. The lattice family is not monolithic.

Why Three Independent Hardness Assumptions

H33 uses three independent mathematical foundations for its attestation layer: MLWE lattices (ML-DSA-65), NTRU lattices (FALCON-512), and stateless hash functions (SLH-DSA-SHA2-128f). This is a deliberate architectural decision based on the reduction landscape.

If MLWE is broken, ML-DSA signatures become forgeable, but FALCON (NTRU) and SLH-DSA (hash) remain secure. If NTRU is broken, FALCON becomes forgeable, but ML-DSA (MLWE) and SLH-DSA remain secure. If collision-resistant hash functions are broken, SLH-DSA becomes forgeable, but ML-DSA and FALCON remain secure. The attestation fails only if all three assumptions fail simultaneously. This defense-in-depth at the mathematical level is distinct from defense-in-depth at the implementation level.

The H33-74 substrate distills the full three-family attestation into 74 bytes while preserving all three hardness assumptions. This is distillation, not compression -- the mathematical guarantees of the original signatures are preserved in the 74-byte form. The substrate survives any single-family cryptographic break, providing long-term security for data that must remain attestable for decades.

Beyond Signatures and FHE

Lattice cryptography enables capabilities that have no classical equivalent. Identity-based encryption (IBE) allows anyone to encrypt a message using a recipient's identity as the public key. Attribute-based encryption (ABE) enables policies like "decrypt only if the reader is a doctor AND the patient's primary care physician." Functional encryption allows computing specific functions on encrypted data while revealing only the function output. All of these build on lattice hardness assumptions.

H33's roadmap includes lattice-based functional encryption for the AI compliance use case: allowing auditors to compute specific compliance metrics on encrypted data while provably preventing them from learning anything else. Lattice cryptography is the only known mathematical framework that supports FHE, digital signatures, key exchange, IBE, ABE, and functional encryption simultaneously. This universality is why lattices dominate the post-quantum cryptographic landscape and why understanding the distinctions between lattice variants matters for architectural decisions.

Practical Implications

For organizations designing post-quantum architectures, the lattice landscape has several practical implications. First, do not treat all lattice-based schemes as equivalent. MLWE, NTRU, and RLWE are different problems with different security characteristics. A portfolio that uses multiple lattice problems provides better security than one that concentrates on a single problem. Second, monitor the cryptanalytic landscape. The best known attack complexities change as new algorithms are published. Third, include at least one non-lattice assumption in your portfolio. SLH-DSA (FIPS 205) provides a hash-based fallback that survives even a complete break of all lattice constructions.

H33's production pipeline processes 2,293,766 authentications per second at 38 microseconds each, demonstrating that multi-family post-quantum cryptography is not a theoretical exercise but a production reality. The performance overhead of using three families instead of one is bounded by the batch signing architecture, where all three signatures are generated in a single pipeline stage.

Contact support@h33.ai for guidance on lattice-based cryptographic architecture for your specific use case.