11institutetext: DIENS, École normale supérieure, PSL University, CNRS, INRIA,
Paris, France 22institutetext: CRED, Université Panthéon-Assas Paris II,
Paris, France 33institutetext: LIP6, Sorbonne Université, Paris, France
44institutetext: Léonard de Vinci Pôle Universitaire, Research Center, Paris
La Défense, France
44email: {celine.chevalier, paul.hermouet<EMAIL_ADDRESS>
# Unclonable Cryptography in the Plain Model

Céline Chevalier 1122 Paul Hermouet 112233 Quoc-Huy Vu 44

###### Abstract

By leveraging the no-cloning principle of quantum mechanics, unclonable
cryptography enables us to achieve novel cryptographic protocols that are
otherwise impossible classically. Two most notable examples of unclonable
cryptography are quantum copy-protection and unclonable encryption. Despite
receiving a lot of attention in recent years, two important open questions
still remain: copy-protection for point functions in the plain model, which is
usually considered as feasibility demonstration, and unclonable encryption
with unclonable indistinguishability security in the plain model.

In this work, by relying on previous works of Coladangelo, Liu, Liu, and
Zhandry (Crypto’21) and Culf and Vidick (Quantum’22), we establish a new
monogamy-of-entanglement property for subspace coset states, which allows us
to obtain the following new results:

  * •

We show that copy-protection of point functions exists in the plain model,
with different challenge distributions (including arguably the most natural
ones).

  * •

We show, for the first time, that unclonable encryption with unclonable
indistinguishability security exists in the plain model.

##  1 Introduction

Quantum information enables us to achieve new cryptographic primitives that
are impossible classically, leading to a prominent research area named
unclonable cryptography. At the heart of this area is the no-cloning principle
of quantum mechanics [WZ82], which has given rise to many unclonable
cryptographic primitives. This includes quantum money [Wie83], quantum copy-
protection [Aar09], unclonable encryption [BL20], single-decryptor encryption
[CLLZ21], and many more. In this work, our focus is on quantum copy-protection
and unclonable encryption.

#### Copy-protection for point functions.

Quantum copy-protection, introduced by Aaronson in [Aar09], is a
functionality-preserving compiler that transforms programs into quantum
states. Moreover, we require that the resulting copy-protected state should
not allow the adversary to copy the functionality of the state. In particular,
this unclonability property, which is often associated with challenge
distributions, is stated as the following game. A splitting adversary
$(\adv,\bdv,\cdv)$ first has $\adv$ receive as input a copy-protected state
that can be used to compute a function $f$. $\adv$ then outputs a bipartite
state to $\bdv$ and $\cdv$. We require that both $\bdv$ and $\cdv$ should not
be able to simultaneously compute $f$, where the inputs given to $\bdv$ and
$\cdv$ are drawn from a distribution, called a _challenge distribution_.

While copy-protection is known to be impossible for general unlearnable
functions and the class of de-quantumizable algorithms [AL21], several
feasibility results have been demonstrated for cryptographic functions (e.g.,
pseudorandom functions, decryption and signing algorithm [CLLZ21, LLQZ22]). Of
particular interest to us is the class of point functions, which is of the
form $f_{y}(\cdot)$: it takes as input $x$ and outputs 1 if and only if $x=y$.

Prior works [CMP20, AK21, AKL+22, AKL23, CHV23] achieved a copy-protection
scheme for point functions with different type of states (e.g., BB84 states
[BB20] or coset states [CLLZ21]) and different challenge distributions.
However, in contrast to known constructions for copy-protection for
cryptographic functions which are in the plain model, these constructions for
copy-protection for point functions are all in the quantum random oracle
model. The only known copy-protection for point functions scheme in the plain
model was recently constructed in [CHV23], but this scheme was shown to be
secure with respect to a “less natural” challenge distribution. We note that
different feasibility for the same copy-protection scheme, based on different
challenge distributions, can be qualitatively incomparable. That is, security
established under one challenge distribution might not necessarily guarantee
security under a different challenge distribution.

Given the inability to prove security with respect to certain natural
challenge distributions for copy-protection for point functions, an important
question that has been left open from prior works is the following:

_Question 1. Do copy-protection schemes for point functions, with negligible
security
and natural challenge distributions, in the plain model exist?_

#### Unclonable Encryption.

Unclonable encryption, introduced by Broadbent and Lord [BL20], is another
beautiful primitive of unclonable cryptography. Roughly speaking, unclonable
encryption is an encryption scheme with quantum ciphertexts having the
following security guarantee: given a quantum ciphertext, no adversary can
produce two (possibly entangled) states that both encode some information
about the original plaintext. Interestingly, besides its own applications,
unclonable encryption also implies private-key quantum money, and copy-
protection for a restricted class of functions [BL20, AK21].

Despite being a natural primitive, constructing unclonable encryption has
remained elusive. Prior works [BL20, AK21] established the feasibility of
unclonable encryption satisfying a weaker property called unclonability, which
can be seen as a _search_ -type security. This weak security notion is far
less useful, as it does not imply the standard semantic security of an
encryption scheme, and also does not lead to the application implication
listed above. The stronger notion, the so-called _unclonable
indistinguishability_ , is only known to be achievable in the quantum random
oracle model [AKL+22]. Given the notorious difficulty of building unclonable
encryption in the standard model, the following question has been left open
from prior works:

_Question 2. Do encryption schemes satisfying unclonable indistinguishability
in the plain model exist?_

In this paper, we answer the two questions above affirmatively. Firstly, we
present a construction of copy-protection of point functions with negligible
security in the plain model. We show that this construction is secure, for
three families of distributions: product distributions, identical
distributions and non-colliding distribution. Secondly, we exhibit two
constructions of unclonable encryption with unclonable indistinguishability
security in the plain model: one for single-bit encryption and the other for
multi-bit encryption. Our constructions based on the construction of single-
decryptor, introduced by [CLLZ21], with new security variants. In the process,
we also present a new monogamy-of-entanglement (MoE) property of coset states
which might be of independent interest.

#### Concurrent and Independent Work.

Very recently, two concurrent and independent works have consider similar
tasks. However, at a high level, the themes of these two papers and ours are
quite different. Coladangelo and Gunn [CG23] show the feasibility of copy-
protection of puncturable functionalities and point functions through a new
notion of quantum state indistinguishability obfuscation, which is also
introduced in the same paper. Ananth and Behera [AB23] also show constructions
for copy-protection of puncturable functionalities (including point functions)
and unclonable encryption, based on a new notion of unclonable puncturable
obfuscation. Among the two, the latter is most similar to our work. Their
construction of unclonable puncturable obfuscation, which is the backbone for
their applications (of copy-protection of point functions and unclonable
encryption), is based on the recent construction of copy-protection of
pseudorandom functions and single-decryptor of Coladangelo et al. [CLLZ21].
They show that a slightly modified construction of [CLLZ21] achieves anti-
piracy security with different challenge distributions and preponed security.
Apart from the naming, these security notions are identical to what we
consider here in our paper. However, the security of their schemes are based
on a new conjecture. We directly show that the same constructions of [CLLZ21]
achieve these security notions, by proving a new monogamy-of-entanglement
property of coset states. This allows us to obtain the first constructions of
copy-protection of point functions and unclonable encryption in the plain
model based on well-studied cryptographic assumptions. Lastly, while the two
concurrent works propose more generic approaches, we believe that our concrete
constructions might be applicable on these approaches to obtain feasibility
results based on standard assumptions.

###  1.1 Technical Overview

We first recall the anti-piracy security definition, discuss several challenge
distributions for copy-protection of point functions, and then present
techniques to achieve security with respect to these challenge distributions.

#### Anti-piracy security.

A piracy game is formalized as a security experiment against cloning
adversaries of the form $(\mathcal{P},\mathcal{F}_{1},\mathcal{F}_{2})$. The
pirate $\mathcal{P}$ receives an copy-protected program
$\rho_{f}\coloneqq\mathsf{Protect}(f)$, which can be used to evaluate a
classical function $f$, prepares a bipartite state, and sends each half of the
state to two non-communicating freeloaders $\mathcal{F}_{1}$ and
$\mathcal{F}_{2}$. In the challenge phase, $\mathcal{F}_{1}$ and
$\mathcal{F}_{2}$ receive inputs $c_{1},c_{2}$, sampled from a challenge
distribution and are asked to output $b_{1},b_{2}$.
$(\mathcal{P},\mathcal{F}_{1},\mathcal{F}_{2})$ win if $b_{i}=f(c_{i})$ for
$i\in\\{1,2\\}$.

It turns out that the choice of challenge distribution plays a crucial role in
evaluating security of copy-protection schemes. Indeed, previous constructions
of copy-protection of point functions have considered different challenge
distributions [CMP20, BJL+21, AKL+22, CHV23]. Some are considered “less
natural” than the others. Ideally, we would like to prove security of the
scheme in a way that is independent of the chosen challenge distribution. In
this paper, we make progress towards achieving this goal. In particular, in
the following, let $y\in\bin^{n}$ the copy-protected point, $x,x^{\prime}$
random strings drawn from some distribution. We consider the following
challenge distributions for copy-protecting point functions.

  * •

Identical: $\mathcal{F}_{1}$ and $\mathcal{F}_{2}$ get either $(y,y)$ or
$(x,x)$ with probability $\frac{1}{2}$ each, where $x$ is drawn uniformly at
random from $\bin^{n}\setminus\\{y\\}$.

  * •

Product: $\mathcal{F}_{1}$ and $\mathcal{F}_{2}$ get either $(y,y)$, $(x,y)$,
$(y,x)$, or $(x,x^{\prime})$ each with probability $\frac{1}{4}$, where
$x,x^{\prime}$ are drawn uniformly at random from $\bin^{n}\setminus\\{y\\}$.

  * •

Non-Colliding: $\mathcal{F}_{1}$ and $\mathcal{F}_{2}$ get either $(x,y)$,
$(y,x)$, or $(x,x^{\prime})$ each with probability $\frac{1}{3}$, where
$x,x^{\prime}$ are drawn uniformly at random from $\bin^{n}\setminus\\{y\\}$.

Arguably, since the copy-protected point basically represents the entire
functionality of the point function, one would say the product distribution is
the most meaningful and natural one. However, the only known construction
known before our work that achieves copy-protection of point functions in the
plain model is the one given in [CHV23], which only achieves security w.r.t
non-colliding distribution. Our construction is identical to that of [CHV23]
and our main technical contribution lies in our proof technique showing that
[CHV23] construction can achieve security with respect to product and
identical distributions.

We continue by recalling [CHV23] construction and briefly explain where it
fails when proving security w.r.t the product challenge distribution, then we
describe our new proof techniques that allow us to overcome the problems.

####  [CHV23]’s copy-protection of point functions.

At a high level, [CHV23] scheme uses a copy-protection scheme of pseudorandom
functions (PRFs) $\prf(\key,\cdot)$ from [CLLZ21]. Protecting a point function
$\mathsf{PF}_{y}$ is done in the following way: sample a PRF key $\key$; then
copy-protect $\key$ using the PRF protection algorithm to get $\rho_{\key}$;
and finally compute $z\leftarrow\prf(\key,y)$ and return the outcome $z$ as
well as $\rho_{\key}$. One can evaluate the copy-protected point function
$\mathsf{PF}_{y}$ on an input $x$ in the following way: compute $\prf(\key,x)$
using the evaluation algorithm of the PRF copy-protection scheme, then check
whether the outcome equals $z$ or not and return $1$ or $0$ accordingly.
Although [CHV23] construction can be cast in the form, we note that their
reduction (and ours) go through an intermediate notion of single decryptor,
which ultimately reduces to some form of monogamy-of-entanglement of hidden
coset states. We refer the reader to the formal proof provided in Section 4
and Section 5 for more details.

#### Challenges when proving anti-piracy security w.r.t the product
distribution.

A coset state is a quantum state of the form
$\ket{A_{s,s^{\prime}}}\coloneqq\frac{1}{\sqrt{\lvert A\rvert}}\sum_{x\in
A}(-1)^{\langle x,s^{\prime}\rangle}\ket{x+s}$ for a subspace
$A\subseteq\FF_{2}^{n}$ and two vectors $s,s^{\prime}\in\FF_{2}^{n}$. Loosely
speaking, a coset state $\ket{A_{s,s^{\prime}}}$ embeds information on both
the coset $A+s$ and its dual $A^{\perp}+s^{\prime}$, and has the following
monogamy-of-entanglement property: given a random coset state
$\ket{A_{s,s^{\prime}}}$, no adversary can split the state and share it to two
non-communicating freeloaders such that, given the description of the subspace
$A$, the first freeloader returns a vector in the coset $A+s$ and the second
one a vector in the dual $A^{\perp}+s^{\prime}$. To prove security based on
monogamy-of-entanglement of coset states, the authors of [CHV23] (based on
techniques from [CLLZ21]) use an extraction property of lockable obfuscation
to extract and outputs two vectors which, with non-negligible probability
belong respectively to $A+s$ and $A^{\perp}+s^{\prime}$, which works perfectly
when the challenge distribution is non-colliding. However, when considering
the identical distribution (or the product distribution for the case when the
challenge inputs are $(y,y)$), the adversary is required to output two vectors
(not necessarily different) from _the same_ coset space: that is, they are
either both in $A+s$ or $A^{\perp}+s^{\prime}$. This in turn leads to no
violation against the monogamy-of-entanglement game describe above. Worse, if
the adversary knows which basis it would play with (either the computational
basis for coset space $A+s$ or the Hadamard basis for coset space
$A^{\perp}+s^{\prime}$), the adversary can win the game trivially.

#### Unclonable encryption.

In this paper, we also propose a construction for unclonable encryption with
unclonable indistinguishability in the plain model. The unclonable
indistinguishability for this primitive is also defined through a piracy game,
in which the pirate $\mathcal{P}$ receives a quantum encryption of a bit $b$,
prepares a bipartite state, and sends each half of the state to two non-
communicating freeloaders $\mathcal{F}_{1}$ and $\mathcal{F}_{2}$. In the
challenge phase, $\mathcal{F}_{1}$ and $\mathcal{F}_{2}$ both receive the
decryption key $\key$ and are asked to output $b_{1},b_{2}$.
$(\mathcal{P},\mathcal{F}_{1},\mathcal{F}_{2})$ win if $b_{i}=b$ for
$i\in\\{1,2\\}$. Our construction of unclonable encryption also uses a copy-
protection scheme of PRF. A key is simply a random bitstring $\key_{S}$.
Encrypting a bit $b$ is done by in the following way: sample a PRF key
$\key_{P}$; then copy-protect $\key_{P}$ using the PRF protection algorithm to
get $\rho_{\key_{P}}$; finally sample a fresh random bitstring $r$ and output
$(r,y,\rho_{\key_{P}})$ where $y$ is either $\prf(\key_{P},\key_{S}\oplus r)$
if $b=0$, or a random bitstring if $b=1$. Similarly as for copy-protection of
point function, the security of our unclonable encryption construction also
reduces to a monogamy-of-entanglement game. As in the piracy game for this
primitive, the same challenge is used for both $\mathcal{F}_{1}$ and
$\mathcal{F}_{2}$, we meet the same problem as for our copy-protection
construction, namely that the adversaries are required to output two vectors
from the same coset space.

#### Our technique: a new monogamy-of-entanglement game of coset states.

We resolve this problem by introducing a new variant of the monogamy-of-
entanglement property of coset states. In this variant, the freeloaders both
have to output a vector in the same coset space, either $A+s$ or
$A^{\perp}+s^{\prime}$, but they learn the challenge coset space only during
the challenge phase after receiving the state from the pirate $\mathcal{P}$.
Crucially the pirate also does not know the challenge coset space before the
challenge phase. We call this new game as _Monogamy-of-Entanglement Game with
Identical Basis_. An illustration of this new game is depicted in Figure 1.

$\mathsf{Challenger}$pt$(A,s,s^{\prime})\leftarrow\$$$b\leftarrow\bin$
$\mathcal{P}$$\ket{A_{s,s^{\prime}}}$$\mathcal{F}_{1}$$\sigma_{1}$$(A,b)$$u_{1}$$\mathcal{F}_{2}$$\sigma_{2}$$(A,b)$$u_{2}$ptWin
Condition:$u_{1},u_{2}\in\begin{cases}A+s&\text{ if }b=0\\\
A^{\perp}+s^{\prime}&\text{ if }b=1\end{cases}$ Figure 1: Monogamy-of-
Entanglement Game with Identical Basis (Coset Version)

We show that the winning probability of this game is at most negligibly far
way from $1/2$, which corresponds to the trivial strategy in which the pirate
always measures the coset state in the computational basis and forwards the
outcome to both the freeloaders, who in turn output it. An overview of the
proof is given at the end of the section.

For now, assuming that we have this property. It is then not hard to see that
a parallel repetition of this game reduces the winning probability to
negligible.111We provide a proof for the parallel version of this game in
Section 3.6Using this new monogamy-of-entanglement property, we are able to
prove security of copy-protection of point functions w.r.t to the product
distribution as well as the identical distribution. Our observation here is
that the challenge inputs pair $(y,y)$ corresponds to a description of the
challenge basis for the monogamy-of-entanglement with identical basis game: in
particular, let $y\coloneqq y_{0}\ldots y_{n}$, each $y_{i}$ describes the
challenge basis for the $i$-th instance of the monogamy game: if $y_{i}=0$, it
is the computational basis (corresponding to the coset space $A_{i}+s_{i}$),
otherwise, it is the Hadamard basis (corresponding to the coset space
$A^{\perp}_{i}+s^{\prime}_{i}$). The final step in the proof is to show that,
if there exists an adversary that wins the anti-piracy game with challenge
input $(y,y)$, we can construct two non-communicating extractors that output
$n$ vectors $(v_{i},w_{i})_{i\in[1,n]}$ satisfying that $v_{i},w_{i}$ both
belong to the same challenge coset space for all $i\in[1,n]$. This step can be
done by using extracting lockable obfuscation technique from [CLLZ21]. .

#### Proof of the new monogamy-of-entanglement game.

We describe the proof of the _BB84 version_ of our new monogamy-of-
entanglement game, as the coset version reduces to this game as proven in
[CV22]. In the BB84 version, the challenger sends $n$ BB84 states
$\bigotimes_{i=1}^{n}\ket{x_{i}}^{\theta_{i}}$ to the pirate, and the
freeloaders are given the basis $\theta$ and a random bit $b$. To win the
game, the freeloaders both need to output a bitstring $x^{*}$ such that
$x^{*}$ is equal to $x$ on all the indices $i$ such that $\theta_{i}=b$. This
proof uses the template of [CV22] and can described in three steps. We refer
the reader to Section 3 for the formal proof.

  1. 1.

In the first step, we define the _extended non-local game_ [JMRW16] associated
to this monogamy-of-entanglement game. This game is between a challenger and
two players. The players start by preparing a tripartite quantum state
$\rho_{012}$; each of them keep one register, and they send the last one, say
$\rho_{2}$, to the challenger. After this point, the players are not allowed
to communicate. The challenger samples $n$ BB84 basis $\theta\in\bin^{n}$ at
random, then measures each qubit $\rho_{C,i}$ of $\rho_{C}$ in the
corresponding basis $\theta_{i}$; let $x$ denote the outcome. Finally, the
challenger sends $\theta$, as well as a random bit $b$, to the two players.
Each player is asked to output a bitstring $x^{*}$ such that $x^{*}$ is equal
to $x$ on all the indices $i$ such that $\theta_{i}=b$.

We show that the largest winning probability of the monogamy game is the same
as the one of this extended non-local game. In this step, we use a technique
from [TFKW13] to bound this winning probability.

  2. 2.

In the second step, we express any strategy for this extended non-local game
with security parameter $n\in\NN$ as a tripartite quantum state $\rho_{012}$
as well as two families of projective measurements, $\\{B^{\theta,b}\\}$ and
$\\{C^{\theta,b}\\}$, both indexed by $\theta\in\mathrm{\Theta}_{n}$ and
$b\in\bin$. We define the projector
$\mathrm{\Pi}_{\theta,b}=\sum_{x\in\bin^{n}}{|x\rangle\\!\langle
x|}^{\theta}\otimes B^{\theta,b}_{x_{T_{b}}}\otimes C^{\theta,b}_{x_{T_{b}}}$
such that the winning probability of this strategy is
$p_{win}=\mathop{\expectationname}_{\theta,b}\left[\mathsf{Tr}\left(\mathrm{\Pi}_{\theta,b}\
\rho_{012}\right)\right]$. Then, we show the following upper-bound:

$\displaystyle p_{win}$
$\displaystyle\leq\frac{1}{2N}\sum_{\begin{subarray}{c}1\leq k\leq N\\\
\alpha\in\bin\end{subarray}}\
\max_{\theta,b}\big{\lVert}\mathrm{\Pi}_{\theta,b}\mathrm{\Pi}_{\pi_{k,\alpha}(\theta\|b)}\rVert$
$\displaystyle=\frac{1}{2}+\frac{1}{2N}\sum_{1\leq k\leq N}\
\max_{\theta,b}\big{\lVert}\mathrm{\Pi}_{\theta,b}\mathrm{\Pi}_{\pi_{k,1}(\theta\|b)}\rVert$

where $\\{\pi_{k,\alpha}\\}_{k\in\llbracket 1,N\rrbracket,\alpha\in\bin}$ is a
mutually orthogonal family of permutations to be defined later in the proof.
We want the maximum in the equation above to be as small as possible. The goal
of step 3 is to find such a family.

  3. 3.

In the third step, we show that, as long as $b^{\prime}\neq b$, the quantity
$\lVert\mathrm{\Pi}_{\theta,b}\
\mathrm{\Pi}_{\theta^{\prime},b^{\prime}}\rVert$ depends on the number of
indices on which $\theta$ and $\theta_{i}$ differ. More precisely,
$\lVert\mathrm{\Pi}_{\theta,b}\
\mathrm{\Pi}_{\theta^{\prime},b^{\prime}}\rVert$ is upper-bounded by
$2^{-d(\theta)/4}$, where $d(\theta)$ is the number of such indices. Thus, we
choose our family of permutations such that, for all $k$, the last bit of
$\pi_{k,1}(\theta,b)$ is $1-b$ and $d(\theta)$ is constant. We build upon a
result of [CV22] to construct a family of permutations with the aforementioned
properties. More concretely, [CV22] define a mutually orthogonal family of
permutations $\pi_{k}$, indexed by $1\geq k\geq N$, with the latter property.
We then define another family $\widetilde{\pi}_{k,b}$, indexed by $1\geq k\geq
N$ and $b\in\bin$, where
$\widetilde{\pi}_{k,b}(\theta,b)=\pi_{k}(\theta)\|1-b$. It is easy to see that
this new family of permutations has both the former and the latter properties,
and we prove that it is also a mutually orthogonal family.

## Acknowledgements

This work was supported in part by the French ANR projects CryptiQ
(ANR-18-CE39-0015) and SecNISQ (ANR-21-CE47-0014).

##  2 Preliminaries

###  2.1 Notations

Throughout this paper, $\secpar$ denotes the security parameter. The notation
$\negl$ denotes any function $f$ such that $f(\lambda)=\lambda^{-\omega(1)}$,
and $\poly$ denotes any function $f$ such that
$f(\lambda)=\mathcal{O}(\lambda^{c})$ for some $c>0$. When sampling uniformly
at random a value $a$ from a set $\mathcal{U}$, we employ the notation
$a\sample\mathcal{U}$. When sampling a value $a$ from a probabilistic
algorithm $\adv$, we employ the notation $a\leftarrow\adv$. By $\ppt$ we mean
a polynomial-time non-uniform family of probabilistic circuits, and by QPT we
mean a polynomial-time family of quantum circuits.

###  2.2 Coset States

Given a subspace $A\subset\FF_{2}^{n}$ of dimension $n/2$ and a pair of
vectors $(s,s^{\prime})\in\FF_{2}^{n}$, the coset state
$\ket{A_{s,s^{\prime}}}$ is defined as

$\ket{A_{s,s^{\prime}}}:=\frac{1}{\sqrt{2^{n/2}}}\sum_{a\in A}(-1)^{a\cdot
s^{\prime}}\ket{a+s}$

where $a\cdot s^{\prime}$ denotes the inner product between $a$ and
$s^{\prime}$.

In particular, a coset state is such that $\mathsf{H}^{\otimes
n}\ket{A_{s,s^{\prime}}}=\ket{A^{\perp}_{s^{\prime},s}}$, where $A^{\perp}$ is
the complement of $A$, i.e. $A^{\perp}:=\\{u\in\FF_{2}^{n}\ |\ u\cdot v=0\
\forall v\in A\\}$.

#### Canonical representation.

As the canonical representation of a coset $A+s$, we use the lexicographically
smallest vector of the the coset; and for $u\in\FF_{2}^{n}$, we note
$\mathsf{Can}_{A}(u)$ the function that returns the canonical representation
(also noted coset representative) of $A+u$. We note that if $u\in A+s$, then
$\mathsf{Can}_{A}(u)=\mathsf{Can}_{A}(s)$. Also, the function
$\mathsf{Can}_{A}(\cdot)$ is efficiently computable given a description of
$A$.

###  2.3 Indistinguishable Obfuscation

######  Definition 1 (Indistinguishability Obfuscator [BGI+01]).

A uniform machine $\iO$ is called an indistinguishability obfuscator for a
classical circuit class $\\{\mathcal{C}_{\secpar}\\}$ if the following
conditions are satisfied:

  * •

For all security parameters $\secpar\in\NN$, for all
$C\in\mathcal{C}_{\secpar}$, for all input $x$, we have that

$\prob{C^{\prime}(x)=C(x)\mid C^{\prime}\leftarrow\iO(\secpar,C)}=1.$

  * •

For any (not necessarily uniform) distinguisher $\mathcal{D}$, for all
security parameters $\secpar\in\NN$, for all pairs of circuits
$C_{0},C_{1}\in\mathcal{C}_{\secpar}$, we have that if $C_{0}(x)=C_{1}(x)$ for
all inputs $x$, then

$\adv^{\iO}(\secpar,\adv)\coloneqq\lvert\prob{\mathcal{D}(\iO(\secpar,C_{0}))=1}-\prob{\mathcal{D}(\iO(\secpar,C_{1}))=1}\rvert\leq\negl.$

We further say that $\iO$ is $\delta$-secure, for some concrete negligible
function $\delta(\secpar)$, if for all QPT adversaries $\adv$, the advantage
$\adv^{\iO}(\secpar,\adv)$ is smaller than $\delta(\secpar)^{\Omega(1)}$.

###  2.4 Compute-and-Compare Obfuscation

This subsection is taken verbatim from [CHV23].

######  Definition 2 (Compute-and-Compare Programs).

Given a function $f:\bin^{\ell_{\mathsf{in}}}\to\bin^{\ell_{\mathsf{out}}}$
along with a target value $y\in\bin^{\ell_{\mathsf{out}}}$ and a message
$m\in\bin^{\ell_{\mathsf{msg}}}$, we define the compute-and-compare program:

$\displaystyle\mathsf{CC}[f,y,m](x)\coloneqq\begin{cases}m&\text{ if
}f(x)=y,\\\ \bot&\text{ otherwise }.\end{cases}$

######  Definition 3 (Unpredictable Distribution).

Let $\mathcal{D}\coloneqq\\{\mathcal{D}_{\secpar}\\}_{\secpar\in\NN}$ be a
distribution over pairs of the form $(\mathsf{CC}[f,y,m],\mathsf{aux})$ where
$\mathsf{CC}[f,y,m]$ is a compute-and-compare program and $\mathsf{aux}$ is
some (possibly quantum) auxiliary information. We say that $\mathcal{D}$ is an
_unpredictable distribution_ if for all QPT algorithm $\adv$, we have that

$\probsublong{(\mathsf{CC}[f,y,m],\mathsf{aux})\leftarrow\mathcal{D}_{\secpar}}{\adv(\secparam,f,\mathsf{aux})=y}\leq\negl.$

######  Definition 4 (Compute-and-Compare Obfuscator).

A $\ppt$ algorithm $\mathsf{CC\text{-}Obf}$ is said to be a compute-and-
compare obfuscator for a family of unpredictable distributions
$\mathcal{D}\coloneqq\\{\mathcal{D}_{\secpar}\\}$ if for all $\secpar\in\NN$:

  * •

$\mathsf{CC\text{-}Obf}$ is functionality preserving: for all $x$

$\prob{\mathsf{CC\text{-}Obf}(\secparam,\mathsf{CC}[f,y,m])(x)=\mathsf{CC}[f,y,m](x)}\geq
1-\negl$

  * •

$\mathsf{CC\text{-}Obf}$ has distributional indistinguishability: there exists
a QPT simulator $\mathcal{S}$ such that

$\left\\{\mathsf{CC\text{-}Obf}(\secparam,C),\mathsf{aux}\right\\}\approx_{c}\left\\{\mathcal{S}(\secparam,C.\mathsf{param}),\mathsf{aux}\right\\},$

where $(C,\mathsf{aux})\leftarrow\mathcal{D}_{\secpar}$.

###  2.5 Pseudorandom functions

This subsection is adapted from [CHV23, CLLZ21]. A pseudorandom function
[GGM84] consists of a keyed function $\prf$ and a set of keys $\mathcal{K}$
such that for a randomly chosen key $\key\in\mathcal{K}$, the output of the
function $\prf(\key,x)$ for any input $x$ in the input space $\mathcal{X}$
“looks” random to a QPT adversary, even when given a polynomially many
evaluations of $\prf(\key,\cdot)$. Puncturable pseudorandom functions have an
additional property that some keys can be generated _punctured_ at some point,
so that they allow to evaluate the pseudorandom function at all points except
for the punctured points. Furthermore, even with the punctured key, the
pseudorandom function evaluation at a punctured point still looks random.

Punctured pseudorandom functions are originally introduced in [BW13, BGI14,
KPTZ13], who observed that it is possible to construct such puncturable
pseudorandom functions for the construction from [GGM84], which can be based
on any one-way function [HILL99].

######  Definition 5 (Puncturable Pseudorandom Function).

A pseudorandom function $\prf:\mathcal{K}\times\mathcal{X}\to\mathcal{Y}$ is a
_puncturable pseudorandom function_ if there is an addition key space
$\mathcal{K}_{p}$ and three algorithms
$\prf=\langle\mathsf{KeyGen},\puncture,\eval\rangle$ such that:

  * •

$\key\leftarrow\mathsf{KeyGen}(1^{\secpar})$. The key generation algorithm
$\mathsf{KeyGen}$ takes the security parameter $1^{\secpar}$ as input and
outputs a random key $\key\in\mathcal{K}$.

  * •

$\key\\{x\\}\leftarrow\puncture(\key,x)$. The puncturing algorithm $\puncture$
takes as input a pseudorandom function key $\key\in\mathcal{K}$ and
$x\in\mathcal{X}$, and outputs a key $\key\\{x\\}\in\mathcal{K}_{p}$.

  * •

$y\leftarrow\eval(\key\\{x\\},x^{\prime})$. The evaluation algorithm takes as
input a punctured key $\key\\{x\\}\in\mathcal{K}_{p}$ and
$x^{\prime}\in\mathcal{X}$, and outputs a classical string $y\in\mathcal{Y}$.

We require the following properties of $\prf$.

  * •

Functionality preserved under puncturing. For all $\secpar\in\NN$, for all
$x\in\mathcal{X}$,

$\textnormal{Pr}\left[\forall
x^{\prime}\in\mathcal{X}\setminus\\{x\\}:\eval(\key\\{x\\},x^{\prime})=\eval(\key,x^{\prime})\
\middle|\begin{array}[]{r}\key\sample\mathsf{KeyGen}(1^{\secpar})\\\
\key\\{x\\}\sample\puncture(\key,x)\end{array}\right]=1.$

  * •

Pseudorandom at punctured points. For every QPT adversary
$\adv\coloneqq(\adv_{1},\adv_{2})$, and every $\secpar\in\NN$, the following
holds:

$\displaystyle\left\lvert\textnormal{Pr}\left[\begin{array}[]{c}1\leftarrow\adv_{2}(\key\\{x^{*}\\},y,\tau)\end{array}\
\middle|\begin{array}[]{r}(x^{*},\tau)\leftarrow\adv_{1}(1^{\secpar},\tau)\\\
\key\sample\mathsf{KeyGen}(1^{\secpar})\\\
\key\\{x^{*}\\}\sample\puncture(\key,x^{*})\\\
y\leftarrow\eval(\key,x^{*})\end{array}\right]\right.$
$\displaystyle\left.\quad-\textnormal{Pr}\left[\begin{array}[]{c}1\leftarrow\adv_{2}(\key\\{x^{*}\\},y,\tau)\end{array}\
\middle|\begin{array}[]{r}(x^{*},\tau)\leftarrow\adv_{1}(1^{\secpar},\tau)\\\
\key\sample\mathsf{KeyGen}(1^{\secpar})\\\
\key\\{x^{*}\\}\sample\puncture(\key,x^{*})\\\
y\sample\mathcal{Y}\end{array}\right]\right\rvert\leq\negl,$

where the probability is taken over the randomness of $\mathsf{KeyGen}$,
$\puncture$, and $\adv_{1}$.

Denote the above probability as $\adv^{\prf}(\secpar,\adv)$. We further say
that $\prf$ is $\delta$-secure, for some concrete negligible function
$\delta(\secpar)$, if for all QPT adversaries $\adv$, the advantage
$\adv^{\prf}(\secpar,\adv)$ is smaller than $\delta(\secpar)^{\Omega(1)}$.

######  Definition 6 (Statistically injective pseudorandom function).

A family of statistically injective (puncturable) pseudorandom functions with
(negligible) failure probability $\varepsilon(\cdot)$ is a (puncturable)
pseudorandom functions family $\prf$ such that with probability
$1-\varepsilon(\secpar)$ over the random choice of key
$\key\leftarrow\mathsf{KeyGen}(1^{\secpar})$, we have that $\prf(\key,\cdot)$
is injective.

######  Definition 7 (Extracting pseudorandom function).

A family of extracting (puncturable) pseudorandom functions with error
$\varepsilon(\cdot)$ for min-entropy $k(\cdot)$ is a (puncturable)
pseudorandom functions family $\prf$ mapping $n(\secpar)$ bits to $m(\secpar)$
bits such that for all $\secpar\in\NN$, if $X$ is any distribution over
$n(\secpar)$ bits with min-entropy greater than $k(\secpar)$, then the
statistical distance between $(\key,\prf(\key,X))$ and
$(\key,r\leftarrow\bin^{m(\secpar)})$ is at most $\varepsilon(\cdot)$, where
$\key\leftarrow\mathsf{KeyGen}(1^{\secpar})$.

##  3 A New Monogamy-of-Entanglement Game for Coset States

In this section, we present a new monogamy-of-entanglement game for coset
states and prove an upper-bound on the probability of winning this game. Along
the way, we present a BB84 version of this game with the same upper-bound.

###  3.1 The Coset Version

######  Definition 8 (Monogamy-of-Entanglement Game with Identical Basis
(Coset Version)).

