💻 computer science

Post-Quantum Sanitizable Signatures from McEliece-Based Chameleon Hashing

本文提出了一种基于麦氏（McEliece）密码系统的后量子可清洗签名方案，该方案利用 Goppa 码陷门实现受控碰撞查找，并在随机预言机模型下通过严格的权重约束证明了其存在性不可伪造性、不变性及完美透明性，从而构建了首个代码基后量子可清洗签名系统。

原作者： Shahzad Ahmad, Stefan Rass, Zahra Seyedi

发布于 2026-02-25

📖 1 分钟阅读☕ 轻松阅读

CC BY 4.0

原作者： Shahzad Ahmad, Stefan Rass, Zahra Seyedi

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

这是一篇关于**“后量子可清洗签名”（Post-Quantum Sanitizable Signatures）的学术论文。为了让你轻松理解，我们可以把这篇论文的核心思想想象成“在一张由未来超级计算机无法破解的魔法羊皮纸上，进行受控的‘涂改’，且让任何人都看不出涂改过的痕迹”**。

下面我用通俗的语言和生动的比喻来拆解这篇论文：

1. 背景：为什么我们需要这个？

想象一下，医生给病人写了一份病历，并签了名。

问题：如果病人想把病历里的“姓名”和“身份证号”涂掉（为了隐私），但保留“病情”和“治疗方案”，该怎么办？
传统做法：如果直接涂改，签名就失效了，因为签名是绑定整份文件的。如果重新签名，原来的医生又没参与，这就破坏了信任。
解决方案：我们需要一种特殊的“魔法印章”。医生签了名后，授权一个“清洁工”（Sanitizer）。清洁工可以擦掉特定的部分（比如姓名），并重新调整印章，让整份文件看起来依然像是医生亲自签的，而且除了被擦掉的部分，其他内容（病情）绝对不能被篡改。

2. 核心挑战：量子计算机的威胁

以前的这种“魔法印章”技术（基于 RSA 或椭圆曲线），就像是用普通的锁。现在的电脑能打开，但未来的量子计算机（Quantum Computer）能像用万能钥匙一样瞬间打开这些锁，让所有旧签名都失效。

这篇论文的目标是：造一把量子计算机也打不开的锁，同时还能让“清洁工”合法地修改文件。

3. 核心创新：麦氏密码（McEliece）与“乱码”

作者没有用传统的数学难题，而是选择了一个非常古老且坚固的数学难题——“麦氏密码”（McEliece），它基于纠错码（就像给数据加了很多冗余的纠错信息）。

比喻：寻找丢失的拼图碎片

普通哈希（Hash）：就像把文件内容变成一串乱码。
可清洗哈希（Chameleon Hash）：这是一种特殊的乱码生成器。
- 普通人：给你文件 $A$ 和乱码 $H$ ，你无法算出怎么修改文件变成 $A'$ 还能得到同样的乱码 $H$ 。
- 清洁工（拥有“陷阱门”）：他手里有一把特殊的“钥匙”（Goppa 码的私钥）。有了这把钥匙，他就能在保持乱码 $H$ 不变的情况下，把文件从 $A$ 变成 $A'$ 。
- 关键难点：以前的方案在量子计算机面前不安全。作者设计了一种新的方法，利用**帕特森解码（Patterson Decoding）**算法作为这把钥匙。

4. 三大亮点（论文的贡献）

A. 量子安全（Post-Quantum）

作者构建的这把“锁”，基于**综合征解码（Syndrome Decoding）**问题。

比喻：想象你在一个巨大的迷宫里找一条特定的路。对于普通电脑，这很难；对于量子电脑，虽然能快一点，但依然难如登天。这个数学难题已经研究了 45 年，非常成熟且坚固。

B. 完美的“透明性”（Perfect Transparency）

这是论文最精彩的部分。

什么是透明性？ 当清洁工修改了文件后，外界（比如法官或审计员）看着修改后的文件和签名，完全无法分辨这是医生刚签的，还是清洁工改过的。
以前的做法：清洁工改完后，留下的痕迹（统计特征）和医生签的有点不一样，像是一个拙劣的模仿者。
作者的做法：作者给医生（签名者）定了一个严格的规矩——“你生成的随机数必须正好有 $t$ 个 1"。
结果：清洁工用钥匙修改后，生成的随机数也正好是 $t$ 个 1。
比喻：就像医生和清洁工都穿着完全一样的制服，戴着完全一样的帽子。外人看过去，根本分不清谁是谁。论文证明了这种“完美伪装”在数学上是成立的（统计距离为 0）。

C. 不可篡改性（Immutability）

虽然清洁工能改“允许修改”的部分（比如姓名），但他绝对不能改“禁止修改”的部分（比如病情）。

