格密码

定义

格密码（Lattice-based Cryptography）以高维格（lattice，即由整数线性组合生成的点阵）上的计算难题为安全基础，是当前最重要的后量子密码路线。

数学基础

核心难题包括最短向量问题（SVP）、最近向量问题（CVP），以及更适合构造方案的带误差学习问题（LWE）与其环/模变体（Ring-LWE、Module-LWE）。这些问题目前没有已知的高效量子算法，且部分方案具有"最坏情况到平均情况"的安全归约，这在密码学中相当罕见。

代表方案

NIST 标准 ML-KEM（Kyber）和 ML-DSA（Dilithium）均属格密码；Gentry 于 2009 年构造的第一个全同态加密方案同样基于理想格，如今的 BGV、BFV、CKKS 等同态方案也建立在 LWE 之上。

优缺点

优点是运算以多项式乘加为主、速度快、可构造的原语丰富（加密、签名、同态、函数加密等）；缺点是密钥和密文尺寸明显大于椭圆曲线方案，且误差参数选取复杂，实现需要谨慎。