# A Note on Copy-Protection from Random Oracles

Prabhanjan Ananth
UCSB<EMAIL_ADDRESS>Fatih Kaleoglu
UCSB<EMAIL_ADDRESS>
###### Abstract

Quantum copy-protection, introduced by Aaronson (CCC’09), uses the no-cloning
principle of quantum mechanics to protect software from being illegally
distributed. Constructing copy-protection has been an important problem in
quantum cryptography.

Since copy-protection is shown to be impossible to achieve in the plain model,
we investigate the question of constructing copy-protection for arbitrary
classes of unlearnable functions in the random oracle model. We present an
impossibility result that rules out a class of copy-protection schemes in the
random oracle model assuming the existence of quantum fully homomorphic
encryption and quantum hardness of learning with errors. En route, we prove
the impossibility of approximately correct copy-protection in the plain model.

##  1 Introduction

Quantum copy-protection, introduced by Aaronson [Aar09], is a foundational
concept in quantum cryptography. It stipulates that the no-cloning principle
of quantum mechanics [Die82, WZ82] can be employed to protect against illegal
distribution of software. In more detail, an efficient adversary, on input a
copy-protected software (represented as a quantum state), cannot create two
copies of software, possibly entangled with each other, such that both copies
compute the same functionality as the original software.

The primitive of copy-protection can be classified under the broad area of
unclonable cryptography, which deals with using the no-cloning principle to
design cryptographic primitives with security properties that are classically
unachievable. Many interesting primitives in this category, such as quantum
money [Wie83, AC12, Zha19b, RS19], one-shot signatures [AGKZ20], single-
decryptor encryption [GZ20, CLLZ21], unclonable encryption [Got02, BL20], and
encryption with certifiable deletion [BI20], can be seen as copy-protecting
specific functionalities.

The focus of our work is on understanding the feasibility of constructing
copy-protection for all classes of unlearnable functions. Ananth and La Placa
[ALP21] show that there are functions that cannot be copy-protected in the
plain model. Thus, one has to rely on alternate models to construct copy-
protection.

In this work, we restrict our attention to the random oracle model.
Interestingly, random oracles have been helpful for achieving copy-protection
for specific classes of functions. Coladangelo, Majenz and Poremba [CMP20]
showed the existence of copy-protection for multi-bit output functions in the
random oracle model. Ananth, Kaleoglu, Liu, Li and Zhandry [AKL+22] presented
a new construction of copy-protection for single-bit output point functions
also in the random oracle model. However, the existence of copy-protection for
all classes of unlearnable functions in the random oracle model is still yet
to be explored.

Before we delve into this direction further, we first need to model the type
of access the algorithms in the copy-protection scheme and the adversarial
entities will have, with the random oracle. There are two types of accesses we
can consider. The first one is classical access, where the interface is
entirely classical: the algorithms submit a binary string $x$ to the oracle
and get back $f(x)$, where $f$ is a classical random function implemented by
the oracle. We will refer to this setting as _classical-accessible random
oracle model_ (CAROM). The second type is quantum access: the algorithms
submit a query of the form
$\sum_{x\in\\{0,1\\}^{n}}\alpha_{x}|x\rangle|y_{x}\rangle$ and get back
$\sum_{x\in\\{0,1\\}^{n}}\alpha_{x}|x\rangle|f(x)\oplus y_{x}\rangle$. This
setting was defined by Boneh, Dagdelen, Fischlin, Lehmann, Schaffner and
Zhandry [BDF+11] as the _quantum random oracle model_ (QROM).

As argued in [BDF+11], QROM is the preferred model over CAROM under most
circumstances. For instance, if the adversary has access to any classical code
that computes the function $f$, then it can always run this code coherently,
thus achieving quantum access. Nonetheless, as per the impossibility result of
[ALP21], one cannot simply instantiate a generic copy-protection scheme in
QROM by replacing the random function $f$ with a concrete function, e.g. a
heuristically secure hash function such as SHA-512 or an obfuscated
pseudorandom function. In contrast, classical-access is appropriate for
alternative methods of instantiation, such as using trusted hardware or a
trusted party, where classical interface can be enforced. Therefore, we argue
that achieving copy-protection in CAROM is still meaingful.

###  1.1 Our Result

We make progress towards understanding the feasibility of copy-protection in
the random oracle model. It turns out that proving impossibility of copy-
protection in the QROM seems quite challenging and thus, we focus on the CAROM
setting. Note that QROM and CAROM are incomparable models, since QROM gives
more power to both the honest algorithms and the adversary.

We show that copy-protection of arbitrary unlearnable functions is impossible
in CAROM. This implies that if copy-protection is possible with a random
oracle, then honest algorithms must query the oracle in superposition.

######  Theorem 1.

Assuming unbounded fully homomorphic encryption for quantum computations
[Mah18, Bra18] and quantum hardness of learning with errors (QLWE), there
exists a class of unlearnable functions ${\cal F}$ such that quantum copy-
protection for ${\cal F}$ is impossible in CAROM.

The above result suggests that if one were to base copy-protection in the
classical-accessible oracle models then the oracle needs to have some
structure. We note that in both the works of [CMP20] and [AKL+22], the copy-
protection algorithm only makes classical queries to the oracle whereas the
evaluation algorithm makes quantum queries.

At the heart of the above theorem is a new impossibility result for copy-
protection in the plain model. Specifically, we show that even copy-protection
with approximate correctness can be ruled out in the plain model (Theorem 17),
while prior works [ALP21, ABDS21] only ruled out copy-protection with
statistical correctness.

We combine this impossibility result with a generic transformation from a
copy-protection scheme in CAROM to an approximate copy-protection scheme in
the plain model (Lemma 21) to rule out copy-protection of arbitrary
unlearnable functions in CAROM (Theorem 22). Our transformation crucially
relies on recording the oracle queries of the honest algorithms and efficient
simulation of a random oracle consistent with a prerecorded database.
Recording quantum queries to a random oracle can be achieved using Zhandry’s
compressed oracle technique [Zha19a], but to our knowledge it is not known how
to efficiently simulate a quantum random oracle consistent with a prerecorded
database. Therefore, any construction in QROM where honest parties make
superposition queries to the oracle would circumvent our impossibility result.

###  1.2 Related Work

Aaronson [Aar09] was the first to study copy-protection in the oracle models.
Their construction relied upon oracles implementing quantum functionalities.
Recently, Aaronson, Liu, Liu, Zhandry and Zhang [ALL+21] constructed copy-
protection in a quantum-accessible oracle model. As mentioned earlier, two
works [CMP20, AKL+22] present constructions of copy-protection for point
functions in the quantum random oracle model.

In a recent exciting work, Coladangelo, Liu, Liu and Zhandry [CLLZ21] proposed
the first construction of copy-protection for a restricted class of functions,
namely pseudorandom functions, in the plain model, based on post-quantum
indistinguishability obfuscation and post-quantum one-way functions. Another
work by Ananth and Kaleoglu [AK21] present a construction of approximately
correct copy-protection for a class of point functions from post-quantum one-
way functions. Some recent works [ALP21, ALL+21, KNY21, BJL+21] present
constructions of weaker notions of copy-protection.

##  2 Overview of Techniques

In this section, we explain the main ideas behind our result. Inspired by the
ideas developed in the program obfuscation literature [BV16, CKP15], we design
a two step approach to proving this impossibility result.

  * •

Ruling out approximate copy-protection in the plain model: In the first step,
we rule out a notion of copy-protection where correctness is only guaranteed
for a large constant fraction of inputs.

  * •

From CP using oracles to approximate CP in the plain model: In the second
step, we show that copy-protection in the classical-accessible random oracle
model implies approximate copy-protection in the plain model. In other words,
given any copy-protection in the classical-accessible random oracle model, we
can generically get rid of the random oracle model at the cost of weakening
the correctness guarantee.

##### Ruling out Approximate Copy-Protection.

We show that copy-protection, where correctness is guaranteed for a fraction
of inputs, say $(1-\varepsilon)$, is impossible to achieve in the plain model.
This strengthens the previous result [ALP21] which ruled out copy-protection
with correctness negligibly close to 1.

Our goal is to transform this scheme, call it $CP$, such that in the
transformed scheme, call it $CP^{\prime}$, on every input, the evaluation of
the copy-protected state is correct with probability $(1-\varepsilon)$ (i.e.,
per-input $(1-\varepsilon)$-correctness); assume for now, that $C$ is a
boolean circuit with 1-bit output. The scheme $CP^{\prime}$ is designed as
follows: to copy-protect $C$, compute a copy-protection of a circuit $G$, with
respect to the scheme $CP$, such that $G$ takes as input an encryption of $x$,
homomorphically computes $C$ on encryption of $x$ and outputs the result. The
output is copy-protection of $G$ along with the public key-secret key pair of
the encryption scheme. During the evaluation process of $CP^{\prime}$, first
encrypt the input $x$, run the $CP$ copy-protection of $G$ to obtain
encryption of $C(x)$ and finally, decrypt the answer to obtain $C(x)$ in the
clear.

This idea was notably developed by Bitansky and Vaikuntanathan [BV16] in the
context of indistinguishability obfuscation. To make this idea work, we would
need fully homomorphic encryption schemes for quantum computations (QFHE).
Moreover, we require the QFHE scheme to satisfy circuit privacy; that is, the
homomorphically evaluated ciphertext does not leak information about the
circuit being used during evaluation. This property is necessary because the
evaluator who obtains a classical description of the function can trivially
break the copy-protection security. Fortunately, a recent work by
Chardouvelis, Döttling, and Malavolta [CDM20] demonstrates the existence of a
QFHE scheme satisfying the circuit privacy property we need111We note that the
definition considered in [CDM20] is weak: for example, they do not even handle
adversaries who can entangle the quantum messages with their private state. We
provide a stronger definition in this paper and remark that the construction
provided in [CDM20] already satisfies this stronger definition..

Failure of Majority Argument. Suppose we manage to reduce the feasibility of
copy-protection with correctness over a $(1-\varepsilon)$-fraction of inputs
to per-input $(1-\varepsilon)$-correctness. The next step would be to rule out
copy-protection with per-input correctness. A natural attempt would be to
consider multiple copies of copy-protection and take a majority vote; this
would improve the correctness to be close to 1. While this argument would work
for program obfuscation, this unfortunately fails in the context of copy-
protection. The reason is simple: once you have many copies of copy-
protection, an adversary can now distribute each copy to a different
individual, thus breaking the security of copy-protection.

Thus, we need to figure out an alternate method to rule out quantum copy-
protection with per-input correctness guarantees. As done in prior works, we
rely upon non-black box techniques to rule out copy-protection. We need to be
especially careful when invoking non-black box arguments in the per-input
$(1-\varepsilon)$-correctness setting, as every evaluation of the copy-
protected state significantly degrades the correctness guarantee of the
original state. If $\varepsilon$ is the correctness error then after $k$
evaluations, the trace distance between the original state and the new state
is $k\sqrt{\varepsilon}$ (by quantum union bound). If
$k\geq\frac{1}{\sqrt{\varepsilon}}$ then the new state is useless. Luckily,
the quantum non-black box technique of [ALP21] involves the attacker only
making two evaluations of the copy-protected state.

In the technical sections, we combine the self-reducibility technique
(presented above) with the non-black box technique of [ALP21] to rule out
copy-protection for $(1-\varepsilon)$-fraction of inputs.

##### From CP using oracles to approximate CP.

The next step would be to rule out copy-protection in the classical-accessible
random oracle model. We rely upon “de-oracle-izing” techniques developed in
the context of obfuscation [CKP15]; the idea is to remove the use of random
oracle in the construction at the cost of weakening the correctness guarantee.
While the overall template is inspired from [CKP15], the actual construction
is different.

In more detail, given a copy-protection scheme $(\mathsf{CP},\mathsf{Eval})$
in the classical-accessible random oracle model, where $\mathsf{CP}$
represents the copy-protection algorithm and $\mathsf{Eval}$ represents the
evaluation algorithm, define a copy-protection scheme
$(\widetilde{\mathsf{CP}},\widetilde{\mathsf{Eval}})$ in the plain model as
follows:

  1. 1.

Using a random oracle $\mathcal{O}$ simulated on-the-fly,
$\widetilde{\mathsf{CP}}(f)$ runs $\mathsf{CP}^{\mathcal{O}}(f)$ to obtain a
copy-protected program $\rho_{f}$. It then runs a random (polynomial) number
of test executions $\mathsf{Eval}^{\mathcal{O}}(\rho_{f},x_{i})$ for randomly
chosen inputs $x_{i}$. It records all the queries made by $\mathsf{Eval}$
during the test executions in a database $D$. Finally, it samples a set of
random oracle answers $R$ and outputs $(\rho,D,R)$.

  2. 2.

$\widetilde{\mathsf{Eval}}((\rho_{f},D,R),x)$ simulates a random oracle
$\mathcal{O^{\prime}}$ using the database $D$ and using $R$ for queries not
recorded in $D$. It runs $\mathsf{Eval}^{\mathcal{O^{\prime}}}(\rho_{f},x)$
and outputs the answer.

The key difference between our construction and the construction of [CKP15] is
that we choose the number of test executions at random. In the classical
world, running more test executions can never hurt the simulation. In the
quantum world, on the other hand, every test execution can significantly alter
the state $\rho_{f}$ by performing measurements. This could be true even if
$\rho_{f}$ is reusable, in the sense that its correctness guarantee is
preserved after polynomially many evaluations222These _forced_ measurements
are a unique feature of the classical-accessible oracle setting, since quantum
queries need not be measured at the time of the query by the deferred
measurement principle.. For instance, the state $\rho_{f}$ could maintain a
counter which affects the oracle queries made by $\mathsf{Eval}$. To ensure
that the oracle queries $\widetilde{\mathsf{Eval}}$ needs to answer are
captured in the database $D$ with probability close to 1, even if $\rho_{f}$
keeps changing, we choose the number of test queries at random and
sufficiently large.

Perhaps surprisingly, our technique also improves the classical impossibility
of obfuscation in the random oracle model! Specifically, it reduces the number
of test executions needed by a factor of $N$ when compared to [CKP15], where
$N$ is a query-bound for $\mathsf{Eval}$.

###  2.1 Acknowledgements

We thank Luowen Qian for valuable discussions.

###  2.2 Organization

Preliminaries are described in Section 3. The impossibility of approximate
copy-protection in the plain model is presented in Section 4.1. We prove the
impossibility of copy-protection in CAROM in Section 4.2.

##  3 Preliminaries

###  3.1 Notation