This game is between a challenger and a triple of adversaries
$(\adv_{0},\adv_{1},\adv_{2})$ \- where $\adv_{1}$ and $\adv_{2}$ are not
communicating, and is parametrized by a security parameter $\secpar$.

  * •

The challenger samples a subspace
$A\leftarrow\bin^{\secpar\times\frac{\secpar}{2}}$ and two vectors
$(s,s^{\prime})\leftarrow\FF_{2}^{n}\times\FF_{2}^{n}$. Then the challenger
prepares the coset state $\ket{A_{s,s^{\prime}}}$ and sends
$\ket{A_{s,s^{\prime}}}$ to $\adv_{0}$.

  * •

$\adv_{0}$ prepares a bipartite quantum state $\sigma_{12}$, then sends
$\sigma_{1}$ to $\adv_{1}$ and $\sigma_{2}$ to $\adv_{2}$.

  * •

The challenger samples $b\leftarrow\bin$, then sends $(A,b)$ to both
$\adv_{1}$ and $\adv_{2}$.

  * •

$\adv_{1}$ returns $u_{1}$ and $\adv_{2}$ returns $u_{2}$.

For $i\in\\{1,2\\}$, we say that $\adv_{i}$ makes a correct guess if $(b=0\
\land\ u^{\prime}_{i}\in A+s)$ or if $(b=1\ \land\ u^{\prime}_{i}\in
A^{\perp}+s^{\prime})$. We say that $(\adv_{0},\adv_{1},\adv_{2})$ win the
game if both $\adv_{1}$ and $\adv_{2}$ makes a correct guess. For any triple
of adversaries $(\adv_{0},\adv_{1},\adv_{2})$ and any security parameter
$\secpar\in\NN$ for this game, we note
$\mathsf{MoE}^{\secpar}_{coset}(\adv_{0},\adv_{1},\adv_{2})$ the random
variable indicating whether $(\adv_{0},\adv_{1},\adv_{2})$ win the game or
not.

We note that there is a trivial way for a triple of adversaries to win this
game with probability $1/2$, by applying the following strategy. $\adv_{0}$
samples a random bit $b^{*}$. $\adv_{0}$ measures $\ket{A_{s,s^{\prime}}}$ in
the computational basis if $b^{*}=0$, or in the Hadamard basis if $b^{*}=1$.
In both cases, $\adv_{0}$ sends the outcome $u$ to both $\adv_{1}$ and
$\adv_{2}$. Regardless of the value of $A$ and $b$, $\adv_{1}$ and $\adv_{2}$
both return $u$. Because when $b^{*}=b$ (which happens with probability
$1/2$), the outcome of the measurement is a vector of the expected coset
space, the adversaries win the game with probability $1/2$. In the rest of
this section we prove that no triple of adversaries can actually win the game
with a probability significantly greater than $1/2$.

######  Theorem 3.1.

There exists a negligible function $\negl[\cdot]$ such that, for any triple of
algorithms $(\adv_{0},\adv_{1},\adv_{2})$ and any security parameter
$\secpar\in\NN$,
$\prob{\mathsf{MoE}^{\secpar}_{coset}(\adv_{0},\adv_{1},\adv_{2})=1}\leq
1/2+\negl$.

The proof of this theorem is given in subsequent sections.

###  3.2 The BB84 Version

We introduce below the BB84 version of this game. We show in the following
that it is sufficient to study the BB84 version (which is simpler) to prove
Theorem 3.1, as any triple of adversaries for the BB84 version can be turned
into a triple of adversaries for the coset version without changing the
probability of winning.

#### Notations.

