Decisional Monogamy-of-Entanglement for Coset States and Applications to Unclonable Cryptography with Correlated Challenges

arXiv:2608.18841 · quant-ph, cs.CR · Submitted 2026-08-19 · Read on arXiv

Listen

Transcript

Introduction to the show: ident: Quantum Radio. Generated commentary on the latest quantum physics and condensed matter papers.

Kai: Today's paper: "Decisional Monogamy-of-Entanglement for Coset States and Applications to Unclonable Cryptography with Correlated Challenges".

Mira: Detailed Research Summary: Decisional Monogamy of Entanglement for Coset States and Applications to Unclonable Cryptography with Correlated Challenges As a fastidious researcher,

Kai: First, who's behind it and why it matters.

Paper summary: Kai: Moving on from the foundations, the paper details how this new theorem is immediately leveraged to define new security primitives. Specifically, they introduce correlated challenge security, which they claim implies all previously defined notions of SDE security.

Mira: That's a big statement because it means that by using this specific type of monogamy theorem for unlearnable states, the resulting construction satisfies the requirements for earlier constructions like the SDE construction from Kitagawa and Yamakawa. This is a direct link between their new technical result and established cryptographic tools.

Lev: So, if this reduction to computational decisional coset monogamy holds as described in Theorem six then we get a very strong security guarantee for the single-decryptor encryption scheme they are proposing. We're wondering how much of that proof relies on the unlearnability assumption itself versus just the structure of the state splitting.

Kai: The paper shows that this reduction is what allows them to prove security in a way that circumvents needing complex techniques like rewinding or threshold measurements for certain tasks. This simplifies the security reductions considerably, which is a major practical advantage.

Mira: And they then move into constructing Copy Protection from Correlated UPO, which is a very flexible definition. It allows for arbitrary correlations among challenge points and puncturing bits, as well as auxiliary information given before and after the state splitting.

Lev: That flexibility sounds powerful but also complex to implement physically. We'll have to figure out how to encode those auxiliary pieces of information into the physical state preparation without introducing too many new sources of decoherence that undermine the security margin established by this theorem.

Kai: The paper states that for this correlated UPO construction, the security requirements are relatively modest: they only need conditionally uniform bits and average conditional min-entropy in each point separately. This flexibility is what lets them construct schemes for arbitrary polynomial-size keyed circuits with input lengths of at least lambda c.

Mira: That level of requirement—conditional uniformity and average conditional min-entropy—is what makes the UPO definition so useful because it doesn't demand perfect randomness everywhere, which is a huge deal when you're dealing with physical quantum systems. This flexibility allows for identical challenge points, which is what this work was aiming for.

Lev: If we look at the construction of the Correlated High min-entropy UPO Sampler, Definition twenty-six it requires that the challenge bits are perfectly random given the auxiliary information and that the min-entropy of those challenge points is at least kappa(lambda), where kappa is related to lambda c. That sets a very high bar for our error correction and measurement apparatus.

Kai: So, to summarize this segment, we're seeing how they take the foundational theorem about coset states and use it to define security for copy-protecting functionalities like UPO with correlated challenges, all while keeping the necessary randomness requirements manageable.

Mira: And that flexibility in defining security metrics is what allows them to map these abstract mathematical structures onto actual cryptographic primitives that can be used for practical copy protection schemes.

Lev: It’s a strong theoretical result, but we're always wondering about the overhead when moving from this theoretical proof to a physical implementation where we have finite resources and noise constraints.

Conclusion: Kai: Looking at the title, "Decisional Monogamy-of-Entanglement for Coset States and Applications to Unclonable Cryptography with Correlated Challenges," it really captures the essence of what this paper is doing: establishing a specific entanglement property that unlocks new security avenues.

Mira: I think the implication here is that we're moving beyond just proving security against independent challenges; we are establishing a framework where adversaries attempting to learn from identical challenge points face a fundamental quantum constraint rooted in state splitting geometry.

Lev: For me, the real impact lies in how this theorem provides a clearer mathematical structure for designing error-correcting codes that inherently resist certain types of information leakage during state manipulation. It gives us something concrete to work with when we try to design physical systems that need to maintain unlearnable properties.

Kai: So, in simple terms, the paper shows that by precisely controlling how a quantum state is split between two adversaries—especially when they use the same challenge point—we can enforce a specific level of security dictated by the geometry of those states.

Mira: Exactly. This means we have a more rigorous way to define and build copy-protection schemes that don't rely on assumptions about independent sampling but on these structural properties of entanglement itself, which is something I think is really important for future research in this area.

Lev: If this work holds up, it suggests that the underlying structure of the quantum state family can be leveraged to enforce strong security guarantees for point functions and bits without needing overly complex or resource-heavy measurement procedures during decryption or obfuscation.