We denote by $x\xleftarrow{\$}X$ the sampling of an element $x$ from the
uniform distribution over $X$. We denote by $\lambda$ the security parameter.
We use the terms function and circuit interchangeably. We denote by
$\mathsf{negl}(\cdot)$ a generic negligible function.
$[N]:=\\{1,2,\dots,N\\}$. If an algorithm $\mathcal{A}$ has oracle access to
$\mathcal{O}$, we may write $\mathcal{A}^{\mathcal{O}}$ to emphasize this
fact. We call a function $\epsilon:\mathbb{Z}^{+}\to\mathbb{R}^{+}\cup\\{0\\}$
noticable if there exists a polynomial $p$ such that
$\epsilon(n)>\frac{1}{p(n)}$ for sufficiently large $n$. We say _overwhelming_
probability to mean probability $1-\mathsf{negl}(\lambda)$. We sometimes
shorten a string of zeros to 0, when the length will be understood from the
context. We write $\mathcal{A}(x;r)$ when a classical algorithm $\mathcal{A}$
is run on input $x$ using specified randomness $r$.

###  3.2 Quantum Computing Basics

For a finite set (register) $X$ we denote by $\mathcal{H}_{X}$ the Hilbert
Space generated by the basis $\left\\{|x\rangle\right\\}_{x\in X}$. We denote
by $\mathcal{D}(\mathcal{H})$ the set of valid mixed quantum states over
Hilbert space $\mathcal{H}$, i.e. linear, positive-semidefinite operators over
$\mathcal{H}$ with unit trace, also known as density operators. We define a
quantum polynomial time (QPT) algorithm as a family of generalized quantum
circuits $\left\\{\mathcal{A}_{\lambda}\right\\}_{\lambda\in\mathbb{N}}$ such
that each $\mathcal{A}_{\lambda}$ contains at most $p(\lambda)$ input/output
qubits (including auxiliary qubits) and at most $p(\lambda)$ gates from a
universal gate set (such as $\left\\{CNOT,H,T\right\\}$), for some polynomial
$p(\cdot)$.

####  3.2.1 Trace Distance

A common way to measure dissimilarity between two quantum states
$\rho,\sigma\in\mathcal{D}(\mathcal{H})$ is the (normalized) trace distance,
defined as

$T(\rho,\sigma):=\frac{1}{2}|\rho-\sigma|_{tr}=\frac{1}{2}\mathsf{Tr}\left(\sqrt{(\rho-\sigma)^{2}}\right).$

It is a fact that no quantum algorithm can increase the trace distance between
two quantum states, i.e. $T(\mathcal{A}(\rho),\mathcal{A}(\sigma))\leq
T(\rho,\sigma)$ for any $\mathcal{A},\rho,\sigma$. When two quantum states
$\rho(\lambda),\sigma(\lambda)$ depend on a security parameter and satisfy
$T(\rho,\sigma)\leq\mathsf{negl}(\lambda)$, we write $\rho\approx_{s}\sigma$,
meaning $\rho$ and $\sigma$ are statistically close.

####  3.2.2 Measurement

A quantum measurement on a Hilbert Space $\mathcal{H}$ with a finite set of
outcomes $[m]$ can be represented by a set of operators $(M_{i})_{i\in[m]}$
satisfying $\sum_{i\in[m]}M_{i}^{\dagger}M_{i}=I$. Given a quantum state
$\rho\in\mathcal{D}(\mathcal{H})$, the probability of outcome $i$ is given by
$\mathsf{Tr}(M_{i}\rho M_{i}^{\dagger})$, whereas the post-measurement state
after measuring outcome $i$ is given by $\frac{M_{i}\rho
M_{i}^{\dagger}}{\mathsf{Tr}(M_{i}\rho M_{i}^{\dagger})}$. If the measurement
outcome is not revealed, then the post-measurement state equals the mixture
$\sum_{i\in[m]}M_{i}\rho M_{i}^{\dagger}$.

####  3.2.3 Almost As Good As New Lemma

The following lemma from [Aar04] is widely used in literature333In quantum
information theory, it is known as the gentle measurement lemma [Win99]..

######  Lemma 2 (Almost as Good as New Lemma).

Let $\rho$ be a quantum state and $(M_{0},M_{1})$ be a $2$-outcome measurement
such that $\mathsf{Tr}(M_{0}\rho M_{0}^{\dagger})\geq 1-\varepsilon$. Then,
after this measurement is performed on $\rho$, it is possible to recover a
state $\rho^{\prime}$ such that $T(\rho,\rho^{\prime})\leq\sqrt{\varepsilon}$.
In addition, the recovery procedure is independent of $\rho$, and is efficient
(runs in polynomial time) given that $(M_{0},M_{1})$ is efficient.

######  Corollary 3.

Let $\mathcal{A}$ be a quantum algorithm that given as input a quantum state
$\rho$ and a classical string $x$, outputs a classical string $y$. Suppose
that

$\displaystyle\operatorname*{\mathsf{Pr}}\left[f(x)\leftarrow\mathcal{A}(\rho,x)\right]\geq
1-\varepsilon(x),$ (1)

where $\rho$ is a quantum input state, $x$ is a classical input, and $f(x)$ is
a classical deterministic function. Then, there exists a quantum algorithm
$\mathcal{A}^{\prime}$ such that (1) $\mathcal{A}^{\prime}(\rho,x)$ outputs a
classical string $y$ identically distributed to output of
$\mathcal{A}(\rho,x)$, and (2) in addition $\mathcal{A}^{\prime}$ outputs a
residual state $\rho^{\prime}$ satisfying
$T(\rho,\rho^{\prime})\leq\sqrt{\varepsilon(x)}$. Moreover,
$\mathcal{A}^{\prime}$ is efficient given that $\mathcal{A}$ is efficient.

###### Sketch.

By deferred measurement principle, we can modify $\mathcal{A}$ so that it
applies a unitary transformation followed by measuring and outputting a value
$y$. Fix $x\in X$, then the statement follows after applying Lemma 2 with
respect to the 2-outcome measurement which checks whether $y=f(x)$ or not. ∎

###  3.3 Quantum Fully Homomorphic Encryption

A fully homomorphic encryption scheme allows for publicly evaluating an
encryption of $x$ using a function $f$ to obtain an encryption of $f(x)$.
Traditionally $f$ has been modeled as classical circuits but in this work, we
consider the setting when $f$ is modeled as quantum circuits and when the
messages are quantum states. This notion is referred to as quantum fully
homomorphic encryption (QFHE). We state our definition borrowed directly
from444With the slight modification that the evaluation key is included as
part of the public key. [BJ15].

######  Definition 4.

Let $\mathcal{M}$ be the Hilbert space associated with the message space
(plaintexts) and $\mathcal{C}$ be the Hilbert space associated with the
ciphertexts. A quantum fully homomorphic encryption (QFHE) scheme is a tuple
of QPT algorithms
$\mathsf{QFHE}=(\mathsf{Gen},\mathsf{Enc},\mathsf{Dec},\allowbreak\mathsf{Eval})$:

  * •

$\mathsf{QFHE}.\mathsf{Gen}(1^{\lambda})$: Takes as input a security parameter
$\lambda$ in unary; outputs a classical public-secret key pair,
$(\mathsf{PK},\mathsf{SK})$.

  * •

$\mathsf{QFHE}.\mathsf{Enc}(\mathsf{PK},\cdot):\mathcal{D}(\mathcal{M})\rightarrow\mathcal{D}(\mathcal{C})$:
Takes as input a public key $\mathsf{PK}$ and a quantum message $\rho$;
outputs a quantum ciphertext $\sigma$.

  * •

$\mathsf{QFHE}.\mathsf{Dec}(\mathsf{SK},\cdot):\mathcal{D}(\mathcal{C})\rightarrow\mathcal{D}(\mathcal{M})$:
Takes as input a secret key $\mathsf{SK}$ and a quantum ciphertext $\sigma$;
outputs a quantum message $\rho$.

  * •

$\mathsf{QFHE}.\mathsf{Eval}(\mathsf{PK},\mathcal{E},\cdot):\mathcal{D}(\mathcal{C}^{\otimes
n})\rightarrow\mathcal{D}(\mathcal{C}^{\otimes m})$: Takes as input a public
key $\mathsf{PK}$, description of a quantum circuit
$\mathcal{E}:\mathcal{D}(\mathcal{M}^{\otimes
n})\rightarrow\mathcal{D}(\mathcal{M}^{\otimes m})$, and a tuple of quantum
ciphertexts $\sigma\in(\mathcal{D}(\mathcal{C}^{\otimes n}))$; outputs a tuple
of quantum ciphertexts $\sigma^{\prime}\in\mathcal{D}(\mathcal{C}^{\otimes
m})$.

Semantic security and compactness are defined analogously to the classical
setting, and we defer to [BJ15] for a definition. For the impossibility
result, we require a $\mathsf{QFHE}$ scheme where ciphertexts of classical
plaintexts are also classical. Given any classical message
$x\in\\{0,1\\}^{k}$, we want
$\mathsf{QFHE}.\mathsf{Enc}(\mathsf{PK},|x\rangle\langle x|)$ to be a
computational basis state $|z\rangle\langle z|$ for some $z\in\\{0,1\\}^{l}$
(here, $l$ is the length of ciphertexts for $k$-qubit messages). In this case,
we write $\mathsf{QFHE}.\mathsf{Enc}_{\mathsf{PK}}(x)$. We also want the same
to be true for evaluated ciphertexts, i.e. if $\mathcal{E}(|x\rangle\langle
x|)=|y\rangle\langle y|$ for some $x\in\\{0,1\\}^{n}$ and $y\in\\{0,1\\}^{m}$,
then

$\mathsf{QFHE}.\mathsf{Enc}_{\mathsf{PK}}(y)\leftarrow\mathsf{QFHE}.\mathsf{Eval}(\mathsf{PK},\mathcal{E},\mathsf{QFHE}.\mathsf{Enc}_{\mathsf{PK}}(x))$

is a classical ciphertext of $y$.

####  3.3.1 Circuit Privacy

An additional property we need a QFHE scheme to satisfy is called malicious
circuit privacy. Informally, it states that the evaluation algorithm does not
leak any information about the circuit being evaluated, i.e. given a
homomorphic evaluation of a circuit $\mathcal{E}$, an adversary cannot learn
any information she would not have learned given only black-box access to
$\mathcal{E}$. We give the formal definition below, adapted from555The
difference is that we sensibly strengthen the definition to account for
adversaries with a possibly entangled auxiliary register $B$. Even though this
was not formally considered by [CDM20], a quick analysis of their argument
reveals that their construction indeed satisfies this stronger definition of
circuit privacy. [CDM20]:

######  Definition 5 (Malicious Circuit Privacy).

A QFHE scheme
$\mathsf{QFHE}=(\mathsf{QFHE}.\mathsf{Gen},\allowbreak\mathsf{QFHE}.\mathsf{Enc},\allowbreak\mathsf{QFHE}.\mathsf{Dec},\allowbreak\mathsf{QFHE}.\mathsf{Eval})$
satisfies malicious circuit privacy if there exist unbounded quantum
algorithms $\mathsf{QFHE}.\mathsf{Ext}$ and $\mathsf{QFHE}.\mathsf{Sim}$ such
that for any (possibly invalid) public key $\mathsf{PK}^{*}$, any quantum
circuit $\mathcal{E}:\mathcal{D}(\mathcal{M}^{\otimes
n})\rightarrow\mathcal{D}(\mathcal{M}^{\otimes m})$, any ancillary register
$A$ with $\mathcal{H}_{A}=\mathcal{M}^{\otimes\mathrm{poly}(\lambda)}$, and
any $\rho\in\mathcal{D}(\mathcal{C}^{\otimes n}\otimes\mathcal{H}_{A})$ we
have

$\left(\mathsf{QFHE}.\mathsf{Eval}(\mathsf{PK}^{*},\mathcal{E},\cdot)\otimes\mathbf{id}_{A}\right)\rho\approx_{s}\mathsf{QFHE}.\mathsf{Sim}(1^{\lambda},(\mathcal{E}\otimes\mathbf{id}_{AB})(\widetilde{\rho})),$

where $\widetilde{\rho}\in\mathcal{D}(\mathcal{C}^{\otimes
n}\otimes\mathcal{H}_{A}\otimes\mathcal{H}_{B})$ is obtained by applying
$\mathsf{QFHE}.\mathsf{Ext}(1^{\lambda},\mathsf{PK}^{*},\cdot)$ to the
$\mathcal{C}^{\otimes n}$ (ciphertext) register of $\rho$, and $B$ is an
ancillary register.

The definition can be alternatively stated as follows: for an unbounded
adversary, one query $\mathsf{QFHE}.\mathsf{Eval}$ evaluation of the circuit
$\mathcal{E}$ is no more powerful than one query to $\mathcal{E}$ itself. Note
also that $A$ is a hidden register held by an adversary that could be
entangled with the ciphertext, so it is not accessible by the algorithms
$\mathsf{QFHE}.\mathsf{Eval}$ and $\mathsf{QFHE}.\mathsf{Ext}$.

##### Instantiation.

Malicious Circuit Privacy can be achieved using a regular QFHE scheme [CDM20].
We state their result as a theorem:

######  Theorem 6.

Assuming QLWE and circular security666This assumption is needed to evaluate
circuits with unbounded depth in both classical and quantum FHE., there exists
a QFHE scheme with malicious circuit privacy, which reduces to a classical FHE
scheme for classical inputs.

###  3.4 Compute-and-Compare Circuits and Quantum-Secure Lockable Obfuscation

##### Compute-and-compare Circuits.

The subclass of circuits that we are interested in is called compute-and-
compare circuits, denoted by $\mathcal{C}_{\mathsf{cnc}}$. A compute-and-
compare circuit is of the following form: $\mathbf{C}[C,\alpha,\beta]$, where
$\alpha$ is called a lock and $C$ has output length $|\alpha|$, is defined as
follows:

$\mathbf{C}[C,\alpha](x)=\left\\{\begin{subarray}{c}\beta,\ \text{ if
}C(x)=\alpha,\\\ \ \\\ 0,\ \text{ otherwise }\end{subarray}\right.$

######  Definition 7 (Quantum-Secure Lockable Obfuscation).

An obfuscation scheme $(\mathsf{Obf},\mathsf{ObfEval})$ for a class of
compute-and-compare circuits $\mathcal{C}_{\mathsf{cnc}}$ is said to be a
quantum-secure lockable obfuscation scheme if the following properties are
satisfied:

  * •

It satisfies the functionality of obfuscation.

  * •

Security: For every polynomial-sized circuit $C$, string
$\beta\in\\{0,1\\}^{\mathrm{poly}(\lambda)}$,for every QPT adversary
$\mathcal{A}$ there exists a QPT simulator $\mathsf{Sim}$ such that the
following holds: sample
$\alpha\xleftarrow{\$}\\{0,1\\}^{\mathrm{poly}(\lambda)}$,

$\left\\{\mathsf{Obf}\left(1^{\lambda},\mathbf{C}\right)\right\\}\approx_{Q,\varepsilon}\left\\{\mathsf{Sim}\left(1^{\lambda},1^{|C|}\right)\right\\},$

where $\mathbf{C}$ is a circuit parameterized by $C,\alpha,\beta$ with
$\varepsilon\leq\frac{1}{2^{|\alpha|}}$.

##### Instantiation.

The works of [WZ17, GKW17, GKVW19] construct a lockable obfuscation scheme
based on polynomial-security of learning with errors. Since learning with
errors is conjectured to be hard against QPT algorithms, the obfuscation
schemes of [WZ17, GKW17, GKVW19] are also secure against QPT algorithms. Thus,
we have the following theorem.

######  Theorem 8 ([GKW17, WZ17, GKVW19]).

Assuming quantum hardness of learning with errors, there exists a quantum-
secure lockable obfuscation scheme.

###  3.5 Classical-Accessible Oracles

We call an oracle $\mathcal{O}:\mathcal{X}\to\mathcal{Y}$ classical-accessible
if it only accepts a classical query $x\in X$, to which it responds with the
classical value $\mathcal{O}(x)$. More formally, a query to $\mathcal{O}$ made
by a quantum algorithm $\mathcal{A}$ can be described as the following quantum
operation: measure the $\mathcal{X}$ (query) register of $\mathcal{A}$ in the
computational basis to obtain $x\in\mathcal{X}$, then XOR the value
$\mathcal{O}(x)$ to the $\mathcal{Y}$ (answer) register. In other words, if
$\mathcal{A}$ queries the oracle in state
$\sum_{x,y,z}\alpha_{x,y,z}|x\rangle|y\rangle|z\rangle$, where $\mathcal{Z}$
is an ancillary register corresponding to the internal state of $\mathcal{A}$,
then the state after the query equals
$\sum_{y,z}\beta_{y,z}|x\rangle|y\oplus\mathcal{O}(x)\rangle|z\rangle$ with
probability $p_{x}=\sum_{y,z}|\alpha_{x,y,z}|^{2}$, where
$\beta_{y,z}=\alpha_{x,y,z}/\sqrt{p_{x}}$.

####  3.5.1 Classical-Accessible Random Oracle Model

In classical-accessible random oracle model (CAROM), the function in question
is assumed to be a uniformly random function
$\mathcal{O}:\mathcal{X}\to\mathcal{Y}$ and modeled as a classical-accessible
oracle.

A classical-accessible random oracle $\mathcal{O}:X\to Y$ can be efficiently
simulated on-the-fly as follows:

  * •

Create an empty database $D\subset X\times Y$.

  * •

On query $x\in X$, check if $D$ contains $x$. If yes, answer consistently;
otherwise sample $y\xleftarrow{\$}Y$, add $(x,y)$ to $D$, and answer with $y$.

A classical-accessible oracle simulated on-the-fly is perfectly
indistinguishable from a classical-accessible random oracle.

###  3.6 Copy-Protection

Below we present the definition of a copy-protection scheme, adapted from
[BJL+21] and originally due to [Aar09].

######  Definition 9 (Copy-Protection Scheme).

Let $\mathcal{F}=\mathcal{F}(\lambda)$ be a class of efficiently computable
functions of the form $f:X\to Y$. A copy protection scheme for $\mathcal{F}$
is a pair of QPT algorithms $(\mathsf{CP},\mathsf{Eval})$ such that for some
output space $\mathcal{D}\left(\mathcal{H}_{Z}\right)$:

  * •

Copy Protected State Generation: $\mathsf{CP}(1^{\lambda},d_{f})$ takes as
input the security parameter $1^{\lambda}$ and a classical description $d_{f}$
of a function $f\in\mathcal{F}$ (that efficiently computes $f$). It outputs a
mixed state $\rho_{f}\in\mathcal{D}\left(\mathcal{H}_{Z}\right)$.

  * •

Evaluation: $\mathsf{Eval}(1^{\lambda},\rho,x)$ takes as input the security
parameter $1^{\lambda}$, a mixed state
$\rho\in\mathcal{D}\left(\mathcal{H}_{Z}\right)$, and an input value $x\in X$.
It outputs a bipartite state $\rho^{\prime}\otimes|y\rangle\langle
y|\in\mathcal{D}\left(\mathcal{H}_{Z}\right)\otimes\mathcal{D}\left(\mathcal{H}_{Y}\right)$.

We will sometimes abuse the notation and write
$\mathsf{Eval}(1^{\lambda},\rho,x)$ to denote either the classical output
$y\in Y$ or the residual state $\rho^{\prime}$ alone when the other is
insignificant. Note that when we work in CAROM, the algorithms
$(\mathsf{CP},\mathsf{Eval})$ will have access to the random oracle and be
written as $(\mathsf{CP}^{\mathcal{O}},\mathsf{Eval}^{\mathcal{O}})$.

There are three properties we require of a copy-protection scheme:
correctness, reusability, and security.

##### Correctness:

Informally speaking, if an honestly generated copy-protected state $\rho_{f}$
for a function $f\in\mathcal{F}$ is honestly evaluated using $\mathsf{Eval}$
on any input $x\in X$, the output should be $f(x)$. We present the formal
definition below:

######  Definition 10 (Correctness).

A copy-protection scheme $(\mathsf{CP},\mathsf{Eval})$ for $\mathcal{F}$ is
$\delta$-correct if the following holds for every $x\in X$, $f\in\mathcal{F}$:

$\operatorname*{\mathsf{Pr}}\left[f(x)\leftarrow\mathsf{Eval}(1^{\lambda},\rho_{f},x)\
:\ \rho_{f}\leftarrow\mathsf{CP}(1^{\lambda},d_{f})\right]\geq\delta.$

Correctness property can be relaxed by averaging over inputs $x$ sampled from
a distribution $\mathcal{D}$.

######  Definition 11 (Mean-Correctness).

Let $\mathcal{D}_{X}$ be a distribution over $X$. A copy-protection scheme
$(\mathsf{CP},\mathsf{Eval})$ for $\mathcal{F}$ is
$(\mathcal{D}_{X},\delta)$-mean-correct if the following holds for every
$f\in\mathcal{F}$:

$\operatorname*{\mathsf{Pr}}\left[f(x)\leftarrow\mathsf{Eval}(1^{\lambda},\rho_{f},x)\
:\ \begin{subarray}{c}\rho_{f}\leftarrow\mathsf{CP}(1^{\lambda},d_{f})\\\ \
{x\leftarrow\mathcal{D}_{X}}\end{subarray}\right]\geq\delta.$

##### Reusability:

The correctness notions we define above are for a single evaluation. In
practice, we would like our copy-protected program to evaluate polynomially
many inputs without losing its functionality. Accordingly, we define
reusability below as a stronger version of these correctness notions.

######  Definition 12 (Reusability).

Let $(\mathsf{CP},\mathsf{Eval})$ be a $\delta$-correct copy-protection scheme
for $\mathcal{F}$. Then, $(\mathsf{CP},\mathsf{Eval})$ is called reusable if
the following holds for every $m=\mathrm{poly}(\lambda)$, every
$(x_{1},\dots,x_{m})\in X^{m}$ and every $f\in\mathcal{F}$:

$\displaystyle\operatorname*{\mathsf{Pr}}\left[f(x_{m})\leftarrow\mathsf{Eval}(1^{\lambda},\rho_{f}^{m},x_{m})\;:\;\begin{subarray}{c}\rho_{f}^{1}\leftarrow\mathsf{CP}(1^{\lambda},d_{f})\\\
\rho_{f}^{i+1}\leftarrow\mathsf{Eval}(1^{\lambda},\rho_{f}^{i},x_{i}),\;1\leq
i\leq m-1\end{subarray}\right]\geq\delta-\mathsf{negl}(\lambda).$

Similarly, let $(\mathsf{CP},\mathsf{Eval})$ be a
$(\mathcal{D}_{X},\delta)$-mean-correct copy-protection scheme for
$\mathcal{F}$. Then, $(\mathsf{CP},\mathsf{Eval})$ is called reusable if the
following holds for any $m=\mathrm{poly}(\lambda)$ and any $f\in\mathcal{F}$:

$\displaystyle\operatorname*{\mathsf{Pr}}\left[f(x_{m})\leftarrow\mathsf{Eval}(1^{\lambda},\rho_{f}^{m},x_{m})\;:\;\begin{subarray}{c}\rho_{f}^{1}\leftarrow\mathsf{CP}(1^{\lambda},d_{f})\\\
x_{i}\leftarrow\mathcal{D}_{X},\;1\leq i\leq m\\\
\rho_{f}^{i+1}\leftarrow\mathsf{Eval}(1^{\lambda},\rho_{f}^{i},x_{i}),\;1\leq
i\leq m-1\end{subarray}\right]\geq\delta-\mathsf{negl}(\lambda).$

######  Remark 13.

In the plain model or the quantum-accessible oracle models, reusability is
implied by correctness by Corollary 3. In particular,
$\delta=1-\mathsf{negl}(\lambda)$ yields $\gamma=\mathsf{negl}(\lambda)$ and
$\delta=1-1/\mathrm{poly}(\lambda)$ yields $\gamma=1/\mathrm{poly}(\lambda)$.
However, in the classical-accessible setting such an implication is unclear
due to the fact that the oracle queries force an intermediate measurement that
cannot be pushed to the end.

##### Security:

Security in the context of copy-protection means that given a copy-protected
program $\rho_{f}$ of a function $f\in\mathcal{F}$, no QPT adversary can
produce two programs that can both be used to compute $f$. This is captured in
the following definition adapted from the ”malicious-malicious security”
definition in [BJL+21]:

######  Definition 14 (Piracy Experiment).

A piracy experiment is a game defined by a copy-protection scheme
$(\mathsf{CP},\mathsf{Eval})$, a distribution $\mathcal{D}_{\mathcal{F}}$ over
$\mathcal{F}$, and a class of distributions
$\mathfrak{D}_{X}=\\{\mathfrak{D}_{X}(f)\\}_{f\in\mathcal{F}}$ over $X$. It is
the following game between a challenger and an adversary, which is a triplet
of algorithms $(\mathcal{A},\mathcal{B},\mathcal{C})$:

  * •

Setup Phase: The challenger samples a function
$f\leftarrow\mathcal{D}_{\mathcal{F}}$ and sends
$\rho_{f}\leftarrow\mathsf{CP}(1^{\lambda},d_{f})$ to $\mathcal{A}$.

  * •

Splitting Phase: $\mathcal{A}$ applies a CPTP map to split $\rho_{f}$ into a
bipartite state $\rho_{BC}$; she sends the $B$ register to $\mathcal{B}$ and
the $C$ register to $\mathcal{C}$. No communication is allowed between
$\mathcal{B}$ and $\mathcal{C}$ after this phase.

  * •

Challenge Phase: The challenger samples
$(x_{B},x_{C})\leftarrow\mathfrak{D}_{X}(f)\times\mathfrak{D}_{X}(f)$ and
sends $x_{B},x_{C}$ to $\mathcal{B},\mathcal{C}$, respectively.

  * •

Output Phase: $\mathcal{B}$ and $\mathcal{C}$ output777Since $\mathcal{B}$ and
$\mathcal{C}$ cannot communicate, the order in which they use their share of
the copy-protected program is insignificant. $y_{B}\in Y$ and $y_{C}\in Y$,
respectively, and send to the challenger. The challenger outputs 1 if
$y_{B}=f(x_{B})$ and $y_{C}=f(x_{C})$, indicating that the adversary has
succeeded, and 0 otherwise.

The bit output by the challenger is denoted by
$\mathsf{PirExp}^{\mathsf{CP},\mathsf{Eval}}_{\mathcal{D}_{\mathcal{F}},\mathfrak{D}_{X}}(1^{\lambda},(\mathcal{A},\mathcal{B},\mathcal{C}))$.

######  Definition 15 (Copy-Protection Security).

Let $(\mathsf{CP},\mathsf{Eval})$ be a copy-protection scheme for a class
$\mathcal{F}$ of functions $f:X\to Y$. Let $\mathcal{D}_{\mathcal{F}}$ be a
distribution over $\mathcal{F}$ and
$\mathfrak{D}_{X}=\left\\{\mathfrak{D}_{X}(f)\right\\}_{f\in\mathcal{F}}$ a
class of distributions over $X$. Then, $(\mathsf{CP},\mathsf{Eval})$ is called
$\left(\mathcal{D}_{\mathcal{F}},\mathfrak{D}_{X},\delta\right)$-secure if any
QPT adversary $(\mathcal{A},\mathcal{B},\mathcal{C})$ satisfies

$\operatorname*{\mathsf{Pr}}\left[b=1\ :\
b\leftarrow\mathsf{PirExp}^{\mathsf{CP},\mathsf{Eval}}_{\mathcal{D}_{\mathcal{F}},\mathfrak{D}_{X}}\left(1^{\lambda},(\mathcal{A},\mathcal{B},\mathcal{C})\right)\right]\leq\delta.$

Note that this definition is referred to as malicious-malicious security
because the adversary is free to choose the registers $B,C$ as well as the
evaluation algorithms used by $\mathcal{B}$ and $\mathcal{C}$.

###  3.7 Quantum-Unlearnability

Below we state the definition of a quantum unlearnable circuit class from
[ALP21], which states that a QPT adversary cannot output a quantum
implementation of $C\in\mathcal{C}$ given oracle access:

######  Definition 16.

A circuit class $\mathcal{C}$ is $\nu$-quantum unlearnable with respect to
distribution $\mathcal{D}_{\mathcal{C}}$ over $\mathcal{C}$ if for any quantum
adversary $\mathcal{A}^{C}$ making at most $\mathrm{poly}(\lambda)$ queries,
we have

$\operatorname*{\mathsf{Pr}}\left[\forall
x,\operatorname*{\mathsf{Pr}}[U^{*}(\rho^{*},x)=C(x)]\geq\nu\ :\
\begin{subarray}{c}C\leftarrow\mathcal{D}_{\mathcal{C}}\\\
(U^{*},\rho^{*})\leftarrow\mathcal{A}^{C(\cdot)}(1^{\lambda})\end{subarray}\right]\leq\mathsf{negl}(\lambda).$

If there exists a distribution $\mathcal{D}_{C}$ satisfying this property,
then $\mathcal{C}$ is simply called $\nu$-quantum unlearnable.

##  4 Impossibility in Classical-Accessible Random Oracle Model

We show the infeasibility of copy-protection in the classical-accessible
random oracle model (CAROM). We prove this in two steps:

  * •

First, we show the impossibility of approximately correct copy-protection
(even without reusability) in the plain model.

  * •

Next, we show that any copy-protection in CAROM can be transformed into
approximately-correct copy-protection in the plain model. Invoking the above
result, it follows that copy-protection in CAROM is impossible.

###  4.1 Impossibility of Approximate Copy-Protection

Following the approach of [ALP21], we will construct a class of circuits,
which cannot be learned via oracle access, yet can be learned given the
quantum circuit. The key tool enabling the latter is the power of homomorphic
evaluation. The class of circuits we construct is related to but different
from that constructed by [ALP21].

######  Theorem 17.

Assuming the existence of QFHE with malicious circuit privacy and QLWE, there
exists an unlearnable class $\mathcal{G}$ of circuits of the form $G:X\to Y$
and an input distribution $\mathcal{D}_{X}$ over $X$ such that there exists no
copy-protection scheme $(\mathsf{CP},\mathsf{Eval})$ in the plain model for
$\mathcal{G}$ with $(\mathcal{D}_{X},1-\varepsilon(\lambda))$-mean-correctness
and $(\mathcal{D}_{\mathcal{G}},\mathfrak{D}_{X},\delta(\lambda))$-security
for any $(\varepsilon,\delta)$ satisfying $\delta\leq 1-3\sqrt{\varepsilon}$
and for any $\mathcal{D}_{\mathcal{G}},\mathfrak{D}_{X}$.

###### Proof.

Let $\mathsf{Obf}$ be a quantum-secure lockable obfuscation scheme (see
Section 3.4) and $\mathsf{QFHE}$ be a quantum fully homomorphic encryption
scheme satisfying malicious circuit privacy (see Section 3.3). We first recall
the circuit class $\mathcal{C}$ used in the impossibility result of [ALP21],
presented in Figure 1. Every circuit in $\mathcal{C}$ is of the form
$C_{a,b,r,\mathsf{PK},\mathcal{O}}$, where $a,b,r,\mathsf{PK},\mathcal{O}$ are
parameters described below.

  * •

$a,b,r\in\\{0,1\\}^{\lambda}$.

  * •

$(\mathsf{PK},\mathsf{SK})$ is in the support of
$\mathsf{QFHE}.\mathsf{Gen}(1^{\lambda})$.

  * •

$\mathcal{O}$ is in the support of
$\mathsf{Obf}(\mathsf{CC}[\allowbreak\mathsf{QFHE}.\mathsf{Dec}(\mathsf{SK},\cdot),b,\allowbreak(\mathsf{SK}||r)])$.

Let
$\widetilde{\mathsf{QFHE}}=(\widetilde{\mathsf{QFHE}}.\mathsf{Setup},\widetilde{\mathsf{QFHE}}.\mathsf{Enc},\widetilde{\mathsf{QFHE}}.\mathsf{Dec},\widetilde{\mathsf{QFHE}}.\mathsf{Eval})$
be a QFHE scheme with malicious circuit privacy (Definition 5).

Using $\mathcal{C}$, we define888In both $\mathcal{C}$ and $\mathcal{G}$, we
assume padding with zeros appropriately to make input/output lengths
compatible. another class of circuits $\mathcal{G}$ in Figure 2. We show that
$\mathcal{G}$ cannot be copy-protected. Every circuit in $\mathcal{G}$ is of
the form $G_{C_{a,b,r,\mathsf{PK},\mathcal{O}}}$, which is a fixed circuit
parameterized by a circuit $C_{a,b,r,\mathsf{PK},\mathcal{O}}\in\mathcal{C}$.

$\underline{C_{a,b,r,\mathsf{PK},\mathcal{O}}(x)}$:
---
1. If $x=0$, output $\mathsf{QFHE}.\mathsf{Enc}\left(\mathsf{PK},a;r\right)|\mathcal{O}|\mathsf{PK}$, where $\mathcal{O}$ is generated as follows:
$\allowbreak\mathcal{O}\leftarrow\mathsf{Obf}(\mathsf{CC}[\allowbreak\mathsf{QFHE}.\mathsf{Dec}(\mathsf{SK},\cdot),b,\allowbreak(\mathsf{SK}|r)])$,
where $\mathsf{CC}$ is a compute-and-compare circuit. 2. Else if $x=a$, output
$b$. 3. Otherwise, output $0$
Figure 1: Description of a circuit $C_{a,b,r,\mathsf{PK},\mathcal{O}}$ in
$\mathcal{C}$.
$\underline{G_{C_{a,b,r,\mathsf{PK},\mathcal{O}}}(\widetilde{\mathsf{PK}},X)}$:
---
1. Parse $X$ as ciphertext $CT$. 2. Compute and output $CT^{*}\leftarrow\widetilde{\mathsf{QFHE}}.\mathsf{Eval}_{\widetilde{\mathsf{PK}}}(C_{a,b,r,\mathsf{PK},\mathcal{O}},CT)$.
Figure 2: Description of a circuit $G\in\mathcal{G}$, used for proving
impossibility of approximate CP

##### Unlearnability.

We will first show that $\mathcal{G}$ is unlearnable with respect to a
distribution $\mathcal{D}_{\mathcal{C}}(\lambda)$, which we define as follows:
$\mathcal{D}_{\mathcal{C}}(\lambda)$ outputs a circuit from
$\mathcal{C}_{\lambda}$ by sampling $a,b,r\xleftarrow{\$}\\{0,1\\}^{\lambda}$,
then computing
$(\mathsf{PK},\mathsf{SK})\leftarrow\mathsf{QFHE}.\mathsf{Gen}(1^{\lambda})$,
and finally computing an obfuscation
$\mathcal{O}\leftarrow\mathsf{Obf}(\mathsf{CC}[\allowbreak\mathsf{QFHE}.\mathsf{Dec}(\mathsf{SK},\cdot),\allowbreak(b,\allowbreak(\mathsf{SK}|r))])$,
where $\mathsf{CC}$ is a compute-and-compare circuit. Since every
$G_{C}\in\mathcal{G}$ is uniquely determined by the description of
$C\in\mathcal{C}$, $\mathcal{D}_{\mathcal{C}}(\lambda)$ induces a distribution
$\mathcal{D}_{\mathcal{G}}(\lambda)$ on $\mathcal{G}$ given by
$G_{C}:C\leftarrow\mathcal{D}_{\mathcal{C}}$.

We cite the following result:

######  Lemma 18 (Proposition 46 in [ALP21]).

For any non-negligible function $\nu=\nu(\lambda)$, $\mathcal{C}$ is
$\nu$-quantum unlearnable with respect to
$\mathcal{D}_{\mathcal{C}}(\lambda)$.

Using this as a black-box, we can now prove unlearnability of $\mathcal{G}$:

######  Lemma 19.

$\mathcal{G}$ is unlearnable with respect to the distribution
$\mathcal{D}_{\mathcal{G}}(\lambda)$.

###### Proof.

Suppose that there exists an unbounded quantum adversary
$\mathcal{A}^{G_{C}(\cdot)}$ which makes at most $\mathrm{poly}(\lambda)$
queries and satisfies

$\operatorname*{\mathsf{Pr}}\left[\forall
x,\operatorname*{\mathsf{Pr}}[U^{*}(\rho^{*},x)=G(x)]\geq\nu(\lambda)\ :\
\begin{subarray}{c}C\leftarrow\mathcal{D}_{\mathcal{C}}\\\
(U^{*},\rho^{*})\leftarrow\mathcal{A}^{G_{C}(\cdot)}(1^{\lambda})\end{subarray}\right]\geq\mu(\lambda)$

for some non-negligible functions $\nu,\mu$. We will use
$\mathcal{A}^{G_{C}(\cdot)}$ to construct an adversary which violates the
unlearnability of $C$.
We will proceed in two steps:

  * •

By malicious circuit privacy of $\widetilde{\mathsf{QFHE}}$, there exists an
unbounded quantum adversary $(\mathcal{A}^{\prime})^{C(\cdot)}$ which makes at
most $\mathrm{poly}(\lambda)$ queries to $C(\cdot)$ and satisfies

$\displaystyle\operatorname*{\mathsf{Pr}}\left[\forall
x,\operatorname*{\mathsf{Pr}}[U^{*}(\rho^{*},x)=G(x)]\geq\nu(\lambda)-\mathsf{negl}(\lambda)\
:\ \begin{subarray}{c}C\leftarrow\mathcal{D}_{\mathcal{C}}\\\
(U^{*},\rho^{*})\leftarrow(\mathcal{A}^{\prime})^{C(\cdot)}(1^{\lambda})\end{subarray}\right]$
$\displaystyle\geq\mu(\lambda)-\mathsf{negl}(\lambda).$ (2)

$\mathcal{A}^{\prime}$ simply uses
$(\widetilde{\mathsf{QFHE}}.\mathsf{Sim},\widetilde{\mathsf{QFHE}}.\mathsf{Ext})$
and oracle access to $C(\cdot)$ to simulate the queries of $\mathcal{A}.$

  * •

Using $(\mathcal{A}^{\prime})^{C(\cdot)}$, we will construct
$(\widetilde{\mathcal{A}^{\prime}})^{C(\cdot)}$ which makes at most
$\mathrm{poly}(\lambda)$ queries to $C(\cdot)$ and satisfies

$\displaystyle\operatorname*{\mathsf{Pr}}\left[\forall
x,\operatorname*{\mathsf{Pr}}[U^{*}(\rho^{*},x)=C(x)]\geq\nu(\lambda)-\mathsf{negl}(\lambda)\
:\ \begin{subarray}{c}C\leftarrow\mathcal{D}_{\mathcal{C}}\\\
(U^{*},\rho^{*})\leftarrow(\widetilde{\mathcal{A}^{\prime}})^{C(\cdot)}(1^{\lambda})\end{subarray}\right]$
$\displaystyle\geq\mu(\lambda)-\mathsf{negl}(\lambda).$ (3)

$(\widetilde{\mathcal{A}^{\prime}})^{C(\cdot)}$ does the following:

    * –

Run $(\mathcal{A}^{\prime})^{C(\cdot)}(1^{\lambda})$ to obtain $(U,\rho)$

    * –

Output $(U^{*},\rho)$, where $U^{*}(\rho,x)$ does the following:

      1. 1.

Compute
$(\mathsf{PK},\mathsf{SK})\leftarrow\widetilde{\mathsf{QFHE}}.\mathsf{Setup}(1^{\lambda})$
and
$\mathsf{CT}\leftarrow\widetilde{\mathsf{QFHE}}.\mathsf{Enc}(\mathsf{PK},x)$

      2. 2.

Compute $\mathsf{CT}^{*}\leftarrow U(\rho,(\mathsf{PK},\mathsf{CT}))$.

      3. 3.

Output
$y\leftarrow\widetilde{\mathsf{QFHE}}.\mathsf{Dec}(\mathsf{SK},\mathsf{CT}^{*})$.

Conditioned on $(U,\rho)$ satisfying the event in • ‣ section 4.1,
$(U,\rho^{*})$ will satisfy the event in • ‣ section 4.1 by correctness of
$\widetilde{\mathsf{QFHE}}$ evaluation, thereby violating $\mu$-quantum
unlearnability of $\mathcal{C}$.

∎

######  Lemma 20.

There exists $\mathcal{D}_{X}$ such that there is no copy-protection scheme
$(\mathsf{CP},\allowbreak\mathsf{Eval})$ in the plain model for $\mathcal{G}$
with $(\mathcal{D}_{X},1-\varepsilon(\lambda))$-mean-correctness and
$(\mathcal{D}_{\mathcal{G}},\allowbreak\mathfrak{D}_{X},\allowbreak\delta(\lambda))$-security
for any $\mathfrak{D}_{X}$ and any $\varepsilon,\delta$ satisfying $\delta\leq
1-3\sqrt{\varepsilon}$.

###### Proof.

Define

$\mathcal{D}_{X}:=\left\\{\widetilde{\mathsf{QFHE}}.\mathsf{Enc}_{\widetilde{\mathsf{PK}}}(x):\begin{subarray}{c}(\widetilde{\mathsf{PK}},\widetilde{\mathsf{SK}})\leftarrow\widetilde{\mathsf{QFHE}}.\mathsf{Setup}(1^{\lambda})\\\
x\xleftarrow{\$}\\{0,1\\}^{\mathrm{poly}(\lambda)}\end{subarray}\right\\}$

Suppose there is an approximate copy-protection scheme
$(\mathsf{CP},\mathsf{Eval})$ for $\mathcal{G}$ with
$1-\varepsilon(\lambda)$-mean-correctness. Let
$\rho\leftarrow\mathsf{CP}(1^{\lambda},G_{C_{a,b,r,\mathsf{PK},\mathcal{O}}})$.
We construct a QPT adversary $\mathcal{A}$ in Figure 3 that given $\rho$, can
recover an approximate classical description of $G$ with probability greater
than $\delta(\lambda)$, hence violating security999The attack is simply to
recover the classical description and send it to both parties at the splitting
phase. Note that this attack succeeds irrespective of the test distributions
$\mathfrak{D}_{X}$..

$\mathcal{A}(\rho)$:
---
1. Compute $(\widetilde{\mathsf{PK}},\widetilde{\mathsf{SK}})\leftarrow\widetilde{\mathsf{QFHE}}.\mathsf{Setup}(1^{\lambda})$. 2. Compute $CT\leftarrow\widetilde{\mathsf{QFHE}}.\mathsf{Enc}_{\widetilde{\mathsf{PK}}}(0)$. 3. Run the copy-protection evaluation, $\rho^{\prime}\otimes CT^{*}\leftarrow\mathsf{Eval}(1^{\lambda},\rho,CT)$. 4. Run the decryption, $(\mathsf{CT}_{a}|\mathcal{O}|\mathsf{PK})\leftarrow\widetilde{\mathsf{QFHE}}.\mathsf{Dec}_{\widetilde{\mathsf{SK}}}(CT^{*})$. Since $\mathsf{CT}_{a}$ is classical, maintain a copy of $\mathsf{CT}_{a}$. 5. Run the $\mathsf{QFHE}$ homomorphic evaluation, CT_b^* ←QFHE.Eval_PK(Φ,CT_a), where $\Phi$ is a quantum circuit that on input $\sigma$, does the following: (a) Compute $\sigma_{1}\leftarrow\widetilde{\mathsf{QFHE}}.\mathsf{Enc}(\widetilde{\mathsf{PK}},\sigma)$. (b) Compute $\sigma_{2}\leftarrow\mathsf{QFHE}.\mathsf{Eval}(\mathsf{PK},\mathsf{Eval}(1^{\lambda},\cdot,\cdot),\mathsf{QFHE}.\mathsf{Enc}(\widetilde{\mathsf{PK}},\rho^{\prime}),\sigma_{1})$. (c) Compute $\sigma_{3}\leftarrow\widetilde{\mathsf{QFHE}}.\mathsf{Dec}(\widetilde{\mathsf{SK}},\sigma_{2})$ and output $\sigma_{3}$. 6. Compute the unitary $\mathcal{O}$ on $\mathsf{CT}_{b}^{*}$ and measure basis to obtain $(sk^{\prime}|r^{\prime})$. 7. Compute $a\leftarrow\mathsf{QFHE}.\mathsf{Dec}(sk^{\prime},\mathsf{CT}_{a})$ and $b\leftarrow\mathsf{QFHE}.\mathsf{Dec}(sk^{\prime},\mathsf{CT}_{b}^{*})$. 8. Output $G_{C_{a,b,r^{\prime},\mathsf{PK},\mathcal{O}}}$.
Figure 3: Description of $\mathcal{A}$

Analysis of $\mathcal{A}(\rho)$: By approximate correctness of
$(\mathsf{CP},\mathsf{Eval})$, we have

$\displaystyle\operatorname*{\mathsf{Pr}}\left[G_{C}(x)\leftarrow\mathsf{Eval}(1^{\lambda},\rho,x)\
:\ \begin{subarray}{c}\rho\leftarrow\mathsf{CP}(1^{\lambda},G_{C})\\\ \
{x\leftarrow\mathcal{D}_{X}}\end{subarray}\right]$
$\displaystyle=\operatorname*{\mathsf{Pr}}\left[G_{C}(x)\leftarrow\mathsf{Eval}(1^{\lambda},\rho,\widetilde{\mathsf{QFHE}}.\mathsf{Enc}_{\widetilde{\mathsf{PK}}}(x))\
:\ \begin{subarray}{c}\rho\leftarrow\mathsf{CP}(1^{\lambda},G_{C})\\\ \
(\widetilde{\mathsf{PK}},\widetilde{\mathsf{SK}})\leftarrow\widetilde{\mathsf{QFHE}}.\mathsf{Setup}(1^{\lambda})\\\
\ x\xleftarrow{\$}\\{0,1\\}^{\mathrm{poly}(\lambda)}\end{subarray}\right]$
$\displaystyle\geq 1-\varepsilon(\lambda).$ (4)

Define

$\displaystyle\zeta_{x}:=\operatorname*{\mathsf{Pr}}\left[G_{C}(x)\leftarrow\mathsf{Eval}(1^{\lambda},\rho,\widetilde{\mathsf{QFHE}}.\mathsf{Enc}_{\widetilde{\mathsf{PK}}}(x))\
:\ \begin{subarray}{c}\rho\leftarrow\mathsf{CP}(1^{\lambda},G_{C})\\\ \
(\widetilde{\mathsf{PK}},\widetilde{\mathsf{SK}})\leftarrow\widetilde{\mathsf{QFHE}}.\mathsf{Setup}(1^{\lambda})\end{subarray}\right],$
(5)

so that eq. 4 can be written as

$\displaystyle\operatorname*{\mathbb{E}}_{x\xleftarrow{\$}\\{0,1\\}^{\mathrm{poly}(\lambda)}}\left[\zeta_{x}\right]\geq
1-\varepsilon(\lambda).$ (6)

We observe that $|\zeta_{x}-\zeta_{x^{\prime}}|\leq\mathsf{negl}(\lambda)$ for
any $x,x^{\prime}\in\\{0,1\\}^{\mathrm{poly}(\lambda)}$. To see this, suppose
the difference is not negligible. Define an adversary $\mathcal{A}^{\prime}$
who can break semantic security of $\widetilde{\mathsf{QFHE}}$. Given a
ciphertext
$CT\leftarrow\widetilde{\mathsf{QFHE}}.\mathsf{Enc}(\widetilde{\mathsf{PK}},x)$,
$\mathcal{A}^{\prime}$ does the following:

  * •

Sample $\rho\leftarrow\mathsf{CP}(1^{\lambda},G_{C})$

  * •

Output 1 if $G_{C}(x)\leftarrow\mathsf{Eval}(1^{\lambda},\rho,CT)$, and 0
otherwise.

$\mathcal{A}^{\prime}$ outputs 1 with probability $\zeta_{x}$, hence she can
distinguish encryptions of $x$ and $x^{\prime}$, contradiction. Hence,
$|\zeta_{x}-\zeta_{0}|\leq\mathsf{negl}(\lambda)$ for all $x$. Let $E_{1}$ be
the event that
$CT^{*}=\widetilde{\mathsf{QFHE}}.\mathsf{Enc}(\widetilde{\mathsf{PK}},\mathsf{QFHE}.\mathsf{Enc}_{\mathsf{PK}}(a)\allowbreak|\mathcal{O}|\mathsf{PK})$,
then by eq. 6 we have

$\displaystyle\operatorname*{\mathsf{Pr}}\left[E_{1}\right]=\zeta_{0}\geq\operatorname*{\mathbb{E}}_{x\xleftarrow{\$}\\{0,1\\}^{\mathrm{poly}(\lambda)}}\left[\zeta_{x}-\mathsf{negl}(\lambda)\right]\geq
1-\varepsilon(\lambda)-\mathsf{negl}(\lambda).$ (7)

At this stage, by modifying $\mathsf{Eval}$ if necessary, we can assume
$T(\rho^{\prime},\rho)\leq\sqrt{\varepsilon(\lambda)}+\mathsf{negl}(\lambda)$
by Corollary 3. Let $E_{2}$ be the event $\mathcal{A}$ succeeds in step 4; in
particular, $E_{2}$ implies
$\mathsf{CT}_{a}=\mathsf{QFHE}.\mathsf{Enc}(\mathsf{PK},a)$. By
$\widetilde{\mathsf{QFHE}}$ correctness we have
$\operatorname*{\mathsf{Pr}}\left[E_{2}\mid E_{1}\right]\geq
1-\mathsf{negl}(\lambda)$.

Conditioned on $E_{2}$, step 5b is nothing but a $\mathsf{QFHE}$ homomorphic
evaluation of $\mathsf{Eval}(1^{\lambda},\rho^{\prime},\sigma_{1})$, where
$\sigma_{1}\leftarrow\widetilde{\mathsf{QFHE}}.\mathsf{Enc}_{\widetilde{\mathsf{PK}}}(\mathsf{CT}_{a})$.
Equation 7 holds for any $\zeta_{x^{\prime}}$ including
$\zeta_{\mathsf{CT}_{a}}$, hence $\mathsf{Eval}(1^{\lambda},\rho,\sigma_{1})$
will succeed with probability $1-\varepsilon(x)-\mathsf{negl}(\lambda)$, i.e.
it will output a $\mathsf{QFHE}$ encryption of $b$. Since $\rho^{\prime}$ is
$\sqrt{\varepsilon}$-close to $\rho$ in trace distance, it follows that
$\mathsf{Eval}(1^{\lambda},\rho^{\prime},\mathsf{CT}_{a})$ will succeed with
probability
$1-\varepsilon(\lambda)-\sqrt{\varepsilon(\lambda)}-\mathsf{negl}(\lambda)$.
This inequality together with correctness of $\widetilde{\mathsf{QFHE}}$ and
correctness of $\mathsf{QFHE}$ homomorphic evaluation imply that
$\operatorname*{\mathsf{Pr}}\left[E_{3}\mid E_{2}\right]\geq
1-\varepsilon(\lambda)-\sqrt{\varepsilon(\lambda)}-\mathsf{negl}(\lambda)\geq
1-2\sqrt{\varepsilon(\lambda)}$, where $E_{3}$ is the event that
$\mathsf{CT}_{b}^{*}\in\mathsf{QFHE}.\mathsf{Enc}_{\mathsf{PK}}(b)$.
Conditioned on $E_{1},E_{2},E_{3}$, the adversary can recover the true
classical description with probability $1-\mathsf{negl}(\lambda)$ by
correctness of $\mathsf{QFHE}$ and $\mathsf{Obf}$. Thus,
$\mathcal{A}^{\prime}$ succeeds in recovering the classical description of
$G_{C}$ wiith probability at least

$\displaystyle\operatorname*{\mathsf{Pr}}\left[E_{3}\right]-\mathsf{negl}(\lambda)\geq\operatorname*{\mathsf{Pr}}\left[E_{3}\mid
E_{2}\right]\cdot\operatorname*{\mathsf{Pr}}\left[E_{2}\mid
E_{1}\right]\cdot\operatorname*{\mathsf{Pr}}\left[E_{1}\right]-\mathsf{negl}(\lambda)\geq$
$\displaystyle\geq\left(1-\varepsilon(\lambda)-\mathsf{negl}(\lambda)\right)(1-\mathsf{negl}(\lambda))(1-2\sqrt{\varepsilon(\lambda)})-\mathsf{negl}(\lambda)$
$\displaystyle\geq 1-3\sqrt{\varepsilon(\lambda)},$

which suffices for the proof.

∎

∎

###  4.2 Impossibility of Copy-Protection in CAROM

Assuming impossibility of approximate copy-protection in the plain model, we
will show that it is impossible to have a copy-protection scheme in CAROM
which satisfies $\left(1-\mathsf{negl}(\lambda)\right)$-correctness and
$\left(1-\allowbreak\frac{1}{\mathrm{poly}(\lambda)}\right)$-security. The
proof will follow closely the proof in [CKP15], which shows impossibility of
classical virtual-black-box obfuscation in the random oracle model assuming
its impossibility in the plain model.

######  Lemma 21.

Let $\delta=\delta(\lambda)$ be a function and $\mathcal{F}$ be a class of
functions of the form $f:X\to Y$. Let
$\mathcal{D}_{\mathcal{F}},\mathcal{D}_{X}$ be distributions over
$\mathcal{F},X$, respectively, and
$\mathfrak{D}_{X}=\\{\widetilde{\mathcal{D}_{X}}^{f}\\}_{f\in\mathcal{F}}$ be
a class of distributions over $X$. Assume that $\mathcal{D}_{X}$ can be
efficiently sampled. Suppose there exists a reusable copy-protection scheme
$(\mathsf{CP}^{\mathcal{O}},\mathsf{Eval}^{\mathcal{O}})$ in CAROM for
$\mathcal{F}$ with
$\left(\mathcal{D}_{X},1-\mathsf{negl}(\lambda)\right)$-mean-correctness and
$\left(\mathcal{D}_{\mathcal{F}},\mathfrak{D}_{X},\delta\right)$-security.
Then, for any noticeable function $\varepsilon$ there exists a copy-protection
scheme $(\widetilde{\mathsf{Eval}},\widetilde{\mathsf{CP}})$ in the plain
model with $(\mathcal{D}_{X},1-\varepsilon(\lambda))$-mean-correctness and
$\left(\mathcal{D}_{\mathcal{F}},\mathfrak{D}_{X},\delta\right)$-security.

Combining Lemma 21 with Theorem 17, we have the following.

######  Theorem 22 (Main Theorem).

There exists an unlearnable class of circuits
$\mathcal{G}=\mathcal{G}(\lambda)$ and an input distribution $\mathcal{D}_{X}$
such that there does not exist a reusable copy-protection scheme in CAROM with
$\left(\mathcal{D}_{X},1-\mathsf{negl}(\lambda)\right)$-mean-correctness and
$(\mathcal{D}_{\mathcal{F}},\allowbreak\mathfrak{D}_{X},\allowbreak
1-\varepsilon(\lambda))$-security for any noticeable function $\varepsilon$
and any distributions $\mathcal{D}_{\mathcal{F}},\mathfrak{D}_{X}$.

###### Proof of Lemma 21.

Let101010In [CKP15], the number of test executions ($T$) has an extra factor
of $N$. Our modified analysis could also be applied to their construction to
get rid of the factor of $N$.
$(\mathsf{CP}^{\mathcal{O}},\mathsf{Eval}^{\mathcal{O}})$ be given as in the
lemma statement. Since $\mathsf{CP}^{\mathcal{O}}$ and
$\mathsf{Eval}^{\mathcal{O}}$ both run in polynomial time, the numbers of
queries they make to $\mathcal{O}$ are bounded by some
$M=\mathrm{poly}(\lambda)$ and $N=\mathrm{poly}(\lambda)$, respectively. We
will construct a valid copy-protection scheme
$(\widetilde{\mathsf{CP}},\widetilde{\mathsf{Eval}})$ for $\mathcal{F}$ in the
plain model. Let $T:=\lceil\frac{2M}{\varepsilon}\rceil$.

Copy Protection: $\widetilde{\mathsf{CP}}(1^{\lambda},d_{f})$ takes as input
the security parameter $1^{\lambda}$ and the classical description $d_{f}$ of
a function $f\in\mathcal{F}$, and it does the following:

  1. 1.

Simulate on-the-fly a classical random oracle $\mathcal{O}$ to be used in any
of the steps below.

  2. 2.

Run $\rho_{f}\leftarrow\mathsf{CP}^{\mathcal{O}}(1^{\lambda},d_{f})$.

  3. 3.

Set $\rho_{f}^{1}:=\rho_{f}$. Pick $S\xleftarrow{\$}\\{0,1,\dots,T-1\\}$. For
$i=1$ to $S$:

    1. (a)

Sample $x_{i}\leftarrow\mathcal{D}_{X}$.

    2. (b)

Compute $\rho_{f}^{i+1}\otimes|y_{i}\rangle\langle
y_{i}|\leftarrow\mathsf{Eval}^{\mathcal{O}}(1^{\lambda},\rho_{f}^{i},x_{i})$
and record the queries made by $\mathsf{Eval}$ with their answers in a
database $D_{\mathsf{Eval}}^{i}$.

  4. 4.

Sample random oracle answers $r_{1},r_{2},\dots,r_{N}\xleftarrow{\$}Y$. These
will be used by $\widetilde{\mathsf{Eval}}$ to answer queries not recorded in
any of the databases $D_{\mathsf{Eval}}^{i}$.

  5. 5.

Output the state
$\widetilde{\rho_{f}}:=\rho_{f}^{S+1}\otimes|D_{\mathsf{Eval}}\rangle\langle
D_{\mathsf{Eval}}|\bigotimes_{j=1}^{N}|r_{j}\rangle\langle r_{j}|$, where
$D_{\mathsf{Eval}}:=\bigcup_{i=1}^{S}D_{\mathsf{Eval}}^{i}$.

Evaluation: $\widetilde{\mathsf{Eval}}(1^{\lambda},\widetilde{\rho_{f}},x)$
takes as input the security parameter $1^{\lambda}$, a copy-protected state
$\widetilde{\rho}$, and an input $x\in X$, and it does the following:

  1. 1.

Parse the state $\widetilde{\rho_{f}}$ as $\rho_{f}\otimes|D\rangle\langle
D|\bigotimes_{j=1}^{N}|r_{j}\rangle\langle r_{j}|$ by measuring the registers
corresponding to the database $D$ and the oracle answers
$\\{r_{j}\\}_{j=1}^{N}$.

  2. 2.

Run $\rho_{f}^{\prime}\otimes|y\rangle\langle
y|\leftarrow\mathsf{Eval}^{\mathcal{O}}(1^{\lambda},\rho_{f},x)$, answering
the oracle queries of $\mathsf{Eval}$ as follows: to answer the $j$th query
made by $\mathsf{Eval}$, answer consistently if the query is in $D$, and
answer using $r_{j}$ if the query is not in $D$ (without loss of generality
$\mathsf{Eval}$ does not make repeated queries). Output the state
$\left(\rho_{f}^{\prime}\otimes|D\rangle\langle
D|\bigotimes_{j=1}^{N}|r_{j}\rangle\langle
r_{j}|\right)\otimes|y\rangle\langle y|$.

##### Approximate Correctness:

Fix $f\in\mathcal{F}$. By $(\mathcal{D}_{X},1-\mathsf{negl}(\lambda))$-mean-
correctness and reusability of
$(\mathsf{CP}^{\mathcal{O}},\mathsf{Eval}^{\mathcal{O}})$, we have

$\displaystyle\operatorname*{\mathsf{Pr}}\left[f(x_{S+1})\leftarrow\mathsf{Eval}^{\mathcal{O}}(1^{\lambda},\rho_{f}^{S+1},x_{S+1})\;:\;\begin{subarray}{c}\rho_{f}^{1}\leftarrow\mathsf{CP}(1^{\lambda},d_{f})\\\
x_{i}\leftarrow\mathcal{D}_{X},\;1\leq i\leq S+1\\\
\rho_{f}^{i+1}\leftarrow\mathsf{Eval}^{\mathcal{O}}(1^{\lambda},\rho_{f}^{i},x_{i}),\;1\leq
i\leq S\end{subarray}\right]\geq 1-\mathsf{negl}(\lambda).$ (8)

Recall that $\widetilde{\mathsf{Eval}}$ emulates
$\mathsf{Eval}^{\mathcal{O}}$, using the database $D=D_{\mathsf{Eval}}$ to
answer oracle queries and using the independent random answers $r_{j}$ when
the query is not in $D$. This is equivalent to running
$\mathsf{Eval}^{\mathcal{O}_{D}}(1^{\lambda},\rho_{f},x)$, where
$\mathcal{O}_{D}$ is defined as a random oracle conditioned to be consistent
with $D$. Let $D_{\mathsf{CP}}$ be the set of queries made by $\mathsf{CP}$ in
step 2 of $\widetilde{\mathsf{CP}}$. Let $E$ be the event that
$\mathsf{Eval}(1^{\lambda},\rho_{f},x)$ does not make any oracle query in
$D_{\mathsf{CP}}\setminus D_{\mathsf{Eval}}$ during the execution of
$\widetilde{\mathsf{Eval}}$.111111Here by a slight abuse of notation we only
consider the input $x\in X$ of the query and not the answer $y\in Y$. Keep in
mind that $\widetilde{\mathsf{Eval}}$ emulates $\mathsf{Eval}^{\mathcal{O}}$
at the time of the $(S+1)$st test execution. Hence, $E$ is equivalently the
event that $\mathsf{Eval}(1^{\lambda},\rho_{f}^{S+1},x_{S+1})$ makes no query
in $D_{\mathsf{CP}}\setminus D_{\mathsf{Eval}}$, where $\rho_{f}^{S+1}$ and
$x_{S+1}$ are as in eq. 8. Conditioned on $E$, the emulation of
$\widetilde{\mathsf{Eval}}$ is flawless, i.e.
$\mathsf{Eval}^{\mathcal{O}}(1^{\lambda},\rho_{f},x)$ and
$\mathsf{Eval}^{\mathcal{O}_{D}}(1^{\lambda},\rho_{f},x)$ are perfectly
indistinguishable. Hence, we can lower-bound the correctness of
$\widetilde{\mathsf{Eval}}$ by lower-bounding the probability of $E$:

$\displaystyle\operatorname*{\mathsf{Pr}}\left[f(x)\leftarrow\widetilde{\mathsf{Eval}}(1^{\lambda},\widetilde{\rho_{f}},x)\
:\
\begin{subarray}{c}\widetilde{\rho_{f}}\leftarrow\widetilde{\mathsf{CP}}(1^{\lambda},d_{f})\\\
\ {x\leftarrow\mathcal{D}_{X}}\end{subarray}\right]$
$\displaystyle=1-\operatorname*{\mathsf{Pr}}\left[y\neq f(x)\ :\
\begin{subarray}{c}\widetilde{\rho_{f}}\leftarrow\widetilde{\mathsf{CP}}(1^{\lambda},d_{f})\\\
\ {x\leftarrow\mathcal{D}_{X}}\\\
y\leftarrow\widetilde{\mathsf{Eval}}(1^{\lambda},\widetilde{\rho_{f}},x)\end{subarray}\right]$
$\displaystyle=1-\operatorname*{\mathsf{Pr}}\left[y\neq f(x_{S+1})\ :\
\begin{subarray}{c}\rho_{f}\leftarrow\mathsf{CP}^{\mathcal{O}}(1^{\lambda},d_{f})\\\
S\xleftarrow{\$}\\{0,1,\dots,T-1\\}\\\ x_{i}\leftarrow\mathcal{D}_{X},\;1\leq
i\leq S+1\\\
\rho_{f}^{i+1}\leftarrow\mathsf{Eval}^{\mathcal{O}}(1^{\lambda},\rho_{f}^{i},x_{i}),\;1\leq
i\leq S\\\
y\leftarrow\mathsf{Eval}^{\mathcal{O}_{D}}(1^{\lambda},\rho_{f}^{S+1},x_{S+1})\end{subarray}\right]$
$\displaystyle\geq
1-\left(\operatorname*{\mathsf{Pr}}\left[E\right]\cdot\operatorname*{\mathsf{Pr}}\left[y\neq
f(x_{S+1})\ :\
\begin{subarray}{c}\rho_{f}\leftarrow\mathsf{CP}^{\mathcal{O}}(1^{\lambda},d_{f})\\\
S\xleftarrow{\$}\\{0,1,\dots,T-1\\}\\\ x_{i}\leftarrow\mathcal{D}_{X},\;1\leq
i\leq S+1\\\
\rho_{f}^{i+1}\leftarrow\mathsf{Eval}^{\mathcal{O}}(1^{\lambda},\rho_{f}^{i},x_{i}),\;1\leq
i\leq S\\\
y\leftarrow\mathsf{Eval}^{\mathcal{O}_{D}}(1^{\lambda},\rho_{f}^{S+1},x_{S+1})\end{subarray}\;\bigg{\rvert}\;E\right]+\operatorname*{\mathsf{Pr}}\left[\neg
E\right]\right)$
$\displaystyle\overset{(\ref{eq:reusable})}{\geq}1-\operatorname*{\mathsf{Pr}}\left[\neg
E\right]-\mathsf{negl}(\lambda).$ (9)

Therefore, the following claim will suffice for the proof together with eq. 9:

######  Claim 23.

$\operatorname*{\mathsf{Pr}}\left[\neg
E\right]\leq\frac{\varepsilon(\lambda)}{2}.$

###### Proof.

Consider the following experiment, which consists of $T$ executions of
$\mathsf{Eval}^{\mathcal{O}}$ with random inputs:

  1. 1.

Let $\mathcal{O}$ be a random oracle.

  2. 2.

Compute $\rho_{f}\leftarrow\mathsf{CP}^{\mathcal{O}}(1^{\lambda},d_{f})$.

  3. 3.

Set $\rho_{f}^{1}:=\rho_{f}$. For $i=1$ to $T$:

    1. (a)

Sample $x_{i}\leftarrow\mathcal{D}_{X}$.

    2. (b)

Compute $\rho_{f}^{i+1}\otimes|y_{i}\rangle\langle
y_{i}|\leftarrow\mathsf{Eval}^{\mathcal{O}}(1^{\lambda},\rho_{f}^{i},x_{i})$.
Let $D_{\mathsf{Eval}}^{i}$ be the set of inputs queried by $\mathsf{Eval}$ in
this step.

Let $w_{i}=\left|\left(D_{\mathsf{Eval}}^{i}\cap
D_{\mathsf{CP}}\right)\setminus\bigcup_{1\leq
j<i}D_{\mathsf{Eval}}^{j}\right|$ be the random variable corresponding to the
number of _new_ queries from $D_{\mathsf{CP}}$ made by
$\mathsf{Eval}^{\mathcal{O}}$ at the $i$th step above. Let
$p_{i}=\operatorname*{\mathsf{Pr}}\left[w_{i}\geq 1\right]$ be the probability
that a new query is made at the $i$th step. Recall that
$\widetilde{\mathsf{Eval}}$ chooses the number of test executions uniformly at
random, hence $\operatorname*{\mathsf{Pr}}\left[\neg
E\right]=\frac{1}{T}\sum_{i=1}^{T}p_{i}$ is the probability that $w_{i}\geq 1$
for a random $i\in[T]$. Now, by linearity of expectation we have

$\displaystyle\sum_{i=1}^{T}p_{i}\leq\sum_{i=1}^{T}\operatorname*{\mathbb{E}}\left[w_{i}\right]=\operatorname*{\mathbb{E}}\left[\sum_{i=1}^{T}w_{i}\right]=\operatorname*{\mathbb{E}}\left[\bigg{|}D_{\mathsf{CP}}\cap\left(\bigcup_{j=1}^{T}D_{\mathsf{Eval}}^{j}\right)\bigg{|}\right]\leq|D_{\mathsf{CP}}|\leq
M.$

Therefore, $\operatorname*{\mathsf{Pr}}\left[\neg
E\right]=\frac{1}{T}\sum_{i=1}^{T}p_{i}\leq\frac{M}{T}\leq\frac{\varepsilon}{2}$
as desired. ∎

##### Copy-Protection Security:

Suppose there is an adversary
$\left(\widetilde{\mathcal{A}},\widetilde{\mathcal{B}},\widetilde{\mathcal{C}}\right)$
which succeeds in the pirating experiment for
$(\widetilde{\mathsf{CP}},\widetilde{\mathsf{Eval}})$ with probability
$\varepsilon$, i.e.

$\operatorname*{\mathsf{Pr}}\left[b=1\ :\
b\leftarrow\mathsf{PirExp}^{\widetilde{\mathsf{CP}},\widetilde{\mathsf{Eval}}}_{\mathcal{D}_{\mathcal{F}},\mathfrak{D}_{X}}\left(1^{\lambda},\left(\widetilde{\mathcal{A}},\widetilde{\mathcal{B}},\widetilde{\mathcal{C}}\right)\right)\right]=\varepsilon.$

Using
$\left(\widetilde{\mathcal{A}},\widetilde{\mathcal{B}},\widetilde{\mathcal{C}}\right)$,
we will construct an adversary
$\left({\mathcal{A}}^{\mathcal{O}},\mathcal{B}^{\mathcal{O}},{\mathcal{C}}^{\mathcal{O}}\right)$
which succeeds in the pirating experiment for $(\mathsf{CP},\mathsf{Eval})$
with probability $\varepsilon$. This will immediately imply $\delta$-security
of $(\widetilde{\mathsf{CP}},\widetilde{\mathsf{Eval}})$ by the
$\delta$-security of $(\mathsf{CP},\mathsf{Eval})$.

We set $\mathcal{B}^{\mathcal{O}}$ and ${\mathcal{C}}^{\mathcal{O}}$ to be
identical to $\widetilde{\mathcal{B}}$ and $\widetilde{\mathcal{C}}$,
respectively, so that they do not make any queries. We define
${\mathcal{A}}^{\mathcal{O}}$, which has oracle access to $\mathcal{O}$, as
follows:

  1. 1.

Given a copy-protected program $\rho_{f}=:\rho_{f}^{1}$, pick
$S\xleftarrow{\$}\\{0,1,\dots,T-1\\}$ and repeat for $i=1$ to $S$:

    1. (a)

Sample $x_{i}\leftarrow\mathcal{D}_{X}$

    2. (b)

Run $\rho_{f}^{i+1}\otimes|y_{i}\rangle\langle
y_{i}|\leftarrow\mathsf{Eval}^{\mathcal{O}}(1^{\lambda},\rho_{f}^{i},x_{i})$,
forwarding the oracle queries of $\mathsf{Eval}$ to $\mathcal{O}$ and
recording them with their answers in a database $D_{\mathsf{Eval}}^{i}$.

  2. 2.

Sample random oracle answers $r_{1},r_{2},\dots,r_{N}\xleftarrow{\$}Y$.

  3. 3.

Set
$\widetilde{\rho_{f}}:=\rho_{f}^{S+1}\otimes|D_{\mathsf{Eval}}\rangle\langle
D_{\mathsf{Eval}}|\bigotimes_{j=1}^{N}|r_{j}\rangle\langle r_{j}|$, where
$D_{\mathsf{Eval}}:=\bigcup_{i=1}^{S}D_{\mathsf{Eval}}^{i}$.

  4. 4.

Run $\widetilde{\mathcal{A}}$ on the state $\widetilde{\rho_{f}}$.

By construction, the bipartite state received by $\mathcal{B}^{\mathcal{O}}$
and ${\mathcal{C}}^{\mathcal{O}}$ is identical to that received by
$\mathcal{B}$ and $\mathcal{C}$. This is because the on-the-fly simulation
done by $\widetilde{\mathsf{CP}}$ is perfectly indistinguishable from the real
oracle answers provided by $\mathcal{O}$. Therefore,

$\displaystyle\operatorname*{\mathsf{Pr}}\left[b=1\ :\
b\leftarrow\mathsf{PirExp}^{\mathsf{CP},\mathsf{Eval}}_{\mathcal{D}_{\mathcal{F}},\mathfrak{D}_{X}}\left(1^{\lambda},(\mathcal{A},\mathcal{B},\mathcal{C})\right)\right]$
$\displaystyle=$ $\displaystyle\operatorname*{\mathsf{Pr}}\left[b=1\ :\
b\leftarrow\mathsf{PirExp}^{\widetilde{\mathsf{CP}},\widetilde{\mathsf{Eval}}}_{\mathcal{D}_{\mathcal{F}},\mathfrak{D}_{X}}\left(1^{\lambda},\left(\widetilde{\mathcal{A}},\widetilde{\mathcal{B}},\widetilde{\mathcal{C}}\right)\right)\right]=\varepsilon$

as desired.

∎

## References

  * [Aar04] Scott Aaronson.  Limitations of quantum advice and one-way communication.  In Proceedings of the 19th IEEE Annual Conference on Computational Complexity, CCC ’04, page 320–332, USA, 2004. IEEE Computer Society.
  * [Aar09] Scott Aaronson.  Quantum copy-protection and quantum money.  In 2009 24th Annual IEEE Conference on Computational Complexity, pages 229–242. IEEE, 2009.
  * [ABDS21] Gorjan Alagic, Zvika Brakerski, Yfke Dulek, and Christian Schaffner.  Impossibility of quantum virtual black-box obfuscation of classical circuits.  In CRYPTO, 2021.
  * [AC12] Scott Aaronson and Paul Christiano.  Quantum money from hidden subspaces.  In Proceedings of the forty-fourth annual ACM symposium on Theory of computing, pages 41–60, 2012.
  * [AGKZ20] Ryan Amos, Marios Georgiou, Aggelos Kiayias, and Mark Zhandry.  One-shot signatures and applications to hybrid quantum/classical authentication.  In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, pages 255–268, 2020.
  * [AK21] Prabhanjan Ananth and Fatih Kaleoglu.  Uncloneable encryption, revisited.  In TCC, 2021.
  * [AKL+22] Prabhanjan Ananth, Fatih Kaleoglu, Xingjian Li, Qipeng Liu, and Mark Zhandry.  On the feasibility of unclonable encryption, and more.  In CRYPTO, 2022.
  * [ALL+21] Scott Aaronson, Jiahui Liu, Qipeng Liu, Mark Zhandry, and Ruizhe Zhang.  New approaches for quantum copy-protection.  In CRYPTO, 2021.
  * [ALP21] Prabhanjan Ananth and Rolando L La Placa.  Secure software leasing.  In Eurocrypt, 2021.
  * [BDF+11] Dan Boneh, Özgür Dagdelen, Marc Fischlin, Anja Lehmann, Christian Schaffner, and Mark Zhandry.  Random oracles in a quantum world.  In International conference on the theory and application of cryptology and information security, pages 41–69. Springer, 2011.
  * [BI20] Anne Broadbent and Rabib Islam.  Quantum encryption with certified deletion.  In Theory of Cryptography Conference, pages 92–122. Springer, 2020\.
  * [BJ15] Anne Broadbent and Stacey Jeffery.  Quantum homomorphic encryption for circuits of low t-gate complexity.  In Annual Cryptology Conference, pages 609–629. Springer, 2015\.
  * [BJL+21] Anne Broadbent, Stacey Jeffery, Sébastien Lord, Supartha Podder, and Aarthi Sundaram.  Secure software leasing without assumptions.  In TCC, 2021.
  * [BL20] Anne Broadbent and Sébastien Lord.  Uncloneable quantum encryption via oracles.  In TQC, 2020.
  * [Bra18] Zvika Brakerski.  Quantum fhe (almost) as secure as classical.  In Annual International Cryptology Conference, pages 67–95. Springer, 2018.
  * [BV16] Nir Bitansky and Vinod Vaikuntanathan.  Indistinguishability obfuscation: from approximate to exact.  In Theory of Cryptography Conference, pages 67–95. Springer, 2016\.
  * [CDM20] Orestis Chardouvelis, Nico Doettling, and Giulio Malavolta.  Rate-1 secure function evaluation for bqp.  Cryptology ePrint Archive, Report 2020/1454, 2020.  https://ia.cr/2020/1454.
  * [CKP15] Ran Canetti, Yael Tauman Kalai, and Omer Paneth.  On obfuscation with random oracles.  In Yevgeniy Dodis and Jesper Buus Nielsen, editors, Theory of Cryptography, pages 456–467, Berlin, Heidelberg, 2015. Springer Berlin Heidelberg.
  * [CLLZ21] Andrea Coladangelo, Jiahui Liu, Qipeng Liu, and Mark Zhandry.  Hidden cosets and applications to unclonable cryptography.  In CRYPTO, 2021.
  * [CMP20] Andrea Coladangelo, Christian Majenz, and Alexander Poremba.  Quantum copy-protection of compute-and-compare programs in the quantum random oracle model.  arXiv preprint arXiv:2009.13865, 2020.
  * [Die82] DGBJ Dieks.  Communication by epr devices.  Physics Letters A, 92(6):271–272, 1982.
  * [GKVW19] Rishab Goyal, Venkata Koppula, Satyanarayana Vusirikala, and Brent Waters.  On perfect correctness in (lockable) obfuscation.  2019\.
  * [GKW17] Rishab Goyal, Venkata Koppula, and Brent Waters.  Lockable obfuscation.  In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), pages 612–621. IEEE, 2017.
  * [Got02] Daniel Gottesman.  Uncloneable encryption.  arXiv preprint quant-ph/0210062, 2002.
  * [GZ20] Marios Georgiou and Mark Zhandry.  Unclonable decryption keys.  IACR Cryptol. ePrint Arch, 877(2020):3, 2020.
  * [KNY21] Fuyuki Kitagawa, Ryo Nishimaki, and Takashi Yamakawa.  Secure software leasing from standard assumptions.  In TCC, 2021.
  * [Mah18] Urmila Mahadev.  Classical homomorphic encryption for quantum circuits.  In 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), pages 332–338. IEEE, 2018.
  * [RS19] Roy Radian and Sattath.  Semi-quantum money.  Proceedings of the 1st ACM Conference on Advances in Financial Technologies, Oct 2019.
  * [Wie83] Stephen Wiesner.  Conjugate coding.  ACM Sigact News, 15(1):78–88, 1983.
  * [Win99] A. Winter.  Coding theorem and strong converse for quantum channels.  IEEE Transactions on Information Theory, 45(7):2481–2485, 1999\.
  * [WZ82] William K Wootters and Wojciech H Zurek.  A single quantum cannot be cloned.  Nature, 299(5886):802–803, 1982.
  * [WZ17] Daniel Wichs and Giorgos Zirdelis.  Obfuscating compute-and-compare programs under lwe.  In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), pages 600–611. IEEE, 2017.
  * [Zha19a] Mark Zhandry.  How to record quantum queries, and applications to quantum indifferentiability.  In Alexandra Boldyreva and Daniele Micciancio, editors, Advances in Cryptology – CRYPTO 2019, pages 239–268, Cham, 2019. Springer International Publishing.
  * [Zha19b] Mark Zhandry.  Quantum lightning never strikes the same state twice.  In Annual International Conference on the Theory and Applications of Cryptographic Techniques, pages 408–438. Springer, 2019.