Through all Section 3.2 and Section 3.3, we use the following notations. Let
$n\in\NN$, we note $\mathrm{\Theta}_{n}:=\\{\theta\in\bin^{n}\ :\
\lvert\theta\rvert=n/2\\}$ \- where $\lvert\cdot\rvert$ denotes the Hamming
weight - and $N:={n\choose n/2}$. Thus $\mathrm{\Theta}_{\secpar}$ has exactly
$N$ elements.

######  Definition 9 (Monogamy-of-Entanglement Game with Identical Basis (BB84
Version)).

This game is between a challenger and a triple of adversaries
$(\adv_{0},\adv_{1},\adv_{2})$ \- where $\adv_{1}$ and $\adv_{2}$ are non-
communicating, and is parametrized by a security parameter $\secpar$.

  * •

The challenger samples $x\leftarrow\bin^{\secpar}$ and
$\theta\leftarrow\mathrm{\Theta}_{\secpar}$. Then the challenger prepares the
state $\ket{x^{\theta}}:=\bigotimes\limits_{i\in\llbracket
1,\secpar\rrbracket}\mathsf{H}^{\theta_{i}}\ket{x_{i}}$ and sends
$\ket{x^{\theta}}$ to $\adv_{0}$.

  * •

$\adv_{0}$ prepares a bipartite quantum state $\sigma_{12}$, then sends
$\sigma_{1}$ to $\adv_{1}$ and $\sigma_{2}$ to $\adv_{2}$.

  * •

The challenger samples $b\leftarrow\bin$, then sends $(\theta,b)$ to both
$\adv_{1}$ and $\adv_{2}$.

  * •

$\adv_{1}$ returns $x_{1}$ and $\adv_{2}$ returns $x_{2}$.

Let $x_{T_{b}}:=\\{x_{i}\ |\ \theta_{i}=b\\}$. We say that
$(\adv_{0},\adv_{1},\adv_{2})$ win the game if $x_{1}=x_{2}=x_{T_{b}}$. For
any triple of adversaries $(\adv_{0},\adv_{1},\adv_{2})$ and any security
parameter $\secpar\in\NN$ for this game, we note
$\mathsf{MoE}^{\secpar}_{BB84}(\adv_{0},\adv_{1},\adv_{2})$ the random
variable indicating whether $(\adv_{0},\adv_{1},\adv_{2})$ win the game or
not.

We note that the trivial strategy for the coset version can be easily adapted
for the BB84 one. Hence the greatest probability of winning this game is also
lower bounded by $1/2$.

######  Theorem 3.2.

There exists a negligible function $\negl[\cdot]$ such that, for any triple of
algorithms $(\adv_{0},\adv_{1},\adv_{2})$ and any security parameter
$\secpar\in\NN$,
$\prob{\mathsf{MoE}^{\secpar}_{BB84}(\adv_{0},\adv_{1},\adv_{2})=1}\leq
1/2+\negl$.

Proof of Theorem 3.1 follows similarly as that of [CV22], in which the winning
probability of cloning adversaries in the monogamy-of-entanglement game of
coset states reduces to the winning probability of the adversaries in the game
of BB84 states. We thus provide the proof of Theorem 3.2 below.

###  3.3 Proof of Theorem 3.2

This proof follows the same structure as [CV22]. We can separate the proof in
four main steps.

  1. 1.

In the first step, we define the _extended non-local game_ [JMRW16] associated
the monogamy-of-entanglement game (BB84 version), and show that the greatest
winning probability of the monogamy game is the same as the one of this
extended non-local game. This step allows us to use a technique from [TFKW13]
to bound the winning probability.

  2. 2.

In the second step, we express any strategy for this extended non-local game
with security parameter $n\in\NN$ as a tripartite quantum state $\rho_{012}$
as well as two families of projective measurements, $\\{B^{\theta,b}\\}$ and
$\\{C^{\theta,b}\\}$, both indexed by $\theta\in\mathrm{\Theta}_{n}$ and
$b\in\bin$. We define the projector
$\mathrm{\Pi}_{\theta,b}=\sum_{x\in\bin^{n}}{|x\rangle\\!\langle
x|}^{\theta}\otimes B^{\theta,b}_{x_{T_{b}}}\otimes C^{\theta,b}_{x_{T_{b}}}$
such that the winning probability of this strategy is
$p_{win}=\mathop{\expectationname}_{\theta,b}\left[\mathsf{Tr}\left(\mathrm{\Pi}_{\theta,b}\
\rho_{012}\right)\right]$. Then, we show the following upper-bound:

$\displaystyle p_{win}$
$\displaystyle\leq\frac{1}{2N}\sum_{\begin{subarray}{c}1\leq k\leq N\\\
\alpha\in\bin\end{subarray}}\
\max_{\theta,b}\big{\lVert}\mathrm{\Pi}_{\theta,b}\mathrm{\Pi}_{\pi_{k,\alpha}(\theta\|b)}\rVert$
$\displaystyle=\frac{1}{2}+\frac{1}{2N}\sum_{1\leq k\leq N}\
\max_{\theta,b}\big{\lVert}\mathrm{\Pi}_{\theta,b}\mathrm{\Pi}_{\pi_{k,1}(\theta\|b)}\rVert$

where $\\{\pi_{k,\alpha}\\}_{k\in\llbracket 1,N\rrbracket,\alpha\in\bin}$ is a
family of permutations to be defined later in the proof.

  3. 3.

In the third step, we show that the quantity $\lVert\mathrm{\Pi}_{\theta,b}\
\mathrm{\Pi}_{\theta^{\prime},b^{\prime}}\rVert$ is upper-bounded by a small
quantity as long as $b^{\prime}\neq b$.

  4. 4.

Finally, in the fourth step, we show that there exists a family of
permutations such that, when $\alpha=0$,
$\pi_{k,\alpha}(\theta,b)=(\theta^{\prime},b^{\prime})$ for some
$\theta^{\prime}$ and $b^{\prime}\neq b$, and conclude the proof.

#### Step 1: extended non-local game.

We define the following extended non-local game, and show that any triple of
adversaries that win the monogamy-of-entanglement game with same basis (BB84
version) with probability $p$ can be turned into another triple of adversaries
that win this extended non-local game with the same probability $p$.

######  Definition 10 (Extended non-local game).

This game is between a challenger and two adversaries $\adv_{0}$ and
$\adv_{1}$, and is parametrized by a security parameter $\secpar$.

  * •

$\adv_{1}$ and $\adv_{2}$ jointly prepare a quantum state $\rho_{012}$ \-
where $\rho_{0}$ is a $\secpar$-qubits quantum state, then send $\rho_{0}$ to
the challenger. $\adv_{1}$ and $\adv_{2}$ keep $\rho_{1}$ and $\rho_{2}$
respectively. From this step $\adv_{1}$ and $\adv_{2}$ cannot communicate.

  * •

The challenger samples $\theta\leftarrow\mathrm{\Theta}_{n}$ and
$b\leftarrow\bin$. Then, for all $i\in\llbracket 1,\secpar\rrbracket$, the
challenger measures the $i^{\text{th}}$ qubit of $\rho_{0}$ in computational
basis if $\theta_{i}=0$ or in Hadamard basis if $\theta_{i}=1$. Let
$m\in\bin^{n}$ denote the measurement outcome. Finally, the challenger sends
$(\theta,b)$ to $\adv_{1}$ and $\adv_{2}$.

  * •

$\adv_{1}$ returns $m_{1}$ and $\adv_{2}$ returns $m_{2}$.

Let $m_{T_{b}}:=\\{m_{i}\ |\ \theta_{i}=b\\}$. We say that
$(\adv_{1},\adv_{2})$ win the game if $m_{1}=m_{2}=m_{T_{b}}$.

######  Lemma 1.

Let $n\in\NN$ and $(\adv_{0},\adv_{1},\adv_{2})$ a triple of adversaries for
the monogamy-of-entanglement game (Definition 9) parametrized by $n$, that win
with probability $p_{n}$. Then there exists a quantum state $\rho_{012}$ and a
pair of adversaries $(\adv^{\prime}_{1},\adv^{\prime}_{2})$ for the extended
non-local game (Definition 10) that win with the same probability $p_{n}$.

###### Proof.

Consider a triple of adversaries for the monogamy-of-entanglement game
(Definition 9), parametrized by $n\in\NN$, that win with probability $p_{n}$.
We can model these adversaries as a CPTP map
$\mathrm{\Phi}:\mathcal{H}_{0}\rightarrow\mathcal{H}_{1}\times\mathcal{H}_{2}$,
and POVMs families $\\{B^{\theta,b}\\}$ and $\\{C^{\theta,b}\\}$, both indexed
by $\theta\in\mathrm{\Theta}_{n}$ and $b\in\bin$. Then we have

$p_{n}=\mathop{\expectationname}_{\begin{subarray}{c}\theta\in\mathrm{\Theta}_{n}\\\
b\in\bin\end{subarray}}\mathop{\expectationname}_{x\in\bin^{n}}Tr\left[(B_{x_{T_{b}}}^{\theta,b}\otimes
C_{x_{T_{b}}}^{\theta,b})\mathrm{\Phi}({|x^{\theta}\rangle\\!\langle
x^{\theta}|})\right].$

The strategy for the extended non-local game is as follows. $\adv_{1}$ and
$\adv_{2}$ prepare the bipartite state $\rho_{00^{\prime}}=\bigotimes_{1\leq
i\leq n}{|\phi^{+}\rangle\\!\langle\phi^{+}|}$ where $\phi^{+}$ denotes the
EPR state $(\ket{00}+\ket{11})/\sqrt{2}$, and where $\rho_{0}$ (resp.
$\rho_{0^{\prime}}$) is composed of the first halves (resp. second halves) of
these EPR states. Then, they apply $\mathrm{\Phi}$ to $\rho_{0^{\prime}}$. Let
$\rho_{012}$ denotes the resulting state. They send $\rho_{0}$ to the
challenger, $\adv_{1}$ keeps $\rho_{1}$ and $\adv_{2}$ keeps $\rho_{2}$.
Later, when $\adv_{1}$ receives $(\theta,b)$, from the challenger, $\adv_{1}$
applies the POVM $B^{\theta,b}$ to $\rho_{1}$ and returns the outcome.
$\adv_{2}$ does the same with POVM $C^{\theta,b}$ and $\rho_{2}$. The
probability of winning of such strategy is then

$p^{\prime}_{n}=\mathop{\expectationname}_{\begin{subarray}{c}\theta\in\mathrm{\Theta}_{n}\\\
b\in\bin\end{subarray}}\sum_{x\in\bin^{n}}Tr\left[\left({|x^{\theta}\rangle\\!\langle
x^{\theta}|}\otimes B_{x_{T_{b}}}^{\theta,b}\otimes
C_{x_{T_{b}}}^{\theta,b}\right)\rho_{012}\right].$ (1)

We do the following calculation.

$\displaystyle Tr\left[\left({|x^{\theta}\rangle\\!\langle x^{\theta}|}\otimes
B_{x_{T_{b}}}^{\theta,b}\otimes
C_{x_{T_{b}}}^{\theta,b}\right)\rho_{012}\right]$
$\displaystyle=\frac{1}{2^{n}}\sum\limits_{r,r^{\prime}\in\bin^{n}}Tr\left[\left({|x^{\theta}\rangle\\!\langle
x^{\theta}|}\otimes B_{x_{T_{b}}}^{\theta,b}\otimes
C_{x_{T_{b}}}^{\theta,b}\right)\left({|r\rangle\\!\langle
r^{\prime}|}\otimes\mathrm{\Phi}\left({|r\rangle\\!\langle
r^{\prime}|}\right)\right)\right]$
$\displaystyle=\frac{1}{2^{n}}\sum\limits_{r,r^{\prime}\in\bin^{n}}\braket{r}{x^{\theta}}\braket{x^{\theta}}{r^{\prime}}Tr\left[\left(B_{x_{T_{b}}}^{\theta,b}\otimes
C_{x_{T_{b}}}^{\theta,b}\right)\mathrm{\Phi}\left({|r\rangle\\!\langle
r^{\prime}|}\right)\right]$
$\displaystyle=\frac{1}{2^{n}}\sum\limits_{r,r^{\prime}\in\bin^{n}}Tr\left[\left(B_{x_{T_{b}}}^{\theta,b}\otimes
C_{x_{T_{b}}}^{\theta,b}\right)\mathrm{\Phi}\left(\ket{r}\braket{r}{x^{\theta}}\braket{x^{\theta}}{r^{\prime}}\bra{r^{\prime}}\right)\right]$
$\displaystyle=\frac{1}{2^{n}}Tr\left[\left(B_{x_{T_{b}}}^{\theta,b}\otimes
C_{x_{T_{b}}}^{\theta,b}\right)\mathrm{\Phi}\left(\frac{1}{2^{n}}\sum\limits_{r\in\bin^{n}}{|r\rangle\\!\langle
r|}\ {|x^{\theta}\rangle\\!\langle
x^{\theta}|}\frac{1}{2^{n}}\sum\limits_{r^{\prime}\in\bin^{n}}{|r^{\prime}\rangle\\!\langle
r^{\prime}|}\right)\right]$
$\displaystyle=\frac{1}{2^{n}}Tr\left[\left(B_{x_{T_{b}}}^{\theta,b}\otimes
C_{x_{T_{b}}}^{\theta,b}\right)\mathrm{\Phi}\left({|x^{\theta}\rangle\\!\langle
x^{\theta}|}\right)\right]$

By plugging this result into Equation 1, we get $p^{\prime}_{n}=p_{n}$, which
concludes the proof.

∎

#### Step 2: first upper-bound of the winning probability.

We prove an upper-bound for the extended non-local game above. We need the
following lemma.

######  Lemma 2 (Lemma 2 of [TFKW13]).

Let $\mathrm{\Pi}_{1},\dots,\mathrm{\Pi}_{n}$ be projective positive semi-
definite operators on a Hilbert space, and $\\{\pi_{i}\\}_{i\in\llbracket
1,n\rrbracket}$ be a set of orthogonal permutations for some integer $n$. Then

$\Big{\lVert}\sum\limits_{i=1}^{n}\mathrm{\Pi}_{i}\Big{\rVert}\leq\sum\limits_{i=1}^{n}\max\limits_{j\in\llbracket
1,n\rrbracket}\big{\lVert}\mathrm{\Pi}_{j}\mathrm{\Pi}_{\pi_{i}(j)}\big{\rVert}$

Let
$\left(\\{B^{\theta,b}\\}_{\theta\in\mathrm{\Theta}_{n},b\in\bin},\\{C^{\theta,b}\\}_{\theta\in\mathrm{\Theta}_{n},b\in\bin},\rho_{012}\right)$
be a strategy for the extended non-local game. Using Naimark’s dilation
theorem, we can assume without loss of generality that the $B^{\theta,b}$ and
$C^{\theta,b}$ are all projective. Let $\mathrm{\Pi}_{\theta,b}$ be the
following projector:
$\mathrm{\Pi}_{\theta,b}:=\sum_{x\in\bin^{n}}{|x\rangle\\!\langle
x|}^{\theta}\otimes B^{\theta,b}_{x_{T_{b}}}\otimes C^{\theta,b}_{x_{T_{b}}}$.
Then the winning probability of this strategy is

$\displaystyle p_{win}$
$\displaystyle=\mathop{\expectationname}\limits_{\theta\in\mathrm{\Theta}_{n},b\in\bin}\mathsf{Tr}\left(\mathrm{\Pi}_{\theta,b}\
\rho_{012}\right)$
$\displaystyle\leq\mathop{\expectationname}\limits_{\theta\in\mathrm{\Theta}_{n},b\in\bin}\|\mathrm{\Pi}_{\theta,b}\|$
$\displaystyle\leq\frac{1}{2N}\sum_{\begin{subarray}{c}1\leq k\leq N\\\
\alpha\in\bin\end{subarray}}\
\max_{\theta,b}\big{\lVert}\mathrm{\Pi}_{\theta,b}\mathrm{\Pi}_{\pi_{k,\alpha}(\theta,b)}\rVert$
(2)

where the first inequality follows from the definition of the norm and the
second from Lemma 2; and where $\\{\pi_{k,\alpha}\\}_{k\in\llbracket
1,N\rrbracket,\alpha\in\bin}$ is a family of mutually orthogonal permutations.

#### Step 3: upper-bound of
$\lVert\mathrm{\Pi}_{\theta,b}\mathrm{\Pi}_{\theta^{\prime},1-b}\rVert$.

In this part, we show that for all
$(\theta,\theta^{\prime})\in\mathrm{\Theta}_{n}$ and all $b\in\bin$, we can
upper-bound
$\lVert\mathrm{\Pi}_{\theta,b}\mathrm{\Pi}_{\theta^{\prime},1-b}\rVert$ by a
small quantity.

Let $(\theta,\theta^{\prime})\in\mathrm{\Theta}_{n}^{2}$ and $b\in\bin$. Note
$R:=\\{i\in\llbracket 1,N\rrbracket\ :\ \theta_{i}\neq\theta^{\prime}_{i}\\}$,
$T:=\\{i\in\llbracket 1,N\rrbracket\ :\ \theta_{i}=b\\}$,
$T^{\prime}:=\\{i\in\llbracket 1,N\rrbracket\ :\ \theta^{\prime}_{i}=1-b\\}$
and $S:=\\{i\in R\ :\ \theta_{i}=b\text{ and }\theta^{\prime}_{i}=1-b\\}$. We
define $\bar{\mathrm{P}}$ and $\bar{\mathrm{Q}}$ as follows:

$\displaystyle\bar{\mathrm{P}}$
$\displaystyle:=\sum\limits_{x_{T}\in\bin^{T}}\mathsf{H}^{b}{|x_{S}\rangle\\!\langle
x_{S}|}\mathsf{H}^{b}\otimes\mathbb{I}_{\bar{S}}\otimes
B^{\theta,b}_{x_{T}}\otimes\mathbb{I}_{C}$ $\displaystyle\bar{\mathrm{Q}}$
$\displaystyle:=\sum\limits_{x_{T^{\prime}}\in\bin^{T^{\prime}}}\mathsf{H}^{1-b}{|x_{S}\rangle\\!\langle
x_{S}|}\mathsf{H}^{1-b}\otimes\mathbb{I}_{\bar{S}}\otimes
C^{\theta^{\prime},1-b}_{x_{T^{\prime}}}\otimes\mathbb{I}_{B}$

where ${|x_{S}\rangle\\!\langle x_{S}|}$ denotes the subsystem of
${|x_{T}\rangle\\!\langle x_{T}|}$ whose indices belong to $S$, and
$\mathbb{I}_{\bar{S}}$ denotes the rest of the system.

Remark that we have:

$\displaystyle\lVert\mathrm{\Pi}_{\theta,b}\mathrm{\Pi}_{\theta^{\prime},1-b}\rVert^{2}$
$\displaystyle=\lVert\mathrm{\Pi}_{\theta^{\prime},1-b}\mathrm{\Pi}_{\theta,b}\mathrm{\Pi}_{\theta^{\prime},1-b}\rVert$
$\displaystyle\leq\lVert\mathrm{\Pi}_{\theta^{\prime},1-b}\bar{\mathrm{P}}\mathrm{\Pi}_{\theta^{\prime},1-b}\rVert$
$\displaystyle=\lVert\bar{\mathrm{P}}\mathrm{\Pi}_{\theta^{\prime},1-b}\bar{\mathrm{P}}\rVert$
$\displaystyle\leq\bar{\mathrm{P}}\bar{\mathrm{Q}}\bar{\mathrm{P}}$

