# Uncloneable Cryptographic Primitives
with Interaction

Anne Broadbent  University of Ottawa, Department of Mathematics and Statistics
<EMAIL_ADDRESS>Eric Culf  University of Waterloo, Institute for
Quantum Computing and Faculty of Mathematics<EMAIL_ADDRESS>
###### Abstract

Much of the strength of quantum cryptography may be attributed to the no-
cloning property of quantum information. We construct three new cryptographic
primitives whose security is based on uncloneability, and that have in common
that their security can be established via a novel monogamy-of-entanglement
(MoE) property:

  * •

We define _interactive uncloneable encryption_ , a version of the uncloneable
encryption defined by Broadbent and Lord [TQC 2020] where the receiver must
partake in an interaction with the sender in order to decrypt the ciphertext.
We provide a one-round construction that is secure in the information-
theoretic setting, in the sense that no other receiver may learn the message
even if she eavesdrops on all the interactions.

  * •

We provide a way to make a bit string commitment scheme uncloneable. The
scheme is augmented with a check step chronologically in between the commit
and open steps, where an honest sender verifies that the commitment may not be
opened by an eavesdropper, even if the receiver is malicious. Our construction
preserves the assumptions of the original commitment while requiring only a
polynomial decrease in the length of the committed string.

  * •

We construct a _receiver-independent quantum key distribution_ (QKD) scheme,
which strengthens the notion of one-sided device independent QKD of
Tomamichel, Fehr, Kaniewski, and Wehner (TFKW) [NJP 2013] by also permitting
the receiver’s classical device to be untrusted. Explicitly, the sender
remains fully trusted while only the receiver’s communication is trusted. We
provide a construction that achieves the same asymptotic error tolerance as
the scheme of TFKW.

To show security, we prove an extension of the MoE property of coset states
introduced by Coladangelo, Liu, Liu, and Zhandry [Crypto 2021]. In our
stronger version, the player Charlie also receives Bob’s answer prior to
making his guess, thus simulating a party who eavesdrops on an interaction. To
make use of this property, we express it as a new type of entropic uncertainty
relation which arises naturally from the structure of the underlying MoE game.

###### Contents

  1. 1 Introduction
    1. 1.1 Uncloneable encryption with interactive decryption
    2. 1.2 Uncloneable bit commitment
    3. 1.3 Receiver-independent QKD
    4. 1.4 Main technique: MoE entropic uncertainty relations
    5. 1.5 Further related work
    6. 1.6 Acknowledgements
    7. 1.7 Outline
  2. 2 Preliminaries
    1. 2.1 Registers and states
    2. 2.2 Finite vector spaces and subspace coset states
    3. 2.3 Entropy and extractors
  3. 3 Novel Coset State Monogamy-of-Entanglement Property
    1. 3.1 Weak and strong MoE properties
    2. 3.2 The leaky MoE property
    3. 3.3 A new type of entropic uncertainty relation
  4. 4 Interactive Uncloneable Encryption
    1. 4.1 QECMs with interactive decryption and their security
    2. 4.2 General properties
    3. 4.3 Instantiation and security proofs
  5. 5 Uncloneable Bit Commitment
    1. 5.1 Motivation and definitions
    2. 5.2 Security proofs
  6. 6 Receiver-Independent Quantum Key Distribution
    1. 6.1 Robust leaky MoE property
    2. 6.2 Motivation and construction
    3. 6.3 QKD security

##  1 Introduction

An important feature of quantum information is the no-cloning principle — the
property that an arbitrary quantum state cannot be perfectly copied, unlike a
classical string [Par70, WZ82, Die82]. This idea underpins many of the unique
constructions in quantum cryptography [BS16], beginning with quantum money
[Wie83] and quantum key distribution (QKD) [BB84]. In this work, we give three
new constructions of cryptographic primitives that, at the intuitive level,
make use of uncloneability: _uncloneable encryption with interactive
decryption_ , _uncloneable bit commitment_ , and _receiver-independent QKD_.
An important consequence of the uncloneability is that none of these
primitives can be secure classically — in fact, as classical information can
always be copied, the security is clearly unachievable.

In order to prove security of these primitives and formally reason about their
“uncloneability,” we show a strengthened form of the subspace coset state
monogamy-of-entanglement (MoE) property [CLLZ21, CV22], which is a bound on
the winning probability of an MoE game built using subspace coset states. MoE
games are used to quantify the strength of quantum tripartite correlations.
They belong to the family of _extended nonlocal games_ [JMRW16], which
generalise nonlocal games, but are highly distinct from them. The MoE game
paradigm, introduced in [TFKW13], has recently been used in various
uncloneability-related cryptographic constructions [BL20, BC23, CLLZ21]. An
MoE game is played between two cooperating players, Bob and Charlie, and an
honest referee, Alice, all of whom may hold a quantum system. The subspace
coset MoE game (called the strong monogamy game in [CLLZ21]), proceeds as
follows. First, Alice samples a subspace $a$ of dimension $n/2$ of the space
of $n$-bit strings $\mathbb{Z}_{2}^{n}$, and strings $t,t^{\prime}$ uniformly
at random, and prepares the coset state333We use lowercase rather than
uppercase letters for subspaces as we aim to reserve the uppercase letters for
registers and random variables.

$\displaystyle\lvert a_{t,t^{\prime}}\rangle=\frac{1}{\sqrt{|a|}}\sum_{u\in
a}(-1)^{u\cdot t^{\prime}}\lvert t+u\rangle.$ (1)

She sends this state to Bob and Charlie, who may do arbitrary actions to
split444Note that the splitting operation is represented by an arbitrary
quantum channel, chosen by Bob and Charlie. It is not necessarily something
simple like a bipartition of the qubits. the state between their two systems,
after which they are isolated. Next, Alice provides them with a description of
$a$. In order to win, Bob must provide a vector from the coset $t+a$ and
Charlie must provide one from $t^{\prime}+a^{\perp}$, where $a^{\perp}$ is the
orthogonal complement of $a$. This game was shown in [CV22] to have an
exponentially small winning probability in $n$. We strengthen the relation by
showing that the same bound holds on a version of the game that is easier to
win — Bob’s answer, whether or not it is correct, leaks to Charlie before he
makes his guess. In this way, we are able to see the information that Charlie
gets as messages sent during an interaction between Alice and Bob, on which he
eavesdrops. We refer to this bound on the winning probability as the _leaky_
monogamy-of-entanglement property.

###  1.1 Uncloneable encryption with interactive decryption

We introduce, study, and construct a variant of uncloneable encryption that
allows for an interaction during the decryption process. Uncloneable
encryption as is currently understood was introduced in [BL20], building on
earlier concepts such as the tamper-evident encryption of [Got03] and the MoE
games of [TFKW13]. In its most general form, an uncloneable encryption scheme
provides a way to encrypt messages in such a way that they cannot be
simultaneously read by two malicious parties, Bob and Charlie, under the
assumption that they are isolated once the encryption key is released. To the
best of our knowledge, it is unknown whether this is achievable in the plain
model, even if we allow computational assumptions. Uncloneable encryption
schemes in the quantum random oracle model (QROM) have been studied [BL20] and
provide nearly optimal security. Other computational assumptions have been
considered: under the assumption of post-quantum one-way functions, [AK21]
show that it is possible to turn an uncloneable encryption scheme into one
with semantic security; and under the assumption of a post-quantum public key
encryption scheme, they show how to turn the scheme into a public-key
uncloneable encryption scheme. Since all these rely on the existence of
uncloneable encryption, a key open question remains concerning the existence
of an “uncloneable bit” — an optimal uncloneable encryption scheme in the
plain model that encrypts one-bit message. This is a fundamental object as any
uncloneable encryption scheme implies an uncloneable bit [BL20, Theorem 9]. We
work with a simple communication assumption rather than a computational
assumption in order to instantiate a new form of uncloneable encryption.

Originally, the encryption was represented by a quantum encryption of
classical messages (QECM), a protocol that encrypts classical messages as
quantum ciphertexts, which can be decrypted using only the classical
encryption key [BL20]. A QECM scheme is uncloneable if two receivers receive a
ciphertext, split it arbitrarily, and only get the key once they are isolated,
then they can simultaneously learn the message with at best near-trivial
probability. We extend the original non-interactive setting of [BL20] by
allowing interaction in the decryption phase. We call this model _quantum
encryption of classical messages with interactive decryption_ (QECM-ID). To
adapt uncloneability to a QECM-ID scheme, we again have two receivers, whom we
call Bob and Eve, who split a ciphertext. To decrypt, Bob initiates an
interaction with Alice. Only after this point does Bob need to be seen as the
intended recipient of the message. To avoid the trivial attack where Bob
simply gives the decrypted message to Eve, they may not communicate directly
during the interaction step — nevertheless, Eve may eavesdrop on the
communication between Alice and Bob. We therefore say that the encryption is
uncloneable if, for any actions Bob and Eve take, the probability that Eve
guesses the message correctly once the interaction finishes and the decryption
protocol does not abort is near-trivial.

We also adapt uncloneable-indistinguishable security, which is meant to
represent an uncloneability version of chosen-plaintext attack (CPA) security.
For a QECM, this is the property that Bob and Eve cannot simultaneously
distinguish the encryption of a chosen message distribution from a fixed
message [BL20]. To adapt this to a QECM-ID, we say that it is uncloneable-
indistinguishable secure if, after the decryption interaction, the probability
that, simultaneously, Alice accepts the decryption and Eve distinguishes a
chosen message distribution from a fixed message is near trivial, _i.e._ half
the probability of accepting. Intuitively, the condition that Bob guesses
correctly is replaced with the condition that Alice accepts the decryption in
order to adapt the definition to a QECM-ID.

Finally, we show that there is an equivalence between uncloneable and
uncloneable-indistinguishable security for QECM-IDs. This extends the result,
shown in [BL20], that uncloneable security implies uncloneable-
indistinguishable security for QECMs. Further, the equivalence generalises an
important property of classical encryption. To the best of our knowledge, it
is unknown whether both implications hold for QECMs.

#### Proof technique.

To instantiate an uncloneable QECM-ID, we make use of the leaky MoE property.
Alice, to encrypt her message $m$, uses as a key a subspace $a$, strings $h$
and $t,t^{\prime}$, and a key $r$ for a quantum-proof strong extractor $e$ .
She sends the pair $(m+e(t^{\prime},r)+h,\lvert a_{t,t^{\prime}}\rangle)$ as
the ciphertext. The MoE property implies that, if Bob is able to provide $t$
to Alice, then with high probability Eve is unable to guess $t^{\prime}$
correctly, even if she learns $t$. Hence, Alice can use the interaction to
check whether Bob knows $t$. If this succeeds, then $t^{\prime}$ is secure
against Eve with high probability, so Alice sends remainder of the key $(r,h)$
to Bob. With this, our construction satisfies both forms of uncloneable
security, with tighter bounds that the equivalence between the properties
implies.

###  1.2 Uncloneable bit commitment

In bit string commitment, a sender Alice commits to a string that a receiver
Bob can only access when she chooses. Ideally, the commitment should be
_hiding_ , in the sense that Bob cannot learn the string Alice has committed
until she chooses to reveal, and _binding_ , in the sense that Alice must
reveal the same string to which she had committed. Without additional
assumptions, bit commitment is impossible [May96, LC97, BS16], but there are a
variety of models in which it was shown to exist. For example, under classical
computational assumptions [Cha87, Nao91] (see also [Cré11]) or in the noisy
quantum storage model [KWW12]. However, a problem underlying many classically-
defined cryptographic primitives is that they are inherently cloneable; if an
eavesdropper Eve is able to eavesdrop on the communications between Alice and
Bob, she may be able to produce a transcript of their interactions and hence
learn the final string whenever it is revealed. This is the case for bit
commitment: in fact, the reveal step is usually represented as a public
broadcast with no indication of security against an eavesdropper. We remedy
this with a method to make a bit string commitment scheme uncloneable.

We define an _uncloneable bit string commitment scheme_ as a commitment scheme
with an additional check step in between the commit and reveal steps, where
Alice verifies whether an eavesdropper has attempted to clone the commitment.
If the commitment passes this check, then an honest Alice can be sure that
only Bob will be able to open it during the reveal phase, despite a lack of
prior agreement between them. Bob may even be malicious: the only restriction
needed on him is that he does not communicate directly to Eve after the check.
With this in mind, the point in time when Alice chooses to undertake the check
allows it to be run under varying assumptions. In particular, Alice may check
immediately after committing, which means that no honest party needs to store
any quantum information, but Alice needs to be sure that Bob does not
communicate privately with Eve at any point after committing. This is more
feasible for near-term quantum devices, but requires that Bob not communicate
information to Eve for a period of time between steps. On the other hand, if
Alice waits until immediately before revealing to do the check, she may assume
that Bob and Eve have arbitrary communication after committing. The drawback
is that Bob must store a quantum state even if he is honest.

#### Proof technique.

We use the leaky MoE property to provide a way to turn a commitment scheme
into an uncloneable commitment of the above form, which works under the same
assumptions as the original commitment. We assume that this is a randomised
commitment scheme, where Alice commits to a uniformly random string; this form
of commitment is equivalent to the standard one where Alice chooses the string
to commit [KWW12]. In order to commit to the random string
$e(t^{\prime},r)+h$, where $e$ is a quantum-proof strong extractor, Alice
commits to $(r,h)$ using the original commitment and sends a coset state
$\lvert a_{t,t^{\prime}}\rangle$ to Bob. Because Bob does not know $a$, he has
no information about $t^{\prime}$ and $(r,h)$ has not been revealed, so the
commitment is hiding. Next, to check for cloning, Alice sends $a$ to Bob and
verifies that he can measure $t$. Due to the leaky MoE property, this implies
that Eve is only able to guess $t^{\prime}$ with low probability. Finally, to
reveal, Alice reveals $(r,h)$ and Bob queries Alice for some information about
$t^{\prime}$ to make sure that their values are consistent, making the scheme
binding. With a good choice of strong extractor, this causes only a polynomial
decrease in the length of the committed string and an exponentially small
change in the binding parameter.

###  1.3 Receiver-independent QKD

Quantum key distribution (QKD), introduced by Bennett and Brassard [BB84], is
a foundationally important quantum cryptographic primitive. In its most basic
form, it allows an honest sender, Alice, to share a secret key with an honest
receiver, Bob, over a public channel without an eavesdropper Eve learning the
key. Many variants of QKD that require only weaker assumptions on the honest
parties have been proposed. In particular, device-independent protocols,
initiated by Ekert [Eke91], seek to allow QKD with few, if any, assumptions on
the behaviour of Alice and Bob’s devices. One-sided device-independent QKD,
shown to be secure against any eavesdropper in [TFKW13], allows Bob’s quantum
device to be fully untrusted, relying on a monogamy-of-entanglement game
winning probability bound for security; and fully device-independent QKD,
shown by Vazirani and Vidick [VV14], allows both Alice and Bob’s quantum
devices to be untrusted, with security coming from the rigidity of a nonlocal
game. These varying assumptions allow implementations of QKD to balance
practicality and security, depending on available resources.

We show security of QKD in a model extending the one-sided device-independent
model, which we call _receiver-independent QKD_. In this model, Alice’s
quantum device remains fully trusted, but neither Bob’s quantum nor his
_classical_ device is trusted. However, we require that Bob’s communication be
trusted: if Bob’s communication were not trusted, any QKD scheme would be
susceptible to the trivial attack where Bob sends his final key to Eve. In
this way, this model can be seen as the minimal assumption on the receiver,
hence warranting the name “receiver-independent”.

Receiver-independent QKD schemes are distinct in a number of ways. First,
since any computation Bob might want to make is inherently untrusted, he
cannot be trusted to check any property of the shared state. As such, only
Alice may be given the power to abort the protocol. In this way, the
interactions between Alice and Bob take the form of a sequence of challenges
and responses. Also, the idea of correctness must be altered to account for
the fact that Bob’s classical computations are untrusted. This is because it
is not possible to be certain that Bob has access to the final key, but it is
possible to be sure that his device can compute it.

#### Proof technique.

We construct a receiver-independent QKD scheme using coset states, and show
its security using an error-robust generalisation of the leaky MoE property.
Alice sends a coset state $\lvert a_{t,t^{\prime}}\rangle$ to Bob. To verify
that Eve does not have $t^{\prime}$, Alice asks Bob to provide $t$, acting as
the parameter estimation step. If he is able to, with only small error, then
Alice issues challenges to Bob that allow her to correct her $t^{\prime}$ to
match the guess $\hat{t}^{\prime}$ Bob’s device claims to have, and then
verify this match, which act as the error correction and information
reconciliation steps, respectively. Finally, for privacy amplification, Alice
acts on her corrected raw key with a quantum-proof strong extractor and
instructs Bob to do the same. It is worth noting that our use of an entropic
uncertainty relation, as introduced in Section 1.4 below, brings the security
proof intuitively closer to earlier proofs of QKD security, as in [Ren05],
than the proof of [TFKW13], which works more directly with an MoE game.

###  1.4 Main technique: MoE entropic uncertainty relations

Entropic uncertainty relations, and earlier uncertainty relations beginning
with [Hei27], have played a foundational role in quantum information [WW10].
Tomamichel, Fehr, Kaniewski, and Wehner show an entropic uncertainty relation
in the same scenario as their MoE game [TFKW13]. We provide an entropic
uncertainty relation that arises naturally from the scenario of the leaky
subspace coset MoE game, allowing us to work with the full strength of the MoE
property in an entropy setting.

To show our relation, we generalise the min-entropy of guessing
$H_{\min}(X|A)_{\rho}$ to a novel property that we refer to as the _sequential
min-entropy_ , $H_{\min}(X|A;Y|B)_{\rho}$, which represents the uncertainty of
guessing $X$ knowing $A$, followed by guessing $Y$ knowing $B$, on the same
state. For any measurement $M$ on $A$ used to guess $X$, this decomposes as
the entropic uncertainty relation

$\displaystyle H_{\min}(X|M(A))_{\rho}+H_{\min}(Y|B)_{\rho_{|(M(A)=X)}}\geq
H_{\min}(X|A;Y|B)_{\rho},$ (2)

where $\rho_{|(M(A)=X)}$ is the state conditioned on the guess of $X$ being
correct. A notable distinction between such an entropic uncertainty and a more
standard relation is that the states on the two terms are different, although
closely related. The winning probability of the leaky MoE game can directly be
expressed using a sequential entropy as $\exp\left\lparen-
H_{\min}(T|AB,T^{\prime}|A^{\prime}TC)_{\rho}\right\rparen$, where
$\rho_{AA^{\prime}TT^{\prime}BC}$ is the state such that $A$ and $A^{\prime}$
hold two copies of the subspace $a$, $T$ and $T^{\prime}$ hold the coset
representatives $t,t^{\prime}$, and $B$ and $C$ hold Bob and Charlie’s quantum
systems once they are isolated. Hence, the leaky MoE property provides the
entropic uncertainty relation

$\displaystyle
H_{\min}(T|M(AB))_{\rho}+H_{\min}(T^{\prime}|A^{\prime}TC)_{\rho_{|(M(AB)=T)}}\in\Omega(n).$
(3)

This may be compared to the MoE game-based entropic uncertainty relation that
was studied in [TFKW13], $H_{\min}(X|\Theta B)_{\rho}+H_{\min}(X|\Theta
C)_{\rho}\geq-2\lg\left[(1+2^{-n/2})/2\right]\in O(1)$, where $\rho_{ABC}$ is
any quantum state with $A=\mathbb{Z}_{2}^{n}$, $X$ is the result of measuring
$A$ in a uniformly random Wiesner basis of states $\lvert
x^{\theta}\rangle=H^{\theta_{1}}\lvert x_{1}\rangle\otimes\cdots
H^{\theta_{n}}\lvert x_{n}\rangle$, and $\Theta$ is the description of the
basis. The relation is found in the same way as their bound on the winning
probability of their MoE game, but is strictly weaker than that bound, since
it only considers entropies with respect to the same state. This makes it too
weak to provide security of cryptographic primitives such as QKD. In fact,
even in the case of the subspace coset MoE game, we similarly have

$\displaystyle
H_{\min}(T|M(AB))_{\rho}+H_{\min}(T^{\prime}|A^{\prime}TC)_{\rho}\in O(1),$
(4)

using the same simple attack: half the time, Bob takes the whole state, and
the other half of the time, Charlie takes the whole state.

In order to extend the use of the leaky MoE property and associated entropic
uncertainty relation to scenarios where errors should be accounted for, such
as QKD, we adapt the MoE game to allow for errors. That is, we show a bound on
the winning probability of a robust generalisation of the leaky MoE game where
Bob and Charlie’s answers are considered to be correct even if some small
number of bits are wrong. The important case for QKD is where Bob is allowed
to guess $t$ incorrectly up to relative error $\gamma$ but Charlie, who
represents the eavesdropper, must still answer perfectly. For small enough
error, the winning probability remains exponentially small in $n$. We can also
handle this probability of approximate guessing as an entropic uncertainty
relation, by representing the “entropy of approximate guessing” as an entropy
of exact guessing on a modified state. Explicitly, the relation takes the now-
familiar form

$\displaystyle
H_{\min}(T|M(AB))_{\sigma}+H_{\min}(T^{\prime}|A^{\prime}TC)_{\sigma_{|(M(AB)=T)}}\in\Omega(n),$
(5)