properties of the first ten pointings of MALS, with the ultimate goal of
measuring the cosmic radio dipole. To achieve a measurement of number counts
unbiased by the inhomogeneities present between the MALS pointings, we have
characterised systematic effects that can influence such a measurement. This
assessment of systematic effects in the ten pointings as presented in this
work shows that these effects are for the most part predictable and can be
properly accounted for. This will eventually not only benefit a dipole
measurement, but all continuum science carried out with MALS. In the current
literature on the cosmic dipole there are many examples of systematic effects
that limit the sensitivity of these estimates, that could not be further
pushed due to a lack of information on the inner workings of the surveys that
were used. For MALS, we have a complete assessment of the inner workings of
the survey, with insight and access into the processing pipeline. Looking
forward, we determine that 100 MALS pointings suffice for a dipole
measurement. Paired with the analysis on source characteristics and counts in
the pointings, we are poised to perform the most complete dipole estimate of a
radio survey thus far.

Calibration and imaging of all the data is carried out through ARTIP. After
imaging we separately create spectral index images, and perform primary beam
correction averaged over the frequency range on these and the continuum images
with a primary beam model derived from holographic measurements. We make an
initial assessment of calibration by checking the flux density scale of the
calibrators and central sources, and find that flux densities are consistent
with those reported in the literature. We investigate the quality of the
images by looking at the RMS noise maps created by PyBDSF. Measuring RMS noise
coverage shows that all pointings have similar noise structure, but overall
noise levels are offset between the pointings. We quantify this offset with
$\sigma_{20}$, which gives the noise level at 20% RMS noise coverage for a
pointing. To try to explain the difference in pointing quality, we calculate
demerit scores for each pointing to estimate the contributions of bright
sources to the noise. Though there is a correlation between the noise in a
pointing and demerit score, other factors play a part that introduce a scatter
in this relation, especially for pointings with lower demerit scores. As
$\sigma_{20}$ directly describes the overall noise in the image, it is the
quality measure of choice for the pointings.

