# Device-independent uncloneable encryption

Srijita Kundu Institute for Quantum Computing and Department of Combinatorics
and Optimization, University of Waterloo, Waterloo, Ontario N2L 3G1, Canada.
<EMAIL_ADDRESS>Ernest Y.-Z. Tan Institute for Quantum Computing
and Department of Physics and Astronomy, University of Waterloo, Waterloo,
Ontario N2L 3G1, Canada<EMAIL_ADDRESS>
###### Abstract

Uncloneable encryption, first introduced by Broadbent and Lord (TQC 2020) is a
quantum encryption scheme in which a quantum ciphertext cannot be distributed
between two non-communicating parties such that, given access to the
decryption key, both parties cannot learn the underlying plaintext. In this
work, we introduce a variant of uncloneable encryption in which several
possible decryption keys can decrypt a particular encryption, and the security
requirement is that two parties who receive independently generated decryption
keys cannot both learn the underlying ciphertext. We show that this variant of
uncloneable encryption can be achieved device-independently, i.e., without
trusting the quantum states and measurements used in the scheme. Moreover, we
show that this variant of uncloneable encryption works just as well as the
original definition in constructing quantum money, and can be used to get
uncloneable bits without using the quantum random oracle model.

##  1 Introduction

A fundamental difference between classical and quantum information lies in the
fact that quantum information cannot be perfectly copied. This property can be
used to do cryptography, as was noted by Wiesner [Wie83], who gave the first
scheme for _quantum money_ which cannot be forged. Later [Got03] considered
the question of whether in the context of encryption schemes, one could
construct a form of _uncloneable encryption_ ; i.e. quantum ciphertexts that
in some sense cannot be copied. Pursuing this line of reasoning, [Got03]
developed an encryption scheme in which an adversary attempting to copy a
quantum ciphertext would be caught with high probability by the intended
(honest) recipient. Following up on a question posed in that work, [BL20]
subsequently constructed an encryption scheme achieving a slightly different
notion of uncloneable encryption111[BL20] refer to the scheme in [Got03] as
one that achieves _tamper-detection_ rather than uncloneability; in this work
we follow their terminology rather than the original terminology in [Got03].,
namely a quantum ciphertext that cannot be distributed amongst two parties in
such a way that they can both decrypt the message with high probability (after
obtaining the decryption key).

An uncloneable encryption scheme needs to satisfy a standard notion of
indistinguishability (or semantic security) that any encryption scheme needs
to satisfy. Aside from this, [BL20] introduced two notions of security that an
uncloneable encryption scheme should satisfy: uncloneability and uncloneable-
indistinguishability. The uncloneable encryption scheme given [BL20] was a
simple construction based on Wiesner states and monogamy of entanglement
games. While this scheme achieved uncloneability in the plain model, it did
not achieve uncloneable-indistinguishability, even in the quantum random
oracle model (QROM). In particular, this means that their scheme cannot do
uncloneable encryption of single-bit messages.

Following [BL20], there have been several subsequent works on uncloneable
encryption. [MST21] showed that uncloneable-indistinguishability cannot be
achieved by schemes using certain kinds of states, and other limitations of
the proof techniques employed in [BL20]. [AK21] considered public-key
uncloneable encryption; [GMP22] gave a protocol for uncloneable encryption
based on the post-quantum hardness of the learning with errors (LWE) problem.
Recently, [AKL+22] gave a more complicated uncloneable encryption protocol
based on subset coset states that achieves uncloneable-indistinguishability in
the QROM. Moreover, [AKL+22] also gave some impossibility results showing that
certain kinds of schemes cannot achieve uncloneable-indistinguishability in
the plain model.

As noted in [BJL+21], uncloneable encryption can be considered the second
level in the hierarchy of uncloneable objects, since it makes _information_
uncloneable. The first level of the hierarchy only lets us verify the
authenticity of objects: this is where private-key quantum money lies. At the
top level of the hierarchy, _functionalities_ are made uncloneable: this
includes quantum copy protection and secure software leasing. It would be
natural to ask if higher levels of the hierarchy can be used to achieve lower
levels. Indeed, [BL20] showed that uncloneable encryption can be used to
construct private-key quantum money. More surprisingly, it has been shown
[CMP20, AK21] that uncloneable encryption can be used to construct quantum
copy protection of a certain class of functions, although these constructions
require either the QROM [CMP20] or additional computational assumptions
[AK21].

#### Device-independence.

The results in [Got03, BL20] were derived in a _device-dependent_ setting, in
which it is assumed that any honest parties can generate trusted states and/or
perform trusted measurements. However, it was observed in e.g. [BHK05, AGM06,
PAB+09] that in some situations, one can construct protocols that are secure
under much weaker assumptions: no assumptions on the states and measurements
are made except that the measurements of spatially separated parties are in
tensor product (or commute). This strong form of security is referred to as
the _device-independent_ (DI) paradigm, in that security can be achieved
(almost) independently of the underlying operations being performed by the
devices used in the protocol. Device-independent protocols that have
information theoretic security are often based on the property of _self-
testing_ or _rigidity_ displayed by some non-local games. Suppose a non-local
game is played with some unknown state and measurements. If these measurements
and state achieve a winning probability close to the optimal winning
probability of the game, then self-testing tells us the state and measurements
are close to the ideal state and measurements needed to achieve the optimal
winning probability for that game. This means that we can do cryptography with
this state and measurements as though they were the ideal state and
measurements.

We note that in the specific context of uncloneable encryption, the security
proofs in [Got03, BL20] do already have a form of “one-sided device-
independent” property, in the sense that for the uncloneable encryption
scenario the receiver may be dishonest, and hence the security proof must
cover the possibility of the receiver not performing the intended operations.
However, our goal in this work is to extend the device-independence to cover
the client’s devices as well222In order to achieve this, our protocol will
involve some interaction between the client and receiver. Note that while a
dishonest receiver could of course lie about the outputs of their devices,
this poses no problems for a DI security proof, because such behaviour can
always be absorbed into the operations/measurements performed by the dishonest
party — this line of reasoning has been used in many previous works on
cryptographic scenarios with some potentially dishonest receiver (including
uncloneable encryption) such as [FM18, GMP22, KT20]. (See also Remark 1 later
below.) (we briefly elaborate on how the [BL20] scheme is insecure in the
fully DI setting in Section 1.1 below). This is somewhat similar to the
scenario considered by [GMP22] (for which they achieve polynomial rather than
exponential security), except that in their scenario, while the states and
measurements are indeed not trusted, it is still assumed that the devices are
computationally bounded. The security achieved in their scenario is not
information theoretic, but under the assumption that the LWE problem cannot be
solved by polynomial-time quantum computers. Hence thus far, there has not
been an uncloneable encryption scheme in the “standard” fully DI scenario,
without computational assumptions.

###  1.1 Our results

In this work, we prove that uncloneable encryption can be achieved in the
standard DI scenario without computational assumptions (and with exponential
security), for a somewhat modified version of uncloneable encryption. We call
our modification _uncloneable encryption with variable keys_. We note that in
particular, this modified version is sufficient to yield a quantum money
scheme that is secure in the standard fully DI setting.

#### Uncloneable encryption with variable keys.

In our modified version of uncloneable encryption, the idea is that a
particular ciphertext can be decrypted with several possible decryption keys,
and each adversary in a cloning attack gets an independently generated
decryption key. To further illustrate what we mean, we shall discuss this in
the context of the uncloneable encryption scheme based on Wiesner states given
by [BL20]. For $a,x\in\\{0,1\\}$, we shall use $\ket{a^{x}}$ to denote the
state $H^{x}\ket{a}$, where $H$ is the Hadamard matrix that takes the
computational basis to the $\ket{+},\ket{-}$ basis. For $a,x\in\\{0,1\\}^{n}$,
we shall use $\ket{a^{x}}$ to denote
$\bigotimes_{i=1}^{n}\ket{(a^{i})^{x_{i}}}$. These $\ket{a^{x}}$ states are
called Wiesner states. The basic encryption scheme (without using the QROM) in
[BL20] is as follows: the ciphertext corresponding to a message $m$ of $n$
bits is $(m\oplus a,\ket{a^{x}})$, for uniformly random $x$ and $a$, and the
decryption key is $x$. On getting $x$, a single party can measure the quantum
part of the ciphertext in the bases indicated by $x$ to recover $a$, and hence
$m$. However, because the Wiesner states satisfy a monogamy of entanglement
property [TFKW13], two parties cannot simultaneously do this.

Note that in the scheme described above, the string $a$ which is generated
really is a “private key”333To avoid confusion: note that here we do not use
the term “private key” in the same sense as in a public key encryption
procedure. that is required to do the encryption procedure, but which cannot
be revealed to any party if any kind of security is desired. Fortunately,
after the encryption procedure is completed, $a$ does not need to be stored;
only the string $x$, which is completely independent of $a$, needs to be
stored and possibly released later as a decryption key.

Now consider the following modification: we still use Wiesner states
$\ket{a^{x}}$, but we cannot use all the bits of $a$ as a one-time-pad for the
message — in fact we require that each party that wants to decrypt the message
has to learn a different (independently generated) subset of the bits of $a$
in order to do so. The reasons we need to do this are technical and have to do
with the proof style based on parallel repetition we use (we shall expand more
on this in Section 1.2), but it can be achieved by modifying the protocol in
the following way. If the message length is $n$ bits, the Wiesner states will
now be $l$ bits, for $l>n$. The ciphertext will be $(m\oplus r,\ket{a^{x}})$,
where $r$ is a uniformly random string of $n$ bits. $(r,a,x)$ will all need to
be stored as private key now, and there will be a “key release" procedure that
takes the private key and generates a decryption key with a random subset $T$
of $[l]$ of size $n$. An instance of the decryption key is $(r\oplus
a_{T},T,x_{T})$, and each time a decryption key is released from the
decryption procedure, $T$ is generated independently. Obviously this means
there are many possible decryption keys, corresponding to different values of
$T$. A single decryptor given the decryption key and using $\ket{a^{x}}$ can
learn $r$, and thus can learn $m$ using the classical part of the ciphertext.
This also satisfies the property we required, that if two parties both want to
learn the message, they have to learn independent subsets of the bits of $a$.

We provide a formal definition of uncloneable encryption with variable keys
and its related security criteria in Section 3. Our definition has some
similarities with uncloneable decryption or single-decryptor encryption, which
is another task that has been studied since the introduction of uncloneable
encryption [GZ20]. As indicated in the illustrative example, the main
difference between our definition and that introduced by [BL20] is that the
whole private key that was used in the encryption needs to be stored, and
there is a key release procedure that takes the private key as input, uses
additional private randomness, and outputs an independent decryption key each
time one is requested (here by independent we mean the additional private
randomness is independent for each decryption key). Additionally, since we
work in the DI setting, our encryption procedure is interactive (although this
can potentially be removed if the client can impose some constraints on their
devices; we elaborate on this in Remark 3), and there needs to be an option to
abort the procedure. This feature is required in all DI cryptography that
involve only classical communication, and was also present in the scheme given
by [GMP22].

Our actual DI scheme for achieving uncloneable encryption with variable keys
is very similar to the modified version of the scheme of [BL20] we described
above, except with a self-testing step to obtain DI security.444To see that
the [BL20] scheme does not work if the state preparation is untrusted, observe
that if the state prepared is simply a classical record of the values $(a,x)$
rather than the Wiesner states $\ket{a^{x}}$, then it is trivially insecure.
If converted to an entanglement-based protocol in which the client performs
some choice of measurement $x$ and obtains an output $a$, observe that if the
client’s measurements are untrusted, then the devices could just be
implementing a completely classical strategy in which for each round the
output $a$ is perfectly deterministic for each $x$, in which case all
dishonest parties will know the value of $a$ once given $x$. (If desired, this
deterministic behaviour could be made undetectable by any statistical checks
involving only the frequency distribution of $a$ and/or $x$, by instead making
the value of $a$ for each $x$ a function of some classical “hidden variable”
$\Lambda$, a copy of which is held by all dishonest parties.) Our main result
regarding the achievability of DI uncloneable encryption with variable keys is
stated in Theorem 14, and the scheme achieving this is described in Scheme 1.

Some additional notable features of our scheme are as follows:

  * •

The uncloneable encryption scheme of [GMP22], which is device-independent with
computational assumptions, allows for some noise in the devices, but their
approach requires the noise parameter to vanish in the limit of large message
length $n$. In contrast, our protocol tolerates a _constant_ level of noise in
the honest devices. (For the device-dependent uncloneable encryption schemes,
to our knowledge none of them have explicitly analyzed noise in the devices,
though it should be possible to modify some of the schemes to account for
this.)

  * •

Most DI cryptographic protocols that guarantee information theoretic security
require that there is no communication between the devices of different
parties involved in the protocol. Our security proof is based on the parallel
repetition of a form of a non-local game; it was shown in [JK22] that proofs
based on parallel repetition can tolerate a small (but linear in $n$) amount
of communication, or leakage, between the devices of all parties involved. We
give a simpler proof, inspired by the lower bound of quantum communication
complexity in terms of the quantum partition bound in [LLR12], to show that
our scheme tolerates leakage between the client and the receiver during the
encryption procedure, and between two parties who are both trying to decrypt
the message in a cloning attack. This makes our security criterion
qualitatively different from that considered in [BL20] (even after accounting
for the fully DI setting we consider), since the two parties in a cloning
attack no longer have to be non-communicating — any communication between the
parties can obviously also be considered leakage between their devices. We
only require that the total number of bits thus leaked be bounded. Our
argument could also be adapted to obtain device-dependent schemes for
uncloneable encryption that can tolerate some communication between the two
parties in a cloning attack.

#### Uncloneable bits and trits with variable keys.

Although our aim in modifying the definition of uncloneable encryption was to
be able to get a DI scheme, we argue that the modified definition can be
useful. Firstly, the modified definition can be used to get uncloneable bits
without using the QROM. The idea here is as follows: suppose the probability
for two parties to simultaneously guess an $l$-bit string is exponentially
small in $l$, but larger than $2^{-l}$. From this we want to “extract" a
single bit such that the probability of two parties simultaneously guessing it
is $\frac{1}{2}+\mathrm{negl}(l)$.555This part of our analysis does not depend
significantly on the exact scaling of the function $\mathrm{negl}(l)$; when
applying it in our protocol, it will be an exponentially small function (since
we achieve exponential rather than polynomial security), though larger than
$2^{-l}$. If instead of two parties, there was a single party, this can be
achieved by using randomness extractors [TSSR11, DPVR12]. The difficulties
with using extractors against two parties were noted in [AKL+22], although
using randomness extractors was not ruled out by the impossibility results in
the same work.

In the setting of uncloneable encryption with variable keys, we can use
randomness extractors with _different_ random seeds for the two parties.
Specifically, we shall use the inner product function, which is known to be an
extractor. If the two parties cannot guess $x$ with high probability from a
shared state $\ket{\rho}_{x}$, we can say that the probability that one party
guesses $x\cdot v^{1}$ and the other guesses $x\cdot v^{2}$, where $v^{1}$ and
$v^{2}$ are independently generated from the uniform distribution over
$\\{0,1\\}^{l}$, is at most $\frac{1}{2}+\mathrm{negl}(l)$.666The argument
also works if there are two (possibly correlated) strings $x^{1}$ and $x^{2}$,
and we have a bound on one party learning $x^{1}$ and the other party learning
$x^{2}$ from $\ket{\rho}_{x^{1}x^{2}}$, which will be the case in our actual
setting. Here we can upper bound the probability of the parties learning
$x^{1}\cdot v^{1}$ and $x^{2}\cdot v^{2}$ respectively. Instead of going via
the standard arguments for extractors, our argument for this is done similar
to the quantum version of the Goldreich-Levin theorem for hardcore bits
[AC02]. The idea is that if the probability of the parties guessing $x\cdot
v^{1}$ and $x\cdot v^{2}$ averaged over $v^{1},v^{2}$ is more than
$\frac{1}{2}+\mathrm{negl}(l)$, then they can independently run the Bernstein-
Vazirani algorithm on their halves of the shared state, to both guess the
entire string $x$ with too high a probability. Since the two parties need to
run the Bernstein-Vazirani algorithm independently, this argument does not
work if we consider the probability of both parties learning $x\cdot v$ for
the same $v$, which would be required in the setting without variable keys.

This argument generalizes to trits as well, but it does not seem to extend to
bit strings. An implication of this result is that we have uncloneable-
indistinguishability in addition to uncloneability for bit and trit messages.

#### Application to quantum money.

