传统公钥密码体系如RSA和椭圆曲线密码，其安全性依赖大整数分解与离散对数问题的困难性。然而量子计算机上运行的Shor算法可以在多项式时间内解决这两类问题，直接动摇当前互联网信任体系的根基。格密码利用高维空间中格结构的计算困难性来构造加密、签名与密钥交换协议，已被NIST列为后量子密码标准化的主要方向。本文系统梳理格密码的核心困难问题、代表性方案以及工程实现中的关键优化。
一、格的定义与基础困难问题
格是n维欧氏空间中离散的加法子群。更直观地说，给定一组线性无关的基向量，格就是这些基向量所有整数线性组合构成的集合。例如在二维平面上，两个不共线的向量可以生成一个由无穷多个离散点组成的格子，这些点均匀分布在平面上，但彼此之间保持最小距离。格的结构完全由基向量决定，但同一个格可以拥有无数组不同的基，这正是格密码安全性的重要来源。
格上最核心的困难问题是最短向量问题SVP和最近向量问题CVP。SVP要求在一个给定的格中找到一个长度最短的非零向量，CVP则要求找到距离某个给定空间点最近的格向量。在高维情况下，尤其是维度达到几百甚至上千时，这两个问题的精确求解都需要指数级时间。实际密码方案通常使用它们的近似版本，例如要求在多项式因子的范围内找到接近最短的向量，这种近似版本仍然被认为是困难的。
另一个重要的格问题是短整数解问题SIS。SIS给定一个随机矩阵A，要求找到一个足够短的整数向量x，使得Ax等于零向量。SIS问题的困难性可用于构造抗碰撞哈希函数和数字签名。与SIS对偶的ISIS问题则用于构造加密方案。这些问题共同构成了格密码的理论基础。
二、LWE问题与最坏情况归约
Oded Regev在2005年提出的误差学习问题LWE是目前格密码中最核心的困难假设。LWE问题可以这样理解：给定一个随机矩阵A和一个向量b，已知b约等于As加上一个小误差向量e，即b等于As加e，要求恢复秘密向量s。由于误差e的存在，直接使用高斯消元等线性代数方法无法精确求解，而误差又不足以被完全忽略。理论和实验都表明，LWE问题在量子计算机上同样难以求解。
LWE的重要性不仅在于它看起来很难，更在于它具有从最坏情况到平均情况的归约。也就是说，如果存在一个算法能够以不可忽略的概率解决随机生成的LWE实例，那么就可以利用这个算法解决格上某些最坏情况下的困难问题。这种归约给出了很强的安全性保证：随机困难实例的难度与最困难的实例相当，避免了某些密码假设只对特殊构造的实例成立的问题。
原始的LWE问题公钥尺寸较大，因为矩阵A需要存储n乘n个元素。为了降低通信和计算开销，研究人员提出了环上的Ring-LWE和模上的Module-LWE。Ring-LWE将矩阵乘法替换为多项式环上的乘法，公钥尺寸从n的平方降低到n的量级，并且可以利用数论变换NTT进行快速多项式乘法。Module-LWE则在安全和效率之间取得平衡，被NIST标准算法Kyber和Dilithium采用。
三、典型格密码方案：加密与签名
基于LWE的公钥加密方案可以非常简洁地构造。私钥是一个秘密向量s，公钥由随机矩阵A和向量b组成，其中b等于As加误差e。加密时，发送方选择一个随机二进制向量r，计算u等于A转置乘r，v等于b内积r再加上需要传输的消息比特乘以q除以2的整数部分。接收方使用私钥s计算v减去u内积s，结果要么接近0，要么接近q除以2，根据这个距离可以恢复出原始消息比特。下面的Python代码演示了一个简化但完整的LWE加密解密流程。
import random
def keygen(n, q):
s = [random.randint(-1, 1) for _ in range(n)]
A = [[random.randint(0, q - 1) for _ in range(n)] for _ in range(n)]
e = [random.randint(-2, 2) for _ in range(n)]
b = [(sum(A[i][j] * s[j] for j in range(n)) + e[i]) % q for i in range(n)]
return (A, b), s
def encrypt(pk, m, q):
A, b = pk
n = len(b)
r = [random.randint(0, 1) for _ in range(n)]
u = [(sum(A[j][i] * r[j] for j in range(n))) % q for i in range(n)]
v = (sum(b[j] * r[j] for j in range(n)) + m * (q // 2)) % q
return u, v
def decrypt(sk, ct, q):
s = sk
u, v = ct
n = len(s)
delta = (v - sum(u[i] * s[i] for i in range(n))) % q
if delta >= q // 2:
delta -= q
return 1 if abs(delta) >= q // 4 else 0
上述代码中keygen生成公钥和私钥，encrypt加密单个比特消息，decrypt根据误差大小判断原始消息是0还是1。真实方案会使用更大的维度n和模数q，并且通过编码多个比特来提升效率，但基本原理相同。FrodoKEM就是基于这类普通LWE构造的密钥封装机制，优点是安全性假设非常保守，缺点是公钥尺寸较大。
数字签名方面，Dilithium是NIST标准化的格签名算法。它基于Module-LWE和Module-SIS假设，采用Fiat-Shamir变换将交互式身份认证协议转化为非交互式签名。签名过程会生成一个很小的挑战向量c，然后计算响应向量z，如果z的某个分量过大就拒绝并重新采样，这种拒绝采样技术可以防止签名泄露私钥信息。Dilithium的签名尺寸约2.5KB，公钥约1.3KB，相比RSA签名虽然更大，但在后量子密码中已经属于高效方案。
四、实现中的关键优化
格密码的性能瓶颈主要集中在多项式环上的乘法运算。以Ring-LWE为例，加密和解密都需要多次计算两个多项式的卷积。直接按定义计算复杂度为n的平方，当n取1024时一次乘法就需要上百万次基本运算。数论变换NTT可以将多项式乘法复杂度降低到n乘以logn，其原理类似于快速傅里叶变换，在模q的有限域中进行根式计算。Kyber和Dilithium的参考实现以及大部分优化实现都使用了分层的NTT结构，极大地提升了吞吐量。
采样方法也是影响性能和安全的关键因素。格密码需要频繁地从离散高斯分布或中心二项分布中采样误差向量。离散高斯采样需要高精度浮点运算，容易受到侧信道攻击。采用中心二项分布可以通过简单的减法操作完成采样，不仅速度更快，而且天然具有常量时间特性，降低了时序侧信道风险。拒绝采样在签名方案中用于保证输出分布独立于私钥，实现时也需要避免所有可能依赖秘密数据的分支。
参数选择直接决定安全级别和性能指标。NIST定义了与AES-128、AES-192、AES-256相对应的安全强度等级。Kyber768对应AES-192安全级别，模数q为3329，维度为768，密文大小约1088字节。在选择参数时，需要在错误增长概率、带宽和攻击成本之间寻找平衡。模数选择较小的素数便于NTT计算，维度太低无法抵抗格基约化攻击，太高又会拖慢性能。
五、后量子迁移的实践与挑战
将格密码部署到现有网络协议中，最常见的方式是采用混合模式。客户端和服务器同时协商传统密钥交换和格密钥交换，例如X25519与Kyber的组合，共享密钥由两者的输出共同派生。这种混合方案能够在不完全放弃传统算法的情况下提供后量子安全性，即使格密码实现存在未知缺陷，传统部分仍然可以保护通信。TLS 1.3、SSH和IPsec等协议都在逐步支持这种混合密钥交换。
迁移过程中主要挑战包括证书体系更新、公钥尺寸增加以及旧设备兼容性。格签名公钥比ECDSA公钥大一个数量级，可能影响证书链的传输延迟。公钥基础设施需要支持新的算法标识符，同时保留对传统算法的支持以兼容旧客户端。此外，格密码算法的实现需要经过严格的侧信道审查，任何与秘密相关的内存访问模式或分支行为都可能被攻击者利用。
从长远看，格密码不仅仅是后量子密码的权宜之计，它带来的全同态加密能力为隐私计算开辟了新道路。基于LWE的全同态加密方案可以在不解密的情况下对密文进行任意计算，这在云计算和多方计算中具有重要价值。随着NIST标准的落地和硬件加速器的出现，格密码有望在未来十年内成为互联网安全的基础组件。