where we have the first line because $\mathrm{\Pi}_{\theta,b}$ is a
projection, the second because $\mathrm{\Pi}_{\theta,b}\leq\bar{\mathrm{P}}$,
the third because $\mathrm{\Pi}_{\theta,b}$ and $\bar{\mathrm{P}}$ are
projections and the last because
$\mathrm{\Pi}_{\theta^{\prime},1-b}\leq\bar{\mathrm{Q}}$.

Consider now the quantity $\bar{\mathrm{P}}\bar{\mathrm{Q}}\bar{\mathrm{P}}$.
We compute the following upper-bound for
$\bar{\mathrm{P}}\bar{\mathrm{Q}}\bar{\mathrm{P}}$:

$\displaystyle\bar{\mathrm{P}}\bar{\mathrm{Q}}\bar{\mathrm{P}}$
$\displaystyle=\sum\limits_{\begin{subarray}{c}x_{T},z_{T}\in\bin^{T}\\\
y_{T^{\prime}}\in\bin^{T^{\prime}}\end{subarray}}\mathsf{H}^{b}{|x_{S}\rangle\\!\langle
x_{S}|}\mathsf{H}^{b}\mathsf{H}^{1-b}{|y_{S}\rangle\\!\langle
y_{S}|}\mathsf{H}^{1-b}\mathsf{H}^{b}{|z_{S}\rangle\\!\langle
z_{S}|}\mathsf{H}^{b}\otimes\mathbb{I}_{\bar{S}}\otimes B^{\theta,b}_{x_{T}}\
B^{\theta,b}_{z_{T}}\otimes C^{\theta^{\prime},1-b}_{y_{T^{\prime}}}$
$\displaystyle=\sum\limits_{\begin{subarray}{c}x_{T}\in\bin^{T}\\\
y_{T^{\prime}}\in\bin^{T^{\prime}}\end{subarray}}\mathsf{H}^{b}{|x_{S}\rangle\\!\langle
x_{S}|}\mathsf{H}^{b}\mathsf{H}^{1-b}{|y_{S}\rangle\\!\langle
y_{S}|}\mathsf{H}^{1-b}\mathsf{H}^{b}{|x_{S}\rangle\\!\langle
x_{S}|}\mathsf{H}^{b}\otimes\mathbb{I}_{\bar{S}}\otimes
B^{\theta,b}_{x_{T}}\otimes C^{\theta^{\prime},1-b}_{y_{T^{\prime}}}$
$\displaystyle=2^{-\lvert
S\rvert}\sum\limits_{\begin{subarray}{c}x_{T}\in\bin^{T}\\\
y_{T^{\prime}}\in\bin^{T^{\prime}}\end{subarray}}\mathsf{H}^{b}{|x_{S}\rangle\\!\langle
x_{S}|}\mathsf{H}^{b}\otimes\mathbb{I}_{\bar{S}}\otimes
B^{\theta,b}_{x_{T}}\otimes C^{\theta^{\prime},1-b}_{y_{T^{\prime}}}$
$\displaystyle=2^{-\lvert
S\rvert}\sum\limits_{x_{T}\in\bin^{T}}\mathsf{H}^{b}{|x_{S}\rangle\\!\langle
x_{S}|}\mathsf{H}^{b}\otimes\mathbb{I}_{\bar{S}}\otimes
B^{\theta,b}_{x_{T}}\otimes\mathbb{I}_{C}$

where the first equality comes from $B^{\theta,b}_{x_{T}}\
B^{\theta,b}_{z_{T}}=B^{\theta,b}_{x_{T}}$ if $x_{T}=z_{T}$ and $0$ otherwise;
the second comes from
$\bra{x_{S}}\mathsf{H}^{b}\mathsf{H}^{1-b}{|y_{S}\rangle\\!\langle
y_{S}|}\mathsf{H}^{1-b}\mathsf{H}^{b}\ket{x_{S}}=\lvert\bra{x_{S}}\mathsf{H}\ket{y_{S}}\rvert^{2}=2^{-\lvert
S\rvert}$ for all $x_{T},y_{T^{\prime}}$ and the third from
$\sum_{y_{T^{\prime}}}C^{\theta^{\prime},1-b}_{y_{T^{\prime}}}=\mathbb{I}_{C}$.
Notice that we can assume without loss of generality that $\lvert S\rvert$ is
larger than $\lvert R\rvert/2$: if it is not the case, we just swap the roles
of $\theta$ and $\theta^{\prime}$. Thus, by linearity and from
$\sum_{x_{T}}B^{\theta,b}_{x_{T}}=\mathbb{I}_{B}$, it comes
$\lVert\bar{\mathrm{P}}\bar{\mathrm{Q}}\bar{\mathrm{P}}\rVert\leq 2^{-\lvert
S\rvert}\leq 2^{-\lvert R\rvert/2}$ hence

$\lVert\mathrm{\Pi}_{\theta,b}\mathrm{\Pi}_{\theta^{\prime},1-b}\rVert\leq
2^{-\lvert R\rvert/4}$ (3)

######  Remark 1.

Remark that, when considering
$\lVert\mathrm{\Pi}_{\theta,b}\mathrm{\Pi}_{\theta^{\prime},b}\rVert$ instead,
we have $S=\emptyset$. Thus, the reasoning above yields the trivial upper-
bound

$\lVert\mathrm{\Pi}_{\theta,b}\mathrm{\Pi}_{\theta^{\prime},b}\rVert\leq 1$
(4)

#### Step 4: finding the permutation family.

In this part, we construct a family of mutually orthogonal permutations
$\\{\pi_{k,\alpha}\\}_{k\in\llbracket 1,N\rrbracket,\alpha\in\bin}$ such for
all $k\in\llbracket 1,N\rrbracket$, $\pi_{k,0}$ “flips” the last input’s bit
and $\pi_{k,1}$ leaves it unchanged.

We use the following lemma, proven in [CV22].

######  Lemma 3 (Lemma 3.4 of [CV22]).

Let $n$ be an even integer, $\mathrm{\Theta}_{n}:=\\{\theta\in\bin^{n}\ :\
\lvert\theta\rvert=n/2\\}$ and $N={n\choose{n/2}}$. Then there is a family of
$N$ mutually orthogonal permutations $\\{\tilde{\pi}_{k}\\}_{k\in\llbracket
1,N\rrbracket}$ of $\mathrm{\Theta}_{n}$ such that the following holds. For
each $i\in\llbracket 1,n/2\rrbracket$, there are exactly ${n/2\choose i}^{2}$
permutations $\tilde{\pi}_{k}$ such that the number of positions at which
$\theta$ and $\tilde{\pi}_{k}(\theta)$ are both $1$ is $n/2-i$.

We prove the following corollary.

######  Corollary 1.

Let $n$ be an even integer, $\mathrm{\Theta}_{n}:=\\{\theta\in\bin^{n}\ :\
\lvert\theta\rvert=n/2\\}$ and $N={n\choose{n/2}}$. Then there is a family of
$2N$ mutually orthogonal permutations $\\{\pi_{k,\alpha}\\}_{k\in\llbracket
1,N\rrbracket,\alpha\in\bin}$ of $\mathrm{\Theta}_{n}\times\bin$ such that the
two following properties hold.

  * •

For each $i\in\llbracket 1,n/2\rrbracket$, there are exactly ${n/2\choose
i}^{2}$ permutations $\pi_{k,0}$ such that the number of positions at which
$\theta$ and $\theta^{\prime}$ are both $1$ is $n/2-i$ (i.e. $\theta$ and
$\theta^{\prime}$ differ in $2i$ positions).

  * •

If $\alpha=0$, then $b^{\prime}=1-b$. Otherwise, $b^{\prime}=b$.

where we use the notation
$(\theta^{\prime}\|b^{\prime}):=\pi_{k,\alpha}(\theta\|b)$.

###### Proof.

Let $\\{\tilde{\pi}_{k}\\}_{k\in\llbracket 1,N\rrbracket}$ be a family of
orthogonal permutations promised in Lemma 3. Define the family
$\\{\pi_{k,\alpha}\\}_{k\in\llbracket 1,N\rrbracket,\alpha\in\bin}$ as
follows. For all $k\in\llbracket 1,N\rrbracket$:

$\displaystyle\pi_{k,0}(\theta||b)$
$\displaystyle=\tilde{\pi}_{k}(\theta)||(1-b)$
$\displaystyle\pi_{k,1}(\theta||b)$ $\displaystyle=\tilde{\pi}_{k}(\theta)||b$

The two properties follow directly by construction. It remains to prove that
these $2N$ permutations are mutually orthogonal. Assume
$\pi_{k,\alpha}(\theta)=\pi_{k^{\prime},\alpha^{\prime}}(\theta)$. Then we
have $\alpha=\alpha^{\prime}$, and
$\tilde{\pi}_{k}(\theta)=\tilde{\pi}_{k^{\prime}}(\theta)$, hence
$k=k^{\prime}$ because $\\{\tilde{\pi}_{k}\\}_{k}$ is a family of orthogonal
permutations. ∎

#### Concluding the proof.

We make use of the following lemma from [CV22].

######  Lemma 4 (Lemma 3.6 of [CV22]).

Let $n\geq 2$ an integer, and note $N={n\choose n/2}$. Then we have

$\frac{1}{N}\sum_{i=0}^{n/2}{n/2\choose
i}^{2}2^{-i/2}\leq\sqrt{e}\left(\cos\frac{\pi}{8}\right)^{n}$

The rest of the proof follows easily. We first rewrite Equation 2 as

$p_{win}\leq\frac{1}{2N}\sum_{k=1}^{N}\
\max_{\theta,b}\big{\lVert}\mathrm{\Pi}_{\theta,b}\mathrm{\Pi}_{\pi_{k,1}(\theta,b)}\rVert+\frac{1}{2N}\sum_{k=1}^{N}\
\max_{\theta,b}\big{\lVert}\mathrm{\Pi}_{\theta,b}\mathrm{\Pi}_{\pi_{k,0}(\theta,b)}\rVert$

Then, by plugging the permutations family of Corollary 1, and using the upper-
bounds proved in Equation 3 and Equation 4, it comes

$\displaystyle p_{win}$
$\displaystyle\leq\frac{1}{2}+\frac{1}{2N}\sum_{i=1}^{n/2}2^{-i/2}$
$\displaystyle\leq\frac{1}{2}+\frac{\sqrt{e}}{2}\left(\cos\frac{\pi}{8}\right)^{n}.$

###  3.4 Computational Version

We provide below a computational version of the monogamy-of-entanglement with
identical basis. The only difference is that the adversaries are given access
to obfuscated membership programs for the coset space and its dual. This game
is still hard to win with probability significantly greater than $1/2$ if we
make the assumption that the adversaries are polynomially bounded. The proof
of this statement follows directly from the proof of hardness of the
computational version of the regular monogamy-of-entanglement game [CLLZ21].

######  Definition 11 (Computational Monogamy-of-Entanglement Game with
Identical Basis (Coset Version)).

This game is between a challenger and a triple of adversaries
$(\adv_{0},\adv_{1},\adv_{2})$ \- where $\adv_{1}$ and $\adv_{2}$ are not
communicating, and is parametrized by a security parameter $\secpar$.

  * •

The challenger samples a subspace
$A\leftarrow\bin^{\secpar\times\frac{\secpar}{2}}$ and two vectors
$(s,s^{\prime})\leftarrow\FF_{2}^{n}\times\FF_{2}^{n}$. Then the challenger
prepares the coset state $\ket{A_{s,s^{\prime}}}$ as well as two obfuscated
membership programs $\widehat{\mathsf{P}}_{A+s}:=\iO(A+s)$ and
$\widehat{\mathsf{P}}_{A^{\perp}+s^{\prime}}:=\iO(A^{\perp}+s^{\prime})$ and
sends
$\left(\ket{A_{s,s^{\prime}}},\widehat{\mathsf{P}}_{A+s},\widehat{\mathsf{P}}_{A^{\perp}+s^{\prime}}\right)$
to $\adv_{0}$.

  * •

$\adv_{0}$ prepares a bipartite quantum state $\sigma_{12}$, then sends
$\sigma_{1}$ to $\adv_{1}$ and $\sigma_{2}$ to $\adv_{2}$.

  * •

The challenger samples $b\leftarrow\bin$, then sends $(A,b)$ to both
$\adv_{1}$ and $\adv_{2}$.

  * •

$\adv_{1}$ returns $u_{1}$ and $\adv_{2}$ returns $u_{2}$.

For $i\in\\{1,2\\}$, we say that $\adv_{i}$ makes a correct guess if $(b=0\
\land\ u^{\prime}_{i}\in A+s)$ or if $(b=1\ \land\ u^{\prime}_{i}\in
A^{\perp}+s^{\prime})$. We say that $(\adv_{0},\adv_{1},\adv_{2})$ win the
game if both $\adv_{1}$ and $\adv_{2}$ makes a correct guess. For any triple
of adversaries $(\adv_{0},\adv_{1},\adv_{2})$ and any security parameter
$\secpar\in\NN$ for this game, we note
$\mathsf{MoE}^{\secpar}_{coset(comp)}(\adv_{0},\adv_{1},\adv_{2})$ the random
variable indicating whether $(\adv_{0},\adv_{1},\adv_{2})$ win the game or
not.

######  Theorem 3.3.

There exists a negligible function $\negl[\cdot]$ such that, for any triple of
QPT algorithms $(\adv_{0},\adv_{1},\adv_{2})$ and any security parameter
$\secpar\in\NN$,
$\prob{\mathsf{MoE}^{\secpar}_{coset(comp)}(\adv_{0},\adv_{1},\adv_{2})=1}\leq
1/2+\negl$.

###  3.5 Parallel Repetition of the Game

For our proof of anti-piracy of copy-protection, we actually need a parallel
version of this game, where the challenger samples $\kappa\in\NN$ independent
cosets and an independent basis choice for each coset; and the adversaries are
suppose to return a vector in the correct space for all the cosets to win the
game. We show that the winning probability of this game is negligible.

######  Definition 12 ($\kappa$-Parallel Computational Monogamy-of-
Entanglement Game with Identical Basis (Coset Version)).

This game is between a challenger and a triple of adversaries
$(\adv_{0},\adv_{1},\adv_{2})$ \- where $\adv_{1}$ and $\adv_{2}$ are not
communicating, and is parametrized by a security parameter $\secpar$.

  * •

The challenger samples $\kappa$ subspaces $\\{A_{i}\\}_{i\in\llbracket
1,\kappa\rrbracket}$ and $\kappa$ pairs of vectors
$\\{(s_{i},s^{\prime}_{i})\\}_{i\in\llbracket 1,\kappa\rrbracket}$ where
$A_{i}\leftarrow\bin^{\secpar\times\frac{\secpar}{2}}$ and
$(s_{i},s^{\prime}_{i})\leftarrow\FF_{2}^{n}\times\FF_{2}^{n}$ for all
$i\in\llbracket 1,\kappa\rrbracket$. Then the challenger prepares the coset
states $\\{\ket{A_{i,s_{i},s^{\prime}_{i}}}\\}_{i\in\llbracket
1,\kappa\rrbracket}$ as well as the associated obfuscated membership programs
$\widehat{\mathsf{P}}_{A_{i}+s_{i}}:=\iO(A_{i}+s_{i})$ and
$\widehat{\mathsf{P}}_{A^{\perp}_{i}+s^{\prime}_{i}}:=\iO(A^{\perp}_{i}+s^{\prime}_{i})$
for $i\in\llbracket 1,\kappa\rrbracket$; and sends
$\left(\\{\ket{A_{i,s_{i},s^{\prime}_{i}}}\\}_{i\in\llbracket
1,\kappa\rrbracket},\\{\widehat{\mathsf{P}}_{A_{i}+s_{i}},\widehat{\mathsf{P}}_{A^{\perp}_{i}+s^{\prime}_{i}}\\}_{i\in\llbracket
1,\kappa\rrbracket}\right)$ to $\adv_{0}$.

  * •

$\adv_{0}$ prepares a bipartite quantum state $\sigma_{12}$, then sends
$\sigma_{1}$ to $\adv_{1}$ and $\sigma_{2}$ to $\adv_{2}$.

  * •

The challenger samples $r\leftarrow\bin^{\kappa}$, then sends
$\\{A_{i}\\}_{i\in\llbracket 1,\kappa\rrbracket}$ and $r$ to both $\adv_{1}$
and $\adv_{2}$.

  * •

$\adv_{1}$ returns $\kappa$ vectors $\\{u_{i}\\}_{i\in\llbracket
1,\kappa\rrbracket}$ and $\adv_{2}$ returns $\kappa$ vectors
$\\{u^{\prime}_{i}\\}_{i\in\llbracket 1,\kappa\rrbracket}$.

We say that $\adv_{1}$ makes a correct guess if $(r_{i}=0\ \land\ u_{i}\in
A_{i}+s_{i})$ or if $(r_{i}=1\ \land\ u_{i}\in A^{\perp}_{i}+s^{\prime}_{i})$
for all $i\in\llbracket 1,\kappa\rrbracket$. Similarly, we say that $\adv_{2}$
makes a correct guess if $(r_{i}=0\ \land\ u^{\prime}_{i}\in A_{i}+s_{i})$ or
if $(r_{i}=1\ \land\ u^{\prime}_{i}\in A^{\perp}_{i}+s^{\prime}_{i})$ for all
$i\in\llbracket 1,\kappa\rrbracket$. We say that
$(\adv_{0},\adv_{1},\adv_{2})$ win the game if both $\adv_{1}$ and $\adv_{2}$
makes a correct guess. For any triple of adversaries
$(\adv_{0},\adv_{1},\adv_{2})$ and any security parameter $\secpar\in\NN$ for
this game, we note
$\kappa-\mathsf{MoE}^{\secpar}_{coset(comp)}(\adv_{0},\adv_{1},\adv_{2})$ the
random variable indicating whether $(\adv_{0},\adv_{1},\adv_{2})$ win the game
or not.

######  Theorem 3.4.

There exists a negligible function $\negl[\cdot]$ such that, for any triple of
QPT algorithms $(\adv_{0},\adv_{1},\adv_{2})$ and any security parameter
$\secpar\in\NN$,
$\prob{\kappa-\mathsf{MoE}^{\secpar}_{coset(comp)}(\adv_{0},\adv_{1},\adv_{2})=1}\leq\negl$.

###  3.6 Proof of Parallel Version of the Monogamy Game

In this subsection, we prove Theorem 3.4. We do it by proving that a parallel
version of the BB84 version of the monogamy game has negligible security, as
the coset version follows as for the single instance. As the proof follows the
same structure as the one of Theorem 3.2, we only describe here the important
steps of the proof.

#### Step 1: extended non-local game.

We first describe the extended non-local game for this parallel version of the
game. This game is between a challenger and two adversaries $\adv_{0}$ and
$\adv_{1}$, and is parametrized by a security parameter $\secpar$ and a number
of repetitions $\kappa:=\poly$.

  * •

$\adv_{1}$ and $\adv_{2}$ jointly prepare a quantum state $\rho_{012}$ \-
where $\rho_{0}$ is composed of $\kappa$ $\secpar$-qubits registers, denoted
as $\rho^{1}_{0},\dots,\rho^{\kappa}_{0}$ \- then send $\rho_{0}$ to the
challenger. $\adv_{1}$ and $\adv_{2}$ keep $\rho_{1}$ and $\rho_{2}$
respectively. From this step $\adv_{1}$ and $\adv_{2}$ cannot communicate.

  * •

