CRT-Decomposed $Σ$-Protocols for CSIDH

技术摘要：用于 CSIDH 类群作用的 CRT 分解 $\Sigma$-协议

问题陈述
本文针对基于 CSIDH（交换超奇异同源迪菲-赫尔曼）群作用的同源盲签名和身份识别协议中，安全证明存在的一个关键弱点进行了研究。目前的尖端方案（例如 CSI-Otter、Tanuki）依赖于交互式身份识别协议，其安全性归约依赖于分叉引理（forking lemma）。该引理需要“重放（rewinding）”量子对手以提取秘密密钥，这一过程会产生二次安全损失，并且在面对内部状态无法被克隆的量子对手时，在理论上是无效的。因此，这些证明迫使使用更大、更慢的参数来补偿这种损失。本文旨在通过利用 CSIDH 类群的代数结构来实现直线提取（straight-line extraction），从而消除重放步骤。

方法论
作者构建了一种零知识知识证明（$\Sigma$-协议），该协议利用了 CSIDH 理想类群的**中国剩余定理（CRT）**结构。这种方法仅适用于类群结构精确已知的情况，目前仅在 CSIDH-512 中满足这一条件。

1. CRT 分解： 阶数为 $N$ 的类群 $C\ell(\mathcal{O})$ 被分解为对应于 $N$ 的素幂因子的独立循环分量。秘密密钥 $s$ 被拆分为关于每个素因子 $q_i$ 的分量 $s_i$。
2. 跳跃曲线（Hop Curves）： 协议发布了一系列“跳跃曲线”（$F_0, \dots, F_k$），代表群作用的中间状态。每个跳跃 $i$ 对应于特定子群 $\langle h_i \rangle$（阶为 $q_i$）内的向量化问题。
3. 协议结构： 该协议由 $k$ 个跳跃组成，每个跳跃在 $t$ 个并行轮次中执行。在每一轮中，证明者承诺一个随机位移，验证者发布一个二进制挑战（$c \in \{0,1\}$），然后证明者返回一个值 $z$。
4. 代数提取： 与需要通过重放来寻找具有不同挑战的两个接受转录的标准证明不同，本协议允许通过闭式代数公式来恢复秘密。给定对于相同承诺的两个接受转录，秘密分量仅为响应之差（$z_0 - z_1$），随后进行模逆运算和 CRT 重组。
5. QROM 编译： 由于每轮恰好有两个响应，该协议与 Unruh 变换兼容。这使得将交互式协议转换为**量子随机预言模型（QROM）**中的非交互式知识证明成为可能，并实现了直线提取，完全避免了分叉引理。

主要贡献
本文做出了五个主要贡献：

1. 形式化定义： 它形式化了加密群作用的弱可提取性（weak extractability），定义了一种安全概念，即提取器仅需使用环运算（无需格规约或启发式算法）即可从接受的转录中恢复秘密。
2. 协议构建 ($\Pi_{CRT}$)： 它构建了一个证明四种属性的协议：
   • 完美完备性（Perfect Completeness）： 诚实的证明者总是成功。
   • 完美特殊 HVZK： 转录不会泄露关于秘密的信息，即使是对无限制的观察者。
   • 2-特殊可靠性（2-Special Soundness）： 秘密可以通过简单的减法和模逆运算，从两个转录中代数地恢复。
   • 知识误差（Knowledge Error）： 证明者在没有密钥的情况下成功的概率为 $2^{-t}$。
3. 机器验证： 作者在精确的 258 位模数 CSIDH-512 上实现了代数层。他们验证了 10,000 个随机实例，确认了代数提取工作完美且协议逻辑成立，且无需计算实际的同源。
4. 界定结果（负面结果）：
   • 挑战空间限制： CRT 分解并未扩大每轮的挑战空间；除非发布多个曲线，否则二进制挑战仍然是必要的，但这会增加密钥大小。
   • 安全性代价： 发布中间跳跃曲线会将密钥恢复的经典安全性从 $\approx 2^{128.6}$ 降低到 $\approx 2^{67.3}$ 次群作用评估。这是因为问题分解为特定子群中的独立向量化实例，可通过针对最大分量的中间相遇攻击（meet-in-the-middle attacks）来解决。
5. QROM 安全性： 本文证明了该协议在通过 Unruh 变换编译后，可在 QROM 中实现具有**在线提取（online extraction）**能力的非交互式知识证明，消除了乘性分叉引理损失。

结果与定量分析

• 实例化： 该方案在 CSIDH-512 上实例化。类群有 5 个素因子（位长度分别为：2, 6, 21, 96, 135）。
• 安全界限：
  • 经典安全性： 安全性受限于最大的素因子（$q_{max} \approx 2^{135}$）。中间相遇攻击的成本为 $O(\sqrt{q_{max}}) \approx 2^{67.3}$。论文指出，由于发布了跳跃曲线，CSIDH-512 在此构造下无法达到 128 位经典安全性。
  • 量子安全性： 安全性受限于 Kuperberg 式筛法，与其他 CSIDH 方案类似。
• 性能：
  • 签名大小： 对于 $t=128$ 轮和 $k=5$ 个分量，签名大小约为 24.1 KiB（相比之下，CSI-FiSh 为 263 B，CSI-Otter 为 8 KiB）。
  • 计算： 代数提取和模拟在微秒级以下。主要的成本仍然是同源评估（预计每次作用为 40 ms），使得总签名时间约为 25.6 秒。
• 模拟： 蒙特卡洛模拟确认，可靠性误差符合理论上的 $2^{-t}$ 界限，置信区间在 95% 内。

意义与主张
本文声称该构造对于已知结构的类群（如 CSIDH-512）在结构上是完整且正确的。其主要意义在于通过消除重放步骤，为基于同源的知识证明提供了一条量子安全的安全归约路径，而重放是后量子安全证明中已知的一个漏洞。

然而，作者明确指出了权衡之处：

• 对安全性的谦逊态度： 由于发布跳跃曲线导致的安全性下降，该方案在 CSIDH-512 上并非在 128 位水平上具有定量安全性。作者指出，该构造“仅在未来具有大素因子（例如每个因子 $\ge 256$ 位）的参数集上具有定量安全性”。
• 并非万能药： CRT 分解并不会减少实现可靠性所需的轮数；它仅仅改变了提取机制。
• 未来工作： 本文将基于此知识证明的盲签名构造及其到端同态环问题的紧凑不可伪造性归约留作未来的研究工作。

总之，本文提出了一种数学严谨且经过机器验证的协议，解决了 CSIDH 类基于知识证明中的“重放问题”，为 QROM 安全的盲签名提供了路径，但代价是更大的签名尺寸以及当前参数集下降低的经典安全性。