#  One-out-of-Many Unclonable Cryptography:
Definitions, Constructions, and More

Fuyuki Kitagawa  NTT Social Informatics Laboratories, Tokyo, Japan
<EMAIL_ADDRESS>Ryo Nishimaki  NTT Social
Informatics Laboratories, Tokyo, Japan
<EMAIL_ADDRESS>
###### Abstract

The no-cloning principle of quantum mechanics enables us to achieve amazing
unclonable cryptographic primitives, which is impossible in classical
cryptography. However, the security definitions for unclonable cryptography
are tricky. Achieving desirable security notions for unclonability is a
challenging task. In particular, there is no indistinguishable-secure
unclonable encryption and quantum copy-protection for single-bit output point
functions in the standard model. To tackle this problem, we introduce and
study relaxed but meaningful security notions for unclonable cryptography in
this work. We call the new security notion _one-out-of-many_ unclonable
security.

We obtain the following results.

  * •

We show that one-time strong anti-piracy secure secret key single-decryptor
encryption (SDE) implies one-out-of-many indistinguishable-secure unclonable
encryption.

  * •

We construct a one-time strong anti-piracy secure secret key SDE scheme in the
standard model from the LWE assumption.

  * •

We construct one-out-of-many copy-protection for single-bit output point
functions from one-out-of-many indistinguishable-secure unclonable encryption
and the LWE assumption.

  * •

We construct one-out-of-many unclonable predicate encryption (PE) from one-
out-of-many indistinguishable-secure unclonable encryption and the LWE
assumption.

Thus, we obtain one-out-of-many indistinguishable-secure unclonable
encryption, one-out-of-many copy-protection for single-bit output point
functions, and one-out-of-many unclonable PE in the standard model from the
LWE assumption. In addition, our one-time SDE scheme is the first SDE scheme
that does not rely on any oracle heuristics and strong assumptions such as
indistinguishability obfuscation and witness encryption.

###### Contents

  1. 1 Introduction
    1. 1.1 Background
    2. 1.2 Our Result
    3. 1.3 Concurrent and Independent Work
    4. 1.4 Technical Overview
    5. 1.5 More on Related Work
  2. 2 Preliminaries
    1. 2.1 Quantum information
    2. 2.2 Standard Cryptographic Tools
    3. 2.3 Quantum Cryptographic Tools
  3. 3 One-out-of-Many Unclonable Security
    1. 3.1 One-out-of-Many Security Notions for SKUE and Secret Key SDE
    2. 3.2 From Secret-Key SDE to SKUE: One-out-of-Many Setting
  4. 4 One-Time Secret Key SDE from LWE
    1. 4.1 Tools
    2. 4.2 Construction
  5. 5 Quantum Copy-Protection from Unclonable Encryption
    1. 5.1 Definition
    2. 5.2 Construction
  6. 6 Unclonable Predicate Encryption
    1. 6.1 Definition
    2. 6.2 Construction
  7. A AD-SIM secure CP-ABE
    1. A.1 Additional Tool
    2. A.2 Construction
  8. B Succinct CPFE
  9. C Injective Commitment with Equivocal Mode

##  1 Introduction

###  1.1 Background

#### Unclonable encryption and quantum copy-protection.

Quantum information enables us to achieve new cryptographic primitives beyond
classical cryptography. Especially the no-cloning principle of quantum
information has given rise to amazing unclonable cryptographic primitives.
This includes quantum money [Wie83], quantum copy-protection [Aar09],
unclonable encryption [BL20], one-shot signatures [AGKZ20], single-decryptor
encryption [GZ20, CLLZ21], and many more. In this work, we mainly focus on
unclonable encryption and quantum copy-protection.

Broadbent and Lord [BL20] introduced unclonable encryption. Unclonable
encryption is a one-time secure secret key encryption where a plaintext is
encoded into a quantum ciphertext that is impossible to clone. More
specifically, an unclonable encryption scheme encrypts a plaintext
$\mathsf{m}$ into a quantum ciphertext $\mathpzc{ct}$. The user who has the
secret key can recover $\mathsf{m}$ from $\mathpzc{ct}$. The security notion
of unclonable encryption ensures that it is impossible to convert
$\mathpzc{ct}$ into possibly entangled bipartite states $\mathpzc{ct}_{1}$ and
$\mathpzc{ct}_{2}$, both of which can be used to recover $\mathsf{m}$ when the
secret key is given. Ananth and Kaleoglu [AK21] later introduced unclonable
public key encryption. Unclonable encryption has interesting applications,
such as preventing cloud storage attacks where an adversary steals ciphertexts
from cloud storage with the hope that they can be decrypted if the secret key
is leaked later.

Quantum copy-protection [Aar09] is a cryptographic primitive that prevents
users from creating pirated copies of a program. More specifically, a quantum
copy-protection scheme transforms a classical program $C$ into a quantum
program $\rho$ that is impossible to copy. We can compute $C(x)$ for any input
$x$ using $\rho$. The security notion of copy-protection ensures that it is
impossible to convert $\rho$ into possibly entangled bipartite states
$\rho_{1}$ and $\rho_{2}$, both of which can be used to compute $C$. As shown
by Ananth and La Placa [AL21], it is impossible to have quantum copy-
protection for general unlearnable functions. For this reason, recent works
have been studying quantum copy-protection for a simple class of functions
such as point functions [CMP20, AK21, AKL+22, AK22].111 Some lines of works
[CLLZ21, LLQZ22] studied quantum copy-protection for cryptographic
functionalities that are not captured by C&C programs. Quantum copy-
protections for cryptographic functionalities have different names, such as
unclonable decryption or single decryptor encryption. In this work, unless
stated otherwise, we use the term quantum copy-protection to indicate quantum
copy-protection for point functions. For the previous works on quantum copy-
protection for cryptographic functionalities, see Section 1.5.  Moreover,
Coladangelo, Majenz, and Poremba [CMP20] show that quantum copy-protection for
point functions can be transformed into quantum copy-protection for a more
general class of compute-and-compare programs (C&C programs) that includes
conjunctions with wildcards, affine testers, plaintext testers, and so on. We
focus on quantum copy-protection for point functions in this work.

#### Definition of unclonability: one-wayness and indistinguishability.

To describe our research questions and contributions, we first explain a
general template for unclonable security games played by a tuple of three
adversaries $(\mathpzc{A}_{0},\mathpzc{A}_{1},\mathpzc{A}_{2})$. The template
is common to unclonable encryption and quantum copy-protection. In the first
stage, the challenger sends a challenge copy-protected object (such as a
quantum ciphertext in unclonable encryption and copy-protected program in
quantum copy-protection) to an adversary $\mathpzc{A}_{0}$. Then,
$\mathpzc{A}_{0}$ generates possibly entangled bipartite states $\rho_{1}$ and
$\rho_{2}$ and sends $\rho_{\alpha}$ to $\mathpzc{A}_{\alpha}$ for
$\alpha\in\\{1,2\\}$. In the second phase, the challenger sends extra
information (such as secret keys in unclonable encryption and some inputs for
the program in quantum copy-protection) to $\mathpzc{A}_{1}$ and
$\mathpzc{A}_{2}$, and they try to compute target information about the copy-
protected object (such as plaintexts in unclonable encryption and computation
results on the given inputs in quantum copy-protection). Here,
$\mathpzc{A}_{1}$ and $\mathpzc{A}_{2}$ are not allowed to communicate. If
both $\mathpzc{A}_{1}$ and $\mathpzc{A}_{2}$ succeed in computing target
information, the adversaries win. Note that if $\mathpzc{A}_{\alpha}$ has the
original objects, computing target information is easy.

Using the above game, we can define both one-wayness-based notion and
indistinguishability-based notion depending on which one the task of
$\mathpzc{A}_{1}$ and $\mathpzc{A}_{2}$ is, recovering entire bits of high
min-entropy information or detecting $1$-bit information. Similarly to
standard security notions, indistinguishability-based one is more general and
enables us to have a wide range of applications. Also, indistinguishability-
based unclonability usually implies standard cryptographic security notions,
but one-wayness-based unclonability does not necessarily imply them.222 For
example, indistinguishability-based unclonability for unclonable encryption
implies (one-time) IND-CPA security, but one-wayness-based unclonability does
not.  In this work, we focus on indistinguishability-based unclonability
notions.

#### Toward indistinguishability-based unclonability in the standard model.

Unclonable encryption and quantum copy-protection have been studied actively
and there are many constructions. Although we have constructions with one-
wayness-based unclonability from standard assumptions in the standard model
[BL20, AK21], we have constructions with indistinguishability-based
unclonability _only in the oracle model_ , in both unclonable encryption and
quantum copy-protection [AKL+22]. Ananth, Kaleoglu, Li, Liu, and Zhandry
[AKL+22] proposed the only indistinguishability-based secure unclonable
encryption and quantum copy-protection schemes. Their proof technique is
highly specific to the oracle model. Thus, it still remains elusive to achieve
unclonable encryption and quantum copy-protection with indistinguishability-
based unclonability in the standard model.

Given the above situation, it is natural and reasonable to explore relaxed but
meaningful indistinguishability-based unclonability and ask whether the notion
can be achieved in the standard model. Such a standard model construction with
a relaxed notion would provide new insights toward achieving full-fledged
indistinguishability-based unclonability in the standard model.

###  1.2 Our Result

Our contributions are proposing new definitions for unclonability and
constructions satisfying them under the LWE assumption in the standard model.

#### New definitions: one-out-of-many unclonability notions.

We introduce a relaxed indistinguishability-based unclonability for unclonable
encryption and copy-protection, called _one-out-of-many_ unclonable security.
This notion captures a meaningful unclonability, as we argue below. It
guarantees that no adversary can generate $n$ copies with probability
significantly better than $\frac{1}{n}$ for any $n$. Thus, roughly speaking,
it guarantees that the expected number of successful target objects generated
by any copying adversary is less than $1$. We define one-out-of-many
unclonability by extending the unclonable game played by a tuple of three
adversaries into a game played by $n+1$ adversaries, where $n\geq 2$ is
arbitrary.

Although one-out-of-many unclonable security looks weaker than existing
unclonable security, it is useful in some applications. For example, suppose
we publish many quantum objects, say $\ell$ objects. Then, one-out-of-many
security guarantees that no matter what copying attacks are applied to those
objects, there are expected to be only $\ell$ objects on average in this
world. Another nice property of one-out-of-many security is that it implies
standard cryptographic security notions. For example, one-out-of-many
unclonability for unclonable encryption implies (one-time) IND-CPA security.
This result contrasts one-wayness-based unclonability notions that do not
necessarily imply standard indistinguishability notions.

#### Unclonable encryption in the standard model via single decryptor
encryption.

We provide unclonable encryption satisfying one-out-of-many unclonability
under the LWE assumption in the standard model. We obtain this result as
follows.

We first define one-out-of-many unclonability for (one-time) single decryptor
encryption (SDE) [GZ20, CLLZ21]. One-time SDE is a dual of unclonable
encryption in the sense that one-time SDE is a one-time secret key encryption
scheme where a secret key is encoded into a quantum state, and its security
notion guarantees that any adversary cannot copy the quantum secret key. Under
appropriate definitions, it is possible to back and forth between unclonable
encryption and one-time SDE, as shown by Georgiou and Zhandry [GZ20]. We show
that we can transform any one-time SDE with one-out-of-many unclonability to
unclonable encryption with one-out-of-many unclonability.

We then show that we can obtain one-time SDE with one-out-of-many
unclonability from the LWE assumption. More specifically, assuming the LWE
assumption, we construct one-time SDE satisfying strong anti-piracy introduced
by Coladangelo, Liu, Liu, and Zhandry [CLLZ21], and show that strong anti-
piracy implies one-out-of-many unclonability. Combining this result with the
above transformation, we obtain unclonable encryption with one-out-of-many
security under the LWE assumption.

###### Theorem 1.1 (informal).

Assuming the LWE assumption holds, there exists strong anti-piracy secure one-
time SDE.

###### Theorem 1.2 (informal).

Assuming the LWE assumption holds, there exists one-out-of-many
indistinguishable-secure unclonable encryption.

To achieve one-time SDE satisfying strong anti-piracy, we develop a technique
enabling us to use a BB84 [BB14] state as a copy-protected secret key. Our
crucial tool is single-key ciphertext-policy functional encryption (CPFE) with
a succinct key, which we introduce in this work. We instantiate it with hash
encryption (HE) [DGHM18] implied by the LWE assumption. The technique of the
post-quantum watermarking by Kitagawa and Nishimaki [KN22] inspired our proof
technique. We emphasize that _our one-time SDE scheme is the first SDE scheme
that does not require either oracle heuristic or strong assumptions such as
indistinguishability obfuscation and witness encryption._

#### Quantum copy-protection in the standard model via unclonable encryption.

We propose quantum copy protection for single-bit output point functions based
on unclonable encryption and the LWE assumption. Known constructions from
unclonable encryption [CMP20, AK21] support only multi-bit output point
functions.333 One might think that copy protection for multi-bit output point
functions implies that for single-bit output point functions. However, this is
not the case. This is because the security of copy protection for multi-bit
output point functions usually relies on the high min-entropy of the multi-bit
output string, and it is broken if the output string does not have enough
entropy as in the case of single-bit output. Realizing copy protection for
single-bit output point function is challenging in the sense that we have to
achieve the security without relying on the entropy of the output string.
Although we formally prove this result with our new one-out-of-many security
notion, our construction also works under standard indistinguishability-based
unclonability definitions defined using three adversaries
$(\mathpzc{A}_{0},\mathpzc{A}_{1},\mathpzc{A}_{2})$.

###### Theorem 1.3 (informal).

Assuming (resp. one-out-of-many) indistinguishable-secure unclonable
encryption and the LWE assumption holds, there exits (resp. one-out-of-many)
copy-protection for single-bit output point functions.

#### Unclonable predicate encryption.

Using the technique proposed by Ananth and Kaleoglu [AK21], we can convert our
one-out-of-many secure unclonable encryption into one-out-of-many secure
unclonable public-key encryption. We construct a one-out-of-many unclonable
predicate encryption (PE) scheme from one-out-of-many unclonable encryption
and the LWE assumption. PE is a stronger variant of attribute-based encryption
(ABE). ABE is an advanced public-key encryption system where we can generate a
user secret key for an attribute $x$ and a ciphertext of a message
$\mathsf{m}$ under a policy $P$.444We focus on ciphertext-policy ABE in this
work. We can decrypt a ciphertext and obtain $\mathsf{m}$ if $P(x)=1$. In PE,
ciphertexts hide not only plaintexts but also policies.

###### Theorem 1.4 (informal).

Assuming (resp. one-out-of-many) indistinguishable-secure unclonable
encryption and the LWE assumption holds, there exits (resp. one-out-of-many)
unclonable PE.

###  1.3 Concurrent and Independent Work

Ananth, Kaleoglu, and Liu [AKL23] introduce a new framework called cloning
games to study unclonable cryptography. They obtain many implications to
unclonable cryptography thanks to the framework. In particular, they obtain
information-theoretically secure one-time SDE in the standard model. The
scheme is _single-bit_ encryption while our computationally secure scheme is
multi-bit encryption. _Note that we do not know how to obtain multi-bit
encryption from single-bit one via parallel repetition and the standard hybrid
argument in unclonable cryptography._ Thus, their results on SDE is
incomparable with ours. We also note that it is not clear whether we can
obtain one-out-of-many indistinguishable-secure unclonable encryption from
their SDE, since it seems that we need strong anti-piracy secure one-time SDE
to obtain one-out-of-many secure one, but their scheme is only proved to
satisfy (non-strong) indistinguishability-based security. For the detailed
reason on the need of strong anti-piracy for the implication, see the “SDE
from LWE” paragraph in Section 1.4.

###  1.4 Technical Overview

We provide a high-level overview of our techniques in this subsection. In this
paper, standard math or sans serif font stands for classical algorithms and
classical variables. The calligraphic font stands for quantum algorithms and
the calligraphic font and/or the bracket notation for (mixed) quantum states.

#### Relaxed definition of unclonable cryptography.

We introduce relaxed security notions for unclonable cryptography called _one-
out-of-many_ unclonable security that roughly guarantees that no adversary can
generate $n$ copies with a probability significantly better than $\frac{1}{n}$
for any $n$. The one-out-of-many unclonability is defined by extending the
unclonable game played by $(\mathpzc{A}_{0},\mathpzc{A}_{1},\mathpzc{A}_{2})$
explained in Section 1.1. The one-out-of-many unclonability game is played by
a tuple of $n+1$ adversaries
$(\mathpzc{A}_{0},\mathpzc{A}_{1},\cdots,\mathpzc{A}_{n})$, where $n$ is
arbitrary. At the first stage of the game, $\mathpzc{A}_{0}$ is given a single
quantum object, generates possibly entangled $n$-partite states
$\rho_{1},\ldots,\rho_{n}$, and sends $\rho_{k}$ to $\mathpzc{A}_{k}$ for
$k\in\\{1,\ldots,n\\}$. At the second stage, the challenger selects one of
$(\mathpzc{A}_{1},\ldots,\mathpzc{A}_{n})$ by a random
$\alpha\leftarrow\\{1,\ldots,n\\}$ and sends additional information _only to
$\mathpzc{A}_{\alpha}$_, and only $\mathpzc{A}_{\alpha}$ tries to detect the
target $1$-bit information. Recall that we focus on indistinguishability-based
setting. The one-out-of-many unclonability guarantees that the adversary
cannot win this game with probability significantly better than the trivial
winning probability $\frac{1}{n}\cdot
1+\frac{n-1}{n}\cdot\frac{1}{2}=\frac{1}{2}+\frac{1}{2n}$. The definition
captures the above intuition because if $\mathpzc{A}_{0}$ could make $n$
copies with probability $\frac{1}{n}+\delta$ for some noticeable $\delta$, the
adversary would win the game with probability at least
$(\frac{1}{n}+\delta)\cdot
1+(1-\frac{1}{n}-\delta)\cdot\frac{1}{2}=\frac{1}{2}+\frac{1}{2n}+\frac{\delta}{2}$.

We consider one-out-of-many unclonable security for the following security
notions in this work: (1) (one-time) unclonable-indistinguishable security for
unclonable encryption, (2) copy-protection security for single-bit output
point functions, (3) (one-time) indistinguishability-based security for one-
time SDE, (4) unclonable-simulation security for PE, which is introduced in
this work.

The nice property of one-out-of-many security are as follows. One-out-of-many
security implies standard cryptographic security notions. For example, one-
out-of-many unclonability for unclonable encryption implies (one-time) IND-CPA
security, and one for copy-protection implies distributional
indistinguishability as virtual black-box obfuscation. Moreover, we can use
one-out-of-many secure unclonable cryptographic primitives as a drop-in-
replacement of standard indistinguishability-based unclonable cryptographic
primitives if our goal is constructing a one-out-of-many secure unclonable
cryptographic primitive (and vice versa). For example, the transformation from
unclonable encryption to unclonable public-key encryption proposed by Ananth
and Kaleoglu [AK21] works also in the one-out-of-many setting. Moreover, all
of the generic constructions from an unclonable primitive to another
unclonable primitive that we propose work in both standard (three adversary
style) setting and one-out-of-many setting.

In addition to the above nice properties, we can prove that _one-out-of-many
indistinguishability-based secure one-time SDE is equivalent to one-out-of-
many unclonable-indistinguishable secure unclonable encryption_. In this work,
we first obtain one-out-of-many indistinguishability-based secure one-time SDE
from the LWE assumption, and using this equivalence, we obtain one-out-of-many
secure unclonable encryption, copy protection for single-bit output point
functions, and unclonable PE.

Before our work, Georgiou and Zhandry [GZ20] showed a transformation from one-
time SDE to unclonable encryption under the standard three adversary style
setting. Informed readers may think that by combining their result with the
result by Coladangelo et al. [CLLZ21] (and the result by Culf and Vidick
[CV22]), we can obtain indistinguishability-based unclonable encryption in the
standard model based on indistinguishability obfuscation. However, this is not
the case due to the fact that those two works used different definitions of
the indistinguishability-based security for SDE, and we do not know any
relation between them. For more details, see Remark 2.23.