For $j\in\llbracket 1,\kappa\rrbracket$, the challenger samples
$\theta^{j}\leftarrow\mathrm{\Theta}_{n}$, then the challenger samples
$r\leftarrow\bin^{\kappa}$. Then, for all $i\in\llbracket 1,\secpar\rrbracket$
and $j\in\llbracket 1,\kappa\rrbracket$, the challenger measures the
$i^{\text{th}}$ qubit of $\rho^{j}_{0}$ in computational basis if
$\theta^{j}_{i}=0$ or in Hadamard basis if $\theta^{j}_{i}=1$. Let
$m^{j}\in\bin^{n}$ denote the measurement outcome for every $j$. Finally, the
challenger sends $\theta:=(\theta^{1},\dots,\theta^{\kappa})$ and $r$ to
$\adv_{1}$ and $\adv_{2}$.

  * •

$\adv_{1}$ returns $\\{m^{j}_{1}\\}_{j\in\llbracket 1,\kappa\rrbracket}$ and
$\adv_{2}$ returns $\\{m^{j}_{2}\\}_{j\in\llbracket 1,\kappa\rrbracket}$.

Let $m^{j}_{T_{r_{j}}}:=\\{m^{j}_{i}\ |\ \theta^{j}_{i}=r_{j}\\}$. We say that
$(\adv_{1},\adv_{2})$ win the game if $m^{j}_{1}=m^{j}_{2}=m_{T_{r_{j}}}$ for
all $j\in\llbracket 1,\kappa\rrbracket$.

#### Step 2: first upper-bound.

Let $\theta=(\theta^{1},...,\theta^{\kappa})$, we define
$\mathrm{\Pi}_{\theta,r}:=\bigotimes\limits_{j=1}^{\kappa}\sum_{x\in\bin^{n}}{|x\rangle\\!\langle
x|}^{\theta^{j}}\otimes B^{\theta,r}_{x_{T_{r}}}\otimes
C^{\theta,r}_{x_{T_{r}}}$. We then prove in the same way as in Theorem 3.2
that

$p_{win}\leq\frac{1}{(2N)^{\kappa}}\sum_{\begin{subarray}{c}k=k_{1}\|\dots\|k_{\kappa}\\\
1\leq k_{j}\leq N\ \forall j\\\ \alpha\in\bin^{\kappa}\end{subarray}}\
\max_{\theta,r}\big{\lVert}\mathrm{\Pi}_{\theta,r}\mathrm{\Pi}_{\pi_{k,\alpha}(\theta,r)}\rVert$

where $\\{\pi_{k,\alpha}\\}$ is a family of mutually orthogonal permutations
indexed by $k=k_{1}\|\dots\|k_{\kappa}$ \- where each $k_{j}\in\llbracket
1,N\rrbracket$ \- and $r\in\bin^{\kappa}$.

#### Step 3: upper-bound of
$\lVert\mathrm{\Pi}_{\theta,r}\mathrm{\Pi}_{\theta^{\prime},\bar{r}}\rVert$.

Let $\theta=(\theta^{1},...,\theta^{\kappa})$ and
$\theta^{\prime}=(\theta^{{}^{\prime}1},...,\theta^{{}^{\prime}\kappa})$ where
each $\theta^{j}$ and $\theta^{{}^{\prime}j}$ belongs to
$\mathrm{\Theta}_{n}$. Let $r\in\bin^{\kappa}$. For every $j\in\llbracket
1,\kappa\rrbracket$, note $R^{j}:=\\{i\in\llbracket 1,N\rrbracket\ :\
\theta^{j}_{i}\neq\theta^{{}^{\prime}j}_{i}\\}$, $T^{j}:=\\{i\in\llbracket
1,N\rrbracket\ :\ \theta^{j}_{i}=r_{j}\\}$,
$T^{{}^{\prime}j}:=\\{i\in\llbracket 1,N\rrbracket\ :\
\theta^{{}^{\prime}j}_{i}=1-r_{j}\\}$ and $S^{j}:=\\{i\in R\ :\
\theta^{j}_{i}=r_{j}\text{ and }\theta^{{}^{\prime}j}_{i}=1-r_{j}\\}$. We
define $\bar{\mathrm{P}}$ and $\bar{\mathrm{Q}}$ as follows:

$\displaystyle\bar{\mathrm{P}}$
$\displaystyle=\sum_{\begin{subarray}{c}j\in\llbracket 1,\kappa\rrbracket\\\
x_{T^{j}}\in\bin^{T^{j}}\end{subarray}}\bigotimes\limits_{j=1}^{\kappa}\mathsf{H}^{r_{j}}{|x_{S^{j}}\rangle\\!\langle
x_{S^{j}}|}\mathsf{H}^{r_{j}}\otimes\mathbb{I}_{\bar{S^{j}}}\otimes
B^{\theta,r}_{x_{T}}\otimes\mathbb{I}_{C}$ $\displaystyle\bar{\mathrm{Q}}$
$\displaystyle=\sum_{\begin{subarray}{c}j\in\llbracket 1,\kappa\rrbracket\\\
x_{T^{{}^{\prime}j}}\in\bin^{T^{{}^{\prime}j}}\end{subarray}}\bigotimes\limits_{j=1}^{\kappa}\mathsf{H}^{1-r_{j}}{|x_{S^{j}}\rangle\\!\langle
x_{S^{j}}|}\mathsf{H}^{1-r_{j}}\otimes\mathbb{I}_{\bar{S^{j}}}\otimes\mathbb{I}_{B}\otimes
C^{\theta^{\prime},1-\bar{r}}_{x_{T^{\prime}}}$

where $T:=T^{1}\|\dots\|T^{\kappa}$, ${|x_{S^{j}}\rangle\\!\langle
x_{S^{j}}|}$ denotes the subsystem of ${|x_{T^{j}}\rangle\\!\langle
x_{T^{j}}|}$ whose indices belong to $S^{j}$, and $\mathbb{I}_{\bar{S^{j}}}$
denotes the rest of the system.

Following the same reasoning as in Theorem 3.2 (step 3), it comes

$\lVert\mathrm{\Pi}_{\theta,r}\mathrm{\Pi}_{\theta^{\prime},\bar{r}}\rVert\leq
2^{-\frac{\sum_{j}\lvert R^{j}\rvert}{4}}$

#### Step 4: finding the permutation family.

Let $\\{\pi^{\star}_{k,\alpha}\\}_{k\in\llbracket
1,N\rrbracket,\alpha\in\bin}$ denotes the permutation family defined in step 4
of Theorem 3.2. We define the permutation family $\\{\pi_{k,\beta}\\}$ \-
indexed by $k=k_{1}\|\dots\|k_{\kappa}$ where each $k_{j}\in\llbracket
1,N\rrbracket$ and $\beta\in\bin^{\kappa}$ \- as
$\pi_{k,r}(\theta_{1}\|\dots\|\theta_{\kappa},r)=\pi^{\star}_{k_{1},\beta_{1}}(\theta_{1},r_{1})\|\dots\|\pi^{\star}_{k_{\kappa},\beta_{\kappa}}(\theta_{\kappa},r_{\kappa})$.
It is easy to see that this family is orthogonal and has the same required
properties as in the single instance proof, that is that for every
$j\in\llbracket 1,\kappa\rrbracket$ and $i\in\llbracket 1,n/2\rrbracket$,
there are exactly ${n/2\choose i}^{2}$ permutations $\pi_{k,0}$ such that the
number of positions at which $\theta^{j}$ and $\theta^{{}^{\prime}j}$ are both
$1$ is $n/2-i$ (i.e. $|R^{j}|=2^{i}$). Using this set of permutations we have:

$\displaystyle p_{win}$
$\displaystyle\leq\frac{1}{(2N)^{\kappa}}\sum_{\begin{subarray}{c}k=k_{1}\|\dots\|k_{\kappa}\\\
\beta\in\bin^{\kappa}\end{subarray}}\max_{\begin{subarray}{c}\theta=\theta_{1}\|\dots,\|\theta_{\kappa}\\\
r\in\bin^{\kappa}\end{subarray}}\|\mathrm{\Pi}_{\theta,r}\mathrm{\Pi}_{\theta^{\prime},r^{\prime}}\|$
$\displaystyle=\frac{1}{(2N)^{\kappa}}\sum_{w=0}^{\kappa}\sum_{\begin{subarray}{c}k=k_{1}\|\dots\|k_{\kappa}\\\
\beta\in\bin^{\kappa},|\beta|=w\end{subarray}}\max_{\begin{subarray}{c}\theta=\theta_{1}\|\dots,\|\theta_{\kappa}\\\
r\in\bin^{\kappa}\end{subarray}}\|\mathrm{\Pi}_{\theta,r}\mathrm{\Pi}_{\theta^{\prime},r^{\prime}}\|$
$\displaystyle\leq\frac{1}{(2N)^{\kappa}}\sum_{w=0}^{\kappa}\binom{\kappa}{w}\left(\sum_{\ell=0}^{n/2}\binom{n/2}{\ell}^{2}2^{-\ell/2}\right)^{w}$
$\displaystyle=\frac{1}{(2N)^{\kappa}}\left(1+\sum_{\ell=0}^{n/2}\binom{n/2}{\ell}^{2}2^{-\ell/2}\right)^{\kappa}$
$\displaystyle\leq\frac{1}{(2N)^{\kappa}}\left(1+\binom{n/2}{n/4}^{2}\sum_{\ell=0}^{n/2}2^{-\ell/2}\right)^{\kappa}$
$\displaystyle=\frac{1}{(2N)^{\kappa}}\left(1+\binom{n/2}{n/4}^{2}\frac{1-2^{-n/4-1/2}}{1-2^{-1/2}}\right)^{\kappa}$

Where in the first equality, we split the sum over the possible weights of
$\beta$; the first inequality comes from Corollary 1; we obtain the second
equality by applying the binomial theorem; the second inequality comes from
$\binom{n}{k}\leq\binom{n}{n/2}$ for all $n,k$; and the last inequality comes
from the fact that the sum is the sum of a geometric series.

Using both Stirling approximation and asymptotic development of logarithm, we
get that the logarithm of this last inequality decreases linearly in $k$,
meaning that the upper bound is negligible in $n$ which concludes the proof.

##  4 Single-Decryptor and Copy-Protection of Pseudorandom Functions

In this section, we recall the notions of single-decryptor and copy-protection
of pseudorandom functions. These primitives are used later to prove the
security of our constructions of copy-protection of point functions and
unclonable encryption. In [CLLZ21], the authors give a definition of anti-
piracy security and provide a secure construction for these two primitives. We
give two variants of anti-piracy security of single-decryptor and of anti-
piracy security of copy-protection of pseudorandom functions and show that
their constructions are secure with respect to these two variants.

###  4.1 Definition of a Single-Decryptor

######  Definition 13 (Single-decryptor encryption scheme).

A single-decryptor encryption scheme is a tuple of algorithms
$\langle\mathsf{Setup},\mathsf{QKeyGen},\allowbreak\enc,\dec\rangle$ with the
following properties:

  * •

$(\sk,\pk)\leftarrow\mathsf{Setup}(1^{\secpar})$. On input a security
parameter $\secpar$, the classical setup algorithm $\mathsf{Setup}$ outputs a
classical secret key $\sk$ and a public key $\pk$.

  * •

$(\rho_{\sk})\leftarrow\mathsf{QKeyGen}(\sk)$. On input a classical secret key
$\sk$, the quantum key generation algorithm $\mathsf{QKeyGen}$ outputs a
quantum secret key $\rho_{\sk}$.

  * •

$c\leftarrow\enc(\pk,m)$. On input a public key $\pk$ and a message $m$ in the
message space $\mathcal{M}$, the classical randomized encryption algorithm
$\enc$ outputs a classical ciphertext $c$. We sometimes write $\enc(\pk,m;r)$
to precise that we use the the random bitstring $r$ as the randomness in the
algorithm.

  * •

$m/\bot\leftarrow\dec(\rho_{\sk},c)$. On input a quantum secret key
$\rho_{\sk}$, a classical ciphertext $y$, the quantum decryption algorithm
$\dec$ outputs a classical message $m$ or a decryption failure symbol $\bot$.

#### Correctness.

We say that a single-decryptor scheme
$\langle\mathsf{Setup},\mathsf{QKeyGen},\allowbreak\enc,\dec\rangle$ has
correctness if there exists a negligible function $\negl[\cdot]$, such that
for all $\secpar\in\NN$, for all $m\in\mathcal{M}$, the following holds:

$\displaystyle\textnormal{Pr}\left[\begin{array}[]{l}\dec(\rho_{\sk},c)=m\end{array}\
\middle|\ \begin{array}[]{r}(\sk,\pk)\leftarrow\mathsf{Setup}(1^{\secpar})\\\
\rho_{\sk}\leftarrow\mathsf{QKeyGen}(\sk)\\\
c\leftarrow\enc(\pk,m)\end{array}\right]\geq 1-\negl.$

Note that correctness implies that a honestly generated quantum decryption key
can be used to decrypt correctly polynomially many times, from the gentle
measurement lemma [Wil11].

#### Anti-piracy security.

We now define indistinguishable anti-piracy security of a single-decryptor
scheme. This security notion is define with respect to two distributions used
in the piracy game that we defined below: $\mathcal{D}_{B}$ that yields two
bits and decides which message will be encrypted for each test, and
$\mathcal{D}_{R}$ that yields two strings to be used as the randomness for the
encryption in each test. Note that the original anti-piracy security proposed
in [CLLZ21] is simply our notion with respect to $\mathcal{D}_{B}$ and
$\mathcal{D}_{R}$ taken as uniform distributions. In contrast, in order to
prove the security of our unclonable encryption and copy-protection schemes,
we need to consider the security when $\mathcal{D}_{R}$ yields a pair of
identical random string $(r,r)$ (sampled uniformly at random) and
$\mathcal{D}_{B}$ either is the uniform distribution and hence yields pairs of
the form $(b_{1},b_{2})$ or is the “identical distribution” and yields pairs
of the form $(b,b)$.

######  Definition 14 (Piracy game for single-decryptor).

We define below a _piracy game for single-decryptor_ , parameterized by a
single-decryptor scheme
$\mathcal{E}=\langle\mathsf{Setup},\mathsf{QKeyGen},\enc,\dec\rangle$, a
security parameter $\secpar$ and a pair of distributions
$\left(\mathcal{D}_{B},\mathcal{D}_{R}\right)$. This game is between a
challenger and an adversary represented by a QPT algorithm $\adv$.

  * •

Setup phase:

    * –

The challenger samples $(\sk,\pk)\leftarrow\mathsf{Setup}(\secparam)$.

    * –

The challenger samples $\rho_{\sk}\leftarrow\mathsf{QKeyGen}(\sk)$.

    * –

The challenger sends $(\pk,\rho_{\sk})$ to $\adv$.

  * •

Splitting phase:

    * –

$\adv$ outputs a bipartite quantum state $\sigma_{12}$, two quantum circuits
$\mathsf{U}_{1}$ and $\mathsf{U}_{2}$, and two pairs of messages
$(m^{1}_{0},m^{1}_{1})$ and $(m^{2}_{0},m^{2}_{1})$.

  * •

Challenge phase: The challenger samples
$(b_{1},b_{2})\leftarrow\mathcal{D}_{B}$,
$(r_{1},r_{2})\leftarrow\mathcal{D}_{R}$ and for $i\in\\{1,2\\}$, the
challenger performs the following test on $(\sigma_{i},\mathsf{U}_{i})$:

    * –

compute $c\leftarrow\enc(\pk,m_{b_{i}};r_{i})$;

    * –

run the circuit $\mathsf{U}_{i}$ on $\sigma_{i}\otimes{|c\rangle\\!\langle
c|}$ and checks whether the outcome is $b$. If so, we say that
$(\sigma_{i},\mathsf{U}_{i})$ passes the test, otherwise that it does not.

$\adv$ wins the game if both $(\sigma_{1},\mathsf{U}_{1})$ and
$(\sigma_{2},\mathsf{U}_{2})$ pass the test.

We denote the random variable that indicates whether an adversary $\adv$ wins
the game or not as $\mathsf{SD-
AP}^{\mathcal{E}}_{\left(\mathcal{D}_{B},\mathcal{D}_{R}\right)}(\secparam,\adv)$.

######  Remark 2.

[CLLZ21] shows that we can assume that the tests of the challenge phase can be
performed in a projective way - that is the test is actually a projective
measurement. For sake of readability, we do not define formally the notions of
_projective/threshold implementation_ and their approximated versions and
refer the interested reader to [CLLZ21] for a more in-depth discussion about
them. Thus, in all the following proofs, we consider that all the tests for
the different piracy games are performed in a projective way (Definitions 14,
20 and 17).

######  Definition 15 (Indistinguishable anti-piracy security).

A single-decryptor scheme $\mathcal{E}$ has _indistinguishable anti-piracy
security_ with respect to distributions
$\left(\mathcal{D}_{B},\mathcal{D}_{R}\right)$ if no QPT adversary can win the
piracy game above with probability significantly greater than $1/2$. More
precisely, for any QPT adversary $\adv$:

$\prob{\mathsf{SD-
AP}^{\mathcal{E}}_{\left(\mathcal{D}_{B},\mathcal{D}_{R}\right)}(\secparam,\adv)=1}\leq
1/2+\negl.$

Whenever, a single-decryptor is secure with respect to the uniform
distribution $\mathcal{D}_{B}$ and the “identical distribution”
$\mathcal{D}_{R}$ \- that yields uniformly random pairs of the form $(r,r)$ \-
we say that the single-decryptor has indistinguishable anti-piracy security in
the _identical randomness_ style.

Furthermore, whenever a single-decryptor is secure with respect to the
identical distribution $\mathcal{D}_{B}$ and the identical distribution
$\mathcal{D}_{R}$ \- that yield uniformly random pairs of the form $(b,b)$ and
$(r,r)$ respectively - we say that the single-decryptor has indistinguishable
anti-piracy security in the _identical randomness and challenge bits_ style.

###  4.2 Construction of Single-Decryptor

In this section, we present the single-decryptor construction of [CLLZ21].

[CLLZ21] Single-Decryptor Schemesd Given a security parameter $\secpar$, let
$n:=\secpar$ and $\kappa$ be polynomial in $\secpar$.

  * •

$(\sk,\pk)\leftarrow\mathsf{Setup}(\secparam)$:

    * –

Sample coset spaces $\\{A_{i},s_{i},s^{\prime}_{i}\\}_{i\in\llbracket
1,\kappa\rrbracket}$ where each $A_{i}$ is of dimension $n/2$;

    * –

Construct the membership programs for each coset
$\\{\widehat{\mathsf{P}}_{A_{i}+si},\widehat{\mathsf{P}}_{A^{\perp}_{i}+s^{\prime}i}\\}_{i\in\llbracket
1,\kappa\rrbracket}$;

    * –

Return $\left(\sk\coloneqq\\{A_{i},s_{i},s^{\prime}_{i}\\}_{i\in\llbracket
1,\kappa\rrbracket},\pk\coloneqq\\{\widehat{\mathsf{P}}_{A_{i}+si},\widehat{\mathsf{P}}_{A^{\perp}_{i}+s^{\prime}i}\\}_{i\in\llbracket
1,\kappa\rrbracket}\right)$.

  * •

$\rho_{\sk}\leftarrow\mathsf{QKeyGen}(\sk)$:

    * –

Parse $\sk$ as $\\{A_{i},s_{i},s^{\prime}_{i}\\}_{i\in\llbracket
1,\kappa\rrbracket}$;

    * –