Our second point regarding the usefulness of uncloneable encryption with
variable keys is to argue that it can be used just as well as the original
notion of uncloneable encryption to get private key quantum money. The
approach here is the same as that sketched in [BL20]. Basically, a bank could
produce a banknote by encrypting a random string $M$ using our procedure, then
storing the private key as well as $M$ in its internal records, and placing
the quantum ciphertext in the banknote. To verify a banknote, the bank would
use the private key to run the key release procedure and generate a decryption
key, then use this to decrypt the state in the banknote and check whether the
output matches $M$. Our security definition for uncloneability immediately
implies that if an adversary attempted to clone the banknote and submit it to
two separate bank locations for verification (each of which independently runs
the key release procedure), the probability of both being accepted777More
precisely, the probability of both banknotes being accepted _and_ the original
encryption procedure accepting as well. is exponentially small.

Since our scheme is secure in the DI setting, this means the above approach
yields a method for obtaining DI quantum money.888This approach avoids an
impossibility result for DI quantum money derived in [HS20], because we are
considering a somewhat different setup from that work.  We note that it does
seem possible that another approach for DI quantum money would be to slightly
modify existing protocols for DI quantum key distribution; however, there may
be some benefits to using the approach in this work. In particular, while our
analysis above does not say anything about what happens if the bank returns
successfully verified banknotes (rather than destroying them and generating
fresh ones), the proof techniques we use here should be modifiable to allow a
security proof for a scheme that returns successfully verified banknotes a
fixed number of times, chosen at the point of generation of the banknote.

###  1.2 Technical overview

In this section, we give an overview of how we construct our DI uncloneable
encryption with variable keys (DI-VKECM) scheme, and how we prove its
security. All the arguments in this section are for proving uncloneability. In
the context of VKECM, uncloneability is the requirement that if the encryption
of a uniformly random message gets distributed between two parties, say Bob
and Charlie, then the average probability that both of them guess the message
given access to independently generated decryption keys, is exponentially
small in the number of bits in the message.

#### Formulating security in terms of a non-local game.

The first thing to notice is that the Wiesner states correspond to the states
after the measurement of one of the parties (let’s say Alice) in the CHSH non-
local game. Therefore, we can consider doing something very similar to many
protocols for DI quantum key distribution (QKD) [PAB+09]. During the
encryption process, the client (who is honest) and the receiver (who may be
dishonest) will share states compatible with some $l$ copies of the CHSH game.
On some of these copies, the CHSH game will be self-tested, and the rest will
be used for encryption. The idea is that, if a random subset is used for self-
testing, the dishonest receiver, who had to have prepared the devices
beforehand, would have had to actually prepare i.i.d. copies of the ideal CHSH
state and measurements in order to pass the self-testing check.999In
principle, one might be able to use some other non-local game with self-
testing properties; however, the CHSH game is particularly convenient since
(after Alice’s measurement) the ideal strategy produces exactly the Wiesner
states. We also note that the monogamy of entanglement game from [TFKW13]
(which was used in the [BL20] security proof) was shown to have some self-
testing properties as well [BC21]. However, to our knowledge all self-testing
properties of that game are derived for the “one-sided DI” scenario where
Alice’s operations are trusted, and hence it is unclear whether they could be
applied to obtain a fully DI protocol.

However, there is one key aspect in which the situation here differs from that
in QKD. In a DIQKD protocol, measurements corresponding to all copies of the
game in question can be done at once, and then the Serfling bound can be
applied to the resulting input-output distribution, in order to say something
about the entire distribution from what is observed in the self-testing subset
of inputs and outputs. However, for uncloneable encryption, measurements
corresponding to the copies of the game which will be used for encryption
cannot be done at the same time as the testing subset; in an honest
implementation, these states need to remain unmeasured because the ciphertext
needs to be quantum. Thus there is no fixed distribution on which the Serfling
bound can be applied.

Because of the above problem, we shall instead use a two-round non-local
game101010While we refer to this as a non-local game for brevity, we note that
strictly speaking it does not fall within the “standard” framework of non-
local games (in which there is no communication between the parties), because
in our scenario the player Barlie sends or distributes states to the players
Bob and Charlie _after_ receiving some inputs. It would be convenient if we
could have analyzed some three- or four-player non-local game in the
“standard” sense; however, some sort of communication between parties seems
unavoidable in order for us to be able to relate this game to the task of
uncloneable encryption (similar to the situation for monogamy of entanglement
games in [TFKW13, BL20]). We specify the exact order in which the players can
share or distribute states in our full game description in Section 4. whose
first round is played between two players Alice and Barlie, and the second
round is played between two players Bob and Charlie, between whom Barlie’s
portion of the state at the end of the first round gets distributed (Alice’s
portion of the state at the end of the first round remains untouched). We call
this game the cloning game $\mathrm{CLONE}_{\gamma}$. We describe a single
instance of the game first; we shall actually need parallel-repeated version
of the game for the security proof. In the first round of a single instance of
the game, Alice will receive a uniformly random single-bit input, and Barlie
will receive a trit in $\\{0,1,\text{keep}\\}$, with “keep" occuring with
probability $(1-\gamma)$. The input “keep" to Barlie indicates that the CHSH
game will not be tested, and in this case the first round is automatically
won; otherwise, Alice and Barlie’s inputs are the same as the inputs of the
CHSH game, and they need to produce outputs that satisfy the CHSH winning
condition. If Barlie did not get “keep" in the first round, the second round
is automatically won; otherwise Bob and Charlie get the same input as Alice
did in the first round of the game, and they both have to guess Alice’s output
bit from the first round. Note that Alice gets the same input regardless of
Bob’s input, and in the honest case, if she gets input $x$ and produces output
$a$ in the first round, the state on Barlie’s side is $\ket{a^{x}}$. If the
first round is won with high enough probability, then the state after the
first round on Barlie’s side is close to $\ket{a^{x}}$, which means by the
monogamy of entanglement property of Wiesner states, we can upper bound the
probability that Bob and Charlie can guess $a$ given $x$. This means that the
overall winning probability of $\mathrm{CLONE}_{\gamma}$ is bounded away from
1. The style of argument we employ here is similar to what was considered in
[ACK+14, KST22] for two-party cryptography, although parallel repetition was
not considered in those works.