where $\sigma$ is the state modified to account for the error bit flips
$\sigma=\operatorname*{\mathchoice{\raisebox{-10.00012pt}{\leavevmode\resizebox{18.9231pt}{10.00012pt}{\hbox{\raisebox{0.0pt}{$\displaystyle\vphantom{\mathbb{E}}\text{\raisebox{0.3pt}{\scalebox{0.9}{$\mathbb{E}$}}}$}}}}}{\raisebox{-10.00012pt}{\leavevmode\resizebox{18.9231pt}{10.00012pt}{\hbox{\raisebox{0.0pt}{$\textstyle\vphantom{\mathbb{E}}\text{\raisebox{0.3pt}{\scalebox{0.9}{$\mathbb{E}$}}}$}}}}}{\raisebox{-7.00009pt}{\leavevmode\resizebox{13.24615pt}{7.00009pt}{\hbox{\raisebox{0.0pt}{$\scriptstyle\vphantom{\mathbb{E}}\text{\raisebox{0.3pt}{\scalebox{0.9}{$\mathbb{E}$}}}$}}}}}{\raisebox{-5.00006pt}{\leavevmode\resizebox{9.46153pt}{5.00006pt}{\hbox{\raisebox{0.0pt}{$\scriptscriptstyle\vphantom{\mathbb{E}}\text{\raisebox{0.3pt}{\scalebox{0.9}{$\mathbb{E}$}}}$}}}}}}_{|u|\leq\gamma
n/2}X_{T}^{u}\rho X_{T}^{u}$.

###  1.5 Further related work

The no-cloning property is found in a wide and growing range of cryptographic
applications, such as tamper-detection [Got03], copy-protection [Aar09,
CMP20], certified deletion [BI20], secure software leasing [ALP21, BJL+21],
and uncloneable decryption [CLLZ21].

The coset states we study act as a generalisation of subspace states — uniform
superpositions of the elements of a subspace — introduced in the context of
quantum money by Aaronson and Christiano [AC12]. Rather than using the
properties of subspaces, it is possible to see the generalisation to coset
states as subspace states encrypted with a quantum one time pad $\lvert
a_{t,t^{\prime}}\rangle=X^{t}Z^{t^{\prime}}\lvert a\rangle$. Coset states
under this definition have been studied in the context of proofs of knowledge
by Vidick and Zhang [VZ21].

Though inspired by uncloneable encryption of [BL20], uncloneable encryption
using a QECM-ID also bears comparison to tamper-evident encryption, introduced
by Gottesman [Got03] (under the name uncloneable encryption). This is a scheme
where an honest receiver can verify, during decryption, whether an
eavesdropper had attempted to clone an encrypted message. We emphasize that
[Got03] requires both an honest sender and receiver and that our techniques
are fundamentally different since they are resilient to a dishonest receiver.

Finally, the recent work of Kundu and Tan [KT22] provides an alternate
extension of the uncloneable encryption paradigm. They consider the case
where, for each encryption key, there are multiple decryption keys. They give
a construction of an encryption scheme that is uncloneable as long as the
attackers receive independently generated keys. Similarly to the interaction
in our model, an assumption on the communication during the decryption is used
to guarantee uncloneability. Also, their results consider noise on the
devices, similarly to what we are concerned with in the robust version of the
game used for receiver-independent QKD; arbitrary small leakage of information
between Bob and Charlie’s devices, contrasting with our fixed but large
leakage of Bob’s measurement result; and full device-independence, which
requires an interactive encryption

###  1.6 Acknowledgements

This work was supported by the Air Force Office of Scientific Research under
award number FA9550-20-1-0375, Canada’s NSERC, and the University of Ottawa’s
Research Chairs program.

###  1.7 Outline

In Section 2, we introduce our notation and the relevant basic technical
facts. In Section 3, we introduce and analyse the monogamy-of-entanglement
game we study, as well as the related entropic uncertainty relation. In
Sections 4, LABEL:, 5, LABEL: and 6 we define and study the primitives of
interactive uncloneable encryption, uncloneable bit commitment, and receiver-
independent QKD, respectively. In Section 6, we also study the robust version
of the MoE game. The MoE properties are given as Theorem 3.2 and Theorem 6.2,
and their expressions as entropic uncertainty relations as Corollary 3.7 and
Corollary 6.5.

##  2 Preliminaries

In this section, we introduce the notation and recall the technical facts we
use in this paper. In Section 2.1, we go over the basics of quantum
information and probability that we need; in Section 2.2, we discuss subspaces
of vector spaces of bit strings and recall the definition of subspace coset
states; and in Section 2.3, we note the definitions of conditional min-entropy
and strong extractors.

###  2.1 Registers and states

A _register_ is a set $X$ that represents the classical states of a physical
system. Note that we may have distinct registers with the same underlying set
of states. We represent registers by uppercase Latin letters and classical
states from the register by the corresponding lowercase letter. For registers
$X_{1}$ and $X_{2}$, write the _compound register_ $X_{1}X_{2}=X_{1}\times
X_{2}$, representing the states of both systems. A register $Y$ is a
_subregister_ of $X$ if $X$ is a compound register with $Y$ as a factor. For a
register $X$, define the Hilbert space $\mathcal{H}_{X}$ as the
$|X|$-dimensional space spanned by the orthonormal basis $\vphantom{\lvert
x\rangle x\in X}\left\\{{\lvert x\rangle}\mid{x\in X}\right\\}$ called the
_register basis_. The pure quantum states on $X$ are given by the unit vectors
of $\mathcal{H}_{X}$, up to phase. We implicitly make use of the isomorphism
$\mathcal{H}_{XY}\cong\mathcal{H}_{X}\otimes\mathcal{H}_{Y}$.

We write the set of _linear operators_
$\mathcal{H}_{X}\rightarrow\mathcal{H}_{Y}$ as $\mathcal{L}(X,Y)$, and if
$X=Y$ as $\mathcal{L}(X)$; the set of _positive semidefinite operators_ on
$\mathcal{H}_{X}$ as $\mathcal{P}(X)$, and when $X$ is evident, write $P\geq
0$ for $P\in\mathcal{P}(X)$; and the set of _density operators_
$\mathcal{D}(X)=\vphantom{\rho\in\mathcal{P}(X)\operatorname{Tr}(\rho)=1}\left\\{{\rho\in\mathcal{P}(X)}\mid{\operatorname{Tr}(\rho)=1}\right\\}$,
representing the mixed quantum states. An operator $\rho\in\mathcal{P}(X)$ is
a _subnormalised state_ if $\operatorname{Tr}(\rho)\leq 1$. The definitions
below for mixed states extend directly to subnormalised states. Write
$\mathbb{I}_{X}\in\mathcal{L}(X)$ for the _identity operator_ , and
$\operatorname{id}_{X}:\mathcal{L}(X)\rightarrow\mathcal{L}(X)$ for the
_identity channel_. For $\rho=\rho_{XY}\in\mathcal{D}(XY)$, write
$\rho_{X}=\operatorname{Tr}_{Y}(\rho_{XY})$. A state $\rho\in\mathcal{D}(X)$
is _classical_ if it is diagonal in the register basis: it corresponds to a
probability distribution on $X$. As a shorthand, write
$[x]:=\vphantom{x}\left\lvert\smash{x}\middle\rangle\\!\middle\langle\smash{x}\right\rvert\in\mathcal{D}(X)$
to represent the density operator of a deterministic classical state. A state
$\rho\in\mathcal{D}(XY)$ is called _classical-quantum_ (cq) or classical on
$X$ if it can be written $\rho=\sum_{x\in X}p_{x}[x]\otimes\rho^{x}_{Y}$ for
some $\rho^{x}_{Y}\in\mathcal{D}(Y)$ and $p_{x}\in[0,1]$. By extension, we say
a state $\rho\in\mathcal{D}(X_{1}\cdots X_{m}Y_{1}\cdots Y_{n})$ is
$\mathrm{c}^{m}\mathrm{q}^{n}$ if it is classical on each $X_{i}$. We say a
register $X$ is _classical_ to assume that every state we work with is
classical on it. We say that a state $\rho_{X}$ is _supported_ on $Y$ if $Y$
is a subregister of $X$.

We represent a probability distribution on a register $X$ by a function
$\pi:X\rightarrow[0,1]$ such that $\sum_{x\in X}\pi(x)=1$. When the
probability distribution is implicit, we write the probability of an event
$\Omega\subseteq X$ as $\Pr\left[\Omega\right]=\sum_{x\in\Omega}\pi(x)$. For
any $\mathbb{C}$-vector space $V$, we write the _expectation value_ with
respect to the distribution as
$\operatorname*{\mathchoice{\raisebox{-10.00012pt}{\leavevmode\resizebox{18.9231pt}{10.00012pt}{\hbox{\raisebox{0.0pt}{$\displaystyle\vphantom{\mathbb{E}}\text{\raisebox{0.3pt}{\scalebox{0.9}{$\mathbb{E}$}}}$}}}}}{\raisebox{-10.00012pt}{\leavevmode\resizebox{18.9231pt}{10.00012pt}{\hbox{\raisebox{0.0pt}{$\textstyle\vphantom{\mathbb{E}}\text{\raisebox{0.3pt}{\scalebox{0.9}{$\mathbb{E}$}}}$}}}}}{\raisebox{-7.00009pt}{\leavevmode\resizebox{13.24615pt}{7.00009pt}{\hbox{\raisebox{0.0pt}{$\scriptstyle\vphantom{\mathbb{E}}\text{\raisebox{0.3pt}{\scalebox{0.9}{$\mathbb{E}$}}}$}}}}}{\raisebox{-5.00006pt}{\leavevmode\resizebox{9.46153pt}{5.00006pt}{\hbox{\raisebox{0.0pt}{$\scriptscriptstyle\vphantom{\mathbb{E}}\text{\raisebox{0.3pt}{\scalebox{0.9}{$\mathbb{E}$}}}$}}}}}}_{x\leftarrow\pi}f(x):=\sum_{x\in
X}\pi(x)f(x)$. The classical state corresponding to $\pi$ is written
$\mu_{\pi}=\operatorname*{\mathchoice{\raisebox{-10.00012pt}{\leavevmode\resizebox{18.9231pt}{10.00012pt}{\hbox{\raisebox{0.0pt}{$\displaystyle\vphantom{\mathbb{E}}\text{\raisebox{0.3pt}{\scalebox{0.9}{$\mathbb{E}$}}}$}}}}}{\raisebox{-10.00012pt}{\leavevmode\resizebox{18.9231pt}{10.00012pt}{\hbox{\raisebox{0.0pt}{$\textstyle\vphantom{\mathbb{E}}\text{\raisebox{0.3pt}{\scalebox{0.9}{$\mathbb{E}$}}}$}}}}}{\raisebox{-7.00009pt}{\leavevmode\resizebox{13.24615pt}{7.00009pt}{\hbox{\raisebox{0.0pt}{$\scriptstyle\vphantom{\mathbb{E}}\text{\raisebox{0.3pt}{\scalebox{0.9}{$\mathbb{E}$}}}$}}}}}{\raisebox{-5.00006pt}{\leavevmode\resizebox{9.46153pt}{5.00006pt}{\hbox{\raisebox{0.0pt}{$\scriptscriptstyle\vphantom{\mathbb{E}}\text{\raisebox{0.3pt}{\scalebox{0.9}{$\mathbb{E}$}}}$}}}}}}_{x\leftarrow\pi}[x]\in\mathcal{D}(x)$.
For the uniform distribution, we write the expectation simply
$\operatorname*{\mathchoice{\raisebox{-10.00012pt}{\leavevmode\resizebox{18.9231pt}{10.00012pt}{\hbox{\raisebox{0.0pt}{$\displaystyle\vphantom{\mathbb{E}}\text{\raisebox{0.3pt}{\scalebox{0.9}{$\mathbb{E}$}}}$}}}}}{\raisebox{-10.00012pt}{\leavevmode\resizebox{18.9231pt}{10.00012pt}{\hbox{\raisebox{0.0pt}{$\textstyle\vphantom{\mathbb{E}}\text{\raisebox{0.3pt}{\scalebox{0.9}{$\mathbb{E}$}}}$}}}}}{\raisebox{-7.00009pt}{\leavevmode\resizebox{13.24615pt}{7.00009pt}{\hbox{\raisebox{0.0pt}{$\scriptstyle\vphantom{\mathbb{E}}\text{\raisebox{0.3pt}{\scalebox{0.9}{$\mathbb{E}$}}}$}}}}}{\raisebox{-5.00006pt}{\leavevmode\resizebox{9.46153pt}{5.00006pt}{\hbox{\raisebox{0.0pt}{$\scriptscriptstyle\vphantom{\mathbb{E}}\text{\raisebox{0.3pt}{\scalebox{0.9}{$\mathbb{E}$}}}$}}}}}}_{x\in
X}$ and the state $\mu_{X}$. Abusing notation a bit, when we consider a random
variable with values in a register $X$, we often refer to the variable as $X$
as well.

A linear map $\Phi:\mathcal{L}(X)\rightarrow\mathcal{L}(Y)$ is called
_completely positive_ if for any register $Z$ and $P\in\mathcal{P}(ZX)$,
$(\operatorname{id}_{Z}\otimes\Phi)(P)\geq 0$. It is _trace-preserving_ if for
any $P\in\mathcal{P}(X)$,
$\operatorname{Tr}\left\lparen\Phi(P)\right\rparen=\operatorname{Tr}(P)$; and
_trace non-increasing_ if
$\operatorname{Tr}\left\lparen\Phi(P)\right\rparen\leq\operatorname{Tr}(P)$.
The _quantum channels_ $X\rightarrow Y$ are the completely positive trace-
preserving (CPTP) maps $\mathcal{L}(X)\rightarrow\mathcal{L}(Y)$ — they
represent the most general quantum operations. A _positive operator-valued
measurement_ (POVM) is a map $P:S\rightarrow\mathcal{P}(X)$, where $S$ and $X$
are registers, such that $\sum_{s\in S}P(s)=\mathbb{I}_{X}$; we write
$P_{s}:=P(s)$. A POVM $P$ is a _projector-valued measurement_ (PVM) if
$P_{s}P_{s^{\prime}}=\delta_{s,s^{\prime}}P_{s}$ for all $s,s^{\prime}\in S$.
We can associate various channels to a measurement. For a POVM
$P:S\rightarrow\mathcal{P}(X)$, the _destructive measurement channel_ is
$\Psi_{P}:\mathcal{L}(X)\rightarrow\mathcal{L}(S)$ defined as

$\displaystyle\Psi_{P}(\rho)=\sum_{s\in S}\operatorname{Tr}(P_{s}\rho)[s],$
(6)

representing the classical outcome of a measurement; and the _nondestructive
measurement channel_ $\Phi_{P}:\mathcal{L}(X)\rightarrow\mathcal{L}(SX)$
defined as

$\displaystyle\Phi_{P}(\rho)=\sum_{s\in
S}[s]\otimes\sqrt{P_{s}}\rho\sqrt{P_{s}},$ (7)

which represents both the classical outcome and the perturbed quantum state
after the measurement. Evidently,
$\operatorname{Tr}_{X}(\Phi_{P}(\rho))=\Psi_{P}(\rho)$. For a state
$\rho_{XY}\in D(XY)$, write
$\rho_{P(X)XY}=(\Phi_{P}\otimes\operatorname{id}_{Y})(\rho_{XY})$. Similarly,
if $\rho_{XY}$ is classical on $X$, for any function $f:X\rightarrow S$, we
write $\rho_{f(X)XY}=\sum_{x\in X}p_{x}[f(x)x]\otimes\rho^{x}_{Y}$. For any cq
state $\rho_{XY}$ and any event $\Omega\subseteq X$ — which may be phrased as
either a subset or as a relation — write the _partial state_

$\displaystyle\rho_{\land\Omega}=\rho_{XY\land\Omega}=\sum_{x\in\Omega}p_{x}[x]\otimes\rho^{x}_{Y},$
(8)

and the _conditional state_
$\rho_{|\Omega}=\frac{\rho_{\land\Omega}}{\operatorname{Tr}\rho_{\land\Omega}}$.
If the event makes reference to a measurement, _e.g._ $\Omega=(P(Y)=s)$, or a
function evaluation, we assume that the measurement or evaluation is
undertaken by the nondestructive channel, used to come up with the partial or
conditional state, and then the result is forgotten by tracing out. This may
perturb registers on which the state is non-classical, so we have to in
particular assure ourselves that any two measurements in the same event are
compatible.

###  2.2 Finite vector spaces and subspace coset states

Consider the vector space of bit strings $V=\mathbb{Z}_{2}^{n}$ over the
finite field $\mathbb{Z}_{2}$. The _canonical basis_ of $V$ is the set
$E=\\{e_{1},\ldots,e_{n}\\}$, where $e_{i}$ is the string that is $1$ at
position $i$ and $0$ elsewhere. For any $u\in V$, we expand in the basis as
$u=\sum_{i}u_{i}e_{i}$. The _inner product_ on $V\times
V\rightarrow\mathbb{Z}_{2}$ is defined as $u\cdot v=\sum_{i}u_{i}v_{i}$. For
any subspace $a\subseteq V$, the _orthogonal subspace_

$\displaystyle a^{\perp}=\vphantom{v\in Vu\cdot v=0\;\forall\;u\in
a}\left\\{{v\in V}\mid{u\cdot v=0\;\forall\;u\in a}\right\\}.$ (9)

This satisfies $(a^{\perp})^{\perp}=a$ and $\dim a+\dim a^{\perp}=\dim V=n$,
but in general $\operatorname{span}_{\mathbb{Z}_{2}}(a\cup
a^{\perp})=a+a^{\perp}\neq V$, for example $\\{00,11\\}^{\perp}=\\{00,11\\}$.

A subspace $a\subseteq V$ is called a _register subspace_ if it may be
expressed as $a=\operatorname{span}_{\mathbb{Z}_{2}}S$ for some $S\subseteq E$
[JNV+21]. For a register subspace, we have that
$a^{\perp}=\operatorname{span}_{\mathbb{Z}_{2}}S^{c}$, and therefore that
$a+a^{\perp}=V$. In this case, we get the canonical isomorphisms $V/a\cong
a^{\perp}$ and $V/a^{\perp}\cong a$. We can easily express any register
subspace by an indicator vector $\iota(a)\in V$ defined by $\iota(a)_{i}=1$ if
and only if $e_{i}\in a$.

The space $V$ can be be seen as a register, giving the Hilbert space
$\mathcal{H}_{V}\cong(\mathbb{C}^{2})^{\otimes n}$.

######  Definition 2.1 ([CLLZ21, VZ21]).

Let $a\subseteq V$ be a subspace. Given $t,t^{\prime}\in V$, the _subspace
coset state_

$\displaystyle\lvert a_{t,t^{\prime}}\rangle=\frac{1}{\sqrt{|a|}}\sum_{u\in
a}(-1)^{u\cdot t^{\prime}}\lvert u+t\rangle.$ (10)

If $u\in t+a$ and $u^{\prime}\in t^{\prime}+a^{\perp}$, we have that $\lvert
a_{u,u^{\prime}}\rangle$ is equal to $\lvert a_{t,t^{\prime}}\rangle$ up to
global phase. To make use of this, for any subspace $a$, we fix a linear map
$\mathbb{Z}_{2}^{n-\dim a}\rightarrow\mathbb{Z}_{2}^{n}$, $t\mapsto t_{a}$
such that $t\mapsto t_{a}+a$ is an isomorphism $\mathbb{Z}_{2}^{n-\dim
a}\cong\mathbb{Z}_{2}^{n}/a$, and then take, for $t\in\mathbb{Z}_{2}^{n-\dim
a}$ and $t^{\prime}\in\mathbb{Z}_{2}^{\dim a}$, $\lvert
a_{t,t^{\prime}}\rangle:=\lvert
a_{t_{a},t_{a}^{\prime}{\scriptscriptstyle\perp}}\rangle$. Then, the coset
states $\vphantom{\lvert a_{t,t^{\prime}}\rangle t\in\mathbb{Z}_{2}^{n-\dim
a},t^{\prime}\in\mathbb{Z}_{2}^{\dim a}}\left\\{{\lvert
a_{t,t^{\prime}}\rangle}\mid{t\in\mathbb{Z}_{2}^{n-\dim
a},t^{\prime}\in\mathbb{Z}_{2}^{\dim a}}\right\\}$ are all distinct and form
an orthonormal basis of $\mathcal{H}_{V}$.

If $a$ is a register subspace, there is a particularly good choice of map. For
$a^{\perp}=\operatorname{span}_{\mathbb{Z}_{2}}\\{e_{i_{1}},\ldots,e_{i_{m}}\\}$
with $i_{1}<i_{2}<\ldots<i_{m}$, we take $t_{a}=\sum_{j=1}^{m}t_{j}e_{i_{j}}$.
This allows us to write the subspace coset state in this case as a Wiesner
state $\lvert a_{t,t^{\prime}}\rangle=\lvert x^{\theta}\rangle$, where
$x=t_{a}+t^{\prime}_{a^{\perp}}$ and $\theta=\iota(a)$.

###  2.3 Entropy and extractors

Given a state $\rho_{XY}\in\mathcal{D}(XY)$, the _conditional min-entropy_ of
$X$ given $Y$ is defined as

