(Quantum) Min-Entropy Resources
Christopher Portmann∗1,2

arXiv:1705.10595v1 [quant-ph] 30 May 2017

1
2

Institute for Theoretical Physics, ETH Zurich, 8093 Zurich, Switzerland.
Department of Computer Science, ETH Zurich, 8092 Zurich, Switzerland.

May 31, 2017

Abstract
We model (interactive) resources that provide Alice with a string
X and a guarantee that any Eve interacting with her interface of
the resource obtains a (quantum) system E such that the conditional
(smooth) min-entropy of X given E is lower bounded by some k,
δ
Hmin
(X|E) ≥ k. This (abstract) resource speciﬁcation encompasses
any setting that results in the honest players holding such a string
(or aborting). For example, it could be constructed from, e.g., noisy
channels, quantum key distribution (QKD), or a violation of Bell inequalities, which all may be used to derive bounds on the min-entropy
of X.
As a ﬁrst application, we use this min-entropy resource to modularize key distribution (KD) schemes by dividing them in two parts,
which may be analyzed separately. In the ﬁrst part, a KD protocol constructs a min-entropy resource given the (physical) resources available
in the speciﬁc setting considered. In the second, it distills secret key
from the min-entropy resource— i.e., it constructs a secret key resource.
We prove security for a generic key distillation protocol that may use
any min-entropy resource. Since the notion of resource construction is
composable — security of a composed protocol follows from the security of its parts — this reduces proving security of a KD protocol (e.g.,
QKD) to proving that it constructs a min-entropy resource.
As a second application, we provide a composable security proof
for the recent Fehr-Salvail protocol [EUROCRYPT 2017] that authenticates classical messages with a quantum message authentication code
(Q-MAC), and recycles all the key upon successfully verifying the authenticity of the message. This protocol uses (and recycles) a nonuniform key, which we model as consuming and constructing a minentropy resource.
∗

chportma@ethz.ch

1

1

Introduction

When formalizing information processing systems, one models the information that matters, e.g., the input and output values of the system. A concrete
implementation is much more complex, e.g., values are output at certain
times, encoded in some physical form. If the exact physical encoding or
timing information is not considered relevant, this is generally not modeled
as part of the abstract representation of the information processing system.
Such a model can be described as a specification of a system, since it speciﬁes
certain behaviors that the system must have, but leaves many (irrelevant)
parameters unspeciﬁed.
The level of speciﬁcation of information processing systems found in
the literature is often ﬁxed, e.g., the Universal Composability (UC) framework [1,2] provides a concrete model of systems in terms of interactive Turing
machines, and all objects in the framework must be speciﬁed in the given
language (or something equivalent) with the given level of speciﬁcity. Using
such a framework, one can neither model more speciﬁc objects (e.g., a protocol run at a speciﬁc location in time and space), nor less speciﬁc objects
(e.g., a non-deterministic behavior), and even less compose such objects with
each other.
The Abstract Cryptography (AC) framework [3] uses a top-down approach to model cryptographic security, which does not have this limitation.
The more traditional bottom-up approach starts with a concrete model of
information processing systems, then deﬁnes how these systems communicate, how scheduling is performed, how parties are corrupted, etc. Instead
of this, AC starts on the most abstract level. It models abstract objects
satisfying certain axioms that are needed to make cryptographic statements.
These objects can then be instantiated with, e.g., diﬀerent models of computation, communication, scheduling, etc. In particular, as done in [4], AC can
be instantiated with a model of resource specifications, where two resources
satisfy a relation R ⊂ S, if R is more speciﬁc than S, i.e., any concrete system
satisfying the speciﬁcations of R also satisﬁes those of S. Such resource speciﬁcations can be composed and a security statements about the composed
system may be derived from the framework.

1.1

Contributions

Our main contribution is to use the concept of resource speciﬁcations [3–6]
to model min-entropy resources, i.e., systems that provide honest player(s)
with a random string X and an adversary with a (possibly quantum) system
E such that the joint state ρXE has bounded conditional (smooth) minδ (X|E) ≥ k. The same techniques could be used for other
entropy,1 Hmin
ρ
entropy measures. The reason we choose the smooth min-entropy, is that
1

A formal definition of smooth min-entropy is provided in Appendix A.3.

2

it has many applications in cryptography, e.g., it caracterizes the maximum
amount of secret key that can be extracted from a source [7].
Speciﬁcations are essential in modeling min-entropy resources, since we
generally do not know (and do not care) how the joint state ρXE was generated — whether the adversary can inﬂuence it or not, whether this is done
with one round or multiple rounds of interaction. Any system which interacts arbitrarily with the adversary, but provides a random string X to the
honest player(s) with a guaranteed lower bound on its conditional min-entropy satisﬁes the speciﬁcation, and can be used by protocols requiring such
a bound.
We then present two applications in which these min-entropy speciﬁcations are needed to model the security of cryptographic schemes. In the ﬁrst,
we show how to distill secret key from any min-entropy resource shared between two players. The protocol is standard, it uses error correction and
privacy ampliﬁcation to construct a secret key resource. But the proof is not
restricted to a certain context or speciﬁc source of randomness, it is valid
for any min-entropy resource, e.g., whether it is constructed by noisy classical channels [8–10], standard quantum key distribution (QKD) [7, 11–14] or
even untrusted (but non-communicating) devices [15–18]. We discuss this
application further in Section 1.2.
Our second application is to provide a composable security proof for a
recent authentication protocol by Fehr and Salvail [19,20], that encodes classical messages in quantum states. Due to the quantum properties of these
states, all of the secret key used in the protocol can be recycled once the
recipient has conﬁrmed the authenticity of the message. But a small loss
of entropy occurs in the key, so it cannot be modeled as a standard (uniform) key resource [21]. Instead, we model the shared key as a min-entropy
speciﬁcation, and prove that a slightly modiﬁed version [20] of the original
Fehr-Salvail protocol [19] uses a min-entropy resource and an insecure channel to construct an authentic channel and a new min-entropy resource (the
recycled key). This result is discussed further in Section 1.3.

1.2

Distilling Secret Key

Secret key distillation from a joint probability distribution PXY E between
three players, Alice, Bob, and Eve, was proposed independently by Maurer [8] and by Ahlswede and Csiszár [9]. This problem has since been generalized to many diﬀerent contexts, e.g., in a ﬁnite setting [10], when E
is quantum and the tripartite state ρXY E has been obtained from a QKD
protocol [7,12–14], or in a device-independent setting, where the devices generating ρXY E are untrusted [17, 18]. The protocols always follow the same
pattern: if needed, one performs some advantage distillation to increase the
correlations between the honest players, then one performs error correction
so that they share the same strings, and ﬁnally privacy amplification to ex3

tract a secret key. The diﬀerent security proofs found in the literature that
one can obtain secret key given a bound on the correlations of the state
ρXY E are very similar, with (small) variations to account for the changes in
context.
This overlap between diﬀerent works can be avoided by employing a
modular (composable) approach: a task is divided in diﬀerent parts, and the
security of each part is proven separately. Thus, if one part is changed, only
that piece requires a new security proof; the new piece can then be seamlessly
plugged into the other parts. The AC framework [3, 4] formalizes this as a
resource theory: a cryptographic protocol uses some resource speciﬁcation
R to construct some other resource speciﬁcation S. Diﬀerent protocols may
be used to construct S in diﬀerent ways. The next part of a cryptosystem
may use S to construct T, and is oblivious to how S was constructed. The
piece constructing S may be changed at will, without aﬀecting anything else.
More concretely, we prove in this work that a min-entropy resource may
be used to construct a secret key resource — using the aforementioned steps
of error correction and privacy ampliﬁcation. As a consequence, informationtheoretic key distribution protocols (e.g., QKD) do not need to show that
they produce secret key (and needlessly repeat many of the steps), it is
suﬃcient to prove that they construct a min-entropy resource, i.e., that
they generate a raw key with a bound on its min-entropy. Bounds on the
security of the ﬁnal key then follow generically from the composability of
the AC framework by plugging this into our work.
This also provides clear conditions on the min-entropy of the raw key
that are suﬃcient for the error correction and privacy ampliﬁcation to go
through (namely, that the constructed resource corresponds to a min-entropy
speciﬁcation, which we deﬁne in Section 3).

1.3

Quantum Authentication of Classical Messages

As far back as 1982, Bennett, Brassard, and Breidbart [22] discussed how
one could authenticate a classical message in a quantum state, so that after
conﬁrming reception of the original message, the secret key used by the protocol can be reused. A recent breakthrough result by Fehr and Salvail [19,20]
showed how to do this with a prepare-and-measure protocol, i.e., one which
involves only preparing and measuring single qubit states, and which could
already be implemented with today’s technology [23]. This has many interesting applications, e.g., it could be used as a subroutine for authenticating
messages in QKD.2 One would then not need to sacriﬁce any key bits for
authentication.
Fehr and Salvail use a trace-distance-type security criterion that is tailored for substitution attacks — Eve changes the message being sent. They
2
Whether this application is practical depends on the noise tolerance of the Fehr-Salvail
protocol, which was has not been worked out [19].

4

then show that this criterion is suﬃcient to prove that their protocol can
be composed sequentially with itself. Diﬀerent contexts, such as sequential
composition with other protocols,3 parallel composition,3 or impersonation
attacks — Eve sends a forged cipher to Bob without knowledge of a valid
message-cipher pair — were not explicitly considered in [19].4 When key
recycling is involved, impersonation attacks are particularly powerful, because they allow Eve to obtain part of the recycled key after Bob receives
the forged cipher (e.g., he uses it in a protocol which leaks it, like a onetime pad), which she can use to generate a message correlated to the key
and provide it to Alice for authentication. The resulting cipher could then
potentially leak more information about the remaining secret key than a cipher prepared by Alice under a substitution attack, where the message and
key are independent. Note that even if the protocol is only composed in a
restricted setting in which the recycled key is not leaked, the accept/reject
bit of the receiver is generally correlated to the recycled key and cannot be
hidden, which leads to the same type of attacks.
This raises the question of whether there are other attacks or vulnerabilities that have not been considered, and what security criteria must be
satisﬁed for the protocol to be usable, e.g., as a subroutine in QKD. This
is answered in a generic way by composable frameworks. In the AC language, a QKD protocol uses an authentic channel resource speciﬁcation A
for the players to communicate [21]. A standard authentication scheme that
appends a message authentication code (MAC) to the message constructs
such an authentic channel A [24]. And hence, by the composition theorem
of the framework, the two may be composed, and the total error is the sum
of the errors of the individual protocols.
In this work we perform such a composable analysis for a slightly modiﬁed version [20] of the original Fehr-Salvail protocol [19]. We show that
k , a uniform key resource K,
this protocol uses a min-entropy resource Hmin
k , a
and an insecure channel Q to construct a new min-entropy resource Hmin
new uniform key K, and an authentic channel A. The constructed channel
A may then be used by any protocol requiring such a resource, while the
k
constructed key resources Hmin
and K (the recycled keys) may be plugged
3
Ad hoc security definitions for individual protocols — e.g., trace-distance-type criteria — do not necessarily guarantee that a composed protocol is secure. When using such
definitions, one needs to additionally prove (for every different context) that the protocol
can be safely used, and work out the corresponding error. For example, Fehr and Salvail
do this for sequential composition of their protocol with itself [19]. This can be avoided
by using composable security definitions — e.g., the notion of resource construction from
AC — which guarantee security in any environment. The error of the composed protocol
is then the sum of the erros of the individual components.
4
Following an initial draft of the current work pointing out the issue with impersonation
attacks and proposing a solution that recycles less key in the case of a reject, an extended
version of the Fehr-Salvail paper was made available [20], which sketches how the protocol
can be modified to resist impersonation attacks without any extra loss of key.

5

into the next round of authentication — or any other protocol requiring such
keys.

1.4

Structure of the paper

We start by introducing the AC framework in Section 2, where we instantiate
the systems with resource speciﬁcations. In Section 3 we then deﬁne the
min-entropy speciﬁcations that are used throughout this work. In Section 4
we show how to distill secret key from such a min-entropy resource. And
in Section 5 we provide a composable security proof for the Fehr-Salvail
authentication protocol, in which the non-uniform keys are modeled as minentropy resources.

2

Constructive Cryptography

The AC framework [3, 4] models cryptography as a resource theory, e.g., a
QKD protocol constructs a secret key resource from an authentic channel
and an insecure quantum channel. More generally, a security statement is
a constructive statement of the form “γ constructs S from R with error ε,”
which we denote
γ,ε
R −−→ S.
(1)
For this reason the framework is also called constructive cryptography in the
literature [4, 25].
In (1), R and S are resource speciﬁcations denoting the resources that are
used by the construction and the ones that are achieved by the construction
γ, respectively. Naturally, if γ constructs S from R and π constructs T from
S, then one expects that applying both constructions in sequence constructs
T from R with an error which is the sum of the individual errors, i.e.,
γ,ε

R −−→ S and

π,δ

π◦γ,ε+δ

S −−→ T =⇒ R −−−−−→ T.

(2)

Similarly, if γ1 constructs S1 from R1 and γ2 constructs S2 from R2 , then
one expects that if resources R1 and R2 are both available simultaneously,
and one applies both constructions, this should result in the resources S1
and S2 both being constructed, i.e.,
γ1 ,ε1

R1 −−−→ S1

γ1 |γ2 ,ε1 +ε2

γ2 ,ε2

and R2 −−−→ S2 =⇒ R1 kR2 −−−−−−−→ S1 kS2 .

(3)

In the rest of this section we formalize the notions of resource speciﬁcations and construction, which allows us to deﬁne constructive security
statement such as Eq. (1) and prove that Eqs. (2) and (3) hold with this
notion of construction. We do this following the AC top-down approach, i.e.,
we only deﬁne the properties of the objects that are needed, allowing them
to be instantiated with any concrete model that satisﬁes these properties.
6

Depolarizing channels Rp
Eλ (ρ)
ρ

Noiseless channel Sid
ρ

ρ

(b) Any depolarizing channel given
by Eλ (ρ) = (1 − λ)ρ + λd I, where λ ≤
p.

(a) A noiseless channel.

Figure 1 – Two examples of resource speciﬁcations. (a) is a speciﬁcation that
contains one channel, the identity. (b) is a speciﬁcation for any depolarization
channel with λ ≤ p.

2.1

Specifications

As mentioned in Section 1, a speciﬁcation can be thought of as a (partial)
description of an object to the accuracy needed for the task at hand. This
concept is much more general than modeling cryptographic systems, and
has been used to model resource theories in physics [5, 6]. For example, let
S denote a chair. A chair with wheels R is more speciﬁc than a chair. We
thus have R ⊂ S, where ⊂ is a transitive relation meaning “more speciﬁc
than”. A piece of furniture T is less speciﬁc, hence T ⊃ S. As another
example, consider instructions for building a model car, which state that a
piece should be painted. Let R denote the pair of the piece from the model
car and some paint, and let γ denote the action of painting the piece. Then
given R, γ constructs a painted piece S. When actually building the model
car, the paint chosen will have a certain color, e.g., red. Let R′ denote the
pair of the piece from the model car and red paint. We then have R′ ⊂ R,
because R′ is more speciﬁc than R. And applying γ to R′ we obtain S′ ⊂ S,
where S′ is the piece of the car painted red. The instructions apply to
anything that satisﬁes the speciﬁcations, in particular, to objects that are
more speciﬁc.
We deﬁne speciﬁcations as in [4]: a speciﬁcation is a subset of a universe
Φ of objects, namely those that satisfy the speciﬁcation. The relation R ⊂ S
for R, S ∈ P(Φ) is then simply the subset relation, where P(Φ) denotes the
power set of Φ.5 We call the elements R ∈ Φ atomic resources, and the
speciﬁcations R ∈ P(Φ) are resource specifications.
As two examples, we have illustrated in Figure 1 speciﬁcations for noiseless and noisy channels. Here the atomic resources correspond to individual
channels deﬁned by their input and output behavior, and the speciﬁcation
denotes any set of channels satisfying the speciﬁcation, e.g., depolarizing
channels with noise λ ≤ p as in Figure 1b.
5

Specifications are more general than this, and may be instantiated in other ways than
with sets.

7

Depolarizing ch. Rp
ρ

α

σ

σ̃

β

ρ̃

Figure 2 – Error correction converters α and β are applied to Alice and Bob’s
interfaces of the channel speciﬁcation Rp .

2.2

Converters

