Multi-Copy Security in Unclonable Cryptography

Basic Information

• Paper ID: 2510.12626
• Title: Multi-Copy Security in Unclonable Cryptography
• Authors: Alper Çakan, Vipul Goyal, Fuyuki Kitagawa, Ryo Nishimaki, Takashi Yamakawa
• Classification: quant-ph cs.CR (Quantum Physics, Cryptography and Security)
• Publication Date: October 14, 2024 (arXiv preprint)
• Paper Link: https://arxiv.org/abs/2510.12626v1

Abstract

Unclonable cryptography leverages the quantum no-cloning principle to protect cryptographic functionalities from being copied. While most existing work addresses basic single-copy security, the stronger notion of multi-copy security remains largely unexplored. This paper introduces a universal compiler that, assuming only the existence of one-way functions, upgrades collusion-resistant unclonable primitives to achieve multi-copy security. Using this framework, the authors obtain the first multi-copy secure constructions of public-key quantum money (termed quantum coins), single-decryptor encryption, and unclonable encryption. The paper also introduces an extended concept of quantum coins—upgradeable quantum coins—which allow weak verification under weaker assumptions and can be upgraded to full public verification through additional classical information released by the bank under stronger assumptions.

Research Background and Motivation

Core Problem

The core problem addressed in this paper is the upgrade from single-copy security to multi-copy security. In unclonable cryptography, traditional research primarily focuses on the 1→2 unclonability setting (where an adversary obtains one copy of a pure quantum state but cannot produce two copies), while the more general q→q+1 setting (where an adversary obtains q copies but cannot produce q+1 copies) has received less attention.

Problem Significance

Multi-copy security is significant for several reasons:

1. Operational Advantage: Equality of pure states can be efficiently verified through SWAP tests, which is useful in applications
2. Anonymity: Multiple copies of identical pure states naturally provide anonymity guarantees
3. Conceptual Motivation: Multiple copies of a pure state correspond to the same physical object, whereas states sampled from the same distribution may be different

Limitations of Existing Approaches

Existing multi-copy security results are very limited:

• Mosca and Stebila proposed the quantum coin concept but only constructed it in the quantum oracle model
• Some works only achieve weaker oracle security notions
• Lack of universal conversion methods from collusion-resistant security to multi-copy security

Core Contributions

1. Universal Compiler: Presents a universal compiler that upgrades collusion-resistant unclonable primitives to achieve multi-copy security, requiring only the existence of one-way functions
2. First Multi-Copy Secure Constructions: Obtains the first multi-copy secure constructions of quantum coins, single-decryptor encryption, and unclonable encryption
3. Upgradeable Quantum Coins: Introduces a new concept allowing different levels of security guarantees under different assumption strengths
4. Technical Tools: Constructs a compiler from single-key to collusion-resistant single-decryptor encryption, and the first multi-challenge secure unclonable encryption scheme

Methodology Details

Task Definition

Multi-Copy Security: For any polynomial t, given t copies of the same pure state, an adversary cannot produce t+1 valid copies. This differs from collusion-resistant security, which provides t independently generated states.

Core Technique: Purification Compiler

Main Theorem (Theorem 7)

Let GenState be a QPT algorithm with classical deterministic output and randomness length r(λ). For PRS key k and PRF key K, define:

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

where $\sum_x α_{k,x}|x⟩$ is the state produced by the PRS scheme, and $|φ_{z,F(K,x)}⟩$ is the state obtained by invoking GenState(z;F(K,x)).

Core Idea: Through PRS and PRF, t independently generated states can be converted to t copies of the same state, computationally indistinguishable from the original.

Compiler Operation

1. State Query Phase: The challenger receives the adversary's request for t copies, originally running GenState(st) t times with independent randomness
2. After Modification: The challenger outputs t identical states: $\sum_x α_{k_i,x}|x⟩ ⊗ |φ_x⟩$ where $|φ_x⟩ = \text{GenState}(st; F(K_i,x))$
3. Security: Based on PRS and PRF security, the modified experiment is computationally indistinguishable from the original

Application Examples

1. Quantum Coin Construction

PRS-Based Compiler:

• Setup: Uses public-key mini-scheme, digital signatures, and PRS
• Bank State: Contains signing key, PRF key, and PRS key
• Coin Generation: Creates state $|⟩ = \sum_x α_x|x⟩|sn_x⟩|\text{Sign}(sgk, sn_x)⟩|$_x⟩$
• Verification: Measures all registers except the mini-coin register, verifies signatures and mini-coins

2. Single-Decryptor Encryption

Compiler from Single-Key to Collusion-Resistant:

• Uses functional encryption as an intermediate layer
• Constructs circuit REone.pk handling different encryption modes
• Ensures security through label ordering in reduction proofs

3. Unclonable Encryption

