技术摘要：一种简单且高效的一次性签名方案

问题陈述

一次性签名（One-Shot Signatures, OSS）是一种独特的量子密码原语，它允许用户生成一个公开验证密钥（$pk$）和一个秘密量子签名状态（$|sk\rangle$）。该签名状态使得用户能够为用户选择的一个特定消息生成且仅生成一个有效的签名；一旦签名完成，该状态会“自我销毁”，从而防止生成第二个签名。虽然 OSS 暗示了如量子货币（quantum money）、量子闪电（quantum lightning）和量子火（quantum fire）等强大的原语，但如何高效地构建这些原语一直是一个挑战。

Shmueli 和 Zhandry (SZ) [SZ25] 最近的突破性进展提供了 OSS 的第一个构造方案。然而，他们的方案存在显著的低效问题：

1. 逐位签名： SZ 构造本质上是逐位对消息进行签名。为了对一个 $\lambda$ 位消息进行签名，该方案需要并行重复，导致密钥和签名大小出现线性膨胀。
2. 复杂的放大过程： 为了实现强安全性，SZ 依赖于 Dall'Agnol 和 Spooner (DS) [DS22] 的归约，该归约使用了复杂的量子重写（quantum rewinding）或量子奇异值变换（QSVT）电路（具体为交替投影或 Marriott-Watrous 风格的算法）。这引入了额外的 $\Theta(\lambda)$ 签名密钥规模开销。
3. 不完美的正确性： SZ 方案具有可忽略的正确性误差，这意味着签名算法可能会无法生成有效的签名。
4. 资源成本： 在预言机模型中，SZ 方案导致的签名密钥大小为 $\Theta(\lambda^4)$ 量子比特，签名大小为 $\Theta(\lambda^3)$ 比特。在纯模型（plain model）中，这些参数甚至更大。

此外，随后由 Çakan, Goyal 和 Shmueli (CGS) [C¸GS25] 提出的工作试图利用 OSS 来构建“公钥量子火”，但其依赖于 SZ 方案并不具备的不可压缩性属性。

方法论

本研究提出了一种新的、直接的 OSS 构造方法，避免了以往方法中所需的复杂归约和并行重复。核心方法论在于签名生成方式的基础性转变：

1. 通过 Grover 搜索进行直接构造

不同于 SZ 方法（其通过搜索具有特定起始位的哈希函数的前像，这需要复杂的放大处理来解决“求和绑定”问题），本研究是在函数的**像（image）**中搜索签名。

• 设置： 该方案利用一个随机置换 $\Pi$ 以及由矩阵 $\mathbf{A}_y$ 和向量 $\mathbf{b}_y$ 定义的一族子空间。签名状态 $|sk\rangle$ 是由这些参数定义的仿射子空间（陪集）上的均匀叠加态。
• 签名过程： 为了对一个比特 $b$ 进行签名，算法并非寻找以 $b$ 开头的特定前像。相反，它使用 Grover 搜索算法，将初始叠加态转化为一个在辅助函数 $\mathcal{P}$ 的像下具有特定前缀 $b$ 的陪集向量状态。
• 预言机使用： 签名算法迭代地应用两个反射预言机：
  1. 一个相位预言机，用于标记图像前缀与消息位匹配的状态。
  2. 一个对偶预言机 $\mathcal{D}$，用于沿子空间的对偶进行反射。
     通过迭代此过程 $\ell$ 次（$\ell$ 为消息长度），算法将状态旋转到整个消息的有效签名叠加态。测量该状态即可得到一个有效的签名。

2. 确保完美正确性

作者通过精心设计矩阵 $\mathbf{A}_y$ 的采样过程，解决了不完美正确性的问题。他们确保 $\mathbf{A}_y$ 的第一列是非零的，从而保证对于任何公开密钥 $y$，该陪集都包含以 0 和 1 开头的向量。这种结构性保证确保了 Grover 搜索始终成功，实现了完美正确性（概率为 1）。