#### SDE from LWE.

We next explain how to obtain one-out-of-many indistinguishability-based
secure one-time SDE. In fact, we obtain one-time SDE satisfying much stronger
security notion called strong anti-piracy [CLLZ21] from the LWE assumption,
and prove that _strong anti-piracy implies one-out-of-many
indistinguishability-based security_. Below, we first introduce the definition
of strong anti-piracy for one-time SDE, briefly explain the intuition of the
implication, and finally present the high level ideas on how to realize strong
anti-piracy secure one-time SDE from the LWE assumption.

Recall the general template of the security game for unclonability played by
three adversaries $(\mathpzc{A}_{0},\mathpzc{A}_{1},\mathpzc{A}_{2})$
explained in Section 1.1. This template also captures the security game of
strong anti-piracy for SDE. In strong anti-piracy security for SDE,
$\mathpzc{A}_{0}$ receives a copy-protected decryption key $\mathpzc{dk}$ in
the first stage. In the second stage, $\mathpzc{A}_{1}$ and $\mathpzc{A}_{2}$
outputs quantum decryptors $\mathpzc{D}_{1}$ and $\mathpzc{D}_{2}$,
respectively, and the challenger tests whether both $\mathpzc{D}_{1}$ and
$\mathpzc{D}_{2}$ are “good” (or “live”) quantum decryptors [Zha20, CLLZ21].
Intuitively, good quantum decryptors can distinguish encryption of $m_{0}$
from that of $m_{1}$ with probability
$\frac{1}{2}+\frac{1}{{\mathrm{poly}}(\lambda)}$, and do not lose the
decryption capability even after its goodness was tested. Strong anti-piracy
guarantees that the probability that both $\mathpzc{D}_{1}$ and
$\mathpzc{D}_{2}$ are tested as good is negligible. See Definition 2.21 for
the precise definition.

The intuition behind the implication from strong anti-piracy to one-out-of-
many security is as follows. The one-out-of-many security game for a one-time
SDE scheme played by a tuple of $n+1$ adversaries
$(\mathpzc{A}_{0},\cdots,\mathpzc{A}_{n})$ is defined as follows. The first
stage adversary $\mathpzc{A}_{0}$ is given a quantum decryption key
$\mathpzc{dk}$, generates possibly entangled $n$-partite states
$\rho_{1},\cdots\rho_{n}$, and sends $\rho_{k}$ to the second stage adversary
$\mathpzc{A}_{k}$ for every $k\in\\{1,\cdots,n\\}$. In the second stage, only
randomly chosen single second stage adversary $\mathpzc{A}_{\alpha}$ is given
the challenge ciphertext and required to guess the challenge bit. The
$n$-partite state $(\rho_{1},\cdots,\rho_{n})$ generated by $\mathpzc{A}_{0}$
can be regarded as a tuple of $n$ quantum decryptors. If the one-time SDE
scheme is strong anti-piracy secure, all $n$ quantum decryptors _except one_
must have success probabilities at most $1/2+{\mathsf{negl}}(\lambda)$. Hence,
the success probability of $(\mathpzc{A}_{0},\cdots,\mathpzc{A}_{n+1})$ in the
one-out-of-many security game is at most $1/n\cdot
1+(n-1)/n\cdot(1/2+{\mathsf{negl}}(\lambda))=1/2+1/2n+{\mathsf{negl}}(\lambda)$,
which proves the one-out-of-many security. It seems that “strong” anti piracy
is required for this argument and it is difficult to prove a similar
implication from (non-strong) indistinguishability-based security defined by
Coladangelo et al. [CLLZ21]. To formally prove the implication, we have to
construct a reduction algorithm that finds two “good” decryptors from $n$
decryptors output by $\mathpzc{A}$. If the reduction attacks strong anti-
piracy, it is sufficient to randomly pick two decryptors out of $n$ since the
reduction’s goal is to output two “good” decryptors with inverse polynomial
probability. However, if the reduction attacks (non-strong)
indistinguishability-based security, the reduction cannot use such random
guessing and needs to detect whether each decryptor is “good” since the
reduction’s goal is to make a distinguishing gap. We are considering the one-
time setting where the adversaries are not given the encryption key. Thus, it
seems difficult to perform such detection of “good” decryptors.

We next explain how to achieve strong anti-piracy secure one-time SDE based on
the LWE assumption in the standard model. We use the monogamy of entanglement
property of BB84 states [TFKW13] differently from the previous work on SDE
[CLLZ21] that used the monogamy of entanglement property of coset states.

We combine BB84 states and ciphertext-policy FE with succinct key to achieve
strong anti-piracy. We first explain the definition of single-key CPFE. A
single-key CPFE scheme $\mathsf{CPFE}$ consists of three algorithms
$(\mathsf{FE}.\mathsf{Setup},\mathsf{FE}.\mathsf{Enc},\mathsf{FE}.\mathsf{Dec})$.
$\mathsf{FE}.\mathsf{Setup}$ takes as input a string $x$ and outputs a public
key $\mathsf{pk}$ and a decryption key $\mathsf{sk}_{x}$.555We omit the
security parameter for simplicity in this overview. The same is applied to
other cryptographic primitives. Here, we assume that $x$ itself works as a
decryption key $\mathsf{sk}_{x}$ for $x$, thus $\mathsf{FE}.\mathsf{Setup}$
outputs only $\mathsf{pk}$. We can achieve such a CPFE (we will explain
later). $\mathsf{FE}.\mathsf{Enc}$ takes as input $\mathsf{pk}$ and a circuit
$C$, and outputs a ciphertext $\mathsf{ct}$. We can decrypt $\mathsf{ct}$ with
$\mathsf{sk}_{x}$ using $\mathsf{FE}.\mathsf{Dec}$, and obtain $C(x)$. The
single-key security of CPFE guarantees that
$\mathsf{FE}.\mathsf{Enc}(\mathsf{pk},C_{0})$ and
$\mathsf{FE}.\mathsf{Enc}(\mathsf{pk},C_{1})$ are computationally
indistinguishable for an adversary who has a decryption key $\mathsf{sk}_{x}$
for $x$ of its choice as long as $C_{0}(x)=C_{1}(x)$ holds.

Let $s[i]$ is the $i$-th bit of a string $s\in\\{0,1\\}^{n}$. Our one-time SDE
scheme is as follows. The key generation algorithm generate a BB84 state
$\ket{x^{\theta}}\coloneqq H^{\theta[1]}\ket{x[1]}\otimes\cdots\otimes
H^{\theta[n]}\ket{x[n]}$, where $H$ is the Hadamard gate, and a public key
$\mathsf{pk}\leftarrow\mathsf{FE}.\mathsf{Setup}(x)$ of $\mathsf{CPFE}$. It
outputs an encryption key $\mathsf{ek}\coloneqq(\theta,\mathsf{pk})$ and
decryption key $\mathpzc{dk}\coloneqq\ket{x^{\theta}}$. Note that although our
one-time SDE scheme is secret key encryption, an encryption key and a
decryption key are different. The encryption algorithm takes as input the
encryption key and a plaintext $\mathsf{m}$, and generates a ciphertext
$\mathsf{fe}.\mathsf{ct}\leftarrow\mathsf{FE}.\mathsf{Enc}(\mathsf{pk},C[\mathsf{m}])$,
where $C[\mathsf{m}]$ is a constant circuit that outputs $\mathsf{m}$ for all
inputs. It outputs a ciphertext $(\theta,\mathsf{fe}.\mathsf{ct})$. We can
decrypt $\mathsf{fe}.\mathsf{ct}$ and obtain $\mathsf{m}$ by recovering $x$
from $\ket{x^{\theta}}$ and $\theta$ since $x$ works as a decryption key of
$\mathsf{CPFE}$ as we assumed. Intuitively, it is hard to copy
$\mathpzc{dk}=\ket{x^{\theta}}$ by the monogamy of entanglement property. The
monogamy of entanglement property can be explained by the template of
unclonable cryptography. In the first stage, $\mathpzc{A}_{0}$ is given
$\ket{x^{\theta}}$. In the second stage, $\mathpzc{A}_{1}$ and
$\mathpzc{A}_{2}$ receive $\theta$ and try to output $x$. It is proved that
the winning probability of the adversaries is exponentially small without any
assumptions [TFKW13].

To prove the strong anti-piracy security, we need to extract $x$ both from
good decryptors $\mathpzc{D}_{1}$ and $\mathpzc{D}_{2}$ respectively output by
$\mathpzc{A}_{1}$ and $\mathpzc{A}_{2}$ to reduce the SDE security to the
monogamy of entanglement property. The idea for the extraction is as follows.
Let $\widetilde{C}[b,\mathsf{m}_{0},\mathsf{m}_{1},i]$ be a circuit that takes
as input $x$ and outputs $\mathsf{m}_{b\oplus x[i]}$. We estimate the
probability that a good decryptor outputs the correct $b$ when we feed
$\mathsf{FE}.\mathsf{Enc}(\mathsf{pk},\widetilde{C}[b,\mathsf{m}_{0},\mathsf{m}_{1},i])$
to it. The security of $\mathsf{CPFE}$ guarantees that
$\mathsf{FE}.\mathsf{Enc}(\mathsf{pk},\widetilde{C}[b,\mathsf{m}_{0},\mathsf{m}_{1},i])$
is indistinguishable from
$\mathsf{FE}.\mathsf{Enc}(\mathsf{pk},C[\mathsf{m}_{b\oplus x[i]}])$ since
$\widetilde{C}[b,\mathsf{m}_{0},\mathsf{m}_{1},i](x)=\mathsf{m}_{b\oplus
x[i]}=C[\mathsf{m}_{b\oplus x[i]}](x)$. Hence, we can analyze the probability
as follows.

  * •

If $x[i]=0$, the distinguishing probability should be greater than
$\frac{1}{2}$ since a good decryptor receives
$\mathsf{FE}.\mathsf{Enc}(\mathsf{pk},C[\mathsf{m}_{b}])$ in its view and
correctly guesses $b$ with probability
$\frac{1}{2}+\frac{1}{{\mathrm{poly}}(\lambda)}$.

  * •

If $x[i]=1$, the distinguishing probability should be smaller than
$\frac{1}{2}$ since a good decryptor receives
$\mathsf{FE}.\mathsf{Enc}(\mathsf{pk},C[\mathsf{m}_{1\oplus b}])$ in its view
and outputs the flipped bit $1\oplus b$ with probability
$\frac{1}{2}+\frac{1}{{\mathrm{poly}}(\lambda)}$.

This means that we can decide $x[i]=0$ or $x[i]=1$ by estimating the success
probability of a good decryptor that receives
$\mathsf{FE}.\mathsf{Enc}(\mathsf{pk},\widetilde{C}[b,\mathsf{m}_{0},\mathsf{m}_{1},i])$.
Thus, we can extract $x$ from good decryptors. This extraction technique is
based on the post-quantum watermarking extraction technique by Kitagawa and
Nishimaki [KN22]. Hence, the extraction succeeds without collapsing good
quantum decryptors $\mathpzc{D}_{1}$ and $\mathpzc{D}_{2}$. See Section 4 for
the detail.

There is one subtle issue in the argument above. Since $\mathsf{pk}$ depends
on $x$, we need leakage information about $x$ to simulate $\mathsf{pk}$ in the
reduction. More specifically, let $\mathsf{Leak}(\cdot)$ be a leakage function
and the reduction needs $\mathsf{Leak}(x)$ to simulate $\mathsf{pk}$ of
$\mathsf{CPFE}$. We can consider such a leakage variant of the monogamy of
entanglement game, where $\mathpzc{A}_{0}$ receives $\ket{x^{\theta}}$ and
$\mathsf{Leak}(x)$ in the first stage. The variant holds if
$\absolutevalue{\mathsf{Leak}(x)}=\lambda$ that is short enough compared to
$n=\absolutevalue{x}$ since we can simply guess $\mathsf{Leak}(x)$ with
probability $\frac{1}{2^{\lambda}}$. Although the bound is degraded to
$\frac{2^{\lambda}}{\exp(n)}$, it is still negligible by setting $n$
appropriately. Hence, we use single-key CPFE with _succinct key_ to ensure
that $\mathsf{Leak}(x)$ does not have much information about $x$.

A single-key CPFE scheme has a succinct key if it satisfies the following
properties. $\mathsf{FE}.\mathsf{Setup}$ consists of two algorithms
$(\mathsf{HKG},\mathsf{Hash})$, computes a hash key
$\mathsf{hk}\leftarrow\mathsf{HKG}(1^{\absolutevalue{x}})$ and a hash value
$h\leftarrow\mathsf{Hash}(\mathsf{hk},x)$ from $x$, and outputs a public key
$\mathsf{pk}\coloneqq(\mathsf{hk},h)$ and a decryption key
$\mathsf{sk}_{x}\coloneqq x$. The length of $h$ should be the same as the
security parameter (no matter how large $x$ is). These properties are crucial
for our construction since we consider
$\mathsf{Leak}(x)\coloneqq\mathsf{Hash}(\mathsf{hk},\cdot)$ and a hash value
$h$ does not have much information about $x$.

We can achieve single-key CPFE with succinct key from hash encryption (HE)
[DGHM18], which can be achieved from the LWE. We use HE instead of plain PKE
in the well-known single-key FE scheme based on PKE [SS10]. Thanks to the
compression property of hash encryption, we can achieve the succinct key
property. A decryption key of HE is a pre-image of a hash. Hence, we can use
$x$ as a decryption key $\mathsf{sk}_{x}$.

#### One-out-of-many unclonable encryption.

Georgiou and Zhandry [GZ20] showed that under appropriate definitions, it is
possible to transform one-time SDE to unclonable encryption. We show that by
using the same transformation, we can transform any one-out-of-many secure SDE
to one-out-of-many secure unclonable encryption. By combining this
transformation with the above one-out-of-many SDE, we can obtain one-out-of-
many secure unclonable encryption based on the LWE assumption.

#### Copy protection for single-bit output point functions.

A point function $f_{y,\mathsf{m}}$ is a function that outputs $\mathsf{m}$ on
input $y$ and outputs $0^{\absolutevalue{\mathsf{m}}}$ otherwise. When we say
single-bit output, we set $\mathsf{m}=1$. When we say multi-bit output, we set
$\mathsf{m}$ as a multi-bit string sampled from some high min-entropy
distribution. We denote the family of single-bit output point functions and
multi-bit output point functions as $\mathcal{P}\mathcal{F}^{1}$ and
$\mathcal{P}\mathcal{F}^{\mathsf{mlt}}$, respectively.

We introduce a simplified security game for copy protection for point
functions. It follows the template given in Section 1.1. The first stage
adversary is given a copy protected program $\rho$ of a randomly generated
point function $f_{y,\mathsf{m}}$. In the second stage, $\mathpzc{A}_{1}$ and
$\mathpzc{A}_{2}$ are given a challenge input $x$ sampled from some
distribution and try to output $f_{y,\mathsf{m}}(x)$ simultaneously. The copy
protection security guarantees that the success probability of the adversary
is bounded by the trivial winning probability.

Coladangelo et al. [CMP20] proposed a generic construction of copy protection
for $\mathcal{P}\mathcal{F}^{\mathsf{mlt}}$ using unclonable encryption.666
Ananth and Kaleoglu [AK21] also proposed a similar construction.  The
construction is as follows. To copy protect a multi-bit output point function
$f_{y,\mathsf{m}}$, it generates a quantum ciphertext of $\mathsf{m}$ of an
unclonable encryption scheme $\mathsf{UE}$ under the key $y$, that is
$\mathpzc{ct}\leftarrow\mathsf{UE}.\mathpzc{Enc}(y,\mathsf{m})$. For
simplicity, we assume that given a key $y^{\prime}$ and a ciphertext
$\mathpzc{ct}^{\prime}$ of $\mathsf{UE}$, we can efficiently check whether
$\mathpzc{ct}^{\prime}$ is generated under the key $y^{\prime}$ or not. Then,
to evaluate this copy protected program with input $x$, it first checks if $x$
and $\mathpzc{ct}$ match or not, and if so, just output the decryption result
of $\mathpzc{ct}$ under the key $x$. We see that the construction satisfies
the correctness. Coladangelo et al. also show that if $\mathsf{UE}$ satisfies
one-wayness-based unclonability, the construction satisfies copy protection
security.

In this work, we propose a generic construction of copy protection for
$\mathcal{P}\mathcal{F}^{1}$ using unclonable-indistinguishable secure
unclonable encryption. The above simple construction by Coladangelo et al.
does not work if our goal is copy protection for $\mathcal{P}\mathcal{F}^{1}$,
even if the underlying unclonable encryption is unclonable-indistinguishable
secure. The above construction crucially relies on the fact that $\mathsf{m}$
is sampled from high min-entropy distribution in
$\mathcal{P}\mathcal{F}^{\mathsf{mlt}}$. In fact, if $\mathsf{m}$ is fixed as
the case of $\mathcal{P}\mathcal{F}^{1}$, the construction is completely
insecure under the above condition that we can efficiently check the
correspondence between a key and a ciphertext of $\mathsf{UE}$, which is
required to achieve correctness.

To fix this issue, our construction uses quantum FHE [Mah18] and obfuscation
for C&C programs [WZ17, GKW17], both of which can be realized from the LWE
assumption. Roughly speaking, in our construction, the above UE-based copy
protected program is encrypted by QFHE. The evaluation of the new copy
protected program is done by the homomorphic evaluation of QFHE, and we obtain
the evaluation result from the QFHE ciphertext by using decryption circuit of
QFHE obfuscated by obfuscation for C&C programs. Our construction works in
both standard three adversary style setting explained above and one-out-of-
many setting.

#### Unclonable PE.

We also define and construct unclonable PE. Our security definition of
unclonable PE is simulation-based. It also can be seen as an extension of
simulation-based security notion for (not unclonable) PE defined by Gorbunov
et al. [GVW15b].

Our construction of unclonable PE is an extension of ABE-to-PE transformation
based on obfuscation for C&C programs proposed in classical cryptography
[WZ17, GKW17]. The above construction of copy protection for
$\mathcal{P}\mathcal{F}^{1}$ can be extended to copy protection for C&C
programs by encrypting a C&C program together with the ciphertext of
unclonable encryption into the QFHE ciphertext. At a high level, we show that
by replacing obfuscation for C&C programs with this copy protection for C&C
programs in the ABE-to-PE transformation, we can obtain unclonable PE. To
achieve hiding of policies in PE, the construction crucially uses the security
notions of the underlying QFHE and obfuscation for C&C programs. Thus, we do
not use the abstraction of copy protection for C&C programs, and present our
construction directly using ABE and the building blocks of our copy protection
construction. Our construction works in both standard three adversary style
setting and one-out-of-many setting.

In the above transformation, we use simulation-based secure ABE instead on
indistinguishability-based one. As far as we know, simulation-based secure ABE
was not studied before and there is no existing construction. Thus, we
construct simulation-based secure ABE by ourselves. The construction is based
on indistinguishability-based secure ABE and obfuscation for C&C programs,
both of which can be based on the LWE assumption. Interestingly, we can also
use our simulation-based secure ABE to convert unclonable encryption into the
first unclonable ABE via the standard KEM-DEM framework.

###  1.5 More on Related Work

#### Copy-protection for C&C programs.

Aaronson proposed candidate constructions of copy-protection for point
functions [Aar09]. However, he did not provide reduction-based proofs.
Coladangelo, Majenz, and Poremba proposed copy-protection for C&C programs in
the QROM and copy-protection for multi-bit output point functions based on
one-way-secure unclonable encryption [CMP20]. They also show that we can
convert copy-protection for point functions into copy-protection for C&C
programs. Ananth and Kaleoglu proposed copy-protected point functions based on
indistinguishable-secure unclonable encryption [AK21]. Ananth et al. [AKL+22]
proposed indistinguishable-secure unclonable encryption and copy-protection
for single-bit output point functions in the QROM. Ananth and La Placa [AL21]
show that there exists a class of functions that we cannot achieve copy-
protection in the plain model. Ananth and Kaleoglu [AK22] extend the
impossibility result by Ananth and La Placa [AL21] and show that there exists
a class of functions that we cannot achieve copy-protection in the classical-
accessible random oracle model (CAROM). CAROM is a model where both
constructions and adversaries can only classically access the random oracle.