比喻：文件被分成了很多块。允许修改的块是“橡皮泥”，清洁工可以捏；禁止修改的块是“石头”。清洁工只有捏橡皮泥的魔法，没有敲碎石头的锤子。如果他试图敲碎石头，签名就会立刻失效，大家都能发现。

5. 实际效果与代价

作者用 Python 写了一个原型系统，并测试了性能：

优点：
- 安全：能抵抗未来的量子攻击。
- 隐私：修改痕迹完全不可见（完美透明）。
- 公钥大小：比目前另一种主流的量子安全方案（基于格密码）要小一些（约 655KB vs 850KB）。
缺点：
- 文件较大：签名和公钥比传统的 RSA 签名大很多（传统是几 KB，这个是几百 KB 甚至几 MB）。
- 速度：虽然比传统慢，但在可接受范围内（修改一个块大约需要几毫秒到几十毫秒）。

6. 总结：这有什么用？

这篇论文提出了一种**“未来-proof"的文档修改方案**。

想象一下：

医院：可以发布脱敏的病历，既保护了患者隐私，又保证了医疗数据的真实性，且这份病历在 50 年后依然安全。
证书机构：可以更新证书的有效期，而不需要重新签发整个证书。
供应链：可以隐藏敏感的价格信息，但保留产品认证信息。

一句话总结：
作者发明了一种基于古老数学难题的“量子防弹”签名技术，它允许授权人员像变魔术一样修改文件中的特定部分，同时让外界完全看不出修改的痕迹，且连未来的超级量子计算机也无法破解。

基于 McEliece 的抗量子可清洗签名方案技术总结

1. 研究背景与问题 (Problem)

可清洗签名 (Sanitizable Signatures) 是一种密码学原语，允许签名者将修改文档特定部分的权限委托给指定的“清洗器”（Sanitizer）。清洗器可以在不破坏签名有效性的前提下修改被标记为“可修改”的块，同时保持其他“不可修改”块的内容不变。这种机制在医疗记录脱敏、证书字段更新和供应链文档匿名化等场景中具有重要应用。

然而，现有的可清洗签名方案主要基于 RSA、离散对数或双线性对等数学难题，这些方案在量子计算机（特别是 Shor 算法）面前是不安全的。虽然近期出现了基于格（Lattice）的抗量子可清洗签名方案，但基于编码理论（Code-based）的抗量子可清洗签名方案此前尚未实现。此外，现有的格基方案在透明性（Transparency）和安全性假设的成熟度上仍有提升空间。

本文旨在填补这一空白，提出首个基于 McEliece 密码体制（编码理论）的、具有完美透明性的后量子可清洗签名方案。

2. 方法论 (Methodology)

该方案的核心创新在于构建了一个基于 McEliece 体制的变色龙哈希函数 (Chameleon Hash Function)，并将其集成到可清洗签名框架中。

2.1 基于 McEliece 的变色龙哈希 (ROM 模型)

