什么是基于格的密码学？后量子安全简明指南

基于格的密码学（lattice-based cryptography）是现代密码学的一个分支，其安全性来自在高维空间点阵上定义的数学难题。它被广泛认为是保护数字系统、抵御量子计算新兴能力的最有前景的基础之一，也是后量子密码学（post-quantum cryptography）研究的核心支柱。

基于格的密码学的意义不限于量子抗性（quantum resistance）。它高效、灵活，适合在区块链、安全消息传递、数字签名和加密通信等实际场景中部署。政府、学术研究人员和科技公司已在为向后量子安全标准过渡作准备，而美国国家标准与技术研究院（NIST）选定的许多标准化算法都以基于格的方案为核心。

量子威胁下的密码学

现代公钥密码学（public key cryptography）建立在少数几个数学假设之上。RSA（Rivest–Shamir–Adleman）依赖大整数分解的困难性，ECC（椭圆曲线密码学，Elliptic Curve Cryptography）则依赖使用经典计算机求解椭圆曲线上离散对数（discrete logarithm）问题的困难性。数十年来，即使数学家和计算机科学家不断努力，这些问题仍难以破解，因而构成了安全互联网通信的支柱。

1994 年，彼得·肖尔（Peter Shor）证明，足够强大的量子计算机可以高效求解整数分解和离散对数问题，这一基础由此受到挑战。肖尔算法（Shor’s algorithm）使这些曾经难以处理的问题，在成熟量子硬件出现后成为可以实际完成的任务。

后量子密码学指的是即使大规模量子计算机成为现实，也旨在保持安全的密码系统。这些系统依赖尚无已知高效经典或量子解法的数学问题。研究人员已经探索了多个候选类别，包括基于哈希的密码学、基于编码的密码学、多变量多项式密码学，以及基于格的密码学。

在这些方案中，基于格的密码学结合了坚实的理论困难性保证、实际效率，以及对多种密码任务的适应能力，因此格外突出。这也解释了为什么 NIST 后量子密码学标准化流程选中的许多算法都采用基于格的构造。

什么是基于格的密码学？

基于格的密码学建立在一种称为格（lattices）的数学结构之上。可以将格想象为延伸到多个维度的规则点阵。在二维空间中，它类似于无限延伸、间距均匀的点的排列。在更高维度中，这种结构变得抽象，但基本原理相同。

基于格的方案的安全性，来自求解这些格中某些计算问题的困难性。例如，寻找极短的向量，或确定哪个格点距离空间中的给定点最近。这些问题很容易描述，但随着维数增加，求解会变得极其困难。

一个有助于形成几何直觉的想象是：有一张庞大的多维网格，每个交点代表一个格点。给定一个稍微偏离网格的点，维数越高，确定最近格点就越复杂。可能的候选点数量迅速增加，辨别正确的那个点需要大量计算。

这一几何视角说明了为什么格问题被认为难以求解。其复杂度随维数急剧增长，即使对量子计算机而言，也没有已知的高效捷径。

基于格的数字签名与加密

区块链无限期保存数据，而在量子计算的背景下，这种永久性带来了一项独特弱点。如果量子技术成熟，今天使用椭圆曲线签名签署的交易，可能在数十年后变得可以伪造。

基于格的密码学既支持后量子加密，也支持后量子数字签名，因此对现代安全架构而言用途广泛。在基于格的签名方案中，秘密的格参数让签名者能够生成可验证的签名，而不泄露私密信息。验证者只需要使用从同一格结构导出的公开参数。

这些签名虽然通常比经典方案更大，却具备一项关键优势：即使量子计算机可以破解 RSA 和椭圆曲线签名，它们仍然安全。对区块链、软件分发网络和长期验证基础设施等系统而言，这种持久性至关重要。

基于格的加密方案采用一种相关机制。发送者利用公开的格参数，结合经过精心构造的噪声，对消息进行编码；只有预定接收者才能使用秘密密钥去除这些噪声。这样形成的加密过程高效、具有严格的数学基础，能够抵御经典与量子攻击。

由于格可以在统一的数学框架内同时支持加密和签名，系统设计者能够构建完整的后量子安全技术栈，无需依赖混合或不兼容的密码学假设。

效率与实际部署考量

基于格的密码学发展势头日益强劲，与其良好的性能密切相关。与许多其他后量子候选方案相比，格方案计算速度快、内存需求适中，而且能在标准硬件上高效实现。因此，它们适合服务器、个人设备、云基础设施，甚至资源受限的嵌入式系统。

主要代价是，与经典密码系统相比，公钥和签名的尺寸更大。不过，现代存储和带宽能力在很大程度上抵消了这一缺点，尤其是在考虑到长期量子抗性的收益时。

此外，格运算非常适合并行处理和现代 CPU 架构，能够通过切实可行的优化进一步提高性能。这些特征推动了探索后量子升级的区块链平台和安全通信系统对格方案进行实验性与早期应用。

基于格的密码学与其他后量子方案的比较

NIST 的后量子密码学计划始于 2016 年，经过广泛评估，最终选定了多项基于格的标准。ML-KEM（基于模格的密钥封装机制，Module-Lattice-Based Key-Encapsulation Mechanism）源自 Kyber，被选用于密钥封装（key encapsulation）与加密。源自 Dilithium 的 ML-DSA（基于模格的数字签名算法，Module-Lattice-Based Digital Signature Algorithm）以及 Falcon 则被选用于数字签名。这些标准将格密码学规范化，以支持全球部署。

其他方法仍然是有价值的选择，例如 SPHINCS+ 这类基于哈希的方案，以及基于编码的密码学。不过，基于格的系统通常在性能、灵活性和多种密码任务的广泛适用性之间提供更均衡的组合。

结语

基于格的密码学体现了安全系统设计的根本转变：从易受量子攻击的数论假设，转向即使在量子计算条件下仍难以求解的几何与代数问题。坚实的数学基础、实际效率，以及在加密、数字签名和高级密码学构造中的通用性，使其成为后量子安全的领先方案。

随着量子计算从理论走向工程现实，对后量子密码学的需求日益迫切。基于格的方案提供了一条可信、研究充分且已标准化的发展道路。在为量子技术冲击作准备的数字世界中，格已不再只是实验性概念，而是下一代密码安全的基础组成部分。