#### Unclonable encryption.

Broadbent and Lord [BL20] proposed the notion of unclonable encryption based
on the idea by Gottesman [Got03].777The notion of unclonable encryption by
Gottesman is slightly diffrent from the one in this paper. His definition
focuses on tamper detection. They considered two security definitions for
unclonable encryption. One is one-wayness against cloning attacks (one-way-
secure unclonable encryption) and they achieve information-theoretic one-
wayness by using BB84 states. The other is indistinguishability against
cloning attacks (indistinguishable-secure unclonable encryption). However,
they did not achieve it. They constructed indistinguishable-secure unclonable
encryption only in a very restricted model by using PRFs. Ananth and Kaleoglu
[AK21] proposed a transformation from unclonable encryption to public key
unclonable encryption. Ananth et al. [AKL+22] proposed the first
indistinguishable-secure unclonable encryption in the QROM.

#### Unclonable decryption.

Georgiou and Zhandry [GZ20] proposed the notion of SDE and show the
equivalence between indistinguishable-secure unclonable encryption and their
SDE.888Selectively secure secret key SDE in the setting of honestly generated
keys. See [GZ20] for the detail., Coladangelo et al. [CLLZ21] proposed new
definitions of SDE and constructed a _public key_ SDE scheme that satisfies
their definitions from IO and the LWE assumption. Although they needed the
strong monogamy of entanglement property conjecture for their constructions,
the conjecture was proved without any assumptions by Culf and Vidick [CV22].
It is unclear whether SDE under the definitions by Coladangelo et al. [CLLZ21]
is equivalent to unclonable encryption. Liu, Liu, Qian, and Zhandry [LLQZ22]
achieved bounded collusion-resistant public key SDE, where adversaries can
receive many copy-protected decryption keys, from IO and the LWE assumption.
They also consider bounded collusion-resistant copy-protection for PRFs and
signatures. Sattath and Wyborski [SW22] also extend SDE to unclonable
decryptors, where we can generate multiple copy-protected decryption keys from
a classical decryption key. They constructed a secret key unclonable
decryptors scheme from copy-protection for balanced binary functions. However,
they need IO or a quantum oracle to instantiate copy-protection for balanced
binary functions.

##  2 Preliminaries

#### Notations and conventions.

In this paper, standard math or sans serif font stands for classical
algorithms (e.g., $C$ or $\mathsf{Gen}$) and classical variables (e.g., $x$ or
$\mathsf{pk}$). Calligraphic font stands for quantum algorithms (e.g.,
$\mathpzc{Gen}$) and calligraphic font and/or the bracket notation for (mixed)
quantum states (e.g., $\mathpzc{q}$ or $\ket{\psi}$). For strings $x$ and $y$,
$x\|y$ denotes the concatenation of $x$ and $y$. Let $[\ell]$ denote the set
of integers $\\{1,\cdots,\ell\\}$, $\lambda$ denote a security parameter, and
$y\coloneqq z$ denote that $y$ is set, defined, or substituted by $z$.

In this paper, for a finite set $X$ and a distribution $D$, $x\leftarrow X$
denotes selecting an element from $X$ uniformly at random, $x\leftarrow D$
denotes sampling an element $x$ according to $D$. Let
$y\leftarrow\mathsf{A}(x)$ and $y\leftarrow\mathpzc{A}(\mathpzc{x})$ denote
assigning to $y$ the output of a probabilistic or deterministic algorithm
$\mathsf{A}$ and a quantum algorithm $\mathpzc{A}$ on an input $x$ and
$\mathpzc{x}$, respectively. When we explicitly show that $\mathsf{A}$ uses
randomness $r$, we write $y\leftarrow\mathsf{A}(x;r)$. PPT and QPT algorithms
stand for probabilistic polynomial-time algorithms and polynomial-time quantum
algorithms, respectively. Let ${\mathsf{negl}}$ denote a negligible function.
Let $\stackrel{{\scriptstyle\mathsf{c}}}{{\approx}}$ denote computational
indistinguishability.

###  2.1 Quantum information

We review several quantum information concepts.

#### Basics.

Let $\mathcal{H}$ be a finite-dimensional complex Hilbert space. A (pure)
quantum state is a vector $\ket{\psi}\in\mathcal{H}$. Let
$\mathcal{S}(\mathcal{H})$ be the space of Hermitian operators on
$\mathcal{H}$. A density matrix is a Hermitian operator
$\mathpzc{X}\in\mathcal{S}(\mathcal{H})$ with $\Tr(\mathpzc{X})=1$, which is a
probabilistic mixture of pure states. A quantum state over
$\mathcal{H}=\mathbb{C}^{2}$ is called qubit, which can be represented by the
linear combination of the standard basis $\\{\ket{0},\ket{1}\\}$. More
generally, a quantum system over $(\mathbb{C}^{2})^{\otimes n}$ is called an
$n$-qubit quantum system for $n\in\mathbb{N}\setminus\\{0\\}$.