构造原理：定义哈希函数 $H_{pk}(m, r) = (G(m) \oplus r) \cdot H_{pub}^T$ $H_{p k} (m, r) = (G (m) \oplus r) \cdot H_{p u b}^{T}$ 。
- $m$ ：消息块。
- $r$ ：随机化向量（Randomizer），其汉明重量被限制为 $t$ 。
- $H_{pub}$ ：公开的校验矩阵（由 Goppa 码的校验矩阵 $H_{sec}$ 经随机可逆矩阵 $S'$ 和置换矩阵 $P$ 掩码得到）。
- $G$ ：随机预言机（Random Oracle, 如 SHA-3），用于预处理消息。
抗碰撞性设计：
- 问题：若直接使用线性哈希 $H(x, r) = (x \oplus r) \cdot H_{pub}^T$ ，攻击者无需陷门即可通过调整 $r$ 轻易找到碰撞。
- 解决方案：引入随机预言机 $G(m)$ 。攻击者若要找到碰撞，必须求解 $G(m) \oplus r \oplus G(m') \oplus r' = 0$ ，这等同于在不知道陷门的情况下解决伴随式解码 (Syndrome Decoding, SD) 问题。
陷门机制：
- 清洗器持有 Goppa 码的陷门（秘密密钥： $P, (S')^{-1}$ 及 Goppa 参数）。
- 给定新消息 $m'$ ，清洗器计算目标伴随式 $s_{target} = (G(m) \oplus r \oplus G(m')) \cdot H_{pub}^T$ 。
- 利用 Patterson 解码算法，清洗器可以在 $O(n \cdot t)$ 时间内找到满足重量约束 $wt(r') \le t$ 的随机向量 $r'$ ，使得 $r' \cdot H_{pub}^T = s_{target}$ ，从而生成碰撞。

2.2 可清洗签名方案架构

双哈希链结构：使用两个独立的 McEliece 变色龙哈希：
- $H_{non}$ ：用于处理不可修改块（Immutable blocks）。
- $H_{san}$ ：用于处理可修改块（Admissible blocks）。
签名流程：
1. 签名者对消息块进行链式哈希处理。
2. 对于每个块，根据掩码 $adm$ 选择对应的哈希函数。
3. 签名者采样重量恰好为 $t$ 的随机向量 $r_i$ 。
4. 最终哈希值 $h_L$ 与掩码 $adm$ 拼接后，使用基于 Dilithium2 的签名算法进行签名。
清洗流程：
1. 清洗器验证原始签名。
2. 对于被修改的块，利用陷门重新计算随机向量 $r'_i$ 以保持哈希值不变。
3. 重新计算后续链式哈希（由于 $h_L$ 保持不变，外层签名 $\sigma_{sig}$ 无需更新）。

3. 关键贡献 (Key Contributions)

首个基于编码理论的抗量子可清洗签名：
- 成功将 McEliece 体制应用于可清洗签名领域，提供了除格基方案外的另一种后量子安全选择。
- 安全性基于伴随式解码 (Syndrome Decoding) 难题，这是一个已有 45 年研究历史的成熟难题，相比格基方案（约 15 年历史）具有更保守和稳健的安全基础。
完美透明性 (Perfect Transparency)：
- 核心突破：通过强制签名者在采样随机向量时严格限制其汉明重量恰好为 $t$ （与 Patterson 解码输出的分布完全一致），实现了统计距离 $\delta = 0$ 的完美透明性。
- 这意味着任何观察者（甚至拥有计算能力的攻击者）都无法区分签名是由原始签名者生成的，还是由清洗器修改后生成的。
形式化安全证明：
- 在随机预言机模型 (ROM) 下，证明了方案的存在性不可伪造性 (EUF-CMA) 和不可变性 (Immutability)。
- 证明了碰撞抵抗性归约于 SD 问题的困难性。
- 提供了精确的透明性界限分析，量化了不同采样策略下的统计距离。
实现与基准测试：
- 基于 NIST 第 1 类 Classic-McEliece 参数 ( $n=3488, k=2720, t=64$ ) 实现了 Python 原型。
- 验证了理论性能：Patterson 解码修改单个块的理论耗时约为 8ms。

4. 实验结果与性能 (Results)

密钥与签名大小：
- 公钥大小：约 655.3 KB（主要源于两个 $327$ KB 的校验矩阵）。相比格基方案（约 850 KB）更小，但远大于经典 RSA 方案。
- 签名大小：对于 $L=10$ 个块，签名大小约为 6.75 KB。随块数 $L$ 线性增长（每块增加约 436 字节）。
性能表现：
- 签名和验证时间随块数 $L$ 近似线性增长。
- 清洗操作（Sanitization）在理论实现（C 语言优化版 Patterson 解码）下非常高效，但在 Python 原型中由于随机搜索解码器效率较低，耗时较长（原型数据仅供参考，实际部署需优化）。
对比分析：
- 与 Clermont 等人提出的格基方案相比，本方案公钥更小，且实现了完美透明性（格基方案仅为弱透明性）。
- 安全性假设更为成熟（SD 问题 vs. Module-LWE/SIS）。

5. 意义与局限性 (Significance & Limitations)

意义

长期安全：为需要长期归档（10 年以上）且需抵抗量子攻击的文档（如医疗记录、法律合同）提供了新的解决方案。
隐私保护：完美透明性确保了清洗行为在密码学层面完全不可检测，极大地保护了清洗者的隐私和文档的完整性。
多样性：丰富了后量子密码学的技术栈，避免了对单一数学难题（如格问题）的过度依赖。

局限性与未来工作

随机预言机模型 (ROM)：变色龙哈希的碰撞抵抗性依赖于 ROM。目前尚无基于编码理论的标准模型（Standard Model）变色龙哈希构造。
密钥尺寸：虽然比格基方案小，但 655 KB 的公钥对于带宽受限的 IoT 设备仍显过大（未来可探索 MDPC/LDPC 码将密钥降至 100 KB 左右）。
暴露无关性 (Exposure-freeness)：方案不具备暴露无关性，即如果清洗器对同一消息块进行多次清洗，可能会逐渐泄露陷门信息。
策略隐藏：可修改块的掩码 $adm$ 是公开的，观察者可以知道哪些块被允许修改。
侧信道攻击：原型实现未采用恒定时间（Constant-time）解码，生产环境需防范时序侧信道攻击。

总结：该论文提出了一种理论严谨、具有完美透明性的后量子可清洗签名方案，利用 McEliece 体制和 Patterson 解码算法，在安全性、透明性和实现可行性之间取得了良好的平衡，为后量子时代的文档安全清洗提供了重要的技术路径。