2025-11-14T17:16:11.719199

Quantum One-Time Protection of any Randomized Algorithm

Gunn, Movassagh
The meteoric rise in power and popularity of machine learning models dependent on valuable training data has reignited a basic tension between the power of running a program locally and the risk of exposing details of that program to the user. At the same time, fundamental properties of quantum states offer new solutions to data and program security that can require strikingly few quantum resources to exploit, and offer advantages outside of mere computational run time. In this work, we demonstrate such a solution with quantum one-time tokens. A quantum one-time token is a quantum state that permits a certain program to be evaluated exactly once. One-time security guarantees, roughly, that the token cannot be used to evaluate the program more than once. We propose a scheme for building quantum one-time tokens for any randomized classical program, which include generative AI models. We prove that the scheme satisfies an interesting definition of one-time security as long as outputs of the classical algorithm have high enough min-entropy, in a black box model. Importantly, the classical program being protected does not need to be implemented coherently on a quantum computer. In fact, the size and complexity of the quantum one-time token is independent of the program being protected, and additional quantum resources serve only to increase the security of the protocol. Due to this flexibility in adjusting the security, we believe that our proposal is parsimonious enough to serve as a promising candidate for a near-term useful demonstration of quantum computing in either the NISQ or early fault tolerant regime.
academic

Quantum One-Time Protection of any Randomized Algorithm

基本信息

  • 论文ID: 2411.03305
  • 标题: Quantum One-Time Protection of any Randomized Algorithm
  • 作者: Sam Gunn, Ramis Movassagh (Google Quantum AI)
  • 分类: quant-ph cs.CR
  • 发表时间: 2025年1月3日 (arXiv v2)
  • 论文链接: https://arxiv.org/abs/2411.03305v2

摘要

机器学习模型的快速发展和对有价值训练数据的依赖重新点燃了本地运行程序的便利性与向用户暴露程序细节风险之间的基本矛盾。同时，量子态的基本性质为数据和程序安全提供了新的解决方案，这些方案只需要极少的量子资源就能实现，并且提供了超越计算运行时间的优势。本工作通过量子一次性令牌展示了这样的解决方案。

量子一次性令牌是一种允许特定程序恰好被评估一次的量子态。一次性安全性保证该令牌不能被用于多次评估程序。作者提出了为任意随机化经典程序（包括生成式AI模型）构建量子一次性令牌的方案，并在黑盒模型中证明了该方案满足有趣的一次性安全定义，前提是经典算法的输出具有足够高的最小熵。

研究背景与动机

问题定义

软件商业化面临核心困境：如何在不放弃所有权的情况下分发软件？传统解决方案存在固有的可用性与排他性权衡：

  1. 程序混淆方案：分发混淆版本的软件，但存在盗版风险且用户可以无限次运行
  2. 服务器查询方案：保持软件在服务器上响应用户查询，但降低了可用性且需要持续通信

问题重要性

在生成式AI时代，这个问题变得更加严重，因为：

  • 软件可能极其有价值
  • 可能泄露私人信息
  • 按查询付费模型日益普遍

现有方法局限性

经典信息总是可以被复制，一旦软件被分发，用户就可以任意多次查询或复制它。这种局限性使得传统方案无法同时实现高可用性和强排他性。

量子解决方案的优势

量子信息的不可克隆性提供了改进现有解决方案的可能：

  • 量子复制保护：改进方案(1)，防止程序被复制但允许无限次运行
  • 量子一次性程序：改进方案(2)，消除按查询付费模型中的在线通信需求

核心贡献

  1. 首个通用量子令牌化程序方案：提出了第一个使用量子信息保护任意随机化算法的通用方案，不局限于特定密码学功能
  2. 独立于程序复杂度的量子资源需求：量子令牌的大小和复杂度完全独立于被保护的程序
  3. 理论安全性证明：在黑盒模型中证明了方案满足一次性安全定义
  4. 实用性考虑：方案足够简洁，有望在NISQ或早期容错量子计算时代实现

方法详解

任务定义

构建量子一次性令牌来保护任意随机化算法f：X × R → Y，使得：

  • 令牌允许程序被评估恰好一次
  • 提供一次性安全保证
  • 不需要程序在量子计算机上相干实现

核心构造 (Construction 2)

密码学原语

方案依赖三个密码学原语：

  1. (AuthKeyGen, AuthTokenGen, Sign, Verify)：量子一次性认证方案
  2. Obf：经典程序混淆器
  3. H：哈希函数（建模为随机预言机）

令牌结构

程序令牌包含两部分：

  • |ψ⟩：不依赖于f的不可克隆量子态
  • Obf(P)：依赖于f的混淆经典电路P

算法流程

KeyGen(1^λ, f)：

  1. 采样 sk ← AuthKeyGen(1^λ)
  2. 定义经典电路 P：X × {0,1}^m → Y ∪ {⊥}
    • 计算 Verify(sk, (x,z))，如果拒绝则输出⊥
    • 否则输出 f(x; H(x,z))
  3. 计算混淆 P̂ = Obf(P)
  4. 输出 (sk, P̂)

TokenGen(sk)：

  1. 计算一次性认证令牌 |tk⟩ ← AuthTokenGen(sk)
  2. 输出 |tk⟩

TokenEval(x, |tk⟩, P̂)：

  1. 计算 z ← Sign(x, |tk⟩)
  2. 计算并输出 P̂(x,z)

量子一次性认证方案

定义 (Definition 1)

量子一次性认证方案需满足：

  • 正确性：合法签名能通过验证
  • 一次性不可伪造性：任何多项式时间对手无法生成两个不同的有效签名对

