⚛️ quantum physics

Copy-Protection with Correlated Challenges: Point Functions and More via Decisional Coset Monogamy

This paper establishes the first plain-model copy-protection schemes for point functions and general functionalities under correlated challenges, including identical challenges, by introducing and proving security for new definitions of correlated challenge single-decryptor encryption and unclonable puncturable obfuscation based on post-quantum indistinguishability obfuscation and quantum-hard LWE.

Original authors: Amit Behera, Alper Çakan, Vipul Goyal

Published 2026-08-20

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Amit Behera, Alper Çakan, Vipul Goyal

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

In the world of cryptography, the goal has always been to keep secrets safe, but the rules of the game are changing. For decades, security relied on the idea that if you could copy a digital file, you could copy the secret inside it. A decryption key, a password, or a software license could be duplicated perfectly, allowing anyone with a copy to use the protected resource. This is a fundamental difference between the classical world and the quantum world. In the quantum realm, the laws of physics forbid the perfect copying of unknown information. This principle, known as the no-cloning theorem, suggests that it might be possible to encode a secret into a quantum state that can be used to perform a task, but cannot be split into two separate copies that both remain useful. This concept, called copy protection, promises a future where software or digital keys can be distributed to millions of users, yet no two of them can collude to create a second, fully functional version of the key.

For years, researchers have struggled to turn this theoretical promise into a practical reality. While they could prove that copy protection worked under very specific, artificial conditions, they hit a wall when trying to address the most natural and common scenario: what happens when two people receive the exact same challenge? In many real-world situations, such as a broadcast signal or a file sent to a group, every recipient gets the same data. Previous attempts to secure quantum keys against copying failed when the attackers were given identical information, leaving a gap between theory and the messy reality of how data is actually shared.

A team of researchers has now bridged this gap, providing the first provably secure method for copy protection in this identical-challenge setting. Their work, which builds on the foundations of quantum mechanics and advanced cryptographic assumptions, demonstrates that it is possible to protect decryption keys and general software programs even when two adversaries receive the exact same encrypted message and try to split the quantum key between them. The researchers did not just find a way to make this work; they also reorganized the entire field's understanding of what security means in this context. They showed that previous definitions of security were insufficient and introduced a new, stronger standard that covers all the old cases while adding the ability to handle identical challenges.

The core of their achievement lies in a new mathematical insight about the nature of quantum entanglement. They proved a theorem regarding "coset states," which are specific types of quantum states used to hide information. Their proof shows that if you split such a state between two people, and then give both of them the exact same piece of information to test it, they cannot both succeed in guessing the hidden secret with any significant advantage. This is a profound result because earlier attempts relied on the two attackers receiving different, independent challenges. The new proof works even when the challenges are perfectly correlated or identical, effectively closing the door on a major class of attacks that had previously seemed impossible to defend against.

To achieve this, the researchers constructed a framework that allows for the protection of various types of digital objects. They showed how to apply their new security method to single-decryptor encryption, which is the quantum equivalent of protecting a decryption key. They also extended this to protect general software programs, including simple point functions (which act like digital lockboxes that only open for one specific password) and more complex compute-and-compare programs. Crucially, their solution works in the "plain model," meaning it does not rely on hypothetical, idealized tools that do not exist in the real world. Instead, it relies on standard cryptographic assumptions that are widely believed to be secure against both classical and quantum computers.

The researchers also took the time to clarify the confusing landscape of security definitions that had accumulated over the last decade. They demonstrated that many of the existing definitions were not as strong as previously thought and that some did not imply others. By establishing a clear hierarchy, they showed that their new definition is the "gold standard" because it implies all the previous ones. This means that if a system is secure under their new definition, it is automatically secure under every other definition that has been proposed. This unification provides a solid foundation for future work, ensuring that when we say a quantum key is copy-protected, we mean it in the strongest possible sense.

One of the most significant outcomes of this work is the resolution of a long-standing open question regarding point functions. Since the introduction of quantum copy protection in 2009, researchers had been unable to prove that these simple digital lockboxes could be protected against identical challenges in a realistic setting. The new results finally solve this problem, showing that such protection is possible under standard assumptions. Furthermore, the team extended this success to more complex programs, proving that even sophisticated software can be protected in a way that prevents two users from splitting the key and using it together, even if they are given the exact same input to test.