$\displaystyle
H_{\min}(X|Y)_{\rho}=-\lg\inf\vphantom{\operatorname{Tr}(\sigma_{Y})\rho_{XY}\leq\mathbb{I}_{X}\otimes\sigma_{Y};\sigma_{Y}\in\mathcal{P}(Y)}\left\\{{\operatorname{Tr}(\sigma_{Y})}\mid{\rho_{XY}\leq\mathbb{I}_{X}\otimes\sigma_{Y};\sigma_{Y}\in\mathcal{P}(Y)}\right\\},$
(11)

where $\lg$ is the base-two logarithm [Ren05, Tom16]. Qualitatively, this
represents the uncertainty on $X$, knowing $Y$. If $\rho$ is classical on $X$,
this takes on a quantitative meaning: $2^{-H_{\min}(X|Y)}$ is the maximal
probability of guessing $X$ when given the register $Y$. In the absence of
side information, the conditional min-entropy becomes the min-entropy
$H_{\min}(X)_{\rho}=-\lg\|\rho_{X}\|$, where the norm here is the operator
norm.

We will use strong extractors to go from a condition on the entropy to a near-
independence of registers.

######  Definition 2.2 ([KT08]).

Let $X,Y,Z$ be classical registers. A _quantum-proof $(k,\varepsilon)$-strong
extractor_ is a function $e:X\times Y\rightarrow Z$ that satisfies the
following property. Let $\rho_{XQ}$ be a subnormalised state, where $Q$ is a
quantum register. If $H_{\min}(X|Q)\geq k$, then

$\displaystyle\left\|\rho_{e(X,Y)YQ}-\mu_{Z}\otimes\mu_{Y}\otimes\rho_{Q}\right\|_{\operatorname{Tr}}\leq\varepsilon,$
(12)

where $\rho_{YXQ}=\mu_{Y}\otimes\rho_{XQ}$.

Here, the norm is the trace norm
$\|A\|_{\operatorname{Tr}}=\frac{1}{2}\operatorname{Tr}\sqrt{A^{\dagger}A}$.
Due to [DPVR12], many constructions of extractors exist. Though we will tend
to stay general, we give an example of their construction that is useful to
keep in mind. For any $m,n\in\mathbb{N}$ and $\varepsilon>0$, there exists a
quantum-proof $(8\lg(3m/2\varepsilon)+m,\varepsilon)$-strong extractor
$e:\mathbb{Z}_{2}^{n}\times\mathbb{Z}_{2}^{d}\rightarrow\mathbb{Z}_{2}^{m}$,
where $d\in O(\lg(m\sqrt{n}/\varepsilon)^{2}\lg m)$. For course, for this to
be useful, we need that $k=8\lg(3m/2\varepsilon)+m<n$. Nevertheless, it is
possible to achieve an exponentially small error $\varepsilon=\eta^{m}$ for
any output length $m$ by taking $n>8\lg(3m/2)+(1+8\lg 1/\eta)m\in O(m)$,
though this requires the key length $d$ to be polynomial in $m$. This example
absolutely defeats the original purpose of strong extractors, to extract a
large amount of near-uniform randomness using a small seed, but is of great
use in our cryptographic applications.

##  3 Novel Coset State Monogamy-of-Entanglement Property

In this section, we introduce and prove the MoE property that we make use of
throughout the paper. In Section 3.1, we recall the MoE properties of coset
states that are already known. In Section 3.2, we show our new leaky MoE
property: the result is given in Theorem 3.2. Finally, in Section 3.3, we show
that this MoE property is equivalent to an entropic uncertainty relation,
given as Corollary 3.7.

###  3.1 Weak and strong MoE properties

Let the register $V=\mathbb{Z}_{2}^{n}$ and $A$ be a set of subspaces of
$\mathbb{Z}_{2}^{n}$ of dimension $n/2$: we take $A$ to either be the set of
all register subspaces of dimension $n/2$ or all subspaces of dimension $n/2$.
We consider the following monogamy-of-entanglement game, played between a
referee Alice, who holds $V$, and two cooperating players, Bob and Charlie.

  1. 1.

Alice samples a uniformly random $a\in A$ and
$t,t^{\prime}\in\mathbb{Z}_{2}^{n/2}$. She prepares the state $\lvert
a_{t,t^{\prime}}\rangle\in\mathcal{H}_{V}$ and sends it to Bob and Charlie.

  2. 2.

They act by an arbitrary channel
$\Phi:\mathcal{L}(V)\rightarrow\mathcal{L}(BC)$ and then are isolated, so that
Bob holds $B$ and Charlie holds $C$.

  3. 3.

Alice shares $a$ with Bob and Charlie, and they each make guesses of the pair
$(t,t^{\prime})$.

  4. 4.

Bob and Charlie win if their guesses are both correct.

It was shown in [CLLZ21] that the winning probability of this game is sub-
exponentially small in $n$. This is called the _weak monogamy-of-entanglement
property of subspace coset states._

There is also a _strong monogamy-of-entanglement property_ , conjectured in
the same work, which constrains the winning probability of a related game. The
difference here is that the winning condition is slackened: Bob needs only
guess $t$ and Charlie needs only guess $t^{\prime}$ correctly to win. It was
shown in [CV22] that the winning probability of this game is upper-bounded by
$\sqrt{e}(\cos\tfrac{\pi}{8})^{n}$.

###  3.2 The leaky MoE property

We exhibit an even stronger version of the MoE properties by showing that the
same bound holds on a family of games that can only be easier to win. In the
same setting as above, the game proceeds as follows:

  1. 1.

Alice samples a uniformly random $a\in A$ and
$t,t^{\prime}\in\mathbb{Z}_{2}^{n/2}$. She prepares the state $\lvert
a_{t,t^{\prime}}\rangle\in\mathcal{H}_{V}$ and sends it to Bob and Charlie.

  2. 2.

They act by an arbitrary channel
$\Phi:\mathcal{L}(V)\rightarrow\mathcal{L}(BC)$ and then are isolated, so that
Bob holds $B$ and Charlie holds $C$.

  3. 3.

Alice shares $a$ with Bob and Charlie.

  4. 4.

Bob makes a guess $t_{B}$ of $t$, which is then given to Charlie; Charlie
makes a guess $t^{\prime}_{C}$ of $t^{\prime}$.

  5. 5.

Bob and Charlie win if their guesses are both correct.