When we consider the parallel-repeated $\mathrm{CLONE}_{\gamma}$, i.e., $l$
i.i.d. copies of $\mathrm{CLONE}_{\gamma}$, a constant fraction of the
instances will be tested in the first round, and the rest can be used for
encryption. The ciphertext in this case will be the state after the first
round on Barlie’s side (which in the honest case is a Wiesner state of the
form $\ket{a_{S}^{x_{S}}}$, where $x$ and $a$ and Alice’s first round inputs
and outputs, and $S$ is the subset on which Barlie’s first round input was
“keep"), along with the classical string $m\oplus a_{S}$. If we can prove that
the winning probability of the parallel-repeated $\mathrm{CLONE}_{\gamma}$
decreases exponentially in $n$, then we could prove the uncloneability of this
scheme. Note that the scheme as described here is actually an uncloneable
encryption scheme in the original sense of [BL20], since $x_{S}$ is the only
decryption key.

#### Parallel repetition of the cloning game.

Unfortunately, we cannot prove a parallel repetition of the game
$\mathrm{CLONE}_{\gamma}$ as described. What we can prove a parallel
repetition theorem for is a modified version of $\mathrm{CLONE}_{\gamma}$
which is “anchored". The anchoring transformation we use is similar to those
used in [Vid17, KT20]. Essentially, the anchoring property requires that Bob
and Charlie’s second round inputs cannot be perfectly correlated with Alice’s
first round input, or each other — with some small probability, these
distributions need to be product instead. We do this by giving Bob and Charlie
independently “blank" inputs rather than $x_{i}$ on some instances, and then
not using those instances for encryption for them (this corresponds to the
second round being won for free on these instances of the game) — this forces
us to use the additional random string $r$ in the ciphertext as described
earlier, with $(r\oplus a_{T\cap S},x_{T\cap S},T)$ being a decryption key for
random $T$. This now places us in the setting of VKECM.

We can prove a parallel repetition theorem for the anchored version of
$\mathrm{CLONE}_{\gamma}$, which we denote by $\mathrm{CLONE}_{\gamma,\alpha}$
for anchoring parameter $\alpha$, similar to how a parallel repetition theorem
for a different two-round game was proved in [KT20]. The game considered in
[KT20] had only two players in both rounds, so in our proof we require some
additional steps to take care of the two players Bob and Charlie, between whom
Barlie’s state is divided after the first round. We use the information
theoretic framework for parallel repetition that was introduced by [Raz95,
Hol07]. In this framework, we consider a strategy for $l$ copies
$\mathrm{CLONE}_{\gamma,\alpha}$ and condition on the event $\mathcal{E}$ of
the winning condition being satisfied on some $C\subseteq[l]$ instances. We
show that if $\Pr[\mathcal{E}]$ is not already small, then we can find another
coordinate in $i\in\overline{C}=[l]\setminus C$ where the winning probability
conditioned on $\mathcal{E}$ is bounded away from 1. The proof is by
contradiction: we show that if the probability of $\mathcal{E}$ is large and
the probability of winning in $i$ conditioned on $\mathcal{E}$ is not bounded
away from 1, then there is a stategy for a single copy of
$\mathrm{CLONE}_{\gamma,\alpha}$, whose winning probability is higher than the
maximum winning probability of $\mathrm{CLONE}_{\gamma,\alpha}$. This is done
by defining a state representing the inputs, outputs and shared entanglement
in the strategy for $\mathrm{CLONE}_{\gamma,\alpha}^{l}$, conditioned on
$\mathcal{E}$. When Alice, Barlie, Bob and Charlie’s inputs for the $i$-th
instance of $\mathrm{CLONE}_{\gamma,\alpha}$ are $x_{i},u_{i},y_{i},z_{i}$
respectively, we denote this state by $\ket{\varphi}_{x_{i}u_{i}y_{i}z_{i}}$.
The state $\ket{\varphi}_{x_{i}u_{i}y_{i}z_{i}}$ is such that the distribution
obtained by measuring the corresponding $i$-th output registers on it is the
distribution of outputs in the original strategy for the inputs
$x_{i}u_{i}y_{i}z_{i}$, conditioned on the event $\mathcal{E}$. Therefore, if
the probability of winning in the original strategy conditioned on
$\mathcal{E}$ is too high, and the players are able to output from the state
$\ket{\varphi}_{x_{i}u_{i}y_{i}z_{i}}$ (or close to this distribution) in a
single instance of $\mathrm{CLONE}_{\gamma,\alpha}$, they can win the single
instance with too high probability.

The rest of the proof will thus involve showing how the players can provide
outputs that are close to the output distribution in
$\ket{\varphi}_{x_{i}u_{i}y_{i}z_{i}}$ when playing a single instance of
$\mathrm{CLONE}_{\gamma,\alpha}$. Let us denote the blank inputs to Bob and
Charlie in the second round by $\bot$, so that
$\ket{\varphi}_{x_{i}u_{i}\bot\bot}$ is $\ket{\varphi}_{x_{i}u_{i}y_{i}z_{i}}$
when they both get this blank input. The first thing to note is that there
exists some $i$ such that the distribution of Alice and Barlie’s first round
outputs is almost the same in $\ket{\varphi}_{x_{i}u_{i}\bot\bot}$ and
$\ket{\varphi}_{x_{i}u_{i}y_{i}z_{i}}$ for any $y_{i}z_{i}$. This is because
the distributions were exactly the same originally (because the first round
outputs being produced without access to $y_{i}z_{i}$), and conditioning on
$\mathcal{E}$ does not change the distribution too much (because we have
assumed the probability of $\mathcal{E}$ happening is not too small). So in
the first round, Alice and Barlie could jointly produce the state
$\ket{\varphi}_{x_{i}u_{i}\bot\bot}$ on getting inputs $x_{i},u_{i}$, and
measure its output registers to give their first round outputs. The
distribution of $X_{i}U_{i}$ conditioned on $Y_{i}=\bot,Z_{i}=\bot$ is
product, so we can use an argument very similar to that of [JPY14] to prove a
parallel repetition theorem for one-round games with product distributions, to
argue that there exist unitaries $V^{\mathrm{A}}_{x_{i}}$ and
$V^{\mathrm{B}\mathrm{C}}_{u_{i}}$ that Alice and Barlie can appear on their
registers of a shared state $\ket{\varphi}_{\bot\bot}$ (which is the
superposition of $\ket{\varphi}_{x_{i}u_{i}\bot\bot}$ over all $x_{i}u_{i}$)
to get close to $\ket{\varphi}_{x_{i}u_{i}\bot\bot}$.

In the second round, Barlie then distributes his registers of the shared state
(which is close to $\ket{\varphi}_{x_{i}u_{i}\bot\bot}$, except with the
$i$-th first-round output registers being measured) between Bob and Charlie,
and also gives them $u_{i}$. Because Bob and Charlie’s inputs are anchored
w.r.t. each other, which means that they are product (with each other and with
Alice) with some constant probability, we can show by a similar argument that
there exist unitaries $V^{\mathrm{B}}_{u_{i}y_{i}}$ and
$V^{\mathrm{C}}_{u_{i}z_{i}}$ that Bob and Charlie can apply on their
registers of $\ket{\varphi}_{x_{i}u_{i}\bot\bot}$ to get it close to
$\ket{\varphi}_{x_{i}u_{i}y_{i}z_{i}}$. These unitaries do not act on the
output registers from the first round, so we can argue that on average,
$V^{\mathrm{B}}_{u_{i}y_{i}}\otimes V^{\mathrm{C}}_{u_{i}z_{i}}$ also takes
$\ket{\varphi}_{x_{i}u_{i}\bot\bot}$ conditioned on particular first round
output values to $\ket{\varphi}_{x_{i}u_{i}y_{i}z_{i}}$ conditioned on the
same values. Therefore, Bob and Charlie can apply these unitaries on the state
they get from Barlie, and provide second round outputs by measuring the $i$-th
second round output registers of the resulting state. This completes the
stategy for Alice, Barlie, Bob and Charlie for the single instance of
$\mathrm{CLONE}_{\gamma,\alpha}$.

###  1.3 Discussion and future work

The first question left open by our work is whether it is possible to do the
original ECM rather than VKECM device-independently. It seems necessary to do
a parallel rather than sequential (which is the setting where parties enter
their inputs and get outputs from their devices one by one, instead of all at
once) style of proof here. This is because, while we could ensure that the
receiver during the encryption procedure enters the inputs for self-testing
into their device one by one, simply by sending the inputs one by one and
requiring a reply before supplying the next input (thereby giving the protocol
many rounds of interaction), it seems fairly unnatural to enforce this
constraint on Bob and Charlie. The only proof technique we have for parallel
device-independent settings is parallel repetition, so proving a parallel
repetition theorem for a game like the $\mathrm{CLONE}_{\gamma}$ game we
described (the version without anchoring) seems necessary. However, it is not
known how to prove an exponential parallel repetition theorem for even one-
round two-player non-local games where the inputs of the two players are
arbitrarily correlated. The most general exponential parallel repetition
theorem known here is also for anchored games [BVY17]. Of course, we do not
need to prove a parallel repetition theorem for all possible games, only the
specific game $\mathrm{CLONE}_{\gamma}$. In our parallel repetition theorem
$\mathrm{CLONE}_{\gamma,\alpha}$, we did not make use for any structure in the
game except for the input distribution. So it may be possible to prove
parallel repetition for $\mathrm{CLONE}_{\gamma}$ by making use of its
specific structure.

The second question we leave open is finding more applications for VKECM. Is
it possible to extend the “randomness extraction" result we have for VKECM to
more than one bit or trit? As we noted before, our style of proof does not
work for bit strings, but could some sort of parallel repetition or
composability result be used to prove security for a case where instead one
inner product we have several inner products?

Moreover, although we showed that VKECM can be used just as well as ECM for
private key quantum money, we have not studied whether the application to
quantum copy protection also works with VKECM. Both constructions of copy
protection from uncloneable encryption [CMP20, AK21] are schemes for copy-
protecting a class of functions known as _multi-bit point functions_. A point
function $f_{a,b}$ evaluates to $0$ on all inputs except a special input $a$,
on which it evaluates to a string $b$. When constructing copy protection from
uncloneable encryption, the string $a$ is taken as the decryption key of the
uncloneable encryption procedure, and $b$ is the encrypted message. The idea
is that two parties among whom the copy-protected program has been
distributed, should not both be able to evaluate $b$ when they have $a$ as
their input — this is guaranteed by the security of the uncloneable encryption
scheme. The question then is: what happens if we try to do these constructions
with VKECM instead of ECM? Because there are many possible valid decryption
keys in VKECM, does this mean we could copy protect a class of functions
different from point functions? We leave all of these interesting questions
for future work.

###  1.4 Organization of the paper

In Section 2, we introduce some notation we shall be using throughout the
paper, and describe some preliminaries on probability theory and quantum
information. In Section 3, we formally define DI-VKECM and related security
criteria; we also describe the device-independent setting and assumptions
therein in this section. In Section 4, we formally define the two-round
cloning games $\mathrm{CLONE}_{\gamma}$ and $\mathrm{CLONE}_{\gamma,\alpha}$
and prove that the probability of winning a single instance of it is bounded
away from 1. In Section 5, we describe our DI-VKECM scheme and prove its
security using the parallel repetition theorem for
$\mathrm{CLONE}_{\gamma,\alpha}$. In Section 6, we describe how to get
uncloneable bits and trits by modifying the scheme in Section 5. Finally, in
Section 7, we prove the parallel repetition theorem for
$\mathrm{CLONE}_{\gamma,\alpha}$.

##  2 Preliminaries

###  2.1 Probability theory

We shall denote the probability distribution of a random variable $X$ on some
set $\mathcal{X}$ by $\mathsf{P}_{X}$. For any event $\mathcal{E}$ on
$\mathcal{X}$, the distribution of $X$ conditioned on $\mathcal{E}$ will be
denoted by $\mathsf{P}_{X|\mathcal{E}}$. For joint random variables $XY$ with
distribution $\mathsf{P}_{XY}$, $\mathsf{P}_{X}$ is the marginal distribution
of $X$ and $\mathsf{P}_{X|Y=y}$ is the conditional distribution of $X$ given
$Y=y$; when it is clear from context which variable’s value is being
conditioned on, we shall often shorten the latter to $\mathsf{P}_{X|y}$. We
shall use $\mathsf{P}_{XY}\mathsf{P}_{Z|X}$ to refer to the distribution

$(\mathsf{P}_{XY}\mathsf{P}_{Z|X})(x,y,z)=\mathsf{P}_{XY}(x,y)\cdot\mathsf{P}_{Z|X=x}(z).$

Occasionally we shall use notation of the form
$\mathsf{P}_{XY}\mathsf{P}_{Z|x^{*}}$. This denotes the distribution

$(\mathsf{P}_{XY}\mathsf{P}_{Z|x^{*}})(x,y,z)=\mathsf{P}_{XY}(x,y)\cdot\mathsf{P}_{Z|X=x^{*}}(z),$

which potentially takes non-zero value when $x\neq x^{*}$. For two
distributions $\mathsf{P}_{X}$ and $\mathsf{P}_{X^{\prime}}$ on the same set
$\mathcal{X}$, the $\ell_{1}$ distance between them is defined as

$\|\mathsf{P}_{X}-\mathsf{P}_{X^{\prime}}\|_{1}=\sum_{x\in\mathcal{X}}|\mathsf{P}_{X}(x)-\mathsf{P}_{X^{\prime}}(x)|.$

######  Fact 1.

For joint distributions $\mathsf{P}_{XY}$ and
$\mathsf{P}_{X^{\prime}Y^{\prime}}$ on the same sets,

$\|\mathsf{P}_{X}-\mathsf{P}_{X^{\prime}}\|_{1}\leq\|\mathsf{P}_{XY}-\mathsf{P}_{X^{\prime}Y^{\prime}}\|_{1}.$

######  Fact 2.

For two distributions $\mathsf{P}_{X}$ and $\mathsf{P}_{X^{\prime}}$ on the
same set and an event $\mathcal{E}$ on the set,

$|\mathsf{P}_{X}(\mathcal{E})-\mathsf{P}_{X^{\prime}}(\mathcal{E})|\leq\frac{1}{2}\|\mathsf{P}_{X}-\mathsf{P}_{X^{\prime}}\|_{1}.$

######  Fact 3.

Suppose probability distributions $\mathsf{P}_{X},\mathsf{P}_{X^{\prime}}$
satisfy $\|\mathsf{P}_{X}-\mathsf{P}_{X^{\prime}}\|_{1}\leq\varepsilon$, and
an event $\mathcal{E}$ satisfies $\mathsf{P}_{X}(\mathcal{E})\geq\alpha$,
where $\alpha>\varepsilon$. Then,

$\|\mathsf{P}_{X|\mathcal{E}}-\mathsf{P}_{X^{\prime}|\mathcal{E}}\|_{1}\leq\frac{2\varepsilon}{\alpha}.$

###  2.2 Quantum information

The $\ell_{1}$ distance between two quantum states $\rho$ and $\sigma$ is
given by

$\|\rho-\sigma\|_{1}=\operatorname{Tr}\sqrt{(\rho-\sigma)^{\dagger}(\rho-\sigma)}=\operatorname{Tr}|\rho-\sigma|.$

The fidelity between two quantum states is given by

$\mathsf{F}(\rho,\sigma)=\|\sqrt{\rho}\sqrt{\sigma}\|_{1}.$

The Bures distance based on fidelity is given by

$\mathsf{B}(\rho,\sigma)=\sqrt{1-\mathsf{F}(\rho,\sigma)}.$

$\ell_{1}$ distance, fidelity and Bures distance are related in the following
way.

######  Fact 4 (Fuchs-van de Graaf inequality).

For any pair of quantum states $\rho$ and $\sigma$,

$2(1-\mathsf{F}(\rho,\sigma))\leq\|\rho-\sigma\|_{1}\leq
2\sqrt{1-\mathsf{F}(\rho,\sigma)^{2}}.$

Consequently,

$2\mathsf{B}(\rho,\sigma)^{2}\leq\left\lVert\rho-\sigma\right\rVert_{1}\leq
2\sqrt{2}\cdot\mathsf{B}(\rho,\sigma).$

For two pure states $\ket{\psi}$ and $\ket{\phi}$, we have

$\left\lVert\,\ket{\psi}\\!\\!\bra{\psi}-\ket{\phi}\\!\\!\bra{\phi}\,\right\rVert_{1}=\sqrt{1-\mathsf{F}\left(\ket{\psi}\\!\\!\bra{\psi},\ket{\phi}\\!\\!\bra{\phi}\right)^{2}}=\sqrt{1-|\langle\psi,\phi\rangle|^{2}}.$

######  Fact 5 (Uhlmann’s theorem).

Suppose $\rho$ and $\sigma$ are mixed states on register $X$ which are
purified to $\ket{\rho}$ and $\ket{\sigma}$ on registers $XY$, then it holds
that

$\mathsf{F}(\rho,\sigma)=\max_{U}|\langle\rho|\mathbbm{1}_{X}\otimes
U|\sigma\rangle|$

where the maximization is over unitaries acting only on register $Y$. Due to
the Fuchs-van de Graaf inequality, this implies that there exists a unitary
$U$ such that

$\left\lVert(\mathbbm{1}_{X}\otimes
U)\ket{\rho}\\!\\!\bra{\rho}(\mathbbm{1}_{X}\otimes
U^{\dagger})-\ket{\sigma}\\!\\!\bra{\sigma}\right\rVert_{1}\leq
2\sqrt{\left\lVert\rho-\sigma\right\rVert_{1}}.$

######  Fact 6.

For a quantum channel $\mathcal{E}$ and states $\rho$ and $\sigma$,

$\|\mathcal{E}(\rho)-\mathcal{E}(\sigma)\|_{1}\leq\|\rho-\sigma\|_{1}\quad\quad\mathsf{F}(\mathcal{E}(\rho),\mathcal{E}(\sigma))\geq\mathsf{F}(\rho,\sigma).$

The entropy of a quantum state $\rho$ on a register $Z$ is given by

$\mathsf{H}(\rho)=-\operatorname{Tr}(\rho\log\rho).$

We shall also denote this by $\mathsf{H}(Z)_{\rho}$. For a state $\rho_{YZ}$
on registers $YZ$, the entropy of $Y$ conditioned on $Z$ is given by

$\mathsf{H}(Y|Z)_{\rho}=\mathsf{H}(YZ)_{\rho}-\mathsf{H}(Z)_{\rho}$

where $\mathsf{H}(Z)_{\rho}$ is calculated w.r.t. the reduced state
$\rho_{Z}$.

The relative entropy between two states $\rho$ and $\sigma$ of the same
dimensions is given by

$\mathsf{D}(\rho\|\sigma)=\operatorname{Tr}(\rho\log\rho)-\operatorname{Tr}(\rho\log\sigma).$

######  Fact 7 (Pinsker’s Inequality).

For any two states $\rho$ and $\sigma$,

$\|\rho-\sigma\|_{1}^{2}\leq 2\ln 2\cdot\mathsf{D}(\rho\|\sigma)\quad\text{
and }\quad\mathsf{B}(\rho,\sigma)^{2}\leq\ln 2\cdot\mathsf{D}(\rho\|\sigma).$

The mutual information between $Y$ and $Z$ with respect to a state $\rho$ on
$YZ$ can be defined in the following equivalent ways:

$\mathsf{I}(Y:Z)_{\rho}=\mathsf{D}(\rho_{YZ}\|\rho_{Y}\otimes\rho_{Z})=\mathsf{H}(Y)_{\rho}-\mathsf{H}(Y|Z)_{\rho}=\mathsf{H}(Z)_{\rho}-\mathsf{H}(Z|Y)_{\rho}.$

The conditional mutual information between $Y$ and $Z$ conditioned on $X$ is
defined as

$\mathsf{I}(Y:Z|X)_{\rho}=\mathsf{H}(Y|X)_{\rho}-\mathsf{H}(Y|XZ)_{\rho}=\mathsf{H}(Z|X)_{\rho}-\mathsf{H}(Z|XY)_{\rho}.$

Mutual information can be seen to satisfy the chain rule

$\mathsf{I}(XY:Z)_{\rho}=\mathsf{I}(X:Z)_{\rho}+\mathsf{I}(Y:Z|X)_{\rho}.$

A state of the form

$\rho_{XY}=\sum_{x}\mathsf{P}_{X}(x)\ket{x}\\!\\!\bra{x}_{X}\otimes\rho_{Y|x}$

is called a CQ (classical-quantum) state, with $X$ being the classical
register and $Y$ being quantum. We shall use $X$ to refer to both the
classical register and the classical random variable with the associated
distribution. As in the classical case, here we are using $\rho_{Y|x}$ to
denote the state of the register $Y$ conditioned on $X=x$, or in other words
the state of the register $Y$ when a measurement is done on the $X$ register
and the outcome is $x$. Hence
$\rho_{XY|x}=\ket{x}\\!\\!\bra{x}_{X}\otimes\rho_{Y|x}$. When the registers
are clear from context we shall often write simply $\rho_{x}$. For CQ states,
the expressions for conditional entropy, relative entropy and mutual
information for $\rho_{XY}$ and $\sigma_{XY}$ given by

$\rho_{XY}=\sum_{x}\mathsf{P}_{X}(x)\ket{x}\\!\\!\bra{x}_{X}\otimes\rho_{Y|x}\quad\quad\sigma_{XY}=\sum_{x}\mathsf{P}_{X^{\prime}}(x)\ket{x}\\!\\!\bra{x}_{X}\otimes\sigma_{Y|x},$

reduce to

$\displaystyle\mathsf{H}(Y|X)_{\rho}=\mathop{\mathbb{E}}_{\mathsf{P}_{X}}\mathsf{H}(Y)_{\rho_{x}},$
$\displaystyle\mathsf{D}(\rho_{XY}\|\sigma_{XY})=\mathsf{D}(\mathsf{P}_{X}\|\mathsf{P}_{X^{\prime}})+\mathop{\mathbb{E}}_{\mathsf{P}_{X}}\mathsf{D}(\rho_{Y|x}\|\sigma_{Y|x})$
$\displaystyle\mathsf{I}(Y:Z|X)=\mathop{\mathbb{E}}_{\mathsf{P}_{X}}\mathsf{I}(Y:Z)_{\rho_{x}}.$

When talking about entropies of only the classical variables of a CQ state, we
shall sometimes omit the state in the subscript. Additionally, for an event
$\mathcal{E}$ defined on the classical variable $X$ of a CQ state, we shall
use notation like use $\mathsf{H}(X|\mathcal{E})$ and
$\mathsf{H}(X_{1}|X_{2};\mathcal{E})$ to talk about entropies of the event
when the classical distribution is conditioned on $\mathcal{E}$.

##  3 Security definitions

In this section, we formally define a DI-VKECM scheme. We begin by laying out
the form of the devices we consider:

#### The device-independent setting with leakage.

The model that is typically used for device-independent security in the
parallel-input setting is as follows: the parties in the protocol (in our
case, the client and receiver) are provided with devices that each hold some
share of a quantum state. Each party’s device can (possibly more than once)
accept a classical input string, which it uses to perform some measurement on
its share of the state and produce a classical output string. In the context
of our uncloneable encryption scheme, for the case of dishonest behaviour, the
receiver’s device also has the ability to distribute the state it contains
across two devices (that also have the ability to accept classical input
strings and produce classical output strings), which will be sent to dishonest
parties Bob and Charlie. The measurements performed by the devices do not have
to be trusted — we require only that each party’s device is performing its
measurement on a separate Hilbert-space tensor factor. In the standard device-
independent scenario, one typically also imposes a “no-leakage” condition in
the sense that while the initial state shared between the devices can be
arbitrarily entangled, the devices do not communicate with each other and/or
any dishonest parties once the inputs have been supplied. Here however, we
shall use a somewhat weakened version of this condition: we allow the devices
to communicate to each other in arbitrary fashion before supplying their
outputs, subject only to the constraint that there is an upper bound on the
total number of bits thus communicated.

More precisely, the devices we consider in our scheme will take strings of
length $l$ as input. Our security proofs hold for devices that are allowed to
leak $\nu l$ bits of communication111111We can restrict to classical
communication without loss of generality, because if quantum communication is
desired, the devices can pre-share entanglement and use it for quantum
teleportation with only classical communication, though this does require $2$
classical bits to send $1$ qubit of information. between each other for some
$\nu>0$. The leakage can be arbitrarily interactive121212There is a subtlety
here in that the _timing_ (or presence/absence) of the leakage should not
itself be allowed to encode information. Hence to put it more precisely, we
should say that there are $\nu l$ times at which a bit is communicated between
the devices. and allows for communication between the client and receiver
before the receiver’s device distributes the state, as well as between Bob and
Charlie’s device after the state is distributed. We shall assume that all
leakage happens after the devices receive their inputs; this is without loss
of generality because any leakage that happens before the devices get their
inputs could have been pre-programmed into the devices. We shall also assume
that the leakage happens before the devices produce their outputs; this is
also without loss of generality because for any model in which leakage happens
after the outputs are produced, we can construct an equivalent model in which
the devices first measure their states but do not announce their outputs yet,
then send out the leakage registers (which could depend on the measurement
outcomes), and finally actually produce their outputs.

######  Remark 1.

From the perspective of modelling dishonest behaviour, it would be reasonable
to allow a dishonest receiver to “open” the device on their side and directly
perform operations on the quantum state within it, rather than being strictly
constrained to supplying inputs to the device in the prescribed fashion.
However, we highlight that since we have not placed any constraints on the
device behaviour in the dishonest case (other than the bounded-leakage
constraint), any operations that a dishonest party could perform after
“opening” the device can equivalently be carried out by the device itself.
Hence for the purposes of our analysis, it does not matter which of these
models we use.

We now describe the security definitions we use. These definitions are
essentially similar to those used in [GMP22], apart from the distinction
between the private key and decryption key in our scheme. The definitions in
[GMP22] specify a classical client (the honest party). For us the honest party
will not be classical, but they can receive their quantum devices from the
dishonest party131313As long as the honest party can still impose the bounded-
leakage constraint on them., and only need to interact with these devices by
providing them with classical inputs and recording their classical outputs. On
the other hand, we shall not be assuming that the dishonest parties are
computationally bounded.

We remark that while the definitions in [GMP22] differ slightly from those in
[BL20], the only differences are basically that the encryption procedure for a
message is allowed to be interactive, and are allowed to output an abort
symbol, with the protocol not continuing if there is an abort (the probability
of not aborting also appears in the security condition).

######  Definition 1 (Device-independent encryption of classical messages with
variable keys).

Let $\lambda$ be a security parameter. A device-independent encryption of
classical messages with variable keys (DI-VKECM) scheme consists of a tuple
$(\mathsf{Enc},\mathsf{KeyRel},\mathsf{Dec})$ such that

  * •

$\mathsf{Enc}(1^{\lambda},m)$ is an interactive protocol between an honest
client, who takes as input the security parameter $\lambda$ and a message $m$
in some message space $\mathcal{M}$, and a potentially dishonest receiver, who
takes as input the security parameter $\lambda$. The output of the protocol is
$(F,K_{\mathrm{priv}},\rho)$, where $F$ is a flag held by the client which
takes values ✓ (accept) or ✗ (reject), $K_{\mathrm{priv}}$ is a private key
held by the client, and $\rho$ is a quantum ciphertext state held by the
receiver on a register we denote as $Q$.

  * •

