Instructions: To add a question/comment to a specific line, equation, table or graph simply click on it.
Click on the annotations on the left side of the paper to read and reply to the questions and comments.
A largely self-contained and complete security
proof for quantum key distribution
Marco Tomamichel
1
and Anthony Leverrier
2
1
Centre for Quantum Software and Information, University of Technology Sydney, Australia
2
Inria Paris, France
July 11, 2017
In this work we present a security analysis for quantum key distribution, establishing a rigorous
tradeoﬀ between various protocol and security parameters for a class of entanglement-based and
prepare-and-measure protocols. The goal of this paper is twofold: 1) to review and clarify the state-
of-the-art security analysis based on entropic uncertainty relations, and 2) to provide an accessible
resource for researchers interested in a security analysis of quantum cryptographic protocols that
takes into account ﬁnite resource eﬀects. For this purpose we collect and clarify several arguments
spread in the literature on the subject with the goal of making this treatment largely self-contained.
More precisely, we focus on a class of prepare-and-measure protocols based on the Bennett-
Brassard (BB84) protocol as well as a class of entanglement-based protocols similar to the Bennett-
Brassard-Mermin (BBM92) protocol. We carefully formalize the diﬀerent steps in these protocols,
including randomization, measurement, parameter estimation, error correction and privacy ampli-
ﬁcation, allowing us to be mathematically precise throughout the security analysis. We start from
an operational deﬁnition of what it means for a quantum key distribution protocol to be secure and
derive simple conditions that serve as suﬃcient condition for secrecy and correctness. We then derive
and eventually discuss tradeoﬀ relations between the block length of the classical computation, the
noise tolerance, the secret key length and the security parameters for our protocols. Our results
signiﬁcantly improve upon previously reported tradeoﬀs.
1 Introduction
Quantum key distribution (QKD) is a cryptographic task that allows two distant parties, Alice and Bob, to
exchange secret keys and communicate securely over an untrusted quantum channel, provided they have access
to an authenticated classical channel. The ﬁrst QKD protocol, BB84, was proposed by Bennett and Brassard
[1] more than three decades ago and the last 30 years have witnessed staggering experimental advances, making
QKD the ﬁrst quantum information technology. With the advent of quantum information theory, Ekert [2]
oﬀered a fruitful new perspective on quantum key distribution by casting it in terms of quantum entanglement
and Bell nonlocality and it was quickly noted that the original BB84 protocol can be seen in this light as well [3].
This new perspective was particularly useful for the development of formal security proofs of QKD.
Formalizing the intuitive security arguments accompanying the ﬁrst protocols has proven to be challenging.
Early proofs by Lo and Chau [4], Shor and Preskill [5], and Mayers [6] successfully attacked the problem in the
asymptotic limit of inﬁnitely many exchanged quantum signals (and unbounded classical computing power).
A later work by Koashi [7] ﬁrst brought to light that security can be certiﬁed using an entropic form [8] of
Heisenberg’s uncertainty principle [9]. However, these works all lacked a convincing treatment of the security
tradeoﬀ in a more realistic regime where the number of exchanged signals and the classical computing power
(i.e., the length of the bit strings computations are performed on) are necessarily ﬁnite, and the ﬁnal secret key
is thus also of ﬁnite length. As absolute security is no longer feasible, the ﬁrst and most crucial question arising
in this ﬁnite regime is how to properly deﬁne approximate security of a cryptographic protocol. Following
developments in classical cryptography, Renner [10] extended the concept of composable security to quantum
key distribution and established a ﬁrst security proof for ﬁnite key lengths. This security analysis essentially
established a tradeoﬀ between diﬀerent parameters of a quantum key distribution protocol:
Marco Tomamichel: marco.tomamichel@uts.edu.au, http://www.marcotom.info
Anthony Leverrier: anthony.leverrier@inria.fr, https://who.paris.inria.fr/Anthony.Leverrier
Accepted in Quantum 2017-06-08, click title to verify 1
arXiv:1506.08458v3 [quant-ph] 10 Jul 2017
Block length: During the run of the protocol the two honest parties, typically called Alice and Bob, prepare,
send and measure quantum signals and store the results of these measurements in bit strings that they store
on their respective (classical) computers. These bit strings will eventually be used to check for the presence
of an interfering eavesdropper and to compute a secret key. As these strings get longer it gets easier to
guard against eavesdroppers and secret keys can be extracted more eﬃciently. On the other hand there
are limitations on the length because we would like to start producing a secret key as early as possible
1
and because computations on longer strings get more and more diﬃcult. The length of the bit strings
used in the protocol is called the block length. Current experimental and commercial implementations of
quantum key distribution typically work with block lengths of the order 10
5
10
6
whereas block lengths
of the order 10
7
10
8
can be achieved, but require an extreme stability of the system during the several
hours required to collect the data [11], [12].
Key length: The secret key length is the length of the secret key (in bits) that is extracted from a single block
of measurement data. An ideal secret key is a uniformly random bit string perfectly correlated between
Alice and Bob and independent of any information the eavesdropper might have collected after the run of
the protocol. The ratio of the key length to the block length is a key performance indicator of quantum
key distribution systems.
Security parameters: Modern security deﬁnitions for quantum key distribution rely on approximate indis-
tinguishability from an ideal protocol, which ensures that the resulting key can be safely used in any other
(secure) application. In this case, the ideal protocol either has the two parties produce an ideal secret
key or an abort ﬂag that indicates that no secret key can be extracted, either because an eavesdropper
is present, or more mundanely because the quantum channel is too noisy. The security parameter is the
distinguishing advantage between the real and the ideal protocols, given by the diamond norm distance
between the two protocols. Evidently we would like this parameter to be very small and while there is no
consensus on what value it should have we will take it to be 10
10
for our numerical examples.
Robustness: According to the notion of security discussed above, a quantum key distribution protocol can be
perfectly secure and completely useless because it always aborts. As an additional requirement we thus
impose that the protocol succeeds with high probability when the quantum channel is subject to noise
below a speciﬁc (and realistic) threshold. This describes the robustness of the protocol against noise, that
is, the probability that the protocol returns a nontrivial key for a given noise level. The noise model
used should capture the dynamics of the quantum channel in the expected ﬁeld operation; however, the
exact speciﬁcation of the noise model and whether the noise is caused by an eavesdropper or just by
the undisturbed operation of the channel is independent of any security considerations and can thus
be treated independently. The robustness, and more speciﬁcally the values of the channel parameters for
which the robustness goes to zero, is an important ﬁgure of merit to compare the expected performance
of various protocols.
The tradeoﬀs between these parameters have been signiﬁcantly improved since Renner’s proof [10], in par-
ticular by Tomamichel et al. [13] and Hayashi and Tsurumaru [14], so that the proofs are now suﬃciently tight
to provide security for realistic implementations of quantum key distribution. The present analysis will mostly
follow the approach in the former paper [13].
So what justiﬁes us revisiting this problem here? Firstly, we believe that presenting a complete and rigorous
security proof in a single article will make the topic of ﬁnite size security more accessible to researchers in
quantum cryptography. Secondly, thanks to some improvements in the technical derivation and a steamlining
of the analysis, our proof yields signiﬁcantly stronger tradeoﬀ relations between security and performance
parameters. It is worth noting here that strengthening theoretical tradeoﬀ relations of a QKD protocol has
rather direct implications for practical implementations as it allows for the generation of more secure key at the
same noise level without any changes to the hardware. Thirdly, although all the necessary technical ingredients
and conceptual insights are present in the literature, we were not able to ﬁnd a concise security proof for any
QKD protocol that satisﬁes the following two stringent criteria:
1. The protocol is able to extract a composably secure key for reasonable parameters (i.e. realistic noise levels,
security parameters and block lengths that can be handled with state-of-the-art computer hardware).
2. The protocol and all the assumptions on the physical devices used in the protocol are completely speciﬁed
and all aspects of the protocol are formalized, including the randomness that is required and all the
communication transcripts that are produced.
1
This is most relevant for implementations that suﬀer from a low rate of measurement events, e.g. entanglement-based imple-
mentations.
Accepted in Quantum 2017-06-08, click title to verify 2
The second point may appear trivial but we believe the absence of a complete formalization of all aspects of
a protocol found in many research papers presents a major obstacle in verifying the proofs and learning about
the security of quantum key distribution and quantum cryptography in general. It is in fact common in much
of the present literature to fully formalize some aspects of a security proof while keeping other aspects vague
and informal and this has lead to various misconceptions.
Let us illuminate this issue with an example. It is often argued (e.g. in [15]) that collective attacks (where the
eavesdropper attacks every quantum signal exchanged between Alice and Bob in the same way) are optimal for
the eavesdropper using symmetry and de-Finetti arguments [16, 17]. To get such symmetry it is at some point
or another used that measurements are performed in a random basis or that a random subset of raw key bits
are used for parameter estimation. However, complete security proofs also must allow for the protocol to abort
in case certain thresholds are not met, and one is then left to analyze the state of the system conditioned on the
fact that the protocol does not abort. This conditioning will in general introduce correlations between the state
held by Alice and Bob and the seeds used to choose the measurement bases and parameter estimation subset,
violating the strict symmetry assumptions. Even if these correlations are weak in typical cases, they prove
problematic since they allow the eavesdropper to slightly inﬂuence Alice and Bob’s measurement devices
2
,
something which is usually explicitly forbidden in security proofs for quantum key distribution with trusted
devices. Hence, many simple arguments based on symmetry or independent randomness simply do not go
through without modiﬁcation when the security proof is put under a microscope.
As mentioned above, the early asymptotic proofs fail with Point 1. Moreover, while Renner’s analysis [10]
gives bounds for ﬁnite keys, these are not suﬃcient to pass Point 1 since the bounds are not strong enough for
realistic key lengths.
3
More recent security proofs by Tomamichel et al. [13] and Hayashi and Tsurumaru [14]
satisfy Point 1, but they are not fully formalized and thus do not satisfy Point 2.
4
In fact, our requirements in
Point 2 are very stringent and we are not aware of any security proof that has met this level of rigor, except
arguably Renner’s thesis [10]. A recent security proof for the one-sided device-independent setting [20] satisﬁes
Point 2 but provides a key rate that is not optimal asymptotically.
Results and Outline. In the present paper, we give a rigorous and largely self-contained security proof for
QKD that satisﬁes the two conditions above. The proof is based on the security analysis in [13] and uses an
entropic uncertainty relation [21] as its main ingredient. A few additional technical results and modiﬁcations
of previous results are needed. We hope that our proof is accessible to all researchers interested in the security
of quantum cryptography. As such, our treatment does not require the reader to have prior knowledge of
various tricks and security reductions in quantum cryptography, but presumes a solid understanding of the
mathematical foundations of quantum information theory.
The remainder of this manuscript is structured as follows. First we introduce necessary notation and concepts
in Section 2. In Part I we analyze a class of simple entanglement-based protocols reminiscent of the BBM92
protocol [3]. Section 3 formally describes the class of protocols we are using (see also Table 2). Section 4
formally introduces our security deﬁnitions and claims. We discuss our results in Section 5 and provide a
detailed security proof in Section 6. In Part II we move on to a prepare-and-measure protocol that is essentially
equivalent to BB84. Section 7 formally introduces this class of protocols (see also Table 5). We discuss our
results in Section 8 and provide in Section 9 the security reduction from the prepare-and-measure protocol to
the entanglement-based protocol.
2 Formalism and notation
We will summarize some concepts necessary for our formal security proofs here, assuming that the reader is
familiar with the mathematical foundations of quantum information theory. We refer to [22] for a comprehen-
sive introduction into this mathematical toolkit. Sections 2.12.4 are necessary for understanding our main
exposition whereas the concepts introduced in Sections 2.5 will be employed only in the security proof.
2
An example is the following attack in the prepare-and-measure version of BB84: for each state sent by Alice, Eve randomly
chooses to either measure it in the computational basis, or do nothing. Such an attack would only create errors when Bob measures
in the Hadamard basis, and the conditioning on not aborting would therefore slightly favor measurement choices for Bob biased
toward the computational basis.
3
Unfortunately, de Finetti reductions often do not provide good bounds in practice and at least 10
5
or 10
6
uses of the quantum
channel are typically required for the key rate to eﬀectively become nonzero [15, 17, 18].
4
For example, a small ﬂaw in the formalization of the protocol in [13] has recently been pointed out by Pﬁster et al. [19]. While
this does not suggest that the security guarantees in [13] are invalid, it is a stark reminder that Point 2 is often not taken seriously
enough.
Accepted in Quantum 2017-06-08, click title to verify 3
2.1 Quantum systems, states and metrics
Individual quantum systems and the corresponding ﬁnite-dimensional Hilbert spaces are denoted by capital
letters. The dimension of the system A is denoted by |A|. A joint quantum system AB is deﬁned via the
tensor product of the corresponding Hilbert spaces of A and B. We use [m] to denote the set {1, 2, . . . , m}
and use A
[m]
to denote a joint quantum system comprised of quantum systems A
1
A
2
. . . A
m
. Similarly, if the
subscript is a subset of [m], we just refer to the subsystems in the subset. Let us also introduce the notation
Π
m,k
:= {π [m] : |π| = k}, the set of subsets of [m] of size k.
We write S(A) to denote normalized states on A, i.e., positive semi-deﬁnite operators acting on the Hilbert
space A with unit trace. A state is called pure if it the corresponding operator has rank 1. We will employ the
trace distance between states, which is deﬁned as
kρ σk
tr
:= sup
P
tr
P (ρ σ)
, (1)
where P ranges over projectors, i.e. positive semi-deﬁnite operators with eigenvalues in {0, 1}. In particular, we
have kρ σk
tr
=
1
2
kρ σk
1
, where k · k
1
denotes the Schatten 1-norm. The trace distance has an immediate
physical interpretation [23]: for two states with trace distance ε, the maximum probability of distinguishing
them with a single measurement equals
1
2
(1 + ε).
We also collect positive semi-deﬁnite operators with trace norm not exceeding 1 on A in the set S
(A), and
call them sub-normalized states.
5
Sub-normalized states will be very convenient for technical reasons as they
allow us to represent the state of quantum systems and classical events simultaneously. The following metric is
very useful when dealing with sub-normalized states:
Deﬁnition 1 (Puriﬁed distance). For ρ
A
, σ
A
S
(A), we deﬁne the generalized ﬁdelity,
F (ρ
A
, σ
A
) :=
tr
n
q
ρ
A
σ
A
ρ
A
o
+
p
1 tr{ρ
A
}
p
1 tr{σ
A
}
2
, (2)
and the puriﬁed distance, P (ρ
A
, σ
A
) :=
p
1 F (ρ
A
, σ
A
).
The puriﬁed distance is a metric on sub-normalized states and satisﬁes [24, Lemma 2]
P (ρ
A
, σ
A
) P
F(ρ
A
), F(σ
A
)
(3)
for every completely positive (CP) trace non-increasing map F. This means in particular that the distance
contracts when we apply a quantum channel to both states. An important property of the puriﬁed distance [22,
Corollary 3.1] is that for any two states ρ
A
, σ
A
and any extension ρ
AB
of ρ
A
, there exists an extension σ
AB
with P (ρ
AB
, σ
AB
) = P (ρ
A
, σ
B
). (This property is not true in general for the trace distance.) Moreover, it is
related to the trace distance as follows [24, Lemma 6]:
ρ
A
σ
A
tr
+
1
2
tr{ρ
A
} tr{σ
A
}
P (ρ
A
, σ
A
) . (4)
2.2 Classical registers and events
We model discrete random variables by ﬁnite-dimensional quantum systems, called registers, with a ﬁxed or-
thonormal basis. For example, let X X be a random variable with probability law x 7→ P
X
(x). Then we
write the corresponding quantum state as
ρ
X
=
X
x∈X
P
X
(x) |xihx|
X
, (5)
where {|xi}
x∈X
is an orthonormal basis of the space X. Conversely, we write Pr[X = x]
ρ
= P
X
(x).
More generally, the classical register might be correlated with a quantum system A, and this is modeled
using classical-quantum (cq) states:
ρ
XA
=
X
x∈X
P
X
(x) |xihx|
X
ρ
A|X=x
, (6)
5
The disk in the subscript of S
symbolizes the unit disk in trace norm.
Accepted in Quantum 2017-06-08, click title to verify 4
where we use ρ
A|X=x
to denote the quantum state on A conditioned on the register X taking the value x. We
also write Pr[X = x]
ρ
= tr{|xihx|
X
ρ
XA
} = P
X
(x). This convention is extended to arbitrary events deﬁned on
a classical register X, i.e. if Ω : X {0, 1} is an event, we write
Pr[Ω]
ρ
=
X
x∈X
P
X
(x)Ω(x) and ρ
XA
=
X
x∈X
P
X
(x)Ω(x) |xihx|
X
ρ
A|X=x
, (7)
a state that is generally sub-normalized. We will also write ρ
XA|
= Pr[Ω]
1
ρ
ρ
XA
for the conditional state.
For any event Ω : X {0, 1} we denote its complement on X by ¬.
2.3 Quantum channels and measurements
A quantum channel E : A B is a completely positive trace-preserving (CPTP) map that maps operators on
A to operators on B. Prime examples of quantum channels are the trace, denoted tr, and the partial trace over
system A, denoted tr
A
. We will encounter the diamond distance between CPTP maps, which we here deﬁne as
kE Fk
:= sup
ρ
AC
∈S(AC)
kE(ρ
AC
) F(ρ
AC
)k
tr
, (8)
where the optimization goes over joint states on A and an auxiliary system C, and we can assume without
loss of generality that |C| |A|. The diamond distance also inherits the physical interpretation of the trace
distance: for two quantum channels with diamond distance ε, the maximum probability of distinguishing them
by preparing a state on the input system and an ancilla system and then measuring the joint system after
applying the channel equals
1
2
(1 + ε).
A generalized measurement on A is a set of linear operators {M
x
A
}
x∈X
such that
X
x∈X
(M
x
A
)
(M
x
A
) = 1
A
, (9)
where 1
A
denotes the identity operator on A. A measurement on A can be represented as a CPTP map M
AX
that maps states on a quantum system A to measurement outcomes stored in a register X. The measurement
in (9) applied to a bipartite state ρ
AB
yields
M
AX
: ρ
AB
7→ σ
XB
=
X
x∈X
|xihx|
X
tr
A
n
M
x
A
ρ
AB
M
x
A
o
, (10)
where σ
XB
is now a (normalized) classical-quantum state. Finally, let f : X Y be a function acting on two
sets X and Y. We denote by E
f
: X XY the corresponding CPTP map
E
f
[·] =
X
x∈X
|f(x)i
Y
|xihx|
X
· |xihx|
X
hf(x)|
Y
(11)
that acts on general quantum states. Note that we deﬁned the map E
f
such that the input register X is kept
intact and the operation is deterministic and invertible.
2.4 Universal hash functions
Universal hashing is used (at least
6
) twice in the analysis of the quantum key distribution protocol: ﬁrst in the
error correction step to ensure the correctness of the protocol (Theorem 2), and then in the privacy ampliﬁcation
procedure to guarantee the secrecy of the ﬁnal key.
Deﬁnition 2 (Universal
2
Hashing). Let H = {h} be a family of functions from X to Z. The family H is
said to be universal
2
if Pr [H(x) = H(x
0
)] =
1
|Z|
for any pair of distinct elements x, x
0
X, when H is chosen
uniformly at random in H.
In this work we do not need to specify any particular family of hash functions, and it suﬃces to note that
such families of functions always exist if |X| and |Z| are powers of 2. (See, e.g., [25, 26].)
6
Universal hashing is also used to provide authentication of the classical channel, but we will not discuss this issue here.
Accepted in Quantum 2017-06-08, click title to verify 5
2.5 Conditional entropies
Conditional entropies measure the amount of uncertainty present in a random variable from the perspective of
an observer with access to correlated side information. Here we are particularly interested in observers that have
access to a quantum system that serves as side information, for example the eavesdropper’s memory after interfer-
ing with the quantum communication during the run of a quantum key distribution protocol. The most common
measure of entropy is the Shannon or von Neumann entropy, deﬁned as H(X)
ρ
:=
P
x∈X
P
X
(x) log P
X
(x).
However, while this entropy has various operational interpretations in the asymptotic limit of inﬁnite repetitions
of an information processing task, it is insuﬃcient to describe ﬁnite size eﬀects. On the other hand, smooth min-
and max-entropy allow us to capture such ﬁnite size eﬀects and share many properties with the von Neumann
entropy. We will not need the full generality of the smooth entropy formalism here and instead refer to [22] for
a comprehensive introduction.
Min- and max-entropy are natural generalizations of conditional Rényi entropies [27] to the quantum setting
and were ﬁrst proposed by Renner [10] and König et al. [28]. The conditional min-entropy captures how diﬃcult
it is for an observer with access to quantum side information to guess the content of a classical register. For a
bipartite cq state ρ
XB
S(AB), we deﬁne
p
guess
(X|B)
ρ
= sup
{E
x
B
}
X
x∈X
Pr[X = x]
ρ
tr
n
E
x
B
ρ
B|X=x
E
x
B
o
, (12)
where the optimization goes over all generalized measurements on B.
The conditional min-entropy for a cq state is then deﬁned as H
min
(X|B)
ρ
:= log p
guess
(X|B)
ρ
. For later
convenience we introduce the measure more generally for any bipartite, potentially sub-normalized, state:
Deﬁnition 3 (Min-entropy). For any bipartite sub-normalized state ρ
AB
S
(AB), we deﬁne
H
min
(A|B)
ρ
:= sup
λ R : σ
B
S(B) such that ρ
AB
2
λ
id
A
σ
B
,
. (13)
Showing equivalence between this deﬁnition and the special case of cq states in (12) involves semideﬁnite-
programming duality [28] and is outside the scope of this work. We will also encounter the max-entropy, which
is a natural dual of the min-entropy in the following sense:
Deﬁnition 4 (Max-entropy). For any bipartite sub-normalized state ρ
AB
S
(AB), we deﬁne
H
max
(A|B)
ρ
:= H
min
(A|C)
ρ
, (14)
where ρ
ABC
is any pure state with tr
C
{ρ
ABC
} = ρ
AB
.
The max-entropy is a measure of the size of the support of X. In particular, we have the following ordering
of unconditional entropies:
H
min
(X)
ρ
H(X)
ρ
H
max
(X)
ρ
log
{x X : Pr[X = x]
ρ
> 0}
, (15)
which is a consequence of the monotonicity of the Rényi entropies [27] in the order parameter. Here and
We will need a slight generalization of the concepts of conditional min- and max-entropy, which takes into
account a ball of states close to ρ
AB
in terms of the puriﬁed distance introduced in the previous section.
Deﬁnition 5 (Smooth Entropies). For ρ
AB
S
(AB) and ε
h
0,
p
tr(ρ
AB
)
, we deﬁne
H
ε
min
(A|B)
ρ
:= sup
˜ρ
AB
∈S
(AB),
P ( ˜ρ
AB
AB
)ε
H
min
(A|B)
˜ρ
, H
ε
max
(A|B)
ρ
:= inf
˜ρ
AB
∈S
(AB),
P ( ˜ρ
AB
AB
)ε
H
max
(A|B)
˜ρ
. (16)
In the above deﬁnitions we can replace the supremum and inﬁmum with a maximum and minimum, respec-
tively. Roughly speaking, the smooth conditional min-entropy of X given B approximates how much randomness
that is uniform for an observer with access to B can be extracted from X. (This will be made formal when
discussing the Leftover Hashing Lemma in Section 6.4.) The smooth entropies inherit the duality relation [24].
For any pure sub-normalized state ρ
ABC
S
(ABC), we have
H
ε
min
(A|B)
ρ
= H
ε
max
(A|C)
ρ
. (17)
Accepted in Quantum 2017-06-08, click title to verify 6
The smooth entropies also satisfy a data-processing inequality (DPI) [24, Theorem 18]. For any cq state
ρ
XB
and any completely positive trace-preserving map E
BC
, we have
H
ε
min
(X|B)
ρ
H
ε
min
(X|C)
E(ρ)
, and H
ε
max
(X|B)
ρ
H
ε
max
(X|C)
E(ρ)
. (18)
This expresses our intuition that performing any processing of the side information can at most increase our
uncertainty about X. Moreover, we need a simple chain rule [29, Lemma 11], which states that
H
ε
min
(A|BX)
ρ
H
ε
min
(A|B)
ρ
log |X| (19)
where X is a (classical) register of dimension |X|. This corroborates our intuition that an additional bit of side
information on X cannot decrease our uncertainty about X by more than one bit.
We have deﬁned all these quantities for sub-normalized states so that we can easily treat restrictions to
events. Let ρ
AXBY
S(ABXY ) be classical on X and Y and let : X × Y {0, 1} be an event. Then
we denote by H
min
(AX |BY )
ρ
the conditional min-entropy evaluated for the state ρ
AXBY
. Similarly,
H
min
(AX |B)
ρ
denotes the conditional min-entropy evaluated for the marginal ρ
AXB
= tr
Y
{ρ
AXBY
}.
These states are in general sub-normalized. The same notational convention is used for (smooth) min- and
max-entropy.
Part I
Entanglement-based protocol
3 Formal description of the entanglement-based protocol
We ﬁrst focus on class of simple entanglement-based QKD protocols. We give an overview of the protocols
in Table 2. Section 3.1 discusses the assumptions that go into our model, Section 3.2 presents the protocol
parameters, and the detailed mathematical description of the individual steps follows in Section 3.3.
Let us emphasize that by simple protocols, we mean that we restrict our attention to protocols where
the sifting procedure is essentially given for free, meaning that Alice and Bob are assumed to initially share a
quantum state on which all the measurements are performed. Relatedly, we also do not allow for strategies where
the measurement settings are biased towards a speciﬁc value.
7
As discussed in Part II, the sifting procedure
can be analyzed separately under certain assumptions.
3.1 Assumptions of our model
Every mathematical model of physical reality requires some assumptions, and in cryptography it is important to
discuss these assumptions since if they are not met by an implementation then the security guarantees derived
here are also not applicable to this implementation.
Finite-dimensional quantum systems: We assume that Alice’s and Bob’s relevant quantum degrees of
freedom can be eﬀectively represented on a ﬁnite-dimensional Hilbert space. (This requirement is not strictly
necessary to show security but allows us to circumvent some technical pitfalls.)
Sealed laboratories: We assume that the laboratories of Alice and Bob are spatially separated. This allows
us to model joint quantum systems AB shared between Alice and Bob as tensor products of respective local
Hilbert spaces A and B. Moreover, an easily overlooked (an in practice hard to ensure) assumption we need is
that we control exactly what information is released from Alice and Bob’s laboratory.
Random seeds: We assume that Alice has access to uniform randomness (uniformly random seeds). In
practice, the seeds can be produced by a trusted quantum random number generator in Alice’s lab.
8
7
Such strategies are advocated in the literature in order to increase the secret key rate by minimizing the cost of sifting [30].
8
See, for instance, [31] for an analysis of realistic quantum random number generators explaining how randomness originating
from quantum processes can be turned into ideal seeds.
Accepted in Quantum 2017-06-08, click title to verify 7
, X Symbols for abort and passing, respectively
M
φ,x
A
i
Measurement operator acting on register A
i
with setting φ and outcome x
c
i
Parameter quantifying the quality of the measurement on register A
i
¯c Parameter quantifying the overall (average) quality of measurements on A
m Total number of quantum systems shared and measured by Alice and Bob
pe Parameter estimation scheme: pe = {k, δ}
k Length (in bits) of the raw key used for parameter estimation
n = m k Length (in bits) of the raw key used for key distillation
δ Threshold for the parameter estimation test
test Test function used in the parameter estimation step
ec Error correcting scheme: ec = {t, r, synd, corr, H
ec
}
r Length (in bits) of the error correction syndrome
t Length (in bits) of the hash used for veriﬁcation in the error correcting scheme
synd Function computing the error syndrome
corr Function that calculate the corrected string
H
ec
Universal
2
family of hash functions used in the error correcting scheme
pa Privacy ampliﬁcation scheme: pa = {, H
pa
}
Length (in bits) of the ﬁnal key
H
pa
Universal
2
family of hash functions used in the privacy ampliﬁcation scheme
A, B Alice’s and Bob’s initial quantum system
E Eve’s quantum memory
M
AX|S
Measurement map applied on register A with setting S and storing the result in register X
V, W Register for Alice’s and Bob’s classical bits used for parameter estimation
X, Y Register for Alice’s and Bob’s classical bits used for key distillation
Z Register for Alice’s syndrome during error correction
T Register containing the hash of Alice’s raw key during error correction
K
A
, K
B
Register for Alice’s and Bob’s ﬁnal keys
S
Φ
Seed for the choice of the measurement bases in the idealized protocol
S
Π
Seed for the choice of the random subset π Π
m,k
used for parameter estimation
S
Ξ
Seed for the choice of the measurement bases for the subsystems used for parameter estimation
S
Θ
Seed for the choice of the measurement bases for the subsystems used for key distillation
S
H
ec
Seed for the choice of the hash function used in the error correction test
S
H
pa
Seed for the choice of the hash function used in the privacy ampliﬁcation step
S Register corresponding to all the seeds, S = (S
Φ
, S
Π
, S
Ξ
, S
Θ
, S
H
pe
, S
H
ec
, S
H
pa
).
F
pe
Flag for the parameter estimation test
F
ec
Flag for the error correction test
F Register corresponding to all the ﬂags, F = (F
pe
, F
ec
)
C
V
Transcript of the register V sent during parameter estimation
C
Z
, C
T
Transcripts of the registers Z and T sent during error correction
C Register containing all the communication transcripts, C = (C
V
, C
Z
, C
T
)
ρ Quantum state before any measurement took place
τ Quantum state after the registers used for parameter estimation have been measured
σ Quantum state once Alice and Bob’s quantum registers have been entirely measured
ω Quantum state describing the ﬁnal output of the protocol
Table 1: Overview of the nomenclature and notation used in Part I.
Authenticated communication channel: We assume that Alice and Bob share an authenticated public
(classical) communication channel. Everything that is communicated over this channel will be in the public
domain and is thus treated as an output of the protocol. The authentication of the classical channel can be
obtained with information-theoretic security by tagging every classical message [26]. A more detailed discussion
of authentication for QKD is beyond the scope of the present work, and the interested reader is referred
to Portmann and Renner [32, Appendix D].
Deterministic detection: We further assume that Alice and Bob’s measurement devices always output a
valid outcome, either 0 or 1. This is unrealistic in practice since it is often the case that detectors will not
detect the quantum system (due to losses or imperfect detection eﬃciency). A simple ﬁx is then to ﬂip a coin
and use the resulting bit as the measurement output. Unfortunately, this solution artiﬁcially decreases the
robustness of the protocol beyond what is usually tolerable in a practical setting. Another much more practical
solution consists in discarding these “no detection” events, but this should be done with care and requires
Accepted in Quantum 2017-06-08, click title to verify 8
extra-assumptions about the measurement devices to prevent various types of side-channel attacks such as that
of Lydersen et al. [33]. We will discuss this solution in more detail in Part II of this work.
Commuting measurements: The block length is given by a protocol parameter, m, which will be discussed
in Section 3.2. For Alice and Bob to run a protocol with block length m, we need to assume that both can
perform up to m measurements (with either one of two possible settings) on their share of the quantum state
in such a way that the order in which they do these measurements does not aﬀect the resulting measurement
outcome distribution. This is a standard assumption in the model of trusted measurement devices (by opposition
to device-independent cryptography) and ensures that there are no memory eﬀects in the measurement devices.
More formally, we assume that Alice’s and Bob’s share of the quantum system can be decomposed into m
individual quantum systems, A A
[m]
= A
1
A
2
. . . A
m
and B B
[m]
= B
1
B
2
. . . B
m
and that the measurements
can be represented as operators acting on the individual subsystems. We model Alice’s i-th measurement with
setting φ {0, 1} by a binary generalized measurement {M
φ,x
A
i
}
x∈{0,1}
acting on subsystem A
i
. The index
x ranges over the two possible outcomes of Alice’s measurement. Analogously, Bob’s i-th measurement with
setting φ {0, 1} is a binary generalized measurement {M
φ,y
B
i
}
y∈{0,1}
acting on subsystem B
i
. The index y
ranges over the two possible outcomes of Bob’s measurement.
Complementarity of Alice’s measurements: The exact description of the measurement devices will not
be relevant for our derivations. However, we will need to assume that Alice’s measurements are suﬃciently
complementary, a property that is encapsulated by the average overlap, ¯c(m, n) that we introduce next. Let m
be the block length and n the number of bits used for key extraction (see Section 3.2 for a discussion of the
protocol parameters). Let us deﬁne
c
{M
x
}
x
, {N
y
}
y
:= max
x,y∈{0,1}
M
x
N
y
2
, and c
i
:= c
M
0,x
A
i
x
,
M
1,y
A
i
y
. (20)
In an ideal physical implementation of the protocol with complementary measurements (for example in the
computational and Hadamard basis), we would have c
i
=
1
2
for all i [m]. In realistic implementations, its
value will be larger. We assume that there exists a reliable upper bound on c
i
. More precisely, we assume that
¯c(m, n) := max
πΠ
m,n
Y
iπ
c
i
!
1
n
¯c . (21)
We always have c
i
[0, 1] and the condition ¯c < 1 is necessary to ensure secrecy. As long as the commuting
measurement assumption holds, the parameter ¯c can in principle be measured directly in an experiment even
if the operators {M
φ,x
A
i
}
φ,x
are unknown.
9
For Bob we do not need to assume a bound on the complementarity parameter. (We only need to assume
that the measurements commute, as described in the previous item.)
3.2 Protocol parameters and overview
From an information theoretic and mathematical point of view, an entanglement-based QKD protocol is simply
a completely positive trace-preserving (CPTP) map composed of local operations and classical communication
(LOCC) that takes a bipartite state ρ
AB
as an input and either aborts or returns two classical binary strings,
the keys, which should ideally be identical and independent of the knowledge of any third party having access
to a purifying system of ρ
AB
and to the transcript of the communication performed by the protocol.
We consider protocols qkd_eb
m,pe,ec,pa
that are parametrized by the block length, m, and the sub-protocols
for parameter estimation, error correction and privacy ampliﬁcation, respectively denoted by pe, ec, and pa.
The block length, m N, determines the number of individual quantum systems that are shared between
Alice and Bob, and thus available to them for parameter estimation and key extraction.
Parameter estimation is characterized by a tuple pe = {k, δ}, where k N, k m determines the number
of quantum systems used for parameter estimation and δ (0,
1
2
) is the tolerated error rate. Let us for
later convenience also deﬁne n := mk to denote the number of quantum systems used for key generation.
9
See, e.g., [34, 35] for an estimation strategy based on Bell tests.
Accepted in Quantum 2017-06-08, click title to verify 9
(K
A
, K
B
, S, C, F ) = qkd_eb
m,pe,ec,pa
ρ
AB
:
Input: Alice and Bob are given a state ρ
AB
, where A A
[m]
and B B
[m]
are comprised of m quantum
systems each.
Randomization: They agree on a random string Φ {0, 1}
m
, a random subset Π Π
m,k
, and random hash
functions H
ec
H
ec
as well as H
pa
H
pa
. The corresponding uniformly random seeds are denoted
S = (S
Φ
, S
Π
, S
H
ec
, S
H
pa
).
Measurement: Alice and Bob measure the m quantum systems with the setting Φ. They store the binary
measurement outcomes in two strings, the raw keys. These are denoted (X, V ) and (Y, W ) for Alice and
Bob, respectively. Here V, W are of length k and correspond to the indices in Π, whereas X, Y of length
n correspond to indices not in Π.
Parameter Estimation: Alice sends V to Bob, the transcript is denoted C
V
. Bob compares V and W . If
the fraction of errors exceeds δ, Bob sets the ﬂag F
pe
= and they abort. Otherwise he sets F
pe
= X
and they proceed.
Error Correction: Alice sends the syndrome Z = synd(X) to Bob, with transcript C
Z
. Bob computes
ˆ
X = corr(Y, Z).
To verify the success of the error correction step, Alice computes the hash T = H
ec
(X) of length t and
sends it to Bob, with transcript C
T
. Bob computes H
ec
(
ˆ
X). If it diﬀers from T , he sets the ﬂag F
ec
=
and they abort the protocol. Otherwise he sets F
ec
= X and they proceed.
Privacy Ampliﬁcation: They compute keys K
A
= H
pa
(X) and K
B
= H
pa
(
ˆ
X) of length .
Output: The output of the protocol consists of the keys K
A
and K
B
, the seeds S = (S
Φ
, S
Π
, S
H
ec
, S
H
pa
), the
transcript C = (C
V
, C
Z
, C
T
) and the ﬂags F = (F
pe
, F
ec
). In case of abort, we assume that all registers
are initialized to a predetermined value.
Table 2: Simple QKD Protocol. The precise mathematical model is to be found in Section 3.3.
The error correcting scheme is described by a quintuple ec = {t, r, synd, corr, H
ec
}. Here, r N is the
length (in bits) of the error correction syndrome. Moreover, synd and corr are functions of the form
synd : {0, 1}
n
{0, 1}
r
and corr : {0, 1}
n
× {0, 1}
r
{0, 1}
n
used to compute the error syndrome and
calculate the corrected string, respectively. We do not need to assume anything about the structure of
this code. To ﬁx ideas, let us just note that there exist good error correction codes with r nh(δ), where
h is the binary entropy function and δ is the number of errors to be corrected.
10
Finally, t N is the length (in bits) of the hash used for veriﬁcation and H
ec
:=
h
ec
: {0, 1}
n
{0, 1}
t
is
a universal
2
family of hash functions. We will see in Theorem 2 that the size t only depends logarithmically
on the targeted correctness parameter.
Privacy ampliﬁcation is characterized by a tuple pa = {, H
pa
}, where  N with  n is the length (in
bits) of the extracted key and H
pa
:=
h
pa
: {0, 1}
n
{0, 1}

is a universal
2
family of hash functions.
Note that , the length of the ﬁnal key, is ﬁxed. It is in principle possible to design adaptive protocols
where the ﬁnal key length is chosen after parameter estimation, but this is beyond the scope of this work.
This allows us to deﬁne a family of protocols qkd_eb
m,pe,ec,pa
in Table 2. </