Kai: So, we have a paper that provides a new mathematical lens—decisional monogamy of entanglement for coset states—to define security measures like correlated challenge security and UPO, which then has serious implications for the practical design of quantum copy protection schemes.

NTT Research · Carnegie Mellon University

quant-ph, cs.CR

Submitted: 2026-08-19

Updated: 2026-10-01

License: http://creativecommons.org/licenses/by/4.0/

Importance score: 83/100

The gist: As a fastidious researcher, I have meticulously analyzed the provided excerpts from the paper, "Decisional Monogamy-of-Entanglement for Coset States and Applications to Unclonable Cryptography with

Key concepts

Decisional Coset Monogamy Theorem: This is a new theorem proving that if an adversary splits a specific quantum state, the probability of both resulting parties getting the same answer about a hidden bit is very low (bounded by 1/2 + 2^-Omega(n)). This provides a strong mathematical foundation for security proofs.
Unclonable Puncture Obfuscation (UPO): UPO is a flexible method for making quantum data uncloneable. It allows for arbitrary correlations among challenge points and bits, requiring only conditionally uniform bits and average conditional min-entropy to ensure security against adversaries.
Correlated Challenge Security (SDE-CORR): This is a new security notion that implies all previous SDE security notions. It is achieved by showing that the construction methods for copy-protecting keys satisfy this condition, relying on reductions to the computational coset monogamy theorem.

Terminology

Entanglement — 37× in this paper · explained in 3 episodes
Single-Decryptor Encryption — 17× in this paper
Generalization — 9× in this paper · explained in 13 episodes
Information Leakage — 6× in this paper · explained in 2 episodes
Hilbert Space — 5× in this paper · explained in 2 episodes
Core — 4× in this paper · explained in 2 episodes
Trace — 4× in this paper · explained in 2 episodes
Verification — 4× in this paper · explained in 2 episodes
Robustness — 2× in this paper · explained in 5 episodes
Abstraction — 1× in this paper · explained in 1 episode
Learning With Errors — 1× in this paper
Provenance — 1× in this paper · explained in 3 episodes
Trace Distance — 1× in this paper · explained in 3 episodes
Unclonable Puncture Obfuscation — 1× in this paper

Summary

As a fastidious researcher, I have meticulously analyzed the provided excerpts from the paper, Decisional Monogamy-of-Entanglement for Coset States and Applications to Unclonable Cryptography with Correlated Challenges. This work represents a significant advancement in applying quantum information theory—specifically entanglement properties—to establish robust security primitives for copy-protection schemes.

The core contribution lies in the development of a new decisional monogamy theorem for coset states, which serves as the technical foundation for proving security guarantees across various quantum cryptographic constructions. The paper bridges fundamental concepts from quantum state splitting with practical cryptographic goals like copy-protection and obfuscation.

The central technical achievement is Theorem 6 (Informal; Decisional Coset Monogamy). This theorem establishes a novel, truly identical-challenge decisional monogamy of entanglement theorem for an unlearnable state family.

Theorem 6 Summary:

This theorem deals with the splitting of a specific quantum state, A s, t:= 1 over pA X a a in A (-1) a, t a + s, where A is a uniformly random n-dimensional subspace over F 2 2n squared, and s, t are uniform vectors in F 2 2n squared. The theorem considers an adversary who splits this state between two non-communicating adversaries. The challenger samples uniform non-zero vectors u in A and v in A, sending them to both parties. The probability that both users correctly output the bit e:= u, t v, s is bounded by 1 over 2 + 2- (n).

Significance: This theorem is groundbreaking because it is the first identical decisional monogamy of entanglement theorem that guarantees the same-bit answers for an unlearnable state family. Crucially, it simplifies security reductions by circumventing the need for complex techniques like rewinding or threshold measurements.

The paper leverages this foundational theorem to define and prove security for several advanced quantum primitives, primarily revolving around Unclonable Puncture Obfuscation (UPO).

The work introduces a new natural security notion called correlated challenge security (SDE-CORR).

Implications: SDE-CORR implies all previously defined SDE security notions, including identical-challenge security.
Construction Link: The SDE construction from Kitagawa and Yamakawa (TCC'25) is shown to satisfy correlated challenge security.
Technical Reliance: The proof of the SDE-CORR construction relies directly on a reduction to the computational decisional coset monogamy of entanglement.

A new definition, correlated challenge unclonable puncturable obfuscation (UPO), is introduced. This definition is highly flexible, allowing for arbitrary correlations among challenge points and puncturing bits, as well as auxiliary information provided before and after the state splitting.

Security Requirements: Security for this construction requires only conditionally uniform bits and average conditional min-entropy in each point separately. This flexibility allows the scheme to support identical challenge points.
Construction: Assuming polynomially secure post-quantum indistinguishability obfuscation (iO) and quantum-hard Learning With Errors (LWE), a correlated UPO for arbitrary polynomial-size keyed circuits with input length at least lambda c is successfully constructed.

The paper formalizes the security landscape around UPO using several defined concepts:

Correlated High min-entropy UPO Sampler (Definition 26): This defines a QPT sampler that outputs auxiliary information and challenge bits such that:

The challenge bits (b B, b C) are perfectly random (outputting 1/2 probability for 0 or 1) given the auxiliary information (aux, B, C).
The min-entropy of the challenge points (x X) conditioned on the auxiliary information is at least kappa(lambda), where kappa = lambda c for some constant c>0.

Improvements for AI systems

Based on the provided scientific paper, here are specific improvements for AI systems that can be made, categorized by the capabilities enabled by these cryptographic primitives:

)1. Enhanced Security for Quantum-Resistant Data Storage and Function Integrity:

The paper establishes provably secure copy protection for fundamental functionalities like point functions and compute-and-compare programs under natural challenge distributions.

The improved AI system can now securely store or process critical data (like decryption keys or proprietary algorithms) in a quantum environment, ensuring that no freeloader adversary can extract the functionality by splitting the quantum state. Furthermore, it can guarantee that complex computational tasks (like verifying a specific function's output) remain secure even against adversaries who have access to auxiliary information or correlated challenge distributions.

)2. Secure Implementation of Single-Decryptor Encryption (SDE) for Distributed Systems:

The development of Correlated-Challenge SDE security allows for the encoding of decryption keys in quantum states that resist splitting, even when multiple recipients receive correlated or identical challenges.

The AI system can be deployed in decentralized or multi-user architectures where a single decryption key is distributed to several entities. It can guarantee that no two recipients can simultaneously derive useful information from the same ciphertext, even if they share correlated challenge points (e.g., in a broadcast scenario).

)3. Robust Copy Protection for General Functionalities (UPO):

The construction of Correlated UPO provides security for arbitrary puncturable functionalities, including complex compute-and-compare programs, under natural security definitions.

This system can securely protect a wide range of software or models—such as neural networks or specialized decision trees—by encoding their behavior into an unclonable quantum state. It can handle complex circuit modifications (puncturing) while maintaining security against adversaries who attempt to copy the functionality, even when challenge points are correlated.

)4. Advanced Function Verification and Integrity Checks:

The results extend copy protection to point functions and k-point functions, which are used for digital lockboxes and password verification.

The AI can be used in secure hardware or software modules that verify specific mathematical properties or function outputs (like checking if a complex calculation matches a known result) without revealing the underlying function structure. This is crucial for building tamper-proof verification layers.

)5. Exploiting Correlation for Evasive Attack Detection:

The framework explicitly handles correlated challenge distributions, which are often relevant in real-world scenarios where adversaries might share information or use correlated sampling techniques to probe a system.

The AI can be trained to detect sophisticated side-channel attacks or probing attempts that rely on correlated challenge distributions, effectively identifying when an adversary is attempting to exploit these correlations to gain an advantage in extracting information from the system.

)6. Foundation for Post-Quantum Cryptographic Primitives:

The work establishes new security definitions (like SDE-CORR) that imply previous, weaker ones, creating a clearer hierarchy and providing a gold standard definition for quantum primitives.

This provides researchers with a rigorous mathematical framework to design future quantum cryptographic protocols. It allows for the selection of the strongest possible security guarantees (e.g., SDE-CORR) based on specific application requirements (e.g., needing identical-challenge security), leading to more robust and well-defined quantum cryptographic tools for AI infrastructure.

Abstract

A main application of quantum information in cryptography is copy-protection, where we encode a functionality (such as a decryption key or software) into a reusable quantum state so that it cannot be split into two adversaries (called freeloaders) that both remain useful. Previous works have only shown security for independently sampled challenges for the two adversaries. A competing natural security notion is identical-challenge security where the adversaries receive the same challenge. This notion has many real-life applications and connections to other fundamental primitives such as unclonable bits (i.e. unclonable encryption) and unclonable lockboxes (i.e. copy-protection of point functions). Despite its importance and numerous attempts, achieving identical-challenge security in the plain model has remained open. We first make progress on the definitional foundations of copy-protection by introducing natural copy-protection security definitions that imply the previous ones (including identical-challenge security) and better capture the security intuitions and real-life use cases; and we also characterize the relationship between the previous definitions. Then, we show how to achieve in the plain model our new stronger definitions for copy-protection of general classes of functionalities. In particular, we resolve the long-standing open questions of copy-protection of point functions, copy-protection of compute-and-compare programs, and identical-challenge secure copy-protection of decryption keys and all puncturable functionalities. Our technical core is a new decisional monogamy-of-entanglement result for coset states, which both allows us to achieve our new results, and also significantly simplifies and unifies unclonable cryptography proofs. We believe this will have further applications and may be of independent interest.