$\mathsf{KeyRel}(k_{\mathrm{priv}})$ takes as input a private key
$k_{\mathrm{priv}}$, and uses some internal randomness to generate and output
a decryption key $K_{\mathrm{dec}}$.

  * •

$\mathsf{Dec}(k_{\mathrm{dec}},\rho)$ takes as input a decryption key
$k_{\mathrm{dec}}$ and a ciphertext state $\rho$ on register $Q$, and outputs
a message value $\widetilde{M}\in\mathcal{M}$.

We say that a DI-VKECM scheme is efficient if the computations that the client
and an honest receiver perform in $\mathsf{Enc},\mathsf{KeyRel},\mathsf{Dec}$
are polynomial time in $\lambda$ and the length (in bits) of $m$.

We require that the DI-VKECM scheme satisfies _completeness_ : if all steps
are carried out honestly, then for any $m\in\mathcal{M}$, we have (in the
following statements, terms such as
$\mathsf{Dec}\circ\mathsf{KeyRel}\circ\mathsf{Enc}$ should be understood as
having each procedure acting only on the relevant registers, e.g.
$\mathsf{KeyRel}$ only acts on the private-key output of $\mathsf{Enc}$):

$\Pr\left[\left(F=\text{\char
51\,}\right)\land\left(\mathsf{Dec}\circ\mathsf{KeyRel}\circ\mathsf{Enc}(1^{\lambda},m)=m\right)\right]\geq
1-\mathrm{negl}(\lambda),$ (1)

i.e. the probability of accepting and correctly decrypting the message is
high.

Additionally, we impose the condition that for any distribution of a message
$M$, if we let $\sigma_{MQ|F=\text{\char 55\,}}$ be the state produced by
$\mathsf{Enc}(1^{\lambda},M)$ on registers $MQ$ conditioned on $F=\text{\char
55\,}$, then we have141414Here we have differed very slightly from [GMP22], in
that for their protocol, when $F=\text{\char 55\,}$ the protocol basically
stops and no state is produced with the receiver (although in their actual
protocol the receiver of course ends up with some quantum state in either case
— the state just does not depend on $m$ when $F=\text{\char 55\,}$, though it
does depend on the key value). The definition we have used is essentially
saying the same thing, i.e. $\rho$ does not depend on $m$ if $F=\text{\char
55\,}$. In the protocol we design below, when $F=\text{\char 55\,}$ the
receiver gets the state $\rho$ they would have gotten if $F=\text{\char 51\,}$
and the message were some uniformly random “dummy value” $m^{\prime}$ which is
independent of $m$. We do this instead of aborting the protocol to simplify
the security proof, because this way we do not have to analyze the receiver
behaving differently conditioned on the value of $F$.

$\sigma_{MQ|F=\text{\char 55\,}}=\sigma_{M|F=\text{\char
55\,}}\otimes\sigma_{Q|F=\text{\char 55\,}},$ (2)

i.e. when $\mathsf{Enc}(1^{\lambda},M)$ aborts, the receiver’s state is
independent of $M$.

######  Remark 2.

In various somewhat similar tasks such as QKD [PR14] or certified deletion
with a third-party eavesdropper [KT20], when considering dishonest behaviour
we typically also require a _correctness_ condition along the following lines:
even when the devices are dishonest, the probability that the message is
incorrectly decrypted and the protocol accepts is low. In our context however,
the only potentially dishonest party is the recipient, and hence it does not
make sense to bound this probability for dishonest behaviour: the set of
dishonest-receiver behaviours always includes trivial processes where they
simply set some random value as their “decrypted message”, in which case it is
clearly impossible to give any nontrivial bounds on the probability of
incorrectly decrypting. (On the other hand, when focusing on the case of
honest behaviour, note that the completeness condition (1) indeed incorporates
the requirement that the probability of incorrectly decrypting the message is
low.)

We now state the security definitions we use, which are the same as in [GMP22]
except with minor modifications to account for the difference in our
decryption procedures.

######  Definition 2 (Distinguishing attack and indistinguishable security).

A _distinguishing attack_ on a DI-VKECM scheme is a process of the following
form (here for ease of explanation we take the message space $\mathcal{M}$ to
contain a particular value labelled as $\mathbf{0}$ without loss of
generality):

  1. 1.

An adversary generates a state on registers $ME$, where $M$ is a classical
register on the message space and $E$ is some (possibly quantum) side-
information.

  2. 2.

A uniformly random bit $B$ is independently generated, and used as follows: if
$B=0$ then $\mathsf{Enc}(1^{\lambda},\mathbf{0})$ is performed; if $B=1$ then
$\mathsf{Enc}(1^{\lambda},M)$ is performed on the $M$ register produced by the
adversary in the previous step. In either case, a flag $F$, a private key
$K_{\mathrm{priv}}$, and a ciphertext state $\rho$ (on a register $Q$) are
produced.

  3. 3.

A measurement is performed on the state on $QE$ to produce a single bit
$\hat{B}$.

A protocol is said to be _indistinguishable-secure_ if for all distinguishing
attacks, we have

$\displaystyle\Pr[(F=\text{\char
51\,})\land(B=\hat{B})]\leq\frac{1}{2}+\mathrm{negl}(\lambda),$

where the probability is taken over all randomness in the described
procedures.

Technically, our DI-VKECM protocol in fact satisfies a stronger form of
indistinguishability, namely that the ciphertext state is completely
independent of the message (because our DI-VCECM protocol basically involves
applying a one-time-pad to the message, which serves to perfectly encrypt it).
However, we present the definition in the above form for consistency with past
work, and also because it is less clear how to formulate an analogous property
for cloning and cloning-distinguishing attacks, which we discuss next.

######  Definition 3 (Cloning attack and uncloneable security).

A _cloning attack_ on a DI-VKECM scheme is a process of the following form:

  1. 1.

A uniformly random message $M\in\mathcal{M}$ is prepared and $\mathsf{Enc}$ is
applied to it, producing a flag $F$, a private key $K_{\mathrm{priv}}$, and a
ciphertext state $\rho$ (on a register $Q$).

  2. 2.

An arbitrary channel is applied to the ciphertext state $\rho$ to distribute
it between Bob and Charlie.

  3. 3.

Without any further communication between Bob and Charlie except as mediated
by leakage via their devices, they receive independently generated decryption
keys from $\mathsf{KeyRel}(K_{\mathrm{priv}})$, and use them together with
their shares of the state to produce guesses $M^{\mathrm{B}}$ and
$M^{\mathrm{C}}$ respectively for the original message $M$.

A protocol is said to be _$t(\lambda)$ -uncloneable-secure_ if for all cloning
attacks, we have

$\displaystyle\Pr[(F=\text{\char
51\,})\land(M=M^{\mathrm{B}}=M^{\mathrm{C}})]\leq\frac{2^{t(\lambda)}}{|\mathcal{M}|}+\mathrm{negl}(\lambda),$

where the probability is taken over the distributions of $M$ and all
randomness in the described procedures.

Qualitatively, the smaller the function $t(\lambda)$ is, the “more secure” the
protocol is (since the probability of Bob and Charlie guessing the message is
smaller). Note that if the protocol also requires that the message is a
bitstring of length $\lambda$ (for instance in the first protocol in [BL20],
or the version of our protocol that we describe in Section 5 here), then there
is a trivial upper bound of $t(\lambda)\leq\lambda$, since in that case the
bound on the guessing probability in the above definition is just $1$. In
other words, for such protocols we only have nontrivial results when
$t(\lambda)<\lambda$.

While the definition of uncloneable security refers to uniformly distributed
messages, satisfying the above definition implies analogous properties for
messages that are not uniformly distributed; see [BL20].

######  Definition 4 (Cloning-distinguishing attack and uncloneable-
indistinguishable security).

A _cloning-distinguishing attack_ on a DI-VKECM scheme is a process of the
following form (here for ease of explanation we take the message space
$\mathcal{M}$ to contain a particular value labelled as $\mathbf{0}$ without
loss of generality):

  1. 1.

An adversary generates a state on registers $ME$, where $M$ is a classical
register on the message space and $E$ is some (possibly quantum) side-
information.

  2. 2.

A uniformly random bit $B$ is independently generated, and used as follows: if
$B=0$ then $\mathsf{Enc}(1^{\lambda},\mathbf{0})$ is performed; if $B=1$ then
$\mathsf{Enc}(1^{\lambda},M)$ is performed on the $M$ register produced by the
adversary in the previous step. In either case, a flag $F$, a private key
$K_{\mathrm{priv}}$, and a ciphertext state $\rho$ (on a register $Q$) are
produced.

  3. 3.

An arbitrary channel is applied to the state on $QE$ to distribute it between
Bob and Charlie.

  4. 4.

Without any further communication between Bob and Charlie except as mediated
by leakage via their devices, they receive independently generated decryption
keys from $\mathsf{KeyRel}(K_{\mathrm{priv}})$, and use them together with
their shares of the state to produce bits $B^{\prime}$ and $B^{\prime\prime}$
respectively.

A protocol is said to be _uncloneable-indistinguishable-secure_ if for all
cloning attacks, we have

$\displaystyle\Pr[(F=\text{\char
51\,})\land(B=B^{\prime}=B^{\prime\prime})]\leq\frac{1}{2}+\mathrm{negl}(\lambda),$

where the probability is taken over all randomness in the described
procedures.

Following [BL20, GMP22], we have stated the above definitions of
indistinguishable security and uncloneable-indistinguishable security in terms
of the adversary initially generating an arbitrary classical-quantum state on
$ME$, which we shall denote here as $\rho^{\mathrm{ini}}_{ME}$. However, one
can argue that without loss of generality, we can restrict to attacks where
the value on the $M$ register is deterministic and the state on the $E$
register is trivial (as long as the final measurement in each of the attacks
is allowed to be a general POVM). This follows from the following observation:
consider any attack that achieves the optimal “success probability” (in the
sense of the probability of the event stated at the end of the respective
definition). This attack would be based on some initial state
$\rho^{\mathrm{ini}}_{ME}$, which is a classical-quantum state and hence
equivalent to a classical mixture of states of the form
$\ket{m}\\!\\!\bra{m}_{M}\otimes\rho_{E|m}$. Because of this, the success
probability of this attack is a convex combination of the success
probabilities that would be obtained by preparing the initial state in the
form $\ket{m}\\!\\!\bra{m}_{M}\otimes\rho_{E|m}$ for various values of $m$. By
linearity, at least one particular value $m^{\star}$ must attain the optimal
success probability151515Furthermore, by observing that if
$\rho^{\mathrm{ini}}_{ME}=\ket{\mathbf{0}}\\!\\!\bra{\mathbf{0}}_{M}\otimes\rho_{E|\mathbf{0}}$
then the success probability can only be exactly $1/2$ (since in that case the
states produced for either value of $B$ are identical), we see that we can
take $m^{\star}\neq\mathbf{0}$ without loss of generality., or in other words
the same success probability could have been attained by the adversary simply
preparing the initial state in the form
$\ket{m^{\star}}\\!\\!\bra{m^{\star}}_{M}\otimes\rho_{E|m^{\star}}$. With this
attack the state on $M$ is deterministic as claimed; furthermore, since the
state on $E$ is now in product with $M$, we can simply suppose that the state
$\rho_{E|m^{\star}}$ is generated after $\mathsf{Enc}$ is applied (and hence
absorbed into the subsequent measurements/channels) rather than at the
beginning of the attack.

It was shown in [BL20] that these security definitions are somewhat related to
each other, as follows:

######  Lemma 8.

Uncloneable-indistinguishability implies indistinguishability.

######  Lemma 9.

If the message space size $|\mathcal{M}|$ is independent of the security
parameter $\lambda$, then $0$-uncloneability implies uncloneable-
indistinguishability.

While the definitions they use differ slightly from ours (because they
consider protocols which do not have an abort outcome and do not use variable
decryption keys), their arguments carry over straightforwardly to our
scenario; we outline the main ideas here.

###### Proof sketch.

For Lemma 8, [BL20] observe that given any distinguishing attack, one can
immediately construct a cloning-distinguishing attack that succeeds with the
same probability: simply perform the distinguishing attack to produce the
classical bit $\hat{B}$, and distribute copies of this value to Bob and
Charlie, who output it as their values $B^{\prime},B^{\prime\prime}$
respectively in the cloning-distinguishing attack. Hence the optimal success
probability of a distinguishing attack cannot be higher than that for cloning-
distinguishing attacks, and referring back to the definitions we see that this
means uncloneable-indistinguishability implies indistinguishability.

For Lemma 9, the idea is again similar: given a cloning-distinguishing attack
that succeeds with some probability $p\in[0,1]$, [BL20] prove that one can
construct a cloning attack that succeeds with probability at least
$\frac{2}{|\mathcal{M}|}p$. (We remark that our above observation regarding
the structure of optimal cloning-distinguishing attacks can somewhat simplify
this proof in [BL20], since without loss of generality we can suppose that the
cloning-distinguishing attack starts by simply setting $M$ to a deterministic
value.) This implies that the optimal success probability of a cloning-
distinguishing attack is at most $\frac{|\mathcal{M}|}{2}$ times greater than
that of a cloning attack, and since $0$-uncloneability is the statement that
the latter is upper bounded by
$\frac{1}{|\mathcal{M}|}+\mathrm{negl}(\lambda)$, this gives the desired
result as long as $|\mathcal{M}|$ is independent of $\lambda$. To see that
this approach also applies for our definitions, one simply has to instead
consider the states conditioned on $F=\text{\char 51\,}$, in which case the
[BL20] construction gives

$\Pr[M=M^{\mathrm{B}}=M^{\mathrm{C}}|F=\text{\char
51\,}]\geq\frac{2}{|\mathcal{M}|}\Pr[B=B^{\prime}=B^{\prime\prime}|F=\text{\char
51\,}],$

where the right-hand-side refers to the probabilities in the cloning attack,
and the left-hand-side refers to those in the cloning-distinguishing attack
constructed from it. Multiplying both sides of this inequality by
$\Pr[F=\text{\char 51\,}]$ and then following the same argument as above gives
the desired result for our context. ∎

Due to the above reductions, we see that for protocols with $\mathcal{M}$
independent of $\lambda$, proving $0$-uncloneability would be sufficient to
imply the other two properties as well. In this work, for messages of
arbitrary size we only prove $O(\lambda)$-uncloneability and hence we cannot
use the above simplification, but we shall show that if the message size is
only a single bit or trit, $0$-uncloneability can be achieved and hence the
other two properties follow automatically.

##  4 Cloning game

For any non-local game $G$ (which includes games with multiple rounds and with
a variable number of players, like we shall soon describe), we shall use
$\omega^{*}(G)$ to denote its quantum value, i.e., its maximum winning
probability with a quantum strategy. We shall use $\omega^{*}(G^{l})$ to
denote the winning probability of $l$ parallel copies of $G$, and
$\omega^{*}(G^{t/l})$ to denote the winning probability of $t$ copies out of
$l$ parallel copies of $G$.

###  4.1 The CHSH game

The CHSH game is one of the simplest one-round non-local games between two
players Alice and Bob, which is as follows:

  * •

Alice and Bob get inputs $x,y\in\\{0,1\\}$ uniformly at random.

  * •

Alice and Bob output $a,b\in\\{0,1\\}$.

  * •

The game is won if $a_{i}\oplus b_{i}=x_{i}\cdot y_{i}$.

The optimal classical winning probability $\omega(\mathrm{CHSH})$ of the game
is $\frac{3}{4}$, while the optimal quantum winning probability is
$\omega^{*}(\mathrm{CHSH})=\frac{1}{2}\left(1+\frac{1}{\sqrt{2}}\right)$. In
the optimal quantum strategy for the CHSH game, Alice and Bob share the
maximally entangled state $\frac{1}{\sqrt{2}}(\ket{00}+\ket{11})$. Alice’s
measurements corresponding to inputs 0 and 1 are
$\\{\ket{0}\\!\\!\bra{0},\ket{1}\\!\\!\bra{1}\\}$ and
$\\{\ket{\frac{\pi}{4}}\\!\\!\bra{\frac{\pi}{4}},\ket{-\frac{\pi}{4}}\\!\\!\bra{-\frac{\pi}{4}}\\}$
respectively, and Bob’s measurements corresponding to 0 and 1 are
$\\{\ket{\frac{\pi}{8}}\\!\\!\bra{\frac{\pi}{8}},\ket{-\frac{3\pi}{8}}\\!\\!\bra{-\frac{3\pi}{8}}\\}$
and
$\\{\ket{\frac{3\pi}{8}}\\!\\!\bra{\frac{3\pi}{8}},\ket{-\frac{\pi}{8}}\\!\\!\bra{-\frac{\pi}{8}}\\}$
respectively, where we are using $\ket{\alpha}$ to denote the state
$\cos\alpha\ket{0}+\sin\alpha\ket{1}$. We shall often refer to these state and
measurements as the ideal CHSH state and measurements.