To model cryptographic protocols, we consider resources that have interfaces,
where each interface can be accessed by one user. For example, the channel
speciﬁcations from Figure 1 have an input interface and an output interface,
with which the sender (Alice) and receiver (Bob) may interact — to send
and receive messages, respectively. We usually label interfaces so as to make
explicit who controls the interface, e.g., A, B, E, for Alice, Bob, and Eve.
A local operation performed at one interface is called a converter. For
example, Alice may encode her message with a converter α and Bob may
decode it with a converter β, as drawn in Figure 2. Formally, we consider a
set of objects Σ, called converters, which are functions mapping a resource
speciﬁcation to another speciﬁcation, i.e., α : P(Φ) → P(Φ) for α ∈ Σ.
For example, the resource constructed in Figure 2 is given by β(α(Rp )) —
or, equivalently, α(β(Rp )) — which we simply write βαRp (or αβRp ). We
usually draw converters with rounded corners.
We often use subscripts to denote the interface to which a converter applies, e.g., βB αA Rp . Converters applied at diﬀerent interfaces must commute
(as in Figure 2), i.e.,
βB αA R = αA βB R.
Composition of converters, β ◦ α, is deﬁned by
(β ◦ α)R := β(αR).
Converters must conserve the speciﬁcity relation, i.e.,
R ⊂ S =⇒ αR ⊂ αS.
The set Σ must also be closed under composition and contain an identity
element id ∈ Σ satisfying
id ◦α = α ◦ id = α.
In this work we usually write converters for honest players on the left of the
resources, and converters for dishonest players on the right, i.e., we write
αA RσE instead of σE αA R, where E denotes Eve’s interface.
Note that a set of converters Σ that are maps α : Φ → Φ on the set of
atomic resources satisfying the properties above immediately induces a set
of converters on resource speciﬁcations with
αR := {αR : R ∈ R}.
8

2.3

Approximations

After constructing the resource βαRp illustrated in Figure 2, one typically
wants to state that it approximately corresponds to a noiseless channel Sid ,
i.e., βαRp ⊂ Sεid , where Sεid is an ε-ball around Sid containing any channel
that is ε-close to Sid . Such an ε-ball is deﬁned with respect to a pseudometric on atomic resources, d : Φ × Φ → R+ ,
Rε := {S ∈ Φ : ∃R ∈ R, d(R, S) ≤ ε}.

It follows from the triangle inequality of the pseudo-metric that
(Rε )δ ⊂ Rε+δ .
Furthermore, if the pseudo-metric is contractive, i.e., for any α ∈ Σ and any
R, S ∈ Φ, d(αR, αS) ≤ d(R, S), then
αRε ⊂ (αR)ε .

2.4

Resource Composition

If two resources R and S are simultaneously accessible to the players, we wish
to write this as one resource corresponding to the (parallel) composition of
both, i.e., they are merged into one resource such that the interfaces of
each resource are simultaneously available to each player. To do this, we
deﬁne a parallel composition operation on resource speciﬁcations k : P(Φ) ×
P(Φ) → P(Φ) and write RkS for the resulting speciﬁcation. For example, a
quantum key distribution (QKD) protocol usually requires two resources to
be available to the players: an insecure quantum channel Q and a (multiple
use, two-way) authentic classical channel Ac .6 As drawn in Figure 3, the
channel Q just delivers the (quantum) message to Eve and allows her to
replace it with an arbitrary message that is sent to Bob. The channel Ac
faithfully delivers (classical) messages between Alice and Bob, but provides
Eve with copies.7 The players thus have access to the resource Ac kQ and
qkd
qkd 8
run their protocol corresponding to a pair of converters (πA
, πB
). The
qkd qkd
c
constructed system is given by the speciﬁcation πB πA (A kQ).
6
The superscript c in Ac represents the number of uses of the channel, which we usually
denote by an unspecified constant c.
7
In order to satisfy the requirement of sequential scheduling for the specific instantiation
of atomic resources with quantum combs (see Appendix B.1, in particular, Remark B.1),
Ac does not immediately output two messages at Eve’s and the receiver’s interfaces. Ac
outputs a single message at the receiver’s interace. Upon a request from Eve at her
interface, it then gives her a copy of the messages that were sent. To simplify Figure 3,
we do not draw the extra “request arrows”, but only the information that is output by
the systems. These requests are not needed for an instantiation of systems such as causal
boxes that supports more complex scheduling (see Appendix B.2).
qkd
qkd
8
Similarly to the authentic channel Ac , πA
and πB
do not spontaneously output the
key generated, they wait for a request to output it. Furthermore, the protocol starts with
qkd
πA
being activated at its outer interface, which is not drawn in Figure 3 either.

9

qkd
πA

t
kA , ⊥

Alice

qkd
πB

Authentic channel Ac
t

kB , ⊥

Insecure channel Q

ρ

Bob

ρ′

t

Eve
Figure 3 – The real QKD setting, with Alice on the left, Bob on the right and
Eve below. Resources Ac and Q are available to the honest players, who run
qkd
qkd
their protocol (πA
, πB
). At the end of this they either hold keys (kA , kB )
or produce an error ⊥.

This notion of parallel composition of resources induces a notion of parallel composition of converters α|β, deﬁned as
(α|β)(RkS) := (αR)k(βS).
We require k to be associative, and when multiple resources are in parallel,
we add subscripts to the resources and converters to clarify how they connect,
e.g, (α1 |β23 )(R1 kS2 kT3 ) — or (αA1 |βB23 )(R1 kS2 kT3 ) when we additionally
need to denote the interface to which the converters connect. Naturally, we
also require that the speciﬁcity relation be conserved, i.e.,
R ⊂ S =⇒ RkT ⊂ SkT

and

TkR ⊂ TkS.

As for converters, if an operation k with the same properties is deﬁned
on atomic resources, then this yields a parallel composition operation on
speciﬁcations, deﬁned as
RkS := {RkS : R ∈ R, S ∈ S}.
And if the pseudo-metric is context-insensitive, i.e., for any atomic resources
R, S, T ∈ Φ, d(RkT, SkT) ≤ d(R, S) and d(TkR, TkS) ≤ d(R, S), then
Rε kS ⊂ (RkS)ε

2.5

and

RkSε ⊂ (RkS)ε .

Cryptographic Security

In a context where some players are dishonest, one typically does not have
an exact description of how they may inﬂuence a protocol outcome, but one
has an upper bound on what they can do. For example, in the case of QKD,
one would ideally construct a secret key resource K that at most allows the

10

Secret key K
Alice

k, ⊥

k, ⊥

Bob

key
0, 1
Eve
Figure 4 – A secret key resource that allows Eve to decide if Alice and Bob
get a uniform key or an error message.10

adversary, Eve, to decide if the players get a key or not,9 but not get any
information about the value of the key, as drawn in Figure 4.10
In reality, Eve might have less power than this, e.g., she decides that
the players should get the key, but the protocol aborts nonetheless. This, of
course, is also an acceptable resource to construct, since it is stronger than
K — it is stronger (for the honest players), because Eve has less inﬂuence
over the outputs. More precisely, any resource KσE is an acceptable ideal
resource for QKD, since anything achieved by it can be achieved by K if Eve
decides to run σE at her interface. A speciﬁcation of an ideal key resource
that (at most) allows Eve to provoke an abort is thus given by
K∗ := {KσE : σ ∈ Σ}.
We are now ready to deﬁne the notion of construction in the special case
of three party protocols with honest Alice and Bob and dishonest Eve.
Definition 2.1 (Cryptographic security [3, 4]). We say that a protocol π =
(πA , πB ) constructs a resource speciﬁcation S from the speciﬁcation R with
error ε, which we denote
π,ε
R −−→ S,
if

πB πA R ⊂ (S∗ )ε .

(4)

One will often want to make several statements about a protocol, e.g.,
π,ε

π,ε′

R −−→ S and R −−→ S, where R and S might be the resources in case of
an active adversary (e.g., Eve can arbitrarily modify the communication
9

Ideally one would want Eve to not even have the possibility of preventing the players from getting the key. But this cannot be achieved, since Eve can always cut the
communication in the real system.
10
To preserve a sequential execution of the systems, the key resource is defined so
that upon inputing her bit, Eve receives a confirmation from K. The players may then
individually send a request to the resource, and get either their key or an error. To simplify
the picture, only the actual information transmitted is drawn in Figure 4. Request and
confirmation arrows have been omitted.

11

between Alice and Bob), and R and S are resources in case no adversary is
present (e.g., there is only non-malicious noise on the channels). One then
typically has R ⊂ R∗ and S ⊂ S∗ , i.e., if we can say something more speciﬁc
about the resources available (e.g., speciﬁc noise model), then we can make
strong statements about the constructed resource (e.g., a key is produced
with probability 1 − ε).
Note that in order to prove that Deﬁnition 2.1 is satisﬁed by a protocol
π, it is suﬃcient to prove that for every R ∈ R there exists an S ∈ S and
σ ∈ Σ such that
d(πB πA R, SσE ) ≤ ε,
(5)
since this implies that Eq. (4) holds. The exact σE used in the security proof
will be called simulator. In the following, we often write R ≈ε S instead of
d(R, S) ≤ ε, e.g., Eq. (5) becomes
πB πA R ≈ε SσE .
We now prove that this deﬁnition of construction is composable — i.e.,
Eqs. (2) and (3) are satisﬁed — with the error of the composed construction
that is the sum of the errors of the parts.
Theorem 2.2. If the pseudo-metric d : Φ × Φ → R+ is contractive, then
γ,ε

R −−→ S

and

π,δ

π◦γ,ε+δ

S −−→ T =⇒ R −−−−−→ T.

If, additionally, d is context-insensitive, then
γ1 ,ε1

R1 −−−→ S1

and

γ1 |γ2 ,ε1 +ε2

γ2 ,ε2

R2 −−−→ S2 =⇒ R1 kR2 −−−−−−−→ S1 kS2 .

Proof. Using the properties of converters and ε-balls from Sections 2.2 and
2.3, one has

∗ ε 

δ ε
πγR ⊂ π(S∗ )ε ⊂ (πS∗ )ε ⊂ (T ∗ )δ
⊂ ((T ∗ )∗ )
⊂ (T ∗ )ε+δ .

Additionally using the properties of parallel composition from Section 2.4,
one has
(γ1 |γ2 )(R1 kR2 ) = (γ1 R1 )k(γ2 R2 ) ⊂ (S∗1 )ε1 k(S∗2 )ε2

ε1 +ε2

⊂ (S∗1 kS∗2 )ε1 +ε2 ⊂ ((S1 kS2 )∗ )

2.6

.

Atomic resources

So far we have instantiated the AC framework with speciﬁcations deﬁned
as sets of atomic resources. To model concrete systems (such as those from
Figures 1, 2, 3, 4), we need to instantiate these atomic resources with a model
of interactive systems that captures quantum information-processing. Such
12

a model has been given in [26], where the atomic resources are called causal
boxes, and proven to satisfy the properties required by the AC framework.
The causal box framework [26] allows superpositions of causal structures
to be modeled, e.g., messages can be sent in superpositions of diﬀerent orders
to superpositions of diﬀerent players. In order for this to be possible, one
has to model messages as pairs |v, ti ∈ HV ⊗ HT , where v denotes the value
being sent and t can be understood as a time tag that controls the ordering
of messages. This then allows superpositions of diﬀerent values at diﬀerent
times (or diﬀerent orders), e.g.,
|ψi = |v1 , t1 i + |v2 , t2 i.
Most of the results in the current paper consider simpler resources, that
use (classical) sequential scheduling, i.e, they receive a message, send a message, receive another message, etc. This is the case of all the examples seen
so far in this section. These can be modeled as memory channels or quantum
combs [27–29] (see also [30–32]), i.e., systems with some internal memory M ,
and which upon receiving an input in some register Xi produce a single output in some register Yi by applying a map Ei : L(HXi M ) → L(HM Yi ) which
updates the internal memory and computes the output. Such systems can
be seen as special cases of causal boxes, in which the (unnecessary) time tag
is not written out explicitly.
These two models of quantum information-processing systems — quantum combs and causal boxes — are introduced in detail in Appendix B. In
the following we model all systems as quantum combs, unless stated otherwise.
Regardless of the instantiation, the distance between two atomic resources R and S is taken to be the distinguishing advantage, i.e., a distinguisher D interacts with one of the two and has to guess which one it is
given. The distinguishing advantage is then deﬁned as
d(R, S) := sup|Pr[D(R) = 1] − Pr[D(S) = 1]|,
D

where D(R) is the binary random variable corresponding to the distinguisher’s
guess when interacting with R. In the case of quantum combs the distinguishing advantage corresponds to the trace distance between the two states
held in memory by the distinguisher after interacting with the corresponding
systems [28, 29]. A similar result is derived for causal boxes [26].

3

Min-entropy resources

Before modeling min-entropy speciﬁcations, we ﬁrst consider min-entropy
atomic resources using both the quantum combs [27–29] and causal boxes [26]
models, in Sections 3.1 and 3.2, respectively. We then deﬁne min-entropy
13

start

Hn

S

X

E

Figure 5 – Hn is a (k, δ)-min-entropy comb if for all S the state ρXE satisﬁes
the conditions from Deﬁnition 3.1.

speciﬁcations in Section 3.3, and discuss ε-balls around min-entropy speciﬁcations in Section 3.4.
The quantum notation and concepts used in this section and the following are introduced in Appendix A. The models of quantum combs and
causal boxes are explained in Appendix B.1 and Appendix B.2, respectively.

3.1

Finite dimensional systems

Quantum combs [27–29], by deﬁnition, can only interact a ﬁnite number of
times with their environment, since they are modeled by (the Choi-Jamiolkowski representation of) a ﬁnite dimensional completely positive, tracepreserving (CPTP) map (see Appendix B.1). This is suﬃcient to model
any min-entropy resource that generates the output X after a ﬁxed number
of rounds of interaction (as is the case for the applications to QKD and
authentication considered in this work), or if the systems have a timeout
after which they abort — since in a ﬁnite amount of time a causal system
can only send a ﬁnite number of messages [26].
To model min-entropy atomic resources with combs, we consider a system Hn that is activated by receiving a ﬁxed symbol “start”. It then outputs
a quantum message, receives a quantum message as input, outputs another
message, etc., until a total of n messages have been exchanged with its environment. It then ﬁnally outputs a classical (random) value X from an
alphabet X ∪ {⊥}, where ⊥ is an error symbol denoting that the system
failed to generate an output (with enough entropy). Such a system is illustrated in Figure 5, and is a called a min-entropy comb if it satisﬁes the
following conditions.
Definition 3.1 (Min-entropy comb). Let Hn be a quantum comb with a
structure as described above, and let S be any comb that mirrors it: S
ﬁrst receives a quantum message, then outputs one, etc, for a total of n
interactions, and ﬁnally outputs a quantum system E. We say that Hn is a
(k, δ)-min-entropy comb if for all S, the ﬁnal joint state ρXE is given by
ρXE = |⊥ih⊥| ⊗ τE + σXE
14

(6)

for an arbitrary state τE , and a state σXE satisfying
δ
Hmin
(X|E)σ ≥ k,

(7)

δ (X|E) denotes the δ-smooth conditional min-entropy of σ
where Hmin
σ
XE
and is deﬁned in Appendix A.3, Deﬁnition A.3.

Note that the min-entropy condition in Eq. (7), is deﬁned on the subnormalized state σXE . This is because the min-entropy of the renormalized
state σXE / tr(σXE ) is not meaningful when the probability of not aborting,
tr(σXE ), is very small — one does not care what happens conditioned on
an unlikely event. For a state σXE with tr(σXE ) ≤ 2−k + δ2 /2, Eq. (7) is
trivially satisﬁed.

3.2

Unbounded interactions

The systems deﬁned in Section 3.1 have a ﬁxed number of interactions
(namely n) with the environment. This is necessary if one wants to keep
the joint input and output Hilbert spaces ﬁnite dimensional. One can however imagine more general systems where the number of interactions is a
priori unbounded and depends on the values that are input — or where the
number of interactions is in a superposition of diﬀerent values. We model
this using causal boxes [26].
As explained in Appendix B.2, in the causal box model a message can
be thought of as a pair of a value v ∈ V and a position t ∈ T , where T is a
discrete partially ordered set allowing messages to be ordered with respect to
each other (e.g., T = Q). Let HX = HV ⊗ HT be the corresponding Hilbert
space. An output of a causal box may consist in one message, multiple messages, no messages at all, or any superposition thereof. The corresponding
message space is a Fock space given by
F(HX ) :=

∞
M
n=0

∨ n HX ,

⊗0
⊗n
is the one
, and HX
where ∨n HX denotes the symmetric subspace of HX
dimensional space containing the vacuum state |Ωi.
Thus, a ﬁgure drawing a causal box does not have one arrow for every
output, but instead one arrow for an output wire that many produce an
unbounded number of messages. For example, in Figure 6, the two causal
boxes H and S are connected by two wires, and may be repeatedly exchanging
messages on these wires — these systems are not required to terminate.11
11

Formally, causal boxes are modeled as sequences of maps over ever increasing intervals
of T , see Appendix B.2.

15

start

H

S

X

E

