量子威胁

Shor 算法能在量子计算机上多项式时间分解大整数、求离散对数——RSA 与 ECC 将被攻破。于是需要「即便有量子计算机也安全」的后量子密码 (PQC)。

格与困难问题

格是向量 $\mathbf b_1,\dots,\mathbf b_n$ 的整系数线性组合构成的离散点阵。其上的难题：

  • 最短向量问题 (SVP)、最近向量问题 (CVP)；
  • 带误差学习 (LWE)：解含噪声的线性方程组 $\mathbf{As}+\mathbf e=\mathbf b$。
    这些问题对量子算法依然困难，是 PQC 的主流基础。

例题

例　二维格里，求离原点最近的非零格点看似简单，但高维（数百维）下 SVP 变得极难——安全性正源于此维度灾难。

应用

NIST 已将基于格的 Kyber（密钥封装）与 Dilithium（签名） 列为后量子标准，正在替换 TLS/VPN 中的 RSA/ECC。格密码还支撑全同态加密（在密文上直接计算），是隐私计算的前沿。