The CHSH game satisfies the following _rigidity_ property (given by a slight
extension of Theorem 2 in [MYS12], by writing the projectors
$\Pi,\widetilde{\Pi}$ in the following statement as linear combinations of the
hermitian observables described in that work).

######  Fact 10.

Let $\ket{\phi},\Pi^{\mathrm{A}}_{a|x},\Pi^{\mathrm{B}}_{b|y}$ denote the
state and measurements used in the ideal CHSH strategy. Suppose a quantum
strategy for the CHSH game with shared state $\ket{\widetilde{\phi}}$ and
projective measurements $\widetilde{\Pi}^{\mathrm{A}}_{a|x}$ and
$\widetilde{\Pi}^{\mathrm{B}}_{b|y}$ of Alice and Bob achieves winning
probability $\omega^{*}(\mathrm{CHSH})-\mu$. Then there exist isometries
$V^{\mathrm{A}},V^{\mathrm{B}}$ acting only on Alice and Bob’s registers in
$\ket{\rho}$, and a state $\ket{\mathrm{junk}}$ such that for all $x,y,a,b$,

$\displaystyle\left\lVert V^{\mathrm{A}}\otimes
V^{\mathrm{B}}\ket{\widetilde{\phi}}-\ket{\phi}\otimes\ket{\mathrm{junk}}\right\rVert_{2}\leq
O(\mu^{1/4});$ $\displaystyle\left\lVert(V^{\mathrm{A}}\otimes
V^{\mathrm{B}})(\widetilde{\Pi}^{\mathrm{A}}_{a|x}\otimes\mathbbm{1})\ket{\widetilde{\phi}}-(\Pi^{\mathrm{A}}_{a|x}\otimes\mathbbm{1})\ket{\phi}\otimes\ket{\mathrm{junk}}\right\rVert_{2}\leq
O(\mu^{1/4});$ $\displaystyle\left\lVert(V^{\mathrm{A}}\otimes
V^{\mathrm{B}})(\mathbbm{1}\otimes\widetilde{\Pi}^{\mathrm{B}}_{b|y})\ket{\widetilde{\phi}}-(\mathbbm{1}\otimes\Pi^{\mathrm{B}}_{b|y})\ket{\phi}\otimes\ket{\mathrm{junk}}\right\rVert_{2}\leq
O(\mu^{1/4}).$

Alice’s ideal measurements in the CHSH game are in the computational and
Hadamard basis. Since the ideal shared state between Alice and Bob is the
maximally entangled state, Bob’s state when Alice does the measurement
corresponding to $x=0$ or 1 and obtains outcome $a=0$ or 1 is $H^{x}\ket{a}$.
These states are called Wiesner states, and we shall denote the Wiesner state
produced when $x$ is the input and $a$ is the output by $\ket{a^{x}}$. The
Wiesner states satisfy the following monogamy of entanglement property, which
we shall use in our security proof.

######  Fact 11 ([TFKW13, BL20]).

If $\ket{a^{x}}$ denotes a Wiesner state, then for any Hilbert spaces
$\mathcal{H}^{\mathrm{B}}$ and $\mathcal{H}^{\mathrm{C}}$, any two collection
of measurements $\\{\Pi^{\mathrm{B}}_{a|x}\\}_{a}$ and
$\\{\Pi^{\mathrm{C}}_{a|x}\\}_{a}$ (for each $x$) on
$\mathcal{H}^{\mathrm{B}}$ and $\mathcal{H}^{\mathrm{C}}$ respectively, and
any CPTP map
$\Lambda:\mathbb{C}^{2}\to\mathcal{H}^{\mathrm{B}}\otimes\mathcal{H}^{\mathrm{C}}$,
we have

$\mathop{\mathbb{E}}_{a,x}\operatorname{Tr}\left[\left(\Pi^{\mathrm{B}}_{a|x}\otimes\Pi^{\mathrm{C}}_{a|x}\right)\Lambda(\ket{a^{x}}\\!\\!\bra{a^{x}})\right]=\frac{1}{2}\left(1+\frac{1}{\sqrt{2}}\right).$

Note that we can also define $n$-qubit versions of the Wiesner states, and the
above result holds with the right-hand side being
$\left(\frac{1}{2}+\frac{1}{2\sqrt{2}}\right)^{n}$ in that case. However, we
shall only need the result for single-qubit Wiesner states for our purposes.

###  4.2 The 2-round cloning game

Using the rigidity or self-testing property of the CHSH game and the monogamy
of entanglement property of the Wiesner states, we shall formulate a game that
we shall call the 2-round cloning game, which we first qualitatively describe
as follows. In a single instance of the game, one of two things will happen
probabilistically: either the CHSH game will be played between two players
whom we call Alice and Barlie, or Alice will get her input for the CHSH game
and produce her output as usual (without knowing what is happening on Barlie’s
side), but Barlie will split into two players Bob and Charlie, who will both
be given the same input as Alice and have to guess her output bit. For
technical reasons, we shall actually split the game into two rounds, with the
CHSH component happening in the first round and Bob and Charlie guessing
Alice’s output in the second.

The measurements used by Barlie for the CHSH component may be different from
those used by Bob and Charlie for the guessing component. However, Alice’s
device does not know which component is taking place, and the shared state
between Alice and Barlie or Alice, Bob and Charlie is distributed beforehand,
and therefore if the CHSH component is won with probability close to
$\omega^{*}(\mathrm{CHSH})$, then by the self-testing property of CHSH, the
shared state and Alice’s measurements must be close to the ideal state and
measurements. Thus, the state on Bob and Charlie’s side post-Alice’s
measurement must be close to a Wiesner state, which will allow us to use the
monogamy of entanglement property to upper bound the probability of Bob and
Charlie both guessing Alice’s output. We shall define the 2-round cloning game
formally below, and formalize the above argument about its winning probability
in Section 4.4.

We now give the detailed description. The 2-round cloning game
$\mathrm{CLONE}_{\gamma}$ with parameter $\gamma$ involves four players Alice,
Barlie, Bob and Charlie, although not all of them have to perform actions in
each round. At the beginning of the game, there can be some arbitrary
entangled state shared between Alice and Barlie.161616For the security
analysis, it might seem more general to allow an initial entangled state
across all four parties. However, as will become clear from the later
description, this does not make any difference since any registers Bob and
Charlie might have started with could also be analyzed by initially giving
them to Barlie instead. The first round only involves the two players Alice
and Barlie, who receive some inputs and produce some outputs (without
communication). Specifically, the first round inputs, outputs and the winning
condition are as follows:

  * •

Alice receives $x\in\\{0,1\\}$ uniformly at random. Barlie receives
$u\in\\{0,1,\mathrm{keep}\\}$, such that $u=\mathrm{keep}$ with probability
$1-\gamma$, and $u=0$ or $1$ with probability $\frac{\gamma}{2}$.

  * •

Alice outputs $a$ and Barlie outputs $s$.

  * •

The first round win condition is

$\mathsf{V}_{1}(x,u,a,s)=\begin{cases}1&\text{ if }u=\mathrm{keep}\\\ 1&\text{
if }(u\neq\mathrm{keep})\land(a\oplus s=x\cdot u)\\\ 0&\text{
otherwise.}\end{cases}$

After Barlie produces his first round output, he can do some further operation
on their part of the shared state (though this can also be absorbed into the
operation he does to produce $s$). Then Barlie distributes his state in some
arbitrary fashion between two other players, Bob and Charlie. Bob and Charlie
do not communicate after this (and Barlie no longer plays any further role in
the game, apart from having his first-round values $(u,s)$ being involved in
the win condition). In the second round, Alice and Barlie do not receive any
inputs and are not required to produce any output; Bob and Charlie receive
inputs and have to produce outputs separately. The inputs, outputs and win
condition in the second round are as follows:

  * •

Bob and Charlie both receive $x$ as their input and produce $b$ and $c$ as
their outputs.

  * •

The second round win condition is

$\mathsf{V}_{2}(x,u,a,s,b,c)=\begin{cases}1&\text{ if }u\neq\mathrm{keep}\\\
1&\text{ if }(u=\mathrm{keep})\land(b=c=a)\\\ 0&\text{ otherwise.}\end{cases}$

###  4.3 Modifying the 2-round cloning game

Although it would be nice to be able to use $\mathrm{CLONE}_{\gamma}$ directly
in our encryption scheme and security proof, in order to be able to prove a
parallel repetition theorem, we need to modify the game somewhat, by an
“anchoring" transformation similar to [Vid17, KT20]. In our case, this means
that Alice’s input $x$ will not be revealed with some probability $\alpha$
independently to Bob and Charlie; we can let the second round win condition be
automatically satisfied for Bob and Charlie if either of them does not receive
$x$ (this will be denoted by the input being $\bot$, and in the protocol will
correspond to this instance not being used for key generation). This is needed
so that Bob and Charlie’s second round inputs and Alice’s registers are in
product with some probability.

The modified 2-round cloning game $\mathrm{CLONE}_{\gamma,\alpha}$ is the same
as $\mathrm{CLONE}_{\gamma}$ in the first round, and after the first round,
Barlie again distributes his state between Bob and Charlie in the same fashion
as $\mathrm{CLONE}_{\gamma}$. However, the second round inputs, outputs and
win condition for $\mathrm{CLONE}_{\gamma,\alpha}$ are instead as follows:

  * •

Bob and Charlie receive $y,z\in\\{0,1,\bot\\}$ respectively, such that
$y=\bot$ and $z=\bot$ independently with probability $\alpha$, and when $y$
and $z$ are not $\bot$, they are equal to $x$.

  * •

Bob and Charlie output $b$ and $c$ respectively.

  * •

The second round win condition is

$\mathsf{V}_{2}(x,u,y,z,a,s,b,c)=\begin{cases}1&\text{ if
}u\neq\mathrm{keep}\\\ 1&\text{ if }(u=\mathrm{keep})\land(y=z=\bot)\\\
1&\text{ if }(u=\mathrm{keep})\land(y=\bot\neq z)\\\ 1&\text{ if
}(u=\mathrm{keep})\land(z=\bot\neq y)\\\ 1&\text{ if
}(u=\mathrm{keep})\land(y,z\neq\bot)\land(b=c=a)\\\ 0&\text{
otherwise.}\end{cases}$

For later use, we summarize the overall win condition
$\mathsf{V}_{1}(x,u,a,s)\cdot\mathsf{V}_{2}(x,u,y,z,a,s,b,c)=1$ as follows:

$\displaystyle\mathsf{V}_{1}(x,u,a,s)\cdot\mathsf{V}_{2}(x,u,y,z,a,s,b,c)=\begin{cases}1&\text{
if }(u\neq\mathrm{keep})\land(a\oplus s=x\cdot u)\\\ 1&\text{ if
}(u=\mathrm{keep})\land(y=z=\bot)\\\ 1&\text{ if
}(u=\mathrm{keep})\land(y=\bot\neq z)\\\ 1&\text{ if
}(u=\mathrm{keep})\land(z=\bot\neq y)\\\ 1&\text{ if
}(u=\mathrm{keep})\land(y,z\neq\bot)\land(b=c=a)\\\ 0&\text{
otherwise.}\end{cases}$ (3)

As qualitatively described above, the various possible win conditions when
$u=\mathrm{keep}$ (which arise mainly from the second-round conditions, since
the first round is trivially won for that case) can be equivalently rewritten
into a single condition

$\displaystyle(y=\bot)\lor(z=\bot)\lor(b=c=a),$

i.e. (at least) one of Bob and Charlie got $\bot$ as input, or they both
guessed $a$ correctly.

In our actual parallel repetition proof, we shall not need to use any specific
structure of $\mathrm{CLONE}_{\gamma,\alpha}$ aside from its input
distribution, and thus the parallel repetition result holds for a more general
class of games. The specific properties of the input distribution that we
shall need to use are:

  1. (i)

The distribution $\mathsf{P}_{XU}$ of the first round inputs is a product
distribution; $U$ is also independent of the second round inputs.

  2. (ii)

The second round inputs $Y,Z$ are correlated with $X$ in the following way:

$\displaystyle\mathsf{P}_{XYZ}(x,x,x)=(1-\alpha)^{2}\cdot\mathsf{P}_{X}(x)$
$\displaystyle\mathsf{P}_{XYZ}(x,\bot,x)=\mathsf{P}_{XYZ}(x,x,\bot)=\alpha(1-\alpha)\cdot\mathsf{P}_{X}(x)$
$\displaystyle\mathsf{P}_{XYZ}(x,\bot,\bot)=\alpha^{2}\cdot\mathsf{P}_{X}(x).$

Note that the above implies that conditioned on $Y=Z=\bot$, the conditional
distribution $\mathsf{P}_{XU||\bot,\bot}$ of $x,u$ is exactly the same as the
marginal distribution of $x,u$. Similarly, conditioned on $Y=\bot$, the
conditional distribution $\mathsf{P}_{XUZ|Y=\bot}$ is the same as the marginal
distribution of $x,u,z$, and conditioned on $Z=\bot$, the conditional
distribution $\mathsf{P}_{XUY|Z=\bot}$ is the same as the marginal
distribution of $x,u,y$. Moreover, $Y$ and $Z$ are independent conditioned on
$X$, and since $U$ is independent of everything else, $YZ$ are independent
conditioned on $XU$ as well. In fact, if we define random variables $DF$ as
follows: $D$ is a uniformly random bit, and $F=XU$ or $F=YZ$ depending on
whether $D=0$ or $D=1$, then $XUYZ$ are independent conditioned on $DF$, i.e.,
$\mathsf{P}_{XUYZ|DF}$ is a product distribution.

###  4.4 The winning probability of $\mathrm{CLONE}_{\gamma,\alpha}$

We shall now show that $\omega^{*}(\mathrm{CLONE}_{\gamma,\alpha})$ is
strictly less than the trivial upper bound of
$(1-\gamma)+\gamma\omega^{*}(\mathrm{CHSH})$. At first sight, it might appear
that this claim holds simply by the following argument sketch: if Bob and
Charlie could win perfectly in the second round, then Alice’s first-round
output must be deterministic conditioned on their side-information, which
implies that the devices cannot achieve the maximum quantum CHSH winning
probability in the first round. However, this idea has two technical flaws
(which we implicitly addressed in previous works [KST22, KT20], though without
detailed elaboration). Firstly, for some non-local games it is known that the
classical winning probability can be exceeded while still ensuring some inputs
give deterministic outputs (see e.g. the _partially deterministic polytope_ in
[WMP14]); also, in our scenario Bob and Charlie’s guesses could potentially
depend on Alice’s round-1 input, in which case the above argument sketch does
not straightforwardly work (see e.g. [Tan21] Appendix B)171717Alternatively,
observe that the argument clearly fails if we were to consider only a single
player Bob instead of both Bob and Charlie, since even if the devices shared
the ideal CHSH state in the first round, when the second round occurs Bob
could simply (focusing on the $u=\text{keep}$ and $y\neq\bot$ case, since
otherwise the second round is automatically won) use his knowledge of Alice’s
first-round input to measure in an appropriate basis and learn her output
perfectly.. Secondly, even if that obstacle were overcome, this argument would
only imply that any particular strategy for $\mathrm{CLONE}_{\gamma,\alpha}$
has winning probability less than
$(1-\gamma)+\gamma\omega^{*}(\mathrm{CHSH})$; it would not rule out the
possibility of a sequence of strategies achieving winning probabilities
_arbitrarily close_ to $(1-\gamma)+\gamma\omega^{*}(\mathrm{CHSH})$. For our
later security proof, we really do need the property that
$\omega^{*}(\mathrm{CLONE}_{\gamma,\alpha})$ is strictly less than
$(1-\gamma)+\gamma\omega^{*}(\mathrm{CHSH})$, which is a stronger condition
(since it means that all strategies have winning probability _bounded away
from_ $(1-\gamma)+\gamma\omega^{*}(\mathrm{CHSH})$). Hence the above argument
sketch does not work by itself; we now present the actual proof.181818We also
remark that in order to obtain the desired bound, a self-testing result with
“nonzero robustness” seems to be necessary, i.e. if Fact 10 had only been
proven for $\mu=0$, it would not have been enough to obtain our desired result
(since it leaves open the possibility of devices with CHSH winning probability
arbitrarily close to $\omega^{*}(\mathrm{CHSH})$ while still allowing Bob and
Charlie to win the second round with arbitrarily high probability).

######  Theorem 12.

For any $\gamma,\alpha\in(0,1)$, there exists a value
$\delta_{\gamma,\alpha}>0$ such that
$\omega^{*}(\mathrm{CLONE}_{\gamma,\alpha})$ is at most
$(1-\gamma)+\gamma\omega^{*}(\mathrm{CHSH})-\delta_{\gamma,\alpha}$.

###### Proof.