The technical heart of this breakthrough is a new type of security game involving quantum states. In this game, a quantum state is split between two parties who cannot communicate. They are then given the same challenge and must each output a single bit of information. The researchers proved that no matter how clever the parties are, or how they entangle their quantum states, they cannot both guess the correct bit with a probability significantly better than random chance. This result simplifies the path to secure copy protection by removing the need for complex extraction techniques that were required in previous, less robust methods. It provides a direct and elegant route to security that works for a wide variety of applications.

By combining these new definitions with advanced cryptographic tools like indistinguishability obfuscation and the hardness of certain mathematical problems, the researchers have constructed a complete system for copy protection. This system is not just a theoretical curiosity; it offers a concrete path forward for securing digital assets in a quantum future. It ensures that the unique properties of quantum information can be harnessed to prevent piracy and unauthorized duplication in ways that are fundamentally impossible with classical technology. The work stands as a definitive step toward making quantum copy protection a practical reality, resolving decades of uncertainty and providing a robust framework for the next generation of cryptographic security.

Technical Summary: Copy-Protection with Correlated Challenges

1. Problem Statement

Quantum copy-protection aims to encode a functionality into a reusable quantum state such that it cannot be split into two distinct states (held by "freeloader" adversaries) that remain simultaneously useful. While significant progress has been made in constructing copy-protection schemes for general functionalities and decryption keys, the field faces two critical limitations:

Definitional Fragmentation: For fundamental primitives like Single-Decryptor Encryption (SDE), there exist seven distinct security notions in the literature. The relationships between these notions are unclear, and no single "gold standard" definition is known to imply all others. Crucially, it is unknown whether standard indistinguishability security implies search security for SDE.
The Identical-Challenge Gap: Existing constructions primarily achieve security against independently sampled challenges. However, a more natural and practically relevant security notion is identical-challenge security, where two adversaries receive the exact same challenge (e.g., the same ciphertext or the same input point). This notion is connected to unclonable bits and the copy-protection of point functions. Despite being an open question since Georgiou and Zhandry (2020), no provably secure construction for identical-challenge SDE or general copy-protection exists in the plain model under standard assumptions.

The central problem addressed is whether one can define a unified, strong security notion that captures these natural use cases (including identical challenges) and achieve constructions satisfying this notion in the plain model.

2. Methodology and Technical Core

The authors resolve these issues through a combination of definitional unification and a novel quantum information-theoretic tool.

A. Definitional Unification

The paper introduces Correlated-Challenge Security for both SDE and Unclonable Puncturable Obfuscation (UPO).

Correlated-Challenge SDE (SDE-CORR): This definition allows the challenge bits for the two adversaries to be arbitrarily correlated, provided their marginal distributions remain uniform. This subsumes both independent-challenge and identical-challenge settings.
Correlated-Challenge UPO: Similarly, this definition allows challenge points and auxiliary information to be arbitrarily correlated. It generalizes previous UPO definitions to include auxiliary information leakage, which is crucial for applications like compute-and-compare programs.

The authors establish a hierarchy of definitions, proving that SDE-CORR implies all seven prior SDE security notions, including the long-sought identical-challenge security. They also clarify that standard indistinguishability (CPA) security does not imply search security in general, and that independent-challenge security does not imply identical-challenge security.

B. The Decisional Coset Monogamy Theorem

The technical heart of the paper is a new Decisional Coset Monogamy-of-Entanglement (MOE) Theorem.

The Setup: An adversary receives a coset state $|A_{s,t}\rangle$ (a superposition over a shifted subspace $A+s$ with phase shifts determined by $t$ ). The adversary splits this state between two non-communicating parties, B and C.
The Challenge: The challenger samples a non-zero vector $u \in A$ and a non-zero vector $v \in A^\perp$ , and sends the same pair $(u, v)$ to both B and C.
The Goal: B and C must output a single bit $e = \langle u, t \rangle \oplus \langle v, s \rangle$ .
The Result: The authors prove that the probability of both B and C outputting the correct bit is at most $1/2 + 2^{-\Omega(n)}$ .