具体构造 (Construction 1)

基于隐藏子空间态的单比特认证：

AuthKeyGen(1^λ)：采样随机子空间 A ⊆ F₂^λ，维数为λ/2

AuthTokenGen(A)：输出 |A⟩ = 2^(-λ/4) ∑_{a∈A} |a⟩

Sign(x, |A⟩)：

  • 若 x = 0：在标准基下测量并输出结果
  • 若 x = 1：在Hadamard基下测量并输出结果

Verify(A, (x,z))：验证 z 是否在相应子空间中

技术创新点

  1. 程序无关的量子资源：量子态|ψ⟩不依赖于被保护的程序，使得复杂程序可以用小型量子设备保护
  2. 随机性绑定机制：通过H(x,z)确定随机性，将输入、认证和输出有效"混合"
  3. 坍缩哈希函数性质：利用测量输出会使输入和认证标签坍缩的量子特性

理论分析

安全性定义

黑盒一次性程序游戏 G^BB-OTP

  1. 对手获得|ψ⟩和对P̂的量子预言机访问
  2. 对手提交量子查询，挑战者计算P̂并测量结果y
  3. 如果y = ⊥则游戏中止，对手失败
  4. 对手提交第二个查询，挑战者测量得到y'
  5. 如果y' ∉ {y, ⊥}则对手获胜

主要定理

定理2：如果对于每个x ∈ X，f(x;r)对随机r的最小熵至少为poly(λ)，且量子一次性认证方案安全，则Construction 2对f是黑盒一次性安全的。

证明核心：坍缩哈希函数

引理1：设f：{0,1}^m × {0,1}^n → Y，如果对所有x，f(x;r)对随机r的最小熵至少为τ，则当H为随机预言机时，函数g^H：x ↦ f(x;H(x))是坍缩的，优势为O(q³·2^(-τ))。

证明思路

使用压缩预言机技术：

  1. 证明Invert_f与CPhsO几乎可交换
  2. 利用最小熵条件限制碰撞概率
  3. 通过测量输出实现输入坍缩

实验与应用

量子资源需求

  • 如果使用CLLZ21的一次性签名方案，用户只需要：
    • 存储常数大小的量子态
    • 在标准基和Hadamard基中进行测量

实用性考虑

  1. 近期可行性：量子能力需求独立于程序复杂度
  2. 可扩展安全性：额外量子资源仅用于提高安全性
  3. 经典通信替代：可通过远程态制备协议用经典通信替代量子通信

适用场景

  • 生成式AI模型保护
  • 按查询付费的软件服务
  • 需要离线执行的敏感程序

相关工作

历史发展

  • GKR08：最初研究一次性程序（无量子计算）
  • BGS13：提出量子一次性程序概念，证明确定性程序的不可能性
  • BS23：在标准模型中保护签名函数
  • GLR+24：并行独立工作，提供更强的安全定义

本文贡献对比

  • 首个保护任意随机化算法的通用方案
  • 简洁的自包含安全证明
  • 实用性导向的设计考虑

结论与讨论

主要结论

  1. 量子一次性令牌可以保护任意随机化经典程序
  2. 安全性依赖于程序输出的高最小熵
  3. 量子资源需求独立于程序复杂度
  4. 方案在NISQ时代具有实现可行性

局限性

  1. 高熵要求：程序输出必须具有足够高的最小熵
  2. 黑盒模型：安全性证明在理想化的黑盒模型中
  3. 确定性程序限制：不适用于确定性程序（由BGS13的不可能结果限制）
  4. 复杂的经典通信协议：虽然理论上可以用经典通信替代量子通信，但协议极其复杂

未来方向

  1. 在标准模型中的安全性分析
  2. 降低对程序输出熵的要求
  3. 实际量子设备上的实现和测试
  4. 与GLR+24工作的关系分析

深度评价

优点

  1. 理论创新：首次提出保护任意随机化算法的通用量子方案
  2. 实用设计：量子资源需求与程序复杂度解耦，增强了实用性
  3. 严格证明：提供了基于坍缩哈希函数的简洁安全性证明
  4. 应用前景：直接适用于当前热门的生成式AI保护需求

不足

  1. 理想化假设：依赖黑盒模型和随机预言机模型
  2. 熵条件限制：高最小熵要求可能限制实际应用范围
  3. 实现复杂性：虽然理论上优雅，实际实现仍面临工程挑战
  4. 安全定义：作者承认这不是一次性安全的最终定义

影响力

  1. 学术价值：为量子密码学中的程序保护问题提供了新的理论框架
  2. 实用潜力：为保护有价值的AI模型提供了可能的量子解决方案
  3. 技术推进：推动了不可克隆密码学的发展
  4. 启发意义：为量子计算在近期的实用应用提供了新思路

适用场景

  • 需要保护知识产权的AI服务提供商
  • 按使用付费的软件许可模式
  • 对安全性要求极高的敏感算法保护
  • 量子优势演示的候选应用

参考文献

本文引用了量子密码学、不可克隆密码学和量子计算复杂性理论的重要工作，特别是：

  • Aar09 Aaronson关于量子复制保护的开创性工作
  • BS23 Ben-David和Sattath关于量子数字签名的工作
  • CLLZ21 关于隐藏陪集和不可克隆密码学的构造
  • Zha19 Zhandry关于压缩预言机技术的工作

该论文在理论量子密码学领域做出了重要贡献，提供了一个优雅的解决方案来平衡软件分发中的可用性和安全性矛盾。虽然仍有实用化的挑战，但为量子计算在密码学应用中的近期实现提供了有希望的方向。