Lattice-based extended withdrawability

技术摘要：基于格的扩展可撤回性 (Lattice-based Extended Withdrawability)

问题陈述
数字签名传统上提供永久性：一旦签名，消息在签名者的公钥下可以无限期地进行验证。然而，许多去中心化应用（例如：限时访问、可撤销协议、去中心化托管）需要能够撤回签名的能力，且不泄露私钥或使其他签名失效。Liu、Susilo 和 Baek 提出了“扩展可撤回签名”（Extended Withdrawable Signatures, EWS）来解决这一问题，该方案允许签名在真实的签名者“确认”之前，在潜在的签名者集合中保持模糊性。其构造依赖于离散对数原语（Schnor 签名和 1-out-of-N 签名）。

本文旨在解决“后量子差距”问题：Shor 算法破坏了现有 EWS 方案的离散对数基础。虽然目前已存在基于格的签名（如 Dilithium），但将 Liu-Susilo-Baek (LSB) 构造直接进行“字面转录”到格上会失败，因为存在结构性障碍。具体而言，LSB 方案依赖于发布公钥的乘法偏移量，以对签名者的贡献进行重随机化。在格的设置中（带有中止的 Fiat-Shamir 范式），此类偏移量表现为 $As_1 s_j$，它们与签名者的公钥 $t_i = As_1 + s_2$ 共享一个共同因子 $As_1$。发布这些偏移量会泄露签名者的身份，从而破坏所需的模糊性。

方法论
作者提出了一种新的基于格的 EWS 构造，该构造通过将方案视为一种“可声称的环签名”（Claimable Ring Signature, Park 和 Sealfon 提出）而背离了 LSB 的方法。该构造不再尝试在明文中对公钥进行重随机化，而是将 EWS 的两个核心功能分离：

1. 模糊性（Ambiguity）： 由一个匿名的 1-out-of-N（环）签名提供，并将其作为黑盒使用。
2. 确认（Confirmation）： 由签名者的声称（Claim）提供，该声称由对可撤回对象的一个绑定签名以及对签名者索引的隐藏承诺（Hiding Commitment）的开启组成。

该构造运行在带有中止的 Fiat-Shamir 范式之上，并依赖于三个模块化组件：

• 一个基础签名方案（例如：无提示、全 $t$ 型 Dilithium 式方案）。
• 一个匿名的 1-out-of-N 签名（通过格 1-out-of-many 证明实例化）。
• 一个隐藏且绑定的承诺方案（Ajtai 式）。

可撤回签名 $\sigma$ 由消息的环签名 $\sigma_r$、一个对签名者索引的承诺 $C$ 以及公钥集组成。为了进行确认，签名者揭示 $C$ 的开启值 $(i, \rho)$，并使用其基础私钥对整个可撤回对象 $\langle \mu, \pi, \sigma \rangle$ 进行签名。

核心贡献

1. 安全模型精炼： 作者精炼了 LSB 的安全模型。

   • 他们用“确认前匿名性”（Anonymity-until-claim）不可区分性博弈（定义 14）取代了 LSB 的“完备性”定义，从而明确捕捉了隐藏保证。
   • 他们引入了“可声称性健全性”（Claimability Soundness, 定义 16），确保经确认的签名绑定到唯一的签名者索引，防止攻击者将同一个签名归属于不同的环成员。
   • 他们形式化了“针对固定目标索引的内部腐败下的不可伪造性”，避免了 LSB 证明中存在的乘法 $q_H$（哈希查询）归约损失。

2. 通用构造： 文中提出了一个基于带有中止的 Fiat-Shamir 范式的通用 EWS 构造。至关重要的是，它没有在明文中发布任何由签名者衍生的值。模糊性完全源于环签名的零知识属性，而可追溯性则源于承诺的绑定属性。

3. 不可能结果： 本文证明（命题 2）对 LSB 1-out-of-N 签名（使用加法挑战拆分）进行字面格转录是不安全的。在具有稀疏挑战的格设置中，诚实签名者产生有效挑战拆分的概率是微不足道的（$2^{-\Omega(n)}$），并且即使修复了完备性，匿名性也会失效，因为模拟的转录与真实的转录是不可区分的。

4. 完整的安全证明： 作者在（量子）随机预言机模型（QROM）中提供了显式的基于博弈的归约，用于证明：

   • 正确性： 归约为底层原语的正确性。
   • 扩展可撤回性： 归约为承诺的隐藏性（Decisional MLWE）和 1-out-of-N 方案的匿名性。
   • 不可伪造性： 归约为基础签名的 EUF-CMA 安全性（无需重写且无 $q_H$ 损失）。
   • 可声称性健全性： 归约为承诺的绑定性（MSIS）。

5. 实例化： 该方案使用无提示、全 $t$ 型 Dilithium 式基础签名和已建立的格 1-out-of-many 证明进行实例化。文中讨论了参数选择，并指出 HAETAE 可以作为另一种替代的基础方案。

结果
本文确立了所提构造具有以下特性：

• 正确性： 诚实签名以极高的概率通过验证。
• 扩展可撤回性： 持有所有私钥的攻击者无法在签名者确认之前，区分出环中的哪位成员生成了可撤回签名。
• 不可伪造性： 即使可以访问签名预言机以及除目标成员外的所有环成员的私钥，攻击者也无法为新的消息伪造经确认的签名。
• 健全性： 经确认的签名不能被归属于两个不同的签名者。

其安全性依赖于标准的模格假设：Decisional MLWE、MSIS 和 SelfTargetMSIS，以及 1-out-of-N 证明的零知识属性。

意义
本文声称其重要性在于提供了第一个安全的后量子实现的可撤回签名。它证明了由于缺乏“自由重随机化”共享值的特性，离散对数构造的 LSB 无法直接移植到格上。通过将问题重新定义为可声称的环签名，并利用基于承诺的确认机制，作者实现了一个满足以下条件的方案：

• 后量子安全： 通过格假设抵抗量子攻击者。
• 公开可验证： 与指定验证者变体不同，任何方都可以验证可撤回签名。
• 模块化： 其安全证明仅依赖于底层原语的接口，允许在不重新证明整个系统的情况下替换不同的格组件（例如不同的基础签名或环证明）。
• 忠实于原始目标： 该设计在修正了格环境下结构性缺陷的同时，保留了原始 LSB 方案的功能目标和直觉。