技术摘要：一种基于同构的紧凑型后量子强指定验证者签名方案

问题陈述

数字签名传统上提供不可否认性，即任何拥有签名者公钥的方都可以验证签名的真实性。虽然这在许多应用场景中非常有用，但在需要“即时通讯（off-the-record）”的场景下，这一属性是不理想的。在这些场景中，签名者（Alice）希望向特定接收者（Bob）认证一条消息，但不希望 Bob 能够向第三方证明该消息源自 Alice。

为了解决这一问题，强指定验证者签名（Strong Designated Verifier Signatures, SDVS） 被引入。一种 SDVS 方案确保只有指定的验证者才能验证签名的真实性。至关重要的是，它满足不可转移性（non-transferability）：指定的验证者可以模拟与真实签名在计算上不可区分的签名，从而防止其向第三方证明签名的有效性。此外，SDVS 方案必须满足签名者身份隐私性（Privacy of Signer's Identity, PSI），即在给定一个有效签名和多个候选公钥的情况下，第三方无法确定使用了哪个密钥进行签名。

虽然基于双线性配对或 Schnorr 签名的经典密码学中已存在 SDVS 方案，但它们容易受到 Shor 算法的量子攻击。现有的基于编码或格（lattice）的后量子提案通常面临较大的密钥和签名尺寸（例如 $O(\lambda^2)$ 复杂度），或者已被证明无法满足不可转移性属性。近期的基于同构（isogeny）的提案则面临着安全破裂的问题（例如 SIDH），或者依赖于可能不够稳健的假设。

方法论

作者提出了 CSI-SDVS，一种基于交换超奇异同构 Diffie-Hellman (CSIDH) 群作用的新型 SDVS 方案。该构造利用了虚二次域中阶的理想类群作用在有限域 $\mathbb{F}_p$ 上的超奇异椭圆曲线集合上的代数结构。

核心组件

1. 群作用设置： 该方案运行在一个有效的群作用 $(G, X, *)$ 内，其中 $G$ 是虚二次域中阶的理想类群，$X$ 是超奇异椭圆曲线的集合。该作用是自由且传递的。
2. 密钥生成：
   • 签名者和验证者生成私钥（$sk_S, sk_V$），其为 $\mathbb{Z}_N$ 中的随机整数（其中 $N$ 是类数）。
   • 公钥通过将群作用应用于基曲线 $E$ 来生成：$pk_S = [g^{sk_S}] * E$ 且 $pk_V = [g^{sk_V}] * E$。
3. 签名与模拟：
   • 签名： 为了对消息 $m$ 进行签名，签名者选择一个随机数 $z \in \mathbb{Z}_N$，计算 $Y = [g^{z+sk_S}] * pk_V$，并设置签名 $\sigma = (h, z)$，其中 $h = H(Y || m)$。
   • 模拟： 拥有 $sk_V$ 的验证者可以通过选择一个随机数 $z$，计算 $Y = [g^{z+sk_V}] * pk_S$，并设置 $\sigma = (h, z)$，其中 $h = H(Y || m)$。
   • 正确性： 由于群作用的交换性，$[g^{z+sk_S}] * pk_V = [g^{z+sk_S+sk_V}] * E = [g^{z+sk_V}] * pk_S$。因此，签名者和模拟器计算出的 $Y$ 值是完全相同的，从而确保两者都能针对相同的哈希输入产生有效的签名。
4. 验证： 验证者检查是否满足 $h = H([g^{z+sk_V}] * pk_S || m)$。

主要贡献

1. 紧凑型后量子 SDVS： 本文提出了 CSI-SDVS，一种高效的 SDVS 方案，具有 $O(\lambda)$ 的密钥和签名复杂度。使用 CSIDH-512 参数，该方案实现了：
   • 私钥：256 bits。
   • 公钥：512 bits。
   • 签名：512 bits。
     这相对于以往基于格的 SDVS 方案（其尺寸通常为 $O(\lambda^2)$）以及具有较大公钥的同构方案，在尺寸上有了显著改进。
2. 在 ROM 和 AGAM 中的安全性证明：
   • 不可转移性 (NT)： 被证明是无条件成立的，因为真实签名与模拟签名的分布是完全一致的。
   • 强不可伪造性 (SUF-CMA) 与 PSI： 在随机预言机模型 (ROM) 下，基于群作用判别式 Diffie-Hellman (GA-DDH) 假设被证明是安全的。
   • 紧凑归约： 作者进一步证明，在代数群作用模型 (AGAM) 中，CSI-SDVS 的 SUF-CMA 和 PSI 安全性可以紧凑地归约为群作用逆问题 (GAIP)，这是一个计算问题而非判别问题。
3. 安全性分析： 该方案被证明满足所有标准的 SDVS 定义（NT, SUF-CMA, PSI），且不依赖于已被破解的 SIDH 协议，而是利用了目前被认为安全的 CSIDH 群作用。

结果

论文提供了形式化的安全证明，表明：

• 该方案是无条件不可转移的。
• 在 ROM 下基于 GA-DDH 假设，该方案具有强不可伪造性并提供签名者身份隐私性。
• 在 AGAM 和 ROM 下基于 GAIP 假设，该方案为 SUF-CMA 和 PSI 安全性实现了紧凑归约。
• 性能： 论文中的表 1 将 CSI-SDVS 与之前的研究（Sun 等人 [26] 和 Khuc 等人 [12]）进行了对比。在对比的后量子方案中，CSI-SDVS 提供了最小的公钥（512 bits）和签名（512 bits），同时保持了 256 bits 的私钥大小。

意义

作者将 CSI-SDVS 定位为一种实用且安全的后量子指定验证者签名解决方案。其意义在于：

• 高效性： 它实现了适用于资源受限环境的紧凑参数，解决了以往基于格或基于同构方案的尺寸限制问题。
• 鲁棒性： 通过在 AGAM 中基于 GAIP（一个计算假设）来构建安全性，该方案避免了依赖于在群作用设置中可能较弱或不够直观的判别性假设。
• 完整性： 该工作提供了涵盖后量子环境下 SDVS 三大支柱（不可转移性、不可伪造性和签名者隐私性）的完整安全性分析，填补了以往方案要么无法满足不可转移性、要么效率低下的空白。

论文结论认为，CSI-SDVS 在安全性和效率之间取得了平衡，使其成为需要量子抗性且具有不可转移性认证应用的理想候选方案。