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

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

arXiv:2608.18841v1 [quant-ph] 19 Aug 2026

Amit Behera∗

Alper Çakan†

Vipul Goyal‡

Abstract Copy-protection is one of the main applications of quantum information in cryptography. In copy-protection, we encode a functionality in a reusable quantum state so that it cannot be split into two states (called freeloader adversaries) that remain simultaneously useful. Despite a long line of research, previous works have only been able to show security with respect to independently sampled challenges in the plain-model. However, arguably a more natural security notion considers the two freeloader adversaries receiving the same challenge. This so-called identical-challenge security notion is also connected to other fundamental quantum cryptographic primitives such as unclonable bits (i.e. unclonable encryption) and copy-protection of point functions. In this work, first we make progress on the definitional foundations of these primitives, and then prove security in the plain model for our new stronger definitions, in particular also resolving the question of copy-protection with identical challenges and copy-protection of point functions. In more detail, we obtain the following results. • Copy-protecting decryption keys (Single-decryptor encryption). We define a new natural security notion for single-decryptor encryption (SDE) called correlated challenge security, and show that implies all previous security definitions for SDE, including identicalchallenge security. Then, we prove that, assuming indistinguishability obfuscation (iO) and one-way functions, the SDE construction of Kitagawa and Yamakawa (TCC’25) satisfies correlated challenge security. We also provide an almost complete characterization of the relationship among previous SDE security notions. • Copy-Protecting General Functionalities with Correlated Challenges. We define correlated challenge unclonable puncturable obfuscation (UPO), allowing arbitrary correlations among challenge points and puncturing bits, plus auxiliary information before and after splitting. Security requires only conditionally uniform bits and λc average conditional min-entropy in each point separately, for any constant c > 0; thus, in particular the challenge points may be identical. Assuming polynomially secure post-quantum iO and quantum-hard LWE, we construct correlated UPO for arbitrary polynomial-size keyed circuits with input length at least λc , answering the open question of Ananth, Behera, Huang, Kitagawa, Yamakawa (EUROCRYPT’26) and Çakan-Goyal (EUROCRYPT’26). • Applications. Our results yield the first plain-model copy protection for point functions, k-point functions, and compute-and-compare programs under natural security definitions, and identical-challenge copy protection for general puncturable functionalities. The technical core of our results is a new decisional monogamy theorem for coset states, which both simplifies the proofs and generalizes the results of existing copy-protection constructions, which may be of independent interest.

Keywords: Quantum cryptography, Copy-protection, Unclonable encryption. ∗

NTT Research amitbehera1767@gmail.com Carnegie Mellon University. alpercakan98@gmail.com. ‡ NTT Research & Carnegie Mellon University. vipul@vipulgoyal.org †

1

Contents 1 Introduction 1.1 Our Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2 Organization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4 6 9

2 Technical Overview 2.1 Our Solution: Identical-Challenge Decisional Coset Monogamy of Entanglement . . . 2.1.1 Information-Theoretic Security Proof . . . . . . . . . . . . . . . . . . . . . . . 2.1.2 Computational Decisional Hidden-Coset Monogamy . . . . . . . . . . . . . . 2.2 Correlated-Challenge Single-Decryptor Encryption . . . . . . . . . . . . . . . . . . . 2.3 Copy Protection from Correlated UPO . . . . . . . . . . . . . . . . . . . . . . . . . .

10 11 12 14 14 16

3 Preliminaries 3.1 Notation and Conventions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2 Pseudorandom Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.3 Digital Signature Schemes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.4 Indistinguishability Obfuscation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.5 Subspace-Hiding Obfuscation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.6 Universal Hash Functions and Average Conditional Min-Entropy . . . . . . . . . . . 3.7 Injective/Lossy Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.8 Unclonable Encryption . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.9 Quantum Information . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

18 18 19 20 21 22 22 23 23 24

I

Definitional Work

27

4 Single-Decryptor Encryption Security Definitions 4.1 Prior Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.2 Correlated-Challenge Decision Security . . . . . . . . . . . . . . . . . . . . . . . . . . 4.3 Hierarchy of Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.3.1 Summary of the Main Relations . . . . . . . . . . . . . . . . . . . . . . . . .

27 27 30 32 45

5 Unclonable Puncturable Obfuscation Security Definitions and Copy-Protection of General Functionalities 5.1 Unclonable Puncturable Obfuscation definitions . . . . . . . . . . . . . . . . . . . . . 5.1.1 Prior Definitions:Generalized UPO Security . . . . . . . . . . . . . . . . . . . 5.1.2 Correlated-Challenge Security . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.2 Copy-Protection Security Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.2.1 Oracular security notions . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

46 46 46 47 50 54

II

Quantum Information Tools

56

6 A New Decisional Coset Monogamy-of-Entanglement Game 56 6.1 Unclonable indistinguishable security of the general class of encryption schemes (Proof of Lemma 9) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61 6.1.1 Proof of Lemma 11 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64

2

7 Computational Monogamy-of-Entanglement Games

III

Copy-Protection Constructions

67

73

8 Single-Decryptor Encryption Construction 8.1 Construction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8.2 Correctness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8.3 Proof of security . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

73 73 74 74

9 Unclonable Puncturable Obfuscation Construction 9.1 Construction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9.2 Proof of Security . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9.2.1 Formal proof of the moreover part of Theorem 23 . . . . . . . . . . . . . . . .

77 77 78 84

10 Applications of Correlated UPO to Copy-Protection

87

3

1

Introduction

Starting with the seminal work of Wiesner [Wie83], a long line of research has shown that quantum information can help us achieve remarkable cryptographic guarantees that are simply impossible with classical information. A central example is the notions of quantum money ([Wie83, AC12]) and quantum copy protection [Aar09]. In the latter, a functionality is encoded into a quantum state that can be evaluated, but no efficient adversary can split the state into two programs/adversaries (also called freeloaders) that both remain useful. The functionality can be a cryptographic object (such as a decryption key for an encryption scheme) or can be a piece of software (such as a video game or a spreadsheet program). Note that a classical program or key can always be copied bit for bit, so copy protection is indeed an inherently quantum security notion. There has been significant recent progress on constructing copy protection for general classes of functionalities and laying down the definitional foundations of copy protection [CMP20, ALL+ 21, CLLZ21, AKL+ 22, AKL23, AB24, ABH+ 26, ÇG26, KY25]. Nevertheless, as we discuss in more detail below, the state of affairs remains quite unsatisfactory on both the construction and definitional fronts. Even for some of the simplest functionalities, such as point functions, we still do not have a provably secure copy protection scheme (under a natural security definition) in the plain model. On the definitional side, we do not have good security definitions for even copy-protecting decryption keys, which is one of the most fundamental applications of copy protection. Further, some of the existing natural security definitions for decryption keys still have not been achieved. In this work, we consider these issues and make significant progress on both construction and definitional fronts. We now discuss the issues in more detail. Copy-protecting decryption keys. The earliest and perhaps the most important primitive in cryptography is encryption, and similarly, one of the earliest and most fundamental questions in quantum copy protection has been the question of copy-protecting decryption keys. Thus, this question has been one of the most studied questions in copy protection [GZ20, CLLZ21, AK21, AKL+ 22, KN23, AKL23, KY25] and even has a dedicated name: single-decryptor encryption (SDE) [CLLZ21]. In SDE, we encode a decryption key in a quantum state, and we require that no adversary can split it into two useful keys. Note that the encryption key and the ciphertexts are still classical. In the case of classical encryption, the notion of a useful adversary has been settled decades ago: The seminal work of Goldwasser and Micali [GM82, GM84] introduced the notion of indistinguishability security (now also called CPA security), where the adversary receives an encryption of either m0 or m1 with probability 1/2, and security is considered violated when it can guess which case it is with probability non-negligibly better than 1/2. This security notion is the gold standard for encryption, and also implies various other properties that one would expect from an encryption, such as unpredictability security (also called search security), where an adversary tries to guess the message from its ciphertext (the message comes from an unpredictable distribution). However, it turns out that the question of defining security for single-decryptor encryption (SDE) is much trickier: There are 7 different security notions currently in the literature! To make things worse, even the relationships among these security notions are unclear, and there is no gold standard definition: No single definition is known to imply all others. For example, unlike classical encryption, it is not even known if the existing indistinguishability security implies unpredictability security (in fact, in this work we show that in general, it does not). Further, while some of the seven definitions have been achieved; for some natural ones we still do not even have provably secure classical-ciphertext constructions under standard assumptions, such as identical-challenge security where the two freeloaders receive the same ciphertext. This directly models a single ciphertext 4

distributed to many users—such as an encrypted television broadcast or a fixed encrypted file sent to all subscribers—on which two copies of the decryption key should not both remain useful. Introduced by Georgiou and Zhandry [GZ20], achieving identical-challenge security notion has proved difficult and remained open despite many attempts [CLLZ21, AKL23, CGLZR23, KN23, CHV23, AKY25a, KY25, AB24, ABH+ 26]. Thus, in this work, we ask the following questions. Can we define a gold-standard security notion for single-decryptor encryption that captures the natural security intuition and uses cases, and implies existing definitions (including identical-challenge security)? Can we achieve a construction with provable security for all known definitions including identical-challenge security? In fact, can we achieve a construction that provably satisfies the gold standard definition, and hence as a result, all known definitions? Copy-protecting general functionalities. Moving beyond encryption, various works have considered copy-protecting general classes of functionalities [CMP20, ALL+ 21, CLLZ21, AKL+ 22, AKL23, AB24, ABH+ 26, ÇG26]. The state of the art consists of the recent concurrent works of Çakan and Goyal [ÇG26] and Ananth, Behera, Huang, Kitagawa, and Yamakawa [ÇG26, ABH+ 26], which show how to copy-protect any puncturable functionality in the plain model. Unfortunately, these results also suffer from the same issues as the case of single-decryptor encryption. First, there is still not a single security definition for copy-protecting general functionalities. Further, these works only achieve what is called independent-challenge security. However, a competing natural definition called identical-challenge security has not been achieved and was left as an open question by both works [ÇG26, ABH+ 26]. This latter notion, identical-challenge security, has many practical security motivations, and aside from that, it is also tightly related to other fundamental questions, such as unclonable bits or unclonable encryption [BL20], and copyprotecting point functions [Aar09]. In contrast, independent-challenge security does not imply any of these notions. More broadly, prior works have struggled to tackle the question of correlation in challenge distributions and to get feasibility for correlated challenge distributions, which raises the following question. Can we achieve copy protection with identical-challenge security, and more generally correlated challenge security for general classes of functionalities? Point functions are perhaps the simplest nontrivial programs and have natural applications such as digital lockboxes and password-verification software. Their conceptual simplicity and concrete applications led Aaronson to single out their copy protection when introducing quantum copy protection in 2009 [Aar09]; he proposed two candidate schemes in the structured ideal oracle model but left proving security under standard assumptions open. Although Coladangelo, Majenz, and Poremba later achieved security in the quantum random-oracle model [CMP20], the input challenge distribution they considered for copy protection was not the natural challenge distribution.1 Hence, getting copy protection for point functions with the natural challenge distribution in the plain model still remains open. Thus, in this work, we ask the following questions. 1

Here, by natural challenge distribution, we mean that for a point function Py with probability 1/2, give the point y to the freeloaders B and C, and with the rest of the probability, give a random point x to both the freeloaders.

5

Can we achieve copy protection for fundamental functionalities such as point functions and compute-and-compare functions? In [AB24], the authors provided a modular pathway to achieving copy protection for general functionalities, via an unclonable variant of obfuscation called Unclonable Puncturable Obfuscation (UPO). However, the UPO security notion itself is sensitive to challenge distributions, and [AB24] considered two variants of UPO security, one with identical challenge distribution and the other with independent challenge distributions, but each with its own set of applications to copy protection and unclonable cryptography in general. In particular, the identical-challenge variant (along with iO) implies identical-challenge secure copy protection for various functionalities, including identical-challenge secure SDE and copy protection of point functions2 , as well as unclonable indistinguishable encryption. Unfortunately, [AB24] could only construct two variants of UPO based on two conjectures. In a later work, the requirement of conjectures was removed for the case of independent challenge distributions [ABH+ 26], but constructing the identical-challenge variant of UPO in the plain model still remains open, which brings us to the following natural question. Can we achieve UPO with identical-challenge security and, more generally, correlatedchallenge security? Moreover, can we achieve stronger generalizations of UPO that can help us obtain copy protection for more functionalities beyond what is currently known in the plain model?

1.1

Our Results

We note that correlation was the missing axis in prior constructions, as they primarily address independent challenges, whereas natural applications often give the two recipients correlated or identical challenges. Our broad conceptual contribution is that we provide a framework to handle correlation in challenge distributions that enables us to answer the questions asked above affirmatively. Gold-standard definition for SDE. We introduce a new simple and natural security definition for SDE called correlated-challenge security (SDE-CORR) that better captures the security intuition and use cases for SDE, and also show that it implies all existing SDE security definitions. Theorem 1 (Informal). SDE-CORR implies all seven prior security notions for SDE, including identical-challenge security. As discussed below, the relationships of the prior definitions among themselves is also unclear. In this work, we establish an almost complete categorization of the prior definitions, which in particular also shows their inadequacy: For example, the usual indistinguishability/CPA SDE security definition3 does not even imply search security! Further, we show that independent-challenge CPA security does not imply identical-challenge CPA security, refuting a folklore conjecture and showing the inadequacy of previous techniques for proving identical-challenge CPA security. We refer the reader to Figure 1 for the complete picture. We also achieve our gold-standard notion in the plain model, with same cryptographic assumptions as previous works. Theorem 2 (Informal). Assuming indistinguishability obfuscation and one-way functions, there exists an SDE scheme satisfying SDE-CORR. 2

In fact, it implies a generalization of point functions called k-point functions. Here in indistinguishability/CPA SDE notion, we do not include non-operational CPA notions like Strong CPA anti-piracy [CLLZ21]. 3

6

In particular, this is the first classical-ciphertext SDE construction satisfying identical-challenge security from standard cryptographic assumptions, resolving the question introduced by Georgiou and Zhandry and left open throughout subsequent work [GZ20, CLLZ21, AKL23, CGLZR23, KN23, CHV23, AB24, AKY25a, KY25]. Copy-Protecting general functionalities. For copy-protecting general functionalities, we follow the modular approach of Ananth and Behera [AB24], and achieve our feasibility results via unclonable puncturable obfuscation (UPO). We first introduce a strengthened definition for UPO called correlated-challenge unclonable puncturable obfuscation (UPO) or simply correlated UPO, that implies both variants of UPO security definitions introduced by [AB24], i.e., identical-challenge security and independent-challenge security. Then, we show how to achieve it in the plain model. Theorem 3 (Informal). Assuming indistinguishability obfuscation and hardness of LWE, there exists an unclonable puncturable obfuscation (UPO) scheme that satisfies correlated security for any sufficiently unpredictable challenge distribution. This gives, in particular, the first provably secure identical-challenge generalized UPO in the plain model and, through the UPO framework, the first identical-challenge-secure copy protection for puncturable functionalities, resolving the question left open by Çakan–Goyal and Ananth et al. [ÇG26, ABH+ 26], as well as new feasibility results for copy protection for various evasive function classes like point functions and compute-and-compare functions. Our definition of correlated UPO security not only allows correlation between challenge distributions but also allows for auxiliary information leakage to the adversaries, which can be critical for various applications. Indeed, the reduction for the application to copy protection of computeand-compare functions crucially relies on the auxiliary information leakage. Applications. As discussed before, identical-challenge UPO security is related to many fundamental questions. Thus, our construction yields the first plain-model copy protection for point functions with the natural challenge distribution, resolving a question posed by Aaronson when he introduced quantum copy protection in 2009 [Aar09]. Our result holds for arbitrary high-min entropic distribution on point functions, and also generalizes to k-point functions, a generalization of point functions, considered in [AB24]. Beyond point functions, we obtain the first plain-model copy protection for compute-andcompare programs with a natural challenge distribution just as in point-functions4 , a more expressive class whose quantum copy protection was introduced and previously achieved only in the quantum random-oracle model by Coladangelo, Majenz, and Poremba [CMP20]. We note that for the application to copy protection of compute-and-compare functions, we rely on the strength of the new correlated UPO security, both in terms of the correlation in the challenge distribution and the auxiliary information leakage that the correlated UPO security definition allows for. Theorem 4 (Informal). Assuming post-quantum indistinguishability obfuscation and quantumhard LWE; point functions, k-point functions, and compute-and-compare programs admit plainmodel copy protection with respect to natural identical challenge distributions, and arbitrary high min-entropic distribution on the respective function families. Moreover, for identical challenge 4 This natural challenge distribution is an identical challenge distribution, as for the case of point functions. We also note that though related, the proof of feasibility of copy protection for compute-and-compare functions does not follow directly from the feasibility of point functions.

7

distributions with uniform marginals for all three copy protection applications, post-quantum oneway functions suffice in place of LWE. Beyond copy-protection for point functions, our feasibility result for correlated UPO extends the existing results of independent-challenge copy-protection for puncturable functionalities to correlated-challenge copy-protection. Moreover, in the identical-challenge setting, our results extend to stronger definitions of copy-protection including oracular security, introduced by [ABH+ 26]. Theorem 5 (Informal). Assuming post-quantum indistinguishability obfuscation and quantum-hard LWE, puncturable functionalities admit unpredictability and pseudorandomness-style copy protection with respect to arbitrary correlated high min-entropic challenge distributions. Moreover, for the case of identical high min-entropic challenge distributions, the oracular variant of the respective copy protection notion (i.e., unpredictability or pseudorandomness-style) that gives adversaries oracle access to the protected function holds. A new decisional monogamy game for coset state. We achieve our results through a new, simple-to-state decisional monogamy-of-entanglement guarantee we prove for coset states. Theorem 6 (Informal; Decisional Coset Monogamy). Let A ≤ F2n 2 be a uniformly random n2n dimensional subspace, let s, t ∈ F2 be uniform, and give an adversary one copy of 1 X |As,t ⟩ := p (−1)⟨a,t⟩ |a + s⟩ . |A| a∈A Consider the game where an adversary splits this state between two noncommunicating adversaries, and a challenger samples uniform non-zero u ∈ A and non-zero v ∈ A⊥ sends it to both adversaries. The probability that both users correctly output the bit e := ⟨u, t⟩ ⊕ ⟨v, s⟩ is at most 1/2 + 2−Ω(n) . Moreover, assuming post-quantum indistinguishability obfuscation and subspace-hiding obfuscation, the corresponding computational version of the MOE guarantee holds even when the adversary receives the public obfuscated membership programs M0 = iO(PA+s )

and

M1 = iO(PA⊥ +t ),

together with correlated simulatable auxiliary information, similar to the computation variant considered in [ABH+ 26]. We emphasize that, unlike the search-style coset monogamy theorem of Culf and Vidick [CV22], our game is decisional, i.e., both recipients B and C output a single-bit answer, rather than a full vector from an affine subspace. Secondly, our monogamy theorem has truly identical challenges for both recipients, i.e., they receive the same challenge (as opposed to mildly correlated challenges) and output the same single-bit answer. Furthermore, to the best of our knowledge, our monogamy of entanglement theorem is the first identical decisional monogamy of entanglement theorem with same-bit answers for an unlearnable state family, which is crucial for our purposes. Earlier decision-style monogamy of entanglement experiments with same bit answers (i.e., requires both recipients to output the same bit) including the celebrated work of [TFKW13] and the recent unclonable encryption result of [AS26], are based on learnable state families such as BB84 or Pauli states. Thus, they cannot be used for copy protection, even in simpler forms such as point function copy protection. Our result provides the missing combination of unlearnability and decision-form monogamy, unifying the study of monogamy games, unclonable encryption and copy protection. Our decisional monogamy of 8

entanglement theorem with same bit answers also significantly simplifies the copy-protection reductions: it avoids the rewinding and threshold-measurement techniques used for simultaneous extraction in previous works [Wat06, Zha20, ALL+ 21] and removes the need to canonicalize recovered subspace vectors, thereby giving a simpler alternative route to achieving copy protection, that does not require any extraction techniques. Hence, we believe our new monogamy of entanglement result will have independent applications.

1.2

Organization

Section 3.1 recalls notation and preliminaries. Sections 4.1 to 4.3 define the SDE notions and establish their hierarchy, after which Sections 5.1.1 and 5.1.2 define correlated-challenge UPO. The next part proves the information-theoretic and computational decisional coset-monogamy theorems. Finally, Section 8 constructs a correlated-challenge SDE, and Section 9 constructs a correlated secure UPO, and Section 10 derives the copy protection applications.

Acknowledgments Alper Çakan was supported by the following grants of Vipul Goyal: NSF award 1916939, DARPA SIEVE program, a gift from Ripple, a DoE NETL award, a JP Morgan Faculty Fellowship, a PNC center for financial services innovation award, and a Cylab seed funding award.

AI Acknowledgment Our information-theoretic MoE result and our SDE-CORR definition was proven with help of interaction with ChatGPT-5.6 Sol. Rest of the results were obtained directly by authors. ChatGPT-5.6 Sol was also used for drafting the initial versions of some text. The authors take full responsibility for the whole paper.

9

2

Technical Overview

In this section, we outline the key ideas and an overview of our proof techniques. We note that the constructions are largely the same as considered in previous works, namely, the construction of [KY25] for the single-decryptor encryption (SDE) construction, and the construction of [ABH+ 26, ÇG26] for the unclonable puncturable obfuscation (UPO) construction. We very briefly recall the definitions of SDE and UPO in the literature. An SDE scheme [CLLZ21, KY25] is a public key encryption scheme with classical ciphers and public keys but equipped with a quantum decryption key that can decrypt any cipher generated using the public key, can be correctly decrypted using the quantum decryption key. In the CPA security experiment, there is a triplet of adversaries (A, B, C) such that A receives a quantum decryption key along with the public key from the challenger, and outputs two pairs of challenge messages, one for B and one for C, and then sends two (potentially entangled) quantum registers, one to B and the other to C who cannot communicate among themselves. Then, the challenger sends each of B and C the encryption of one of the two challenge messages chosen according to a randomly sampled challenge bit for each recipient, and then B and C need to guess their respective challenge bits. In the identical challenge setting, A only chooses a single pair of challenge messages, and the challenger uses the same uniformly random bit for both B and C, who receive the exact same cipher text, and needs to predict their common bit, whereas in the independent challenge setting, the challenge bits for B and C are sampled uniformly at random independently. In this work, we also consider a generalization of the independent challenge setting, where we allow the challenge bits of B and C to be arbitrarily correlated as long as the marginal distribution for each of the two challenge bits is uniform. An unclonable puncturable obfuscation (UPO) [AB24] is a tuple of QPT algorithms Obf, Eval where Obf compiles a classical circuit C into a quantum program ρC , and Eval takes as input a quantum program ρC and an input x, and outputs C(x). In the identical challenge UPO security experiment, again there are three adversaries (A, B, C). A selects a circuit C to the challenger, who then samples challenge bit b, and a single challenge input point x sampled from a high min-entropy distribution, and if the bit b = 0, the challenger runs Obf on C else if b = 1, it first punctures the circuit at the point x using a puncturing algorithm equipped with the circuit class5 , and sends the program to A who then splits the state in to two quantum registers and sends one to B and one to C, after which the puncture point x is revealed to both B and C and then both B and C need to output the bit b. In the independent challenge settings, the only difference is that there are two challenge points sampled independently for B and C, whereas in general correlated challenge setting, we allow the two challenge points to be arbitrarily correlated. Existing approaches and their limitations. For a subspace A ≤ Fq2 of dimension q/2, and vector shifts s, t ∈ Fq2 , coset states refer to states of the form 1 X |As,t ⟩ := p (−1)⟨a,t⟩ |a + s⟩ , |A| a∈A 1 and we refer to H ⊗q |As,t ⟩ = A⊥ t,s := √ ⊥

|A |

⟨a,s⟩ |a + t⟩ , as the corresponding dual a∈A⊥ (−1)

P

coset for the dual subspace A⊥ . Coset states are a natural candidate of state family to build SDE, and copy protection in general as well as UPO, because they have two desirable yet contrasting By puncturing a circuit at a point x, we just mean outputting a circuit that outputs the true value C(x′ ) on all points x′ ̸= x and outputs ⊥ on input x. Clearly, any circuit class can be equipped with at least the canonical puncturing algorithm that given a circuit C and point x produces such a circuit by hardcoding C and x into a new circuit Cx . 5

10

properties, namely, they can be verified publicly, but they still satisfy a strong form of unclonability, colloquially referred to as monogamy of entanglement (MOE) [CV22, CLLZ21]. In particular, the monogamy of entanglement guarantees that, given a random coset state, A cannot split the state into two registers and send them to B and C then, given the subspace A, B and C cannot recover the vector shifts s and t, respectively. How coset monogamy of entanglement was used in previous works. The starting point in previous works is an information-theoretic search guarantee: after A splits a coset state, B and C cannot both output suitable elements of the primal coset A + s and the dual coset A⊥ + t. Here “search” means that they must output complete coset elements, rather than one-bit answers. Coladangelo, Liu, Liu, and Zhandry [CLLZ21] proved a computational version in which the cosets are represented by obfuscated membership programs, namely, programs that check whether an input belongs to the primal or dual coset without revealing the cosets themselves. Their proof uses subspace-hiding obfuscation, which hides certain changes to the subspaces represented by these programs, together with information-theoretic properties of coset states. The SDE and UPO security games ask B and C to predict bits. Previous proofs therefore need a search-to-decision reduction connecting these one-bit predictions to the search guarantee above. After a sequence of hybrids using iO and other cryptographic properties, these proofs canonicalize the accepting inputs: among the many coset elements accepted by an iO-obfuscated membership program, they specify one value to be extracted as the search output. The proof of [CLLZ21] performs this extraction using threshold implementations and compute-and-compare obfuscation. A threshold implementation is a quantum measurement that tests whether an algorithm’s success probability is above a chosen threshold, while a compute-and-compare program accepts when a hidden computation equals a specified value. The proofs of [ÇG26, ABH+ 26] instead use the simultaneous Goldreich–Levin theorem of Ananth, Kaleoglu, and Yuen [AKY25a], which turns sufficiently good inner-product predictors on both sides into the corresponding hidden values. Why the previous techniques do not handle identical challenges. Extraction is particularly difficult when the two registers may be entangled. Extracting a coset element from B’s register may disturb C’s register and destroy the guarantee needed on his side. Previous works handle this issue in the independent-challenge setting by critically using the independence of the two challenges via threshold implementations of local tests. However, these techniques do not work when B and C receive identical challenges. One approach used in previous works to avoid search-to-decision reduction and hence extraction was to use MOE guarantees where B and C only need to output a single-bit answer. However, the only MOE experiment with such a property, which was proved by Kitagawa and Yamakawa [KY25], is not an identical-challenge MOE guarantee, as the basis for it is the simultaneous Goldreich-Levin theorem [AKY25b], and hence gives the B and C independently sampled random strings as part of their challenges. Thus, the existing coset monogamy of entanglement guarantees are either searchbased [CLLZ21, CV22] or are not with respect to identical challenges, whereas to circumvent the extraction barrier, we need a decisional guarantee in which B and C receive the same challenge, and both must output the same single bit.

2.1

Our Solution: Identical-Challenge Decisional Coset Monogamy of Entanglement

We prove the following truly identical-challenge decisional coset monogamy of entanglement theorem. 11

Identical-Challenge Decisional Coset Monogamy of Entanglement 1. The challenger samples a uniformly random q/2-dimensional subspace A ≤ Fq2 , uniform shifts s, t ∈ Fq2 , and gives |As,t ⟩ to A. 2. A splits the state into two registers and sends one to B and the other to C. $

$

3. The challenger samples u ← − A \ {0} and v ← − A⊥ \ {0}, and gives the same pair (u, v) to both B and C. 4. B and C output bits eB and eC , respectively. They win if eB = eC = e := ⟨u, t⟩ ⊕ ⟨v, s⟩. We will show that for every adversary (A, B, C), s 1 1 2q 1 Pr[eB = eC = e] ≤ + = + 2−Ω(q) . q q−1 2 2 (2 − 1)(2 − 1) 2

(1)

Remark 1. A nice property of our decisional coset MOE guarantee is that the final answer given by e := ⟨u, t⟩ ⊕ ⟨v, s⟩ remains unchanged even if we replace s and t with arbitrary coset elements in A + s and A⊥ + t. This is especially useful while proving the security of SDE and UPO, since now we do not need the values of s and t, or their canonical representatives, to calculate the required parity for the decisional coset MOE game. Hence, the reduction from SDE or UPO to the decisional coset MOE does not do any form of extraction of canonical representatives for the cosets. (For the formal game and theorem, see Definition 38 and Theorem 19.) 2.1.1

Information-Theoretic Security Proof

We first express the game above as a one-bit unclonable-encryption scheme based on coset states. For a ∈ Fq2 , define the Pauli operators X a and Z a by X a |x⟩ := |x ⊕ a⟩ and Z a |x⟩ := (−1)⟨a,x⟩ |x⟩. Coset-UE 1. GenKey: Sample a uniformly random nonzero orthogonal pair k = (u, v), meaning that u, v ∈ Fq2 \ {0} and ⟨u, v⟩ = 0. 2. Enc(k, e): Sample a uniformly random q/2-dimensional subspace A satisfying u ∈ A and v ∈ A⊥ . Sample s, t ∈ Fq2 uniformly subject to ⟨u, t⟩ ⊕ ⟨v, s⟩ = e, and output |As,t ⟩. 3. Dec(k, ρ): Measure X u Z v on ρ and output the bit e corresponding to the measured eigenvalue (−1)e . 4. Security: Give an encryption of a uniform bit e to A. After A sends one register to each recipient, reveal the same key (u, v) to both. They win only if both output e. Every nonzero orthogonal pair (u, v) belongs to the same number of subspaces A satisfying u ∈ A and v ∈ A⊥ , and for fixed A, u, v, the bit ⟨u, t⟩ ⊕ ⟨v, s⟩ is uniform over s, t. Consequently, sampling the coset state first and (u, v) afterwards, as in the monogamy game, gives the same joint distribution as sampling (u, v) first and then encrypting, as in Coset-UE. (For the formal equivalence, see Lemma 8.)

12

Conditional state of the ciphertext given the message and the key. Let |A⟩ := |A0,0 ⟩. Directly from the definition of a coset state and the Pauli commutation rule, we have X x Z z |A⟩ = |Ax,z ⟩

and

Z v X s = (−1)⟨v,s⟩ X s Z v .

(2)

Since |As,t ⟩ = X s Z t |A⟩, these identities give X u Z v |As,t ⟩ = (−1)⟨v,s⟩ |As+u,t+v ⟩ .

(3)

We now use u ∈ A and v ∈ A⊥ . Expanding the state on the right and changing the summation variable from a to a + u gives 1 X (−1)⟨a,t+v⟩ |a + s + u⟩ = (−1)⟨u,t⟩ |As,t ⟩ . |As+u,t+v ⟩ = p |A| a∈A

(4)

The condition v ∈ A⊥ is used here to remove ⟨a, v⟩, while u ∈ A ensures that a 7→ a + u is a change of variable within A. Combining the last two equations yields X u Z v |As,t ⟩ = (−1)⟨u,t⟩⊕⟨v,s⟩ |As,t ⟩ .

(5)

Thus a Coset-UE encryption of e is an eigenvector of X u Z v with eigenvalue (−1)e . Next, fix the key k = (u, v) and encrypted bit e. The equation above shows that every possible ciphertext lies in the (−1)e -eigenspace of X u Z v . We next explain why the ciphertext is in fact uniformly distributed over this entire eigenspace. Fix any subspace A satisfying u ∈ A and v ∈ A⊥ . Two shifts s that differ by an element of A describe the same shifted subspace A + s, while all other choices give disjoint sets of computationalbasis vectors. For a fixed shifted subspace, choices of t that differ by an element of A⊥ give the same relative signs, while all other choices give orthogonal sign patterns over A. The resulting 2q coset states therefore form an orthonormal basis of the full 2q -dimensional space. Since X u Z v is a non-identity Pauli operator, each of its two eigenspaces has dimension 2q−1 . Exactly half of this coset basis has eigenvalue (−1)e , so the allowed ciphertexts form an orthonormal basis of that eigenspace. Moreover, the uniform choices of s, t make the mixture uniform on this basis. Writing N := 2q and letting Πk,e be the projector onto the (−1)e -eigenspace, we obtain Πk,e =

I + (−1)e X u Z v 2

and

ρk,e =

2 1 Πk,e = I + (−1)e X u Z v . N N

(6)

Crucially, the final expression does not depend on A. Thus, averaging over the randomly chosen subspaces satisfying u ∈ A and v ∈ A⊥ leaves the same state. This is our main technical observation: conditioned on the key and message bit, a Coset-UE ciphertext is simply the maximally mixed state on one eigenspace of X u Z v . (For the complete calculation, see Claim 1.) Using the argument of Ananth and Sahai [AS26]. The form of the conditional ciphertext in (6) is exactly the structure used in their proof of unclonable encryption. We prove a generalization for any family of Hermitian operators {Θk }k on an N -dimensional space such that each Θk has eigenvalues +1 and −1 with equally large eigenspaces, and Tr(Θk Θk′ ) = 0 for distinct keys. If a key is sampled from a distribution P and the encryption of e is N −1 (I + (−1)e Θk ), then the probability that both recipients recover e is at most s X 1 1 + N P (k)2 . (7) 2 2 k

13

P The quantity k P (k)2 is the collision probability of the distribution on the key space, namely, the probability that two independently sampled keys are equal. The proof uses the same argument as [AS26]; it depends only on the fact that the ciphertext state is the normalized projection onto the eigenspace, that there are only 1, −1 eigenvalues, and that both eigenspaces have equal dimensions, which follows from the abstractions mentioned above. It is easy to see that the unclonable-encryption scheme   of [AS26] satisfies these conditions. Coset-UE also satisfies them ′ ′ u v u v because Tr (X Z )(X Z ) = 0 for distinct Pauli operators. Finally, substituting the uniform distribution over nonzero orthogonal pairs gives the required bound in (1), proving our informationtheoretic decisional coset monogamy of entanglement theorem. (For the general statement and proof, see Lemma 9.) 2.1.2