Figure 6 – In the model of causal boxes, each wire may be used an unbounded
number of times to transmit messages, e.g., there is no bound on the number
of rounds of communication between H and S. The system H is a (k, δ)-minentropy causal box if for all S and all t the state ρ≤t
XE satisﬁes the conditions
from Deﬁnition 3.2, where ρ≤t
is
the
state
of
the
XE systems truncated at
XE
position t.

Similar to the model of min-entropy combs, we model a min-entropy
causal box as being started by receiving a corresponding message,12 after
which it interacts with an environment (e.g., the system S drawn in Figure 6).
At any point during this interaction, it may output a value on the wire X
from the alphabet X ∪ {⊥}, where, as above, ⊥ is an error symbol denoting
that the system failed to generate an output (with enough entropy). But
⊗1
⊗0
, i.e., at most one
⊕ HX
we restrict the output on X to the subspace HX
value is output. Unlike for combs, we cannot place a requirement on the
entropy of X once a value is output, since this condition might not be welldeﬁned (e.g., for t ∈ N, a value is produced in position t with probability
2−t ). Instead, we bound the entropy of the output up to position t for all
t∈T.
Definition 3.2 (Min-entropy causal box). Let H be a causal box with a
structure as described above, and let S be any causal box with an input and
output wire that match the dimensions of the output and input wires of H,
and with an additional output wire E, and let them be connected by these
wires. Furthermore, for V T = X, let ρ≤t
V T E be the subnormalized output
on XE up to position t projected on the non-vacuum subspace HV ⊗ HT ⊗
F(HE ). We say that H is a (k, δ)-min-entropy causal box if for all S and all
t ∈ T , the state ρ≤t
V T E is given by
ρ≤t
V T E = |⊥ih⊥| ⊗ τT E + σV T E
for an arbitrary state τT E , and a state σV T E satisfying
δ
Hmin
(V |T E)σ ≥ k.

Note that Deﬁnition 3.2 conditions the entropy of the output on the
register T as well as E, since this ordering information could be learned
12

Technically this is not necessary, a causal box may spontaneously output a message.
But it simplifies the scheduling with other systems to consider only causal boxes that are
started by an external message.

16

by an adversary. Though if one considers only systems where timing is
independent of the values of messages, then it would be suﬃcient to bound
δ (V |E) .
Hmin
σ

3.3

Min-entropy specification

For min-entropy combs and causal boxes (deﬁned in the previous two sections) to be valid atomic resources, one still has to assign interfaces to the
various inputs and outputs. In a model with two interfaces A and E — accessed by Alice and Eve, respectively — the ﬁnal output X occurs at Alice’s
interface, and the interaction with the environment occurs at Eve’s interface. The input “start” may be provided at either Alice or Eve’s interface,
depending on the protocol considered. A min-entropy speciﬁcation is then
simply the set of all min-entropy atomic resources satisfying a certain bound
on the conditional min-entropy.
Definition 3.3 (Min-entropy speciﬁcation). A (k, δ)-min-entropy speciﬁcak,δ
is the set of all (k, δ)-min-entropy atomic resources.
tion Hmin
Deﬁnition 3.3 is typically the min-entropy speciﬁcation one would construct in an adversarial setting: it provides a bound on the entropy, but
not on the actual probability of terminating which such a random string,
since usually Eve can force honest players to abort. If one considers a context where Eve is not active, then one generally wishes to prove something
stronger, e.g., with high probability the protocol generates a random string.
k,δ
to contain
Such a statement can easily be achieved by restricting the set Hmin
only those systems such that for all S, the output ρXE = |⊥ih⊥| ⊗ τE + σXE
has tr(σXE ) ≥ 1 − ε.13
In the two applications considered in this work, we need min-entropy
resources with three interfaces for Alice, Bob, and Eve. These are deﬁned
identically to the two interface versions described so far, except that a string
Y is output at Bob’s interface as well.14 Here, the conditional min-entropy is
always deﬁned on the XE system. The allowed correlations between Y and
XE will depend on the context, e.g., the min-entropy resource constructed
by QKD allows Y to be an arbitrary random string, whereas the min-entropy
resource used as a secret key by the Fehr-Salvail protocol requires Y to be
a copy of X.
13
In the model with causal boxes, one would require that by a certain position t0 ,
≤t0
tr(σXE
) ≥ 1 − ε.
14
As in the examples of systems in Section 2, to preserve sequential scheduling when
the atomic resources are instantiated with quantum combs, the outputs X and Y are not
produced spontaneously, but only after having received a request from Alice and Bob,
respectively.

17

3.4

Approximate min-entropy specifications

In Section 2.3 we deﬁned a notion of an approximate speciﬁcation, directly in
the AC language, by taking an ε-ball around speciﬁcations. The min-entropy
resources deﬁned in Section 3.3 have their own notion of approximation builtin, namely the smoothing parameter δ. This is useful, because (as we prove
in the next lemma) δ-smoothing is a less speciﬁc condition that results in a
larger set of atomic resources than ε-balls.15 It remains open to ﬁnd bounds
ε′

k,δ
k,δ+ε
for some reasonable
⊂ Hmin
in the other direction — i.e., whether Hmin
ε′ — or examples showing that such bounds do not exist.

Lemma 3.4. For min-entropy specifications one has
ε

√
k,δ+ 2ε
k,δ
⊂ Hmin
Hmin
.

Proof. By contradiction, let us suppose there exists an H such that
k,δ+
H∈
/ Hmin

√

2ε

,

(8)

ε

k,δ
.
H ∈ Hmin

(9)

but

From Eq. (8) we ﬁnd that there must exist an S such that the state ρXE =
|⊥ih⊥| ⊗ τE + σXE resulting from S and H interacting has
√

δ+
Hmin

2ε

(X|E)σ < k.

(10)

From Eq. (9) there must exist an H′ ≈ε H such that when interacting with
′
′
the same S, the resulting state ρ′XE = |⊥ih⊥| ⊗ τXE
+ σXE
has
δ
Hmin
(X|E)σ′ ≥ k.

(11)

Since H′ ≈ε H, it follows that D(ρ′XE , ρXE ) ≤ ε, where D(·, ·) is the
trace distance. One then obtains
1 ′
1
D(ρ′XE , ρXE ) =
σXE − σXE tr + τE′ − τE tr
2
2
1
1 ′
σ
− σXE tr + tr τE′ − tr τE
≥
2 XE
2
′
= D̄(σXE , σXE )
′
≥ P (σXE
, σXE )2 /2,

where D̄(·, ·) is the generalized trace distance and P (·, ·) is the puriﬁed distance (see Appendix A.2 and [33]).
Putting this together with Eq. (11) and the triangle inequality, there
√
must exist a σ̃XE such that Hmin (X|E)σ̃ ≥ k and P (σ̃XE , σXE ) ≤ δ + 2ε,
which contradicts Eq. (10).
15

It is currently unknown if it is possible to prove that a QKD protocol constructs the
smaller set of resources without the smoothing parameter.

18

4

Distilling Secret Key

In this section we show how to extract secret key from a tripartite minentropy resource, where Alice and Bob obtain strings X and Y , and Eve
gets side information. In Section 4.1 we show how error correction and
veriﬁcation construct a min-entropy resource which provides Alice and Bob
with identical strings X ′ = Y ′ , given a resource that has no guarantee on
the correlations between X and Y . Then in Section 4.2 the players use
privacy ampliﬁcation to construct a secret key resource (see Figure 4 for
an illustration of a secret key resource). The two steps are composed in
Section 4.3.
These steps of error correction and privacy ampliﬁcation are performed
in a generic way for any resource that satisﬁes the min-entropy speciﬁcation.
We show in Appendix C that QKD is a special case of this, which constructs
a (more speciﬁc) min-entropy resource.

4.1

Error Correction

In this section we analyze a generic class of error correction schemes, which
are now standard in QKD (see, e.g., [12,14]). The error correction procedure
has two steps. In the ﬁrst, Alice applies a function Z = synd(X) which
computes a syndrome for X. She then sends this on an authentic channel to
Bob, who applies the second function X̂ = corr(Y, Z) to get an estimate X̂
of Alice’s string X. Such pairs of functions (synd, corr) are parametrized by
two values: by a subset S ⊂ X × X of strings that they can correct, i.e, for
all (x, y) ∈ S, corr(y, synd(x)) = x, and by the length of the string |Z| = r,
which bounds how much information is leaked to the adversary about X.
Let π corr denote the ﬁrst part of the procedure.
In the second step, the players verify whether the error correction was
successful. They do this by ﬁrst choosing a function f uniformly at random
from a family of almost universal hash functions, i.e., a set F = {f : X → Y}
such that for all x, x′ ∈ X , x 6= x′ ,


Pr f (x) = f (x′ ) ≤ εverif .
(12)
f ∈F

Alice sends (f, f (X)) to Bob, who veriﬁes that f (X) = f (X̂), and tells Alice
whether this is successful or whether they should abort. Let the length of
the hash be |f (x)| = t, i.e., |Y| = 2t . Let π verif denote the second part of this
procedure. The complete error correction scheme is then π ec = π verif ◦ π corr .
There are now two cases to consider. The ﬁrst is when the players
have absolutely no guarantee about the correlations between X and Y —
in QKD, this is the case if an adversary is eavesdropping on the channel
and can arbitrarily change the quantum messages. In this case, we wish to
bound the information Eve has as well as bound the probability that the
19

honest players end up with diﬀerent strings. The second case is when some
bounds on the correlations between X and Y are known (e.g., the number of
bit ﬂips between the two) — in QKD, this is the case if only natural noise is
present on the channel. If such a more speciﬁc resource is present, we then
wish to prove that a more speciﬁc (stronger) resource is constructed, namely,
we additionally want a bound on the probability that the players abort —
which is known as the robustness (to this noise model) of a protocol.
4.1.1

Security
k,δ

We start with the ﬁrst case, when Alice and Bob share a resource Hmin ,
where Bob’s string Y may be arbitrary (but is always ⊥ if Alice’s is ⊥). Furthermore, they share an authentic channel Ac .16 It is straightforward that
without any further information about Y one has no hope of guaranteeing
that π corr will work. Instead, we just bound the information leaked to the
adversary by this procedure.
Lemma 4.1. π corr leaks at most r bits of information about Alice’s string
X to Eve, i.e.,
π corr ,0
k,δ
k−r,δ
Hmin kAc −−−−→ Hmin .
Proof. Immediate from Lemma D.1.
In this case, the crucial part of the error correction procedure is the error
veriﬁcation, which constructs a min-entropy resource that provides Bob with
a perfect copy of Alice’s string (or aborts).
k,δ

Theorem 4.2. Let Hmin denote a (k, δ)-min-entropy resource, where Bob’s
k,δ
denote a
string Y is arbitrary (but is always ⊥ if Alice’s is ⊥), and Hmin
(k, δ)-min-entropy resource in which Bob has an exact copy of Alice’s string.
Then
π verif ,εverif

k,δ

k−t,δ
Hmin kAc −−−−−−→ Hmin
.
k,δ

k,δ
⊂ Hmin . What π verif does is check if the resource
Note that one has Hmin
k,δ
shared by Alice and Bob belongs to Hmin
, and aborts if not. It leaks t bits
in the process and fails with probability εverif .
k,δ

Proof. Let H ∈ Hmin and deﬁne H′ to work as follows. H′ internally runs H.
If it obtains X = ⊥, it simply outputs ⊥ at both Alice and Bob’s interfaces
when requested. If X 6= ⊥, it prepares (f, f (X)) for a uniformly chosen f to
be output at Eve’s interface as information sent on the authentic channel if
requested. It checks whether f (X) = f (Y ), and prepares the corresponding
bit of backwards information to be output at Eve’s interface if requested. If
See the description of the multiple use authentic channel Ac in Section 2.4 and
Footnote 7 (though in this case, a single use channel is sufficient).
16

20

these strings are equal, H′ now outputs X ′ = Y ′ = X at Alice’s and Bob’s
interfaces when requested. If they are diﬀerent, it outputs X ′ = Y ′ = ⊥.
To prove that this theorem holds, we will show that
ε

k,δ
k−t,δ verif
.
π verif Hmin ⊂ Hmin

k−t,δ
and that π verif H ≈εverif
This statement follows if we can show that H′ ∈ Hmin
′
verif
′
H . Note that π
H and H behave identically, except for the string Y ′ output at Bob’s interface, which, in the case of H′ is always Y ′ = X ′ , whereas
in the real setting one might have Y ′ 6= X ′ . A bound on the probability that
Y ′ 6= X ′ is thus a bound on the distinguishability between the two systems;
and it follows from the almost universal hashing property (Eq. (12)) that
Pr[Y ′ 6= X ′ ] ≤ εverif .
k−t,δ
we need to show that for all S interacting
To prove that H′ ∈ Hmin
′
with H , the resulting state is of the from ρX ′ Y ′ E ′ = |⊥, ⊥ih⊥, ⊥| ⊗ τE ′ +
δ (X ′ |E ′ ) ≥ k − t. By construction we
σX ′ Y ′ E ′ with X ′ = Y ′ and Hmin
σ
′
′
always have X = Y , so the only condition to verify is the min-entropy
bound. The last messages output by H′ at Eve’s interface are f , f (X), and
the decision bit f (X) = f (Y ). We denote these registers by F , Z, and Ω.
It is suﬃcient to consider a system S that interacts with H, and together
with the output in register E also outputs F ZΩ, hence E ′ = EF ZΩ. By
deﬁnition of H, the state ρXY EF ZΩ resulting from S interacting with H and
adding the transcript F ZΩ that is produced at Eve’s interface has the form
δ (X|E) ≥ k. From
ρXY EF ZΩ = |⊥, ⊥ih⊥, ⊥| ⊗ τEF ZΩ + γXY EF ZΩ with Hmin
γ
δ
Lemma D.1 one has Hmin (X|EF Z)γ ≥ k − t. Furthermore, γXY EF ZΩ =
1
0
1
γXY
EF Z ⊗ |0ih0| + γXY EF Z ⊗ |1ih1|, and σX ′ Y ′ E ′ = γXY EF Z ⊗ |1ih1|. It then
δ
′
′
follows from Lemma D.2 that Hmin (X |E )σ ≥ k − t.
k,δ

k−r−t,δ
Corollary 4.3. π ec = π verif ◦ π corr constructs Hmin
from Hmin and Ac
with error εverif ,
k,δ

π ec ,εverif

k−r−t,δ
,
Hmin kAc −−−−−→ Hmin

where Ac = Ac1 kAc2 , and Ac1 and Ac2 are used by π corr and π verif , respectively.
Proof. Follows from Lemma 4.1, Theorem 4.2, and Theorem 2.2.
4.1.2

Robustness

We now consider the case where correlations between X and Y are known.
The procedure π corr must be chosen to deal speciﬁcally with these errors. Let
k,δ,p
k,δ
Rmin ⊂ Hmin be a min-entropy speciﬁcation that is restricted to resources
that only abort with probability at most p and furthermore, that do not allow
arbitrary outputs Y , but only strings such that (X, Y ) ⊂ S, where S is the
21

k,δ
set of pairs that can be corrected. And let Rk,δ,p
min ⊂ Hmin be a speciﬁcation of
resources that also abort with probability at most p and produce identical
strings at Alice’s and Bob’s interfaces. It is straightforward that in this
k−r−t,δ,p
case the procedure π ec constructs Rk,δ,p
, i.e., one can make
min from Rmin
statements about the probability that the protocol aborts.
k,δ,p

Lemma 4.4. Let π ec , Rmin , and Rk,δ,p
min be as described above. Then
k,δ,p

π ec ,0

k−r−t,δ,p
.
Rmin kAc −−−→ Rmin

Proof. Immediate from Lemma D.1, and the properties of the error correction code chosen.
Note that if (X, Y ) ⊂ S only holds with probability 
1 − ε, then
 one does
k,δ,p
k,δ,p ε
not have the resource Rmin , but a less speciﬁc resource Rmin , and using
id,ε

the fact that for any S, Sε −−→ S, and Theorem 2.2, one has
 k,δ,pε
π ec ,ε
k−r−t,δ,p
Rmin kAc −−−→ Rmin
.

4.2

Privacy Amplification

After the error correction scheme, the players share a string that is partially
known to the adversary. To obtain a secret string, Alice picks a string Z
uniformly at random, a seed, and sends it to Bob on an authentic channel.
They then each compute the strings K = Ext(X, Z) and K ′ = Ext(Y, Z)
for some predeﬁned function Ext, known as an extractor. This procedure is
called privacy ampliﬁcation [34, 35], and we denote the corresponding pair
of converters as π pa . The function Ext has to satisfy the following property.
Definition 4.5. A function Ext : {0, 1}n × {0, 1}d → {0, 1}m is a quantumproof (k, ε)-strong extractor for subnormalized states if for any subnormalized state ρXE classical on X, with Hmin (X|E)ρ ≥ k, and a uniform Z, we
have
1
ρ
− τK ⊗ τZ ⊗ ρE tr ≤ ε,
2 Ext(X,Z)ZE
where τK is the fully mixed state.
The more standard deﬁnition for quantum-proof extractors only requires
them to be deﬁned for normalized states. But as shown in Lemma D.3, any
extractor for normalized states is also an extractor for subnormalized states
with slightly weaker parameters. Eﬃcient constructions of extractors are
given in, e.g., [35–39]. Note that some of these, e.g., the universal hashing
extractors [35, 37, 38], directly satisfy Deﬁnition 4.5.
We are now ready to state the main theorem for this section.

