3、后量子密码学入门：格密码、哈希签名、多变量密码、编码密码四大流派简介

好，咱们进入正题。后量子密码学，说白了就是能扛得住量子计算机攻击的密码算法。传统 RSA 和 ECC 在 Shor 算法面前就像纸糊的一样，几分钟就能被攻破。我 2018 年第一次跑通一个格密码的 demo 时，心里就一个念头：这玩意儿才是未来。

目前 NIST 后量子标准化竞赛筛选出了四大主流流派。每个流派背后的数学难题都不一样，安全性假设、性能特征也天差地别。咱们一个一个来过。

3.1 格密码（Lattice-based Cryptography）

格密码是目前最火、最成熟的后量子方案。NIST 首批选中的 Kyber（KEM）和 Dilithium（签名）都属于这个流派。

它的数学基础是格上的困难问题——比如最短向量问题（SVP）和学习带错误问题（LWE）。你想想看，在一个高维空间里找一个最短的向量，量子计算机也没什么好办法。

我个人习惯把格密码比作「在乱麻中找线头」。加密时故意加入一些微小的噪声，解密时只有持有正确密钥的人才能把噪声滤掉。攻击者看到的是一团乱麻，根本理不清。

格密码的主要优势：

• 安全性强：有最坏情况到平均情况的归约证明，理论根基扎实
• 性能均衡：加解密和签名验证都很快，尤其验证端
• 功能丰富：支持全同态加密、属性基加密等高级功能

主要短板：

• 尺寸偏大：公钥和签名比传统方案大一个数量级
• 实现复杂：需要处理多项式乘法、噪声采样等操作，容易引入侧信道漏洞

3.2 哈希签名（Hash-based Signatures）

哈希签名是四大流派里最「保守」的一个。它不依赖任何数论难题，只依赖哈希函数的抗碰撞性。你想想看，只要 SHA-256 还是安全的，哈希签名就安全。

它的代表方案是 LMS（Leighton-Micali Signature）和 XMSS（eXtended Merkle Signature Scheme）。NIST 已经发布了 SP 800-208 标准，推荐在特定场景下使用。

哈希签名的核心思想是用 Merkle 树来管理一次性签名密钥。每个密钥只能签一条消息，签完就废掉。树根就是公钥，叶子就是一次性签名密钥。

我记得有一次给客户做方案评审，对方问：「密钥用一次就扔，那要签很多消息怎么办？」答案是：建一棵更大的树。树深 20 层就能签 100 万次，够用了。

哈希签名的特点：

• 安全性极简：只依赖哈希函数，量子安全强度清晰
• 签名验证快：就是哈希计算，没有大数运算
• 签名尺寸大：XMSS 签名大约 2-3KB，比格密码还大
• 有状态管理：这是最大的工程痛点

3.3 多变量密码（Multivariate-based Cryptography）

多变量密码的数学基础是：求解一组多变量二次方程组是 NP-hard 的。说白了，给你一堆二次方程，让你找解，难得很。

代表方案是 Rainbow（已淘汰）和 GeMSS。Rainbow 在 NIST 第三轮被攻破了，但多变量这个方向依然有研究价值。

多变量密码的签名非常短——这是它最大的卖点。Rainbow 的签名只有几十字节，比 ECDSA 还小。但公钥巨大，动不动就几十 KB 甚至上百 KB。

我个人的看法是：多变量密码适合签名方资源无限、验证方资源有限的场景。比如代码签名，发布方有强大的服务器，公钥大点无所谓；但验证方是嵌入式设备，签名小就能省带宽。

主要优缺点：

• 签名极短：四大流派里签名尺寸最小
• 公钥巨大：存储和传输成本高
• 安全性存疑：多次被攻破，参数选择要格外谨慎
• 加解密慢：多变量求值计算量大

3.4 编码密码（Code-based Cryptography）

编码密码基于编码理论中的困难问题——比如一般线性码的解码问题。最经典的方案是 McEliece 加密系统，1978 年就提出来了，比 RSA 还早。

McEliece 用了 Goppa 码，安全性经过了 40 多年的考验。NIST 第四轮入选的 Classic McEliece 就是这个流派。

编码密码的加解密速度非常快——就是矩阵乘法，没有大数指数运算。但公钥巨大，Classic McEliece 的公钥动辄几百 KB 甚至 1MB。

嗯，这里要注意：编码密码目前主要做 KEM（密钥封装），签名方案还不成熟。如果你要做远程证明协议，编码密码更适合做密钥交换，而不是签名。

编码密码的特点：

• 安全性久经考验：40 年未被攻破
• 加解密快：适合资源受限的验证方
• 公钥巨大：存储和传输是最大痛点
• 签名方案不成熟：目前主要做 KEM

3.5 四大流派对比总览

下面这张表是我做方案选型时常用的参考。你直接拿去用。

流派	数学难题	代表方案	签名尺寸	公钥尺寸	验证速度	成熟度
格密码	LWE/SVP	Dilithium, Kyber	~2.5KB	~1.5KB	快	高（NIST 标准）
哈希签名	哈希抗碰撞	XMSS, LMS	~2-3KB	~64B	快	高（NIST 标准）
多变量密码	MQ 问题	Rainbow, GeMSS	~几十 B	~几十 KB	中等	中（有攻破记录）
编码密码	解码问题	Classic McEliece	N/A（KEM）	~几百 KB	快	高（40 年考验）

3.6 知识体系总览

下面这张 SVG 图把四大流派的核心要素串起来了。你可以看到每个流派的安全基础、代表方案和工程痛点。

3.7 选型建议：远程证明协议怎么选？

好，讲完了理论，咱们落地到远程证明协议。你该怎么选？

我个人习惯按场景来分：

• 通用场景：选格密码（Dilithium）。性能均衡，NIST 标准，生态最成熟。
• 高安全场景：选哈希签名（XMSS）。安全性假设最简单，适合长期保存的证明。
• 带宽敏感场景：选多变量密码。签名极小，但要做好公钥分发的成本预算。
• 密钥协商场景：选编码密码（Classic McEliece）。加解密快，安全性久经考验。