格密码学

2026年10月

格密码学（Lattice-based Cryptography）是一类基于数学中格（Lattice）难题构建的公钥密码系统，因其在抗量子计算攻击方面的强大潜力，被视为后量子密码学（Post-Quantum Cryptography）的重要候选方案之一。

什么是格

在数学中，格是由一组线性无关的向量通过整系数线性组合生成的离散点集。例如，在二维平面上，若有两个不共线的向量 v₁ 和 v₂，则所有形如 a·v₁ + b·v₂（其中 a, b 为整数）的点构成一个格。格结构具有高度的几何对称性和代数复杂性，使得某些与之相关的计算问题（如最短向量问题 SVP、最近向量问题 CVP）在高维空间中极难求解。

核心困难问题

格密码学的安全性依赖于若干被广泛研究的计算难题，主要包括：

最短向量问题（SVP）：在给定格中找到长度最短的非零向量。
最近向量问题（CVP）：给定一个不在格中的目标点，找到格中最接近该点的向量。
带错误学习问题（LWE）：从带有少量噪声的线性方程组中恢复秘密向量，已被证明在量子和经典模型下均难解。

这些问题即使在量子计算机面前也未发现高效算法，因此成为构建安全密码协议的理想基础。

应用与优势

格密码学不仅可用于构造加密、数字签名和密钥交换等传统密码原语，还能支持高级功能，如全同态加密（FHE）和属性基加密（ABE）。其主要优势包括：

抗量子安全性：目前没有已知的量子算法能在多项式时间内破解基于格的密码系统。
结构简洁：许多格密码方案基于简单的线性代数操作，易于实现和优化。
功能丰富：天然支持复杂密码学构造，推动隐私保护计算的发展。

随着 NIST 后量子密码标准化进程的推进，多个基于格的方案（如 CRYSTALS-Kyber 和 CRYSTALS-Dilithium）已被选为标准或备选方案，标志着格密码学正逐步走向实际部署。