Conversion from SDE to UE:

• Exchanges roles of ciphertexts and keys
• Leverages one-time pad techniques
• Based on collusion-resistant same-challenge search security

Experimental Setup

Theoretical Analysis Framework

The paper primarily conducts theoretical analysis, proving security through a series of hybrid experiments:

1. Hybrid Sequence: Constructs computationally indistinguishable hybrid experiment sequences
2. Reduction Arguments: Reduces the security of new constructions to the security of underlying primitives
3. Parameter Selection: Ensures negligible security loss through appropriate parameter choices

Security Proof Techniques

Quantum Coin Security Proof

• Hyb0 to Hyb1: PRF security
• Hyb1 to Hyb2: Quantum state read-once small-range distribution lemma
• Subsequent Hybrids: BZ secure digital signatures and mini-scheme security

Threshold Implementation Technique

Uses Zhandry et al.'s threshold implementation technique:

• TI_t(P): Threshold implementation of POVM P
• Properties: If the test passes, the post-measurement state succeeds with probability at least t

Experimental Results

Main Theoretical Results

Construction Efficiency

1. Quantum Coins: Based on subspace hiding obfuscation and one-way functions
2. Single-Decryptor Encryption: Based on polynomial-secure iO and one-way functions
3. Unclonable Encryption: Based on polynomial-secure iO and one-way functions

Security Guarantees

• Multi-Copy Security: For arbitrary polynomial numbers of copies
• Standard Model: Independent of random oracles
• Optimal Assumptions: Weaker assumptions compared to existing work

Comparative Analysis

Comparison with Existing Work

vs. Poremba et al. PRV24:

• This work: Unbounded multi-copy security, standard security notions
• PRV24: Bounded multi-copy, oracle security notions
• Assumption strength: This work requires iO, PRV24 only requires one-way functions

vs. Ananth et al. AMP25:

• This work: Standard certified deletion security
• AMP25: Oracle security notions
• Applicable scenarios: This work supports reusable and public-key settings

Related Work

Development of Unclonable Cryptography

1. Quantum Money: From Wiesner's conjugate coding to modern public-key schemes
2. Copy Protection: Quantum copy protection of programs
3. Secure Rental: Temporary usage rights transfer of keys
4. Certified Deletion: Provable data deletion

Multi-Copy vs. Collusion-Resistant

• Collusion-Resistant: Multiple independently generated states
• Multi-Copy: Multiple copies of the same pure state
• Technical Differences: Require different analysis techniques and security reductions

Conclusions and Discussion

Main Conclusions

1. First universal compiler from collusion-resistant to multi-copy security
2. Resolves quantum coin construction in the standard model
3. Achieves multi-copy secure versions of several important unclonable primitives

Limitations

1. Assumption Strength: Some constructions require stronger cryptographic assumptions (e.g., iO)
2. Efficiency Issues: The compiler may introduce additional computational overhead
3. Application Scope: Requires underlying algorithms to have classical deterministic output

Future Directions

1. Assumption Optimization: Seek constructions based on weaker assumptions
2. Efficiency Improvement: Optimize concrete implementations of the compiler
3. New Applications: Explore applications of multi-copy security in other cryptographic primitives

In-Depth Evaluation

Strengths

1. Theoretical Breakthrough: Resolves the important theoretical problem of multi-copy security
2. Generality: Provides a unified framework applicable to multiple primitives
3. Technical Innovation: Cleverly combines PRS, PRF, and quantum testing techniques
4. Completeness: Provides complete solutions from theoretical framework to concrete constructions

Weaknesses

1. Practicality: Based on strong theoretical assumptions, practical deployment may face challenges
2. Efficiency Analysis: Lacks concrete efficiency analysis and optimization discussion
3. Parameter Selection: Lacks concrete guidance for certain security parameter choices

Impact

1. Theoretical Contribution: Provides important theoretical tools for unclonable cryptography
2. Inspirational Value: Offers new ideas and methods for subsequent research
3. Application Potential: Has application prospects in quantum cryptography and blockchain

Applicable Scenarios

1. Quantum Money Systems: Digital currencies requiring anti-counterfeiting and anonymity
2. Digital Rights Protection: Copy protection of software and content
3. Secure Multi-Party Computation: Privacy-preserving computation in quantum environments

References

The paper cites important literature in quantum cryptography, unclonable cryptography, and related mathematical tools, including:

• Wiesner's original quantum money work
• Aaronson-Christiano's public-key quantum money
• Ji-Liu-Song's pseudorandom quantum states
• Zhandry's quantum testing techniques
• Recent work on unclonable encryption and secure rental

Overall Assessment: This is a high-quality theoretical cryptography paper that resolves an important open problem in unclonable cryptography, providing an elegant theoretical framework and concrete constructions with significant implications for the field's development.