Take an arbitrary strategy for playing $\mathrm{CLONE}_{\gamma,\alpha}$. Note
that the events listed in (3) that give
$\mathsf{V}_{1}(X,U,A,S)\cdot\mathsf{V}_{2}(X,U,Y,Z,A,S,B,C)=1$ are mutually
exclusive. Therefore, the winning probability of this strategy on
$\mathrm{CLONE}_{\gamma,\alpha}$ is given by summing the probabilities it
gives for these events.

We begin by considering the first event. We first note that $\Pr[A\oplus
S=X\cdot U|U\neq\mathrm{keep}]$ is just the probability for this strategy to
win the CHSH game if it is played in the first round. Therefore, we can denote
this value as $\omega^{*}(\mathrm{CHSH})-\mu$ for some
$\mu\in[0,\omega^{*}(\mathrm{CHSH})]$ without loss of generality. Putting this
together with $\Pr[U\neq\mathrm{keep}]=\gamma$ from the game definition, we
have

$\displaystyle\Pr\left[(U\neq\mathrm{keep})\land(A\oplus S=X\cdot
U)\right]=\gamma(\omega^{*}(\mathrm{CHSH})-\mu).$

For the second, third, and fourth events, we apply the game definition to get:

$\displaystyle\Pr\left[(U=\mathrm{keep})\land(Y=Z=\bot)\right]=(1-\gamma)\alpha^{2},$
$\displaystyle\Pr\left[(U=\mathrm{keep})\land(Y=\bot\neq
Z)\right]=(1-\gamma)\alpha(1-\alpha),$
$\displaystyle\Pr\left[(U=\mathrm{keep})\land(Z=\bot\neq
Y)\right]=(1-\gamma)\alpha(1-\alpha),$

so the sum of their probabilities is

$(1-\gamma)(\alpha^{2}+2\alpha(1-\alpha))=(1-\gamma)(1-\tilde{\alpha}),\quad\text{
where }\tilde{\alpha}=(1-\alpha)^{2}.$

For the last event, first recall that we have parametrized the probability of
this strategy winning the CHSH game as $\omega^{*}(\mathrm{CHSH})-\mu$. Hence
by the CHSH rigidity property (Fact 10), after Alice performs her measurement
(chosen uniformly at random), the resulting joint state across her
input/output registers and Barlie’s register is $O(\mu^{1/4})$-close in trace
distance to the “ideal” mixture
$\mathop{\mathbb{E}}_{a,x}\left[\ket{x}\\!\\!\bra{x}\otimes\ket{a}\\!\\!\bra{a}\otimes\ket{a^{x}}\\!\\!\bra{a^{x}}\right]$
(where $\ket{a^{x}}\\!\\!\bra{a^{x}}$ again denotes Wiesner states), up to an
isometry on Barlie’s register.191919While that rigidity property is only
stated for projective measurements, in this case we are interested only in the
classical-quantum state produced after Alice’s measurements, which allows us
to focus on a suitably chosen Stinespring dilation to projective measurements
without loss of generality. Putting this together with the monogamy of
entanglement property (Fact 11), we can conclude that
$\Pr\left[B=C=A|(U=\mathrm{keep})\land(Y,Z\neq\bot)\right]\leq\frac{1}{2}\left(1+\frac{1}{\sqrt{2}}\right)+O(\mu^{1/4})$
(here we implicitly used the fact that the event
$(U=\mathrm{keep})\land(Y,Z\neq\bot)$ is independent of Alice’s measurement
distribution). Combining this with the trivial bound
$\Pr\left[B=C=A|(U=\mathrm{keep})\land(Y,Z\neq\bot)\right]$ $\leq 1$, we have
overall

$\displaystyle\Pr\left[(U=\mathrm{keep})\land(Y,Z\neq\bot)\land(B=C=A)\right]$
$\displaystyle\leq(1-\gamma)(1-\alpha)^{2}\min\left\\{1,\frac{1}{2}\left(1+\frac{1}{\sqrt{2}}\right)+O(\mu^{1/4})\right\\}$
$\displaystyle=(1-\gamma)\tilde{\alpha}\min\left\\{1,\frac{1}{2}\left(1+\frac{1}{\sqrt{2}}\right)+O(\mu^{1/4})\right\\}.$

Summing the terms, we get the following upper bound on the winning
probability:

$\displaystyle(1-\gamma)\left(1-\tilde{\alpha}+\tilde{\alpha}\min\left\\{1,\frac{1}{2}\left(1+\frac{1}{\sqrt{2}}\right)+O(\mu^{1/4})\right\\}\right)+\gamma(\omega^{*}(\mathrm{CHSH})-\mu)$
$\displaystyle=$
$\displaystyle(1-\gamma)\min\left\\{1,1-\tilde{\alpha}+\tilde{\alpha}\left(\frac{1}{2}\left(1+\frac{1}{\sqrt{2}}\right)+O(\mu^{1/4})\right)\right\\}+\gamma(\omega^{*}(\mathrm{CHSH})-\mu)$
$\displaystyle=$
$\displaystyle(1-\gamma)\min\left\\{1,\beta+O(\mu^{1/4})\right\\}+\gamma(\omega^{*}(\mathrm{CHSH})-\mu)\quad\text{for
}\beta=1-\tilde{\alpha}+\tilde{\alpha}\left(\frac{1}{2}\left(1+\frac{1}{\sqrt{2}}\right)\right)<1,$

absorbing a factor of $\tilde{\alpha}$ into the $O(\mu^{1/4})$ term in the
last line (recall $\alpha$ is a constant for the purposes of this proof).

Finally, observe that we have
$(1-\gamma)\min\left\\{1,\beta+O({\mu}^{1/2})\right\\}\leq 1-\gamma$ and
$\gamma(\omega^{*}(\mathrm{CHSH})-\mu)\leq\gamma\omega^{*}(\mathrm{CHSH})$ for
any $\mu\in[0,\omega^{*}(\mathrm{CHSH})]$; however, there is no $\mu$ in that
interval that simultaneously saturates both inequalities (the only value that
saturates the second inequality is $\mu=0$, in which case the first inequality
is not saturated since $\beta<1$). Therefore we have a strict inequality

$\displaystyle(1-\gamma)\min\left\\{1,\beta+O(\mu^{1/4})\right\\}+\gamma(\omega^{*}(\mathrm{CHSH})-\mu)<(1-\gamma)+\gamma\omega^{*}(\mathrm{CHSH}),$

for all $\mu\in[0,\omega^{*}(\mathrm{CHSH})]$. To ensure the winning
probability is bounded away from $(1-\gamma)+\gamma\omega^{*}(\mathrm{CHSH})$
by a constant $\delta_{\gamma,\alpha}>0$, we note that
$(1-\gamma)\min\left\\{1,\beta+O(\mu^{1/4})\right\\}+\gamma(\omega^{*}(\mathrm{CHSH})-\mu)$
is a continuous function of $\mu$ on the closed interval
$[0,\omega^{*}(\mathrm{CHSH})]$. Hence it attains its maximum at some value in
that interval, and this maximal value will be an upper bound strictly smaller
than $(1-\gamma)+\gamma\omega^{*}(\mathrm{CHSH})$, as desired. ∎

With this, we give the following parallel repetition theorem upper bounding
the winning probability of $\mathrm{CLONE}_{\gamma,\alpha}^{t/l}$:

######  Theorem 13.

There exists $\kappa>0$ such that for $\delta_{\gamma,\alpha}$ from Theorem
12, and
$t=((1-\gamma)+\gamma\omega^{*}(\mathrm{CHSH})-{\delta_{\gamma,\alpha}}/{2})l$,

$\omega^{*}\left(\mathrm{CLONE}_{\gamma,\alpha}^{t/l}\right)\leq
2^{-\kappa\delta_{\gamma,\alpha}^{3}\alpha^{4}l}.$

We prove this theorem (in fact, a more general version of it) in Section 7.

##  5 Uncloneable encryption scheme with variable keys

In this section, we prove our main theorem:

######  Theorem 14.

There is a scheme for DI-VKECM with message space
$\mathcal{M}=\\{0,1\\}^{\lambda}$, such that:

  1. 1.

It satisfies the completeness property (1) given i.i.d. honest devices with a
constant level of noise;

  2. 2.

It achieves indistinguishable security;

  3. 3.

There exists some $\nu>0$ such that the scheme achieves
$t(\lambda)$-uncloneable security against dishonest devices with $\nu\lambda$
bits of leakage, where $t(\lambda)$ is a function satisfying
$t(\lambda)<\lambda$ for all sufficiently large $\lambda$.

The protocol achieving Theorem 14 is described in Scheme 1. We prove that
Scheme 1 satisfies completeness in Section 5.1, and prove that it satisfies
indistinguishability and $t(\lambda)$-uncloneability in Section 5.2, which
together constitute the proof of Theorem 14. Before describing the protocol,
we shall first describe the devices that our protocol requires, the noise
model we use, and the choices of various parameters in the description of the
scheme.

#### Description of devices.

Our uncloneable encryption scheme, which we shall describe as Scheme 1 below,
is carried out with devices compatible with $l$ instances of the CHSH game,
where $l$ will be taken to be equal to the security parameter $\lambda$. Since
we shall be working in the parallel setting, we assume the client and
receiver’s devices will only take inputs for all $l$ of the instances at once,
although some of the inputs may be “blank" as we shall soon discuss. The
client’s device takes inputs $x_{1}\ldots x_{l}\in\\{0,1\\}^{l}$, and the
receiver’s device takes inputs $y_{1}\ldots y_{l}\in\\{0,1,2,3,\perp\\}^{l}$.
When the receiver is honest, the shared state between the client and the
receiver is $l$ i.i.d. copies of (a noisy version of) the maximally entangled
state $\ket{\Phi^{+}}=\frac{1}{\sqrt{2}}(\ket{00}+\ket{11})$ of two qubits.
Also in the honest case, the client’s device performs Alice’s ideal CHSH
measurement corresponding to $x_{i}$ on the $i$-th copy of the shared state.
The honest behaviour of the receiver’s device is to perform Bob’s ideal CHSH
measurement corresponding to $y_{i}$ on the $i$-th copy, if
$y_{i}\in\\{0,1\\}$, and Alice’s ideal CHSH measurement on the $i$-th copy, if
$y_{i}\in\\{2,3\\}$. If $y_{i}=\perp$, then the receiver’s honest device does
nothing on the $i$-th copy; however, we require the device’s outputs to be in
$\\{0,1\\}^{l}$, so we shall say that the honest behaviour of the devices is
to always output 0 (without measuring the state) in the locations where
$y_{i}=\perp$. We also require that the receiver’s device is able to take
inputs twice — once during the (interactive) encryption procedure and once
during decryption. However, the honest decryption procedure only requires the
use of outputs in the second round from those $i$ which had input
$y_{i}=\perp$ during encryption, which means that in the honest behaviour, all
the relevant outputs are produced by only measuring each qubit once.202020In
step 30 of our protocol description, the decryption procedure as presented
does technically provide non-trivial inputs to some locations $i$ where we had
$U_{i}\neq\mathrm{keep}$ in the first round, i.e., the first round input was
not $\perp$. However, this is only for simplicity of description — it can be
seen in step 31 that the second-round outputs corresponding to these locations
are ignored, so it does not matter what the (honest) device does on these
locations in the second round, e.g. even if it is attempting to measure the
corresponding qubit a second time.

On the other hand, in the dishonest case, we only assume that the client and
receiver’s devices hold shares of a quantum state on some bipartite Hilbert
space, and the devices can perform arbitrary measurements on their shares of
the state depending on the inputs supplied. Moreover, we allow the client and
receiver’s devices to interactively communicate with each other, and produce
outputs depending on the communication, subject only to the bounded-leakage
constraint as described in Section 3.

#### Honest-device noise model.

We allow a small amount of noise in the honest behaviour of the devices, under
a depolarizing-noise model. Specifically, we allow that rather than sharing
exactly $\ket{\Phi^{+}}=\frac{1}{\sqrt{2}}(\ket{00}+\ket{11})$ in each
instance, the honest devices instead share a _Werner state_

$\rho_{q}=(1-2q)\ket{\Phi^{+}}\\!\\!\bra{\Phi^{+}}+2q\frac{\mathbbm{1}}{4},$
(4)

where $q\in[0,1/2]$ will be referred to as the depolarizing-noise parameter.
We take the measurements for each input value to still correspond to the ideal
CHSH measurements in the manner specified above. This model for the honest
devices (in each instance) achieves a CHSH winning probability of
$(1-2q)\omega^{*}(\mathrm{CHSH})+q$, and when the input pairs $(x,y)=(0,2)$ or
$(1,3)$ are used, the outputs are equal with probability $1-q$ (and the
marginal output distributions are uniform). Note that even with noise, in the
honest case we take the shared state between the parties to be $l$ i.i.d.
copies of the same Werner state.

While this noise model is quite simple, we remark that given i.i.d. honest
devices with an arbitrary single-instance input-output distribution, it is
possible in principle to perform a depolarization procedure (see [MAG06]) to
transform their input-output distribution into a form matching the above
description (except on the input pairs $(x,y)=(0,3)$ and $(1,2)$, which do not
occur in the protocol), although this is not necessarily the optimal way to
use the devices [MPW21]. Alternatively, we note that our subsequent analysis
can in fact be phrased entirely in terms of three parameters of the (i.i.d.)
honest devices: the probability that they win the CHSH game given uniformly
random $x,y\in\\{0,1\\}$, the entropy of Alice’s output conditioned on Bob’s
output for $(x,y)=(0,2)$, and the same for $(x,y)=(1,3)$. Hence if necessary,
one could instead specify these three parameters independently, but for ease
of presentation in this work we simply use the single-parameter depolarizing-
noise model.

#### Error correction.

Because we allow some noise in the honest devices, the client and receiver’s
output strings from the devices will not be perfectly correlated even in the
honest case. We shall accommodate this in our protocol by incorporating
standard error correction procedures (see e.g. [Ari10, Ren05, TMPE17]), which
we briefly summarize as follows:

######  Fact 15.

Suppose Alice and Bob hold classical random variables $CC^{\prime}$ following
an i.i.d. distribution $\mathsf{P}_{C_{i}C^{\prime}_{i}}^{\otimes l}$. We
shall refer to an error correction procedure as a process in which Alice
computes a syndrome value $\mathtt{syn}(C)$ of length $\ell_{\mathtt{syn}}$
(in bits) to send to Bob, who uses it together with $C^{\prime}$ to produce a
guess for $C$. Then for any $\xi>1$ and $\beta<1/2$, there exists an efficient
error-correction procedure such that the syndrome length is

$\displaystyle\ell_{\mathtt{syn}}=\xi\mathsf{H}(C_{i}|C^{\prime}_{i})l,$ (5)

and the probability of Bob’s guess being wrong is upper bounded by a function
$p_{\mathrm{err}}(l)=O(2^{-l^{\beta}})$.

With this in mind, we shall lay out the error correction procedure used in our
DI-VKECM scheme. Some of the discussion here will refer to parameters and
registers appearing in various steps of the protocol; see the presentation of
Scheme 1 below for the description of such quantities.

Here we shall describe the error correction procedure in terms of arbitrary
values for the protocol parameters $\gamma,\alpha,q$. The protocol steps
corresponding to the error correction procedure are step 24, in which a
syndrome is computed for a string $\widetilde{A}$, and step 32, where the
receiver uses it to produce a guess for $\widetilde{A}$. We note that in the
honest case, when the full process
$\mathsf{Dec}\circ\mathsf{KeyRel}\circ\mathsf{Enc}$ in Scheme 1 is carried
out, at the point of step 24 the receiver holds an output string
$\widetilde{S}$ from the device along with the values $U,\widetilde{X}$.
Furthermore, the device behaviour is i.i.d. in the honest case. With this, we
take the error-correction procedure to be performed as specified in Fact 15,
interpreting the distribution on $(C_{i},C^{\prime}_{i})$ in that procedure to
be the distribution on
$(\widetilde{A}_{i},\widetilde{S}_{i}U_{i}\widetilde{X}_{i})$ for the _honest_
devices. Note that this means the value $\mathsf{H}(C_{i}|C^{\prime}_{i})$ in
(5) in this context has the following value (letting $h_{2}$ denote the binary
entropy function):

$\displaystyle\mathsf{H}(\widetilde{A}_{i}|\widetilde{S}_{i}U_{i}\widetilde{X}_{i})$
$\displaystyle=\sum_{u_{i}\tilde{x}_{i}}\Pr[U_{i}\widetilde{X}_{i}=u_{i}\tilde{x}_{i}]\mathsf{H}\\!\left(\widetilde{A}_{i}|\widetilde{S}_{i};U_{i}\widetilde{X}_{i}=u_{i}\tilde{x}_{i}\right)=(1-\gamma)(1-\alpha)h_{2}(q),$
(6)

