# A largely self-contained and complete security proof for quantum key
distribution

Marco Tomamichel  Centre for Quantum Software and Information, University of
Technology Sydney, Australia  School of Physics, The University of Sydney,
Australia<EMAIL_ADDRESS>www.marcotom.info Anthony Leverrier
Inria Paris, France<EMAIL_ADDRESS>https://who.paris.inria.fr/Anthony.Leverrier

###### Abstract

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
amplification, 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:

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 possible111This is most relevant for implementations that
suffer from a low rate of measurement events, e.g. entanglement-based
implementations. 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
indistinguishability 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 particular 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. 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. 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.

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 devices222An 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., 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.333Unfortunately, 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, 18]. 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.444For 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. 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) and Section 9.3 reduces their security to the
security of the entanglement-based protocol.

_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. [22]. 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. [23]. 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.

###  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 [24] for a comprehensive introduction
into this mathematical toolkit. Sections 2.1–2.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.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,\ldots,m\\}$ and use $A_{[m]}$ to denote a joint
quantum system comprised of quantum systems $A_{1}A_{2}\ldots 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
$\Pi_{m,k}:=\\{\pi\subset[m]:|\pi|=k\\}$, the set of subsets of $[m]$ of size
$k$.

We write $\mathcal{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

$\displaystyle\|\rho-\sigma\|_{\operatorname{tr}}:=\sup_{P}\operatorname{tr}\big{\\{}P(\rho-\sigma)\big{\\}}\,,$
(1)

where $P$ ranges over projectors, i.e. positive semi-definite operators with
eigenvalues in $\\{0,1\\}$. In particular, we have
$\|\rho-\sigma\|_{\operatorname{tr}}=\frac{1}{2}\|\rho-\sigma\|_{1}$, where
$\|\cdot\|_{1}$ denotes the Schatten 1-norm. The trace distance has an
immediate physical interpretation [25]: for two states with trace distance
$\varepsilon$, the maximum probability of distinguishing them with a single
measurement equals $\frac{1}{2}(1+\varepsilon)$.

We also collect positive semi-definite operators with trace norm not exceeding
1 on $A$ in the set $\mathcal{S}_{\bullet}(A)$, and call them sub-normalized
states.555The disk in the subscript of $\mathcal{S}_{\bullet}$ symbolizes the
unit disk in trace norm. 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 $\rho_{A},\sigma_{A}\in\mathcal{S}_{\bullet}(A)$, we define the
_generalized fidelity_ ,

$\displaystyle F(\rho_{A},\sigma_{A})$
$\displaystyle:=\bigg{(}\operatorname{tr}\Big{\\{}\sqrt{\sqrt{\rho_{A}}\sigma_{A}\sqrt{\rho_{A}}}\Big{\\}}+\sqrt{1-\operatorname{tr}\\{\rho_{A}\\}}\sqrt{1-\operatorname{tr}\\{\sigma_{A}\\}}\bigg{)}^{2}\,,$
(2)

and the _purified distance_ ,
$P(\rho_{A},\sigma_{A}):=\sqrt{1-F(\rho_{A},\sigma_{A})}$.

The purified distance is a metric on sub-normalized states and satisfies [26,
Lemma 2]

$\displaystyle P(\rho_{A},\sigma_{A})\geq
P\big{(}\mathcal{F}(\rho_{A}),\mathcal{F}(\sigma_{A})\big{)}$ (3)

for every completely positive (CP) trace non-increasing map $\mathcal{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 [24,
Corollary 3.1] is that for any two states $\rho_{A},\sigma_{A}$ and any
extension $\rho_{AB}$ of $\rho_{A}$, there exists an extension $\sigma_{AB}$
with $P(\rho_{AB},\sigma_{AB})=P(\rho_{A},\sigma_{B})$. (This property is not
true in general for the trace distance.) Moreover, it is related to the trace
distance as follows [26, Lemma 6]:

$\displaystyle\big{\|}\rho_{A}-\sigma_{A}\big{\|}_{\operatorname{tr}}+\frac{1}{2}\big{|}\operatorname{tr}\\{\rho_{A}\\}-\operatorname{tr}\\{\sigma_{A}\\}\big{|}\leq
P(\rho_{A},\sigma_{A})\,.$ (4)

####  2.2 Classical registers and events

We model discrete random variables by finite-dimensional quantum systems,
called _registers_ , with a fixed orthonormal basis. For example, let
$X\in\mathcal{X}$ be a random variable with probability law $x\mapsto
P_{X}(x)$. Then we write the corresponding quantum state as

$\displaystyle\rho_{X}=\sum_{x\in\mathcal{X}}P_{X}(x)\left|x\middle\rangle\\!\middle\langle
x\right|_{X},$ (5)

where $\\{\left|x\right\rangle\\}_{x\in\mathcal{X}}$ is an orthonormal basis
of the space $X$. Conversely, we write $\Pr[X=x]_{\rho}=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:

$\displaystyle\rho_{XA}=\sum_{x\in\mathcal{X}}P_{X}(x)\left|x\middle\rangle\\!\middle\langle
x\right|_{X}\otimes\rho_{A|X=x}\,,$ (6)

where we use $\rho_{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]_{\rho}=\operatorname{tr}\\{\left|x\middle\rangle\\!\middle\langle
x\right|_{X}\rho_{XA}\\}=P_{X}(x)$. This convention is extended to arbitrary
events defined on a classical register $X$, i.e. if
$\Omega:\mathcal{X}\to\\{0,1\\}$ is an _event_ , we write

$\displaystyle\Pr[\Omega]_{\rho}=\sum_{x\in\mathcal{X}}P_{X}(x)\Omega(x)\quad\textrm{and}\quad\rho_{XA\land\Omega}=\sum_{x\in\mathcal{X}}P_{X}(x)\Omega(x)\left|x\middle\rangle\\!\middle\langle
x\right|_{X}\otimes\rho_{A|X=x}\,,$ (7)

a state that is generally sub-normalized. We will also write
${\rho}_{XA|\Omega}=\Pr[\Omega]_{\rho}^{-1}\rho_{XA|\Omega}$ for the
conditional state. For any event $\Omega:\mathcal{X}\to\\{0,1\\}$ we denote
its complement on $\mathcal{X}$ by $\lnot\Omega$.

####  2.3 Quantum channels and measurements

A _quantum channel_ $\mathcal{E}:A\to 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 $\operatorname{tr}$, and
the partial trace over system $A$, denoted $\operatorname{tr}_{A}$. We will
encounter the diamond distance between CPTP maps, which we here define as

$\displaystyle\|\mathcal{E}-\mathcal{F}\|_{\diamond}:=\sup_{\rho_{AC}\in\mathcal{S}(AC)}\|\mathcal{E}(\rho_{AC})-\mathcal{F}(\rho_{AC})\|_{\operatorname{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|\leq|A|$. The
diamond distance also inherits the physical interpretation of the trace
distance: for two quantum channels with diamond distance $\varepsilon$, 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 $\frac{1}{2}(1+\varepsilon)$.

A _generalized measurement_ on $A$ is a set of linear operators
$\\{M_{A}^{x}\\}_{x\in\mathcal{X}}$ such that

$\displaystyle\sum_{x\in\mathcal{X}}(M_{A}^{x})^{\dagger}(M_{A}^{x})=1_{A}\,,$
(9)

where $1_{A}$ denotes the identity operator on $A$. A measurement on $A$ can
be represented as a CPTP map $\mathcal{M}_{A\to X}$ 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 $\rho_{AB}$ yields

$\displaystyle\mathcal{M}_{A\to
X}:\rho_{AB}\mapsto\sigma_{XB}=\sum_{x\in\mathcal{X}}\left|x\middle\rangle\\!\middle\langle
x\right|_{X}\otimes\operatorname{tr}_{A}\Big{\\{}M_{A}^{x}\,\rho_{AB}\big{(}M_{A}^{x}\big{)}^{{\dagger}}\Big{\\}},$
(10)

where $\sigma_{XB}$ is now a (normalized) classical-quantum state. Finally,
let $f:\mathcal{X}\to\mathcal{Y}$ be a function acting on two sets
$\mathcal{X}$ and $\mathcal{Y}$. We denote by $\mathcal{E}_{f}:X\to XY$ the
corresponding cptp map

$\displaystyle\mathcal{E}_{f}[\cdot]=\sum_{x\in\mathcal{X}}\left|f(x)\right\rangle_{Y}\left|x\middle\rangle\\!\middle\langle
x\right|_{X}\cdot\left|x\middle\rangle\\!\middle\langle
x\right|_{X}\left\langle f(x)\right|_{Y}\,$ (11)

that acts on classical registers $X$ and $Y$ of a general cq state. Note that
we defined the map 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 least666Universal hashing is also used to
provide authentication of the classical channel, but we will not discuss this
issue here.) 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 (Universal2 Hashing).

Let $\mathcal{H}=\\{h\\}$ be a family of functions from $\mathcal{X}$ to
$\mathcal{Z}$. The family $\mathcal{H}$ is said to be _universal 2_ if
$\Pr\,[H(x)=H(x^{\prime})]=\frac{1}{|\mathcal{Z}|}$ for any pair of distinct
elements $x,x^{\prime}\in\mathcal{X}$, when $H$ is chosen uniformly at random
in $\mathcal{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 $|\mathcal{X}|$ and $|\mathcal{Z}|$ are powers of $2$. (See, e.g.,
[27, 28].)

####  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 interfering 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)_{\rho}:=-\sum_{x\in\mathcal{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 [24] for a comprehensive
introduction.

Min- and max-entropy are natural generalizations of conditional Rényi
entropies [29] to the quantum setting and were first proposed by Renner [10]
and König et al. [30]. 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
$\rho_{XB}\in\mathcal{S}(AB)$, we define

$\displaystyle p_{\rm guess}(X|B)_{\rho}=\sup_{\\{E_{B}^{x}\\}}\
\sum_{x\in\mathcal{X}}\Pr[X=x]_{\rho}\operatorname{tr}\Big{\\{}E_{B}^{x}\,\rho_{B|X=x}\big{(}E_{B}^{x}\big{)}^{\dagger}\Big{\\}},$
(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)_{\rho}:=-\log p_{\rm guess}(X|B)_{\rho}$. For later convenience
we introduce the measure more generally for any bipartite, potentially sub-
normalized, state:

######  Definition 3 (Min-entropy).

For any bipartite state $\rho_{AB}\in\mathcal{S}_{\bullet}(AB)$, we define

$\displaystyle H_{\min}(A|B)_{\rho}$
$\displaystyle:=\sup\big{\\{}\lambda\in\mathbb{R}:\exists\,\sigma_{B}\in\mathcal{S}(B)\textrm{
such that }\rho_{AB}\leq
2^{-\lambda}\mathrm{id}_{A}\otimes\sigma_{B},\big{\\}}\,.$ (13)

Showing equivalence between this definition and the special case of cq states
in (12) involves semidefinite-programming duality [30] 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 tripartite state $\rho_{AB}\in\mathcal{S}_{\bullet}(AB)$, we define

$\displaystyle H_{\max}(A|B)_{\rho}:=-H_{\min}(A|C)_{\rho}\,,$ (14)

where $\rho_{ABC}$ is any pure state with
$\operatorname{tr}_{C}\\{\rho_{ABC}\\}=\rho_{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:

$\displaystyle H_{\min}(X)_{\rho}\leq H(X)_{\rho}\leq
H_{\max}(X)_{\rho}\leq\log\big{|}\\{x\in X:\Pr[X=x]_{\rho}>0\\}\big{|},$ (15)

which is a consequence of the monotonicity of the Rényi entropies [29] 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 $\rho_{AB}$ in
terms of the purified distance introduced in the previous section.

######  Definition 5 (Smooth Entropies).

For $\rho_{AB}\in\mathcal{S}_{\bullet}(AB)$ and
$\varepsilon\in\Big{[}0,\sqrt{\operatorname{tr}(\rho_{AB})}\Big{)}$, we define

$\displaystyle
H_{\min}^{\varepsilon}(A|B)_{\rho}:=\sup_{\tilde{\rho}_{AB}\in\mathcal{S}_{\bullet}(AB),\atop
P(\tilde{\rho}_{AB},\rho_{AB})\leq\varepsilon}H_{\min}(A|B)_{\tilde{\rho}},\qquad
H_{\max}^{\varepsilon}(A|B)_{\rho}:=\inf_{\tilde{\rho}_{AB}\in\mathcal{S}_{\bullet}(AB),\atop
P(\tilde{\rho}_{AB},\rho_{AB})\leq\varepsilon}H_{\max}(A|B)_{\tilde{\rho}}\,.$
(16)

In the above definitions we can replace the supremum and infimum with a
maximum and minimum, respectively. 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 [26]. For any pure state
$\rho_{ABC}\in\mathcal{S}_{\bullet}(ABC)$, we have

$\displaystyle
H_{\min}^{\varepsilon}(A|B)_{\rho}=-H_{\max}^{\varepsilon}(A|C)_{\rho}\,.$
(17)

The smooth entropies also satisfy a data-processing inequality (DPI) [26,
Theorem 18]. For any cq state $\rho_{XB}$ and any completely positive trace-
preserving map $\mathcal{E}_{B\to C}$, we have

$\displaystyle H_{\min}^{\varepsilon}(X|B)_{\rho}\leq
H_{\min}^{\varepsilon}(X|C)_{\mathcal{E}(\rho)},\quad\textrm{and}\quad
H_{\max}^{\varepsilon}(X|B)_{\rho}\leq
H_{\max}^{\varepsilon}(X|C)_{\mathcal{E}(\rho)}\,.$ (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 [31, Lemma 11], which states that

$\displaystyle H_{\min}^{\varepsilon}(A|BX)_{\rho}\geq
H_{\min}^{\varepsilon}(A|B)_{\rho}-\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 $\rho_{AXBY}\in\mathcal{S}(ABXY)$ be
classical on $X$ and $Y$ and let
$\Omega:\mathcal{X}\times\mathcal{Y}\to\\{0,1\\}$ be an event. Then we denote
by $H(AX\land\Omega|BY)_{\rho}$ the conditional entropy evaluated for the
state $\rho_{AXBY\land\Omega}$. Similarly, $H(AX\land\Omega|B)_{\rho}$ denotes
the smooth conditional min-entropy evaluated for the marginal
$\rho_{AXB\land\Omega}=\operatorname{tr}_{Y}\\{\rho_{AXBY\land\Omega}\\}$.
These states are in general sub-normalized. The same notational convention is
also used for (smooth) min- and max-entropy.

##  Part I Entanglement-based protocol

$\varnothing$, $\checkmark$ | Symbols for abort and passing, respectively
---|---
$M_{A_{i}}^{\phi,x}$ |  Measurement operator acting on register $A_{i}$ with setting $\phi$ and outcome $x$
$c_{i}$ |  Parameter quantifying the quality of the measurement on register $A_{i}$
$\bar{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: $\mathrm{pe}=\\{k,\delta\\}$
$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
$\delta$ | Threshold for the parameter estimation test
test | Test function used in the parameter estimation step
ec |  Error correcting scheme: $\mathrm{ec}=\\{t,r,\mathrm{synd},\mathrm{corr},\mathcal{H}_{\mathrm{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
$\mathcal{H}_{\mathrm{ec}}$ |  Universal2 family of hash functions used in the error correcting scheme
pa |  Privacy amplification scheme: $\mathrm{pa}=\\{\ell,\mathcal{H}_{\mathrm{pa}}\\}$
$\ell$ | Length (in bits) of the final key
$\mathcal{H}_{\mathrm{pa}}$ |  Universal2 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
$\mathcal{M}_{A\to X|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^{\Phi}$ | Seed for the choice of the measurement bases in the idealized protocol
$S^{\Pi}$ |  Seed for the choice of the random subset $\pi\in\Pi_{m,k}$ used for parameter estimation
$S^{\Xi}$ | Seed for the choice of the measurement bases for the subsystems used for parameter estimation
$S^{\Theta}$ | Seed for the choice of the measurement bases for the subsystems used for key distillation
$S^{H_{\mathrm{ec}}}$ | Seed for the choice of the hash function used in the error correction test
$S^{H_{\mathrm{pa}}}$ | Seed for the choice of the hash function used in the privacy amplification step
$S$ |  Register corresponding to all the seeds, $S=(S^{\Phi},S^{\Pi},S^{\Xi},S^{\Theta},S^{H_{\mathrm{pe}}},S^{H_{\mathrm{ec}}},S^{H_{\mathrm{pa}}})$.
$F^{\mathrm{pe}}$ | Flag for the parameter estimation test
$F^{\mathrm{ec}}$ | Flag for the error correction test
$F$ |  Register corresponding to all the flags, $F=(F^{\mathrm{pe}},F^{\mathrm{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})$
$\rho$ | Quantum state before any measurement took place
$\tau$ | Quantum state after the registers used for parameter estimation have been measured
$\sigma$ | Quantum state once Alice and Bob’s quantum registers have been entirely measured
$\omega$ | Quantum state describing the final output of the protocol
Table 1: Overview of the nomenclature and notation used in Part I.

###  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.777Such strategies are advocated in the literature in order to
increase the secret key rate by minimizing the cost of sifting [32]. 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.888See, for instance, [33] for an analysis of
realistic quantum random number generators explaining how randomness
originating from quantum processes can be turned into ideal seeds.

##### 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 [28]. 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 [34, 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 extra-assumptions about the measurement devices to
prevent various types of side-channel attacks such as that of Lydersen et al.
[35]. 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\equiv
A_{[m]}=A_{1}A_{2}\ldots A_{m}$ and $B\equiv B_{[m]}=B_{1}B_{2}\ldots 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
$\phi\in\\{0,1\\}$ by a binary generalized measurement
$\\{M_{A_{i}}^{\phi,x}\\}_{x\in\\{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 $\phi\in\\{0,1\\}$ is a
binary generalized measurement $\\{M_{B_{i}}^{\phi,y}\\}_{y\in\\{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, $\bar{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

$\displaystyle
c\big{(}\\{M^{x}\\}_{x},\\{N^{y}\\}_{y}\big{)}:=\max_{x,y\in\\{0,1\\}}\left\|M^{x}\big{(}N^{y}\big{)}^{{\dagger}}\right\|_{\infty}^{2},\quad\textrm{and}\quad
c_{i}:=c\Big{(}\big{\\{}M_{A_{i}}^{0,x}\big{\\}}_{x},\big{\\{}M_{A_{i}}^{1,y}\big{\\}}_{y}\Big{)}\,.$
(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}=\frac{1}{2}$ for all $i\in[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

$\displaystyle\bar{c}(m,n):=\max_{\pi\in\Pi_{m,n}}\left(\prod_{i\in\pi}c_{i}\right)^{\frac{1}{n}}\leq\bar{c}\,.$
(21)

We always have $c_{i}\in[0,1]$ and the condition $\bar{c}<1$ is necessary to
ensure secrecy. As long as the commuting measurement assumption holds, the
parameter $\bar{c}$ can in principle be measured directly in an experiment —
even if the operators $\\{M_{A_{i}}^{\phi,x}\\}_{\phi,x}$ are unknown.999See,
e.g., [36, 37] for an estimation strategy based on Bell tests.

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

$(K_{A},K_{B},S,C,F)=$ qkd_ebm,pe,ec,pa $\\!\\!\big{(}\rho_{AB}\big{)}$:
Input: Alice and Bob are given a state $\rho_{AB}$, where $A\equiv A_{[m]}$
and $B\equiv B_{[m]}$ are comprised of $m$ quantum systems each.
Randomization: They agree on a random string $\Phi\in\\{0,1\\}^{m}$, a random
subset $\Pi\in\Pi_{m,k}$, and random hash functions
$H_{\mathrm{ec}}\in\mathcal{H}_{\textrm{ec}}$ as well as
$H_{\mathrm{pa}}\in\mathcal{H}_{\textrm{pa}}$. The corresponding uniformly
random seeds are denoted
$S=(S^{\Phi},S^{\Pi},S^{H_{\textrm{ec}}},S^{H_{\textrm{pa}}})$. Measurement:
Alice and Bob measure the $m$ quantum systems with the setting $\Phi$. 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 $\Pi$, whereas $X,Y$ of
length $n$ correspond to indices not in $\Pi$. Parameter Estimation: Alice
sends $V$ to Bob, the transcript is denoted $C^{V}$. Bob compares $V$ and $W$.
If the fraction of errors exceeds $\delta$, Bob sets the flag
$F^{\mathrm{pe}}=\varnothing$ and they abort. Otherwise he sets
$F^{\mathrm{pe}}=\checkmark$ and they proceed. Error Correction: Alice sends
the syndrome $Z=\mathrm{synd}(X)$ to Bob, with transcript $C^{Z}$. Bob
computes $\hat{X}=\mathrm{corr}(Y,Z)$. To verify the success of the error
correction step, Alice computes the hash $T=H_{\mathrm{ec}}(X)$ of length $t$
and sends it to Bob, with transcript $C^{T}$. Bob computes
$H_{\mathrm{ec}}(\hat{X})$. If it differs from $T$, he sets the flag
$F^{\mathrm{ec}}=\varnothing$ and they abort the protocol. Otherwise he sets
$F^{\mathrm{ec}}=\checkmark$ and they proceed. Privacy Amplification: They
compute keys $K_{A}=H_{\mathrm{pa}}(X)$ and $K_{B}=H_{\mathrm{pa}}(\hat{X})$
of length $\ell$. Output: The output of the protocol consists of the keys
$K_{A}$ and $K_{B}$, the seeds
$S=(S^{\Phi},S^{\Pi},S^{H_{\textrm{ec}}},S^{H_{\textrm{pa}}})$, the transcript
$C=(C^{V},C^{Z},C^{T})$ and the flags $F=(F^{\mathrm{pe}},F^{\mathrm{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.

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 $\rho_{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 $\rho_{AB}$ and to the transcript of the communication performed by
the protocol.

We consider protocols qkd_ebm,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 $\mathrm{pe}$,
$\mathrm{ec}$, and $\mathrm{pa}$.

  * •

The block length, $m\in\mathbb{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 $\mathrm{pe}=\\{k,\delta\\}$,
where $k\in\mathbb{N},k\leq m$ determines the number of quantum systems used
for parameter estimation and $\delta\in(0,\frac{1}{2})$ is the tolerated error
rate. Let us for later convenience also define $n:=m-k$ to denote the number
of quantum systems used for key generation.

  * •

The error correcting scheme is described by a quintuple
$\mathrm{ec}=\\{t,r,\mathrm{synd},\mathrm{corr},\mathcal{H}_{\mathrm{ec}}\\}$.
Here, $r\in\mathbb{N}$ is the length (in bits) of the error correction
syndrome. Moreover, $\mathrm{synd}$ and $\mathrm{corr}$ are functions of the
form $\mathrm{synd}:\\{0,1\\}^{n}\to\\{0,1\\}^{r}$ and
$\mathrm{corr}:\\{0,1\\}^{n}\times\\{0,1\\}^{r}\to\\{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\approx nh(\delta)$, where $h$ is the binary entropy function and $\delta$
is the number of errors to be corrected.101010For example, $\mathrm{synd}$
could be a linear code described by an $r\times n$ parity check matrix $H$
such that $\mathrm{synd}(x)=Hx$. Moreover, $\mathrm{corr}$ can be any decoder,
for example the (optimal) maximum likelihood decoder, but also a more
practical suboptimal iterative decoder.

Finally, $t\in\mathbb{N}$ is the length (in bits) of the hash used for
verification and
$\mathcal{H}_{\mathrm{ec}}:=\big{\\{}h_{\mathrm{ec}}:\\{0,1\\}^{n}\rightarrow\\{0,1\\}^{t}\big{\\}}$
is a universal2 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
$\mathrm{pa}=\\{\ell,\mathcal{H}_{\mathrm{pa}}\\}$, where $\ell\in\mathbb{N}$
with $\ell\leq n$ is the length (in bits) of the extracted key and
$\mathcal{H}_{\mathrm{pa}}:=\big{\\{}h_{\mathrm{pa}}:\\{0,1\\}^{n}\rightarrow\\{0,1\\}^{\ell}\big{\\}}$
is a universal2 family of hash functions.

Note that $\ell$, 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_ebm,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.

##### Input:

Alice and Bob are given a state $\rho_{AB}$, where $A=A_{[m]}=A_{1}A_{2}\ldots
A_{m}$ consists of $m$ quantum systems of arbitrary, finite dimension,
$B=B_{[m]}=B_{1}B_{2}\ldots B_{m}$ consists of $m$ quantum systems of
arbitrary, finite dimension. Note that apart from the above structure, the
state $\rho_{AB}$ is fully general. The situation is depicted in Figure 1.

Alicepublic domainBob$A$$B$ Figure 1: State of the classical and quantum
systems at the beginning of the protocol. The initial state is denoted
$\rho_{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 $\rho_{S}$ which is assumed to be
maximally mixed and independent of $\rho_{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^{\Phi}$ in the state

$\displaystyle\rho_{S^{\Phi}}=\sum_{\phi\in\\{0,1\\}^{m}}\frac{1}{2^{m}}\,\left|\phi\middle\rangle\\!\middle\langle\phi\right|_{S^{\Phi}},$
(22)

where $\\{|\phi\rangle\\}_{\phi\in\\{0,1\\}^{m}}$ is an orthonormal basis of
the space $S^{\Phi}$ and $\phi=\phi_{[m]}=(\phi_{1},\phi_{2},\ldots,\phi_{m})$
with $\phi_{i}\in\\{0,1\\}$. The total state at the beginning of the protocol
is thus of the form $\rho_{AB}\otimes\rho_{S^{\Phi}}$.

The seed for the choice of the random subset is denoted $S^{\Pi}$ and is
initially in the state

$\displaystyle\rho_{S^{\Pi}}=\sum_{\pi\in\Pi_{m,k}}\frac{1}{{m\choose
k}}\,\left|\pi\middle\rangle\\!\middle\langle\pi\right|_{S^{\Pi}}\,,$ (23)

where $\\{|\pi\rangle\\}_{\pi\in\Pi_{m,k}}$ is an orthonormal basis of the
space $S^{\Pi}$. For any $\pi\in\Pi_{m,k}$, we denote its $k$ elements by
$\pi_{i}$, for $i\in[k]$ and we denote by $\bar{\pi}\in[m]$ the complement of
$\pi$.

At this point we reorder the measurement settings in $S^{\Phi}$ into two
parts: the settings to be used for measuring quantum systems in $\pi$ will be
stored in a register $S^{\Xi}$ and the settings to be used for measuring the
remaining $n$ quantum systems in $\bar{\pi}$ will be stored in a register
$S^{\Theta}$. Formally, we consider the function

$\displaystyle\textrm{ro}:\\{0,1\\}^{m}\times\Pi_{m,k}\to\\{0,1\\}^{k}\times\\{0,1\\}^{n},\quad(\phi,\pi)\mapsto(\phi_{\pi},\phi_{\bar{\pi}})\,.$
(24)

Since $S^{\Phi}$ is uniformly random, the resulting state after applying this
function and discarding $S^{\Phi}$ is of the form

$\displaystyle\rho_{S^{\Pi}S^{\Xi}S^{\Theta}}=\operatorname{tr}_{S^{\Phi}}\big{\\{}\mathcal{E}_{\textrm{ro}}(\rho_{S^{\Phi}}\otimes\rho_{S^{\Pi}})\big{\\}}=\rho_{S^{\Pi}}\otimes\rho_{S^{\Xi}}\otimes\rho_{S^{\Theta}}\,,$
(25)

where the registers containing $S^{\Xi}$ and $S^{\Theta}$ are again uniformly
random:

$\displaystyle\rho_{S^{\Xi}}=\sum_{\xi\in\\{0,1\\}^{k}}\frac{1}{2^{k}}\,\left|\xi\middle\rangle\\!\middle\langle\xi\right|_{S^{\Xi}}\quad\textrm{and}\quad\rho_{S^{\Theta}}=\sum_{\theta\in\\{0,1\\}^{n}}\frac{1}{2^{n}}\,\left|\theta\middle\rangle\\!\middle\langle\theta\right|_{S^{\Theta}}$
(26)

for $\xi=\xi_{[k]}=(\xi_{1},\xi_{2},\ldots,\xi_{k})$ and
$\theta=\theta_{[n]}=(\theta_{1},\theta_{2},\ldots,\theta_{n})$ with
$\xi_{i},\theta_{i}\in\\{0,1\\}$.

The choice of the hash function in the family
$\mathcal{H}_{\mathrm{ec}}=\\{h_{\mathrm{ec}}:\\{0,1\\}^{n}\rightarrow\\{0,1\\}^{t}\\}$
and the choice of hash function in the family
$\mathcal{H}_{\mathrm{pa}}=\\{h_{\mathrm{pa}}:\\{0,1\\}^{n}\rightarrow\\{0,1\\}^{t}\\}$
are modeled via random seeds

$\displaystyle\rho_{S^{H_{\mathrm{ec}}}}=\sum_{h\in\mathcal{H}_{\mathrm{ec}}}\frac{1}{|\mathcal{H}_{\mathrm{ec}}|}|h\rangle\\!\langle
h|_{S^{H_{\mathrm{ec}}}}\qquad\textrm{and}\qquad\rho_{S^{H_{\mathrm{pa}}}}=\sum_{h\in\mathcal{H}_{\mathrm{pa}}}\frac{1}{|\mathcal{H}_{\mathrm{pa}}|}|h\rangle\\!\langle
h|_{S^{H_{\mathrm{pa}}}}.$ (27)

Alicepublic domainBob$A$$S$$B$$S$$S$ Figure 2: State of the classical and
quantum systems after randomization. The state of the total system is
$\rho_{AB}\otimes\rho_{S}$, where
$\rho_{S}=\rho_{S^{\Phi}}\otimes\rho_{S^{\Pi}}\otimes\rho_{S^{H_{\mathrm{ec}}}}\otimes\rho_{S^{H_{\mathrm{pa}}}}$.

##### Measurement:

We split the measurement process into two parts, measuring the systems in the
set $\pi$ and $\bar{\pi}$ 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 $\pi$, which are used for parameter estimation. For
any subset $\pi\in\Pi_{m,k}$, we define a completely positive trace-preserving
map $\mathcal{M}_{A\to V|S^{\Xi}}^{\pi}:A_{\pi}S^{\Xi}\to VA_{\pi}S^{\Xi}$
where $V=V_{[k]}=V_{1}\otimes V_{2}\otimes\ldots V_{k}$ models $k$ binary
classical registers storing the measurement outcomes. The map is given by

$\displaystyle\mathcal{M}_{A\to
V|S^{\Xi}}^{\pi}(\cdot)=\\!\\!\sum_{\xi\in\\{0,1\\}^{k}}\sum_{v\in\\{0,1\\}^{k}}\left|v\right\rangle_{V}\Big{(}M_{A_{\pi}}^{\xi,v}\otimes\left|\xi\middle\rangle\\!\middle\langle\xi\right|_{S^{\Xi}}\Big{)}\
\cdot\
\Big{(}M_{A_{\pi}}^{\xi,v}\otimes\left|\xi\middle\rangle\\!\middle\langle\xi\right|_{S^{\Xi}}\Big{)}^{\dagger}\left\langle
v\right|_{V},$ (28)

where
$M_{A_{\pi}}^{\xi,v}:=\bigotimes_{i\in[k]}M_{A_{\pi_{i}}}^{\xi_{i},v_{i}}$.
This map measures the $k$ subsystems determined by $\pi$ using the (random)
measurement settings stored in the register $S^{\Xi}$. The results are stored
in the classical register $V$, and the post-measurement state remains in the
systems $A_{\pi}$.

Similarly, we define $\mathcal{M}_{B\to W|S^{\Xi}}^{\pi}:B_{\pi}S^{\Xi}\to
WB_{\pi}S^{\Xi}$ as

$\displaystyle\mathcal{M}_{B\to
W|S^{\Xi}}^{\pi}(\cdot)=\\!\\!\sum_{\xi\in\\{0,1\\}^{k}}\sum_{w\in\\{0,1\\}^{k}}\left|w\right\rangle_{W}\Big{(}M_{B_{\pi}}^{\xi,w}\otimes\left|\xi\middle\rangle\\!\middle\langle\xi\right|_{S^{\Xi}}\Big{)}\
\cdot\
\Big{(}M_{B_{\pi}}^{\xi,w}\otimes\left|\xi\middle\rangle\\!\middle\langle\xi\right|_{S^{\Xi}}\Big{)}^{\dagger}\left\langle
w\right|_{W},$ (29)

where
$M_{B_{\pi}}^{\xi,w}:=\bigotimes_{i\in[k]}M_{B_{\pi_{i}}}^{\xi_{i},w_{i}}$.
The two maps $\mathcal{M}_{A\to V|S^{\Xi}}^{\pi}$ and $\mathcal{M}_{B\to
W|S^{\Xi}}^{\pi}$ commute since they act on different systems and we write
their concatenation as $\mathcal{M}_{A\to
V|S^{\Xi}}^{\pi}\circ\mathcal{M}_{B\to W|S^{\Xi}}^{\pi}=\mathcal{M}_{B\to
W|S^{\Xi}}^{\pi}\circ\mathcal{M}_{A\to V|S^{\Xi}}^{\pi}$.

So far we have considered $\pi$ to be fixed. The full measurement for
parameter estimation instead consults the register $S^{\Pi}$ and is modeled as
a map $\mathcal{M}_{AB\to VW|S^{\Pi}S^{\Xi}}:ABS^{\Pi}S^{\Xi}\to
ABVWS^{\Pi}S^{\Xi}$ given by

$\displaystyle\mathcal{M}_{AB\to
VW|S^{\Pi}S^{\Xi}}(\cdot)=\sum_{\pi\in\Pi_{m,k}}\,\mathcal{M}_{A\to
V|S^{\Xi}}^{\pi}\circ\mathcal{M}_{B\to
W|S^{\Xi}}^{\pi}\big{(}\left|\pi\middle\rangle\\!\middle\langle\pi\right|_{S^{\Pi}}\
\cdot\ \left|\pi\middle\rangle\\!\middle\langle\pi\right|_{S^{\Pi}}\big{)}.$
(30)

The state of the total system after the measurement required for parameter
estimation is thus given by

$\displaystyle\tau_{ABVWS^{\Pi}S^{\Xi}S^{\Theta}}$
$\displaystyle=\mathcal{M}_{AB\to
VW|S^{\Pi}S^{\Xi}}(\rho_{ABS^{\Pi}S^{\Xi}S^{\Theta}})$ (31)
$\displaystyle=\sum_{\pi\in\Pi_{m,k}}\sum_{\xi\in\\{0,1\\}^{k}}\sum_{v,w\in\\{0,1\\}^{k}}\frac{1}{2^{k}{m\choose
k}}\left|\pi,\xi\middle\rangle\\!\middle\langle\pi,\xi\right|_{S^{\Pi}S^{\Xi}}\otimes\rho_{S^{\Theta}}\otimes\leavevmode\nobreak\
$ $\displaystyle\qquad\qquad\qquad\dots\
\left|v,w\middle\rangle\\!\middle\langle
v,w\right|_{VW}\otimes\big{(}M_{A_{\pi}}^{\xi,v}\otimes
M_{B_{\pi}}^{\xi,w}\big{)}\rho_{AB}\big{(}M_{A_{\pi}}^{\xi,v}\otimes
M_{B_{\pi}}^{\xi,w}\big{)}^{\dagger}\,.$ (32)

The second measurement concerns the quantum systems used for extracting the
secret key. The corresponding measurement maps are defined analogously to the
measurements maps above, but now act on the systems determined by $\bar{\pi}$,
the complement of $\pi$ in $[m]$. We define

$\displaystyle\mathcal{M}_{A\to X|S^{\Pi}S^{\Theta}}(\cdot)$
$\displaystyle=\sum_{\pi\in\Pi_{m,k}}\sum_{\theta,x\in\\{0,1\\}^{n}}\left|x\right\rangle_{X}\big{(}M_{A_{\bar{\pi}}}^{\theta,x}\otimes\left|\pi,\theta\middle\rangle\\!\middle\langle\pi,\theta\right|_{S^{\Pi}S^{\Theta}}\big{)}\
\cdot\
\big{(}M_{A_{\bar{\pi}}}^{\theta,x}\otimes\left|\pi,\theta\middle\rangle\\!\middle\langle\pi,\theta\right|_{S^{\Pi}S^{\Theta}}\big{)}^{\dagger}\left\langle
x\right|_{X},$ (33) $\displaystyle\mathcal{M}_{B\to
Y|S^{\Pi}S^{\Theta}}(\cdot)$
$\displaystyle=\sum_{\pi\in\Pi_{m,k}}\sum_{\theta,y\in\\{0,1\\}^{n}}\left|y\right\rangle_{Y}\big{(}M_{B_{\bar{\pi}}}^{\theta,y}\otimes\left|\pi,\theta\middle\rangle\\!\middle\langle\pi,\theta\right|_{S^{\Pi}S^{\Theta}}\big{)}\
\cdot\
\big{(}M_{B_{\bar{\pi}}}^{\theta,y}\otimes\left|\pi,\theta\middle\rangle\\!\middle\langle\pi,\theta\right|_{S^{\Pi}S^{\Theta}}\big{)}^{\dagger}\left\langle
y\right|_{Y}$ (34)

as well as $\mathcal{M}_{AB\to XY|S^{\Pi}S^{\Theta}}=\mathcal{M}_{A\to
X|S^{\Pi}S^{\Theta}}\circ\mathcal{M}_{B\to Y|S^{\Pi}S^{\Theta}}$. It is
evident that all measurements $\mathcal{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 $\mathcal{M}_{AB\to
VWXY|S^{\Pi}S^{\Xi}S^{\Theta}}:=\mathcal{M}_{AB\to
VW|S^{\Pi}S^{\Xi}}\circ\mathcal{M}_{AB\to XY|S^{\Pi}S^{\Theta}}$.

Of particular interest is the state of the system after measurement and after
we discard the quantum systems. This is given by a classical state
$\sigma_{VWXYS^{\Pi}S^{\Xi}S^{\Theta}}$. This state is of the form

$\displaystyle\sigma_{VWXYS^{\Pi}S^{\Xi}S^{\Theta}}$ (35)
$\displaystyle\quad=\operatorname{tr}_{AB}\big{(}\mathcal{M}_{AB\to
VWXY|S^{\Pi}S^{\Xi}S^{\Theta}}(\rho_{ABS^{\Pi}S^{\Xi}S^{\Theta}})\big{)}$ (36)
$\displaystyle\quad=\operatorname{tr}_{AB}\big{(}\mathcal{M}_{AB\to
XY|S^{\Pi}S^{\Theta}}(\tau_{ABVWS^{\Pi}S^{\Xi}S^{\Theta}})\big{)}$ (37)
$\displaystyle\quad=\sum_{\pi\in\Pi_{m,k}}\sum_{\xi\in\\{0,1\\}^{k}\atop\theta\in\\{0,1\\}^{n}}\sum_{v,w\in\\{0,1\\}^{k}\atop
x,y\in\\{0,1\\}^{n}}\frac{1}{2^{m}{m\choose
k}}\left|\pi,\xi,\theta\middle\rangle\\!\middle\langle\pi,\xi,\theta\right|_{S^{\Pi}S^{\Xi}S^{\Theta}}\otimes\left|v,w,x,y\middle\rangle\\!\middle\langle
v,w,x,y\right|_{VWXY}\otimes\leavevmode\nobreak\ $
$\displaystyle\qquad\qquad\dots\
\operatorname{tr}_{AB}\Big{\\{}\big{(}\widetilde{M}_{A_{\pi}}^{\xi,v}\otimes\widetilde{M}_{A_{\bar{\pi}}}^{\theta,x}\otimes\widetilde{M}_{B_{\pi}}^{\xi,w}\otimes\widetilde{M}_{B_{\bar{\pi}}}^{\theta,y}\big{)}\rho_{AB}\Big{\\}}\,,$
(38)

where we write
$\widetilde{M}_{A_{\pi}}^{\xi,v}=\big{(}M_{A_{\pi}}^{\xi,v}\big{)}^{\dagger}M_{A_{\pi}}^{\xi,v}$
and analogously introduce $\widetilde{M}_{A_{\bar{\pi}}}^{\theta,x}$,
$\widetilde{M}_{B_{\pi}}^{\xi,w}$ and
$\widetilde{M}_{B_{\bar{\pi}}}^{\theta,y}$.

The situation after the complete measurement is depicted in Figure 3.

Alicepublic domainBob$S$$A$$V$$X$$S$$B$$W$$Y$$\mathcal{M}$$\mathcal{M}$$S$
Figure 3: State of the classical and quantum systems during and after
measurement. The measurement can be summarized as a CPTP map
$\rho_{AB}\otimes\rho_{S^{\Phi}}\otimes\rho_{S^{\Pi}}\mapsto\sigma_{VWXYABS^{\Phi}S^{\Pi}}$.

##### Parameter estimation:

We model parameter estimation by a test function acting on the registers $V$
and $W$ and creating a binary flag $F^{\textrm{pe}}$ as follows:

$\displaystyle\mathrm{test}:\\{0,1\\}^{k}\times\\{0,1\\}^{k}\to\\{\varnothing,\checkmark\\},\quad\mathrm{pe}(v,w)=\begin{cases}\varnothing&\textrm{if}\
\sum_{i\in[k]}1\\{v_{i}\neq w_{i}\\}\geq k\delta,\\\
\checkmark&\textrm{otherwise}.\end{cases}$ (39)

This test can be applied to the states $\tau_{ABVWS^{\Pi}S^{\Xi}S^{\Theta}}$
or $\sigma_{VWXYS^{\Pi}S^{\Xi}S^{\Theta}}$ defined previously. This requires
Alice to communicate $V$ to Bob on the authenticated classical channel in
order to evaluate the value of $\mathrm{pe}(v,w)$ and the transcript of this
communication is stored in the variable $C^{V}=V$.

We are specifically interested in the state
$\tau_{ABVWS^{\Pi}S^{\Xi}S^{\Theta}F^{\textrm{pe}}}=\mathcal{E}_{\textrm{pe}}\big{(}\tau_{ABVWS^{\Pi}S^{\Xi}S^{\Theta}}\big{)}$
and the corresponding state conditioned on the outcome
$F^{\textrm{pe}}=\checkmark$, given by

$\displaystyle\tau_{ABVWS^{\Pi}S^{\Xi}S^{\Theta}|F^{\textrm{pe}}=\checkmark}=\frac{1}{\Pr[F^{\textrm{pe}}=\checkmark]_{\tau}}\sum_{\pi\in\Pi_{m,k}}\sum_{\xi\in\\{0,1\\}^{k}}\sum_{v,w\in\\{0,1\\}^{k}\atop\sum_{i=1}^{k}1\\{v_{i}\neq
w_{i}\\}<k\delta}\frac{1}{2^{k}{m\choose
k}}\left|\pi,\xi\middle\rangle\\!\middle\langle\pi,\xi\right|_{S^{\Pi}S^{\Xi}}\otimes\leavevmode\nobreak\
$ $\displaystyle\qquad\qquad\qquad\dots\
\rho_{S^{\Theta}}\otimes\left|v,w\middle\rangle\\!\middle\langle
v,w\right|_{VW}\otimes\big{(}M_{A_{\pi}}^{\xi,v}\otimes
M_{B_{\pi}}^{\xi,w}\big{)}\rho_{AB}\big{(}M_{A_{\pi}}^{\xi,v}\otimes
M_{B_{\pi}}^{\xi,w}\big{)}^{\dagger}\,.$ (40)

We will see that this state is crucial for the security analysis in the next
section. Finally, we note that $\mathcal{M}_{XY}$ and
$\mathcal{E}_{\textrm{pe}}$ commute, and thus in particular we find that

$\displaystyle\operatorname{tr}_{AB}\big{\\{}\mathcal{M}_{AB\to
XY|S^{\Pi}S^{\Theta}}(\tau_{ABVWS^{\Pi}S^{\Xi}S^{\Theta}|F^{\textrm{pe}}=\checkmark})\big{\\}}$
$\displaystyle=\sigma_{VWXYS^{\Pi}S^{\Xi}S^{\Theta}|F^{\textrm{pe}}=\checkmark},\qquad\textrm{where}$
(41) $\displaystyle\sigma_{VWXYS^{\Pi}S^{\Xi}S^{\Theta}F^{\textrm{pe}}}$
$\displaystyle=\mathcal{E}_{\textrm{pe}}(\sigma_{VWXYS^{\Pi}S^{\Xi}S^{\Theta}})\,.$
(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.

Alicepublic domainBob$X$$S$$V$$Y$$W$$S$$V$$F^{\mathrm{pe}}$$S$$C^{V}$avg
Figure 4: State of the classical and quantum systems during and after
parameter estimation. Parameter estimation is summarized as a CPTP map
$\sigma_{VW}\mapsto\sigma_{C^{V}F^{\mathrm{pe}}}$.

##### 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 $\mathrm{synd}$ and $\mathrm{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=\mathrm{synd}(X)$ and sends it to Bob over
the public channel. Bob then computes an estimate
$\hat{X}=\mathrm{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
$\hat{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 $\hat{X}$. This test is summarized as a classical map $\mathrm{ec}$ acting
on registers $X$, $\hat{X}$ and $S^{H_{\mathrm{ec}}}$ creating a transcript of
the hash value $C^{T}$ and a binary flag $F^{\mathrm{ec}}$ as follows:

$\displaystyle\mathrm{ec}:\\{0,1\\}^{n}\times\\{0,1\\}^{n}\times\mathcal{H}_{\mathrm{ec}}\to\\{0,1\\}^{t}\times\\{\varnothing,\checkmark\\},\quad(x,\hat{x})\mapsto\begin{cases}(h_{\mathrm{ec}}(x),\varnothing)&\textrm{if}\
h_{\mathrm{ec}}(x)\neq h_{\mathrm{ec}}(\hat{x}),\\\
(h_{\mathrm{ec}}(x),\checkmark)&\textrm{otherwise}.\end{cases}$ (43)

These classical functions are modeled using CPTP maps
$\mathcal{E}_{\mathrm{synd}}$, $\mathcal{E}_{\mathrm{corr}}$ and
$\mathcal{E}_{\mathrm{ec}}$, respectively. Applying them to the state
$\sigma_{XYC^{V}S^{\Pi}S^{\Xi}S^{\Theta}F^{\textrm{pe}}}$ yields

$\displaystyle\sigma_{X\hat{X}C^{V}C^{Z}C^{T}S^{\Pi}S^{\Xi}S^{\Theta}S^{H_{\mathrm{ec}}}F^{\textrm{pe}}F^{\textrm{ec}}}=\operatorname{tr}_{Y}\Big{\\{}\mathcal{E}_{\mathrm{ec}}\circ\mathcal{E}_{\mathrm{corr}}\circ\mathcal{E}_{\mathrm{synd}}\left(\sigma_{XYC^{V}S^{\Pi}S^{\Xi}S^{\Theta}F^{\textrm{pe}}}\otimes\rho_{S^{H_{\mathrm{ec}}}}\right)\Big{\\}},$
(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.

Alicepublic
domainBob$X$$Z$synd$S$$T$hash$Y$$Z$$\hat{X}$corr$T$$S$$\hat{T}$$F^{\mathrm{ec}}$$F^{\mathrm{pe}}$hash$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
$\sigma_{XY}\otimes\rho_{S^{H_{\mathrm{ec}}}}\mapsto\sigma_{X\hat{X}C^{Z}F^{\mathrm{ec}}}$.

##### Privacy amplification:

Alice and Bob use the seed $H_{\mathrm{pa}}$ to choose a hash function, which
they then both apply on their raw key to compute $K_{A}=H_{\mathrm{pa}}(X)$
and $K_{B}=H_{\mathrm{pa}}(\hat{X})$, their respective keys. Formally, the
privacy amplification map is defined as:

$\mathrm{pa}:\\{0,1\\}^{n}\times\\{0,1\\}^{n}\times\mathcal{H}_{\mathrm{pa}}\to\\{0,1\\}^{\ell}\times\\{0,1\\}^{\ell},\quad(x,\hat{x},h_{\mathrm{pa}})\mapsto(h_{\mathrm{pa}}(x),h_{\mathrm{pa}}(\hat{x})).$
(45)

Denoting by $K_{A}$ and $K_{B}$ the respective key spaces of Alice and Bob,
the final quantum state is

$\displaystyle\omega_{K_{A}K_{B}C{S}F}=\operatorname{tr}_{X\hat{X}}\big{\\{}\mathcal{E}_{\mathrm{pa}}(\sigma_{X\hat{X}C{S}F}\otimes\rho_{S^{H_{\mathrm{pa}}}})\big{\\}}.$
(46)

Finally, Bob reveals the status of his flag registers. This final step is
depicted in Figure 6.

Alicepublic domainBob$S$$X$$K_{A}$$S$$\hat{X}$$K_{B}$$F$hashhash$S$$C$$F$
Figure 6: State of the classical and quantum systems during and after privacy
amplification. Privacy amplification is a CPTP map
$\sigma_{X\hat{X}}\otimes\rho_{S^{H_{\mathrm{pa}}}}\mapsto\omega_{K_{A}K_{B}}$.
The complete final state is denoted by $\omega_{K_{A}K_{B}SCF}$.

###  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 [34]. For our purposes here
(consistent with [10] and [34]), we say that our protocol is $\Delta$-secure
if is $\Delta$-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_idealm,pe,ec,pa designed in such a way
that it is close to the original qkd_ebm,pe,ec,pa protocol.

$(K_{A},K_{B},S,C,F)=$ qkd_idealm,pe,ec,pa $\\!\\!\big{(}\rho_{AB}\big{)}$:
Run protocol: Set
$(K_{A},K_{B},S,C,F)=\mbox{{{qkd\\_eb${}_{m,\mathrm{pe},\mathrm{ec},\mathrm{pa}}$}}}(\rho_{AB})$.
Output: If $F^{\mathrm{pe}}=F^{\mathrm{ec}}=\checkmark$, then replace $K_{A}$
and $K_{B}$ by an independent and uniformly distributed random string $K$ of
length $\ell$, i.e. set $K_{A}=K_{B}=K$.

Table 3: An ideal QKD protocol that is close to qkd_ebm,pe,ec,pa.

In order to show that the protocol is secure, it thus suffices to show that

$\displaystyle\Delta_{m,\mathrm{pe},\mathrm{ec},\mathrm{pa}}$
$\displaystyle:=\big{\|}\mbox{{{qkd\\_eb${}_{m,\mathrm{pe},\mathrm{ec},\mathrm{pa}}$}}}{}-\mbox{{{qkd\\_ideal${}_{m,\mathrm{pe},\mathrm{ec},\mathrm{pa}}$}}}{}\big{\|}_{\diamond}$
(47)
$\displaystyle\;=\sup_{\rho_{ABE}\in\mathcal{S}(ABE)}\big{\|}\mbox{{{qkd\\_eb${}_{m,\mathrm{pe},\mathrm{ec},\mathrm{pa}}$}}}(\rho_{ABE})-\mbox{{{qkd\\_ideal${}_{m,\mathrm{pe},\mathrm{ec},\mathrm{pa}}$}}}(\rho_{ABE})\big{\|}_{\mathrm{tr}}$
(48)

is very small for certain choices of parameters $k,n,\delta,\mathrm{ec}$ and
$\mathrm{pa}$. In the latter expression $\rho_{ABE}$ is an arbitrary extension
of $\rho_{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 $\rho_{ABE}$.

Let us now fix $\rho_{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

$\displaystyle\big{\|}\mbox{{{qkd\\_eb${}_{m,\mathrm{pe},\mathrm{ec},\mathrm{pa}}$}}}(\rho_{ABE})-\mbox{{{qkd\\_ideal${}_{m,\mathrm{pe},\mathrm{ec},\mathrm{pa}}$}}}(\rho_{ABE})\big{\|}_{\operatorname{tr}}$
$\displaystyle\qquad=\Pr\big{[}F=\,(\checkmark,\checkmark)\big{]}_{\omega}\cdot\big{\|}\omega_{K_{A}K_{B}SCE|F=\,(\checkmark,\checkmark)}-\chi_{K_{A}K_{B}}\otimes\omega_{SCE|F=\,(\checkmark,\checkmark)}\big{\|}_{\operatorname{tr}}$
(49) $\displaystyle\qquad=\big{\|}\tilde{\omega}_{K_{A}K_{B}SCFE\land
F=\,(\checkmark,\checkmark)}-\chi_{K_{A}K_{B}}\otimes\tilde{\omega}_{SCFE\land
F=\,(\checkmark,\checkmark)}\big{\|}_{\operatorname{tr}}$ (50)

where we use
$\omega_{K_{A}K_{B}SCFE}=\texttt{qkd\\_eb}_{k,n,\delta,\mathrm{ec},\mathrm{pa}}(\rho_{ABE})$
and define a perfect key $\chi_{K_{A}K_{B}}$ as follows:

$\displaystyle\chi_{K_{A}K_{B}}:=\frac{1}{2^{\ell}}\sum_{k\in\\{0,1\\}^{\ell}}\left|k\middle\rangle\\!\middle\langle
k\right|_{K_{A}}\otimes\left|k\middle\rangle\\!\middle\langle
k\right|_{K_{B}}\,.$ (51)

Recall that ${\omega}$ in (50) corresponds to a subnormalized state with trace
equal to $\Pr[F=\,(\checkmark,\checkmark)]_{\omega}$.

Our goal in the following is to bound (50) or (49) uniformly in $\rho_{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 [34,
Theorem 4.1], but we provide a proof here for completeness.

######  Lemma 1.

Let $\varepsilon_{\textrm{ec}},\varepsilon_{\textrm{pa}}\in[0,1)$ be two
constants. If, for every state $\rho_{ABE}\in\mathcal{S}(ABE)$ and
$\omega_{K_{A}K_{B}SCFE}=\mbox{{{qkd\\_eb${}_{m,\mathrm{pe},\mathrm{ec},\mathrm{pa}}$}}}(\rho_{ABE})$,
we have

$\displaystyle\Pr[K_{A}\neq K_{B}\land
F^{\textrm{pe}}=F^{\textrm{ec}}=\checkmark]_{\omega}$
$\displaystyle\leq\varepsilon_{\textrm{ec}}\qquad\textrm{and}$ (52)
$\displaystyle\big{\|}\omega_{K_{A}SCFE\land
F=\,(\checkmark,\checkmark)}-\chi_{K_{A}}\otimes\omega_{SCFE\land
F=\,(\checkmark,\checkmark)}\big{\|}_{\operatorname{tr}}$
$\displaystyle\leq\varepsilon_{\textrm{pa}}\,.$ (53)

Then,
$\Delta_{m,\mathrm{pe},\mathrm{ec},\mathrm{pa}}\leq\varepsilon_{\mathrm{ec}}+\varepsilon_{\textrm{pa}}$.

###### Proof.

Let us introduce an auxiliary state $\eta_{K_{A}K_{B}SCFE}$ that is equal to
$\omega_{K_{A}K_{B}SCFE}$ except that we set $K_{B}=K_{A}$. Then, applying the
triangle inequality to the trace distance in (49) and simplifying the
resulting terms, we find

$\displaystyle\big{\|}\omega_{K_{A}K_{B}SCE|F=\,(\checkmark,\checkmark)}-\chi_{K_{A}K_{B}}\otimes\omega_{SCE|F=\,(\checkmark,\checkmark)}\big{\|}_{\operatorname{tr}}$
$\displaystyle\qquad\leq\big{\|}\omega_{K_{A}K_{B}SCE|F=\,(\checkmark,\checkmark)}-\eta_{K_{A}K_{B}SCE|F=\,(\checkmark,\checkmark)}\big{\|}_{\operatorname{tr}}$
$\displaystyle\qquad\qquad\qquad+\big{\|}\eta_{K_{A}K_{B}SCE|F=\,(\checkmark,\checkmark)}-\chi_{K_{A}K_{B}}\otimes\omega_{SCE|F=\,(\checkmark,\checkmark)}\big{\|}_{\operatorname{tr}}$
(54) $\displaystyle\qquad=\Pr\big{[}K_{A}\neq
K_{B}|F=\,(\checkmark,\checkmark)\big{]}_{\omega}+\big{\|}\eta_{K_{A}SCE|F=\,(\checkmark,\checkmark)}-\chi_{K_{A}}\otimes\omega_{SCE|F=\,(\checkmark,\checkmark)}\big{\|}_{\operatorname{tr}}\,.$
(55)

Multiplying this with $\Pr[F=\,(\checkmark,\checkmark)]_{\omega}$ as in (49)
yields the desired implication. ∎

The first condition of the above Lemma 1 ensures that the protocol is
_$\varepsilon_{\textrm{ec}}$ -correct_, and the second condition ensures that
the protocol _$\varepsilon_{\textrm{pa}}$ -secret_. If both are satisfied, we
say that the protocol is
_$(\varepsilon_{\mathrm{ec}}+\varepsilon_{\textrm{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_ebm,pe,ec,pa in Section 3 with
$\mathrm{ec}=\\{t,\ldots\\}$. Then for every state
$\rho_{AB}\in\mathcal{S}(AB)$ and
$\omega_{K_{A}K_{B}SCF}=\mbox{{{qkd\\_eb${}_{m,\mathrm{pe},\mathrm{ec},\mathrm{pa}}$}}}(\rho_{AB})$
we have

$\displaystyle\Pr[K_{A}\neq K_{B}\land F=\,(\checkmark,\checkmark)]_{\omega}$
$\displaystyle\leq\varepsilon_{\rm 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 $\nu$, which ought to be optimized numerically. The
proof is given in Sections 6.2–6.4.

######  Theorem 3.

Consider the protocol qkd_ebm,pe,ec,pa in Section 3 with
$\mathrm{pe}=\\{k,\delta\\}$, $\mathrm{ec}=\\{t,r,\ldots\\}$ and
$\mathrm{pa}=\\{\ell,\ldots\\}$. Then, for every state $\rho_{ABE}$ and
_$\omega_{K_{A}K_{B}SCFE}=\texttt{qkd\\_eb}_{k,n,\delta,\mathrm{ec},\mathrm{pa}}(\rho_{ABE})$_
, we have

$\displaystyle\big{\|}\omega_{K_{A}SCFE\land
F=\,(\checkmark,\checkmark)}-\chi_{K_{A}}\otimes\omega_{SCFE\land
F=\,(\checkmark,\checkmark)}\big{\|}_{\operatorname{tr}}\leq\inf_{\nu\in(0,\frac{1}{2}-\delta)}\varepsilon_{\textrm{pe}}(\nu)+\varepsilon_{\textrm{pa}}(\nu)\,,$
(57)

where the error functions are given as

$\displaystyle\varepsilon_{\textrm{pa}}(\nu):=\frac{1}{2}\sqrt{2^{-(m-k)\big{(}\log\frac{1}{\bar{c}}-h(\delta+\nu)\big{)}+r+t+\ell}}\quad\textrm{and}\quad\varepsilon_{\textrm{pe}}(\nu):=2\,e^{-\frac{(m-k)k^{2}\nu^{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, $\varepsilon_{\textrm{pe}}$, $\varepsilon_{\rm ec}$, and
$\varepsilon_{\textrm{pa}}$. Let us take a close look at these errors for the
case of large $m$. First, we note that $\varepsilon_{\rm ec}$ vanishes
asymptotically when we choose $t=\log(m)$, or any other slowly growing
function of $m$. To make sure that $\varepsilon_{\textrm{pe}}$ vanishes we
choose $k=\sqrt{m}$ and $\nu=\log(m)^{-1}$, for example. For a robust
operation at noise level $\delta$ it is necessary (and in theory sufficient)
that the error correction leakage satisfies $r\approx(m-k)h(\delta)$. Since
$h(\delta+\nu)\approx h(\delta)$ by continuity, we find that
$\varepsilon_{\textrm{pa}}$ vanishes as long as

$\displaystyle(m-k)\left(\log\frac{1}{\bar{c}}-2h(\delta)\right)-\ell-\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 [38], with
$\ell/m=\log\frac{1}{\bar{c}}-2h(\delta)$.

[width=0.85]keylength.pdf

Figure 7: This plot shows the maximal secret key rate $\ell/m$ as a function
of $m$ for different error thresholds $\delta\in\\{0.01,0.025,0.05,0.075\\}$,
optimized over all protocols. The protocols are required to be
$\varepsilon$-secure with $\varepsilon=10^{-10}$ and the device parameter is
assumed to be $\bar{c}=0.5$. The error correction leakage is approximated to
be $r=1.1(m-k)h(\delta)$, see for instance [39]. (A more detailed
approximation that includes finite-size effects was recently given in [40].)
All remaining parameters, i.e. $\nu,k$ and $t$, are optimized numerically to
maximize $\ell$ (code available online). The dotted horizontal lines show the
corresponding asymptotic limit of the key rate for each value of $\delta$,
given as $1-2h(\delta)$. The markers indicate the points at which the key rate
matches $50\%$ of the asymptotic limit.

###  6 Security proof

The purpose of this section is to prove Theorems 2 and 3.

####  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:

$\displaystyle\Pr[K_{A}\neq K_{B}\land
F^{\textrm{pe}}=F^{\textrm{ec}}=\,\checkmark]_{\omega}$
$\displaystyle\leq\Pr[K_{A}\neq K_{B}\land
F^{\textrm{ec}}=\,\checkmark]_{\omega}$ (60)
$\displaystyle=\Pr[H_{\mathrm{pa}}(X)\neq H_{\mathrm{pa}}(X^{\prime})\land
H_{\mathrm{ec}}(X)=H_{\mathrm{ec}}(X^{\prime})]_{\omega}$ (61)
$\displaystyle\leq\Pr[X\neq X^{\prime}\land
H_{\mathrm{ec}}(X)=H_{\mathrm{ec}}(X^{\prime})]_{\sigma}$ (62)
$\displaystyle=\Pr[X\neq
X^{\prime}]_{\sigma}\Pr[H_{\mathrm{ec}}(X)=H_{\mathrm{ec}}(X^{\prime})\>|\>X\neq
X^{\prime}]_{\sigma}$ (63)
$\displaystyle\leq\Pr[H_{\mathrm{ec}}(X)=H_{\mathrm{ec}}(X^{\prime})\>|\>X\neq
X^{\prime}]_{\sigma}$ (64)
$\displaystyle\leq|\mathcal{H}_{\mathrm{ec}}|^{-1}=2^{-t}.$ (65)

The first inequality follows since we ignore the status of the flag
$F^{\mathrm{pe}}$. The second inequality is a consequence of the fact
$X=X^{\prime}$ implies $H_{\mathrm{pa}}(X)=H_{\mathrm{pa}}(X^{\prime})$. The
third inequality follows since $\Pr[X\neq X^{\prime}]_{\sigma}\leq 1$ and the
last one by definition of universal2 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 [41, Corollary 7.4].

######  Proposition 4.

Let $\tau_{APRS}\in\mathcal{S}_{\bullet}(APRS)$ be an arbitrary state with $P$
a classical register, and set $t:=\operatorname{tr}\\{\tau_{APRS}\\}$.
Furthermore, let $\varepsilon\in[0,\sqrt{t})$ and let $q$ be a bijective
function on $P$ that is a symmetry of $\tau_{ABCP}$ in the sense that
$\tau_{ARS,P=p}=\tau_{ARS,P=q(p)}$ for all $p\in P$. Then, we have

$\displaystyle
H_{\min}^{\varepsilon}(X|PR)_{\sigma}+H_{\max}^{\varepsilon}(X|PS)_{\sigma}\geq\log\frac{1}{c_{q}},\qquad\textrm{where}$
(66)

where $c_{q}=\max_{p\in P}\max_{x,z\in
X}\big{\|}{F_{A}^{q(p),x}}\big{(}{F_{A}^{p,z}}\big{)}^{{\dagger}}\big{\|}_{\infty}^{2}$.
Here, $\sigma_{XPRS}=\mathcal{M}_{A\to X|P}(\tau_{APRS})$ for the map

$\displaystyle\mathcal{M}_{A\to X|P}\big{[}\cdot\big{]}$
$\displaystyle=\operatorname{tr}_{A}\Bigg{(}\sum_{p\in P}\sum_{x\in
X}\left|x\right\rangle_{X}\Big{(}\left|p\middle\rangle\\!\middle\langle
p\right|_{P}\otimes F_{A}^{p,x}\Big{)}\ \cdot\
\Big{(}\left|p\middle\rangle\\!\middle\langle p\right|_{P}\otimes
F_{A}^{p,x}\Big{)}^{\dagger}\left\langle x\right|_{X}\Bigg{)}\,.$ (67)

and any set (indexed by $p\in P$) of generalized measurements
$\\{F_{A}^{p,x}\\}_{x\in X}$.

A variant of this uncertainty relation was first shown in [41], 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_ebm,pe,ec,pa in Section 3 with
$\mathrm{pe}=\\{k,\ldots\\}$ applied to a state
$\rho_{ABE}\in\mathcal{S}(ABE)$ and the state
$\sigma_{XYVWS^{\Pi}S^{\Xi}S^{\Theta}F^{\mathrm{pe}}E}$ as in (42) that
results after measurement and parameter estimation. Define $\bar{c}$ as in
(21). Then, for
$\varepsilon\in\big{[}0,\sqrt{\Pr[F^{\mathrm{pe}}=\checkmark]_{\sigma}}\big{)}$,
we have

$\displaystyle H_{\min}^{\varepsilon}(X\land
F^{\mathrm{pe}}=\checkmark|VWS^{\Pi}S^{\Xi}S^{\Theta}E)_{\sigma}+H_{\max}^{\varepsilon}(X\land
F^{\mathrm{pe}}=\checkmark|Y)_{\sigma}\geq(m-k)\log\frac{1}{\bar{c}}\,.$ (68)

###### Proof.

Consider the state $\tau_{ABVWS^{\Pi}S^{\Xi}S^{\Theta}F^{\mathrm{pe}}E\land
F^{\textrm{pe}}=\checkmark}$ defined in (40) and note that it is of the form

$\displaystyle\tau_{ABVWS^{\Pi}S^{\Xi}S^{\Theta}F^{\mathrm{pe}}E\land
F^{\textrm{pe}}=\checkmark}=\tau_{ABVWS^{\Pi}S^{\Xi}F^{\mathrm{pe}}E\land
F^{\textrm{pe}}=\checkmark}\otimes\rho_{S^{\Theta}}.$ (69)

This is the state of the system after parameter estimation and after measuring
$V$ and $W$, but with the measurement of $X$ and $Y$ (in the basis determined
by $S^{\Theta}$) delayed. In particular we have used the fact that the
register $S^{\Theta}$ has not yet been touched in the protocol, and is thus
independent and uniform and independent even after we consider the event
$F^{\textrm{pe}}=\checkmark$.

Let us now apply Proposition 4 to this state. For this purpose we equate
$P=S^{\Pi}S^{\Xi}S^{\Theta}$, $R=VWE$, and $S=B$. The symmetry is determined
by the map $q:\theta\mapsto\bar{\theta}$ with $\bar{\theta}_{i}=1-\theta_{i}$,
which only acts on $S^{\Theta}$ 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 $\mathcal{M}_{A\to
X|S^{\Pi}S^{\Theta}}$ and we can calculate

$\displaystyle
c_{q}=\max_{\pi\in\Pi_{m,k}}\max_{\theta,x,z\in\\{0,1\\}^{n}}\Big{\|}M_{A_{\bar{\pi}}}^{\bar{\theta},x}\big{(}M_{A_{\bar{\pi}}}^{{\theta},z}\big{)}^{{\dagger}}\Big{\|}_{\infty}^{2}=\max_{\pi\in\Pi_{m,k}}\left(\prod_{i\in\bar{\pi}}c_{i}\right)=\bar{c}^{n}\,.$
(70)

Proposition 4 applied to our setup thus yields

$\displaystyle H_{\min}^{\varepsilon}(X\land
F^{\mathrm{pe}}=\checkmark|VWES^{\Pi}S^{\Xi}S^{\Theta})_{\sigma}+H_{\max}^{\varepsilon}(X\land
F^{\mathrm{pe}}=\checkmark|BS^{\Pi}S^{\Xi}S^{\Theta})_{\tau}\geq
n\log\frac{1}{\bar{c}}.$ (71)

Finally, the statement of the Proposition follows by applying the measurement
map $\mathcal{M}_{B\to Y|S^{\Pi}S^{\Theta}}$ (and discarding the seed
registers) and noting that $H_{\max}^{\varepsilon}(X\land
F^{\mathrm{pe}}=\checkmark|BS^{\Pi}S^{\Xi}S^{\Theta})_{\tau}\leq
H_{\max}^{\varepsilon}(X\land F^{\mathrm{pe}}=\checkmark|Y)_{\sigma}$ 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},\ldots,Z_{m})$ with
$Z_{i}$ taking values in $\\{0,1\\}$ and $m=n+k$. Let $\Pi\in\Pi_{m,k}$ be an
independent, uniformly distributed random variable. Then,

$\displaystyle\Pr\Bigg{[}\sum_{i\in\Pi}Z_{i}\leq k\delta\ \land\
\sum_{i\in\bar{\Pi}}Z_{i}\geq n(\delta+\nu)\Bigg{]}\leq
e^{-2\nu^{2}\frac{nk^{2}}{(n+k)(k+1)}}.$ (72)

Remarkably this bound is valid without any assumption on the distribution of
$Z$.

###### Proof.

Let $\mu(z)=\frac{1}{m}\sum_{i\in[m]}z_{i}$. Consider the following sequence
of inequalities:

$\displaystyle\Pr\Bigg{[}\frac{1}{k}\sum_{i\in\Pi}Z_{i}\leq\delta\ \land\
\frac{1}{n}\sum_{i\notin\Pi}Z_{i}\geq\delta+\nu\Bigg{]}$
$\displaystyle\leq\Pr\Bigg{[}\frac{1}{n}\sum_{i\in\bar{\Pi}}Z_{i}\geq\frac{1}{k}\sum_{i\in\Pi}Z_{i}+\nu\Bigg{]}$
(73)
$\displaystyle=\sum_{z\in\\{0,1\\}^{m}}\\!\\!\Pr[Z=z]\Pr\Bigg{[}\frac{1}{n}\sum_{i\in\bar{\Pi}}z_{i}\geq\frac{1}{k}\sum_{i\in\Pi}z_{i}+\nu\Bigg{]}$
(74)
$\displaystyle=\sum_{z\in\\{0,1\\}^{m}}\\!\\!\Pr[Z=z]\Pr\Bigg{[}\frac{1}{n}\sum_{i\in\bar{\Pi}}z_{i}\geq\mu(z)+\frac{k\nu}{m}\Bigg{]}.$
(75)

Here, the first inequality holds since $A\implies B$ implies
$\Pr[A]\leq\Pr[B]$ for any events $A$ and $B$. The first equality follows from
the fact that $\Pi$ is independent of $Z$. The last equality follows by
substituting $\sum_{i\in\Pi}z_{i}=m\mu(z)-\sum_{i\in\bar{\Pi}}z_{i}$ and
rearranging the terms appropriately.

Now note that the random sums $S_{n}:=\sum_{i\in\bar{\Pi}}z_{i}$ can be seen
as emanating from randomly sampling without replacement $n$ balls labelled by
$z_{i}\in\\{0,1\\}$ from a population $z$ with mean $\mu(z)$. Serfling’s bound
[42, Corollary 1.1] then tells us that

$\displaystyle\Pr\bigg{[}\frac{1}{n}S_{n}\geq\mu(z)+\frac{k\nu}{m}\bigg{]}$
$\displaystyle\leq
e^{-2n\bigg{(}\frac{k\nu}{m}\bigg{)}^{2}\frac{1}{1-f_{n}^{*}}}=e^{-2\nu^{2}\frac{nk^{2}}{(n+k)(k+1)}}\,.$
(76)

where we substituted $f_{n}^{*}=\frac{n-1}{m}$. It is important to note that
this bound is independent of $\mu(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 $\rho_{AX}\in\mathcal{S}_{\bullet}(AX)$ be classical on $X$ and
$\Omega:\mathcal{X}\to\\{0,1\\}$ an event with
$\Pr[\Omega]_{\rho}=\varepsilon<\operatorname{tr}\\{\rho_{AX}\\}$. Then there
exists a state $\tilde{\rho}_{AX}\in\mathcal{S}_{\bullet}(AX)$ with
$\Pr[\Omega]_{\tilde{\rho}}=0$ and
$P(\rho_{AX},\tilde{\rho}_{AX})\leq\sqrt{\varepsilon}$.

###### Proof.

Set $t=\operatorname{tr}\\{\rho_{AX}\\}$. Let
$\tilde{\rho}_{AX}=\frac{\sin^{2}(\phi)}{t-\varepsilon}\rho_{AX\land\lnot\Omega}$
for some normalization $\phi\in[0,\frac{\pi}{2}]$ to be determined. Then the
generalized fidelity evaluates to

$\displaystyle\sqrt{F\big{(}\rho_{AX},\tilde{\rho}_{AX}\big{)}}$
$\displaystyle=\frac{\sin(\phi)}{\sqrt{t-\varepsilon}}\operatorname{tr}\left\\{\sqrt{\sqrt{\rho_{AX}}\rho_{AX\land\lnot\Omega}\sqrt{\rho_{AX}}}\right\\}+\cos(\phi)\sqrt{1-t}$
(77) $\displaystyle=\sin(\phi)\sqrt{t-\varepsilon}+\cos(\phi)\sqrt{1-t}\,.$
(78)

This expression is maximized for $\tan(\phi)=\sqrt{\frac{t-\varepsilon}{1-t}}$
and, thus, $\sin(\phi)=\sqrt{\frac{t-\varepsilon}{1-\varepsilon}}$ and
$\cos(\phi)=\sqrt{\frac{1-t}{1-\varepsilon}}$. Substituting this into (78)
yields $F(\rho_{AX},\tilde{\rho}_{AX})=1-\varepsilon$, 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_ebm,pe,ec,pa in Section 3 with
$\mathrm{pe}=\\{k,\delta\\}$ applied to a state $\rho_{AB}\in\mathcal{S}(AB)$
and the state $\sigma_{XYF^{\textrm{pe}}}$ in (42) that results after
measurement and parameter estimation. For any $\nu\in(0,1)$, we first define

$\displaystyle\varepsilon(\nu):=e^{-\frac{(m-k)k^{2}\nu^{2}}{m(k+1)}}\,.$ (79)

Then, for any $\nu\in(0,\frac{1}{2}-\delta]$ such that
$\varepsilon(\nu)^{2}<\Pr[F^{\mathrm{pe}}=\,\checkmark]_{\sigma}$, the
following holds:

$\displaystyle H_{\max}^{\varepsilon(\nu)}(X\land
F^{\mathrm{pe}}=\checkmark|Y)_{\sigma}\leq(m-k)\,h(\delta+\nu)\qquad\textrm{where}\qquad
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, conditioned on any particular value of $Y$, the
support of $X$ is small as the number of errors (positions where $x_{i}\neq
y_{i}$) is bounded (with high probability).

###### Proof.

We use the shorthand $p=\Pr[F^{\mathrm{pe}}=\,\checkmark]_{\sigma}$ and
$n:=m-k$. Define the event event
$\Omega:=1\big{\\{}\sum_{i\in[n]}1\\{X_{i}\neq Y_{i}\\}\geq
n(\delta+\nu)\big{\\}}$. We show that the statement in (80) holds when
$p>\varepsilon^{2}$. Using Lemma 6, we find

$\displaystyle\Pr\bigg{[}F^{\mathrm{pe}}=\checkmark\land\Omega\bigg{]}_{\sigma}=\Pr\bigg{[}\sum_{i\in[k]}1\\{V_{i}\neq
W_{i}\\}\leq k\delta\ \land\ \sum_{i\in[n]}1\\{X_{i}\neq Y_{i}\\}\geq
n(\delta+\nu)\bigg{]}_{\sigma}\leq\varepsilon(\nu)^{2}.$ (81)

This gives an upper bound on the probability of the unlikely coincidence where
the parameter estimation test passes with threshold $\delta$ but the fraction
of errors between $X$ and $Y$ exceeds the threshold $\delta$ by a constant
amount. We now want to remove the above unlikely events from our state
$\sigma_{XYF^{\textrm{pe}}\land F^{\textrm{pe}}=\,\checkmark}$ by means of
smoothing. Lemma 7 allows to do just that, and we introduce the state
$\tilde{\sigma}_{XYF^{\textrm{pe}}}$ that is $\varepsilon(\nu)$-close to
$\sigma_{XYF^{\textrm{pe}}\land F^{\textrm{pe}}=\,\checkmark}$ in purified
distance and satisfies $\Pr[\Omega]_{\tilde{\sigma}}=0$. From this we conclude
that

$\displaystyle H_{\max}^{\varepsilon(\nu)}(X\land
F^{\mathrm{pe}}=\checkmark|Y)_{\sigma}\leq H_{\max}(X\land
F^{\mathrm{pe}}=\checkmark|Y)_{\tilde{\sigma}}=H_{\max}(X|Y)_{\tilde{\sigma}}\,,$
(82)

where the last equality is a consequence of the fact that $\tilde{\sigma}$ is
only supported on $F^{\mathrm{pe}}=\checkmark$.

It remains to show that $H_{\max}(X|Y)_{\tilde{\sigma}}\leq nh(\delta+\nu)$.
Using the expansion of the conditional max-entropy in [41, Sec. 4.3.2], we
find

$\displaystyle H_{\max}(X|Y)_{\tilde{\sigma}}$
$\displaystyle=\log\Bigg{(}\sum_{y\in\\{0,1\\}^{n}}\Pr[Y=y]_{\tilde{\sigma}}\
2^{H_{\max}(X|Y=y)_{\tilde{\sigma}}}\Bigg{)}$ (83)
$\displaystyle\leq\max_{y\in\\{0,1\\}^{n}\atop\Pr[Y=y]_{\tilde{\sigma}}>0}H_{\max}(X|Y=y)_{\tilde{\sigma}}$
(84)
$\displaystyle\leq\max_{y\in\\{0,1\\}^{n}\atop\Pr[Y=y]_{\tilde{\sigma}}>0}\log\Big{|}\Big{\\{}x\in\\{0,1\\}^{n}:\Pr[X=x|Y=y]_{\tilde{\sigma}}>0\Big{\\}}\Big{|}$
(85)
$\displaystyle=\max_{y\in\\{0,1\\}^{n}}\log\Big{|}\Big{\\{}x\in\\{0,1\\}^{n}:\Pr[X=x\land
Y=y]_{\tilde{\sigma}}>0\Big{\\}}\,.$ (86)

In the ultimate inequality we used that the (unconditional) Rényi entropy is
upper bounded by the logarithm of the distribution’s support [29].
Furthermore, since $\Pr[\Omega]_{\tilde{\sigma}}=0$, we have

$\displaystyle\Big{|}\Big{\\{}x\in\\{0,1\\}^{n}:\Pr[X=x\land
Y=y]_{\tilde{\sigma}}>0\Big{\\}}\Big{|}$
$\displaystyle\leq\sum_{x\in\\{0,1\\}^{n}}1\Bigg{\\{}\sum_{i\in[n]}1\\{x_{i}\neq
y_{i}\\}<n(\delta+\nu)\Bigg{\\}}$ (87)
$\displaystyle=\sum_{e\in\\{0,1\\}^{n}}1\bigg{\\{}\sum_{i=1}^{n}e_{i}<n(\delta+\nu)\bigg{\\}}$
(88)
$\displaystyle=\sum_{\lambda=0}^{n}{n\choose\lambda}1\big{\\{}\lambda<n(\delta+\nu)\big{\\}}=\sum_{\lambda=0}^{\lfloor
n(\delta+\nu)\rfloor}{n\choose\lambda}.$ (89)

Here, in order to derive (88) we reparameterize $e_{i}=x_{i}\textrm{ xor
}y_{i}$, indicating if there is an error at the $i$-th position. Finally, in
(89) we substitute $\lambda=\sum_{i=1}^{n}e_{i}$, the total number of errors.
The inequality $\sum_{\lambda=0}^{\lfloor
n(\delta+\nu)\rfloor}{n\choose\lambda}\leq 2^{nh(\delta+\nu)}$ for
$\delta+\nu\leq 1/2$ (see, e.g., [43, 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 $\sigma_{XD}\in\mathcal{S}_{\bullet}(XD)$ be a classical on $X$ and let
$\mathcal{H}$ be a universal2 family of hash functions from
$\mathcal{X}=\\{0,1\\}^{n}$ to $\mathcal{K}=\\{0,1\\}^{\ell}$. Moreover, let
$\rho_{S^{H}}=\frac{1}{|\mathcal{H}|}\sum_{h\in\mathcal{H}}\left|h\middle\rangle\\!\middle\langle
h\right|_{S^{H}}$. Then,

$\displaystyle\|\omega_{KS^{H}D}-\chi_{K}\otimes\omega_{S^{H}D}\|_{\operatorname{tr}}\leq\frac{1}{2}2^{-\frac{1}{2}\left(H_{\min}^{\varepsilon}(X|D)_{\sigma}-\ell\right)}+2\varepsilon$
(90)

where $\chi_{K}=\frac{1}{2^{\ell}}\mathrm{id}_{K}$ is the fully mixed state
and
$\omega_{KS^{H}D}=\operatorname{tr}_{X}\big{(}\mathcal{E}_{f}(\sigma_{XD}\otimes\rho_{S^{H}})\big{)}$
for the function $f:(x,h)\mapsto h(x)$ that acts on the registers $X$ and
$S^{H}$.

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 $\rho_{ABXY}\in\mathcal{S}_{\bullet}(ABXY)$ be classical on $X$ and $Y$
and let $\Omega:\mathcal{X}\times\mathcal{Y}\to\\{0,1\\}$ be an event with
$\Pr[\Omega]_{\rho}>0$. Then, for
$\varepsilon\in\big{[}0,\sqrt{\Pr[\Omega]_{\rho}}\big{)}$, we have

$\displaystyle H_{\min}^{\varepsilon}(AX\land\Omega|BY)_{\rho}\geq
H_{\min}^{\varepsilon}(AX|BY)_{\rho}\quad\textrm{and}\quad
H_{\min}^{\varepsilon}(AX\land\Omega|B)_{\rho}\geq
H_{\min}^{\varepsilon}(AX|B)_{\rho}$ (91)

###### Proof.

Let us start with the first inequality. By definition of the smooth
conditional min-entropy there exists a state
$\tilde{\rho}_{ABXY}\in\mathcal{S}_{\bullet}(ABXY)$ and a state
$\sigma_{BY}\in\mathcal{S}(BY)$ such that

$\displaystyle\tilde{\rho}_{ABXY}\leq
2^{-H_{\min}^{\varepsilon}(AX|BY)_{\rho}}\mathrm{id}_{AX}\otimes\sigma_{BY}\quad\textrm{and}\quad
P(\tilde{\rho}_{ABXY},\rho_{ABXY})\leq\varepsilon\,.$ (92)

Without loss of generality [24, Lemma 6.6] we can assume that
$\tilde{\rho}_{ABXY}$ is classical on $X$ and $Y$. As such, we have
$\tilde{\rho}_{ABXY\land\Omega}\leq\tilde{\rho}_{ABXY}$ and
$P(\tilde{\rho}_{ABXY\land\Omega},\rho_{ABXY\land\Omega})\leq
P(\tilde{\rho}_{ABXY},\rho_{ABXY})\leq\varepsilon$ 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 $\Omega$.

The second inequality follows similarly. By definition of the smooth
conditional min-entropy there exists a state
$\tilde{\rho}_{ABX}\in\mathcal{S}_{\bullet}(ABX)$ and a state
$\sigma_{B}\in\mathcal{S}(B)$ such that

$\displaystyle\tilde{\rho}_{ABX}\leq
2^{-H_{\min}^{\varepsilon}(AX|B)_{\rho}}\mathrm{id}_{AX}\otimes\sigma_{B}\quad\textrm{and}\quad
P(\tilde{\rho}_{ABX},\rho_{ABX})\leq\varepsilon\,.$ (93)

As discussed previously, this implies in particular the existence of an
extension $\tilde{\rho}_{ABXY}\in\mathcal{S}_{\bullet}(ABXY)$ that satisfies
$P(\tilde{\rho}_{ABXY},\rho_{ABXY})\leq\varepsilon$. Without loss of
generality we can assume that $\tilde{\rho}_{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 $\tilde{\rho}_{ABXY}$ and
$\rho_{ABXY}$, leaving the latter state invariant.) On the state
$\tilde{\rho}_{ABXY}$ we can now define the restriction on the event $\Omega$
and find

$\displaystyle\tilde{\rho}_{ABXY\land\Omega}\leq\tilde{\rho}_{ABXY}\implies\tilde{\rho}_{ABX\land\Omega}=\operatorname{tr}_{Y}\\{\tilde{\rho}_{ABXY\land\Omega}\\}\leq\tilde{\rho}_{ABX}\,.$
(94)

Finally, we proceed in the same fashion as for the first inequality to show
that $P(\tilde{\rho}_{ABX\land\Omega},\rho_{ABX\land\Omega})\leq\varepsilon$
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 $\rho_{ABE}\in\mathcal{S}(ABE)$. Consider the protocol qkd_ebm,pe,ec,pa in
Section 3 with $\mathrm{pe}=\\{k,\delta\\}$, $\mathrm{ec}=\\{t,r,\ldots\\}$
and $\mathrm{pa}=\\{\ell,\ldots\\}$ and the state
$\omega_{K_{A}K_{B}SCFE}=\mbox{{{qkd\\_eb${}_{m,\mathrm{pe},\mathrm{ec},\mathrm{pa}}$}}}(\rho_{ABE})$.
Define $\varepsilon(\nu)$ as in (79). Then, for any
$\nu\in(0,\frac{1}{2}-\delta]$ such that
$\varepsilon(\nu)^{2}<\Pr[F=(\checkmark,\checkmark)]_{\sigma}$, the following
holds:

$\displaystyle\Big{\|}\omega_{K_{A}SCFE\land
F=\,(\checkmark,\checkmark)}-\chi_{K_{A}}\otimes\omega_{SCFE\land
F=\,(\checkmark,\checkmark)}\Big{\|}_{\mathrm{tr}}\leq\frac{1}{2}2^{-\frac{1}{2}g(\nu)}+2\varepsilon(\nu)\,.$
(95)

where
$g(\nu):=(m-k)\big{(}\log\frac{1}{\bar{c}}-h(\delta+\nu)\big{)}+r+t+\ell$.

###### Proof.

We use $n=m-k$. Since
$\Pr[F=(\checkmark\checkmark)]_{\sigma}\leq\Pr[F^{\mathrm{pe}}=\checkmark]_{\sigma}$
the condition of Proposition 8 is satisfied and we find that
$H_{\max}^{\varepsilon(\nu)}(X\land F^{\mathrm{pe}}=\checkmark|Y)_{\sigma}\leq
nh(\delta+\nu)$ for the state
$\sigma_{XYVWS^{\Pi}S^{\Xi}S^{\Theta}F^{\mathrm{pe}}E}$ as in (42) that
results after measurement and parameter estimation. Combining this with
Corollary 5 yields

$\displaystyle H_{\min}^{\varepsilon(\nu)}(X\land
F^{\mathrm{pe}}=\checkmark|VWS^{\Pi}S^{\Xi}S^{\Theta}E)_{\sigma}\geq nq\,,$
(96)

where we introduced the shorthand $q=\log\frac{1}{\bar{c}}-h(\delta+\nu)$.

Our goal is to translate this in a condition on the state
$\sigma_{X\hat{X}C^{V}C^{Z}C^{T}S^{\Pi}S^{\Xi}S^{\Theta}S^{H_{\mathrm{ec}}}F^{\textrm{pe}}F^{\textrm{ec}}E}$
as in (44) that results after error correction. The following chain of
inequalities holds:

$\displaystyle nq$ $\displaystyle\leq H_{\min}^{\varepsilon(\nu)}(X\land
F^{\mathrm{pe}}=\checkmark|S^{\Pi}S^{\Xi}S^{\Theta}C^{V}E)_{{\sigma}}$ (97)
$\displaystyle\leq H_{\min}^{\varepsilon(\nu)}(X\land
F^{\mathrm{pe}}=\checkmark|S^{\Pi}S^{\Xi}S^{\Theta}C^{V}C^{Z}E)_{{\sigma}}+r$
(98) $\displaystyle=H_{\min}^{\varepsilon(\nu)}(X\land
F^{\mathrm{pe}}=\checkmark|S^{\Pi}S^{\Xi}S^{\Theta}S^{H_{\mathrm{ec}}}C^{V}C^{Z}E)_{{\sigma}\otimes\rho}+r$
(99) $\displaystyle\leq H_{\min}^{\varepsilon(\nu)}(X\land F^{\rm
pe}=\checkmark|S^{\Pi}S^{\Xi}S^{\Theta}S^{H_{\mathrm{ec}}}C^{V}C^{Z}C^{T}E)_{{\sigma}}+r+t$
(100) $\displaystyle\leq H_{\min}^{\varepsilon(\nu)}\big{(}X\land F^{\rm
pe}=\checkmark\land F^{\rm
ec}=\checkmark\big{|}S^{\Pi}S^{\Xi}S^{\Theta}S^{H_{\mathrm{ec}}}C^{V}C^{Z}C^{T}E\big{)}_{{\sigma}}+r+t.$
(101)

The first inequality follows by relabeling $V$ to $C^{V}$ and discarding $W$,
an instance of the data-processing inequality. 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_{\mathrm{ec}}}$ in the state $\rho_{S^{H_{\mathrm{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^{\prime}=(S^{\Pi},S^{\Xi},S^{\Theta},S^{H_{\mathrm{ec}}})$ as
well as $C=(C^{V},C^{Z},C^{T})$, and $F=(F^{\mathrm{pe}},F^{\mathrm{ec}})$ as
usual, we can thus more compactly write this as

$\displaystyle H_{\min}^{\varepsilon(\nu)}(X\land
F=(\checkmark,\checkmark)\,|S^{\prime}CE)_{{\sigma}}\geq nq-r-t\,.$ (102)

Proposition 9 applied with this bound then immediately yields the desired
inequality. ∎

The above proposition suffers from the assumption
$\varepsilon(\nu)^{2}<\Pr[F=(\checkmark,\checkmark)]_{\omega}$. However, the
other case can easily be dealt with. Indeed, the trace distance
$\big{\|}\omega_{K_{A}SCFE\land
F=\,(\checkmark,\checkmark)}-\chi_{K_{A}}\otimes\omega_{SCFE\land
F=\,(\checkmark,\checkmark)}\big{\|}_{\mathrm{tr}}$ is upper bounded by the
the trace of both states, i.e. the probability
$\Pr[F=(\checkmark,\checkmark)]_{\omega}$. The inequalities
$\Pr[F=(\checkmark,\checkmark)]_{\sigma}\leq\varepsilon(\nu)^{2}\leq\varepsilon(\nu)$
then yield the following corollary, which is equivalent to Theorem 3.

######  Corollary 12.

Consider the setup of Proposition 11. For any $\nu\in(0,\frac{1}{2}-\delta]$
the following holds:

$\displaystyle\Big{\|}\omega_{K_{A}SCFE\land
F=\,(\checkmark,\checkmark)}-\chi_{K_{A}}\otimes\omega_{SCFE\land
F=\,(\checkmark,\checkmark)}\Big{\|}_{\mathrm{tr}}\leq\frac{1}{2}\sqrt{2^{-(m-k)\big{(}\log\frac{1}{\bar{c}}-h(\delta+\nu)\big{)}+r+t+\ell}}+2\varepsilon(\nu),$
(103)

where $\varepsilon(\nu)$ is defined in (79).

##  Part II Prepare-and-measure protocol

$\mathcal{N}_{A\to B}$ | Quantum channel between Alice and Bob
---|---
$\mathcal{P}_{\varnothing\to A|RS^{\Phi_{\\!A}}}$ |  Preparation map that returns a state in register $A$ depending on the settings $R,S^{\Phi_{\\!A}}$
$M$ | Number of states sent by Alice in the prepare-and-measure version
$\Omega$ |  Subset of $[M]$ for which Bob obtains a conclusive measurement result
$\Sigma$ |  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^{\Phi_{\\!A}}$ | Seed for the choice of Alice’s measurement bases in the prepare-and-measure protocol
$S^{\Phi_{\\!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^{\Pi},S^{\Xi},S^{\Theta},S^{H_{\mathrm{pe}}},S^{H_{\mathrm{ec}}})$
$F^{\mathrm{si}}$ | Flag for the sifting procedure in the prepare-and-measure protocol
$F$ |  Register corresponding to all the flags, $F=(F^{\mathrm{si}},F^{\mathrm{pe}},F^{\mathrm{ec}})$
$C^{\Omega},C^{\Sigma}$ |  Transcripts of the registers $\Omega$ and $\Sigma$ sent during sifting
$C$ |  Register containing all the communication transcripts, $C=(C^{\Omega},C^{\Sigma},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_pmM,m,pe,ec,pa, which is essentially 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.

####  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\in[M]$, Alice’s preparation device takes two
bits as input: $\phi\in\\{0,1\\}$ describing a basis choice and
$x\in\\{0,1\\}$ describing the bit value within each basis. It produces a
quantum state $\rho_{A_{i}}^{\phi,x}$, 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 $\rho_{A_{i}}^{\phi,x}$ does not leak any
information about the basis choice $\phi$, i.e., we require that

$\displaystyle\sum_{x\in\\{0,1\\}}\rho_{A_{i}}^{0,x}=\sum_{x\in\\{0,1\\}}\rho_{A_{i}}^{1,x}\,.$
(104)

Moreover, instead of the complementarity assumption on the measurements, we
require that the prepared states are sufficiently complementary. More
precisely, let us define

$\displaystyle
c^{\prime}\big{(}\\{\rho^{x}\\}_{x},\\{\sigma^{y}\\}_{y}\big{)}:=\max_{x,y}\left\|\sqrt{\rho^{x}}X^{-1}\sqrt{\sigma^{y}}\right\|_{\infty}^{2},\quad\textrm{for
states satisfying}\quad\sum_{x}\rho^{x}=\sum_{y}\sigma^{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

$\displaystyle
c_{i}^{\prime}:=c^{\prime}\Big{(}\big{\\{}\rho_{A_{i}}^{0,x}\big{\\}}_{x},\big{\\{}\rho_{A_{i}}^{1,y}\big{\\}}_{y}\Big{)}\leq\bar{c}^{\prime}$
(106)

for all $i\in[M]$ and some constant $\bar{c}^{\prime}<1$. The constant
$\bar{c}^{\prime}$ is closely related to the constant $\bar{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 $\rho^{\phi,r}$
would be single-qubit states given by

$\displaystyle\rho^{0,0}=\left|0\middle\rangle\\!\middle\langle
0\right|,\quad\rho^{0,1}=\left|1\middle\rangle\\!\middle\langle
1\right|,\quad\rho^{1,0}=\left|+\middle\rangle\\!\middle\langle+\right|,\quad\rho^{1,1}=\left|-\middle\rangle\\!\middle\langle-\right|.$
(107)

These states obviously satisfy the assumption in (104) and it is easy to
verify that $\bar{c}^{\prime}=\frac{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 states111111If the single-photon polarization qubit
states are given by (107), then the four encoded BB84 states are
$\tau^{i,j}=e^{-\alpha^{2}}\bigoplus_{k=0}^{\infty}\frac{\alpha^{2k}}{k!}(\rho^{i,j})^{\otimes
k}$ for $i,j\in\\{0,1\\}$, where $\alpha>0$ is the amplitude of the coherent
states.. 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 [44]. While we believe that our framework could accommodate such
modifications (see for instance [45, 46]), 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\equiv B_{[M]}=B_{1}B_{2}\ldots 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, ‘$\varnothing$’, 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)121212Indeed, 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..

For any $i\in[M]$, we model Bob’s measurement on subsystem $B_{i}$ with
setting $\phi\in\\{0,1\\}$ by a ternary generalized measurement
$\\{M_{B_{i}}^{\phi,z}\\}_{z\in\\{0,1,\varnothing\\}}$ 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 $\varnothing$. We require
that

$\displaystyle(M_{B_{i}}^{0,\varnothing})^{\dagger}(M_{B_{i}}^{0,\varnothing})=(M_{B_{i}}^{1,\varnothing})^{\dagger}(M_{B_{i}}^{1,\varnothing}),$
(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 [35].

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 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_pmM,m,pe,ec,pa is parametrized as qkd_ebm,pe,ec,pa, but with
one extra parameter:

  * •

The number of individual states prepared and sent through the quantum channel
by Alice, $M\in\mathbb{N}$. We require that $M\geq m$ and for optical
implementations a typical value for $M$ is $\frac{2m}{\eta}$ where $\eta$ is
the overall transmittance of the optical channel between Alice and Bob.

$(K_{A},K_{B},S,C,F)=\mbox{{{qkd\\_pm${}_{M,m,\mathrm{pe},\mathrm{ec},\mathrm{pa}}$}}}\big{(}\mathcal{N}_{A\to
B}\big{)}$: Input: Alice and Bob have access to a quantum channel
$\mathcal{N}_{A\to B}:A\to B$ where $A\equiv A_{[M]}$ and $B\equiv B_{[M]}$
are comprised of $M$ quantum systems. Randomization: Alice and Bob
respectively choose two random strings
$\Phi_{\\!A},\Phi_{\\!B}\in\\{0,1\\}^{M}$. Alice also chooses a random string
$R\in\\{0,1\\}^{M}$. These private seeds are denoted
$S^{\Phi_{\\!A}},S^{\Phi_{\\!B}}$ and $R$. Finally, similarly as in the simple
protocol, Alice chooses a random subset $\Pi\in\Pi_{m,k}$, and random hash
functions $H_{\mathrm{ec}}\in\mathcal{H}_{\textrm{ec}}$ as well as
$H_{\mathrm{pa}}\in\mathcal{H}_{\textrm{pa}}$. These uniformly random seeds
are denoted $S=(S^{\Pi},S^{H_{\textrm{ec}}},S^{H_{\textrm{pa}}})$. State
Preparation: Alice prepares a quantum state $\rho_{A}^{R,\Phi_{A}}$, encoding
the string $R$ in the measurement basis corresponding to $\phi_{A}$. State
Distribution: Alice sends the state $\rho_{A}^{R,\Phi_{A}}$ through the
quantum channel $\mathcal{N}$ and Bob receives the output state
$\rho_{B}^{R,\Phi_{A}}=\mathcal{N}(\rho_{A}^{R,\Phi_{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
$\Phi_{\\!B}$, and stores his ternary measurement outcomes in a string
$U\in\\{0,1,\varnothing\\}^{M}$, where $\varnothing$ denotes an inconclusive
measurement result. He also computes the set $\Omega\subseteq 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 $\Phi_{\\!B}$ and $\Omega$. The
corresponding transcripts are denoted by $C^{\Phi_{\\!B}}$ and $C^{\Omega}$,
respectively. Alice sends the value of the seeds
$S=(S^{\Pi},S^{H_{\mathrm{ec}}},S^{H_{\mathrm{pa}}})$ to Bob through the
authenticated public channel. Sifting: If it exists, Alice publicly announces
a set $\Sigma\subseteq\Omega$, with transcript $C^{\Sigma}$ of cardinality
$m$, such that $\Phi_{\\!A}$ and $\Phi_{\\!B}$ coincide on $\Sigma$, and sets
the flag $F^{\mathrm{si}}=\checkmark$. Otherwise, she sets
$F^{\mathrm{si}}=\varnothing$ and they abort. The respective binary substrings
$R^{\prime}$ and $U^{\prime}$ of $R$ and $U$ restricted to $\Sigma$ 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 $\Pi$, whereas $X,Y$ of length $n$
correspond to indices not in $\Pi$. Parameter Estimation: Alice sends $V$ to
Bob, the transcript is denoted $C^{V}$. Bob compares $V$ and $W$. If the
fraction of errors exceeds $\delta$, Bob sets the flag $F^{\mathrm{pe}}=$
‘$\varnothing$’ and they abort. Otherwise he sets $F^{\mathrm{pe}}=$
‘$\checkmark$’ and they proceed. Error Correction: Alice sends the syndrome
$Z=\mathrm{synd}(X)$ to Bob, with transcript $C^{Z}$. Bob computes
$\hat{X}=\mathrm{corr}(Y,Z)$. Alice computes the hash $T=H_{\mathrm{ec}}(X)$
of length $t$ and sends it to Bob, with transcript $C^{T}$. Bob computes
$H_{\mathrm{ec}}(\hat{X})$. If it differs from $T$, he sets the flag
$F^{\mathrm{ec}}=$ ‘$\varnothing$’ and they abort the protocol. Otherwise he
sets $F^{\mathrm{ec}}=$ ‘$\checkmark$’ and they proceed. Privacy
Amplification: They compute keys $K_{A}=H_{\mathrm{pa}}(X)$ and
$K_{B}=H_{\mathrm{pa}}(\hat{X})$ of length $\ell$. Output: The output of the
protocol consists of the keys $K_{A}$ and $K_{B}$, the seeds
$(S^{\Phi_{\\!B}},S^{\Pi},S^{H_{\textrm{ec}}},S^{H_{\textrm{pa}}})$, the
transcript $C=(C^{\Omega},C^{\Sigma},C^{V},C^{Z},C^{H})$ and the flags
$F=(F^{\mathrm{si}},F^{\mathrm{pe}},F^{\mathrm{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_pmM,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 $\mathcal{N}$ 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_pmM,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 $\mathcal{N}_{A\to B}$ 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.

Alicepublic domainBob$\mathcal{N}$ Figure 8: (Input.) Alice and Bob have
access to a quantum channel: $\mathcal{N}:A\to B$.

##### Randomization:

The random seeds are modeled similarly as for the idealized version of the
protocol. Here, the seed $S^{\Phi}$ corresponding to identical measurement
settings is not provided directly. Instead, Alice and Bob initially choose
independently two strings $\Phi_{\\!A},\Phi_{\\!B}\in\\{0,1\\}^{M}$, and it
will later be the role of the sifting procedure to produce a set of identical
measurement settings $\Phi$. The random choice of the strings
$\Phi_{\\!A},\Phi_{\\!B}$ is modeled by two registers
$S^{\Phi_{\\!A}},S^{\Phi_{\\!B}}$ in the state

$\displaystyle\rho_{S^{\Phi_{\\!A}}}\otimes\rho_{S^{\Phi_{\\!B}}}=\frac{1}{4^{M}}\sum_{\phi_{A},\phi_{B}\in\\{0,1\\}^{M}}\left|\phi_{A}\middle\rangle\\!\middle\langle\phi_{A}\right|_{S^{\Phi_{\\!A}}}\otimes\left|\phi_{B}\middle\rangle\\!\middle\langle\phi_{B}\right|_{S^{\Phi_{\\!B}}},$
(109)

where $\\{|\phi_{A}\rangle\\},\\{|\phi_{B}\rangle\\}$ are orthonormal bases of
$S^{\Phi_{\\!A}}$ and $S^{\Phi_{\\!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:

$\displaystyle\rho_{R}=\frac{1}{2^{M}}\sum_{r\in\\{0,1\\}^{M}}\left|r\middle\rangle\\!\middle\langle
r\right|_{R},$ (110)

where $\\{|r\rangle\\}$ is an orthonormal basis of $R$. The other random seeds
$\rho_{S^{\Pi}},\rho_{S^{H_{\mathrm{ec}}}},\rho_{S^{H_{\mathrm{pa}}}}$ are
identical to the idealized version. This situation is depicted in Figure 9.

Alicepublic domainBob$\mathcal{N}$$\Phi_{\\!A}$$R$$S$$\Phi_{\\!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,\Phi_{\\!A}$ for Alice, $\Phi_{\\!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^{\Phi_{\\!A}}$ to Bob since the
sifting procedure is performed by Alice.

In a practical implementation, the various random seeds, except for
$S^{\Phi_{\\!B}}$ would be initially prepared by Alice, and only communicated
to Bob when needed (except for $R$ and $S^{\Phi_{\\!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 n $M$ systems $A\equiv A_{[n]}$ using the
map

$\displaystyle\mathcal{P}_{\varnothing\to
A|RS^{\Phi_{\\!A}}}(\cdot)=\sum_{r,\phi\in\\{0,1\\}^{M}}\Big{(}\left|r\middle\rangle\\!\middle\langle
r\right|_{R}\otimes\left|\phi\middle\rangle\\!\middle\langle\phi\right|_{S^{\Phi_{\\!A}}}\Big{)}\cdot\Big{(}\left|r\middle\rangle\\!\middle\langle
r\right|_{R}\otimes\left|\phi\middle\rangle\\!\middle\langle\phi\right|_{S^{\Phi_{\\!A}}}\Big{)}\otimes\rho_{A}^{r,\phi}$
(111)

where $\rho_{A}^{r,\phi}=\bigotimes_{i=1}^{M}\rho_{A_{i}}^{r_{i},\phi_{i}}$.
Applying this map to the seeds in registers $R$ and $S^{\Phi_{\\!A}}$ results
in the state

$\displaystyle\rho_{RS^{\Phi_{\\!A}}A}=\frac{1}{4^{M}}\sum_{r,\phi\in\\{0,1\\}^{M}}\left|r\middle\rangle\\!\middle\langle
r\right|_{R}\otimes\left|\phi\middle\rangle\\!\middle\langle\phi\right|_{S^{\Phi_{\\!A}}}\otimes\rho_{A}^{r,\phi}.$
(112)

This situation is depicted in Figure 10.

Alicepublic
domainBob$\mathcal{N}$$\Phi_{\\!A}$$R$$\mathcal{P}$$A$$S$$\Phi_{\\!B}$ Figure
10: (State Preparation.) Using her private seeds $R$ and $\Phi_{\\!A}$, Alice
prepares system $A$.

##### State distribution:

Alice sends her register $A$ to Bob through the quantum channel
$\mathcal{N}:A\to B$. The state shared by Alice and Bob is given by:

$\displaystyle\rho_{RS^{\Phi_{\\!A}}B}$ $\displaystyle=\mathcal{N}_{A\to
B}(\rho_{RS^{\Phi_{\\!A}}A})$ (113)
$\displaystyle=\frac{1}{4^{M}}\sum_{r,\phi\in\\{0,1\\}^{M}}\left|r\middle\rangle\\!\middle\langle
r\right|_{R}\otimes\left|\phi\middle\rangle\\!\middle\langle\phi\right|_{S^{\Phi_{\\!A}}}\otimes\rho_{B}^{r,\phi},$
(114)

where we defined
$\rho_{B}^{r,\phi}=\mathcal{N}\left(\rho_{A}^{r,\phi}\right)$. This situation
is depicted in Figure 11.

Alicepublic domainBob$\mathcal{N}$$\Phi_{\\!A}$$R$$S$$B$$\Phi_{\\!B}$$S$
Figure 11: (State Distribution.) Alice sends the system $A$ through the
quantum channel $\mathcal{N}$ and Bob receives system $B$.

##### Measurement:

Alicepublic domainBob$\Phi_{\\!A}$$R$$S$$S$$\Omega$$U$$B$meas$\Phi_{\\!B}$
Figure 12: (Bob’s Measurement.) Bob measures the quantum system $B$ using the
measurement settings given by his private randomness $\Phi_{\\!B}$ and obtains
two classical strings stored in registers $\Omega$ and $U$.

Bob measures each of his $M$ quantum systems in the basis corresponding to
$\Phi_{\\!B}$ and stores his measurement outcomes, either 0, 1, or
$\varnothing$ in the case of inconclusive outcomes, in a classical register
$U$ taking values in $\\{0,1,\varnothing\\}^{M}$. The measurement map
$\mathcal{M}_{B\to U\Omega|S^{\Phi_{\\!B}}}$ is defined as:

$\displaystyle\mathcal{M}_{B\to
U\Omega|S^{\Phi_{\\!B}}}(\cdot)=\\!\\!\sum_{\phi\in\\{0,1\\}^{M}}\sum_{u\in\\{0,1,\varnothing\\}^{M}}\left|u,\omega\right\rangle_{TC^{\Omega}}\Big{(}M_{B}^{\phi,u}\otimes\left|\phi\middle\rangle\\!\middle\langle\phi\right|_{S^{\Phi_{\\!B}}}\Big{)}\
\cdot\
\Big{(}M_{B}^{\phi,u}\otimes\left|\phi\middle\rangle\\!\middle\langle\phi\right|_{S^{\Phi_{\\!B}}}\Big{)}^{\dagger}\left\langle
u,\omega\right|_{UC^{\Omega}},$ (115)

where $\omega=\omega(u)$ is the subset of $[M]$ where $u$ takes values in
$\\{0,1\\}$, namely

$\displaystyle\omega(u):=\\{i\in[M]\>:\>u_{i}\neq\varnothing\\}.$ (116)

The state of the total system after Bob’s measurement is given by

$\displaystyle\sigma_{RUC^{\Omega}BS^{\Phi_{\\!A}}S^{\Phi_{\\!B}}}=\frac{1}{8^{M}}\sum_{r,\phi_{A},\phi_{B}\in\\{0,1\\}^{M}}\left|r,u,\omega,\phi_{A},\phi_{B}\middle\rangle\\!\middle\langle
r,u,\omega,\phi_{A},\phi_{B}\right|_{RUC^{\Omega}S^{\Phi_{\\!A}}S^{\Phi_{\\!B}}}\otimes
M_{B}^{\phi_{B},u}\rho_{B}^{r,\phi_{A}}\left(M_{B}^{\phi_{B},u}\right)^{\dagger},$
(117)

and the situation is depicted in Figure 12.

##### Randomness distribution:

Alicepublic
domainBob$\Omega$$\Phi_{\\!B}$$R$$\Phi_{\\!A}$$S$$\Phi_{\\!B}$$\Omega$$S$$U$$S^{\Phi_{\\!B}}$$C^{\Omega}$$S$
Figure 13: (Randomness distribution.) Bob communicates the both the value of
$\Phi_{\\!B}$ and $\Omega$ to Alice with the authenticated classical channel.
Alice publicly announces the value of the various seeds,
$S=(S^{\Pi},S^{H_{\mathrm{ec}}},S^{H_{\mathrm{pa}}})$.

Bob publicly announces the content of the register $S^{\Phi_{\\!B}}$ together
with the description $C^{\Omega}$ of the set $\omega$ 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^{\Pi},S^{H_{\mathrm{ec}}},S^{H_{\mathrm{pa}}})$.

##### Sifting:

Alice applies the sifting map, a classical map ‘sift’ defined as follows

$\displaystyle\textrm{sift}:\left\\{\begin{array}[]{ccc}\\{0,1\\}^{M}\times\\{0,1\\}^{M}\times
2^{[M]}&\to&\Pi_{M,m}\times\\{\varnothing,\checkmark\\}\\\
(\phi_{\\!A},\phi_{\\!B},\omega)&\mapsto&(\Sigma,F^{\mathrm{si}})\end{array}\right.$
(120)

where $\Sigma$ is either the first subset of $\Omega$ of cardinality $m$ in
the lexicographic order where $\phi_{\\!A}$ and $\phi_{\\!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^{\mathrm{si}}$ is set to $\checkmark$, otherwise
it is set to $\varnothing$ and the protocol aborts. The output of the sifting
map immediately allows Alice and Bob to compute the value of the seed
$S^{\Phi}$ which is simply the restriction of either $S^{\Phi_{\\!A}}$ or
$S^{\Phi_{\\!B}}$ to the indices in $\Sigma$. This classical map is lifted to
give a CPTP map
$\mathcal{E}_{\mathrm{si}}=S^{\Phi_{\\!A}}S^{\Phi_{\\!B}}C^{\Omega}\to
C^{\Sigma}C^{\Omega}F^{\mathrm{si}}S^{\Phi_{\\!A}}S^{\Phi_{\\!B}}$. This
situation is depicted in Figure 14.

Alicepublic
domainBob$S$$\Omega$$\Phi_{\\!B}$$R$$\Phi_{\\!A}$$\Sigma$$F^{\mathrm{si}}$$F^{\mathrm{si}}$$U$$\Sigma$$S$$S$$\Phi_{\\!B}$$C^{\Sigma}$$S^{\Phi_{\\!B}}$$C^{\Omega}$
Figure 14: (Sifting $1/2$.) Using her private randomness $\Phi_{\\!A}$
together with the registers $\Omega$ and $\Phi_{\\!B}$ sent by Bob, Alice
computes the set $\Sigma$ when it exists and sets the value of the flag
$F^{\mathrm{si}}$. Both values are then publicly announced.

We then define a CPTP map $\mathcal{E}_{\mathrm{di}}$ that discards the
systems in $R$, $U$ and $\Phi_{\\!A}$ which do not correspond to the subset
$\Sigma$ and put the remaining systems in registers denoted $R^{\prime}$,
$U^{\prime}$ and $\Phi$ of size $m$, respectively.

$\displaystyle\mathcal{E}_{\mathrm{di}}:C^{\Sigma}RUS^{\Phi_{\\!A}}\to
R^{\prime}U^{\prime}C^{\Phi}C^{\Sigma}.$ (121)

This situation is depicted in Figure 15.

Alicepublic
domainBob$S$$\Sigma$$F^{\mathrm{si}}$$\Phi_{\\!A}$$\Phi$$\Phi$$R$$R^{\prime}$$S$$U$$\Sigma$$U^{\prime}$$\Phi_{\\!B}$$F^{\mathrm{si}}$$C^{\Omega}$$S$$C^{\Sigma}$$S^{\Phi_{\\!B}}$
Figure 15: (Sifting $2/2$.) Using $\Sigma$, Alice (resp. Bob) discards the
$M-m$ irrelevant systems of $R$ (resp. $U$) and stores the $m$ remaining ones
in $R^{\prime}$ (resp. $U^{\prime}$). Both Alice and Bob further compute
$\Phi$ from $\Sigma$ and either $\Phi_{\\!A}$ or $\Phi_{\\!B}$.

Finally, similarly as in the simple protocol of Part I, Alice and Bob use the
content of register $\Pi$ 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^{\Sigma}$, $C^{\Omega}$, $S^{\Phi_{\\!B}}$ and
$F^{\mathrm{si}}$ now available in the public domain.

Alicepublic
domainBob$S$$R^{\prime}$$\Phi$$V$$X$$S$$U^{\prime}$$W$$Y$$\Phi$$F^{\mathrm{si}}$$C^{\Omega}$$S$$C^{\Sigma}$$S^{\Phi_{\\!B}}$
Figure 16: (Reordering.) Using the content of $S^{\Pi}$, Alice reorder their
raw keys, $R^{\prime}$ and $U^{\prime}$, which become respectively $(X,V)$ and
$(Y,W)$.

##### 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
$\mathcal{N}_{A\to B}$ given to qkd_pmM,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 Part I, we define the security parameter

$\displaystyle\Delta_{M,\mathrm{si},\mathrm{pe},\mathrm{ec},\mathrm{pa}}:=\sup_{\mathcal{N}_{A\to
BE}}\Big{\|}\mbox{{{qkd\\_pm${}_{M,m,\mathrm{pe},\mathrm{ec},\mathrm{pa}}$}}}(\mathcal{N}_{A\to
BE})-\texttt{qkd\\_ideal}_{M,k,n,\delta,\mathrm{ec},\mathrm{pa}}(\mathcal{N}_{A\to
BE})\Big{\|}_{\mathrm{tr}},$ (122)

where again
$\texttt{qkd\\_ideal}_{M,k,n,\delta,\mathrm{si},\mathrm{ec},\mathrm{pa}}$ is
defined analogously to the entanglement-based case and simply replaces the
output of
$\mbox{{{qkd\\_pm${}_{M,m,\mathrm{pe},\mathrm{ec},\mathrm{pa}}$}}}(\mathcal{N}_{A\to
BE})$ with a perfect key in case the protocol does not abort. Here, the
channels $\mathcal{N}_{A\to BE}$ 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 $\rho_{AB}$ independent
from the uniformly distributed random seed $S^{\Phi}$ 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.