3. 处理多项式长度的消息

该方案并非将单比特方案重复 $\lambda$ 次（这会导致 $\lambda$ 倍的膨胀），而是在一次执行中对整个 $\lambda$ 位消息进行签名。Grover 搜索被改编为在单次执行中进行逐位签名，将 $\lambda$ 个签名压缩为单个大小为 $\Theta(\lambda^2)$ 的签名。对于任意多项式长度，则应用标准的“哈希并签名”（hash-and-sign）变换。

4. 不可压缩性与量子火

本文指出 CGS [C¸GS25] 关于 SZ 方案满足“强签名不可压缩性”的断言存在缺陷。SZ 方案之所以无法满足该属性，是因为签名算法需要同时访问前向和反向预言机（$\mathcal{P}$ 和 $\mathcal{P}^{-1}$），这使得攻击者能够为不在压缩列表中的密钥生成签名。
新构造修改了方案，使得签名仅需调用对偶预言机 $\mathcal{D}$，而验证则使用另一个单独的预言机 $\mathcal{D}_0$。这种分离实现了强签名不可压缩性的证明，从而恢复了 CGS 所提议的量子火应用的有效性。

主要贡献与结果

效率提升

与 SZ 构造相比，本文实现了资源复杂度的显著降低：

• 签名密钥大小： 从 $\Theta(\lambda^4)$ 量子比特减少到 $\Theta(\lambda^2)$ 量子比特。
• 签名大小： 从 $\Theta(\lambda^3)$ 比特减少到 $\Theta(\lambda^2)$ 比特。
• 公开密钥大小： 从 $\Theta(\lambda^3)$ 比特（预言机模型）和 $\Theta(\lambda^5)$ 比特（纯模型）减少到 $\Theta(\lambda^2)$ 比特（预言机模型）和 $\Theta(\lambda^4)$ 比特（纯模型）。
• 运行时间： 签名算法所需的预言机查询次数显著减少，避免了与 QSVT/重写电路相关的 $\Theta(\lambda)$ 开销。

安全性与正确性

• 完美正确性： 与 SZ 不同，新方案保证能以概率 1 生成有效签名。
• 强安全性： 该方案实现了强不可伪造性，即无法为不同的消息生成有效的签名，也无法为同一消息生成不同的签名。
• 不可压缩性： 该方案满足强签名不可压缩性，这是实现量子火等高级应用所必需的属性。

理论结果

论文通过两个主要定理形式化了这些改进：

1. 定理 1.1： 确立了对于多项式长度的消息，在经典预言机模型（无条件）和纯模型（假设后量子不可区分性混淆和 LWE）下，存在具有完美正确性的高效 OSS 方案。
2. 定理 1.2： 证明了这种新型不可压缩 OSS 方案能够实现具有完美正确性的公钥量子火和密钥火（key-fire）方案，纠正了 CGS [C¸GS25] 工作中的错误。

重要意义

本文声称提供了一个比现有最先进的一次性签名方案更“简单、直接且高效”的替代方案。通过绕过以往工作中使用的复杂归约 (DS [DS22]) 和并行重复策略，作者实现了密钥和签名大小的二次方级提升。

这项工作的意义在于两个方面：

1. 实际效率： 通过将量子比特和比特需求从四次/三次规模降低到二次方规模，使量子签名方案在实践上变得更加可行。
2. 基础性修正： 它弥补了文献中关于 OSS 不可压缩性的关键空白。通过修复不可压缩性属性，本文验证并实现了“量子火”及相关原语的构建，这些原理此前虽被声称可能，但其依赖于对 SZ 方案的错误假设。

作者指出，尽管他们已经显著优化了参数，但若要在预言机模型中进一步优化至 $\Theta(\lambda)$，可能需要全新的技术，因为目前的瓶颈在于对无对偶情况（dual-free case）的分析。同样，改进纯模型参数仍然是一个开放性问题。