where we have used the facts that
$\mathsf{H}\\!\left(\widetilde{A}_{i}|\widetilde{S}_{i};U_{i}\widetilde{X}_{i}=u_{i}\tilde{x}_{i}\right)=0$
whenever $u_{i}\neq\mathrm{keep}$ or $\tilde{x}_{i}=\bot$ (because
$\widetilde{A}_{i}$ is set to a deterministic value in those cases), and
$\mathsf{H}\\!\left(\widetilde{A}_{i}|\widetilde{S}_{i};U_{i}\widetilde{X}_{i}=u_{i}\tilde{x}_{i}\right)=h_{2}(q)$
otherwise (because in that case we have $u_{i}=\mathrm{keep}$ and
$\tilde{x}_{i}=x_{i}+2$, i.e. for the honest devices this corresponds to the
client and receiver measuring in the same basis on a Werner state (4), hence
their output values $(\widetilde{A}_{i},\widetilde{S}_{i})$ have uniform
marginal distributions, and the probability that they differ is $q$).

#### Parameter choices.

We now specify the parameter choices for our DI-VKECM scheme. The input/output
length $l$ for the devices is set equal to the security parameter $\lambda$ as
mentioned before, and the message is also required to be a bit string of
length $\lambda$, i.e. we have $\mathcal{M}=\\{0,1\\}^{\lambda}$. (This is a
slightly redundant parametrization in this case since
$\lambda,l,\log|\mathcal{M}|$ are all equal to each other, but we present it
this way to maintain flexibility for potentially choosing $l$ and
$\mathcal{M}$ differently in terms of $\lambda$, as shall return to in Section
6.) Take any choice of values for $\xi>1$ and $\gamma,\alpha\in(0,1)$, and set
the parameter $\delta_{\gamma,\alpha}$ appearing in the protocol to be the
corresponding value from Theorem 12. Letting $\kappa$ be the constant from
Theorem 13, we require the honest devices to have depolarizing-noise values
$q$ satisfying

$q<\frac{\delta_{\gamma,\alpha}}{4},\qquad
2\xi(1-\gamma)(1-\alpha)h_{2}(q)<\kappa\delta_{\gamma,\alpha}^{3}\alpha^{4},$
(7)

which is always possible by taking a sufficiently small value of $q$ since
$\gamma,\alpha,\delta_{\gamma,\alpha},\kappa$ have been fixed. With this, all
parameters necessary to specify the error correction procedure (in steps 24
and 32) have been fixed; in particular, the length of
$\mathtt{syn}(\widetilde{A})$ in that procedure is given by

$\ell_{\mathtt{syn}}=\xi(1-\gamma)(1-\alpha)h_{2}(q)l.$ (8)

Note that since the error-correction procedure is based on the honest
behaviour, $\ell_{\mathtt{syn}}$ is a protocol parameter, not a random
variable.

#### Protocol description.

The DI-VKECM scheme with these parameters is described below. We highlight
that when a receiver is dishonest, they do not need to be following their
parts as described in the scheme, although we still require them to supply
some values to the client at all steps where they are supposed to in the
scheme (but these values do not have to be “honestly” produced, of course).

######  Remark 3.

While we have described the encryption step in this scheme as an interactive
procedure, there is an alternative setup that does not require interaction, if
we suppose the client is able to locally impose a particular constraint on the
devices. Specifically, we could instead consider a procedure in which the
client begins by holding _both_ the devices and performs steps 4–9 on them,
before sending the “receiver’s device” over to the receiver (and then
proceeding with the rest of the scheme according to the original description),
in which case the encryption procedure is non-interactive since it only
involves the client sending messages (and devices) to the receiver. For this
version, our security proof is still valid as long as the client can enforce
that during steps 4–9, the devices are still subject to the bounded-leakage
constraint (physically, this might be possible by imposing some “shielding”
measures on the devices, keeping them well isolated from each other).
Qualitatively, this version can be viewed as having the client locally “test”
the devices (while constraining the communication/leakage between them) before
using them in the rest of the scheme.

1:

2:$\mathsf{Enc}(1^{\lambda},m)$:

3:

4: Devices of the form described above are distributed between the client and
receiver, with $l=\lambda$

5:The client samples strings $X,U$ as follows: for each $i\in[l]$, set
$X_{i}\in\\{0,1\\}$ uniformly at random, and independently set
$U_{i}=\mathrm{keep},0,1$ with probabilities $1-\gamma,\gamma/2,\gamma/2$
respectively

6:The client inputs $X$ into their device and receives an output string
$A\in\\{0,1\\}^{l}$

7:The client sends $U$ to the receiver

8:The receiver inputs $U$ into their device, interpreting
$U_{i}=\mathrm{keep}$ as $\perp$ for each $i$, and receives an output string
$S\in\\{0,1\\}^{l}$

9:The receiver sends $S$ to the client

10:The client tests if the number of $i\in[l]$ such that
$U_{i}\neq\mathrm{keep}$ and $A_{i}\oplus S_{i}\neq X_{i}\cdot U_{i}$ is at
most $(\gamma(1-\omega^{*}(\mathrm{CHSH}))+{\delta_{\gamma,\alpha}}/{2})l$

11:if the test passes then

12: The client sets the flag to $F=\text{\char 51\,}$

13: The client samples $R\in\mathcal{M}$ uniformly at random and sends
$C=m\oplus R$ to the receiver

14:else

15: The client sets the flag to $F=\text{\char 55\,}$

16: The client samples $M^{\prime}\in\mathcal{M}$ uniformly at random and
sends $C=M^{\prime}$ to the receiver

17:The client stores $(X,U,A,R)$ as the private key; the receiver stores
$\rho=\rho^{\prime}\otimes\ket{C}\\!\\!\bra{C}$ as the ciphertext, where
$\rho^{\prime}$ is the quantum state in their share of the devices

18:

19:$\mathsf{KeyRel}(k_{\mathrm{priv}})$:

20:

21:Interpret the private key as $k_{\mathrm{priv}}=(X,U,A,R)$

22:Sample a string $\widetilde{X}\in\\{0,1,\perp\\}^{l}$ as follows: for each
$i\in[l]$, set $\widetilde{X}_{i}=\bot$ with probability $\alpha$, and
otherwise set $\widetilde{X}_{i}=X_{i}+2$

23:Set a string $\widetilde{A}\in\\{0,1\\}^{l}$ as follows: for each
$i\in[l]$, set $\widetilde{A}_{i}=0$ if $U_{i}\neq\mathrm{keep}$ or
$\widetilde{X}_{i}=\bot$, and otherwise set $\widetilde{A}_{i}=A_{i}$

24:Compute the syndrome $\mathtt{syn}(\widetilde{A})$ following the error-
correction procedure described above

25:Release the decryption key
$K_{\mathrm{dec}}=(R\oplus\widetilde{A},\mathtt{syn}(\widetilde{A}),\widetilde{X})$

26:

27:$\mathsf{Dec}(\rho,k)$:

28:

29:Interpret $\rho$ as $\rho^{\prime}\otimes\ket{C}\\!\\!\bra{C}$ where
$\rho^{\prime}$ has $l$ qubit registers and $C\in\mathcal{M}$; interpret the
decryption key $k_{\mathrm{dec}}$ as
$(D,\mathtt{syn}(\widetilde{A}),\widetilde{X})$

30:Input $\widetilde{X}$ into the receiver’s device and obtain the output
string $S^{\prime}\in\\{0,1\\}^{l}$

31:Set a string $\widetilde{S}\in\\{0,1\\}^{l}$ as follows: for each
$i\in[l]$, set $\widetilde{S}_{i}=0$ if $U_{i}\neq\mathrm{keep}$ or
$\widetilde{X}_{i}=\bot$, and otherwise set $\widetilde{S}_{i}=S^{\prime}_{i}$

32:Use $\widetilde{S},U,\widetilde{X}$ and $\mathtt{syn}(\widetilde{A})$ to
compute a guess $G$ for $\widetilde{A}$

33:Output $\widetilde{M}=C\oplus D\oplus G$

Scheme 1 DI-VKECM with security parameter $\lambda$ and messages in
$\mathcal{M}=\\{0,1\\}^{\lambda}$

###  5.1 Completeness of Scheme 1

It is easy to see that Scheme 1 satisfies the property (2) that when
$F=\text{\char 55\,}$, the ciphertext state is independent of the message. We
now show that it also satisfies the completeness property (1).

######  Theorem 16.

With the parameter choices as specified in (7)-(8), Scheme 1 satisfies the
completeness property (1), with the bound on the right-hand-side being
$1-\left(e^{-\delta_{\gamma,\alpha}^{2}\lambda/8}+p_{\mathrm{err}}(\lambda)\right)$
where $p_{\mathrm{err}}$ is the function described in Fact 15.

###### Proof.

Since

$\displaystyle\Pr\left[\left(F=\text{\char
51\,}\right)\land\left(\mathsf{Dec}\circ\mathsf{KeyRel}\circ\mathsf{Enc}(1^{\lambda},m)=m\right)\right]$
$\displaystyle=$ $\displaystyle 1-\Pr\left[\left(F=\text{\char
55\,}\right)\lor\left(\mathsf{Dec}\circ\mathsf{KeyRel}\circ\mathsf{Enc}(1^{\lambda},m)\neq
m\right)\right]$ $\displaystyle=$ $\displaystyle
1-\left(\Pr\left[F=\text{\char 55\,}\right]+\Pr\left[\left(F=\text{\char
51\,}\right)\land\left(\mathsf{Dec}\circ\mathsf{KeyRel}\circ\mathsf{Enc}(1^{\lambda},m)\neq
m\right)\right]\right),$

to prove completeness it suffices to bound the two probabilities in the last
line when the devices are honest.

To bound $\Pr\left[F=\text{\char 55\,}\right]$, we recall that our model of
the honest devices gives a CHSH winning probability of
$(1-2q)\omega^{*}(\mathrm{CHSH})+q>\omega^{*}(\mathrm{CHSH})-q$. Therefore, by
the distribution of $U_{i}$ in the protocol, in each round we have

$\displaystyle\Pr[(U_{i}\neq\mathrm{keep})\land(A_{i}\oplus S_{i}\neq
X_{i}\cdot U_{i})]$ $\displaystyle=\gamma\Pr[A_{i}\oplus S_{i}\neq X_{i}\cdot
U_{i}|U_{i}\neq\mathrm{keep}]$
$\displaystyle\leq\gamma\left(1-\omega^{*}(\mathrm{CHSH})+q\right)$
$\displaystyle\leq\gamma\left(1-\omega^{*}(\mathrm{CHSH})\right)+\frac{\delta_{\gamma,\alpha}}{4}\quad\text{since
$q<\frac{\delta_{\gamma,\alpha}}{4}$ and $\gamma<1$}.$

Since this value is ${\delta_{\gamma,\alpha}}/{4}$ less than the threshold
fraction $\gamma(1-\omega^{*}(\mathrm{CHSH}))+{\delta_{\gamma,\alpha}}/{2}$ in
the step 10 test, and all the instances are i.i.d. in the honest case, we can
apply the Chernoff bound to get that the probability of failing the test (i.e.
$F=\text{\char 55\,}$) is at most $e^{-\delta_{\gamma,\alpha}^{2}l/8}$.

As for $\Pr\left[\mathsf{Dec}\circ\mathsf{Enc}(1^{\lambda},m)\neq m\right]$,
first observe that when $F=\text{\char 51\,}$, the honest receiver’s decrypted
value is equal to $m$ whenever $G=\widetilde{A}$, and hence

$\Pr\left[\left(F=\text{\char
51\,}\right)\land\left(\mathsf{Dec}\circ\mathsf{KeyRel}\circ\mathsf{Enc}(1^{\lambda},m)\neq
m\right)\right]\leq\Pr\left[\left(F=\text{\char
51\,}\right)\land\left(G\neq\widetilde{A}\right)\right]\leq\Pr\left[G\neq\widetilde{A}\right].$

Since the honest behaviour is i.i.d., and the error-correction step was taken
to be as described in Fact 15 based on the honest behaviour, we have that the
probability of the receiver’s guess $G$ being wrong (i.e.
$G\neq\widetilde{A}$) is at most $p_{\mathrm{err}}(l)$ in the honest case.
This gives the claimed result, recalling that $l=\lambda$. ∎

###  5.2 Security of Scheme 1

We begin with a simple observation about the behaviour of one-time-pads (which
can be verified with a straightforward calculation):

######  Fact 17.

Consider an arbitrary state $\rho_{EC_{1}}$ where $C_{1}$ is a classical
$n$-bit register. Suppose we generate an independent uniformly random $n$-bit
string $C_{2}$, set another register $C_{3}=C_{1}\oplus C_{2}$, and trace out
$C_{2}$. Then the resulting state $\rho_{EC_{1}C_{3}}$ has the product form
$\rho_{EC_{1}C_{3}}=\rho_{EC_{1}}\otimes\mathbbm{1}_{C_{3}}/2^{n}$, i.e. it
could equivalently be generated by setting $C_{3}$ to be a uniformly random
value independent of $\rho_{EC_{1}}$.

From this, we immediately obtain indistinguishable security for our protocol:

######  Theorem 18.

Scheme 1 is indistinguishable-secure.

###### Proof.

By definition, indistinguishable security only involves the output of the
encryption procedure excluding the private key $K_{\mathrm{priv}}$. We observe
that in the encryption procedure, the only step that depends on the message
$M$ is step 13 (when $F=\text{\char 51\,}$), where basically a one-time-pad
$R$ is independently generated uniformly at random and applied to the message.
Furthermore, since we exclude the private key in analyzing indistinguishable
security, we can trace out $R$ immediately after that step. Hence we can apply
Fact 17 (identifying $M,R$ with $C_{1},C_{2}$ respectively) to conclude that
the ciphertext register $C$ is completely independent of the message. Since
this is the only register that could potentially depend on the message here,
it clearly follows that indistinguishable security holds. ∎

Next, we turn to proving uncloneable security. We begin by first considering a
modified version of a cloning attack in which some registers are not provided
to the dishonest parties, and proving a bound on the probability that Bob and
Charlie can simultaneously guess some parts of the “internal” values
$\widetilde{A}$ produced in step 23 of the $\mathsf{KeyRel}$ procedure:

######  Lemma 19.

We introduce the following notation for some registers produced in a cloning
attack (as defined in Definition 3): when $\mathsf{KeyRel}$ is performed for
Bob (resp. Charlie), let $Y$ (resp. $Z$) denote the value of $\widetilde{X}$
produced in step 22, and let $\widetilde{A}^{\mathrm{B}}$ (resp.
$\widetilde{A}^{\mathrm{C}}$) denote the value of $\widetilde{A}$ produced in
step 23. Let $\mathcal{T}$ denote the subset of instances $i\in[l]$ such that
$Y_{i}$ and $Z_{i}$ are _both_ equal to $X_{i}$.

Now consider a cloning attack, except with the following modifications:

  * •

When the encryption procedure $\mathsf{Enc}$ is performed, the receiver is not
given the register $C$ in step 13 (or step 16).

  * •

When the key-release procedure $\mathsf{KeyRel}$ is performed for Bob (resp.
Charlie), the values $R\oplus\widetilde{A}^{\mathrm{B}}$ and
$\mathtt{syn}(\widetilde{A}^{\mathrm{B}})$ (resp.
$R\oplus\widetilde{A}^{\mathrm{C}}$ and
$\mathtt{syn}(\widetilde{A}^{\mathrm{C}})$) are omitted from the decryption
key in step 25.

  * •

Instead of Bob (resp. Charlie) producing a guess for the message $M$, he
produces a guess $G^{\mathrm{B}}$ (resp. $G^{\mathrm{C}}$) for
$\widetilde{A}^{\mathrm{B}}$ (resp. $\widetilde{A}^{\mathrm{C}}$).

Then if there is no leakage between the client and receiver’s devices during
$\mathsf{Enc}(1^{\lambda},M)$, or between Bob and Charlie’s devices after they
receive their decryption keys, the following bound holds:

$\Pr[(F=\text{\char
51\,})\land(\widetilde{A}^{\mathrm{B}}_{\mathcal{T}}=G^{\mathrm{B}}_{\mathcal{T}})\land(\widetilde{A}^{\mathrm{C}}_{\mathcal{T}}=G^{\mathrm{C}}_{\mathcal{T}})]\leq
2^{-\kappa\delta_{\gamma,\alpha}^{3}\alpha^{4}l},$

where $\kappa$ is the constant from Theorem 13, and the notation
$W_{\mathcal{T}}$ for any string $W$ denotes the substring of $W$ on the
instances in $\mathcal{T}$.

###### Proof.