Return $\bigotimes\limits_{i=1}^{\kappa}\ket{A_{i,s_{i},s^{\prime}_{i}}}$.

  * •

$c\leftarrow\enc(\pk,m)$:

    * –

Parse $\pk$ as
$\\{\widehat{\mathsf{P}}_{A_{i}+si},\widehat{\mathsf{P}}_{A^{\perp}_{i}+s^{\prime}i}\\}_{i\in\llbracket
1,\kappa\rrbracket}$;

    * –

Sample $r\sample\bin^{\kappa}$;

    * –

Generate an obfuscated program $\iO(\mathsf{Q_{m,r}})$ of program
$\mathsf{Q_{m,r}}$ described in Figure 2.

    * –

Return $c\coloneqq\left(r,\iO(\mathsf{Q_{m,r}})\right)$.

  * •

$m/\bot\leftarrow\dec(\rho_{\sk},c)$:

    * –

Parse $\rho_{\sk}$ as
$\bigotimes\limits_{i=1}^{\kappa}\ket{A_{i,s_{i},s^{\prime}_{i}}}$ and
$c\leftarrow\left(r,\iO(\mathsf{Q_{m,r}})\right)$;

    * –

For all $i\in\llbracket 1,\kappa\rrbracket$: if $r_{i}=1$, apply
$\mathsf{H}^{\otimes n}$ to $\ket{A_{i,s_{i},s^{\prime}_{i}}}$;

    * –

Let $\rho^{\prime}$ be the resulting state, run $\iO(\mathsf{Q_{m,r}})$
coherently on $\rho^{\prime}$ and measure the final register to get $m$;

    * –

Return $m$.

