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
tradeoff 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 finite resource effects. 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 different steps in these protocols,
including randomization, measurement, parameter estimation, error correction and privacy ampli-
fication, allowing us to be mathematically precise throughout the security analysis. We start from
an operational definition of what it means for a quantum key distribution protocol to be secure and
derive simple conditions that serve as sufficient condition for secrecy and correctness. We then derive
and eventually discuss tradeoff 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
significantly improve upon previously reported tradeoffs.
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 first 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 first quantum information technology. With the advent of quantum information theory, Ekert [2]
offered 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 first 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 infinitely many exchanged quantum signals (and unbounded classical computing power).
A later work by Koashi [7] first brought to light that security can be certified using an entropic form [8] of
Heisenberg’s uncertainty principle [9]. However, these works all lacked a convincing treatment of the security
tradeoff 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 finite, and the final secret key
is thus also of finite length. As absolute security is no longer feasible, the first and most crucial question arising
in this finite regime is how to properly define 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 first security proof for finite key lengths. This security analysis essentially
established a tradeoff between different 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 efficiently. 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 difficult. 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 definitions 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 flag 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 specific (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 field operation; however, the
exact specification 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 specifically the values of the channel parameters for
which the robustness goes to zero, is an important figure of merit to compare the expected performance
of various protocols.
The tradeoffs between these parameters have been significantly 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 sufficiently 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 justifies 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 finite 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 significantly stronger tradeoff relations between security and performance
parameters. It is worth noting here that strengthening theoretical tradeoff 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 find a concise security proof for any
QKD protocol that satisfies 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 specified
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 suffer 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 influence 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 modification 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 finite keys, these are not sufficient 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] satisfies
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 satisfies 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 modifications
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 definitions 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 effectively become nonzero [15, 17, 18].
4
For example, a small flaw in the formalization of the protocol in [13] has recently been pointed out by Pfister 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 finite-dimensional Hilbert spaces are denoted by capital
letters. The dimension of the system A is denoted by |A|. A joint quantum system AB is defined 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-definite 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 defined as
kρ σk
tr
:= sup
P
tr
P (ρ σ)
, (1)
where P ranges over projectors, i.e. positive semi-definite 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-definite 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:
Definition 1 (Purified distance). For ρ
A
, σ
A
S
(A), we define the generalized fidelity,
F (ρ
A
, σ
A
) :=
tr
n
q
ρ
A
σ
A
ρ
A
o
+
p
1 tr{ρ
A
}
p
1 tr{σ
A
}
2
, (2)
and the purified distance, P (ρ
A
, σ
A
) :=
p
1 F (ρ
A
, σ
A
).
The purified distance is a metric on sub-normalized states and satisfies [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 purified 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 finite-dimensional quantum systems, called registers, with a fixed 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 defined 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 define 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 defined 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: first in the
error correction step to ensure the correctness of the protocol (Theorem 2), and then in the privacy amplification
procedure to guarantee the secrecy of the final key.
Definition 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 suffices 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, defined 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 infinite repetitions
of an information processing task, it is insufficient to describe finite size effects. On the other hand, smooth min-
and max-entropy allow us to capture such finite size effects 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 first proposed by Renner [10] and König et al. [28]. The conditional min-entropy captures how difficult
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 define
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 defined 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:
Definition 3 (Min-entropy). For any bipartite sub-normalized state ρ
AB
S
(AB), we define
H
min
(A|B)
ρ
:= sup
λ R : σ
B
S(B) such that ρ
AB
2
λ
id
A
σ
B
,
. (13)
Showing equivalence between this definition and the special case of cq states in (12) involves semidefinite-
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:
Definition 4 (Max-entropy). For any bipartite sub-normalized state ρ
AB
S
(AB), we define
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
throughout this article log denotes the binary logarithm.
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 purified distance introduced in the previous section.
Definition 5 (Smooth Entropies). For ρ
AB
S
(AB) and ε
h
0,
p
tr(ρ
AB
)
, we define
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 definitions we can replace the supremum and infimum 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 defined 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 first 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 specific 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 effectively represented on a finite-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 verification 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 amplification scheme: pa = {`, H
pa
}
` Length (in bits) of the final key
H
pa
Universal
2
family of hash functions used in the privacy amplification 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 final 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 amplification 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 flags, 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 final 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 efficiency). A simple fix is then to flip a coin
and use the resulting bit as the measurement output. Unfortunately, this solution artificially 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 affect 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 effects 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 sufficiently
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 define
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 amplification, 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 define 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 flag 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 differs from T , he sets the flag F
ec
=
and they abort the protocol. Otherwise he sets F
ec
= X and they proceed.
Privacy Amplification: 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 flags 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 fix 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 verification 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 amplification 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 final key, is fixed. It is in principle possible to design adaptive protocols
where the final key length is chosen after parameter estimation, but this is beyond the scope of this work.
This allows us to define a family of protocols qkd_eb
m,pe,ec,pa
in Table 2. Note that any such protocol is
simply a completely positive trace-preserving map that maps bipartite quantum states shared between Alice
and Bob onto probability distributions of the classical outputs, and we will define their exact operation in
Section 3.3.
3.3 Exact mathematical model of the protocol
Here we describe in detail the mathematical model underlying the protocol in Table 2. It is worth emphasizing
that the eavesdropper does not appear anywhere in this description, but will of course be required when assessing
the security of the protocol as discussed in Section 4.
10
For example, synd could be a linear code described by an r × n parity check matrix H such that synd(x) = Hx. Moreover,
corr can be any decoder, for example the (optimal) maximum likelihood decoder, but also a more practical suboptimal iterative
decoder.
Accepted in Quantum 2017-06-08, click title to verify 10
Input: Alice and Bob are given a state ρ
AB
, where A = A
[m]
= A
1
A
2
. . . A
m
consists of m quantum systems
of arbitrary, finite dimension, B = B
[m]
= B
1
B
2
. . . B
m
consists of m quantum systems of arbitrary, finite
dimension. Note that apart from the above structure, the state ρ
AB
is fully general. The situation is depicted
in Figure 1.
Alice public domain Bob
A B
Figure 1: State of the classical and quantum systems at the beginning of the protocol. The initial state is denoted ρ
AB
.
Randomization: We model the randomization by random seeds (uniform random variables), shared between
Alice and Bob over the public authenticated channel. These random seeds are represented by a quantum state
ρ
S
which is assumed to be maximally mixed and independent of ρ
AB
. The situation after randomization is
depicted in Figure 2. Let us now detail the content of the system S.
The first random variable is a random basis choice for each quantum system. This is modeled as a register
S
Φ
in the state
ρ
S
Φ =
X
φ∈{0,1}
m
1
2
m
|φihφ|
S
Φ
, (22)
where {|φi}
φ∈{0,1}
m
is an orthonormal basis of the space S
Φ
and φ = φ
[m]
= (φ
1
, φ
2
, . . . , φ
m
) with φ
i
{0, 1}.
The total state at the beginning of the protocol is thus of the form ρ
AB
ρ
S
Φ .
The seed for the choice of the random subset is denoted S
Π
and is initially in the state
ρ
S
Π =
X
πΠ
m,k
1
m
k
|πihπ|
S
Π
, (23)
where {|πi}
πΠ
m,k
is an orthonormal basis of the space S
Π
. For any π Π
m,k
, we denote its k elements by π
i
,
for i [k] and we denote by ¯π [m] the complement of π.
At this point we reorder the measurement settings in S
Φ
into two parts: the settings to be used for measuring
quantum systems in π will be stored in a register S
Ξ
and the settings to be used for measuring the remaining
n quantum systems in ¯π will be stored in a register S
Θ
. Formally, we consider the function
ro : {0, 1}
m
× Π
m,k
{0, 1}
k
× {0, 1}
n
, (φ, π) 7→ (φ
π
, φ
¯π
) . (24)
Since S
Φ
is uniformly random, the resulting state after applying this function and discarding S
Φ
is of the form
ρ
S
Π
S
Ξ
S
Θ = tr
S
Φ
E
ro
(ρ
S
Φ ρ
S
Π )
= ρ
S
Π ρ
S
Ξ ρ
S
Θ , (25)
where the registers containing S
Ξ
and S
Θ
are again uniformly random:
ρ
S
Ξ =
X
ξ∈{0,1}
k
1
2
k
|ξihξ|
S
Ξ
and ρ
S
Θ =
X
θ∈{0,1}
n
1
2
n
|θihθ|
S
Θ
(26)
for ξ = ξ
[k]
= (ξ
1
, ξ
2
, . . . , ξ
k
) and θ = θ
[n]
= (θ
1
, θ
2
, . . . , θ
n
) with ξ
i
, θ
i
{0, 1}.
The choice of the hash function in the family H
ec
= {h
ec
: {0, 1}
n
{0, 1}
t
} and the choice of hash function
in the family H
pa
= {h
pa
: {0, 1}
n
{0, 1}
t
} are modeled via random seeds
ρ
S
H
ec
=
X
h∈H
ec
1
|H
ec
|
|hihh|
S
H
ec
and ρ
S
H
pa
=
X
h∈H
pa
1
|H
pa
|
|hihh|
S
H
pa
. (27)
Measurement: We split the measurement process into two parts, measuring the systems in the set π and ¯π
separately. While this distinction is not relevant for the practical implementation of the protocol, the notation
introduced here will be important for the security analysis later. The first measurement concerns the registers
in π, which are used for parameter estimation. For any subset π Π
m,k
, we define a completely positive
Accepted in Quantum 2017-06-08, click title to verify 11
Alice public domain Bob
A
S
B
S
-
6
S
Figure 2: State of the classical and quantum systems after randomization. The state of the total system is ρ
AB
ρ
S
, where
ρ
S
= ρ
S
Φ
ρ
S
Π
ρ
S
H
ec
ρ
S
H
pa
.
trace-preserving map M
π
AV |S
Ξ
: A
π
S
Ξ
V A
π
S
Ξ
where V = V
[k]
= V
1
V
2
. . . V
k
models k binary classical
registers storing the measurement outcomes. The map is given by
M
π
AV |S
Ξ
(·) =
X
ξ∈{0,1}
k
X
v∈{0,1}
k
|vi
V
M
ξ,v
A
π
|ξihξ|
S
Ξ
·
M
ξ,v
A
π
|ξihξ|
S
Ξ
hv|
V
, (28)
where M
ξ,v
A
π
:=
N
i[k]
M
ξ
i
,v
i
A
π
i
. This map measures the k subsystems determined by π using the (random)
measurement settings stored in the register S
Ξ
. The results are stored in the classical register V , and the
post-measurement state remains in the systems A
π
.
Similarly, we define M
π
BW |S
Ξ
: B
π
S
Ξ
W B
π
S
Ξ
as
M
π
BW |S
Ξ
(·) =
X
ξ∈{0,1}
k
X
w∈{0,1}
k
|wi
W
M
ξ,w
B
π
|ξihξ|
S
Ξ
·
M
ξ,w
B
π
|ξihξ|
S
Ξ
hw|
W
, (29)
where M
ξ,w
B
π
:=
N
i[k]
M
ξ
i
,w
i
B
π
i
. The two maps M
π
AV |S
Ξ
and M
π
BW |S
Ξ
commute since they act on different
systems and we write their concatenation as M
π
AV |S
Ξ
M
π
BW |S
Ξ
= M
π
BW |S
Ξ
M
π
AV |S
Ξ
.
So far we have considered π to be fixed. The full measurement for parameter estimation instead consults
the register S
Π
and is modeled as a map M
ABV W |S
Π
S
Ξ : ABS
Π
S
Ξ
ABV W S
Π
S
Ξ
given by
M
ABV W |S
Π
S
Ξ (·) =
X
πΠ
m,k
M
π
AV |S
Ξ
M
π
BW |S
Ξ
|πihπ|
S
Π
· |πihπ|
S
Π
. (30)
The state of the total system after the measurement required for parameter estimation is thus given by
τ
ABV W S
Π
S
Ξ
S
Θ = M
ABV W |S
Π
S
Ξ (ρ
ABS
Π
S
Ξ
S
Θ ) (31)
=
X
πΠ
m,k
X
ξ∈{0,1}
k
X
v,w∈{0,1}
k
1
2
k
m
k
|π, ξihπ, ξ|
S
Π
S
Ξ
ρ
S
Θ
. . . |v, wihv, w|
V W
M
ξ,v
A
π
M
ξ,w
B
π
ρ
AB
M
ξ,v
A
π
M
ξ,w
B
π
. (32)
The second measurement concerns the quantum systems used for extracting the secret key. The correspond-
ing measurement maps are defined analogously to the measurements maps above, but now act on the systems
determined by ¯π, the complement of π in [m]. We define
M
AX|S
Π
S
Θ (·) =
X
πΠ
m,k
X
θ,x∈{0,1}
n
|xi
X
M
θ,x
A
¯π
|π, θihπ, θ|
S
Π
S
Θ
·
M
θ,x
A
¯π
|π, θihπ, θ|
S
Π
S
Θ
hx|
X
, (33)
M
BY |S
Π
S
Θ (·) =
X
πΠ
m,k
X
θ,y∈{0,1}
n
|yi
Y
M
θ,y
B
¯π
|π, θihπ, θ|
S
Π
S
Θ
·
M
θ,y
B
¯π
|π, θihπ, θ|
S
Π
S
Θ
hy|
Y
(34)
as well as M
ABXY |S
Π
S
Θ = M
AX|S
Π
S
Θ M
BY |S
Π
S
Θ . It is evident that all measurements M defined so
far mutually commute because they act either on classical registers or on distinct quantum registers. Finally,
we define the total measurement map as M
ABV W XY |S
Π
S
Ξ
S
Θ := M
ABV W |S
Π
S
Ξ M
ABXY |S
Π
S
Θ .
Of particular interest is the state of the system after measurement and after we discard the quantum systems.
Accepted in Quantum 2017-06-08, click title to verify 12
Alice public domain Bob
S
A
-
V X
S
B
-
W Y
MM
S
Figure 3: State of the classical and quantum systems during and after measurement. The measurement can be summarized
as a CPTP map ρ
AB
ρ
S
Φ
ρ
S
Π
7→ σ
V W XY ABS
Φ
S
Π
.
Alice public domain Bob
X S
V
Y W
S
V
F
pe
--
6
S C
V
avg
Figure 4: State of the classical and quantum systems during and after parameter estimation. Parameter estimation is summa-
rized as a CPTP map σ
V W
7→ σ
C
V
F
pe
.
This is given by a classical state σ
V W XY S
Π
S
Ξ
S
Θ . This state is of the form
σ
V W XY S
Π
S
Ξ
S
Θ (35)
= tr
AB
M
ABV W XY |S
Π
S
Ξ
S
Θ (ρ
ABS
Π
S
Ξ
S
Θ )
(36)
= tr
AB
M
ABXY |S
Π
S
Θ (τ
ABV W S
Π
S
Ξ
S
Θ )
(37)
=
X
πΠ
m,k
X
ξ∈{0,1}
k
θ∈{0,1}
n
X
v,w∈{0,1}
k
x,y∈{0,1}
n
1
2
m
m
k
|π, ξ, θihπ, ξ, θ|
S
Π
S
Ξ
S
Θ
|v, w, x, yihv, w, x, y|
V W XY
. . . tr
AB
n
f
M
ξ,v
A
π
f
M
θ,x
A
¯π
f
M
ξ,w
B
π
f
M
θ,y
B
¯π
ρ
AB
o
, (38)
where we write
f
M
ξ,v
A
π
=
M
ξ,v
A
π
M
ξ,v
A
π
and analogously introduce
f
M
θ,x
A
¯π
,
f
M
ξ,w
B
π
and
f
M
θ,y
B
¯π
.
The situation after the complete measurement is depicted in Figure 3.
Parameter estimation: We model parameter estimation by a test function acting on the registers V and W
and creating a binary flag F
pe
as follows:
test : {0, 1}
k
× {0, 1}
k
{, X}, pe(v, w) =
(
if
P
i[k]
1{v
i
6= w
i
} kδ,
X otherwise.
(39)
This test can be applied to the states τ
ABV W S
Π
S
Ξ
S
Θ or σ
V W XY S
Π
S
Ξ
S
Θ defined previously. This requires
Alice to communicate V to Bob on the authenticated classical channel in order to evaluate the value of pe(v, w)
and the transcript of this communication is stored in the variable C
V
= V .
We are specifically interested in the state τ
ABV W S
Π
S
Ξ
S
Θ
F
pe = E
pe
τ
ABV W S
Π
S
Ξ
S
Θ
and the corresponding
state conditioned on the outcome F
pe
= X, given by
τ
ABV W S
Π
S
Ξ
S
Θ
|F
pe
=X
=
1
Pr[F
pe
= X]
τ
X
πΠ
m,k
X
ξ∈{0,1}
k
X
v,w∈{0,1}
k
P
k
i=1
1{v
i
6=w
i
}<kδ
1
2
k
m
k
|π, ξihπ, ξ|
S
Π
S
Ξ
. . . ρ
S
Θ |v, wihv, w|
V W
M
ξ,v
A
π
M
ξ,w
B
π
ρ
AB
M
ξ,v
A
π
M
ξ,w
B
π
. (40)
We will see that this state is crucial for the security analysis in the next section. Finally, we note that
M
ABXY |S
Π
S
Θ and E
pe
commute, and thus in particular we find that
tr
AB
M
ABXY |S
Π
S
Θ (τ
ABV W S
Π
S
Ξ
S
Θ
|F
pe
=X
)
= σ
V W XY S
Π
S
Ξ
S
Θ
|F
pe
=X
, where (41)
σ
V W XY S
Π
S
Ξ
S
Θ
F
pe = E
pe
(σ
V W XY S
Π
S
Ξ
S
Θ ) . (42)
We then relabel V to C
V
and keep it around as part of the transcript, while we discard W after performing
parameter estimation. The situation after parameter estimation is depicted in Figure 4.
Accepted in Quantum 2017-06-08, click title to verify 13
Error correction: The error correction part of the protocol is split into two parts. The first part consists of
the actual error correction procedure, determined by two functions synd and corr that are executed by Alice
and Bob, respectively. We do not assume anything about these functions, but rather check their success in the
second part by evaluating hash functions.
First Alice computes a syndrome Z = synd(X) and sends it to Bob over the public channel. Bob then
computes an estimate
ˆ
X = corr(Y, Z), discarding Y in the process.
Alice and Bob then need to check that the decoding procedure succeeded with high probability by comparing
hashes of their respective strings X and
ˆ
X and abort the protocol if they differ. Alice computes a hash of size
t (in bits) of X and sends it to Bob, who computes the corresponding hash for
ˆ
X. This test is summarized as
a classical map ec acting on registers X,
ˆ
X and S
H
ec
creating a transcript of the hash value C
T
and a binary
flag F
ec
as follows:
ec : {0, 1}
n
× {0, 1}
n
× H
ec
{0, 1}
t
× {, X}, (x, ˆx) 7→
(
(h
ec
(x), ) if h
ec
(x) 6= h
ec
(ˆx),
(h
ec
(x), X) otherwise.
(43)
These classical functions are modeled using CPTP maps E
synd
, E
corr
and E
ec
, respectively. Applying them
to the state σ
XY C
V
S
Π
S
Ξ
S
Θ
F
pe yields
σ
X
ˆ
XC
V
C
Z
C
T
S
Π
S
Ξ
S
Θ
S
H
ec
F
pe
F
ec
= tr
Y
n
E
ec
E
corr
E
synd
(σ
XY C
V
S
Π
S
Ξ
S
Θ
F
pe ρ
S
H
ec
)
o
, (44)
where the transcript register C
Z
contains the value of the syndrome and C
T
the output of Alice’s hash. This
process is depicted in Figure 5.
Alice public domain Bob
X Z
-
synd
S T
-
hash
Y
Z
-
ˆ
X
corr
T
S
ˆ
T
F
ec
F
pe
?
hash
-
6
S C
V
C
Z
-
?
C
T
Figure 5: State of the classical and quantum systems during and after error correction. Error correction is summarized as a
CPTP map σ
XY
ρ
S
H
ec
7→ σ
X
ˆ
XC
Z
F
ec
.
Privacy amplification: Alice and Bob use the seed H
pa
to choose a hash function, which they then both
apply on their raw key to compute K
A
= H
pa
(X) and K
B
= H
pa
(
ˆ
X), their respective keys. Formally, the
privacy amplification map is defined as:
pa : {0, 1}
n
× {0, 1}
n
× H
pa
{0, 1}
`
× {0, 1}
`
, (x, ˆx, h
pa
) 7→ (h
pa
(x), h
pa
(ˆx)). (45)
Denoting by K
A
and K
B
the respective key spaces of Alice and Bob, the final quantum state is
ω
K
A
K
B
CSF
= tr
X
ˆ
X
E
pa
(σ
X
ˆ
XCSF
ρ
S
H
pa
)
. (46)
Finally, Bob reveals the status of his flag registers. This final step is depicted in Figure 6.
4 Security of the generated key
For a detailed discussion of the security of quantum key distribution, we refer the reader to Portmann and
Renner [32]. For our purposes here (consistent with [10] and [32]), we say that our protocol is -secure if it
is -close to an ideal protocol in terms of the diamond distance. Note in particular that an ideal protocol
is allowed to abort, but it will always output a uniformly random shared key in case it does not. Table 3
gives such an ideal protocol, denoted qkd_ideal
m,pe,ec,pa
designed in such a way that it is close to the original
qkd_eb
m,pe,ec,pa
protocol.
Accepted in Quantum 2017-06-08, click title to verify 14
Alice public domain Bob
S
X
-
K
A
S
ˆ
X
-
K
B
F
6
hashhash
S C F
Figure 6: State of the classical and quantum systems during and after privacy amplification. Privacy amplification is a CPTP
map σ
X
ˆ
X
ρ
S
H
pa
7→ ω
K
A
K
B
. The complete final state is denoted by ω
K
A
K
B
SCF
.
(K
A
, K
B
, S, C, F ) = qkd_ideal
m,pe,ec,pa
ρ
AB
:
Run protocol: Set (K
A
, K
B
, S, C, F ) = qkd_eb
m,pe,ec,pa
(ρ
AB
).
Output: If F
pe
= F
ec
= X, then replace K
A
and K
B
by an independent and uniformly distributed random
string K of length `, i.e. set K
A
= K
B
= K.
Table 3: An ideal QKD protocol that is close to qkd_eb
m,pe,ec,pa
.
In order to show that the protocol is secure, it thus suffices to show that
m,pe,ec,pa
:=
qkd_eb
m,pe,ec,pa
qkd_ideal
m,pe,ec,pa
(47)
= sup
ρ
ABE
∈S(ABE)
qkd_eb
m,pe,ec,pa
(ρ
ABE
) qkd_ideal
m,pe,ec,pa
(ρ
ABE
)
tr
(48)
is very small for certain choices of parameters k, n, δ, ec and pa. In the latter expression ρ
ABE
is an arbitrary
extension of ρ
AB
to an auxiliary system E. Without loss of generality we may take |E| = |A||B|, which is
sufficient to achieve the supremum. Physically the system E is held by a potential adversary, the eavesdropper.
In particular, this assures that E can be assumed finite-dimensional. Hence, we need to show that the trace
distance between the protocols’ outputs is small for all possible input states ρ
ABE
.
Let us now fix ρ
ABE
for the moment. The trace distance in (48) can be simplified by noting that the output
of qkd_ideal equals the output of qkd_eb if the protocol aborts. We find
qkd_eb
m,pe,ec,pa
(ρ
ABE
) qkd_ideal
m,pe,ec,pa
(ρ
ABE
)
tr
= Pr
F = (X, X)
ω
·
ω
K
A
K
B
SCE|F = (X,X)
χ
K
A
K
B
ω
SCE|F = (X,X)
tr
(49)
=
ω
K
A
K
B
SCF EF = (X,X)
χ
K
A
K
B
ω
SCF EF = (X,X)
tr
(50)
where we use ω
K
A
K
B
SCF E
= qkd_eb
k,n,δ,ec,pa
(ρ
ABE
) and define a perfect key χ
K
A
K
B
as follows:
χ
K
A
K
B
:=
1
2
`
X
k∈{0,1}
`
|kihk|
K
A
|kihk|
K
B
. (51)
Recall that ω in (50) corresponds to a subnormalized state with trace equal to Pr[F = (X, X)]
ω
.
Our goal in the following is to bound (50) or (49) uniformly in ρ
ABE
, which implies an upper bound on (48)
as well. In order to do this we will employ the following lemma which allows us to split the norm into two terms
corresponding to correctness and secrecy. This has been shown, e.g., in [32, Theorem 4.1], but we provide a
proof here for completeness.
Lemma 1. Let ε
ec
, ε
pa
[0, 1) be two constants. If, for every state ρ
ABE
S(ABE) and ω
K
A
K
B
SCF E
=
qkd_eb
m,pe,ec,pa
(ρ
ABE
), we have
Pr[K
A
6= K
B
F
pe
= F
ec
= X]
ω
ε
ec
and (52)
ω
K
A
SCF EF = (X,X)
χ
K
A
ω
SCF EF = (X,X)
tr
ε
pa
. (53)
Then,
m,pe,ec,pa
ε
ec
+ ε
pa
.
Proof. Let us introduce an auxiliary state η
K
A
K
B
SCF E
that is equal to ω
K
A
K
B
SCF E
except that we set K
B
=
K
A
. Then, applying the triangle inequality to the trace distance in (49) and simplifying the resulting terms,
Accepted in Quantum 2017-06-08, click title to verify 15
we find
ω
K
A
K
B
SCE|F = (X,X)
χ
K
A
K
B
ω
SCE|F = (X,X)
tr
ω
K
A
K
B
SCE|F = (X,X)
η
K
A
K
B
SCE|F = (X,X)
tr
+
η
K
A
K
B
SCE|F = (X,X)
χ
K
A
K
B
ω
SCE|F = (X,X)
tr
(54)
= Pr
K
A
6= K
B
|F = (X, X)
ω
+
η
K
A
SCE|F = (X,X)
χ
K
A
ω
SCE|F = (X,X)
tr
. (55)
Multiplying this with Pr[F = (X, X)]
ω
as in (49) yields the desired implication.
The first condition of the above Lemma 1 ensures that the protocol is ε
ec
-correct, and the second condition
ensures that the protocol ε
pa
-secret. If both are satisfied, we say that the protocol is (ε
ec
+ ε
pa
)-secure. In the
security proof we can thus verify the two conditions separately.
5 Results and discussion
We will show the following theorems, which essentially give bounds on the security parameters in terms of the
protocol parameters. The first theorem establishes correctness of the protocol. Correctness of the protocol is
ensured in the error correction step using hash functions, and consequently correctness can be bounded in term
of the length t of the hash that is used. The proof is given in Section 6.1.
Theorem 2. Consider the protocol qkd_eb
m,pe,ec,pa
in Section 3 with ec = {t, . . .}. Then for every state
ρ
AB
S(AB) and ω
K
A
K
B
SCF
= qkd_eb
m,pe,ec,pa
(ρ
AB
) we have
Pr[K
A
6= K
B
F = (X, X)]
ω
ε
ec
:= 2
t
. (56)
The second theorem asserts secrecy. Secrecy is ensured by a combination of the parameter estimation
and privacy amplification steps of the protocol, which both introduce an error. There is a tradeoff between
these two errors, parametrized by a scalar ν, which ought to be optimized numerically. The proof is given in
Sections 6.26.4.
Theorem 3. Consider the protocol qkd_eb
m,pe,ec,pa
in Section 3 with pe = {k, δ}, ec = {t, r, . . .} and pa =
{`, . . .}. Then, for every state ρ
ABE
and ω
K
A
K
B
SCF E
= qkd_eb
m,pe,ec,pa
(ρ
ABE
), we have
ω
K
A
SCF EF = (X,X)
χ
K
A
ω
SCF EF = (X,X)
tr
inf
ν(0,
1
2
δ)
ε
pe
(ν) + ε
pa
(ν) , (57)
where the error functions are given as
ε
pa
(ν) :=
1
2
q
2
(mk)
log
1
¯c
h(δ+ν)
+r+t+`
and ε
pe
(ν) := 2 e
(mk)k
2
ν
2
m(k+1)
(58)
and h(x) := x log x (1 x) log(1 x) denotes the binary entropy.
Combining Theorems 2 and 3 we see that total error is thus composed of three components, ε
pe
, ε
ec
, and ε
pa
.
Let us take a close look at these errors for the case of large m. First, we note that ε
ec
vanishes asymptotically
when we choose t = log(m), or any other slowly growing function of m. To make sure that ε
pe
vanishes we
choose k =
m and ν = log(m)
1
, for example. For a robust operation at noise level δ it is necessary (and in
theory sufficient) that the error correction leakage satisfies r (mk)h(δ). Since h(δ + ν) h(δ) by continuity,
we find that ε
pa
vanishes as long as
(m k)
log
1
¯c
2h(δ)
` log(m) (59)
is positive and grows in m. Since k and log m become negligible compared to m as m gets large, our protocol
thus achieves the asymptotically optimal rate by Devetak and Winter [36], with `/m = log
1
¯c
2h(δ).
6 Security proof
The purpose of this section is to prove Theorems 2 and 3.
Accepted in Quantum 2017-06-08, click title to verify 16
10
3
10
4
10
5
10
6
10
7
10
8
m
0.0
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
`/m
=0.01
=0.025
=0.05
=0.075
Figure 7: This plot shows the maximal secret key rate `/m as a function of m for different error thresholds δ
{0.01, 0.025, 0.05, 0.075}, optimized over all protocols. The protocols are required to be ε-secure with ε = 10
10
and
the device parameter is assumed to be ¯c = 0.5. The error correction leakage is approximated to be r = 1.1(m k)h(δ), see
for instance [37]. (A more detailed approximation that includes finite-size effects was recently given in [38].) All remaining
parameters, i.e. ν, k and t, are optimized numerically to maximize ` (code available online). The dotted horizontal lines show
the corresponding asymptotic limit of the key rate for each value of δ, given as 1 2h(δ). The markers indicate the points at
which the key rate matches 50% of the asymptotic limit.
6.1 Error correction: Proof of Theorem 2
We wish to upper bound the probability of the protocol not aborting and outputting distinct final keys for Alice
and Bob.
Proof of Theorem 2. We consider the following chain of inequalities:
Pr[K
A
6= K
B
F
pe
= F
ec
= X]
ω
Pr[K
A
6= K
B
F
ec
= X]
ω
(60)
= Pr[H
pa
(X) 6= H
pa
(X
0
) H
ec
(X) = H
ec
(X
0
)]
ω
(61)
Pr[X 6= X
0
H
ec
(X) = H
ec
(X
0
)]
σ
(62)
= Pr[X 6= X
0
]
σ
Pr[H
ec
(X) = H
ec
(X
0
) | X 6= X
0
]
σ
(63)
Pr[H
ec
(X) = H
ec
(X
0
) | X 6= X
0
]
σ
(64)
|H
ec
|
1
= 2
t
. (65)
The first inequality follows since we ignore the status of the flag F
pe
. The second inequality is a consequence
of the fact X = X
0
implies H
pa
(X) = H
pa
(X
0
). The third inequality follows since Pr[X 6= X
0
]
σ
1 and the
last one by definition of universal
2
hashing.
6.2 Measurements: Uncertainty tradeoff between smooth min- and max-entropy
The crucial bound on the smooth entropy of Alice’s measurement outcomes follows by the entropic uncertainty
relation, suitably applied. We state the uncertainty relation in a natural form [39, Corollary 7.4].
Proposition 4. Let τ
AP RS
S
(AP RS) be an arbitrary sub-normalized state with P a classical register, and
set t := tr{τ
AP RS
}. Furthermore, let ε [0,
t) and let q be a bijective function on P that is a symmetry of
Accepted in Quantum 2017-06-08, click title to verify 17
τ
ABCP
in the sense that τ
ARS,P =p
= τ
ARS,P =q(p)
for all p P . Then, we have
H
ε
min
(X|P R)
σ
+ H
ε
max
(X|P S)
σ
log
1
c
q
, where (66)
where c
q
= max
pP
max
x,zX
F
q(p),x
A
F
p,z
A
2
. Here, σ
XP RS
= M
AX|P
(τ
AP RS
) for the map
M
AX|P
·
= tr
A
X
pP
X
xX
|xi
X
|pihp|
P
F
p,x
A
·
|pihp|
P
F
p,x
A
hx|
X
!
. (67)
and any set (indexed by p P ) of generalized measurements {F
p,x
A
}
xX
.
A variant of this uncertainty relation was first shown in [39], based on the techniques introduced in [21]. We
provide a full proof of the uncertainty relation in Appendix A for completeness. In the following corollary we
apply it to the situation at hand during our protocol.
Corollary 5. Consider the protocol qkd_eb
m,pe,ec,pa
in Section 3 with pe = {k, . . .} applied to a state ρ
ABE
S(ABE) and the state σ
XY V W S
Π
S
Ξ
S
Θ
F
pe
E
as in (42) that results after measurement and parameter estimation.
Define ¯c as in (21). Then, for ε
0,
p
Pr[F
pe
= X]
σ
, we have
H
ε
min
(X F
pe
= X|V W S
Π
S
Ξ
S
Θ
E)
σ
+ H
ε
max
(X F
pe
= X|Y )
σ
(m k) log
1
¯c
. (68)
Proof. Consider the state τ
ABV W S
Π
S
Ξ
S
Θ
F
pe
EF
pe
=X
defined in (40) and note that it is of the form
τ
ABV W S
Π
S
Ξ
S
Θ
F
pe
EF
pe
=X
= τ
ABV W S
Π
S
Ξ
F
pe
EF
pe
=X
ρ
S
Θ . (69)
This is the state of the system after parameter estimation and after measuring V and W , but with the mea-
surement of X and Y (in the basis determined by S
Θ
) delayed. In particular we have used the fact that the
register S
Θ
has not yet been touched in the protocol, and is thus independent and uniform and independent
even after we consider the event F
pe
= X.
Let us now apply Proposition 4 to this state. For this purpose we equate P = S
Π
S
Ξ
S
Θ
, R = V W E, and
S = B. The symmetry is determined by the map q : θ 7→
¯
θ with
¯
θ
i
= 1 θ
i
, which only acts on S
Θ
and since
this system is uniform and in product with the rest of the state trivially satisfies the symmetry condition of the
theorem. The measurement map is then simply M
AX|S
Π
S
Θ and we can calculate
c
q
= max
πΠ
m,k
max
θ,x,z∈{0,1}
n
M
¯
θ,x
A
¯π
M
θ,z
A
¯π
2
= max
πΠ
m,k
Y
i¯π
c
i
!
= ¯c
n
. (70)
Proposition 4 applied to our setup thus yields
H
ε
min
(X F
pe
= X|V W ES
Π
S
Ξ
S
Θ
)
σ
+ H
ε
max
(X F
pe
= X|BS
Π
S
Ξ
S
Θ
)
τ
n log
1
¯c
. (71)
Finally, the statement of the Proposition follows by applying the measurement map M
BY |S
Π
S
Θ (and discarding
the seed registers) and noting that H
ε
max
(X F
pe
= X|BS
Π
S
Ξ
S
Θ
)
τ
H
ε
max
(X F
pe
= X|Y )
σ
by the data-
processing inequality.
6.3 Parameter estimation: Statistical bounds on smooth max-entropy
This section covers the necessary statistical analysis. This is essentially a variation of the analysis in [13], but
requires a new tool, Lemma 7, presented in Section 2.2, as we are finding it clearer to do the analysis with
sub-normalized states here. We use the following standard tail bound.
Lemma 6. Consider a set of binary random variables Z = (Z
1
, Z
2
, . . . , Z
m
) with Z
i
taking values in {0, 1} and
m = n + k. Let Π Π
m,k
be an independent, uniformly distributed random variable. Then,
Pr
"
X
iΠ
Z
i
kδ
X
i
¯
Π
Z
i
n(δ + ν)
#
e
2ν
2
nk
2
(n+k)(k+1)
. (72)
Remarkably this bound is valid without any assumption on the distribution of Z.
Accepted in Quantum 2017-06-08, click title to verify 18
Proof. Let µ(z) =
1
m
P
i[m]
z
i
. Consider the following sequence of inequalities:
Pr
"
1
k
X
iΠ
Z
i
δ
1
n
X
i /Π
Z
i
δ + ν
#
Pr
"
1
n
X
i
¯
Π
Z
i
1
k
X
iΠ
Z
i
+ ν
#
(73)
=
X
z∈{0,1}
m
Pr[Z = z] Pr
"
1
n
X
i
¯
Π
z
i
1
k
X
iΠ
z
i
+ ν
#
(74)
=
X
z∈{0,1}
m
Pr[Z = z] Pr
"
1
n
X
i
¯
Π
z
i
µ(z) +
kν
m
#
. (75)
Here, the first inequality holds since A = B implies Pr[A] Pr[B] for any events A and B. The first
equality follows from the fact that Π is independent of Z. The last equality follows by substituting
P
iΠ
z
i
=
(z)
P
i
¯
Π
z
i
and rearranging the terms appropriately.
Now note that the random sums S
n
:=
P
i
¯
Π
z
i
can be seen as emanating from randomly sampling with-
out replacement n balls labelled by z
i
{0, 1} from a population z with mean µ(z). Serfling’s bound [40,
Corollary 1.1] then tells us that
Pr
1
n
S
n
µ(z) +
kν
m
e
2n
m
2
1
1f
n
= e
2ν
2
nk
2
(n+k)(k+1)
. (76)
where we substituted f
n
=
n1
m
. It is important to note that this bound is independent of µ(z). Thus,
substituting this back into (75), we conclude the proof.
The following lemma ensures that disregarding an unlikely event will not disturb the state too much in terms
of the purified distance.
Lemma 7. Let ρ
AX
S
(AX) be classical on X and : X {0, 1} an event with Pr[Ω]
ρ
= ε < tr{ρ
AX
}.
Then there exists a sub-normalized state ˜ρ
AX
S
(AX) with Pr[Ω]
˜ρ
= 0 and P (ρ
AX
, ˜ρ
AX
)
ε.
Proof. Set ξ = tr{ρ
AX
}. Let ˜ρ
AX
=
sin
2
(φ)
ξε
ρ
AX∧¬
for some normalization φ [0,
π
2
] to be determined. Then
the generalized fidelity evaluates to
q
F
ρ
AX
, ˜ρ
AX
=
sin(φ)
ξ ε
tr
q
ρ
AX
ρ
AX∧¬
ρ
AX
+ cos(φ)
p
1 ξ (77)
= sin(φ)
p
ξ ε + cos(φ)
p
1 ξ . (78)
This expression is maximized for tan(φ) =
q
ξε
1ξ
and, thus, sin(φ) =
q
ξε
1ε
and cos(φ) =
q
1ξ
1ε
. Substituting
this into (78) yields F (ρ
AX
, ˜ρ
AX
) = 1 ε, concluding the proof.
With this in hand, we wish to bound the smooth max-entropy of the state when passing the parameter
estimation test.
Proposition 8. Consider the protocol qkd_eb
m,pe,ec,pa
in Section 3 with pe = {k, δ} applied to a state ρ
AB
S(AB) and the state σ
XY F
pe
in (42) that results after measurement and parameter estimation. For any ν
(0, 1), we first define
ε(ν) := e
(mk)k
2
ν
2
m(k+1)
. (79)
Then, for any ν (0,
1
2
δ] such that ε(ν)
2
< Pr[F
pe
= X]
σ
, the following holds:
H
ε(ν)
max
(X F
pe
= X|Y )
σ
(m k) h(δ + ν) where h(x) := x log x (1 x) log(1 x) . (80)
Intuitively, this result is a consequence of the fact that when we pass the parameter estimation test, condi-
tioned on any particular value of Y , the support of X is small as the number of errors (positions where x
i
6= y
i
)
is bounded (with high probability).
Accepted in Quantum 2017-06-08, click title to verify 19
Proof. We use the shorthand p = Pr[F
pe
= X]
σ
and n := m k. Define the event event Ω := 1
P
i[n]
1{X
i
6=
Y
i
} n(δ + ν)
. We show that the statement in (80) holds when p > ε
2
. Using Lemma 6, we find
Pr
F
pe
= X
σ
= Pr
X
i[k]
1{V
i
6= W
i
}
X
i[n]
1{X
i
6= Y
i
} n(δ + ν)
σ
ε(ν)
2
. (81)
This gives an upper bound on the probability of the unlikely coincidence where the parameter estimation test
passes with threshold δ but the fraction of errors between X and Y exceeds the threshold δ by a constant amount.
We now want to remove the above unlikely events from our state σ
XY F
pe
F
pe
= X
by means of smoothing.
Lemma 7 allows to do just that, and we introduce the state ˜σ
XY F
pe
that is ε(ν)-close to σ
XY F
pe
F
pe
= X
in
purified distance and satisfies Pr[Ω]
˜σ
= 0. From this we conclude that
H
ε(ν)
max
(X F
pe
= X|Y )
σ
H
max
(X F
pe
= X|Y )
˜σ
= H
max
(X|Y )
˜σ
, (82)
where the last equality is a consequence of the fact that ˜σ is only supported on F
pe
= X.
It remains to show that H
max
(X|Y )
˜σ
nh(δ + ν). Using the expansion of the conditional max-entropy
in [39, Sec. 4.3.2], we find
H
max
(X|Y )
˜σ
= log
X
y∈{0,1}
n
Pr[Y = y]
˜σ
2
H
max
(X|Y =y)
˜σ
!
(83)
max
y∈{0,1}
n
Pr[Y =y]
˜σ
>0
H
max
(X|Y = y)
˜σ
(84)
max
y∈{0,1}
n
Pr[Y =y]
˜σ
>0
log
n
x {0, 1}
n
: Pr[X = x|Y = y]
˜σ
> 0
o
(85)
= max
y∈{0,1}
n
log
n
x {0, 1}
n
: Pr[X = x Y = y]
˜σ
> 0
o
. (86)
In the ultimate inequality we used that the (unconditional) Rényi entropy is upper bounded by the logarithm
of the distribution’s support [27]. Furthermore, since Pr[Ω]
˜σ
= 0, we have
n
x {0, 1}
n
: Pr[X = x Y = y]
˜σ
> 0
o
X
x∈{0,1}
n
1
(
X
i[n]
1{x
i
6= y
i
} < n(δ + ν)
)
(87)
=
X
e∈{0,1}
n
1
n
X
i=1
e
i
< n(δ + ν)
(88)
=
n
X
λ=0
n
λ
1
λ < n(δ + ν)
=
bn(δ+ν)c
X
λ=0
n
λ
. (89)
Here, in order to derive (88) we reparameterize e
i
= x
i
xor y
i
, indicating if there is an error at the i-th position.
Finally, in (89) we substitute λ =
P
n
i=1
e
i
, the total number of errors. The inequality
P
bn(δ+ν)c
λ=0
n
λ
2
nh(δ+ν)
for δ + ν 1/2 (see, e.g., [41, Sec. 1.4]) then concludes the proof.
6.4 Privacy amplification: Proof of Theorem 3
The last main ingredient of our proof is a so-called Leftover Hashing Lemma. It ensures that if the smooth
min-entropy of X given some side information B is large, then we can extract randomness from X that is
independent of B. The Leftover Hashing Lemma is, up to a slight change of the definition of the smooth
min-entropy, due to Renner [10, Corollary 5.6.1]. The proof of this exact statement is provided in Appendix B
for the convenience of the reader.
Proposition 9. Let σ
XD
S
(XD) be classical on X and ε
0,
p
tr(σ
XD
)
. Let H be a universal
2
family of
hash functions from X = {0, 1}
n
to K = {0, 1}
`
. Moreover, let ρ
S
H
=
1
|H|
P
h∈H
|hihh|
S
H
. Then,
kω
KS
H
D
χ
K
ω
S
H
D
k
tr
1
2
2
1
2
(H
ε
min
(X|D)
σ
`)
+ 2ε (90)
where χ
K
=
1
2
`
id
K
is the fully mixed state and ω
KS
H
D
= tr
X
E
f
(σ
XD
ρ
S
H
)
for the function f : (x, h) 7→ h(x)
that acts on the registers X and S
H
.
Accepted in Quantum 2017-06-08, click title to verify 20
The following technical lemma allows us to bound the smooth conditional min-entropy restricted to events
in terms of the unrestricted entropy.
Lemma 10. Let ρ
ABXY
S
(ABXY ) be classical on X and Y and let : X × Y {0, 1} be an event with
Pr[Ω]
ρ
> 0. Then, for ε
0,
p
Pr[Ω]
ρ
, we have
H
ε
min
(AX |BY )
ρ
H
ε
min
(AX|BY )
ρ
and H
ε
min
(AX |B)
ρ
H
ε
min
(AX|B)
ρ
(91)
Proof. Let us start with the first inequality. By definition of the smooth conditional min-entropy there exists a
sub-normalized state ˜ρ
ABXY
S
(ABXY ) and a state σ
BY
S(BY ) such that
˜ρ
ABXY
2
H
ε
min
(AX|BY )
ρ
id
AX
σ
BY
and P (˜ρ
ABXY
, ρ
ABXY
) ε . (92)
Without loss of generality [22, Lemma 6.6] we can assume that ˜ρ
ABXY
is classical on X and Y . As such,
we have ˜ρ
ABXY
˜ρ
ABXY
and P (˜ρ
ABXY
, ρ
ABXY
) P (˜ρ
ABXY
, ρ
ABXY
) ε by the monotonicity of
the purified distance under trace non-increasing maps. The desired inequality then follows by definition of the
smooth min-entropy evaluated for the state with the event .
The second inequality follows similarly. By definition of the smooth conditional min-entropy there exists a
sub-normalized state ˜ρ
ABX
S
(ABX) and a state σ
B
S(B) such that
˜ρ
ABX
2
H
ε
min
(AX|B)
ρ
id
AX
σ
B
and P (˜ρ
ABX
, ρ
ABX
) ε . (93)
As discussed previously, this implies in particular the existence of an extension ˜ρ
ABXY
S
(ABXY ) that
satisfies P (˜ρ
ABXY
, ρ
ABXY
) ε. Without loss of generality we can assume that ˜ρ
ABXY
is classical on X and
Y . (To see this, note that pinching in the computational basis on Y would indeed only decrease the distance
between the ˜ρ
ABXY
and ρ
ABXY
, leaving the latter state invariant.) On the state ˜ρ
ABXY
we can now define
the restriction on the event and find
˜ρ
ABXY
˜ρ
ABXY
= ˜ρ
ABX
= tr
Y
{˜ρ
ABXY
} ˜ρ
ABX
. (94)
Finally, we proceed in the same fashion as for the first inequality to show that P (˜ρ
ABX
, ρ
ABX
) ε and
conclude the proof.
The next proposition builds on Corollary 5 and Proposition 8 and the above Leftover Hashing Lemma to
establish the secrecy of the key.
Proposition 11. Let ρ
ABE
S(ABE). Consider the protocol qkd_eb
m,pe,ec,pa
in Section 3 with pe = {k, δ},
ec = {t, r, . . .} and pa = {`, . . .} and the state ω
K
A
K
B
SCF E
= qkd_eb
m,pe,ec,pa
(ρ
ABE
). Define ε(ν) as in (79).
Then, for any ν (0,
1
2
δ] such that ε(ν)
2
< Pr[F = (X, X)]
σ
, the following holds:
ω
K
A
SCF EF = (X,X)
χ
K
A
ω
SCF EF = (X,X)
tr
1
2
2
1
2
g(ν)
+ 2ε(ν) . (95)
where g(ν) := (m k)
log
1
¯c
h(δ + ν)
r t `.
Note that in the above proposition, in order to ensure that the smooth min-entropy is always well-defined,
we restricted ourselves to the case where the success probabillity exceeds the squared smoothing parameter,
i.e. we required that ε(ν)
2
< Pr[F = (X, X)]. The case where the success probability is small will be handled
separately in Corollary 12 below.
Proof. We use n = m k. Since Pr[F = (XX)]
σ
Pr[F
pe
= X]
σ
the condition of Proposition 8 is satisfied and
we find that H
ε(ν)
max
(X F
pe
= X|Y )
σ
nh(δ + ν) for the state σ
XY V W S
Π
S
Ξ
S
Θ
F
pe
E
as in (42) that results after
measurement and parameter estimation. Combining this with Corollary 5 yields
H
ε(ν)
min
(X F
pe
= X|V W S
Π
S
Ξ
S
Θ
E)
σ
nq , (96)
where we introduced the shorthand q = log
1
¯c
h(δ + ν).
Our goal is to translate this in a condition on the state σ
X
ˆ
XC
V
C
Z
C
T
S
Π
S
Ξ
S
Θ
S
H
ec
F
pe
F
ec
E
as in (44) that
results after error correction. The following chain of inequalities holds:
nq H
ε(ν)
min
(X F
pe
= X|S
Π
S
Ξ
S
Θ
C
V
E)
σ
(97)
H
ε(ν)
min
(X F
pe
= X|S
Π
S
Ξ
S
Θ
C
V
C
Z
E)
σ
+ r (98)
= H
ε(ν)
min
(X F
pe
= X|S
Π
S
Ξ
S
Θ
S
H
ec
C
V
C
Z
E)
σρ
+ r (99)
H
ε(ν)
min
(X F
pe
= X|S
Π
S
Ξ
S
Θ
S
H
ec
C
V
C
Z
C
T
E)
σ
+ r + t (100)
H
ε(ν)
min
X F
pe
= X F
ec
= X
S
Π
S
Ξ
S
Θ
S
H
ec
C
V
C
Z
C
T
E
σ
+ r + t. (101)
Accepted in Quantum 2017-06-08, click title to verify 21
The first inequality follows by relabeling V to C
V
and discarding W, an instance of the data-processing inequal-
ity. The transcript register C
Z
contains the syndrome sent from Alice to Bob and the inequality (98) follows
by the chain rule in (19), and the fact that log |C
Z
| = r. The register S
H
ec
in the state ρ
S
H
ec
is independent
of the other registers. The register C
T
contains the hash of the raw key X of size log |C
T
| = t leading to the
penultimate inequality. In the last step we used Lemma 10.
Summarizing S
0
= (S
Π
, S
Ξ
, S
Θ
, S
H
ec
) as well as C = (C
V
, C
Z
, C
T
), and F = (F
pe
, F
ec
) as usual, we can
thus more compactly write this as
H
ε(ν)
min
(X F = (X, X) |S
0
CE)
σ
nq r t . (102)
Proposition 9 applied with this bound then immediately yields the desired inequality.
The above proposition suffers from the assumption ε(ν)
2
< Pr[F = (X, X)]
ω
. However, the other case
can easily be dealt with. Indeed, the trace distance
ω
K
A
SCF EF = (X,X)
χ
K
A
ω
SCF EF = (X,X)
tr
is upper
bounded by the the trace of both states, i.e. the probability Pr[F = (X, X)]
ω
. The inequalities Pr[F =
(X, X)]
σ
ε(ν)
2
ε(ν) then yield the following corollary, which is equivalent to Theorem 3.
Corollary 12. Consider the setup of Proposition 11. For any ν (0,
1
2
δ] the following holds:
ω
K
A
SCF EF = (X,X)
χ
K
A
ω
SCF EF = (X,X)
tr
1
2
q
2
(mk)
log
1
¯c
h(δ+ν)
+r+t+`
+ 2ε(ν) . (103)
Part II
Prepare-and-measure protocol
N
AB
Quantum channel between Alice and Bob
P
A|RS
Φ
A
Preparation map that returns a state in register A depending on the settings R, S
Φ
A
M Number of states sent by Alice in the prepare-and-measure version
Subset of [M] for which Bob obtains a conclusive measurement result
Σ Subset of m indices where Alice and Bob’s settings agree and Bob obtained a conclusive outcome
ro Reordering map used in the sifting step.
R Register for Alice’s raw key in the prepare-and-measure protocol
U Register for Bob’s measurement results in the prepare-and-measure protocol
S
Φ
A
Seed for the choice of Alice’s measurement bases in the prepare-and-measure protocol
S
Φ
B
Seed for the choice of Bob’s measurement bases in the prepare-and-measure protocol
S Register corresponding to all the seeds that Alice communicates to Bob after state distribution
S = (S
Π
, S
Ξ
, S
Θ
, S
H
pe
, S
H
ec
)
F
si
Flag for the sifting procedure in the prepare-and-measure protocol
F Register corresponding to all the flags, F = (F
si
, F
pe
, F
ec
)
C
, C
Σ
Transcripts of the registers and Σ sent during sifting
C Register containing all the communication transcripts, C = (C
, C
Σ
, C
V
, C
Z
, C
T
)
Table 4: Additional nomenclature and notation used in Part II. See also Table 1
7 Formal description of the prepare-and-measure protocol
Here we discuss a prepare-and-measure (PM) protocol for QKD, denoted qkd_pm
M,m,pe,ec,pa
, which is essen-
tially equivalent to BB84 [1], and prove that its security follows from that of the entanglement-based protocol
considered in Part I, provided that some additional assumptions are made.
Section 7.2 provides the details of the protocol described in Table 5, for the steps where it differs from the
entanglement-based protocol. We describe the additional assumptions on the preparation and measurement
devices in 7.1 and present a mathematical model of the protocol in 7.3.
Accepted in Quantum 2017-06-08, click title to verify 22
7.1 Additional assumptions on preparation and measurement devices
The physical equipment of Alice an Bob is modified compared to that of the entanglement-based protocol
considered in Part I. Indeed, the main point of implementing a prepare-and-measure protocol is that it is no
longer required for Alice and Bob to share an entangled state, a task that remains very challenging if the two
parties are a few tens of kilometers apart, which is typical in realistic scenarios where one wants to distribute
secret keys at the scale of a metropolitan area. In the prepare-and-measure setup Alice and Bob do not start
with an entangled state but instead have access to a quantum channel from Alice to Bob.
The assumption on finite-dimensional quantum systems, sealed laboratories, random seeds and authenticated
communication channel discussed in Section 3.1 still apply. The assumption of sealed laboratories in particular
implies that the quantum channel between Alice and Bob models all quantum communication leaving Alice’s
lab. However, we will replace the assumption of commuting measurements, deterministic detection and the
complementarity of Alice’s measurements.
Alice’s preparation: In every round, indexed by i [M], Alice’s preparation device takes two bits as input:
φ {0, 1} describing a basis choice and x {0, 1} describing the bit value within each basis. It produces
a quantum state ρ
φ,x
A
i
, ideally corresponding to one of the four BB84 states. The commuting measurement
assumption for Alice is replaced with the requirement that these states do not depend on the preparations in
previous or later rounds (which is already ensured by our notation). Our next assumption is that the state ρ
φ,x
A
i
does not leak any information about the basis choice φ, i.e., we require that
X
x∈{0,1}
ρ
0,x
A
i
=
X
x∈{0,1}
ρ
1,x
A
i
. (104)
Moreover, instead of the complementarity assumption on the measurements, we require that the prepared states
are sufficiently complementary. More precisely, let us define
c
0
{ρ
x
}
x
, {σ
y
}
y
:= max
x,y
ρ
x
X
1
σ
y
2
, for states satisfying
X
x
ρ
x
=
X
y
σ
y
:= X . (105)
In case X has not full support we take the generalized inverse (on its support) in the above definition. Our
second assumption on Alice’s preparation is that
c
0
i
:= c
0
ρ
0,x
A
i
x
,
ρ
1,y
A
i
y
¯c
0
(106)
for all i [M] and some constant ¯c
0
< 1. The constant ¯c
0
is closely related to the constant ¯c that described the
complementarity of Alice’s measurement in the entanglement-based protocol, as we will see in Corollary 15.
In an ideal implementation of the BB84 protocol, the states ρ
φ,r
would be single-qubit states given by
ρ
0,0
= |0ih0|, ρ
0,1
= |1ih1|, ρ
1,0
= |+ih+|, ρ
1,1
= |−ih−|. (107)
These states obviously satisfy the assumption in (104) and it is easy to verify that ¯c
0
=
1
2
is a valid bound.
We should note that our first assumption is rather strong and for instance does not allow us to assess the
security of popular implementations of the BB84 protocol relying on a weak-coherent-state encoding. Since
single-photon sources remain expensive and imperfect today, it is indeed tempting to encode each qubit with
two polarization modes and replace single-photons by phase-randomized weak-coherent states
11
. For such an
implementation, the four BB84 states become linearly independent, and Eq. (104) cannot hold. It is well-known
that such implementations are sensitive to “photon-number-splitting” attacks but that solutions exist to restore
their security, for instance with the help of decoy states [42]. While we believe that our framework could
accommodate such modifications (see for instance [43, 44]), we do not address this issue here.
Bob’s measurement: As for the simple protocol of Part I, we require that Bob’s quantum system can be
decomposed as B B
[M]
= B
1
B
2
. . . B
M
. Bob’s measurement device is similar to that of the simple protocol of
Part I, but the measurement operators now need to be specified for indices in [M] and allow for an additional
outcome, ’, corresponding to an inconclusive result. Such an inconclusive result can for instance occur when
no detector clicked (photon loss) or when more than 1 detector clicked (dark counts)
12
.
11
If the single-photon polarization qubit states are given by (107), then the four encoded BB84 states are τ
i,j
=
e
α
2
L
k=0
α
2k
k!
(ρ
i,j
)
k
for i, j {0, 1}, where α > 0 is the amplitude of the coherent states.
12
Indeed, in most experiments, the measurement device is usually implemented with the help of two single-photon detectors, and
a conclusive measurement outcome, 0 or 1, will correspond to which detector clicked while inconclusive outcomes occur if none or
both of the detectors clicked.
Accepted in Quantum 2017-06-08, click title to verify 23
For any i [M], we model Bob’s measurement on subsystem B
i
with setting φ {0, 1} by a ternary
generalized measurement {M
φ,z
B
i
}
z∈{0,1,}
acting on B
i
. The index z ranges over the two conclusive outcomes,
0 and 1, of Bob’s measurement as well as the inconclusive outcomes . We require that
(M
0,
B
i
)
(M
0,
B
i
) = (M
1,
B
i
)
(M
1,
B
i
), (108)
meaning that the element corresponding to an inconclusive result coincides for both measurements. As will be
formalized in Lemma 16, this implies that Bob’s measurement map can be interpreted as a two-step process
first deciding whether the result is conclusive or not, and then, in the former case, proceeding with the ideal
measurement considered in Part I. While this assumption seems quite reasonable for photon detector working
in the few photons regime, it usually fails to apply when avalanche photo diodes are accessed in the linear mode,
and this was precisely the origin of the “blinding attack” of [33].
In any realistic implementation, Alice and Bob would need to be synchronized so that Bob can keep track of
which system he is currently measuring. This is especially relevant in high-loss regimes where Bob’s detectors
would not click most of the time. Such a synchronization procedure can be realized classically, provided that
both players have access to an authenticated channel. For simplicity, we ignore this synchronization issue in
our model.
7.2 Protocol parameters and overview
The protocol qkd_pm
M,m,pe,ec,pa
is parametrized as qkd_eb
m,pe,ec,pa
, but with one extra parameter:
The number of individual states prepared and sent through the quantum channel by Alice, M N. We
require that M m and for optical implementations a typical value for M is
2m
η
where η is the overall
transmittance of the optical channel between Alice and Bob.
7.3 Exact mathematical model of the protocol
Here we describe in detail the mathematical model corresponding to the protocol in Table 5, for the steps where
it differs from the simple protocol of Part I.
Input: The realistic protocol qkd_pm
M,m,pe,ec,pa
we consider is a prepare-and-measure protocol, and the role
of the input is now played by an (arbitrary) quantum channel N
AB
between Alice and Bob. Here A = A
[M]
and B = B
[M]
. This situation is depicted in Figure 8.
As before, we make the assumption that the input and output of the quantum channel are finite-dimensional.
This arguably appears quite restrictive since any complete description of the optical channel would involve
infinite-dimensional Fock spaces, with the idea that each of the M systems prepared by Alice corresponds to
two polarization modes for instance. However, we point out that we do not require any explicit upper bound
on the dimension of the Hilbert spaces occurring in the protocol, and that any physical state necessarily has
a bounded energy, which means that it can be arbitrarily well approximated by a quantum state in a finite-
dimensional Hilbert space of sufficiently large dimension.
Alice public domain Bob
-
N
Figure 8: (Input.) Alice and Bob have access to a quantum channel: N : A B.
Randomization: The random seeds are modeled similarly as for the idealized version of the protocol. Here,
the seed S
Φ
corresponding to identical measurement settings is not provided directly. Instead, Alice and Bob
initially choose independently two strings Φ
A
, Φ
B
{0, 1}
M
, and it will later be the role of the sifting procedure
to produce a set of identical measurement settings Φ. The random choice of the strings Φ
A
, Φ
B
is modeled by
two registers S
Φ
A
, S
Φ
B
in the state
ρ
S
Φ
A
ρ
S
Φ
B
=
1
4
M
X
φ
A
B
∈{0,1}
M
|φ
A
ihφ
A
|
S
Φ
A
|φ
B
ihφ
B
|
S
Φ
B
, (109)
Accepted in Quantum 2017-06-08, click title to verify 24
(K
A
, K
B
, S, C, F ) = qkd_pm
M,m,pe,ec,pa
N
AB
:
Input: Alice and Bob have access to a quantum channel N
AB
: A B where A A
[M]
and B B
[M]
are
comprised of M quantum systems.
Randomization: Alice and Bob respectively choose two random strings Φ
A
, Φ
B
{0, 1}
M
. Alice also chooses
a random string R {0, 1}
M
. These private seeds are denoted S
Φ
A
, S
Φ
B
and R. Finally, similarly as in
the simple protocol, Alice chooses a random subset Π Π
m,k
, and random hash functions H
ec
H
ec
as
well as H
pa
H
pa
. These uniformly random seeds are denoted S = (S
Π
, S
H
ec
, S
H
pa
).
State Preparation: Alice prepares a quantum state ρ
R,Φ
A
A
, encoding the string R in the measurement basis
corresponding to φ
A
.
State Distribution: Alice sends the state ρ
R,Φ
A
A
through the quantum channel N and Bob receives the output
state ρ
R,Φ
A
B
= N(ρ
R,Φ
A
A
). (In practice, Alice would send the systems one by one, and use the quantum
channel M times.)
Measurement: Bob measures the M quantum systems with the setting Φ
B
, and stores his ternary measurement
outcomes in a string U {0, 1, }
M
, where denotes an inconclusive measurement result. He also
computes the set 2
[M]
of indices corresponding to conclusive measurements (In practice, Bob would
start measuring the systems as soon as he receives them.)
Randomness distribution: Bob publicly announces both the value of Φ
B
and . The corresponding tran-
scripts are denoted by C
Φ
B
and C
, respectively. Alice sends the value of the seeds S = (S
Π
, S
H
ec
, S
H
pa
)
to Bob through the authenticated public channel.
Sifting: If it exists, Alice publicly announces a set Σ , with transcript C
Σ
of cardinality m, such that
Φ
A
and Φ
B
coincide on Σ, and sets the flag F
si
= X. Otherwise, she sets F
si
= and they abort. The
respective binary substrings R
0
and U
0
of R and U restricted to Σ become the raw keys. As in the idealized
protocol, they are then reordered and 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 flag 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).
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 differs from T , he sets the flag F
ec
= and they abort the protocol. Otherwise he sets
F
ec
= X and they proceed.
Privacy Amplification: 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
Φ
B
, S
Π
, S
H
ec
, S
H
pa
), the
transcript C = (C
, C
Σ
, C
V
, C
Z
, C
H
) and the flags F = (F
si
, F
pe
, F
ec
). In case of abort, we assume that
all registers are initialized to a predetermined value.
Table 5: Realistic Prepare-and-Measure QKD Protocol qkd_pm
M,m,pe,ec,pa
. The precise mathematical model is described
in Section 7. This protocol differs from the entanglement-based protocol in several points: in particular, the input now
corresponds to the quantum channel N between Alice and Bob.
where {|φ
A
i}, {|φ
B
i} are orthonormal bases of S
Φ
A
and S
Φ
B
, respectively.
Another difference with the simple protocol of Part I is that Alice also has access to a register R that she
will use to choose which state to prepare. This register is modeled similarly as the other seeds as a maximally
mixed state:
ρ
R
=
1
2
M
X
r∈{0,1}
M
|rihr|
R
, (110)
Accepted in Quantum 2017-06-08, click title to verify 25
where {|ri} is an orthonormal basis of R. The other random seeds ρ
S
Π , ρ
S
H
ec
, ρ
S
H
pa
are identical to the idealized
version. This situation is depicted in Figure 9.
Alice public domain Bob
-
N
Φ
A
R S Φ
B
Figure 9: (Randomization.) Alice prepares a public seed S that will later be communicated to Bob through an authenticated
classical channel. Alice and Bob also prepare private seeds: R, Φ
A
for Alice, Φ
B
for Bob.
Note that while in the simple protocol all the seeds are communicated publicly during a step of the protocol,
it is crucially not the case here for the seed R, from which the final key could be immediately inferred. We will
see that it is not necessary to communicate the seed S
Φ
A
to Bob since the sifting procedure is performed by
Alice.
In a practical implementation, the various random seeds, except for S
Φ
B
would be initially prepared by
Alice, and only communicated to Bob when needed (except for R and S
Φ
A
). In particular, one should wait until
the state distribution is over before communicating the value of the chosen subset for parameter estimation or
of the various hash functions.
State preparation: Alice prepares a quantum state on M systems A A
[M]
using the map
P
A|RS
Φ
A
(·) =
X
r,φ∈{0,1}
M
|rihr|
R
|φihφ|
S
Φ
A
·
|rihr|
R
|φihφ|
S
Φ
A
ρ
r,φ
A
(111)
where ρ
r,φ
A
=
N
M
i=1
ρ
r
i
i
A
i
. Applying this map to the seeds in registers R and S
Φ
A
results in the state
ρ
RS
Φ
A
A
=
1
4
M
X
r,φ∈{0,1}
M
|rihr|
R
|φihφ|
S
Φ
A
ρ
r,φ
A
. (112)
This situation is depicted in Figure 10.
Alice public domain Bob
-
N
Φ
A
R
-
P
A
S Φ
B
Figure 10: (State Preparation.) Using her private seeds R and Φ
A
, Alice prepares system A.
State distribution: Alice sends her register A to Bob through the quantum channel N : A B. The state
shared by Alice and Bob is given by:
ρ
RS
Φ
A
B
= N
AB
(ρ
RS
Φ
A
A
) (113)
=
1
4
M
X
r,φ∈{0,1}
M
|rihr|
R
|φihφ|
S
Φ
A
ρ
r,φ
B
, (114)
where we defined ρ
r,φ
B
= N
ρ
r,φ
A
. This situation is depicted in Figure 11.
Accepted in Quantum 2017-06-08, click title to verify 26
Alice public domain Bob
-
N
Φ
A
R
S
B
Φ
B
S
Figure 11: (State Distribution.) Alice sends the system A through the quantum channel N and Bob receives system B.
Alice public domain Bob
Φ
A
R
SS
U
B
meas
Φ
B
Figure 12: (Bob’s Measurement.) Bob measures the quantum system B using the measurement settings given by his private
randomness Φ
B
and obtains two classical strings stored in registers and U.
Measurement: Bob measures each of his M quantum systems in the basis corresponding to Φ
B
and stores
his measurement outcomes, either 0, 1, or in the case of inconclusive outcomes, in a classical register U taking
values in {0, 1, }
M
. The measurement map M
BU|S
Φ
B
is defined as:
M
BU|S
Φ
B
(·) =
X
φ∈{0,1}
M
X
u∈{0,1,}
M
|u, ωi
T C
M
φ,u
B
|φihφ|
S
Φ
B
·
M
φ,u
B
|φihφ|
S
Φ
B
hu, ω|
UC
, (115)
where ω = ω(u) is the subset of [M] where u takes values in {0, 1}, namely
ω(u) := {i [M] : u
i
6= }. (116)
The state of the total system after Bob’s measurement is given by
σ
RUC
BS
Φ
A
S
Φ
B
=
1
8
M
X
r,φ
A
B
∈{0,1}
M
X
u∈{0,1,}
M
|r, u, ω, φ
A
, φ
B
ihr, u, ω, φ
A
, φ
B
|
RUC
S
Φ
A
S
Φ
B
M
φ
B
,u
B
ρ
r,φ
A
B
M
φ
B
,u
B
,
(117)
and the situation is depicted in Figure 12.
Alice public domain Bob
Φ
B
R Φ
A
S
Φ
B
S U
?
-
6 6
S
Φ
B
C
S
Figure 13: (Randomness distribution.) Bob communicates the both the value of Φ
B
and to Alice with the authenticated
classical channel. Alice publicly announces the value of the various seeds, S = (S
Π
, S
H
ec
, S
H
pa
).
Randomness distribution: Bob publicly announces the content of the register S
Φ
B
together with the de-
scription C
of the set ω of indices corresponding to conclusive measurement results. This situation is depicted
in Figure 13. Alice publicly announces the value of the various seeds, S = (S
Π
, S
H
ec
, S
H
pa
).
Accepted in Quantum 2017-06-08, click title to verify 27
Sifting: Alice applies the sifting map, a classical map ‘sift’ defined as follows
sift :
(
{0, 1}
M
× {0, 1}
M
× 2
[M]
Π
M,m
× {, X}
(φ
A
, φ
B
, ω) 7→ , F
si
)
(118)
where Σ is either the first subset of of cardinality m in the lexicographic order where φ
A
and φ
B
coincide, if
such a set exists, or else it is set to a dummy value, for instance [m]. In the first case, the flag F
si
is set to X,
otherwise it is set to and the protocol aborts. The output of the sifting map immediately allows Alice and
Bob to compute the value of the seed S
Φ
which is simply the restriction of either S
Φ
A
or S
Φ
B
to the indices
in Σ. This classical map is lifted to give a CPTP map E
si
= S
Φ
A
S
Φ
B
C
C
Σ
C
F
si
S
Φ
A
S
Φ
B
. This situation is
depicted in Figure 14.
Alice public domain Bob
S
Φ
B
R Φ
A
Σ
-
@
@R ?
F
si
F
si
-
?
U
Σ
S
S
Φ
B
?
-
C
Σ
S
Φ
B
C
Figure 14: (Sifting 1/2.) Using her private randomness Φ
A
together with the registers and Φ
B
sent by Bob, Alice computes
the set Σ when it exists and sets the value of the flag F
si
. Both values are then publicly announced.
We then define a CPTP map E
di
that discards the systems in R, U and Φ
A
which do not correspond to the
subset Σ and put the remaining systems in registers denoted R
0
, U
0
and Φ of size m, respectively.
E
di
: C
Σ
RUS
Φ
A
R
0
U
0
C
Φ
C
Σ
. (119)
This situation is depicted in Figure 15.
Alice public domain Bob
S Σ
F
si
Φ
A
-
Φ Φ
R
R
0
S
U
Σ
U
0
Φ
B
-
F
si
C
S
C
Σ
S
Φ
B
Figure 15: (Sifting 2/2.) Using Σ, Alice (resp. Bob) discards the M m irrelevant systems of R (resp. U) and stores the m
remaining ones in R
0
(resp. U
0
). Both Alice and Bob further compute Φ from Σ and either Φ
A
or Φ
B
.
Finally, similarly as in the simple protocol of Part I, Alice and Bob use the content of register Π to reorder
their raw keys, which become (V, X) for Alice and (W, Y ) for Bob. The situation here is similar to that obtained
after measurement in the simple protocol (compare Figures 16 and 3), with the addition of the registers C
Σ
,
C
, S
Φ
B
and F
si
now available in the public domain.
Remaining steps: The remaining steps are as in the entanglement-based QKD protocol presented in Part I.
8 Results and Discussion
The security proof should establish that for any input channel N
AB
given to qkd_pm
M,m,pe,ec,pa
, either the
protocol outputs secret identical keys, or else it aborts. In the same spirit as the entanglement-based version of
Accepted in Quantum 2017-06-08, click title to verify 28
Alice public domain Bob
S
R
0
Φ
-
V X
S
U
0
-
W Y
Φ
F
si
C
S
C
Σ
S
Φ
B
Figure 16: (Reordering.) Using the content of S
Π
, Alice reorder their raw keys, R
0
and U
0
, which become respectively (X, V )
and (Y, W ).
Part I, we define the security parameter
M,si,pe,ec,pa
:= sup
N
ABE
qkd_pm
M,m,pe,ec,pa
(N
ABE
) qkd_ideal
M,k,n,δ,ec,pa
(N
ABE
)
tr
, (120)
where again qkd_ideal
M,k,n,δ,si,ec,pa
is defined analogously to the entanglement-based case and simply replaces
the output of qkd_pm
M,m,pe,ec,pa
(N
ABE
) with a perfect key in case the protocol does not abort. Here, the
channels N
ABE
have an additional output that goes to an eavesdropper, and it again suffices to consider maps
where E is finite-dimensional. Establishing security thus boils down to showing that this trace distance is small
for all such channels.
Our strategy is to show that the realistic protocol is equivalent to applying the idealized QKD protocol on
a virtual quantum state ρ
AB
independent from the uniformly distributed random seed S
Φ
for the measurement
settings. If this holds, then the security proof of Part I for the simple protocol applies, and establishes the
security of the prepare-and-measure protocol. For this, we need to make explicit assumptions about (i) the
state preparation on Alice’s side to make sure that no basis information is leaked and (ii) the measurement
device on Bob’s side to ensure that the invalid measurement results do not depend on the measurement basis.
Under the assumptions in Section 7.1, we show that the prepare-and-measure QKD protocol is secure.
Theorem 13. Let m, pe, ec, pa be such that the protocol qkd_eb
m,pe,ec,pa
in Section 3 is ε-secure with device
parameter ¯c = ¯c
0
. Then qkd_pm
M,m,pe,ec,pa
is also ε-secure.
As will be shown in Section 9, the security of the prepare-and-measure protocol is a consequence of that of
the simple protocol studied in Part I, provided that some additional assumptions are made.
When assessing the performance of the protocol, however, two modifications appear. First, the device
parameter (¯c
0
instead of ¯c) needs to be defined differently since it is no longer a function of the measurement
device of Alice, but rather of her preparation device. In an ideal implementation, it is still expected to be equal
to
1
2
, as was discussed in Section 7.1. The more important difference is due to the sifting procedure. Indeed, the
definition of the secret key rate should now be modified to mean the ration between the key length ` and the
number M of individual states prepared and sent by Alice (instead of the number m in the simple entanglement-
based protocol). The means that the secret key rate achieved with the prepare-and-measure protocol is given
by
`
M
=
m
M
·
`
m
. (121)
The sifting procedure that we have considered here (and described in Section 7.3) is not optimized to maximize
the secret key rate (or equivalently the ratio
m
M
), but rather to simplify the analysis as much as possible. Better
sifting procedures are discussed in [19] and could involve not fixing the value of M in advance for instance.
A typical experiment would be characterized by a given overall transmittance η of the optical channel,
meaning that approximately ηM photons will be detected by Bob, or in other words, that the expected value
of || is ηM. Given that Alice and Bob’s measurement bases will coincide on expectation 50% of the time, we
therefore expect that
m
M
η
2
(122)
holds asymptotically.
In particular, the secret key rate of the prepare-and-measure protocol is then expected to be equal to
η
2
times the secret key rate of the simple protocol displayed in Figure 7.
9 Security reduction
In Sections 9.1 and 9.2, we discuss some implications of the device assumptions made in Section 7.1. The
security reduction to the simple protocol will be addressed in Section 9.3.
Accepted in Quantum 2017-06-08, click title to verify 29
9.1 Preparation: Assumptions on Alice’s device
Consider the four states {ρ
x,φ
A
i
}
x,φ∈{0,1}
created by Alice in round i of the protocol for some i [M]. Since these
states adhere to the assumptions stated in (104) and (106), the following lemma is applicable:
Lemma 14. Let {ρ
φ,x
A
}
φ,x
S(A) where x and φ are taken from discrete sets. Moreover, let {p
φ
x
}
x
be a
probability distribution for each φ such that
X
x
p
φ
x
ρ
φ,x
A
=
X
x
p
φ
0
x
ρ
φ
0
,x
A
for all φ and φ
0
. (123)
Then there exists a state τ
AA
0
S(AA
0
) where A
0
A and a generalized measurement {M
φ,x
A
0
}
x
on A
0
for each
φ such that
p
φ
x
ρ
φ,x
A
= tr
A
0
h
τ
AA
0
id
A
M
φ,x
A
0
M
φ,x
A
0
i
and c
M
φ,x
A
0
x
,
M
φ
0
,x
A
0
x
= c
0
{ρ
φ,x
A
}
x
, {ρ
φ
0
,x
A
}
x
. (124)
Proof. We will explicitly construct the state and measurement as follows. First, let us introduce τ
A
:=
P
x
p
φ
x
ρ
φ,x
A
and choose τ
AA
0
as its purification on A
0
. Now we choose
M
φ,x
A
0
:=
q
p
φ
x
ρ
φ,x
A
1
2
T
τ
1
2
A
T
(125)
where the transpose is taken with regards to the Schmidt basis of τ
AA
0
. Let us first verify that this constitutes
a generalized measurement. Indeed, for every φ, we find
X
x
M
φ,x
A
0
M
φ,x
A
0
=
X
x
p
φ
x
τ
1
2
A
T
ρ
φ,x
A
T
τ
1
2
A
T
= id
A
0
. (126)
Let us now verify the conditions in (124). Since τ
AA
0
= |τ
AA
0
ihτ
AA
0
| purifies τ
A
, we find
id
A
M
φ,x
A
0
τ
AA
0
=
q
p
φ
x
id
A
ρ
φ,x
A
1
2
T
τ
1
2
A
T
τ
AA
0
=
q
p
φ
x
ρ
φ,x
AA
0
, (127)
where ρ
φ,x
AA
0
= |ρ
φ,x
AA
0
ihρ
φ,x
AA
0
| purifies ρ
φ,x
A
. The first equality readily follows. The second equality can be confirmed
by consulting the definitions of c and c
0
in (20) and (105), respectively.
These assumptions on Alice’s preparation allow us to replace the state preparation by a measurement
performed on a virtual extension of the average prepared state.
Corollary 15. If the two assumptions in (104) and (106) on Alice’s preparation device hold, then for each
i [M] there exists a state ρ
A
i
A
0
i
where A
0
i
A
i
and generalized measurements on A
0
i
of the form prescribed
in Section 3.1 such that c
i
c
0
i
, and, in particular, ¯c ¯c
0
. Combining all these measurements into a map
M
A
0
R|S
Φ
A
acting on A
0
A
0
[M]
, we further have
ρ
ARΦ
A
= M
A
0
R|S
Φ
A
(ρ
AA
0
ρ
Φ
A
) . (128)
9.2 Assumption on Bob’s measurement:
The objective of the assumption made on Bob’s measurement is to show that when the sifting procedure
succeeds, the resulting register S
Φ
is independent of the state shared by Alice and Bob, similarly as in the
entanglement-based protocol of Part I.
Lemma 16. If Bob’s measurement satisfies (108), that is, (M
0,
B
i
)
(M
0,
B
i
) = (M
1,
B
i
)
(M
1,
B
i
) for all i [M],
then the measurement map M
BU|S
Φ
B
can be decomposed as
M
BU|S
Φ
B
= M
BU|S
Φ
B
M
BB
. (129)
Proof. Define for each i [M] operators M
X
B
i
and M
B
i
satisfying
(M
X
B
i
)
(M
X
B
i
) =
X
z∈{0,1}
(M
0,z
B
i
)
(M
0,z
B
i
) =
X
z∈{0,1}
(M
1,z
B
i
)
(M
1,z
B
i
) (130)
(M
B
i
)
(M
B
i
) = (M
0,
B
i
)
(M
0,
B
i
) = (M
1,
B
i
)
(M
1,
B
i
). (131)
Accepted in Quantum 2017-06-08, click title to verify 30
Note in particular that (M
X
B
i
)
(M
X
B
i
) + (M
B
i
)
(M
B
i
) = id
B
i
. The generalized measurement M
BB
is then
described by
M
BB
: ρ
B
7→ ρ
B
=
X
c∈{X,}
M
|cihc|
M
c
B
ρ
B
(M
c
B
)
, (132)
with M
c
B
:=
N
M
i=1
M
c
i
B
i
. Up to relabeling, the string c contained in register describes the subset ω describing
the indices for which the measurement was conclusive. Indeed ω(c) = {i [M] : c
i
6= } = {i [M] : c
i
= X}.
It will be convenient in the following to write M
ω
B
instead of M
c
B
, and put the value ω = ω(c) in register .
Let us now define the second measurement, M
BU|S
Φ
B
, characterized by operators {M
u,φ,c
B
i
}
u∈{0,1,}
for each
i [M]. In the case where the register
i
is set to (or equivalently that the set ω does not contain index i),
we choose
M
,φ,
B
i
= id
B
i
, M
0,φ,
B
i
= 0, M
1,φ,
B
i
= 0 (133)
which means that the measurement is essentially trivial and simply reveals the content of register
i
. To address
the case where the register is set to X, indicating that a conclusive outcome should be obtained, we choose
operators M
0,φ,X
B
i
and M
1,φ,X
B
i
given by
M
0,φ,X
B
i
= M
0
B
i
(M
X
B
i
)
1/2
, M
1,φ,X
B
i
= M
1
B
i
(M
X
B
i
)
1/2
. (134)
It is immediate to check that these define valid generalized measurements and that Eq. (129) is satisfied.
Lemma 17. If the assumption of Eq. (108) on Bob’s measurement holds, then for any state ρ
A
0
BE
, define
ρ
A
00
B
0
C
Σ
C
S
Φ
EF
si = E
di
E
si
M
BB
(ρ
A
0
BE
ρ
S
Φ
A
ρ
S
Φ
B
). (135)
Then, the state conditioned on the sifting procedure passing satisfies:
ρ
A
00
B
0
S
Φ
C
Σ
C
E|F
si
=X
= ρ
A
0
BC
Σ
C
E|F
si
=X
ρ
S
Φ , (136)
where ρ
S
Φ =
1
2
m
P
φ∈{0,1}
m
|φihφ|
Φ
.
Proof. Since the measurement map M
BB
only acts on register B, independently of the value Φ
B
, we have
M
BB
(ρ
A
0
BE
ρ
S
Φ
A
ρ
S
Φ
B
) = ρ
A
0
BE
ρ
S
Φ
A
ρ
S
Φ
B
, (137)
where the state ρ
A
0
BE
= M
BB
(ρ
A
0
BE
) is a classical-quantum state:
ρ
A
0
BE
=
X
ω2
[M]
|ωihω|
(id
A
0
M
ω
B
id
E
)ρ
A
0
BE
(id
A
0
(M
ω
B
)
id
E
). (138)
It is straightforward to check that the classical map ‘sift’ has the following property: for all strings φ
A
, φ
B
, θ
{0, 1}
M
and any subset ω [M], if the sifting succeeds, then
sift(φ
A
+ θ, φ
B
+ θ, ω) = sift(φ
A
, φ
B
, ω). (139)
Indeed, this is true since the map ‘sift’ only examines whether Alice and Bob’s measurement bases coincide or
not, and not their actual value. In particular, if Φ
A
and Φ
B
are uniformly distributed, then Φ, the restriction
of Φ
A
to the subset Σ returned by the sifting map when it succeeds, will also be uniformly distributed over the
set of strings of length m.
Finally, the discarding map E
di
examines register S
Φ
A
and puts its content, restricted to the subset deter-
mined by the sifting map, into register S
Φ
, and traces over all the systems that do not belong to that subset.
The above property of the sifting map ensures that the value of Φ does not depend on .
This establishes that whenever the sifting test passes, the output state takes a tensor product form:
ρ
A
00
B
0
S
Φ
C
Σ
C
E|F
si
=X
= ρ
A
00
B
0
C
Σ
C
E|F
si
=X
ρ
S
Φ .
This lemma shows in particular that it is legitimate to consider S
Φ
as a uniform seed, and not as a transcript,
hence its notation S
Φ
instead of C
Φ
.
Accepted in Quantum 2017-06-08, click title to verify 31
9.3 Security: reduction to the entanglement-based protocol
We are now ready to prove Theorem 13.
Proof. It is sufficient to consider the case where the sifting procedure succeeds, since otherwise the protocol
aborts and its output is trivially secret. For this reason, let us define a slight variant qkd_modified
m,pe,ec,pa
of
the entanglement-based protocol of Part I which differs by taking an additional input register F
si
{X, }. The
variant starts by examining the content of this registers, and either aborts if the flag is set to , or proceeds
with the protocol qkd_eb
m,pe,ec,pa
if the flag is set to X. A second difference between qkd_eb
m,pe,ec,pa
and
qkd_modified
m,pe,ec,pa
is that the randomness for the measurement basis choice is explicitly given as an input.
In particular, for any state ρ
A
0
BE
, it holds that:
qkd_modified
m,pe,ec,pa
(ρ
A
0
BE
ρ
S
Φ |XihX|
F
si
) = qkd_eb
m,pe,ec,pa
(ρ
A
0
BE
) . (140)
From it definition, it is immediate that if qkd_eb
m,pe,ec,pa
is ε-secure, then so is qkd_modified
m,pe,ec,pa
. Indeed,
the only quantitative difference between the two protocol is that the latter one is less robust since it will not
output nontrivial keys as soon as the sifting flag is set to .
Our goal is therefore to show that in that case, for any input channel N
ABE
, there exists a state ρ
A
00
B
0
E
0
F
si
where A
00
and B
0
consist of m systems such that
qkd_pm
M,m,pe,ec,pa
(N
ABE
) = qkd_modified
m,pe,ec,pa
(ρ
A
00
B
0
E
0
F
si
ρ
S
Φ ). (141)
Let us therefore consider the application of the prepare-and-measure protocol qkd_pm
M,m,pe,ec,pa
to an arbitrary
quantum channel N
ABE
. According to the description of the protocol, the classical-quantum state shared by
Alice, Bob and Eve after the distribution step is given by some ρ
RBES
Φ
A
S
Φ
B
. The assumption made on Alice’s
preparation shows, as stated in Corollary 15, show that there exist a state τ
AA
0
and a measurement map
M
A
0
R|S
Φ
A
such that
ρ
RBES
Φ
A
S
Φ
B
= N
ABE
(ρ
RAS
Φ
A
S
Φ
B
) (142)
=
N
ABE
M
A
0
R|S
Φ
A
(τ
AA
0
ρ
S
Φ
A
ρ
S
Φ
B
) (143)
= M
A
0
R|S
Φ
A
(ρ
A
0
BE
ρ
Φ
A
ρ
Φ
B
) , (144)
where we defined ρ
A
0
BE
= N
ABE
(τ
AA
0
). The last equality follows from the fact that the maps N
ABE
and M
A
0
R|S
Φ
A
trivially commute since they act on distinct systems. After applying the measurement map
M
BB
promised by Lemma 16, followed by the sifting and discard maps, we obtain
ρ
R
0
B
0
ES
Φ
S
Φ
B
C
Σ
C
F
si
= E
di
E
si
M
BB
(ρ
RBES
Φ
A
S
Φ
B
) (145)
= E
di
E
si
M
BB
M
A
0
R|S
Φ
A
(ρ
A
0
BES
Φ
A
S
Φ
B
) , (146)
where R
0
and B
0
are now restricted to the m indices corresponding to the set Σ provided by the sifting map.
Indeed, recall that the discard map E
di
replaces the M-system registers R and B by m-system registers R
0
and
B
0
obtained by tracing over the systems not corresponding to Σ.
Since the measurement map M
A
0
R|S
Φ
A
of Alice’s system A
0
commutes with E
si
M
BB
, we obtain:
ρ
R
0
B
0
ES
Φ
S
Φ
B
C
Σ
C
F
si
= E
di
M
A
0
R|S
Φ
A
E
si
M
BB
(ρ
A
0
BES
Φ
A
S
Φ
B
) , (147)
In the mathematical description of the protocol given in Section 7.3, the discard map was applied to registers
R, B, but since it commutes with measurement maps on either Alice’s or Bob’s system, the map can be just
as well applied to registers A
0
and U, with outputs denoted A
00
and U
0
, respectively. We deduce that we can
replace the map E
di
M
A
0
R|S
Φ
A
by M
A
00
R
0
|S
Φ E
di
in (147). This yields:
ρ
R
0
B
0
ES
Φ
S
Φ
B
C
Σ
C
F
si
= M
A
00
R
0
|S
Φ E
di
E
si
M
BB
(ρ
A
0
BES
Φ
A
S
Φ
B
) (148)
= M
A
00
R
0
|S
Φ (ρ
A
00
B
0
C
Σ
C
S
Φ
S
Φ
B
EF
si
) . (149)
Lemma 17 now shows that
ρ
R
0
B
0
ES
Φ
S
Φ
B
C
Σ
C
|F
si
=X
= M
A
00
R
0
|S
Φ
ρ
A
00
B
0
EC
Σ
C
|F
si
=X
ρ
S
Φ . (150)
Let us finally collect E
0
= ES
Φ
B
C
Σ
C
. If the sifting test passes, then
qkd_modified
m,pe,ec,pa
ρ
A
00
B
0
S
Φ
E
0
|F
si
=X
ρ
S
Φ |XihX|
F
si
= qkd_eb
m,pe,ec,pa
(ρ
A
00
B
0
E
0
), (151)
which concludes the proof.
Accepted in Quantum 2017-06-08, click title to verify 32
10 Conclusion
We provide a self-contained security proof of QKD detailing all the steps of the protocol and explicitly spelling
out all the required assumptions for the security proof to go through. For simplicity, we focussed on a variant
of the entanglement-based BBM92 protocol as well as the BB84 protocol and showed that practical secret key
rates can be achieved, even for moderately large block size. These results, however, come at the price of several
assumptions which are sometimes challenging to enforce in practice. This should not come as a surprise since
many simplified implementations are known to be vulnerable to quantum hacking, illustrating that there exist
necessary trade-offs between ease of implementation and security guarantees.
We believe that there is room for improvement for these trade-offs and that further collaboration between
theory and experiment will be essential for achieving this objective. In this context, it is crucial to model
the protocols as thoroughly as possible in order to understand what level of security can be obtained, and
under which assumptions. Finally, we would like to encourage more research into derving tight finite resource
trade-offs for quantum key distribution protocols beyond BB84 and BBM92. This will likely require techniques
beyond the entropic uncertainty relation presented here. An example of interest is the 6-state protocol [45]
where entropic uncertainty relations do not currently yield optimal secret key rates (even asymptotically) and
approaches based on a more complete tomography of the channel lead to large penalities for finite keys.
Note added. After completion of this work a novel and intriguing proof technique (based on Rényi entropy
accumulation) has been proposed by Dupuis et al. [46]. This technique does not yet seem to yield tradeoffs
between security and protocol parameters that match those found in [13] and [14], on which we improve upon
here. However, the technique is more versatile and in particular allows to show security of device-independent
protocols as demonstrated by Arnon-Friedman et al. [47]. Device-independent protocols have the advantage
that fewer assumptions on the physical devices used in the protocol are required, but are beyond the scope of
this work.
Acknowledgements. We thank Philippe Grangier, Christopher Portmann and Charles Lim Ci Wen for
helpful comments. MT is funded by an ARC Discovery Early Career Researcher Award (DECRA) fellowship
and acknowledges support from the ARC Centre of Excellence for Engineered Quantum Systems (EQUS).
References
[1] C.H. Bennett and G. Brassard. Quantum Cryptography: Public Key Distribution and Coin Tossing. In
Proc. IEEE International Conference on Computers, Systems and Signal Processing 1984, volume 1, pages
175–179, Bangalore, 1984.
[2] A.K. Ekert. Quantum Cryptography Based on Bell’s Theorem. Physical Review Letters, 67(6):661–663,
1991. DOI: 10.1103/PhysRevLett.67.661.
[3] C. Bennett, G. Brassard, and N. Mermin. Quantum Cryptography Without Bell’s Theorem. Physical
Review Letters, 68(5):557–559, 1992. DOI: 10.1103/PhysRevLett.68.557.
[4] H.-K. Lo and H.F. Chau. Unconditional Security of Quantum Key Distribution over Arbitrarily Long
Distances. Science, 283(5410):2050–2056, 1999. DOI: 10.1126/science.283.5410.2050.
[5] P.W. Shor and J. Preskill. Simple Proof of Security of the BB84 Quantum Key Distribution Protocol.
Physical Review Letters, 85(2):441–444, 2000. DOI: 10.1103/PhysRevLett.85.441.
[6] D. Mayers. Unconditional Security in Quantum Cryptography. Journal of the ACM, 48(3):351–406, 2001.
DOI: 10.1145/382780.382781.
[7] M. Koashi. Unconditional Security of Quantum Key Distribution and the Uncertainty Principle. Journal
of Physics: Conference Series, 36(1):98–102, 2006. DOI: 10.1088/1742-6596/36/1/016.
[8] H. Maassen and J. Uffink. Generalized Entropic Uncertainty Relations. Physical Review Letters, 60(12):
1103–1106, 1988. DOI: 10.1103/PhysRevLett.60.1103.
[9] W. Heisenberg. Über den Anschaulichen Inhalt der Quantentheoretischen Kinematik und Mechanik.
Zeitschrift für Physik, 43(3-4):172–198, mar 1927.
[10] R. Renner. Security of Quantum Key Distribution. PhD thesis, ETH Zurich, 2005. URL http://arxiv.
org/abs/quant-ph/0512258.
[11] L.C. Comandar, M. Lucamarini, B. Fröhlich, J.F. Dynes, A.W. Sharpe, S.W.-B. Tam, Z.L. Yuan,
R.V. Penty, and A.J. Shields. Quantum key distribution without detector vulnerabilities using optically
seeded lasers. Nature Photonics, 10(5):312–315, 2016. DOI: 10.1038/nphoton.2016.50.
[12] P. Jouguet, S. Kunz-Jacques, A. Leverrier, P. Grangier, and E. Diamanti. Experimental demonstration of
long-distance continuous-variable quantum key distribution. Nature Photonics, 7(5):378–381, 2013. DOI:
10.1038/nphoton.2013.63.
Accepted in Quantum 2017-06-08, click title to verify 33
[13] M. Tomamichel, C.C.W. Lim, N. Gisin, and R. Renner. Tight Finite-Key Analysis for Quantum Cryptog-
raphy. Nature Communications, 3:634, 2012. DOI: 10.1038/ncomms1631.
[14] M. Hayashi and T. Tsurumaru. Concise and Tight Security Analysis of the Bennett-Brassard 1984
Protocol with Finite Key Lengths. New Journal of Physics, 14(9):093014, 2012. DOI: 10.1088/1367-
2630/14/9/093014.
[15] V. Scarani and R. Renner. Quantum Cryptography with Finite Resources: Unconditional Security Bound
for Discrete-Variable Protocols with One-Way Postprocessing. Physical Review Letters, 100(20), 2008. DOI:
10.1103/PhysRevLett.100.200501.
[16] R. Renner. Symmetry of Large Physical Systems Implies Independence of Subsystems. Nature Physics, 3
(9):645–649, 2007. DOI: 10.1038/nphys684.
[17] M. Christandl, R. König, and R. Renner. Postselection Technique for Quantum Channels with Applications
to Quantum Cryptography. Physical Review Letters, 102(2), 2009. DOI: 10.1103/PhysRevLett.102.020504.
[18] L. Sheridan, T.P. Le, and V. Scarani. Finite-Key Security Against Coherent Attacks in Quantum Key
Distribution. New Journal of Physics, 12:123019, 2010.
[19] C. Pfister, N. Lütkenhaus, S. Wehner, and P.J. Coles. Sifting Attacks in Finite-Size Quantum Key Distri-
bution. New Journal of Physics, 18(5):053001, 2016. DOI: 10.1088/1367-2630/18/5/053001.
[20] M. Tomamichel, S. Fehr, J. Kaniewski, and S. Wehner. A Monogamy-of-Entanglement Game with Ap-
plications to Device-Independent Quantum Cryptography. New Journal of Physics, 15(10):103002, 2013.
DOI: 10.1088/1367-2630/15/10/103002.
[21] M. Tomamichel and R. Renner. Uncertainty Relation for Smooth Entropies. Physical Review Letters, 106
(11):110506, 2011. DOI: 10.1103/PhysRevLett.106.110506.
[22] M. Tomamichel. Quantum Information Processing with Finite Resources Mathematical Foundations,
volume 5 of SpringerBriefs in Mathematical Physics. Springer International Publishing, 2016. ISBN 978-
3-319-21890-8. DOI: 10.1007/978-3-319-21891-5.
[23] C.W. Helstrom. Quantum Detection and Estimation Theory. Academic Press, New York, NY, 1976.
[24] M. Tomamichel, R. Colbeck, and R. Renner. Duality Between Smooth Min- and Max-Entropies. IEEE
Transactions on Information Theory, 56(9):4674–4681, 2010. DOI: 10.1109/TIT.2010.2054130.
[25] J.L. Carter and M.N. Wegman. Universal Classes of Hash Functions. Journal of Computer and System
Sciences, 18(2):143–154, 1979. DOI: 10.1016/0022-0000(79)90044-8.
[26] M.N. Wegman and J.L. Carter. New Hash Functions and their Use in Authentication and Set Equality.
Journal of Computer and System Sciences, 22(3):265–279, 1981. DOI: 10.1016/0022-0000(81)90033-7.
[27] A. Rényi. On Measures of Information and Entropy. In Proc. 4th Berkeley Symposium on Mathematical
Statistics and Probability, volume 1, pages 547–561, Berkeley, California, USA, 1961. University of California
Press.
[28] R. König, R. Renner, and C. Schaffner. The Operational Meaning of Min- and Max-Entropy. IEEE
Transactions on Information Theory, 55(9):4337–4347, 2009. DOI: 10.1109/TIT.2009.2025545.
[29] S. Winkler, M. Tomamichel, S. Hengl, and R. Renner. Impossibility of Growing Quantum Bit Commitments.
Physical Review Letters, 107(9):090502, 2011. ISSN 0031-9007. DOI: 10.1103/PhysRevLett.107.090502.
[30] H.-K. Lo, H.F. Chau, and M. Ardehali. Efficient Quantum Key Distribution Scheme and a Proof of Its
Unconditional Security. Journal of Cryptology, 18(2):133–165, 2004 DOI: 10.1007/s00145-004-0142-y
[31] D. Frauchiger, R. Renner, and M. Troyer. True randomness from realistic quantum devices, 2013. URL
http://arxiv.org/abs/1311.4547.
[32] C. Portmann and R. Renner. Cryptographic Security of Quantum Key Distribution, 2014. URL http:
//arxiv.org/abs/1409.3525.
[33] L. Lydersen, C. Wiechers, C. Wittmann, D. Elser, J. Skaar, and V. Makarov. Hacking Commercial Quantum
Cryptography Systems by Tailored Bright Illumination. Nature Photonics, 4(10):686–689, 2010. DOI:
10.1038/nphoton.2010.214.
[34] M. Tomamichel and Esther Hänggi. The Link Between Entropic Uncertainty and Nonlocality. Journal of
Physics A: Mathematical and Theoretical, 46(5):055301, 2013. DOI: 10.1088/1751-8113/46/5/055301.
[35] C.C.W. Lim, C. Portmann, M. Tomamichel, R. Renner, and Nicolas Gisin. Device-Independent Quan-
tum Key Distribution with Local Bell Test. Physical Review X, 3(3):031006, 2013. DOI: 10.1103/Phys-
RevX.3.031006.
[36] I. Devetak and A. Winter. Distillation of Secret Key and Entanglement from Quantum States. Proceedings
of the Royal Society A, 461(2053):207–235, 2005. DOI: 10.1098/rspa.2004.1372.
[37] D. Elkouss, A. Leverrier, R. Alleaume, and J.J. Boutros. Efficient Reconciliation Protocol for Discrete-
Variable Quantum Key Distribution. In Proc. IEEE ISIT 2009, pages 1879–1883, 2009. DOI:
10.1109/ISIT.2009.5205475.
Accepted in Quantum 2017-06-08, click title to verify 34
[38] M. Tomamichel, J. Martinez-Mateo, C. Pacher, and D. Elkouss. Fundamental Finite Key Limits for
Information Reconciliation in Quantum Key Distribution, 2014. URL http://arxiv.org/abs/1401.5194.
[39] M. Tomamichel. A Framework for Non-Asymptotic Quantum Information Theory. PhD thesis, ETH
Zurich, 2012. URL http://arxiv.org/abs/1203.2142.
[40] R.J. Serfling. Probability Inequalities for the Sum in Sampling without Replacement. Annals of Statistics,
2(1):39–48, 1974.
[41] J.H. van Lint. Introduction to Coding Theory. Graduate Texts in Mathematics. Springer, third edition,
1999.
[42] H.-K. Lo, X. Ma, and K. Chen. Decoy State Quantum Key Distribution. Physical Review Letters, 94(23),
2005. DOI: 10.1103/PhysRevLett.94.230504.
[43] J. Hasegawa, M. Hayashi, T. Hiroshima, and A. Tomita. Security analysis of decoy state quantum key
distribution incorporating finite statistics, 2007. URL http://arxiv.org/abs/0707.3541.
[44] C.C.W. Lim, M. Curty, N. Walenta, F. Xu, and H. Zbinden. Concise security bounds for practical
decoy-state quantum key distribution. Physical Review A, 89(2):022307, 2014. DOI: 10.1103/Phys-
RevA.89.022307.
[45] D. Bruss. Optimal Eavesdropping in Quantum Cryptography with Six States. Physical Review Letters, 81
(14):3018–3021, 1998. DOI: 10.1103/PhysRevLett.81.3018.
[46] F. Dupuis, O. Fawzi, and R. Renner. Entropy accumulation, 2016. URL http://arxiv.org/abs/1607.
01796.
[47] R. Arnon-Friedman, R. Renner, and T. Vidick. Simple and tight device-independent security proofs, 2016.
URL http://arxiv.org/abs/1607.01797.
[48] R. Bhatia. Matrix Analysis. Graduate Texts in Mathematics. Springer, 1997. ISBN 0-387-94846-5.
A Proof of entropic uncertainty relation in Proposition 4
Let us restate the desired inequality for the convenience of the reader.
Proposition 4 (restated). Let τ
AP RS
S
(AP RS) be an arbitrary sub-normalized state with P a classical
register, and set t := tr{τ
AP RS
}. Furthermore, let ε [0,
t) and let q be a bijective function on P that is a
symmetry of τ
AP RS
in the sense that τ
ARS,P =p
= τ
ARS,P =q(p)
for all p P . Then, we have
H
ε
min
(X|P R)
σ
+ H
ε
max
(X|P S)
σ
log
1
c
q
, where (152)
where c
q
= max
pP
max
x,zX
F
q(p),x
A
F
p,z
A
2
. Here, σ
XP RS
= M
AX|P
(τ
AP RS
) for the map
M
AX|P
·
= tr
A
(
X
pP
X
xX
|xi
X
|pihp|
P
F
p,x
A
·
|pihp|
P
F
p,x
A
hx|
X
)
. (153)
and any set (indexed by p P ) of generalized measurements {F
p,x
A
}
xX
.
Proof. The condition on ε ensures that all smooth entropies are well-defined. We first introduce the Stinespring
dilation isometry of the measurement map M
AX|P
. This is the isometry V : A AXX
0
|P given by
V :=
X
pP
X
xX
|xi
X
|xi
X
0
|pihp|
P
F
p,x
A
. (154)
Now note that the measured state σ
XP RS
in (153) has a natural purification in
σ
P P
0
AXX
0
RSD
= V
τ
P P
0
ARSD
V
, where (155)
|τ
P P
0
ARSD
i =
X
pP
p
Pr[P = p]
τ
|pi
P
|pi
P
0
τ
ARSD|P =p
, (156)
where P
0
is isomorphic to P and
τ
ARSD|P =p
is any purification of τ
ARS|P =p
on a sufficiently large auxiliary
system D. (The choice |D| = |A||R||S| ensures that all purifications can be accommodated.) This now allows us
to rephrase our target inequality. Using the duality relation for smooth min- and max-entropy in (17) together
with the fact that H
ε
min
(X|P R)
σ
= H
ε
min
(X|P
0
R)
σ
since P
0
is a copy of P , we find that (152) is equivalent to
H
ε
min
(X|P R)
σ
H
ε
min
(X|P AX
0
RD)
σ
+ log
1
c
q
. (157)
Accepted in Quantum 2017-06-08, click title to verify 35
Moreover, the data-processing inequality for the smooth min-entropy in (18) applied for the map tr
D
yields
H
ε
min
(X|P AX
0
RD)
σ
H
ε
min
(X|P AX
0
R)
σ
and thus it in fact suffices to show that
13
H
ε
min
(X|P R)
σ
H
ε
min
(X|P AX
0
R)
σ
+ log
1
c
q
. (158)
The remainder of the proof will be concerned with showing the inequality in (158).
For this purpose, let us consider the following unitary rotation:
Q
P
=
X
pP
q
1
(p)
p
P
. (159)
that exchanges p with its conjugate, q(p). It clearly acts as a permutation when acting on the classical register
P and furthermore we have Q
P
(τ
AP RS
)Q
P
= τ
AP RS
due to the symmetry condition that we imposed on q and
τ
P ARS
in the statement of the proposition. Based on this we define the isometry
¯
V := Q
P
V Q
P
=
X
pP
X
xX
|xi
X
|xi
X
0
|pihp|
P
F
q(p),x
A
, (160)
that corresponds to a measurement in the basis determined by q(p) instead of p. We find
¯
V V
σ
AXX
0
P RS
V
¯
V
= Q
P
V Q
P
(τ
AP RS
)Q
P
V
Q
P
= Q
P
σ
AXX
0
P RS
Q
P
, (161)
which shows that the trace non-increasing map
¯
V V
(·)V
¯
V
coherently undoes the measurement in the basis
determined by p and then instead measures in the basis determined by q(p).
Now we have the tools at hand to prove the inequality in (158). By the definition of the smooth min-
entropy, H
ε
min
(X|P AX
0
R)
σ
, there exists a state ω
P AX
0
R
S(P AX
0
R) and a sub-normalized state ˜σ
P AXX
0
R
S
(P AXX
0
R) that is ε-close to σ
P AXX
0
R
in the sense that P(σ
P AXX
0
R
, ˜σ
P AXX
0
R
) ε such that the following
inequality holds:
˜σ
P AXX
0
R
2
λ
id
X
ω
P AX
0
R
with λ := H
ε
min
(X|P AX
0
R)
σ
. (162)
Next we consider the CP trace non-increasing map
F
XX
0
AX|P
[ ·] =
X
pP
tr
AX
0
Q
P
¯
V V
|pihp|
P
· |pihp|
P
V
¯
V
Q
P
. (163)
From (161) we learn that F
σ
P AXX
0
R
= σ
P XR
. Thus, using the fact that the purified distance contracts (3)
when we apply F, we find that the state ˆσ
P XR
:= F
˜σ
P AXX
0
R
satisfies
P (ˆσ
P XR
, σ
P XR
) P (˜σ
P AXX
0
R
, σ
P AXX
0
R
) ε. (164)
Furthermore, applying F on both sides of (162) yields
ˆσ
P XR
2
λ
F
id
X
ω
P AX
0
R
= 2
λ
tr
X
0
A
Q
P
¯
V V
id
X
ˆω
P AX
0
R
V
¯
V
Q
P
, (165)
where ˆω
P AX
0
R
=
P
pP
|pihp|
P
ˆω
p
AX
0
R
with ˆω
p
AX
0
R
= hp|ω
P AX
0
R
|pi
P
.
Let us now simplify the right-hand side of this inequality, hoping to capture the incompatibility of the
measurements in the basis p versus the basis q(p). First, we note that
Q
P
¯
V V
=
X
pP
X
x,zX
|zihx|
X
|zihx|
X
0
q(p)
p
P
F
q(p),z
A
F
p,x
A
. (166)
13
In its cryptographic application, another intuitive way to justify that we can remove the purifying system D is that, without
loss of generality, we may assume that the eavesdropper already holds a purification of the state shared by the honest parties and
D is thus trivial. Luckily this physical intuition is corroborated by a mathematical argument the data-processing inequality.
Accepted in Quantum 2017-06-08, click title to verify 36
and, hence, we can write
tr
X
0
A
Q
P
¯
V V
id
X
ˆω
P AX
0
R
V
¯
V
Q
P
=
X
pP
X
x,zX
|xihx|
X
|q(p)ihq(p)|
P
hz|tr
A
F
q(p),z
A
F
p,x
A
ˆω
p
AX
0
R
F
p,x
A
F
q(p),z
A
|zi
X
0
(167)
X
pP
X
x,zX
|xihx|
X
|q(p)ihq(p)|
P
F
p,x
A
F
q(p),z
A
F
q(p),z
A
F
p,x
A
hz|tr
A
ˆω
p
AX
0
R
|zi
X
0
(168)
=
X
pP
X
x,zX
|xihx|
X
|q(p)ihq(p)|
P
F
q(p),x
A
F
p,z
A
2
hz| ˆω
p
X
0
R
|zi
X
0
(169)
max
pP
max
x,zX
F
q(p),x
A
F
p,z
A
2
·
X
pP
X
x,zX
|xihx|
X
|pihp|
P
hz| ˆω
p
X
0
R
|zi
X
0
(170)
= c
q
·
X
pP
id
X
|pihp|
P
ˆω
p
R
. (171)
To establish (168) and (169) we used the fact that L
L kL
Lk
id = kLk
2
id for every linear operator L by
definition of the operator norm. The final equality (171) follows from the definition of c
q
.
Combining this bound with (165) yields
ˆσ
P XR
2
λ
c
q
· id
X
X
pP
|pihp|
P
ˆω
p
R
. (172)
Since
P
pP
tr(ˆω
p
R
) = 1 by construction and P (ˆσ
P XR
, σ
P XR
) ε due to (164), the definition of the smooth
entropy implies that
H
ε
min
(X|P R)
σ
λ log c
q
= H
ε
min
(X|P AX
0
R)
σ
log c
q
, (173)
concluding the proof.
B Proof of Leftover Hashing Lemma in Proposition 9
Our proof of the leftover hashing lemma is based on the following result due to Renner [10, Corollary 5.5.2]:
Lemma 18. Let σ
XD
S
(XD) be a classical on X and let H be a universal
2
family of hash functions from
X = {0, 1}
n
to K = {0, 1}
`
. Moreover, let ρ
S
H
=
1
|H|
P
h∈H
|hihh|
S
H
be fully mixed. Then,
ω
KS
H
D
χ
K
ω
S
H
D
tr
1
2
p
tr{σ
XD
}2
1
2
(H
min
(X|D)
σ
`)
(174)
where χ
K
=
1
2
`
id
K
is the fully mixed state and ω
KS
H
D
= tr
X
E
f
(σ
XD
ρ
S
H
)
for the function f : (x, h) 7→ h(x)
that acts on the registers X and S
H
.
We provide a short proof for the convenience of the reader (see [22, Section 7.3.2]).
Proof. First, by definition of the min-entropy, there exists a state τ
D
S(D) such that σ
XD
2
H
min
(X|D)
σ
id
X
τ
D
. Next, note that by definition of the trace distance, we have
ω
KS
H
D
χ
K
ω
S
H
D
tr
=
X
h∈H
1
2|H|
ω
KD|S
H
=h
χ
K
ω
D|S
H
=h
1
, (175)
where k · k
1
denotes the Schatten 1-norm. Moreover, by construction of ω
KS
H
D
it is evident that ω
D|S
H
=h
=
ω
D
= σ
D
for all h H. Due to Hölder’s inequality for Schatten norms [48, Corollary IV.2.6], we have
ω
KD|S
H
=h
χ
K
σ
D
2
1
id
K
τ
1
2
D
2
2
id
K
τ
1
2
D
ω
KD|S
H
=h
χ
K
σ
D
2
2
(176)
= 2
`
tr{τ
D
}tr
n
id
K
τ
1
D
ω
KD|S
H
=h
χ
K
σ
D
2
o
(177)
= 2
`
tr

id
K
τ
1
D
ω
2
KD|S
H
=h
tr
τ
1
D
σ
2
D
, (178)
Accepted in Quantum 2017-06-08, click title to verify 37
where τ
D
is inverted on its support. We took advantage of the fact that χ
K
=
1
2
`
id
K
is proportional to the
identity to simplify the above expression. Combining this with (175), Jensen’s inequality thus ensures that
ω
KS
H
D
χ
K
ω
S
H
D
tr
1
2
s
X
h∈H
2
`
|H|
tr
n
id
K
τ
1
D
ω
2
KD|S
H
=h
o
tr
τ
1
D
σ
2
D
. (179)
Next, observe that ω
KD|S
H
=h
=
P
k∈{0,1}
`
P
x∈{0,1}
n
,h(x)=k
|kihk| σ
DX=x
by construction. We then use
the universal
2
property of H which implies that
1
|H|
P
h∈H
1{h(x) = h(y)} = 2
`
when x 6= y. This yields
X
h∈H
1
|H|
tr
id
K
τ
1
D
ω
2
KD|S
H
=h
=
X
x,y∈{0,1}
n
1
|H|
X
h∈H
1{h(x) = h(y)}tr
τ
1
D
σ
DX=x
σ
DX=y
(180)
=
X
x∈{0,1}
n
tr
τ
1
D
σ
2
DX=x
+
X
x,y∈{0,1}
n
x6=y
2
`
tr
τ
1
D
σ
DX=x
σ
DX=y
(181)
=
1 2
`
tr

id
X
τ
1
D
σ
2
XD
+ 2
`
tr{τ
1
D
σ
2
D
}. (182)
Bounding 1 2
`
1 and plugging this into (179), we find
ω
KS
H
D
χ
K
ω
S
H
D
tr
1
2
q
2
`
tr

id
X
τ
1
D
σ
2
XD
. (183)
Finally, due to the operator anti-monotonicity of the inverse and the definition of τ
D
, we have id
X
τ
1
D
2
H
min
(X|D)
σ
1
XD
. Combined with (183) this yields the desired result.
Let us restate the desired inequality for the convenience of the reader.
Proposition 9 (restated). Let σ
XD
S
(XD) be a classical on X and let H be a universal
2
family of hash
functions from X = {0, 1}
n
to K = {0, 1}
`
. Moreover, let ρ
S
H
=
1
|H|
P
h∈H
|hihh|
S
H
be fully mixed. Then,
ω
KS
H
D
χ
K
ω
S
H
D
tr
1
2
2
1
2
(H
ε
min
(X|D)
σ
`)
+ 2ε (184)
where χ
K
and ω
KS
H
D
are define as in Lemma 18.
Proof. Let ˜σ
XD
S
(XD) be a sub-normalized state such that H
ε
min
(X|D)
σ
= H
min
(X|D)
˜σ
and P (˜σ
XD
, σ
XD
)
ε. Without loss of generality we can assume that ˜σ
XD
is classical on X. Now, the Lemma 18 yields the inequality
k˜ω
KS
H
D
χ
K
˜ω
S
H
D
k
tr
1
2
p
tr{˜σ
XD
} · 2
1
2
(H
min
(X|D)
˜σ
`)
1
2
· 2
1
2
(H
ε
min
(X|D)
σ
`)
, (185)
where we constructed ˜ω
KS
H
D
= tr
X
E
f
(˜σ
XD
ρ
S
H
)
and bounded tr{˜σ
XD
} 1 to arrive at the second inequal-
ity. Using the monotonicity of the purified distance under CPTP maps we conclude that P (˜ω
S
H
D
, ω
S
H
D
)
P (˜ω
KS
H
D
, ω
KS
H
D
) ε. Finally, exploiting the triangle inequality for the trace norm we find
kω
KS
H
D
χ
K
ω
S
H
D
k
tr
2ε + k˜ω
KS
H
D
χ
K
˜ω
S
H
D
k
tr
. (186)
Accepted in Quantum 2017-06-08, click title to verify 38