We perform source extraction on all the images using PyBDSF, and convert
PyBDSF catalogues to full Stokes I catalogues, extending them to include
spectral indices and flagging artefacts. We consider sources that have been
fit with multiple Gaussian components to be potentially complex and visually
inspect them to investigate how well the Gaussian fit describes these sources.
We further assess the quality of the individual pointings and how it affects
source finding by measuring completeness, flux recovery, and purity. For
completeness and flux recovery we need to know the intrinsic properties of the
sources in the images, so we create mock catalogues of sources from the SKADS
simulated sample and inject these into the residual images of the pointings.
We assess completeness separately for unresolved and resolved sources. Using
unresolved sources, we assess completeness as a function of distance from the
pointing centre, and for resolved sources we investigate completeness as a
function of source size.

Combining the catalogues of the individual pointings, we correct for residual
primary beam effects in the flux densities and spectral indices sources
originating from the frequency dependence of the primary beam. To check these
corrections and other potential systematic effects, we cross-match the
catalogues with NVSS to check if positions and flux densities are consistent.
There is no appreciable astrometric offset, however there is a 18% offset in
flux density compared to NVSS, though still within the uncertainties. Using
$\sigma_{20}$ as a normalisation factor, we combine completeness measures from
the individual pointings and find unified completeness relations that hold for
all pointings. Combining flux recovery statistics from all pointings, we find
that a systematic bias is present in the integrated flux densities from the
fitted Gaussians in the catalogue. This bias is not present in the integrated
flux densities of the islands which the sources occupy, making this quantity
the logical choice of flux density for the here presented analysis. Combining
purity from all pointings, we find that we can account for 20% of false
detections with a suitable artefact identification scheme. The remaining false
detections are shown to make up an increasing fraction of sources further out
from the pointing centre.