Hardcoded: Programs $\\{\mathsf{P}_{i}\\}_{i\in\llbracket 1,\kappa\rrbracket}$
such that for all $i\in\llbracket 1,\kappa\rrbracket$:
$\mathsf{P}_{i}:=\left\\{\begin{array}[]{ll}\widehat{\mathsf{P}}_{A_{i}+si}&\text{
if }r_{i}=0\\\ \widehat{\mathsf{P}}_{A^{\perp}_{i}+s^{\prime}i}&\text{ if
}r_{i}=1\end{array}\right.$. On input vectors $u_{1},u_{2},\dots,u_{\kappa}$,
do the following: 1. If for all $i\in\llbracket 1,\kappa\rrbracket$:
$\mathsf{P}_{i}(u_{i})=1$, then output $m$. 2. Otherwise: output $\bot$.
Figure 2: Program $\mathsf{Q_{m,r}}$.

######  Remark 3.

Note that the underlying $\iO$ algorithm used in the encryption algorithm of
LABEL:constr:sd might use randomness. In the following, we denote by
$\enc(\pk,m;(r_{\iO},r))$ the encryption of a message $m$ with the key $\pk$
and with random bitstrings $r_{\iO}$ and $r$ respectively used for the $\iO$
algorithm and for the program $\mathsf{Q_{m,r}}$.

######  Theorem 4.1.

Assuming the existence of post-quantum indistinguishability obfuscation, one-
way functions, and compute-and-compare obfuscation for the class of
unpredictable distributions, LABEL:constr:sd has _indistinguishable anti-
piracy security in the identical randomness style_.

######  Theorem 4.2.

Assuming the existence of post-quantum indistinguishability obfuscation, one-
way functions, and compute-and-compare obfuscation for the class of
unpredictable distributions, LABEL:constr:sd has _indistinguishable anti-
piracy security in the identical randomness and challenge bits style_.

###  4.3 Proof of Theorem 4.1

In this section, we prove Theorem 4.1. Our proof follows the structure of
[CLLZ21]. We proceed in the proof through a sequence of hybrids. For any pair
of hybrids $(G_{i},G_{j})$, we say that $G_{i}$ is negligibly close to $G_{j}$
if for every QPT adversary $\adv\coloneqq(\adv_{0},\adv_{1},\adv_{2})$, the
probability that $\adv$ wins $G_{i}$ is negligibly close to the probability
that they win $G_{j}$.

  1. Game $G_{\thepcgamecounter}\gameprocedurearg$:

This is the piracy game for the single-decryptor of LABEL:constr:sd, in the
identical randomness style.

     * •

Setup phase:

       * –

The challenger samples coset spaces
$\\{A_{i},s_{i},s^{\prime}_{i}\\}_{i\in\llbracket 1,\kappa\rrbracket}$ where
each $A_{i}$ is of dimension $n/2$;

       * –

Then the challenger constructs the membership programs for each coset
$\\{\widehat{\mathsf{P}}_{A_{i}+si},\widehat{\mathsf{P}}_{A^{\perp}_{i}+s^{\prime}i}\\}_{i\in\llbracket
1,\kappa\rrbracket}$;

       * –

Finally the challenger sends
$\rho_{\sk}:=\\{\ket{A_{i,s_{i},s^{\prime}_{i}}}\\}_{i\in\llbracket
1,\kappa\rrbracket}$ and
$\pk:=\\{\widehat{\mathsf{P}}_{A_{i}+si},\widehat{\mathsf{P}}_{A^{\perp}_{i}+s^{\prime}i}\\}_{i\in\llbracket
1,\kappa\rrbracket}$ to $\adv$.

     * •

Splitting phase:

       * –

$\adv$ outputs a bipartite quantum state $\sigma_{12}$, two quantum circuits
$\mathsf{U}_{1}$ and $\mathsf{U}_{2}$, and two pairs of messages
$(m^{1}_{0},m^{1}_{1})$ and $(m^{2}_{0},m^{2}_{1})$.

     * •

Challenge phase: The challenger samples random bitstrings $r_{\iO}$ and $r$,
to be used in the encryption algorithm, and performs the following test on
each $(\sigma_{i},\mathsf{U}_{i})$ for $i\in\\{1,2\\}$:

       * –

sample $b\in\bin$;

       * –

compute $c:=(r,\mathsf{Q})\leftarrow\enc(\pk,m^{i}_{b};(r,r_{\iO}))$ \- note
that the program $\mathsf{Q}$ has been obfuscated using $r_{\iO}$ as the
randomness;

       * –

run the circuit $\mathsf{U}_{i}$ on $\sigma_{i}\otimes{|c\rangle\\!\langle
c|}$ and checks whether the outcome is $b$. If so, we say that
$(\sigma_{i},\mathsf{U}_{i})$ passes the test, otherwise that it does not.

$\adv$ wins the game if both $(\sigma_{1},\mathsf{U}_{1})$ and
$(\sigma_{2},\mathsf{U}_{2})$ pass the test.

  2. Game $G_{\thepcgamecounter}\gameprocedurearg$:

In this second hybrid, we replace the obfuscated programs $\mathsf{Q}$ by
obfuscated compute-and-compare programs. More formally, for $i\in\llbracket
1,\kappa\rrbracket$, we note222Recall that for a subspace $A$ and a vector
$u$, $\mathsf{Can}_{A}(u)$ \- defined in Section 2.2 \- is the coset
representative of $A+u$. Recall also that $\mathsf{Can}_{A}$ can be
efficiently implemented given a description of $A$.

$\mathsf{Can}_{i,b}(\cdot):=\left\\{\begin{array}[]{ll}\mathsf{Can}_{A_{i}}(\cdot)&\text{
if }b=0\\\ \mathsf{Can}_{A^{\perp}_{i}}(\cdot)&\text{ if
}b=1\end{array}\right.\text{ and
}c_{i,b}:=\left\\{\begin{array}[]{ll}\mathsf{Can}_{A_{i}}(s_{i})&\text{ if
}b=0\\\ \mathsf{Can}_{A^{\perp}_{i}}(s^{\prime}_{i})&\text{ if
}b=1\end{array}\right.$

We similarly define
$\mathsf{Can}_{r}(u_{1},...,u_{\kappa})=(\mathsf{Can}_{1,r_{1}}(u_{1}),\dots,\mathsf{Can}_{\kappa,r_{\kappa}}(u_{\kappa}))$
and $c_{r}=(c_{1,r_{1}},\dots,c_{\kappa,r_{\kappa}})$ for any
$r\in\bin^{\kappa}$.

Then, we replace $\mathsf{Q}$ by
$\iO(\mathsf{CC}[\mathsf{Can}_{r},c_{r},m^{1}_{b}])$ in the first test and by
$\iO(\mathsf{CC}[\mathsf{Can}_{r},c_{r},m^{2}_{b}])$ in the second test.
Because the programs $\mathsf{Q}$ in each test $i\in\\{1,2\\}$ and
$\mathsf{CC}[\mathsf{Can}_{r},c_{r},m^{i}_{b}]$ are functionally equivalent,
$G_{0}$ and $G_{1}$ are negligibly close from $\iO$ security.

  3. Game $G_{\thepcgamecounter}\gameprocedurearg$:

In this last hybrid, we replace
$\iO(\mathsf{CC}[\mathsf{Can}_{r},c_{r},m^{i}_{b}])$ by
$\iO(\mathsf{CC\text{-}Obf}(\secparam,\mathsf{CC}[\mathsf{Can}_{r},c_{r},m^{i}_{b_{i}}]))$
in each test $i\in\\{1,2\\}$. Because the programs
$\mathsf{CC}[\mathsf{Can}_{r},c_{r},m^{i}_{b}]$ and
$\mathsf{CC\text{-}Obf}(\secparam,\mathsf{CC}[\mathsf{Can}_{r},c_{r},m^{i}_{b_{i}}])$
are functionally equivalent, $G_{1}$ and $G_{2}$ are negligibly close from
$\iO$ security.

#### Leveraging compute-and-compare obfuscation.

Before proceeding to the reduction, we introduce the two following lemmas.

######  Lemma 5.

There exists an efficient algorithm $\ext$ such that the following holds.
Sample uniformly at random $\kappa$ cosets spaces
$\\{A_{i},s_{i},s^{\prime}_{i}\\}_{i\in\llbracket 1,\kappa\rrbracket}$ and a
$\kappa$-long bitstring $r$. Let $(\sigma,\mathsf{U})$ be a pair of quantum
state and quantum circuits that passes the test of $G_{2}$ with respect to a
pair of messages $(m_{0},m_{1})$ with non-negligible advantage over $1/2$.

Then $\ext$, on input the description of the subspaces
$(A_{i})_{i\in\llbracket 1,\kappa\rrbracket}$, the bitstring $r$, and the pair
$(\sigma,\mathsf{U})$, outputs the canonical vectors
$(u_{1},\dots,u_{\kappa})$ \- where $u_{i}$ is the canonical vector for the
coset space $A_{i}+s_{i}$ if $r_{i}=0$ or $A^{\perp}_{i}+s^{\prime}_{i}$ if
$r_{i}=1$ \- with non-negligible probability.

###### Proof.

We define two distributions $\mathcal{D}$ and $\mathcal{D}_{\simulator}$, both
parametrized by a pair of messages $m_{0},m_{1}$. Let $\mathcal{D}$ be the
following distribution:

  * •

sample $\sk:=\\{A_{i},s_{i},s^{\prime}_{i}\\}_{i\in\llbracket
1,\kappa\rrbracket}$ as in the setup phase of $G_{2}$;

  * •

sample $r$ as in the challenge phase of $G_{2}$;

  * •

compute
$\mathsf{C}:=\iO(\mathsf{CC\text{-}Obf}(\secparam,\mathsf{CC}[\mathsf{Can}_{r},c_{r},m_{b}]))$
as in the challenge phase of $G_{2}$;

  * •

let $(\sigma,U)$ be a pair (quantum state, quantum circuit) that passes the
test of $G_{2}$ with respect to $(m_{0},m_{1})$ with non-negligible advantage
over $1/2$;

  * •

output $(\mathsf{C},\mathsf{aux})$ where $\mathsf{aux}:=(\sigma,\mathsf{U})$.

Let $\mathcal{D}_{\simulator}$ be the same distribution, except that
$\mathsf{C}$ is replaced by the output of an efficient simulator $\simulator$
taking as input $(\secparam,\mathsf{C}.\mathsf{params})$, where
$\mathsf{C}.\mathsf{params}$ denotes the parameters of $\mathsf{C}$ (input and
output size, circuit size, etc.). From compute-and-compare obfuscation
(Definition 4), we know that if, for any simulator $\simulator$, there exists
an efficient procedure to distinguish these two distributions $\mathcal{D}$
and $\mathcal{D}_{\simulator}$, then there exists an efficient algorithm
$\extractor$, that takes as input $\mathsf{aux}$ and the description of the
function in the compute-and-compare program (here $\mathsf{Can}_{r}$), and
extracts the lock-value of the program $\mathsf{C}$, namely the canonical
vectors $(u_{i})_{i\in\llbracket 1,\kappa\rrbracket}$ respectively for the
coset spaces $A_{i}+s_{i}$ if $r_{i}=0$ or $A^{\perp}_{i}+s^{\prime}_{i}$ if
$r_{i}=1$. We describe below such an efficient procedure to distinguish the
two distributions. On input
$(\mathsf{C}^{*},\mathsf{aux}=(\sigma,\mathsf{U}))$, sampled from
$\mathcal{D}$ or $\mathcal{D}_{\simulator}$, the procedure behaves in the
following way:

  * •

sample $b\sample\bin$;

  * •

run $\mathsf{U}$ on
$\sigma\otimes{|\mathsf{C}^{*}\rangle\\!\langle\mathsf{C}^{*}|}$; let $b^{*}$
denotes the outcome;

  * •

if $b^{*}=b$: return $0$, meaning that $\mathsf{C}^{*}$ comes from
$\mathcal{D}$;

  * •

otherwise: return $1$, meaning that $\mathsf{C}^{*}$ comes from
$\mathcal{D}_{\simulator}$.

Because, $(\sigma,\mathsf{U})$ passes the challenge test of $G_{2}$ with non-
negligible advantage over $1/2$, the procedure succeeds with the same
advantage conditioned on $\mathsf{C}^{*}$ coming from $\mathcal{D}$. On the
other hand, when $\mathsf{C}^{*}$ comes from $\mathcal{D}_{\simulator}$, then
$\mathsf{C}^{*}$ does not hold any information on $b$, hence $b^{*}=b$ only
with probability $1/2$. Thus the procedure distinguishes the two distributions
with non-negligible advantage over $1/2$. Because $\mathsf{Can}_{r}$ can be
implemented given $(A_{i})_{i\in\llbracket 1,\kappa\rrbracket}$ and $r$, it
concludes the proof. ∎

The following lemma is a claim from [CLLZ21] adapted to our settings. We refer
the interested reader to [CLLZ21] for a proof of this lemma.

######  Lemma 6 (Claim 6.18 of [CLLZ21]).

Let $\sigma_{12},\mathsf{U}_{1},\mathsf{U}_{2}$ a bipartite quantum state and
two quantum circuits such that both $(\sigma_{1},\mathsf{U}_{1})$ and
$(\sigma_{2},\mathsf{U}_{2})$ pass the (projective) test in the challenge
phase. Apply any POVM on $\sigma_{1}$; let $\sigma^{\prime}_{12}$ denotes the
post-measurement state. Then $(\sigma^{\prime}_{2},\mathsf{U}_{2})$ still
passes the (projective) test of the challenge phase with non-negligible
probability over $1/2$.

#### Reduction to monogamy-of-entanglement.

We are now ready to proceed to the reduction. Assume that there exists a QPT
algorithm $\adv$ that wins the last hybrid $G_{2}$ with non-negligible
advantage over $1/2$. We construct a triple of QPT algorithms
$(\bdv_{0},\bdv_{1},\bdv_{2})$ that win the $\kappa$-parallel computational
version of monogamy-of-entanglement game (Definition 12) with with non-
negligible advantage over $1/2$, which contradicts Theorem 3.4. $\bdv$ behaves
in the following way; on input
$\ket{A_{i,s_{i},s^{\prime}_{i}}}_{i\in\llbracket 1,\kappa\rrbracket}$ and
$\left(\widehat{\mathsf{P}}_{A_{i}+s_{i}},\widehat{\mathsf{P}}_{A^{\perp}_{i}+s^{\prime}_{i}}\right)_{i\in\llbracket
1,\kappa\rrbracket}$:

  * •

$\bdv_{0}$ sets $\rho_{\sk}:=\ket{A_{i,s_{i},s^{\prime}_{i}}}_{i\in\llbracket
1,\kappa\rrbracket}$ and
$\pk:=\left(\widehat{\mathsf{P}}_{A_{i}+s_{i}},\widehat{\mathsf{P}}_{A^{\perp}_{i}+s^{\prime}_{i}}\right)_{i\in\llbracket
1,\kappa\rrbracket}$.

  * •

$\bdv_{0}$ runs $\adv$ on $\left(\rho_{\sk},\pk\right)$; let
$\left(\sigma_{12},(\mathsf{U}_{1},\mathsf{U}_{2}),(m^{1}_{0},m^{1}_{1}),(m^{2}_{0},m^{2}_{1})\right)$
denote the outcome.

  * •

$\bdv_{0}$ samples $r_{\iO}$: a uniformly random bitstring to be used in
$\iO$.

  * •

For $i\in\\{1,2\\}$, let
$\sigma^{\prime}_{i}:=\sigma_{i}\otimes{|\mathsf{U}_{i}\rangle\\!\langle\mathsf{U}_{i}|}$;
$\bdv_{0}$ sends $\sigma^{\prime}_{1}$ to $\bdv_{1}$ and $\sigma^{\prime}_{2}$
to $\bdv_{2}$.

For $i\in\\{1,2\\}$: on input
$\sigma^{\prime}_{i}:=\sigma_{i}\otimes{|\mathsf{U}_{i}\rangle\\!\langle\mathsf{U}_{i}|}$
as well as the challenge $\left((A_{i})_{i\in\llbracket
1,\kappa\rrbracket},r\right)$: $\bdv_{i}$ runs the algorithm $\ext$ from Lemma
5 on $\left((A_{i})_{i\in\llbracket 1,\kappa\rrbracket},r\right)$ and
$(\sigma_{i},\mathsf{U}_{i})$ to extract $(u_{1},\dots,u_{\kappa})$.
$\bdv_{i}$ then returns $(u_{1},\dots,u_{\kappa})$. Note that both
$(\sigma_{1},\mathsf{U}_{1})$ and $(\sigma_{2},\mathsf{U}_{2})$ pass the test
of the challenge phase with non-negligible advantage over $1/2$, and that all
the other elements are sampled as in Lemma 5, allowing us to use the
extractor. Although, one might fear the using the extractor on $\sigma_{1}$
would disturb $\sigma_{2}$, making this new
$(\sigma^{\prime}_{2},\mathsf{U}_{2})$ unable to pass the test of the
challenge phase (and hence we would not be able to perform the extraction
procedure on $\sigma^{\prime}_{2}$), we know from Lemma 6 that this does not
happen and $\sigma^{\prime}_{2}$ still passes the test after the action of the
extractor on $\sigma_{1}$. Thus, both $\bdv_{1}$ and $\bdv_{2}$ extract the
expected $(u_{1},\dots,u_{\kappa})$ with non-negligible probability, which
concludes the proof.

###  4.4 Proof of Theorem 4.2

We now prove Theorem 4.2. As this proof is very similar to the one of Theorem
4.1, we only provide a sketch of it. We proceed with a sequence of hybrids.
The first one $G_{0}$ is the piracy game in the identical randomness and
challenge bits style. We recall that it is the same game as the first hybrid
of the proof of Theorem 4.1, except that the tests in the challenge phase
either both use the encryption of the first message of the corresponding pair,
or both use the second message (depending on a random bit $b$). In the second
and third hybrids $G_{1}$ and $G_{2}$, we do the same as in the proof above,
namely we replace the obfuscated programs in the ciphertexts by their compute-
and-compare obfuscated versions, with function $\mathsf{Can}_{r}$ and lock-
value $c_{r}$. Finally, the reduction is exactly the same as above: we use
Lemma 5 and Lemma 6 to argue that both $\bdv_{1}$ and $\bdv_{2}$ can use an
extractor $\ext$ on their respective shares of $\sigma_{12}$ and obtain the
expected vectors $(u_{1},\dots,u_{\kappa})$, which concludes the proof.

###  4.5 Copy-Protection of Pseudorandom Functions

In this subsection, we formally define copy-protection of pseudorandom
function and its correctness and anti-piracy notions.

######  Definition 16 (Pseudorandom function copy-protection scheme).

A pseudorandom function copy-protection scheme for the pseudorandom function
$\prf:\mathcal{K}\times\mathcal{X}\rightarrow\mathcal{Y}$ (where
$\mathcal{Y}\subseteq\bin^{m}$) associated with the key generation procedure
$\mathsf{KeyGen}$ is a tuple of algorithms
$\langle\mathsf{KeyGen},\mathsf{Protect},\eval\rangle$ with the following
properties:

  * •

$\key\leftarrow\mathsf{KeyGen}(\secparam)$. This is the key generation
procedure of the underlying pseudorandom function: on input a security
parameter, the $\mathsf{KeyGen}$ algorithm outputs a key $\key$.

  * •

$\rho_{\key}\leftarrow\mathsf{Protect}(\secparam,\key)$. On input a
pseudorandom function key $\key\in\mathcal{K}$, the quantum protection
algorithm outputs a quantum state $\rho_{\key}$.

  * •

$y\leftarrow\eval(\secparam,\rho,x)$. On input a quantum state $\rho$ and an
input $x\in\mathcal{X}$, the quantum evaluation algorithm outputs
$y\in\mathcal{Y}$.

#### Correctness.

A pseudorandom function copy-protection scheme has _correctness_ if the
quantum protection of any key $\key$ computes $\prf(\key,\cdot)$ on every $x$
with overwhelming probability.

$\forall\key\in\mathcal{K},\ \forall x\in\mathcal{X},\
\textnormal{Pr}\left[\eval(\secparam,\rho_{\key},x)=\prf(\key,x)\ :\
\rho_{\key}\leftarrow\mathsf{Protect}(\secparam,\key)\right]=1-\negl$

#### Anti-piracy security.

We now define anti-piracy security of a pseudorandom function copy-protection
scheme in a similar way as the anti-piracy of single-decryptor. Anti-piracy
security is defined through the following _piracy game_ , in which the
adversary is provided a quantum key and a pseudorandom function image, and
must “split” the quantum key such that both shares can be used to distinguish
between the input of this image or another “fake” input sampled uniformly at
random. We define two different “styles” for this security: the _product
challenge bits style_ and the _identical distribution style_. In the _product
challenge bits style_ , the challenge in the test of each “share” is either
the input of the image or a freshly sampled fake input (both with probability
$1/2$). In the _identical distribution style_ on the other hand, a fake input
is sampled before the tests and either both shares are tested with the input
of the image, or with this fake input.

######  Definition 17 (Piracy game for pseudorandom function copy-protection).

We define below a _piracy game for pseudorandom function copy-protection_ ,
parameterized by a pseudorandom function copy-protection scheme
$\langle\mathsf{KeyGen},\mathsf{Protect},\eval\rangle$ and a security
parameter $\secpar$. As the game in the product challenge bits style and the
game in the identical distribution style differ only in the challenge phase,
we define a different challenge phase for each style.

  * •

Setup phase:

    * –

The challenger samples $\key\in\mathsf{KeyGen}(\secparam)$ and computes
$\rho_{\key}\leftarrow\mathsf{Protect}(\secparam,\key)$.

    * –

The challenger samples $x\sample\mathcal{X}$ and computes $y:=\prf(\key,x)$.

    * –

The challenger sends $\rho_{\key}$ and $y$ to $\adv$.

  * •

Splitting phase: $\adv$ outputs a bipartite quantum state $\sigma_{12}$, as
well as two quantum circuits $\mathsf{U}_{1}$ and $\mathsf{U}_{2}$.

  * •

Challenge phase (product challenge bits style): The challenger performs the
following test on $(\sigma_{i},\mathsf{U}_{i})$ for $i\in\\{1,2\\}$:

    * –

sample $b\sample\bin$;

    * –

set $x_{0}:=x$ and sample $x_{1}\sample\mathcal{X}$.

    * –

run the circuit $\mathsf{U}_{i}$ on $\sigma_{i}\otimes{|x_{b}\rangle\\!\langle
x_{b}|}$ and check whether the outcome is $b$. If so, we say that
$(\sigma_{i},\mathsf{U}_{i})$ passes the test, otherwise that it does not.

  * •

Challenge phase (identical distribution style): The challenger samples a bit
$b\sample\bin$ and a fake input $x_{1}\sample\mathcal{X}$, then performs the
following test on $(\sigma_{i},\mathsf{U}_{i})$ for $i\in\\{1,2\\}$:

    * –

set $x_{0}:=x$;

    * –

run the circuit $\mathsf{U}_{i}$ on $\sigma_{i}\otimes{|x_{b}\rangle\\!\langle
x_{b}|}$ and check whether the outcome is $b$. If so, we say that
$(\sigma_{i},\mathsf{U}_{i})$ passes the test, otherwise that it does not.

$\adv$ wins the game if both $(\sigma_{1},\mathsf{U}_{1})$ and
$(\sigma_{2},\mathsf{U}_{2})$ pass the test.

We denote the random variable that indicates whether an adversary $\adv$ wins
the game or not as $\mathsf{CP-PRF-
AP}^{\langle\mathsf{KeyGen},\mathsf{Protect},\eval\rangle}_{\text{PCB}}(\secparam,\adv)$
or $\mathsf{CP-PRF-
AP}^{\langle\mathsf{KeyGen},\mathsf{Protect},\eval\rangle}_{\text{ID}}(\secparam,\adv)$
depending if we use the product challenge bits or the identical distribution
style.

######  Remark 4.

As said in Remark 2, we assume that the tests of each challenge phase are done
in a projective way.

######  Definition 18 (Indistinguishable anti-piracy security).

A pseudorandom function copy-protection scheme
$\langle\mathsf{KeyGen},\mathsf{Protect},\eval\rangle$ has _indistinguishable
anti-piracy security_ in the product challenge bits style if no QPT adversary
can win the piracy game above in the product challenge bits style with
probability significantly greater than $1/2$. More precisely, for any QPT
adversary $\adv$:

$\prob{\mathsf{CP-PRF-
AP}^{\langle\mathsf{KeyGen},\mathsf{Protect},\eval\rangle}_{\text{PCB}}(\secparam,\adv)=1}\leq
1/2+\negl.$

Furthermore, we say that such a scheme has _indistinguishable anti-piracy
security_ in the identical distribution style if no QPT adversary can win the
piracy game above in the identical distribution style with probability
significantly greater than $1/2$. More precisely, for any QPT adversary
$\adv$:

$\prob{\mathsf{CP-PRF-
AP}^{\langle\mathsf{KeyGen},\mathsf{Protect},\eval\rangle}_{\text{ID}}(\secparam,\adv)=1}\leq
1/2+\negl.$

######  Theorem 4.3.

Assuming the existence of post-quantum indistinguishability obfuscation, one-
way functions, and compute-and-compare obfuscation for the class of
unpredictable distributions, there exists a pseudorandom function copy-
protection scheme with indistinguishable anti-piracy security both in the
product challenge bits style and in the identical distribution style.

We present the construction that achieves this security in the two styles and
the corresponding proof in Appendix 0.A.

##  5 Copy-Protection of Point Functions in the Plain Model

In this section, we present the definition of copy-protection of point
functions. Then we present a construction of this primitive from [CHV23]. This
construction was proven secure for a non-colliding anti-piracy game’s
challenge distribution. We prove that the same construction is actually secure
for the product challenge distribution as well as the identical challenge
distribution.333We actually present a more general version of the construction
of [CHV23].Through all this section, $\secpar$ denotes a security parameter
and $n=\poly$.

###  5.1 Definitions

We consider copy-protection of point functions for a family of point functions
$\\{\mathsf{PF}_{y}\\}_{y\in\bin^{n}}$. We denote $\mathsf{PF}_{y}$ the point
function with point $y$, i.e. the function such that

$\mathsf{PF}_{y}(x)=\left\\{\begin{array}[]{ll}1&\text{ if }x=y\\\ 0&\text{
otherwise }\end{array}\right.$

######  Definition 19 (Point functions copy-protection scheme).

A copy-protection scheme of a family of point functions
$\\{\mathsf{PF}\\}_{y\in\bin^{n}}$ is a tuple of algorithms
$\langle\mathsf{Protect},\eval\rangle$ with the following properties:

  * •

$\rho_{y}\leftarrow\mathsf{Protect}(\secparam,y)$. On input a point
$y\in\bin^{n}$, the quantum protection algorithm outputs a quantum state
$\rho_{y}$.

  * •

$b\leftarrow\eval(\secparam,\rho,x)$. On input a quantum state $\rho$ and an
input $x\in\bin^{n}$, the quantum evaluation algorithm outputs a bit
$b\in\bin$.

#### Correctness.

A point functions copy-protection scheme has _correctness_ if the quantum
protection of any point function $\mathsf{PF}_{y}$ computes $\mathsf{PF}_{y}$
on every $x$ with overwhelming probability.

$\forall y\in\bin^{n},\ \forall x\in\bin^{n},\
\textnormal{Pr}\left[\eval(\secparam,\rho_{y},x)=\mathsf{PF}_{y}(x)\ :\
\rho_{y}\leftarrow\mathsf{Protect}(\secparam,y)\right]=1-\negl$

#### Anti-piracy security.

We now define anti-piracy security of a point functions copy-protection
scheme. This notion is defined through a piracy game, in which the adversary
is given a quantum copy-protection of a point function $\prf_{y}$ and must
split it such that both shares can be used to evaluate the function correctly.
We consider two variants of this security notion, namely _anti-piracy security
with respect to the product distribution_ and _anti-piracy security with
respect to the identical distribution_. In the first variant, the challenge in
the test of each share is either the point $y$ or another freshly sampled
random point; in the second variant, a random point $x$ is sampled before the
tests, and either both shares are tested with $y$ or both are tested with $x$.

######  Definition 20 (Piracy game for copy-protection of point functions).

We define below a _piracy game for copy-protection of point functions_ ,
parameterized by a copy-protection scheme
$\mathsf{CP}=\langle\mathsf{Protect},\eval\rangle$ and a security parameter
$\secpar$. This game is between a challenger and an adversary $\adv$. As the
two variants of the game differ only in the challenge phase, we describe below
a different challenge phase for each variant.

  * •

Setup phase:

    * –

The challenger samples $y\in\bin^{n}$ and computes
$\rho_{y}\leftarrow\mathsf{Protect}(\secparam,y)$.

    * –

The challenger then sends $\rho_{y}$ to $\adv$.

  * •

Splitting phase: $\adv$ outputs a bipartite quantum state $\sigma_{12}$ as
well as two quantum circuits $\mathsf{U}_{1}$ and $\mathsf{U}_{2}$.

  * •

Challenge phase (product distribution): For $i\in\\{1,2\\}$, the challenger
performs the following test on $(\sigma_{i},\mathsf{U}_{i})$:

    * –

sample $b\sample\bin$;

    * –

set $x_{0}:=y$ and sample $x_{1}\sample\bin^{n}$;

    * –

run $\mathsf{U}_{i}$ on $\sigma_{i}\otimes{|x_{b}\rangle\\!\langle x_{b}|}$
and check whether the outcome is $b$. If so, we say that
$(\sigma_{i},\mathsf{U}_{i})$ passes the test, otherwise that it does not.

  * •

Challenge phase (identical distribution): The challenger samples a bit
$b\sample\bin$ and an input $x_{1}\sample\bin^{n}$ and performs the following
test on $(\sigma_{i},\mathsf{U}_{i})$ for $i\in\\{1,2\\}$:

    * –

set $x_{0}:=y$;

    * –

run $\mathsf{U}_{i}$ on $\sigma_{i}\otimes{|x_{b}\rangle\\!\langle x_{b}|}$
and check whether the outcome is $b$. If so, we say that
$(\sigma_{i},\mathsf{U}_{i})$ passes the test, otherwise that it does not.

$\adv$ wins the game if both $(\sigma_{1},\mathsf{U}_{1})$ and
$(\sigma_{2},\mathsf{U}_{2})$ pass the test. We denote the random variable
that indicates whether an adversary $\adv$ wins the game or not as
$\mathsf{CP-
AP}^{\langle\mathsf{Protect},\eval\rangle}_{\text{PD}}(\secparam,\adv)$ or as
$\mathsf{CP-
AP}^{\langle\mathsf{Protect},\eval\rangle}_{\text{ID}}(\secparam,\adv)$
depending on which variant is considered in the game.

######  Remark 5.

As said in Remark 2, we assume that the tests of the challenge phase are done
in a projective way.

######  Definition 21 (Anti-piracy security).

A point functions copy-protection scheme
$\langle\mathsf{Protect},\eval\rangle$ has _anti-piracy security_ with respect
to the product distribution if no QPT adversary can win the piracy game above
with probability significantly greater than $1/2$. More precisely, for any QPT
adversary $\adv$:

$\prob{\mathsf{CP-
AP}^{\langle\mathsf{Protect},\eval\rangle}_{\text{PD}}(\secparam,\adv)=1}\leq
1/2+\negl.$

Furthermore, we say that a point functions copy-protection scheme
$\langle\mathsf{Protect},\eval\rangle$ has _anti-piracy security_ with respect
to the identical distribution if no QPT adversary can win the piracy game
above with probability significantly greater than $1/2$. More precisely, for
any QPT adversary $\adv$:

$\prob{\mathsf{CP-
AP}^{\langle\mathsf{Protect},\eval\rangle}_{\text{ID}}(\secparam,\adv)=1}\leq
1/2+\negl.$

###  5.2 Construction

In this subsection, we present a construction for copy-protection of point
functions. This construction uses a pseudorandom functions copy-protection
scheme $\prf.\langle\mathsf{KeyGen},\mathsf{Protect},\eval\rangle$.

Copy-Protection of Point Functionscp-cc-from-cp-prf

  * •

$\mathsf{Protect}(\secparam,y)$:

    * –

Sample $\key\leftarrow\prf.\mathsf{KeyGen}(\secparam)$.

    * –

Compute $\rho_{\key}\leftarrow\prf.\mathsf{Protect}(\key)$.

    * –

Compute $z:=\prf(\key,y)$.

    * –

Return $(\rho_{\key},z)$.

  * •

$\eval(\secparam,(\rho,z),x)$:

    * –

Compute $z^{\prime}\leftarrow\prf.\eval(\rho,x)$.

    * –

If $z^{\prime}=z$: return 1.

    * –

Otherwise: return 0.

######  Theorem 5.1.

Assuming the underlying pseudorandom functions copy-protection scheme has
anti-piracy security in the product challenge bits style, LABEL:constr:cp-cc-
from-cp-prf has correctness and anti-piracy security with respect to the
product distribution.

######  Theorem 5.2.

Assuming the underlying pseudorandom functions copy-protection scheme has
anti-piracy security in the identical distribution style, LABEL:constr:cp-cc-
from-cp-prf has correctness and anti-piracy security with respect to the
identical distribution.

###### Proof of Theorems 5.1 and 5.2.

(Correctness) for any $y$, running the evaluation algorithm on the point $y$
yields $1$ with probability close to $1$ from the correctness of the
underlying copy-protection of pseudorandom functions. Running the evaluation
algorithm on a point $x\neq y$ yields $1$ only if
$\prf.\eval(\rho_{\key},x)=\prf(\key,y)$, which happens with negligible
probability over $\key$ from the security of the underlying pseudorandom
function.

(Anti-piracy security) the anti-piracy security with respect to the product
distribution (resp. identical distribution) comes directly from the anti-
piracy security in the single image style (resp. identical distribution style)
of the underlying copy-protection of pseudorandom function scheme. In both
cases, the reduction is simply the identity. ∎

######  Corollary 2.

Assuming the existence of post-quantum indistinguishability obfuscation, one-
way functions, and compute-and-compare obfuscation for the class of
unpredictable distributions, there exists a point functions copy-protection
scheme with correctness and anti-piracy security with respect to both the
product and the identical distribution.

###### Proof.

This result follows directly from Theorem 4.3. ∎

##  6 Unclonable Encryption in the Plain Model

In this section, we introduce the notion of unclonable encryption and present
a construction in the plain model. Our construction uses a pseudorandom
function copy-protection scheme with anti-piracy security in the identical
distribution style (Definition 18) as a black box. Our construction is a
symmetric one-time unclonable encryption scheme, which implies the existence
of a reusable public key encryption scheme using the transformation of [AK21].

###  6.1 Definitions

In this section, we define unclonable encryption as well as its correctness
and indistinguishable anti-piracy security.

######  Definition 22 (Symmetric one-time unclonable encryption scheme).

An symmetric one-time unclonable encryption scheme with message space
$\mathcal{M}$ is a tuple of algorithms
$\langle\mathsf{KeyGen},\enc,\dec\rangle$ with the following properties:

  * •

$\key\leftarrow\mathsf{KeyGen}(\secparam)$. On input a security parameter, the
key generation algorithm outputs a key $\key$.

  * •

$\rho\leftarrow\enc(\key,m)$. On input a key $\key$ and a message
$m\in\mathcal{M}$, the encryption algorithm outputs quantum ciphertext $\rho$.

  * •

$m\leftarrow\dec(\key,\rho)$. On input a key $\key$ and a quantum ciphertext
$\rho$, the decryption algorithm outputs a message $m$.

#### Correctness.

An unclonable encryption scheme has _correctness_ if decrypting a quantum
encryption of any message $m$ yields $m$ with overwhelming probability. More
precisely:

$\forall m\in\mathcal{M},\ \textnormal{Pr}\left[\dec(\key,\rho)=m\ :\
\begin{array}[]{l}\key\leftarrow\mathsf{KeyGen}(\secparam)\\\
\rho\leftarrow\enc(\key,m)\end{array}\right]=1-\negl$

#### Indistinguishable anti-piracy security.

We now define indistinguishable anti-piracy security of a symmetric one-time
unclonable encryption scheme. This notion is defined through a game in which
an adversary is given a quantum encryption of either $m_{0}$ or $m_{1}$ \- two
messages that parametrize the game - and is asked to split it such that both
shares can be used to guess which message has been encrypted.444As in the
other unclonable primitives’ definitions, the decryption procedure used on the
share is not necessarily the original one $\dec$ but is provided by the
adversary as a quantum circuit.Note that that although our definition holds
for _one-time_ unclonable encryption schemes, we can similarly define this
notion for _reusable_ unclonable encryption schemes by giving the adversary
access to an encryption oracle, and then letting them choose the pair of
messages $(m_{0},m_{1})$.

######  Definition 23 (Piracy game for a symmetric one-time unclonable
encryption scheme).

We define below a _piracy game for symmetric one-time unclonable encryption_ ,
parameterized by a symmetric one-time unclonable encryption scheme
$\langle\mathsf{KeyGen},\enc,\dec\rangle$, a security parameter $\secpar$, and
a pair of messages $(m_{0},m_{1})$. This game is between a challenger and an
adversary $\adv$.

  * •

Setup phase:

    * –

The challenger samples $\key\in\mathsf{KeyGen}(\secparam)$ and $b\sample\bin$,
and computes $\rho\leftarrow\enc(\key,m_{b})$.

    * –

The challenger sends $\rho$ to $\adv$.

  * •

Splitting phase: $\adv$ outputs a bipartite quantum state $\sigma_{12}$, as
well as two quantum circuits $\mathsf{U}_{1}$ and $\mathsf{U}_{2}$.

  * •

Challenge phase: For $i\in\\{1,2\\}$, the challenger performs the following
test on $(\sigma_{i},\mathsf{U}_{i})$:

    * –

Run the circuit $\mathsf{U}_{i}$ on
$\sigma_{i}\otimes{|\key\rangle\\!\langle\key|}$ and checks whether the
outcome is $b$. If so, we say that $(\sigma_{i},\mathsf{U}_{i})$ passes the
test, otherwise that it does not.

$\adv$ wins the game if both $(\sigma_{1},\mathsf{U}_{1})$ and
$(\sigma_{2},\mathsf{U}_{2})$ pass the test.

We denote the random variable that indicates whether an adversary $\adv$ wins
the game or not as $\mathsf{UncEnc-
AP}^{\langle\mathsf{KeyGen},\enc,\dec\rangle}_{(m_{0},m_{1})}(\secparam,\adv)$.

######  Definition 24 (Indistinguishable anti-piracy security of an unclonable
encryption scheme).

A symmetric one-time unclonable encryption scheme
$\langle\mathsf{KeyGen},\enc,\dec\rangle$ has _indistinguishable anti-piracy
security_ if, for any pair of messages $(m_{0},m_{1})$, no QPT adversary can
win the piracy game above with probability significantly greater than $1/2$.

More precisely, for any QPT adversary $\adv$

$\prob{\mathsf{UncEnc-
AP}^{\langle\mathsf{KeyGen},\enc,\dec\rangle}_{(m_{0},m_{1})}(\secparam,\adv)=1}\leq
1/2+\negl.$

###  6.2 Construction

In this subsection, we present a construction of a symmetric one-time
unclonable encryption scheme for single-bit messages. Through all the
subsection, $\secpar$ denotes a security parameter and $n(\cdot),m(\cdot)$ are
polynomials; whenever it is clear from the context, we note $n$ and $m$
instead of $n(\secpar)$ and $m(\secpar)$. Let
$\prf.\langle\mathsf{KeyGen},\mathsf{Protect},\eval\rangle$ be a pseudorandom
function copy-protection scheme with input space $\bin^{n}$ and output space
$\bin^{m}$. In addition, we ask the copy-protected pseudorandom function to be
extracting with error $2^{-\lambda-1}$ for min-entropy $n$. Note that the
copy-protected pseudorandom function presented in Appendix 0.A has this
property.

Unclonable Encryptionunc-enc

  * $\mathsf{KeyGen}(\secparam)$:

    * –

Sample a key $\key_{S}\sample\bin^{n}$.

    * –

Return $\key_{S}$.

  * $\enc(\key_{S},b)$:

    * –

Sample $\key_{P}\leftarrow\prf.\mathsf{KeyGen}(\secparam)$ and compute
$\rho_{\key_{P}}\leftarrow\prf.\mathsf{Protect}(\key_{P})$.

    * –

Sample $r\sample\bin^{n}$; let $c_{0}\leftarrow\prf(\key_{P},k_{S}\oplus r)$
and $c_{1}\sample\bin^{m}$.

    * –

Return $(r,c_{b},\rho_{\key_{P}})$.

  * $\dec(\key_{S},(r,c,\rho_{\key_{P}}))$:

    * –

Compute $c^{*}\leftarrow\prf(\key_{P},\key_{S}\oplus r)$.

    * –

Return $0$ if $c^{*}=c$ and $1$ otherwise.

######  Theorem 6.1.

Assume $\prf.\langle\mathsf{KeyGen},\mathsf{Protect},\eval\rangle$ has
indistinguishable anti-piracy security in the identical distribution style
security (Definition 18). Then LABEL:constr:unc-enc has correctness and
indistinguishable anti-piracy security.

#### Proof of correctness.

The correctness comes directly from the correctness and security of the
underlying $\prf$ copy-protection scheme. More precisely,
$\dec(\key_{S},\enc(\key_{S},0))=1$ means that
$\prf.\eval(\rho_{\key_{P}},\key_{S}\oplus r)\neq\prf(\key_{P},\key_{S}\oplus
r)$ which happens with negligible probability from the correctness of the
$\prf$ copy-protection scheme. And $\dec(\key_{S},\enc(\key_{S},1))=0$ means
that $\prf.\eval(\rho_{\key_{P}},\key_{S}\oplus r)=y$ for a uniformly random
$y$ happens with non-negligible probability, which contradicts $\prf$
security.

#### Proof of indistinguishable anti-piracy security.

We proceed in the proof through a sequence of hybrids. For any pair of hybrids
$(G_{i},G_{j})$, we say that $G_{i}$ is negligibly close to $G_{j}$ if for
every QPT adversary $\adv\coloneqq(\adv_{0},\adv_{1},\adv_{2})$, the
probability that $\adv$ wins $G_{i}$ is negligibly close to the probability
that they win $G_{j}$.

  1. Game $G_{\thepcgamecounter}\gameprocedurearg$:

The first hybrid is the piracy game for our construction.

     * •

Setup phase:

       * –

The challenger samples $\key_{S}\sample\bin^{n}$;

       * –

The challenger samples $\key_{P}\leftarrow\prf.\mathsf{KeyGen}(\secparam)$ and
computes $\rho_{\key_{P}}\leftarrow\prf.\mathsf{Protect}(\key_{P})$;

       * –

The challenger samples $r\sample\bin^{n}$, then sets
$c_{0}\leftarrow\prf(\key_{P},k_{S}\oplus r)$ and samples
$c_{1}\sample\bin^{m}$;

       * –

The challenger samples $b\sample\bin$ and sends $(r,c_{b},\rho_{\key_{P}})$ to
$\adv$.

     * •

Splitting phase: $\adv$ outputs a bipartite quantum state $\sigma_{12}$, as
well as two quantum circuits $\mathsf{U}_{1}$ and $\mathsf{U}_{2}$.

     * •

Challenge phase: For $i\in\\{1,2\\}$, the challenger performs the following
test on $(\sigma_{i},\mathsf{U}_{i})$:

       * –

Run the circuit $\mathsf{U}_{i}$ on
$\sigma_{i}\otimes{|\key_{S}\rangle\\!\langle\key_{S}|}$ and checks whether
the outcome is $b$. If so, we say that $(\sigma_{i},\mathsf{U}_{i})$ passes
the test, otherwise that it does not.

$\adv$ wins the game if both $(\sigma_{1},\mathsf{U}_{1})$ and
$(\sigma_{2},\mathsf{U}_{2})$ pass the test.

  2. Game $G_{\thepcgamecounter}\gameprocedurearg$:

In the second hybrid, we replace $c_{1}$ by the pseudorandom function
evaluation of a random input. More formally, in the setup phase, we replace
$c_{1}\sample\bin^{m}$ by $c_{1}:=\prf(\key_{P},x)$ where $x\sample\bin^{m}$.
As $x$ is sampled uniformly at random, from the extracting property of the
underlying pseudorandom function, $G_{0}$ is negligibly close to $G_{1}$.

  3. Game $G_{\thepcgamecounter}\gameprocedurearg$:

In this third hybrid, we replace the random $x$ by $\key^{\prime}_{S}\oplus r$
where $\key^{\prime}_{S}$ is sampled uniformly at random from $\bin^{n}$. As
$\key^{\prime}_{S}\oplus r$ is still uniformly random, this does not change
the overall distribution of the game. Thus, $G_{2}$ is negligibly close to
$G_{1}$ (more precisely, it is exactly the same game).

  4. Game $G_{\thepcgamecounter}\gameprocedurearg$:

For the third hybrid, instead of sending either $\prf(\key_{P},\key_{S}\oplus
r)$ or $\prf(\key_{P},\key^{\prime}_{S}\oplus r)$ \- depending on $b$ \- to
the adversary in the setup phase, and testing each
$(\mathsf{U}_{i},\sigma_{i})$ on $\key_{S}$, we send only
$\prf(\key_{P},\key_{S}\oplus r)$ to the adversary in the setup phase and
perform the tests on either $\key_{S}$ or $\key^{\prime}_{S}$ \- still
depending on $b$. Note that this is actually only relabelling, hence the
distribution of the game is not changed either. Thus the $G_{3}$ has exactly
the same distribution as $G_{2}$. We describe $G_{3}$ more precisely below:

     * •

Setup phase:

       * –

The challenger samples $\key_{S},\key^{\prime}_{S}\sample\bin^{n}$;

       * –

The challenger samples $\key_{P}\leftarrow\prf.\mathsf{KeyGen}(\secparam)$ and
computes $\rho_{\key_{P}}\leftarrow\prf.\mathsf{Protect}(\key_{P})$;

       * –

The challenger samples $r\sample\bin^{n}$, and sends
$(r,\prf(\key_{P},k_{S}\oplus r),\rho_{\key_{P}})$ to $\adv$.

     * •

Splitting phase: $\adv$ outputs a bipartite quantum state $\sigma_{12}$, as
well as two quantum circuits $\mathsf{U}_{1}$ and $\mathsf{U}_{2}$.

     * •

Challenge phase: The challenger samples $b\sample\bin$, sets
$\key_{0}:=\key_{S}$ and $\key_{1}:=\key^{\prime}_{S}$, then performs the
following test on $(\sigma_{i},\mathsf{U}_{i})$ for $i\in\\{1,2\\}$:

       * –

Run the circuit $\mathsf{U}_{i}$ on
$\sigma_{i}\otimes{|\key_{b}\rangle\\!\langle\key_{b}|}$ and checks whether
the outcome is $b$. If so, we say that $(\sigma_{i},\mathsf{U}_{i})$ passes
the test, otherwise that it does not.

$\adv$ wins the game if both $(\sigma_{1},\mathsf{U}_{1})$ and
$(\sigma_{2},\mathsf{U}_{2})$ pass the test.

We now reduce the game $G_{3}$ from the piracy game of the underlying
pseudorandom function copy-protection scheme in the identical distribution
style. Assume that there exists a QPT adversary $\adv$ who wins $G_{3}$ with
advantage $\delta$. We construct a QPT adversary $\bdv$ who wins the piracy
game of the underlying pseudorandom function copy-protection scheme in the
identical distribution style with the same advantage $\delta$. $\bdv$ behaves
in the following way; on input a quantum protected pseudorandom function key
$\rho_{\key}$ and a pseudorandom function image $y:=\prf(\key,x)$:

  * •

$\bdv$ sends $\rho_{\key}$ and $y$ to $\adv$; let
$\sigma_{12},\mathsf{U}_{1},\mathsf{U}_{2}$ denote the outcome.

  * •

$\bdv$ prepares the circuits
$(\mathsf{U}^{\prime}_{1},\mathsf{U}^{\prime}_{2})$ described below using
$\mathsf{U}_{1}$ and $\mathsf{U}_{2}$ respectively.

  * •

Finally, $\bdv$ outputs $\sigma_{12}$ as the shares and
$\mathsf{U}^{\prime}_{1},\mathsf{U}^{\prime}_{2}$ as the quantum circuits.

Hardcoded: Circuit $\mathsf{U}_{i}$. On input quantum state
$\sigma_{i}\otimes{|x\rangle\\!\langle x|}$ and $\prf$ input $x$, do the
following: 1. Compute $\key:=r\oplus x$. 2. Run $\mathsf{U}_{i}$ on
$(\sigma_{1},\key)$. 3. Return the outcome. Figure 3: Circuit
$\mathsf{U}^{\prime}_{i}$.

The inputs of $\mathsf{U}_{1}$ and $\mathsf{U}_{2}$ in circuits
$\mathsf{U}^{\prime}_{1}$ and $\mathsf{U}^{\prime}_{2}$ follow the same
distribution as the inputs for $\mathsf{U}_{1}$ and $\mathsf{U}_{2}$ in
$G_{3}$. Thus $\bdv$ wins the game with the same advantage as $\adv$, which
concludes the proof.

######  Corollary 3.

Assuming the existence of post-quantum indistinguishability obfuscation, one-
way functions, and compute-and-compare obfuscation for the class of
unpredictable distributions, there exists a symmetric one-time unclonable
encryption scheme with correctness and indistinguishable anti-piracy security.

###  6.3 Extension to Multi-bits Messages

We describe below a way to extend our scheme to any message space of the form
$\bin^{\ell}$ where $\ell(\cdot)$ is a polynomial in $\secpar$. Our
construction encrypts the message bit by bit, but not in an independent way.
Indeed, we use the same pseudorandom function key for encrypting all the bits
(and hence the same copy-protected pseudorandom function key); and show that
this is enough to achieve indistinguishable anti-piracy security.

Unclonable Encryption with Message Space $\bin^{\ell}$unc-enc-multibits

  * $\mathsf{KeyGen}(\secparam)$:

    * –

For $i\in\llbracket 1,\ell\rrbracket$: sample a key
$\key_{S,i}\sample\bin^{n}$.

    * –

Return $\key_{S}:=\left(\key_{S,i}\right)_{i\in\llbracket 1,\ell\rrbracket}$.

  * $\enc(\key_{S},m)$:

    * –

Sample $\key_{P}\leftarrow\prf.\mathsf{KeyGen}(\secparam)$ and compute
$\rho_{\key_{P}}\leftarrow\prf.\mathsf{Protect}(\key_{P})$.

    * –

For $i\in\llbracket 1,\ell\rrbracket$: sample $r_{i}\sample\bin^{n}$ and
compute $y_{i}:=\key_{S,i}\oplus r_{i}$.

    * –

Let $c_{0,i}\leftarrow\prf(\key_{P},y_{i})$ and $c_{1,i}\sample\bin^{m}$.

    * –

Let $r:=\left(r_{i}\right)_{i\in\llbracket 1,\ell\rrbracket}$ and
$c_{m}:=\left(c_{m_{i},i}\right)_{i\in\llbracket 1,\ell\rrbracket}$.

    * –

Return $(r,c_{m},\rho_{\key_{P}})$.

  * $\dec(\key_{S},(r,c,\rho_{\key_{P}}))$:

    * –

For $i\in\llbracket 1,\ell\rrbracket$: compute $y_{i}:=\key_{S,i}\oplus r_{i}$
and $c^{*}_{i}\leftarrow\prf(\key_{P},y_{i})$.

    * –

Set $m\in\bin^{\ell}$ such that $m_{i}:=0$ if $c^{*}_{i}=c_{i}$ and $m_{i}:=1$
otherwise.

    * –

Return $m$

######  Theorem 6.2.

Assume $\prf.\langle\mathsf{KeyGen},\mathsf{Protect},\eval\rangle$ has
indistinguishable anti-piracy security in the identical distribution style.
Then LABEL:constr:unc-enc-multibits has correctness and indistinguishable
anti-piracy security.

###### Proof.

The correctness proof is the same as for the single-bit version: it relies on
correctness and security of the underlying pseudorandom function copy-
protection scheme.

We give a short summary of the proof of anti-piracy security, as it uses a
usual hybrids argument. By doing small hops, we show that if no adversary can
distinguish between the encryption of two messages differing on only one
index, then no adversary can distinguish between the encryption of two
messages differing on only two indices, and so on and so forth until finally
showing that no adversary can distinguish between the encryption of two
messages differing on all indices. It then remains to show that no adversary
can distinguish between the encryption of two messages differing only on one
index, which follows from the anti-piracy security of the pseudorandom
function copy-protection scheme. ∎

######  Corollary 4.

Assuming the existence of post-quantum indistinguishability obfuscation, one-
way functions, and compute-and-compare obfuscation for the class of
unpredictable distributions, there exists a public-key reusable unclonable
encryption scheme with correctness and indistinguishable anti-piracy security.

###### Proof.

In [AK21, Section 5], the authors present a way to construct a public-key
reusable one-time unclonable encryption scheme from any symmetric one-time
unclonable encryption scheme with indistinguishable anti-piracy security,
using a (post-quantum) symmetric encryption scheme with pseudorandom
ciphertexts and a (post-quantum) single-key public-key functional encryption
scheme. We refer the interested reader to this paper for a description of the
construction. ∎

## References

  * [Aar09] Scott Aaronson.  Quantum copy-protection and quantum money.  In 2009 24th Annual IEEE Conference on Computational Complexity, pages 229–242. IEEE, 2009.
  * [AB23] Prabhanjan Ananth and Amit Behera.  A modular approach to unclonable cryptography, 2023.  https://arxiv.org/abs/2311.11890.
  * [AK21] Prabhanjan Ananth and Fatih Kaleoglu.  Unclonable encryption, revisited.  In Kobbi Nissim and Brent Waters, editors, TCC 2021, Part I, volume 13042 of LNCS, pages 299–329. Springer, Heidelberg, November 2021\.
  * [AKL+22] Prabhanjan Ananth, Fatih Kaleoglu, Xingjian Li, Qipeng Liu, and Mark Zhandry.  On the feasibility of unclonable encryption, and more.  In Yevgeniy Dodis and Thomas Shrimpton, editors, CRYPTO 2022, Part II, volume 13508 of LNCS, pages 212–241. Springer, Heidelberg, August 2022.
  * [AKL23] Prabhanjan Ananth, Fatih Kaleoglu, and Qipeng Liu.  Cloning games: A general framework for unclonable primitives.  In Helena Handschuh and Anna Lysyanskaya, editors, CRYPTO 2023, Part V, volume 14085 of LNCS, pages 66–98. Springer, Heidelberg, August 2023.
  * [AL21] Prabhanjan Ananth and Rolando L. La Placa.  Secure software leasing.  In Anne Canteaut and François-Xavier Standaert, editors, EUROCRYPT 2021, Part II, volume 12697 of LNCS, pages 501–530. Springer, Heidelberg, October 2021.
  * [BB20] Charles H Bennett and Gilles Brassard.  Quantum cryptography: Public key distribution and coin tossing.  arXiv preprint arXiv:2003.06557, 2020.
  * [BGI+01] Boaz Barak, Oded Goldreich, Russell Impagliazzo, Steven Rudich, Amit Sahai, Salil P. Vadhan, and Ke Yang.  On the (im)possibility of obfuscating programs.  In Joe Kilian, editor, CRYPTO 2001, volume 2139 of LNCS, pages 1–18. Springer, Heidelberg, August 2001.
  * [BGI14] Elette Boyle, Shafi Goldwasser, and Ioana Ivan.  Functional signatures and pseudorandom functions.  In Hugo Krawczyk, editor, PKC 2014, volume 8383 of LNCS, pages 501–519. Springer, Heidelberg, March 2014.
  * [BJL+21] Anne Broadbent, Stacey Jeffery, Sébastien Lord, Supartha Podder, and Aarthi Sundaram.  Secure software leasing without assumptions.  In Kobbi Nissim and Brent Waters, editors, TCC 2021, Part I, volume 13042 of LNCS, pages 90–120. Springer, Heidelberg, November 2021\.
  * [BL20] Anne Broadbent and Sébastien Lord.  Uncloneable Quantum Encryption via Oracles.  158:4:1–4:22, 2020.