作者: Gopikrishnan Muraleedharan, Minh Thuy Truc Pham, Vir Pathak, Thomas Gardner, Chuanqi Zhang, QPerfect, Gavin K. Brennen

1. 核心物理图象

这篇文章的核心物理图象是将量子力学中“量子态不可克隆”这一基本物理定律，直接转变为一个强大的密码学工具。想象一下，你的签名密钥不是一个可以无限复制的数字文件，而是一个脆弱的量子态。当你用它签名时，这个量子态会不可避免地“自毁”（被测量），从而在物理上保证了这把密钥一生只能用一次。这就叫“一次性签名”。

该论文做出了以下贡献：

1. 首次给出了一个完整、可实现的量子电路级别的算法来生成和消费这种“一次性密钥”。
2. 提出了更高效的多比特消息签名方法，替代了以往逐个比特签名的复杂流程。
3. 对实现该算法所需的量子比特数和量子门数量进行了精确计算和资源分析，为该方案的实用化铺平了道路。

2. 关键术语解释

• 一次性签名 (One-Shot Signature, OSS)：一种新型的数字签名。它的核心特性是，用于签名的量子密钥在完成一次签名后，通过测量过程被物理消耗掉，无法复用。这从根本上杜绝了密钥的复制和盗用。

  • 在本文中的作用：它是文章实现的终极目标。文章提供了实现这种签名的具体量子电路方案。

• 可穿刺伪随机函数 (Puncturable Pseudorandom Function, PPRF)：一种特殊的伪随机函数。除了常规功能外，它额外允许你“刺穿”掉某个或某些特定输入点的函数值，而其他所有点的函数值依然可以被正确计算。

  • 在本文中的作用：它是构造一次性签名方案的核心密码学原语。文章用“金-戈-米-卡 (GGM) 树”结构的具体电路来实现它，用于生成隐藏在秘钥背后的、独一无二的“隐藏仿射陪集”。

• 隐藏仿射陪集 (Hidden Affine Coset)：一个通过线性代数操作（平移和线性变换）得到的、被隐藏起来的点集合。具体来说，它是由PPRF的输出确定的仿射子空间（即，该空间中所有点都是通过一个矩阵和一个向量计算出来的）。

  • 在本文中的作用：量子签名密钥就是对这个隐藏陪集所有点的均匀叠加态。签名时，通过测量这个叠加态，可以得到该陪集中的一个特定点，作为对消息的签名。

3. 主要贡献 (Key Contributions)

1. 首个可实现的量子电路级一次性签名方案：之前的理论工作只给出了“一次性签名”的协议框架和安全证明。这篇工作首次将这个协议落地，明确给出了量子密钥生成(KeyGen)、签密(Sign)和验签(Verify)算法的完整量子线路结构，并提供了详细的量子比特和量子门资源开销分析。

2. 高效的全局签密方法：在如何对多比特消息进行签名时，本文提出了一个创新的“全局测量和翻译”方案。它只需对签名状态进行一次全局相位翻转，就能将测量结果一次性校正到目标消息，而无需像以往方案那样对每个比特进行迭代地测量和修正，极大降低了电路深度和复杂性。

3. 创新的线性代数（线性阵）生成方法：为了高效生成构成密钥的随机线性阵（Grassmannian，格拉斯曼流形，即随机子空间），文章引入了Bruhat分解技术。这种方法能够直接根据伪随机数生成唯一的量子门序列，避免了复杂且难以实现的矩阵求逆和随机采样过程。

4. 研究方法 (Methodology)

作者实现一次性签名的流程如下：

1. 密钥生成 (KeyGen)：

   • 初始化：对所有量子比特施加Hadamard门，创建出所有可能输入状态的均匀叠加态。
   • 量子GGM查找：通过一个可逆的GGM树遍历电路，计算“可穿刺伪随机函数 (PPRF)”，为每一个可能公开的“公钥（y）”生成一个独特的、伪随机的树状密钥。
   • 线性阵生成：利用该伪随机密钥，结合Bruhat分解技术，构建一个线性代数电路。这个电路的作用是动态地生成一个名为“隐藏陪集”的量子叠加态。该陪集由PPRF的输出唯一确定，作为量子签名密钥。
   • 测量：测量该叠加态中的一部分，得到经典的“公钥（y）”，剩下的量子部分就是对应的“量子私钥”。

2. 签密 (Sign)：

   • 校正：用户持有量子私钥（即隐藏陪集的叠加态）。要签名一个消息（m），用户的签密算法会进行Hadamard变换、一个基于消息的全局相位翻转（利用Fourier shift定理），再逆Hadamard变换。这个过程能将量子签名状态修正到与消息m对应的子空间。
   • 测量：测量修正后的量子态，得到一个经典比特串，这个串就是“签名 (σ)”。此过程会消耗掉原有的量子私钥。

3. 验签 (Verify)：

   • 经典检查：验签者收到公钥、消息和签名。他们利用公钥（y）和包含在公共参考串（CRS）中的隐藏PPRF密钥，重新计算出“隐藏陪集”的相关参数。然后，只需要进行简单的经典线性代数计算和比特比较，即可验证签名是否属于该陪集。

5. 实验结果与结论 (Results and Conclusion)

本文通过理论分析，提供了在不同安全参数下实现一次性签名所需的量子逻辑门和量子比特数量。例如，对于安全参数λ=10，该方案需要约2,438个逻辑量子比特和超过6亿个量子门。

结论与展望：

• 贡献：本文成功将一个抽象的一次性签名协议转化为了具体的、可量化分析的量子电路方案，证明了其在理论上的可实现性。其资源分析为未来在物理硬件上的部署提供了关键参考。
• 开放问题：文章明确指出，该方案当前仍是一个“未被混淆的”版本。其安全性依赖于对签名和密钥生成电路中特定组件的隐藏（即混淆）。当前最先进的可混淆密码学工具还不足以高效、安全地混淆本文所需的整个量子电路。因此，实现一个完全安全且实用的一次性签名系统，关键在于未来量子混淆技术的突破。

6. 论文标签 (Tags)

量子算法, 量子信息, 编译与优化

📄 点击此处展开/折叠原文 PDF

原文链接： A quantum algorithm for one-shot signatures