22

Secret key Km
k, ⊥

k, ⊥
key
0, 1

σE

Figure 7 – An m-bit secret key resource Km connected to a simulator σE at
Eve’s interface. As in Section 2.5, Km does not spontaneously output the keys
at the players’ interfaces, but only after having received a request, which is
omitted from the drawing.

Theorem 4.6. Let π pa be a privacy amplification protocol as described
above, which uses a quantum-proof (k, εpa )-strong extractor for subnormalk,δ
which provides Alice
ized states. Given a (k, δ)-min-entropy resource Hmin
and Bob with identical strings X = Y , and an authentic channel Ac , π pa constructs am m-bit secret key resource Km (see Figure 7) with error εpa + 2δ,
π pa ,εpa +2δ

k,δ
kAc −−−−−−−→ Km .
Hmin

Unlike previous proofs, the current one requires a simulator, σE , which
we draw in Figure 7. Note that the number of messages exchanged at the
outer interface of σE (i.e., the number of arrows in Figure 7) will depend on
k,δ
kAc ) from the real system. For example,
the atomic resource R ∈ π pa (Hmin
in the case of a min-entropy resource constructed using a QKD protocol,
this would be three messages as drawn in Figure 7: the quantum states
generated by Alice are output at Eve’s interface, the modiﬁed states are
then input by Eve, and ﬁnally a transcript of the classical communication
is given to Eve as well (upon request).
ε

k,δ
kAc ) ⊂ ((Km )∗ ) pa , for every atomic resource
Proof. To prove that π pa (Hmin
k,δ
kAc ) we will ﬁnd a K and σE such that π pa (HkA) ≈εpa
π pa (HkA) ∈ π pa (Hmin
KσE . Since Ac and Km both have cardinality 1, we only need to ﬁnd a
simulator σE for every H. We construct σE as follows. σE runs H internally
and generates all the communication at the outer interface. If H outputs ⊥,
σE notiﬁes the key resource K to output an error ⊥ as well. If H outputs a
string X 6= ⊥, then it picks a random seed Z, which is made available to be
output at its outer interface as the transcript on the authentic channel. It
notiﬁes K to generate a uniform key k, which is output at Alice’s and Bob’s
interfaces when requested.

23

Let a distinguisher interact with the real system. After interacting with
H it gets a system E, then obtains Z and ﬁnally an output K from Alice’s
and Bob’s interface. We take Z = ⊥ in case H generated a string X = ⊥.
The distinguisher then holds the state
⊤
ρKZE = |⊥, ⊥ih⊥, ⊥| ⊗ ρ⊥
E + ρExt(X,Z)ZE .

In the case where the distinguisher is interacting with KσE , it is going to
get the state
⊤
ρ̃KZE = |⊥, ⊥ih⊥, ⊥| ⊗ ρ⊥
E + τK ⊗ τZ ⊗ ρE .

The distinguishability between the two systems is bounded by the trace
distance between ρKZE and ρ̃KZE , namely
1 ⊤
1
kρKZE − ρ̃KZE ktr =
ρ
− τK ⊗ τZ ⊗ ρ⊤
E
2
2 Ext(X,Z)ZE

tr

≤ εpa + 2δ,

δ (X|E)
where the last inequality uses the fact that Hmin
ρ⊤ ≥ k, that Ext
is a quantum-proof (k, εpa )-strong extractor for subnormalized states and
Lemma D.4, which shows that a (k, ε)-extractor has error ε + 2δ if used
on states with a bound on their smooth min-entropy instead of their minentropy.

4.3

Composed statement

By composing Corollary 4.3, Lemma 4.4 and Theorem 4.6, we get the following.
k,δ

Corollary 4.7. Let Hmin be a (k, δ)-min-entropy resource that produces an
k,δ
k,δ
arbitrary output at Bob’s interface, let Rmin ⊂ Hmin be a (k, δ)-min-entropy
resource that never aborts and furthermore, produces strings (X, Y ) ⊂ S
that are always corrected by the functions (synd, corr). Let Km be a secret
key resource that always provides the players with a uniform key of length m
and let Km be a secret key resource that only provides a key if the adversary
allows it. Finally, let π = π pa ◦ π ec be the construction described in this
section. Then
k,δ

π,εpa +2δ

Rmin kAc −−−−−→ Km
and
k,δ

π,εverif +εpa +2δ

Hmin kAc −−−−−−−−−→ Km ,
where Ac = Ac1 kAc2 , and Aci are the authentic channels used by the different
parts of the protocol.
24

5

Quantum Authentication of Classical Messages

Fehr and Salvail [19, 20] propose a prepare-and-measure protocol that authenticates a classical message by encoding it into a quantum cipher. The
main feature of their protocol is that it recycles all the key if the message is
accepted by the receiver. In this section we provide a composable security
analysis of a slightly modiﬁed version of their protocol, which is adapted
from [20]. We ﬁrst provide a high level view of what the protocol achieves
in the AC framework in Section 5.1. Then in Section 5.2 we give the details
of the protocol. The security proof is provided in Section 5.3. And ﬁnally,
in Section 5.4 we prove bounds on the security if the compromised key is
replaced instead of being discarded.

5.1

The Construction

In this section we model the Fehr-Salvail protocol as a pair of converters
π = (πA , πB ) that construct some resource S given some other resource R.
As in Section 4, there are two statements we wish to make. The ﬁrst is
when an adversary is present and the players share an insecure quantum
channel Q as drawn in Figure 8a, i.e., the adversary can change the message
being sent and insert a message of her own. We model the real and ideal
systems for this case in Section 5.1.1 and Section 5.1.2, respectively. The
second setting is when no adversary is present, but the channel shared has
some natural noise, as in Figure 8b. This case is discussed in Section 5.1.3.
5.1.1

Real System

The protocol π = (πA , πB ) has a very simple structure. First πA encodes a
classical message in a quantum cipher and sends it to Bob on the insecure
channel Q. πB decodes, and either accepts or rejects the message. It also
recycles some key depending on the decision. πB then sends one bit of
information back to Alice, to notify her of whether the message was accepted
or rejected, after which πA recycles Alice’s keys.
To send this bit of information to Alice, we assume that the players
share a backward authentic channel A1 . As in Section 4, this is deﬁned as
a channel that always transmits the message, but provides a copy to Eve if
she requests it. This is illustrated in Figure 8c (but to simplify the drawing,
we do not draw the request that Eve must make to get the transcript of the
authentic channel).
The ﬁnal resources the players are going to need are the key resources.
The protocol uses three keys, (ℓss , ℓmac , θ). ℓss and ℓmac need to be uniform,
so we provide Alice and Bob with a shared uniform key resource K, as
depicted in Figure 4, which generates these keys. Note that if Eve does
not allow the players to get a key, they cannot run the protocol, and it is

25

Noisy channel Rεϕ

Insecure channel Q
ρ′

ρ
Alice

Bob

ρ

Eϕ (ρ)

Alice

Bob

Eve

Eve

(b) When no adversary is present, Alice’s message is delivered to Bob, but
some natural noise is inserted.

(a) An insecure channel from Alice
(on the left) to Bob (on the right)
allows Eve (below) to intercept the
message and insert a message of her
own.
Authentic channel A
x

Authentic channel A
x

Alice

x, ⊥

x

Bob

Alice

Bob

0, 1
Eve

Eve

(c) An idealized authentic channel
from Alice to Bob allows Eve to receive a copy of the message, but guarantees that Bob always gets it.

(d) A realistic authentic channel
from Alice to Bob allows Eve to
receive a copy of the message and
choose whether Bob receives it or an
error symbol.

Figure 8 – Some resources needed in the Fehr-Salvail construction.

trivially secure. Thus, in the following, we assume the switch is set by Eve
to provide the players with a key.
The key θ does not need to be uniform, it is suﬃcient if it has bounded
min-entropy. So we provide the players with a (k, 0)-min-entropy resource
k,0
as deﬁned in Section 3.3. Since we always take the smoothing paramHmin
k . Note that
eter to be 0 in this section, we denote this resource by Hmin
k
to satisfy sequential scheduling, both the key resources K and Hmin
only
provide the keys (or error messages) to the players when they request them
(see Remark B.1, and the discussion of these resources in Sections 2.5 and
3.3).
Putting this together, we get the real system drawn in Figure 9a. (The
switch on K as well as the requests to get keys and messages have been
omitted from the picture.)
5.1.2

Ideal system

The goal of the protocol is to construct an authentic channel. But the
channel A depicted in Figure 8c always delivers the message, and this cannot
be achieved, since Eve can jumble the communication if desired. What is
achieved is a slightly weaker resource A, which allows Eve to choose if Bob
26

πA

πB

Secret key K

ℓ

ℓ

key

ℓ

ℓ

k
Min-entropy resource Hmin

θ, ⊥

θ

θ, ⊥

θ
Auth. ch. A1

Insecure ch. Q

m′ , ⊥

m

(a) The real system consists of the resources consumed and the honest players
converters (πA , πB ) that run the protocol.
Secret key K

ℓ

key

ℓ

k
Min-entropy resource Hmin

θ, ⊥

θ, ⊥
Authentic ch. A

m, ⊥

m

simE

(b) The ideal system consists of the constructed resources and the simulator
simE .
Figure 9 – The real and ideal systems of the modiﬁed FS protocol in the case
where Eve is present.

27

gets the message or not — here too, the receiver must request the message
for it to be output, it is not spontaneously output when Eve allows it. This
is illustrated in Figure 8d without the request arrow for the message to be
delivered.
The protocol also recycles keys, which is modeled as key resources in
the ideal system. All the uniform key (ℓss , ℓmac ) is recycled, so the ideal
system must have a resource K as well, which provides the players with
fresh uniform keys (independent of the messages and ciphers obtained by
Eve).
As we show in Theorem 5.4 in Section 5.3, the subnormalized key with
distribution PΘ′ (θ) := Pr[Θ = θ and “accept”] that is output by players the
if the message is accepted has the same min-entropy as the original normalized key Θ. So the recycled key in the ideal system is captured by a
k
speciﬁcation Hmin
with the same entropy bound k. Note that the renormalized key with distribution PΘ′ (θ) := Pr[Θ = θ|“accept”] may have much less
entropy, so there is eﬀectively an entropy loss during the protocol. But the
relevant measure of entropy for future uses of the key is that of the subnork , measures the entropy
malized state — since the resource consumed, Hmin
of the subnormalized state.
Putting this together along with a simulator simE that is needed for the
security proof, we get the ideal system drawn in Figure 9b.
The corresponding constructive statement formulated in the AC framek kA from KkHk kA1 kQ (with some error
work is that π constructs KkHmin
min
εadv ),
π,ε
k
k
−→ KkHmin
kA.
(13)
KkHmin
kA1 kQ −−−adv
k
The key resources K and Hmin
may be seen as catalysts, since they appear
both in the real and ideal systems.

5.1.3

Natural Noise

In the case where Eve is not present, the players share a channel that has
natural noise instead of the insecure channel Q. More speciﬁcally, the protocol is designed to correct ϕ errors, so we assume a channel speciﬁcation
that is ε-close to having ϕ errors when the states sent are encoded as in the
protocol.17 We denote this channel speciﬁcation by Rεϕ , and illustrate this
in Figure 8b.
Furthermore, in this case we wish to make a stronger statement, namely
that the message is delivered for sure, i.e., a channel of the type A from
17

We model the channel as only adding noise to the quantum states sent, but assume
that the classical part of the cipher is transmitted without errors. One can easily compose
a noisy classical channel with converters that perform error correction if this is not the
case (see Figure 2), i.e., construct a noiseless channel from a noisy one. We do not want
to do this for a quantum channel, because quantum error correcting codes are not prepareand-measure.

28

Figure 8c is constructed. But to achieve this, it is not suﬃcient that the
communication is not jumble by Eve, we also need to be sure that the
players always get keys. We denote by K and Hkmin resources which always
provide keys to the players. In this case, the recycled keys are of the same
type.
The corresponding constructive statement is that π constructs KkHkmin kA
from KkHkmin kA1 kRεϕ (with some error εnoise ),
π,ε

noise
−→ KkHkmin kA.
KkHkmin kA1 kRεϕ −−−

5.2

(14)

Protocol

The Fehr-Salvail [19] protocol requires two diﬀerent (keyed) hash functions,
which we denote ss : {0, 1}nss × {0, 1}rss → {0, 1}mss and mac : {0, 1}nmac ×
{0, 1}rmac → {0, 1}mmac . Both of these functions are constructed from extractors18 Exth : {0, 1}nh × {0, 1}rh −mh → {0, 1}mh , for h ∈ {ss, mac}. The hash
functions are deﬁned as h(x, ℓ1 kℓ2 ) := Exth (x, ℓ1 ) ⊕ ℓ2 .
Note that not any extractor will do. They have to be quantum-proof
(k, ε)-strong
extractors for subnormalized states for any value k and an error
√
ε = ν2h 2−k+mh , where νh are parameters speciﬁc to each extractor. Universal hashing [35], almost universal hashing [37], dual universal hashing [38],
as well as δ-biased masking [36] all satisfy this requirement (for parameters
νh which depend on the speciﬁc constructions). To obtain composable security, we additionally require that these extractors be linear functions in the
ﬁrst input [20], which is satisﬁed by all the constructions cited above.
The reason for this speciﬁc form of extractor is that the security proof
requires the following property.
Definition 5.1 (ν-key-privacy [19]). A function h : X × L → T oﬀers νkey-privacy if for any subnormalized state ρLXT E ∈ S≤ (HLXT E ) with the
properties ρLX = τL ⊗ ρX , T = h(X, L), and L ↔ XT ↔ E forms a Markov
chain, it holds that
p
kρLT E − τL ⊗ ρT E ktr ≤ ν 2−Hmin (X|T E)+m ,

where τL is the fully mixed state and T = {0, 1}m .

Fehr and Salvail [19] prove that if Exth is an extractor of the type
given above, then the corresponding function h provides νh -key-privacy (see
Lemma D.6).
Note that a function like h obtained by XORing a uniform key always
produces a uniform output.
18

The definition of an extractor is given in Definition 4.5.

29

Definition 5.2 (Uniformity [19]). We say that a function h : X × L → T is
uniform if for a uniform L and any x ∈ X , T = h(x, L) is uniformly random
on T .
The ﬁrst keyed hash function, (a secure sketch) ss, is used for error
correction. Apart from the underlying extractor having the required properties, we additionally need that for a uniformly chosen ℓ ∈ {0, 1}rss and any
x, x′ ∈ {0, 1}nss with Hamming distance w(x, x′ ) ≤ ϕnss for some ﬁxed ϕ, x
may be recovered from (x′ , ss(x, ℓ), ℓ) except with probability εss . This can
be implemented using universal hashing [7], but the recovery operation is
not known to be eﬃcient. Fehr and Salvail propose another construction
based in δ-biased masking [36], which has an eﬃcient recovery operation,
but has less noise tolerance ϕ (see [19] for more details).
The second keyed hash function, mac, is used to detect if the adversary
tampered with the message. The additional requirement is that {mac(·, ℓ)}ℓ
must be a family of εmac -strongly universal hash functions [40, 41], i.e., for
any x1 , x2 ∈ {0, 1}nmac and t1 , t2 ∈ {0, 1}mmac with x1 6= x2 ,
Pr[mac(x1 , ℓ) = t1 and mac(x2 , ℓ) = t2 ] ≤
ℓ

εmac
.
2mmac

Constructions for such hash functions are given in [40,41], e.g., mac(x, ykb) =
φ(x ∗ y) + b where φ is any linear surjective function and ∗ and + are multiplication and addition in the corresponding ﬁnite ﬁelds. In this example,
Extmac (x, y) = φ(x ∗ y) is a universal hash function, so mac has the required
extractor properties. We denote by νmac the corresponding extractor parameter. The probability that tampering is not detected when this function is
used as a standard message authentication code (MAC) — i.e., when a tag
t = mac(x, ℓ) is appended to a message x, and upon receiving (x′ , t′ ), the
receiver checks if t′ = mac(x′ , ℓ) [40,41] — is εmac . In the case of the example
given, νmac = 1 and εmac = 2m1mac .
In the following we denote the length of the message to be authenticated
by m and the length of the ﬁrst input to ss by n = nss . The function mac is
always used with nmac = n + m + mss .
The ﬁnal ingredient needed is a code C ⊂ {0, 1}n with minimum distance
d between any two code words.
The modiﬁed Fehr-Salvail protocol works as follows (see Remark 5.3 here
below for a description of the diﬀerences with the original protocol).
Encryption. The players, Alice and Bob, share keys ℓss ∈ {0, 1}rss , ℓmac ∈
{0, 1}rmac , and θ ∈ C. ℓss and ℓmac have to be uniform. θ has bounded
min-entropy, i.e., it should be generated by a min-entropy resource with
parameter k. To authenticate a message y ∈ {0, 1}m , Alice picks a string
x ∈ {0, 1}n uniformly at random, and generates the n qubit quantum state
30

N θi
H θ |xi, where H θ =
and H is the Hadamard matrix. She then
iH
computes the values s = ss(x, ℓss ) and t = mac(xkyks, ℓmac ). Finally, she
sends the cipher consisting of ykskt and ρ = H θ |xihx|H θ to Bob.
Note that it follows from Lemma D.7 that the function χy : {0, 1}n ×
{0, 1}rss +rmac → {0, 1}mss +mmac with χy (x, ℓg kℓh ) := skt provides (νg + νh )key-privacy and uniformity.
Decryption. Upon receiving y ′ ks′ kt′ and ρ′ from Alice, Bob ﬁrst computes
H θ ρ′ H θ and measures in the computational basis, obtaining x̃. He then uses
the recovery procedure to get x′ from (x̃, s′ , ℓss ). He checks if w(x′ , x̃) ≤ ϕn
and if t′ = h(x′ ky ′ ks′ , ℓmac ). If one of these conditions does not hold, he
rejects the message. Otherwise, he accepts y ′ as the message that Alice
sent.
Key recycling. If the message was rejected, Bob recycles ℓss and ℓmac . If
the message was accepted, he recycles ℓss and ℓmac , as well as θ. He sends
one bit of information on a backward authentic channel to Alice to tell her
if he accepted or rejected, and she recycles the same keys.
Remark 5.3. The protocol described here diﬀers in two ways from the original Fehr-Salvail protocol [19]. Firstly, the extractors have to be linear in
their ﬁrst input, which was introduced in the extended version [20] following
an initial draft of the current work pointing out the issue with impersonation
attacks. Secondly, we do not require the players to have fresh key to replace
the discarded θ in case of a reject, our analysis goes through without this.
Hence, in this version of the protocol, the players can run the authentication
scheme even if they only have the keys (ℓss , ℓmac , θ), but no access to a key
refreshing function as in [19, 20] that generates a new θ ′ .

5.3

Analysis

Our task now is to prove that Eqs. (13) and (14) hold and to bound the
corresponding errors. We get similar errors to the original, non-composable
proof [19,20], but with minor improvements in the constants. This is stated
in the following theorem.
k , Hk , A1 , Q, Rε , A, and A, be resource
Theorem 5.4. Let K, K, Hmin
ϕ
min
specification as described above and let π = (πA , πB ) be the converters running the modified Fehr-Salvail protocol from Section 5.2. Then
π,εnoise

KkHkmin kA1 kRεϕ −−−−→ KkHkmin kA
and
π,ε

adv
k
k
KkHmin
kA1 kQ −−−
→ KkHmin
kA,

31

with εnoise = ε + εss and
s

εadv = εmac + (νss + νmac )


|C|
|C|2h(ϕ)n mss +mmac −k
2 + d/2 +
2
.
2d
2

(15)

Proof. The formal statements we will prove are that for any K ∈ K, H ∈
Hkmin , A1 ∈ A1 , and R ∈ Rεϕ , there exists a K′ ∈ K, H′ ∈ Hkmin , A ∈ A, and
a simulator simE such that


πB πA KkHkA1 kR ≈εnoise K′ kH′ kA simE ;
(16)
k , A1 ∈ A1 , and Q ∈ Q, there exists a
and that for any K ∈ K, H ∈ Hmin
k , A ∈ A, and a simulator sim such that
K′ ∈ K, H′ ∈ Hmin
E


(17)
πB πA KkHkA1 kQ ≈εadv K′ kH′ kA simE .
id,ε

We start with the case of Eq. (16). Since for any resource R, Rε −−→ R,
it follows from Theorem 2.2 that it is suﬃcient to consider a noisy channel
speciﬁcation Rϕ and add an error ε to the ﬁnal statement.
The distinguisher could either ﬁrst provide Alice with a message y to
be encrypted, or ﬁrst interact with the key resources so that they generate
keys ℓ, θ. The second case is a more powerful distinguisher, since it can
choose a message correlated to θ, due to the side information it has about
θ. So w.l.o.g. we consider only this second case, i.e., the distinguisher ﬁrst
k
so that θ is generated, and notiﬁes K to generate the
interacts with Hmin
key ℓ = (ℓss , ℓmac ). It then provides a message y to Alice, who prepares the
cipher, and sends it on the noisy channel Rϕ . Due to the error correction
properties of the function ss, Bob can reconstruct the correct x except with
probability εss . If he reconstructs the correct x, then Alice’s message is
always accepted and θ is recycled.
k
For every H ∈ Hmin
we construct a H′ that behaves identically to H,
except that once θ has been generated, H′ does not accept to output it at
the players’ interface if requested, but waits to get a notiﬁcation at Eve’s
interface that it can be output. The simulator simE allows the distinguisher
to interact directly with H′ , except for the last message. It also blocks the
notiﬁcation to K′ to generate the key. Once θ has been generated (but
not output), the activation of K′ received from the distinguisher (but not
delivered), and the simulator has received the notiﬁcation that the message
has been received and delivered by A, it generates the one bit message for
the transcript of the backwards authentic channel and notiﬁes H′ and K′
that their keys can now be output if requested.
These real and ideal systems behave identically, except if Bob fails to
correctly reconstruct x in the real system. So the ﬁnal error is εnoise = ε+εss .
In the case of Eq. (17), we may also assume w.l.o.g. that the distinguisher
k
ﬁrst interacts with Hmin
and notiﬁes K to generate the keys. But it then has
32

two options. It ﬁrst provides Alice with a message y, intercepts and possibly
changes the cipher, and ﬁnally obtains Bob’s outcome as well as the keys —
a substitution attack. Or, the distinguisher may ﬁrst input a cipher on the
insecure channel Q, obtain Bob’s output as well as the recycled keys, then
choose a message y that it inputs at Alice’s interface, and ﬁnally gets her
cipher — an impersonation attack.
We start analyzing the substitution attack. This case follows closely
the security proof from [19]. Let ρΘE be the subnormalized state of the
key θ and Eve’s side information after interacting with H when a key θ is
successfully generated. Eve will now measurePthe E system to choose her
y,θ
message y, resulting in a new state σY ΘE = y py |y, θihy, θ| ⊗ σE
, where
y
we have normalized the states so that tr σΘE = tr ρΘE . By deﬁnition we
have Hmin (Θ|EY )σ ≥ k. Note that one also has
2−Hmin (Θ|EY )σ = pguess (Θ|EY )σ =
X
X
py 2−Hmin (Θ|E)σy . (18)
py pguess (Θ|E)σy =
y

y

y
From now one, we take y to be ﬁxed and σΘE
to be the shared state. At
the end of the proof we average over the diﬀerent y weighted by py .
Alice runs her authentication protocol, after which the shared state bey
tween Alice and the distinguisher is given by σLΘXZQE
, where Z contains
the classical part of the cipher, Q contains the quantum part, X is the
uniform string that Alice generated and encoded in Q, and L contains the
uniform keys ℓss kℓmac . The ZQ systems are intercepted by the distinguisher,
who applies a map E : L(HZQE ) → L(HZZ ′ QE ) which leaves Z unmodiﬁed
and generates a new Z ′ . Let µyLΘXZZ ′ QE be the resulting state. Z ′ Q is
now sent to Bob, who measures Q to get X̃, decodes it with (S ′ , ℓss ) to get
X ′ , and checks whether w(X ′ , X̃) ≤ ϕn and T ′ = h(Y ′ kS ′ kX ′ , ℓmac ), where
Z ′ = Y ′ kS ′ kT ′ . He ﬁnally sends a bit D to Alice containing his decision. If
D = 1 he outputs the received message Y ′ when requested, and outputs the
keys L and Θ when requested. If D = 0, he outputs an error ⊥ and only
recycles L. Let the ﬁnal state be ρyDLΘXX ′ X̃ZZ ′ E .
In the ideal case, we deﬁne H′ and simE to work as follows. H′ ﬁrst runs H,
so that exactly the same key Θ and side information E are generated while
interacting with the distinguisher — the simulator simE lets all these messages between H′ and the distinguisher go through. Once the distinguisher
has input the message y in the ideal authentic channel, the simulator gets
a copy, which it forwards to H′ . H′ then picks its own keys (ℓ′ss , ℓ′mac ) uniformly at random and a uniform X, and generates a cipher ZQ. It then
outputs ZQ at Eve’s interface, which the simulator simE passes on to the
distinguisher. Let the state shared between the diﬀerent systems at this
y
point be σ̃LΘXZQE
, where L represents the new keys that are to be output
by K (not those generated internally by H′ ). The distinguisher performs the

33

same map, E, as when interacting with the real system, resulting in a state
µ̃yLΘXZZ ′ QE , and gives Z ′ Q to the simulator simE who forwards them to H′ .
H′ now measures Q just as Bob would do, gets X̃. It then reconstructs X ′ ,
checks that X ′ = X, that w(X ′ , X̃) ≤ ϕn and that Z = Z ′ . If one of these
three conditions is not satisﬁed, it outputs a bit D = 0, otherwise D = 1,
which the simulator intercepts. If D = 0, simE tells the authentic channel
to output an error symbol at Bob’s interface when requested, if D = 1 the
message y is output instead. Regardless of the value of D, simE outputs D
as the bit on the backward authentic channel if requested, and also notiﬁes
K to output a random key ℓ = ℓss kℓmac when requested. And if D = 0,
it tells H′ to output ⊥ when requested, otherwise θ. Let the ﬁnal state be
ρ̃yDLΘXX ′ X̃ZZ ′ E .
k , and secondly
We now need to prove two things. Firstly, that H′ ∈ Hmin
that the real and ideal systems are indistinguishable except with advantage
εadv , i.e.,
1 y,1
ρLΘZZ ′ E − ρ̃y,1
LΘZZ ′ E
2

tr

≤ εy,1
adv

and

1 y,0
ρLZZ ′ E − ρ̃y,0
LZZ ′ E
2

tr

≤ εy,0
adv ,

(19)
y,1
where ρyLΘXX ′ X̃ZZ ′ ED = ρy,0
⊗
|0ih0|
+
ρ
⊗
|1ih1|
and
LΘXX ′ X̃ZZ ′ E
LΘXX ′ X̃ZZ ′ E
P
y,0
y,1
y py (εadv + εadv ) = εadv .
k . For this, it is suﬃcient to show that
We start with H′ ∈ Hmin

Hmin Θ|ZZ ′ E ρ̃y,1 ≥ Hmin (Θ|E)σy ,

y
where σΘE
is the state output by H (after the measurement to choose y),
since it them follows from Eq. (18) that Θ has enough min-entropy. From
Lemma D.2 we have



Hmin Θ|ZZ ′ E ρ̃y,1 ≥ Hmin Θ|ZZ ′ E ρ̃y = Hmin Θ|ZZ ′ E µ̃y .

Applying a map to the side information can only increase the entropy, hence

Hmin Θ|ZZ ′ E µ̃y ≥ Hmin (Θ|ZQE)σ̃y .

Because Z = ykSkT and the function which computes SkT is uniform (see
Deﬁnition 5.2), Z is independent from the other systems, hence
Hmin (Θ|ZQE)σ̃y = Hmin (Θ|QE)σ̃y .

Finally,
Q was generated by applying a unitary H θ to a fully mixed state
P
1
x |xihx|, so Q is also fully mixed and independent of the other systems
2n
(which contain no information about x), hence
Hmin (Θ|QE)σ̃y = Hmin (Θ|E)σ̃y .
34

We now return to Eq. (19). From the properties of mac, it follows that if
D = 1, then Z ′ = Z and X ′ = X except with probability εmac , i.e., the state
ρ̄yLΘXX ′ X̃Y ′ ZZ ′ ED obtained by ﬂipping the value of D from 1 to 0 if either
Z ′ 6= Z or X ′ 6= X must be εmac -close to ρyLΘXX ′ X̃ZZ ′ ED . It now suﬃces to
bound the distance between ρ̃y and ρ̄y . To simplify notation, we introduce
a new register Θ′ such that if D = 0, Θ′ = ⊥, and if D = 1, then Θ′ = Θ.
Thus, we are now trying to prove that
1 y
ρ̄ ′ ′
− ρ̃yLΘ′ ZZ ′ ED
2 LΘ ZZ ED

tr

≤ εyadv − εmac .

(20)

In the ideal case we have ρ̃yLΘ′ ZZ ′ ED = τL ⊗ ρ̄yΘ′ ZZ ′ ED , where τL is the
fully mixed state, because by construction L is uniform and independent of
the rest, and ρ̃yΘ′ ZZ ′ ED = ρ̄yΘ′ ZZ ′ ED — H′ runs the real protocol, the only
diﬀerence is the reject condition, but by the ﬂip of D that generated ρ̄y
from ρy makes them now abort under the same conditions. Plugging this in
Eq. (20), it remains to show that
1 y
ρ̄ ′ ′
− τL ⊗ ρ̄yΘ′ ZZ ′ ED
2 LΘ ZZ ED

tr

≤ εyadv − εmac .

From Lemma D.7 it follows that the function
χy : {0, 1}n × {0, 1}rss +rmac → {0, 1}mss +mmac
with χy (x, ℓss kℓmac ) := skt, s = ss(x, ℓss ), and t = mac(xkyks, ℓmac ) provides
(νss + νmac )-key-privacy. Furthermore, the state ρ̄yLXΘ′ ZZ ′ ED satisﬁes the
assumptions of Deﬁnition 5.1 (with T = Z). Hence we have
1 y
ρ̄LΘ′ ZZ ′ ED − τL ⊗ ρ̄yΘ′ ZZ ′ ED tr
2
νss + νmac p −Hmin (X|Θ′ ZZ ′ ED)ρ̄y +mss +mmac
.
≤
2
2

It now remains to upper bound
′

′

2−Hmin (X|Θ ZZ ED)ρ̄y = pguess X|Θ′ ZZ ′ ED



ρ̄y

= pguess X|Θ′ ZZ ′ E



ρ̄y

,

where we have removed D because this register is redundant, it can be
inferred from Θ′ (since Θ′ = ⊥ ⇐⇒ D = 0).
Let us deﬁne a new register Ω which takes the value 1 if w(X, X̃) ≤ ϕn
y,1
and Ω = 0 otherwise. Let ρ̄yXΘ′ ZZ ′ EΩ = ρ̄y,0
XΘ′ ZZ ′ E ⊗ |0ih0| + ρ̄XΘ′ ZZ ′ E ⊗ |1ih1|.
We have


pguess X|Θ′ ZZ ′ E ρ̄y ≤ pguess X|Θ′ ZZ ′ EΩ ρ̄y


= pguess X|Θ′ ZZ ′ E ρ̄y,0 + pguess X|Θ′ ZZ ′ E ρ̄y,1


≤ pguess X|ZZ ′ E ρ̄y,0 + pguess X|ΘZZ ′ E ρ̄y,1 .
35

The third line follows because adding Θ to the side information when Θ′ = ⊥
can only increase the probability of guessing X.
We now bound these two terms separately.


pguess X|ZZ ′ E ρ̄y,0 ≤ pguess X|ZZ ′ E ρ̄y

= pguess X|ZZ ′ E ρy

= pguess X|ZZ ′ E µy
≤ pguess (X|ZQE)σy
= pguess (X|QE)σy .

The ﬁrst line follows from Lemma D.2. The fourth line follows because
applying a map to the side information can only decrease the probability of
guessing X. The ﬁfth line follows because χy is uniform soZ is independent.
y
y
+
+
Finally, by noting that σΘXQE
= MBB84
ΘA,X σΘXE ⊗ ΦAQ , where ΦAQ are

EPR pairs and MBB84
ΘA,X measures A according to the basis in Θ and writes
the result in X (see Appendix D.4 for a formal deﬁnition of MBB84
ΘA,X ), we
can apply Lemma D.8 with B = QE, from which we get


|C|
pguess (X|QE)σy ≤ pguess (Θ|E)σy 1 + d/2 .
2

To bound pguess (X|ΘZZ ′ E)ρ̄y,1 we will use Lemma D.9. Let P Ω be an
operator which projects the state on the event Ω = 1, namely w(X, X̃) ≤ ϕn.
be Bob’s measurement of the cipher Q that yields the string X̃.
Let MBB84
ΘQ,X̃
Let E : L(HZQE ) → L(HZZ ′ QE ) be the map performed by the distinguisher
Y
Ω
BB84
on the cipher. We thus have ρ̄y,1
XΘZZ ′ E = trX̃ ◦ P ◦ MΘQ,X̃ ◦ E(σXΘZQE ).
Note furthermore that by the uniformity of χy , Z = ykSkT where SkT is
uniform and independent from the other registers, and XQ may be generated
by measuring halves of EPR pairs Φ+
AQ according to Θ (which commutes
with E). Hence we have
y
+
BB84
Ω
BB84
ρ̄y,1
XΘZZ ′ E = trX̃ ◦P ◦ MΘQ,X̃ ◦ MΘA,X ◦ E(σΘE ⊗ ΦAQ ⊗ τZ ).

This puts us in a position to apply Lemma D.9 with B = Q and C = ZZ ′ E,
from which we get
!

|C|2h(ϕ)n
′
.
pguess X|ΘZZ E ρ̄y,1 ≤ pguess (Θ|E)σy 1 +
2d
Finally, taking the average over py along with Jensen’s inequality, we get
the bound from Eq. (15).
The ﬁnal case to consider is that of impersonation attacks. In the real
system, the distinguisher sends a forged cipher to Bob, who performs the
36

decoding. He then either accepts and recycles both ℓ = (ℓss , ℓmac ) and θ, or
rejects and recycles only ℓ = (ℓss , ℓmac ). Let σLΘED denote the joint state at
this point, where, as previously, D is Bob’s decision to accept or reject the
message, L contains the uniform keys (ℓss , ℓmac ), Θ is the non-uniform key
(which may have been given to the distinguisher if D = 1).
The distinguisher can then choose a message Y to input at Alice’s interface for encryption. Let E : L(HLΘED ) → L(HLΘY ED ) be the operator
applied by the distinguisher to generate Y , which we deﬁne so as to leave
the classical registers LΘD unmodiﬁed, and furthermore, E is only allowed
to use information from Θ if D = 1. We denote the resulting state by
ρLΘY ED = E(σLΘED ). Finally, Alice’s protocol generates a cipher, resulting
in the joint shared state ρLΘU Y QED , where U Y denotes the classical part of
the cipher with U = SkT (jointly written Z = Y kSkT in the proof against
substitution attacks), and Q is the quantum part of the cipher.
In the ideal case, if the simulator simE receives a forged cipher at its
outer interface from the distinguisher before it receives the message y from
the authentic channel, it knows that we are dealing with an impersonation
attack. It then tells the authentic channel to output an error when requested,
the key resource K′ to output some fresh uniform key ℓ = (ℓss , ℓmac ) when
requested, and the min-entropy resource H′ to output an error ⊥ when requested. Let σ̃LΘED denote the joint state at this point. As in the real case,
the distinguisher applies the map E to generate a message Y , inputs this to
the authentic channel, which gives it to the simulator. simE now picks its
own key ℓ′ and asks H′ to give it the key θ that it generated while running
H internally. simE then follows the protocol and generates a cipher Y U Q,
which it outputs at its outer interface. Let the ﬁnal state shared by the
diﬀerent parties be ρ̃LΘU Y QED .
As in the case of impersonation attacks, we need to prove two things.
k , and secondly, that
Firstly, that H′ ∈ Hmin
1
kρLU Y QED − ρ̃LU Y QED ktr ≤ εadv .
2

(21)

Note that Eq. (21) does not contain Θ. This is because it is only ever recycled in the real case (the ideal system cannot get fooled by an impersonation
attack), but the bit D = 1 is already enough to perfectly distinguisher real
from ideal in this case, one does not need Θ.
Since H′ always outputs ⊥, it trivially satisﬁes the deﬁnition of a (k, 0)min-entropy resource. For bounding Eq. (21), note that by the deﬁnition
of mac, the probability of accepting the forged cipher is at most εmac . Let
σ̄LΘED be the state obtained by ﬂipping D from 1 to 0 on σLΘED and deﬁne
ρ̄LΘU Y QED as the state obtained after the distinguisher applies E to σ̄LΘED
and Alice generates the cipher. Then
1
kρLU Y QED − ρ̄LU Y QED ktr ≤ εmac .
2
37

Furthemore, in the ideal system one has ρ̃LU Y QED = τL ⊗ τU ⊗ ρ̄Y QED ,
where τL and τU are fully mixed states. This follows, because L is uniform
by deﬁnition, U is uniform because it is generated by the uniform function χy ,
and ρ̃Y QED = ρ̄Y QED because the simulator uses the same θ and performs
the same operation to generate Q. Since we always have D = 0, this register
can be removed, and it remains to show that,
1
kρ̄LU Y QE − τL ⊗ τU ⊗ ρ̄Y QE ktr ≤ εadv − εmac .
2
We now look more closely at how the protocol generates U . Since the
extractors used are linear, we have u = skt with s = Aℓss x + bℓss and t =
Aℓmac (xkyks) + bℓmac , where Aℓss and Aℓmac are matrices, and bℓss and bℓmac are
strings, whichdepend on ℓss and ℓmac . One can alternatively write this as u =
Aℓss xkA1ℓmac x + 0kA3ℓmac Aℓss x + Bℓss ,ℓmac y + cℓss ,ℓmac , where A1ℓmac and A3ℓmac
are the ﬁrst n columns and last mss columns of Aℓmac = A1ℓmac kA2ℓmac kA3ℓmac ,
respectively, and Bℓss ,ℓmac and cℓss ,ℓmac are a matrix and string which depend
on ℓss and ℓmac .
Since Extmac (xkyks, ℓmac ) = Aℓmac (xkyks) is a (k, ε)-strong extractor,
then so is Ext′mac (x, ℓmac ) := A1ℓmac x. And from Lemma D.5 and the bounds
on the errors of Extss and Extmac , we ﬁnd that Ext(x, ℓss kℓmac ) := Aℓss xkA1ℓmac x
√
mac
is a (k, ε)-strong extractor for any k and ε = νss +ν
2−k+mss +mmac . The
2

state ρ̄LU Y QE may thus be written as ρ̄LU Y QE = G ◦ F ρ̄LExt(X,L)Y QE ,
where F : L(HLU ) → L(HLU ) with U = ST reads L and S and XORs
A3ℓmac s to the T register, and G : L(HLU Y ) → L(HLU Y ) reads L and Y and
XORs Bℓss ,ℓmac y and cℓss ,ℓmac to U . Since L is uniform and independent from
ρ̄Y QE , it follows from the deﬁnition of an extractor that

1
G ◦ F ρ̄LExt(X,L)Y QE − G ◦ F(τL ⊗ τU ⊗ ρ̄Y QE ) tr
2
νss + νmac p −Hmin (X|Y QE)ρ̄ +mss +mmac
.
2
≤
2

To ﬁnish the proof we need that F and G XOR a value to a uniform
string, which results in a uniform string, hence
G ◦ F(τL ⊗ τU ⊗ ρ̄Y QE ) = τL ⊗ τU ⊗ ρ̄Y QE ,
and we need to upper bound 2−Hmin (X|Y QE)ρ̄ = pguess (X|Y QE)ρ̄ . This latter
bound is obtained from Lemma D.8 following the same steps as the bound
on pguess (X|QE)σy in the case of substitution attacks, from which we get




|C|
|C|
k
pguess (X|Y QE)ρ̄ ≤ pguess (Θ|E)σ 1 + d/2 ≤ 2 1 + d/2 .
2
2

38

5.4

Continuing after a reject

Since the construction from Theorem 5.4 generates the same resources K
k
and Hmin
that it uses, it is trivial to recursively apply the protocol to authenticate multiple messages using the same keys. By Theorem 2.2, the error
of n runs of the protocol, π ◦ · · · ◦ π, is nεadv . But note that the protocol
k
does not perform anything if it gets an error from the resource Hmin
instead
of a key. This way of composing the protocol with itself aborts all future
rounds as soon as tampering is detected and the key θ is not recycled.
One can imagine a diﬀerent scenario, in which the players have spare
secret key, which they use to replace θ, if it cannot be recycled. Let K denote
k
such an extra key resource, and let Hmin
denote a min-entropy resource,
which might produce an error ⊥. Given these two resources, we wish to
′
construct a new resource Hkmin which always outputs a key, by “giving” the
k . We are then left with a resource K which might still
key from K to Hmin
k . K can be deﬁned as in Figure 4,
output a key if it was not given to Hmin
with a switch that decides if it produces a key or not.
new , π new ) be a protocol where both π new and
Lemma 5.5. Let π new = (πA
B
A
new get keys (k, θ) from K and Hk . If θ 6= ⊥, they output (k, θ) at their
πB
min
outer interfaces when requested. If θ = ⊥, they output (⊥, k) at their outer
interfaces instead. Then
π new ,0

′

k
−−−−→ KkHkmin
KkHmin

with k′ = − log 2−n + 2−k .

k , and after interacting with this, let the shared state of
Proof. Let H ∈ Hmin
the key and the distinguisher be ρΘE = |⊥ih⊥|⊗µE +σΘE with Hmin (Θ|E)σ ≥
k.
We deﬁne H′ to run H, and if it gets ⊥, it generates a fresh uniform
key τΘ , which it outputs when requested. The shared state is then ρ′ΘE =
τΘ ⊗ µE + σXE . One has

pguess (Θ|E)ρ′ ≤ pguess (Θ|E)τ ⊗µ + pguess (Θ|E)σ ≤ 2−n + 2−k .
Hence


Hmin (Θ|E)ρ′ = − log pguess (Θ|E)ρ′ ≥ − log 2−n + 2−k .

This shows that H′ ∈ Hkmin . We additionally need H′ to output at Eve’s
interface whether H generated ⊥ or not, and for a simulator to activate the
corresponding switch on K.
If one has enough spare key K, recursively composing π new with the
modiﬁed Fehr-Salvail protocol π — i.e., running π ◦ π new ◦ π ◦ · · · ◦ π new ◦ π —
39

allows one to encrypt multiple messages by using keys from K to replace
lost θ. Note that since the entropy of the key decreases slightly when this
is done, the error εadv will increase slightly with each run (if one does not
change the parameters to compensate).

Appendices
A

Notation and basic concepts

We assume the reader is familiar with basic quantum information theory,
e.g., textbooks such as [42, 43]. In this appendix we explain the notation,
and introduce the distance and entropy measures that we use in this work.

A.1

Quantum states, maps, and norms

We use standard notation for quantum information theory. H denotes a
Hilbert space. In all sections except Section 3.2 and Appendix B.2, where
causal boxes are used, Hilbert spaces are ﬁnite dimensional. In ﬁnite dimensions, L(H) denotes the set of linear operators on H, S(H) is the set of
normalized positive operators — density operators — and S≤ (H) is the set
of subnormalized positive operators, i.e., if ρ ∈ S≤ (H), then 0 ≤ tr ρ ≤ 1.
In inﬁnite dimensions, T(H) denotes the set of trace class operators.19
We write HAB = HA ⊗ HB for a bipartite quantum system and ρAB ∈
S≤ (HAB ) for a bipartite (subnormalized) quantum state. ρA = trB (ρAB )
and ρB = trA (ρAB ) denote the corresponding reduced density operators.
Let E : L(HA ) → L(HB ) be a completely positive, trace-preserving (CPTP)
map.20 When it is applied to a state ρ ∈ S≤ (HAC ), we write E(ρ) as
shorthand for (E ⊗ idC )(ρ), where idC is the identity on system C.
The only norm we need in
√ this work is the trace norm (or Schatten 1norm), deﬁned as kAktr := tr A† A.

A.2

Distance measures

The trace distance between two states ρ and σ is given by
1
D(ρ, σ) := kρ − σktr .
2
This corresponds to the maximum advantage one has in distinguishing between the two states, i.e., if given ρ or σ chosen uniformly at random one
√
P
V ∈ T(H) if kV ktr = i hi| V † V |ii < ∞, where {|ii} is an orthonormal basis of H.
A density operator is a non-negative self-adjoint operator ρ ∈ T(H) with tr ρ = 1.
20
In the case of infinite dimensional systems, a CPTP map acts on trace class operators,
E : T(HA ) → T(HB ).
19

40

has to guess which one we hold, then the probability of guessing correctly is
[43]
1 1
p = + D(ρ, σ).
2 2
Another widely used measure is the ﬁdelity, deﬁned as
q

1/2
1/2
F (ρ, σ) := tr
ρ σρ
.
When dealing with subnormalized states, we need to generalize these
measures to retain their properties. The following distance notions are
treated in detail in [33], and we refer to that work for more information.
For any two subnormalized states ρ, σ ∈ S≤ (H), we deﬁne the generalized
trace distance as
1
D̄(ρ, σ) := D(ρ, σ) + | tr ρ − tr σ|,
2
and the generalized ﬁdelity as
F̄ (ρ, σ) := F (ρ, σ) +

p

(1 − tr ρ)(1 − tr σ).

The (generalized) ﬁdelity has a useful property, known as Uhlmann’s
theorem (see [33, 42]), which states that for any two states ρ and σ, there
exist puriﬁcations of these states which have the same ﬁdelity. The purified
distance is deﬁned based on the ﬁdelity, so as to have the same property [33]:
q
:=
1 − F̄ 2 (ρ, σ).
P (ρ, σ)
This metric coincides with the generalized distance for pure states, and
is larger otherwise.
Lemma A.1 ([33, Lemma 6]). Let ρ, σ ∈ S≤ (H). Then
q
D̄(ρ, σ) ≤ P (ρ, σ) ≤ 2D̄(ρ, σ).

The puriﬁed distance is used to deﬁne smooth min-entropy in the following section.

A.3

Min-entropy

The smooth conditional min-entropy that we use throughout this work to
deﬁne the randomness of a quantum system was ﬁrst proposed by Renner [7].
It represents the optimal measure for randomness extraction in the sense that
it is always possible to extract that amount of almost uniform randomness
from a source, but never more. Before deﬁning this notion, we ﬁrst state a
non-smooth version.
41

Definition A.2 (conditional min-entropy [7]). Let ρAB ∈ S≤ (HAB ). The
min-entropy of A conditioned on B is deﬁned as
Hmin (A|B)ρ := max{λ ∈ R : ∃σB ∈ S(HB ) s.t. 2−λ 1A ⊗ σB ≥ ρAB },
where 1A denotes the identity operator and A ≥ B if and only if A − B is
positive semi-deﬁnite (A − B ≥ 0).
We will often drop the subscript ρ when there is no doubt about what
underlying state is meant.
This deﬁnition has a simple operational interpretation when the ﬁrst
system is classical, which
König et al. [44] showed
P is the case we consider.
x
that for a state ρXB = x∈X px |xihx| ⊗ ρB classical on X,
Hmin (X|B)ρ = − log pguess (X|B)ρ ,

(22)

where pguess (X|B) is the maximum probability of guessing X given B, namely
!
X
px tr(Γx ρxB ) ,
pguess (X|B)ρ := max
{Γx }x∈X

x∈X

where the maximum is taken over all positive-operator
valued measures
P
(POVMs) {Γx }x∈X on B (i.e., Γx is positive and x Γx = I). If the system
B is empty, then the min-entropy of X reduces to the Rényi entropy of order
inﬁnity, Hmin (X) = − log maxx∈X px (often written H∞ (X)). In this case
the connection to the guessing probability is particularly obvious: when no
side information is available, the best guess we can make is simply the value
x ∈ X with highest probability.
The smooth min-entropy then consists in maximizing the min-entropy
over all subnormalized states δ-close in the puriﬁed distance to the actual
state ρXB of the system considered. Thus by introducing an extra error δ,
we have a state with potentially much more entropy.
Definition A.3 (smooth min-entropy [7,33]). Let δ ≥ 0 and ρAB ∈ S≤ (HAB ),
then the δ-smooth min-entropy of A conditioned on B is deﬁned as
δ
Hmin
(A|B)ρ :=

B
B.1

max

σAB :P (σ,ρ)≤δ

Hmin (A|B)σ .

Formalizing Information-Processing Systems
Quantum Combs

A quantum comb [27–29] (see also [30–32]) models an interactive quantum
information-processing system that receives an input, sends an output, receives an input, sends an output, etc, and terminates after a ﬁxed number
of steps. Such a system is drawn in Figure 10. One trivial way to model
42

Figure 10 – A single information-processing system modeled as a comb. The
nodes represent an operation and the arrows capture a quantum state. Each
tooth of the comb corresponds to a pair of an input and an output message.

such systems is to explicitly denote their internal memory, e.g., let HM be
the space of the internal memory, then a system is given by a sequence of
CPTP maps:
Ei : L(HXi M ) → L(HM Yi ).
Let the internal memory start in some initial state |0iM . Upon receiving
an input ρX1 ∈ L(HX1 ) one can evaluate the output and new memory state
as σM Y1 = E1 (ρX1 ⊗ |0ih0|M ). Upon receiving the next input σX2 , the new
memory state and output are τM Y2 = E2 (σX2 M ), etc.
A more compact representation of a comb which omits the internal memory is given by a single CPTP map
E : L(HX1 ···Xn ) → L(HY1 ···Yn ),
which, for all i ∈ [n] and all ρX1 ···Xn , σX1 ···Xn ∈ L(HX1 ···Xn ) such that
ρX1 ···Xi = σX1 ···Xi satisﬁes the relation
trYi+1 ···Yn [E(ρX1 ···Xn )] = trYi+1 ···Yn [E(σX1 ···Xn )],
i.e., if the inputs are identical up to position i, then the outputs must be
identical up to position i as well. This can be seen as a causality condition,
namely that an input after i cannot inﬂuence an output before i.
A very convenient representation of combs is given by the Choi-Jamiolkowski representation [43] of the map E, namely the operator RY1 ···Yn X1 ···Xn ∈
L(HY1 ···Yn X1 ···Xn ) given by
X
RY1 ···Yn X1 ···Xn :=
E(|iihj|) ⊗ |iihj|.
i,j

The causality condition then becomes
trYi+1 ···Yn (RY1 ···Yn X1 ···Xn ) = RY1 ···Yi X1 ···Xi ⊗ IXi+1 ···Xn .
Remark B.1 (Sequential scheduling). If the output value in register Yi corresponds to one message being sent to one (random) party — where the name
of the party might be a classical part of the message — then the composition
of combs obtained by routing messages to the correct parties is alway a new
43

Alice

Ali
B

ce!

ob!

Charlie

Alice
or Bob?

Bob
Figure 11 – Alice and Bob both send messages to Charlie, who outputs the
ﬁrst message he receives. Although each system can be described by a comb,
the composition of the three, depicted as the dashed box, is undeﬁned.

well-deﬁned comb.21 The systems used in this work in all sections except
Section 3.2 follow this rule, and are thus modeled as quantum combs. In
Appendix B.2 we discuss some settings that do not use sequential scheduling,
and thus need a more complex model of systems to be captured.

B.2

Causal Boxes

The quantum combs introduced in Appendix B.1 are well-suited for modeling ﬁnite systems with sequential scheduling, which is the case for all the
concrete protocols analyzed in this work. There are however situations which
require a more developed model of systems. Consider the example drawn
in Figure 11: two players, Alice and Bob, each send a message to a third
player, Charlie, who outputs the ﬁrst message he receives and ignores the
second. Each of the systems is a well-deﬁned comb. Alice and Bob just output a single message. When Charlie receives the ﬁrst message, m = (v, p) —
value v from player p — he outputs v and ignores all further inputs. But the
composition of all three systems (depicted as a dashed box in Figure 11) is
not deﬁned: it is a system with no input and one output, but this output is
undetermined.
The composition of these three systems is undeﬁned, because Charlie’s
output depends on the order of the messages he receives, but this is not
speciﬁed by the individual systems of Alice and Bob. The causal box framework [26] was developed to model such systems. It achieves this by assigning
a tag t ∈ T to values v ∈ V that are output (and input) by quantum information-processing systems. T is a partially ordered set (e.g., T = Q), and
t ∈ T , which can be thought of as a time, denotes the order of v with respect to other messages. This also allows superpositions of causal structures
to be modeled by allowing a message to be in a superposition of diﬀerent
positions, e.g., |t1 i + |t2 i. Additionally, when the cardinality of T is inﬁnite,
21
This follows because in such a network of systems, there is always ever only one active
party, the one that has just received a message. Thus, the next message to be output and
the next active party is always uniquely defined.

44

the resulting causal boxes can process an unbounded number of messages,
e.g., a beacon which outputs a qubit every second is valid causal box, but
cannot be modeled as a quantum comb.
More precisely, a quantum message that is either input to or output
from a causal box is an element of a Hilbert space with an orthonormal
basis given by {|v, ti}v∈V,t∈T . For a ﬁnite V and inﬁnite T , this Hilbert
space corresponds to
C|V| ⊗ ℓ2 (T ) ,
(23)

where ℓ2 (T ) = {(xt )t∈T : xtp∈ C, kxk < ∞} is P
the sequence space with
bounded 2-norm with kxk = hx|xi and hx|yi = t∈T xt yt .
An arrow used in ﬁgures such as Figure 6 captures an unbounded number
of messages being output or input. We refer to such an object as a wire
(which may connect two systems), and its Hilbert space is given by a Fock
space,
∞
M
∨n H ,
(24)
F(H) :=
n=0

where ∨n H denotes the symmetric subspace of H⊗n , and H⊗0 is the one
dimensional space containing the vacuum state |Ωi. Plugging Eq. (23) into
Eq. (24) for a d dimensional value (|V| = d), we ﬁnd that the message space
of a wire is
∞



 M
(25)
∨n Cd ⊗ ℓ2 (T ) .
F Cd ⊗ ℓ2 (T ) =
n=0

∨n

Cd


The orthogonal subspaces
⊗ ℓ2 (T ) for n ∈ N0 capture n messages
being sent on a wire. The restriction to the symmetric space guarantees that
there is no order amongst the messages other than what might be deﬁned
from their state, e.g., their position in T .
Let A denote a wire that carries dA -dimensional messages. Abusing
language, we will refer to this as a dA -dimensional wire.22 We write FAT for
the corresponding state space, namely


FAT := F CdA ⊗ ℓ2 (T ) .
Note that for any Hilbert spaces HA and HB ,

F(HA ) ⊗ F(HB ) ∼
= F(HA ⊕ HB ) ,

(26)

where the isomorphism preserves the meaning associated with the bases of
the Fock spaces, i.e., a tensor product of two vacuum states on the left in
Eq. (26) is mapped to a vacuum state on the right, a tensor product of a
vacuum state and one message on the left is mapped to a single message
with the same value and position on the right, etc. (see [26] for the exact
22

The Hilbert space of the wire is in fact infinite dimensional.

45

isomorphism). This allows the tensor product of two wires with dimensions
dA and dB to be written as one wire with dimension dA + dB ,
T
FAT ⊗ FBT ∼
.
= FAB

Similarly, for any P ⊂ T , a wire may be split in two parts corresponding to
messages in P and P̃ := T \ P, respectively:
FAT ∼
= FAP ⊗ FAP̃ .
We use this in particular to trace out messages that are not before some
position t ∈ T by taking P = {p ∈ T : p ≤ t}, e.g.,
ρ≤t
A = trt (ρA ).

T and F T denote the Hilbert spaces of an input wire X and output
Let FX
Y
T ) and T(F T ) be the corresponding sets of trace class
wire Y . And let T(FX
Y
operators. For the specical case of a totally ordered set T ,23 a causal box is
deﬁned as a set of mutually consistent CPTP maps
o
n


T
R = E ≤t : T FX
→ T FY≤t
,
t∈T

i.e., for t ≤ u,

E ≤t = tr>t ◦ E ≤u .

In some cases the map E = limt→∞ E ≤t is well-deﬁned, in which case a causal
box can be deﬁned by this limit instead of by the sequence.
As for quantum combs, causal boxes must satisfy a notion of causality,
so that an input before position t cannot inﬂuence an output after position t.
The exact deﬁnition is not needed in this work, so we omit it, and refer the
interested reader to [26]. Similarly, causal boxes can be represented using
the Choi-Jamiolkowski isomorphism, which we omit here as well.
Causal boxes may be connected in arbitrary ways, i.e., any output wire
of one box can be “plugged into” an input wire of the same dimension from
a diﬀerent box, or may be looped back and connected to one if its own
inputs. This always results in a new well-deﬁned causal box, even if loops
are present. It does not create any causality conﬂicts since messages are
ordered and an output can only depend on inputs that arrived before.
Remark B.2 (From combs to causal boxes). Quantum combs may be seen
as special cases of causal boxes, which do not specify the positions t ∈ T
of the outputs, only the (local) order with respect to the other outputs it
generates. One can easily “upgrade” a quantum comb to a causal box by
assigning some (ﬁxed) processing time δi to produce the output Yi after
receiving the input Xi , in which case it inherits all the properties (e.g.,
closure under composition) of causal boxes. Alternatively, a comb can be
modeled as a speciﬁcation of causal boxes, namely those that produce the
same outputs in the same order, but at undetermined times.
23

The case for a partial order on T can be found in [26].

46

C

Quantum Key Distribution

A QKD protocol typically has three phases.24 In the ﬁrst, the players exchange some quantum states — either one player (Alice) generates them and
sends them to the other (Bob), or an untrusted third party (Eve) prepares
states that are sent to both players. We assume for simplicity that the
players measure the quantum states upon reception, but the same analysis
holds for protocols that require quantum memory as well. In Figure 3 we
illustrated the case where the players have access to an (insecure) quantum
channel that they use to send quantum states from Alice to Bob. In the
second phase of the protocol, the players compare some of the measurement
results to estimate the amount of noise on the channel. At the end of this
phase, they obtain a bound on the entropy of the remaining undisclosed bit
strings conditioned on the adversary’s information. In the ﬁnal phase, the
players run some (classical) post-processing protocols on the strings they
hold to extract a secret key. More precisely, they ﬁrst need to correct errors between the strings held by Alice and Bob. Then they run a privacy
ampliﬁcation step to extract a secret key from their strings.
In Section 4 we used these error correction and privacy ampliﬁcation
procedures to get a secret key from any min-entropy resource. Here, we show
that a standard QKD security proof, but with the post-processing omitted,
dis = (π dis , π dis )
constructs such a min-entropy resource. More precisely, let πAB
A
B
be a protocol that distributes quantum states using an insecure channel Q,
then uses an authentic channel Ac to compare the measurement results,
and either aborts or produces two (random) strings X and Y . Let Eve have
access to the quantum channel and apply any operation allowed by quantum
mechanics to the states being sent, and let her obtain a transcript of the
messages sent on the classical authentic channel. We prove below that if we
dis constructs a mincan bound the information Eve has about X, then πAB
entropy resource.
Proving that we can bound the information Eve has about X is the
diﬃcult part of QKD security proofs. Here we only show that if this can be
done, then the protocol can be written as a constructive statement in the AC
framework. An overview of how one can actually bound Eve’s information
can be found in [23], and detailed security proofs for BB84 and BBM92 that
compute these bounds are given in [14].
dis = (π dis , π dis ) be a protocol as described above. SupLemma C.1. Let πAB
A
B
pose that one can prove that the subnormalized state σXY E resulting from
δ (X|E) ≥ k. And let Hk,δ
Alice and Bob not aborting is such that Hmin
σ
min
be a (k, δ)-min-entropy resource where the output Y at Bob’s interface is
dis (perfectly) constructs
arbitrary (but is always ⊥ if Alice’s is ⊥). Then πAB
24

A detailed review of QKD can be found in [23].

47

k,δ

Hmin from QkAc ,
π dis ,0

k,δ

−−→ Hmin .
QkAc −−AB
k,δ

dis (QkAc ) ⊂ H
Proof. We will show that πAB
min . By contradiction, suppose
k,δ

dis (QkAc ) such that H ∈
there exists H ∈ πAB
/ Hmin . This means there must
exist an S such that the output ρXE = |⊥ih⊥| ⊗ τE + σXE after interacting
δ (X|E) < k. By running such a system S, Eve would thus
with H has Hmin
σ
obtain more information about the string X than allowed.

If no adversary is eavesdropping on the quantum channel Q, but instead
it is only subject to natural noise, then one can make stronger statements
than Lemma C.1 in which Y is not arbitrary, but a bound on the number
of errors between X and Y is known, and the probability of aborting is
also bounded. Such statements are necessary for proving the robustness of
the protocols, i.e., the probability that they terminate with a shared secret
key when only natural noise is present (see [21] for a formal treatment of
robustness in QKD.)
For example, instead of an insecure channel Q, let the players share a
noisy channel speciﬁcation C such as the depolarizing channels depicted in
Figure 1b. Then one can often prove statements such as
π dis ,εnoise

k,δ

AB
−−−−→ Rmin ,
CkAc −−

k,δ

(27)

k,δ

where Rmin ⊂ Hmin is a speciﬁcation of min-entropy resources that never
aborts and outputs strings X and Y with speciﬁc correlations (e.g., no more
than t bit ﬂips).
Composing Corollary 4.7, Lemma C.1, and Eq. (27), we recover the standard QKD security statement [21].
Corollary C.2. Let π qkd = π pa ◦ π ec ◦ π dis consist of the composition of the
protocols described here and Section 4, then
π qkd ,εnoise +εpa +2δ

CkAc −−−−−−−−−−−−→ Km ,
and
π qkd ,εverif +εpa +2δ

QkAc −−−−−−−−−−−→ Km ,
where Ac = Ac1 kAc2 kAc3 , and Aci are the authentic channels used by the
different parts of the protocol.

48

D
D.1

Technical Lemmas
Min-entropy inequalities

The following inequality shows that if an additional r bit string Z is given
to the adversary, then she gets r bits of information.
Lemma D.1 ([45, Lemma 11]). Let ρ ∈ S≤ (HABZ ) be any subnormalized
state where Z is a classical system over the alphabet Z. Then
δ
δ
Hmin
(A|BZ)ρ ≥ Hmin
(A|B)ρ − log |Z|.

The next inequality shows that the min-entropy of a state conditioned
on an event is bounded by the min-entropy before this conditioning.
Lemma D.2. Let ρ ∈ S≤ (HABZ ) be any subnormalized state with a binary
classical register Z. This state may be written as
ρABZ = ρ0AB ⊗ |0ih0| + ρ1AB ⊗ |1ih1|.
Then
δ
δ
(A|B)ρ .
Hmin
(A|B)ρ0 ≥ Hmin

Proof. Follows from [14, Lemma 10] by taking X to be empty, Y = Z and
√
Ω : Y → {0, 1} is the identity. We also remove the condition δ ∈ [0, tr ρ)
by deﬁning Hmin (A|B)ρ = +∞ if tr ρ = 0.

D.2

Extractors

Extractors are usually deﬁned on normalized states. We show here than
any extractor for normalized states is also an extractor for subnormalized
states. This proof follows the steps of an equivalent proof for multi-source
extractors in the Markov model from [46, Lemma 37], but is adapted to
seeded extractors.
Lemma D.3. If Ext is a quantum-proof (k, ε)-strong extractor for normalized states, then it is a quantum-proof (k + 1, 2ε)-strong extractor for
subnormalized states.
Proof. Let ρXE ∈ S≤ (HXE ) be a subnormalized state with Hmin (X|E)ρ ≥
k + 1, and let p = tr(ρXE ). We deﬁne ρ̃E := 1−p
p ρE and the normalized state
σXEP := ρXE ⊗ |0ih0|P + τX ⊗ ρ̃E ⊗ |1ih1|P ,
where τX is the fully mixed state.
This state satisﬁes a slightly modiﬁed min-entropy condition:
pguess (X|EP )σ = pguess (X|E)ρ + pguess (X|E)τ ⊗ρ̃
≤ 2−k−1 + (1 − p)2−n ≤ 2−k ,
49

(28)

where n is the length of the string X. Hence Hmin (X|EP )σ ≥ k. And
because Ext is an extractor for normalized states it follows that
1
σ
− τK ⊗ τZ ⊗ σEP
2 Ext(X,Z)ZEP

tr

≤ ε.

Plugging in Eq. (28) and tracing out P , we get
1
ρ
− τExt(X,Z)Z ⊗ ρ̃E − τK ⊗ τZ ⊗ ρE + τK ⊗ τZ ⊗ ρ̃E
2 Ext(X,Z)ZE

tr

≤ ε.

Thus starting from the expression kρExt(X,Z)ZE − τK ⊗ τZ ⊗ ρE ktr and then
adding and subtracting the term τExt(X,Z)Z ⊗ ρ̃E − τK ⊗ τZ ⊗ ρ̃E as well as
applying the triangle inequality leaves us with
1
ρ
− τK ⊗ τZ ⊗ ρE tr
2 Ext(X,Z)ZE
1
≤ ε + τExt(X,Z)Z ⊗ ρ̃E − τK ⊗ τZ ⊗ ρ̃E tr
2
1
≤ ε + tr(ρ̃E ) τExt(X,Z)Z − τK ⊗ τZ tr ≤ 2ε.
2
The following lemma shows that any extractor deﬁned for subnormalized
states can be used to extract from states with a bound on the smooth minentropy instead of on the min-entropy with a small adjustment to the error
parameter. Note that the original lemma from [39, Lemma 3.5] omitted to
specify that the extractor has to be deﬁned for subnormalized states for the
proof to go through.
Lemma D.4 ([39, Lemma 3.5]). If Ext is a quantum-proof (k, ε)-strong extractor for subnormalized states, then for any subnormalized ρXE ∈ S≤ (HXE )
δ (X|E) ≥ k, and a uniform Z,
with classical X and Hmin
ρ
1
ρ
− τ K ⊗ τ Z ⊗ ρE
2 Ext(X,Z)ZE

tr

≤ ε + 2δ,

where τK is the fully mixed state.
The ﬁnal extractor lemma that we need states that the composition of
two extractors is also an extractor, and is also taken from [39].
Lemma D.5 ([39, Lemma A.4]). Let Ext1 : {0, 1}n × {0, 1}d1 → {0, 1}m1
and Ext2 : {0, 1}n × {0, 1}d2 → {0, 1}m2 be quantum-proof (k, ε1 )- and (k −
m1 , ε2 )-strong extractors for subnormalized states. Then the composition of
the two, namely
Ext3 :{0, 1}n × {0, 1}d1 +d2 → {0, 1}m1 +m2

(x, y1 ky2 ) 7→ Ext1 (x, y1 )k Ext2 (x, y2 ),

is a quantum-proof (k, ε1 + ε2 )-strong extractor for subnormalized states.
50

D.3

Key-Privacy and uniformity

The lemmas in this section are all from [19]. The ﬁrst states that a speciﬁc
kind of extractor can provides ν-key-privacy (Deﬁnition 5.1) and uniformity
(Deﬁnition 5.2).
Lemma D.6 ([19, Proposition 2]). Let Ext : {0, 1}n × {0, 1}r−m → {0, 1}m
be a quantum-proof
(k, ε)-strong extractors for subnormalized states for any
√
k and ε = ν2 2−k+m . And let h : {0, 1}n × {0, 1}r → {0, 1}m be defined as
h(x, ℓ1 kℓ2 ) := Ext(x, ℓ1 ) ⊕ ℓ2 . Then h provides ν-key-privacy.
The next lemma shows that the composition of two functions that provide key-privacy results in a new function also providing key-privacy. The
same holds for uniformity.
Lemma D.7 ([19, Proposition 4]). Let h1 : X ×L1 → T1 and h2 : (X × T1 )×
L2 → T2 be two functions. We define h : X × (L1 × L2 ) → (T1 × T2 ) with
h(x, ℓ1 kℓ2 ) := tkh2 (xkt, ℓ2 ) where t := h1 (x, ℓ1 ). If h1 and h2 provide ν1 and
ν2 -key-privacy, respectively, then h provides ν1 + ν2 -key-privacy. And if h1
and h2 are both uniform, then h is uniform.

D.4

Guessing Games

The lemmas in this section are also from [19]. They are concerned with a
setting in which diﬀerent players sharing a quantum state are trying to guess
the outcome of a measurement performed by one of them.
θ
θ
θ
In the following we denote n EPR pairs by Φ+
AB , and Px = H |xihx|H
denotes a projector, which we use to measure qubits in either the computational or diagonal basis. Note that by measuring half of EPR pairs with
these projectors, the other half results in the state H θ |xihx|H θ , i.e.,
trA

i


h
1
θ
= n H θ |xihx|H θ .
P
⊗
I
Pxθ ⊗ IB Φ+
B
x
AB
2

Given two registers Θ and A, where Θ is classical and A is quantum, we
denote the map which performs this measurement on A according to Θ and
writes the result in a register X as MBB84
ΘA,X , i.e.,
MBB84
ΘA,X (ρΘA ) =

X
θ,x

trA |xihx| ⊗

h

i


|θihθ| ⊗ Pxθ ρΘAB |θihθ| ⊗ Pxθ .

The ﬁrst lemma considers a two player setting, where one player obtains
the measurement outcome X and the second player wants to guess it.
Lemma D.8 ([19, Corollary 2]). Let ρΘE be any cq-state, where the strings
θ ∈ C ⊂ {0, 1}n are taken from a code C with minimal distance d, let E :

51

L(HE ) → L(HAB ) be any CPTP map where L(HA ) is an n qubit Hilbert
space, and let σXΘB := MBB84
ΘA,X ◦ E(ρΘE ). Then


|C|
pguess (X|B)σ ≤ pguess (Θ|E)ρ 1 + d/2 .
2
The second lemma considers a three player setting. The ﬁrst player
obtains the measurement outcome X, the second one has to get an outcome
X ′ that is close to X and the third one wants to guess X. Note that in this
setting, the all players have access to Θ.
Lemma D.9 ([19, Corollary 3, Remark 6]). Let ρΘE be any cq-state, where
the strings θ ∈ C ⊂ {0, 1}n are taken from a code C with minimal distance
d. Let E : L(HE ) → L(HABC ) be any CPTP map where L(HA ) and L(HB )
BB84
are an n qubit Hilbert spaces. Let σXX ′ ΘC := MBB84
ΘA,X ◦ MΘB,X ′ ◦ E(ρΘE ),
i.e., both A and B are measured according to Θ and the results are written
1
in X and X ′ , respectively. Finally, let σXX
′ ΘC be the projection of σXX ′ ΘC
′
on the space with w(X, X ) ≤ ϕn. Then
!
|C|2h(ϕ)n
.
pguess (X|ΘC)σ1 ≤ pguess (Θ|E)ρ 1 +
2d

Acknowledgments
CP if grateful to Serge Fehr for lively conversations on composable security,
and for a lot of help understanding his paper. He would also like to thank
Ueli Maurer for discussions on Constructive Cryptography, and Renato Renner for commenting on an initial draft of this work and proposing many of
the ideas used in this paper.
CP is partially supported by the US Air Force Oﬃce of Scientiﬁc Research (AFOSR) via grant FA9550-16-1-0245, the Swiss National Science
Foundation (via the National Centre of Competence in Research ‘Quantum
Science and Technology’), and the Zurich Information Security and Privacy
Center.

References
[1] Ran Canetti. Universally composable security: A new paradigm for
cryptographic protocols. In Proceedings of the 42nd Symposium on
Foundations of Computer Science, FOCS ’01, pages 136–145. IEEE,
2001. [doi:10.1109/SFCS.2001.959888].
[2] Ran Canetti. Universally composable security: A new paradigm for
cryptographic protocols. Cryptology ePrint Archive, Report 2000/067,
2013. Updated version of [1]. [IACR e-print: 2000/067].
52

[3] Ueli Maurer and Renato Renner. Abstract cryptography. In Proceedings
of Innovations in Computer Science, ICS 2011, pages 1–21. Tsinghua
University Press, 2011.
[4] Ueli Maurer and Renato Renner. From indiﬀerentiability to constructive cryptography (and back). In Theory of Cryptography, Proceedings
of TCC 2016-B, Part I, volume 9985 of Lecture Notes in Computer
Science, pages 3–24. Springer, 2016. [doi:10.1007/978-3-662-53641-4 1,
IACR e-print: 2016/903].
[5] Lı́dia del Rio.
Resource theories of knowledge.
PhD thesis, Swiss Federal Institute of Technology (ETH) Zurich, 2015.
[doi:10.3929/ethz-a-010553983].
[6] Lı́dia del Rio, Lea Kraemer, and Renato Renner. Resource theories of
knowledge. Eprint, 2015. [arXiv:1511.08818].
[7] Renato Renner. Security of Quantum Key Distribution. PhD thesis,
Swiss Federal Institute of Technology (ETH) Zurich, September 2005.
[arXiv:quant-ph/0512258].
[8] Ueli Maurer. Secret key agreement by public discussion. IEEE Transaction on Information Theory, 39(3):733–742, May 1993. A preliminary
version appeared at CRYPTO ’92. [doi:10.1109/18.256484].
[9] Rudolph Ahlswede and Imre Csiszár. Common randomness in information theory and cryptography—Part I: Secret sharing. IEEE
Transactions on Information Theory, 39(4):1121–1132, July 1993.
[doi:10.1109/18.243431].
[10] Renato Renner and Stefan Wolf. Simple and tight bounds for information reconciliation and privacy ampliﬁcation. In Advances in Cryptology
– ASIACRYPT 2005, volume 3788 of Lecture Notes in Computer Science, pages 199–216. Springer, 2005. [doi:10.1007/11593447 11].
[11] Charles H. Bennett and Gilles Brassard. Quantum cryptography: Public key distribution and coin tossing. In Proceedings of IEEE International Conference on Computers, Systems, and Signal Processing, pages
175–179, 1984.
[12] Marco Tomamichel, Charles Ci Wen Lim, Nicolas Gisin, and Renato Renner.
Tight ﬁnite-key analysis for quantum cryptography. Nature Communications, 3:634, 2012. [doi:10.1038/ncomms1631,
arXiv:1103.4130].
[13] Masahito Hayashi and Toyohiro Tsurumaru. Concise and tight
security analysis of the Bennett-Brassard 1984 protocol with ﬁ53

nite key lengths.
New Journal of Physics, 14(9):093014, 2012.
[doi:10.1088/1367-2630/14/9/093014, arXiv:1107.0589].
[14] Marco Tomamichel and Anthony Leverrier. A largely self-contained
and complete security proof for quantum key distribution. Eprint, 2015.
[arXiv:1506.08458].
[15] Jonathan Barrett, Lucien Hardy, and Adrian Kent. No signaling and
quantum key distribution. Physical Review Letters, 95:010503, June
2005. [doi:10.1103/PhysRevLett.95.010503, arXiv:quant-ph/0405101].
[16] Stefano Pironio, Antonio Acı́n, Nicolas Brunner, Nicolas Gisin,
Serge Massar, and Valerio Scarani. Device-independent quantum
key distribution secure against collective attacks. New Journal of
Physics, 11(4):045021, 2009.
[doi:10.1088/1367-2630/11/4/045021,
arXiv:0903.4460].
[17] Umesh Vazirani and Thomas Vidick. Fully device-independent quantum key distribution. Physical Review Letters, 113:140501, September
2014. [doi:10.1103/PhysRevLett.113.140501, arXiv:1210.1810].
[18] Rotem Arnon-Friedman, Renato Renner, and Thomas Vidick. Simple and tight device-independent security proofs.
Eprint, 2016.
[arXiv:1607.01797].
[19] Serge Fehr and Louis Salvail. Quantum authentication and encryption
with key recycling. In Advances in Cryptology – EUROCRYPT 2017,
Proceedings, Part III, volume 10212 of Lecture Notes in Computer Science, pages 311–338. Springer, 2017. [doi:10.1007/978-3-319-56617-7 11,
IACR e-print: 2017/102].
[20] Serge Fehr and Louis Salvail. Quantum authentication and encryption with key recycling. Eprint, 2017. Extended version of [19].
[arXiv:1610.05614].
[21] Christopher Portmann and Renato Renner. Cryptographic security of
quantum key distribution. Eprint, 2014. [arXiv:1409.3525].
[22] Charles H. Bennett, Gilles Brassard, and Seth Breidbart. Quantum
cryptography II: How to re-use a one-time pad safely even if P=NP.
Original unpublished manuscript uploaded to arXiv in 2014, 1982.
[arXiv:1407.0451].
[23] Valerio Scarani, Helle Bechmann-Pasquinucci, Nicolas J. Cerf, Miloslav
Dušek, Norbert Lütkenhaus, and Momtchil Peev. The security of
practical quantum key distribution. Reviews of Modern Physics,
81:1301–1350, September 2009. [doi:10.1103/RevModPhys.81.1301,
arXiv:0802.4155].
54

[24] Christopher Portmann. Key recycling in authentication. IEEE
Transactions on Information Theory, 60(7):4383–4396, July 2014.
[doi:10.1109/TIT.2014.2317312, arXiv:1202.1229].
[25] Ueli Maurer. Constructive cryptography—a new paradigm for security
deﬁnitions and proofs. In Proceedings of Theory of Security and Applications, TOSCA 2011, volume 6993 of Lecture Notes in Computer Science,
pages 33–56. Springer, 2012. [doi:10.1007/978-3-642-27375-9 3].
[26] Christopher Portmann, Christian Matt, Ueli Maurer, Renato Renner,
and Björn Tackmann. Causal boxes: Quantum information-processing
systems closed under composition. IEEE Transactions on Information
Theory, 63(5):3277–3305, May 2017. [doi:10.1109/TIT.2017.2676805,
arXiv:1512.02240].
[27] Gus Gutoski and John Watrous. Toward a general theory of quantum
games. In Proceedings of the 39th Symposium on Theory of Computing,
STOC ’07, pages 565–574. ACM, 2007. [doi:10.1145/1250790.1250873,
arXiv:quant-ph/0611234].
[28] Gus Gutoski. On a measure of distance for quantum strategies. Journal
of Mathematical Physics, 53(3):032202, 2012. [doi:10.1063/1.3693621,
arXiv:1008.4636].
[29] Giulio Chiribella, Giacomo Mauro D’Ariano, and Paolo Perinotti. Theoretical framework for quantum networks. Physical Review A, 80:022339,
August 2009. [doi:10.1103/PhysRevA.80.022339, arXiv:0904.4483].
[30] Lucien Hardy. Reformulating and reconstructing quantum theory.
Eprint, 2011. [arXiv:1104.2066].
[31] Lucien Hardy. The operator tensor formulation of quantum theory.
Philosophical Transactions of the Royal Society of London A: Mathematical, Physical and Engineering Sciences, 370(1971):3385–3417, 2012.
[doi:10.1098/rsta.2011.0326, arXiv:1201.4390].
[32] Lucien Hardy.
Quantum theory with bold operator tensors.
Philosophical Transactions of the Royal Society of London A:
Mathematical, Physical and Engineering Sciences, 373(2047), 2015.
[doi:10.1098/rsta.2014.0239].
[33] Marco Tomamichel, Roger Colbeck, and Renato Renner. Duality between smooth min- and max-entropies. IEEE Transactions on Information Theory, 56(9):4674–4681, 2010. [doi:10.1109/TIT.2010.2054130,
arXiv:0907.5238].

55

[34] Charles H. Bennett, Gilles Brassard, Claude Crépeau, and Ueli Maurer.
Generalized privacy ampliﬁcation. IEEE Transaction on Information
Theory, 41(6):1915–1923, November 1995. [doi:10.1109/18.476316].
[35] Renato Renner and Robert König.
Universally composable privacy ampliﬁcation against quantum adversaries.
In Theory of
Cryptography, Proceedings of TCC 2005, volume 3378 of Lecture Notes in Computer Science, pages 407–425. Springer, 2005.
[doi:10.1007/978-3-540-30576-7 22, arXiv:quant-ph/0403133].
[36] Serge Fehr and Christian Schaﬀner. Randomness extraction via δbiased masking in the presence of a quantum attacker. In Theory of Cryptography, Proceedings of TCC 2008, volume 4948 of
Lecture Notes in Computer Science, pages 465–481. Springer, 2008.
[doi:10.1007/978-3-540-78524-8 26, arXiv:0706.2606].
[37] Marco Tomamichel, Christian Schaﬀner, Adam Smith, and Renato Renner. Leftover hashing against quantum side information. IEEE Transactions on Information Theory, 57(8):5524–5535, August 2011. A preleminary version appeared at ISIT 2010. [doi:10.1109/TIT.2011.2158473,
arXiv:1002.2436].
[38] Masahito Hayashi and Toyohiro Tsurumaru. More eﬃcient privacy
ampliﬁcation with less random seeds via dual universal hash function. IEEE Transactions on Information Theory, 62(4):2213–2232,
April 2016. [doi:10.1109/TIT.2016.2526018, arXiv:1311.5322].
[39] Anindya De, Christopher Portmann, Thomas Vidick, and Renato
Renner.
Trevisan’s extractor in the presence of quantum side
information. SIAM Journal on Computing, 41(4):915–940, 2012.
[doi:10.1137/100813683, arXiv:0912.5514].
[40] Mark N. Wegman and Larry Carter. New hash functions and their use
in authentication and set equality. Journal of Computer and System
Sciences, 22(3):265–279, 1981.
[41] Douglas R. Stinson. Universal hashing and authentication codes. Designs, Codes and Cryptography, 4(3):369–380, 1994. A preliminary version appeared at CRYPTO ’91. [doi:10.1007/BF01388651].
[42] Michael A. Nielsen and Isaac L. Chuang. Quantum Computation and
Quantum Information. Cambridge University Press, 2000.
[43] John Watrous. Theory of quantum information, 2016. Book draft,
https://cs.uwaterloo.ca/~watrous/TQI/.

56

[44] Robert König, Renato Renner, and Christian Schaﬀner. The operational meaning of min- and max-entropy. IEEE Transactions on Information Theory, 55(9):4337–4347, 2009. [arXiv:0807.1338].
[45] Severin Winkler, Marco Tomamichel, Stefan Hengl, and Renato Renner.
Impossibility of growing quantum bit commitments.
Physical Review Letters, 107:090502, August 2011.
[doi:10.1103/PhysRevLett.107.090502, arXiv:1105.1165].
[46] Rotem Arnon-Friedman, Christopher Portmann, and Volkher B. Scholz.
Quantum-proof multi-source randomness extractors in the Markov
model. In 11th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2016), volume 61
of Leibniz International Proceedings in Informatics (LIPIcs), pages
2:1–2:34. Schloss Dagstuhl, 2016. [doi:10.4230/LIPIcs.TQC.2016.2,
arXiv:1510.06743].

57