A Hilbert space is divided into registers
$\mathcal{H}=\mathcal{H}^{{\color[rgb]{.5,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,.5,.5}\pgfsys@color@gray@stroke{.5}\pgfsys@color@gray@fill{.5}{\mathsf{R}}}_{1}}\otimes\mathcal{H}^{{\color[rgb]{.5,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,.5,.5}\pgfsys@color@gray@stroke{.5}\pgfsys@color@gray@fill{.5}{\mathsf{R}}}_{2}}\otimes\cdots\otimes\mathcal{H}^{{\color[rgb]{.5,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,.5,.5}\pgfsys@color@gray@stroke{.5}\pgfsys@color<EMAIL_ADDRESS>We sometimes write
$\mathpzc{X}^{{\color[rgb]{.5,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,.5,.5}\pgfsys@color@gray@stroke{.5}\pgfsys@color<EMAIL_ADDRESS>to emphasize that the operator $\mathpzc{X}$ acts on register
$\mathcal{H}^{{\color[rgb]{.5,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,.5,.5}\pgfsys@color@gray@stroke{.5}\pgfsys@color<EMAIL_ADDRESS>superscript parts are gray colored. When we apply
$\mathpzc{X}^{{\color[rgb]{.5,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,.5,.5}\pgfsys@color@gray@stroke{.5}\pgfsys@color<EMAIL_ADDRESS>to registers
$\mathcal{H}^{{\color[rgb]{.5,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,.5,.5}\pgfsys@color@gray@stroke{.5}\pgfsys@color<EMAIL_ADDRESS>and
$\mathcal{H}^{{\color[rgb]{.5,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,.5,.5}\pgfsys@color@gray@stroke{.5}\pgfsys@color<EMAIL_ADDRESS>$\mathpzc{X}^{{\color[rgb]{.5,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,.5,.5}\pgfsys@color@gray@stroke{.5}\pgfsys@color<EMAIL_ADDRESS>is identified with
$\mathpzc{X}^{{\color[rgb]{.5,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,.5,.5}\pgfsys@color@gray@stroke{.5}\pgfsys@color@gray@fill{.5}{\mathsf{R}}}_{1}}\otimes\bm{I}^{{\color[rgb]{.5,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,.5,.5}\pgfsys@color@gray@stroke{.5}\pgfsys@color<EMAIL_ADDRESS>
A unitary operation is represented by a complex matrix $\bm{U}$ such that
$\bm{U}\bm{U}^{\dagger}=\bm{I}$. The operation $\bm{U}$ transforms
$\ket{\psi}$ and $\mathpzc{X}$ into $\bm{U}\ket{\psi}$ and
$\bm{U}\mathpzc{X}\bm{U}^{\dagger}$, respectively. A projector $\bm{P}$ is a
Hermitian operator ($\bm{P}^{\dagger}=\bm{P}$) such that $\bm{P}^{2}=\bm{P}$.

For a quantum state $\mathpzc{X}$ over two registers
$\mathcal{H}^{{\color[rgb]{.5,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,.5,.5}\pgfsys@color@gray@stroke{.5}\pgfsys@color<EMAIL_ADDRESS>and
$\mathcal{H}^{{\color[rgb]{.5,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,.5,.5}\pgfsys@color@gray@stroke{.5}\pgfsys@color<EMAIL_ADDRESS>we denote the state in
$\mathcal{H}^{{\color[rgb]{.5,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,.5,.5}\pgfsys@color@gray@stroke{.5}\pgfsys@color<EMAIL_ADDRESS>as
$\mathpzc{X}[{\color[rgb]{.5,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,.5,.5}\pgfsys@color@gray@stroke{.5}\pgfsys@color<EMAIL_ADDRESS>where
$\mathpzc{X}[{\color[rgb]{.5,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,.5,.5}\pgfsys@color@gray@stroke{.5}\pgfsys@color<EMAIL_ADDRESS>is a partial trace of $\mathpzc{X}$ (trace out
${\color[rgb]{.5,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,.5,.5}\pgfsys@color@gray@stroke{.5}\pgfsys@color@gray@fill{.5}{\mathsf{R}}}_{2}$).

#### Measurement Implementation

We review some concepts on quantum measurements.

###### Definition 2.1 (Projective Implementation [Zha20]).

Let:

  * •

$\mathcal{D}$ be a finite set of distributions over an index set
$\mathcal{I}$.

  * •

$\mathcal{P}=\\{\bm{P}_{i}\\}_{i\in\mathcal{I}}$ be a POVM

  * •

$\mathcal{E}=\\{\bm{E}_{D}\\}_{D\in\mathcal{D}}$ be a projective measurement
with index set $\mathcal{D}$.

We consider the following measurement procedure.

  1. 1.

Measure under the projective measurement $\mathcal{E}$ and obtain a
distribution $D$.

  2. 2.

Output a random sample from the distribution $D$.

We say $\mathcal{E}$ is the projective implementation of $\mathcal{P}$,
denoted by $\mathsf{ProjImp}(\mathcal{P})$, if the measurement process above
is equivalent to $\mathcal{P}$.

###### Theorem 2.2 ([Zha20, Lemma 1]).

Any binary outcome POVM $\mathcal{P}=(\bm{P},\bm{I}-\bm{P})$ has a unique
projective implementation $\mathsf{ProjImp}(\mathcal{P})$.

###### Definition 2.3 (Mixture of Projetive Measurement [Zha20]).

Let $D:\mathcal{R}\rightarrow\mathcal{I}$ where $\mathcal{R}$ and
$\mathcal{I}$ are some sets. Let
$\\{(\bm{P}_{i},\bm{Q}_{i})\\}_{\in\mathcal{I}}$ be a collection of binary
projective measurement. The mixture of projective measurements associated to
$\mathcal{R}$, $\mathcal{I}$, $D$, and
$\\{(\bm{P}_{i},\bm{Q}_{i})\\}_{\in\mathcal{I}}$ is the binary POVM
$\mathcal{P}_{D}=(\bm{P}_{D},\bm{Q}_{D})$ defined as follows

$\displaystyle\bm{P}_{D}=\sum_{i\in\mathcal{I}}\Pr[i\leftarrow
D(R)]\bm{P}_{i}$
$\displaystyle\bm{Q}_{D}=\sum_{i\in\mathcal{I}}\Pr[i\leftarrow
D(R)]\bm{Q}_{i},$ (1)

where $R$ is uniformly distributed in $\mathcal{R}$.

###### Definition 2.4 (Shift Distance).

For two distributions $D_{0},D_{1}$, the shift distance with parameter
$\epsilon$, denoted by $\Delta_{\mathsf{Shift}}^{\epsilon}(D_{0},D_{1})$, is
the smallest quantity $\delta$ such that for all $x\in\mathbb{R}$:

$\displaystyle\Pr[D_{0}\leq x]$ $\displaystyle\leq\Pr[D_{1}\leq
x+\epsilon]+\delta,$ $\displaystyle\Pr[D_{0}\geq x]\leq\Pr[D_{1}\geq
x-\epsilon]+\delta,$ (2) $\displaystyle\Pr[D_{1}\leq x]$
$\displaystyle\leq\Pr[D_{0}\leq x+\epsilon]+\delta,$
$\displaystyle\Pr[D_{1}\geq x]\leq\Pr[D_{0}\geq x-\epsilon]+\delta.$ (3)

For two real-valued measurements $\mathcal{M}$ and $\mathcal{N}$ over the same
quantum system, the shift distance between $\mathcal{M}$ and $\mathcal{N}$
with parameter $\epsilon$ is

$\Delta_{\mathsf{Shift}}^{\epsilon}(\mathcal{M},\mathcal{N})\coloneqq\sup_{\ket{\psi}}\Delta_{\mathsf{Shift}}^{\epsilon}(\mathcal{M}(\ket{\psi}),\mathcal{N}(\ket{\psi})).$

###### Theorem 2.5 ([Zha20, KN22]).

Let $D$ be any probability distribution and
$\mathcal{P}=\\{(\Pi_{i},\bm{I}-\Pi_{i})\\}_{i}$ be a collection of binary
outcome projective measurements. For any $0<\epsilon,\delta<1$, there exists
an algorithm of measurement
$\mathpzc{API}_{\mathcal{P},\mathcal{D}}^{\epsilon,\delta}$ that satisfies the
following.

  * •

$\Delta_{\mathsf{Shift}}^{\epsilon}(\mathpzc{API}_{\mathcal{P},D}^{\epsilon,\delta},\mathsf{ProjImp}(\mathcal{P}_{D}))\leq\delta$.

  * •

$\mathpzc{API}_{\mathcal{P},D}^{\epsilon,\delta}$ is
$(\epsilon,\delta)$-almost projective in the following sense. For any quantum
state $\ket{\psi}$, we apply $\mathpzc{API}_{\mathcal{P},D}^{\epsilon,\delta}$
twice in a row to $\ket{\psi}$ and obtain measurement outcomes $x$ and $y$,
respectively. Then, $\Pr[\absolutevalue{x-y}\leq\epsilon]\geq 1-\delta$.

  * •

$\mathpzc{API}_{\mathcal{P},D}^{\epsilon,\delta}$ is
$(\epsilon,\delta)$-reverse almost projective in the following sense. For any
quantum state $\ket{\psi}$, we apply
$\mathpzc{API}_{\mathcal{P},D}^{\epsilon,\delta}$ and
$\mathpzc{API}_{\mathcal{P}^{\mathtt{rev}},D}^{\epsilon,\delta}$ in a row to
$\ket{\psi}$ and obtain measurement outcomes $x$ and $y$, respectively, where
$\mathcal{P}^{\mathtt{rev}}=\\{(\bm{I}-\Pi_{i},\Pi_{i})\\}_{i}$. Then,
$\Pr[\absolutevalue{(1-x)-y}\leq\epsilon]\geq 1-\delta$.

  * •

The expected running time of $\mathpzc{API}_{\mathcal{P},D}^{\epsilon,\delta}$
is $T_{\mathcal{P},D}\cdot{\mathrm{poly}}(1/\epsilon,\log(1/\delta))$ where
$T_{\mathcal{P},D}$ is the combined running time of $D$, the procedure mapping
$i\rightarrow(\bm{P}_{i},\bm{I}-\bm{P}_{i})$, and the running time of
measurement $(\bm{P}_{i},\bm{I}-\bm{P}_{i})$.

###### Theorem 2.6 ([Zha20, Corollary 1]).

Let $\mathpzc{q}$ be an efficiently constructible, potentially mixed state,
and $D_{0},D_{1}$ efficiently sampleable distributions. If $D_{0}$ and $D_{1}$
are computationally indistinguishable, for any inverse polynomial $\epsilon$
and any function $\delta$, we have
$\Delta_{\mathsf{Shift}}^{3\epsilon}(\mathpzc{API}_{\mathcal{P},D_{0}}^{\epsilon,\delta},\mathpzc{API}_{\mathcal{P},D_{1}}^{\epsilon,\delta})\leq
2\delta+{\mathsf{negl}}(\lambda)$.

#### Quantum program with classical inputs and outputs

We formalize quantum programs whose inputs and outputs are always classical
strings.

###### Definition 2.7 (Quantum Program with Classical Inputs and Outputs
[ALL+21]).

A quantum program with classical inputs is a pair of quantum state
$\mathpzc{q}$ and unitaries $\\{\bm{U}_{x}\\}_{x\in[N]}$ where $[N]$ is the
domain, such that the state of the program evaluated on input $x$ is equal to
$\bm{U}_{x}\mathpzc{q}\bm{U}_{x}^{\dagger}$. We measure the first register of
$\bm{U}_{x}\mathpzc{q}\bm{U}_{x}^{\dagger}$ to obtain an output. We say that
$\\{\bm{U}_{x}\\}_{x\in[N]}$ has a compact classical description $\bm{U}$ when
applying $\bm{U}_{x}$ can be efficiently computed given $\bm{U}$ and $x$.

###  2.2 Standard Cryptographic Tools

#### Commitment.

We introduce the notion of injective commitment with equivocal mode. This is
an extension of injective commitment introduced by Cohen et al. [CHN+18].

###### Definition 2.8 (Injective Commitment with Equivocal Mode).

An injective commitment scheme $\mathsf{Com}$ with equivocal mode for the
message space $\mathcal{M}$ and random coin space $\mathcal{R}$ is a tuple of
four algorithms
$(\mathsf{Setup},\mathsf{Commit},\mathsf{EqSetup},\mathsf{Open})$.

  * •

The setup algorithm $\mathsf{Setup}$ takes as input a security parameter
$1^{\lambda}$, and outputs a commitment key $\mathsf{ck}$.

  * •

The commitment algorithm $\mathsf{Commit}$ takes as input the commitment key
$\mathsf{ck}$, a message $m\in\mathcal{M}$, and a random coin
$r\in\mathcal{R}$, and outputs a commitment $\mathsf{com}$.

  * •

The equivocation setup algorithms $\mathsf{EqSetup}$ takes as input a security
parameter $1^{\lambda}$, and outputs a commitment key $\mathsf{ck}^{*}$, a
commitment $\mathsf{com}^{*}$, and a trapdoor $\mathsf{td}$.

  * •

The open algorithm $\mathsf{Open}$ takes as input the trapdoor $\mathsf{td}$,
a message $m\in\mathcal{M}$, and a commitment $\mathsf{com}^{*}$, and outputs
a random coin $r^{*}\in\mathcal{R}$.

We say that injective commitment with equivocal mode is secure if it satisfies
the following two properties.

Injectivity:

We require that

$\displaystyle\Pr[\exists(m_{1},r_{1})\neq(m_{2},r_{2})\textrm{~{}~{}s.t.~{}~{}}\mathsf{Commit}(\mathsf{ck},m_{1};r_{1})=\mathsf{Commit}(\mathsf{ck},m_{2},r_{2})\mid\mathsf{ck}\leftarrow\mathsf{Setup}(1^{\lambda})]={\mathsf{negl}}(\lambda).$
(4)

Trapdoor Equivocality:

For any message $m\in\mathcal{M}$, we have

$\displaystyle(\mathsf{ck},\mathsf{com},r)\stackrel{{\scriptstyle\mathsf{c}}}{{\approx}}(\mathsf{ck}^{*},\mathsf{com}^{*},r^{*}),$
(5)

where $\mathsf{ck}\leftarrow\mathsf{Setup}(1^{\lambda})$,
$r\leftarrow\mathcal{R}$,
$\mathsf{com}\leftarrow\mathsf{Commit}(\mathsf{ck},m;r)$,
$(\mathsf{ck}^{*},\mathsf{com}^{*},\mathsf{td})\leftarrow\mathsf{EqSetup}(1^{\lambda})$,
and $r^{*}\leftarrow\mathsf{Open}(\mathsf{td},m,\mathsf{com}^{*})$.

We do not explicitly require a hiding property since we do not need it in this
work.

###### Theorem 2.9.

If the LWE assumption holds, there exists a secure injective commitment with
equivocal mode.

We can obtain Theorem 2.9 from the construction of injective commitment by
Kitagawa and Nishimaki [KN22] since it is Naor’s commitment scheme [Nao91] and
it is well known that Naor’s commitment has a trapdoor equivocal mode. See
Appendix C for the construction.

#### Ciphertext-policy attribute-based encryption.

We define ciphertext-policy attribute-base encryption (CP-ABE) and adaptive-
indistinguishability (AD-IND security) and adaptive-simulation security (AD-
SIM security) for it.

###### Definition 2.10 (CP-ABE (Syntax)).

A CP-ABE scheme is a tuple of PPT algorithms
$(\mathsf{Setup},\mathsf{KG},\mathsf{Enc},\mathsf{Dec})$ with plaintext space
$\mathcal{M}$.

$\mathsf{Setup}(1^{\lambda})\rightarrow(\mathsf{mpk},\mathsf{msk})$:

The setup algorithm takes as input the security parameter $1^{\lambda}$ and
outputs a key pair $(\mathsf{mpk},\mathsf{msk})$.

$\mathsf{KG}(\mathsf{msk},x)\rightarrow\mathsf{sk}_{x}$:

The key generation algorithm takes as input the master secret key
$\mathsf{msk}$ and an attribute $x$, and outputs a decryption key
$\mathsf{sk}_{x}$.

$\mathsf{Enc}(\mathsf{mpk},C,\mathsf{m})\rightarrow\mathsf{ct}$:

The encryption algorithm takes as input $\mathsf{mpk}$, policy $C$, and a
plaintext $\mathsf{m}\in\mathcal{M}$, and outputs a ciphertext $\mathsf{ct}$.

$\mathsf{Dec}(\mathsf{sk}_{x},\mathsf{ct})\rightarrow\mathsf{m}^{\prime}\mbox{
or }\bot$:

The decryption algorithm takes as input $\mathsf{sk}_{x}$ and $\mathsf{ct}$
and outputs a plaintext $\mathsf{m}^{\prime}$ or $\bot$.

Decryption Correctness:

There exists a negligible function ${\mathsf{negl}}$ such that for any
$\mathsf{m}\in\mathcal{M}$, $C$, and $x$ such that $C(x)=1$, we have

$\displaystyle\Pr\left[\mathsf{Dec}(\mathsf{sk}_{x},\mathsf{ct})=\mathsf{m}\
\middle|\begin{array}[]{ll}(\mathsf{mpk},\mathsf{msk})\leftarrow\mathsf{Setup}(1^{\lambda})\\\
\mathsf{sk}_{x}\leftarrow\mathsf{KG}(\mathsf{msk},x)\\\
\mathsf{ct}\leftarrow\mathsf{Enc}(\mathsf{mpk},C,\mathsf{m})\end{array}\right]=1-{\mathsf{negl}}(\lambda).$
(9)

###### Definition 2.11 (AD-IND Security for CP-ABE).

Let
$\mathsf{CPABE}=(\mathsf{Setup},\mathsf{KG},\allowbreak\mathsf{Enc},\allowbreak\mathsf{Dec})$
be a CP-ABE scheme. We consider the following security experiment
$\mathsf{Exp}_{\mathsf{CPABE},\mathpzc{A}}^{\mathsf{ad}\mbox{-}\mathsf{ind}}(\lambda,\mathsf{coin})$
for a QPT adversary $\mathpzc{A}$.

  1. 1.

The challenger computes
$(\mathsf{mpk},\mathsf{msk})\leftarrow\mathsf{KG}(1^{\lambda})$ and sends
$\mathsf{mpk}$ to $\mathpzc{A}$.

  2. 2.

$\mathpzc{A}$ can get access to the following oracle.

$O_{\mathtt{\mathsf{KG},1}}(x)$:

Given $x$, it returns $\mathsf{sk}_{x}\leftarrow\mathsf{KG}(\mathsf{msk},x)$.

  3. 3.

$\mathpzc{A}$ sends $C$ and
$(\mathsf{m}_{0},\mathsf{m}_{1})\in\mathcal{M}^{2}$ to the challenger, where
$C$ satisfies $C(x)=0$ for all $x$ queried by $\mathpzc{A}$ in the previous
step. The challenger returns
$\mathsf{ct}\leftarrow\mathsf{Enc}(\mathsf{mpk},C,m_{\mathsf{coin}})$ to
$\mathpzc{A}$.

  4. 4.

$\mathpzc{A}$ can get access to the following oracle.

$O_{\mathtt{\mathsf{KG},2}}(x)$:

Given $x$, if $C(x)=0$, it returns
$\mathsf{sk}_{x}\leftarrow\mathsf{KG}(\mathsf{msk},x)$. If $C(x)=1$, it
returns $\bot$.

  5. 5.

$\mathpzc{A}$ outputs $\mathsf{coin}^{\prime}\in\\{0,1\\}$.

We say that $\mathsf{CPABE}$ is AD-IND secure if for any QPT adversary
$\mathpzc{A}$, it holds that

$\displaystyle\mathsf{Adv}_{\mathsf{CPABE},\mathpzc{A}}^{\mathsf{ad}\mbox{-}\mathsf{ind}}(\lambda)\coloneqq\absolutevalue{\Pr[\mathsf{Exp}_{\mathsf{CPABE},\mathpzc{A}}^{\mathsf{ad}\mbox{-}\mathsf{ind}}(\lambda,0)=1]-\Pr[\mathsf{Exp}_{\mathsf{CPABE},\mathpzc{A}}^{\mathsf{ad}\mbox{-}\mathsf{ind}}(\lambda,1)=1]}\leq{\mathsf{negl}}(\lambda).$
(10)

######  Remark 2.12.

We can consider the selective variant of Definition 2.11, where $\mathpzc{A}$
declares $C$ at the beginning of the games. We can also consider the selective
variant of Definition 2.14 introduced below. We denote these notions by SEL-
IND and SEL-SIM, respectively.

###### Theorem 2.13 ([GVW15a, BGG+14]).

If the LWE assumption holds, there exists SEL-IND secure CP-ABE for all
boolean circuits. In addition, if the LWE assumption holds against sub-
exponential time algorithms, there exists ADA-IND secure CP-ABE for all
boolean circuits.

We define AD-SIM security for CP-ABE, which is a natural adaptation of AD-SIM
security for functional encryption [GVW12] to CP-ABE.

###### Definition 2.14 (AD-SIM Security for CP-ABE).

Let
$\mathsf{CPABE}=(\mathsf{Setup},\mathsf{KG},\allowbreak\mathsf{Enc},\allowbreak\mathsf{Dec})$
be a CP-ABE scheme. We consider the following security experiment
$\mathsf{Exp}_{\mathsf{CPABE},\mathpzc{Sim},\mathpzc{A}}^{\mathsf{ad}\mbox{-}\mathsf{sim}}(\lambda,\mathsf{coin})$
for a QPT simulator $\mathpzc{Sim}=(\mathpzc{SimEnc},\mathpzc{SimKG})$ and a
QPT adversary $\mathpzc{A}$.

  1. 1.

The challenger computes
$(\mathsf{mpk},\mathsf{msk})\leftarrow\mathsf{KG}(1^{\lambda})$ and sends
$\mathsf{mpk}$ to $\mathpzc{A}$.

  2. 2.

$\mathpzc{A}$ can get access to the following oracle.

$O_{\mathtt{\mathsf{KG},1}}(x)$:

Given $x$, it returns $\mathsf{sk}_{x}\leftarrow\mathsf{KG}(\mathsf{msk},x)$.

  3. 3.

$\mathpzc{A}$ sends $C$ and $m\in\mathcal{M}$ to the challenger, where $C$
satisfies $C(x)=0$ for all $x$ queried by $\mathpzc{A}$ in the previous step.
The challenger does the following.

     * •

If $\mathsf{coin}=0$, the challenger generates
$\mathsf{ct}\leftarrow\mathsf{Enc}(\mathsf{mpk},C,m)$ and returns
$\mathsf{ct}$ to $\mathpzc{A}$.

     * •

If $\mathsf{coin}=1$, the challenger generates
$(\mathsf{ct},\mathsf{st})\leftarrow\mathpzc{SimEnc}(\mathsf{mpk},C)$ and
returns $\mathsf{ct}$ to $\mathpzc{A}$.

  4. 4.

$\mathpzc{A}$ can get access to the following oracle.

$O_{\mathtt{\mathsf{KG},2}}(x)$:

Given $x$, if $C(x)=0$, it returns
$\mathsf{sk}_{x}\leftarrow\mathsf{KG}(\mathsf{msk},x)$. If $C(x)=1$, it does
the following.

     * •

If $\mathsf{coin}=0$, the challenger returns
$\mathsf{sk}_{x}\leftarrow\mathsf{KG}(\mathsf{msk},x)$ to $\mathpzc{A}$.

     * •

If $\mathsf{coin}=1$, the challenger returns
$\mathsf{sk}_{x}\leftarrow\mathpzc{SimKG}(\mathsf{msk},\mathsf{st},x,m)$ to
$\mathpzc{A}$.

  5. 5.

$\mathpzc{A}$ outputs $\mathsf{coin}^{\prime}\in\\{0,1\\}$.

We say that $\mathsf{CPABE}$ is AD-SIM secure if there exists $\mathpzc{Sim}$
such that for any QPT adversary $\mathpzc{A}$, it holds that

$\displaystyle\mathsf{Adv}_{\mathsf{CPABE},\mathpzc{Sim},\mathpzc{A}}^{\mathsf{ad}\mbox{-}\mathsf{sim}}(\lambda)\coloneqq\absolutevalue{\Pr[\mathsf{Exp}_{\mathsf{CPABE},\mathpzc{Sim},\mathpzc{A}}^{\mathsf{ad}\mbox{-}\mathsf{sim}}(\lambda,0)=1]-\Pr[\mathsf{Exp}_{\mathsf{CPABE},\mathpzc{Sim},\mathpzc{A}}^{\mathsf{ad}\mbox{-}\mathsf{sim}}(\lambda,1)=1]}\leq{\mathsf{negl}}(\lambda).$
(11)

AD-SIM security has been widely studied for functional encryption, but as far
as we know, there was no previous work studied it for CP-ABE. In Appendix A,
we show how to transform any AD-IND secure CP-ABE scheme into AD-SIM secure
one by using tools implied by the LWE assumption.

#### Compute-and-compare obfuscation.

We define a class of circuits called compute-and-compare circuits for which we
study copy protection and secure software leasing in this work.

###### Definition 2.15 (Compute-and-Compare Circuits).

A compute-and-compare circuit $\mathbf{CC}[P,\mathsf{lock},\mathsf{m}]$ is of
the form

$\mathbf{CC}[P,\mathsf{lock},\mathsf{m}](x)\left\\{\begin{array}[]{ll}\mathsf{m}&(P(x)=\mathsf{lock})\\\
0&(\text{otherwise})~{},\end{array}\right.$

where $P$ is a circuit, $\mathsf{lock}$ is a string called lock value, and
$\mathsf{m}$ is a message.

We introduce the definition of compute-and-compare obfuscation. We assume that
a program $P$ has an associated set of parameters $\mathsf{pp}_{P}$ (input
size, output size, circuit size) which we do not need to hide.

###### Definition 2.16 (Compute-and-Compare Obfuscation).

A PPT algorithm $\mathsf{CC}.\mathsf{Obf}$ is an obfuscator for the family of
distributions $D=\\{D_{\lambda}\\}$ if the following holds:

Functionality Preserving:

There exists a negligible function ${\mathsf{negl}}$ such that for all program
$P$, all lock value $\mathsf{lock}$, and all message $\mathsf{m}$, it holds
that

$\displaystyle\Pr[\forall
x,\tilde{P}(x)=\mathbf{CC}[P,\mathsf{lock},\mathsf{m}](x)\mid\tilde{P}\leftarrow\mathsf{CC}.\mathsf{Obf}(1^{\lambda},P,\mathsf{lock},\mathsf{m})]=1-{\mathsf{negl}}(\lambda).$
(12)

Distributional Indistinguishability:

There exists an efficient simulator $\mathsf{Sim}$ such that for all message
$\mathsf{m}$, we have

$\displaystyle(\mathsf{CC}.\mathsf{Obf}(1^{\lambda},P,\mathsf{lock},\mathsf{m}),\mathpzc{aux})\stackrel{{\scriptstyle\mathsf{c}}}{{\approx}}(\mathsf{Sim}(1^{\lambda},\mathsf{pp}_{P},\absolutevalue{\mathsf{m}}),\mathpzc{aux}),$
(13)

where $(P,\mathsf{lock},\mathpzc{aux})\leftarrow D_{\lambda}$.

###### Theorem 2.17 ([GKW17, WZ17]).

If the LWE assumption holds, there exists compute-and-compare obfuscation for
all families of distributions $D=\\{D_{\lambda}\\}$, where each $D_{\lambda}$
outputs uniformly random lock value $\mathsf{lock}$ independent of $P$ and
$\mathpzc{aux}$.

###  2.3 Quantum Cryptographic Tools

#### Unclonable encryption.

We introduce the definition of secret key unclonable encryption (SKUE) [BL20]
and one-time indistinguishability for it.

###### Definition 2.18 (SKUE (Syntax)).

A SKUE scheme with the message space $\mathcal{M}$ is a tuple of quantum
algorithms $(\mathsf{KG},\mathpzc{Enc},\mathpzc{Dec})$.

$\mathsf{KG}(1^{\lambda})\rightarrow\mathsf{uk}$:

The key generation algorithm takes as input the security parameter
$1^{\lambda}$ and outputs a key $\mathsf{uk}$.

$\mathpzc{Enc}(\mathsf{uk},m)\rightarrow\mathpzc{ct}$:

The encryption algorithm takes as input $\mathsf{uk}$ and a plaintext
$\mathsf{m}\in\mathcal{M}$ and outputs a ciphertext $\mathpzc{ct}$.

$\mathpzc{Dec}(\mathsf{uk},\mathpzc{ct})\rightarrow\mathsf{m}^{\prime}$:

The decryption algorithm takes as input $\mathsf{uk}$ and $\mathpzc{ct}$ and
outputs a plaintext $\mathsf{m}^{\prime}\in\mathcal{M}$ or $\bot$.

Decryption correctness:

For any $\mathsf{m}\in\mathcal{M}$, it holds that

$\displaystyle\Pr\left[\mathpzc{Dec}(\mathsf{uk},\mathpzc{ct})=\mathsf{m}\
\middle|\begin{array}[]{ll}\mathsf{uk}\leftarrow\mathsf{KG}(1^{\lambda})\\\
\mathpzc{ct}\leftarrow\mathpzc{Enc}(\mathsf{uk},\mathsf{m})\end{array}\right]=1-{\mathsf{negl}}(\lambda).$
(16)

###### Definition 2.19 (One-Time Unclonable-Indistinguishable Security for
SKUE).

Let $\mathsf{UE}=(\mathpzc{Enc},\mathpzc{Dec})$ be an SKUE scheme with the key
space $\mathcal{K}$ and the message space $\mathcal{M}$. We consider the
following security experiment
$\mathsf{Exp}_{\mathsf{UE},\mathpzc{A}}^{\mathsf{ot}\mbox{-}\mathsf{ind}\mbox{-}\mathsf{clone}}(\lambda)$,
where $\mathpzc{A}=(\mathpzc{A}_{0},\mathpzc{A}_{1},\mathpzc{A}_{2})$.

  1. 1.

$\mathpzc{A}_{0}$ sends $(m_{0},m_{1})$ to the challenger.

  2. 2.

The challenger generates $\mathsf{coin}\leftarrow\\{0,1\\}$,
$\mathsf{uk}\leftarrow\mathsf{KG}(1^{\lambda})$, and
$\mathpzc{ct}\leftarrow\mathpzc{Enc}(\mathsf{uk},m_{\mathsf{coin}})$, and
sends $\mathpzc{ct}$ to $\mathpzc{A}_{0}$.

  3. 3.

$\mathpzc{A}_{0}$ creates a bipartite state $\mathpzc{q}$ over registers
${\color[rgb]{.5,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,.5,.5}\pgfsys@color@gray@stroke{.5}\pgfsys@color<EMAIL_ADDRESS>and
${\color[rgb]{.5,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,.5,.5}\pgfsys@color@gray@stroke{.5}\pgfsys@color<EMAIL_ADDRESS>$\mathpzc{A}$ sends
$\mathpzc{q}[{\color[rgb]{.5,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,.5,.5}\pgfsys@color@gray@stroke{.5}\pgfsys@color<EMAIL_ADDRESS>and
$\mathpzc{q}[{\color[rgb]{.5,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,.5,.5}\pgfsys@color@gray@stroke{.5}\pgfsys@color<EMAIL_ADDRESS>to $\mathpzc{A}_{1}$ and $\mathpzc{A}_{2}$, respectively.

  4. 4.

The challenger sends $\mathsf{uk}$ to $\mathpzc{A}_{1}$ and $\mathpzc{A}_{2}$.
$\mathpzc{A}_{1}$ and $\mathpzc{A}_{2}$ respectively output
$\mathsf{coin}_{1}^{\prime}$ and $\mathsf{coin}_{2}^{\prime}$. If
$\mathsf{coin}_{i}^{\prime}=\mathsf{coin}$ for $i\in\\{1,2\\}$, the challenger
outputs $1$, otherwise outputs $0$.

We say that $\mathsf{UE}$ is one-time unclonable-indistinguishable secure SKUE
scheme if for any QPT $\mathpzc{A}$, it holds that

$\displaystyle\mathsf{Adv}_{\mathsf{UE},\mathpzc{A}}^{\mathsf{ot}\mbox{-}\mathsf{ind}\mbox{-}\mathsf{clone}}(\lambda)\coloneqq\Pr[\mathsf{Exp}_{\mathsf{UE},\mathpzc{A}}^{\mathsf{ot}\mbox{-}\mathsf{ind}\mbox{-}\mathsf{clone}}(\lambda)=1]\leq\frac{1}{2}+{\mathsf{negl}}(\lambda).$
(17)

#### Single-decryptor encryption.

We review the definition of single-decryptor encryption (SDE). We consider a
one-time secret key variant of SDE by Coladangelo et al. [CLLZ21] in this
work.

###### Definition 2.20 (Secret Key SDE (Syntax)).

A secret key SDE scheme $\mathsf{SDE}$ is a tuple of quantum algorithms
$(\mathpzc{KG},\mathsf{Enc},\mathpzc{Dec})$ with plaintext space
$\mathcal{M}$.

$\mathpzc{KG}(1^{\lambda})\rightarrow(\mathsf{ek},\mathpzc{dk})$:

The key generation algorithm takes as input the security parameter
$1^{\lambda}$ and outputs an encryption key $\mathsf{ek}$ and a quantum
decryption key $\mathpzc{dk}$.

$\mathsf{Enc}(\mathsf{ek},m)\rightarrow\mathsf{ct}$:

The encryption algorithm takes as input $\mathsf{ek}$ and a plaintext
$m\in\mathcal{M}$ and outputs a ciphertext $\mathsf{ct}$.

$\mathpzc{Dec}(\mathpzc{dk},\mathsf{ct})\rightarrow m^{\prime}$:

The decryption algorithm takes as input $\mathpzc{dk}$ and $\mathsf{ct}$ and
outputs a plaintext $m^{\prime}\in\mathcal{M}$ or $\bot$.

Decryption correctness:

There exists a negligible function ${\mathsf{negl}}$ such that for any
$m\in\mathcal{M}$,

$\displaystyle\Pr\left[\mathpzc{Dec}(\mathpzc{dk},\mathsf{ct})=m\
\middle|\begin{array}[]{ll}(\mathsf{ek},\mathpzc{dk})\leftarrow\mathpzc{KG}(1^{\lambda})\\\
\mathsf{ct}\leftarrow\mathsf{Enc}(\mathsf{ek},m)\end{array}\right]=1-{\mathsf{negl}}(\lambda).$
(20)

###### Definition 2.21 (One-Time Strong Anti-Piracy Security for Secret Key
SDE).

Let $\gamma\in[0,1]$. Let
$\mathsf{SDE}=(\mathpzc{KG},\mathsf{Enc},\mathpzc{Dec})$ be a secret key SDE
scheme. We consider the one-time strong anti-piracy game
$\mathsf{Exp}_{\mathsf{SDE},\mathpzc{A}}^{\mathsf{ot}\mbox{-}\mathsf{santi}\mbox{-}\mathsf{piracy}}(\lambda,\gamma)$
between the challenger and an adversary
$\mathpzc{A}=(\mathpzc{A}_{0},\mathpzc{A}_{1},\mathpzc{A}_{2})$ below.

  1. 1.

The challenger generates
$(\mathsf{ek},\mathpzc{dk})\leftarrow\mathpzc{KG}(1^{\lambda})$ and sends
$\mathpzc{dk}$ to $\mathpzc{A}_{0}$.

  2. 2.

$\mathpzc{A}_{0}$ creates a bipartite state $\mathpzc{q}$ over registers
${\color[rgb]{.5,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,.5,.5}\pgfsys@color@gray@stroke{.5}\pgfsys@color<EMAIL_ADDRESS>and
${\color[rgb]{.5,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,.5,.5}\pgfsys@color@gray@stroke{.5}\pgfsys@color<EMAIL_ADDRESS>$\mathpzc{A}$ sends $(m_{0},m_{1})$,
$\mathpzc{q}[{\color[rgb]{.5,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,.5,.5}\pgfsys@color@gray@stroke{.5}\pgfsys@color<EMAIL_ADDRESS>and
$\mathpzc{q}[{\color[rgb]{.5,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,.5,.5}\pgfsys@color@gray@stroke{.5}\pgfsys@color<EMAIL_ADDRESS>to the challenger, $\mathpzc{A}_{1}$, and $\mathpzc{A}_{2}$, respectively.

  3. 3.

$\mathpzc{A}_{1}$ and $\mathpzc{A}_{2}$ respectively output
$\mathpzc{D}_{1}=(\rho[{\color[rgb]{.5,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,.5,.5}\pgfsys@color@gray@stroke{.5}\pgfsys@color@gray@fill{.5}{\mathsf{R}}}_{1}],\bm{U}_{1})$
and
$\mathpzc{D}_{2}=(\rho[{\color[rgb]{.5,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,.5,.5}\pgfsys@color@gray@stroke{.5}\pgfsys@color@gray@fill{.5}{\mathsf{R}}}_{2}],\bm{U}_{2})$.

  4. 4.

For $\alpha\in[2]$, let
$\bm{P}_{\alpha}=(\bm{P}_{\alpha,b,\mathsf{ct}},\bm{I}-\bm{P}_{\alpha,b,\mathsf{ct}})_{b,\mathsf{ct}}$
be a collection of binary projective measurements, where

$\displaystyle\bm{P}_{\alpha,b,\mathsf{ct}}=\bm{U}_{\alpha,\mathsf{ct}}^{\dagger}\ket{b}\bra{b}\bm{U}_{\alpha,\mathsf{ct}}.$
(21)

We also define $D$ as the distribution that generates $b\leftarrow\\{0,1\\}$
and $\mathsf{ct}\leftarrow\mathsf{Enc}(\mathsf{ek},m_{b})$ and outputs
$(b,\mathsf{ct})$. Also, for $\alpha\in[2]$, we denote the mixture of
$\bm{P}_{\alpha}$ with respect to $D$ as $\bm{P}_{\alpha,D}$. Then, for every
$\alpha\in[2]$, the challenger applies $\mathsf{ProjImp}(\bm{P}_{\alpha,D})$
to
$\rho[{\color[rgb]{.5,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,.5,.5}\pgfsys@color@gray@stroke{.5}\pgfsys@color<EMAIL_ADDRESS>and obtains $p_{\alpha}$. If $p_{\alpha}>\frac{1}{2}+\gamma$ for every
$\alpha\in[2]$, the challenger outputs $1$. Otherwise, the challenger outputs
$0$.

We say that $\mathsf{SDE}$ is one-time strong anti-piracy secure if for any
$\gamma\in[0,1]$ and QPT adversary $\mathpzc{A}$, it satisfies that

$\displaystyle\mathsf{Adv}_{\mathsf{SDE},\mathpzc{A}}^{\mathsf{ot}\mbox{-}\mathsf{santi}\mbox{-}\mathsf{piracy}}(\lambda,\gamma)\coloneqq\Pr[\mathsf{Exp}_{\mathsf{SDE},\mathpzc{A}}^{\mathsf{ot}\mbox{-}\mathsf{santi}\mbox{-}\mathsf{piracy}}(\lambda,\gamma)=1]={\mathsf{negl}}(\lambda).$
(22)

######  Remark 2.22.

Readers might think the meaning of “one-time” is unclear in Definition 2.21.
Here, “one-time” means that $\mathpzc{A}_{0}$ cannot access an encryption
oracle that returns a ciphertext for a query $\mathsf{m}$. This naming might
sound strange since $\mathpzc{A}_{0}$ does not receive any ciphertext.
However, we stick to this naming for correspondence with one-time unclonable-
indistinguishable security of unclonable encryption in Definition 2.19.

######  Remark 2.23 (On the issue in indistinguishability-based definitions).

There are two indistinguishability-based security notions for SDE. The first
one is defined by Georgiou and Zhandry (denoted by GZ) [GZ20] and the second
one is defined by Coladangelo et al. (denoted by CLLZ)101010They call “CPA-
style anti-piracy security”. [CLLZ21]. Both of them are defined using a
security game similar to that in Definition 2.21, except that
$\mathpzc{A}_{1}$ and $\mathpzc{A}_{2}$ are given the challenge ciphertexts
and required to guess the challenge bits. In the GZ definition,
$\mathpzc{A}_{1}$ and $\mathpzc{A}_{2}$ receive the same ciphertext
$\mathsf{Enc}(\mathsf{sk},m_{\mathsf{coin}})$ for the single challenge bit.
However, in the CLLZ definition, $\mathpzc{A}_{1}$ and $\mathpzc{A}_{2}$
receive different ciphertexts
$\mathsf{Enc}(\mathsf{sk},m_{\mathsf{coin}_{1}})$ and
$\mathsf{Enc}(\mathsf{sk},m_{\mathsf{coin}_{2}})$, respectively, where
$\mathsf{coin}_{1}$ and $\mathsf{coin}_{2}$ are independent challenge bits.
Currently, the relationship between these two security notions for SDE remains
elusive.111111Ananth et al. [AKL23] show the relationship between _one-
wayness-based_ security with the same ciphertext and one with the different
ciphertexts. The GZ definition is known to imply unclonable-indistinguishable
secure unclonable encryption, but the CLLZ definition is not. Also, strong
anti-piracy security defined in Definition 2.21 implies the CLLZ definition
but not the GZ definition.

#### Quantum fully homomorphic encryption.

We introduce quantum fully homomorphic encryption (QFHE) with classical
ciphretexts.

###### Definition 2.24 (QFHE with Classical Ciphertexts [Mah18, Bra18]).

A QFHE scheme with classical ciphertext is a tuple of algorithms
$(\mathsf{KG},\mathsf{Enc},\mathpzc{Eval},\mathsf{Dec})$.

$\mathsf{KG}(1^{\lambda})\rightarrow(\mathsf{pk},\mathsf{sk})$:

The key generation algorithm takes as input the security parameter
$1^{\lambda}$ and outputs a key pair $(\mathsf{pk},\mathsf{sk})$.

$\mathsf{Enc}(\mathsf{pk},m)\rightarrow\mathsf{ct}$:

The encryption algorithm takes as input a public key $\mathsf{pk}$ and a
plaintext $m$, and outputs a ciphertext $\mathsf{ct}$. Without loss of
generality, we can assume that a ciphertext includes the public key
$\mathsf{pk}$.

$\mathpzc{Eval}(\mathpzc{C},\rho,\mathsf{ct}_{1},\cdots,\mathsf{ct}_{n})\rightarrow\mathsf{evct}$:

The evaluation algorithm takes as input a quantum circuit $\mathpzc{C}$ with
classical outputs, quantum state $\rho$, and ciphertexts
$\mathsf{ct}_{1},\cdots,\mathsf{ct}_{n}$, and outputs a classical ciphertext
$\mathsf{evct}$.

$\mathsf{Dec}(\mathsf{sk},\mathsf{ct})\rightarrow m^{\prime}$:

The decryption algorithm takes as input a secret key $\mathsf{sk}$ and a
ciphertext $\mathsf{ct}$, and outputs a plaintext $m$.

Decryption Correctness:

Let $(\mathsf{pk},\mathsf{sk})\leftarrow\mathsf{KG}(1^{\lambda})$. Let
$(m_{1},\cdots,m_{n})$ be any $n$ messages. For any $i\in[n]$, let
$\mathsf{ct}_{i}\leftarrow\mathsf{Enc}(\mathsf{pk},m_{i})$ for every
$i\in[n]$. Let $\mathpzc{C}$ be a quantum circuit that takes a quantum state
and $n$ classical input, $\rho$ a quantum state, and
$\mathsf{evct}\leftarrow\mathpzc{Eval}(\mathpzc{C},\rho,\mathsf{ct}_{1},\cdots,\mathsf{ct}_{n})$.
Then, we have
$\mathsf{Dec}(\mathsf{sk},\mathsf{evct})=\mathpzc{C}(\rho,m_{1},\cdots,m_{n})$.

Semantic Security:

For any two messages of equal length $m_{0},m_{1}$, we have

$\displaystyle(\mathsf{pk},\mathsf{Enc}(\mathsf{pk},m_{0}))\stackrel{{\scriptstyle\mathsf{c}}}{{\approx}}(\mathsf{pk},\mathsf{Enc}(\mathsf{pk},m_{1})),$
(23)

where $(\mathsf{pk},\mathsf{sk})\leftarrow\mathsf{KG}(1^{\lambda})$.

The existing QFHE schemes [Mah18, Bra18] can be seen as QFHE with classical
ciphertexts, since they have a property that if the encrypted plaintext is
classical, we can make the ciphertext classical. Thus, the following theorem
holds.

###### Theorem 2.25 ([Mah18, Bra18]).

If the LWE assumption holds, there exists QFHE with classical ciphertexts.

QFHE with classical ciphertexts was previously used in the context of
impossibility on copy protection [AL21] and quantum obfuscation [ABDS21]. For
the detailed explanation for how to use the existing QFHE schemes as QFHE with
classical ciphertexts, please refer to [ABDS21].

##  3 One-out-of-Many Unclonable Security

This section introduces new unclonable security notions that we call one-out-
of-many unclonable security. The definition is roughly as follows. The one-
out-of-many unclonable security game is an indistinguishability-style game
played by a tuple of $n+1$ adversaries
$(\mathpzc{A}_{0},\mathpzc{A}_{1},\cdots,\mathpzc{A}_{n})$, where $2\leq n$ is
arbitrary. At the first stage of the game, $\mathpzc{A}_{0}$ is given a single
quantum object (such as ciphertext in unclonable encryption), generates
possibly entangled $n$-partite states $\rho_{1},\ldots,\rho_{n}$, and sends
$\rho_{k}$ to $\mathpzc{A}_{k}$ for $k\in\\{1,\ldots,n\\}$. At the second
stage, the challenger selects one of
$(\mathpzc{A}_{1},\ldots,\mathpzc{A}_{n})$ by a random
$\alpha\leftarrow\\{1,\ldots,n\\}$ and sends additional information (such as a
secret key in unclonable encryption) _only to $\mathpzc{A}_{\alpha}$_, and
only $\mathpzc{A}_{\alpha}$ tries to guess the challenge bit
$\mathsf{coin}\in\\{0,1\\}$. The one-out-of-many unclonable security
guarantees that the adversary cannot win this game with a probability
significantly better than the trivial winning probability
$\frac{1}{2}+\frac{1}{2n}$.121212Suppose $\mathpzc{A}_{0}$ forwards the given
quantum state to $\mathpzc{A}_{1}$ and nothing to
$(\mathpzc{A}_{2},\ldots,\mathpzc{A}_{n})$. If $\alpha=1$ is chosen, the
adversaries win with probability $1$ because the additional information,
together with the original quantum object, can be used to compute the
challenge bit $\mathsf{coin}$ correctly. If one of
$(\mathpzc{A}_{2},\ldots,\mathpzc{A}_{n})$ is chosen, the adversaries win with
probability $\frac{1}{2}$ by random guess. Hence, the advantage is
$\frac{1}{n}\cdot 1+\frac{n-1}{n}\cdot\frac{1}{2}=\frac{1}{2}+\frac{1}{2n}$,
which we consider as the trivial advantage. .

The one-out-of-many unclonable security notion guarantees that no adversary
can generate $n$ copies with a probability significantly better than
$\frac{1}{n}$ for any $n$. This is because an adversary who can generate $n$
copies with probability $\frac{1}{n}+\delta$ can win the one-out-of-many game
with probability at least $(\frac{1}{n}+\delta)\cdot
1+(1-\frac{1}{n}-\delta)\cdot\frac{1}{2}=\frac{1}{2}+\frac{1}{2n}+\frac{\delta}{2}$,
which violates to the one-out-of-many unclonable security. The one-out-of-many
unclonable security notion does not rule out a copying process that can
generate $n$ copies with probability $\frac{1}{n}$. However, it guarantees
that such a process must completely destroy the original object with
probability $1-\frac{1}{n}$. In fact, it guarantees that the expected number
of successful copies generated by any copying adversary is at most $1$.

Although one-out-of-many unclonable security looks weaker than existing
unclonable security, it still seems useful in some applications. For example,
suppose we publish many quantum objects, say $\ell$ objects. Then, the one-
out-of-many security guarantees that no matter what copying attacks are
applied to those objects, there are expected to be only $\ell$ objects on
average in this world.

Below, we define one-out-of-many one-time unclonable-indistinguishable
security for SKUE and one-out-of-many one-time anti-piracy for secret key SDE.
We prove that one-out-of-many one-time unclonable-indistinguishable security
for SKUE implies one-time IND-CPA security. We also prove that one-time strong
anti-piracy for secret key SDE implies one-out-of-many one-time anti-piracy
for secret key SDE. Then, we show that we can transform secret key SDE with
one-out-of-many one-time anti-piracy into one-out-of-many one-time unclonable-
indistinguishable secure SKUE.

In Section 5, we define one-out-of-many copy protection security for single-
bit output point functions. In Section 6, we define simulation-based security
for unclonable PE and introduce its one-out-of-many variant.

###  3.1 One-out-of-Many Security Notions for SKUE and Secret Key SDE

###### Definition 3.1 (One-out-of-Many One-Time Unclonable-
Indistinguishability for SKUE).

Let $\mathsf{UE}=(\mathsf{KG},\mathpzc{Enc},\mathpzc{Dec})$ be an SKUE scheme
with the message space $\mathcal{M}$. We consider one-out-of-many one-time
unclonable-indistinguishability game
$\mathsf{Exp}_{\mathsf{UE},\mathpzc{A}}^{\mathsf{om}\mbox{-}\mathsf{ot}\mbox{-}\mathsf{clone}\mbox{-}\mathsf{ind}}(\lambda,n)$
between the challenger and an adversary
$\mathpzc{A}=(\mathpzc{A}_{0},\mathpzc{A}_{1},\allowbreak\cdots,\mathpzc{A}_{n})$
below.

  1. 1.

$\mathpzc{A}_{0}$ sends $(\mathsf{m}_{0},\mathsf{m}_{1})$ to the challenger.

  2. 2.

The challenger generates $\mathsf{coin}\leftarrow\\{0,1\\}$,
$\mathsf{uk}\leftarrow\mathsf{KG}(1^{\lambda})$, and
$\mathpzc{ct}\leftarrow\mathpzc{Enc}(\mathsf{uk},\mathsf{m}_{\mathsf{coin}})$,
and sends $\mathpzc{ct}$ to $\mathpzc{A}_{0}$.

  3. 3.

$\mathpzc{A}_{0}$ creates a quantum state $\mathpzc{q}$ over $n$ registers
${\color[rgb]{.5,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,.5,.5}\pgfsys@color@gray@stroke{.5}\pgfsys@color@gray@fill{.5}{\mathsf{R}}}_{1},\cdots,{\color[rgb]{.5,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,.5,.5}\pgfsys@color@gray@stroke{.5}\pgfsys@color<EMAIL_ADDRESS>$\mathpzc{A}_{0}$ sends
$\mathpzc{q}[{\color[rgb]{.5,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,.5,.5}\pgfsys@color@gray@stroke{.5}\pgfsys@color<EMAIL_ADDRESS>to $\mathpzc{A}_{i}$ for every $i\in[n]$.

  4. 4.

The challenger generates $\alpha\leftarrow[n]$, and gives $\mathsf{uk}$ to
$\mathpzc{A}_{\alpha}$. $\mathpzc{A}_{\alpha}$ outputs
$\mathsf{coin}^{\prime}$. The challenger outputs $1$ if
$\mathsf{coin}^{\prime}=\mathsf{coin}$ and outputs $0$ otherwise.

We say that $\mathsf{UE}$ is one-out-of-many one-time unclonable-
indistinguishable if for any polynomial $n=n(\lambda)$ and QPT adversary
$\mathpzc{A}=(\mathpzc{A}_{0},\mathpzc{A}_{1},\cdots,\mathpzc{A}_{n})$, it
satisfies that

$\displaystyle\mathsf{Adv}_{\mathsf{UE},\mathpzc{A}}^{\mathsf{om}\mbox{-}\mathsf{ot}\mbox{-}\mathsf{clone}\mbox{-}\mathsf{ind}}(\lambda,n)\coloneqq\Pr[\mathsf{Exp}_{\mathsf{UE},\mathpzc{A}}^{\mathsf{om}\mbox{-}\mathsf{ot}\mbox{-}\mathsf{unclone}\mbox{-}\mathsf{ind}}(\lambda,n)=1]\leq\frac{1}{2}+\frac{1}{2n}+{\mathsf{negl}}(\lambda).$
(24)

###### Theorem 3.2.

Let $\mathsf{UE}=(\mathsf{KG},\mathpzc{Enc},\mathpzc{Dec})$ be a one-out-of-
many one-time unclonable-indistinguishable secure SKUE scheme with the message
space $\mathcal{M}$. Then, $\mathsf{UE}$ satisfies one-time IND-CPA security,
that is,

$\mathpzc{Enc}(\mathsf{uk},\mathsf{m}_{0})\stackrel{{\scriptstyle\mathsf{c}}}{{\approx}}\mathpzc{Enc}(\mathsf{uk},\mathsf{m}_{1})$

for any $(\mathsf{m}_{0},\mathsf{m}_{1})\in\mathcal{M}$, where
$\mathsf{uk}\leftarrow\mathsf{KG}(1^{\lambda})$.

###### Proof.

Suppose there exists $\mathpzc{B}$ who can distinguish
$\mathpzc{Enc}(\mathsf{uk},\mathsf{m}_{0})$ from
$\mathpzc{Enc}(\mathsf{uk},\mathsf{m}_{1})$ with probability $\frac{1}{2}+p$
for some $(\mathsf{m}_{0},\mathsf{m}_{1})\in\mathcal{M}$ and inverse
polynomial $p$, where $\mathsf{uk}\leftarrow\mathsf{KG}(1^{\lambda})$.
Consider the following $n=\frac{1}{p}$ tuple of adversaries
$\mathpzc{A}=(\mathpzc{A}_{0},\mathpzc{A}_{1},\cdots,\mathpzc{A}_{n})$ for the
one-out-of-many one-time unclonable-indistinguishable security. On input
$\mathpzc{ct}$, $\mathpzc{A}_{0}$ gives them to $\mathpzc{B}$ and obtains
$\mathpzc{B}$’s guess $\mathsf{coin}^{\prime}$, and sends it to
$\mathpzc{A}_{i}$ for every $i\in[n]$. $\mathpzc{A}_{i}$ just outputs
$\mathsf{coin}^{\prime}$ if $\alpha=i$ is chosen by the challenger. We have
$\mathsf{Adv}_{\mathsf{UE},\mathpzc{A}}^{\mathsf{om}\mbox{-}\mathsf{ot}\mbox{-}\mathsf{unclone}\mbox{-}\mathsf{ind}}(\lambda,n)=\frac{1}{2}+p$,
which contradicts to the one-out-of-many unclonable-indistinguishable security
since $p>\frac{1}{2n}=\frac{p}{2}$. ∎

###### Definition 3.3 (One-out-of-Many One-Time Anti-Piracy Security for
Secret Key SDE).

Let $\mathsf{SDE}=(\mathpzc{KG},\mathsf{Enc},\mathpzc{Dec})$ be a secret key
SDE scheme. We consider one-out-of-many one-time anti-piracy game
$\mathsf{Exp}_{\mathsf{SDE},\mathpzc{A}}^{\mathsf{om}\mbox{-}\mathsf{otanti}\mbox{-}\mathsf{piracy}}(\lambda,n)$
between the challenger and an adversary
$\mathpzc{A}=(\mathpzc{A}_{0},\mathpzc{A}_{1},\cdots,\mathpzc{A}_{n})$ below.

  1. 1.

The challenger generates
$(\mathsf{ek},\mathpzc{dk})\leftarrow\mathpzc{KG}(1^{\lambda})$ and sends
$\mathpzc{dk}$ to $\mathpzc{A}_{0}$.

  2. 2.

$\mathpzc{A}_{0}$ creates a quantum state $\mathpzc{q}$ over $n$ registers
${\color[rgb]{.5,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,.5,.5}\pgfsys@color@gray@stroke{.5}\pgfsys@color@gray@fill{.5}{\mathsf{R}}}_{1},\cdots,{\color[rgb]{.5,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,.5,.5}\pgfsys@color@gray@stroke{.5}\pgfsys@color<EMAIL_ADDRESS>$\mathpzc{A}_{0}$ sends $(\mathsf{m}_{0},\mathsf{m}_{1})$ to the challenger.
$\mathpzc{A}_{0}$ also sends
$\mathpzc{q}[{\color[rgb]{.5,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,.5,.5}\pgfsys@color@gray@stroke{.5}\pgfsys@color<EMAIL_ADDRESS>to $\mathpzc{A}_{i}$ for every $i\in[n]$.

  3. 3.

$\mathpzc{A}_{i}$ outputs
$\mathpzc{D}_{i}=(\rho[{\color[rgb]{.5,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,.5,.5}\pgfsys@color@gray@stroke{.5}\pgfsys@color@gray@fill{.5}{\mathsf{R}}}_{i}],\bm{U}_{i})$
for every $i\in[n]$.

  4. 4.

The challenger generates $\alpha\leftarrow[n]$ and
$\mathsf{coin}\leftarrow\\{0,1\\}$, and generates
$\mathsf{ct}\leftarrow\mathsf{Enc}(\mathsf{ek},\mathsf{m}_{\mathsf{coin}})$.
The challenge runs $\mathpzc{D}_{\alpha}$ on input $\mathsf{ct}$ and obtains
$\mathsf{coin}^{\prime}$. The challenger outputs $1$ if
$\mathsf{coin}^{\prime}=\mathsf{coin}$ and outputs $0$ otherwise.

We say that $\mathsf{SDE}$ is one-out-of-many one-time anti-piracy secure if
for any polynomial $n=n(\lambda)$ and QPT adversary
$\mathpzc{A}=(\mathpzc{A}_{0},\mathpzc{A}_{1},\cdots,\mathpzc{A}_{n})$, it
satisfies that

$\displaystyle\mathsf{Adv}_{\mathsf{SDE},\mathpzc{A}}^{\mathsf{om}\mbox{-}\mathsf{otanti}\mbox{-}\mathsf{piracy}}(\lambda,n)\coloneqq\Pr[\mathsf{Exp}_{\mathsf{SDE},\mathpzc{A}}^{\mathsf{om}\mbox{-}\mathsf{otanti}\mbox{-}\mathsf{piracy}}(\lambda,n)=1]\leq\frac{1}{2}+\frac{1}{2n}+{\mathsf{negl}}(\lambda).$
(25)

We show that one-time strong anti-piracy security for secret key SDE implies
one-ouf-of-many one-time anti-piracy for secret key SDE.

###### Theorem 3.4.

Let $\mathsf{SDE}$ be a secret key SDE scheme. If $\mathsf{SDE}$ is one-time
strong anti-piracy secure, then $\mathsf{SDE}$ is also one-out-of-many one-
time anti-piracy secure.

###### Proof.

$\mathsf{Exp}_{\mathsf{SDE},\mathpzc{A}}^{\mathsf{om}\mbox{-}\mathsf{anti}\mbox{-}\mathsf{piracy}}(\lambda,n)$
is equivalent to the security game where item 4 is replaced with the
following.

  * •

The challenger generates $\alpha\leftarrow[n]$. For every
${\alpha^{\prime}}\in[n]$, the challenger applies
$\mathsf{ProjImp}(\bm{P}_{{\alpha^{\prime}},D})$ to
$\rho[{\color[rgb]{.5,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,.5,.5}\pgfsys@color@gray@stroke{.5}\pgfsys@color<EMAIL_ADDRESS>and obtains $p_{\alpha^{\prime}}$. The challenger outputs $1$ with probability
$p_{\alpha}$.

This equivalence follows from the definition of $\mathsf{ProjImp}$. Using this
version of
$\mathsf{Exp}_{\mathsf{SDE},\mathpzc{A}}^{\mathsf{om}\mbox{-}\mathsf{anti}\mbox{-}\mathsf{piracy}}(\lambda,n)$,
we prove that
$\mathsf{Adv}_{\mathsf{SDE},\mathpzc{A}}^{\mathsf{om}\mbox{-}\mathsf{anti}\mbox{-}\mathsf{piracy}}(\lambda,n)\leq\frac{1}{2}+\frac{1}{2n}+\gamma$
for any inverse polynomial $\gamma$. Since $\mathsf{SDE}$ is strong anti-
piracy secure, except for some single index $i^{*}$, $p_{i}$ computed by the
challenger is smaller than $\frac{1}{2}+\gamma$, with overwhelming
probability. Thus, we have

$\displaystyle\mathsf{Adv}_{\mathsf{SDE},\mathpzc{A}}^{\mathsf{om}\mbox{-}\mathsf{anti}\mbox{-}\mathsf{piracy}}(\lambda,n)$
$\displaystyle\leq\frac{1}{n}\cdot
1+\frac{n-1}{n}\cdot(\frac{1}{2}+\gamma)+{\mathsf{negl}}(\lambda)$ (26)
$\displaystyle\leq\frac{1}{2}+\frac{1}{2n}+\gamma.$ (27)

This completes the proof. ∎

###  3.2 From Secret-Key SDE to SKUE: One-out-of-Many Setting

We present a transformation from a secret key SDE scheme that satisfies
Definition 3.3 into a SKUE scheme that satisfies Definition 3.1. Georgiou and
Zhandry developed this transformation [GZ20]. Note that they do not consider
one-out-of-many security for secret key SDE and SKUE. We show that their
transformation works even in the one-out-of-many setting.

Let
$\mathsf{SDE}=(\mathsf{SDE}.\mathpzc{KG},\mathsf{SDE}.\mathsf{Enc},\mathsf{SDE}.\mathpzc{Dec})$
be a secret key SDE scheme. We also let $\ell$ be the length of ciphertexts of
$\mathsf{SDE}$. We construct a SKUE scheme
$\mathsf{UE}=(\mathsf{UE}.\mathsf{KG},\mathsf{UE}.\mathpzc{Enc},\mathsf{UE}.\mathpzc{Dec})$
as follows.

$\mathsf{UE}.\mathsf{KG}(1^{\lambda})$:

  * •

Output $\mathsf{uk}\leftarrow\\{0,1\\}^{\ell}$.

$\mathsf{UE}.\mathpzc{Enc}(\mathsf{uk},\mathsf{m})$:

  * •

Generate
$(\mathsf{sde}.\mathsf{ek},\mathsf{sde}.\mathpzc{dk})\leftarrow\mathsf{SDE}.\mathpzc{KG}(1^{\lambda})$.

  * •

Compute
$\mathsf{sde}.\mathsf{ct}\leftarrow\mathsf{SDE}.\mathsf{Enc}(\mathsf{sde}.\mathsf{ek},\mathsf{m})$.

  * •

Output
$\mathsf{ue}.\mathpzc{ct}\coloneqq(\mathsf{sde}.\mathsf{ct}\oplus\mathsf{uk},\mathsf{sde}.\mathpzc{dk})$.

$\mathsf{UE}.\mathpzc{Dec}(\mathsf{uk},\mathsf{ue}.\mathpzc{ct})$:

  * •

Parse
$(\mathsf{ct}_{1}^{\prime},\mathsf{sde}.\mathpzc{dk})=\mathsf{ue}.\mathpzc{ct}$.

  * •

Compute
$\mathsf{sde}.\mathsf{ct}^{\prime}\coloneqq\mathsf{ct}_{1}^{\prime}\oplus\mathsf{uk}$.

  * •

Output
$\mathsf{m}^{\prime}\leftarrow\mathsf{SDE}.\mathpzc{Dec}(\mathsf{sde}.\mathpzc{dk},\mathsf{sde}.\mathsf{ct}^{\prime})$.

###### Theorem 3.5.

If $\mathsf{SDE}$ is one-out-of-many one-time anti-piracy secure,
$\mathsf{UE}$ is one-out-of-many one-time unclonable-indistinguishable secure.

###### Proof.

Let $n$ be any polynomial of $\lambda$. We construct an adversary
$\mathpzc{B}=(\mathpzc{B}_{0},\mathpzc{B}_{1},\cdots,\mathpzc{B}_{n})$ for
$\mathsf{SDE}$ by using the adversary
$\mathpzc{A}=(\mathpzc{A}_{0},\mathpzc{A}_{1},\cdots,\mathpzc{A}_{n})$ for
$\mathsf{UE}$.

  1. 1.

$\mathpzc{B}_{0}$ is given $\mathsf{sde}.\mathpzc{dk}$ from its challenger.

  2. 2.

$\mathpzc{B}_{0}$ runs $\mathpzc{A}_{0}$ and receives
$(\mathsf{m}_{0},\mathsf{m}_{1})$, and passes
$(\mathsf{m}_{0},\mathsf{m}_{1})$ to its challenger.

  3. 3.

$\mathpzc{B}_{0}$ generates $\mathsf{uk}\leftarrow\\{0,1\\}^{\ell}$, sets
$\mathsf{ue}.\mathpzc{ct}\coloneqq(\mathsf{uk},\mathsf{sde}.\mathpzc{dk})$,
and passes $\mathsf{ue}.\mathpzc{ct}$ to $\mathpzc{A}_{0}$. Then,
$\mathpzc{A}_{0}$ create a quantum state $\mathpzc{q}{A}$ over $n$ registers
${\color[rgb]{.5,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,.5,.5}\pgfsys@color@gray@stroke{.5}\pgfsys@color@gray@fill{.5}{\mathsf{C}}}_{1},\cdots,{\color[rgb]{.5,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,.5,.5}\pgfsys@color@gray@stroke{.5}\pgfsys@color<EMAIL_ADDRESS>$\mathpzc{B}_{0}$ receives them.

  4. 4.

$\mathpzc{B}_{0}$ creates a quantum state $\mathpzc{q}{B}$ over $n$ registers
${\color[rgb]{.5,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,.5,.5}\pgfsys@color@gray@stroke{.5}\pgfsys@color@gray@fill{.5}{\mathsf{R}}}_{1},\cdots,{\color[rgb]{.5,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,.5,.5}\pgfsys@color@gray@stroke{.5}\pgfsys@color<EMAIL_ADDRESS>such that
$\mathpzc{q}{B}[{\color[rgb]{.5,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,.5,.5}\pgfsys@color@gray@stroke{.5}\pgfsys@color@gray@fill{.5}{\mathsf{R}}}_{i}]\coloneqq(\mathsf{uk},\mathpzc{q}{A}[{\color[rgb]{.5,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,.5,.5}\pgfsys@color@gray@stroke{.5}\pgfsys@color@gray@fill{.5}{\mathsf{C}}}_{i}])$
for every $i\in[n]$, then $\mathpzc{B}_{0}$ sends
$\mathpzc{q}{B}[{\color[rgb]{.5,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,.5,.5}\pgfsys@color@gray@stroke{.5}\pgfsys@color<EMAIL_ADDRESS>to $\mathpzc{B}_{i}$ for every $i\in[n]$.

  5. 5.

For every $i\in[n]$, $\mathpzc{B}_{i}$ outputs
$\mathpzc{D}_{i}=(\mathpzc{q}{B}[{\color[rgb]{.5,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,.5,.5}\pgfsys@color@gray@stroke{.5}\pgfsys@color@gray@fill{.5}{\mathsf{R}}}_{1}],\bm{U}_{i})$,
where $\bm{U}_{i}$ is a unitary that takes $\mathsf{sde}.\mathsf{ct}$ and
$\mathpzc{q}{B}[{\color[rgb]{.5,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,.5,.5}\pgfsys@color@gray@stroke{.5}\pgfsys@color<EMAIL_ADDRESS>as inputs, and outputs
$\mathsf{coin}^{\prime}\leftarrow\mathpzc{A}_{i}(\mathpzc{q}{A}[{\color[rgb]{.5,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,.5,.5}\pgfsys@color@gray@stroke{.5}\pgfsys@color@gray@fill{.5}{\mathsf{C}}}_{i}],\mathsf{uk}\oplus\mathsf{sde}.\mathsf{ct})$.

If the challenger of one-out-of-many security of SDE chooses
$\alpha\leftarrow[n]$ and $\mathsf{coin}\leftarrow\\{0,1\\}$, and generates
$\mathsf{sde}.\mathsf{ct}\leftarrow\mathsf{SDE}.\mathsf{Enc}(\mathsf{sde}.\mathsf{ek},\mathsf{m}_{\mathsf{coin}})$,
then the challenger runs $\mathpzc{D}_{\alpha}$ on input
$\mathsf{sde}.\mathsf{ct}$ and obtains the output
$\mathsf{coin}^{\prime}\leftarrow\mathpzc{A}_{\alpha}(\mathpzc{q}{A}[{\color[rgb]{.5,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,.5,.5}\pgfsys@color@gray@stroke{.5}\pgfsys@color@gray@fill{.5}{\mathsf{C}}}_{\alpha}],\mathsf{uk}\oplus\mathsf{sde}.\mathsf{ct})$.
If
$\mathsf{sde}.\mathsf{ct}=\mathsf{SDE}.\mathsf{Enc}(\mathsf{sde}.\mathsf{ek},\mathsf{m}_{\mathsf{coin}})$,
then
$\mathsf{ue}.\mathpzc{ct}=(\mathsf{uk},\mathsf{sde}.\mathpzc{dk})=\mathsf{UE}.\mathpzc{Enc}(\mathsf{sde}.\mathsf{ct}\oplus\mathsf{uk},\mathsf{m}_{\mathsf{coin}})$.
$\mathpzc{B}$ correctly simulates the one-out-of-many security game of SKUE
for $\mathpzc{A}$ since $\mathsf{uk}$ is a uniformly random string. Therefore,
the probability that $\mathpzc{A}$ succeeds in breaking $\mathsf{UE}$ is
bounded by the probability that $\mathpzc{B}$ succeeds in breaking
$\mathsf{SDE}$. This completes the proof. ∎

##  4 One-Time Secret Key SDE from LWE

We construct secret key SDE satisfying one-time strong anti-piracy based on
the LWE assumption in this section.

###  4.1 Tools

#### Ciphertext-policy functional encryption.

We introduce ciphertext-policy functional encryption (CPFE). Since we consider
single-key setting by default, we use a simplified syntax where the setup
algorithm takes as input $x$ and outputs a master public key and a functional
decryption key for $x$. There is no key generation algorithm.

###### Definition 4.1 (Single-Key Ciphertext-Policy Functional Encryption).

A single-key CPFE scheme for the circuit space $\mathcal{C}$ and the input
space $\mathcal{X}$ is a tuple of algorithms
$(\mathsf{Setup},\mathsf{Enc},\mathsf{Dec})$.

  * •

The setup algorithm $\mathsf{Setup}$ takes as input a security parameter
$1^{\lambda}$ and an input $x\in\mathcal{X}$, and outputs a master public key
$\mathsf{MPK}$ and functional decryption key $\mathsf{sk}_{x}$.

  * •

The encryption algorithm $\mathsf{Enc}$ takes as input the master public key
$\mathsf{MPK}$ and $C\in\mathcal{C}$, and outputs a ciphertext $\mathsf{ct}$.

  * •

The decryption algorithm $\mathsf{Dec}$ takes as input a functional decryption
key $\mathsf{sk}_{x}$ and a ciphertext $\mathsf{ct}$, and outputs $y$.

Decryption Correctness:

We require
$\mathsf{Dec}(\mathsf{sk}_{x},\mathsf{Enc}(\mathsf{MPK},C))\allowbreak=C(x)$
for every $C\in\mathcal{C}$, $x\in\mathcal{X}$, and
$\left(\mathsf{MPK},\mathsf{sk}_{x}\right)\leftarrow\mathsf{Setup}(1^{\lambda},x)$.

###### Definition 4.2 ($1$-Bounded Security).

Let $\mathsf{CPFE}$ be a single-key CPFE scheme. We define the game
$\mathsf{Expt}_{\mathsf{CPFE},\mathpzc{A}}^{\mathsf{1\textrm{-}bounded}}(\lambda,\mathsf{coin})$
as follows.

  1. 1.

$\mathpzc{A}$ sends $x\in\mathcal{X}$ to the challenger.

  2. 2.

The challenger generates
$(\mathsf{MPK},\mathsf{sk}_{x})\leftarrow\mathsf{Setup}(1^{\lambda},x)$ and
sends $(\mathsf{MPK},\mathsf{sk}_{x})$ to $\mathpzc{A}$.

  3. 3.

$\mathpzc{A}$ outputs $(C_{0},C_{1})$ such that $C_{0}(x)=C_{1}(x)$. The
challenger generates
$\mathsf{ct}\leftarrow\mathsf{Enc}(\mathsf{MPK},C_{\mathsf{coin}})$, and sends
$\mathsf{ct}$ to $\mathpzc{A}$.

  4. 4.

$\mathpzc{A}$ outputs $\mathsf{coin}^{\prime}\in\\{0,1\\}$.

We say that $\mathsf{CPFE}$ is $1$-bounded secure if for every QPT
$\mathpzc{A}$, we have

$\displaystyle\mathsf{Adv}_{\mathsf{CPFE},\mathpzc{A}}^{\mathsf{1\textrm{-}bounded}}(\lambda)=\absolutevalue{\Pr[\mathsf{Expt}_{\mathsf{CPFE},\mathpzc{A}}^{\mathsf{1\textrm{-}bounded}}(\lambda,0)=1]-\Pr[\mathsf{Expt}_{\mathsf{CPFE},\mathpzc{A}}^{\mathsf{1\textrm{-}bounded}}(\lambda,1)=1]}={\mathsf{negl}}(\lambda).$
(28)

###### Definition 4.3 (Succinct Key).

We say that a single-key CPFE scheme satisfies succinct key property if there
exist two algorithms $\mathsf{HKG}$ and $\mathsf{Hash}$ satisfying the
following conditions.

  * •

$\mathsf{Setup}(1^{\lambda},x)$ runs
$\mathsf{hk}\leftarrow\mathsf{HKG}(1^{\lambda},1^{\absolutevalue{x}})$,
compute $h\leftarrow\mathsf{Hash}(\mathsf{hk},x)$, and outputs
$\mathsf{MPK}\coloneqq(\mathsf{hk},h)$ and $\mathsf{sk}_{x}\coloneqq x$. For
the setup of a CPFE scheme with succinct key property, we omit to write
$\mathsf{sk}_{x}\coloneqq x$ from the output of $\mathsf{Setup}$ and we simply
write $\mathsf{MPK}\leftarrow\mathsf{Setup}(1^{\lambda},x)$.

  * •

The length of $h$ output by $\mathsf{Hash}$ is $\lambda$ regardless of the
length of the input $x$.

###### Theorem 4.4.

If the LWE or exponentially-hard LPN assumption holds, there exists single-key
CPFE with succinct key for $\mathsf{P}/\mathsf{poly}$.

See Appendix B for the proof of Theorem 4.4.

#### Monogamy of entanglement.

We review the monogamy of entanglement property of of BB84 states [TFKW13] and
its variant.

###### Theorem 4.5 (Monogamy Property of BB84 States [TFKW13]).

Consider the following game between a challenger and an adversary
$\mathpzc{A}=(\mathpzc{A}_{0},\mathpzc{A}_{1},\mathpzc{A}_{2})$.

  1. 1.

The challenger picks a uniformly random strings $x\in\\{0,1\\}^{n}$ and
$\theta\in\\{0,1\\}^{n}$. It sends $\ket{x^{\theta}}\coloneqq
H^{\theta[1]}\ket{x[1]}\otimes\cdots\otimes H^{\theta[n]}\ket{x[n]}$ to
$\mathpzc{A}_{0}$.

  2. 2.

$\mathpzc{A}_{0}$ creates a bipartite state $\mathpzc{q}$ over registers
${\color[rgb]{.5,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,.5,.5}\pgfsys@color@gray@stroke{.5}\pgfsys@color<EMAIL_ADDRESS>and
${\color[rgb]{.5,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,.5,.5}\pgfsys@color@gray@stroke{.5}\pgfsys@color<EMAIL_ADDRESS>Then, $\mathpzc{A}_{0}$ sends register
${\color[rgb]{.5,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,.5,.5}\pgfsys@color@gray@stroke{.5}\pgfsys@color<EMAIL_ADDRESS>to $\mathpzc{A}_{1}$ and register
${\color[rgb]{.5,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,.5,.5}\pgfsys@color@gray@stroke{.5}\pgfsys@color<EMAIL_ADDRESS>to $\mathpzc{A}_{2}$.

  3. 3.

$\theta$ is then sent to both $\mathpzc{A}_{1}$ and $\mathpzc{A}_{2}$.
$\mathpzc{A}_{1}$ and $\mathpzc{A}_{2}$ return respectively $x_{1}^{\prime}$
and $x_{2}^{\prime}$.

Let $\mathsf{MoEBB84}(\mathpzc{A},\lambda)$ be a random variable which takes
the value $1$ if $x_{1}^{\prime}=x_{2}^{\prime}=x$, and takes the value $0$
otherwise. Then, there exists an exponential function $\mathsf{exp}$ such that
for any adversary
$\mathpzc{A}=(\mathpzc{A}_{0},\mathpzc{A}_{1},\mathpzc{A}_{2})$, it holds that

$\displaystyle\Pr[\mathsf{MoEBB84}(\mathpzc{A},\lambda)=1]\leq 1/\exp(n).$
(29)

We introduce a variant of the monogamy property above where the adversary can
select a leakage function $\mathsf{Leak}$ and obtain $\mathsf{Leak}(x)$.

###### Theorem 4.6 (Monogamy Property of BB84 States with Leakage).

Consider the following game between a challenger and an adversary
$\mathpzc{A}=(\mathpzc{A}_{0},\mathpzc{A}_{1},\mathpzc{A}_{2})$.

  1. 1.

$\mathpzc{A}$ sends a function $\mathsf{Leak}$ whose output length is $\ell$
to the challenger.

  2. 2.

The challenger picks a uniformly random strings $x\in\\{0,1\\}^{n}$ and
$\theta\in\\{0,1\\}^{n}$. It sends $\ket{x^{\theta}}\coloneqq
H^{\theta[1]}\ket{x[1]}\otimes\cdots\otimes H^{\theta[n]}\ket{x[n]}$ and
$\mathsf{Leak}(x)$ to $\mathpzc{A}_{0}$.

  3. 3.

$\mathpzc{A}_{0}$ creates a bipartite state $\mathpzc{q}$ over registers
${\color[rgb]{.5,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,.5,.5}\pgfsys@color@gray@stroke{.5}\pgfsys@color<EMAIL_ADDRESS>and
${\color[rgb]{.5,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,.5,.5}\pgfsys@color@gray@stroke{.5}\pgfsys@color<EMAIL_ADDRESS>Then, $\mathpzc{A}_{0}$ sends register
${\color[rgb]{.5,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,.5,.5}\pgfsys@color@gray@stroke{.5}\pgfsys@color<EMAIL_ADDRESS>to $\mathpzc{A}_{1}$ and register
${\color[rgb]{.5,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,.5,.5}\pgfsys@color@gray@stroke{.5}\pgfsys@color<EMAIL_ADDRESS>to $\mathpzc{A}_{2}$.

  4. 4.

$\theta$ is then sent to both $\mathpzc{A}_{1}$ and $\mathpzc{A}_{2}$.
$\mathpzc{A}_{1}$ and $\mathpzc{A}_{2}$ return respectively $x_{1}^{\prime}$
and $x_{2}^{\prime}$.

Let $\mathsf{MoEBB84Leak}(\mathpzc{A},\lambda)$ be a random variable which
takes the value $1$ if $x_{1}^{\prime}=x_{2}^{\prime}=x$, and takes the value
$0$ otherwise. Then, there exists an exponential function $\mathsf{exp}$ such
that for any adversary
$\mathpzc{A}=(\mathpzc{A}_{0},\mathpzc{A}_{1},\mathpzc{A}_{2})$, it holds that

$\displaystyle\Pr[\mathsf{MoEBB84Leak}(\mathpzc{A},\lambda)=1]\leq
2^{\ell}/\exp(n).$ (30)

Especially, if $\ell$ is independent of $n$, the right hand side is negligible
in $\lambda$ by setting $n$ appropriately.

We can reduce Theorem 4.6 to Theorem 4.5 by guessing $\mathsf{Leak}(x)$ with
probability $1/2^{\ell}$.

###  4.2 Construction

We use a CPFE scheme with succinct key property
$\mathsf{CPFE}=(\mathsf{Setup},\mathsf{Enc},\mathsf{Dec})$ to construct a
secret key SDE scheme
$\mathsf{SDE}=(\mathsf{SDE}.\mathpzc{KG},\mathsf{SDE}.\mathsf{Enc},\mathsf{SDE}.\mathpzc{Dec})$.
The description of $\mathsf{SDE}$ is as follows. The plaintext space of
$\mathsf{SDE}$ is $\\{0,1\\}^{\ell}$.

$\mathsf{SDE}.\mathpzc{KG}(1^{\lambda})$:

  * •

Generate $x,\theta\leftarrow\\{0,1\\}^{n}$.

  * •

Generate $\ket{x^{\theta}}=H^{\theta[1]}\ket{x[1]}\otimes\ldots
H^{\theta[n]}\ket{x[n]}$.

  * •

Generate $\mathsf{MPK}\leftarrow\mathsf{Setup}(1^{\lambda},x)$.

  * •

Output $\mathsf{ek}\coloneqq(\theta,\mathsf{MPK})$ and
$\mathpzc{dk}\coloneqq\ket{x^{\theta}}$.

$\mathsf{SDE}.\mathsf{Enc}(\mathsf{ek},m)$:

  * •

Parse $\mathsf{ek}=(\theta,\mathsf{MPK})$.

  * •

Let $C[m]$ be a constant circuit that outputs $m$ on any input. $C$ is padded
so that it has the same size as $C^{*}$ appeared in the security proof.

  * •

Compute $\mathsf{ct}\leftarrow\mathsf{CPFE}.\mathsf{Enc}(\mathsf{MPK},C[m])$.

  * •

Output $\mathsf{sdct}\coloneqq(\theta,\mathsf{ct})$.

$\mathsf{SDE}.\mathpzc{Dec}(\mathpzc{dk},\mathsf{sdct})$:

  * •

Parse $\mathpzc{dk}=\ket{x^{\theta}}$ and
$\mathsf{sdct}=(\theta,\mathsf{ct})$.

  * •

Compute $x$ from $\ket{x^{\theta}}$ and $\theta$.

  * •

Output $m\leftarrow\mathsf{Dec}(x,\mathsf{ct})$.

###### Theorem 4.7.

If $\mathsf{CPFE}$ is a CPFE scheme that satisfies succinct key property and
$1$-bounded security, $\mathsf{SDE}$ is a one-time strong anti-piracy secure
single-decryptor SKE.

From Theorems 4.7, 4.4, 3.5 and 3.4, we immediately obtain the following
corollary.

###### Corollary 4.8.

If the LWE assumption holds, there exists one-out-of-many unclonable-
indistinguishable secure unclonable encryption.

###### Proof of Theorem 4.7.

Let $\gamma\in[0,1]$ and
$\mathpzc{A}=(\mathpzc{A}_{0},\mathpzc{A}_{1},\mathpzc{A}_{2})$ be any QPT
adversary. $\mathpzc{A}_{1}$ and $\mathpzc{A}_{2}$ respectively output
$\mathpzc{D}_{1}=({\color[rgb]{.5,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,.5,.5}\pgfsys@color@gray@stroke{.5}\pgfsys@color@gray@fill{.5}{\mathsf{R}}}_{1},\bm{U}_{1})$
and
$\mathpzc{D}_{2}=({\color[rgb]{.5,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,.5,.5}\pgfsys@color@gray@stroke{.5}\pgfsys@color@gray@fill{.5}{\mathsf{R}}}_{2},\bm{U}_{2})$,
where
${\color[rgb]{.5,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,.5,.5}\pgfsys@color@gray@stroke{.5}\pgfsys@color<EMAIL_ADDRESS>and
${\color[rgb]{.5,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,.5,.5}\pgfsys@color@gray@stroke{.5}\pgfsys@color<EMAIL_ADDRESS>have a possibly entangled quantum state $\rho$, and
$\bm{U}_{\alpha}=(\bm{U}_{\alpha,\mathsf{ct}})_{\mathsf{ct}}$ for
$\alpha\in[2]$. We define the collection of binary projective measurements
$\bm{P}_{\alpha}=(\bm{P}_{\alpha,b,\mathsf{ct}},\bm{I}-\bm{P}_{\alpha,b,\mathsf{ct}})_{b,\mathsf{ct}}$
for every $\alpha\in[2]$, the distribution $D$, and the mixture of
$\bm{P}_{\alpha}$ with respect to $D$ $\bm{P}_{\alpha,D}$ for every
$\alpha\in[2]$ in the same way as Definition 2.21. Then, we can write

$\displaystyle\mathsf{Adv}_{\mathsf{SDE},\mathpzc{A}}^{\mathsf{ot}\mbox{-}\mathsf{santi}\mbox{-}\mathsf{piracy}}(\lambda,\gamma)=\Pr[p_{1}>\frac{1}{2}+\gamma\land
p_{2}>\frac{1}{2}+\gamma],$ (31)

where $p_{\alpha}$ is the result of applying
$\mathsf{ProjImp}(\bm{P}_{\alpha,D})$ to
${\color[rgb]{.5,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,.5,.5}\pgfsys@color@gray@stroke{.5}\pgfsys@color<EMAIL_ADDRESS>
We assume that
$\mathsf{Adv}_{\mathsf{SDE},\mathpzc{A}}^{\mathsf{ot}\mbox{-}\mathsf{santi}\mbox{-}\mathsf{piracy}}(\lambda,\gamma)=\eta$
for some inverse polynomial $\eta$. Using $\mathpzc{A}$, we construct
$\mathpzc{B}=(\mathpzc{B}_{0},\mathpzc{B}_{1},\mathpzc{B}_{2})$ that attacks
the monogamy property of BB84 states with leakage. Recall that since
$\mathsf{CPFE}$ satisfies succinct key property, there exist two algorithms
$\mathsf{HKG}$ and $\mathsf{Hash}$ such that $\mathsf{Setup}(1^{\lambda},x)$
runs $\mathsf{hk}\leftarrow\mathsf{HKG}(1^{\lambda},1^{\absolutevalue{x}})$,
compute $h\leftarrow\mathsf{Hash}(\mathsf{hk},x)$, and outputs
$\mathsf{MPK}:=(\mathsf{hk},h)$, where $h$ is a $\lambda$-bit string. (See
Definition 4.3.)

  1. 1.

$\mathpzc{B}_{0}$ generates
$\mathsf{hk}\leftarrow\mathsf{HKG}(1^{\lambda},1^{n})$ and sends a function
$\mathsf{Leak}(\cdot):=\mathsf{Hash}(\mathsf{hk},\cdot)$ to the challenger.

  2. 2.

$\mathpzc{B}_{0}$ is given $\ket{x^{\theta}}$ and $\mathsf{Leak}(x)=h$.
$\mathpzc{B}_{0}$ sets $\mathsf{MPK}:=(\mathsf{hk},h)$.

  3. 3.

By setting $\mathpzc{dk}\coloneqq\ket{x^{\theta}}$, $\mathpzc{B}_{0}$
simulates
$\mathsf{Exp}_{\mathsf{SDE},\mathpzc{A}}^{\mathsf{ot}\mbox{-}\mathsf{santi}\mbox{-}\mathsf{piracy}}(\lambda,\gamma)$
for $\mathpzc{A}_{0}$ and obtains $(m_{0},m_{1})$ and a quantum state
$\mathpzc{q}$ over registers
${\color[rgb]{.5,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,.5,.5}\pgfsys@color@gray@stroke{.5}\pgfsys@color<EMAIL_ADDRESS>and
${\color[rgb]{.5,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,.5,.5}\pgfsys@color@gray@stroke{.5}\pgfsys@color<EMAIL_ADDRESS>Then, $\mathpzc{B}_{0}$ sends
$(\gamma,\mathsf{MPK},m_{0},m_{1},{\color[rgb]{.5,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,.5,.5}\pgfsys@color@gray@stroke{.5}\pgfsys@color@gray@fill{.5}{\mathsf{R}}}_{1})$
to $\mathpzc{B}_{1}$ and
$(\gamma,\mathsf{MPK},m_{0},m_{1},{\color[rgb]{.5,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,.5,.5}\pgfsys@color@gray@stroke{.5}\pgfsys@color@gray@fill{.5}{\mathsf{R}}}_{2})$
to $\mathpzc{B}_{2}$.

  4. 4.

$\theta$ is then sent to both $\mathpzc{B}_{1}$ and $\mathpzc{B}_{2}$.
$\mathpzc{B}_{1}$ and $\mathpzc{B}_{2}$ behave as follows.

     * •

$\mathpzc{B}_{\alpha}$ first sets $\mathsf{ek}=(\theta,\mathsf{MPK})$.
$\mathpzc{B}_{\alpha}$ simulates
$\mathsf{Exp}_{\mathsf{SDE},\mathpzc{A}}^{\mathsf{ot}\mbox{-}\mathsf{santi}\mbox{-}\mathsf{piracy}}(\lambda,\gamma)$
for $\mathpzc{A}_{\alpha}$ and obtains
$\mathpzc{D}_{\alpha}=(\mathpzc{q}_{\alpha},\bm{U}_{\alpha})$.
$\mathpzc{B}_{\alpha}$ computes
$x_{\alpha}^{\prime}\leftarrow\mathpzc{Extract}(\mathsf{MPK},m_{0}^{*},m_{1}^{*},\mathpzc{D}_{\alpha},\gamma)$
and outputs $x_{\alpha}^{\prime}$, where the algorithm $\mathpzc{Extract}$ is
described below.

$\mathpzc{Extract}(\mathsf{MPK},\mathsf{m}_{0}^{*},\mathsf{m}_{1}^{*},\mathpzc{D}_{\alpha},\epsilon)$:

  * •

Let $\epsilon^{\prime}=\epsilon/4(n+1)$ and $\delta^{\prime}=2^{-\lambda}$.

  * •

Parse $(\mathpzc{q}_{\alpha},\bm{U}_{\alpha})\leftarrow\mathpzc{D}_{\alpha}$.
Let $D_{i}$ be the following distribution for every $i\in[\lambda]$.

$D_{i}$:

Generate $b\leftarrow\\{0,1\\}$. Generate
$\mathsf{ct}\leftarrow\mathsf{CPFE}.\mathsf{Enc}(\mathsf{MPK},C^{*}[b,m_{0},m_{1},i])$,
where $C^{*}[b,m_{0},m_{1},i]$ is a circuit that takes $x$ as input and
outputs $m_{b\oplus x[i]}$. Output $(b,\mathsf{ct})$.

  * •

Compute
$\widetilde{p}_{\alpha,0}\leftarrow\mathpzc{API}_{\mathcal{P},D}^{\epsilon^{\prime},\delta^{\prime}}(\mathpzc{q}_{\alpha})$.
If $\widetilde{p}_{\alpha,0}<\frac{1}{2}+\epsilon-4\epsilon^{\prime}$, return
$\bot$. Otherwise, letting $\mathpzc{q}_{\alpha,0}$ be the post-measurement
state, go to the next step.

  * •

For all $i\in[\lambda]$, do the following.

    1. 1.

Compute
$\widetilde{p}_{\alpha,i}\leftarrow\mathpzc{API}_{\mathcal{P},D_{i}}^{\epsilon^{\prime},\delta^{\prime}}(\mathpzc{q}_{\alpha,i-1})$.
Let $\mathpzc{q}_{\alpha,i}$ be the post-measurement state.

    2. 2.

If $\widetilde{p}_{\alpha,i}>\frac{1}{2}+\epsilon-4(i+1)\epsilon^{\prime}$,
set $x_{\alpha}^{\prime}[i]=0$. If
$\widetilde{p}_{\alpha,i}<\frac{1}{2}-\epsilon+4(i+1)\epsilon^{\prime}$, set
$x_{\alpha}^{\prime}[i]=1$. Otherwise, exit the loop and output $\bot$.

  * •

Output
$x_{\alpha}^{\prime}=x_{\alpha}^{\prime}[1]\|\cdots\|x_{\alpha}^{\prime}[\lambda]$.

We will estimate $\Pr[\mathsf{MoEBB84Leak}(\mathpzc{A},\lambda)=1]$. We define
the events $\mathsf{BadDec}_{\alpha}$, and $\mathsf{BadExt}_{\alpha,i}$ for
every $i\in[\lambda]$.

$\mathsf{BadDec}_{\alpha}$:

When $\mathpzc{B}_{\alpha}$ runs
$\mathpzc{Extract}(\mathsf{MPK},m_{0}^{*},m_{1}^{*},\mathpzc{D}_{\alpha},\epsilon)$,
$\widetilde{p}_{\alpha,0}<\frac{1}{2}+\epsilon-4\epsilon^{\prime}$ holds.

$\mathsf{BadExt}_{\alpha,i}$:

When $\mathpzc{B}_{\alpha}$ runs
$\mathpzc{Extract}(\mathsf{MPK},m_{0}^{*},m_{1}^{*},\mathpzc{D}_{\alpha},\epsilon)$,
the following conditions hold.

  * •

$\widetilde{p}_{\alpha,0}\geq\frac{1}{2}+\epsilon-4\epsilon^{\prime}$ holds.

  * •

$x_{\alpha}^{\prime}[j]=x[j]$ holds for every $j\in[i-1]$.

  * •

$x_{\alpha}^{\prime}[i]\neq x[i]$ holds.

From the assumption that
$\mathsf{Adv}_{\mathsf{SDE},\mathpzc{A}}^{\mathsf{ek}\mbox{-}\mathsf{santi}\mbox{-}\mathsf{piracy}}(\lambda,\gamma)=\eta$,
for $\widetilde{p}_{\alpha,0}$ computed in $\mathpzc{Extract}$,
$\widetilde{p}_{\alpha,0}\geq\frac{1}{2}+\epsilon-\epsilon^{\prime}$ holds
with probability $\eta-{\mathsf{negl}}(\lambda)$ for $\alpha\in[2]$, due to
the first item of Theorem 2.5. This means that
$\Pr[\mathsf{BadDec}_{1}\lor\mathsf{BadDec}_{2}]=1-\eta+{\mathsf{negl}}(\lambda)$.
Then, we have

$\displaystyle\Pr[\mathsf{MoEBB84Leak}(\mathpzc{A},\lambda)=1]$
$\displaystyle\geq
1-\left(\Pr[\mathsf{BadDec}_{1}\lor\mathsf{BadDec}_{2}]+\sum_{i\in[\lambda]}\Pr[\mathsf{BadExt}_{1,i}]+\sum_{i\in[\lambda]}\Pr[\mathsf{BadExt}_{2,i}]\right)$
(32)
$\displaystyle=\eta-{\mathsf{negl}}(\lambda)-\left(\sum_{i\in[\lambda]}\Pr[\mathsf{BadExt}_{1,i}]+\sum_{i\in[\lambda]}\Pr[\mathsf{BadExt}_{2,i}]\right)$
(33)

#### Estimation of $\Pr[\mathsf{BadExt}_{\alpha,i}]$ for every $\alpha\in[2]$
and $i\in[\lambda]$.

We first estimate $\Pr[\mathsf{BadExt}_{\alpha,1}]$. We first consider the
case of $x[1]=0$. From the first item of the event, we have
$\widetilde{p}_{\alpha,0}>\frac{1}{2}+\epsilon-4\epsilon^{\prime}$. Let
$\widetilde{p}^{\prime}_{\alpha,0}\leftarrow\mathpzc{API}_{\mathcal{P},D}^{\epsilon^{\prime},\delta^{\prime}}(\mathpzc{q}_{\alpha,0})$.
From, the almost-projective property of $\mathpzc{API}$, we have

$\displaystyle\Pr[\widetilde{p}^{\prime}_{\alpha,0}>\frac{1}{2}+\epsilon-4\epsilon^{\prime}-\epsilon^{\prime}]\geq
1-\delta^{\prime}.$ (34)

###### Lemma 4.9.

When $x[1]=0$, $D_{1}$ is computationally indistinguishable from $D$.

###### Proof.

The difference between $D_{1}$ and $D$ is that $\mathsf{ct}$ is generated as
$\mathsf{ct}\leftarrow\mathsf{CPFE}.\mathsf{Enc}\allowbreak(\mathsf{MPK},C^{*}[b,m_{0},m_{1},1])$
in $D_{1}$ and it is generated as
$\mathsf{ct}\leftarrow\mathsf{CPFE}.\mathsf{Enc}(\mathsf{MPK},C[\mathsf{m}_{b}])$
in $D$. From the condition that $x[1]=0$, we have
$C^{*}[b,m_{0},m_{1},1](x)=C[m_{b}](x)=m_{b}$. Thus, from the $1$-bounded
security of $\mathsf{CPFE}$, $D_{1}$ and $D$ are computationally
indistinguishable when $x[1]=0$. ∎

Thus, from Theorem 2.6 and Lemma 4.9, we have

$\displaystyle
1-\delta^{\prime}\leq\Pr[\widetilde{p}^{\prime}_{\alpha,0}>\frac{1}{2}+\epsilon-5\epsilon^{\prime}]\leq\Pr[\widetilde{p}_{\alpha,1}>\frac{1}{2}+\epsilon-8\epsilon^{\prime}]+{\mathsf{negl}}(\lambda).$
(35)

This means that $\Pr[\mathsf{BadExt}_{\alpha,1}]={\mathsf{negl}}(\lambda)$
when $x[1]=0$. We next consider the case of $x[1]=1$. We define the following
distribution $D^{\mathtt{rev}}$.

$D^{\mathtt{rev}}$:

Generate $(b,\mathsf{ct})\leftarrow D$. Output $(1\oplus b,\mathsf{ct})$.

That is, the first bit of the output is flipped from $D$. Then, for any random
coin $r$, we have
$(\bm{P}_{D^{\mathtt{rev}}(r)},\bm{Q}_{D^{\mathtt{rev}}(r)})=(\bm{Q}_{D(r)},\bm{P}_{D(r)})$.
This is because we have
$\bm{Q}_{b,\mathsf{ct}}=\bm{I}-\bm{P}_{b,\mathsf{ct}}=\bm{P}_{1\oplus
b,\mathsf{ct}}$ for any tuple $(b,\mathsf{ct})$. Therefore,
$\mathpzc{API}_{\mathcal{P},D^{\mathtt{rev}}}^{\epsilon^{\prime},\delta^{\prime}}$
is exactly the same process as
$\mathpzc{API}_{\mathcal{P}^{\mathtt{rev}},D}^{\epsilon^{\prime},\delta^{\prime}}$,
where
$\mathcal{P}^{\mathtt{rev}}=(\bm{Q}_{b,\mathsf{ct}},\bm{P}_{b,\mathsf{ct}})_{b,\mathsf{ct}}$.
Let
$\widetilde{p}^{\prime}_{\alpha,0}\leftarrow\mathpzc{API}_{\mathcal{P},D^{\mathtt{rev}}}^{\epsilon^{\prime},\delta^{\prime}}(\mathpzc{q}_{\alpha,0})$.
From, the reverse-almost-projective property of $\mathpzc{API}$, we have

$\displaystyle\Pr[\widetilde{p}^{\prime}_{\alpha,0}<\frac{1}{2}-\epsilon+4\epsilon^{\prime}+\epsilon^{\prime}]\geq
1-\delta^{\prime}.$ (36)

###### Lemma 4.10.

When $x[1]=1$, $D_{1}$ is computationally indistinguishable from
$D^{\mathtt{rev}}$.

###### Proof.

We see that $D^{\mathtt{rev}}$ is identical to the following distribution.

  * •

Generate $b\leftarrow\\{0,1\\}$ and
$\mathsf{ct}\leftarrow\mathsf{Enc}(\mathsf{ek},\mathsf{m}_{1\oplus b})$.
Output $(b,\mathsf{ct})$.

Then, the difference between $D_{1}$ and $D^{\mathtt{rev}}$ is that
$\mathsf{ct}$ is generated as
$\mathsf{ct}\leftarrow\mathsf{CPFE}.\mathsf{Enc}(\mathsf{MPK},C^{*}[b,m_{0},m_{1},1])$
in $D$ and it is generated as
$\mathsf{ct}\leftarrow\mathsf{CPFE}.\mathsf{Enc}(\mathsf{MPK},C[\mathsf{m}_{1\oplus
b}])$ in $D^{\mathtt{rev}}$. From the condition that $x[1]=1$, we have
$C^{*}[b,m_{0},m_{1},1](x)=C[m_{1\oplus b}](x)=\mathsf{m}_{1\oplus b}$. Thus,
from the $1$-bounded security of $\mathsf{CPFE}$, $D_{1}$ and
$D^{\mathtt{rev}}$ are computationally indistinguishable when $x[1]=1$. ∎

Thus, from Theorem 2.6 and Lemma 4.10, we have

$\displaystyle
1-\delta^{\prime}\leq\Pr[\widetilde{p}^{\prime}_{\alpha,0}<\frac{1}{2}-\epsilon+5\epsilon^{\prime}]\leq\Pr[\widetilde{p}_{\alpha,1}<\frac{1}{2}-\epsilon+8\epsilon^{\prime}]+{\mathsf{negl}}(\lambda).$
(37)

This means that $\Pr[\mathsf{BadExt}_{\alpha,1}]={\mathsf{negl}}(\lambda)$
when $x[1]=1$.

Overall, $\Pr[\mathsf{BadExt}_{\alpha,1}]={\mathsf{negl}}(\lambda)$ regardless
of the value of $x[1]$. We can similarly show that
$\Pr[\mathsf{BadExt}_{\alpha,i}]={\mathsf{negl}}(\lambda)$ for
$i\in\\{2,\cdots,\lambda\\}$ using the fact that $D_{i}$ is computationally
indistinguishable from $D$ if $x[i]=0$ and it is computationally
indistinguishable form $D^{\mathtt{rev}}$ if $x[i]=1$. We omit the details.

From the above discussion, we have
$\Pr[\mathsf{MoEBB84Leak}(\mathpzc{A},\lambda)=1]=\eta-{\mathsf{negl}}(\lambda)$
for some inverse polynomial $\eta$, which contradicts to the monogamy property
of BB84 states with leakage. This completes the proof of Theorem 4.7. ∎

##  5 Quantum Copy-Protection from Unclonable Encryption

We introduce one-out-of-many copy protection security for single-bit output
point functions and present how to achieve it using one-out-of-many secure
unclonable encyption in this section.

###  5.1 Definition

###### Definition 5.1 (Copy-Protection (Syntax)).

A copy-protection scheme $\mathsf{CP}$ for a family of circuits $\mathcal{C}$
consists of two algorithms $(\mathpzc{CopyProtect},\mathpzc{Eval})$.

$\mathpzc{CopyProtect}(1^{\lambda},C)\rightarrow\rho$:

The copy-protection algorithm takes as input the security parameter
$1^{\lambda}$, a circuit $C\in\mathcal{C}$, and outputs a quantum state
$\rho$.

$\mathpzc{Eval}(\rho,x)$:

The evaluation algorithm takes as input a quantum state $\rho$ and an input
$x$, and outputs $y$.

Evaluation Correctness:

For every circuit $C$ and input $x$, we have

$\displaystyle\Pr[\mathpzc{Eval}(\rho,x)=C(x)\mid\rho\leftarrow\mathpzc{CopyProtect}(1^{\lambda},C)]=1-{\mathsf{negl}}(\lambda).$
(38)

######  Remark 5.2.

We can assume without loss of generality that a copy protected program $\rho$
output by $\mathpzc{CopyProtect}$ is reusable, that is, it can be reused
polynomially many times. This is because the output of $\mathpzc{Eval}$ on
input $\rho$ and any input $x$ is almost deterministic by correctness, and
thus such an operation can be done without almost disturbing $\rho$ by the
gentle measurement lemma [Win99].

We focus on copy protection scheme for a family of single-bit output point
functions that we denote $\mathcal{P}\mathcal{F}^{1}$. We also define a family
of single-bit output point functions
$\mathcal{P}\mathcal{F}_{\ell_{\mathsf{inp}}}^{1}$ as
$\mathcal{P}\mathcal{F}_{\ell_{\mathsf{inp}}}^{1}=\\{f_{y}\\}_{y\in\\{0,1\\}^{\ell_{\mathsf{inp}}}}$,
where $f_{y}$ outputs $1$ if the input is
$y\in\\{0,1\\}^{\ell_{\mathsf{inp}}}$ and $0$ otherwise.

We review the widely used copy-protection security for
$\mathcal{P}\mathcal{F}^{1}$ originally introduced by Coladangelo et al.
[CMP20].

###### Definition 5.3 (Copy-Protection Security for
$\mathcal{P}\mathcal{F}^{1}$).

Let $\mathsf{CP}$ be a copy protection scheme for
$\mathcal{P}\mathcal{F}_{\ell_{\mathsf{inp}}}^{1}$. Let $D_{Y}$ be a
distribution over $\\{0,1\\}^{\ell_{\mathsf{inp}}}$. Let $D_{X}(\cdot)$ be a
distribution over
$\\{0,1\\}^{\ell_{\mathsf{inp}}}\times\\{0,1\\}^{\ell_{\mathsf{inp}}}$, where
$D_{X}(\cdot)$ takes as input $y^{\prime}\in\\{0,1\\}^{\ell_{\mathsf{inp}}}$.
We consider the following security experiment
$\mathsf{Exp}_{\mathsf{CP},D_{Y},D_{X},\mathpzc{A}}^{\mathsf{cp}\mbox{-}\mathsf{pf1}}(\lambda)$
for $\mathpzc{A}=(\mathpzc{A}_{0},\mathpzc{A}_{1},\mathpzc{A}_{2})$.

  1. 1.

The challenger generates $y\leftarrow D_{Y}$. The challenger generates
$\rho\leftarrow\mathpzc{CopyProtect}(1^{\lambda},f_{y})$ and sends $\rho$ to
$\mathpzc{A}_{0}$.

  2. 2.

$\mathpzc{A}_{0}$ creates a bipartite state $\mathpzc{q}$ over registers
${\color[rgb]{.5,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,.5,.5}\pgfsys@color@gray@stroke{.5}\pgfsys@color<EMAIL_ADDRESS>and
${\color[rgb]{.5,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,.5,.5}\pgfsys@color@gray@stroke{.5}\pgfsys@color<EMAIL_ADDRESS>$\mathpzc{A}_{0}$ sends
$\mathpzc{q}[{\color[rgb]{.5,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,.5,.5}\pgfsys@color@gray@stroke{.5}\pgfsys@color<EMAIL_ADDRESS>and
$\mathpzc{q}[{\color[rgb]{.5,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,.5,.5}\pgfsys@color@gray@stroke{.5}\pgfsys@color<EMAIL_ADDRESS>to $\mathpzc{A}_{1}$ and $\mathpzc{A}_{2}$, respectively.

  3. 3.

The challenger generates $(x_{1},x_{2})\leftarrow D_{X}(y)$, and sends $x_{1}$
and $x_{2}$ to $\mathpzc{A}_{1}$ and $\mathpzc{A}_{2}$, respectively.

  4. 4.

$\mathpzc{A}_{1}$ and $\mathpzc{A}_{2}$ respectively output $b_{1}$ and
$b_{2}$. If $b_{i}=f_{y}(x_{i})$ for $i\in\\{1,2\\}$, the challenger outputs
$1$, otherwise outputs $0$.

We define
$p^{\mathtt{triv}}=\max_{i\in\\{1,2\\},\mathpzc{S}}p_{i,\mathpzc{S}}$, where

$\displaystyle p_{i,\mathpzc{S}}=\Pr\left[b_{i}=f_{y}(x_{i})\
\middle|\begin{array}[]{ll}y\leftarrow D_{Y},(x_{1},x_{2})\leftarrow
D_{X}(y)\\\ b_{i}\leftarrow\mathpzc{S}(x_{i})\end{array}\right]$ (41)

and the maximization is done by all possibly computationally unbounded
algorithm $\mathpzc{S}$.

We say that $\mathsf{CP}$ satisfies copy-protection security for
$\mathcal{P}\mathcal{F}^{1}$ with respect to $D_{Y}$ and $D_{X}$ if for any
QPT $\mathpzc{A}$, it holds that

$\displaystyle\mathsf{Adv}_{\mathsf{CP},D_{Y},D_{X},\mathpzc{A}}^{\mathsf{cp}\mbox{-}\mathsf{pf1}}(\lambda)\coloneqq\Pr[\mathsf{Exp}_{\mathsf{CP},D_{Y},D_{X},\mathpzc{A}}^{\mathsf{cp}\mbox{-}\mathsf{pf1}}(\lambda)=1]\leq
p^{\mathtt{triv}}+{\mathsf{negl}}(\lambda).$ (42)

The following definition is a natural adaptation of Definition 5.3 into one-
out-of-many setting.

###### Definition 5.4 (One-out-of-Many Copy-Protection Security for
$\mathcal{P}\mathcal{F}^{1}$).

Let $\mathsf{CP}$ be a copy protection scheme for
$\mathcal{P}\mathcal{F}_{\ell_{\mathsf{inp}}}^{1}$. Let $D_{Y}$ and
$D_{X}(\cdot)$ be distributions over $\\{0,1\\}^{\ell_{\mathsf{inp}}}$, where
$D_{X}(\cdot)$ takes as input $y^{\prime}\in\\{0,1\\}^{\ell_{\mathsf{inp}}}$.
We consider the following security experiment
$\mathsf{Exp}_{\mathsf{CP},D_{Y},D_{X},\mathpzc{A}}^{\mathsf{cp}\mbox{-}\mathsf{pf1}\mbox{-}\mathsf{om}}(\lambda,n)$
for $\mathpzc{A}=(\mathpzc{A}_{0},\mathpzc{A}_{1},\cdots,\mathpzc{A}_{n})$.

  1. 1.

The challenger generates $y\leftarrow D_{Y}$. The challenger generates
$\rho\leftarrow\mathpzc{CopyProtect}(1^{\lambda},f_{y})$ and sends $\rho$ to
$\mathpzc{A}_{0}$.

  2. 2.

$\mathpzc{A}_{0}$ creates a quantum state $\mathpzc{q}$ over $n$ registers
${\color[rgb]{.5,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,.5,.5}\pgfsys@color@gray@stroke{.5}\pgfsys@color@gray@fill{.5}{\mathsf{R}}}_{1},\cdots,{\color[rgb]{.5,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,.5,.5}\pgfsys@color@gray@stroke{.5}\pgfsys@color<EMAIL_ADDRESS>$\mathpzc{A}_{0}$ sends
$\mathpzc{q}[{\color[rgb]{.5,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,.5,.5}\pgfsys@color@gray@stroke{.5}\pgfsys@color<EMAIL_ADDRESS>to $\mathpzc{A}_{i}$ for every $i\in[n]$.

  3. 3.

The challenger generates $\alpha\leftarrow[n]$. The challenger generates
$x\leftarrow D_{X}(y)$ and sends $x$ to $\mathpzc{A}_{\alpha}$.
$\mathpzc{A}_{\alpha}$ outputs $b_{\alpha}$. If $b_{\alpha}=f_{y}(x)$, the
challenger outputs $1$, otherwise outputs $0$.

We define $p^{\mathtt{triv}}=\max_{\mathpzc{S}}p_{\mathpzc{S}}$, where

$\displaystyle p_{\mathpzc{S}}=\Pr\left[b=f_{y}(x)\
\middle|\begin{array}[]{ll}y\leftarrow D_{Y},x\leftarrow D_{X}(y)\\\
b\leftarrow\mathpzc{S}(x)\end{array}\right]$ (45)

and the maximization is done by all possibly computationally unbounded
algorithm $\mathpzc{S}$.

We say that $\mathsf{CP}$ satisfies one-out-of-many copy-protection security
for $\mathcal{P}\mathcal{F}^{1}$ with respect to $D_{Y}$ and $D_{X}$ if for
any polynomial $n=n(\lambda)$ and QPT $\mathpzc{A}$, it holds that

$\displaystyle\mathsf{Adv}_{\mathsf{CP},D_{Y},D_{X},\mathpzc{A}}^{\mathsf{cp}\mbox{-}\mathsf{pf1}\mbox{-}\mathsf{om}}(\lambda,n)\coloneqq\Pr[\mathsf{Exp}_{\mathsf{CP},D_{Y},D_{X},\mathpzc{A}}^{\mathsf{cp}\mbox{-}\mathsf{pf1}\mbox{-}\mathsf{om}}(\lambda,n)=1]\leq\frac{1}{n}\cdot
1+\frac{n-1}{n}\cdot p^{\mathtt{triv}}+{\mathsf{negl}}(\lambda).$ (46)

###  5.2 Construction

We construct a copy-protection scheme for single-bit output point functions
$\mathcal{P}\mathcal{F}_{\ell_{\mathsf{inp}}}^{1}$, where
$\ell_{\mathsf{inp}}$ is specified later. We use the following tools:

  * •

SKUE
$\mathsf{UE}=(\mathsf{UE}.\mathsf{KG},\mathsf{UE}.\mathpzc{Enc},\mathsf{UE}.\mathpzc{Dec})$.
Suppose the plaintext space of $\mathsf{UE}$ is $\\{0,1\\}^{\lambda}$ and the
key length is $\ell_{\mathsf{uk}}$.

  * •

Injective commitment scheme with equivocal mode
$\mathsf{Com}=(\mathsf{Setup},\mathsf{Commit},\mathsf{EqSetup},\mathsf{Open})$.
Suppose the message space of $\mathsf{Com}$ is
$\\{0,1\\}^{\ell_{\mathsf{uk}}}$ and the random coin space is
$\\{0,1\\}^{\ell_{\mathsf{comr}}}$.

  * •

Compute-and-compare obfuscation $\mathsf{CC}.\mathsf{Obf}$ with the simulator
$\mathsf{CC}.\mathsf{Sim}$. In this section, the message feed to
$\mathsf{CC}.\mathsf{Obf}$ is fixed to $1$. Thus, we omit to write it from the
input.

  * •

QFHE with classical ciphertexts
$\mathsf{QFHE}=(\mathsf{QFHE}.\mathsf{KG},\mathsf{QFHE}.\mathsf{Enc},\mathsf{QFHE}.\mathpzc{Eval},\mathsf{QFHE}.\mathsf{Dec})$.

We set $\ell_{\mathsf{inp}}=\ell_{\mathsf{uk}}+\ell_{\mathsf{comr}}$. The