Key Innovations in the Proof:

Decisional vs. Search: Unlike previous MOE theorems (e.g., Culf and Vidick) which are "search-style" (requiring the output of full vectors), this is a "decisional" game where parties output a single bit.
Identical Challenges: The challenge $(u, v)$ is identical for both parties. Previous decisional MOE results relied on learnable states (like BB84) or independent challenges. This is the first identical decisional MOE theorem for an unlearnable state family (coset states).
No Extraction: The proof avoids the complex "extraction" techniques (threshold measurements, rewinding) required in previous works to convert search guarantees to decision guarantees. Instead, it uses an information-theoretic argument showing that conditioned on the key and message, the ciphertext is a maximally mixed state on a specific eigenspace, leveraging the structure of Pauli operators.
Computational Variant: The authors extend this to the computational setting using Indistinguishability Obfuscation (iO) and Subspace-Hiding Obfuscation, handling correlated auxiliary information.

C. Construction Strategy

Using the new Decisional Coset MOE theorem, the authors construct:

Correlated-Challenge SDE: They adapt the Kitagawa-Yamakawa (2025) construction. By rewriting the challenge bits using a hidden identical bit and a correlation parameter, they reduce the security of the SDE scheme directly to the Decisional Coset MOE game.
Correlated UPO: They construct a UPO scheme for arbitrary polynomial-size keyed circuits. The security proof involves a sequence of hybrids where the challenge points are punctured, and the values are replaced using injective/lossy functions and universal hashing to simulate the pre-split auxiliary information. The final hybrid reduces to the computational Decisional Coset MOE game.

3. Key Results

The paper provides the following concrete results in the plain model:

SDE Security: Assuming post-quantum Indistinguishability Obfuscation (iO) and One-Way Functions (OWF), there exists an SDE scheme satisfying SDE-CORR. This is the first classical-ciphertext SDE construction satisfying identical-challenge security from standard assumptions.
UPO Security: Assuming post-quantum iO and the quantum hardness of Learning With Errors (LWE), there exists a Correlated UPO scheme for arbitrary polynomial-size circuits. This scheme satisfies security against arbitrary correlated challenge distributions with high min-entropy.
- Note: For the specific case of identical-uniform challenge distributions, the LWE assumption can be replaced with post-quantum OWF.
Copy-Protection Applications: Through the UPO framework, the authors derive the first plain-model copy-protection schemes for:
- Point Functions: With natural identical challenge distributions (resolving Aaronson's 2009 open question).
- $k$ -Point Functions: Generalizations of point functions.
- Compute-and-Compare Programs: With natural identical challenge distributions.
- General Puncturable Functionalities: With unpredictability-style and pseudorandomness-style security, including oracular security (where adversaries have oracle access to the function) for identical challenges.

4. Significance and Claims

The paper claims to resolve several long-standing open problems in quantum cryptography:

Resolution of the Identical-Challenge Open Question: It provides the first provably secure copy-protection for point functions and decryption keys under the identical-challenge security notion in the plain model, a problem that has remained open for over a decade.
Definitional Clarity: It establishes a "gold standard" definition (SDE-CORR) that subsumes all prior definitions, clarifying the hierarchy of security notions and proving that previous definitions were insufficient to capture natural security intuitions (e.g., that CPA does not imply search).
Technical Advancement: The new Decisional Coset Monogamy Theorem is presented as a result of independent interest. It unifies the study of monogamy games, unclonable encryption, and copy-protection by providing a decisional guarantee for unlearnable states with identical challenges, simplifying future proofs by removing the need for complex extraction techniques.
Modular Framework: By introducing Correlated UPO, the paper provides a modular pathway to achieving copy-protection for a wide range of functionalities (beyond just point functions) under natural security definitions, including those requiring auxiliary information leakage.

The authors emphasize that their results rely on standard post-quantum assumptions (iO, OWF, LWE) and operate in the plain model, without relying on idealized models like the Quantum Random Oracle Model (QROM) for these specific results.