As the full catalogues are expected to be populated by various sources types,
we assess how these can influence source counts. Looking at the number of
Gaussian components fit to sources, we see that the number of components
needed to describe sources increases as a function of flux density until it
stagnates at around 100 mJy. This implies that around this flux density
sources separate and can be counted multiple times, however as only a tiny
percentage of sources is present at these flux densities, it is unlikely to
bias the source counts. To further differentiate between source populations,
we look at spectral indices of sources, and find that we can reasonably
separate core-dominated FRI and lobe-dominated FRII sources by making a cut at
$\alpha=-0.5$. At low flux densities we find that spectral indices are much
steeper than expected which is likely caused by low S/N and inadequate
modelling by the MTMFS deconvolution scheme.

Finally, to show that we can account for the systematic effects present in the
catalogues, we calculate and correct differential number counts for a set of
simulated catalogues using the SKADS simulated sample. We find that a simple
correction using only the RMS noise coverage produces correct number counts
down to 100-200 µJy. We then compute differential number counts for the full
catalogue and correct number counts using combined completeness measures found
for unresolved and resolved sources, as well as the RMS noise coverage. Once
again, corrections seem to hold down to 100-200 µJy. Comparing these number
counts to the expected number counts from the SKADS sample, we see that our
number counts are higher in the full range of probed flux densities. This is
independent of corrections, so a likely explanation is that MALS is probing
overdense regions, as it targets bright sources. The same effect can however
be (partially) produced by a systematic flux density offset, which should be
taken into consideration given the results on the flux density scale.

