2025-11-15T00:07:12.138794

Multi-Copy Security in Unclonable Cryptography

Çakan, Goyal, Kitagawa et al.
Unclonable cryptography leverages the quantum no-cloning principle to copy-protect cryptographic functionalities. While most existing works address the basic single-copy security, the stronger notion of multi-copy security remains largely unexplored. We introduce a generic compiler that upgrades collusion-resistant unclonable primitives to achieve multi-copy security, assuming only one-way functions. Using this framework, we obtain the first multi-copy secure constructions of public-key quantum money (termed quantum coins), single-decryptor encryption, unclonable encryption, and more. We also introduce an extended notion of quantum coins, called upgradable quantum coins, which allow weak (almost-public) verification under weaker assumptions and can be upgraded to full public verification under stronger assumptions by the bank simply publishing additional classical information. Along the way, we give a generic compiler that upgrades single-copy secure single-decryptor encryption to a collusion-resistant one, assuming the existence of functional encryption, and construct the first multi-challenge secure unclonable encryption scheme, which we believe are of independent interest.
academic

Multi-Copy Security in Unclonable Cryptography

基本信息

  • 论文ID: 2510.12626
  • 标题: Multi-Copy Security in Unclonable Cryptography
  • 作者: Alper Çakan, Vipul Goyal, Fuyuki Kitagawa, Ryo Nishimaki, Takashi Yamakawa
  • 分类: quant-ph cs.CR (量子物理，密码学与安全)
  • 发表时间: 2024年10月14日 (arXiv预印本)
  • 论文链接: https://arxiv.org/abs/2510.12626v1

摘要

不可克隆密码学利用量子不可克隆原理来保护密码学功能免于被复制。虽然大多数现有工作解决了基本的单拷贝安全性，但更强的多拷贝安全性概念仍然很大程度上未被探索。本文引入了一个通用编译器，仅假设单向函数的存在，就能将抗共谋的不可克隆原语升级为实现多拷贝安全性。利用这个框架，作者获得了公钥量子货币（称为量子硬币）、单解密器加密、不可克隆加密等的首个多拷贝安全构造。文章还引入了量子硬币的扩展概念——可升级量子硬币，在较弱假设下允许弱验证，并可通过银行发布额外的经典信息在更强假设下升级为完整的公开验证。

研究背景与动机

核心问题

本文要解决的核心问题是从单拷贝安全性到多拷贝安全性的升级问题。在不可克隆密码学中，传统研究主要关注1→2不可克隆性设置（敌手获得一个纯量子态副本但无法产生两个副本），而更一般的q→q+1设置（敌手获得q个副本但无法产生q+1个副本）研究较少。

问题重要性

多拷贝安全性具有重要意义：

  1. 操作优势：纯态的相等性可以通过SWAP测试有效检验，这在应用中很有用
  2. 匿名性：相同纯态的多个副本天然提供匿名性保障
  3. 概念动机：多个纯态副本对应相同的物理对象，而从同一分布采样的态可能是不同的

现有方法局限性

现有的多拷贝安全性结果非常有限：

  • Mosca和Stebila提出量子硬币概念但仅在量子预言机模型中构造
  • 一些工作仅实现了较弱的预言机安全性概念
  • 缺乏从抗共谋安全性到多拷贝安全性的通用转换方法

核心贡献

  1. 提出通用编译器：给出了将抗共谋不可克隆原语升级为多拷贝安全的通用编译器，仅需假设单向函数存在
  2. 首个多拷贝安全构造：获得了量子硬币、单解密器加密、不可克隆加密等的首个多拷贝安全构造
  3. 可升级量子硬币：引入新概念，允许在不同假设强度下提供不同级别的安全保障
  4. 技术工具：构造了从单拷贝到抗共谋的单解密器加密编译器，以及首个多挑战安全的不可克隆加密方案

方法详解

任务定义

多拷贝安全性：对于任何多项式t，给定t个相同纯态的副本，敌手无法产生t+1个有效副本。这与抗共谋安全性不同，后者给定的是t个独立生成的态。

核心技术：净化编译器 (Purification Compiler)

主要定理（Theorem 7）

设GenState是具有经典确定输出的QPT算法，随机性长度为r(λ)。对于PRS密钥k和PRF密钥K，定义：

∣ψz,k,K⟩=∑xαk,x∣x⟩⊗∣φz,F(K,x)⟩|ψ_{z,k,K}⟩ = \sum_x α_{k,x}|x⟩ ⊗ |φ_{z,F(K,x)}⟩

其中∑xαk,x∣x⟩\sum_x α_{k,x}|x⟩是PRS方案产生的态，∣φz,F(K,x)⟩|φ_{z,F(K,x)}⟩是调用GenState(z;F(K,x))得到的态。

核心思想：通过PRS和PRF，可以将t个独立生成的态转换为t个相同态的副本，且在计算上不可区分。

编译器工作原理

  1. 态查询阶段：挑战者接收敌手请求的数量t，原本运行GenState(st) t次使用独立随机性
  2. 修改后：挑战者输出t个相同的态： ∑xαki,x∣x⟩⊗∣φx⟩\sum_x α_{k_i,x}|x⟩ ⊗ |φ_x⟩ 其中∣φx⟩=GenState(st;F(Ki,x))|φ_x⟩ = \text{GenState}(st; F(K_i,x))
  3. 安全性：基于PRS和PRF的安全性，修改后的实验与原实验在计算上不可区分