Computational Decisional Hidden-Coset Monogamy

The eigenspace identity above averages over the hidden subspace and shifts. In the security experiment for SDE and UPO, the adversary also receives membership programs and auxiliary strings correlated with these hidden values. We cannot replace the coset states by their conditional average without first handling the correlated information. Therefore, we follow the modular template of [CLLZ21, ABH+ 26] to first present an additional computational version of our decisional coset MOE guarantee that would help us prove the security of both SDE and UPO. The computational variant gives A the coset state together with obfuscated membership programs for A + s and A⊥ + t; these programs test membership while hiding A, s, t. It also allows A to receive classical information before splitting the state, as long as this information can be generated without the later pair (u, v), and it allows separate classical information to be given to B and C after (u, v) is sampled. Even with this information, no efficient adversary can make both parties recover ⟨u, t⟩ ⊕ ⟨v, s⟩ with probability noticeably greater than 1/2. (For the formal computational game and theorem, see Definition 39 and Theorem 21.) The proof mainly uses the previous computational coset monogamy of entanglement techniques of [ABH+ 26, CLLZ21]. In particular, subspace-hiding obfuscation lets the proof change the subspaces represented by the public membership programs without an efficient adversary noticing, and the algebraic properties of coset states used in those works remove the remaining dependence on the original hidden coset. The classical information given before the split is then replaced by a separately generated copy with the same distribution that does not use (u, v). After these changes, the remaining experiment is the information-theoretic identical challenge-decisional game proved above. Thus, the proof of the computational MOE theorem follows by combining the earlier computational techniques with our new information-theoretic theorem.

2.2

Correlated-Challenge Single-Decryptor Encryption

Independent challenges do not capture the setting where a ciphertext is generated once and then copied to several users, or when the same or correlated messages are encrypted separately to get potentially different challenge distributions. We therefore want a single definition that includes independent encryption executions, literal copies of one ciphertext, and arbitrary correlations between the two challenge bits, subject to uniform marginals. We define such a notion of SDE security as follows. Correlated-challenge SDE security. The experiment begins as in the usual SDE game: the challenger gives (pk, sk ) to A, who prepares one register for B and one for C. In addition, A chooses polynomially many challenge-message pairs. The use of several pairs means that one challenge bit 14

chooses the left or right message in every pair; it does not mean that a new challenge bit is sampled for each pair. The experiment has two modes. In separate mode, A may choose different message pairs for B and C. The challenger samples (bB , bC ) from any efficiently samplable joint distribution such that the marginal distribution on each of the two individual bits is uniform, and independently encrypts one of the two messages from the polynomially many pairs of challenge messages according to the bit bX , and gives the resulting ciphertexts to recipient X. Note that the two bits may be independent, or arbitrary correlated. In identical mode, A chooses the same message pairs for both B and C, and the challenger samples one uniform bit b, generates one ciphertext for each message selected by b, and gives an exact copy of every resulting ciphertext to both recipients. The scheme is secure if no efficient (A, B, C) makes both recipients recover their respective challenge bits with probability noticeably greater than 1/2. When there is only one challenge-message pair, the two modes reduce to the usual independent-CPA and identical-CPA experiments. (For the formal sampler and security game, see Definitions 21 and 22.) Construction. We use the coset-based SDE construction of [KY25]. Key generation samples A, s, t, publishes obfuscated programs testing membership in A + s and A⊥ + t, and uses |As,t ⟩ as the quantum decryption key. To encrypt a message µ, the encryption algorithm chooses a uniformly random string r, called the pad, and obfuscates a program with the following behavior: on an input from A + s, it returns µ ⊕ r, while on an input from A⊥ + t, it returns r. An honest decryptor evaluates the first behavior using the coset state, applies Hadamard gates to obtain the dual coset state, evaluates the second behavior, and sum the two answers to recover µ. Both evaluations are reversed, so the quantum decryption key is restored. Security proof: reduction to computational decisional coset monogamy of entanglement. We follow the proof template of [KY25], but now in the setting of correlated ciphertext distribution. In order to handle arbitrary correlation among challenge bits bB and bC , we observe that it is possible to rewrite arbitrarily correlated challenge bits using one identical hidden bit, without changing the overall distribution. Indeed, two bits that are individually uniform can be sampled by first deciding whether they should be equal or opposite and then sampling their common random value. Let ∆ record this first choice: ∆ = 0 means that the bits are equal and ∆ = 1 means that they are opposite. Their joint distribution can then be written as (g, g ⊕ ∆) for a uniform bit g. The computational coset monogamy game provides the hidden bit e = ⟨u, t⟩ ⊕ ⟨v, s⟩. We sample another uniform bit ζ and set bB = e ⊕ ζ

and

bC = e ⊕ ζ ⊕ ∆.

(8)

Because e ⊕ ζ is uniform, these two bits have the desired joint distribution. Moreover, correct answers from B and C immediately give two answers to the same monogamy challenge: Add B’s answer with ζ, and add C’s answer with ζ ⊕ ∆. If both recipients answered correctly, both resulting bits equal e. The remaining question is how to create the corresponding ciphertexts without knowing the shifts s and t. We rewrite the ciphertext program so that its value on A + s depends only on ⟨v, s⟩, while its value on A⊥ + t depends only on ⟨u, t⟩. These two bits can be computed from the program’s input: ⟨v, w⟩ = ⟨v, s⟩ for w ∈ A + s, and ⟨u, w⟩ = ⟨u, t⟩ for w ∈ A⊥ + t. The rewritten program agrees with an honestly generated ciphertext program on every input, so iO allows us to replace one by the other. This is the same programming idea used in the proof of Kitagawa and 15

Yamakawa [KY25]; the new point is that the equal-or-opposite representation above makes it work for every allowed correlation between the two challenge bits. Thus, if both SDE recipients recover their challenge bits, the two summing corrections described above make both of them recover e, contradicting computational decisional coset monogamy of entanglement. In identical mode, we use the same message pair, pad, program, and obfuscation randomness for both recipients and copy the resulting classical ciphertext. The proof therefore preserves the fact that the two recipients receive exactly the same ciphertext. (For the formal construction and reduction, see Section 8 and Theorem 22.)

2.3

Copy Protection from Correlated UPO

Given a UPO scheme (Obf, Eval), we protect a circuit C by running Obf(C) and evaluate it using Eval. The security proof changes the value of C at the challenge points. UPO ensures that two recipients cannot distinguish the protected original circuit from the protected modified circuit, while the classical assumptions on C ensure that its original values at those points remain hidden after the change. This follows the framework of [AB24, ABH+ 26]. The new point is that our proofs preserve the correlation between the two challenge points and modify the circuit only once when those points are equal. Point functions and k-point functions. A point function Py outputs one only at the marked point y and zero everywhere else. If an independently sampled challenge point has high min-entropy, then it equals y only with negligible probability. In this independent case, we can therefore replace the required answer by zero and then use UPO security to replace the protected point function by the protected all-zero circuit. This extends the proof of [AB24] from uniformly random points to arbitrary high-min-entropy distributions. The same argument applies to functions that output one on k marked points, under the corresponding sampling and entropy requirements. (For the formal statements, see Theorem 25 and Corollary 5.) Compute-and-compare functions and auxiliary information. A compute-and-compare function has the form CCf,y (x) = [f (x) = y]. The natural construction publishes f , protects the point function Py , and evaluates it on f (x), as in [CMP24]. Its security does not follow immediately from point-function copy protection: the public function f may be correlated with y, and the recipients are challenged with a preimage x, not directly with the point f (x). A reduction must therefore give f to A before she sends out the two registers, but give x to B and C only afterwards. Correlated UPO allows precisely this order of information. We give f to A first, use z = f (x) as the common UPO challenge point, and give the same preimage x to both recipients later. The required entropy condition says that z remains difficult to guess even after f is known. An attack on the resulting compute-and-compare copy protection would therefore give an attack on correlated UPO. This is why the auxiliary-information feature of our UPO definition is needed for this application. (For the formal result, see Theorem 26.) General function classes with correlated challenges. The transformations of [AB24, ABH+ 26] also extend to general functions satisfying the required classical security properties. For unpredictabilitystyle security, where both recipients must compute the correct function values, we change the circuit at the distinct challenge points. For pseudorandomness-style security, where each recipient must distinguish the real value from a random one, we change only the values selected to be random. Throughout both arguments, the two challenge points remain jointly distributed. If they are equal,

16

the circuit is changed only once, following the same convention as in the correlated UPO experiment. (For the formal transformations, see Theorems 27 and 29.) Oracle access with an identical challenge. Here A receives the protected program and oracle access to the original function C. After she sends one register to each recipient, the challenger samples a high-min-entropy point x and gives the same x to both recipients. In addition, B receives oracle access to C \x , which agrees with C everywhere except that it returns ⊥ at x, and C receives oracle access to this same function C \x . The only additional issue is A’s earlier access to C. The point x is sampled only after she sends the two registers and is difficult to guess, so her polynomially many oracle queries are very unlikely to involve x. A standard quantum-query argument therefore lets us replace her oracle by C \x with only a negligible change. Since B and C already receive the same point and the same punctured oracle, the rest of the proof follows directly from correlated UPO. (For the formal results, see Theorems 28 and 30.)

17

3

Preliminaries

3.1

Notation and Conventions

We refer the reader to [Gol01, Gol04] for a preliminary on cryptography and to [NC10] for a preliminary on quantum information and computation. We follow the notations and conventions commonly used in (quantum) cryptography, theoretical computer science and mathematics. In this section, we non-exhaustively highlight some of them. All of our conventions are implicitly followed unless otherwise specified, e.g. our cryptographic assumptions are always post-quantum even though most of the time we will not write this explicitly, and if there is a rare occasion where we assume classical security only, we will specify this explicitly. Functions For a function f : N+ → N+ , we will say that it is an efficiently computable function if it is polynomially bounded, that is, if there is some n0 ∈ N+ and c ∈ R+ such that f (n) ≤ nc for all n > n0 . Sometimes we will say polynomial to also mean polynomially bounded instead (e.g. √ we will say polynomial to refer to O(poly(λ)), which includes, say, n) - the precise meaning will be clear from context. f (λ) is said to be negligible if for any c ∈ N+ , there is n0 ∈ N+ such that f (λ) ≤ n1c for all n ≥ n0 . f (λ) is said to superlogarithmic if f = ω(log(λ)) or equivalently, if 2−f (λ) is negligible. When we describe a function, such as a polynomial, if no input is mentioned, it will implicitly be the security parameter λ. Classical and Quantum Information and Oracles Variables written in lower-case, such as pk, sk or pk, sk, are classical objects. Variables written in the font sk are quantum variables. We write R to mean a quantum register, which keeps a quantum state that will evolve when the register is acted on, and it can be entangled with other registers. We write R ← ρ to mean that the register R is initialized with a sample from the quantum distribution (i.e. mixed state) ρ. For simplicity, we will usually write non-normalized versions of the quantum states, however, they are always implicitly normalized. For mixed states ρ and σ, we write ∥ρ − σ∥T r := 12 ∥ρ − σ∥1 for their trace distance. We write O to denote a classical oracle, and write AO to denote an algorithm that has quantum query-access to O. Similarly, for unitary oracles we write U and AU . All adversaries always have quantum access to all of the oracles. Distributions When S is a set, we write x ← S to mean that x is sampled uniformly at random from S. When D is a distribution, we write x ← D to mean that x is sampled from D. Finally, we write x ← B(R) or x ← B(a) to mean that x is a sample as output by the (quantum or classical randomized) algorithm B run on the quantum input register R or classical input a. We use similar notation for quantum registers, e.g., R ← B(a). Adversaries and Constructions/Algorithms We write QPT to mean quantum polynomial time and PPT to mean probabilistic (classical) polynomial time. We say query-bounded to mean that the algorithm (e.g. construction, adversary) makes polynomially many queries to the oracle, but it can possibly take unbounded time outside the queries. All of these are polynomial in the security parameter λ. Note that for QPT and PPT, this also means that the inputs to these algorithms are also of polynomial size in λ.

18

We say efficient to mean QPT or PPT (will be clear from context) in the plain model, or query-bounded in the oracle model. For constructions, efficient means QPT or PPT, even in the oracle model (though the oracles themselves might not be efficiently sampleable or implementable). In the plain model, adversaries will be implicitly QPT. In the oracle security model, adversaries will be implicitly query-bounded. An admissible adversary means an adversary that conforms to the (implicit) requirements of the security game (e.g. polynomial time or query bounded, has the correct interaction model and has correct input-output format and so on). All of our cryptographical assumptions are post-quantum, e.g., one-way functions means post-quantum secure one-way functions. Adversaries are stateful uniform QPT. When we say that a primitive is subexponentially secure, we mean that any polynomial time adversary has subexponentially small advantage. Sometimes we require security against subexponential time adversaries, in which case we will specify this explicitly. All algorithms of a cryptographic scheme are uniform (stateless) PPT or QPT (will be clear from context). Security Games A security game is a binary random variable which is the outcome of an experiment between a challenger and an adversary. For a security game, we say that the adversary has won if the experiment output is 1, and otherwise we say that the adversary has lost. When we say that an adversary has negligible advantage, we mean that the probability of the adversary winning (or distinguishing, depending on context) is upper bounded by a negligible function of λ. Domains We write M to denote the message space for various cryptographic primitives, and it will be equal to {0, 1}p(λ) for some polynomial p(·) (will be clear from context).

3.2

Pseudorandom Functions

In this section, we recall pseudorandom functions (PRF) and puncturable PRFs. Definition 1 (Pseudorandom Functions). A pseudorandom function (PRF) scheme PRF is a family of functions {F : {0, 1}c(λ) × {0, 1}m(λ) → {0, 1}n(λ) }λ∈N+ along with the following efficient algorithms. • PRF.Gen(1λ ) : Takes in the unary representation of the security parameter and outputs a key K in {0, 1}c(λ) . • PRF.Eval(K, x) : Takes in a key K ∈ {0, 1}c(λ) and an input x ∈ {0, 1}m(λ) , outputs an evaluation of the PRF in {0, 1}n(λ) . We require the following. Correctness.   Pr ∀x PRF.Eval(K, x) = F (K, x) : K ← PRF.Gen(1λ ) = 1. Security

We require that for any QPT adversary A, Pr [AH (1λ ) = 1] −

H←H

[AF (K,·) (1λ ) = 1] ≤ negl(λ).

Pr

K←PRF.Gen(1λ )

where H is the uniform distribution over the functions {0, 1}m(λ) → {0, 1}n(λ) . 19

We will usually write FK (x) or F (K, x) in algorithms and this will implicitly mean PRF.Eval(K, x). Definition 2 (Puncturable PRF). A puncturable PRF scheme PRF is a PRF scheme together with the following efficient algorithm. • K{S} ← PRF.Puncture(K, S) takes a key K ∈ {0, 1}c(λ) and a polynomial-size set S ⊆ {0, 1}m(λ) , and outputs a punctured key K{S} . We require the following properties. Punctured correctness. For every polynomial-size set S ⊆ {0, 1}m(λ) and every x ∈ {0, 1}m(λ) \ S, h i Pr FK{S} (x) = FK (x) : K ← PRF.Gen(1λ ), K{S} ← PRF.Puncture(K, S) = 1. Pseudorandom at punctured point. For every polynomial-size set S ⊆ {0, 1}m(λ) and every QPT distinguisher A, h   i Pr A FK{S} , {FK (x)}x∈S = 1  i h  − Pr A FK{S} , (Un(λ) )|S| = 1 ≤ negl(λ), where in both probabilities K ← PRF.Gen(1λ ),

K{S} ← PRF.Puncture(K, S),

and Un(λ) is the uniform distribution over {0, 1}n(λ) . If S = {x⋆1 , . . . , x⋆q }, we write K{x⋆1 ,...,x⋆q } for K{S} . For brevity, we sometimes write KS as simply K{S} . It is easy to see that any puncturable PRF scheme that satisfies puncturing security also satisfies usual PRF security. Theorem 7 ([SW14, Zha12]). Let n(·), m(·) be polynomially bounded. • If (post-quantum) one-way functions exist, then there exists a (post-quantum) puncturable PRF with input space {0, 1}m(λ) and output space {0, 1}n(λ) . • If subexponentially-secure (post-quantum) one-way functions exist, then for any c > 0, there c exists a (post-quantum) 2−λ -secure6 puncturable PRF with input space {0, 1}m(λ) and output space {0, 1}n(λ) .

3.3

Digital Signature Schemes

In this section we recall the definition of signatures schemes. Definition 3. A digital signature scheme with message space M consists of the following efficient algorithms that satisfy the correctness and security guarantees below. 6

While the original results are for negligible security against polynomial time adversaries, it is easy to see that they carry over to subexponential security. Further, by scaling the security parameter by a polynomial and simple input/output conversions, subexponentially secure (for any exponent c′ ) one-way functions is sufficient to construct c for any c a puncturable PRF that is 2−λ -secure.

20

• Setup(1λ ) : Takes the unary representation of the security parameter and outputs a signing key sk and a verification key vk. • Sign(sk, m) : Takes a signing key sk and a message m ∈ M, returns a signature for m. • Ver(vk, m, sig) : Takes the public verification key vk, a message m ∈ M and an alleged signature sig for m, outputs 1 if s is a valid signature for m. Correctness

We require the following for all messages m ∈ M.   sk, vk ← Setup(1λ ) = 1. Pr Ver(vk, m, s) = 1 : s ← Sign(sk, m)

Adaptive existential-unforgeability security under chosen message attack (EUF-CMA) We require that any QPT adversary A wins the following game with negligible probability. 1. The challenger samples the keys sk, vk ← Setup(1). 2. The adversary A receives vk, and interacts with the signing oracle by sending classical messages m ∈ M and receiving the corresponding signatures that is computed by the challenger as sig ← Sign(sk, m). 3. The adversary A outputs a message m∗ ∈ M that it has not queried the oracle with and a forged signature sig ∗ . 4. The challenger outputs 1 if and only if Ver(vk, m∗ , sig ∗ ) = 1. If the adversary A is required to output the message m∗ before receiving vk, we call it selective EUF-CMA security.

3.4

Indistinguishability Obfuscation

In this section, we recall indistinguishability obfuscation (iO). Definition 4 (Indistinguishability Obfuscation). An indistinguishability obfuscation (iO) scheme for a class of circuits C = {Cλ }λ is an efficient algorithm iO that satisfies the following. Correctness.

For all λ ∈ N+ , C ∈ Cλ and all inputs x to C, h i Pr C̃(x) = C(x) : C̃ ← iO(1λ , C) = 1.

Security. Let B be any QPT algorithm that outputs two circuits C0 , C1 ∈ C of the same size, along  with quantum auxiliary information Raux , such that Pr ∀x C0 (x) = C1 (x) : (C0 , C1 , Raux ) ← B(1λ ) ≥ 1 − negl(λ). Then, for any QPT adversary A, h i Pr A(iO(1λ , C0 ), Raux ) = 1 : (C0 , C1 , Raux ) ← B(1λ ) − h i Pr A(iO(1λ , C1 ), Raux ) = 1 : (C0 , C1 , Raux ) ← B(1λ ) ≤ negl(λ).  For subexponentially secure obfuscation, we  require security for circuit samplers B such that Pr ∀x C0 (x) = C1 (x) : (C0 , C1 , Raux ) ← B(1λ ) = 1. Fix an arbitrary constant c > 0 and set n := ⌈λc/3 ⌉. 21

3.5

Subspace-Hiding Obfuscation