Using both the demerit score to predict the quality of other MALS pointings
and the corrected number counts of this sample, we show that we will require
100 MALS pointings to reach the necessary number counts for a $3\sigma$
measurement of the dipole. Going further, we assert that we can assess the
dipole on the level of individual sources using the information on flux
density scale, completeness, purity, flux errors, and position errors. The
precise implementation is left to later works, along with a exploration of
viable dipole estimators.

###### Acknowledgements.

We thank the anonymous referee for their useful comments and feedback. We
thank Charles Walker for his insightful comments and feedback on the text. JDW
acknowledges the support from the International Max Planck Research School
(IMPRS) for Astronomy and Astrophysics at the Universities of Bonn and
Cologne. EB acknowledges support by NASA under award number 80GSFC21M0002. PK
is partially supported by the BMBF project 05A17PC2 for D-MeerKAT II. The
MeerKAT telescope is operated by the South African Radio Astronomy
Observatory, which is a facility of the National Research Foundation, an
agency of the Department of Science and Innovation. The MeerKAT data were
processed using the MALS computing facility at IUCAA
(https://mals.iucaa.in/releases). The Common Astronomy Software Applications
(CASA) package is developed by an international consortium of scientists based
at the National Radio Astronomical Observatory (NRAO), the European Southern
Observatory (ESO), the National Astronomical Observatory of Japan (NAOJ), the
Academia Sinica Institute of Astronomy and Astrophysics (ASIAA), the CSIRO
division for Astronomy and Space Science (CASS), and the Netherlands Institute
for Radio Astronomy (ASTRON) under the guidance of NRAO. The National Radio
Astronomy Observatory is a facility of the National Science Foundation
operated under cooperative agreement by Associated Universities, Inc.

## References

  * Baars et al. (1977) Baars, J. W. M., Genzel, R., Pauliny-Toth, I. I. K., & Witzel, A. 1977, A&A, 61, 99
  * Bengaly et al. (2018) Bengaly, C. A. P., Maartens, R., & Santos, M. G. 2018, J. Cosmology Astropart. Phys., 2018, 031
  * Bengaly et al. (2019) Bengaly, C. A. P., Siewert, T. M., Schwarz, D. J., & Maartens, R. 2019, MNRAS, 486, 1350
  * Bhatnagar et al. (2008) Bhatnagar, S., Cornwell, T. J., Golap, K., & Uson, J. M. 2008, A&A, 487, 419
  * Blake & Wall (2002) Blake, C. & Wall, J. 2002, Nature, 416, 150
  * Blum et al. (2016) Blum, R. D., Burleigh, K., Dey, A., et al. 2016, in American Astronomical Society Meeting Abstracts, Vol. 228, American Astronomical Society Meeting Abstracts #228, 317.01
  * Bonaldi et al. (2019) Bonaldi, A., Bonato, M., Galluzzi, V., et al. 2019, MNRAS, 482, 2
  * Bridle & Schwab (1999) Bridle, A. H. & Schwab, F. R. 1999, in Astronomical Society of the Pacific Conference Series, Vol. 180, Synthesis Imaging in Radio Astronomy II, ed. G. B. Taylor, C. L. Carilli, & R. A. Perley, 371
  * Briggs (1995) Briggs, D. S. 1995, PhD thesis
  * Colin et al. (2017) Colin, J., Mohayaee, R., Rameez, M., & Sarkar, S. 2017, MNRAS, 471, 1045
  * Combes et al. (2021) Combes, F., Gupta, N., Muller, S., et al. 2021, A&A, 648, A116
  * Condon et al. (1998) Condon, J. J., Cotton, W. D., Greisen, E. W., et al. 1998, AJ, 115, 1693
  * Condon & Ransom (2016) Condon, J. J. & Ransom, S. M. 2016, Essential Radio Astronomy
  * Cornwell & Fomalont (1989) Cornwell, T. & Fomalont, E. B. 1989, in Astronomical Society of the Pacific Conference Series, Vol. 6, Synthesis Imaging in Radio Astronomy, ed. R. A. Perley, F. R. Schwab, & A. H. Bridle, 185
  * Cornwell et al. (2005) Cornwell, T. J., Golap, K., & Bhatnagar, S. 2005, in Astronomical Society of the Pacific Conference Series, Vol. 347, Astronomical Data Analysis Software and Systems XIV, ed. P. Shopbell, M. Britton, & R. Ebert, 86
  * Crawford (2009) Crawford, F. 2009, ApJ, 692, 887
  * Darling (2022) Darling, J. 2022, ApJ, 931, L14
  * de Villiers & Cotton (2022) de Villiers, M. S. & Cotton, W. D. 2022, AJ, 163, 135
  * Deka et al. (2022) Deka, P., Gupta, N., & Jagannathan, P. 2022, ApJ, submitted
  * Eddington (1913) Eddington, A. S. 1913, MNRAS, 73, 359
  * Ellis & Baldwin (1984) Ellis, G. F. R. & Baldwin, J. E. 1984, MNRAS, 206, 377
  * Fanaroff & Riley (1974) Fanaroff, B. L. & Riley, J. M. 1974, MNRAS, 167, 31P
  * Franzen et al. (2015) Franzen, T. M. O., Banfield, J. K., Hales, C. A., et al. 2015, MNRAS, 453, 4020
  * Grobler et al. (2014) Grobler, T. L., Nunhokee, C. D., Smirnov, O. M., van Zyl, A. J., & de Bruyn, A. G. 2014, MNRAS, 439, 4030
  * Gupta et al. (2021) Gupta, N., Jagannathan, P., Srianand, R., et al. 2021, ApJ, 907, 11
  * Gupta et al. (2022) Gupta, N., Shukla, G., Srianand, R., et al. 2022, ApJ, 929, 108
  * Gupta et al. (2016) Gupta, N., Srianand, R., Baan, W., et al. 2016, in MeerKAT Science: On the Pathway to the SKA, 14
  * Hale et al. (2021) Hale, C. L., McConnell, D., Thomson, A. J. M., et al. 2021, PASA, 38, e058
  * Hale et al. (2019) Hale, C. L., Robotham, A. S. G., Davies, L. J. M., et al. 2019, MNRAS, 487, 3971
  * Hale et al. (2022) Hale, C. L., Whittam, I. H., Jarvis, M. J., et al. 2022, arXiv e-prints, arXiv:2211.05741
  * Heywood et al. (2020) Heywood, I., Hale, C. L., Jarvis, M. J., et al. 2020, MNRAS, 496, 3469
  * Heywood et al. (2013) Heywood, I., Jarvis, M. J., & Condon, J. J. 2013, MNRAS, 432, 2625
  * Holschneider et al. (1989) Holschneider, M., Kronland-Martinet, R., Morlet, J., & Tchamitchian, P. 1989, in Wavelets, ed. J.-M. Combes, A. Grossmann, & P. Tchamitchian (Berlin, Heidelberg: Springer Berlin Heidelberg), 286–297
  * Intema et al. (2017) Intema, H. T., Jagannathan, P., Mooley, K. P., & Frail, D. A. 2017, A&A, 598, A78
  * Lacy et al. (2020) Lacy, M., Baum, S. A., Chandler, C. J., et al. 2020, PASP, 132, 035001
  * Lineweaver (1997) Lineweaver, C. H. 1997, in Microwave Background Anisotropies, Vol. 16, 69–75
  * Longair & Scheuer (1966) Longair, M. S. & Scheuer, P. A. G. 1966, MNRAS, 133, 421
  * LSST Science Collaboration et al. (2009) LSST Science Collaboration, Abell, P. A., Allison, J., et al. 2009, arXiv e-prints, arXiv:0912.0201
  * Matthews et al. (2021) Matthews, A. M., Condon, J. J., Cotton, W. D., & Mauch, T. 2021, ApJ, 909, 193
  * Mauch et al. (2020) Mauch, T., Cotton, W. D., Condon, J. J., et al. 2020, ApJ, 888, 61
  * Mauch et al. (2003) Mauch, T., Murphy, T., Buttery, H. J., et al. 2003, MNRAS, 342, 1117
  * McConnell et al. (2020) McConnell, D., Hale, C. L., Lenc, E., et al. 2020, PASA, 37
  * Mohan & Rafferty (2015) Mohan, N. & Rafferty, D. 2015, Astrophysics Source Code Library, ascl:1502.007
  * Penzias & Wilson (1965) Penzias, A. A. & Wilson, R. W. 1965, ApJ, 142, 419
  * Perley & Butler (2017) Perley, R. A. & Butler, B. J. 2017, ApJS, 230, 7
  * Rau & Cornwell (2011) Rau, U. & Cornwell, T. J. 2011, A&A, 532, A71
  * Rengelink et al. (1997) Rengelink, R. B., Tang, Y., de Bruyn, A. G., et al. 1997, A&AS, 124, 259
  * Rubart & Schwarz (2013) Rubart, M. & Schwarz, D. J. 2013, A&A, 555, 1
  * Ryle & Scheuer (1955) Ryle, M. & Scheuer, P. a. G. 1955, Proceedings of the Royal Society of London. Series A. Mathematical and Physical Sciences, 230, 448
  * Secrest et al. (2022) Secrest, N. J., von Hausegger, S., Rameez, M., Mohayaee, R., & Sarkar, S. 2022, ApJ, 937, L31
  * Secrest et al. (2021) Secrest, N. J., von Hausegger, S., Rameez, M., et al. 2021, ApJ, 908, L51
  * Shimwell et al. (2019) Shimwell, T. W., Tasse, C., Hardcastle, M. J., et al. 2019, A&A, 622, A1
  * Siewert et al. (2021) Siewert, T. M., Schmidt-Rubart, M., & Schwarz, D. J. 2021, A&A, 653, A9
  * Singal (2011) Singal, A. K. 2011, ApJ, 742, L23
  * Singal (2019) Singal, A. K. 2019, Phys. Rev. D, 100, 063501
  * Singal (2021) Singal, A. K. 2021, Universe, 7, 107
  * Smolčić et al. (2017) Smolčić, V., Novak, M., Bondi, M., et al. 2017, A&A, 602, A1
  * Taylor & Legodi (2021) Taylor, A. & Legodi, L. 2021, Data Products for Polarization of MeerKAT Calibrators
  * THE CASA TEAM et al. (2022) THE CASA TEAM, Bean, B., Bhatnagar, S., et al. 2022, arXiv e-prints, arXiv:2210.02276
  * Tiwari & Jain (2013) Tiwari, P. & Jain, P. 2013, MNRAS, 447, 2658
  * Tiwari et al. (2015) Tiwari, P., Kothari, R., Naskar, A., Nadkarni-Ghosh, S., & Jain, P. 2015, Astroparticle Physics, 61, 1
  * Wilman et al. (2008) Wilman, R. J., Miller, L., Jarvis, M. J., et al. 2008, MNRAS, 388, 1335

##  Appendix A Cutouts of bright FRI and FRII sources

Figure 26: Selection of brightest sources in the combined catalogue with
$\alpha>=-0.5$. As discussed in Section 5.2, this range of spectral indices is
expected to come from emission originating in AGN cores, which are generally
point sources. The majority of this sample indeed is unresolved or can be seen
to dominate the emission from their associated lobes.

Figure 27: Selection of brightest sources from the combined catalogue with
$\alpha<-0.5$. As discussed in Section 5.2, this range of spectral indices is
generally associated with synchrotron, which is the dominant emission
mechanism in radio lobes. Though a number of sources in this sample are
unresolved, many show the two component structure characteristic of FRIIs or
even more complex extended structure.

##  Appendix B Table of sources

Table 4: Example of the final source catalogue structure. Columns are as
described in Section 4.5.

Pointing_id | Source_name | Source_id | Isl_id | RA | E_RA | DEC | E_DEC | Sep_PC
---|---|---|---|---|---|---|---|---
|  |  |  | J2000, $\degree$ | $\degree$ | J2000, $\degree$ | $\degree$ | $\degree$
PT-J0001-1540 | J000012.63-154312.0 | 1607 | 1618 | 0.052609 | 6.82e-05 | -15.720001 | 9.42e-05 | 0.36
PT-J0006+1728 | J000409.33+163842.5 | 1285 | 1331 | 1.038859 | 8.34e-05 | 16.645139 | 1.36e-04 | 1.04
PT-J0126+1420 | J012317.38+133309.1 | 1504 | 1530 | 20.822411 | 1.70e-04 | 13.552529 | 1.65e-04 | 1.06
PT-J0240+0957 | J023823.97+094637.3 | 888 | 904 | 39.599861 | 3.05e-05 | 9.777035 | 5.93e-05 | 0.54
PT-J0249+0440 | J024648.18+035955.5 | 1469 | 1483 | 41.700764 | 8.47e-05 | 3.998738 | 1.61e-04 | 0.98
PT-J0249-0759 | J024633.91-073732.5 | 2518 | 2529 | 41.641290 | 1.64e-04 | -7.625700 | 2.18e-04 | 0.83
PT-J1133+0015 | J113059.76+000708.0 | 708 | 717 | 172.749000 | 2.06e-04 | 0.118892 | 2.53e-04 | 0.53
PT-J1232-0224 | J122945.15-021418.1 | 507 | 517 | 187.438138 | 1.29e-04 | -2.238372 | 1.77e-04 | 0.59
PT-J1312-2026 | J130900.75-204924.6 | 2326 | 2334 | 197.253139 | 4.04e-05 | -20.823501 | 5.03e-05 | 0.82
PT-J2023-3655 | J202008.96-371033.3 | 2055 | 2067 | 305.037343 | 2.38e-04 | -37.175915 | 1.73e-04 | 0.77

Total_flux | E_Total_flux | Peak_flux | E_Peak_flux | Spectral_index | Spectral_index_correction | E_Spectral_index
---|---|---|---|---|---|---
mJy | mJy | mJy/beam | mJy/beam |  |  |
0.409 | 0.050 | 0.273 | 0.022 | -1.90 | 0.10 | 0.21
4.564 | 0.458 | 2.101 | 0.151 | -0.10 | 0.80 | 0.09
19.007 | 1.561 | 2.288 | 0.121 | -0.53 | 0.83 | 0.07
4.692 | 0.368 | 2.575 | 0.062 | -0.74 | 0.21 | 0.05
1.418 | 0.231 | 0.985 | 0.102 | 0.46 | 0.72 | 0.16
0.421 | 0.113 | 0.285 | 0.049 | -0.94 | 0.51 | 0.27
0.423 | 0.114 | 0.254 | 0.046 | -1.51 | 0.21 | 0.10
0.530 | 0.121 | 0.394 | 0.057 | -2.36 | 0.25 | 0.10
1.761 | 0.117 | 1.136 | 0.050 | 0.09 | 0.50 | 0.07
0.511 | 0.116 | 0.306 | 0.047 | -1.56 | 0.43 | 0.23

RA_max | E_RA_max | DEC_max | E_DEC_max | Maj | E_Maj | Min | E_Min | PA | E_PA
---|---|---|---|---|---|---|---|---|---
J2000, $\degree$ | $\degree$ | J2000, $\degree$ | $\degree$ | ′′ | ′′ | ′′ | ′′ | $\degree$ | $\degree$
0.052609 | 6.82e-05 | -15.720001 | 9.42e-05 | 9.35 | 0.80 | 7.78 | 0.57 | 6.66 | 19.55
1.038859 | 8.34e-05 | 16.645139 | 1.36e-04 | 14.55 | 1.16 | 10.66 | 0.70 | 171.83 | 11.22
20.824116 | 1.70e-04 | 13.551953 | 1.65e-04 | 19.38 | 1.50 | 17.70 | 1.33 | 38.22 | 36.76
39.601394 | 3.05e-05 | 9.776665 | 5.93e-05 | 14.21 | 0.51 | 9.25 | 0.25 | 80.33 | 3.76
41.700764 | 8.47e-05 | 3.998738 | 1.61e-04 | 11.36 | 1.38 | 7.74 | 0.69 | 10.10 | 13.35
41.641290 | 1.64e-04 | -7.625700 | 2.18e-04 | 10.19 | 1.97 | 7.82 | 1.22 | 154.03 | 30.80
172.749000 | 2.06e-04 | 0.118892 | 2.53e-04 | 11.83 | 2.42 | 8.42 | 1.34 | 146.13 | 26.09
187.438138 | 1.29e-04 | -2.238372 | 1.77e-04 | 9.72 | 1.53 | 7.90 | 1.04 | 162.61 | 31.48
197.253139 | 4.04e-05 | -20.823501 | 5.03e-05 | 9.35 | 0.43 | 8.03 | 0.33 | 17.92 | 12.99
305.037343 | 2.38e-04 | -37.175915 | 1.73e-04 | 12.52 | 2.08 | 9.91 | 1.38 | 72.24 | 30.76

DC_Maj | E_DC_Maj | DC_Min | E_DC_Min | DC_PA | E_DC_PA
---|---|---|---|---|---
′′ | ′′ | ′′ | ′′ | $\degree$ | $\degree$
5.60 | 0.80 | 4.16 | 0.57 | 31.11 | 19.55
9.03 | 1.16 | 8.62 | 0.70 | 161.03 | 11.22
17.71 | 1.50 | 15.05 | 1.33 | 64.76 | 36.76
0.00 | 0.51 | 0.00 | 0.25 | 0.00 | 3.76
6.93 | 1.38 | 3.53 | 0.69 | 22.80 | 13.35
6.49 | 1.97 | 3.62 | 1.22 | 141.44 | 30.80
8.15 | 2.42 | 4.45 | 1.34 | 133.16 | 26.09
4.97 | 1.53 | 3.85 | 1.04 | 135.68 | 31.48
6.02 | 0.43 | 4.12 | 0.33 | 44.66 | 12.99
8.28 | 2.08 | 4.65 | 1.38 | 29.77 | 30.76

Table 5: continued

Isl_Total_flux | E_Isl_Total_flux | Isl_rms | Isl_mean | Resid_Isl_rms | Resid_Isl_mean | S_Code | N_Gaus
---|---|---|---|---|---|---|---
mJy/beam | mJy/beam | mJy/beam | mJy/beam |  |  |  |
0.369 | 0.034 | 0.020 | -0.004 | 0.007 | -0.004 | S | 1
4.343 | 0.276 | 0.141 | -0.021 | 0.121 | -0.002 | S | 1
11.940 | 0.416 | 0.121 | -0.010 | 0.121 | -0.010 | M | 2
3.954 | 0.160 | 0.062 | 0.005 | 0.021 | 0.004 | M | 2
1.231 | 0.136 | 0.098 | -0.020 | 0.019 | -0.019 | S | 1
0.349 | 0.060 | 0.047 | -0.000 | 0.009 | -0.000 | S | 1
0.384 | 0.064 | 0.043 | 0.003 | 0.003 | 0.003 | S | 1
0.426 | 0.065 | 0.054 | -0.001 | 0.006 | -0.001 | S | 1
1.613 | 0.082 | 0.046 | -0.019 | 0.035 | -0.014 | S | 1
0.373 | 0.056 | 0.043 | -0.008 | 0.007 | -0.008 | S | 1

RA_mean | DEC_mean | Cutout_Spectral_index | Cutout_Total_flux | Cutout_flag | Cutout_class | Resolved | Flag_artifact
---|---|---|---|---|---|---|---
J2000, $\degree$ | J2000, $\degree$ |  | mJy |  |  |  |
– | – | – | – | – | – | True | False
– | – | – | – | – | – | True | False
20.822423 | 13.552525 | 10.482 | -0.24 | C | I | True | False
39.599830 | 9.777032 | 3.583 | -0.75 | C | P | True | False
– | – | – | – | – | – | True | False
– | – | – | – | – | – | False | False
– | – | – | – | – | – | True | False
– | – | – | – | – | – | False | False
– | – | – | – | – | – | True | False
– | – | – | – | – | – | False | False