Lattice-Based Cryptography

Lattice-based schemes are the workhorse of post-quantum standardization. Their security rests on problems about high-dimensional lattices — finding short or close vectors — that resist both classical and quantum attack while still allowing small keys, small ciphertexts, and fast arithmetic. NIST chose lattice schemes for the majority of its standard slots.

The Hard Problems

A lattice is the set of all integer combinations of a set of basis vectors — an infinite, regular grid of points in n-dimensional space. The core geometric problems are believed intractable as dimension grows:

Shortest Vector Problem (SVP) — find the shortest nonzero vector in the lattice.
Closest Vector Problem (CVP) — given a target point, find the nearest lattice point.

Modern schemes are not built directly on SVP/CVP but on average-case problems with proven reductions to these worst-case problems:

LWE (Learning With Errors) — recover a secret from noisy linear equations. Adding small random errors makes the system hard to solve.
Ring-LWE / Module-LWE — algebraically structured variants that shrink key sizes and speed up arithmetic by working over polynomial rings or modules.
SIS / Module-SIS (Short Integer Solution) — find a short nonzero integer combination of given vectors summing to zero; the basis for many signatures.
NTRU — an early ring-based assumption about short polynomials, underlying Falcon.

Note

The crucial guarantee is the worst-case-to-average-case reduction: under appropriate parameters and error distributions, there is a reduction relating LWE/Module-LWE to certain worst-case approximate lattice problems, so security on random instances can rest on the hardness of high-dimensional lattice problems. This gives lattice cryptography unusually strong theoretical backing.

Why Lattices Won Most Slots

Among all PQC families, lattice schemes offer the best overall balance:

Property	Lattice schemes
Key / ciphertext size	Small to moderate (kilobytes, not megabytes)
Signature size	Compact compared to hash- and code-based
Speed	Fast key generation, encapsulation, signing, verification
Versatility	Support both KEMs and signatures

The Lattice Standards

ML-KEM (formerly Kyber) — key encapsulation built on Module-LWE; FIPS 203.
ML-DSA (formerly Dilithium) — signatures built on Module-LWE and Module-SIS; FIPS 204.
Falcon (FN-DSA) — compact signatures built on NTRU lattices; standard pending.

Tradeoffs and Caveats

Lattice schemes are not without sharp edges:

Larger than ECC — keys and signatures are bigger than elliptic-curve equivalents, affecting bandwidth and handshake sizes.
Decryption failures — LWE-style KEMs add noise, so there is a tiny, carefully bounded probability that decapsulation fails. Parameters are chosen so this is negligible, but it must be analyzed.
Parameter care — security depends on precise noise distributions and modulus choices; sampling and implementation must be correct and constant-time to avoid side-channel leakage.

Because so much of the standardized ecosystem now depends on lattices, NIST deliberately keeps non-lattice backups (hash-based signatures, code-based KEMs) to preserve cryptographic diversity.

Standards & references

FIPS 203 (ML-KEM) — the Module-LWE key-encapsulation standard.
FIPS 204 (ML-DSA) — the Module-LWE / Module-SIS signature standard.
CRYSTALS-Kyber project — the lattice KEM behind ML-KEM.
CRYSTALS-Dilithium project — the lattice signature behind ML-DSA.
Resources — full standards register

ML-KEM →

The Module-LWE key encapsulation standard (FIPS 203).

ML-DSA →

The Module-LWE + Module-SIS signature standard (FIPS 204).

Falcon →

Compact NTRU-lattice signatures (FN-DSA).

格基密码

格基方案是后量子标准化的主力。其安全性建立在高维格问题之上——寻找最短或最近向量——这类问题对经典与量子攻击都具抗性同时仍能保持小密钥小密文与快速运算。NIST 在多数标准位置选用了格基方案。

困难问题

格是一组基向量所有整数组合构成的集合——n 维空间中无限延展的规则点阵。随着维度增长其核心几何问题被认为难以求解

最短向量问题 SVP——在格中寻找最短的非零向量。
最近向量问题 CVP——给定目标点寻找离它最近的格点。

现代方案并非直接建立在 SVP/CVP 上而是建立在已证明可归约到这些最坏情况问题的平均情况问题上

LWE 带误差学习——从带噪声的线性方程中恢复秘密。加入小的随机误差使方程组难以求解。
Ring-LWE / Module-LWE——具代数结构的变体通过在多项式环或模上运算来缩小密钥并加速运算。
SIS / Module-SIS 短整数解——寻找给定向量的短非零整数组合使其和为零这是许多签名的基础。
NTRU——一种早期基于环的短多项式假设支撑 Falcon。

注意

关键保证在于最坏到平均情况归约：在适当参数与误差分布下，LWE/Module-LWE 与某些最坏情形近似格问题之间存在归约关系；这使得随机实例上的安全性可以建立在高维格问题的困难性之上。这赋予格密码异常坚实的理论支撑。

格基为何赢得多数位置

在所有 PQC 家族中格基方案在整体上达到最佳平衡

属性	格基方案
密钥与密文体积	小到中等千字节级而非兆字节级
签名体积	相比哈希基与编码基更紧凑
速度	密钥生成封装签名验证均快
通用性	同时支持 KEM 与签名

格基标准

ML-KEM 原 Kyber——基于 Module-LWE 的密钥封装 FIPS 203。
ML-DSA 原 Dilithium——基于 Module-LWE 与 Module-SIS 的签名 FIPS 204。
Falcon FN-DSA——基于 NTRU 格的紧凑签名标准待发布。

权衡与注意事项

格基方案也并非毫无棱角

大于 ECC——密钥与签名比椭圆曲线对应方案更大会影响带宽与握手体积。
解密失败——LWE 型 KEM 引入噪声因此存在极小且经过严格界定的解封装失败概率。参数选取使其可忽略但必须经过分析。
参数谨慎——安全性依赖精确的噪声分布与模数选择采样与实现必须正确且常量时间以防侧信道泄露。

由于已标准化生态如此倚重格 NIST 有意保留非格备份哈希基签名编码基 KEM 以维系密码多样性。

标准与参考

FIPS 203 ML-KEM — 基于 Module-LWE 的密钥封装标准。
FIPS 204 ML-DSA — 基于 Module-LWE 与 Module-SIS 的签名标准。
CRYSTALS-Kyber 项目 — ML-KEM 所源自的格 KEM。
CRYSTALS-Dilithium 项目 — ML-DSA 所源自的格签名。
资源链接 — 完整标准登记册