Definition 5 (Subspace-hiding obfuscation). Let N = N (λ) and d0 = d0 (λ) < d1 = d1 (λ) ≤ N (λ) be polynomially bounded. A subspace-hiding obfuscator shO is a PPT algorithm that, on input 1λ λ b and a subspace S ≤ FN 2 of dimension d0 or d1 , outputs a circuit S ← shO(1 , S). Correctness. For every such subspace S, except with negligible probability over the randomness b of shO, S(x) = 1 if and only if x ∈ S for every x ∈ FN 2 . Security. For every QPT algorithm B that outputs a d0 -dimensional subspace S0 ≤ FN 2 together with quantum auxiliary information R, the following distributions are computationally indistinguishable:   λ ), (S , R) ← B(1   0   n o $ λ λ b b b N . (R, S0 ) : (S0 , R) ← B(1 ), S0 ← shO(1 , S0 ) ≈c (R, S1 ) : S1 ← − {S ≤ F2 : dim(S) = d1 , S0 ⊆ S},     λ b S1 ← shO(1 , S1 ) (9) Theorem 8 (Subspace-hiding obfuscation from iO and one-way functions [Zha21, CLLZ21, ABH+ 26]). Assume the existence of post-quantum polynomially secure iO and post-quantum one-way functions. Then, for every polynomially bounded n = n(λ) ∈ ω(log λ), there exists a post-quantum secure subspace-hiding obfuscator for N = 4n, d0 = 2n, and d1 = 3n. These are the parameters used in Theorem 21.

3.6

Universal Hash Functions and Average Conditional Min-Entropy

Definition 6 (Average conditional min-entropy). For jointly distributed classical random variables X, Z, define ! X e ∞ (X | Z) := − log Pr[Z = z] max Pr[X = x | Z = z] . (10) H x

z

When Z is empty, this is the usual min-entropy of X. Definition 7 (Universal hash family). A family H of functions from {0, 1}ℓ to {0, 1}m is universal if it is efficiently sampleable and, for every distinct x, x′ ∈ {0, 1}ℓ , Pr $ [h(x) = h(x′ )] ≤ 2−m . h← −H Theorem 9 (Universal hash families). For every polynomially bounded ℓ = ℓ(λ) and m = m(λ), there exists an efficiently sampleable universal hash family from {0, 1}ℓ to {0, 1}m . In Theorem 23, we use such a family from Xλ = {0, 1}ℓin (λ) to {0, 1}8n . Lemma 1 (Leakage bound and leftover hash lemma). Let X, Y, Z be jointly distributed classical e ∞ (X | Z, Y ) ≥ H e ∞ (X | Z) − q. Moreover, let H be a random variables. If | Supp(Y )| ≤ 2q , then H $

universal hash family from the support of X to {0, 1}m , let h ← − H be independent of (X, Z), and $ m e ∞ (X | Z) ≥ m + 2 log(1/ε), then (h, Z, h(X)) let Um ← − {0, 1} be independent of (h, X, Z). If H and (h, Z, Um ) are within statistical distance at most ε.

22

3.7

Injective/Lossy Functions

Definition 8 (Injective/lossy functions). An injective/lossy function family LF = (LF.Geninj , LF.Genloss ) with domain Xλ and range Tλ consists of two PPT algorithms that output descriptions of deterministic functions L : Xλ → Tλ . We require the following. 1. Every L ← LF.Geninj (1λ ) is injective. 2. There exists a polynomially bounded function ℓimg = ℓimg (λ) such that every L ← LF.Genloss (1λ ) satisfies | Im(L)| ≤ 2ℓimg . 3. The distributions {LF.Geninj (1λ )}λ and {LF.Genloss (1λ )}λ are computationally indistinguishable against QPT algorithms. Theorem 10 (Injective/lossy functions from LWE [ABH+ 26]). Assume the quantum hardness of LWE. Then, for every constant c > 0 and every polynomially bounded input length ℓin = ℓin (λ) satisfying ℓin (λ) ≥ λc , there exists a post-quantum secure injective/lossy function family with domain {0, 1}ℓin (λ) for which ℓimg ≤ λ2c/3 . This is the parameter setting used in the proof of Theorem 23.

3.8

Unclonable Encryption

Next, we define (one-time) unclonable encryption for single bit messages. Definition 9 (Unclonable encryption for bits). An unclonable encryption scheme for bits is a tuple UE = (KeyGen, Enc, Dec) with the following syntax. • k ← KeyGen(1λ ) outputs a classical key k ∈ Kλ . • ρct ← Enc(k, m), on input m ∈ {0, 1}, outputs a quantum ciphertext in a finite-dimensional Hilbert space Hct . • m′ ← Dec(k, ρct ) outputs a bit. For every m ∈ {0, 1}, correctness requires   k ← KeyGen(1λ ), Pr m′ = m : ρct ← Enc(k, m),  ≥ 1 − negl(λ). m′ ← Dec(k, ρct )

(11)

For arbitrary finite-dimensional Hilbert spaces HB and HC , let an adversary AUE consist of a quantum channel ΦA : L(Hct ) −→ L(HB ⊗ HC ) (12) and, for every k ∈ Kλ , binary POVMs {B0k , B1k } on HB and {C0k , C1k } on HC . Consider the following experiment. UE-Unclonable-IndistinguishableUE,AUE (1λ ): $

1. Ch samples k ← KeyGen(1λ ) and m ← − {0, 1}, computes ρct ← Enc(k, m), and sends ρct to A while retaining k. 2. A applies ΦA and sends the resulting registers to B and C. 3. After the split, Ch sends k to both B and C. 23

4. B measures with {B0k , B1k } and outputs m b B , while C measures with {C0k , C1k } and outputs m b C. 5. The output of the experiment is 1 if m bB = m b C = m. Definition 10 (ϵ-unclonable indistinguishable security). For ϵ = ϵ(λ) ≥ 0, define the winning advantage of AUE by h i 1 λ AdvUI (13) UE,AUE (λ) := Pr UE-UIUE,AUE (1 ) = 1 − . 2 The scheme UE satisfies ϵ-unclonable indistinguishable security if, for every (potentially unbounded) adversary AUE as above, (14) AdvUI UE,AUE (λ) ≤ ϵ(λ), or equivalently, h i 1 Pr UE-UIUE,AUE (1λ ) = 1 ≤ + ϵ(λ). 2

3.9

(15)

Quantum Information

We recall some facts about quantum information that we use later. Gentle measurement and rewinding. The almost-as-good-as-new lemma shows that a measurement that accepts with high probability can be gently rewound. Lemma 2 (Almost As Good As New Lemma [Aar16]; see also [Win99]). Let d, d′ ∈ N+ , let ρ be a ′ mixed state over Cd , and let U be a unitary over Cd ⊗ Cd . Let (Π0 , Π1 = I − Π0 ) be a projective ′ measurement over Cd ⊗Cd . Consider the measurement that appends an ancillary register initialized to |0⟩⟨0|, applies U , and then measures (Π0 , Π1 ). Suppose that, for some ϵ ∈ [0, 1], i h Tr Π0 U (ρ ⊗ |0⟩⟨0|) U † = 1 − ϵ. Define 



ρe := TrCd′ U † 

  X

Πb U (ρ ⊗ |0⟩⟨0|) U † Πb  U  .

b∈{0,1}

Then, ∥ρ − ρe∥T r ≤

√

ϵ.

We refer to the operation of undoing U after the measurement and then tracing out the ancillary register as rewinding the measured register. Thus, ρe in Lemma 2 is the state obtained after rewinding. Projective and threshold implementations. Definition 11 (Projective implementation [Zha20]). Let P = (P, I − P ) be a binary-outcome POVM. A projective implementation of P is a projective measurement E = (Πp )p∈S , for a finite set S ⊆ [0, 1], such that the following measurement is equivalent to P: apply E to obtain p, and output 1 with probability p and 0 otherwise. We denote the unique projective implementation of P by ProjImp(P).

24

We use the following efficient, gapped form of approximate threshold implementation for a general efficient POVM. The fixed running-time and reference-system guarantees are recorded explicitly because both are needed in our reductions. Lemma 3 (Fixed-time gapped approximate threshold instrument [Zha20, ALL+ 21]). Let P = (P, I − P ) be an efficient binary-outcome POVM on a register A, where an efficient implementation means a uniform polynomial-size unitary dilation (with its inverse) followed by a one-qubit projective measurement. Let 0 ≤ s < c ≤ 1, where ∆ := c − s is inverse polynomial, and let η ∈ (0, 1] be inverse polynomial. There is a uniform, fixed-polynomial-time two-outcome instrument
GATIc,s η (P) = A, R with the following properties. Write Πhi := 1[P ≥ c],

Πlo := 1[P ≤ s].

For every subnormalized state ρAR , with an arbitrary reference register R, and σ := (A ⊗ IdR )(ρ), we have Tr[(Πhi ⊗ I)ρ] − η Tr(ρ) ≤ Tr(σ), Tr(σ) ≤ Tr[(1[P > s] ⊗ I)ρ] + η Tr(ρ), Tr[(Πlo ⊗ I)σ] ≤ η Tr(ρ).

(16) (17) (18)

Consequently, for σ := (1[P > s] ⊗ I)σ(1[P > s] ⊗ I), we have

√ ∥σ − σ∥1 ≤ 3 η Tr(ρ).

Tr(σ) ≥ Tr(σ) − η Tr(ρ),

(19)

The running time is
TP · poly ∆−1 , log(1/η), η −1 , where TP is the running time of the dilation of P. The same circuit and bounds apply uniformly for every reference register. Proof. Purify all classical coins and deferred measurements in the implementation of P. To recall why the cited threshold construction applies to a general efficient POVM, let Π0 project the dilation workspace onto its initial state and let Π1 be the accepting projector pulled back through the dilation unitary. On the image of Π0 , Π0 Π1 Π0 = P. The standard two-projector (Jordan-block) construction underlying the approximate projective implementation of Zhandry [Zha20] and the approximate threshold implementation of Aaronson et al. [ALL+ 21] therefore measures the spectral parameter of P and returns the dilation workspace to its initial state. This gives an instrument on A, not merely on the dilation space. Set ξ := ∆/4 and run that approximate threshold implementation at threshold c − ξ, with shift and almost-projectivity errors at most η/20. Its shift guarantee compares its acceptance probability from below with the exact threshold projector 1[P ≥ c] and from above with 1[P > c − 2ξ] ⪯ 1[P > s], up to error η/20. Its post-measurement guarantee places all but η/10 of the accepted subnormalized state above threshold c − 3ξ > s. These are operator and local post-state guarantees on A. For an input entangled with R, the reduced accepted state on A is exactly A(ρA ); hence the same probability and low-subspace bounds hold after tensoring the construction with IR . 25

The cited implementation has expected running time TP poly(∆−1 , log(1/η)), uniformly over its input state. Fix a corresponding polynomial upper bound Texp and truncate after 20Texp /η steps, outputting reject if the cutoff is reached. Markov’s inequality bounds the cutoff probability by η/20 for every input, including one entangled with a reference. Absorbing the approximation and truncation errors proves Equations (16) to (18) and gives the claimed fixed polynomial running time. Finally, Equation (19) follows from Equation (18) and the gentle-measurement inequality, after normalizing ρ; the displayed constant also absorbs the discarded low-subspace block. Definition 12 (Threshold implementation [Zha20, ALL+ 21]). Let P and ProjImp(P) = (Πp )p∈S be as above. For a threshold τ ∈ [0, 1], the threshold implementation of P with threshold τ is the binary projective measurement   X X Πp  . Πp , I − TIτ (P) :=  p≥τ

p≥τ

When clear from context, we also use TIτ (P) to denote its projector corresponding to outcome 1.

26

Part I

Definitional Work 4

Single-Decryptor Encryption Security Definitions

In this section, we present security definitions for single-decryptor encryption (SDE). We first define syntax and correctness. We then recall the prior security definitions in Section 4.1 and present our new definition in Section 4.2. Finally, in Section 4.3, we discuss the relationships between these notions. Now we present the syntax. Definition 13 (Single-Decryptor Encryption (SDE)). A public-key single-decryptor encryption scheme SDE = (GenKey, Enc, Dec) for the message space M consists of the following efficient, possibly quantum, algorithms. • GenKey(1λ ): Takes as input a security parameter and outputs a classical public key pk and a quantum decryption key sk . • Enc(pk, m): Takes as input a public-key pk and a message m ∈ M and outputs a classical ciphertext ct. • Dec(sk , ct): Takes as input a decryption key sk and a ciphertext ct, and outputs a message m ∈ M or ⊥. We require the following correctness guarantee. Correctness:

4.1

For any message m ∈ M, there exists a negligible function negl(λ) such that   (pk, sk ) ← GenKey(1λ )  ≥ 1 − negl(λ). ct ← Enc(pk, m) Prm′ = m : ′ m ← Dec(sk , ct)

Prior Definitions

We recall the prior security definitions for SDE. Each game is between a challenger and an adversary tuple A = (A, B, C). The adversary A receives the quantum decryption key and splits it into two, possibly entangled, registers for B and C, who do not communicate after receiving their registers. We begin with the two search-type notions. Definition 14 (Independent-Challenge Search Anti-Piracy [CLLZ21, KY25]). Let SDE be an SDE scheme with message space M, and let A = (A, B, C) be an adversary tuple. Consider the following game. SDE-IND-SEARCHSDE,A (1λ ) 1. The challenger samples (pk, sk ) ← SDE.GenKey(1λ ) and submits (pk, sk ) to A. 2. A outputs a pair of registers (R1 , R2 ). The challenger submits R1 to B and R2 to C. 3. The challenger independently samples mB , mC ← M and, in two independent executions of encryption, computes ctB ← SDE.Enc(pk, mB ) and ctC ← SDE.Enc(pk, mC ). 27

4. The challenger submits ctB to B and ctC to C. Then, B outputs m e B and C outputs m e C. 5. The challenger outputs 1 if and only if m e B = mB and m e C = mC . SDE satisfies independent-challenge search anti-piracy security if, for every QPT adversary A, h i 1 Pr SDE-IND-SEARCHSDE,A (1λ ) = 1 ≤ + negl(λ). |M| Definition 15 (Identical-Challenge Search Anti-Piracy [KY25]). Let SDE be an SDE scheme with message space M, and let A = (A, B, C) be an adversary tuple. Consider the following game. SDE-IDEN-SEARCHSDE,A (1λ ) 1. The challenger samples (pk, sk ) ← SDE.GenKey(1λ ) and submits (pk, sk ) to A. 2. A outputs a pair of registers (R1 , R2 ). The challenger submits R1 to B and R2 to C. 3. The challenger samples m ← M and computes a single ciphertext ct ← SDE.Enc(pk, m). 4. The challenger submits this same ciphertext ct to both B and C. Then, B outputs m e B and C outputs m e C. 5. The challenger outputs 1 if and only if m e B = m and m e C = m. SDE satisfies identical-challenge search anti-piracy security if, for every QPT adversary A, h i 1 Pr SDE-IDEN-SEARCHSDE,A (1λ ) = 1 ≤ + negl(λ). |M| We next recall the two CPA-type notions. In the independent-challenge game, the adversary may choose a different message pair for each party ([KY25]). The original definition of Coladangelo et al. ([CLLZ21]) requires the two pairs to be equal. Definition 16 (Independent-Challenge CPA Anti-Piracy [CLLZ21, KY25]). Let SDE be an SDE scheme with message space M, and let A = (A, B, C) be an adversary tuple. Consider the following game. SDE-IND-CPASDE,A (1λ ) 1. The challenger samples (pk, sk ) ← SDE.GenKey(1λ ) and submits (pk, sk ) to A. 2. A outputs message pairs (mB,0 , mB,1 ) ∈ M2 and (mC,0 , mC,1 ) ∈ M2 , and a pair of registers (R1 , R2 ). The challenger submits R1 to B and R2 to C. 3. The challenger samples bB , bC ← {0, 1} independently. In two independent executions of encryption, it computes ctB ← SDE.Enc(pk, mB,bB ) and ctC ← SDE.Enc(pk, mC,bC ). 4. The challenger submits ctB to B and ctC to C. Then, B outputs ebB and C outputs ebC . 5. The challenger outputs 1 if and only if ebB = bB and ebC = bC . SDE satisfies independent-challenge CPA anti-piracy security if, for every QPT adversary A, h i 1 Pr SDE-IND-CPASDE,A (1λ ) = 1 ≤ + negl(λ). 2 Definition 17 (Identical-Challenge CPA Anti-Piracy [GZ20]). Let SDE be an SDE scheme with message space M, and let A = (A, B, C) be an adversary tuple. Consider the following game. 28

SDE-IDEN-CPASDE,A (1λ ) 1. The challenger samples (pk, sk ) ← SDE.GenKey(1λ ) and submits (pk, sk ) to A. 2. A outputs a message pair (m0 , m1 ) ∈ M2 and a pair of registers (R1 , R2 ). The challenger submits R1 to B and R2 to C. 3. The challenger samples b ← {0, 1} and computes a single ciphertext ct ← SDE.Enc(pk, mb ). 4. The challenger submits this same ciphertext ct to both B and C. Then, B outputs ebB and C outputs ebC . 5. The challenger outputs 1 if and only if ebB = b and ebC = b. SDE satisfies identical-challenge CPA anti-piracy security if, for every QPT adversary A, h i 1 Pr SDE-IDEN-CPASDE,A (1λ ) = 1 ≤ + negl(λ). 2 CPA+ anti-piracy uses the independent-challenge CPA experiment with a stronger winning condition. Definition 18 (CPA+ Anti-Piracy Security [KY25]). Let SDE be an SDE scheme and let A = (A, B, C) be an adversary tuple. The game SDE-CPA+ SDE,A (1λ ) is identical to the experiment in Definition 16, except that the challenger outputs 1 if and only if ebB ⊕ ebC = bB ⊕ bC . SDE satisfies CPA+ anti-piracy security if, for every QPT adversary A, h i 1 Pr SDE-CPA+ SDE,A (1λ ) = 1 ≤ + negl(λ). 2 We finally recall strong anti-piracy security ([CLLZ21, KY25]). A quantum decryptor is a pair D = (ρ, U ), where ρ is a quantum state and U is a unitary circuit that takes a ciphertext and ρ as input and produces a classical output. We define the two tests used in the strong definitions. CPA test. For a public key pk, a message pair (m0 , m1 ), and a quantum decryptor D, let PDcpa [pk; m0 , m1 ] denote the binary-outcome POVM corresponding to the following test: sample b ← {0, 1}, compute ct ← SDE.Enc(pk, mb ), run D(ct), and accept if and only if the output is b. The γ-good CPA test applies TI1/2+γ (PDcpa [pk; m0 , m1 ]) to the quantum state of D, where for any ϵ and binary outcome POVM P , TIϵ (P ) denotes the threshold implementation (with threshold ϵ) of P , as defined in Section 3.9. Search test. Fix a public key pk and a quantum decryptor D. Let PDsearch [pk] denote the binary-outcome POVM corresponding to the following test. Sample m ← M, compute ct ← SDE.Enc(pk, m), and run D(ct). Accept if and only if the output is m. The γ-good search test applies TI1/|M|+γ (PDsearch [pk]) to the quantum state of D. Definition 19 (Strong CPA Anti-Piracy Security [CLLZ21, KY25]). Let γ : N → [0, 1], let SDE be an SDE scheme with message space M, and let A be an adversary. Consider the following game. 29

SDE-STRONG-CPASDE,A (1λ , γ) 1. The challenger samples (pk, sk ) ← SDE.GenKey(1λ ) and submits (pk, sk ) to A. 2. A outputs message pairs (mB,0 , mB,1 ) ∈ M2 and (mC,0 , mC,1 ) ∈ M2 , and two possibly entangled quantum decryptors DB and DC . 3. The challenger applies the γ-good CPA test with respect to (pk, mX,0 , mX,1 ) to DX , for each X ∈ {B, C}. The challenger outputs 1 if and only if both tests pass. SDE satisfies strong CPA anti-piracy security if, for every inverse polynomial γ and every QPT adversary A, h i Pr SDE-STRONG-CPASDE,A (1λ , γ(λ)) = 1 ≤ negl(λ). Definition 20 (Strong Search Anti-Piracy Security [CLLZ21]). Let γ : N → [0, 1], let SDE be an SDE scheme with message space M, and let A be an adversary. Consider the following game. SDE-STRONG-SEARCHSDE,A (1λ , γ) 1. The challenger samples (pk, sk ) ← SDE.GenKey(1λ ) and submits (pk, sk ) to A. 2. A outputs two possibly entangled quantum decryptors DB and DC . 3. The challenger applies the γ-good search test with respect to pk to each decryptor. The challenger outputs 1 if and only if both tests pass. SDE satisfies strong search anti-piracy security if, for every inverse polynomial γ and every QPT adversary A, h i Pr SDE-STRONG-SEARCHSDE,A (1λ , γ(λ)) = 1 ≤ negl(λ).

4.2

Correlated-Challenge Decision Security

We generalize the prior definition of SDE in two ways. First we allow the challenge bits for B and C to be arbitrarily correlated as long as their marginal distributions are uniform. Secondly, we follow a Left-or-Right version of CPA game where for each freeloader X ∈ {B, C}, there are polynomially many pairs (as opposed to a single pair) of challenge messages that the adversary A can specify, and then the challenger provides either the encryptions of the left half of the challenge message pairs or the encryptions of the right half of the challenge message pairs, depending on the challenge bit for X. Next we define an admissible sampler that specifies this allowed correlation between the challenge bits. Definition 21 (Admissible Challenge Sampler). Fix an SDE scheme SDE. An admissible challenge sampler Samp is an efficient, possibly quantum, algorithm with classical output such that, for every public key pk that SDE.GenKey(1λ ) can output: on input (pk, IND) it returns (bB , bC ) with uniform marginals, and on input (pk, IDEN) it returns one uniform bit b. Equivalently, for every X ∈ {B, C} and β ∈ {0, 1}, 1 [bX = β] = , 2 (bB ,bC )←Samp(pk,IND)

1 [b = β] = . 2 b←Samp(pk,IDEN)

Pr

Pr

(20)

The two bits returned in separate mode may otherwise be arbitrarily correlated. Identical mode has one common bit by syntax. 30

Definition 22 (SDE-CORR Security). Let SDE be an SDE scheme, Samp an admissible challenge sampler, and A = (A, B, C) a QPT adversary tuple. Consider the following game, in which one selector (or selector pair) is used throughout the batch but the message pairs may vary by coordinate. SDE-CORRSDE,A,Samp (1λ ) 1. The challenger samples (pk, sk ) ← SDE.GenKey(1λ ) and submits (pk, sk ) to A. 2. A outputs 1N , for N ≥ 1, a mode mode ∈ {IND, IDEN}, registers (R1 , R2 ), and challengemessage pairs: • if mode = IND, it outputs 4N messages
mB,i,0 , mB,i,1 , mC,i,0 , mC,i,1 i∈[N ] ∈ (M4 )N ; • if mode = IDEN, it outputs 2N messages
mi,0 , mi,1 i∈[N ] ∈ (M2 )N . 3. The challenger sends R1 to B and R2 to C, and creates the challenge batches as follows. • If mode = IND, sample (bB , bC ) ← Samp(pk, IND). For every X ∈ {B, C} and i ∈ [N ], independently compute ctX,i ← SDE.Enc(pk, mX,i,bX ). • If mode = IDEN, sample b ← Samp(pk, IDEN) and set bB = bC := b. For every i ∈ [N ], independently compute one ciphertext cti ← SDE.Enc(pk, mi,b ), and give that same ciphertext to both parties by setting ctB,i = ctC,i := cti . 4. The challenger sends ctX := (ctX,1 , . . . , ctX,N ) to each X ∈ {B, C}. 5. After receiving their batches, B and C output ebB and ebC , respectively. The challenger outputs 1 if and only if ebB = bB and ebC = bC . We demand the output of A in Item 2 to be unary, in order to make N polynomially bounded. Clearly, N = 1 is the usual CPA security with a single-ciphertext. The scheme SDE is SDE-CORR secure if, for every admissible Samp and every QPT A, h i 1 Pr SDE-CORRSDE,A,Samp (1λ ) = 1 ≤ + negl(λ). 2

31

4.3

Hierarchy of Definitions

All statements below concerning search security assume bit-string messages of length m(λ) = ω(log λ). Equivalently, 1/|M| is negligible, so uniform guessing succeeds with only negligible probability in the search games. Figure 1 summarizes the implications and separations proved or recalled below. For notions X and Y, the notation X ⇏ Y means that some SDE scheme satisfies X but not Y. SDE-CORR implies all notions below

×

SDE-CPA+ SDE-STRONG-CPA

×

SDE-IDEN-CPA × ×

SDE-IND-CPA

× ×× × × ×

SDE-IND-SEARCH

×

SDE-IDEN-SEARCH SDE-STRONG-SEARCH × ×

Provenance:

new in this work

Relation:

implies

prior or elementary ×

equivalent

does not imply

Figure 1: Hierarchy of SDE security notions under the standing assumptions of this subsection. Solid arrows denote implication, solid double-headed lines denote equivalence, and dashed directed arrows marked by a midpoint × denote failure of the implication in the arrow direction. Violet heavy lines are new in this work; black lines are prior or elementary. Unmarked directions are not claimed; in particular, the implication from SDE-CPA+ to SDE-IDEN-CPA remains open.

32

We begin with the only implication that uses more than one challenge-message pair in SDECORR security (Definition 22). The proof estimates a quantum test from independently generated ciphertexts and then invokes the approximate threshold measurement of Lemma 3. Preliminaries We first prove a perturbation bound that we need for the results below. Let A, B be Hermitian, let κ > ℓ, and set Π := 1[A ≥ κ] and Q := 1[B ≤ ℓ]. Then ∥QΠ∥ ≤

∥A − B∥ . κ−ℓ

(21)

Here BQ and AΠ denote the restrictions of B and A to the ranges of Q and Π, respectively. They satisfy BQ (QΠ) − (QΠ)AΠ = −Q(A − B)Π, and their spectra are separated by κ − ℓ, which proves the bound. It follows that every positive operator ρ such that Tr(ρ) ≤ 1 and ρ = ΠρΠ satisfies Tr(Qρ) ≤ (∥A − B∥/(κ − ℓ))2 Tr(ρ). The same conclusion holds when ρ is entangled with an additional register. We first record two immediate consequences of the definition. Lemma 4. SDE-CORR security implies SDE-IND-CPA and SDE-IDEN-CPA security. Proof. Set N = 1 in the SDE-CORR game of Definition 22. In separate mode, choosing independent uniform bits bB , bC gives exactly the independent-challenge CPA experiment of Definition 16. In identical mode, the admissible distribution returns one uniform bit and the challenger gives a copy of the resulting ciphertext to each party, which is exactly the identical-challenge CPA experiment of Definition 17. We also recall the implications from prior works. Theorem 11 (Prior relations [KY25, AKL23]). The following relations hold. 1. SDE-CPA+ and SDE-STRONG-CPA security are equivalent. 2. SDE-CPA+ security implies SDE-IND-CPA and SDE-IND-SEARCH security. 3. SDE-STRONG-SEARCH and SDE-IND-SEARCH security are equivalent. 4. SDE-IND-SEARCH security implies SDE-IDEN-SEARCH security. Proof. The first three statements follow from [KY25, Theorem 6.24, Corollary 6.32, Remark 6.19]. The last is the independent-to-identical search implication from [KY25, Section 6.1], which uses the product-to-correlated comparison of Ananth, Kaleoglu, and Liu [AKL23]. The above-mentioned relations show that strong CPA implies strong search. For superlogarithmic message length, this implication is strict, in the sense that not every strong search secure SDE scheme is strong CPA secure. Theorem 12 (Strong CPA strictly implies strong search). For superlogarithmic message length, strong-CPA security implies strong-search security. Assuming post-quantum-secure indistinguishability obfuscation (iO; Definition 4) and post-quantum-secure one-way functions, the converse does not hold. More generally, every strong-search-secure SDE scheme over a message space M0 satisfying 1/|M0 | = negl(λ) yields a strong-search-secure scheme that is not strong-CPA secure.

33

Proof. By Theorem 11, strong CPA is equivalent to CPA+ , CPA+ implies IND-SEARCH, and IND-SEARCH is equivalent to strong search. For strictness, let Π0 be strong-search secure over M0 . Define Πclr over {0, 1} × M0 using the same key generation. Its encryption of (a, m) is (a, Π0 .Enc(pk, m)), and decryption of (a, ct) returns (a, Π0 .Dec(sk , ct)). Fix a decryptor D′ for Πclr . Construct a decryptor D for Π0 as follows. On input ct, it prepares a uniform bit a, runs D′ (a, ct) reversibly, and measures only the final output. It returns m′ if the result is (a, m′ ), and returns a fixed symbol ⊥ ∈ / M0 otherwise. The two decryptors have exactly the same search-success operator. Let K := |M0 |. Because 1/K is negligible, for every inversepolynomial γ and all sufficiently large λ, we have 1/(2K) + γ ≥ 1/K + γ/2. Hence, every state that reaches the strong-search threshold for Πclr with gap γ also reaches the threshold for Π0 with gap γ/2; see Definition 20. Applying this conversion separately to the two decryptors, including when their states are entangled, transforms any strong-search attack on Πclr into one on Π0 without decreasing the probability that both threshold tests accept. $

To violate strong CPA, sample m⋆ ← − M0 and give each receiver the pair ((0, m⋆ ), (1, m⋆ )). Each decryptor reads the first ciphertext component and determines the challenge bit perfectly without using the quantum key. Thus, both CPA acceptance operators are the identity, and both threshold tests accept with probability one, for example when γ(λ) = 1/λ and λ is sufficiently large. Therefore, Πclr is not strong-CPA secure. Under post-quantum-secure iO and one-way functions, the SDE-CORR-secure scheme from Theorem 22 supplies the required base scheme. Next we show that our notion of CORR-SDE security notion implies strong CPA security. Theorem 13 (Correlated challenges imply strong CPA). Every SDE-CORR-secure scheme satisfies SDE-STRONG-CPA security. Proof. We prove the contrapositive. Suppose that there are inverse polynomials γ and ε and a QPT algorithm A, which outputs the two decryptors in the strong-CPA experiment of Definition 19, such that the experiment accepts with probability at least ε for infinitely many security parameters. We construct an adversary for the SDE-CORR game of Definition 22 with non-negligible advantage on this infinite set. Set  2 2 εγ η := . (22) 106 Because η is inverse polynomial, every invocation of Lemma 3 below runs in polynomial time. The constructed adversary runs A internally and controls all subsequent operations by its classical output; we suppress the corresponding classical registers. Local tests. For a binary quantum test, its acceptance operator is the POVM element M for which the acceptance probability on state ρ is Tr(M ρ). For X ∈ {B, C}, let DX be the decryptor produced by A. Given a ciphertext ct, let DX,y (ct) be the measurement operator corresponding to the exact output y ∈ {0, 1}, and define ZX (ct) := DX,0 (ct) − DX,1 (ct). For j ∈ {0, 1}, let ZX,j := Ect←SDE.Enc(pk,mX,j ) [ZX (ct)], and set HX := (ZX,0 − ZX,1 )/4. Let PX be the acceptance operator of the CPA test in Definition 19. Let DX,j,y be the average of DX,y (ct) over ct ← SDE.Enc(pk, mX,j ), and set RX,j := I − DX,j,0 − DX,j,1 . Thus, RX,j is the average measurement operator for outputs outside {0, 1}. Direct calculation gives   RX,0 + RX,1 I HX − PX − = ⪰ 0. (23) 2 4

34

Moreover, ∥HX ∥ ≤ 1/2, so FX := I/2 + HX is a valid acceptance operator. It corresponds to the $

following binary version of the CPA test: choose j ← − {0, 1}, encrypt mX,j , and run DX ; accept if the output is j, reject if it is 1 − j, and accept with probability 1/2 on every other output. For j = 0 and j = 1, the acceptance operators are I/2 + ZX,0 /2 and I/2 − ZX,1 /2, respectively, and their average is FX . Repeating the challenge pair. In the CORR attack, A uses the same strong-CPA message pair in every coordinate: mX,i,j := mX,j for every i ∈ [N ] and j ∈ {0, 1}. If the common challenge bit is b, party X receives ctX = (ctX,1 , . . . , ctX,N ), where each ctX,i encrypts mX,b . Define ! N X Z + Z 1 1 X,0 X,1 b X,b := H . (24) ZX (ctX,i ) − 2 N 2 i=1

The second term is implemented by an independent execution of public-key encryption, and b X,b ] = (−1)b HX . Define the following acceptance operator for a test on the N received ciE[H phertexts: b X,b H I GX (ctX ) := + . (25) 2 2 Although b appears in the notation because it determines the distribution of the received cipher$

texts, the test does not use b. To implement it, flip a fair coin. On heads, choose i ← − [N ], run DX on ctX,i , accept on output 0, reject on output 1, and accept with probability 1/2 P on every other −1 output. The acceptance operator in this case is (I + SX,b )/2, where SX,b := N i ZX (ctX,i ). On $

tails, choose j ← − {0, 1}, independently encrypt mX,j , run DX , and reverse the acceptance rule. The average acceptance operator in this case is (I − Z X )/2, where Z X := (ZX,0 + ZX,1 )/2. Averaging the two cases gives I/2 + (SX,b − Z X )/4 = GX (ctX ). Thus, GX (ctX ) defines an efficient binary test, and E[GX (ctX )] = I/2 + (−1)b HX /2. We may assume that γ ≤ 1/2, because otherwise the strong-CPA threshold exceeds one and the premise is vacuous. Let qX be the number of qubits in the state and initialized workspace of DX . Applying Tropp’s matrix concentration bound to the independent Hermitian operators above gives [Tro12]   h γ i N γ2 b qX +1 b Pr ∥HX,b − (−1) HX ∥ > ≤2 exp − . (26) 100 25000 Choose the following common power-of-two number of challenge pairs: 5 2 N := 2⌈log2(10 (maxX qX +λ)/γ )⌉ .

(27)

The probability that Equation (26) fails for either party is then negligible. The remainder of the proof applies the approximate threshold measurement of Lemma 3, with error η, to the efficient tests with acceptance operators PX , FX , and GX (ctX ). Each test has a reversible implementation using fresh randomness, the public encryption circuit, and the decryptor circuit. First threshold measurement. ρ be the joint decryptor state, define Π+ X := 1[PX ≥  + Let + 1/2 + γ], and set pstr := Tr (ΠB ⊗ ΠC )ρ . Averaging over the classical output of A, we have E[pstr ] ≥ ε. For each party, apply the threshold measurement of Lemma 3 to PX , with completeness threshold 1/2 + γ and soundness threshold 1/2 + 3γ/4. Let APX be the map corresponding to acceptance, 35

let σP := (APB ⊗ APC )(ρ), and let pP := Tr(σP ). Completeness remains valid when the measured register is entangled with the other party; applying it successively to the two parties gives pP ≥ pstr − 2η.

(28)

Set ΠX := 1[PX > 1/2 + 3γ/4], Π := ΠB ⊗ ΠC , and σ P := ΠσP Π. The post-measurement guarantee of Lemma 3 places at most η probability outside each local projector. Therefore, Tr(σ P ) ≥ pP − 2η, √ and the gentle measurement bound from Section 3.9 gives ∥σP − σ P ∥1 ≤ 3 2η. Second threshold measurement. We now pass from states supported where PX > 1/2 + 3γ/4 to states with non-negligible support where HX ≥ γ/2. Let ΩX := 1[HX ≥ γ/2]. By Equation (23), ΠX HX ΠX ⪰ (3γ/4)ΠX . Since ∥HX ∥ ≤ 1/2, we also have ΠX HX ΠX ⪯ (γ/2)ΠX + (1/2 − γ/2)ΠX ΩX ΠX . Setting c := γ/(2(1 − γ)), which is at least γ/2, gives ΠX ΩX ΠX ⪰ cΠX .

(29)

Apply the same threshold measurement to FX = I/2 + HX , now with completeness threshold 1/2 + γ/2 and soundness threshold 1/2 + γ/4. Let AH X be its acceptance map, let σH := H )(σ ), and let p := Tr(σ ). Tensoring Equation (29) gives (Π Ω Π ) ⊗ (Π Ω Π ) ⪰ (AH ⊗ A P H H B B B C C C B C c2 Π, including for entangled inputs. The two completeness guarantees therefore imply pH ≥ Tr[(ΩB ⊗ ΩC )σP ] − 2η ≥ c2 Tr(σ P ) − 2η − ∥σP − σ P ∥1 . Combining this inequality with Equation (28) yields p γ2 pstr − 6η − 3 2η. (30) pH ≥ 4 Define ΘX := 1[HX > γ/4], Θ := ΘB ⊗ ΘC , and σ H := ΘσH Θ. Soundness of the second pair of √ threshold measurements gives Tr(σ H ) ≥ pH − 2η, and Section 3.9 gives ∥σH − σ H ∥1 ≤ 3 2η. Recovering the challenge bit. Condition on the event in which Equation (26) holds. Apply b X,b , κ = γ/4, and ℓ = γ/8. Since ∥A − B∥ ≤ γ/100, any Equation (21) with A = HX , B = (−1)b H state supported where HX > γ/4 has weight at most  2 γ/100 1 = 0.0064 < (31) γ/4 − γ/8 100 b X,b ≤ γ/8. on the subspace where (−1)b H Each party now applies GATIη1/2+γ/16, 1/2−γ/16 GX (ctX ), I − GX (ctX )

(32)

and guesses 0 on acceptance and 1 on rejection. If b = 0, then outside the subspace bounded in Equation (31), we have GX > 1/2 + γ/16, so completeness bounds the rejection probability by the weight of that subspace plus η. If b = 1, then outside that subspace, we have GX < 1/2 − γ/16, so soundness gives the same bound on the acceptance probability; explicitly, 1[GX > b X,1 ≤ γ/8]. These bounds remain valid when the measured state is entangled 1/2 − γ/16] ⪯ 1[−H with an additional register. Hence, on σ H , both guesses are correct with probability at least   2 1− Tr(σ H ) − 2η. (33) 100 Replacing σ H by σH costs at most ∥σH − σ H ∥1 , and averaging over the ciphertext lists incurs only the negligible failure probability from Equation (26). 36

The constructed CORR adversary. The algorithm A chooses the separate mode of Definition 22, repeats each strong-CPA message pair in all N coordinates, and uses the admissible distribution from Definition 21 that produces a common uniform challenge bit bB = bC = b. Before it sends the two registers to the receivers, it performs the four threshold measurements above and gives both parties the four outcomes and the same uniform random bit g. If all four measurements accept, each party applies Equation (32) to its ciphertexts; otherwise, both output g. Let sH be the probability that all four measurements accept and both final guesses are correct. √ The preceding bounds and Equation (33) give sH ≥ (4/5)pH − 4η − 3 2η − negl(λ), after weakening the constant. When at least one threshold measurement rejects, the shared uniform guess is correct with probability 1/2. The total success probability is therefore (1 − pH )/2 + sH , which is at least √ 1/2 + (3/10)pH − 4η − 3 2η − negl(λ). After averaging Equation (30), the CORR advantage is √ at least (3/40)εγ 2 − 6η − 6 2η − negl(λ). By Equation (22), this quantity is at least εγ 2 /20 for all sufficiently large security parameters in the infinite set. This contradicts SDE-CORR security because εγ 2 is inverse polynomial. Remark 2 (A stronger form of strong CPA). The theorem also holds for a stronger test that accepts whenever both local acceptance eigenvalues are inverse-polynomially far from 1/2, irrespective of their signs. More precisely, for X ∈ {B, C}, let HX := PX − I/2. For an inverse polynomial γ, the joint acceptance projector of this test is 1[|HB | ≥ γ] ⊗ 1[|HC | ≥ γ]. Decompose this projector according to the four sign choices (sB , sC ) ∈ {+1, −1}2 , where sX HX ≥ γ. If the stronger test accepts with non-negligible probability, then one of these four choices occurs with non-negligible probability. The reduction applies the corresponding threshold measurements, b X,b . Since sX H b X,b ≈ sends sX to party X, and asks that party to use the sign-corrected operator sX H b (−1) sX HX and sX HX is positive on the accepted state, the same argument with N ciphertexts recovers b. When sX = −1, party X simply reverses its final output. For comparison, let W+ be the acceptance operator for the test that checks whether the two parties’ outputs agree. Then W+ = I/2 + 2HB ⊗ HC . A positive threshold for W+ − I/2 covers the equal-sign cases (+1, +1) and (−1, −1), whereas a two-sided threshold for |W+ − I/2| also covers the two opposite-sign cases. Up to an inverse-polynomial change in the threshold, the latter is equivalent to requiring both |HB | and |HC | to be inverse-polynomially bounded away from zero. Thus, the stronger test combines ordinary strong CPA, the threshold form of CPA+ , and the variants obtained by reversing either party’s output; we do not introduce a separate security definition. Next, we show that the separate mode of CORR-SDE security, used in Theorem 13 is also implied by and hence (by Theorem 13) equivalent to strong CPA security (and equivalently CPA+ security). Theorem 14 (Separate mode is exactly CPA+ ). Let SDE-CORR|IND denote the SDE-CORR game of Definition 22 restricted to adversaries that choose separate mode. Then SDE-CORR|IND security is equivalent to CPA+ security from Definition 18, and hence to strong-CPA security from Definition 19. Proof. The proof of Theorem 13 uses only separate mode and therefore proves that SDE-CORR|IND implies strong CPA. Strong CPA and CPA+ are equivalent by Theorem 11. It remains to prove that CPA+ implies SDE-CORR in separate mode. Fix a separate-mode CORR adversary A = (A, B, C) and condition on the public classical information produced by A before the challenge; the reduction runs A honestly and finally averages over this information. For X ∈ {B, C} and b ∈ {0, 1}, let PX,b be the average acceptance operator when X receives independent encryptions of (mX,1,b , . . . , mX,N,b ) and outputs b. Because the encryptions 37

for Bob and Charlie use independent randomness, the operator for both parties to answer a fixed pair of challenge bits correctly is PB,bB ⊗ PC,bC . Every joint distribution on (bB , bC ) with uniform marginals satisfies Pr[00] = Pr[11] = θ/2 and Pr[01] = Pr[10] = (1 − θ)/2 for some θ ∈ [0, 1], which may depend on the public key. Define
1 PB,0 ⊗ PC,0 + PB,1 ⊗ PC,1 , 2
1 Woff := PB,0 ⊗ PC,1 + PB,1 ⊗ PC,0 . 2

Wdiag :=

The CORR acceptance operator is WIND = θWdiag + (1 − θ)Woff . Now use the same state and receivers in CPA+ , where the challenge bits are independent. The acceptance operator for the CPA+ condition that the two receivers’ correctness bits agree is W+ :=

1 4

X

PB,b ⊗ PC,c + (I − PB,b ) ⊗ (I − PC,c ) .

b,c∈{0,1}

Expanding this expression gives
1 (I − PB,0 ) ⊗ (I − PC,1 ) + (I − PB,1 ) ⊗ (I − PC,0 ) ⪰ 0, 2
1 W+ − Woff = (I − PB,0 ) ⊗ (I − PC,0 ) + (I − PB,1 ) ⊗ (I − PC,1 ) ⪰ 0. 2

W+ − Wdiag =

(34) (35)

Thus, WIND ⪯ W+ . Every successful separate-mode CORR attack therefore yields a successful CPA+ attack with N challenge pairs. We next reduce the latter attack to the usual game with one pair per receiver. For a ciphertext list ct, let ZX (ct) be the difference between the acceptance operators for outputs (j) 0 and 1. For j ∈ {0, . . . , N }, let ZX be its expectation when the first j coordinates encrypt their messages indexed by 1 and all later coordinates encrypt their messages indexed by 0. For j ∈ [N ], (j−1) (j) set ∆X,j := ZX − ZX . The advantage of the N -pair CPA+ attack over 1/2 is exactly i 1 X 1 h (0) (N ) (0) (N ) Tr (ZB − ZB ) ⊗ (ZC − ZC )ρ = Tr[(∆B,j ⊗ ∆C,k )ρ]. 8 8

(36)

j,k∈[N ]

Let T (λ) be a polynomial upper bound on the number N chosen by the fixed adversary. An $

ordinary CPA+ adversary runs A and samples j, k ← − [T ]. If j > N or k > N , it submits arbitrary fixed valid message pairs and has both receivers return fixed answers; over the independent challenge bits, the success probability is exactly 1/2. Otherwise, it submits Bob’s coordinate-j pair and Charlie’s coordinate-k pair. It gives the receivers copies of pk, N , both message lists, the selected indices, and descriptions of the original receiver algorithms. Each receiver places its one challenge ciphertext in the selected coordinate, independently encrypts the message indexed by 1 in each earlier coordinate and the message indexed by 0 in each later coordinate, and then runs the original receiver on the resulting list. Conditioned on valid j, k, the difference between the receiver’s average output operators for challenge bits 0 and 1 is exactly ∆B,j or ∆C,k . By Equation (36), averaging over j, k gives an ordinary CPA+ advantage equal to 1/T 2 times the original N -pair advantage. Thus, a non-negligible N -pair advantage contradicts CPA+ security. It is not known whether CPA+ security implies full SDE-CORR security. By Theorem 14, separate-mode SDE-CORR is already equivalent to CPA+ . Therefore, any separation between full 38

SDE-CORR and CPA+ , or equivalently strong CPA, must use identical mode, in which both parties receive the same ciphertext. Even for N = 1, where identical-mode SDE-CORR is IDEN-CPA, this copied-ciphertext setting is not covered by the implications of Kitagawa and Yamakawa [KY25]. In particular, it is not known whether CPA+ implies IDEN-CPA security. The reverse implication is ruled out by the standard two-key construction of [CGLZR23, Theorem 13]. Theorem 15 (IDEN-CPA does not imply CPA+ ). Let Π be a perfectly correct IDEN-CPA-secure SDE scheme whose message space contains two distinct messages. There is a perfectly correct IDEN-CPA-secure two-key scheme Π2key that is not CPA+ secure. If Π.Enc is classical, then so is Π2key .Enc. In particular, this separation holds under post-quantum-secure iO and post-quantumsecure one-way functions. Proof. The scheme Π2key generates independent key pairs (pkt , sk t ) ← Π.GenKey(1λ ) for t ∈ {0, 1}, $

publishes (pk0 , pk1 ), and uses sk 0 ⊗ sk 1 as its quantum key. To encrypt m, it samples t ← − {0, 1}, computes ct ← Π.Enc(pkt , m), and outputs (t, ct). Decryption reads t and uses the corresponding key. Perfect correctness is immediate. Suppose that an adversary A = (A, B, C) violates IDEN-CPA security of Π2key . We construct $

an adversary against Π. Given (pk⋆ , sk ⋆ ), it samples J ← − {0, 1} and generates an independent key pair. It places the given key pair in position J and the independently generated pair in the other position, and then runs A for Π2key . It forwards the common message pair output by A to the challenger for Π and gives each receiver a classical copy of J. Upon receiving the copied ciphertext ct⋆ , each receiver runs its original circuit on (J, ct⋆ ). The two key pairs are independent and identically distributed, so the ordered public and quantum keys reveal no information about the uniform position J. The simulation is therefore identical to the real IDEN-CPA experiment for Π2key , even if A jointly processes the two component keys. IDEN-CPA security of Π proves that Π2key is also IDEN-CPA secure. To violate CPA+ security, fix distinct messages (µ0 , µ1 ) and use this pair for both receivers. The algorithm A gives sk 0 to Bob and sk 1 to Charlie. Bob decrypts when the first ciphertext component is 0 and otherwise returns a private fair bit; Charlie acts analogously when that component is 1. Each receiver is correct with probability 3/4 and incorrect with probability 1/4, independently of the other receiver. Their correctness bits therefore agree with probability (3/4)2 + (1/4)2 = 5/8, so Π2key is not CPA+ secure. Taking Π to be the SDE-CORR-secure scheme of Theorem 22 gives the final assertion in the plain model under post-quantum iO and post-quantum one-way functions. The preceding CPA+ attack gives sk 0 to Bob and sk 1 to Charlie, so their joint state is a product state. The next lemma shows that an IDEN-CPA attack whose joint output is a classical mixture of product states cannot separate CPA+ from IDEN-CPA. Lemma 5 (Separable IDEN-CPA attacks violate strong CPA). Let SDE be an SDE scheme and let A = (A, B, C) be an adversary in the IDEN-CPA experiment of Definition 17. Let u contain the public key and all classical information output by A before the challenge. For every value u that occurs with nonzero probability, let ρuBC be the corresponding normalized state onP the registers sent to B and C. Suppose that this state is separable for every u, meaning that ρuBC = z pu,z ρu,z ⊗ σu,z for probabilities pu,z and local states ρu,z , σu,z . If, for some ε = ε(λ) ∈ (0, 1/2], h i 1 (37) Pr SDE-IDEN-CPASDE,A (1λ ) = 1 ≥ + ε, 2 then there is an adversary Astr in the strong-CPA experiment of Definition 19 such that h i ε3 Pr SDE-STRONG-CPASDE,Astr (1λ , ε/4) = 1 ≥ . (38) 4 39

Thus, if SDE is strong-CPA secure, every IDEN-CPA adversary of this form has negligible advantage. Proof. The adversary Astr runs A, uses its common message pair for both strong-CPA decryptors, and equips the two output registers with the circuits of B and C. We prove that these decryptors satisfy Equation (38). Claim. Let u be a classical random variable with distribution (qu )u . For every u, let i be drawn from a distribution Du , and let 0 ⪯ Au,i , Bu,i ⪯ I be operators on two registers. P Define Pu := Ei←Du [Au,i ], Qu := EP [B ], and W := E [A ⊗ B ]. Suppose that ρ = u,i u u,i u,i u i←Du i←Du z pu,z ρu,z ⊗ σu,z is separable and u qu Tr(Wu ρu ) ≥ 1/2 + ε. For Πu := 1[Pu ≥ 1/2 + ε/4] and Γu := 1[Qu ≥ 1/2 + ε/4], we have X
ε3 qu Tr (Πu ⊗ Γu )ρu ≥ . (39) 4 u To prove the claim, write τu,z := ρu,z ⊗ σu,z , and define au,z := Tr(Pu ρu,z ), bu,z := Tr(Qu σu,z ), and su,z := Tr(Wu τu,z ). Since su,z = Ei [Tr(Au,i ρu,z ) Tr(Bu,i σu,z )] and both factors lie in [0, 1], we have su,z ≤ min{au,z , bu,z }. Give each pair (u, z) probability qu pu,z , and let G be the set of pairs for which su,z ≥ 1/2 + ε/2. Since 0 ≤ su,z ≤ 1, the premise of the claim implies that G has probability at least ε/(1 − ε). For every (u, z) ∈ G, both au,z and bu,z are at least 1/2 + ε/2. Moreover, Pu ⪯ (1/2 + ε/4)I + (1/2 − ε/4)Πu , and hence Tr(Πu ρu,z ) ≥ ε/(2 − ε). The same argument gives Tr(Γu σu,z ) ≥ ε/(2 − ε). It follows that  2 X
ε ε ε3 qu Tr (Πu ⊗ Γu )ρu ≥ ≥ , (40) 1−ε 2−ε 4 u where the last inequality uses 0 < ε ≤ 1/2. This proves the claim. We apply the claim to the IDEN-CPA attack. Let u contain pk, the common message pair, and all classical information produced before the challenge ciphertext. Conditioned on u, let i = (b, ct), $

where b ← − {0, 1} and ct ← SDE.Enc(pk, mb ). Let Au,i be the P measurement operator for B to output b on input ct, and define Bu,i analogously for C. Then u qu Tr(Wu ρuBC ) is exactly the success probability in Equation (37). The operators Pu and Qu are the two local CPA acceptance operators, so Πu and Γu are exactly the accepting projectors in the strong-CPA experiment with gap ε/4. Thus, Equation (39) proves Equation (38). Lemma 5 rules out every separable IDEN-CPA attack arising from a classical mixture over public indices or challenge bits. Thus, separating CPA+ from IDEN-CPA would require an entangled attack that specifically exploits the fact that both parties receive the same ciphertext. Constructing such an attack remains open. We next compare the two identical-challenge notions. Theorem 16 (Identical CPA implies identical search [AKL23]). For superlogarithmic message length, identical-CPA security implies identical-search security. Proof. Suppose that an identical-search adversary succeeds with probability p. To construct an identical-CPA adversary, first run the search adversary to obtain its two receiver registers and $

circuits. Independently sample m0 , m1 ← − M and submit (m0 , m1 ) as the challenge pair. Each CPA receiver runs the corresponding search receiver and outputs 1 exactly when the recovered message equals m1 . If the challenge bit is 1, both parties are correct with probability p. If it is 0, each CPA receiver first runs its search receiver on the ciphertext and then compares the recovered value 40

with m1 . The recovered value is independent of the fresh uniform message m1 , so a union bound shows that both parties output 0 with probability at least 1 − 2/|M|. The resulting CPA success probability is at least 1/2 + p/2 − 1/|M|. If p ≥ 1/|M| + ε for non-negligible ε, this lower bound is 1/2+ε/2−1/(2|M|). The final term is negligible for superlogarithmic message length, contradicting identical-CPA security. Identical-challenge search and CPA security do not imply their independent-challenge counterparts; the corresponding two-key constructions appear in [CGLZR23, Theorems 12 and 13]. The CPA construction also fails independent-search security: assigning one component key to each receiver allows both to decrypt whenever their independently sampled ciphertext indices identify the assigned keys, an event of constant probability. We omit this additional separation between identical and independent challenges from the figure for readability. Search security does not imply CPA security either. Given a search-secure scheme over M0 , enlarge its message space to {0, 1} × M0 and include the first component in the clear in every ciphertext. Exact recovery still requires recovering the M0 component, and superlogarithmic message length makes the resulting change in the uniform-guessing probability negligible. By contrast, messages that differ only in the first component are perfectly distinguishable. This construction gives the search-to-CPA separations in the figure, including the analogous separations between identical- and independent-challenge notions. It remains to prove the separations with IND-CPA on the left. One scheme suffices: if it is INDCPA secure but not IDEN-SEARCH secure, then the implications above show that it is neither IDEN-CPA nor IND-SEARCH secure. It is also neither CPA+ nor strong-CPA secure, since both imply IND-SEARCH. The next construction, due to Coladangelo, Liu, Liu, and Zhandry, uses quantum states associated with shifted subspaces and a logarithmic-length public index in each ciphertext. The proof must also accommodate the unrelated message pairs allowed for the two receivers in IND-CPA. Theorem 17 (Independent CPA does not imply strong CPA). Assuming post-quantum-secure indistinguishability obfuscation and post-quantum-secure one-way functions, there is a perfectly correct SDE scheme that is SDE-IND-CPA secure but not SDE-STRONG-CPA secure. The same scheme is not SDE-IDEN-SEARCH secure and establishes every displayed separation in Figure 1 whose left-hand notion is SDE-IND-CPA. Proof. Let n = 2λ, let L = ⌈c log λ⌉ for any fixed constant c > 0, set R := 2L , and take M = {0, 1}λ . For a subspace A ≤ Fn2 and shifts s, t ∈ Fn2 , define the coset state 1 X |As,t ⟩ := p (−1)⟨a,t⟩ |a + s⟩ . |A| a∈A For all sufficiently large λ, we have R ≥ 4. For each i ∈ [L], key generation independently samples $

an n/2-dimensional subspace Ai ≤ Fn2 and shifts si , ti ← − Fn2N . It publishes obfuscated programs that ⊥ test membership in Ai + si and Ai + ti , and it sets sk := L i=1 |(Ai )si ,ti ⟩. ⊥, c For a ∈ {0, 1}, define B := A , B := A := s i,0 i i,1 i,0 i , and ci,1 := ti . For a public index i Q r ∈ {0, 1}L , let Br := i Bi,ri , let cr := (c1,r1 , . . . , cL,rL ), and set Sr := Br + cr . The public programs determine membership in Sr . For m ∈ M, define ( m, z ∈ Sr , Pr,m (z) := ⊥, z ∈ / Sr .

41

$

Encryption samples r ← − {0, 1}L and outputs ct = (r, iO(Pr,m )). To decrypt, apply a Hadamard transform to the register containing |(Ai )si ,ti ⟩ exactly when ri = 1, evaluate the obfuscated program reversibly, and undo these operations. The transformed key state is supported on Sr , so correctness is perfect. This is the SDE construction of [CLLZ21], with the program enlarged to output λ bits. We use the following known no-cloning property of coset states. Given the public membership programs and the tensor product of coset states above, no QPT algorithm A that distributes two registers can enable two noncommunicating parties, after descriptions of the Ai are revealed, to output (r, z) and (r′ , z ′ ) satisfying r ̸= r′ , z ∈ Sr , and z ′ ∈ Sr′ .

(41)

The computational statement follows from [CLLZ21, Theorem 4.18]; the information-theoretic claim assumed there was later proved by Culf and Vidick [CV22]. The one-coordinate game in the cited theorem asks one party for a point in AJ + sJ and the other for a point in A⊥ J + tJ . To reduce the statement above for two distinct indices to that game, place its challenge in a uniformly hidden coordinate J and generate every other coordinate honestly. The reduction neither reveals nor uses J while it runs A, performs the threshold measurements, or chooses the two indices. Because the coordinates are independently and identically distributed, conditioned on r ̸= r′ , the probability that rJ ̸= rJ′ is dist(r, r′ )/L ≥ 1/L. After r and r′ have been chosen, but before the two registers are sent, the reduction sends the register whose Jth index bit is 0 to the party required to output a point in AJ + sJ , and it sends the other register to the party required to output a point in A⊥ J + tJ . The reduction loses a factor of at most L. The scheme is not IDEN-SEARCH secure. Fix r⋆ ∈ {0, 1}L , apply Hadamard transforms according to r⋆ , and measure the quantum key to obtain z ⋆ ∈ Sr⋆ . Give both parties a classical copy of z ⋆ and the same uniform value g ∈ M. On a common ciphertext whose first component is r, both parties recover the message if r = r⋆ , and otherwise both output g. Their joint success probability is     1 1 1 1 1 1 + 1− = + 1− , (42) R R |M| |M| R |M| which exceeds the uniform-guessing probability by an inverse polynomial. We now prove IND-CPA security in the generalized game in which the parties may choose unrelated message pairs. Suppose, toward a contradiction, that an adversary A = (A, B, C) succeeds with probability at least 1/2+ε for inverse-polynomial ε. The adversary’s classical message-pair and circuit-output registers remain part of the state, and all operations below are controlled by them; we suppress these registers. For X ∈ {B, C} and r ∈ {0, 1}L , let PX,r be X’s acceptance operator when the first ciphertext component P is fixed to r, the challenge bit is uniform, and encryption is otherwise honest. Set PX := R−1 r∈{0,1}L PX,r . The two parties receive independent challenge bits, public indices, and encryptions, so their joint acceptance operator is PB ⊗ PC . Hence, the state ρ distributed by A satisfies 1 Tr[(PB ⊗ PC )ρ] ≥ + ε. (43) 2 If either party chooses the same message twice, its challenge bit is independent of its view and its acceptance operator is I/2, which makes the joint success probability at most 1/2. Thus, both message pairs are distinct. We first find distinct public indices for which the two receivers have nontrivial prediction probabilities. Every threshold measurement below is the measurement from Lemma 3, whose guarantees remain valid when the measured register is entangled with another register. Choose the inversepolynomial error parameters sufficiently small, as fixed polynomials in ε/L, that all resulting errors 42

are absorbed by the inverse-polynomial lower bounds below. These measurements have reversible implementations using the public encryption and receiver circuits while preserving their randomness and work registers; no cryptographic assumption is used in this step. The algorithm A performs every threshold measurement and chooses both indices before distributing the two registers. It uses only the public key, the message pairs, and the public encryption algorithm. Descriptions of the hidden subspaces are revealed only later, when the two receivers run the point-producing algorithms described below. Apply the threshold measurement to PB ⊗ PC , with completeness threshold 1/2 + 3ε/4 and soundness threshold 1/2 + 2ε/3. The inequality M ⪯ τ I + (1 − τ )1[M ≥ τ ] and Equation (43) imply that this measurement accepts with probability Ω(ε). Apart from the chosen approximation error, every pair of local eigenvalues (λB , λC ) in the accepted state satisfies λB λC >

1 2ε + . 2 3

(44)

√ Both eigenvalues exceed 1/2 + 2ε/3, and at least one exceeds 1/ 2 > 11/16. Choose one party uniformly, denote it by H, and denote the other by W ; the letter H merely identifies the party tested against the higher constant threshold. Apply the threshold measurement to PH with completeness threshold 11/16 and soundness threshold 43/64. With constant probability, H is a party whose eigenvalue exceeds 11/16, and the measurement accepts. Apart from the chosen approximation error, the resulting state is supported on local spectral subspaces on which   43 1 2ε PH ⪰ I and PW ⪰ + I. (45) 64 2 3 Here and below, such inequalities are understood after compression to the stated post-measurement support, and I denotes the identity on that support. $

Sample rW ← − {0, 1}L and apply the threshold measurement to PW,rW with completeness threshold 1/2 + ε/4 and soundness threshold 1/2 + 7ε/32. Averaging the threshold bound over rW and $

using Equation (45) gives acceptance probability Ω(ε). Next sample rH ← − {0, 1}L \ {rW }. On the accepted support, PH ⪰ (43/64)I, and PH,rW ⪯ I; hence X RPH − PH,rW 1 R(43/64) − 1 9 PH,r = ⪰ I ⪰ I, R−1 R−1 R−1 16

(46)

r̸=rW

where the last inequality uses R ≥ 4. Applying the threshold measurement to PH,rH with completeness threshold 17/32 and soundness threshold 67/128 therefore accepts with constant probability. A measurement on one party does not disturb spectral support already established on the other party’s register. Thus, before the two registers are distributed, with probability Ω(ε2 ) we obtain distinct indices rW ̸= rH and a state that, apart from the chosen approximation error, is supported where 1 7ε 1 3 and PH,rH > + . (47) PW,rW > + 2 32 2 128 It remains to show that a decryptor that predicts the challenge bit for a fixed public index r can produce a point in Sr , even for an arbitrary local message pair (µX,0 , µX,1 ). Let ∆X := µX,0 ⊕ µX,1 , $

where a · ∆X denotes ∆X when a = 1 and the all-zero string when a = 0. For q ← − Br⊥ and $

d← − {0, 1}, define ( µX,0 ⊕ (d ⊕ ⟨q, z⟩) · ∆X , z ∈ Sr , QX,r,q,d (z) := ⊥, z∈ / Sr . 43

(48)

For z ∈ Sr = Br + cr , we have ⟨q, z⟩ = ⟨q, cr ⟩. Thus, for b = d ⊕ ⟨q, cr ⟩, the circuits satisfy QX,r,q,d ≡ Pr,µX,b . Moreover, b is uniform because d is uniform. By iO security from Definition 4, replacing the honest fixed-r program by QX,r,q,d changes the prediction probability by at most a negligible amount. The following claim states the required conclusion when the receiver may be entangled with an additional register. Fixed-index recovery claim. Let τ be an efficiently preparable subnormalized state, that is, a positive operator satisfying Tr(τ ) ≤ 1, that contains the honestly generated classical setup, a public index r, a distinct message pair (µ0 , µ1 ), a receiver register, and an arbitrary additional register. Suppose that p := Tr(τ ) is inverse polynomial and that, in the honest fixed-r challenge-bit experiment, the receiver is correct with total probability at least (1/2 + δ)p, where δ is inverse polynomial. After descriptions of the Ai are revealed, there is a local QPT algorithm that leaves the additional register unchanged and outputs z ∈ Sr with probability Ω(pδ 2 ). To prove the claim, an adversary in the iO security experiment of Definition 4 generates the $

honest setup and prepares τ , and thus knows cr for this comparison. It samples q ← − Br⊥ and $

d ← − {0, 1}, sets b = d ⊕ ⟨q, cr ⟩, and gives its iO challenger equally padded descriptions of Pr,µb and Qr,q,d , which compute the same function. It runs the receiver on the returned obfuscation and tests whether the output is b; if preparation of τ fails, it instead outputs a fair bit. With Pr,µb , this is exactly the honest fixed-r test for uniform b. With Qr,q,d , XORing the receiver’s output with d predicts ⟨q, cr ⟩. Post-quantum iO therefore preserves the total prediction advantage on τ up to negl(λ), or up to negl(λ)/p after conditioning on successful preparation of τ . The argument works directly with τ ; it neither prepares the normalized state nor requires inverse-polynomial probability for each individual value of r. After the Ai are revealed, let Gr be a full-rank matrix whose rows span Br⊥ , and write q = GT r y. The predictor now guesses ⟨q, cr ⟩ = ⟨y, Gr cr ⟩. The quantum Goldreich–Levin lemma [CLLZ21, Lemma B.12] allows the predictor to hold an arbitrary quantum register and recovers Gr cr with probability Ω(δ 2 ), conditioned on successful preparation of τ . More precisely, let ΓQ be twice the prediction advantage when using Q, weighted by the trace p of τ . Then iO security and the averaging identity in the cited lemma give ΓQ ≥ 2δp − negl(λ), and Cauchy–Schwarz gives Pr[recover] ≥ Γ2Q /p = Ω(pδ 2 ). These bounds average over the honest setup and the public index. Solving Gr z = Gr cr yields z ∈ Br + cr = Sr . The algorithm producing z computes q, the program in Equation (48), and the classical obfuscator reversibly, keeping every random coin in a work register. The iO comparison samples q classically and never invokes iO on a superposition of circuits. The prediction-to-recovery guarantee of the cited Goldreich–Levin lemma remains valid when the receiver register is entangled with the additional register. This proves the claim. Apply the claim first to W , treating H’s register as the additional register that must remain unchanged. The first inequality in Equation (47) gives conditional probability Ω(ε2 ) of producing a valid point. Verify the output publicly and condition on successful verification, thereby obtaining a subnormalized state. Because this operation acts only on W , the second spectral-support condition in Equation (47) remains valid up to the chosen measurement error; see [CLLZ21, Claim 6.18]. The subnormalized state still has inverse-polynomial trace, so applying the claim to H gives constant conditional probability of producing a valid point for rH . The two local algorithms may run concurrently; we describe them sequentially only to analyze their joint success. Including the Ω(ε2 ) probability of reaching the state in Equation (47), the algorithms produce valid points for the distinct indices rW and rH with probability Ω(ε4 ) after accounting for those errors. The additional 1/L loss in the one-coordinate reduction is inverse polynomial, contradicting Equation (41). Thus, the scheme is IND-CPA secure. 44

Together with Equation (42), this result separates IND-CPA from IDEN-SEARCH. Since IDENCPA implies IDEN-SEARCH and IND-SEARCH implies IDEN-SEARCH, it also gives the corresponding two separations. Finally, if the scheme were strong-CPA secure, then Theorem 11 would imply CPA+ security, then IND-SEARCH security, and finally IDEN-SEARCH security, contradicting Equation (42). Hence, the scheme is not strong-CPA secure and, by the same equivalence, is not CPA+ secure. 4.3.1

Summary of the Main Relations

For convenience, we summarize the main relations established above. As in Section 4.3, every statement involving search security assumes superlogarithmic message length. 1. SDE-CORR security implies strong-CPA security (and hence CPA+ security by [KY25]) by Theorem 13, and it directly implies IND-CPA and IDEN-CPA security by Lemma 4. 2. The restriction of SDE-CORR to separate mode is equivalent to CPA+ security and hence to strong-CPA security, even with polynomially many challenge-message pairs and every admissible challenge sampler; see Theorem 14. 3. Strong-CPA security, or equivalently CPA+ security, implies IND-CPA and IND-SEARCH security, while IND-SEARCH and strong-search security are equivalent and imply IDENSEARCH security; see Theorem 11. 4. Strong-CPA security strictly implies strong-search security under the assumptions stated in Theorem 12. Moreover, IDEN-CPA security implies IDEN-SEARCH security by Theorem 16. 5. IDEN-CPA security does not imply CPA+ security by Theorem 15. Assuming post-quantumsecure iO and post-quantum-secure one-way functions, IND-CPA security does not imply IDEN-CPA, IND-SEARCH, IDEN-SEARCH, CPA+ , or strong-CPA security; all these separations are witnessed by the scheme in Theorem 17. 6. IDEN-SEARCH security does not imply IND-SEARCH security, and IDEN-CPA security implies neither IND-CPA nor IND-SEARCH security [CGLZR23, Theorems 12 and 13]. Moreover, placing one component of every message in the clear shows that IND-SEARCH implies neither IND-CPA nor IDEN-CPA, and that IDEN-SEARCH implies neither IDEN-CPA nor IND-CPA.

45

5

Unclonable Puncturable Obfuscation Security Definitions and Copy-Protection of General Functionalities

In this section, we present security definitions for unclonable puncturable obfuscation and copyprotection of general functionalities.

5.1

Unclonable Puncturable Obfuscation definitions

First, we recall the syntax and correctness of UPO from [AB24, ABH+ 26], then in Section 5.1.1 we recall the prior security definitions. Then, in Section 5.1.2 we present our new definition and show that our new definition implies all prior UPO security notions considered in previous works, except UPO plus. Let C = {Cλ }λ∈N be a keyed circuit class, where Cλ = {Ck : Xλ → Yλ }k∈Kλ , Xλ := {0, 1}ℓin (λ) , and Yλ := {0, 1}ℓout (λ) . Definition 23 (Unclonable puncturable obfuscation). A UPO scheme Π = (Obf, Eval) for C consists of a pair of efficient algorithms as follows. 1. ρk ← Obf(1λ , Ck ) : is a QPT algorithm that takes as input a circuit Ck ∈ Cλ and outputs a quantum obfuscation ρk . 2. (ρ′k , y) ← Eval(ρk , x) : is a QPT algorithm that takes as input a quantum obfuscation ρk and an input x ∈ Xλ , and outputs an updated quantum obfuscation ρ′k and y ∈ Yλ . Correctness We require that there exists a negligible function negl(·) such that, for every λ ∈ N, every k ∈ Kλ , and every x ∈ Xλ , i h (49) Pr y = Ck (x) | ρk ← Obf(1λ , Ck ), (ρ′k , y) ← Eval(ρk , x) ≥ 1 − negl(λ). As in [AB24, Remark 8], the almost-as-good-as-new lemma and a quantum union bound give polynomial reusability. We say that the scheme is perfectly correct when the probability above is one. Throughout this section, whenever a UPO security experiment obfuscates a circuit produced by one of its specified puncturing, programming, or compilation algorithms, the UPO scheme and its correctness requirement are understood to apply to that circuit as well. 5.1.1

Prior Definitions:Generalized UPO Security

We next recall generalized puncturing from [AB24, ABH+ 26]. A keyed circuit class C is generalized puncturable if there exists a deterministic PPT algorithm GenPuncture with the following syntax. Definition 24 (Generalized puncturing). G⋆k,xB ,xC ,µB ,µC ← GenPuncture(k, xB , xC , µB , µC ) : takes as input a key k ∈ Kλ , points xB , xC ∈ Xλ , and circuits µB , µC : Xλ → Yλ , and outputs a circuit G⋆k,xB ,xC ,µB ,µC satisfying   µB (x), ⋆ Gk,xB ,xC ,µB ,µC (x) := µC (x),   Ck (x), All compared circuits are padded to the same size.

46

x = xB , x = xC and xC ̸= xB , otherwise.

(50)

For any distribution DX over Xλ × Xλ and any QPT adversarial triplet AUPO = (A, B, C), consider the following experiment. GenUPOΠ,AUPO ,DX ,C (1λ ): 1. A(1λ ) sends (k, µB , µC ) to Ch, where k ∈ Kλ and µB , µC : Xλ → Yλ . $

2. Ch samples (xB , xC ) ← DX (1λ ) and b ← − {0, 1}, and computes G⋆ ← GenPuncture(k, xB , xC , µB , µC ). 3. Ch generates ρb ← Obf(1λ , Ck ) if b = 0, and ρb ← Obf(1λ , G⋆ ) if b = 1, and sends ρb to A. 4. A outputs a joint state σR1 ,R2 and sends register R1 to B and register R2 to C. 5. After the split, Ch sends xB to B and xC to C. 6. B and C output bbB , bbC . 7. The output of the experiment is 1 if bbB = bbC = b. Definition 25 (DX -generalized UPO security). A UPO scheme Π satisfies DX -generalized UPO security with respect to C if, for every QPT adversarial triplet AUPO = (A, B, C), there exists a negligible function negl(·) such that h i 1 Pr GenUPOΠ,AUPO ,DX ,C (1λ ) = 1 ≤ + negl(λ). 2

(51)

We use the following standard instantiations of the challenge distribution. Remark 3. For a distribution D over Xλ , let D2 denote the product distribution obtained by sampling xB , xC ← D independently. Let IDD denote the diagonal distribution obtained by sampling x ← D and outputting (x, x). Let U denote the uniform distribution on Xλ2 . In particular, IDU := $

IDU denotes the identical-uniform distribution, which samples x ← − Xλ and outputs (x, x). Thus U-generalized UPO is the independent-uniform or product-challenge notion, while IDD -generalized UPO is the diagonal notion and IDU -generalized UPO is the identical-uniform notion. 5.1.2

Correlated-Challenge Security

We generalize the prior definition of UPO in three ways: first, we allow the challenge bits for B and C to be arbitrarily correlated; next, we allow both the challenge points and the two puncturing bits to be sampled jointly, thus allowing them to be correlated; finally, we allow the sampler to output classical auxiliary information zaux that is given to A before she chooses the circuit and classical auxiliary information wB , wC that is given to B, C, respectively, after the split7 . We require the challenge bits to have uniform marginals conditioned on all the auxiliary information and the challenge points, and require each challenge point to have high average conditional min-entropy, as defined in Definition 6, conditioned on the pre-split auxiliary information.8 7

We note that auxiliary information leakage is a natural generalization which can become crucial for some of the applications of UPO (in fact, this generalization is crucial for the application to copy protection for compute-andcompare functions, see Theorem 26). 8 Arbitrary correlation without these restrictions is not tolerable, since the auxiliary information or the challenge points may trivially reveal a challenge bit.

47

Definition 26 (Correlated High min-entropy UPO sampler). Let κ := κ(λ) = λc for some constant c > 0. A correlated UPO sampler with κ-entropic marginals for a keyed-circuit class C = {Cλ }λ∈N with input space X is a QPT algorithm Samp that, on input 1λ , outputs (zaux , xB , xC , bB , bC , wB , wC ) ← Samp(1λ ), where zaux ∈ Zλaux is a polynomial-length classical auxiliary string, xB , xC ∈ Xλ and bB , bC ∈ {0, 1}, and wB , wC are polynomial-length classical auxiliary strings, such that 1. For every (z̄aux , x̄B , x̄C , w̄B , w̄C ) in the support of (zaux , xB , xC , wB , wC ), every X ∈ {B, C}, and every a ∈ {0, 1},   1 aux , xB =x̄B , xC =x̄C , Pr bX = a | zaux =z̄ = . (52) wB =w̄B , wC =w̄C 2 e ∞ (xX | zaux ) ≥ κ(λ). 2. For every X ∈ {B, C}, H We identify a sampler with no explicit auxiliary output with the special case zaux := wB := wC := ⊥. For k, xB , xC , bB , bC , µB , µC as above, define   µB (x), ac Gk,xB ,xC ,bB ,bC ,µB ,µC (x) := µC (x),   Ck (x),

x = xB , bB = 1, x = xC , xC ̸= xB , bC = 1, otherwise.

(53)

Equivalently, Gac ← Correlated-Puncture(k, xB , xC , bB , bC , µB , µC ). If xB = xC and bB ̸= bC , we follow the convention used in [ABH+ 26] that B’s challenge bit takes priority, i.e., the common point xB = xC is punctured using µB if bB = 1, and is left unpunctured if bB = 0, oblivious of C’s challenge bit bC . Definition 27 (Correlated UPO security). For any QPT adversarial triplet AUPO = (A, B, C) against a UPO scheme Π = (Obf, Eval) and any correlated UPO sampler Samp with κ-entropic marginals, write A = (A0 , A1 ), where A0 may retain an arbitrary quantum state for A1 , and consider the following experiment. Correlated-UPOΠ,AUPO ,Samp,C (1λ ): 1. Ch samples (zaux , xB , xC , bB , bC , wB , wC ) ← Samp(1λ ) and sends zaux to A0 . 2. A0 (1λ , zaux ) sends (k, µB , µC ) to Ch, where k ∈ Kλ and µB , µC : Xλ → Yλ , while retaining an arbitrary quantum state. 3. Ch computes Gac ← Correlated-Puncture(k, xB , xC , bB , bC , µB , µC ), generates ρ ← Obf(1λ , Gac ), and sends ρ to A1 . 4. A1 outputs a joint state σR1 ,R2 and sends register R1 to B and register R2 to C. 5. After the split, Ch sends (xB , wB ) to B and (xC , wC ) to C. 6. B and C output bbB , bbC . 7. The output of the experiment is 1 if bbB = bB and bbC = bC .

48

A UPO scheme Π satisfies κ-entropic Correlated-UPO security with respect to C if, for every correlated UPO sampler Samp with κ-entropic marginals for C, and every QPT adversarial triplet AUPO , there exists a negligible function negl(·) such that h i 1 Pr Correlated-UPOΠ,AUPO ,Samp,C (1λ ) = 1 ≤ + negl(λ). (54) 2 Definition 28 (iO-security for UPO, adapted from [ABH+ 26, Definition 3.15]). A UPO scheme Π = (Obf, Eval) for a circuit class C satisfies iO-security if, for every QPT adversarial pair AiO = (AiO,0 , AiO,1 ), where AiO,0 (1λ ) outputs same-size circuits C0 , C1 ∈ Cλ and a quantum state σaux such that C0 (x) = C1 (x) for every input x, there exists a negligible function negl(·) such that   (C0 , C1 , σaux ) ← AiO,0 (1λ ),   1 $ Pr bb = b : b ← (55) − {0, 1}, ρb ← Obf(1λ , Cb ),  ≤ + negl(λ). 2 bb ← AiO,1 (σaux , ρb ) Next, we show the following composition theorem for correlated security of UPO using the same argument as in the proof of [AB24, Theorem 12]. Theorem 18 (Adding iO security, adapted from [AB24, Theorem 12],[ABH+ 26, Lemma 3.16]). Let Circℓin ,ℓout denote the full class of polynomial-size circuits from {0, 1}ℓin (λ) to {0, 1}ℓout (λ) , regarded as a keyed circuit class whose keys are circuit descriptions. If there exist a post-quantum secure indistinguishability obfuscation scheme and a UPO scheme for Circℓin ,ℓout satisfying κ-entropic correlated UPO security, then there exists a UPO scheme for this circuit class satisfying both κ-entropic correlated UPO security and iO-security. Consequently, the same holds for every polynomial-size keyed subclass C ⊆ Circℓin ,ℓout . Proof. This follows from the add-iO transformation of [ABH+ 26, Lemma 3.16], using the composition theorem of [AB24, Theorem 12]; the same reduction applies to the correlated experiment by using the sampler’s entire output tuple, including the pre-split and post-split auxiliary strings, unchanged. Lemma 6 (Relation to prior UPO notions). For any κ := κ(λ) = λc for some constant c > 0, κ-entropic Correlated-UPO security implies DX -generalized UPO security for every QPT-samplable distribution DX over challenge pairs, that induces marginal challenge distribution on each of the two challenges with min-entropy at least κ(λ). In particular, for every QPT-samplable distribution e ∞ (D) ≥ κ(λ) (such as the uniform random distribution), it implies D2 -generalized D satisfying H UPO security and IDD -generalized UPO security.9 . Proof. Given DX , define a sampler that sets zaux := wB := wC := ⊥, samples (xB , xC ) ← DX , $

samples b ← − {0, 1}, and sets bB = bC := b. By the hypothesis of the lemma, DX , the resulting sampler has κ-entropic marginals on the individual challenges. Moreover, clearly, this sampler satisfies Equation (52). Since every nonempty sampler output is hidden from A0 before it sends (k, µB , µC ), sampling the tuple before this message does not change the joint distribution. If b = 0, the punctured circuit is Ck , while if b = 1, it is exactly the generalized punctured circuit from Equation (50), including the Bob-priority convention used in the generalized UPO security definition when the points coincide. Hence the two security experiments are identically distributed. Taking DX = D2 , DX = IDD , DX = U, or DX = IDU gives the stated instantiations. Vanilla UPO security follows since it is implied by generalized UPO security. 9

The only known UPO security notion that is not covered by correlated UPO security is the UPO+ notion defined in [ABH+ 26], which can be seen as a completely different flavor of security notion. In particular, UPO+ has a different winning condition and is not an instance of the correlated-UPO experiment.

49

5.2

Copy-Protection Security Definitions

We first recall the standard copy-protection security notions, including the identical-challenge pointfunction experiment of [AB24]. We then define the stronger oracular variants of [ABH+ 26]. Except in the point-function, k-point-function, and compute-and-compare experiments stated separately below, the circuit and the challenge sampler are independent, while the two challenge points themselves may be arbitrarily correlated. Let Circ = {Circλ }λ∈N be a class of polynomial-size circuits C : Xλ → Yλ , where Xλ = {0, 1}ℓin (λ) and Yλ = {0, 1}ℓout (λ) . Let DCirc be a QPT-samplable distribution over Circλ . Definition 29 (Copy protection, adapted from [AB24, Appendix A.1] and [ABH+ 26, Definition 3.1]). A copy-protection scheme CP = (CopyProtect, Eval) for Circ consists of a pair of efficient algorithms as follows. 1. ρC ← CopyProtect(1λ , C) : is a QPT algorithm that takes as input a circuit C ∈ Circλ and outputs a quantum program ρC . 2. y ← Eval(ρC , x) : is a QPT algorithm that takes as input a quantum program ρC and an input x ∈ Xλ , and outputs y ∈ Yλ . Correctness. We require that there exists a negligible function negl(·) such that, for every λ ∈ N, every C ∈ Circλ , and every x ∈ Xλ , h i Pr Eval(ρC , x) = C(x) : ρC ← CopyProtect(1λ , C) ≥ 1 − negl(λ). (56) When polynomial reusability is required, the evaluation algorithm is understood to return its residual program state; the concrete scheme used below restores that state perfectly. Definition 30 (Correlated copy-protection challenge sampler). A correlated copy-protection challenge sampler SampCP is a QPT algorithm that, on input 1λ , outputs (xB , xC ) ← SampCP (1λ ), where xB , xC ∈ Xλ . The two challenge points may be arbitrarily correlated. We say that SampCP e ∞ (xX ) ≥ κ(λ) for every X ∈ {B, C}. has κ-entropic marginals if H We use the notion of trivial adversaries from previous works [ABH+ 26, Definition 3.1]. The first-stage adversary Atriv B sends the entire protected program ρC to B and the fixed dummy state |⊥⟩⟨⊥| to C. The first-stage adversary Atriv C is defined symmetrically. Define   triv Triv := (Atriv (57) B , B, C) : B, C are QPT ∪ (AC , B, C) : B, C are QPT . Thus, the recipient not receiving the protected program receives no auxiliary state prepared by A. For any QPT adversarial triplet ACP = (A, B, C), consider the following experiment. UnpCPCP,ACP ,DCirc ,SampCP (1λ ): 1. Ch samples C ← DCirc (1λ ) and ρC ← CopyProtect(1λ , C), and gives ρC to A. 2. A outputs a joint state σR1 ,R2 and sends register R1 to B and register R2 to C. 3. After the split, Ch samples (xB , xC ) ← SampCP (1λ ), gives xB to B, and gives xC to C. 4. B and C output ybB , ybC . 5. The output of the experiment is 1 if ybB = C(xB ) and ybC = C(xC ). 50

Definition 31 (Unpredictability-style copy-protection security with correlated challenges, adapted from [AB24, Appendix A.1] and [ABH+ 26, Definition 3.1]). A copy-protection scheme CP satisfies unpredictability-style copy-protection security with respect to (DCirc , SampCP ) if, for every QPT adversarial triplet ACP , there exist a trivial adversary Atriv ∈ Triv and a negligible function negl(·) such that h i h i Pr UnpCPCP,ACP ,DCirc ,SampCP (1λ ) = 1 ≤ Pr UnpCPCP,Atriv ,DCirc ,SampCP (1λ ) = 1 + negl(λ). (58) Definition 32 (Identical-challenge unpredictability-style copy protection for point functions, adapted from [AB24, Theorem 89 and Corollary 90]). Let Xλ = {0, 1}ℓin (λ) , let D = {Dλ }λ∈N be a QPTsamplable distribution over Xλ , and for every y ∈ Xλ define Py (x) := [x = y]. For a copy-protection scheme CP for point functions and any QPT adversarial triplet APF = (A, B, C), consider the following experiment. PFCPCP,APF ,D (1λ ): 1. Ch samples y ← Dλ and ρy ← CopyProtect(1λ , Py ), and sends ρy to A. 2. A outputs a joint state σR1 ,R2 and sends register R1 to B and register R2 to C. $

3. After the split, Ch samples b ← − {0, 1}. If b = 0, it samples an independent x ← Dλ ; if b = 1, it sets x := y. It sends the same x to both B and C. 4. B and C output vbB , vbC ∈ {0, 1}. 5. The output of the experiment is 1 if vbB = vbC = Py (x). A copy-protection scheme for point functions satisfies identical-challenge point-function security with respect to D if, for every QPT adversarial triplet APF , there exist a trivial adversary Atriv ∈ Triv and a negligible function negl(·) such that h i Pr PFCPCP,APF ,D (1λ ) = 1 ≤ pPF,D (59) triv (λ) + negl(λ), where pPF,D triv (λ) :=

sup Atriv ∈Triv

h i Pr PFCPCP,Atriv ,D (1λ ) = 1 .

(60)

The uniform choice of Dλ recovers the experiment of [AB24, Theorem 89 and Corollary 90]. We note that, assuming the point distribution has sufficiently high min-entropy, the trivial success probability is negligibly close to 1/2. P Lemma 7 (Trivial success in the point-function experiment). Let cp(Dλ ) := x Pr[Dλ = x]2 . For the experiment in Definition 32, pPF,D triv (λ) =

1 1 1 1 e + cp(Dλ ) ≤ + 2−H∞ (Dλ ) . 2 2 2 2

(61)

e ∞ (Dλ ) ≥ λc for some constant c > 0, then Consequently, if H pPF,D triv (λ) =

1 + negl′ (λ). 2

51

(62)

Proof. Both events induce the marginal distribution x ← Dλ . For every x in its support, Pr[Py (x) = 1 | x] =

1 1 + Pr[Dλ = x] . 2

(63)

Under a trivial strategy, the recipient receiving the dummy register has no information about y beyond x, and hence cannot do better than always outputting 1. This strategy is attained when both recipients output 1 and has average success 1/2 + cp(Dλ )/2. Finally, cp(Dλ ) ≤ maxx Pr[Dλ = x] = e 2−H∞ (Dλ ) . Remark 4 (Copy protection definition for k-point functions). The copy protection definition for point functions, as outlined above, also extends to the fixed-k-point functions considered in [AB24, (k) Theorem 85 and Corollary 90]. Let D(k) = {Dλ }λ∈N be any QPT-samplable distribution over the e ∞ (D(k) ) ≥ λc for some constant c > 0. For a set k = k(λ) element subsets of Xλ such that H λ S ⊆ Xλ of size k, define PS (x) := [x ∈ S], and let Dλpt denote the distribution obtained by sampling $ (k) e ∞ (Dpt ) ≥ λc′ for some constant c′ > 0. The identicaland then x ← S ← D − S, such that H λ

λ $ (k) challenge experiment samples S ← Dλ and protects PS . After the split, it samples b ← − {0, 1}. If $ $ (k) b = 0, it samples an independent S ′ ← Dλ and then x ← − S ′ ; if b = 1, it samples x ← − S. In either

case, it gives the same x to both recipients. Security uses the same trivial-adversary comparison as above. For qλ (x) := PrS←D(k) [x ∈ S], the trivial success probability is λ

PF(k),D(k)

ptriv

(λ) =

1 1 X 1 k(λ) + qλ (x)2 = + cp(Dλpt ), 2 2k(λ) 2 2

(64)

x∈Xλ

which is 1/2 + negl(λ) whenever k is polynomially bounded. Definition 33 (Identical-challenge copy protection for compute-and-compare functions, adapted from [CMP24]). Following [CMP24, Construction 4 and Theorem 7], the definition above extends to compute-and-compare functions CCf,y (x) := [f (x) = y], where f : Xλ → Zλ , Zλ = {0, 1}ℓcc (λ) , and y ∈ Zλ . Let Samp be a QPT algorithm that samples (f, y) ← Samp(1λ ), interpreted as sampling CCf,y , and let (F, Y ) denote its output distribution. We e ∞ (Y | F ) ≥ λc for some constant c > 0. require H For every f in the support of F and every z in the support of the conditional distribution of Y given F = f , fix a distribution Qf,z supported on f −1 (z). The identical-challenge copy-protection experiment for compute-and-compare functions samples (f, y) ← Samp(1λ ) and protects CCf,y as $

(f, ρy ), where ρy is a copy protection of Py . After the split, it samples b ← − {0, 1}. If b = 0, it samples a fresh z independently according to the conditional distribution of Y given F = f ; if b = 1, it sets z := y. It then samples x ← Qf,z and gives the same x to both recipients. The same family of distributions {Qf,z }f,z is used for both values of b. We say that the scheme satisfies identicalchallenge compute-and-compare copy-protection security if, for every QPT adversarial triplet, there exists a negligible function negl such that its success probability in the experiment above is at most pCC,Samp (λ) + negl(λ), triv

52

where pCC,Samp (λ) denotes the supremum success probability in this experiment over the trivial triv adversaries in Triv, as defined in Definition 32. We say that this identical-challenge experiment is efficiently realizable if there exist QPT procedures that: 1. on input (1λ , f ), sample a fresh z according to the conditional distribution of Y given F = f ; and 2. on input (1λ , f, z), sample x ← Qf,z . Next, we recall the pseudorandomness-style copy protection notion from previous works. Definition 34 (Correlated pseudorandomness-style copy-protection challenge sampler). A correlated pseudorandomness-style copy-protection challenge sampler SampPRCP with κ-entropic marginals is a QPT algorithm that, on input 1λ , outputs (xB , xC , bB , bC ) ← SampPRCP (1λ ), where xB , xC ∈ Xλ and bB , bC ∈ {0, 1}, such that, for every (x̄B , x̄C ) in the support of (xB , xC ) and every X ∈ {B, C}, 1 Pr[bX = 0 | xB = x̄B , xC = x̄C ] = Pr[bX = 1 | xB = x̄B , xC = x̄C ] = , 2

(65)

e ∞ (xX ) ≥ κ(λ) for every X ∈ {B, C}. and H $

$

We write Samppr − Xλ and b ← − {0, 1}, and outputs (xB , xC , bB , bC ) := IDU for the sampler that samples x ← (x, x, b, b). $

Given C, a sampled tuple (xB , xC , bB , bC ), and independent yB , yC ← − Yλ , define  (  xC = xB , zB , C(xB ), bB = 0, zB := zC := C(xC ), xC ̸= xB and bC = 0,  yB , bB = 1,  yC , xC ̸= xB and bC = 1.

(66)

Thus, just as in the correlated UPO security case (see Equation (53)), a potential tie (i.e., xB = xC but bB ̸= bC ) is resolved using B’s challenge bit. For any QPT adversarial triplet APRCP = (A, B, C), consider the following experiment. PRCPCP,APRCP ,DCirc ,SampPRCP (1λ ): 1. Ch samples C ← DCirc (1λ ) and ρC ← CopyProtect(1λ , C), and gives ρC to A. 2. A outputs a joint state σR1 ,R2 and sends register R1 to B and register R2 to C. $

3. After the split, Ch samples (xB , xC , bB , bC ) ← SampPRCP (1λ ) and independent yB , yC ← − Yλ . It defines zB , zC according to Equation (66). 4. Ch gives (xB , zB ) to B and (xC , zC ) to C. 5. B and C output bbB , bbC . 6. The output of the experiment is 1 if bbB = bB and bbC = bC . Definition 35 (Pseudorandomness-style copy-protection security with correlated challenges, adapted from [ABH+ 26, Definition 3.3]). A copy-protection scheme CP satisfies κ-entropic pseudorandomnessstyle copy-protection security with respect to (DCirc , SampPRCP ) if, for every QPT adversarial triplet APRCP , there exists a negligible function negl(·) such that h i 1 (67) Pr PRCPCP,APRCP ,DCirc ,SampPRCP (1λ ) = 1 ≤ + negl(λ). 2 53

5.2.1

Oracular security notions

Next we recall the oracular versions of the copy-protection security definitions defined in [ABH+ 26]. The experiments below are identical to the experiments above, except that A receives oracle access to the sampled circuit before the split and each recipient receives oracle access punctured at that recipient’s challenge point after the split. For every circuit C : Xλ → Yλ and x⋆ ∈ Xλ , define ( ⊥, x = x⋆ , ⋆ C \x (x) := (68) C(x), x ̸= x⋆ . All oracle accesses below are quantum superposition accesses. For any QPT adversarial triplet ACP = (A, B, C), consider the following experiment. OraUnpCPCP,ACP ,DCirc ,SampCP (1λ ): 1. Ch samples C ← DCirc (1λ ) and ρC ← CopyProtect(1λ , C), and gives ρC and oracle access to C to A. 2. AC outputs a joint state σR1 ,R2 and sends register R1 to B and register R2 to C. 3. After the split, Ch samples (xB , xC ) ← SampCP (1λ ), gives xB and oracle access to C \xB to B, and gives xC and oracle access to C \xC to C. 4. B C

\xB

and C C

\xC

output ybB , ybC .

5. The output of the experiment is 1 if ybB = C(xB ) and ybC = C(xC ). The notion of trivial strategies in this experiment is defined similarly to the case of no oracle access. For X ∈ {B, C}, rhe first-stage adversary Atriv X with access to the oracle sends the entire protected program ρC to X and the fixed dummy state |⊥⟩⟨⊥| to the other party, and, we define   triv Triv := (Atriv (69) B , B, C) : B, C are QPT ∪ (AC , B, C) : B, C are QPT . Definition 36 (Oracular unpredictability-style copy-protection security with correlated challenges, adapted from [ABH+ 26, Definition 3.1]). A copy-protection scheme CP satisfies oracular unpredictabilitystyle copy-protection security with respect to (DCirc , SampCP ) if, for every QPT adversarial triplet ACP , there exist a trivial adversary Atriv ∈ Triv (defined in Equation (69)) and a negligible function negl(·) such that h i h i Pr OraUnpCPCP,ACP ,DCirc ,SampCP (1λ ) = 1 ≤ Pr OraUnpCPCP,Atriv ,DCirc ,SampCP (1λ ) = 1 + negl(λ). (70) For any QPT adversarial triplet APRCP = (A, B, C), consider the following experiment. OraPRCPCP,APRCP ,DCirc ,SampPRCP (1λ ): 1. Ch samples C ← DCirc (1λ ) and ρC ← CopyProtect(1λ , C), and gives ρC and oracle access to C to A. 2. AC outputs a joint state σR1 ,R2 and sends register R1 to B and register R2 to C. $

3. After the split, Ch samples (xB , xC , bB , bC ) ← SampPRCP (1λ ) and independent yB , yC ← − Yλ . It defines zB , zC according to Equation (66). 54

4. Ch gives (xB , zB ) and oracle access to C \xB to B, and gives (xC , zC ) and oracle access to C \xC to C. 5. B C

\xB

and C C

\xC

output bbB , bbC .

6. The output of the experiment is 1 if bbB = bB and bbC = bC . Definition 37 (Oracular pseudorandomness-style copy-protection security with correlated challenges, adapted from [ABH+ 26, Definition 3.3]). A copy-protection scheme CP satisfies κ-entropic oracular pseudorandomness-style copy-protection security with respect to (DCirc , SampPRCP ) if, for every QPT adversarial triplet APRCP , there exists a negligible function negl(·) such that h i 1 Pr OraPRCPCP,APRCP ,DCirc ,SampPRCP (1λ ) = 1 ≤ + negl(λ). 2

55

(71)

Part II

Quantum Information Tools 6

A New Decisional Coset Monogamy-of-Entanglement Game

In this section, we state and prove a new information theoretic decisional Coset Monogamy-of-Entanglement game, that implies (with other cryptographic assumptions) all the feasibility results in this article, i.e., all the security proofs finally reduce to this Monogamy-of-Entanglement game. We note that all adversaries in this section are computationally unbounded, and can be modeled as arbitrary (finite-dimensional) quantum channels, and all the results hold unconditionally, without any computational assumptions. Definition 38 (Decisional-Coset-MOE). Let n := n(λ) be a polynomial function in λ. For any triplet of adversaries Amoe = (A, B, C), consider the following experiment between a challenger Ch and Amoe . Decisional-Coset-MOEAmoe (1λ ): $

1. Ch samples a uniformly random n-dimensional subspace A ≤PF2n − F2n 2 and samples s, t ← 2 ⟨a,t⟩ |a + s⟩. independently, and prepares and sends the state |As,t ⟩ = √1 (−1) a∈A |A|

2. A outputs a joint state σR1 ,R2 and sends registers R1 to B and R2 to C. $

$

3. After the split, Ch samples u ← − A \ {0} and v ← − A⊥ \ {0} and sends the pair (u, v) to B and C. 4. B and C output bB , bC . 5. The output of the experiment 1 if bB = bC = ⟨u, t⟩ + ⟨v, s⟩. It is easy to see that the Decisional-Coset-MOE experiment can be seen as an unclonableindistinguishable experiment (see Definition 10) as follows. Lemma 8. The Decisional-Coset-MOE experiment is equivalent to the unclonable-indistinguishable experiment (see Definition 10) for the following unclonable encryption scheme. Coset-UE: 1. GenKey(1λ ): Sample u, v ← F2n 2 \ {0} subject to ⟨u, v⟩ = 0. Output k = (u, v). ⊥ 2. Enc(k, m): Sample a uniformly random subspace A ≤ F2n 2 subject to u ∈ A and v ∈ A where $

k = (u, v). Sample s, t ← − F2n 2 subject to m = ⟨u, t⟩ + ⟨v, s⟩. Prepare and output the state ρct = |As,t ⟩. 3. Dec(k, ρct ): Interpret k := (u, v), compute m1 = ⟨v, s⟩, by computing the inner product of v coherently with all strings in superposition in the state |As,t ⟩ and then measure the outcome, which does not collapse the state (since ⟨a + s, v = ⟨s, v⟩ for every a ∈ A). Then apply the QF T on the state to get the state A⊥ t,s , and then compute m2 = ⟨u, t⟩ similarly using the ⊥ state At,s and u. Output m = m1 + m2 .

56

2n Proof. For every fixed nonzero orthogonal pair (u, v) ∈ F2n 2 × F2 , let the set of n-dimensional subspaces A satisfying u ∈ A and v ∈ A⊥ be defined as Compatible(u, v). It is easy to see that |Compatible(u, v)| depends only on n and is independent of the choice of (u, v). Hence the marginal distribution on the pair (u, v) induced by the Decisional-Coset-MOE experiment is uniform over the key space of Coset-UE, given as K := {(u, v) | u, v ∈ F2n 2 \ {0}, ⟨u, v⟩ = 0}. Thus sampling $

$

A uniformly at random, and then sampling u ← − A \ {0}, v ← − A⊥ \ {0}, is the same as first 2n sampling a uniformly random nonzero orthogonal pair (u, v) ∈ F2n 2 × F2 , and then sampling A ∈ Compatible(u, v), and therefore the marginal distribution of (A, u, v)) in the Decisional-Coset-MOE experiment and the unclonable-indistinguishable experiment (see Definition 10) for Coset-UE, is the same. Next, for a fixed non-zero orthogonal pair (u, v) and a fixed subspace A ∈ Compatible(u, v), the map (s, t) 7−→ ⟨u, t⟩ + ⟨v, s⟩ is a nonzero linear function and hence is balanced; therefore, sampling s, t uniformly and setting the message to this parity is equivalent to first sampling a uniform message m and then sampling s, t uniformly conditioned on m = ⟨u, t⟩ + ⟨v, s⟩. Therefore, conditioned on A, (u, v), the distribution of the subspace s, t and the bit ⟨u, t⟩ + ⟨v, s⟩ in the Decisional-Coset-MOE experiment, is the same as that of s, t and the message bit m in the unclonable indistinguishable experiment for Coset-UE, which concludes the proof of the lemma. Theorem 19 (Decisional Coset Monogamy). For any λ ∈ N, and any triplet of adversary Amoe = (A, B, C), s i 1 1 h 22n Pr Decisional-Coset-MOEAmoe (1λ ) = 1 ≤ + . 2n 2 2 (2 − 1)(22n−1 − 1) Due to Lemma 8, Theorem 19 gives the following immediate corollary. q 22n Corollary 1. The encryption scheme Coset-UE is an unconditional 12 (22n −1)(2 2n−1 −1) -unclonable indistinguishable encryption scheme. In order to prove Theorem 19, we will use its interpretation as a unclonable indistinguishable experiment, given in Lemma 8. In particular, we mildly extend the proof of [AS26]10 to get a general lemma showing unclonable-indistinguishable security of a class of unclonable bit-encryption schemes, that captures both Coset-UE and the construction of [AS26]. Lemma 9 (General class of unclonable indistinguishable encryption schemes). Suppose for every ℓ ∈ N, there exists a set of keys K and a set of hermitian operators {Θk }k∈K in L((C2 )⊗ℓ ), indexed by K, satisfying that for every k, tr[Θk ] = 0, Θ2k = I, and for every k, k ′ ∈ K, tr[Θk Θk′ ] = N δk,k′ where N = 2ℓ is the dimension of the space, and δij is the Kronecker Delta function, then for any distribution P = {pk }k∈K on K, the following quantum encryption scheme given by 1. GenKey(1λ ): Sample k ← P , and output k. m 2. Enc(k, m): Prepare and output the state ρk,m ct = 1/N (I + (−1) Θk ).

3. Dec(k, ρ): Measure ρ in the eigen basis of Θk , i.e., the POVM (Π0 , Π1 ) := output the outcome. 10



I+Θk I−Θk 2 , 2



and

A similar generalization of [AS26] have been independently shown in the concurrent works of [BBC26, BDF26]

57

satisfies that for every λ, and adversarial triplet AUE = (A, B, C) against it in the unclonableindistinguishable experiment (see Definition 10), the adversarial success probability is at most 12 + p p P 1 N Col(P ), where Col(P ) = k∈K p2k ’ i.e., the above scheme satisfies 12 N Col(P )-unclonable2 indistinguishability11 . The class of unclonable encryption scheme in the above lemma is a generalization of [AS26] in two directions, first, in terms of considering arbitrary hermitian operator family as opposed to Paulis, and second in terms of considering arbitrary distribution on the keyspace as opposed to the uniformly random distribution. Next we prove Theorem 19 assuming Lemma 9.  q  22n Proof of Theorem 19. We will use the interpretation of Lemma 8 and prove 12 (22n −1)(2 2n−1 −1) unclonable-indistinguishable security of Coset-UE, which by Lemma 8 would imply Theorem 19. We will show that Coset-UE is an instance of the general class of unclonable indistinguishable encryption schemes in Lemma 9. Let K := {(u, v) | u, v ∈ F2n 2 \ {0}, ⟨u, v⟩ = 0} denote the key space for Coset-UE. For any key k = (u, v) ∈ K, let Θk = X u Z v ∈ L((C2 )⊗2n ). Since for every k, Θk = X u Z v is a product of Pauli, it is a unitary and it holds that Θ†k = Z v X u = (−1)⟨u,v⟩ X u Z v = X u Z v = Θk , i.e., Θk is Hermitian, and hence, due to unitary condition, Θ2k = Θk Θ†k = I. Moreover, since (u, v) ̸= 0, Θk = X u Z v is a non-identity product of Paulis and therefore Tr[Θk ] = 0 and Θ2k = I. Similarly, for any pair of keys, k = (u, v) ∈ K and k ′ = (u′ , v ′ )K,       ′ ′ ′ ′ ′ ′ ′ ′ tr (Θk Θk′ ) = tr X u Z v X u Z v = tr (−1)⟨v,u ⟩ X u+u Z v+v = (−1)⟨v,u ⟩ tr X u+u Z v+v , which is tr(I) = 22n if u = u′ , v = v ′ , and 0 otherwise. Hence, we conclude that for any pair of keys k, k ′ ∈ K, tr(Θk Θk′ ) = 22n δk,k′ . Hence {Θk }k∈K satisfies the hypothesis of Lemma 9 with N = 22n . Next, let P denote the distribution induced by the GenKey algorithm of Coset-UE is just the 1 uniformly random distribution on K. Hence, Col(P ) = |K| . It is easy to check that |K| = (22n − 1)(22n−1 − 1). Hence, we conclude that Col(P ) :=

1 . (22n − 1)(22n−1 − 1)

(72)

Next we claim that for any message m ∈ {0, 1}, and key k ∈ K, the cipher is of the form required in the hypothesis of Lemma 9. Claim 1. For any message m ∈ {0, 1}, and key k ∈ K, let ρk,m denote the ciphertext produced by ct Coset-UE.Enc(k, m), then it holds that ρk,m ct =

1 (I + (−1)m Θk ) . N

Next we complete the proof of the theorem assuming Claim 1 before proving the claim. Let UE be a quantum encryption schme that is the same as Coset-UE, but with a different decryption algorithm, namely the new decryption algorithm Dec′ on input k, ρc t simply measure in the eigenbasis 11

We clarify that for certain choices of the operator family {Θk }k∈K and distribution P , the obtained scheme may not be efficient.

58

  k I−Θk , and outputs the outcome12 . Clearly, the fact that of Θk , i.e., the POVM (Π0 , Π1 ) := I+Θ 2 2 the operator family {Θk }k∈K satisfies the hypothesis of Lemma 9, combined with Claim 1 imply that UE is an instance of the general class p of encryption schemes described in Lemma 9. Hence by Lemma 9, we conclude that UE satisfies 12 N Col(P )-unclonable indistinguishable security. Since the unclonable-indistinguishable experiment (see Definition 10) is independent of the decryption algorithm of the encryption p scheme, and Coset-UE and UE only differ in decryption algorithms, 1 Coset-UE must also satisfy 2 N Col(P )-unclonable indistinguishable security. By Equation (72), this implies that Coset-UE satisfies s 22n 1p 1 N Col(P ) = -unclonable indistinguishable security. 2 2 (22n − 1)(22n−1 − 1) Next we prove Claim 1 to complete the proof. Proof of Claim 1. For any (u, v) ∈ K, let Compatible(u, v) denote the set of all subspace A ≤ F2n 2 with dim(A) = n such that u ∈ A and v ∈ A⊥ . For a fixed A ∈ Compatible(u, v), let Coset-rep(A) and Coset-rep(A⊥ ) denote the sets of canonical representatives of the cosets of A and A⊥ , respectively, where a canonical representative of a coset is the lexicographically first vector in the coset, and also define Comp-Parity-Coset((u, v), m, A) n o := (s, t) ∈ Coset-rep(A) × Coset-rep(A⊥ ) ⟨v, s⟩ + ⟨u, t⟩ = m . There are exactly 2n cosets of A and 2n cosets of A⊥ and the inner product of every vector in a fixed coset A + s′ with v is the same as ⟨v, s⟩, and similarly, the inner product of every vector in ⊥ a fixed coset A⊥ + t′ is the as ⟨u,
same
t⟩. Hence, the map F : (s + A, t + A ) 7−→ ⟨v, s⟩ + ⟨u, t⟩ 2n 2n ⊥ is well-defined on F2 /A × F2 /A . Since for both u and v, and any bit b ∈ {0, 1}, there are exactly 22n−1 vectors that have inner product b with u and 22n−1 vectors that have inner product b with v, it holds that F is a balanced function, i.e., has the same number of preimages of 0 as that for 1. Moreover, for any m ∈ {0, 1}, the set Comp-Parity-Coset((u, v), m, A) denotes the preimage set of m under F . Hence |Comp-Parity-Coset((u, v), m, A)| =

F2n F2n 2 2 A × A⊥

2

=

22n = 22n−1 . 2

(73)

Since every pair of cosets has the same number of vector representatives, and the parity is $

constant on each pair of cosets, sampling s, t ← − F2n 2 conditioned on ⟨v, s⟩ + ⟨u, t⟩ = m induces the uniform distribution over Comp-Parity-Coset((u, v), m, A). (u,v),m,A For any fixed key (u, v) ∈ K, A ∈ Compatible(u, v), and message m ∈ {0, 1}, let ρct denote the cipher state, conditioned on the sampled subspace being A. Hence, by the above conclusion, we can write X 1 (u,v),m,A ρct = |As,t ⟩⟨As,t | . |Comp-Parity-Coset((u, v), m, A)| (s,t)∈Comp-Parity-Coset((u,v),m,A)

(u,v),m

The ciphertext ρct

= Coset-UE.Enc((u, v), m) can then be written as (u,v),m

ρct 12

=E

(u,v),m,A

$

A← −Compatible(u,v)

ρct

.

Nevertheless, it can be checked that the two decryption algorithms are functionally the same.

59

(74)

Next, we will prove that for any fixed key (u, v) ∈ K, A ∈ Compatible(u, v) and message m ∈ {0, 1}, it holds that
1 (u,v),m,A I + (−1)m Θ(u,v) , (75) ρct = N since that would imply  

1 1 (u,v),m (u,v),m,A m ρct =E $ ρct =E $ I + (−1) Θ(u,v) = I + (−1)m Θ(u,v) , A← −Compatible(u,v) A← −Compatible(u,v) N N (76) which proves the claim. Next we prove Equation (75) to complete the proof of the claim. Fix a key k = (u, v), m ∈ {0, 1} and A ∈ Compatible(k) = Compatible(u, v) arbitrarily. Since Θk is Hermitian, and Θ2k = I, it holds that Θk only has eigen values in {−1, +1}. For any bit b ∈ {0, 1}, let the eigenspace of (−1)b , i.e., the subspace of eigenvectors with eigenvalue (−1)b of Θk , be denoted as Vbk . Clearly, the Hilbert space (C2 )⊗2n can be written as the direct sum of V0k and V1k . Since Tr(Θk ) = 0, this implies that dim(V0k ) = 22n−1 = dim(V1k ). Moreover, for any bit b ∈ {0, 1}, the projection on to the eigenspace Vbk , denoted as ΠV k can be written as b

ΠV k = b

1 2

 I + (−1)b Θk .

(77)

Next, for every (s, t) ∈ Comp-Parity-Coset((u, v), m, A), it holds that Θk |As,t ⟩ = X u Z v |As,t ⟩ = X u Z v X s Z t |A⟩

since X s Z t |A⟩ = |As,t ⟩.

= (−1)⟨v,s⟩ X u X s Z v Z t |A⟩ ⟨v,s⟩

= (−1)

X

u+s

Z

v+t

by Pauli anti-commutaion.

|A⟩

= (−1)⟨v,s⟩ |Au+s,v+t ⟩ = (−1)⟨v,s⟩ (−1)⟨u,t⟩ |As,t ⟩ = (−1)⟨v,s⟩+⟨u,t⟩ |As,t ⟩ = (−1)m |As,t ⟩ , where the last equality follows from the fact that 1 X |Au+s,v+t ⟩ = p (−1)⟨v+t,a⟩ |a + s + u⟩ |A| a∈A 1 X =p (−1)⟨t,a⟩ |a + s + u⟩ |A| a∈A 1 X ′ =p (−1)⟨u,t⟩ (−1)⟨a ,t⟩ a′ + s |A| a′ ∈A =

since v ∈ A⊥ . substituting a′ = u + a and a = u + a′ .

(−1)⟨u,t⟩ X ′ p (−1)⟨a ,t⟩ a′ + s |A| a′ ∈A

= (−1)⟨u,t⟩ |As,t ⟩ . Therefore the set of vectors {|As,t ⟩}(s,t)∈Comp-Parity-Coset(k,m,A) ⊂ Vmk . But clearly, for any two pairs of (s, t), (s′ , t′ ) ∈ Comp-Parity-Coset(k, m, A), such that (s, t) ̸= (s′ , t′ ), As,t As′ ,t′ = 0. This follows from the fact that if s ̸= s′ then they are simply supported on different subsets of computational basis elements, and if t ̸= t′ , then the same holds after applying QFT 60

E = A⊥ on both states, as QF T |As,t ⟩ = A⊥ t,s and QF T As′ ,t′ t′ ,s′ . Combined with the fact that each element in {|As,t ⟩}(s,t)∈Comp-Parity-Coset(k,m,A) is a normalized state, we conclude that {|As,t ⟩}(s,t)∈Comp-Parity-Coset(k,m,A) forms an orthonormal set inside Vmk . However, dim(Vmk ) = 22n−1 = |Comp-Parity-Coset((u, v), m, A)| = |Comp-Parity-Coset(k, m, A)| (see Equation (73)). Therefore it must hold that {|As,t ⟩}(s,t)∈Comp-Parity-Coset(k,m,A) is an orthonormal basis for Vmk . Hence, it holds that X |As,t ⟩⟨As,t | . (78) ΠVmk = (s,t)∈Comp-Parity-Coset(k,m,A)

Combined with Equation (77), Equation (78) implies, X 1 ρk,m,A = ct |Comp-Parity-Coset(k, m, A)|

|As,t ⟩⟨As,t |

(79)

(s,t)∈Comp-Parity-Coset(k,m,A)

=

1 22n−1

ΠVmk

by Equations (73) and (78) (80)

=

2 Π k N Vm

by definition of N . (81)

2 1 = · [I + (−1)m Θk ] N 2

by Equation (77). (82)

1 = [I + (−1)m Θk ] , N which completes the proof of Equation (75) and hence the claim.

6.1

(83)

Unclonable indistinguishable security of the general class of encryption schemes (Proof of Lemma 9)

We first note that the scheme is perfectly correct. Since Θk is a Hermitian operator, with Θ2k = I, all its eigenvalues are in {+1, −1}. Hence I + (−1)m Θk ⪰ 0. Moreover, since tr[Θk ] = 0, h i 1 tr ρk,m = (tr[I] + (−1)m tr[Θk ]) = 1. ct N m Thus ρk,m ct is a valid density operator. Furthermore, it is supported entirely on the (−1) -eigenspace of Θk , and hence the decryption measurement outputs m with probability one. Next, we prove unclonable-indistinguishability security. We closely follow the notations and the proof template of [AS26]. In particular, we reprove the Parts 2 and 3 of their main security proof [AS26, Theorem 3.2] for the general case of arbitrary Hermitian operators, and arbitrary distributions on the key space. Next, we recall the following results from [AS26] that will be required for our proof. Let ∥∥∞ denote the operator norm, i.e., for any operator M , we denote ∥M ∥∞ := sup|ψ|=1 ∥M |ψ⟩ ∥, where ∥∥ is the L2 norm Hermitian operator M , that can be spectral P for vectors. Similarly, or any P decomposed as M = j λj |vj ⟩⟨vj |, we denote M+ := j max(λj , 0) |vj ⟩⟨vj |.

61

Theorem 20 (Normalized Choi identity, [AS26, Theorem 2.1]). Let Φ : L(HE ) → L(HR1 ⊗ HR2 ) be a quantum channel, where dim(HE ) = N . Let HA ≃ HE , and define N

1 X |Ω⟩AE := √ |i⟩A |i⟩E . N i=1 Then, for every M ∈ L(HE ) and Q ∈ L(HR1 ⊗ HR2 ),   1 tr[QΦ(M )] = tr (M T ⊗ Q)(IA ⊗ Φ)(|Ω⟩⟨Ω|) , N where the transpose is taken in the basis used to define |Ω⟩. Lemma 10 (Conditional overlap, [AS26, Lemma 3.3]). Let UAR1 ∈ L(HA ⊗ HR1 ) and VAR2 ∈ L(HA ⊗ HR2 ). Viewing them canonically (by tensoring with identity operators) as operators on HA ⊗HR1 ⊗HR2 , we have q q ∥U V ∥∞ ≤ ∥trA [U † U ]∥∞ ∥trA [V V † ]∥∞ . Next, we abstract out an operator bound implicit in the proof of [AS26, Proposition 3.8]. Lemma 11 (Abstracted from the Positive-part bound, [AS26, Proposition 3.8]). Let EB , EC , EBC be Hermitian operators on a finite-dimensional Hilbert space, and define the Hermitian operator G :=

1 (EB + EC + EBC − I) . 2

Suppose that, 1. for every a, c ∈ {+1, −1}, Γa,c := 41 (I + aEB + cEC + acEBC ) ⪰ 0, and 2. there exists γ ≥ 0 such that for every integer ℓ ≥ 0, ℓ EB EBC EC

Then, given the spectral decomposition G = that

∞

P

≤ γ.

j λj |vj ⟩⟨vj | and G+ :=

P

j max(λj , 0) |vj ⟩⟨vj |, it holds

∥G+ ∥2∞ ≤ γ. We defer the proof of Lemma 11 to Section 6.1.1, which follows from similar arguments as used in the proof of [AS26, Proposition 3.8]. Next we complete the security proof assuming Lemma 11. Fix an arbitrary adversarial triplet AUE = (A, B, C). Let Φ : L((C2 )⊗ℓ ) → L(HR1 ⊗ HR2 ) denote the splitting channel applied by A to produce the registers R1 and R2 for B and C respectively, before the key is revealed to them. Next, for every key k ∈ K, let k k {MB,0 , MB,1 }

and

k k {MC,0 , MC,1 }

denote the binary POVM corresponding to the measurements applied by B and C respectively, after receiving k, and define k k Bk := MB,0 − MB,1 ,

k k Ck := MC,0 − MC,1 .

62

It is easy to see that Bk and Ck are Hermitian contractions, and we can rewrite k MB,m =

Let |Ω⟩AE := √1N

I + (−1)m Bk , 2

k MC,m =

I + (−1)m Ck . 2

PN

i=1 |i⟩A |i⟩E , where E is isomorphic to the ciphertext register A, and let

τAR1 R2 := (IA ⊗ ΦE ) (|Ω⟩⟨Ω|) be the normalized Choi state of Φ. b k := (ΘT )A , and define Define For every k, define Θ k X b k ⊗ Bk ⊗ I, EB := pk Θ

(84)

k∈K

EC :=

X

b k ⊗ I ⊗ Ck , pk Θ

(85)

pk I ⊗ Bk ⊗ Ck .

(86)

k∈K

EBC :=

X k∈K

Also define G :=

1 (EB + EC + EBC − I) . 2

By Theorem 20, Pr[bB = bC = m] " =E

$

k←P, m← −{0,1}

tr



mb

I + (−1) Θk



# I + (−1)m Bk I + (−1)m Ck ⊗ ⊗ τ . 2 2

(87)

Expanding the three factors and averaging over the uniform bit m removes all terms containing an odd power of (−1)m . Hence 1 (1 + tr[EB τ ] + tr[EC τ ] + tr[EBC τ ]) 4 1 = (1 + tr[Gτ ]) 2 1 ≤ (1 + ∥G+ ∥∞ ) , 2

Pr[bB = bC = m] =

(88)

where the last inequality follows from G ⪯ G+ ⪯ ∥G+ ∥∞ I, and the fact that τ is a density operator. We now show that the operator bounds used in [AS26] continue to hold when the key is sampled from the possibly distribution P . P nonuniform 2 Let γ := N k∈K pk = N Col(P ), and define X X b k ⊗ Bk , VAR := b k ⊗ Ck . UAR1 := pk Θ pk Θ 2 k∈K

k∈K

Their canonical extensions to the three registers are EB and EC , respectively. Using the Hilbert–Schmidt orthogonality of {Θk }k∈K , we obtain h i X † trA UAR U =N p2k Bk2 ⪯ γIR1 , 1 AR1 k∈K

63

(89)

h i X † trA VAR2 VAR = N p2k Ck2 ⪯ γIR2 . 2

(90)

k∈K

Hence, by Lemma 10, ∥EB EC ∥∞ ≤ γ.

(91)

We next verify the corresponding extension of [AS26, Proposition 3.6]. For every integer ℓ ≥ 0, ℓ EB EBC EC

∞

≤ γ.

(92)

ℓ For ℓ = 0, this follows from Equation (91). For ℓ ≥ 1, expanding EBC gives X ℓ pk1 · · · pkℓ (I ⊗ I ⊗ Ck1 · · · Ckℓ ) EB EC (I ⊗ Bk1 · · · Bkℓ ⊗ I) . EB EBC EC =

(93)

k1 ,...,kℓ

The two exterior operators are contractions, while the nonnegative coefficients sum to one. Therefore Equation (92) follows from Equation (91). Finally, for a, c ∈ {+1, −1}, define Γa,c :=

1 (I + aEB + cEC + acEBC ) . 4

b k ⊗Bk ⊗I and Θ b k ⊗I ⊗Ck are commuting Hermitian contractions, For every fixed k, the operators Θ and their product is I ⊗ Bk ⊗ Ck . Therefore   1 b k ⊗ Bk ⊗ I I + cΘ b k ⊗ I ⊗ Ck ⪰ 0. I + aΘ 4 Averaging with weights pk shows that Γa,c ⪰ 0

for every a, c ∈ {+1, −1}.

(94)

By Equations (92) and (94), the hypotheses of Lemma 11 hold with γ = N Col(P ). Therefore ∥G+ ∥2∞ ≤ N Col(P ). Combining this with Equation (88) gives Pr[bB = bC = m] ≤ 21 + 21 proof of the lemma. 6.1.1

p N Col(P ), which completes the

Proof of Lemma 11

Proof of Lemma 11. The proof follows the same arguments as in the proof of [AS26, Proposition 3.8]. Let t := ∥G+ ∥∞ . If t = 0, there is nothing to prove. Suppose t > 0. Since the Hilbert space is finite dimensional and G is Hermitian, there exists a unit vector |ψ⟩ such that G |ψ⟩ = t |ψ⟩ . First note that the positivity of the four operators Γa,c implies that −I ⪯ EB , EC , EBC ⪯ I.

64

Indeed, suitable pairs of the four operators Γa,c sum to 1 (I ± EB ), 2 Define ∆ := I −EBC , of Γ+1,−1 and Γ−1,+1 gives

1 (I ± EC ), 2

1 (I ± EBC ). 2

R := EB −EC . Then it is easy to see that ∆ ⪰ 0. Moreover, positivity ∆ + R ⪰ 0,

∆ − R ⪰ 0,

and hence −∆ ⪯ R ⪯ ∆.

(95)

Next, the eigenvector equation for G gives (EB + EC ) |ψ⟩ = (2tI + ∆) |ψ⟩ .

(96)

Define F := 2t(2tI + ∆)−1 . Since t > 0 and ∆ ⪰ 0, F is well defined and 0 ≺ F ⪯ I,

F (2tI + ∆) = 2tI.

We will first show that RF R ⪯ 2t∆.

(97)

For arbitrary vectors |ξ⟩ , |η⟩, positivity of ∆ + R and ∆ − R gives 1 1 ⟨ξ + η| (∆ + R) |ξ + η⟩ + ⟨ξ − η| (∆ − R) |ξ − η⟩ + 2t∥η∥2 2 2 = ⟨ξ| ∆ |ξ⟩ + 2 Re ⟨ξ| R |η⟩ + ⟨η| (∆ + 2tI) |η⟩ .

0≤

(98)

Choosing |η⟩ = −(∆ + 2tI)−1 R |ξ⟩ in Equation (98) yields R(∆ + 2tI)−1 R ⪯ ∆. Multiplying by 2t proves Equation (97). For any vector |w⟩, define QF (w) := ⟨w|F |w⟩. Using Equation (96) and F (2tI + ∆) = 2tI, we have
QF (EB + EC )ψ = 4t2 + 2t⟨ψ|∆|ψ⟩.

(99)

On the other hand, by Equation (97),
QF (EB − EC )ψ = ⟨ψ|RF R|ψ⟩ ≤ 2t⟨ψ|∆|ψ⟩.

(100)

Subtracting Equation (100) from Equation (99) and expanding the cross terms gives t2 ≤ Re⟨ψ|EB F EC |ψ⟩ ≤ ∥EB F EC ∥∞ .

(101)

It remains to upper bound the last norm. Set q := (1 + 2t)−1 ∈ (0, 1). Since ∆ = I − EBC , F = (1 − q)(I − qEBC )−1 .

65

For an integer L ≥ 1, define FL := (1 − q)

PL−1 ℓ ℓ ℓ=0 q EBC . By the hypothesis of the lemma,

∥EB FL EC ∥∞ ≤ (1 − q) ≤ (1 − q)

L−1 X ℓ=0 L−1 X

ℓ EC q ℓ EB EBC

∞

qℓγ

ℓ=0 L

= (1 − q )γ.

(102)

L F. Moreover, F − FL = q L EBC As observed above, ∥EB ∥∞ , ∥EC ∥∞ , ∥EBC ∥∞ , ∥F ∥∞ ≤ 1.

Therefore L L ∥EB (F − FL )EC ∥∞ = ∥EB (q L EBC F )EC ∥∞ = q L ∥EB EBC F EC ∥∞ ≤ q L .

Letting L → ∞ in conjunction with Equation (102) gives ∥EB F EC ∥∞ ≤ γ. Combining this with Equation (101), we obtain t2 ≤ γ. Since t = ∥G+ ∥∞ , this concludes the proof of the lemma.

66

7

Computational Monogamy-of-Entanglement Games

In this subsection, we prove the computational versions of the Decisional-Coset-MOE game that will be used in the security proofs of SDE and UPO. The proof follows the computational subspacehiding proof of [CLLZ21], and its extension to simulatable auxiliary information in [ABH+ 26, ÇG26]. We deviate from the formalism [ABH+ 26, ÇG26] who considered independent auxiliary -information generators for B and C and instead use a joint auxiliary information generator for B and C, rather than two independent generators, since the applications in this article allow the two auxiliary strings to be arbitrarily correlated. For the computational games, let V := F4n 2 . For any subspace S ≤ V and z ∈ V , let PS+z denote the canonical circuit that, on input x ∈ V , outputs 1 if and only if x ∈ S + z. All circuits compared using iO below are padded to the same size. We condition on the event that all the generated membership programs are correct on every input; the complement of this event contributes a negligible term. We first record the following immediate extension of Theorem 19, which will be used at the end of the computational reduction. Corollary 2 (Post-split auxiliary information). Consider the Decisional-Coset-MOE experiment, except that after sampling (u, v), the challenger applies an arbitrary, possibly inefficient, classical algorithm (zB , zC ) ← Post(A, u, v), and sends (u, v, zB ) to B and (u, v, zC ) to C. The algorithm Post does not receive s, t or the split registers, and its two outputs may be arbitrarily correlated. Then, for every triplet of adversaries Amoe = (A, B, C), s Pr[win] ≤

1 1 + 2 2

22n . (22n − 1)(22n−1 − 1)

Proof. Fix a nonzero orthogonal pair k = (u, v) and a bit m. By Claim 1, for every compatible subspace A, the state conditioned on k, m, A is = ρk,m,A ct

1 (I + (−1)m Θk ) , 22n

which is independent of A. Moreover, for every fixed compatible A and k, the bit m = ⟨u, t⟩ + ⟨v, s⟩ is uniform. Hence, conditioned on k, the joint distribution of (A, zB , zC ) is independent of m. The splitting adversary may append a shared classical random string to the two output registers. After receiving k, both recipients can use this common random string to sample the same value of A according to its conditional distribution given k, and then sample the correlated pair (zB , zC ) according to Post(A, k). This does not require communication and does not use m. Therefore, the post-split auxiliary information can be absorbed into the local strategies of B and C, and the corollary follows from Theorem 19. Next, we define the auxiliary information allowed in the computational game. Definition 39 (Simulatable pre-split auxiliary information). Let Aux = (Aux.Setup, Aux.Gen) be a pair of QPT algorithms with the following syntax. 67

1. pp ← Aux.Setup(1λ ) : takes as input the security parameter 1λ , and outputs a classical public parameter pp. 2. (z1,B , z2,B , z1,C , z2,C ) ← Aux.Gen(pp, A, u, v) : takes as input a classical public parameter pp, a subspace A ≤ V , vectorsu ∈ A \ {0}, and v ∈ A⊥ \ {0}, and outputs pre-split auxiliary information (z1,B , z1,C ) and post-split auxiliary information (z2,B , z2,C ), for B and C respectively13 .

There exists a possibly inefficient algorithm Aux.Sim such that for every subspace A ≤ V , u ∈ A \ {0}, v ∈ A⊥ \ {0},     pp ← Aux.Setup(1λ ), pp ← Aux.Setup(1λ ), ≈s (pp, ze1,B , ze1,C ) : (pp, z1,B , z1,C ) : (e z1,B , ze1,C ) ← Aux.Sim(pp) (z1,B , z2,B , z1,C , z2,C ) ← Aux.Gen(pp, A, u, v) (103) where the first distribution is obtained by sampling pp ← Aux.Setup(1λ ) and then running Aux.Gen(pp, A, u, v), and the second is obtained by sampling pp ← Aux.Setup(1λ ) and then running Aux.Sim(pp). Definition 40 (Comp-Decisional-Coset-MOE). Let n := n(λ) be a polynomial function in λ, and V = F4n 2 . For a triplet of QPT adversaries Amoe = (A, B, C) and auxiliary algorithms Aux as above, consider the following experiment. Comp-Decisional-Coset-MOEAmoe ,Aux (1λ ): $

1. Ch samples a uniformly random 2n-dimensional subspace A ≤ V and independent s, t ← − V, and prepares 1 X |As,t ⟩ = p (−1)⟨a,t⟩ |a + s⟩ . |A| a∈A It also generates M0 ← iO(PA+s ), and M1 ← iO(PA⊥ +t ). $

$

2. Ch samples u ← − A \ {0}, v ← − A⊥ \ {0}, and generates pp ← Aux.Setup(1λ ), and samples (z1,B , z2,B , z1,C , z2,C ) ← Aux.Gen(pp, A, u, v). 3. Ch sends (|As,t ⟩ , M0 , M1 , pp, z1,B , z1,C ) to A. 4. A outputs a joint state σR1 ,R2 and sends registers R1 to B and R2 to C. 5. After the split, Ch sends (u, v, z2,B ) to B and (u, v, z2,C ) to C. 6. B and C output bB , bC . 7. The output of the experiment is 1 if bB = bC = ⟨u, t⟩ + ⟨v, s⟩. Note that the pair (u, v) is sampled before the split only because the pre-split auxiliary information may depend on it. For convenience, define s 1 22n 2n − 1 ϵDCMOE,n := , β := . n 2 (22n − 1)(22n−1 − 1) 22n − 1 13

The four strings (z1,B , z2,B , z1,C , z2,C ) can be arbitrarily correlated.

68

Theorem 21 (Computational Decisional Coset Monogamy with auxiliary information). Assume post-quantum secure iO and post-quantum secure subspace-hiding obfuscation. Then, for every function n = n(λ) ∈ ω(log(λ)), and for every QPT triplet Amoe = (A, B, C) and every auxiliaryinformation generator satisfying Definition 39, there exists a negligible function negl(λ) such that h i 1 Pr Comp-Decisional-Coset-MOEAmoe ,Aux (1λ ) = 1 ≤ + negl(λ). 2 Proof. Fix a QPT triplet of adversaries Amoe = (A, B, C). We proceed through a sequence of hybrids, following the computational monogamy proof of [CLLZ21] and the auxiliary-information hybrids of [ABH+ 26, ÇG26]. Hyb0 .

This is the experiment Comp-Decisional-Coset-MOEAmoe ,Aux (1λ ).

Hyb1 : Enlarge the primal subspace. Replace the first public program M0 = iO(PA+s ) by b (x−s)), where U ⊃ A is a uniformly random 3n-dimensional superspace and U b ← shO(U ). iO(x 7→ U Formally, this change is performed through the standard intermediate hybrid in which M0 is first b − s)) for A b ← shO(A), followed by the subspace-hiding replacement of A b replaced by iO(x 7→ A(x b . The reduction knows (A, s, t, u, v) and can therefore prepare the coset state and generate all by U four auxiliary strings. Hence Hyb0 and Hyb1 are computationally indistinguishable. $

Hyb2 : Rerandomize the primal shift. Sample ws ← − U , set σ := s + ws , and replace the source shift s in the first public program by σ. Since U +s = U +σ, the two source circuits are functionally equivalent, and therefore Hyb1 and Hyb2 are computationally indistinguishable by iO-security. Hyb3 : Enlarge the dual subspace. Sample a uniformly random n-dimensional subspace L ⊂ A, so that L⊥ is a uniformly random 3n-dimensional superspace of A⊥ , and replace the second public c⊥ (y − t)), where L c⊥ ← shO(L⊥ ). As in Hyb , this is program M1 = iO(PA⊥ +t ) by iO(y 7→ L 1 performed through the standard intermediate hybrid using an obfuscation of A⊥ , and subspacehiding security gives that Hyb2 and Hyb3 are computationally indistinguishable. $

Hyb4 : Rerandomize the dual shift. Sample wt ← − L⊥ , set τ := t + wt , and replace the source ⊥ shift t in the second public program by τ . Since L + t = L⊥ + τ , iO-security gives that Hyb3 and Hyb4 are computationally indistinguishable. The first four hybrids are exactly the primal and dual subspace-hiding and affine-rerandomization hybrids used in [CLLZ21]. Their validity is unaffected by the joint auxiliary information because the reduction can sample the auxiliary information as it knows the smaller subspace and all values required to run Aux.Setup and Aux.Gen. Thus, there exists a negligible function negl such that |Pr[Hyb0 = 1] − Pr[Hyb4 = 1]| ≤ negl(λ). Hyb5 : Simulate the pre-split auxiliary information. Sample (e z1,B , ze1,C ) ← Aux.Sim(pp) and use this pair in place of (z1,B , z1,C ). Then sample (z2,B , z2,C ) jointly from the conditional distribution given by (z1,B , z2,B , z1,C , z2,C ) ← Aux.Gen(pp, A, u, v)), conditioned on the event (z1,B , z1,C ) = (e z1,B , ze1,C ). 69

If this event (z1,B , z1,C ) = (e z1,B , ze1,C ) has probability zero, define the conditional distribution arbitrarily. By Definition 39 and the fact that statistical distance does not increase under a classical channel, there exists a negligible function negl′ (λ) such that |Pr[Hyb4 = 1] − Pr[Hyb5 = 1]| ≤ negl′ (λ). The experiment Hyb5 may be inefficient, but this is harmless since the transition is statistical and no further computational indistinguishability argument will be used. In Hyb5 , the entire input given to A before the split is independent of (u, v) conditioned on (A, s, t) and the two public programs. Hence, the experiment is identically distributed if (u, v) is sampled only after A outputs the two registers, and (z2,B , z2,C ) is subsequently sampled from the conditional distribution above. Hyb6 : Reveal L, U, σ, τ . In addition to the information already given before the split, give (L, U, σ, τ ) to A. This can only increase the winning probability, and therefore Pr[Hyb5 = 1] ≤ Pr[Hyb6 = 1]. Analysis of Hyb6 . Condition on fixed values of (L, U, σ, τ, pp, ze1,B , ze1,C ) and on the two publicprogram strings. Conditioned on these values, A is uniformly distributed among the 2n-dimensional subspaces satisfying L ⊂ A ⊂ U . Moreover, s + σ is uniform over U , t + τ is uniform over L⊥ , and these two random variables are independent. Choose an invertible linear transformation T , as a deterministic function of (L, U ), such that T (L) = Fn2 ⊕ 0 ⊕ 0

T (U ) = Fn2 ⊕ F2n 2 ⊕ 0.

and

We use T on computational-basis coordinates and T −T on phase coordinates. For every intermediate subspace A, there exists a unique n-dimensional subspace A ≤ F2n 2 such that T (A) = Fn2 ⊕ A ⊕ 0,

⊥

T −T (A⊥ ) = 0 ⊕ A ⊕ Fn2 .

Since A is uniform subject to L ⊂ A ⊂ U , the induced subspace A is uniformly distributed among the n-dimensional subspaces of F2n 2 . By the same change-of-basis calculation as in [CLLZ21, ABH+ 26, ÇG26], after applying the known Pauli correction X σ Z τ and the unitary corresponding to T , the coset state becomes, up to a global phase, |+⟩⊗n ⊗ As,t ⊗ |0⟩⊗n , $

where s, t ← − F2n 2 are independent and uniform. The two outer registers are fixed and can be incorporated into A’s strategy. Write the transformed vectors as T −T (v) = (0, v, vR ),

T (u) = (uL , u, 0), ⊥

where u ∈ A and v ∈ A . The target bit satisfies ⟨u, t⟩ + ⟨v, s⟩ = ⟨u, τ ⟩ + ⟨v, σ⟩ + ⟨u, t⟩ + ⟨v, s⟩.

(104)

The first two terms depend only on (σ, τ, u, v) and are therefore known to both recipients after the split. Next, let Bad denote the event that u = 0 or v = 0. Since u = 0 exactly when u ∈ L, and v = 0 exactly when v ∈ U ⊥ , we have Pr[u = 0] = Pr[v = 0] = 70

2n − 1 = βn . 22n − 1

Therefore, Pr[Bad] ≤ 2βn .

(105) $

Conditioned on ¬Bad, the subspace A remains uniform and, conditioned on A, the vectors u ← − $

⊥

A \ {0} and v ← − A \ {0} are independent and uniform. We now reduce Hyb6 , conditioned on the fixed values above and on ¬Bad, to the informationtheoretic experiment of Corollary 2. The information-theoretic A receives As,t , appends |+⟩⊗n and |0⟩⊗n , applies the inverse of the known change of basis and Pauli correction, supplies the fixed public programs and the fixed strings (pp, ze1,B , ze1,C , L, U, σ, τ ), and runs the splitting algorithm from Hyb6 . $

After the information-theoretic challenger reveals (u, v), the post-split algorithm samples uL , vR ← − Fn2 and defines

u := T −1 (uL , u, 0),

v := T T (0, v, vR ).

These are distributed exactly as the original vectors conditioned on ¬Bad. The algorithm reconstructs
A = T −1 Fn2 ⊕ A ⊕ 0 , samples (z2,B , z2,C ) jointly according to the conditional distribution used in Hyb5 , and computes η := ⟨u, τ ⟩ + ⟨v, σ⟩. It gives (u, v, z2,B , η) to B and (u, v, z2,C , η) to C. This procedure may be inefficient, but it does not receive (s, t) or the split registers and is therefore allowed by Corollary 2. Each recipient runs the corresponding recipient from Hyb6 . If the recipient outputs bX , the information-theoretic recipient outputs bX + η. By Equation (104), the winning events in the two experiments are identical. Therefore, Pr[Hyb6 = 1 | ¬Bad] ≤

1 + ϵDCMOE,n . 2

Let δ := Pr[Bad]. Upper bounding the winning probability conditioned on Bad by one and using Equation (105), we obtain   1 Pr[Hyb6 = 1] ≤ δ + (1 − δ) + ϵDCMOE,n 2 δ 1 ≤ + ϵDCMOE,n + 2 2 1 ≤ + ϵDCMOE,n + βn . 2 Combining the computational hybrid transitions, the statistical transition from Hyb4 to Hyb5 , and the inequality between Hyb5 and Hyb6 , and absorbing all negligible functions into a single negligible function, gives Pr[Hyb0 = 1] ≤

1 + ϵDCMOE,n + βn + negl(λ). 2

In particular, since n = ω(log λ), both ϵDCMOE,n and βn are negligible, which completes the proof of the theorem. Corollary 3 (Computational Decisional Coset Monogamy without auxiliary information). Let Comp-Decisional-Coset-MOEAmoe (1λ ) denote the experiment of Definition 40 with no auxiliary information, i.e., with pp = z1,B = z2,B = z1,C = z2,C = ⊥. 71

Assume post-quantum secure iO and post-quantum secure subspace-hiding obfuscation. Then, for every function n = n(λ) ∈ ω(log λ) and every QPT triplet Amoe = (A, B, C), there exists a negligible function negl(λ) such that h i 1 Pr Comp-Decisional-Coset-MOEAmoe (1λ ) = 1 ≤ + negl(λ). 2 Proof. Let Aux.Setup(1λ ) output ⊥, let Aux.Gen(pp, A, u, v) output (⊥, ⊥, ⊥, ⊥), and let Aux.Sim(pp) output (⊥, ⊥). The statistical simulatability condition in Definition 39 then holds perfectly, and the result follows directly from Theorem 21. The subspace-hiding obfuscators required by Corollary 3 can be obtained from post-quantum secure indistinguishability obfuscation and injective keyed one-way functions (see [CLLZ21]) which can be constructed from indistinguishability obfuscation and one-way functions [BPW16].

72

Part III

Copy-Protection Constructions 8

Single-Decryptor Encryption Construction

In this section, we construct an SDE scheme for the message space M = {0, 1}m(λ) and prove that it satisfies correlated-challenge decision security. The construction is a minor variant of the cosetstate SDE scheme of Kitagawa and Yamakawa ([KY25]): we combine the two ciphertext programs in their construction into a single program with a selector bit.

8.1

Construction

Let iO be an indistinguishability obfuscation scheme and set n = n(λ) := 2λ. For the ciphertext programs used below, let ΩiO = {0, 1}ℓiO (λ) be the random-tape space of iO. We regard iO as deterministic once this tape is fixed. All circuits compared in an iO hybrid are padded to the same size, and ⊥ is represented by a fixed string distinct from the message outputs. SDE.GenKey(1λ ) $

1. Sample a uniformly random n-dimensional subspace A ≤ F2n − F2n 2 and independent s, t ← 2 . 2. Compute M̂0 ← iO(1λ , M0 ) and M̂1 ← iO(1λ , M1 ), where M0 , M1 are the following programs. M0 (v) Hardcoded: A + s 1. If v ∈ A + s, output 1; otherwise, output 0. M1 (v) Hardcoded: A⊥ + t 1. If v ∈ A⊥ + t, output 1; otherwise, output 0. 3. Set pk := (M̂0 , M̂1 ) and sk := |As,t ⟩ := √1

⟨a,t⟩ |a + s⟩ . Output (pk, sk ). a∈A (−1)

P

|A|

SDE.Enc(pk, m) The randomness space of encryption is R := M × ΩiO . On randomness τ = $

(r, ω) ← − R, proceed as follows. 1. Parse pk = (M̂0 , M̂1 ). 2. Compute P̂ ← iO(1λ , Pm,r ; ω), where Pm,r is the following program. Pm,r (c, v) Hardcoded: M̂0 , M̂1 , m, r 1. If c = 0 and M̂0 (v) = 1, output m ⊕ r.

73

2. If c = 1 and M̂1 (v) = 1, output r. 3. Otherwise, output ⊥. 3. Output ct := P̂ . Thus, encryption is fully classical and uses an independent uniform pad and an ordinary fresh iO tape. SDE.Dec(sk , ct) 1. Parse P̂ = ct. 2. Run P̂ (0, ·) on sk coherently, let y0 denote the outcome. Then, apply the inverse unitary on sk to restore the state sk (as in Lemma 2). 3. Apply H ⊗2n(λ) to sk . 4. Run P̂ (1, ·) on sk coherently, let y1 denote the outcome. Then, again apply the inverse of the last unitary to recover the state sk (as in Lemma 2). 5. Apply H ⊗2n(λ) to sk . 6. Output y0 ⊕ y1 . Theorem 22 (Correlated-challenge-secure SDE). Assuming post-quantum secure indistinguishability obfuscation and post-quantum one-way functions, the scheme above is perfectly correct and satisfies correlated-challenge decision security (Definition 22). Consequently, it satisfies strong CPA and CPA+ anti-piracy security.

8.2

Correctness

Lemma 12. The above construction is perfectly correct. Proof of Lemma 12. Fix an honestly generated key pair and a ciphertext encrypting m ∈ M with pad r. For every a ∈ A, correctness of iO gives P̂ (0, a + s) = m ⊕ r. The first evaluation therefore returns y0 = m ⊕ r with certainty and leaves the coset state unchanged. Moreover, ⊥ ⊥ ⊥ H ⊗2n |As,t ⟩ = (−1)⟨s,t⟩ A⊥ t,s . Since P̂ (1, a + t) = r for every a ∈ A , the second evaluation returns y1 = r with certainty. Thus decryption outputs (m ⊕ r) ⊕ r = m, and the final Hadamard transform restores |As,t ⟩ up to a global phase.

8.3

Proof of security

Proof of Theorem 22. Fix an admissible sampler Samp and a QPT adversary A = (A, B, C) for the correlated-challenge experiment. Let N be the number of challenge pairs per party output by A; since it is encoded in unary, N is polynomially bounded. For X ∈ {B, C} and i ∈ [N ], write (µX,i,0 , µX,i,1 ) for X’s i-th pair, identifying the two parties’ pairs in identical mode. Set δX,i := µX,i,0 ⊕ µX,i,1 and µX,i := µX,i,bX = µX,i,0 ⊕ bX · δX,i , where b · z = z if b = 1 and b · z = 0m(λ) otherwise. For the ith challenge ciphertext that party X ∈ {B, C} receives, let rX,i denote the uniform pad hardcoded in its obfuscated circuit. In separate mode, the pads (rX,i )X∈{B,C}, i∈[N ] are mutually independent. In identical mode, the challenger samples one pad ri for each i ∈ [N ], uses it in the single ciphertext for that coordinate, and gives the same ciphertext to both parties; equivalently, rB,i = rC,i := ri . 74

Hyb0 : Real experiment. This is the correlated-challenge experiment of Definition 22, instantiated with the scheme above. Hyb1 : Use one uniform challenge bit. output by (b′B , b′C ).

In separate mode, run Samp(pk, IND) and denote its $

Set ∆ := b′B ⊕ b′C .

In identical mode, set ∆ := 0. Next sample ee ← − {0, 1}. Use bB := ee as Bob’s challenge bit and bC := ee ⊕ ∆ as Charlie’s challenge bit. All other steps are unchanged. We show that Hyb0 and Hyb1 are identically distributed. Fix pk. For i, j ∈ {0, 1}, let pij be the probability that Samp(pk, IND) outputs (i, j). The uniform-marginal condition gives p00 = p11 and p01 = p10 . Consequently, conditioned on any value of ∆ in its support, b′B is uniform and b′C = b′B ⊕ ∆. Thus (e e, ee ⊕ ∆) in Hyb1 has the same distribution as (b′B , b′C ) in Hyb0 . In identical mode, the sampler’s output is a single uniform bit, which has the same distribution as ee. Finally, A produces its messages and split registers before the sampler is invoked, and the sampler receives only pk and uses fresh coins. The equality therefore holds jointly with the complete output of A. Hyb2 : Mask the coset parity to get to the challenge bit. $

After sampling (A, s, t), addi-

$

$ tionally sample u ← − A \ {0}, v ← − A⊥ \ {0}, and ζ ← − {0, 1}.

Define α := ⟨v, s⟩, β := ⟨u, t⟩, and e := α ⊕ β, and set bB := e ⊕ ζ and bC := e ⊕ ζ ⊕ ∆. For every fixed choice of the remaining variables, e ⊕ ζ is uniform. Hence Hyb1 and Hyb2 are identically distributed. For later use, define dB := ζ and dC := ζ ⊕ ∆; then bX = e ⊕ dX for X ∈ {B, C}. This hybrid changes only the sampling of the challenge bits; the pads rX,i are still sampled as specified above.

Hyb3 : Write the encryption pads using uniform strings. We change only how the pads, i.e., (rX,i )X∈{B,C}, i∈[N ] from Hyb2 are sampled. In separate mode, sample mutually independent $

$

qX,i ← − M for every X ∈ {B, C} and i ∈ [N ]. In identical mode, sample independent qi ← − M for i ∈ [N ] and set qB,i = qC,i := qi . In either mode, define rX,i := qX,i ⊕ β · δX,i . Conditioned on all variables sampled before the q’s, the string β · δX,i is fixed, so the map from qX,i to rX,i is a bijection on M. Consequently, in separate mode the pads remain mutually independent and uniform. In identical mode, δB,i = δC,i and qB,i = qC,i , so rB,i = rC,i is a single uniform pad, exactly as in Hyb2 . The transformation is independent across coordinates, and therefore the complete joint distribution of the pads is unchanged. Hence Hyb2 and Hyb3 are identically distributed. This way of sampling the pads prepares the next hybrid. Since bX = α ⊕ β ⊕ dX , the two occurrences of β · δX,i cancel in µX,i,bX ⊕ rX,i , giving µX,i,bX ⊕ rX,i = qX,i ⊕ µX,i,0 ⊕ (α ⊕ dX ) · δX,i . Thus the first branch of the ciphertext program will use the value α available on A + s, while its second branch will use the value β available on A⊥ + t. Hyb4 : Replace the ciphertext programs. PµX,i ,rX,i by the following program QX,i .

For every X, i, set γX,i := dX · δX,i and replace

QX,i (c, w) Hardcoded: M̂0 , M̂1 , u, v, qX,i , γX,i , µX,i,0 , δX,i 1. If c = 0 and M̂0 (w) = 1, output qX,i ⊕ µX,i,0 ⊕ γX,i ⊕ ⟨v, w⟩ · δX,i . 2. If c = 1 and M̂1 (w) = 1, output qX,i ⊕ ⟨u, w⟩ · δX,i .

75

3. Otherwise, output ⊥. The old and new programs are functionally equivalent. If w ∈ A + s, then ⟨v, w⟩ = α, and the first branch returns qX,i ⊕ µX,i,0 ⊕ (dX ⊕ α) · δX,i = µX,i,bX ⊕ rX,i . If w ∈ A⊥ + t, then ⟨u, w⟩ = β, and the second branch returns qX,i ⊕ β · δX,i = rX,i . Both programs return ⊥ otherwise. In separate mode, the 2N obfuscations use independent tapes, and hence we change the 2N programs inside the obfuscations one at a time using iO security. In identical mode, there is one common old program and one common new program per coordinate i ∈ [N ], and we change the two identical copies of the obfuscations of the N programs. Since N is polynomial, |Pr[Hyb3 = 1] − Pr[Hyb4 = 1]| ≤ negl(λ). We reduce Hyb4 to computational decisional coset monogamy (Corollary 3), instantiated there with n = λ. Its challenger samples a 2λ-dimensional subspace of F4λ 2 , exactly as in our construction, where n = 2λ. The splitter A′ receives the coset state and the two obfuscated membership programs for the cosets. It treats the programs as pk and runs A on (pk, |As,t ⟩). It samples ∆, ζ, dB , dC , the q’s, and the iO tapes as in Hyb4 , and appends to party X’s register pk, dX and (µX,i,0 , δX,i , qX,i , ωX,i )i∈[N ] . In identical mode, the parties receive the same qi and tape ωi for each coordinate; otherwise, all tapes are independent. These values can be generated before (u, v) are revealed and without knowing (u, v) or e. Upon receiving (u, v), party X ′ computes γX,i = dX · δX,i , constructs and obfuscates every QX,i using the tape it received for every i ∈ [N ] from A′ , and runs X on the resulting ciphertexts, and obtains ebX . In particular, in the identical mode, the two parties use identical program descriptions and tapes, so they obtain the same obfuscation, exactly matching a single ciphertext copied to both parties. Finally, X ′ outputs zX := ebX ⊕ dX . Since bX = e ⊕ dX , we have zX = e exactly when ebX = bX . Thus the reduction wins the coset-monogamy game exactly when Awins Hyb4 . By  Corollary 3, Pr[Hyb4 = 1] ≤ 21 +negl(λ), and hence Pr SDE-CORRSDE,A,Samp (1λ ) = 1 ≤ 21 +negl(λ). Strong CPA and CPA+ security follow from Theorems 11 and 13.

76

9

Unclonable Puncturable Obfuscation Construction

In this section, we prove the following theorem. Theorem 23 (Correlated UPO from iO and LWE). Assume the existence of post-quantum polynomially secure iO and the quantum hardness of LWE. Then, for every constant c > 0 and every polynomial-size keyed circuit class C = {Ck : Xλ → Yλ }k∈Kλ where X = {0, 1}ℓin , Y := {0, 1}ℓout and ℓin = ℓin (λ) ≥ λc for some constant c > 0, then there exists a UPO scheme for C that satisfies λc entropic correlated UPO security. Moreover, for the special case of IDU -generalized UPO security, the LWE assumption can be replaced with post-quantum one-way functions.

9.1

Construction

Fix an arbitrary constant c > 0, with respect to which we want to prove Theorem 23. The UPO scheme that we will use to prove Theorem 23 is the UPO construction of [ABH+ 26, ÇG26]. Next, we recall the construction of [ABH+ 26] (also considered for copy protection in [ÇG26], independently) as follows. ℓout (λ) . Let PPRF be a puncturable PRF with Let n := ⌈λc/3 ⌉, let V := F4n 2 , and let Yλ = {0, 1} domain Xλ and range Yλ . UPO.Obf(1λ , Ck ) $

1. Sample a uniformly random 2n-dimensional subspace A ≤ V and independent s, t ← −V. 2. Sample M̂0 ← iO(M0 ) and M̂1 ← iO(M1 ), where M0 , M1 are the following programs. M0 (a) Hardcoded: A + s 1. If a ∈ A + s, output 1; otherwise, output 0.

M1 (a) Hardcoded: A⊥ + t 1. If a ∈ A⊥ + t, output 1; otherwise, output 0. 3. Sample K ← PPRF.Gen(1λ ). 4. Sample Q̂0 ← iO(Q0 ) and Q̂1 ← iO(Q1 ), where Q0 , Q1 are the following programs. Q0 (a, x) Hardcoded: M̂0 , Ck , K 1. If M̂0 (a) = 0, output ⊥. 2. Otherwise, output FK (x) ⊕ Ck (x).

77

Q1 (a, x) Hardcoded: M̂1 , K 1. If M̂1 (a) = 0, output ⊥. 2. Otherwise, output FK (x).

  5. Output ρk := |As,t ⟩ , Q̂0 , Q̂1 . UPO.Eval(ρk , x)   1. Parse ρk = |As,t ⟩ , Q̂0 , Q̂1 , and let R denote the register containing |As,t ⟩. 2. Using a reversible implementation of Q̂0 , coherently evaluate Q̂0 (·, x) on R into a fresh output register, and measure the output register to obtain y0 . 3. Apply H ⊗4n to R, obtaining A⊥ t,s up to a global phase. 4. Using a reversible implementation of Q̂1 , coherently evaluate Q̂1 (·, x) on R into a fresh output register, and measure the output register to obtain y1 . 5. Apply H ⊗4n to R, restoring |As,t ⟩. 6. Output (ρk , y0 ⊕ y1 ). Lemma 13 (Correctness). The above construction is perfectly correct. Proof. Every basis vector in the support of |As,t ⟩ belongs to A + s. Hence the first coherent evaluation returns y0 = FK (x) ⊕ Ck (x) and does not disturb the coset state. After applying H ⊗4n , ⊥ every basis vector in the support of A⊥ t,s belongs to A + t, and the second coherent evaluation returns y1 = FK (x). The final Hadamard transform restores the input state, so the evaluation algorithm outputs (ρk , Ck (x)) with certainty.

9.2

Proof of Security

The proof follows the template used in the proof of [ABH+ 26, Theorem 6.3]. There are two main differences, first we use a probabilistic argument to rewrite the experiment arbitrary correlated challenge bits, as an experiment with a single challenge bit (see the indistinguishability argument in the indistinguishability proof of Hyb0 and Hyb1 , which crucially relies on the restriction (Equation (52)) of the UPO sampler definition (Definition 26)), which is suitable for reducing to the computational MOE experiment Comp-Decisional-Coset-MOE, secondly, analogous to the [ABH+ 26, Lemma 5.3], we prove a new simulation lemma (see Lemma 14) for the correlated UPO security definition that itself allows auxiliary information leakage to the adversaries, (see Definition 27), to show that the pre-split auxiliary information in our final hybrid can be simulated to reduce the hybrid to a valid instance of Comp-Decisional-Coset-MOE. Let m := 8n, and for u, v ∈ V define msg(u, v) := u ∥ v ∈ {0, 1}m . Let H be an efficiently sampleable universal hash family from Xλ to {0, 1}m . Let LF = (LF.Geninj , LF.Genloss ) be the injective/lossy function family from [ABH+ 26], with domain Xλ , such that every function sampled 78

in injective mode is injective, the two modes are computationally indistinguishable against QPT algorithms, and every function sampled in lossy mode has image size at most 2ℓimg , where ℓimg ≤ λ2c/3 . We use the puncturable PRF and subspace-hiding obfuscation instantiated in [ABH+ 26]. 2c/3 For a ∈ {0, 1} and z ∈ Yλ , define a · z := z if a = 1, and a · z := 0ℓout if a = 0. Set ε := 2−λ . For all sufficiently large λ, λc ≥ 2m + 2ℓimg + 2 log(1/ε) + 3. For jointly distributed classical random variables X, Z, we use average conditional min-entropy, defined as ! X e ∞ (X | Z) := − log H Pr[Z = z] max Pr[X = x | Z = z] . (106) x

z

e ∞ (X | Z, Y ) ≥ H e ∞ (X | Z) − ℓ. In particular, if Y has support size at most 2ℓ , then H Proof of Theorem 23. We need to prove λc -entropic correlated UPO security for UPO. e ∞ (xX | zaux ) ≥ λc for every X ∈ {B, C}, and Fix any correlated UPO sampler Samp satisfying H a QPT triplet of adversaries AUPO = (A, B, C). We view A as a two-stage algorithm with retained state. The pre-split auxiliary string zaux is given to the first stage of A before it chooses (k, µB , µC ), while wB , wC are carried unchanged through all the hybrids and are given to B, C, respectively, after the split. We consider the following set of hybrids. Hyb0 : Real experiment. This is the real experiment Correlated-UPOΠ,AUPO ,Samp,C (1λ ) from Definition 27, instantiated with UPO as the construction. Hyb1 : Sample the challenge bits using one uniform bit.

Run (zaux , xB , xC , b′B , b′C , wB , wC ) ←

$

− {0, 1}, and set bB := ee and bC := ee + ∆. Samp(1λ ), set ∆ := b′B + b′C , discard b′B , b′C , sample ee ← The remaining steps are unchanged. We show that Hyb0 and Hyb1 are identically distributed. Fix (z̄aux , x̄B , x̄C , w̄B , w̄C ) in the support of (zaux , xB , xC , wB , wC ), and let   aux , xB =x̄B , xC =x̄C , . pij := Pr bB = i, bC = j zaux =z̄ wB =w̄B , wC =w̄C By the condition (Equation (52)) in Definition 26, it is easy to see that p00 = p11 and p01 = p10 , and hence conditioned on bB ⊕ bC = b for some bit b, the marginal distribution on bB as well as bC remains uniform. Therefore, we conclude that conditioned on (zaux , xB , xC , wB , wC , ∆), the bit bB is uniform and bC = bB + ∆. The first-stage output and retained state of A are obtained from zaux and independent randomness, so adjoining them preserves this identical distribution. Hyb2 : Write the common uniform bit as the coset parity plus a uniform mask. $

In the

$

$ execution of Obf, after sampling (A, s, t), sample u ← − A \ {0}, v ← − A⊥ \ {0}, and ζ ← − {0, 1}, and

define α := ⟨v, s⟩, β := ⟨u, t⟩, and e := α + β. Set bB := e + ζ and bC := e + ζ + ∆. Since e + ζ is uniform for every fixed value of the remaining variables, Hyb1 and Hyb2 are identically distributed. Define dB := ζ, dC := ζ + ∆, and diff X (x) := Ck (x) ⊕ µX (x) for X ∈ {B, C}. Then bX = α + β + dX . Hyb3 : Puncture the PRF and hardcode its values at the challenge points. Let S := {xB , xC }, and let KS be the puncturable PRF key punctured at S. If xB ̸= xC , let yX := FK (xX ) for every X ∈ {B, C}. If xB = xC , let yB := FK (xB ) and set yC := yB . Replace Q0 , Q1 by the following programs P0 , P1 .

79

P0 (a, x) Hardcoded: M̂0 , Ck , µB , µC , KS , xB , xC , bB , bC , yB , yC 1. If M̂0 (a) = 0, output ⊥. 2. If x = xB , output yB ⊕ Ck (x) ⊕ bB · diff B (x). 3. If x = xC and xC ̸= xB , output yC ⊕ Ck (x) ⊕ bC · diff C (x). 4. Output FKS (x) ⊕ Ck (x).

P1 (a, x) Hardcoded: M̂1 , KS , xB , xC , yB , yC 1. If M̂1 (a) = 0, output ⊥. 2. If x = xB , output yB . 3. If x = xC and xC ̸= xB , output yC . 4. Output FKS (x). The relevant circuits in Hyb2 and Hyb3 have the same functionality. At x = xB , the programs in Hyb3 output yB ⊕ Ck (xB ) ⊕ bB · diff B (xB ) and yB , respectively, which are exactly the corresponding outputs of the programs in Hyb2 . This also covers the case xB = xC , since the Bob line is evaluated first. If xB ̸= xC , the same argument applies at x = xC . Finally, for x ∈ / S, punctured correctness gives FKS (x) = FK (x). Therefore, by iO-security, we conclude that Hyb2 and Hyb3 are computationally indistinguishable. Hyb4 : Replace the hardcoded PRF values by uniform strings. $

If xB ̸= xC , replace

$

(FK (xB ), FK (xC )) by independent yB , yC ← − Yλ . If xB = xC , sample yB ← − Yλ and set yC := yB . Puncturable-PRF security implies that Hyb3 and Hyb4 are computationally indistinguishable. $

Hyb5 : Rewrite the uniform values. Sample independent qB , qC ← − Yλ . If xB ̸= xC , then for every X ∈ {B, C} set yX := qX ⊕ β · diff X (xX ). (107) If xB = xC , set yB = yC := qB ⊕ β · diff B (xB ),

(108)

and let qC be an unused independent uniform string. Since the values yX in Hyb4 are uniform, this is an exact change of variables. Replace P0 , P1 by the following programs. P0′ (a, x) Hardcoded: M̂0 , Ck , µB , µC , KS , xB , xC , qB , qC , α, dB , dC 1. If M̂0 (a) = 0, output ⊥. 2. If x = xB , output qB ⊕ Ck (x) ⊕ (α + dB ) · diff B (x).

80

3. If x = xC and xC ̸= xB , output qC ⊕ Ck (x) ⊕ (α + dC ) · diff C (x). 4. Output FKS (x) ⊕ Ck (x). P1′ (a, x) Hardcoded: M̂1 , Ck , µB , µC , KS , xB , xC , qB , qC , β 1. If M̂1 (a) = 0, output ⊥. 2. If x = xB , output qB ⊕ β · diff B (x). 3. If x = xC and xC ̸= xB , output qC ⊕ β · diff C (x). 4. Output FKS (x). The relevant circuits in Hyb4 and Hyb5 have the same functionality. Suppose first that xB ̸= xC and fix X ∈ {B, C}. By the definition of yX , qX ⊕ β · diff X (xX ) = yX .

(109)

Moreover, since bX = α + β + dX , qX ⊕ Ck (xX ) ⊕ (α + dX ) · diff X (xX ) = yX ⊕ Ck (xX ) ⊕ (α + β + dX ) · diff X (xX ) = yX ⊕ Ck (xX ) ⊕ bX · diff X (xX ). Thus, the individual outputs of P0′ , P1′ at xX are exactly the corresponding outputs of P0 , P1 . If xB = xC , the Bob line is evaluated first, and the same calculation applies with X = B. At every other point, the programs are unchanged. Therefore, by iO-security we conclude that Hyb4 and Hyb5 are computationally indistinguishable. Hyb6 : Replace the explicit point comparisons by injective-function comparisons. $

(1λ ) independently, and set η

every X ∈ {B, C}, sample hX ← − H and LX ← LF.Geninj and strX := msg(u, v) ⊕ hX (xX ). Replace P0′ , P1′ by the following programs R0 , R1 . R0 (a, x) Hardcoded: M̂0 , Ck , µB , µC , KS , qB , qC , dB , dC , LB , LC , ηB , ηC , hB , hC , strB , strC 1. If M̂0 (a) = 0, output ⊥. 2. If LB (x) = ηB , parse (u′B , vB′ ) := strB ⊕ hB (x) and output
qB ⊕ Ck (x) ⊕ ⟨vB′ , a⟩ + dB · diff B (x). 3. If LC (x) = ηC , parse (u′C , vC′ ) := strC ⊕ hC (x) and output
qC ⊕ Ck (x) ⊕ ⟨vC′ , a⟩ + dC · diff C (x).

81

For

X := LX (xX )

4. Output FKS (x) ⊕ Ck (x).

R1 (a, x) Hardcoded: M̂1 , Ck , µB , µC , KS , qB , qC , LB , LC , ηB , ηC , hB , hC , strB , strC 1. If M̂1 (a) = 0, output ⊥. 2. If LB (x) = ηB , parse (u′B , vB′ ) := strB ⊕ hB (x) and output qB ⊕ ⟨u′B , a⟩ · diff B (x). 3. If LC (x) = ηC , parse (u′C , vC′ ) := strC ⊕ hC (x) and output qC ⊕ ⟨u′C , a⟩ · diff C (x). 4. Output FKS (x). The relevant circuits in Hyb5 and Hyb6 have the same functionality. Suppose first that xB ̸= xC . At x = xX , the equality LX (xX ) = ηX holds, while the equality corresponding to the other recipient does not hold by injectivity. Moreover, strX ⊕ hX (xX ) = u∥v. For every a ∈ A + s, it holds that ⟨v, a⟩ = ⟨v, s⟩ = α, and for every a ∈ A⊥ + t, it holds that ⟨u, a⟩ = ⟨u, t⟩ = β. Therefore, the individual outputs of R0 and R1 at xX are exactly the corresponding outputs of P0′ and P1′ . If xB = xC , both equalities hold at the common point, but the Bob equality is evaluated first in both programs. Hence, the programs use the Bob values independently of ∆, exactly as prescribed by Equation (53). At every x ∈ / S, neither equality holds, and the final lines of the programs are evaluated. Thus, the two pairs of programs are functionally equivalent. Therefore, by iO-security, we conclude that Hyb5 and Hyb6 are computationally indistinguishable. Hyb7 : Replace the punctured PRF key with the unpunctured key. Replace KS by K in the final line of R0 , R1 . The relevant circuits have the same functionality, since one of the preceding equality tests holds at every point in S, and FKS (x) = FK (x) for every x ∈ / S. Therefore, by iO-security, we conclude that Hyb6 and Hyb7 are computationally indistinguishable. Hyb8 : Switch the two functions to lossy mode. Replace LB and LC , one at a time, by functions sampled using LF.Genloss (1λ ), and recompute ηX := LX (xX ) after each replacement. Injective/lossy mode indistinguishability implies that Hyb7 and Hyb8 are computationally indistinguishable. Define the auxiliary-information generator (see Definition 39) as follows. The algorithm Aux.Setup(1λ ) $

samples hB , hC ← − H and independent LB , LC ← LF.Genloss (1λ ), and outputs pp := (LB , LC , hB , hC ). On input (pp, A, u, v), the algorithm Aux.Gen runs (zaux , xB , xC , b′B , b′C , wB , wC ) ← Samp(1λ ), sets ∆ := b′B +b′C , computes ηX := LX (xX ) and strX := msg(u, v)⊕hX (xX ) for X ∈ {B, C}, and outputs z1,B := (zaux , ∆, ηB , ηC , strB , strC ),

z2,B := (xB , wB ),

z1,C := ⊥,

z2,C := (xC , wC ).

The simulator Aux.Sim(pp) runs (zaux , xB , xC , b′B , b′C , wB , wC ) ← Samp(1λ ), computes ∆, ηB , ηC , dis$

cards wB , wC , samples independent UB , UC ← − {0, 1}m , and outputs ze1,B := (zaux , ∆, ηB , ηC , UB , UC ) 82

and ze1,C := ⊥. Next we show the statistical simulatability condition for the above auxiliaryinformation generator, as requried in Definition 39. Lemma 14 (Statistical simulation of the pre-split auxiliary information). For every fixed subspace A ≤ V , u ∈ A \ {0}, and v ∈ A⊥ \ {0}, the auxiliary-information algorithms defined above satisfy the statistical simulatability condition in Equation (103) with statistical distance at most ε. Proof of Lemma 14. Let (Zaux , XB , XC , bB , bC , WB , WC ) ← Samp(1λ ) and set ∆ := bB + bC . The variables WB , WC are carried as post-split auxiliary information and do not occur in the pre-split strings. Condition on the descriptions of LB , LC , set ηX := LX (XX ) for every X ∈ {B, C}, and let Z := (∆, ηB , ηC ). Since the descriptions of LB , LC are independent of (Zaux , XB , XC , ∆) and | Supp(Z)| ≤ 21+2ℓimg , the support-size leakage bound for average conditional min-entropy gives e ∞ (XX | Zaux , Z) ≥ λc − 1 − 2ℓimg for every X ∈ {B, C}. H For every fixed (Zaux , Z) = (zaux , z), let cpB (zaux , z), cpC (zaux , z), and cpB,C (zaux , z) denote the collision probabilities of XB , XC , and (XB , XC ), respectively, conditioned on (Zaux , Z) = (zaux , z). For every X ∈ {B, C}, X EZaux ,Z [cpX (Zaux , Z)] ≤ Pr[Zaux = zaux , Z = z] max Pr[XX = x | Zaux = zaux , Z = z] x

zaux ,z c

= 2−H∞ (XX |Zaux ,Z) ≤ 2−(λ −1−2ℓimg ) . e

Moreover, cpB,C (zaux , z) ≤ min{cpB (zaux , z), cpC (zaux , z)} for every (zaux , z). Independence and universality of hB , hC give, for every fixed (Zaux , Z) = (zaux , z), 
 EhB ,hC cp hB (XB ), hC (XC ) | Zaux = zaux , Z = z
≤ 2−2m + 2−m cpB (zaux , z) + cpC (zaux , z) + cpB,C (zaux , z). Averaging over (Zaux , Z) therefore gives 
 EZaux ,Z,hB ,hC cp hB (XB ), hC (XC )
c ≤ 2−2m + 1 + 21−m 2−(λ −1−2ℓimg ) . The collision-probability bound on statistical distance, followed by Jensen’s inequality, gives statistical distance at most q 1 c 22m−(λ −1−2ℓimg ) (1 + 21−m ) ≤ ε, (110) 2 where the last inequality follows from the choice of parameters. Finally, XORing both hash values with the fixed string msg(u, v) does not change statistical distance. Hence the real and simulated pre-split auxiliary-information distributions satisfy the statistical simulatability condition in Definition 39. b b b [ We construct a QPT triplet of adversaries A moe = (A, B, C) for Theorem 21. The algob rithm A receives |As,t ⟩, M̂0 , M̂1 , pp, and the pre-split auxiliary information, from which it parses zaux , ∆, ηB , ηC , strB , strC . It runs the first stage of A on (1λ , zaux ) to obtain (k, µB , µC ) and re$

$

tained state, samples ζ ← − {0, 1}, qB , qC ← − Yλ , and K ← PPRF.Gen(1λ ), sets dB := ζ and dC := ζ + ∆, constructs the two lossy-mode programs from Hyb8 , obfuscates them using iO, and gives ρk := (|As,t ⟩ , R̂0 , R̂1 ) to the continuation of A together with its retained state. When A outputs its two registers, Ab appends a classical copy of ζ to the register sent to Bb and classical b copies of (ζ, ∆) to the register sent to C. 83

After the split, Bb receives (u, v, xB , wB ), runs B on (xB , wB ), and outputs bbB + ζ. The algorithm b C receives (u, v, xC , wC ), runs C on (xC , wC ), and outputs bbC +ζ +∆. Since bB = e+ζ, bC = e+ζ +∆, [ and e = ⟨u, t⟩ + ⟨v, s⟩, the winning event in Hyb8 is identical to the winning event of A moe in the 1 computational Decisional-Coset-MOE experiment. By Theorem 21, Pr[Hyb8 = 1] ≤ 2 + negl(λ). Combining the preceding hybrid transitions and the statistical error ε proves the theorem. Changes for the identical-uniform challenge distribution. For the IDU -generalized UPO special case, we replace the injective/lossy-function and universal-hashing hybrids Hyb6 –Hyb8 , together with Lemma 14, by the NCE-based hybrids of [ABH+ 26, Theorem 5.2]. In particular, for the common uniform challenge point x, we sample one key-robust NCE key, encrypt msg(u, v) under this key, and use the resulting NCE ciphertext and masked key string in both modified programs. NCE correctness and key robustness give the required functionality equivalence to invoke iO security, while the non-committing property gives a simulation of the pre-split information that is independent of (u, v). The preceding puncturable PRF and iO hybrids and the final reduction to computational Decisional-Coset-MOE remain unchanged. Since the required NCE can be instantiated from post-quantum one-way functions, the LWE assumption can be replaced with one-way functions in this case. For completeness, we give the formal proof of the “Moreover” part in Section 9.2.1.

9.2.1

Formal proof of the moreover part of Theorem 23

We need the following primitive. Definition 41 (Key-robust one-time non-committing encryption). A key-robust one-time noncommitting encryption scheme NCE = (NCE.Gen, NCE.Enc, NCE.Dec, NCE.Fake, NCE.Open) with message space {0, 1}ℓNCE−msg and key space {0, 1}ℓNCE−key consists of five PPT algorithms as follows. 1. k ← NCE.Gen(1λ ) : outputs an encryption key k. 2. ct ← NCE.Enc(k, M ) : takes as input a key k and a message M , and outputs a ciphertext ct. 3. M ′ ← NCE.Dec(k, ct) : is deterministic and outputs a message M ′ or ⊥. 4. (ct⋆ , st) ← NCE.Fake(1λ ) : outputs a fake ciphertext and state. 5. k ⋆ ← NCE.Open(st, M ) : takes as input a state and a message, and outputs a key. A key k is good if, for every message M and every k ′ ̸= k, NCE.Dec(k, NCE.Enc(k, M )) = M

and

NCE.Dec(k ′ , NCE.Enc(k, M )) = ⊥.

(111)

A key generated by NCE.Gen is good with overwhelming probability. Non-committing security requires that, for every QPT algorithm that outputs a message M together with quantum auxiliary information R, (R, ct, k) ≈c (R, ct⋆ , k ⋆ ), (112) where k ← NCE.Gen(1λ ) and ct ← NCE.Enc(k, M ) in the first distribution, while (ct⋆ , st) ← NCE.Fake(1λ ) and k ⋆ ← NCE.Open(st, M ) in the second distribution. We may assume that NCE.Open is deterministic by including its random tape in st.

84

Theorem 24 (Key-robust one-time non-committing encryption from iO and one-way functions [ABH+ 26]). Assume the existence of post-quantum polynomially secure iO and post-quantum one-way functions. For every polynomially bounded input length ℓin = ℓin (λ) ∈ ω(log λ), the parameters can be chosen so that there exist n = n(λ) ∈ ω(log λ) and a key-robust one-time non-committing encryption scheme with message space {0, 1}8n and key space {0, 1}ℓNCE−key , where ℓNCE−key ≤ ℓin (λ), satisfying Equations (111) and (112) against QPT distinguishers with quantum auxiliary information. For the proof below, fix n and a key-robust one-time non-committing encryption scheme as guaranteed by Theorem 24. Detailed proof of the moreover part of Theorem 23. Fix a QPT triplet of adversaries against IDU $

$

generalized UPO. The challenger samples x ← − Xλ and b ← − {0, 1}, gives the same point x to both recipients after the split, and uses the generalized punctured circuit that equals µB (x) at x if b = 1 and equals Ck (x) otherwise. Choose n ∈ ω(log λ) and a key-robust one-time non-committing encryption scheme with message length m = 8n and key length ℓNCE−key ≤ ℓin . Parse every point as x = x0 ∥x1 , where |x0 | = ℓNCE−key . Specialize Hyb0 –Hyb5 above to xB = xC = x, bB = bC = b, ∆ = 0, and µB . Thus, after sampling $

$

$

u← − A \ {0}, v ← − A⊥ \ {0}, and ζ ← − {0, 1}, we have b = α + β + ζ, where α = ⟨v, s⟩ and β = ⟨u, t⟩. The puncturable PRF is punctured at the single point x, its value at x is replaced by a uniform $

y, and we sample q ← − Yλ and write y = q ⊕ β · diff(x), where diff(z) := Ck (z) ⊕ µB (z). The two hardcoded values at x are therefore q ⊕ Ck (x) ⊕ (α + ζ) · diff(x) and q ⊕ β · diff(x). Next sample knce ← NCE.Gen(1λ ), ct ← NCE.Enc(knce , msg(u, v)), and set str := knce ⊕ x0 . Replace the two point-hardcoded programs by the following programs, initially using the punctured key K{x} in their last lines. S0 (a, z) Hardcoded: M̂0 , Ck , µB , K{x} , q, ζ, ct, str, x1 1. If M̂0 (a) = 0, output ⊥. 2. Parse z = z0 ∥z1 , set kz := str ⊕ z0 , and compute Mz := NCE.Dec(kz , ct). 3. If z1 = x1 and Mz ̸= ⊥, parse (u′ , v ′ ) := Mz and output q ⊕ Ck (z) ⊕ (⟨v ′ , a⟩ + ζ) · diff(z). 4. Output FK{x} (z) ⊕ Ck (z).

S1 (a, z) Hardcoded: M̂1 , Ck , µB , K{x} , q, ct, str, x1 1. If M̂1 (a) = 0, output ⊥. 2. Parse z = z0 ∥z1 , set kz := str ⊕ z0 , and compute Mz := NCE.Dec(kz , ct). 3. If z1 = x1 and Mz ̸= ⊥, parse (u′ , v ′ ) := Mz and output q ⊕ ⟨u′ , a⟩ · diff(z). 4. Output FK{x} (z). Condition on the overwhelmingly likely event that knce is good. At z = x, kz = str ⊕ x0 = knce , so correctness gives Mz = msg(u, v). Hence, for a ∈ A + s, S0 returns q ⊕ Ck (x) ⊕ (α + ζ) · diff(x), 85

and for a ∈ A⊥ + t, S1 returns q ⊕ β · diff(x). If z ̸= x, either z1 ̸= x1 , or z0 ̸= x0 and kz ̸= knce , in which case key robustness gives Mz = ⊥. Thus the relevant circuits have the same functionality, and two applications of iO-security justify the replacement. We then replace K{x} by the full puncturable PRF key K in the last line of each program. The relevant circuits again have the same functionality, and this replacement follows from iO-security. Since x0 is uniform, the same distribution can be sampled by first generating knce and ct, $

$

− {0, 1}ℓin −ℓNCE−key , and finally setting x0 := str ⊕ knce . then sampling str ← − {0, 1}ℓNCE−key and x1 ← Apply non-committing security to replace (ct, knce ) by (ct⋆ , k ⋆ ), where (ct⋆ , st) ← NCE.Fake(1λ ) and k ⋆ := NCE.Open(st, msg(u, v)). Except with negligible probability, NCE.Dec(k ⋆ , ct⋆ ) = msg(u, v); otherwise, testing this equality would distinguish the fake/open distribution from the real correct distribution. In the resulting hybrid, the values (ct⋆ , str, x1 ) given before the split are independent of (u, v). We reduce this hybrid to the computational Decisional-Coset-MOE experiment without auxiliary information. The algorithm Ab receives |As,t ⟩, M̂0 , M̂1 , runs the first stage of A to obtain (k, µB , µC ), $

$

$

$

samples (ct⋆ , st) ← NCE.Fake(1λ ), str ← − {0, 1}ℓNCE−key , x1 ← − {0, 1}ℓin −ℓNCE−key , q ← − Yλ , ζ ← − {0, 1}, λ ⋆ and K ← PRF.Gen(1 ). It constructs and obfuscates the two programs S0 , S1 with ct and the full key K, gives the resulting UPO state to the continuation of A, and appends classical copies of (st, str, x1 , ζ) to both output registers. b Cb receives (u, v). It computes M := msg(u, v), k ⋆ := NCE.Open(st, M ), After the split, each of B, ⋆ x0 := str ⊕ k , and x := x0 ∥x1 , runs the corresponding original recipient on x, and adds ζ to its output. Since the IDU challenge bit is b = ⟨u, t⟩ + ⟨v, s⟩ + ζ, both original recipients output b if and only if both Bb and Cb output ⟨u, t⟩+⟨v, s⟩. Therefore, Corollary 3 bounds the winning probability by 1 2 + negl(λ). Combining the puncturable PRF, iO, non-committing encryption, and negligible badkey errors proves IDU -generalized UPO security from post-quantum iO and post-quantum one-way functions.

86

10

Applications of Correlated UPO to Copy-Protection

We recall the UPO-to-copy-protection implications of [AB24, ABH+ 26] and adapt them to correlated challenge distributions. Throughout this subsection, Circ = {Ck : k ∈ Kλ } is a keyed circuit class and DCirc is induced by an efficiently samplable key distribution DK : sampling C ← DCirc (1λ ) means sampling k ← DK (1λ ) and setting C := Ck . The key, and hence C, is sampled independently of the corresponding challenge sampler. Definition 42 (Two-point unpredictability-style puncturing security, adapted from [ABH+ 26]). Let Circ be a circuit class with output space Yλ = {0, 1}m(λ) . The class Circ is two-point unpredictabilitystyle puncturable with respect to (DCirc , SampCP ) if there exists a deterministic PPT algorithm Puncture such that, on input a circuit C ∈ Circλ and a set S ⊆ Xλ of size at most two, it outputs a circuit C \S : Xλ → Yλ satisfying ( 0m(λ) , x ∈ S, \S C (x) = (113) C(x), x ∈ / S. All circuits compared below are padded to the same size. Moreover, for every QPT adversary D, there exists a negligible function negl such that   C ← DCirc (1λ ),  (xB , xC ) ← SampCP (1λ ),  2     ≤ 1 − 1 − 2−m(λ) + negl(λ). S := {x , x }, Pr  y b = C(x ) ∨ y b = C(x ) : B C B B C C     C \S ← Puncture(C, S), (b yB , ybC ) ← D(C \S , xB , xC )

(114)

Definition 43 (Two-point pseudorandomness-style puncturing security with correlated challenges, adapted from [ABH+ 26]). Let Circ be a deterministic circuit class with output space Yλ = {0, 1}m(λ) . We say that Circ is two-point pseudorandomness-style puncturable with respect to (DCirc , SampPRCP ) if it has a deterministic PPT puncturing algorithm satisfying Equation (113), and the following two ensembles are computationally indistinguishable. Sample C ← DCirc (1λ ) and (xB , xC , bB , bC ) ← SampPRCP (1λ ), and let S := {xB , xC }. In the first ensemble, output (C \S , xB , xC , bB , bC , C(xB ), C(xC )). (115) $

In the second ensemble, sample an independent Ux ← − Yλ for every distinct x ∈ S, and output (C \S , xB , xC , bB , bC , UxB , UxC ).

(116)

Given a UPO scheme Π = (Obf, Eval), define CPΠ by CopyProtect(1λ , C) := Obf(1λ , C) and by letting CPΠ .Eval(ρ, x) run (ρ′ , y) ← Eval(ρ, x) and output y. Whenever we invoke UPO security below, the supported circuit class is understood to contain the base circuits and the circuits produced by the relevant puncturing and programming algorithms, padded to a common size. For Definition 42, the corresponding generalized-puncturing algorithm first computes C \S ← Puncture(C, S) and then programs µB (xB ) and, if xC ̸= xB , µC (xC ), using Bob priority on a collision. Thus the punctured event of the UPO game uses the same puncturing procedure as the security assumption. We first adapt the non-oracular point-function application of generalized UPO to arbitrary high-min-entropy point distributions.

87

Theorem 25 (Copy protection for point functions from IDD -generalized UPO, adapted from [AB24, Theorem 89 and Corollary 90]). Let D = {Dλ }λ∈N be a QPT-samplable distribution over Xλ = e ∞ (Dλ ) ∈ ω(log λ). Suppose that there is a UPO scheme for polynomial{0, 1}ℓin (λ) such that H size circuits satisfying IDD -generalized UPO security and iO-security. Then point functions whose point is sampled according to Dλ have a copy-protection scheme satisfying identical-challenge pointfunction security with respect to D from Definition 32. Proof. We adapt the proof of [AB24, Theorem 89]. Let C0 be the all-zero circuit and let Gy be obtained by programming C0 to output one at y. The iO-security of UPO replaces an obfuscation of Py by an obfuscation of the functionally equivalent circuit Gy . In the independent event, replace the desired output by zero. This changes success only when the independent samples x, y ← Dλ coincide, which occurs with probability X e Pr[Dλ = x]2 ≤ 2−H∞ (Dλ ) = negl(λ). (117) cp(Dλ ) := x

The switch from an obfuscation of Gy to an obfuscation of C0 in the independent event is precisely the guarantee given by IDD -generalized UPO security with the constant-one replacement circuits. After this switch, both events have challenge-point marginal Dλ , and the final experiment is the IDD generalized UPO experiment. Thus every adversary succeeds with probability at most 1/2+negl(λ). By Lemma 7, this implies the required trivial-adversary comparison. The uniform specialization is exactly [AB24, Corollary 90]. Corollary 4 (Copy-protection for point functions). Assume post-quantum polynomially secure iO and the quantum hardness of LWE. For every constant c > 0 and every QPT-samplable distribution e ∞ (Dλ ) ≥ λc , point functions whose point is sampled ensemble D = {Dλ }λ∈N over Xλ satisfying H according to Dλ have a copy-protection scheme satisfying identical-challenge point-function security with respect to D. Moreover, when Dλ is uniform over {0, 1}ℓin (λ) and ℓin ∈ ω(log λ), LWE can be replaced with post-quantum one-way functions. Proof. The first claim follows from Theorems 18 and 23 and Lemma 6, which give a UPO satisfying IDD -generalized UPO security and iO-security, and Theorem 25. The uniform claim uses the “Moreover” part of Theorem 23 together with the add-iO transformation of [ABH+ 26, Lemma 3.16]. Corollary 5 (Copy protection for k-point functions). Assume post-quantum polynomially secure iO (k) and the quantum hardness of LWE. Let k = k(λ) be polynomially bounded, and let D(k) = {Dλ }λ∈N e ∞ (D(k) ) ≥ λc for be a QPT-samplable distribution over the k-element subsets of Xλ such that H λ (k)

$

some constant c > 0. Let Dλpt be the distribution obtained by sampling S ← Dλ and then x ← − S, ′ pt c ′ e and suppose that H∞ (Dλ ) ≥ λ for some constant c > 0. Suppose moreover that the resulting distribution over k-point functions is preimage-samplable in the sense of [AB24, Definition 84], with the uniform challenge distribution in that definition replaced by Dλpt . Then the k-point functions sampled according to D(k) have a copy-protection scheme satisfying the identical-challenge security (k) (see Remark 4). If Dλ is uniform over the k-element subsets of Xλ and k(λ)/|Xλ | is negligible, then LWE can be replaced with post-quantum one-way functions. Proof. For every fixed x ∈ Xλ ,   pt e Pr [x ∈ S] = k(λ) Pr Dλpt = x ≤ k(λ)2−H∞ (Dλ ) = negl(λ), (k)

S←Dλ

88

(118)

so the sampled function class is evasive. Under the stated preimage-samplability assumption, the proof of [AB24, Theorem 89] applies after replacing each uniform challenge point by a sample from Dλpt . By Theorems 18 and 23 and Lemma 6, the stated assumptions give the required IDDpt generalized UPO and iO-security. The uniform specialization is the setting of [AB24, Theorem 85 and Corollary 90], and the “Moreover” part of Theorem 23 together with the add-iO transformation of [ABH+ 26, Lemma 3.16] supplies the required IDU -generalized UPO from one-way functions. The trivial success probability is given by Equation (64). Theorem 26 (Copy protection for compute-and-compare functions). Assume post-quantum polynomially secure iO and the quantum hardness of LWE. Let Samp be a QPT algorithm that samples (f, y) ← Samp(1λ ), where f : Xλ → Zλ is a polynomial-size circuit, Zλ = {0, 1}ℓcc (λ) , and y ∈ Zλ . e ∞ (Y | F ) ≥ λc for some constant c > 0. Let (F, Y ) denote its output distribution and suppose that H Fix a family of distributions {Qf,z }f,z as in Definition 33, and suppose that the resulting identicalchallenge experiment is efficiently realizable. Then the compute-and-compare functions sampled by Samp have a copy-protection scheme satisfying the identical-challenge security of Definition 33. Moreover, if Y conditioned on F = f is uniform over Zλ for every f in the support of F , then the LWE assumption can be replaced with post-quantum one-way functions. Proof. Let Π be a UPO, guaranteed by Theorems 18 and 23 for any polynomial input and output length circuit class, and let CPPF be the point-function scheme obtained from Π by the construction used in Theorem 25. Following the generic transformation of [CMP24, Construction 4 and Theorem 7], define ρy ← CopyProtectPF (1λ , Py ),

CopyProtectCC (1λ , CCf,y ) := (f, ρy ),

(119)

and EvalCC ((f, ρy ), x) := EvalPF (ρy , f (x)).

(120)

Correctness follows from CCf,y (x) = Py (f (x)). For every f in the support of F , let Df denote the conditional distribution of Y given F = f . Consider the correlated-UPO sampler that samples (f, z) ← Samp(1λ ),

x ← Qf,z ,

$

b← − {0, 1},

(121)

(zaux , xB , xC , bB , bC , wB , wC ) := (f, z, z, b, b, x, x).

(122)

where the second output of Samp is denoted by z, and outputs

This sampler satisfies Definition 26: the shared bit is uniform conditioned on (f, z, x) and e ∞ (z | f ) = H e ∞ (Y | F ) ≥ λc . H We adapt the proof of Theorem 25. Let C0 be the all-zero circuit and let Gy be obtained by programming C0 to output one at y. The iO-security of UPO replaces an obfuscation of Py by an obfuscation of the functionally equivalent circuit Gy . In the event b = 0, replace the desired output by zero. This changes success only if the independent samples y, z ← Df coincide. Averaged over f , this occurs with probability Ef [cp(Df )] ≤ 2−H∞ (Y |F ) = negl(λ). e

89

(123)

Next, in the event b = 0, replace the obfuscation of Gy by an obfuscation of C0 . To justify this change, consider the correlated-UPO sampler that samples (f, y) ← Samp(1λ ), a uniform bit $

d← − {0, 1}, and outputs (zaux , xB , xC , bB , bC , wB , wC ) := (f, y, y, d, d, ⊥, ⊥).

(124)

e ∞ (y | f ) ≥ λc . Correlated UPO security therefore implies that This is a valid sampler because H the ensembles consisting of (f, Obf(Gy )) and (f, Obf(C0 )) are computationally indistinguishable: otherwise, RA runs the distinguisher and sends a classical copy of its output to each of RB and RC . In the event b = 0, the fresh value z ← Df and the point x ← Qf,z are independent of y conditioned on f and are efficiently sampleable. Hence adjoining (z, x) and applying the QPT algorithms of the compute-and-compare adversary preserves this indistinguishability. After this change, the resulting experiment is exactly the correlated-UPO experiment for the first sampler (Equation (122)) displayed above. The reduction RA , after receiving f and the UPO state, gives (f, ρ) to A and forwards its two output registers; after the split, RB and RC ignore the common UPO point z and give the common post-split auxiliary string x to B and C, respectively. When the shared bit is zero, the state protects C0 and both recipients must output zero. When the shared bit is one, the common UPO challenge point is z, the state protects Gz = Pz , and both recipients must output one. Since x ← Qf,z and hence f (x) = z, their target value is CCf,y (x) = Py (z).

(125)

Thus correlated UPO security implies that every adversary in the last experiment succeeds with probability at most 1/2 + negl(λ). Therefore, we conclude that the success probability of the adversaries in the original compute-and-compare copy protection experiment is at most 1/2 + negl′ (λ) for some negligible function negl′ (λ). Combining the last conclusion with the fact that the trivial adversarial strategy of outputting 1 (i.e., A sends the copy-protected state to B and C always outputs 1) has success probability 1 1 1 1 e + Ef [cp(Df )] ≤ + 2−H∞ (Y |F ) , 2 2 2 2

(126)

which is 1/2 plus some negligible function, we conclude that the trivial success probability for the experiment is 12 plus some negligible function. Hence, by the preceding argument, we conclude that the success probability for any adversary is upper bounded by the trivial success probability upto negligible corrections (see Definition 33), which concludes the proof of the security. The “Moreover” clearly follows by noting that in this special case, we only need correlated UPO secure against identical uniform challenge distribution and then replacing the general statement of Theorem 23 in the above proof with the “Moreover” part of Theorem 23. Next, we turn our attention to unpredictability-style copy protection for puncturable functionalities. Theorem 27 (Unpredictability-style copy protection from UPO, adapted from [AB24, Theorem 57]). Let DX be the joint distribution induced by SampCP , let m ∈ ω(log λ), and let Circ be two-point unpredictability-style puncturable with respect to (DCirc , SampCP ). If Π satisfies DX generalized UPO security, then CPΠ satisfies unpredictability-style copy-protection security with respect to (DCirc , SampCP ) (see Definition 31).

90

Proof. We adapt the reduction of [AB24, Theorem 57] while preserving the sampled joint pair. In summary, the argument below uses the challenge pair as a jointly sampled object, and hence permits arbitrary correlation among challenge points. Fix a copy-protection adversary, and construct a generalized-UPO adversary using the constant replacement circuits µX (z) := 0m(λ) for X ∈ {B, C}. Let p0 be the probability that both recipients recover their respective values when the UPO challenge bit is zero, and let p1 be the probability that neither recipient recovers its respective value when the challenge bit is one. By construction, p0 is exactly the success probability in the copy-protection experiment (see Definition 31). In the punctured event, the puncturing guarantee Equation (114) yields  2 p1 ≥ 1 − 2−m(λ) − negl(λ).

(127)

The reduction outputs zero precisely upon a correct prediction and one otherwise, so generalizedUPO security gives (p0 + p1 )/2 ≤ 1/2 + negl(λ). Therefore,  2 p0 ≤ 1 − 1 − 2−m(λ) + negl(λ),

(128)

which is negligible in λ. Corollary 6 (Unpredictability-style copy protection with correlated challenges). Assume postquantum polynomially secure iO and the quantum hardness of LWE. Let c > 0, let SampCP be any QPT sampler whose two challenge-point marginals have min-entropy at least λc , and let Circ have output length m ∈ ω(log λ) and satisfy Definition 42. Then there exists a copy-protection scheme for Circ satisfying unpredictability-style security for (DCirc , SampCP ). Proof. Apply Theorem 23 and Lemma 6 to the joint distribution induced by SampCP , and then apply Theorem 27. We note that the above result can be strengthened to oracular security when the two challenge points are identical and are sampled from a high-min-entropy distribution. Let D = {Dλ }λ∈N be a QPT-samplable distribution ensemble over Xλ . We write SampIDD for the sampler that samples x ← Dλ and outputs (xB , xC ) := (x, x). e ∞ (Dλ ) ∈ Theorem 28 (Oracular unpredictability-style copy protection for identical challenges). Let H ω(log λ) and m ∈ ω(log λ). Suppose that Circ is two-point unpredictability-style puncturable with respect to (DCirc , SampIDD ) and that Π satisfies IDD -generalized UPO security. Then CPΠ satisfies oracular unpredictability-style copy-protection security with respect to (DCirc , SampIDD ). Proof. We combine the reduction above with the oracle-hybrid argument of [ABH+ 26, Remark 8.3], specialized to one common point x ← Dλ . Let Gx be the punctured circuit, which agrees with C off x and outputs 0m(λ) at x. Conditioned on the event that the UPO challenge bit is one, suppose that A makes at most q = q(λ) oracle queries, and let W be their total query weight on x when A receives Obf(Gx ) but still has oracle access to C. We claim that E[W ] is negligible. e To see this, let δλ := 2−H∞ (Dλ ) . For q ≥ 1, construct an IDD -generalized UPO adversary R = (RA , RB , RC ) that samples k ← DK (1λ ), submits k together with the constant replacement circuits µB (z) = µC (z) := 0m(λ) , and uses C := Ck to simulate A’s C-oracle. The algorithm RA $

chooses i ← − [q], measures the input of the i-th query if it occurs, sets x′ := ⊥ otherwise, and sends x′ to both reduction recipients. Upon receiving the common challenge x, each of RB and RC outputs one if x′ = x and zero otherwise. Conditioned on the event that the UPO challenge 91

bit is zero, x′ is independent of the fresh x ← Dλ , so both reduction recipients are correct with probability at least 1 − δλ . Conditioned on the event that the UPO challenge bit is one, both are correct with probability E[W ]/q. Therefore, IDD -generalized UPO security gives   1 E[W ] 1 1 − δλ + ≤ + negl(λ), (129) 2 q 2 and hence E[W ] ≤ qδλ + negl(λ) = negl(λ). The case q = 0 is immediate. By the BBBV query bound [ABH+ 26, Theoremp 2.1], changing A’s oracle from C to Gx changes the adversarial success probability by at most O( qE[W ]) = negl(λ). Both post-split recipient \x oracles are already identical, since C \x = Gx . The puncturing reduction can consequently simulate the punctured event using Gx , and the same p0 , p1 calculation as above gives negligible piracy success and hence the required trivial-strategy bound. Corollary 7 (Oracular unpredictability-style copy protection for identical challenges). Assume post-quantum polynomially secure iO and the quantum hardness of LWE. Let c > 0 be a constant, e ∞ (Dλ ) ≥ λc , and let Circ have output length m ∈ ω(log λ) and let D be QPT-samplable with H satisfy Definition 42 with respect to (DCirc , SampIDD ). Then there exists a copy-protection scheme for Circ satisfying oracular unpredictability-style security with respect to (DCirc , SampIDD ). Proof. Apply Theorem 23 and Lemma 6 to IDD and then apply Theorem 28. For the OWF-based instantiation, we retain the identical-uniform distribution, since the “Moreover” part of Theorem 23 establishes IDU -generalized UPO security. Corollary 8 (Identical-uniform oracular unpredictability-style copy protection). Assume postquantum polynomially secure iO and post-quantum one-way functions. Let ℓin , m ∈ ω(log λ), and suppose that Circ is two-point unpredictability-style puncturable for the identical-uniform sampler. Then there exists a copy-protection scheme for Circ satisfying oracular unpredictability-style security for that sampler. Proof. Combine the “Moreover” part of Theorem 23 with Theorem 28, taking Dλ to be uniform over Xλ . Next, we consider applications to pseudorandomness-style copy protection. Theorem 29 (Pseudorandomness-style copy protection from correlated UPO, adapted from [ABH+ 26, Theorem 7.4]). Let SampPRCP be a correlated pseudorandomness-style challenge sampler, and let Circ satisfy two-point pseudorandomness-style puncturing security for (DCirc , SampPRCP ). Suppose that Π satisfies correlated-UPO security for SampPRCP and iO-security. Then CPΠ satisfies pseudorandomness-style copy-protection security for (DCirc , SampPRCP ). Proof. We adapt the non-oracular portion of [ABH+ 26, Theorem 7.4]. Since the challenge tuple is independent of the sampled circuit and of the adversary’s pre-challenge view, we may sample it at the outset and withhold it until after the split without changing the experiment. For a sampled tuple let S := {xB , xC } contain each distinct point once. Define the effective bit dxB := bB and, when xC ̸= xB , dxC := bC , and let T := {x ∈ S : dx = 1}. This is precisely the Bob-priority $

convention on a collision. Write Rx := C(x), and let Ux , Yx ← − Yλ be independent for each x ∈ S. \S \S For values v = (vx )x∈S , let Program(C , v) agree with C off S and output vx at x ∈ S.

92

First, iO-security replaces Obf(C) by Obf(Program(C \S , R)). We use the following consequence of two-point pseudorandomness-style puncturing: for every T ⊆ S efficiently determined from the public tuple (xB , xC , bB , bC ), (C \S , RS\T , RT ) ≈c (C \S , RS\T , UT ).

(130)

Indeed, the real and fully uniform ensembles are indistinguishable by Definition 43. Applying to both the map that retains the coordinates outside T and freshly resamples those in T shows that the mixed and fully uniform ensembles are indistinguishable. The triangle inequality gives Equation (130). The sampled bits are retained throughout, so this argument also permits arbitrary correlation between the points and bits. Apply Equation (130) to replace the protected values RT by UT , retaining the independent challenge values YT as auxiliary information. Swapping the names of the independent uniform families UT , YT is distribution preserving. Apply Equation (130) a second time, now to replace the uniform challenge values by RT while retaining the independently programmed values as auxiliary information. Thus the classical challenge is C(xX ) for both recipients, while the protected circuit is programmed with independent uniform values exactly at the points whose effective bit is one. Finally, iO-security replaces this circuit by the canonical correlated-punctured circuit. $

For completeness, the final correlated-UPO reduction samples k ← DK and independent uB , uC ← − Yλ before sending (k, µB , µC ) to the challenger, where µX is the constant-uX circuit. After the split, recipient X computes Ck (xX ) and feeds (xX , Ck (xX )) to its copy-protection recipient. If the points collide, uC is unused by Bob priority. Hence the simulated experiment is exactly the final hybrid, and correlated-UPO security bounds its success by 1/2 + negl(λ). No oracle-switch hybrid is used, so no independence between xB and xC is required. Corollary 9 (Pseudorandomness-style copy protection with correlated challenges). Assume postquantum polynomially secure iO and the quantum hardness of LWE. Let c > 0, let SampPRCP have point marginals of min-entropy at least λc , and suppose that Circ satisfies Definition 43. Then Circ has a copy-protection scheme satisfying pseudorandomness-style security for (DCirc , SampPRCP ). Proof. Combine Theorems 18 and 23 with Theorem 29. $

− {0, 1} For the oracular pseudorandomness-style result, let Samppr IDD sample x ← Dλ and b ← and output (xB , xC , bB , bC ) := (x, x, b, b). (131) Theorem 30 (Oracular pseudorandomness-style copy protection for identical challenges, adapted e ∞ (Dλ ) ∈ ω(log λ). Suppose that Circ is two-point pseudorandomnessfrom [ABH+ 26, Theorem 7.4]). Let H pr style puncturable for (DCirc , SampIDD ) and that Π satisfies IDD -generalized UPO security and iOsecurity. Then CPΠ satisfies oracular pseudorandomness-style copy-protection security for (DCirc , Samppr IDD ). Proof. Specialize the hybrids of [ABH+ 26, Theorem 7.4] to xB = xC = x ← Dλ and bB = bC = b. The programming and puncturing hybrids use one shared uniform value. Since the protected circuit and C differ only at x, the punctured oracles given to B and C are identical in every corresponding hybrid, and hence the cross-point oracle switches of [ABH+ 26, Claim 7.5] are unnecessary. It remains to justify the oracle switch for A. Let q = q(λ) be a polynomial upper bound on the number of its oracle queries and let W be their total query weight on x immediately before this switch. The case q = 0 is immediate, so suppose q ≥ 1. In the initial experiment, x is sampled

93

independently of A’s pre-challenge view. Thus, if an index is sampled uniformly from [q] and the input of that query is measured to obtain x′ , with x′ := ⊥ if the query does not occur, then   e Pr x′ = x ≤ 2−H∞ (Dλ ) = negl(λ).

(132)

The preceding programming and puncturing hybrids remain indistinguishable when this measurement is included. In the hybrid immediately before the oracle switch, the same test succeeds with probability E[W ]/q. Therefore, exactly as in [ABH+ 26, Claim 7.6], E[W ] ≤ q · 2−H∞ (Dλ ) + negl(λ) = negl(λ). e

(133)

The BBBV query bound [ABH+ 26, Theorem 2.1] then changes the oracle between C and the programmed circuit at negligible cost. The last iO hybrid replaces the programmed circuit by the functionally equivalent circuit produced by the generalized-puncturing algorithm. The resulting experiment is exactly the IDD -generalized UPO experiment, and its winning probability is at most 1/2 + negl(λ). We remark that for independent high-min-entropy challenge points with a common challenge bit, the corresponding oracular pseudorandomness-style result is already shown in [ABH+ 26, Theorem 7.4], and the oracular unpredictability-style result follows from [ABH+ 26, Theorem 8.1 and Remark 8.3]. Next Theorem 30 combined with our feasibility result for UPO (Theorem 23) gives us the following immediate corollaries. Corollary 10 (Oracular pseudorandomness-style copy protection for identical challenges). Assume post-quantum polynomially secure iO and the quantum hardness of LWE. Let c > 0 be a constant, e ∞ (Dλ ) ≥ λc , and suppose that Circ is two-point pseudorandomnesslet D be QPT-samplable with H style puncturable for (DCirc , Samppr IDD ). Then there exists a copy-protection scheme for Circ satisfying oracular pseudorandomness-style security for (DCirc , Samppr IDD ). Proof. Combine Theorems 18 and 23 and Lemma 6 with Theorem 30. For the OWF-based instantiation, we again retain identical-uniform challenges. Corollary 11 (Identical-uniform oracular pseudorandomness-style copy protection). Assume postquantum polynomially secure iO and post-quantum one-way functions. Let ℓin ∈ ω(log λ), and suppose that Circ is two-point pseudorandomness-style puncturable for (DCirc , Samppr IDU ). Then there exists a copy-protection scheme for Circ satisfying oracular pseudorandomness-style security for (DCirc , Samppr IDU ). Proof. The “Moreover” part of Theorem 23 gives IDU -generalized UPO security. Add iO-security using [ABH+ 26, Lemma 3.16], and apply Theorem 30 with Dλ uniform over Xλ . Corollary 12 (Oracular pseudorandomness-style copy protection for PRFs). Assume post-quantum polynomially secure iO and post-quantum one-way functions. Then there exists a puncturable PRF family on every domain {0, 1}ℓin (λ) with ℓin ∈ ω(log λ) having a copy-protection scheme satisfying oracular pseudorandomness-style security for Samppr IDU . Proof. Post-quantum one-way functions imply post-quantum puncturable PRFs. Since the identical sampler yields the singleton set S = {x}, ordinary puncturable-PRF security gives Definition 43; apply Corollary 11.

94

References [Aar09]

Scott Aaronson. Quantum copy-protection and quantum money. In 24th Annual IEEE Conference on Computational Complexity, pages 229–242, 2009.

[Aar16]

Scott Aaronson. The complexity of quantum states and transformations: From quantum money to black holes, 2016.

[AB24]

Prabhanjan Ananth and Amit Behera. A modular approach to unclonable cryptography. In Advances in Cryptology – CRYPTO 2024, page 3–37. Springer Nature Switzerland, 2024.

[ABH+ 26]

Prabhanjan Ananth, Amit Behera, Zikuan Huang, Fuyuki Kitagawa, and Takashi Yamakawa. Copy-protection from unclonable puncturable obfuscation, revisited. In Advances in Cryptology – EUROCRYPT 2026, page 541–570. Springer Nature Switzerland, 2026.

[AC12]

Scott Aaronson and Paul Christiano. Quantum money from hidden subspaces. Cryptology ePrint Archive, Report 2012/171, 2012.

[AK21]

Prabhanjan Ananth and Fatih Kaleoglu. Unclonable encryption, revisited. In Kobbi Nissim and Brent Waters, editors, TCC 2021: 19th Theory of Cryptography Conference, Part I, volume 13042 of Lecture Notes in Computer Science, pages 299–329, Raleigh, NC, USA, November 8–11, 2021. Springer, Cham, Switzerland.

[AKL+ 22]

Prabhanjan Ananth, Fatih Kaleoglu, Xingjian Li, Qipeng Liu, and Mark Zhandry. On the feasibility of unclonable encryption, and more. In Yevgeniy Dodis and Thomas Shrimpton, editors, Advances in Cryptology – CRYPTO 2022, Part II, volume 13508 of Lecture Notes in Computer Science, pages 212–241, Santa Barbara, CA, USA, August 15–18, 2022. Springer, Cham, Switzerland.

[AKL23]

Prabhanjan Ananth, Fatih Kaleoglu, and Qipeng Liu. Cloning games: A general framework for unclonable primitives. In Helena Handschuh and Anna Lysyanskaya, editors, Advances in Cryptology – CRYPTO 2023, Part V, volume 14085 of Lecture Notes in Computer Science, pages 66–98, Santa Barbara, CA, USA, August 20–24, 2023. Springer, Cham, Switzerland.

[AKY25a]

Prabhanjan Ananth, Fatih Kaleoglu, and Henry Yuen. Simultaneous haar indistinguishability with applications to unclonable cryptography. In Raghu Meka, editor, ITCS 2025: 16th Innovations in Theoretical Computer Science Conference, volume 325, pages 7:1–7:23, New York, NY, USA, January 7–10, 2025. Leibniz International Proceedings in Informatics (LIPIcs).

[AKY25b]

Prabhanjan Ananth, Fatih Kaleoglu, and Henry Yuen. Simultaneous haar indistinguishability with applications to unclonable cryptography. In Raghu Meka, editor, 16th Innovations in Theoretical Computer Science Conference, ITCS 2025, Columbia University, New York, NY, USA, January 7-10, 2025, volume 325 of LIPIcs, pages 7:1–7:23. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025.

[ALL+ 21]

Scott Aaronson, Jiahui Liu, Qipeng Liu, Mark Zhandry, and Ruizhe Zhang. New approaches for quantum copy-protection. In Tal Malkin and Chris Peikert, editors,

95

Advances in Cryptology – CRYPTO 2021, Part I, volume 12825 of Lecture Notes in Computer Science, pages 526–555, Virtual Event, August 16–20, 2021. Springer, Cham, Switzerland. [AS26]

Prabhanjan Ananth and Amit Sahai. Unconditional unclonable encryption, 2026.

[BBC26]

Archishna Bhattacharyya, Anne Broadbent, and Eric Culf. Statistically secure uncloneable encryption of arbitrary messages, 2026.

[BDF26]

Pierre Botteron, Sébastien Designolle, and Omar Fawzi. Pauli encodings & unclonable encryption, 2026.

[BL20]

Anne Broadbent and Sébastien Lord. Uncloneable quantum encryption via oracles. volume 158, pages 4:1–4:22. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2020.

[BPW16]

Nir Bitansky, Omer Paneth, and Daniel Wichs. Perfect structure on the edge of chaos trapdoor permutations from indistinguishability obfuscation. In Eyal Kushilevitz and Tal Malkin, editors, TCC 2016-A: 13th Theory of Cryptography Conference, Part I, volume 9562 of Lecture Notes in Computer Science, pages 474–502, Tel Aviv, Israel, January 10–13, 2016. Springer Berlin Heidelberg, Germany.

[ÇG26]

Alper Çakan and Vipul Goyal. How to copy-protect malleable-puncturable cryptographic functionalities under arbitrary challenge distributions: A unified solution to quantum protection. In Advances in Cryptology – EUROCRYPT 2026, pages 481–509. Springer Nature Switzerland, 2026.

[CGLZR23] Alper Cakan, Vipul Goyal, Chen-Da Liu-Zhang, and João Ribeiro. Unbounded leakageresilience and intrusion-detection in a quantum world. Cryptology ePrint Archive, Report 2023/410, 2023. [CHV23]

Céline Chevalier, Paul Hermouet, and Quoc-Huy Vu. Towards unclonable cryptography in the plain model. Cryptology ePrint Archive, Report 2023/1825, 2023.

[CLLZ21]

Andrea Coladangelo, Jiahui Liu, Qipeng Liu, and Mark Zhandry. Hidden cosets and applications to unclonable cryptography. In Tal Malkin and Chris Peikert, editors, Advances in Cryptology – CRYPTO 2021, Part I, volume 12825 of Lecture Notes in Computer Science, pages 556–584, Virtual Event, August 16–20, 2021. Springer, Cham, Switzerland.

[CMP20]

Andrea Coladangelo, Christian Majenz, and Alexander Poremba. Quantum copyprotection of compute-and-compare programs in the quantum random oracle model. Cryptology ePrint Archive, Report 2020/1194, 2020.

[CMP24]

Andrea Coladangelo, Christian Majenz, and Alexander Poremba. Quantum copyprotection of compute-and-compare programs in the quantum random oracle model. Quantum, 8:1330, May 2024.

[CV22]

Eric Culf and Thomas Vidick. A monogamy-of-entanglement game for subspace coset states. Quantum, 6:791, 2022.

[GM82]

Shafi Goldwasser and Silvio Micali. Probabilistic encryption and how to play mental poker keeping secret all partial information. In 14th Annual ACM Symposium on 96

Theory of Computing, pages 365–377, San Francisco, CA, USA, May 5–7, 1982. ACM Press. [GM84]

Shafi Goldwasser and Silvio Micali. Probabilistic encryption. Journal of Computer and System Sciences, 28(2):270–299, 1984.

[Gol01]

Oded Goldreich. Foundations of Cryptography. Cambridge University Press, 2001.

[Gol04]

Oded Goldreich. Foundations of Cryptography. Cambridge University Press, 2004.

[GZ20]

Marios Georgiou and Mark Zhandry. Unclonable decryption keys. Cryptology ePrint Archive, Report 2020/877, 2020.

[KN23]

Fuyuki Kitagawa and Ryo Nishimaki. One-out-of-many unclonable cryptography: Definitions, constructions, and more. In Guy N. Rothblum and Hoeteck Wee, editors, TCC 2023: 21st Theory of Cryptography Conference, Part IV, volume 14372 of Lecture Notes in Computer Science, pages 246–275, Taipei, Taiwan, November 29 – December 2, 2023. Springer, Cham, Switzerland.

[KY25]

Fuyuki Kitagawa and Takashi Yamakawa. Foundations of single-decryptor encryption. In Theory of Cryptography Conference, pages 166–197. Springer, 2025.

[NC10]

Michael A. Nielsen and Isaac L. Chuang. Quantum Computation and Quantum Information: 10th Anniversary Edition. Cambridge University Press, 2010.

[SW14]

Amit Sahai and Brent Waters. How to use indistinguishability obfuscation: deniable encryption, and more. In David B. Shmoys, editor, 46th Annual ACM Symposium on Theory of Computing, pages 475–484, New York, NY, USA, May 31 – June 3, 2014. ACM Press.

[TFKW13] Marco Tomamichel, Serge Fehr, Jedrzej Kaniewski, and Stephanie Wehner. One-sided device-independent QKD and position-based cryptography from monogamy games. In Thomas Johansson and Phong Q. Nguyen, editors, Advances in Cryptology – EUROCRYPT 2013, volume 7881 of Lecture Notes in Computer Science, pages 609–625, Athens, Greece, May 26–30, 2013. Springer Berlin Heidelberg, Germany. [Tro12]

Joel A. Tropp. User-friendly tail bounds for sums of random matrices. Foundations of Computational Mathematics, 12(4):389–434, 2012.

[Wat06]

John Watrous. Zero-knowledge against quantum attacks. In Jon M. Kleinberg, editor, 38th Annual ACM Symposium on Theory of Computing, pages 296–305, Seattle, WA, USA, May 21–23, 2006. ACM Press.

[Wie83]

Stephen Wiesner. Conjugate coding. ACM SIGACT News, 15(1):78–88, 1983.

[Win99]

Andreas Winter. Coding theorem and strong converse for quantum channels. IEEE Transactions on Information Theory, 45(7):2481–2485, 1999.

[Zha12]

Mark Zhandry. How to construct quantum random functions. In 53rd Annual Symposium on Foundations of Computer Science, pages 679–687, New Brunswick, NJ, USA, October 20–23, 2012. IEEE Computer Society Press.

97

[Zha20]

Mark Zhandry. Schrödinger’s pirate: How to trace a quantum decoder. In Rafael Pass and Krzysztof Pietrzak, editors, TCC 2020: 18th Theory of Cryptography Conference, Part III, volume 12552 of Lecture Notes in Computer Science, pages 61–91, Durham, NC, USA, November 16–19, 2020. Springer, Cham, Switzerland.

[Zha21]

Mark Zhandry. Quantum lightning never strikes the same state twice. or: Quantum money from cryptographic assumptions. J. Cryptol., 34(1):6, 2021.

98

Related documents

• Narrowing Data Protection's Enforcement Gap#964839
• Matchings: Source, Goal and Faithful Companion#614906
• Matchings: Source, Goal and Faithful Companion#613939
• Data Protection and the Role of Fairness#462039
• Kant's Two Solutions to the Free Rider Problem#760959