Withdrawability in Fiat-Shamir with aborts constructions

技术摘要：带有中止机制的 Fiat–Shamir 可撤回性构造

问题陈述
数字签名传统上提供永久性；一旦生成，若不破坏签名者的私钥或使其他签名失效，则无法撤销签名。这种局限性在动态环境（如区块链智能合约、去中心化电子投票和托管服务）中带来了挑战，因为参与者可能需要根据变化的情况撤回承诺。Liu、Baek 和 Susilo [LBS23] 引入了“可撤回签名”（withdrawable signatures），这是一种允许签名者生成仅由指定验证者可验证的签名的原语，该签名随后可以被转化为公开可验证的签名。然而，他们的构造依赖于易受量子攻击的经典假设（离散对数、Diffie-Hellman）。

本文旨在解决的问题是将可撤回签名概念扩展到后量子领域，特别是基于 Fiat–Shamir with aborts（带有中止机制的 Fiat–Shamir）范式。该范式是 Dilithium (ML-DSA) 和 HAETAE 等领先后量子签名方案的基础。存在一个特定的结构性障碍：原始的 Liu–Baek–Susilo 构造依赖于一个“免费”的 Diffie-Hellman 共享密钥来实现签名者/验证者的歧义性（ambiguity）与指定性（designation）的同时实现。基于格（lattice）的密码学缺乏这种高效且廉价的共享密钥类比，因此需要一种新的架构方法。

方法论
本文提出了一种基于 Fiat–Shamir with aborts 范式的可撤回签名的一般抽象构造，并随后给出了一个具体的实例化。

1. 抽象构造：
   作者定义了一个包含五个算法的框架：KeyGen、WSign（可撤回签名）、WSVerify（可撤回验证）、Confirm 和 C-Verify。

   • 核心机制： 该方案利用了一个两方 Fiat–Shamir with aborts OR-proof（或证明）。可撤回签名由两个分支组成：一个由签名者生成（使用其私钥），另一个由签名者模拟以模仿验证者的分支。
   • 歧义性： 由于签名者和指定验证者都可以生成一个有效分支（签名者通过模拟验证者，验证者通过模拟签名者），第三方无法辨别签名的来源。
   • 确认（Confirmation）： 为了使签名具有公开可验证性，签名者运行 Confirm 算法，该算法生成一个关于消息、公钥集及可撤回签名本身的标准普通签名。这在不要求重新推导共享随机性的情况下（由于拒绝采样，这在基于格的 FS-with-aborts 中是不可行的），将可撤回签名与签名者的身份绑定。

2. 强指定验证者 (SDV) 变体：
   为了确保可撤回签名不是公开可验证的（符合 Liu–Baek–Susilo 模型），作者使用公钥加密 (PKE) 方案（具体为支撑 ML-KEM/Kyber 的 CPA 安全 module-LWE 加密）对签名的公开核心部分进行加密。

   • 签名被加密至指定验证者的公钥和签名者的公钥。这使得验证者可以解密并验证，同时也允许签名者解密并以无状态方式执行 Confirm 操作。
   • 这种方法使用显式加密取代了 Diffie-Hellman 共享密钥，承认了基于格的非交互式密钥交换 (NIKE) 目前对于此目的而言过于低效。

3. 具体实例化：
   该抽象框架通过一个 no-hint, full-$t$ Dilithium 风格的构造进行实例化。

   • 作者使用了不使用“提示”（$t_1$/$t_0$ 分割）的 Dilithium 变体，确保了零知识证明的模拟器是完美的 ($\varepsilon_{zk} = 0$)。
   • 这种选择简化了安全证明，特别是对于可撤回性属性，因为它避免了与基于提示的方案相关的微小统计误差。

主要贡献

• 通用框架： 本文引入了第一个基于 Fiat–Shamir with aborts 范式的可撤回签名抽象构造，弥合了 Liu–Baek–Susilo 模型与后量子格密码学之间的鸿沟。
• 安全证明：
  • 不可伪造性： 证明了该方案在内部破坏（即攻击者持有验证者的私钥）的情况下，在（量子）随机预言机模型 (QROM) 下是不可伪造的。证明将其归约为底层格签名方案（SelfTargetMSIS/MSIS 假设）的 EUF-CMA 安全性。
  • 可撤回性： 证明了该方案具有可撤回性，即攻击者无法区分签名是由签名者还是指定验证者生成的。对于 no-hint 实例化，该属性是统计性的（信息论级的），其 $\varepsilon_{zk} = 0$，依赖于底层识别方案的完美非中止诚实验证者零知识性 (naHVZ) 以及承诺的最小熵。
• 适应后量子约束： 本文明确解决了缺乏基于格的 Diffie-Hellman 共享密钥的问题。它展示了可以通过公钥加密 (PKE) 而非 NIKE 来实现指定性，并且可以通过 OR-proofs 而非代数对称性来实现歧义性。

结果

• 具体安全性： 对于 no-hint Dilithium 实例化，本文提供了具体的安全界限。不可伪造性的优势受限于底层方案的安全性和与随机预言机编程相关的微小项 ($2^{-1024}$)。可撤回性的优势受限于 $1/2$ 加上一个微小的统计项，在 no-hint 情况下实际上实现了针对指定验证者的完美歧义性。
• 对比： 作者提供了与 Liu–Baek–Susilo 方案的详细对比（表 2）。虽然格构造需要额外的密钥材料（加密密钥）并导致更大的签名（由于加密开销），但它获得了两个显著属性：可撤回签名是伪随机的（对其存在性向第三方隐藏），且针对指定验证者的不可转移性是完美的（统计级的）而非计算级的。

意义
本文声称其意义在于将可撤回签名原语向后量子时代的必要适配。它确立了在不依赖于低效或不存在的 Diffie-Hellman 格类比的情况下，实现基于格密码的可撤回性是可行的。通过将指定机制（加密）与歧义机制（OR-proofs）分离，作者提供了一个稳健且可证明安全的构造，在保持底层方案（如 Dilithium）安全特性的同时，增加了关键的签名撤回灵活性。这项工作表明，这些构造可以增强区块链系统中交易撤回功能的量子抗性，而这类功能在传统上难以实现。