We first briefly summarize the main processes involving the dishonest parties
in this modified cloning-attack scenario. The receiver begins with some share
of a quantum state in their devices, then gets the classical value $U$ from
the client and uses it to produce a value $S$ to send to the receiver (in step
9). Without any further communication from the client (since the register $C$
has been omitted), the receiver distributes states between Bob and Charlie.
Finally Bob and Charlie receive values $Y$ and $Z$ respectively (since the
values
$R\oplus\widetilde{A}^{\mathrm{B}},\mathtt{syn}(\widetilde{A}^{\mathrm{B}}),R\oplus\widetilde{A}^{\mathrm{C}},\mathtt{syn}(\widetilde{A}^{\mathrm{C}})$
have been omitted from their decryption keys), and measure their states to
produce their guesses $G^{\mathrm{B}},G^{\mathrm{C}}$. Our proof proceeds by
comparing this situation to the game $\mathrm{CLONE}_{\gamma,\alpha}^{t/l}$
(with $t$ arbitrary for now; we shall fix a suitable value at the end).

We observe that in terms of the input distribution (and the order in which
they are supplied relative to the state distribution step), the distribution
of $X,U,Y,Z$ in this scenario is exactly the same as in
$\mathrm{CLONE}_{\gamma,\alpha}^{t/l}$. Furthermore, the client’s output
string $A$ produced during the protocol is produced the same way as Alice’s
output in $\mathrm{CLONE}_{\gamma,\alpha}^{t/l}$, the receiver’s output string
$S$ is produced the same way as Barlie’s first-round output in
$\mathrm{CLONE}_{\gamma,\alpha}^{t/l}$, and Bob and Charlie’s guesses
$G^{\mathrm{B}},G^{\mathrm{C}}$ are produced the same way as their second-
round outputs in $\mathrm{CLONE}_{\gamma,\alpha}^{t/l}$. Hence we shall treat
these values as their outputs in the game
$\mathrm{CLONE}_{\gamma,\alpha}^{t/l}$.

Our goal is to bound the probability of the event $(F=\text{\char
51\,})\land(\widetilde{A}^{\mathrm{B}}_{\mathcal{T}}=G^{\mathrm{B}}_{\mathcal{T}})\land(\widetilde{A}^{\mathrm{C}}_{\mathcal{T}}=G^{\mathrm{C}}_{\mathcal{T}})$.
We shall first argue that this event implies that the game
$\mathrm{CLONE}_{\gamma,\alpha}^{t/l}$ is won on all instances $i\in[l]$ where
$U_{i}=\mathrm{keep}$. To do so, consider any such instance $i$, and observe
that if $i\notin\mathcal{T}$ (i.e. at least one of $Y_{i},Z_{i}$ is $\bot$),
then $\mathrm{CLONE}_{\gamma,\alpha}^{t/l}$ is automatically won on that
instance, recalling the win conditions (3). On the other hand, if
$i\in\mathcal{T}$, then the event $(F=\text{\char
51\,})\land(\widetilde{A}^{\mathrm{B}}_{\mathcal{T}}=G^{\mathrm{B}}_{\mathcal{T}})\land(\widetilde{A}^{\mathrm{C}}_{\mathcal{T}}=G^{\mathrm{C}}_{\mathcal{T}})$
implies that we have
$(\widetilde{A}^{\mathrm{B}}_{i}=G^{\mathrm{B}}_{i})\land(\widetilde{A}^{\mathrm{C}}_{i}=G^{\mathrm{C}}_{i})$.
Furthermore, since $i\in\mathcal{T}$ we have that
$\widetilde{A}^{\mathrm{B}}_{i}$ and $\widetilde{A}^{\mathrm{C}}_{i}$ are
equal to $A_{i}$ (recalling how they were constructed in step 23 of the
protocol). So we see that
$\widetilde{A}_{i}=G^{\mathrm{B}}_{i}=G^{\mathrm{C}}_{i}$, i.e. the win
condition of $\mathrm{CLONE}_{\gamma,\alpha}^{t/l}$ is indeed fulfilled on all
such instances as well.

Hence the only instances on which the win condition of
$\mathrm{CLONE}_{\gamma,\alpha}^{t/l}$ might not be fulfilled are those in
which $U_{i}\neq\mathrm{keep}$. Again referring back to the win conditions
(3), we see that such instances fail the win condition if and only if
$A_{i}\oplus S_{i}\neq X_{i}\cdot U_{i}$. But recalling the definition of the
“testing” step 10 in the protocol, we see that $F=\text{\char 51\,}$ is the
statement that the number of such instances is at most
$(\gamma(1-\omega^{*}(\mathrm{CHSH}))+{\delta_{\gamma,\alpha}}/{2})l$. Thus
overall, we conclude that the event $(F=\text{\char
51\,})\land(\widetilde{A}^{\mathrm{B}}_{\mathcal{T}}=G^{\mathrm{B}}_{\mathcal{T}})\land(\widetilde{A}^{\mathrm{C}}_{\mathcal{T}}=G^{\mathrm{C}}_{\mathcal{T}})$
implies the number of instances satisfying the win condition is at least

$l-\left(\gamma(1-\omega^{*}(\mathrm{CHSH}))+\frac{\delta_{\gamma,\alpha}}{2}\right)l=\left((1-\gamma)+\gamma\omega^{*}(\mathrm{CHSH})-\frac{\delta_{\gamma,\alpha}}{2}\right)l.$

Therefore, the probability of $(F=\text{\char
51\,})\land(\widetilde{A}^{\mathrm{B}}_{\mathcal{T}}=G^{\mathrm{B}}_{\mathcal{T}})\land(\widetilde{A}^{\mathrm{C}}_{\mathcal{T}}=G^{\mathrm{C}}_{\mathcal{T}})$
is at most the probability of having at least
$t=\left((1-\gamma)+\gamma\omega^{*}(\mathrm{CHSH})-{\delta_{\gamma,\alpha}}/{2}\right)l$
win instances in $\mathrm{CLONE}_{\gamma,\alpha}^{t/l}$. By Theorem 13, the
latter probability is upper bounded by
$2^{-\kappa\delta_{\gamma,\alpha}^{3}\alpha^{4}l}$, which gives the desired
result. ∎

With this, we now prove a bound on the probability Bob and Charlie can both
guess the values $\widetilde{A}^{\mathrm{B}},\widetilde{A}^{\mathrm{C}}$
described above, but using all the registers involved in an actual cloning
attack. Informally, the idea is that to compensate for the syndromes
$\mathtt{syn}(\widetilde{A}^{\mathrm{B}}),\mathtt{syn}(\widetilde{A}^{\mathrm{C}})$
we simply multiply the guessing probability by a factor corresponding to the
lengths of the syndromes, whereas for the registers
$C,R\oplus\widetilde{A}^{\mathrm{B}},R\oplus\widetilde{A}^{\mathrm{C}}$ we
shall argue that they are mostly “decoupled” from
$\widetilde{A}^{\mathrm{B}}\widetilde{A}^{\mathrm{C}}$ and hence have limited
effects on the optimal guessing probability.

######  Lemma 20.

We follow the notation as defined in Lemma 19. Consider a cloning attack with
the modification that instead of Bob (resp. Charlie) producing a guess for the
message $M$, he produces a guess $G^{\mathrm{B}}$ (resp. $G^{\mathrm{C}}$) for
$\widetilde{A}^{\mathrm{B}}$ (resp. $\widetilde{A}^{\mathrm{C}}$). Then if
there is no leakage between the client and receiver’s devices during
$\mathsf{Enc}(1^{\lambda},M)$, or between Bob and Charlie’s devices after they
receive their decryption keys, the following bound holds:

$\Pr[(F=\text{\char
51\,})\land(\widetilde{A}^{\mathrm{B}}=G^{\mathrm{B}})\land(\widetilde{A}^{\mathrm{C}}=G^{\mathrm{C}})]\leq
2^{-\kappa\delta_{\gamma,\alpha}^{3}\alpha^{4}l+2\ell_{\mathtt{syn}}},$ (9)

where $\kappa$ is the constant from Theorem 13, and $\ell_{\mathtt{syn}}$
given by (8).

###### Proof.

The difference between this scenario as compared to that described in Lemma 19
is that here, the dishonest parties have access to more registers:
specifically, the receiver is given the register $C$ in the ciphertext, and
Bob (resp. Charlie) is given
$R\oplus\widetilde{A}^{\mathrm{B}},\mathtt{syn}(\widetilde{A}^{\mathrm{B}})$
(resp.
$R\oplus\widetilde{A}^{\mathrm{C}},\mathtt{syn}(\widetilde{A}^{\mathrm{C}})$)
in his decryption key. For brevity, let $D^{\mathrm{B}}$ and $H^{\mathrm{B}}$
denote the values $R\oplus\widetilde{A}^{\mathrm{B}}$ and
$\mathtt{syn}(\widetilde{A}^{\mathrm{B}})$ for Bob, and define
$D^{\mathrm{C}}$ and $H^{\mathrm{C}}$ analogously for Charlie. To prove the
claimed bound (9) in this scenario, we shall analyze a sequence of modified
scenarios in which we progressively remove these registers from consideration,
finally arriving at the scenario in Lemma 19. (Note that the probability we
are bounding in this lemma is also slightly different from that in Lemma 19,
because it involves the full strings
$\widetilde{A}^{\mathrm{B}},G^{\mathrm{B}},\widetilde{A}^{\mathrm{C}},G^{\mathrm{C}}$
rather than just the substrings on $\mathcal{T}$. We return to this point
later in this proof.)

To facilitate this analysis, we introduce the following notation. For any
subset $Q$ of the registers mentioned above (i.e.
$Q\subseteq\\{C,D^{\mathrm{B}},D^{\mathrm{C}},H^{\mathrm{B}},H^{\mathrm{C}}\\}$),
let $\mathcal{C}_{Q}$ denote the set of all “modified cloning attacks” in the
sense described in the Lemma 19 statement (i.e. at the end Bob and Charlie
produce guesses for $\widetilde{A}^{\mathrm{B}}$ and
$\widetilde{A}^{\mathrm{C}}$), except that the dishonest parties additionally
have access to the registers $Q$ (with the implicit understanding that these
registers become available to the dishonest parties at the same points as in a
standard cloning attack). In terms of this notation, Lemma 19 is considering
all attacks in the set $\mathcal{C}_{\emptyset}$ ($\emptyset$ denotes the
empty set), while this lemma statement we aim to prove here is simply the
statement that

$\max_{\mathcal{C}_{CD^{\mathrm{B}}D^{\mathrm{C}}H^{\mathrm{B}}H^{\mathrm{C}}}}\Pr[\mathcal{E}_{\mathrm{succ}}]\leq
2^{-\kappa\delta_{\gamma,\alpha}^{3}\alpha^{4}l+2\ell_{\mathtt{syn}}},\quad\text{where
}\mathcal{E}_{\mathrm{succ}}=(F=\text{\char
51\,})\land(\widetilde{A}^{\mathrm{B}}=G^{\mathrm{B}})\land(\widetilde{A}^{\mathrm{C}}=G^{\mathrm{C}}).$
(10)

As the first step, we argue that Bob and Charlie having access to the
registers $H^{\mathrm{B}}H^{\mathrm{C}}$ could only have increased the
attack’s maximum success probability by at most a factor of
$2^{2\ell_{\mathtt{syn}}}$, i.e. in terms of the above notation we have

$\max_{\mathcal{C}_{CD^{\mathrm{B}}D^{\mathrm{C}}H^{\mathrm{B}}H^{\mathrm{C}}}}\Pr[\mathcal{E}_{\mathrm{succ}}]\leq
2^{2\ell_{\mathtt{syn}}}\max_{\mathcal{C}_{CD^{\mathrm{B}}D^{\mathrm{C}}}}\Pr[\mathcal{E}_{\mathrm{succ}}].$

This follows from a standard guessing-strategy argument: given any attack in
which Bob and Charlie use $H^{\mathrm{B}}H^{\mathrm{C}}$ to achieve
$\Pr[\mathcal{E}_{\mathrm{succ}}]=p$ for some $p\in[0,1]$, there is always
another attack in which Bob and Charlie achieve
$\Pr[\mathcal{E}_{\mathrm{succ}}]\geq 2^{-2\ell_{\mathtt{syn}}}p$ _without_
access to $H^{\mathrm{B}}H^{\mathrm{C}}$, as follows: Bob and Charlie
independently produce uniformly random guesses for $H^{\mathrm{B}}$ and
$H^{\mathrm{C}}$ respectively, then proceed with the original strategy as
though these guesses were the true values of $H^{\mathrm{B}}H^{\mathrm{C}}$.
Note that the probability of these guesses being (both) equal to the true
syndrome values is always exactly $2^{-2\ell_{\mathtt{syn}}}$, hence the
described attack succeeds with probability at least
$2^{-2\ell_{\mathtt{syn}}}p$, as claimed.

With this bound we can remove the registers $H^{\mathrm{B}}H^{\mathrm{C}}$
from consideration, in the sense that to prove (10), it would suffice to show
that

$\max_{\mathcal{C}_{CD^{\mathrm{B}}D^{\mathrm{C}}}}\Pr[\mathcal{E}_{\mathrm{succ}}]\leq
2^{-\kappa\delta_{\gamma,\alpha}^{3}\alpha^{4}l}.$ (11)

To do so, we now proceed to remove the register $C$ as well, by arguing that

$\max_{\mathcal{C}_{CD^{\mathrm{B}}D^{\mathrm{C}}}}\Pr[\mathcal{E}_{\mathrm{succ}}]=\max_{\mathcal{C}_{D^{\mathrm{B}}D^{\mathrm{C}}}}\Pr[\mathcal{E}_{\mathrm{succ}}].$

This follows by observing that in the definition of a cloning attack (or
modified cloning attack, in this context), the message $M$ is chosen uniformly
at random and independently of everything else. This means we can effectively
view it as playing the role of a one-time-pad in the process of generating $C$
— note that this is “reversed” from our earlier Theorem 18 proof, in that here
we shall view $M$ rather than $R$ as the one-time-pad. To put this rigorously:
before step 13, in this context $M$ is a uniformly random value that was
generated independently of everything else. Furthermore, for the event
$\mathcal{E}_{\mathrm{succ}}$ that we are considering, the only role played by
the message $M$ is in generating the value $C=M\oplus R$ in step 13 (focusing
on the $F=\text{\char 51\,}$ case, since otherwise $C$ is really just a “dummy
value” $M^{\prime}$ independent of everything else), and hence we can just
trace out $M$ immediately after that step. With this, we apply Fact 17
(identifying $R,M$ with $C_{1},C_{2}$ respectively — again, we stress that the
roles are “reversed” from our Theorem 18 proof) to conclude that the state
produced after step 13 is _exactly_ the same as though $C$ was generated as a
uniformly random value independent of everything else. Since a dishonest
receiver could generate such a $C$ on their own anyway, we can absorb it into
the actions of a dishonest receiver when considering the set of attacks
$\mathcal{C}_{D^{\mathrm{B}}D^{\mathrm{C}}}$, and conclude that the maximum
value of $\Pr[\mathcal{E}_{\mathrm{succ}}]$ over attacks in the set
$\mathcal{C}_{CD^{\mathrm{B}}D^{\mathrm{C}}}$ is the same as over the set
$\mathcal{C}_{D^{\mathrm{B}}D^{\mathrm{C}}}$.

The last step is to remove the registers $D^{\mathrm{B}}D^{\mathrm{C}}$ and
connect $\mathcal{E}_{\mathrm{succ}}$ to the event considered in Lemma 19. We
start by observing that whenever Bob and Charlie have access to
$D^{\mathrm{B}}=R\oplus\widetilde{A}^{\mathrm{B}}$ and
$D^{\mathrm{C}}=R\oplus\widetilde{A}^{\mathrm{C}}$, they can simultaneously
guess (respectively) $\widetilde{A}^{\mathrm{B}}$ and
$\widetilde{A}^{\mathrm{C}}$ correctly _if and only if_ they can
simultaneously guess $R$ — this follows by observing that if e.g. Bob guesses
$R$ correctly, he can get $\widetilde{A}^{\mathrm{B}}$ by computing $R\oplus
D^{\mathrm{B}}$; conversely if he guesses $\widetilde{A}^{\mathrm{B}}$
correctly he can get $R$ from $\widetilde{A}^{\mathrm{B}}\oplus
D^{\mathrm{B}}$ (the analysis for Charlie is analogous). To discuss this more
easily, let $\widehat{\mathcal{C}}_{Q}$ denote the set of all modified cloning
attacks in a similar fashion to $\mathcal{C}_{Q}$, except with one further
modification that rather than having Bob (resp. Charlie) produce a guess
$G^{\mathrm{B}}$ (resp. $G^{\mathrm{C}}$) for $\widetilde{A}^{\mathrm{B}}$
(resp. $\widetilde{A}^{\mathrm{C}}$), he is to produce a guess