应用实例

1. 量子硬币构造

基于PRS的编译器：

  • 设置：使用公钥迷你方案、数字签名和PRS
  • 银行状态：包含签名密钥、PRF密钥和PRS密钥
  • 钞票生成：创建态∣|⟩ = \sum_x α_x|x⟩|sn_x⟩|\text{Sign}(sgk, sn_x)⟩|x⟩_x⟩
  • 验证：测量除迷你钞票寄存器外的所有寄存器，验证签名和迷你钞票

2. 单解密器加密

从单密钥到抗共谋的编译器：

  • 使用功能加密作为中间层
  • 构造电路REone.pk处理不同模式的加密
  • 通过标签排序确保安全性证明中的归约

3. 不可克隆加密

从SDE到UE的转换：

  • 交换密文和密钥的角色
  • 利用一次性填充技术
  • 基于抗共谋相同挑战搜索安全性

实验设置

理论分析框架

本文主要进行理论分析，通过一系列混合实验证明安全性：

  1. 混合序列：构造计算上不可区分的混合实验序列
  2. 归约论证：将新构造的安全性归约到底层原语的安全性
  3. 参数选择：通过适当的参数选择确保安全性损失可忽略

安全性证明技术

量子硬币安全性证明

  • Hyb0到Hyb1：PRF安全性
  • Hyb1到Hyb2：量子态只读一次小范围分布引理
  • 后续混合：BZ安全数字签名和迷你方案安全性

阈值实现技术

使用Zhandry等人的阈值实现技术：

  • TI_t(P)：对POVM P的阈值实现
  • 性质：如果测试通过，后测量态成功概率至少为t

实验结果

主要理论结果

构造效率

  1. 量子硬币：基于子空间隐藏混淆和单向函数
  2. 单解密器加密：基于多项式安全iO和单向函数
  3. 不可克隆加密：基于多项式安全iO和单向函数

安全性保证

  • 多拷贝安全性：对任意多项式数量的副本
  • 标准模型：不依赖随机预言机
  • 最优假设：相比现有工作假设更弱

比较分析

与现有工作对比

vs. Poremba等人PRV24：

  • 本文：无界多拷贝安全性，标准安全概念
  • PRV24：有界多拷贝，预言机安全概念
  • 假设强度：本文需要iO，PRV24仅需单向函数

vs. Ananth等人AMP25：

  • 本文：标准认证删除安全性
  • AMP25：预言机安全概念
  • 适用场景：本文支持可重用和公钥设置

相关工作

不可克隆密码学发展

  1. 量子货币：从Wiesner的共轭编码到现代公钥方案
  2. 拷贝保护：程序的量子拷贝保护
  3. 安全租赁：密钥的临时使用权转让
  4. 认证删除：可证明的数据删除

多拷贝vs抗共谋

  • 抗共谋：多个独立生成的态
  • 多拷贝：相同纯态的多个副本
  • 技术差异：需要不同的分析技术和安全归约

结论与讨论

主要结论

  1. 首次给出了抗共谋到多拷贝安全性的通用编译器
  2. 解决了量子硬币在标准模型中的构造问题
  3. 实现了多项重要不可克隆原语的多拷贝安全版本

局限性

  1. 假设强度：某些构造需要较强的密码学假设（如iO）
  2. 效率问题：编译器可能引入额外的计算开销
  3. 应用范围：要求底层算法具有经典确定输出

未来方向

  1. 假设优化：寻求基于更弱假设的构造
  2. 效率改进：优化编译器的具体实现
  3. 新应用：探索多拷贝安全性在其他密码原语中的应用

深度评价

优点

  1. 理论突破：解决了多拷贝安全性这一重要理论问题
  2. 通用性：提供了适用于多种原语的统一框架
  3. 技术创新：巧妙结合了PRS、PRF和量子测试技术
  4. 完整性：从理论框架到具体构造都给出了完整方案

不足

  1. 实用性：基于较强的理论假设，实际部署可能面临挑战
  2. 效率分析：缺乏具体的效率分析和优化讨论
  3. 参数选择：某些安全参数的选择缺乏具体指导

影响力

  1. 理论贡献：为不可克隆密码学提供了重要的理论工具
  2. 启发意义：为后续研究提供了新的思路和方法
  3. 应用潜力：在量子密码学和区块链等领域有应用前景

适用场景

  1. 量子货币系统：需要防伪和匿名性的数字货币
  2. 数字版权保护：软件和内容的拷贝保护
  3. 安全多方计算：量子环境下的隐私保护计算

参考文献

论文引用了量子密码学、不可克隆密码学和相关数学工具的重要文献，包括：

  • Wiesner的量子货币原始工作
  • Aaronson-Christiano的公钥量子货币
  • Ji-Liu-Song的伪随机量子态
  • Zhandry的量子测试技术
  • 近期的不可克隆加密和安全租赁工作

总体评价：这是一篇高质量的理论密码学论文，解决了不可克隆密码学中的重要开放问题，提供了优雅的理论框架和具体构造，对该领域的发展具有重要推动作用。