Alice$\lvert
a_{t,t^{\prime}}\rangle$$\Phi$BobCharlie$a$$t_{B}$$a{\color[rgb]{.5,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,.5,.5}\pgfsys@color@gray@stroke{.5}\pgfsys@color@gray@fill{.5},t_{B}}$$t_{B}{\color[rgb]{.75,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{.75,.75,.75}\pgfsys@color@gray@stroke{.75}\pgfsys@color@gray@fill{.75},t^{\prime}_{B}}$${\color[rgb]{.75,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{.75,.75,.75}\pgfsys@color@gray@stroke{.75}\pgfsys@color@gray@fill{.75}t_{C},}t^{\prime}_{C}$
Figure 1: The subspace coset MoE games. The additional guesses Bob and Charlie
need to make in the weak MoE game are given in light gray, and the additional
interaction step in the leaky MoE game is given in dark gray.

We call this the _$(n,A)$ -leaky monogamy-of-entanglement game_. The scenario
is illustrated in Fig. 1. An alternate but equivalent way to play the game, in
order to bring it closer to the original form of an MoE game, is to have Alice
provide Charlie with the correct value of $t$ rather than Bob’s guess. The
equivalence can be seen by noting that, in the original interpretation, only
the cases when Bob’s guess is correct are relevant to the computation of the
winning probability. Next, we formalise the strategies and winning probability
of this game.

######  Definition 3.1.

A quantum _strategy_ for the $(n,A)$-leaky MoE game is a tuple of the form
$\texttt{S}=\lparen B,C,\vphantom{B^{a}}\left\\{\smash{B^{a}}\right\\}_{a\in
A},\vphantom{C^{a,t}}\left\\{\smash{C^{a,t}}\right\\}_{a\in
A,t\in\mathbb{Z}_{2}^{n/2}},\Phi\rparen$, where

  * •

$B$ and $C$ are the registers representing Bob and Charlie’s systems,
respectively;

  * •

$B^{a}:\mathbb{Z}_{2}^{n/2}\rightarrow\mathcal{P}(B)$ and
$C^{a,t}:\mathbb{Z}_{2}^{n/2}\rightarrow\mathcal{P}(C)$ are POVMs,
representing Bob and Charlie’s measurements;

  * •

$\Phi:\mathcal{L}(V)\rightarrow\mathcal{L}(BC)$ is a quantum channel,
representing the splitting operation.

The _winning probability_ of a strategy S is

$\displaystyle\mathfrak{w}_{n,A}(\texttt{S})$
$\displaystyle=\\!\\!\\!\operatorname*{\mathchoice{\raisebox{-10.00012pt}{\leavevmode\resizebox{18.9231pt}{10.00012pt}{\hbox{\raisebox{0.0pt}{$\displaystyle\vphantom{\mathbb{E}}\text{\raisebox{0.3pt}{\scalebox{0.9}{$\mathbb{E}$}}}$}}}}}{\raisebox{-10.00012pt}{\leavevmode\resizebox{18.9231pt}{10.00012pt}{\hbox{\raisebox{0.0pt}{$\textstyle\vphantom{\mathbb{E}}\text{\raisebox{0.3pt}{\scalebox{0.9}{$\mathbb{E}$}}}$}}}}}{\raisebox{-7.00009pt}{\leavevmode\resizebox{13.24615pt}{7.00009pt}{\hbox{\raisebox{0.0pt}{$\scriptstyle\vphantom{\mathbb{E}}\text{\raisebox{0.3pt}{\scalebox{0.9}{$\mathbb{E}$}}}$}}}}}{\raisebox{-5.00006pt}{\leavevmode\resizebox{9.46153pt}{5.00006pt}{\hbox{\raisebox{0.0pt}{$\scriptscriptstyle\vphantom{\mathbb{E}}\text{\raisebox{0.3pt}{\scalebox{0.9}{$\mathbb{E}$}}}$}}}}}}_{\begin{subarray}{c}a\in
A\\\
t,t^{\prime}\in\mathbb{Z}_{2}^{n/2}\end{subarray}}\\!\\!\\!\operatorname{Tr}\left[(B^{a}_{t}\otimes
C^{a,t}_{t^{\prime}})\Phi(\vphantom{a_{t,t^{\prime}}}\left\lvert\smash{a_{t,t^{\prime}}}\middle\rangle\\!\middle\langle\smash{a_{t,t^{\prime}}}\right\rvert)\right].$
(13)

The optimal winning probability of the $(n,A)$-leaky MoE game is the supremum
over all quantum strategies
$\mathfrak{w}^{\ast}(n,A)=\sup_{\texttt{S}}\mathfrak{w}_{n,A}(\texttt{S})$.

Now, we can formally express the leaky MoE property.

######  Theorem 3.2.

Let $n\in\mathbb{N}$ and $A$ be either the collection of register subspaces or
the collection of all subspaces of dimension $n/2$ of $\mathbb{Z}_{2}^{n}$.
Then,

$\displaystyle\mathfrak{w}^{\ast}(n,A)\leq\sqrt{e}(\cos\tfrac{\pi}{8})^{n}.$
(14)

First, we note that, as in [TFKW13], we need only consider strategies for the
$(n,A)$-strong MoE game where the measurements $B^{a}$ and $C^{a,t}$ are
projective, as any measurement may be made projective by dilating using
Naimark’s theorem. Next, we need an important lemma.

######  Lemma 3.3 (Lemma 2 in [TFKW13]).

Let $P^{s}\in\mathcal{P}(H)$ for $s\in S$ be a collection of positive
operators. For any set of mutually orthogonal permutations
$\pi_{s}:S\rightarrow S$ (permutations such that $\pi_{s}\circ\pi_{t}^{-1}$
has a fixed point iff $s=t$) then

$\displaystyle\Big{\|}\sum_{s\in S}P^{s}\Big{\|}$ $\displaystyle\leq\sum_{s\in
S}\max_{t\in S}\left\|\sqrt{P^{t}}\sqrt{P^{\pi_{s}(t)}}\right\|.$

The following technical lemma is the final step of the proof of the theorem.

######  Lemma 3.4.

For any $a,b\in A$, $\|P^{a}P^{b}\|\leq\sqrt{\frac{|a\cap b|}{2^{n/2}}},$
where
$P^{a}=\sum_{t,t^{\prime}\in\mathbb{Z}_{2}^{n/2}}\vphantom{a_{t,t^{\prime}}}\left\lvert\smash{a_{t,t^{\prime}}}\middle\rangle\\!\middle\langle\smash{a_{t,t^{\prime}}}\right\rvert\otimes
B^{a}_{t}\otimes C^{a,t}_{t^{\prime}}$.

###### Proof.

First, note that
$P^{a}\leq\sum_{t,t^{\prime}}\vphantom{a_{t,t^{\prime}}}\left\lvert\smash{a_{t,t^{\prime}}}\middle\rangle\\!\middle\langle\smash{a_{t,t^{\prime}}}\right\rvert\otimes\mathbb{I}_{B}\otimes
C^{a,t}_{t^{\prime}}$ and

$\displaystyle
P^{b}\leq\sum_{u,u^{\prime}}\vphantom{b_{u,u^{\prime}}}\left\lvert\smash{b_{u,u^{\prime}}}\middle\rangle\\!\middle\langle\smash{b_{u,u^{\prime}}}\right\rvert\otimes
B^{b}_{u}\otimes\mathbb{I}_{C}=\sum_{u}\Pi_{b+u_{b}}\otimes
B^{b}_{u}\otimes\mathbb{I}_{C},$ (15)

where $\Pi_{b+u_{b}}=\sum_{v\in
b+u_{b}}\vphantom{v}\left\lvert\smash{v}\middle\rangle\\!\middle\langle\smash{v}\right\rvert$
is the projector onto $b+u_{b}$. Then,

$\displaystyle\begin{split}\left\|P^{a}P^{b}\right\|&\leq\Big{\|}\sum_{t,t^{\prime},u}\vphantom{a_{t,t^{\prime}}}\left\lvert\smash{a_{t,t^{\prime}}}\middle\rangle\\!\middle\langle\smash{a_{t,t^{\prime}}}\right\rvert\Pi_{b+u_{b}}\otimes
B^{b}_{u}\otimes C^{a,t}_{t^{\prime}}\Big{\|}\\\
&=\max_{u\in\mathbb{Z}_{2}^{n/2}}\Big{\|}\sum_{t,t^{\prime}}\vphantom{a_{t,t^{\prime}}}\left\lvert\smash{a_{t,t^{\prime}}}\middle\rangle\\!\middle\langle\smash{a_{t,t^{\prime}}}\right\rvert\Pi_{b+u_{b}}\otimes
C^{a,t}_{t^{\prime}}\Big{\|},\end{split}$ (16)

since the $B^{b}_{u}$ are orthogonal projectors. Next, by the $C^{\ast}$
identity,

$\displaystyle\Big{\|}\sum_{t,t^{\prime}}\vphantom{a_{t,t^{\prime}}}\left\lvert\smash{a_{t,t^{\prime}}}\middle\rangle\\!\middle\langle\smash{a_{t,t^{\prime}}}\right\rvert\Pi_{b+u_{b}}\otimes
C^{a,t}_{t^{\prime}}\Big{\|}=\Big{\|}\sum_{t,t^{\prime}}\Pi_{b+u_{b}}\vphantom{a_{t,t^{\prime}}}\left\lvert\smash{a_{t,t^{\prime}}}\middle\rangle\\!\middle\langle\smash{a_{t,t^{\prime}}}\right\rvert\Pi_{b+u_{b}}\otimes
C^{a,t}_{t^{\prime}}\Big{\|}^{1/2}.$ (17)

Now, the terms in this sum are Hermitian with orthogonal supports, because
$\Pi_{b+u_{b}}\vphantom{a_{t,t^{\prime}}}\left\lvert\smash{a_{t,t^{\prime}}}\middle\rangle\\!\middle\langle\smash{a_{t,t^{\prime}}}\right\rvert\Pi_{b+u_{b}}$
provides the orthogonality for different values of $t$, and equal values of
$t$, $C^{a,t}_{t^{\prime}}$ provides it for different values of $t^{\prime}$.
Therefore, we can again decompose this norm as the maximum of the norms of
each term. Putting this together, we get

$\displaystyle\begin{split}\left\|P^{a}P^{b}\right\|&\leq\max_{t,t^{\prime},u\in\mathbb{Z}_{2}^{n/2}}\left\|\Pi_{b+u_{b}}\vphantom{a_{t,t^{\prime}}}\left\lvert\smash{a_{t,t^{\prime}}}\middle\rangle\\!\middle\langle\smash{a_{t,t^{\prime}}}\right\rvert\Pi_{b+u_{b}}\right\|^{1/2}=\max_{t,t^{\prime},u\in\mathbb{Z}_{2}^{n/2}}\sqrt{\vphantom{a_{t,t^{\prime}}\Pi_{b+u_{b}}a_{t,t^{\prime}}}\left\langle\smash{a_{t,t^{\prime}}}\middle\rvert\smash{\Pi_{b+u_{b}}}\middle\rvert\smash{a_{t,t^{\prime}}}\right\rangle},\end{split}$
(18)

and we complete the proof by noting that

$\displaystyle\vphantom{a_{t,t^{\prime}}\Pi_{b+u_{b}}a_{t,t^{\prime}}}\left\langle\smash{a_{t,t^{\prime}}}\middle\rvert\smash{\Pi_{b+u_{b}}}\middle\rvert\smash{a_{t,t^{\prime}}}\right\rangle=\frac{1}{2^{n/2}}\sum_{v\in(a+t_{a})\cap(b+u_{b})}|(-1)^{t^{\prime}_{a}{\scriptscriptstyle\perp}\cdot
v}|^{2}\leq\frac{|a\cap b|}{2^{n/2}}.$ (19)

∎

Now, we can proceed to the proof of Theorem 3.2, which follows the method of
the analogous proof in [CV22].

###### Proof of Theorem 3.2.

First, for any strategy, we upper bound the winning probability by the norm of
a related operator. Using the Choi-Jamiołkowski representation
$J(\Phi)=\frac{1}{2^{n}}\sum_{u,v\in\mathbb{Z}_{2}^{n}}\vphantom{uv}\left\lvert\smash{u}\middle\rangle\\!\middle\langle\smash{v}\right\rvert\otimes\Phi(\vphantom{uv}\left\lvert\smash{u}\middle\rangle\\!\middle\langle\smash{v}\right\rvert)\in\mathcal{D}(VBC)$
of $\Phi$, we see that

$\displaystyle\begin{split}\mathfrak{w}_{n,A}(\texttt{S})&=\operatorname*{\mathchoice{\raisebox{-10.00012pt}{\leavevmode\resizebox{18.9231pt}{10.00012pt}{\hbox{\raisebox{0.0pt}{$\displaystyle\vphantom{\mathbb{E}}\text{\raisebox{0.3pt}{\scalebox{0.9}{$\mathbb{E}$}}}$}}}}}{\raisebox{-10.00012pt}{\leavevmode\resizebox{18.9231pt}{10.00012pt}{\hbox{\raisebox{0.0pt}{$\textstyle\vphantom{\mathbb{E}}\text{\raisebox{0.3pt}{\scalebox{0.9}{$\mathbb{E}$}}}$}}}}}{\raisebox{-7.00009pt}{\leavevmode\resizebox{13.24615pt}{7.00009pt}{\hbox{\raisebox{0.0pt}{$\scriptstyle\vphantom{\mathbb{E}}\text{\raisebox{0.3pt}{\scalebox{0.9}{$\mathbb{E}$}}}$}}}}}{\raisebox{-5.00006pt}{\leavevmode\resizebox{9.46153pt}{5.00006pt}{\hbox{\raisebox{0.0pt}{$\scriptscriptstyle\vphantom{\mathbb{E}}\text{\raisebox{0.3pt}{\scalebox{0.9}{$\mathbb{E}$}}}$}}}}}}_{a\in
A}\sum_{t,t^{\prime}\in\mathbb{Z}_{2}^{n/2}}\operatorname{Tr}\left[(\vphantom{a_{t,t^{\prime}}}\left\lvert\smash{a_{t,t^{\prime}}}\middle\rangle\\!\middle\langle\smash{a_{t,t^{\prime}}}\right\rvert\otimes
B^{a}_{t}\otimes C^{a,t}_{t^{\prime}})J(\Phi)\right]\\\
&\leq\Big{\|}\operatorname*{\mathchoice{\raisebox{-10.00012pt}{\leavevmode\resizebox{18.9231pt}{10.00012pt}{\hbox{\raisebox{0.0pt}{$\displaystyle\vphantom{\mathbb{E}}\text{\raisebox{0.3pt}{\scalebox{0.9}{$\mathbb{E}$}}}$}}}}}{\raisebox{-10.00012pt}{\leavevmode\resizebox{18.9231pt}{10.00012pt}{\hbox{\raisebox{0.0pt}{$\textstyle\vphantom{\mathbb{E}}\text{\raisebox{0.3pt}{\scalebox{0.9}{$\mathbb{E}$}}}$}}}}}{\raisebox{-7.00009pt}{\leavevmode\resizebox{13.24615pt}{7.00009pt}{\hbox{\raisebox{0.0pt}{$\scriptstyle\vphantom{\mathbb{E}}\text{\raisebox{0.3pt}{\scalebox{0.9}{$\mathbb{E}$}}}$}}}}}{\raisebox{-5.00006pt}{\leavevmode\resizebox{9.46153pt}{5.00006pt}{\hbox{\raisebox{0.0pt}{$\scriptscriptstyle\vphantom{\mathbb{E}}\text{\raisebox{0.3pt}{\scalebox{0.9}{$\mathbb{E}$}}}$}}}}}}_{a\in
A}\sum_{t,t^{\prime}\in\mathbb{Z}_{2}^{n/2}}\vphantom{a_{t,t^{\prime}}}\left\lvert\smash{a_{t,t^{\prime}}}\middle\rangle\\!\middle\langle\smash{a_{t,t^{\prime}}}\right\rvert\otimes
B^{a}_{t}\otimes C^{a,t}_{t^{\prime}}\Big{\|}.\end{split}$ (20)

Using the notation of the previous lemma, this is
$\mathfrak{w}_{n,A}(\texttt{S})\leq\left\|\operatorname*{\mathchoice{\raisebox{-10.00012pt}{\leavevmode\resizebox{18.9231pt}{10.00012pt}{\hbox{\raisebox{0.0pt}{$\displaystyle\vphantom{\mathbb{E}}\text{\raisebox{0.3pt}{\scalebox{0.9}{$\mathbb{E}$}}}$}}}}}{\raisebox{-10.00012pt}{\leavevmode\resizebox{18.9231pt}{10.00012pt}{\hbox{\raisebox{0.0pt}{$\textstyle\vphantom{\mathbb{E}}\text{\raisebox{0.3pt}{\scalebox{0.9}{$\mathbb{E}$}}}$}}}}}{\raisebox{-7.00009pt}{\leavevmode\resizebox{13.24615pt}{7.00009pt}{\hbox{\raisebox{0.0pt}{$\scriptstyle\vphantom{\mathbb{E}}\text{\raisebox{0.3pt}{\scalebox{0.9}{$\mathbb{E}$}}}$}}}}}{\raisebox{-5.00006pt}{\leavevmode\resizebox{9.46153pt}{5.00006pt}{\hbox{\raisebox{0.0pt}{$\scriptscriptstyle\vphantom{\mathbb{E}}\text{\raisebox{0.3pt}{\scalebox{0.9}{$\mathbb{E}$}}}$}}}}}}_{a}P^{a}\right\|$.
In the case that $A$ is the set of all subspaces of dimension $n/2$, we split
the expectation into two: first we take the average over the bases $\beta$ of
$\mathbb{Z}_{2}^{n}$, and then over the subspaces than can be spanned by that
basis, that is

$\displaystyle\begin{split}\mathfrak{w}_{n,A}(\texttt{S})&\leq\Big{\|}\operatorname*{\mathchoice{\raisebox{-10.00012pt}{\leavevmode\resizebox{18.9231pt}{10.00012pt}{\hbox{\raisebox{0.0pt}{$\displaystyle\vphantom{\mathbb{E}}\text{\raisebox{0.3pt}{\scalebox{0.9}{$\mathbb{E}$}}}$}}}}}{\raisebox{-10.00012pt}{\leavevmode\resizebox{18.9231pt}{10.00012pt}{\hbox{\raisebox{0.0pt}{$\textstyle\vphantom{\mathbb{E}}\text{\raisebox{0.3pt}{\scalebox{0.9}{$\mathbb{E}$}}}$}}}}}{\raisebox{-7.00009pt}{\leavevmode\resizebox{13.24615pt}{7.00009pt}{\hbox{\raisebox{0.0pt}{$\scriptstyle\vphantom{\mathbb{E}}\text{\raisebox{0.3pt}{\scalebox{0.9}{$\mathbb{E}$}}}$}}}}}{\raisebox{-5.00006pt}{\leavevmode\resizebox{9.46153pt}{5.00006pt}{\hbox{\raisebox{0.0pt}{$\scriptscriptstyle\vphantom{\mathbb{E}}\text{\raisebox{0.3pt}{\scalebox{0.9}{$\mathbb{E}$}}}$}}}}}}_{\beta\subseteq\mathbb{Z}_{2}^{n}\text{
basis}}\operatorname*{\mathchoice{\raisebox{-10.00012pt}{\leavevmode\resizebox{18.9231pt}{10.00012pt}{\hbox{\raisebox{0.0pt}{$\displaystyle\vphantom{\mathbb{E}}\text{\raisebox{0.3pt}{\scalebox{0.9}{$\mathbb{E}$}}}$}}}}}{\raisebox{-10.00012pt}{\leavevmode\resizebox{18.9231pt}{10.00012pt}{\hbox{\raisebox{0.0pt}{$\textstyle\vphantom{\mathbb{E}}\text{\raisebox{0.3pt}{\scalebox{0.9}{$\mathbb{E}$}}}$}}}}}{\raisebox{-7.00009pt}{\leavevmode\resizebox{13.24615pt}{7.00009pt}{\hbox{\raisebox{0.0pt}{$\scriptstyle\vphantom{\mathbb{E}}\text{\raisebox{0.3pt}{\scalebox{0.9}{$\mathbb{E}$}}}$}}}}}{\raisebox{-5.00006pt}{\leavevmode\resizebox{9.46153pt}{5.00006pt}{\hbox{\raisebox{0.0pt}{$\scriptscriptstyle\vphantom{\mathbb{E}}\text{\raisebox{0.3pt}{\scalebox{0.9}{$\mathbb{E}$}}}$}}}}}}_{\gamma\subseteq\beta,|\gamma|=n/2}P^{\operatorname{span}\gamma}\Big{\|}\leq\operatorname*{\mathchoice{\raisebox{-10.00012pt}{\leavevmode\resizebox{18.9231pt}{10.00012pt}{\hbox{\raisebox{0.0pt}{$\displaystyle\vphantom{\mathbb{E}}\text{\raisebox{0.3pt}{\scalebox{0.9}{$\mathbb{E}$}}}$}}}}}{\raisebox{-10.00012pt}{\leavevmode\resizebox{18.9231pt}{10.00012pt}{\hbox{\raisebox{0.0pt}{$\textstyle\vphantom{\mathbb{E}}\text{\raisebox{0.3pt}{\scalebox{0.9}{$\mathbb{E}$}}}$}}}}}{\raisebox{-7.00009pt}{\leavevmode\resizebox{13.24615pt}{7.00009pt}{\hbox{\raisebox{0.0pt}{$\scriptstyle\vphantom{\mathbb{E}}\text{\raisebox{0.3pt}{\scalebox{0.9}{$\mathbb{E}$}}}$}}}}}{\raisebox{-5.00006pt}{\leavevmode\resizebox{9.46153pt}{5.00006pt}{\hbox{\raisebox{0.0pt}{$\scriptscriptstyle\vphantom{\mathbb{E}}\text{\raisebox{0.3pt}{\scalebox{0.9}{$\mathbb{E}$}}}$}}}}}}_{\beta\subseteq\mathbb{Z}_{2}^{n}\text{
basis}}\Big{\|}\operatorname*{\mathchoice{\raisebox{-10.00012pt}{\leavevmode\resizebox{18.9231pt}{10.00012pt}{\hbox{\raisebox{0.0pt}{$\displaystyle\vphantom{\mathbb{E}}\text{\raisebox{0.3pt}{\scalebox{0.9}{$\mathbb{E}$}}}$}}}}}{\raisebox{-10.00012pt}{\leavevmode\resizebox{18.9231pt}{10.00012pt}{\hbox{\raisebox{0.0pt}{$\textstyle\vphantom{\mathbb{E}}\text{\raisebox{0.3pt}{\scalebox{0.9}{$\mathbb{E}$}}}$}}}}}{\raisebox{-7.00009pt}{\leavevmode\resizebox{13.24615pt}{7.00009pt}{\hbox{\raisebox{0.0pt}{$\scriptstyle\vphantom{\mathbb{E}}\text{\raisebox{0.3pt}{\scalebox{0.9}{$\mathbb{E}$}}}$}}}}}{\raisebox{-5.00006pt}{\leavevmode\resizebox{9.46153pt}{5.00006pt}{\hbox{\raisebox{0.0pt}{$\scriptscriptstyle\vphantom{\mathbb{E}}\text{\raisebox{0.3pt}{\scalebox{0.9}{$\mathbb{E}$}}}$}}}}}}_{\gamma\subseteq\beta,|\gamma|=n/2}P^{\operatorname{span}\gamma}\Big{\|}.\end{split}$
(21)

If A is the set of register subspaces, we don’t need to take this step as we
have
$\mathfrak{w}_{n,A}(\texttt{S})\leq\|\operatorname*{\mathchoice{\raisebox{-10.00012pt}{\leavevmode\resizebox{18.9231pt}{10.00012pt}{\hbox{\raisebox{0.0pt}{$\displaystyle\vphantom{\mathbb{E}}\text{\raisebox{0.3pt}{\scalebox{0.9}{$\mathbb{E}$}}}$}}}}}{\raisebox{-10.00012pt}{\leavevmode\resizebox{18.9231pt}{10.00012pt}{\hbox{\raisebox{0.0pt}{$\textstyle\vphantom{\mathbb{E}}\text{\raisebox{0.3pt}{\scalebox{0.9}{$\mathbb{E}$}}}$}}}}}{\raisebox{-7.00009pt}{\leavevmode\resizebox{13.24615pt}{7.00009pt}{\hbox{\raisebox{0.0pt}{$\scriptstyle\vphantom{\mathbb{E}}\text{\raisebox{0.3pt}{\scalebox{0.9}{$\mathbb{E}$}}}$}}}}}{\raisebox{-5.00006pt}{\leavevmode\resizebox{9.46153pt}{5.00006pt}{\hbox{\raisebox{0.0pt}{$\scriptscriptstyle\vphantom{\mathbb{E}}\text{\raisebox{0.3pt}{\scalebox{0.9}{$\mathbb{E}$}}}$}}}}}}_{\gamma\subseteq
E,|\gamma|=n/2}P^{\operatorname{span}\gamma}\|$. In either case, we will
complete the proof by fixing $\beta$ and showing that
$\|\operatorname*{\mathchoice{\raisebox{-10.00012pt}{\leavevmode\resizebox{18.9231pt}{10.00012pt}{\hbox{\raisebox{0.0pt}{$\displaystyle\vphantom{\mathbb{E}}\text{\raisebox{0.3pt}{\scalebox{0.9}{$\mathbb{E}$}}}$}}}}}{\raisebox{-10.00012pt}{\leavevmode\resizebox{18.9231pt}{10.00012pt}{\hbox{\raisebox{0.0pt}{$\textstyle\vphantom{\mathbb{E}}\text{\raisebox{0.3pt}{\scalebox{0.9}{$\mathbb{E}$}}}$}}}}}{\raisebox{-7.00009pt}{\leavevmode\resizebox{13.24615pt}{7.00009pt}{\hbox{\raisebox{0.0pt}{$\scriptstyle\vphantom{\mathbb{E}}\text{\raisebox{0.3pt}{\scalebox{0.9}{$\mathbb{E}$}}}$}}}}}{\raisebox{-5.00006pt}{\leavevmode\resizebox{9.46153pt}{5.00006pt}{\hbox{\raisebox{0.0pt}{$\scriptscriptstyle\vphantom{\mathbb{E}}\text{\raisebox{0.3pt}{\scalebox{0.9}{$\mathbb{E}$}}}$}}}}}}_{\gamma\subseteq\beta,|\gamma|=n/2}P^{\operatorname{span}\gamma}\|\leq\sqrt{e}(\cos\tfrac{\pi}{8})^{n}$.
Let $S$ be the set of subsets of $\beta$ of cardinality $n/2$. There exists a
family of orthogonal permutations $\pi_{s}:S\rightarrow S$ such that for each
$k=0,\cdots,\frac{n}{2}$, the number of permutations such that
$|\gamma\cap\pi_{s}(\gamma)|=\dim(\operatorname{span}\gamma\cap\operatorname{span}\pi_{s}(\gamma))=\frac{n}{2}-k$
for each $\gamma$ is $\binom{n/2}{k}^{2}$. Using Lemma 3.3 and then Lemma 3.4,
we have, since $P^{a}$ is a projector,

$\displaystyle\begin{split}\Big{\|}\operatorname*{\mathchoice{\raisebox{-10.00012pt}{\leavevmode\resizebox{18.9231pt}{10.00012pt}{\hbox{\raisebox{0.0pt}{$\displaystyle\vphantom{\mathbb{E}}\text{\raisebox{0.3pt}{\scalebox{0.9}{$\mathbb{E}$}}}$}}}}}{\raisebox{-10.00012pt}{\leavevmode\resizebox{18.9231pt}{10.00012pt}{\hbox{\raisebox{0.0pt}{$\textstyle\vphantom{\mathbb{E}}\text{\raisebox{0.3pt}{\scalebox{0.9}{$\mathbb{E}$}}}$}}}}}{\raisebox{-7.00009pt}{\leavevmode\resizebox{13.24615pt}{7.00009pt}{\hbox{\raisebox{0.0pt}{$\scriptstyle\vphantom{\mathbb{E}}\text{\raisebox{0.3pt}{\scalebox{0.9}{$\mathbb{E}$}}}$}}}}}{\raisebox{-5.00006pt}{\leavevmode\resizebox{9.46153pt}{5.00006pt}{\hbox{\raisebox{0.0pt}{$\scriptscriptstyle\vphantom{\mathbb{E}}\text{\raisebox{0.3pt}{\scalebox{0.9}{$\mathbb{E}$}}}$}}}}}}_{\gamma\in
S}P^{\operatorname{span}\gamma}\Big{\|}&\leq\operatorname*{\mathchoice{\raisebox{-10.00012pt}{\leavevmode\resizebox{18.9231pt}{10.00012pt}{\hbox{\raisebox{0.0pt}{$\displaystyle\vphantom{\mathbb{E}}\text{\raisebox{0.3pt}{\scalebox{0.9}{$\mathbb{E}$}}}$}}}}}{\raisebox{-10.00012pt}{\leavevmode\resizebox{18.9231pt}{10.00012pt}{\hbox{\raisebox{0.0pt}{$\textstyle\vphantom{\mathbb{E}}\text{\raisebox{0.3pt}{\scalebox{0.9}{$\mathbb{E}$}}}$}}}}}{\raisebox{-7.00009pt}{\leavevmode\resizebox{13.24615pt}{7.00009pt}{\hbox{\raisebox{0.0pt}{$\scriptstyle\vphantom{\mathbb{E}}\text{\raisebox{0.3pt}{\scalebox{0.9}{$\mathbb{E}$}}}$}}}}}{\raisebox{-5.00006pt}{\leavevmode\resizebox{9.46153pt}{5.00006pt}{\hbox{\raisebox{0.0pt}{$\scriptscriptstyle\vphantom{\mathbb{E}}\text{\raisebox{0.3pt}{\scalebox{0.9}{$\mathbb{E}$}}}$}}}}}}_{s\in
S}\max_{\gamma\in
S}\|P^{\operatorname{span}\gamma}P^{\operatorname{span}\pi_{s}(\gamma)}\|\\\
&\leq\operatorname*{\mathchoice{\raisebox{-10.00012pt}{\leavevmode\resizebox{18.9231pt}{10.00012pt}{\hbox{\raisebox{0.0pt}{$\displaystyle\vphantom{\mathbb{E}}\text{\raisebox{0.3pt}{\scalebox{0.9}{$\mathbb{E}$}}}$}}}}}{\raisebox{-10.00012pt}{\leavevmode\resizebox{18.9231pt}{10.00012pt}{\hbox{\raisebox{0.0pt}{$\textstyle\vphantom{\mathbb{E}}\text{\raisebox{0.3pt}{\scalebox{0.9}{$\mathbb{E}$}}}$}}}}}{\raisebox{-7.00009pt}{\leavevmode\resizebox{13.24615pt}{7.00009pt}{\hbox{\raisebox{0.0pt}{$\scriptstyle\vphantom{\mathbb{E}}\text{\raisebox{0.3pt}{\scalebox{0.9}{$\mathbb{E}$}}}$}}}}}{\raisebox{-5.00006pt}{\leavevmode\resizebox{9.46153pt}{5.00006pt}{\hbox{\raisebox{0.0pt}{$\scriptscriptstyle\vphantom{\mathbb{E}}\text{\raisebox{0.3pt}{\scalebox{0.9}{$\mathbb{E}$}}}$}}}}}}_{s\in
S}\max_{\gamma\in
S}\sqrt{\frac{\left\lvert\operatorname{span}\gamma\cap\operatorname{span}\pi_{s}(\gamma)\right\rvert}{2^{n/2}}}\\\
&=\frac{1}{\binom{n}{n/2}}\sum_{k=0}^{n/2}\binom{n/2}{k}^{2}\sqrt{\frac{2^{n/2-k}}{2^{n/2}}}=\frac{1}{\binom{n}{n/2}}\sum_{k=0}^{n/2}\binom{n/2}{k}^{2}2^{-k/2}.\end{split}$
(22)

Using a result of [CV22], this is upper-bounded by
$\sqrt{e}(\cos\tfrac{\pi}{8})^{n}$, finishing the proof. ∎

###  3.3 A new type of entropic uncertainty relation

We define a generalisation of the min-entropy that can be used to express MoE
properties.

######  Definition 3.5.

Let $\rho$ be a state supported on not necessarily distinct classical
registers $X_{1},\ldots,X_{n}$ and quantum registers $A_{1},\ldots,A_{n}$. For
POVMs $M^{i}:X_{i}\rightarrow\mathcal{P}(A_{i})$, write

$\displaystyle
H_{\min}(X_{1}|M^{1}(A_{1});\ldots;X_{n}|M^{n}(A_{n}))_{\rho}=-\lg\operatorname{Tr}\left[(\cdots(\rho_{\land(M^{1}(A_{1})=X_{1})})\cdots)_{\land(M^{n}(A_{n})=X_{n})}\right].$
(23)

Then, we define the _sequential min-entropy_ of $X_{1},\ldots,X_{n}$ knowing
$A_{1},\ldots,A_{n}$ as

$\displaystyle
H_{\min}(X_{1}|A_{1};\ldots;X_{n}|A_{n})_{\rho}=\inf_{M^{1},\ldots,M^{n}\text{
POVMs}}H_{\min}(X_{1}|M^{1}(A_{1});\ldots;X_{n}|M^{n}(A_{n})).$ (24)

Note that the sequential min-entropy is a generalisation of the conditional
min-entropy in the sense that they are the same for $n=1$.

The winning probability of the $(n,A)$-leaky MoE game may be phrased using
this entropy. First, for registers $T=T^{\prime}=\mathbb{Z}_{2}^{n/2}$ and $A$
representing either the register subspaces or all subspaces of
$\mathbb{Z}_{2}^{n}$ of dimension $n/2$, Alice prepares
$\rho_{ATT^{\prime}}=\mu_{A}\otimes\mu_{T}\otimes\mu_{T^{\prime}}$, and then
copies $A$ and prepares coset states on $V=\mathbb{Z}_{2}^{n}$ accordingly to
get

$\displaystyle\rho_{AA^{\prime}TT^{\prime}V}=\operatorname*{\mathchoice{\raisebox{-10.00012pt}{\leavevmode\resizebox{18.9231pt}{10.00012pt}{\hbox{\raisebox{0.0pt}{$\displaystyle\vphantom{\mathbb{E}}\text{\raisebox{0.3pt}{\scalebox{0.9}{$\mathbb{E}$}}}$}}}}}{\raisebox{-10.00012pt}{\leavevmode\resizebox{18.9231pt}{10.00012pt}{\hbox{\raisebox{0.0pt}{$\textstyle\vphantom{\mathbb{E}}\text{\raisebox{0.3pt}{\scalebox{0.9}{$\mathbb{E}$}}}$}}}}}{\raisebox{-7.00009pt}{\leavevmode\resizebox{13.24615pt}{7.00009pt}{\hbox{\raisebox{0.0pt}{$\scriptstyle\vphantom{\mathbb{E}}\text{\raisebox{0.3pt}{\scalebox{0.9}{$\mathbb{E}$}}}$}}}}}{\raisebox{-5.00006pt}{\leavevmode\resizebox{9.46153pt}{5.00006pt}{\hbox{\raisebox{0.0pt}{$\scriptscriptstyle\vphantom{\mathbb{E}}\text{\raisebox{0.3pt}{\scalebox{0.9}{$\mathbb{E}$}}}$}}}}}}_{a,t,t^{\prime}}[aatt^{\prime}]\otimes\vphantom{a_{t,t^{\prime}}}\left\lvert\smash{a_{t,t^{\prime}}}\middle\rangle\\!\middle\langle\smash{a_{t,t^{\prime}}}\right\rvert.$
(25)

Bob and Charlie act with a channel $\Phi$, giving
$\rho_{AA^{\prime}TT^{\prime}BC}=(\operatorname{id}_{AA^{\prime}TT^{\prime}}\otimes\Phi)(\rho_{AA^{\prime}TT^{\prime}V})$.
In terms of the sequential min-entropy, the leaky MoE property is the
statement that

$\displaystyle
H_{\min}(T|AB;T^{\prime}|A^{\prime}TC)_{\rho}\geq-\lg\mathfrak{w}^{\ast}(n,A)\geq(-\lg\cos\tfrac{\pi}{8})n-\tfrac{1}{2\ln
2}.$ (26)

This expression follows directly from the definition. The only snarl is that,
in general in the definition of the sequential min-entropy, Bob’s measurement
may not preserve $A$; and similarly Charlie’s measurement may not preserve
$A^{\prime}T$. However, since these classical registers are not reused, only
the diagonal blocks have any effect, and therefore, we may assume that the
measurements are diagonal on the classical registers. As such, the infimum
over the measurements is attained by those measurements that correspond to
strategies. Note that any MoE game admits an entropic expression of this form.

To close off this section, we present a way to expand the sequential min-
entropy as an entropic uncertainty relation.

######  Proposition 3.6.

Let $\rho$ be a state supported on classical registers $X,Y$ and quantum
registers $A,B$. Then,

$\displaystyle
H_{\min}(X|A;Y|B)_{\rho}=\inf_{M:X\rightarrow\mathcal{P}(A)\text{
POVM}}\left\lparen
H_{\min}(X|M(A))_{\rho}+H_{\min}(Y|B)_{\rho_{|(M(A)=X)}}\right\rparen.$ (27)

Note the contrast between this entropic uncertainty relation and that found in
[TFKW13]. Most importantly, their relation considers the min-entropy of the
same state on both terms, whereas ours uses different, albeit closely related,
states. This avoids the shortcoming of their entropic uncertainty relation —
that the entropy can remain bounded for any dimension of Alice’s space — and
thus allows us to make use of the full power of the MoE property in terms of
an entropy.

###### Proof.

This follows immediately from the definition. We have

$\displaystyle\begin{split}H_{\min}(X|A;Y|B)&=\inf_{M,N}-\lg\operatorname{Tr}\left[(\rho_{\land(M(A)=X)})_{\land(N(B)=Y)}\right]\\\
&=\inf_{M,N}-\lg\operatorname{Tr}\left[\rho_{\land(M(A)=X)}\right]\operatorname{Tr}\left[(\rho_{|(M(A)=X)})_{\land(N(B)=Y)}\right]\\\
&=\inf_{M}\left\lparen-\lg\operatorname{Tr}\left[\rho_{\land(M(A)=X)}\right]+\inf_{N}-\lg\operatorname{Tr}\left[(\rho_{|(M(A)=X)})_{\land(N(B)=Y)}\right]\right\rparen\\\
&=\inf_{M}\left\lparen
H_{\min}(X|M(A))_{\rho}+H_{\min}(Y|B)_{\rho_{|(M(A)=X)}}\right\rparen\qed\end{split}$
(28)

Using the above proposition, we may express the leaky MoE property as an
entropic uncertainty relation.

######  Corollary 3.7 (Leaky MoE entropic uncertainty relation).

For any measurement $M:T\rightarrow\mathcal{P}(AB)$ Bob makes in the leaky MoE
game, we have

$\displaystyle
H_{\min}(T|M(AB))_{\rho}+H_{\min}(T^{\prime}|A^{\prime}TC)_{\rho_{|(M(AB)=T)}}\geq(-\lg\cos\tfrac{\pi}{8})n-\tfrac{1}{2\ln
2}.$ (29)

This follows immediately by combining Theorem 3.2 with Proposition 3.6 via Eq.
26. This is the form of the bound that we make use of throughout the remainder
of the paper.

##  4 Interactive Uncloneable Encryption

In this section, we discuss our first application, introduced in Section 1.1.
In Section 4.1, we introduce the formalism used for interactive uncloneable
encryption and discuss its security. In Section 4.3, we give a construction,
given as 4.5, and prove its security using the leaky MoE property of the
previous section.

###  4.1 QECMs with interactive decryption and their security

We construct an uncloneable encryption scheme which requires only a
communication assumption. That is, in order to decrypt a message, the sender
Alice is required to have a short interaction with the receiver Bob. Note
that, like uncloneable encryption, interactive uncloneable encryption does not
assume an intended recipient, but once the interaction is started, only the
party that initiated the interaction will be able to decrypt the message with
high probability. First, in order to make sense of this interactive
decryption, we extend the idea of a quantum encryption of classical messages
of [BL20], by allowing the decryption to contain an interaction between the
sender Alice and the receiver Bob. This allows for uncloneability via the
leaky MoE property, as it will permit Alice to check whether an eavesdropper
has the ciphertext by checking whether Bob holds an uncorrelated piece of
information. We present this formally.

######  Definition 4.1.

A _quantum encryption of classical messages with interactive decryption (QECM-
ID)_ is a tuple
$\texttt{Q}=\left\lparen\texttt{Key},\texttt{Enc},\texttt{Dec}\right\rparen$.

  * •

$\texttt{Key}:\mathcal{D}(\\{0\\})\rightarrow\mathcal{D}(K)$ is the quantum
channel representing the key-generation algorithm, where $K$ is the classical
key register.

  * •

$\texttt{Enc}:\mathcal{D}(KM)\rightarrow\mathcal{D}(KMC)$ is the quantum
channel representing the encryption algorithm, where $M$ is the classical
message register and $C$ is the quantum ciphertext register. Enc preserves
$KM$, _i.e._ $\texttt{Enc}([km])=[km]\otimes\sigma^{km}_{C}$, where
$\sigma^{km}_{C}$ is the quantum ciphertext.

  * •

The decryption algorithm Dec is an interaction between Alice and Bob that
takes a state $\rho_{KMB}$ to $\rho_{KMF\hat{M}B^{\prime}}$, where Alice holds
$K$, $M$, and $F=\mathbb{Z}_{2}$ (a classical register that indicates whether
Alice aborts (0) or accepts the decryption (1)); and Bob holds $\hat{M}$ (a
classical register holding Bob’s decryption of the message), and $B$ and
$B^{\prime}$ (additional quantum registers).

The scheme is _$\varepsilon$ -correct_ if, for any classical state $\rho_{M}$,
when Alice and Bob run Dec as intended on
$\rho_{KMC}=\texttt{Enc}(\texttt{Key}([0])\otimes\rho_{M})$ for $B=C$, they
get $\rho_{KMF\hat{M}}$ such that555We use this definition as it presents an
operational way to simultaneously lower bound the probabilities of aborting
and decrypting the correct message.

$\displaystyle\|\rho_{M\hat{M}\land(F=1)}-\rho_{MM}\|_{\operatorname{Tr}}\leq\varepsilon.$
(30)

Note that this reduces to the original definition of a QECM if the decryption
is a simple one-round interaction: Alice sends the key $k$ to Bob, who uses it
to decrypt the ciphertext, and Alice always accepts the decryption. We extend
the security properties of indistinguishable, uncloneable, and uncloneable-
indistinguishable security of a QECM to this setting as well. Intuitively, the
definitions are meant to replace the condition of Bob guessing correctly with
Alice accepting the decryption.

First, we can describe the security properties by means of security games. The
_indistinguishable security game_ is played by an adversary Bob against a
challenger Alice.

  1. 1.

Bob prepares a cq state $\rho_{MS}$ and sends register $M$ to Alice, keeping
hold of the side-information.

  2. 2.

Alice samples a bit $y$ uniformly at random. If $y=0$ she replaces $M$ with a
fixed message $m_{0}$; else she preserves $M$.

  3. 3.

Alice samples a key using Key and encrypts the message. She then sends the
ciphertext to Bob.

  4. 4.

Bob attempts to guess $y$. He wins if he guesses correctly.

Indistinguishable security is achieved if the winning probability of this game
is only slightly above $\frac{1}{2}$. This is a standard property of
encryption schemes.

Uncloneable security guarantees that, even if a colluding party decrypts, an
eavesdropper can only guess the message as well as her side information
allows. The _uncloneable security game_ is played by two cooperating
adversaries Bob and Eve against a challenger Alice.

  1. 1.

Alice samples a message uniformly at random. She samples a key and encrypts
the message. She sends the ciphertext to the adversaries.

  2. 2.

The adversaries split the state between them using a quantum channel, and then
may no longer communicate.

  3. 3.

Alice and Bob decrypt with the interaction Dec, and Eve eavesdrops on their
interactions.

  4. 4.

Eve attempts to guess the message. The adversaries win if Alice accepts the
decryption ($f=1$) and Eve guesses correctly.

Uncloneable security is achieved if the winning probability is only slightly
above the probability of Alice accepting and Eve guessing the message given no
information $\frac{\Pr[F=1]}{|M|}$.

Finally, uncloneable-indistinguishable security combines uncloneable and
indistinguishable security: it guarantees that, even if a colluding party
decrypts, an eavesdropper cannot distinguish between the encryptions of an
intended message and a fixed message. The _uncloneable-indistinguishable
security game_ is also played by two cooperating adversaries against a
challenger.

  1. 1.

The adversaries prepare a cq state $\rho_{MS}$ and send register $M$ to Alice.

  2. 2.

Alice samples a bit $y$ uniformly at random. If $y=0$ she replaces $M$ with a
fixed message $m_{0}$; else she preserves $M$.

  3. 3.

Alice samples a key and encrypts the message. She sends the ciphertext to the
adversaries.

  4. 4.

The adversaries split the state between them using a quantum channel, and then
may no longer communicate.

  5. 5.

Alice and Bob decrypt with the interaction Dec, and Eve eavesdrops on their
interactions.

  6. 6.

Eve tries to guess $y$. The adversaries win if Alice accepts the decryption
and Eve guesses correctly.

Uncloneable-indistinguishable security is achieved if the winning probability
is only slightly above $\tfrac{1}{2}\Pr[F=1]$, half the probability of
accepting.

We now formalise the intuition of these security games in a way that is
amenable to security proofs in the information-theoretic setting.

######  Definition 4.2.

Let
$\texttt{Q}=\left\lparen\texttt{Key},\texttt{Enc},\texttt{Dec}\right\rparen$
be a QECM-ID. We say the scheme satisfies

$\varepsilon_{1}$-indistinguishable security

if

$\displaystyle\|\rho_{CS|(Y=0)}-\rho_{CS|(Y=1)}\|_{\operatorname{Tr}}\leq\varepsilon_{1},$
(31)

for $\rho$ prepared as follows. Fix $m_{0}\in M$, and let $Y=\mathbb{Z}_{2}$
and $\rho_{MS}$ be any cq state. Alice prepares the state
$\rho_{MSY}=\tfrac{1}{2}([m_{0}]\otimes\rho_{S}\otimes[0]+\rho_{MS}\otimes[1])$,
then encrypts to get
$\rho_{KMCSY}=(\texttt{Enc}\otimes\operatorname{id}_{SY})(\texttt{Key}([0])\otimes\rho_{MSY})$.

$\varepsilon_{2}$-uncloneable security

if

$\displaystyle\Pr\left[M=\check{M}\land
F=1\right]_{\rho}\leq\frac{1}{|M|}\Pr\left[F=1\right]_{\rho}+\varepsilon_{2},$
(32)

for $\rho$ prepared as follows. Let $\rho_{M}=\mu_{M}$ be the maximally mixed
state. Alice then encrypts
${\rho_{KMC}=\texttt{Enc}(\texttt{Key}([0])\otimes\rho_{M})}$ and an
eavesdropper Eve acts with a quantum channel
${\Phi:\mathcal{L}(C)\rightarrow\mathcal{L}(BE)}$ to get
$\rho_{KMBE}=(\operatorname{id}_{KM}\otimes\Phi)(\rho_{KMC})$. Then, after
eavesdropping on all the interactions during Dec, Eve produces a guess
$\check{M}$ of $M$.

$\varepsilon_{3}$-uncloneable-indistinguishable security

if

$\displaystyle\|\rho_{E^{\prime}|(Y=0)\land(F=1)}-\rho_{E^{\prime}|(Y=1)\land(F=1)}\|_{\operatorname{Tr}}\leq\varepsilon_{3},$
(33)

for $\rho$ prepared as follows. Fix $m_{0}\in M$, and let $Y=\mathbb{Z}_{2}$
and $\rho_{MS}$ be any cq state. Alice prepares the state
$\rho_{MSY}=\tfrac{1}{2}([m_{0}]\otimes\rho_{S}\otimes[0]+\rho_{MS}\otimes[1])$,
then encrypts to get
$\rho_{KMCSY}=(\texttt{Enc}\otimes\operatorname{id}_{SY})(\texttt{Key}([0])\otimes\rho_{MSY})$.
Next, an eavesdropper Eve acts with a quantum channel
$\Phi:\mathcal{L}(CS)\rightarrow\mathcal{L}(BE)$ to get
$\rho_{KMBEY}=(\operatorname{id}_{KM}\otimes\Phi\otimes\operatorname{id}_{Y})(\rho_{KMCSY})$
and after eavesdropping on all the interactions during Dec, Eve holds a
register $E^{\prime}$.

The security definitions are illustrated in Fig. 2.

$0$$K$$M$$C$$\hat{M}$$M$$F$KeyEncDec (a) Correctness

$0$$K$$M$$\mu_{M}\\{$$C$$B$$E$$\check{M}$$M$$F$$\Phi$KeyEncDec (b)
Uncloneability

$0$$K$$M$$S$$Y$$\Bigg{\\{}$$\rho_{MS}$$C$$Y$$S$KeyEnc (c) Indistinguishability

$0$$K$$M$$S$$Y$$\Bigg{\\{}$$\rho_{MS}$$C$$Y$$B$$E$$E^{\prime}$$F$$\Phi$KeyEncDec
(d) Uncloneability-indistinguishability

Figure 2: Schematics of the state constructions in the QECM-ID security
definitions. Blocks represent operations, with interactions if they are split
by a dotted line. Horizontal lines represent registers; they take part in the
operations they touch. Vertical arrows represent eavesdropping.

###  4.2 General properties

In this section, we show some relations on the uncloneable security properties
for QECM-IDs, with the idea to generalise properties of classical encryption
schemes. These extend and strengthen results known for QECMs.

First, we see that uncloneable security holds for non-uniform message
distributions, generalising a property shown in [BL20].

######  Lemma 4.3.

Let Q be an $\varepsilon$-uncloneable QECM-ID. Then, if the uncloneable
security game is played with a classical state $\rho_{M}$ not necessarily
uniform, the winning probability

$\displaystyle\Pr\left[M=\check{M}\land F=1\right]_{\rho}\leq
2^{-H_{\min}(M)_{\rho}}\Pr[F=1]+|M|2^{-H_{\min}(M)_{\rho}}\varepsilon.$ (34)

###### Proof.

We relate this to the winning probability with $\rho_{M}=\mu_{M}$. In fact,

$\displaystyle\begin{split}\Pr[M=\check{M}\land F=1]_{\rho}&=\sum_{m\in
M}\Pr[M=m]\Pr[\check{M}=m\land F=1|M=m]\\\
&\leq\max_{m}\Pr[M=m]\sum_{m}\Pr[\check{M}=m\land F=1|M=m]\\\
&=|M|2^{-H_{\min}(M)_{\rho}}\Pr[M=\check{M}\land F=1]_{\mu}\\\ &\leq
2^{-H_{\min}(M)_{\rho}}\Pr[F=1]+|M|2^{-H_{\min}(M)_{\rho}}\varepsilon\end{split}$
(35)

∎

Next, we find an equivalence, up to scalar multiple of the parameters, between
the uncloneable and uncloneable-indistinguishable security properties. One
direction, uncloneable security implying uncloneable-indistinguishable
security, generalises a similar property shown for QECMs in [BL20], while the
other direction is new, and remains an open question for QECMs in the
information-theoretic setting. The equivalence of these security properties is
similar to the equivalence of semantic security and indistinguishability in
classical encryption.

######  Theorem 4.4.

Let Q be a perfectly indistinguishable QECM-ID.

  * •

If Q is $\varepsilon$-uncloneable secure then it is
$|M|\varepsilon$-uncloneable-indistinguishable secure.

  * •

If Q is $\varepsilon$-uncloneable-indistinguishable secure then it is
$\varepsilon$-uncloneable secure.

Note that this theorem means that, outside of some pathological cases, it is
only necessary to show either uncloneable and uncloneable-indistinguishable
security for QECM-IDs, not both. However, we nevertheless show both in the
following section, as it allows us to work out better parameters.

###### Proof.

  * •

We proceed by contrapositive. Suppose there exists an attack for the
uncloneable-indistinguishable security game that wins with advantage greater
than $|M|\varepsilon$. An important observation we make to help simplify the
proof is that we may always assume that $\rho_{MS}=[m_{1}]$ for some message
$m_{1}\in M$ [KT22]. This is because the trace norm is convex, so

$\displaystyle\left\|\rho_{E^{\prime}|(Y=0)\land(F=1)}-\rho_{E^{\prime}|(Y=1)\land(F=1)}\right\|_{\operatorname{Tr}}\leq\sum_{m\in
M}p_{m}\left\|\rho^{m}_{E^{\prime}|(Y=0)\land(F=1)}-\rho^{m}_{E^{\prime}|(Y=1)\land(F=1)}\right\|_{\operatorname{Tr}},$
(36)

and thus we can take $m_{1}$ to be the value whose term in this convex
combination is maximal. Finally, we can remove the side information by
redefining the splitting channel
$\Phi^{\prime}(\sigma)=\Phi(\sigma\otimes\rho^{m_{1}}_{S})$.

With such an attack, we construct an attack against the uncloneable security
game. The splitting operation and Bob act in the same way. To attempt to guess
the message, Charlie makes the measurement that optimally distinguishes the
cases $y=0$ and $y=1$, and guess $m_{0}$ or $m_{1}$, respectively. Then, the
guessing probability

$\displaystyle\begin{split}\Pr\left[M=\check{M}\land
F=1\right]&=\Pr\left[M=\check{M}\land F=1\land
M\notin\\{m_{0},m_{1}\\}\right]\\\
&+\Pr\left[M\in\\{m_{0},m_{1}\\}\right]\Pr\left[M=\check{M}\land
F=1|M\in\\{m_{0},m_{1}\\}\right]\\\ &=\frac{2}{|M|}\Pr\left[M=\check{M}\land
F=1|M\in\\{m_{0},m_{1}\\}\right]\end{split}$ (37)

Since $\Pr\left[M=\check{M}\land F=1|M\in\\{m_{0},m_{1}\\}\right]$ is the
probability of distinguishing messages $m_{0}$ and $m_{1}$, we have by
hypothesis that this is greater than
$\frac{\Pr[F=1|M\in\\{m_{0},m_{1}\\}]+|M|\varepsilon}{2}$. Finally, as Q is
perfectly indistinguishable, $\Pr[F=1|M\in\\{m_{0},m_{1}\\}]=\Pr[F=1]$ —
otherwise Bob could distinguish the messages without access to the key.
Putting this together,

$\displaystyle\Pr\left[M=\check{M}\land
F=1\right]>\frac{\Pr[F=1]}{|M|}+\varepsilon.$ (38)

  * •

Let
$\rho_{ME^{\prime}\land(F=1)}=\operatorname*{\mathchoice{\raisebox{-10.00012pt}{\leavevmode\resizebox{18.9231pt}{10.00012pt}{\hbox{\raisebox{0.0pt}{$\displaystyle\vphantom{\mathbb{E}}\text{\raisebox{0.3pt}{\scalebox{0.9}{$\mathbb{E}$}}}$}}}}}{\raisebox{-10.00012pt}{\leavevmode\resizebox{18.9231pt}{10.00012pt}{\hbox{\raisebox{0.0pt}{$\textstyle\vphantom{\mathbb{E}}\text{\raisebox{0.3pt}{\scalebox{0.9}{$\mathbb{E}$}}}$}}}}}{\raisebox{-7.00009pt}{\leavevmode\resizebox{13.24615pt}{7.00009pt}{\hbox{\raisebox{0.0pt}{$\scriptstyle\vphantom{\mathbb{E}}\text{\raisebox{0.3pt}{\scalebox{0.9}{$\mathbb{E}$}}}$}}}}}{\raisebox{-5.00006pt}{\leavevmode\resizebox{9.46153pt}{5.00006pt}{\hbox{\raisebox{0.0pt}{$\scriptscriptstyle\vphantom{\mathbb{E}}\text{\raisebox{0.3pt}{\scalebox{0.9}{$\mathbb{E}$}}}$}}}}}}_{m\in
M}[m]\otimes\rho^{m}_{E^{\prime}\land(F=1)}$ be the final state in the
uncloneable security game. Since we have by hypothesis that Q is uncloneable-
indistinguishable secure,
$\|\rho^{m_{0}}_{E^{\prime}\land(F=1)}-\rho^{m}_{E^{\prime}\land(F=1)}\|_{\operatorname{Tr}}\leq\varepsilon$
for all $m\in M$. Setting the state
$\tau_{ME^{\prime}\land(F=1)}=\mu_{M}\otimes\rho^{m_{0}}_{E^{\prime}\land(F=1)}$,
we have that

$\displaystyle\|\tau_{ME^{\prime}\land(F=1)}-\rho_{ME^{\prime}\land(F=1)}\|_{\operatorname{Tr}}=\operatorname*{\mathchoice{\raisebox{-10.00012pt}{\leavevmode\resizebox{18.9231pt}{10.00012pt}{\hbox{\raisebox{0.0pt}{$\displaystyle\vphantom{\mathbb{E}}\text{\raisebox{0.3pt}{\scalebox{0.9}{$\mathbb{E}$}}}$}}}}}{\raisebox{-10.00012pt}{\leavevmode\resizebox{18.9231pt}{10.00012pt}{\hbox{\raisebox{0.0pt}{$\textstyle\vphantom{\mathbb{E}}\text{\raisebox{0.3pt}{\scalebox{0.9}{$\mathbb{E}$}}}$}}}}}{\raisebox{-7.00009pt}{\leavevmode\resizebox{13.24615pt}{7.00009pt}{\hbox{\raisebox{0.0pt}{$\scriptstyle\vphantom{\mathbb{E}}\text{\raisebox{0.3pt}{\scalebox{0.9}{$\mathbb{E}$}}}$}}}}}{\raisebox{-5.00006pt}{\leavevmode\resizebox{9.46153pt}{5.00006pt}{\hbox{\raisebox{0.0pt}{$\scriptscriptstyle\vphantom{\mathbb{E}}\text{\raisebox{0.3pt}{\scalebox{0.9}{$\mathbb{E}$}}}$}}}}}}_{m\in
M}\|\rho^{m_{0}}_{E^{\prime}\land(F=1)}-\rho^{m}_{E^{\prime}\land(F=1)}\|_{\operatorname{Tr}}\leq\varepsilon.$
(39)

Because the registers $M$ and $E^{\prime}$ are independent on $\tau$, the
guessing probability $\Pr[M=\check{M}\land
F=1]_{\tau}\leq\frac{\Pr[F=1]_{\tau}}{|M|}$. Finally, because $\tau$ is only
$\varepsilon$ away from $\rho$ in trace norm and
$\Pr[F=1]_{\tau}=\Pr[F=1|M=m_{0}]_{\rho}=\Pr[F=1]_{\rho}$ by perfect
indistinguishability, we get that $\Pr[M=\check{M}\land
F=1]_{\rho}\leq\frac{\Pr[F=1]_{\rho}}{|M|}+\varepsilon$. ∎

###  4.3 Instantiation and security proofs

Now, we give a construction of a QECM-ID. Let $e:\mathbb{Z}_{2}^{n/2}\times
R\rightarrow\mathbb{Z}_{2}^{\ell}$ be a quantum-proof
$(\kappa,\varepsilon)$-strong extractor and let $A$ be the set of all
subspaces of $V=\mathbb{Z}_{2}^{n}$ of dimension $n/2$.

######  Protocol 4.5 (Coset state QECM-ID).

Key generation Let $T=T^{\prime}=\mathbb{Z}_{2}^{n/2}$ and
$H=\mathbb{Z}_{2}^{\ell}$ and take $K=ATT^{\prime}RH$. The channel
$\displaystyle\texttt{Key}([0])=\operatorname*{\mathchoice{\raisebox{-10.00012pt}{\leavevmode\resizebox{18.9231pt}{10.00012pt}{\hbox{\raisebox{0.0pt}{$\displaystyle\vphantom{\mathbb{E}}\text{\raisebox{0.3pt}{\scalebox{0.9}{$\mathbb{E}$}}}$}}}}}{\raisebox{-10.00012pt}{\leavevmode\resizebox{18.9231pt}{10.00012pt}{\hbox{\raisebox{0.0pt}{$\textstyle\vphantom{\mathbb{E}}\text{\raisebox{0.3pt}{\scalebox{0.9}{$\mathbb{E}$}}}$}}}}}{\raisebox{-7.00009pt}{\leavevmode\resizebox{13.24615pt}{7.00009pt}{\hbox{\raisebox{0.0pt}{$\scriptstyle\vphantom{\mathbb{E}}\text{\raisebox{0.3pt}{\scalebox{0.9}{$\mathbb{E}$}}}$}}}}}{\raisebox{-5.00006pt}{\leavevmode\resizebox{9.46153pt}{5.00006pt}{\hbox{\raisebox{0.0pt}{$\scriptscriptstyle\vphantom{\mathbb{E}}\text{\raisebox{0.3pt}{\scalebox{0.9}{$\mathbb{E}$}}}$}}}}}}_{a,t,t^{\prime},r,h}[att^{\prime}rh].$
(40) Encryption Let $M=\bar{M}=\mathbb{Z}_{2}^{\ell}$ and $C=\bar{M}V$. Take
$\displaystyle\texttt{Enc}([att^{\prime}rh]\otimes[m])=[att^{\prime}rh]\otimes[m]\otimes[m+e(t^{\prime},r)+h]\otimes\vphantom{a_{t,t^{\prime}}}\left\lvert\smash{a_{t,t^{\prime}}}\middle\rangle\\!\middle\langle\smash{a_{t,t^{\prime}}}\right\rvert.$
(41) Decryption Dec proceeds as follows. First, Alice sends $a$ to Bob. Then,
Bob measures $V$ in the coset state basis to get measurements
$\hat{t},\hat{t}^{\prime}$ of $t,t^{\prime}$. Bob sends $\hat{t}$ to Alice: if
$\hat{t}=t$, Alice sets $f=1$, else she sets $f=0$ and aborts. Alice sends $r$
and $h$ to Bob. Bob computes $\hat{m}=\bar{m}+e(\hat{t}^{\prime},r)+h$.

######  Proposition 4.6.

4.5 is perfectly correct, _i.e._ $0$-correct.

###### Proof.

First, writing $\rho_{M}=\sum_{m}p_{m}[m]$,

$\displaystyle\rho_{KMC}=\rho_{ATT^{\prime}RHM\bar{M}V}=\operatorname*{\mathchoice{\raisebox{-10.00012pt}{\leavevmode\resizebox{18.9231pt}{10.00012pt}{\hbox{\raisebox{0.0pt}{$\displaystyle\vphantom{\mathbb{E}}\text{\raisebox{0.3pt}{\scalebox{0.9}{$\mathbb{E}$}}}$}}}}}{\raisebox{-10.00012pt}{\leavevmode\resizebox{18.9231pt}{10.00012pt}{\hbox{\raisebox{0.0pt}{$\textstyle\vphantom{\mathbb{E}}\text{\raisebox{0.3pt}{\scalebox{0.9}{$\mathbb{E}$}}}$}}}}}{\raisebox{-7.00009pt}{\leavevmode\resizebox{13.24615pt}{7.00009pt}{\hbox{\raisebox{0.0pt}{$\scriptstyle\vphantom{\mathbb{E}}\text{\raisebox{0.3pt}{\scalebox{0.9}{$\mathbb{E}$}}}$}}}}}{\raisebox{-5.00006pt}{\leavevmode\resizebox{9.46153pt}{5.00006pt}{\hbox{\raisebox{0.0pt}{$\scriptscriptstyle\vphantom{\mathbb{E}}\text{\raisebox{0.3pt}{\scalebox{0.9}{$\mathbb{E}$}}}$}}}}}}_{a,t,t^{\prime},r,h}\sum_{m}p_{m}[att^{\prime}rh]\otimes[m]\otimes[m+e(t^{\prime},r)+h]\otimes\vphantom{a_{t,t^{\prime}}}\left\lvert\smash{a_{t,t^{\prime}}}\middle\rangle\\!\middle\langle\smash{a_{t,t^{\prime}}}\right\rvert.$
(42)

To begin the decryption, Bob measures in the coset state basis and gets

$\displaystyle\rho_{ATT^{\prime}RHM\bar{M}\hat{T}\hat{T}^{\prime}}=\operatorname*{\mathchoice{\raisebox{-10.00012pt}{\leavevmode\resizebox{18.9231pt}{10.00012pt}{\hbox{\raisebox{0.0pt}{$\displaystyle\vphantom{\mathbb{E}}\text{\raisebox{0.3pt}{\scalebox{0.9}{$\mathbb{E}$}}}$}}}}}{\raisebox{-10.00012pt}{\leavevmode\resizebox{18.9231pt}{10.00012pt}{\hbox{\raisebox{0.0pt}{$\textstyle\vphantom{\mathbb{E}}\text{\raisebox{0.3pt}{\scalebox{0.9}{$\mathbb{E}$}}}$}}}}}{\raisebox{-7.00009pt}{\leavevmode\resizebox{13.24615pt}{7.00009pt}{\hbox{\raisebox{0.0pt}{$\scriptstyle\vphantom{\mathbb{E}}\text{\raisebox{0.3pt}{\scalebox{0.9}{$\mathbb{E}$}}}$}}}}}{\raisebox{-5.00006pt}{\leavevmode\resizebox{9.46153pt}{5.00006pt}{\hbox{\raisebox{0.0pt}{$\scriptscriptstyle\vphantom{\mathbb{E}}\text{\raisebox{0.3pt}{\scalebox{0.9}{$\mathbb{E}$}}}$}}}}}}_{a,t,t^{\prime},r,h}\sum_{m}p_{m}[att^{\prime}rh]\otimes[m]\otimes[m+e(t^{\prime},r)+h]\otimes[tt^{\prime}].$
(43)

Sending $\hat{t}=t$ to Alice, she always sets $F=1$, and then gives $r$ and
$h$ to Bob. Then, the state become

$\displaystyle\rho_{ATT^{\prime}RHMF\bar{M}\hat{T}^{\prime}}=\operatorname*{\mathchoice{\raisebox{-10.00012pt}{\leavevmode\resizebox{18.9231pt}{10.00012pt}{\hbox{\raisebox{0.0pt}{$\displaystyle\vphantom{\mathbb{E}}\text{\raisebox{0.3pt}{\scalebox{0.9}{$\mathbb{E}$}}}$}}}}}{\raisebox{-10.00012pt}{\leavevmode\resizebox{18.9231pt}{10.00012pt}{\hbox{\raisebox{0.0pt}{$\textstyle\vphantom{\mathbb{E}}\text{\raisebox{0.3pt}{\scalebox{0.9}{$\mathbb{E}$}}}$}}}}}{\raisebox{-7.00009pt}{\leavevmode\resizebox{13.24615pt}{7.00009pt}{\hbox{\raisebox{0.0pt}{$\scriptstyle\vphantom{\mathbb{E}}\text{\raisebox{0.3pt}{\scalebox{0.9}{$\mathbb{E}$}}}$}}}}}{\raisebox{-5.00006pt}{\leavevmode\resizebox{9.46153pt}{5.00006pt}{\hbox{\raisebox{0.0pt}{$\scriptscriptstyle\vphantom{\mathbb{E}}\text{\raisebox{0.3pt}{\scalebox{0.9}{$\mathbb{E}$}}}$}}}}}}_{a,t,t^{\prime},r,h}\sum_{m}p_{m}[att^{\prime}rh]\otimes[m]\otimes[1]\otimes[m+e(t^{\prime},r)+h]\otimes[t^{\prime}].$
(44)

Finally, Bob computes $\hat{m}=\bar{m}+e(\hat{t}^{\prime},r)+h=m$, getting

$\displaystyle\rho_{KMF\hat{M}}=\operatorname*{\mathchoice{\raisebox{-10.00012pt}{\leavevmode\resizebox{18.9231pt}{10.00012pt}{\hbox{\raisebox{0.0pt}{$\displaystyle\vphantom{\mathbb{E}}\text{\raisebox{0.3pt}{\scalebox{0.9}{$\mathbb{E}$}}}$}}}}}{\raisebox{-10.00012pt}{\leavevmode\resizebox{18.9231pt}{10.00012pt}{\hbox{\raisebox{0.0pt}{$\textstyle\vphantom{\mathbb{E}}\text{\raisebox{0.3pt}{\scalebox{0.9}{$\mathbb{E}$}}}$}}}}}{\raisebox{-7.00009pt}{\leavevmode\resizebox{13.24615pt}{7.00009pt}{\hbox{\raisebox{0.0pt}{$\scriptstyle\vphantom{\mathbb{E}}\text{\raisebox{0.3pt}{\scalebox{0.9}{$\mathbb{E}$}}}$}}}}}{\raisebox{-5.00006pt}{\leavevmode\resizebox{9.46153pt}{5.00006pt}{\hbox{\raisebox{0.0pt}{$\scriptscriptstyle\vphantom{\mathbb{E}}\text{\raisebox{0.3pt}{\scalebox{0.9}{$\mathbb{E}$}}}$}}}}}}_{a,t,t^{\prime},r,h}\sum_{m}p_{m}[att^{\prime}rh]\otimes[m]\otimes[1]\otimes[m].$
(45)

Thus, $\rho_{M\hat{M}\land(F=1)}=\sum_{m}p_{m}[m]\otimes[m]=\rho_{MM}$. ∎

######  Proposition 4.7.

4.5 is perfectly indistinguishable.

###### Proof.

Writing $\rho_{MS}=\sum_{m}p_{m}[m]\otimes\rho^{m}_{S}$, we see that

$\displaystyle\begin{split}\rho_{KMCSY}&=\frac{1}{2}\left\lparen\texttt{Enc}(\texttt{Key}(0)\otimes[m_{0}])\otimes\rho_{S}\otimes[0]+(\texttt{Enc}\otimes\operatorname{id}_{S})(\texttt{Key}(0)\otimes\rho_{MS})\otimes[1]\right\rparen\\\
&=\frac{1}{2}\sum_{m}\texttt{Enc}(\texttt{Key}(0)\otimes[m])\otimes\left\lparen\delta_{m,m_{0}}\rho_{S}\otimes[0]+p_{m}\rho^{m}_{S}\otimes[1]\right\rparen\\\
&=\frac{1}{2}\sum_{m}\operatorname*{\mathchoice{\raisebox{-10.00012pt}{\leavevmode\resizebox{18.9231pt}{10.00012pt}{\hbox{\raisebox{0.0pt}{$\displaystyle\vphantom{\mathbb{E}}\text{\raisebox{0.3pt}{\scalebox{0.9}{$\mathbb{E}$}}}$}}}}}{\raisebox{-10.00012pt}{\leavevmode\resizebox{18.9231pt}{10.00012pt}{\hbox{\raisebox{0.0pt}{$\textstyle\vphantom{\mathbb{E}}\text{\raisebox{0.3pt}{\scalebox{0.9}{$\mathbb{E}$}}}$}}}}}{\raisebox{-7.00009pt}{\leavevmode\resizebox{13.24615pt}{7.00009pt}{\hbox{\raisebox{0.0pt}{$\scriptstyle\vphantom{\mathbb{E}}\text{\raisebox{0.3pt}{\scalebox{0.9}{$\mathbb{E}$}}}$}}}}}{\raisebox{-5.00006pt}{\leavevmode\resizebox{9.46153pt}{5.00006pt}{\hbox{\raisebox{0.0pt}{$\scriptscriptstyle\vphantom{\mathbb{E}}\text{\raisebox{0.3pt}{\scalebox{0.9}{$\mathbb{E}$}}}$}}}}}}_{a,t,t^{\prime},r,h}[att^{\prime}rhm]\otimes[m+e(t^{\prime},r)+h]\otimes\vphantom{a_{t,t^{\prime}}}\left\lvert\smash{a_{t,t^{\prime}}}\middle\rangle\\!\middle\langle\smash{a_{t,t^{\prime}}}\right\rvert\otimes\left\lparen\delta_{m,m_{0}}\rho_{S}\otimes[0]+p_{m}\rho^{m}_{S}\otimes[1]\right\rparen.\end{split}$
(46)

Hence,

$\displaystyle\begin{split}\rho_{CSY}&=\frac{1}{2}\sum_{m}\operatorname*{\mathchoice{\raisebox{-10.00012pt}{\leavevmode\resizebox{18.9231pt}{10.00012pt}{\hbox{\raisebox{0.0pt}{$\displaystyle\vphantom{\mathbb{E}}\text{\raisebox{0.3pt}{\scalebox{0.9}{$\mathbb{E}$}}}$}}}}}{\raisebox{-10.00012pt}{\leavevmode\resizebox{18.9231pt}{10.00012pt}{\hbox{\raisebox{0.0pt}{$\textstyle\vphantom{\mathbb{E}}\text{\raisebox{0.3pt}{\scalebox{0.9}{$\mathbb{E}$}}}$}}}}}{\raisebox{-7.00009pt}{\leavevmode\resizebox{13.24615pt}{7.00009pt}{\hbox{\raisebox{0.0pt}{$\scriptstyle\vphantom{\mathbb{E}}\text{\raisebox{0.3pt}{\scalebox{0.9}{$\mathbb{E}$}}}$}}}}}{\raisebox{-5.00006pt}{\leavevmode\resizebox{9.46153pt}{5.00006pt}{\hbox{\raisebox{0.0pt}{$\scriptscriptstyle\vphantom{\mathbb{E}}\text{\raisebox{0.3pt}{\scalebox{0.9}{$\mathbb{E}$}}}$}}}}}}_{a,t,t^{\prime},r,h}[m+e(t^{\prime},r)+h]\otimes\vphantom{a_{t,t^{\prime}}}\left\lvert\smash{a_{t,t^{\prime}}}\middle\rangle\\!\middle\langle\smash{a_{t,t^{\prime}}}\right\rvert\otimes\left\lparen\delta_{m,m_{0}}\rho_{S}\otimes[0]+p_{m}\rho^{m}_{S}\otimes[1]\right\rparen\\\
&=\frac{1}{2}\operatorname*{\mathchoice{\raisebox{-10.00012pt}{\leavevmode\resizebox{18.9231pt}{10.00012pt}{\hbox{\raisebox{0.0pt}{$\displaystyle\vphantom{\mathbb{E}}\text{\raisebox{0.3pt}{\scalebox{0.9}{$\mathbb{E}$}}}$}}}}}{\raisebox{-10.00012pt}{\leavevmode\resizebox{18.9231pt}{10.00012pt}{\hbox{\raisebox{0.0pt}{$\textstyle\vphantom{\mathbb{E}}\text{\raisebox{0.3pt}{\scalebox{0.9}{$\mathbb{E}$}}}$}}}}}{\raisebox{-7.00009pt}{\leavevmode\resizebox{13.24615pt}{7.00009pt}{\hbox{\raisebox{0.0pt}{$\scriptstyle\vphantom{\mathbb{E}}\text{\raisebox{0.3pt}{\scalebox{0.9}{$\mathbb{E}$}}}$}}}}}{\raisebox{-5.00006pt}{\leavevmode\resizebox{9.46153pt}{5.00006pt}{\hbox{\raisebox{0.0pt}{$\scriptscriptstyle\vphantom{\mathbb{E}}\text{\raisebox{0.3pt}{\scalebox{0.9}{$\mathbb{E}$}}}$}}}}}}_{a,t,t^{\prime}}\mu_{\bar{M}}\otimes\vphantom{a_{t,t^{\prime}}}\left\lvert\smash{a_{t,t^{\prime}}}\middle\rangle\\!\middle\langle\smash{a_{t,t^{\prime}}}\right\rvert\otimes\sum_{m}\left\lparen\delta_{m,m_{0}}\rho_{S}\otimes[0]+p_{m}\rho^{m}_{S}\otimes[1]\right\rparen\\\
&=\frac{1}{2}\mu_{C}\otimes\left\lparen\rho_{S}\otimes[0]+\rho_{S}\otimes[1]\right\rparen=\mu_{C}\otimes\rho_{S}\otimes\mu_{Y}.\end{split}$
(47)

Thus, $\rho_{CS|(Y=0)}=\rho_{CS|(Y=1)}$. ∎

######  Theorem 4.8.

Suppose $\kappa\geq\frac{-\lg\cos\frac{\pi}{8}}{2}n-\frac{1}{4\ln 2}$. Then,
4.5 is $\max\\{\varepsilon,e^{1/4}(\cos\tfrac{\pi}{8})^{n/2}\\}$-uncloneable.

###### Proof.

We have the state before decryption

$\displaystyle\rho_{ATT^{\prime}RHMBE}=\operatorname*{\mathchoice{\raisebox{-10.00012pt}{\leavevmode\resizebox{18.9231pt}{10.00012pt}{\hbox{\raisebox{0.0pt}{$\displaystyle\vphantom{\mathbb{E}}\text{\raisebox{0.3pt}{\scalebox{0.9}{$\mathbb{E}$}}}$}}}}}{\raisebox{-10.00012pt}{\leavevmode\resizebox{18.9231pt}{10.00012pt}{\hbox{\raisebox{0.0pt}{$\textstyle\vphantom{\mathbb{E}}\text{\raisebox{0.3pt}{\scalebox{0.9}{$\mathbb{E}$}}}$}}}}}{\raisebox{-7.00009pt}{\leavevmode\resizebox{13.24615pt}{7.00009pt}{\hbox{\raisebox{0.0pt}{$\scriptstyle\vphantom{\mathbb{E}}\text{\raisebox{0.3pt}{\scalebox{0.9}{$\mathbb{E}$}}}$}}}}}{\raisebox{-5.00006pt}{\leavevmode\resizebox{9.46153pt}{5.00006pt}{\hbox{\raisebox{0.0pt}{$\scriptscriptstyle\vphantom{\mathbb{E}}\text{\raisebox{0.3pt}{\scalebox{0.9}{$\mathbb{E}$}}}$}}}}}}_{a,t,t^{\prime},r,h,m}[att^{\prime}rh]\otimes[m]\otimes\Phi([m+e(t^{\prime},r)+h]\otimes\vphantom{a_{t,t^{\prime}}}\left\lvert\smash{a_{t,t^{\prime}}}\middle\rangle\\!\middle\langle\smash{a_{t,t^{\prime}}}\right\rvert).$
(48)

To begin the decryption, Alice shares $a$, and Bob makes a measurement $N$ on
$B$ to determine a guess $\hat{t}$ of $t$. Fix $\bar{m}\in\bar{M}$. Then,
taking $\sigma\mapsto\Phi([\bar{m}]\otimes\sigma)$ to be the cloning channel
in the leaky MoE game, we get by the leaky MoE property that
$H_{\min}(T|AB;T^{\prime}|A^{\prime}TE)_{\rho_{|(\bar{M}=\bar{m})}}\geq(-\lg\cos\tfrac{\pi}{8})n-\frac{1}{2\ln
2}$, where $A^{\prime}$ is a copy of $A$. Thus, we must have either
$H_{\min}(T|N(AB))_{\rho_{|(\bar{M}=\bar{m})}}\geq\frac{-\lg\cos\frac{\pi}{8}}{2}n-\frac{1}{4\ln
2}$ or
$H_{\min}(T^{\prime}|A^{\prime}TE)_{\rho_{|(N(AB)=T\land\bar{M}=\bar{m})}}\geq\frac{-\lg\cos\frac{\pi}{8}}{2}n-\frac{1}{4\ln
2}$. In the former case, as $AB$ is the register Bob has access to by that
point, we have

$\displaystyle\Pr[F=1]=\Pr[\hat{T}=T]=\Pr[N(AB)=T]\leq
e^{1/4}(\cos\tfrac{\pi}{8})^{n/2}.$ (49)

In the latter case, we have by hypothesis and the strong extractor property,

$\displaystyle\begin{split}&\|\rho_{e(T^{\prime},R)RA^{\prime}TE|(F=1\land\bar{M}=\bar{m})}-\mu_{\tilde{M}}\otimes\mu_{R}\otimes\rho_{A^{\prime}TE|(F=1\land
M=m)}\|_{\operatorname{Tr}}\\\
&=\|\rho_{e(T^{\prime},R)RA^{\prime}TE|(N(AB)=T\land\bar{M}=\bar{m})}-\mu_{\tilde{M}}\otimes\mu_{R}\otimes\rho_{A^{\prime}TE|(N(AB)=T\land\bar{M}=\bar{m})}\|_{\operatorname{Tr}}\leq\varepsilon,\end{split}$
(50)

where $\tilde{M}=\mathbb{Z}_{2}^{\ell}$ is the register containing
$e(T^{\prime},R)$. Combining the two cases,

$\displaystyle\begin{split}&\|\rho_{e(T^{\prime},R)RA^{\prime}TE\land(F=1)|(\bar{M}=\bar{m})}-\mu_{\tilde{M}}\otimes\mu_{R}\otimes\rho_{A^{\prime}TE\land(F=1)|(\bar{M}=\bar{m})}\|_{\operatorname{Tr}}\\\
&=\Pr[F=1]_{\rho}\|\rho_{e(T^{\prime},R)RA^{\prime}TE|(F=1\land\bar{M}=\bar{m})}-\mu_{\tilde{M}}\otimes\mu_{R}\otimes\rho_{A^{\prime}TE|(F=1\land\bar{M}=\bar{m})}\|_{\operatorname{Tr}}\\\
&\leq\varepsilon^{\ast},\end{split}$ (51)

where we set
$\varepsilon^{\ast}=\max\\{\varepsilon,e^{1/4}(\cos\tfrac{\pi}{8})^{n/2}\\}$.
This implies that, as $m$ and $\bar{m}=m+e(t^{\prime},r)+h$ are uniformly
distributed and independent,

$\displaystyle\begin{split}\rho_{M\bar{M}e(T^{\prime},R)RA^{\prime}TE\land(F=1)}&=\operatorname*{\mathchoice{\raisebox{-10.00012pt}{\leavevmode\resizebox{18.9231pt}{10.00012pt}{\hbox{\raisebox{0.0pt}{$\displaystyle\vphantom{\mathbb{E}}\text{\raisebox{0.3pt}{\scalebox{0.9}{$\mathbb{E}$}}}$}}}}}{\raisebox{-10.00012pt}{\leavevmode\resizebox{18.9231pt}{10.00012pt}{\hbox{\raisebox{0.0pt}{$\textstyle\vphantom{\mathbb{E}}\text{\raisebox{0.3pt}{\scalebox{0.9}{$\mathbb{E}$}}}$}}}}}{\raisebox{-7.00009pt}{\leavevmode\resizebox{13.24615pt}{7.00009pt}{\hbox{\raisebox{0.0pt}{$\scriptstyle\vphantom{\mathbb{E}}\text{\raisebox{0.3pt}{\scalebox{0.9}{$\mathbb{E}$}}}$}}}}}{\raisebox{-5.00006pt}{\leavevmode\resizebox{9.46153pt}{5.00006pt}{\hbox{\raisebox{0.0pt}{$\scriptscriptstyle\vphantom{\mathbb{E}}\text{\raisebox{0.3pt}{\scalebox{0.9}{$\mathbb{E}$}}}$}}}}}}_{m,\bar{m}}[m\bar{m}]\otimes\rho_{e(T^{\prime},R)RA^{\prime}TE\land(F=1)|(\bar{M}=\bar{m})}\\\
&\approx_{\varepsilon^{\ast}}\operatorname*{\mathchoice{\raisebox{-10.00012pt}{\leavevmode\resizebox{18.9231pt}{10.00012pt}{\hbox{\raisebox{0.0pt}{$\displaystyle\vphantom{\mathbb{E}}\text{\raisebox{0.3pt}{\scalebox{0.9}{$\mathbb{E}$}}}$}}}}}{\raisebox{-10.00012pt}{\leavevmode\resizebox{18.9231pt}{10.00012pt}{\hbox{\raisebox{0.0pt}{$\textstyle\vphantom{\mathbb{E}}\text{\raisebox{0.3pt}{\scalebox{0.9}{$\mathbb{E}$}}}$}}}}}{\raisebox{-7.00009pt}{\leavevmode\resizebox{13.24615pt}{7.00009pt}{\hbox{\raisebox{0.0pt}{$\scriptstyle\vphantom{\mathbb{E}}\text{\raisebox{0.3pt}{\scalebox{0.9}{$\mathbb{E}$}}}$}}}}}{\raisebox{-5.00006pt}{\leavevmode\resizebox{9.46153pt}{5.00006pt}{\hbox{\raisebox{0.0pt}{$\scriptscriptstyle\vphantom{\mathbb{E}}\text{\raisebox{0.3pt}{\scalebox{0.9}{$\mathbb{E}$}}}$}}}}}}_{m,\bar{m}}[m\bar{m}]\otimes\mu_{\tilde{M}}\otimes\mu_{R}\otimes\rho_{A^{\prime}TE\land(F=1)|(\bar{M}=\bar{m})},\end{split}$
(52)

hence
$\|\rho_{\tilde{M}RM\bar{M}A^{\prime}TE\land(F=1)}-\mu_{\tilde{M}RM}\otimes\rho_{\bar{M}A^{\prime}TE\land(F=1)}\|_{\operatorname{Tr}}\leq\varepsilon^{\ast}$.
Supposing $f=1$, the decryption continues and Eve also gets
$h=m+\bar{m}+\tilde{m}$ and tries to guess $m$. As classical computations are
CPTP maps, we see that

$\displaystyle\begin{split}&\|\rho_{R\tilde{M}M\bar{M}A^{\prime}TE\land(F=1)}-\mu_{R\tilde{M}M}\otimes\rho_{\bar{M}A^{\prime}TE\land(F=1)}\|_{\operatorname{Tr}}\\\
&\geq\|\rho_{R\tilde{M}M(M+\bar{M}+\tilde{M})\bar{M}A^{\prime}TE\land(F=1)}-\mu_{R}\otimes\sigma_{\tilde{M}M(M+\bar{M}+\tilde{M})\bar{M}A^{\prime}TE\land(F=1)}\|_{\operatorname{Tr}}\\\
&\geq\|\rho_{RM(M+\bar{M}+\tilde{M})A^{\prime}TE\land(F=1)}-\mu_{R}\otimes\sigma_{M(M+\bar{M}+\tilde{M})A^{\prime}TE\land(F=1)}\|_{\operatorname{Tr}},\end{split}$
(53)

where
$\sigma_{\tilde{M}M\bar{M}A^{\prime}TE\land(F=1)}=\mu_{\tilde{M}M}\otimes\rho_{MA^{\prime}TE\land(F=1)}$,
so

$\displaystyle\begin{split}\sigma_{M(M+\bar{M}+\tilde{M})A^{\prime}TE\land(F=1)}&=\operatorname*{\mathchoice{\raisebox{-10.00012pt}{\leavevmode\resizebox{18.9231pt}{10.00012pt}{\hbox{\raisebox{0.0pt}{$\displaystyle\vphantom{\mathbb{E}}\text{\raisebox{0.3pt}{\scalebox{0.9}{$\mathbb{E}$}}}$}}}}}{\raisebox{-10.00012pt}{\leavevmode\resizebox{18.9231pt}{10.00012pt}{\hbox{\raisebox{0.0pt}{$\textstyle\vphantom{\mathbb{E}}\text{\raisebox{0.3pt}{\scalebox{0.9}{$\mathbb{E}$}}}$}}}}}{\raisebox{-7.00009pt}{\leavevmode\resizebox{13.24615pt}{7.00009pt}{\hbox{\raisebox{0.0pt}{$\scriptstyle\vphantom{\mathbb{E}}\text{\raisebox{0.3pt}{\scalebox{0.9}{$\mathbb{E}$}}}$}}}}}{\raisebox{-5.00006pt}{\leavevmode\resizebox{9.46153pt}{5.00006pt}{\hbox{\raisebox{0.0pt}{$\scriptscriptstyle\vphantom{\mathbb{E}}\text{\raisebox{0.3pt}{\scalebox{0.9}{$\mathbb{E}$}}}$}}}}}}_{m,\bar{m},\tilde{m}}[m(m+\bar{m}+\tilde{m})]\otimes\rho_{A^{\prime}TE\land(F=1)|(\bar{M}=\bar{m})}\\\
&=\mu_{MH}\otimes\rho_{A^{\prime}TE\land(F=1)}.\end{split}$ (54)

During the decryption, all the information Eve receives is contained in
$E^{\prime}=RHA^{\prime}TE$. Let the subnormalised state
$\tau_{ME^{\prime}}=\mu_{MRH}\otimes\rho_{A^{\prime}TE\land(F=1)}$. By the
above, we have that
$\|\rho_{ME^{\prime}\land(F=1)}-\tau_{ME^{\prime}}\|_{\operatorname{Tr}}\leq\varepsilon^{\ast}$.
As such, if the shared state were $\tau$, $M$ is independent from
$E^{\prime}$, and therefore $\Pr\left[M=\check{M}\land
F=1\right]_{\tau}\leq\frac{\operatorname{Tr}\tau}{|M|}=\frac{\Pr[F=1]_{\rho}}{|M|}$.
This implies that the probability of guessing $M$ given $E^{\prime}$ of
$\rho_{ME^{\prime}\land(F=1)}$ is at most

$\displaystyle\Pr[M=\check{M}\land F=1]_{\rho}\leq\Pr\left[M=\check{M}\land
F=1\right]_{\tau}+\varepsilon^{\ast}\leq\frac{\Pr[F=1]_{\rho}}{|M|}+\varepsilon^{\ast},$
(55)

as wanted. ∎

######  Theorem 4.9.

Suppose $\kappa\geq\frac{-\lg\cos\frac{\pi}{8}}{2}n-\frac{1}{4\ln 2}$. Then,
4.5 is $\max\\{2\varepsilon,2e^{1/4}(\cos\tfrac{\pi}{8})^{n/2}\\}$
-indistinguishable-uncloneable.

###### Proof.

With $\rho_{MS}=\sum_{m}p_{m}[m]\otimes\rho^{m}_{S}$, we have again

$\displaystyle\rho_{KMCSY}=\rho_{ATT^{\prime}RHM\bar{M}VSY}$ (56)
$\displaystyle=\frac{1}{2}\sum_{m}\operatorname*{\mathchoice{\raisebox{-10.00012pt}{\leavevmode\resizebox{18.9231pt}{10.00012pt}{\hbox{\raisebox{0.0pt}{$\displaystyle\vphantom{\mathbb{E}}\text{\raisebox{0.3pt}{\scalebox{0.9}{$\mathbb{E}$}}}$}}}}}{\raisebox{-10.00012pt}{\leavevmode\resizebox{18.9231pt}{10.00012pt}{\hbox{\raisebox{0.0pt}{$\textstyle\vphantom{\mathbb{E}}\text{\raisebox{0.3pt}{\scalebox{0.9}{$\mathbb{E}$}}}$}}}}}{\raisebox{-7.00009pt}{\leavevmode\resizebox{13.24615pt}{7.00009pt}{\hbox{\raisebox{0.0pt}{$\scriptstyle\vphantom{\mathbb{E}}\text{\raisebox{0.3pt}{\scalebox{0.9}{$\mathbb{E}$}}}$}}}}}{\raisebox{-5.00006pt}{\leavevmode\resizebox{9.46153pt}{5.00006pt}{\hbox{\raisebox{0.0pt}{$\scriptscriptstyle\vphantom{\mathbb{E}}\text{\raisebox{0.3pt}{\scalebox{0.9}{$\mathbb{E}$}}}$}}}}}}_{a,t,t^{\prime},r,h}[att^{\prime}rhm]\otimes[m+e(t^{\prime},r)+h]\otimes\vphantom{a_{t,t^{\prime}}}\left\lvert\smash{a_{t,t^{\prime}}}\middle\rangle\\!\middle\langle\smash{a_{t,t^{\prime}}}\right\rvert\otimes\left\lparen\delta_{m,m_{0}}\rho_{S}\otimes[0]+p_{m}\rho^{m}_{S}\otimes[1]\right\rparen,$

so given the cloning attack
$\Phi:\mathcal{L}(\bar{M}VS)\rightarrow\mathcal{L}(BE)$, the state before
decryption is

$\displaystyle\rho_{KMBEY}=\frac{1}{2}\sum_{m}\\!\\!\operatorname*{\mathchoice{\raisebox{-10.00012pt}{\leavevmode\resizebox{18.9231pt}{10.00012pt}{\hbox{\raisebox{0.0pt}{$\displaystyle\vphantom{\mathbb{E}}\text{\raisebox{0.3pt}{\scalebox{0.9}{$\mathbb{E}$}}}$}}}}}{\raisebox{-10.00012pt}{\leavevmode\resizebox{18.9231pt}{10.00012pt}{\hbox{\raisebox{0.0pt}{$\textstyle\vphantom{\mathbb{E}}\text{\raisebox{0.3pt}{\scalebox{0.9}{$\mathbb{E}$}}}$}}}}}{\raisebox{-7.00009pt}{\leavevmode\resizebox{13.24615pt}{7.00009pt}{\hbox{\raisebox{0.0pt}{$\scriptstyle\vphantom{\mathbb{E}}\text{\raisebox{0.3pt}{\scalebox{0.9}{$\mathbb{E}$}}}$}}}}}{\raisebox{-5.00006pt}{\leavevmode\resizebox{9.46153pt}{5.00006pt}{\hbox{\raisebox{0.0pt}{$\scriptscriptstyle\vphantom{\mathbb{E}}\text{\raisebox{0.3pt}{\scalebox{0.9}{$\mathbb{E}$}}}$}}}}}}_{a,t,t^{\prime},r,h}\\!\\!\\![att^{\prime}rhm]\otimes\big{(}$
$\displaystyle\delta_{m,m_{0}}\Phi([m+e(t^{\prime},r)+h]\otimes\vphantom{a_{t,t^{\prime}}}\left\lvert\smash{a_{t,t^{\prime}}}\middle\rangle\\!\middle\langle\smash{a_{t,t^{\prime}}}\right\rvert\otimes\rho_{S})\otimes[0]$
(57)
$\displaystyle+p_{m}\Phi([m+e(t^{\prime},r)+h]\otimes\vphantom{a_{t,t^{\prime}}}\left\lvert\smash{a_{t,t^{\prime}}}\middle\rangle\\!\middle\langle\smash{a_{t,t^{\prime}}}\right\rvert\otimes\rho^{m}_{S})\otimes[1]\big{)}.$

On $\rho_{|(Y=0\land\bar{M}=\bar{m})}$, the cloning attack is
$\sigma\mapsto\Phi([\bar{m}]\otimes\sigma\otimes\rho_{S})$, so we have

$\displaystyle
H_{\min}(T|AB;T^{\prime}|A^{\prime}TE)_{\rho_{|(Y=0\land\bar{M}=\bar{m})}}\geq(-\lg\cos\tfrac{\pi}{8})n-\tfrac{1}{2\ln
2},$ (58)

where $A^{\prime}$ is a copy of $A$, and hence as above

$\displaystyle\|\rho_{e(T^{\prime},R)RA^{\prime}TE|(Y=0\land\bar{M}=\bar{m})\land(F=1)}-\mu_{\tilde{M}}\otimes\mu_{R}\otimes\rho_{A^{\prime}TE|(Y=0\land\bar{M}=\bar{m})\land(F=1)}\|_{\operatorname{Tr}}\leq\varepsilon^{\ast},$
(59)

and then, in order to include $M$ and $\bar{M}$,

$\displaystyle\begin{split}\rho_{Me(T^{\prime},R)RA^{\prime}TE\bar{M}|(Y=0)\land(F=1)}&=\operatorname*{\mathchoice{\raisebox{-10.00012pt}{\leavevmode\resizebox{18.9231pt}{10.00012pt}{\hbox{\raisebox{0.0pt}{$\displaystyle\vphantom{\mathbb{E}}\text{\raisebox{0.3pt}{\scalebox{0.9}{$\mathbb{E}$}}}$}}}}}{\raisebox{-10.00012pt}{\leavevmode\resizebox{18.9231pt}{10.00012pt}{\hbox{\raisebox{0.0pt}{$\textstyle\vphantom{\mathbb{E}}\text{\raisebox{0.3pt}{\scalebox{0.9}{$\mathbb{E}$}}}$}}}}}{\raisebox{-7.00009pt}{\leavevmode\resizebox{13.24615pt}{7.00009pt}{\hbox{\raisebox{0.0pt}{$\scriptstyle\vphantom{\mathbb{E}}\text{\raisebox{0.3pt}{\scalebox{0.9}{$\mathbb{E}$}}}$}}}}}{\raisebox{-5.00006pt}{\leavevmode\resizebox{9.46153pt}{5.00006pt}{\hbox{\raisebox{0.0pt}{$\scriptscriptstyle\vphantom{\mathbb{E}}\text{\raisebox{0.3pt}{\scalebox{0.9}{$\mathbb{E}$}}}$}}}}}}_{\bar{m}}[m_{0}]\otimes\rho_{e(T^{\prime},R)RA^{\prime}TE|(Y=0\land\bar{M}=\bar{m})\land(F=1)}\otimes[\bar{m}]\\\
&\approx_{\varepsilon^{\ast}}\operatorname*{\mathchoice{\raisebox{-10.00012pt}{\leavevmode\resizebox{18.9231pt}{10.00012pt}{\hbox{\raisebox{0.0pt}{$\displaystyle\vphantom{\mathbb{E}}\text{\raisebox{0.3pt}{\scalebox{0.9}{$\mathbb{E}$}}}$}}}}}{\raisebox{-10.00012pt}{\leavevmode\resizebox{18.9231pt}{10.00012pt}{\hbox{\raisebox{0.0pt}{$\textstyle\vphantom{\mathbb{E}}\text{\raisebox{0.3pt}{\scalebox{0.9}{$\mathbb{E}$}}}$}}}}}{\raisebox{-7.00009pt}{\leavevmode\resizebox{13.24615pt}{7.00009pt}{\hbox{\raisebox{0.0pt}{$\scriptstyle\vphantom{\mathbb{E}}\text{\raisebox{0.3pt}{\scalebox{0.9}{$\mathbb{E}$}}}$}}}}}{\raisebox{-5.00006pt}{\leavevmode\resizebox{9.46153pt}{5.00006pt}{\hbox{\raisebox{0.0pt}{$\scriptscriptstyle\vphantom{\mathbb{E}}\text{\raisebox{0.3pt}{\scalebox{0.9}{$\mathbb{E}$}}}$}}}}}}_{\bar{m}}[m_{0}]\otimes\mu_{\tilde{M}R}\otimes\rho_{A^{\prime}TE|(Y=0\land\bar{M}=\bar{m})\land(F=1)}\otimes[\bar{m}]\\\
&=[m_{0}]\otimes\mu_{\tilde{M}R}\otimes\rho_{A^{\prime}TE\bar{M}|(Y=0)\land(F=1)}.\end{split}$
(60)

As $H=\tilde{M}+M+\bar{M}$, this gives that

$\displaystyle\|\rho_{MRHA^{\prime}TE|(Y=0)\land(F=1)}-[m_{0}]\otimes\mu_{RH}\otimes\rho_{A^{\prime}TE|(Y=0)\land(F=1)}\|_{\operatorname{Tr}}\leq\varepsilon^{\ast}$

In the same way, we get that on $\rho_{|(Y=1\land M=m\land\bar{M}=\bar{m})}$,
the cloning attack is
$\sigma\mapsto\Phi([\bar{m}]\otimes\sigma\otimes\rho_{S}^{m})$, so the entropy
$H_{\min}(T|AB;T^{\prime}|A^{\prime}TE)_{\rho_{|(Y=1\land
M=m\land\bar{M}=\bar{m})}}\geq(-\lg\cos\tfrac{\pi}{8})n-\tfrac{1}{2\ln 2}$,
and hence as above

$\displaystyle\|\rho_{e(T^{\prime},R)RATE|(Y=1\land
M=m)\land(F=1)}-\mu_{\tilde{M}}\otimes\mu_{R}\otimes\rho_{ATE|(Y=1\land
M=m)\land(F=1)}\|_{\operatorname{Tr}}\leq\varepsilon^{\ast}.$ (61)

To include $M$ and $\bar{M}$,

$\displaystyle\begin{split}\rho_{e(T^{\prime},R)RA^{\prime}TEM\bar{M}|(Y=1)\land(F=1)}&=\sum_{m}\operatorname*{\mathchoice{\raisebox{-10.00012pt}{\leavevmode\resizebox{18.9231pt}{10.00012pt}{\hbox{\raisebox{0.0pt}{$\displaystyle\vphantom{\mathbb{E}}\text{\raisebox{0.3pt}{\scalebox{0.9}{$\mathbb{E}$}}}$}}}}}{\raisebox{-10.00012pt}{\leavevmode\resizebox{18.9231pt}{10.00012pt}{\hbox{\raisebox{0.0pt}{$\textstyle\vphantom{\mathbb{E}}\text{\raisebox{0.3pt}{\scalebox{0.9}{$\mathbb{E}$}}}$}}}}}{\raisebox{-7.00009pt}{\leavevmode\resizebox{13.24615pt}{7.00009pt}{\hbox{\raisebox{0.0pt}{$\scriptstyle\vphantom{\mathbb{E}}\text{\raisebox{0.3pt}{\scalebox{0.9}{$\mathbb{E}$}}}$}}}}}{\raisebox{-5.00006pt}{\leavevmode\resizebox{9.46153pt}{5.00006pt}{\hbox{\raisebox{0.0pt}{$\scriptscriptstyle\vphantom{\mathbb{E}}\text{\raisebox{0.3pt}{\scalebox{0.9}{$\mathbb{E}$}}}$}}}}}}_{\bar{m}}p_{m}\rho_{e(T^{\prime},R)RA^{\prime}TE|(Y=1\land
M=m\land\bar{M}=\bar{m})\land(F=1)}\otimes[m\bar{m}]\\\
&\approx_{\varepsilon^{\ast}}\sum_{m}\operatorname*{\mathchoice{\raisebox{-10.00012pt}{\leavevmode\resizebox{18.9231pt}{10.00012pt}{\hbox{\raisebox{0.0pt}{$\displaystyle\vphantom{\mathbb{E}}\text{\raisebox{0.3pt}{\scalebox{0.9}{$\mathbb{E}$}}}$}}}}}{\raisebox{-10.00012pt}{\leavevmode\resizebox{18.9231pt}{10.00012pt}{\hbox{\raisebox{0.0pt}{$\textstyle\vphantom{\mathbb{E}}\text{\raisebox{0.3pt}{\scalebox{0.9}{$\mathbb{E}$}}}$}}}}}{\raisebox{-7.00009pt}{\leavevmode\resizebox{13.24615pt}{7.00009pt}{\hbox{\raisebox{0.0pt}{$\scriptstyle\vphantom{\mathbb{E}}\text{\raisebox{0.3pt}{\scalebox{0.9}{$\mathbb{E}$}}}$}}}}}{\raisebox{-5.00006pt}{\leavevmode\resizebox{9.46153pt}{5.00006pt}{\hbox{\raisebox{0.0pt}{$\scriptscriptstyle\vphantom{\mathbb{E}}\text{\raisebox{0.3pt}{\scalebox{0.9}{$\mathbb{E}$}}}$}}}}}}_{\bar{m}}p_{m}\mu_{\tilde{M}R}\otimes\rho_{A^{\prime}TE|(Y=1\land
M=m)\land(F=1)}\otimes[m\bar{m}]\\\
&=\mu_{\tilde{M}R}\otimes\rho_{A^{\prime}TEM\bar{M}|(Y=1)\land(F=1)}.\end{split}$
(62)

This gives that, again using $H=\tilde{M}+M+\bar{M}$,

$\displaystyle\|\rho_{RHMA^{\prime}TE|(Y=1)\land(F=1)}-\mu_{RH}\otimes\rho_{MA^{\prime}TE|(Y=1)\land(F=1)}\|_{\operatorname{Tr}}\leq\varepsilon^{\ast}.$
(63)

As $E^{\prime}=RHA^{\prime}TE$, this implies that

$\displaystyle\begin{split}&\|\rho_{E^{\prime}|(Y=0)\land(F=1)}-\rho_{E^{\prime}|(Y=1)\land(F=1)}\|_{\operatorname{Tr}}\\\
&\leq\|\mu_{RH}\otimes\rho_{A^{\prime}TE|(Y=0)\land(F=1)}-\mu_{RH}\otimes\rho_{A^{\prime}TE|(Y=1)\land(F=1)}\|_{\operatorname{Tr}}+2\varepsilon^{\ast}\\\
&=\|\rho_{A^{\prime}TE|(Y=0)\land(F=1)}-\rho_{A^{\prime}TE|(Y=1)\land(F=1)}\|_{\operatorname{Tr}}+2\varepsilon^{\ast}.\end{split}$
(64)

To finish the proof, we study the state $\rho_{A^{\prime}TEY\land(F=1)}$. The
cloning attack and the first decryption step takes
$\rho_{A^{\prime}T\bar{M}VSY}$ to $\rho_{A^{\prime}TEY\land(F=1)}$ via a trace
non-increasing channel. Therefore, if we have
$\rho_{A^{\prime}T\bar{M}VS|(Y=0)}=\rho_{A^{\prime}T\bar{M}VS|(Y=1)}$, then
$\rho_{A^{\prime}TE|(Y=0)\land(F=1)}=\rho_{A^{\prime}TE|(Y=1)\land(F=1)}$. To
that end,

$\displaystyle\rho_{A^{\prime}T\bar{M}VSY}$
$\displaystyle=\frac{1}{2}\sum_{m}\operatorname*{\mathchoice{\raisebox{-10.00012pt}{\leavevmode\resizebox{18.9231pt}{10.00012pt}{\hbox{\raisebox{0.0pt}{$\displaystyle\vphantom{\mathbb{E}}\text{\raisebox{0.3pt}{\scalebox{0.9}{$\mathbb{E}$}}}$}}}}}{\raisebox{-10.00012pt}{\leavevmode\resizebox{18.9231pt}{10.00012pt}{\hbox{\raisebox{0.0pt}{$\textstyle\vphantom{\mathbb{E}}\text{\raisebox{0.3pt}{\scalebox{0.9}{$\mathbb{E}$}}}$}}}}}{\raisebox{-7.00009pt}{\leavevmode\resizebox{13.24615pt}{7.00009pt}{\hbox{\raisebox{0.0pt}{$\scriptstyle\vphantom{\mathbb{E}}\text{\raisebox{0.3pt}{\scalebox{0.9}{$\mathbb{E}$}}}$}}}}}{\raisebox{-5.00006pt}{\leavevmode\resizebox{9.46153pt}{5.00006pt}{\hbox{\raisebox{0.0pt}{$\scriptscriptstyle\vphantom{\mathbb{E}}\text{\raisebox{0.3pt}{\scalebox{0.9}{$\mathbb{E}$}}}$}}}}}}_{a,t,t^{\prime},r,h}[at]\otimes[m+e(t^{\prime},r)+h]\otimes\vphantom{a_{t,t^{\prime}}}\left\lvert\smash{a_{t,t^{\prime}}}\middle\rangle\\!\middle\langle\smash{a_{t,t^{\prime}}}\right\rvert\otimes\left\lparen\delta_{m,m_{0}}\rho_{S}\otimes[0]+p_{m}\rho^{m}_{S}\otimes[1]\right\rparen$
$\displaystyle=\frac{1}{2}\operatorname*{\mathchoice{\raisebox{-10.00012pt}{\leavevmode\resizebox{18.9231pt}{10.00012pt}{\hbox{\raisebox{0.0pt}{$\displaystyle\vphantom{\mathbb{E}}\text{\raisebox{0.3pt}{\scalebox{0.9}{$\mathbb{E}$}}}$}}}}}{\raisebox{-10.00012pt}{\leavevmode\resizebox{18.9231pt}{10.00012pt}{\hbox{\raisebox{0.0pt}{$\textstyle\vphantom{\mathbb{E}}\text{\raisebox{0.3pt}{\scalebox{0.9}{$\mathbb{E}$}}}$}}}}}{\raisebox{-7.00009pt}{\leavevmode\resizebox{13.24615pt}{7.00009pt}{\hbox{\raisebox{0.0pt}{$\scriptstyle\vphantom{\mathbb{E}}\text{\raisebox{0.3pt}{\scalebox{0.9}{$\mathbb{E}$}}}$}}}}}{\raisebox{-5.00006pt}{\leavevmode\resizebox{9.46153pt}{5.00006pt}{\hbox{\raisebox{0.0pt}{$\scriptscriptstyle\vphantom{\mathbb{E}}\text{\raisebox{0.3pt}{\scalebox{0.9}{$\mathbb{E}$}}}$}}}}}}_{a,t,t^{\prime}}[at]\otimes\mu_{\bar{M}}\otimes\vphantom{a_{t,t^{\prime}}}\left\lvert\smash{a_{t,t^{\prime}}}\middle\rangle\\!\middle\langle\smash{a_{t,t^{\prime}}}\right\rvert\otimes\left\lparen\rho_{S}\otimes[0]+\rho_{S}\otimes[1]\right\rparen$
(65) $\displaystyle=\rho_{A^{\prime}T\bar{M}V}\otimes\rho_{S}\otimes\mu_{Y},$

so $\rho_{A^{\prime}T\bar{M}VS|(Y=0)}=\rho_{A^{\prime}T\bar{M}VS|(Y=1)}$,
giving the result. ∎

##  5 Uncloneable Bit Commitment

In this section, we discuss our second application, introduced in Section 1.2.
In Section 5.1, we define uncloneable commitments and provide a construction,
given as 5.3. Finally, in Section 5.2, we prove security of our construction.

###  5.1 Motivation and definitions

We want to extend bit commitment protocols to make them uncloneable — that is
that only the intended recipient can successfully reveal a commitment. First,
we recall a usual definition of bit commitment, as in [KWW12]. The form of
commitment we use allows for strings, not just single bits, to be committed.
Also, it supposes that, in the honest case, a uniformly random string is
chosen to be committed; this however is not a restriction on the general case.

######  Definition 5.1.

A _$(\ell,\varepsilon_{1},\varepsilon_{2},\varepsilon_{3})$ -randomised bit
string commitment (RBC) scheme_ is a pair of interactive protocols between two
parties Alice and Bob: a protocol commit that creates a state $\rho_{YAB}$,
and a protocol reveal that creates a state
$\rho_{YA^{\prime}\hat{Y}FB^{\prime}}$. Here $Y=\mathbb{Z}_{2}^{\ell}$ is a
classical register holding the committed string;
$\hat{Y}=\mathbb{Z}_{2}^{\ell}$ is a classical register holding the revealed
string; $F=\mathbb{Z}_{2}$ is a classical register that indicates whether Bob
accepts (1) or rejects (0) the reveal; and $A,A^{\prime}$ and $B,B^{\prime}$
are additional quantum registers that Alice and Bob hold, respectively. The
scheme additionally satisfies

$\varepsilon_{1}$-correctness

If Alice and Bob are honest, then
$\|\rho_{Y\hat{Y}F}-\sigma_{YYF}\|_{\operatorname{Tr}}\leq\varepsilon_{1}$,
for $\sigma_{YF}=\mu_{Y}\otimes[1]$.

$\varepsilon_{2}$-hiding

If Alice is honest, then after commit,
$\|\rho_{YB}-\mu_{Y}\otimes\rho_{B}\|_{\operatorname{Tr}}\leq\varepsilon_{2}$.

$\varepsilon_{3}$-binding

If Bob is honest, there exists a state $\sigma_{YAB}$ such that
$\|\rho_{YAB}-\sigma_{YAB}\|_{\operatorname{Tr}}\leq\varepsilon_{3}$, and if
reveal is run to get $\sigma_{YA^{\prime}\hat{Y}FB^{\prime}}$,
$\Pr[Y\neq\hat{Y}\land F=1]_{\sigma}\leq\varepsilon_{3}$.

Bit commitment is not possible with no additional assumptions [BS16], so we
need a model with, _e.g._ , computational or storage assumptions in order for
this definition to not be vacuous. Notwithstanding, we can extend the
definition to handle uncloneability as well. We do so by adding an
eavesdropper Eve, from whom Alice wishes to hide her commitment. In order to
check for cloning, the protocol will have an additional check step which is
used to verify whether it is in fact Bob who received the commitment. The
separation of the check step also allows us to consider various models: Eve
can be allowed to freely communicate with Bob prior to that step, but not
afterwards, as Bob could in that case simply give his register that passed the
check to her.

######  Definition 5.2.

A _$(\ell,\varepsilon_{1},\varepsilon_{2},\varepsilon_{3},\delta)$
-uncloneable randomised bit string commitment (URBC) scheme_ is a triple of
protocols between two parties Alice and Bob, eavesdropped by an eavesdropper
Eve: a protocol commit that creates a state $\rho_{YABE}$, a protocol check
that creates a state $\rho_{YGA^{\prime}B^{\prime}E^{\prime}}$, and a protocol
reveal that creates a state
$\rho_{YGA^{\prime\prime}\hat{Y}FB^{\prime\prime}E^{\prime\prime}}$. Here,
$Y=\mathbb{Z}_{2}^{\ell}$ is a classical register holding the committed
string; $\hat{Y}=\mathbb{Z}_{2}^{\ell}$ is a classical register holding the
revealed string; $G=\mathbb{Z}_{2}$ is a classical register that indicates
whether Alice accepts (1) or rejects (0) the check; $F=\mathbb{Z}_{2}$ is a
classical register that indicates whether Bob accepts (1) or rejects (0) the
reveal; and $A,A^{\prime},A^{\prime\prime}$, $B,B^{\prime},B^{\prime\prime}$,
and $E,E^{\prime},E^{\prime\prime}$ are additional quantum registers that
Alice, Bob, and Eve hold, respectively. The scheme additionally satisfies

$\varepsilon_{1}$-correctness

If Alice and Bob are honest, and Eve does not act, then
$\|\rho_{YG\hat{Y}F}-\sigma_{YGYF}\|_{\operatorname{Tr}}\leq\varepsilon_{1}$,
where $\sigma_{YGF}=\mu_{Y}\otimes[1]\otimes[1]$.

$\varepsilon_{2}$-hiding

If Alice is honest, then after commit,
$\left\|\rho_{YBE}-\mu_{Y}\otimes\rho_{BE}\right\|_{\operatorname{Tr}}\leq\varepsilon_{2}$,
and after check,
$\left\|\rho_{YB^{\prime}E^{\prime}}-\mu_{Y}\otimes\rho_{B^{\prime}E^{\prime}}\right\|_{\operatorname{Tr}}\leq\varepsilon_{2}$.

$\varepsilon_{3}$-binding

If Bob is honest, there exists a state $\sigma_{YABE}$ such that
$\|\rho_{YABE}-\sigma_{YABE}\|_{\operatorname{Tr}}\leq\varepsilon_{3}$ and
$\Pr[Y\neq\hat{Y}\land F=1]_{\sigma}\leq\varepsilon_{3}$.

$\delta$-uncloneability

If Alice is honest,
$\left\|\rho_{YE^{\prime\prime}\land(G=1)}-\mu_{Y}\otimes\rho_{E^{\prime\prime}\land(G=1)}\right\|_{\operatorname{Tr}}\leq\delta$.

From this definition, we see that uncloneability holds for any malicious Bob,
even one who colludes with Eve, as long as they do not communicate after the
check. Similarly to interactive uncloneable encryption, the commitment can be
seen as not having an intended recipient prior to the check step — in
particular, Bob and Eve may have arbitrary communication before then. This
illustrates an important aspect of the uncloneability, as only Bob will be
able to open despite a lack of an agreement between him an Alice, such as a
pre-shared secret key.

######  Remark.

Note that the above definitions do not hold as given in the computational
setting. However, it is straightforward to adapt them by replacing the
supremum in the trace norm $\|A\|_{\operatorname{Tr}}=\sup_{0\leq
P\leq\mathbb{I}}\operatorname{Tr}(PA)$ with the distinguishing advantage
corresponding to a computationally-bounded guessing strategy. This allows
adaptation to a wide range of computational settings where different
computational assumptions that give rise to commitments can be considered. For
simplicity, we use the trace norm definition to prove security of our URBC
construction, but the proofs work as well in such computational settings
simply because the trace norm upper bounds any seminorm given as a supremum
over fewer operators. Nevertheless, in our instantiation, the information-
theoretic nature of the uncloneability property may be preserved as this does
not depend on the choice of commitment assumption.

Now, we can define a candidate URBC scheme. We do so by taking an RBC scheme
and turning it into an uncloneable one on polynomially shorter bit strings
using the leaky MoE property, implicitly working under the assumptions that
are required for the commitment.

Let $c=(\texttt{commit}_{0},\texttt{reveal}_{0})$ be a
$(k+\ell,\varepsilon_{1},\varepsilon_{2},\varepsilon_{3})$-RBC scheme, let $A$
be the set of all subspaces of $V=\mathbb{Z}_{2}^{n}$ of dimension $n/2$, let
$e:\mathbb{Z}_{2}^{n/2}\times\mathbb{Z}_{2}^{k}\rightarrow\mathbb{Z}_{2}^{\ell}$
be a quantum-proof $(\kappa,\varepsilon^{\prime})$-strong extractor, and let
$C\subseteq\mathbb{Z}_{2}^{n/2}$ be an $(n/2,n/2-s,d)$-linear error-correcting
code with syndrome
$\operatorname{syn}:\mathbb{Z}_{2}^{n/2}\rightarrow\mathbb{Z}_{2}^{s}$.

######  Protocol 5.3 (Uncloneable bit string commitment).

Commit Let $R=\mathbb{Z}_{2}^{k}$, $H=\mathbb{Z}_{2}^{\ell}$, and
$T=T^{\prime}=\mathbb{Z}_{2}^{n/2}$. Alice and Bob commit to $(r,h)\in R\times
H$ using $c$. Then, Alice samples $a\in A$, $t\in T$, and $t^{\prime}\in
T^{\prime}$ uniformly at random, after which she prepares the state $\lvert
a_{t,t^{\prime}}\rangle$ and sends it to Bob. Alice stores $t,t^{\prime},a$
and Bob stores $\lvert a_{t,t^{\prime}}\rangle$, and they both store what is
needed to reveal the commitment of $(r,h)$. Check Alice sends Bob $a$ and he
measures in the coset state basis to get measurements
$\hat{t},\hat{t}^{\prime}$ of $t,t^{\prime}$, then sends $\hat{t}$ to Alice.
If $\hat{t}=t$, Alice sets $g=1$, else she sets $g=0$. Alice stores
$t^{\prime}$ and Bob stores $\hat{t}^{\prime}$, and they both store what is
needed to reveal the commitment of $(r,h)$. Reveal Bob selects a random subset
$j\subseteq\\{1,\ldots,n/2\\}$ of cardinality $\eta n/2$ and sends it to
Alice. She replies with $\operatorname{syn}(t^{\prime})$ and $t^{\prime}_{j}$.
Then, they reveal the commitment $c$ to get $(\hat{r},\hat{h})$. If
$\mathrm{syn}(\hat{t}^{\prime})=\mathrm{syn}(t^{\prime})$,
$t^{\prime}_{j}=\hat{t}^{\prime}_{j}$, and $\texttt{reveal}_{0}$ accepts
($f_{0}=1$), Bob sets $f=1$; else he sets $f=0$. Alice’s output is
$e(t^{\prime},r)+h$ and Bob’s output is $e(\hat{t}^{\prime},\hat{r})+\hat{h}$.

This protocol is illustrated in Fig. 3.

AliceBob$\lvert a_{t,t^{\prime}}\rangle$$r,h$ (a) The protocol commit

AliceBob$a$$\hat{t}$ (b) The protocol check

AliceBob$r,h$$j$$\operatorname{syn}(t^{\prime}),t^{\prime}_{j}$$e(t^{\prime},r)+h$$e(\hat{t}^{\prime},\hat{r})+\hat{h}$
(c) The protocol reveal

Figure 3: Illustration of the commitment protocol 5.3. Solid arrows represent
transmission of quantum states, double arrows represent transmission of
classical information, dashed arrows represent commitment and opening, and
dotted lines represent other interactions involved in the commitment without
transmission of relevant information.

###  5.2 Security proofs

######  Proposition 5.4.

5.3 is $\varepsilon_{1}$-correct.

###### Proof.

We suppose Alice and Bob are honest, and Eve does not act. First, Alice and
Bob run $\texttt{commit}_{0}$ to get $\rho_{RHA_{0}B_{0}}$. Then, in the
commit and check phases, Alice sends $\lvert a_{t,t^{\prime}}\rangle$ and $a$
to Bob, and he is able to measure $t,t^{\prime}$ exactly, so $\hat{t}=t$ and
$\hat{t}^{\prime}=t^{\prime}$. Bob sends $\hat{t}$ to Alice, and she sets
$g=1$. At that point, the shared state has the form
$\rho_{RHA_{0}B_{0}T^{\prime}\hat{T}^{\prime}G}=\rho_{RHA_{0}B_{0}}\otimes\sigma_{T^{\prime}T^{\prime}}\otimes[1]$
for $\sigma_{T^{\prime}}=\mu_{T^{\prime}}$. Next, in the reveal phase, we have
that $\mathrm{syn}(\hat{t}^{\prime})=\mathrm{syn}(t^{\prime})$ and
$\hat{t}_{j}^{\prime}=t_{j}^{\prime}$, so Bob’s flag $f=f_{0}$. When Alice and
Bob run $\texttt{reveal}_{0}$, the shared state becomes