Finite-Key Analysis of Quantum Key Distribution with Characterized Devices Using Entropy Accumulation

Ian George^*
Institute for Quantum Computing and Department of Physics and Astronomy, University of Waterloo, Waterloo, Ontario N2L 3G1, Canada
Department of Electrical & Computer Engineering, University of Illinois, Urbana, Illinois 61801, USA

Jie Lin^*
Institute for Quantum Computing and Department of Physics and Astronomy, University of Waterloo, Waterloo, Ontario N2L 3G1, Canada

Thomas van Himbeeck^*
Institute for Quantum Computing and Department of Physics and Astronomy, University of Waterloo, Waterloo, Ontario N2L 3G1, Canada
Department of Electrical & Computer Engineering, University of Toronto, Toronto, Ontario M5S 3G4, Canada

Kun Fang
Institute for Quantum Computing and Department of Physics and Astronomy, University of Waterloo, Waterloo, Ontario N2L 3G1, Canada
Institute for Quantum Computing, Baidu Research, Beijing 100193, China

Norbert Lütkenhaus
Institute for Quantum Computing and Department of Physics and Astronomy, University of Waterloo, Waterloo, Ontario N2L 3G1, Canada

*These authors contributed equally to this workfootnote

The Entropy Accumulation Theorem (EAT) was introduced to significantly improve the finite-size rates for device-independent quantum information processing tasks such as device-independent quantum key distribution (QKD). A natural question would be whether it also improves the rates for device-dependent QKD. In this work, we provide an affirmative answer to this question. We present new tools for applying the EAT in the device-dependent setting. We present sufficient conditions for the Markov chain conditions to hold as well as general algorithms for constructing the needed min-tradeoff function. Utilizing Dupuis' recent privacy amplification without smoothing result, we improve the key rate by optimizing the sandwiched Rényi entropy directly rather than considering the traditional smooth min-entropy. We exemplify these new tools by considering several examples including the BB84 protocol with the qubit-based version and with a realistic parametric downconversion source, the six-state four-state protocol and a high-dimensional analog of the BB84 protocol.

§ INTRODUCTION

Quantum key distribution (QKD) protocols [Bennett and Brassard, 1984, Ekert, 1991]  enable two legitimate parties (Alice and Bob) to establish shared secret keys in the presence of any eavesdropper (Eve) who has control over the channel connecting the two parties and is only limited by the laws of quantum mechanics. That is, QKD protocols establish an information-theoretically secure shared secret key. The generated secret keys can be used in many cryptographic applications that our modern cybersecurity relies on, such as encryption and authentication. The field of QKD has grown rapidly in the last couple decades. Novel protocols have been proposed and analyzed (see [Scarani et al., 2009, Xu et al., 2020, Pirandola et al., 2020] for reviews). Many QKD experiments (e.g. [Boaron et al., 2018, Fang et al., 2020]) have been demonstrated to reach increasingly longer distances and/or to achieve higher key bits per second. The maturity of the field can be witnessed by development of commercial prototypes in several companies, successful launch of a QKD satellite in China [Liao et al., 2017], many ongoing efforts to launch QKD satellites from all over the world [Bedington et al., 2017], and developments of chip-based QKD systems [Sibson et al., 2017, Zhang et al., 2019, Wei et al., 2020].

While currently the field of implementation security (as opposed to protocol security), requiring certification procedures and security proofs with more refined models, captures an increasing amount of attention, there are still challenges to be addressed on the level of protocol security itself.  One major technical difficulty is guaranteeing security of the protocol when using finite resources. The security of a novel protocol is often first proved in the asymptotic key limit where Alice and Bob exchange infinitely many signals, since in that regime typically reduction to the identically and independently distributed (i.i.d.) assumption about the individual exchanged signals can be made and statistical fluctuations can be neglected. However, any realistic system can only exchange a finite number of signals. For example, the time interval of low orbiting satellites having line of sight to ground stations is limited to minutes, thus naturally limiting the total number of signals that can be exchanged. The study of security with finite resources is known as finite key analysis. In recent years, finite key analysis against general attacks has been performed for several QKD protocols. One aims to provide security proofs that allow one to generate the most key using the fewest signals and converge to the fundamental asymptotic limit quickly.

Over the past decade, several techniques have been proposed to bridge the gap between asymptotic security and finite key analysis against general attacks. The Quantum de Finetti theorem [Renner, 2005] was first used to achieve this task. While it makes no restrictions on the QKD protocol implemented, the key rate becomes very pessimistic at practical signal block size. The postselection technique [Christandl et al., 2009] was later presented to improve the key rate if the protocol is permutation invariant with respect to any input. Although it gives better performance, the key rate is believed to remain pessimistic as it scales exponentially in the dimension of Alice and Bob's signals. More recently, the entropy accumulation theorem [Dupuis et al., 2020, Dupuis and Fawzi, 2019] was developed to offer tighter finite key analysis. It has been successfully applied to prove the security of device-independent (DI) QKD protocols [Arnon-Friedman et al., 2018, Arnon-Friedman et al., 2019].

From the perspective of implementation security, DIQKD is favorable since it requires minimal assumptions on Alice and Bob's devices and thus is immune to most side-channel attacks. Thanks to the entropy accumulation theorem [Dupuis et al., 2020] and its application to DIQKD [Arnon-Friedman et al., 2018], the experimental requirements to implement DIQKD have become within reach of state-of-the-art technologies. Very recently, proof-of-principle experimental demonstrations of DIQKD with positive key rates are reported for extremely short distances [Nadlinger et al., 2021, Zhang et al., 2021, Liu et al., 2021]. Even if the transmission distance is extended to practical regimes in a near future, a DIQKD system is expected to be more costly since the experimental requirements are still demanding. In fact beyond the experimental requirements, it may be viewed as significantly more expensive simply because at best one must use a new system of devices each time one wishes to establish a key because DIQKD is not known to be universally composably secure [Barrett et al., 2013, Arnon-Friedman et al., 2019]. As such, while DIQKD has advantages for implementation security and can be implemented, at least over very short distances, device-dependent QKD (i.e. QKD with characterized devices) remains the more practical option at the moment.[We note that measurement-device-independent (MDI) QKD also falls in the category of device-dependent QKD since one still makes assumptions on both Alice's and Bob's devices.]

Beyond these limitations, as less assumptions are put on trusted parties' devices, DIQKD key rates are unavoidably lower than a standard device-dependent QKD protocol. On the other hand, with the best practice to countermeasure known side-channel attacks, suitable risk management and use cases, and efforts from standardization, device-dependent QKD remains a vital player for a wide adoption of QKD in the future. Therefore, it is still of great interest to provide as tight as possible key rates for device-dependent QKD. Our goal here is to apply the entropy accumulation theorem to provide better finite key rates of device-dependent QKD.

So far, the entropy accumulation theorem has not been applied to determine the key rate for any device-dependent QKD protocol.[In [Dupuis et al., 2020] the authors presented how the asymptotic rate was recovered for BB84, but did not present finite-size key lengths.] There are two major obstacles to overcome in applying EAT to device-dependent QKD. The first one is to guarantee the Markov condition is satisfied by the protocol. This condition in effect guarantees the protocol is well-behaved in what side-information is leaked to Eve during the protocol. This is an important aspect as device-dependent protocols often make use of announcing more information about each signal than DI protocols. In this work, we provide sufficient conditions for satisfying the Markov conditions of the EAT. Specifically, we prove that when Alice and Bob's announcements are determined by POVMs with a simple block-diagonal structure, then the protocol satisfies the Markov chain conditions (see <Ref>). This block-diagonal structure is satisfied for many practical discrete-variable QKD protocols. The second challenge is to have a general method to construct the required min-tradeoff function. This challenge has been addressed for the device-independent scenario in a recent work [Brown et al., 2021], but has not been addressed in the device-dependent scenario in which we have more structure of which to take advantage. We present a numerical method (with two algorithm variants) to construct tight min-tradeoff functions for device-dependent QKD protocols satisfying the above restrictions. The basic idea of one of the algorithm variants is similar to our existing numerical method for asymptotic key rates [Coles et al., 2016, Winick et al., 2018] and the other one which improves on the first one is based on the Fenchel duality. However, unlike the formulation of the objective function in Refs. [Coles et al., 2016, Winick et al., 2018], we present here a different formulation of the objective function for the optimization which has advantages in terms of dimension needed for the numerical optimization as well as a simpler representation of procedures to handle classical postprocessing. Using the guarantee of our numerical method constructing a min-tradeoff function, we present a general key length bound. It is largely similar to that of Ref. [Arnon-Friedman et al., 2018], but, building on the recent result that privacy amplification may be characterized using sandwiched Rényi entropies rather than the smooth min-entropy [Dupuis, 2021], we are able to show we can improve the key rate by optimizing over sandwiched Rényi entropies rather than using the smooth min-entropy bounds. We then apply our method to several examples. The first example is a simple qubit-based BB84 protocol and the second example is the entanglement-based six-state four-state protocol [Tannous et al., 2019]. We use these two examples to demonstrate behaviors of our algorithms. The third one is a high-dimensional analog of the BB84 protocols. We compare these results with the key rates obtained by the postselection technique [Christandl et al., 2009] to show that the EAT can outperform the postselection technique for high-dimensional signals. In the last example, we demonstrate that our method can also work for optical implementations of QKD and in particular, we study the entanglement-based BB84 protocol with a spontaneous parametric downconversion source in a lossy and noisy channel.

Our work here provides a first step along the direction of applying EAT to general device-dependent QKD protocols. Currently, we limit ourselves to entanglement-based protocols. To handle prepare-and-measure protocols, one needs to be able to incorporate the source-replacement scheme [Ferenczi and Lütkenhaus, 2012] into the EAT subprotocol and to be able to add a promise that Alice's reduced density operator is not affected by Eve's attacks. There remain technical challenges to do so. We leave this for future work.

The rest of the paper is organized as follows. In <Ref>, we summarize our notational conventions and in <Ref>, we review the security definition of QKD. In <Ref>, we review the entropy accumulation theorem and adapt the theorem to the device-dependent setting. We do this first in the case where side information is all seeded randomness, as was the case in previous works. We then provide sufficient conditions for satisfying the Markov chain conditions necessary to apply the EAT without relying on all side-information being randomly seeded. This is important as many device-dependent QKD protocols make announcements which depend on the outcome of the measurement. In <Ref>, we describe the generic protocol to which our method is applicable and also the assumptions on public announcements. In <Ref>, we then apply the EAT to this family of protocols and obtain a key length formula. In <Ref>, we discuss how to construct min-tradeoff functions numerically and present two numerical algorithms for obtaining a nearly tight min-tradeoff function. In <Ref>, we apply our method to several examples. We then conclude in <Ref>. We leave technical details to appendixes.

§ PRELIMINARIES

We discuss the notational convention and some useful definitions in <Ref>. We then review the security definition of QKD in <Ref>.

§.§ Notation

We briefly summarize the notation which we use throughout this work.

General notations     Descriptions

$A,B,C,\cdots$     Quantum systems and their associated Hilbert spaces

$|A|,|B|,|C|,\cdots$     Dimension of the Hilbert spaces

$A^n_1$     Shorthand for $A_1A_2 \cdots A_n$

$[n]$     The set of natural numbers from 1 to $n$

$\id$     Identity map

$f$     A min-tradeoff function

$\vect{f}$     A vector that is used to construct the min-tradeoff function $f$

$\vect{1}$     A vector of all ones

EAT statement     Descriptions

$P_i$     Public information in the EAT statement

$S_i$     Secret information in the EAT statement

$T_i$     Test flag variable

$X_i$     Test result register in the EAT statement

$E$     Eve's system

$\Omega$     An event

$\rho[\Omega]$     Probability of $\Omega \subset \cX$ for $\rho_{XA}$ (See main text in <Ref>)

$\freq$     Frequency of a given event

$\q$     A probability vector

$\PP(\cX)$     The probability vector space with events from $\cX$

$\mathrm{D}(A)$     The set of quantum states on Hilbert space $A$

Overview of notational conventions.

For consistency, we at times use the notation for quantum states conditioned on an event from previous works [Dupuis et al., 2020, Dupuis and Fawzi, 2019]. Let $\cX$ be a finite alphabet, $X \cong \mathbb{C}^{|\cX|}$. Then a classical-quantum (CQ) state may be written as $\rho_{XA} = \sum_{x \in \cX} \dyad{x} \otimes \rho_{A,x}$ where the quantum part of this decomposition is generally called the conditional state. Given an event $\Omega \subset \cX$, the probability of the event is $\rho[\Omega]$, which may be calculated by $\rho[\Omega]:= \sum_{x \in \Omega} \Tr[\rho_{A,x}]$. Lastly, the state conditioned on the event is given by $\rho_{XA|\Omega} = \frac{1}{\rho[\Omega]} \sum_{x \in \Omega} \rho_{A,x}$. Note that a conditioned state is therefore re-normalized.

We will also require various entropies which we also introduce here. We use the notation of [Dupuis et al., 2020, Dupuis and Fawzi, 2019]. We refer to [Tomamichel, 2016] for further background, but note that the notation differs in that work.

For $\alpha \in (0,1) \cup (1, \infty)$, define the minimal divergence by

\begin{align*}
D_{\alpha}(\rho||\sigma) :=
\begin{cases}
\frac{1}{\alpha-1} \log \frac{\|\sigma^{\frac{1-\alpha}{2\alpha}} \rho \sigma^{\frac{1-\alpha}{2\alpha}} \|^{\alpha}_{\alpha}}{\Tr(\rho)} & \text{ if }\alpha <1 \text{ or if } \alpha > 1\text{ and } \mathrm{supp}(\rho) \subseteq \mathrm{supp}(\sigma) \\
+\infty & \text{ otherwise}
\end{cases}\ ,
\end{align*}
where $\norm{\cdot}_p$ is the Schatten $p$-norm for $p \geq 1$ and the definition is extended to all $p >0$.
For any $\rho \in \mathrm{D}(A\otimes B)$, $\sigma \in \mathrm{D}(B)$, define
$$H_{\alpha}(\rho_{AB}||\sigma_{B}) := -D_{\alpha}(\rho_{AB}||\mathbb{1}_{A} \otimes \sigma_{B}) \, . $$

We then define
$H_{\alpha}(A|B)_{\rho_{AB}} := H_{\alpha}(\rho_{AB}||\rho_{B})$ and $H^{\uparrow}_{\alpha}(A|B)_{\rho} := \sup_{\sigma_{B}} -D_{\alpha}(\rho_{AB}|| \mathbb{1}_{A} \otimes \sigma_{B})$. We refer to both these classes of entropies as sandwiched Rényi entropies. We may also recall the smooth min-entropy defined by

$$ H^{\varepsilon}_{\min}(A|B)_{\rho_{AB}} := \underset{\tilde{\rho} \in \mathcal{B}^{\epsilon}(\rho_{AB})}{\max} H_{\min}(A|B)_{\tilde{\rho}} \ , $$

where $H_{\min}(A|B)_{\rho_{AB}} := -\log(\min \{\Tr(Y): \rho_{AB} \leq \mathbb{1}_{A} \otimes Y_{B} \ \})$, $\mathcal{B}^{\epsilon}(\rho_{AB}) := \{\tilde{\rho}_{AB} \geq 0 : \Tr(\tilde{\rho}_{AB}) \leq 1 \, \& \, P(\tilde{\rho}_{AB},\rho_{AB}) \leq \varepsilon \}$, and $P$ is the purified distance [Tomamichel, 2012, Tomamichel, 2016]. Throughout this work, $\log$ is referred to $\log_2$.

§.§ QKD security definition

We provide a short review of the $\ve$-security framework of QKD [Renner, 2005, Portmann and Renner, 2014]. A QKD protocol is $\ve$-secure if for any input state, the output state $\rho_{S_AS_BE}$ conditioned on that the protocol does not abort (and thus subnormalized) satisfies

1/2ρ_S_AS_BE-π_S_AS_Bρ_E_1 ≤  ,
where $\pi_{S_AS_B} = \sum_{s \in \cS}\frac{1}{\abs{\cS}}\dyad{s}\ox\dyad{s}$, and $\cS$ is the space of keys that could be generated from the protocol. The security parameter $\ve$ quantifies the amount of deviation of the real protocol from an ideal protocol. In an ideal QKD protocol, Alice and Bob are supposed to obtain an identical key, which is the correctness requirement; The key is supposed to be distributed from a uniform distribution among all possible keys and that Eve knows no information about the key, which is the secrecy requirement. This security definition in terms of trace distance has an operational interpretation: If a distinguisher is given either the real or the ideal protocol as a black box with an equal a priori probability and the goal is to verify which protocol the black box implements, then the probability that this distinguisher can guess correctly by looking at output states of the black box is at most $\frac{1}{2}(1+\ve)$. We note that in the case of aborting, both protocols output a trivial key symbol.

In <Ref>, we use subnormalized states. Equivalently, if we define in terms of normalized output states $\tilde{\rho}_{S_AS_BE} = \rho_{S_AS_BE}/\Tr(\rho_{S_AS_BE})$ and $\tilde{\rho}_E = \rho_E/\Tr(\rho_E)$ where $\Tr(\rho_{S_AS_BE}) = \Tr(\rho_E):=\Pr(\text{accept})$ denotes the probability that the protocol does not abort, then <Ref> can be written as

\begin{equation}\label{eq:security-scaled-by-accept}
\frac{1}{2}\Pr(\text{accept})\norm{\tilde{\rho}_{S_AS_BE}-\pi_{S_AS_B}\ox \tilde{\rho}_E}_1 \leq \ve \ .
\end{equation}

It is often convenient to discuss the secrecy requirement and correctness requirement separately since the correctness requirement is usually guaranteed by the error correction and error verification steps of a QKD protocol. A key is $\vSec$-secret if

1/2ρ_S_AE-π_S_Aρ_E_1 ≤  ,
where $\pi_{S_A} = \sum_{s \in \cS}\frac{1}{\abs{\cS}}\dyad{s}$. A QKD protocol is $\ve_{\text{cor}}$-correct if the joint probability that the protocol does not abort and that Bob's key is different from Alice's key is at most $\ve_{\text{cor}}$. By the triangle inequality of the trace norm, it is easy to see that if the QKD protocol is $\ve_{\text{cor}}$-correct and it generates $\vSec$-secret keys, then the protocol is $\ve$-secure with $\ve=\vSec +\ve_{\text{cor}}$.

§ THE ENTROPY ACCUMULATION THEOREM

porte = [draw=black!50, fill=black!20]
++(1, 0) node[porte] (m1) $\cM_1$
++(3, 0) node[porte] (m2) $\cM_2$
++(2, 0) node (dotdotdot) $\cdots$
++(2, 0) node[porte] (mn) $\cM_n$
(m1) ++(-1, -1.2) node (a1) $S_1$
(m1) ++(1, -1.2) node (b1) $P_1$
(m1) ++(0, -2.3) node (x1) $X_1$
(m2) ++(-1, -1.2) node (a2) $S_2$
(m2) ++(1, -1.2) node (b2) $P_2$
(m2) ++(0, -2.3) node (x2) $X_2$
(mn) ++(-1, -1.2) node (an) $S_n$
(mn) ++(1, -1.2) node (bn) $P_n$
(mn) ++(0, -2.3) node (xn) $X_n$
(x2) ++(0,-1) node (a)  EAT Process.
(m1) edge[->] (a1)
(m1) edge[->] (b1)
(m2) edge[->] (a2)
(m2) edge[->] (b2)
(mn) edge[->] (an)
(mn) edge[->] (bn)
(a1) edge[->, dotted] (x1)
(b1) edge[->, dotted] (x1)
(a2) edge[->, dotted] (x2)
(b2) edge[->, dotted] (x2)
(an) edge[->, dotted] (xn)
(bn) edge[->, dotted] (xn)
(m1) ++(-1.5, 0) edge[->] node[midway, above] $R_0$ (m1)
(m1) edge[->] node[midway, above] $R_1$ (m2)
(m2) edge[->] node[midway, above] $R_2$ (dotdotdot)
(dotdotdot) edge[->] node[midway, above] $R_{n-1}$ (mn)
(-0.5,0)  – (-1,0.5) – (-0.5,1) node[above,shift=(0.5,0)]  $E$ (-0.5,1) edge[->] (8.9,1);
[dashed,very thick] (-2.2,2.4) – (-2.2,-3);
(0.5, 0) node[porte] (mi) $\cM_i$
(mi) ++(-1, -1.2) node (ai) $S_i$
(mi) ++(1, -1.2) node (bi) $P_i $
(mi) ++(0, -2.3) node (xi) $X_i$
(xi) ++(0,-1) node (b) Single round.
(mi) ++(-1.5, 0) edge[->] node[midway, above] $R_{i-1}$ (mi)
(mi) edge[->] (ai)
(mi) edge[->] (bi)
(ai) edge[->, dotted] (xi)
(bi) edge[->, dotted] (xi)
(mi) edge[->] node[midway,above] $R_{i}$ (2,0)
(-1,0)  – (-1.5,0.5) – (-1,1) node[above,shift=(0.5,0)]  $R$ (-1,1) edge[->] (2,1)

Diagrammatic depiction of EAT process and theorem. (a) Captures the overall process and (b) is the process captured by the min-tradeoff function (See <Ref>). They are related by the Entropy Accumulation Theorem (<Ref>). Note that $\cM_{n}$ may be viewed as outputting a trivial register, $R_{n} \cong \mathbb{C}$, which we have suppressed. The output of the EAT process is $\rho_{S^{n}_{1}P^{n}_{1}X^{n}_{1}E}$, the output registers along with the purification.

In this section we review the Entropy Accumulation Theorem (EAT) [Dupuis et al., 2020, Dupuis and Fawzi, 2019] which is the unifying technical tool of this work. The EAT is motivated as follows. Fundamentally, the formal property of secrecy using a process with a finite number of rounds is characterized by the smooth min-entropy [Renner, 2005]. Unfortunately, the smooth min-entropy is a functional that is difficult to calculate directly for large systems. It therefore follows that one wishes to determine tight bounds on the smooth min-entropy of a given process via a reduction that is computationally feasible. The EAT accomplishes this task for well-behaved sequential processes. The idea of the EAT is that, under some reasonable behavior, one can bound the smooth min-entropy of the finite-length process by the worst-case accepted asymptotic behavior along with some correction terms.

However, in this work we find empirically that a recent work that characterizes secrecy using the sandwiched Rényi entropies $H^{\uparrow}_{\alpha}$ [Dupuis, 2021] can lead to improved key rates. As such, rather than presenting results in terms of smoothed entropies in the main text, we present them in terms of $H^{\uparrow}_{\alpha}$ entropies. For completeness and perhaps intuition, in Appendix <ref>, we present all results in terms of smooth entropies. We now present the formal statement of the EAT along with relevant definitions after which we elaborate on the intuition and relation to the rest of this work.

§.§ Formal statement

To formally state the EAT, we review some definitions first [Dupuis et al., 2020, Dupuis and Fawzi, 2019] (See <Ref> for a visualization).

EAT channels are Completely Positive Trace-Preserving (CPTP) maps
_i: R_i-1 →S_i P_i X_i R_i

where for all $i \in \{1,\cdots n\}$, $R_i$ are quantum systems (with $R_{n} \cong \mathbb{C}$ the trivial register) and where $S_i$, $P_i$, and $ X_i$ for $i\in \{1,\cdots n\}$ are classical systems taking values in $\cS, \cP$, and $\cX$ respectively.

Furthermore, we assume that $X_i$ is a deterministic function of $S_i$ and $P_i$. In other words, the EAT channels can be decomposed as
_i = _i ∘_i '

where $\cM_{i}': R_{i-1} \to S_{i} P_{i} R_{i}$ is some CPTP map and where $\cT_{i}:S_{i} P_{i} \to S_{i} P_{i}X_{i}$ is a classical operation assigning a value for $X_i$ as a function of $S_i$ and $P_i$ of the form

_i(W_S_i P_i) = ∑_s ∈,   p ∈ (Π_S_i,s Π_P_i,p) W_S_i P_i (Π_S_i,s Π_P_i,p) |t(s,p)⟩⟨t(s,p)|_X_i,
where $\{\Pi_{S_i, s}: s \in \cS\}$ and $\{\Pi_{P_i, p}: p \in \cP\}$ are families of mutually orthogonal projectors on $S_i$ and $P_i$, and the function $t : \cS \times \cP  \to \cX$ is a deterministic function.

In the above definition, the registers $S_{i}$ and $P_{i}$ stand for `secret' key registers and `public' announcement registers respectively as this will be the natural interpretations of these registers in the context of cryptography. The $X_{i}$ register is then a `testing' register which is a function of the secret and public registers. Note that we consider the particular case of classical systems $S_{i}$ and $P_{i}$, compared to [Dupuis et al., 2020, Dupuis and Fawzi, 2019, Dupuis, 2021] where they can be quantum, as this is sufficient for this work. The main idea of the EAT channels is that they can be composed such as in <Ref>, starting from an initial state $\rho_{R_{0}E}^0 \in \mathrm{D}(R_0\otimes E)$ and applying the EAT maps sequentially to produce the output state

\begin{align}\label{eq:outputStateForm}
\rho_{S^{n}_{1}P^{n}_{1}X^{n}_{1}E} = (\mathcal{M}_{n} \circ \cdots \circ \mathcal{M}_{1} \ox \id_{E})(\rho_{R_0E}^0)\,.
\end{align}

The most important restriction on this state is that we require it to satisfy the Markov chain conditions:

\begin{align} \label{eq:Markov_cond}
S_1^{i-1} \leftrightarrow P_1^{i-1}  E \leftrightarrow P_{i} \qquad \forall i \in \{1, \ldots, n\} \ ,
\end{align}
where one may recall a quantum Markov chain, denoted $A \leftrightarrow B \leftrightarrow C$, is a quantum state $\rho_{ABC}$ such that the conditional mutual information is zero, i.e. $I(A:C|B) = 0$.[There exist other characterizations of quantum Markov chains, though the characterization presented here is sufficient for our exposition. See [Sutter, 2018] for further information on quantum Markov chains.] It follows the Markov chain conditions are claims about the mutual information between the previous secret registers and the previous public registers (along with Eve's information) when conditioned on the current public announcement. The reason this is important to the proof of the theorem is that the Markovian behavior restriction guarantees that the process (defined by the sequential application of $\cM_{i}$) does not a priori destroy entropy being accumulated in the $S^{n}_{1}$ registers. It does this by guaranteeing that, for each $i \in [n]$, the public announcement in round $i$, $P_{i}$, is not correlated to the generated secret information of previous rounds, $S^{i-1}_{1}$, when we condition on the side information $E$ and all public announcements up to then $P_1^{i-1}$.

It is also perhaps useful to preemptively stress that the EAT channels do not have to be a model of the actual implementation, rather they only need to capture the same relationships between the output random variables $S^{n}_{1},P^{n}_{1}$ and $X^{n}_{1}$ as the actual implementation because the entropy only depends on the random variables. This insight is what allowed the EAT to be used for device-independent information processing where dimensions cannot be bounded.

An affine function $f$ on the space of probability distributions $\PP(\cX)=\{\vect{p} \in \mathbb{R}^{\abs{\cX}}:\vect{p}(x)\geq 0, \sum_x \vect{p}(x) = 1\}$ is called a min-tradeoff function for the EAT channel $\cM_i$ if it satisfies

\begin{align}\label{eqn:mintradeofffunction}
f(\vect{q}) \leq \min_{\nu \in \Sigma_i(\vect{q})} H(S_i|P_i R)_{\nu} \quad \forall \vect{q} \in \PP(\cX),
\end{align}

where the minimization is over the set of quantum states compatible with the statistics $\vect{q}$ that is defined as below:

\begin{align}\label{eq:minTF_seet}
\Sigma_i(\vect{q}):= \left\{\nu_{S_iP_iX_iR_iR} = (\cM_i \ox \id_{R})(\omega_{R_{i-1}R}): \omega \in \DM(R_{i-1}\ox R) \text{ and } \nu_{X_i} =\vect{q}\right\} \, ,
\end{align}

where $R$ is isomorphic to $R_{i-1}$.

Note that Ref. [Dupuis et al., 2020] considers affine functions. However, because of $\sum_x \vect{q}(x) = 1$, any affine function on $\PP(\cX)$ can be represented as a linear function. In particular, $f$ can be specified by a vector $\vect{f} \in \mbR^{\abs{\cX}}$, that is, $f(\vect{q})= \vect{f}\cdot \vect{q} := \sum_x \vect{f}(x) \vect{q}(x)$. We note that this is equivalent to an affine function since for an affine function $f'_0 + \vect{f'}\cdot \vect{q}$, one can define $\vect{f}(x) = \vect{f'}(x) + f'_0 \ \forall x \in \cX$ such that $f'_0 + \vect{f'}\cdot \vect{q} =\vect{f}\cdot \vect{q}$.

By <Ref>, the min-tradeoff function characterizes the minimum amount of (von Neumann) entropy of the secret information conditioned on the public information and quantum side-information (encoded as the register $R$) for all probability distributions on the testing register. This encapsulates the notion of the minimum von Neumann entropy being accumulated in a given round. For QKD security proofs, the min-tradeoff function can be seen as the term that bounds Eve's ignorance about the key in the asymptotic regime given by the Devetak-Winter formula [Devetak and Winter, 2005], and so the min-tradeoff function may be seen as determining the first-order term in a finite-size key distillation protocol.

With these considerations, we can state the EAT with its improved second order term [Dupuis and Fawzi, 2019].

Consider EAT channels $\cM_{1},...,\cM_{n}$ and their output $\rho_{S^{n}_{1}P^{n}_{1}X^{n}_{1}E}$ such that it satisfies the Markov conditions and $S_{i}$ is a classical register for all $i \in [n]$. Let $h \in \mathbb{R}$, $\alpha \in (1,2)$, and $f$ be a min-tradeoff function for $\cM_1,\dots,\cM_n$. Then, for any event $\Omega \subseteq \cX^n$ that implies $f(\freq{X_1^n}) \geqslant h$,[Following [Dupuis et al., 2020], we say an event $\Omega \subseteq \cX^{n}$ implies $f(\freq{X_{1}^n}) \geq h$ if for every $x^{n}_{1} \in \Omega$, $f(\freq{X_{1}^n}) \geq h$.]

\begin{align}
\label{eqn:eat-min} H_{\alpha}^{\uparrow}(S_1^n | P_1^n E)_{\rho_{|\Omega}} & > nh - n \frac{(\alpha-1)\ln 2}{2}V^{2} - \frac{\alpha}{\alpha-1} \log \frac{1}{\rho[\Omega]} - n(\alpha-1)^{2} K_{\alpha}
\end{align}

holds for

\begin{align}
V &= \sqrt{\Var{f}+2} + \log(2 d_{S}^{2}+1) \; \label{eq: EAT constant V} \\
K_\alpha &= \frac{1}{6(2-\alpha)^{3} \ln 2} 2^{(\alpha-1)(\log d_{S} + (\Max{f} - \MinSigma{{f}))}} \ln^{3} \left( 2^{\log d_{S} + (\Max{f} - \MinSigma{f})} + e^{2} \right) \label{eq: EAT constant Kalpha}
\end{align}

f    := max_q ∈() f(q),

f    := min_q ∈() f(q),

Min_Σ(f)    := min_q:Σ_i(q) ≠∅ f(q),

Var(f)    := max_q:Σ_i(q) ≠∅ ∑_x q(x)f(x)^2 - [ ∑_x q(x)f(x) ]^2
and $d_S = \max_{i\in [n]} |S_i|$ is the maximum dimension of the systems $S_i$.

Note that, beyond the Markov chain conditions, the EAT applying to a state depends on the event $\Omega \subseteq \cX^{n}$ implying $f(\freq{X^{n}_{1}})$. Letting $\cZ$ be a finite alphabet, if one is interested in an event $\Omega' \subseteq \cZ^{n} \times \cX^{n}$ that guarantees such an $\Omega$ (i.e. $\Pr[\Omega|\Omega'] = 1$ which denotes the probability of event $\Omega$ conditioned on event $\Omega'$) then, assuming the conditions for EAT held on generating $X^{n}_{1},S^{n}_{1},P^{n}_{1}$, the EAT will hold for $\rho_{X^{n}_{1}S^{n}_{1}P^{n}_{1}E|_{|\Omega'}}$. This has been used implicitly in previous works such as [Arnon-Friedman et al., 2018], but we stress it here for completeness as we also use it.

It is worth noting the above theorem from [Dupuis and Fawzi, 2019] is actually an improved version of the original EAT [Dupuis et al., 2020]. The improvement is in the the second-order term where the dependency on the gradient of the min-tradeoff function $f$ is eliminated, which for certain applications caused the second-order term to dominate. We note that for a specific choice of $\alpha$, one can write <Ref> in the form $H_{\alpha}^{\uparrow} >nh - O(\sqrt{n})$ [Dupuis and Fawzi, 2019] to clearly separate the first-order and second-order terms. However, we do not state it in this form because, while asymptotically optimal, to get the best finite size bounds we will optimize over the parameter $\alpha \in (1,2)$ as suggested in [Dupuis and Fawzi, 2019]. It is also noted that the exact from of the expression of $K_{\alpha}$ here uses the fact that $S_i$ is classical <cit.>.

§.§ Applying EAT to device-dependent QKD

§.§.§ Tensor product structure

As noted earlier, the EAT maps in general do not have to be the same maps as the actual process as long as they capture the same relationship between output random variables. In the case of device-independent information processing, this is necessary since one cannot describe the device itself. In contrast, for device-dependent QKD as we consider here, without loss of generality we can let the EAT maps model the guaranteed behavior of the device in each round. It then follows that the EAT maps act on separate quantum systems. Formally, if we let $(Q_i)_{i\in [n]}$ be $n$ quantum systems then we can consider the $n$ rounds of the QKD protocol as $n$ CPTP maps of the form

_i : Q_i →S_i P_i X_i   ,
each acting independently on its own $Q_i$ space. It follows that these maps can be expressed in the notation of the EAT theorem by defining the EAT channels $\cM_i: R_{i-1} \rightarrow S_i P_i X_i R_i$ as follows:

_i    = _i ⊗𝕀_Q_i+1^n
where $R_i = \bigotimes_{j=i+1}^n Q_j$ and $\id_{Q_{i+1}^n}$ is the identity map on the registers $Q_{i+1}^n$. In other words, at round $i$ the EAT channel $\cM_i$ effectively only acts on the system $Q_i$ to produce the outputs $S_i,P_i,$ and $X_i$, but not on the next systems $Q_{i+1}^n$.

By the fact that the outputs $S_i$ and $P_i$ are classical, we can make another simplification. In this case, the first requirement in <Ref> of the EAT channels boils down to the requirement that $X_i$ is obtained by applying a deterministic function on $S_i$ and $P_i$: $x_i = t(s_i,p_i)$. In typical QKD protocols, we can further assume this function is identical for all rounds. Under this assumption, the EAT channels are thus entirely defined by specifying the function $t$ and the POVM elements $\{M_{sp}\}_{s,p}$ such that

_i (ρ) = ∑_s,p (ρM_sp) |s,p⟩⟨_|S_iP_i ⊗|t(s,p)⟩⟨_|X_i
for all $\rho\in \mathrm D(Q_i)$. These POVM elements $\{M_{sp}\}_{s,p}$ are uniquely associated to $\widetilde\cM_i$ and satisfy $M_{sp}\geq 0$ and $\sum_{s,p} M_{sp}= \idm{}$.

Now that we have reduced the scope of the EAT theorem, we still have two challenges to solve. The first challenge is how  we can generate the best possible min-tradeoff function. The second is how we guarantee the Markov chain conditions in <Ref>.

§.§.§ Challenge 1: constructing optimal min-tradeoff functions

It is desirable to have a general procedure (applicable to many protocols) to construct min-tradeoff functions according to <Ref>. In addition to having valid min-tradeoff functions, we would like to find the best possible min-tradeoff function that can produce as tight key rates as possible for each signal block size when it is used in the EAT. In general, the construction of tight min-tradeoff functions is difficult. The difficulty arises from the non-trivial behavior of the conditional von Neumann entropy of the output state of a map (in this case the EAT channel) as a function of the resulting observations. We note that while for certain small-dimensional and theoretically simple QKD protocols, it may be possible to determine the optimal min-tradeoff function from uncertainty relations <cit.>, the analytic construction of min-tradeoff functions for generic device-dependent protocols is less straightforward, and thus it warrants a numerical method. This issue has also been recognized in the device-independent scenario and been addressed with its own numerical method [Brown et al., 2021]. In this work, we address this issue in the device-dependent setting and utilize additional structures of device-dependent QKD protocols. In <Ref>, we present two algorithms for numerically constructing (almost) tight min-tradeoff functions in the case where one knows the structure of the EAT channels.

§.§.§ Challenge 2: guaranteeing Markov chain conditions

The Markov chain conditions [<Ref>] put strong restrictions on the maps $\cM_i$'s that can be used with the EAT theorem. Roughly speaking, it states that, from the point of view of the adversary $E$, the process at round $j$ does not leak information about the secret register(s) $S_{i}$ of previous rounds $i < j$. In typical device-independent protocols, this restriction on the output state is in a sense trivially satisfied as all public announcements $P_{i}$, such as measurement settings, are independently seeded with random numbers. In other words, the probability distribution of the announcement $P_i$ does not depend on the state sent by Eve. Formally, if $\{p\}$ is the set of public announcements in round $i$ and there are $n$ rounds, then the Markov chain conditions trivially hold if $\Pr[p|\rho_i] = \Pr[p]$ $\forall \rho_i \in \mathrm{D}(Q_{i})$, $\forall i \in [n]$, i.e., the distribution over announcements is independent of the state being measured in each round.

However, one advantage of device-dependent QKD over device-independent QKD is its ability to have more complicated public announcement structures. One example is postselection on detection events in device-dependent QKD. Postselection implicitly requires an announcement. However, since the probability of a detection event depends on the state sent by Eve, the public announcement is not based on independently seeded randomness. A simple argument shows that this is potentially problematic, as it can lead to a violation of the Markov chain conditions, even when the EAT channels act on independent systems. This happens when Eve prepares a pure state $\ket{\phi}_{Q_1^nE} = \ket{\psi}_{Q_1^n}\otimes \ket{\psi'}_E$, entangled between different rounds but not with her quantum memory. In that case, there can be correlations between announcements in one round and the private key register in another round. This could potentially prevent us from applying the EAT even if Eve could only learn from the public announcement. We therefore prove in <Ref> that the following condition (<Ref>) still guarantees the Markov conditions hold for Eve's optimal attack, which is sufficient for applying the EAT (<Ref>). We state this result below as <Ref>.

Given some quantum-to-classical CPTP map $\mathcal W: Q \rightarrow SP$ which can be fully specified by a POVM $\{M_{sp}: s \in \cS, \ p \in \cP\}$, we say that the variable $P$ is weakly dependent (on the input state) when there exists a decomposition of the input space $Q$ into a direct sum of orthogonal subspaces $V^\lambda$, i.e., $Q = \bigoplus_\lambda V^\lambda$, such that

* the channel $\mathcal W$ is block diagonal along $V^\lambda$: i.e., its POVM elements are of the form $M_{sp} = {\bigoplus}_\lambda M_{sp}^{(\lambda)}$ with $M_{sp}^{(\lambda)}\in \mathcal L(V^{\lambda})$ acting on $V^\lambda$;

*  the probability of an announcement $P$ is the same for all states in a given subspace $V^\lambda$: i.e., there exist constants $c_{p,\lambda}$'s such that
Pr_P(p|ρ_λ) = c_p,λ   ,    for all ρ_λ ∈D(V^λ)

where $\mathrm{Pr}_P(p|\rho_\lambda) := \Tr[M_p \rho_\lambda]$ with $M_p = \sum_{s} M_{sp}$.

Note that item:weakly_dependent_b in the definition is equivalent to saying that for each $\lambda$ and $p$, $M_p^{(\lambda)} := \sum_s M_{sp}^{(\lambda)} = c_{p,\lambda}\idm_{V^\lambda}$ is proportional to the identity. This means that, equivalently, for any $\sigma \in Q$, $\Pr_{P}(p|\sigma) = c_{p,\lambda} \Tr[\Pi_{\lambda}\sigma\Pi_{\lambda}]$, where $\Pi_{\lambda}$ is the projector onto the subspace, i.e. the announcement only depends on a constant and the weight of the state on the subspace, which makes it `weakly' dependent on the state. For intuition, this is distinct from independently randomly seeded announcements where each announcement has POVM elements of the form $M_{p} = c_{p} \idm_{Q}$, which results in the announcement being independent on the state all together. Note the independently randomly seeded case trivially satisfies <Ref>, and so it is a (strictly) special case of weakly dependent announcements.

Here we state that the advantage of weakly dependent announcements is that they guarantee the EAT may be applied.

If the announcements $P_i$ of the CPTP maps $\widetilde \cM_i: Q_i \rightarrow S_iP_iX_i$ are weakly dependent, then the result of <Ref> may be applied to prove security.

We give a physical intuition why this theorem would hold and defer the proof to <Ref>. The POVM being of the block-diagonal form in <Ref> means the subspace information is knowable to Eve. This is because without loss of generality, Eve should send such block-diagonal states and so she knows the information by implementing a quantum nondemolition (QND) measurement that determines the subspace which she then stores in a secondary register. Indeed, this idea of Eve having an extra register with the subspace information is how this is proven in <Ref>.  We note equivalently that Eve's purification of such a block-diagonal state includes the subspace information and so it is knowable to Eve from the perspective of purification as well.

§ THE QUANTUM KEY DISTRIBUTION PROTOCOL

In this section we present the class of entanglement-based (EB) QKD protocols for which we prove security. At a high level, there are three related protocols: the  QKD protocol for physical implementations (<Ref>), its equivalent virtual QKD protocol (<Ref>) for security proof purposes, and the (also virtual) Entropy Accumulation subprotocol (<Ref>), referred to as the EAT subprotocol, to which we apply the EAT to derive a desired entropic bound. The virtual QKD protocol requires certain properties so that the EAT subprotocol can be applied to its analysis. Of particular importance is that the virtual QKD protocol can be thought of as acting sequentially, i.e. the signals are processed round by round, and that the announcements satisfy the Markov chain conditions in <Ref>. The necessary properties of the virtual QKD protocol impose necessary structures on the physical implementation of the protocol so that it is equivalent to the virtual QKD protocol.

§.§ Physical and virtual protocol description

In this section, we present the physical QKD protocol followed by the virtual QKD protocol to which it is equivalent.
Physical Device-Dependent Quantum Key Distribution Protocolprotocol]prot:physicalDDQKD

$\{M^{A}_{a}\}_a, \{M^{B}_{b}\}_b$     Alice and Bob's measurement devices (POVMs)

$ \mathbf{K} $      Subset of Alice and Bob's public announcements to be kept during sifting

$n \in \mathbb{N}_{+}$     Number of rounds

$\gamma \in (0,1]$     Probability of testing

$\mathcal{Q}$     Set of acceptable frequency distributions over $\cX$

For $i \in [n]$, do <Ref>:

* step]step:phys_transmission [0.5cm]0cm
State Transmission: A source (that may be under Eve's control) distributes a state $\rho_{Q_{i}}$ between Alice and Bob.

* step]step:phys_measurements
Alice and Bob implement their local POVMs $\{M_{a}^{A}\}_{a}$, $\{M_{b}^{B}\}_{b}$ to measure their respective halves of the state and record their outcomes.

* step]step:data_partitioning
Data Partition:
Alice partitions her data into (data that will eventually be) public $\widetilde{A}_{i}$ and (data that will stay) private $\overline{A}_{i}$. Likewise, Bob partitions his data into public $\widetilde{B}_{i}$ and private $\overline{B}_{i}$.

* step]step:phys_labeling[0.5cm]0cm
Testing Designation:
Alice randomly chooses $T_{i} \in \{0,1\}$ according to $\Pr(T_{i}=1) = \gamma$.

* step]step:phys_announcements Announcements: Alice and Bob announce their public data $\wt{A}^{n}_{1}$ and $\wt{B}^{n}_{1}$, respectively. Alice then announces $T^{n}_{1}$. For all $i \in [n]$ such that $T_{i} = 1$, Alice announces $\ol{A}_{i}$.

* step]step:phys_PE
Parameter Estimation:
For all $i \in [n]$, Bob computes $X^{n}_{1}$ according to $X_{i} = t(\overline{A}_{i}, \overline{B}_{i}, \widetilde{A}_{i}, \widetilde{B}_{i})$ if $T_{i}=1$ and $X_{i} = \perp$ otherwise, where $t$ is a deterministic function. Alice and Bob abort the protocol if $\freq{X^{n}_{1}} \not \in \mathcal{Q}$.

* step]step:phys_sifting
General Sifting:
If $(\widetilde{A}_{i},\widetilde{B}_{i},T_{i}) \in \mathbf{K}^{C} \times \{0\}$, Alice sets the $\overline{A}_{i} = \perp$.

* step]step:phys_keymap
Key Map: If $(\widetilde{A}_{i},\widetilde{B}_{i},T_{i}) \in \mathbf{K} \times \{0\}$, Alice updates $\overline{A}_{i} := f_{KM}(\overline{A}_{i},\widetilde{A}_i,\widetilde{B}_i)$ where $f_{KM}$ is the key map. This subset of rounds may be denoted as the register $\mathbf{Z}$, Alice's raw key.

* step]step:phys_ECError Correction & Detection: Using an error correction scheme, Alice and Bob communicate for Bob to construct his guess of Alice's raw key, $\mathbf{\widehat{{Z}}}$. He then uses a 2-universal hash function to send a hash of his guess to Alice. This detects if the correction worked. If it did not, they abort. Otherwise, they continue.

* step]step:phys_PAPrivacy Amplification: Using a family of 2-universal hash functions, Alice and Bob perform privacy amplification to achieve the desired secrecy.

A few remarks are necessary. First, we have implicitly required that the announcement structure of the protocol be round by round. This announcement structure is necessary to move to our virtual protocol as we need a protocol that is sequential for the majority of the steps. Second, we have required no announcements be made until all of the measurement data have been obtained. This is important as it avoids Eve altering her actions depending on announcements. This requirement makes the protocol equivalent to the one where Eve distributes the whole $n$-round state (for which she may hold a purification) at the beginning and then only gains additional information via Alice's and Bob's announcements. The latter will be the necessary structure for the virtual protocol. Third, we have required the function $t$ in <Ref> to be deterministic. This is a condition needed to apply the Entropy Accumulation Theorem [see <Ref>], but it does not seem limiting for standard protocols.

We note that requiring the testing be done round by round specifically differs from standard practice in device-dependent QKD security proofs [Renner, 2005] which perform fixed-length parameter estimation. Fixed-length parameter estimation is when, before the protocol is executed, it is decided that $m$ of the $n$ signals will be used for parameter estimation. Then, rather than having <Ref> of <Ref>, the protocol would include Alice uniformly choosing a bit string from the set of bit strings of length $n$ and Hamming weight $m$ which determines which rounds to test. This is not necessarily a large gap if one considers testing probability $\gamma$ such that $\gamma n = m$, as a Bernoulli variable converges to its mean quickly. However, for rigor, after proving the security of <Ref>, which is equivalent to the security of <Ref>, in <Ref>, we present how to convert statements of security on this probabilistic round-by-round testing protocol to statements of security on the fixed length testing protocol without introducing any looseness.

Lastly, we note that we need the extra assumption beyond being round by round that the announcements satisfy the Markov conditions. More technically, the announcement structure will have to be such that the virtual QKD protocol would satisfy the Markov chain conditions in <Ref> in the case that Alice did not announce her fine-grained data $\ol{A}_{i}$ when the round $i$ is a testing round, i.e., $T_{i} = 1$. Since Alice does announce her fine-grained data during testing rounds, we stress why this works preemptively. If Alice's fine-grained data $\ol{A}_{i}$ is announced publicly, it could threaten the Markov chain conditions by leaking too much information if Eve sends states that are correlated across rounds. However, this fine-grained data is needed by Bob to compute $X_{i}$ on testing rounds, so we require Alice to announce this data. We therefore need a way to address this. In the security proof, we start with the conditional entropy of Alice's raw key which, among other registers, is conditioned on Eve knowing the fine-grained data Alice announces during testing rounds. By applying entropic chain rules, we are able to convert to a conditional entropy term corresponding to the case in which Alice kept all fine-grained data private. In this case, the Markov conditions hold by restrictions on the announcement structure we require. The final technical issue is that physically $X_{i}$ needs to be computed using $\ol{A}_{i}$ and $\ol{B}_{i}$. It follows that if neither party has both registers, there is no physical process to compute $X_{i}$. However, this is not an issue as the EAT subprotocol is virtual (that is, there is no need to implement this protocol in practice) and only needs to generate the same (quantum) random variables as the real process. Therefore we construct a sequence of protocols where the security claim on the physical protocol holds by the equivalence to the security of the virtual protocol whose security relies on a virtual EAT subprotocol. We also note for intuition that there is a penalty to the key rate by announcing the $\ol{A}_{i}$ in the aforementioned chain rules, which is not a part of the virtual EAT subprotocol. We discuss the specific assumptions on the announcement structure to guarantee the Markov chain conditions hold in <Ref> after presenting the virtual QKD protocol.

We now present the virtual QKD protocol. Given the discussion above, we note that the difference from the physical QKD protocol is that announcements, sifting, generation of the test round data (but not aborting based on the test data), and the key map are all implemented round by round. Beyond this conversion of many steps to being performed sequentially, the virtual QKD protocol is the same as the physical one. This is what will allow the protocols to be equivalent.

Virtual Device-Dependent Quantum Key Distribution Protocolprotocol]prot:DDQKD

$\{M^{A}_{a}\}_a, \{M^{B}_{b}\}_b$     Alice and Bob's measurement devices (POVMs)

$ \mathbf{K} $      Subset of Alice and Bob's public announcements to be kept during sifting

$n \in \mathbb{N}_{+}$     Number of rounds

$\gamma \in (0,1]$     Probability of testing

$\mathcal{Q}$     Set of acceptable frequency distributions over $\cX$

* step]step:transmission State Transmission: Eve distributes the $n$ states, which may be entangled in an arbitrary manner, such that the total state is of the form $\rho_{Q_{1}^{n}E}$.

For $i \in [n]$, do <Ref>:

* step]step:measurements[0.5cm]0cm
Alice and Bob implement their local POVMs $\{M_{a}^{A}\}_{a}$, $\{M_{b}^{B}\}_{b}$ to measure their respective halves of the state and record their outcomes.

* step]step:announcement[0.5cm]0cm
Data Partition and Announcement: Alice partitions her data into public $\widetilde{A}_{i}$ and private $\overline{A}_{i}$. Likewise, Bob partitions his data into public $\widetilde{B}_{i}$ and private $\overline{B}_{i}$. Then they announce their public data.

* step]step:labeling[0.5cm]0cm
Testing Designation: Alice randomly chooses $T_{i} \in \{0,1\}$ according to $\Pr(T_{i}=1) = \gamma$.

* step]step:sifting[0.5cm]0cm General Sifting:
If $(\widetilde{A}_{i},\widetilde{B}_{i},T_{i}) \in \mathbf{K}^{C} \times \{0\}$, Alice sets the $\overline{A}_{i} = \perp$. Denote
$$\mathcal{S} = \{ i \in [n]: (\widetilde{A}_{i},\widetilde{B}_{i},T_{i}) \in \mathbf{K}^{C} \times \{0\} \} $$
so that $\overline{A}_{\mathcal{S}}$ denotes the registers of discarded rounds.

* step]step:keymap[0.5cm]0cm Key Map: If $(\widetilde{A}_{i},\widetilde{B}_{i},T_{i}) \in \mathbf{K} \times \{0\}$, Alice updates $\overline{A}_{i} := f_{KM}(\overline{A}_{i},\widetilde{A}_i,\widetilde{B}_i)$ where $f_{KM}$ is the key map. This subset of rounds may be denoted as the register $\mathbf{Z}$, Alice's raw key.

* step]step:test[0.5cm]0cm Statistical Tests:

* If $T_{i} = 1$, Alice announces $\overline{A}_{i}$ publicly. Using this, Bob generates $X_i$ using a deterministic function $t$ such that $X_{i} = t(\overline{A}_{i}, \overline{B}_{i}, \widetilde{A}_{i}, \widetilde{B}_{i})$.

* If $T_{i} = 0$, Bob sets $X_{i} = \perp$.

Denote $\cT = \{i \in [n]: T_{i} = 1\}$. Then the registers Alice announces are $\overline{A}_{\mathcal{\cT}}$.

* step]step:PEParameter Estimation: Alice and Bob abort the protocol if $\freq{X^{n}_{1}} \not \in \mathcal{Q}$.

* Error Correction and Parameter Estimation: Do <Ref> of <Ref>.

We note that both <Ref> assume Alice establishes the key. However, if Bob were to establish the key, this merely switches the roles of Alice and Bob in <Ref> and <Ref>. Thus, this setting is not a restriction. Furthermore, we emphasize we still require that testing be determined in a round-by-round manner as the EAT is an i.i.d. reduction for sequential processes, which was discussed earlier.

The only remaining assumption to make explicit is the ability to guarantee the Markov chain conditions hold from the announcement structure.

§.§ Assumptions on public announcements

To verify the applicability of the EAT for a given protocol, we need to verify that the conditions from <Ref> are satisfied. This puts some restrictions on the type of protocols that can be included in our security proof and more specifically on the type of announcements and postselection that we can do.

<Ref> says that the partitioned announcements can have some dependence on the state, but only in a limited way. It can only depend on the subspace $V^\lambda$ in which the state lies. The underlying reason for this is that for block diagonal measurements, we can assume without loss of generality that Eve sends a state $\rho_{Q_1^nE}$ where each state in register $Q_i$ is block diagonal and so she already holds that information in her purification. We therefore do not give her new information about the state by leaking $\wt{A}_i$ and $\wt{B}_i$. Recall that announcements being independent of the input state is a particular case of this setting as explained in <Ref>.

To summarize, we make the following assumption throughout this work, which guarantees we can apply <Ref> by <Ref> so long as we guarantee the conditions stated in Definition <ref> are satisfied.

The measurements and subsequent announcement structure of Alice and Bob guarantee that the partitioned data $\widetilde{A}_i$'s and $\wt{B}_i$'s are weakly dependent (<Ref>).

Example (optical discrete-variable protocols):

The generalization from independently seeded announcements to weakly dependent announcements is crucial in the case of discrete-variable protocols. In those protocols, we typically perform postselection in the case of loss to remove the no-detection events from the raw data. However, postselection implies that each party needs to publicly announce if they have a detection or not (in addition to announcing the basis choice for protocols like BB84). This announcement is potentially problematic because the detection probability depends on the state; i.e., states with more photons have a higher probability of being detected. However, we can use the fact that the measurements by single-photon detectors commute with the total photon number operators $N$. In other words, Alice's (or Bob's) optical space can be decomposed in subspaces, each of which has a given total photon number $n_a$ (or $n_b$), as $Q_A = \oplus_{n_a=0}^\infty V_A^{n_a}$ (or $Q_B = \oplus_{n_b=0}^\infty V_B^{n_b}$), and the measurement device's POVM elements are block diagonal along the subspaces $V^{n_a}_A$ (or $V^{n_b}_B$).

Let's take BB84 as an example. Assuming that the basis choice is independently seeded, we only need to verify that the probability of a detection is the same for all states with the given basis choice $x$ and the same total photon number $N_A=n_a$. That is, for each total photon number $n_a$ and basis choice $x$, there exists some constant $c_{x,n_a}$ such that the probability of detection conditioned on sending a state from the basis $x$ in the subspace $V^{n_a}_A$ is

Pr(detection  | x,ρ_n_a)= c_x,n_aρ_n_a ∈(V^n_a_A)   .
Likewise, we have a similar requirement for Bob's detectors. This requirement needs to hold for both Alice's and Bob's detectors.

We remark that this property holds for the BB84 passive-detection setup using identical (imperfect) single-photon detectors (See <Ref>).

§ SECURITY OF DEVICE-DEPENDENT QKD FROM EAT

In this section we present the security of the considered QKD protocols (<Ref>). We stress that our security proof is for coherent attacks. Recall <Ref> does not assume anything about the state distribution but guarantees announcements are after all measurements. It is therefore equivalent to <Ref> where $\rho_{Q_1^{n}E}$ is an arbitrary state and announcements are made round-by-round. Recall that for an i.i.d. collective attack,[Collective attacks are usually defined (e.g. [Scarani et al., 2009]) by assuming that Eve interacts with each signal with a new ancillary state using the same unitary operation (which also includes mixed-unitary channels). Under this definition, collective attacks and i.i.d. assumption can be treated as synonymous for many protocols (as long as the protocol structure allows for the i.i.d. behavior). Some authors seem to generalize the definition to allow time-dependent unitary operations to include, for example, channels with a slowly rotating reference frame. This generalized definition would be non-i.i.d. collective attacks. For this reason, we use the terminology of i.i.d. collective attacks to emphasize the i.i.d. assumption.] one would assume $\rho_{Q_{1}^{n}E} = \sigma_{QR}^{\otimes n}$ so that Eve sends $n$ copies of the state $\sigma_{Q}$ for which she holds a purification $\sigma_{QR}$ to Alice and Bob. However, we do not make this assumption here in the security proof.

§.§ Entropy rate of EAT process

As discussed previously, we aim to apply the EAT to analyze the virtual QKD protocol (<Ref>) which is equivalent to the physical QKD protocol (<Ref>) in terms of security. However, we cannot directly use the EAT to analyze the virtual protocol. Specifically, the QKD protocol only accumulates entropy[In the main text we consider the sandwiched Rényi entropy. In <Ref> we consider smooth min-entropy. In both cases the main point is that some entropic quantity accumulates, so we just use entropy without a qualifier to refer to both cases.] until parameter estimation. As such, our interest is in the entropy accumulated given some event passes, namely that parameter estimation passes. Therefore, the security proof is broken into two parts. First, one proves the entropy accumulation rate on a `subprotocol' that is nearly (for technical reasons) equivalent to that of <Ref> of <Ref>. After this, one proves the security of the virtual protocol by relating it back to the subprotocol. In this subsection, we present the EAT subprotocol (<Ref>) and its entropy accumulation rate. Then in the next subsection we present the secure key length of the QKD protocol (<Ref>). A similar proof for a device-independent QKD protocol was given in [Arnon-Friedman et al., 2018]. However, that proof relied on a particular structure of the protocol which simplifies the analysis but is not as general as the protocol we consider here. In particular, the parameter estimation was done on the error corrected bit string instead of on the raw measurement results, like we do here. This allows us to use all the available measurement information to bound the key rate.

Device-Dependent Entropy Accumulation Subprotocol protocol]prot:DDEA
Inputs: Same as <Ref>

Protocol: Run <Ref> of <Ref>, except in <Ref>, Bob assigns $\overline{B}_{i} = \perp$ (i.e. if $T_{i} = 0$, then $\overline{B}_{i} = \perp$), and in <Ref> Alice does not announce $\ol{A}_{i}$ when $T_{i} = 1$. Regardless, $X_{i} = t(\ol{A}_{i},\ol{B}_{i},\wt{A}_{i},\wt{B}_{i})$ can be calculated the same as before.

It is worth noting that in principle the EAT does not rely on knowing all of the steps of the protocol explicitly. It just requires the existence of EAT channels that output (quantum) random variables that are the same as the real process. This is why we are not concerned about $X_{i}$ being computed locally. Here we described the procedure per round largely the same as in <Ref>, because when we use our numerical algorithms to construct the min-tradeoff function (<Ref>), we use our knowledge of a way to implement the process to construct the EAT channels explicitly. We also note for this reason, this protocol can handle QKD protocols in which one party's public announcement is conditioned upon the other, so long as one can prove the resulting output random variables still satisfy the required Markov conditions.

With the protocol defined, we may use the EAT to bound the entropy accumulated. We first state the relabeling from the registers used in the EAT statement in <Ref> and ones used in <Ref>:

\begin{align*}
S_{i} &\leftrightarrow \overline{A}_{i} \overline{B}_{i} \\
P_{i} &\leftrightarrow \widetilde{A}_{i} \widetilde{B}_{i} T_{i} \\
X_{i} &\leftrightarrow X_{i} \\
Q_{i} &\leftrightarrow A_{i}B_i \\
R_{i} & \leftrightarrow R_i\\
E &\leftrightarrow E \ .
\end{align*}

With these conversions, we state the sandwiched Rényi  entropy rate of the entropy accumulation subprotocol (<Ref>).

Consider the entropy accumulation protocol defined in <Ref> and assume the <Ref> is satisfied. Let $\Omega = \{x^{n}_{1} \in \cX^{n}: \freq{x^{n}_{1}} \in \mathcal{Q}\}$ and $\rho$ be the output of the protocol. Let $h$ such that $f(\vect{q}) \geq h$ for all $\vect{q} \in \mathcal{Q}$ where $f$ is the min-tradeoff function generated by either <Ref> or <Ref>. Then for any $\vEA \in (0,1)$, either the protocol aborts with probability greater than $1-\vEA$, or

\begin{align}\label{eq:entropyRate}
H^{\uparrow}_{\beta}(\ol{A}^{n}_{1} \ol{B}^{n}_{1}| \widetilde{A}^{n}_{1} \widetilde{B}^{n}_{1} T^{n}_{1} E)_{\rho_{|\Omega}} > n h - n \frac{(\beta-1)\ln 2}{2}V^{2} - \frac{\beta}{\beta-1} \log \frac{1}{\vEA} - n(\beta-1)^{2} K_{\beta}
\end{align}

where $\beta \in (1,2)$ by <Ref>.

We simply check that everything we have done satisfies the requirements of EAT.

* As we assume the protocol satisfies <Ref> which implies that <Ref> holds for the protocol, the output state $\rho$ satisfies the Markov conditions in <Ref>.

* By our definition of how we compute the test register $X_{i}$, the testing map $\cT_{i}$ is of the form in <Ref> of <Ref>.

* By our construction of the min-tradeoff function (<Ref> or <Ref>), we have a min-tradeoff function and the value $h$ in the statement of the theorem above satisfies the requirements to be $h$ in the statement of <Ref>.

Thus we have satisfied the requirements of the EAT and can apply it.

The statement of <Ref> requires that either the EAT protocol aborts with a probability greater than $1-\vEA$ or else the entropy bound holds. In the language of Renner's PhD thesis [Renner, 2005], this theorem says either $\rho$ is $\vEA$-securely filtered by the EAT protocol or the entropy bound holds. This explains the replacement of the failure probability of parameter estimation, which appeared in Renner's original coherent-attack security proofs [Renner, 2005], with the term $\vEA$ in the statement of  $\ve$-security.

§.§ Security of QKD protocol

We can now present the key length for a QKD protocol using the EAT without introducing any smoothing. We note this depends on the construction of a max-tradeoff entropy accumulation theorem for the sandwiched Rényi entropy $H^{\uparrow}_{\delta}$, which we provide in <Ref>.

Consider any QKD protocol which follows <Ref> and satisfies <Ref>. Let $\vSec,\vEC,\vAcc \in (0,1]$ such that $\vAcc \geq \vSec + \vEC$. Let $h$ such that $f(\vect{q}) \geq h$ for all $\vect{q} \in \mathcal{Q}$ where $f$ is the min-tradeoff function generated by <Ref> or <Ref>.

Let $\beta \in (1,2)$, $\delta \in (1/2,1)$ and $\alpha = \frac{-\beta +\delta}{-1+2\delta-\beta\delta}$.
The QKD protocol is $\vAcc$-secure for key length

\begin{equation}\label{eq:KeyLength_without_smoothing}
\begin{aligned}
\ell \leq & n h - \leak_{\vEC} - n \frac{(\beta-1)\ln 2}{2}V^{2} - n(\beta-1)^{2} K_{\beta} - n\gamma\log|\mathcal{A} \times \mathcal{B}| \\
& \hspace{3mm}
+ \frac{\alpha}{\alpha - 1} \log(\vSec) + 1
\end{aligned}
\end{equation}

\begin{align*}
V &= \sqrt{\Var{f}+2} + \log(2 d_{S}^{2}+1) \\
K_\beta &= \frac{1}{6(2-\beta)^{3} \ln 2} 2^{(\beta-1)(\log d_{S} + \Max{f} - \MinSigma{{f})}} \ln^{3} \left( 2^{\log d_{S} + \Max{f} - \MinSigma{f}} + e^{2} \right)
\end{align*}

$\mathcal{A}$ and $\mathcal{B}$ are the alphabets of private outcomes for Alice's and Bob's announcements excluding the symbol $\perp$, respectively, $d_{S} = (|\cA|+1)(|\cB|+1)$, $\leak_{\vEC}$ is the amount of information leakage during the error correction step.

See <Ref>.

In the proof of <Ref> in <Ref> there is another parameter, $\eta$, to optimize over. At the end of the proof, we make a natural choice for this parameter. As a result, the parameter $\eta$ is not stated in the above theorem.

While not necessary, it seems natural to set $\vAcc = \vEC + \vSec$. As shown in the proof of <Ref>, the optimal choice of security parameters will always have $\vAcc \geq \vEC + \vSec$. In principle, one has no control over the input states, so it is necessary to prove the security for many states, which would require $\vAcc$ to be small. The scaling term of $\log(\vAcc)$ in the theorem is small unless $(\beta,\delta)$ is near $(2,1)$, which is clearly suboptimal as the $V$ and $K_{\beta}$ correction terms increase linearly and exponentially in $\beta$ respectively. Moreover, $\delta$ is effectively free as $\alpha \in [1,1.5]$ always. As such, it is reasonable to set $\vAcc = \vEC + \vSec$ as this results in the strongest security claim without changing $\vEC,\vSec$ and, one would expect, obtains similar key rates assuming $\vAcc,\vSec,\vEC$ were not originally significantly different orders.

As noted in <Ref>, by specific choice of parameters in using the EAT, the resulting bound on the entropy can scale as $nh - O(\sqrt{n})$. As such, with suitable choices of $\beta$ and $\delta$, <Ref> gives the the key length that scales as $\ell(n) \leq nh - \leak_{\vEC} - O(\sqrt{n})$. If the min-tradeoff function is chosen appropriately, the key rate will reach the asymptotic key rate in the infinite-key limit.

§.§.§ Fixed number of test rounds

We have just proven the security of <Ref> by proving the security of <Ref> with the help of entropy accumulation subprotocol (<Ref>). However, traditionally device-dependent QKD protocols use fixed-length testing instead of probabilistic round-by-round testing. This leaves us with two options. First, the device-dependent QKD protocol could be altered to do the parameter estimation round by round as is described in <Ref>. In this case, one can use the result of <Ref> directly. However, if one wishes to use <Ref> and apply it to QKD protocols with fixed-length testing, one must connect the failure probability of <Ref> to the failure probability of the device-dependent QKD protocol actually implemented. Here we state the relation between the two failure probabilities in the case that $T_{i}$ is an independent Bernoulli random variable (e.g. determined by seeded randomness). This can then be used to calculate secure key length using <Ref> for protocols with fixed-length testing as explained beneath the following theorem. In <Ref>, we present the derivation of this result. We note that, given the proof method, this result is exact rather than a bound.

Let $\rho^{in}_{Q_{1}^{n}E} \in \mathrm{D}(Q_1^{n}E)$ be the input to the protocol. Let $\rho^{out}$ denote the output of <Ref> but with fixed-length parameter estimation on the input state $\rho^{in}_{Q_{1}^{n}E}$. Let $\rho^{out}_{EAT}$ denote the output of the EAT protocol where for each round the probability of testing is $\gamma$. Let $\Omega$ be the event of not aborting on parameter estimation, which to be the same in both protocols, can only accept when there are $m$ tests. Then $\rho^{out}_{EAT}[\Omega] = 2^{-nh(\gamma)} \binom{n}{m}\rho^{out}[\Omega]$. Furthermore, $\rho^{out}_{|\Omega} = \rho^{out}_{EAT|\Omega}$. (See <Ref> to recall notation.)

See <Ref>.

In proving security, one wishes to consider the set of inputs $\rho^{in}$ which will be accepted except with probability $\ve$ in the testing. In EAT this probability is $\vEA$ and in fixed-length testing we will say this is $\vPE$. That is, one would like to consider the set of $\rho^{in}$ such that $\rho^{out}[\Omega] \geq \vEA$ (resp. $\vPE$). The above theorem tells us how the set of $\rho^{in}$ that satisfy these conditions changes when going between the considered fixed-length setting and probabilistic round-by-round testing. In other words, if one wishes to consider a protocol with a fixed-length testing that considers all input states that are not $\vPE$-filtered, it suffices to calculate the secure key length of the EAT with $\vEA = 2^{-nh(\gamma)} \binom{n}{m} \vPE$. As <Ref> is tight, this completely closes the gap in this setting. Note, however, that this approach does make the second-order term in <Ref> scale closer to that of the first-order term. That is, considering that $\log(\vBar \rho[\Omega])$ is replaced with $\log(\vBar \vEA)$ in applying <Ref> for  <Ref>, we see $\log( \vBar \rho^{out}_{EAT}[\Omega]) \geq \log(\vBar \vPE) + \log( \frac{e^2}{\sqrt{2\pi}} \sqrt{\gamma(1-\gamma)n})$, as is shown in <Ref>.[One may verify this is the appropriate direction of bound as we are interested in the $\delta$ term of <Ref>, and if $y \geq x$, then $n \beta - \sqrt{1-z-y} \geq n\beta - \sqrt{1-z-x}$, so the bound on the key length has only decreased.] This means that the correction term scales as $O(\sqrt{n}\log(\sqrt{n}))$ rather than $O(\sqrt{n})$, which may suggest this is not the ideal way to merge fixed-length testing and the ideas from EAT.

§ CONSTRUCTION OF (NEAR-)OPTIMAL MIN-TRADEOFF FUNCTIONS

The QKD key rates obtained by the EAT method crucially depend on the choice of min-tradeoff function. For any given block size, it is desirable to choose the min-tradeoff function that maximizes the key rate among all valid min-tradeoff functions. In the infinite-key limit, we would like to choose a min-tradeoff function such that the key rate obtained by the EAT method reproduces the expected asymptotic key rate. We also would like to make our method as general as possible so that it can be applied to a large family of protocols. Our framework can be used whenever the EAT maps have the specific tensor product form as explained in <Ref>. Our first approach is to use the numerical framework for asymptotic QKD rate calculation [Winick et al., 2018] to construct min-tradeoff functions (via a similar two-step procedure). As will be explained in depth later, the important observation here is that the dual problem of the linearization of the original optimization problem gives us the desired min-tradeoff functions. The linearization is a semidefinite program (SDP) and thus its dual problem can be efficiently solved. This method is conceptually simple and can give us a family of valid min-tradeoff functions. We then optimize the choice of min-tradeoff functions when we evaluate the key rate in the finite-key regime using this algorithm. On the other hand, the generation of each individual min-tradeoff function by this approach takes into account only the first-order information in the key rate expression. It is typically the case that the min-tradeoff function that gives the highest first-order term does not give the optimal finite-key rate when lower-order terms are included. This motivates us to derive the second algorithm that also considers the second-order terms. With the aid of Fenchel duality, we show that the second algorithm can also be written in terms of convex optimization.

As a starting point, we review the asymptotic key rate optimization formulation in [Winick et al., 2018]. We present our first algorithm that utilizes the essential idea of [Winick et al., 2018] in <Ref> and then discuss the second algorithm in <Ref>.

§.§ Review of asymptotic key rate optimization

To construct min-tradeoff functions, we establish the intimate relation that exists between the problem of generating a good min-tradeoff function for a given protocol and the problem of computing asymptotic key rates in QKD. It is shown [Winick et al., 2018, George et al., 2021] that the latter problem can be rewritten as a convex optimization problem. The main idea is that, given a map $\wt \cM_i: Q_i \rightarrow S_iP_iX_i$ (from an input quantum system to the key, public announcement and testing registers), the function $r_{\infty}(\vect{q})$ gives the worst-case conditional entropy compatible with the given statistics $\vect{q}$. Explicitly, it is the result of the following convex optimization problem:

r_∞() = _ρ_Q       W(ρ_Q)

[ρ_Q M_x] = (x)

ρ_Q ≥0
where the objective function
W(ρ_Q) := H(S_i|P_iR)__i ⊗𝕀_R(ρ_QR)

is defined as the conditional entropy of the state obtained by applying the map $\wt\cM_i \otimes \id_R$ to the state $\rho_{QR}$ which is a purification of $\rho_Q$, and the constraints come from the POVM elements $M_x := \sum_{s,p:t(s,p) = x} M_{sp}$ associated to the map $\Tr_{S_iP_i} \circ \wt \cM_{i}$. Here we use register $R$ to refer to Eve's register in a single round as depicted in <Ref>. The objective function can be written in terms of these POVM elements as <Ref> shows.

Let $\{M_{sp}: s, p\}$ be Alice and Bob's joint POVM which is regrouped according to the public information $p$ and the value of the final key $s$. Let $M_p = \sum_s M_{sp}$. Then for $\rho \in \DM(Q_i)$,

\begin{align}\label{eq:objective_conditional_entropy}
W(\rho)& = \sum_{s,p} H\left(\cK_{sp}(\rho)\right) - \sum_p H\left( \cK_p(\rho)\right)
\end{align}
where $\cK_{sp}(\rho) := K_{sp}\rho K_{sp}^\dagger$ with $K_{sp} = \sqrt{M_{sp}}$,  and $\cK_{p}(\rho) := K_{p}\rho K_{p}^\dagger$ with $K_{p} = \sqrt{M_{p}}$.

See <Ref>.

To solve the convex optimization problem in <Ref>, numerical algorithms typically require the gradient information of the objective function. The gradient of $W$ for $\rho > 0$ is given as

∇W(ρ)    = - ∑_s,p _sp^† (log_sp(ρ)) + ∑_p _p^†( log_p(ρ)),
where $\cK_{sp}^{\dagger}$ denotes the adjoint map of $\cK_{sp}$ and can be written as $\cK_{sp}^{\dagger}(\rho) := K_{sp}^{\dagger}\rho K_{sp}$. Similarly, $\cK_{p}^{\dagger}$ is the adjoint map of $\cK_{p}$. When $\rho$ is singular, this gradient is not well-defined. We can use the same perturbation technique used in [Winick et al., 2018] for the quantum relative entropy formulation to define the gradient for every $\rho \geq 0$. In particular, we denote the depolarizing channel with a depolarizing probability $p$ by $\cD_p$, which is defined as

_p(ρ) = (1-p) ρ+ p (ρ) /d   ,
where $d$ is the dimension of the Hilbert space relevant for $\rho$. We denote the perturbed version of the objective function as $W_{\epsilon}(\rho)$ with a perturbation $\epsilon$, which is defined as

\begin{align}\label{eq:perturbed_objective_function}
W_\epsilon(\rho)= \sum_{s,p} H\left(\cK^\epsilon_{sp}(\rho)\right) - \sum_p H\left( \cK^\epsilon_p(\rho)\right),
\end{align}
where $\cK^\epsilon_{sp} = \cD_{\epsilon} \circ \cK_{sp} $ and $\cK^\epsilon_{p} = \cD_{\epsilon} \circ \cK_p$. In <Ref>, we also discuss the continuity of our objective function under this small perturbation. In particular, we have

\begin{align}
\label{eq:continuity_bound}
|W(\rho) - W_\epsilon(\rho)| \leq \eta_\epsilon\quad \text{with} \quad \eta_\epsilon = (\abs{S}+1)\abs{P} \epsilon(d-1)\log \frac{d}{\epsilon(d-1)},
\end{align}
where $\abs{S}$ and $\abs{P}$ denote the size of alphabets for $S_i$ and $P_i$, respectively.

§.§ An algorithm derived from the asymptotic numerical optimization

<Ref> for finding a min-tradeoff function has the same spirit as the algorithm for finding the asymptotic key rate in Ref. [Winick et al., 2018]. We prove it provides a valid min-tradeoff function in <Ref>. In <Ref>, we show that each construction of min-tradeoff function gives us tight asymptotic key rate for the observed statistics $\vect{q}_0$ that we use in the construction.

Algorithm for constructing the min-tradeoff functions based on the asymptotic key rate method

$\vect{q}_0$     A given probability distribution in $\mbP(\cX)$

$\{M_x: x \in \cX\}$     Bipartite POVM used for testing

$\vect{y^\star}$     A vector in $\mbR^\abs{\cX}$ which defines a min-tradeoff function by $f_\epsilon(\vect{q}) := \langle \vect{q},\vect{y^\star}\rangle - \eta_\epsilon$.

* Consider the convex optimization  $r_\epsilon(\vect{q}_0) := \min_{\rho \in \Sigma_i(\vect{q}_0)} W_\epsilon(\rho)$ with the true optimal solution $\rho^{\text{opt}}$. Solve the optimization (e.g. by Frank-Wolfe algorithm) and obtain a near-optimal solution $\rho_\epsilon^{\star}$ with the perturbation error $\epsilon \in (0,1/(e(d-1))]$ determined by the algorithm.

* Let $W_{\epsilon}^{\text{lin}}(\rho):= W_\epsilon(\rho_\epsilon^\star) + \Tr [\nabla W_\epsilon(\rho_\epsilon^\star) \cdot (\rho - \rho_\epsilon^\star)]$ be the linearization of the function $W_\epsilon$ at the point $\rho_\epsilon^\star$. It can be equivalently written as

\begin{align}
\label{eq: algorithm tmp2}
W_{\epsilon}^{\text{lin}}(\rho) = \Tr[O_\epsilon\rho] \quad \text{with}\quad O_\epsilon:= \left(W_\epsilon(\rho_\epsilon^\star) - \Tr \big[\nabla W_\epsilon(\rho_\epsilon^\star) \cdot \rho_\epsilon^\star\big]\right) \idm +\nabla W_\epsilon(\rho_\epsilon^\star).
\end{align}

Since $W_\epsilon(\rho)$ is a convex function in $\rho$, we know that $W_{\epsilon}^{\text{lin}}(\rho) \leq W_\epsilon(\rho)$, $\forall \rho$, and $W_{\epsilon}^{\text{lin}}(\rho_\epsilon^\star) = W_\epsilon(\rho_\epsilon^\star)$.

* Consider the SDP $\min_{\rho \in \Sigma_i(\vect{q}_0)} W_{\epsilon}^{\text{lin}}(\rho)$ whose dual SDP is given by

\begin{align}\label{eq:EAT_algorithm_linearization}
\max_y\ \langle \vect{q}_0, \vect{y}\rangle \quad \text{subject to} \quad \sum_{x \in \cX} \vect{y}(x) M_x \leq O_\epsilon,\ \vect{y} \in \mbR^{\abs{\cX}}.
\end{align}

Solve the dual program and obtain an optimal solution $\vect{y^\star}$.

* Construct the min-tradeoff function by $f_\epsilon(\vect{q}) := \langle \vect{q},\vect{y^\star}\rangle - \eta_\epsilon$.

Note that the first term of $O_\epsilon$ in <Ref> always vanishes, i.e., $W_\epsilon(\rho_\epsilon^\star) - \Tr \big[\nabla W_\epsilon(\rho_\epsilon^\star) \cdot \rho_\epsilon^\star\big] = 0$ for any $\rho_\epsilon^\star$. This can be shown by expanding the definitions.

Let $\lambda_{\min}$ be the smallest eigenvalue of $O_\epsilon$. It follows that $(\lambda_{\min} - 1) \idm  < O_\epsilon$. Since $\sum_x M_x = \idm$, $(\lambda_{\min} - 1, \lambda_{\min} - 1, \cdots, \lambda_{\min} - 1)$ is a strictly feasible solution for <Ref>. As long as $\Sigma_i(\q_0)$ is non-empty, the Slater's condition is satisfied <cit.>. Thus, the strong duality holds for the SDP in <Ref>. This means that the dual problem in <Ref> gives the same optimal value as the primal problem which is $\min_{\rho \in \Sigma_i(\vect{q}_0)} W_{\epsilon}^{\text{lin}}(\rho)$.

Note that the min-tradeoff function constructed by <Ref> depends on the input choice of $\q_0 \in \PP(\cX)$. In the end we need to optimize over $\q_0$ to get the best key rate (similar to <cit.>).

In the following we show that the function constructed in <Ref> is indeed a valid min-tradeoff function.

Let $\epsilon \in (0,1/(e(d'-1))]$ and assume that $\sum_i \vect{y^\star}(i) \Gamma_i \leq O_\epsilon$ is satisfied. Then $f_\epsilon$ constructed from <Ref> is a valid min-tradeoff function.

To check whether $f_\epsilon$ is a valid min-tradeoff function, according to <Ref>, one needs to check that $f_\epsilon$ is an affine function and it satisfies <Ref>. It is clear that $f_\epsilon$ is a real-valued affine function by construction. It remains to check <Ref>. For any $\q \in \PP(\cX)$ and any $\rho\in \Sigma_i(\q)$, it holds

\begin{align}
f_\epsilon(\q)  =\<\q,\vect{y}^\star\> - \eta_\epsilon & = \sum_i \vect{y}^\star(i) \vect{q}(i) - \eta_\epsilon \\
& = \sum_i \vect{y}^\star(i) \Tr[\rho \Gamma_i] - \eta_\epsilon\\
& = \Tr \big[\big(\sum_i \vect{y}^\star(i) \Gamma_i \big) \rho\Big] - \eta_\epsilon\\
& \leq \Tr [O_\epsilon \rho] - \eta_\epsilon\\
& = W_{\epsilon}^{\lin}(\rho) - \eta_\epsilon\\
&  \leq W_\epsilon(\rho) - \eta_\epsilon\\
& \leq W(\rho),
\end{align}

where the second line follows by the assumption that $\rho \in \Sigma_i(\q)$, the third line follows by the linearity of trace, the fourth line follows by the assumption that $\vect{y}^\star$ satisfying the constraint $\sum_i \vect{y}^\star(i)  \Gamma_i \leq O_\epsilon$, the fifth line follows by definition of $W_{\epsilon}^{\lin}$, the sixth line follows as $W$ is a convex function and $W_{\epsilon}^{\lin}$ is a linearization of $W$, and the last line follows by the continuity bound in <Ref>. Minimizing over all $\rho \in \Sigma_i(\q)$, we have

\begin{align}
f_\epsilon(\q) \leq r(\q) := \min_{\rho \in \Sigma_i(\q)} W(\rho).
\end{align}

As this holds for any $\q \in \PP(\cX)$, we conclude that $f_\epsilon$ is a valid min-tradeoff function.

Let $\epsilon\in (0,1/(e(d'-1))]$ and assume that $\Sigma_i(\q_0)$ is non-empty and the first step of <Ref> is solved exactly, i.e., $\rho_\epsilon^\star = \rho^{\opt}$. Then $\lim_{\epsilon \to 0^+} f_\epsilon(\q_0) = r(\q_0)$.

Since $\rho_\epsilon^\star$ is the minimizer of $W_\epsilon$ over the convex set $\Sigma_i(\q_0)$, by <cit.>, we know that $\min_{\rho \in \Sigma_i(\q_0)} \Tr [\nabla W_\epsilon(\rho_\epsilon^\star) \cdot (\rho - \rho_\epsilon^\star)] = 0$. Thus $ \min_{\rho \in \Sigma_i(\q_0)} W_{\epsilon}^{\lin}(\rho) = W_\epsilon(\rho_\epsilon^\star) = r_\epsilon(\q_0)$. Moreover, since $\Sigma_i(\q_0)$ is non-empty, by <Ref> the strong duality of <Ref> holds. Then we have $f_\epsilon(\q_0) + \eta_\epsilon = \langle\q_0,\vect{y}^\star\rangle = \min_{\rho \in \Sigma_i(\q_0)} W_{\epsilon}^{\lin}(\rho) = r_\epsilon(\q_0)$. This implies $\lim_{\epsilon \to 0^+} f_\epsilon(\q_0) = \lim_{\epsilon \to 0^+} r_\epsilon(\q_0) = r(\q_0)$.

§.§ An alternative algorithm that uses second-order information

To apply <Ref> in the finite-key rate calculation, we need to optimize the choice of min-tradeoff functions by heuristically picking different starting points. As such, while the previous algorithm will reproduce the asymptotic key rate in the infinite-key limit, it may behave poorly in the small block-size regime if the optimization over the starting point $\vect{q}_0$ is not done properly. This limitation motivates us to design a new algorithm that considers the effect of the choice of min-tradeoff function on second-order correction terms when constructing the min-tradeoff function. While ideally we would look at the key length expression in <Ref> and collect all terms that depend on the choice of min-tradeoff function $f$ for our new objective function, this would involve an additional optimization over the choices of $\beta$ and $\delta$. This is because the terms $V$ and $K_{\beta}$ depend on both the min-tradeoff function $f$ and the choice of $\beta$, and there are constant terms that depend on both $\beta$ and $\delta$. In principle, one could optimize the min-tradeoff function $f$ and two parameters $\beta$ and $\delta$ simultaneously to obtain the best possible key rate. However, because such a joint optimization is challenging, we choose to consider a simpler scenario that we now explain.

As we will claim the Rényi entropy key length obtains better key lengths than the smooth min-entropy key length, we build an algorithm that should behave best for the smooth min-entropy key length, <Ref> [see <Ref>], which already has one fewer free parameters than in <Ref>. To simplify further, we follow [Dupuis and Fawzi, 2019] in fixing a specific choice of $\alpha$ that leads to a simplified statement of the EAT <cit.>. Again using the fact that $S_i$ is classical, and dividing relevant terms by the number of signals, $n$, we have the following candidate for the objective function to use to to generate a near-optimal min-tradeoff function:

(f):= f(q_0) - 1/√(n)c(f)-1/n c'(f),
where $c(f)$ and $c'(f)$ are defined as

c(f)    = √(2ln(2))[log(2d_S^2+1)+√(2+f)]√(1-2log(ρ[Ω])),

c'(f)    = 35[1-2log(ρ[Ω])]/[log(2d_S^2+1)+√(2+f)]^22^log(d_S) + f-fln^3(2^logd_S+f-f+e^2).

For a general min-tradeoff function $f$, $\Var{f}$ can be upper bounded by a function of $\Max{f}$ and $\Min{f}$ as

f ≤1/4[f-f]^2.
We note that in the application of EAT to security proofs of QKD protocols (see <Ref>), one replaces $\rho[\Omega]$ by $\vAcc$ and uses $\vBar/4$ in the place of $\vBar$. We also note while the term $c'(f)$ has a complicated dependence on the min-tradeoff function $f$, its contribution to the key rate is much smaller than the first two terms of <Ref> due to the $1/n$ dependence. Therefore, for simplicity of our method, we ignore the $c'(f)$ term in our objective function for the purpose of constructing min-tradeoff function. We make another simplification in the $c(f)$ term by dropping the term related to $\log(2d_S^2+1)$ since it does not depend on the min-tradeoff function. With all these simplifications, we would like to consider the following objective function:

(f)   := f(q_0) - 1/√(n)√(2ln(2))√(1-2log(/4))√(2+1/4[f-f]^2)

= f(q_0) - 2/√(n)√(ln(2))√(1-2log(/4))√(1+1/8[f-f]^2).
Since a min-tradeoff function $f$ can be fully specified by a vector $\vect{f}$, it is the case that $\Max{f} = \max(\vect{f}) := \max_x \vect{f}(x)$ and similarly, $\Min{f} = \min(\vect{f}) := \min_x \vect{f}(x)$ (see <Ref> for definitions). This leads to the following optimization problem

_f      f ·q_0  - c_0 √(1+ c_1^2 [max(f) - min(f)]^2)

∑_x f(x) (ρM_x) ≤W(ρ)   ∀ρ∈(Q_i),
where $c_0, c_1$ are two constants to be set for generality, and $\{M_x\}$ is the POVM used for testing. In particular, the set of values, $c_0 =2\sqrt{\ln2}\sqrt{1-2\log(\vAcc\vBar/4)}/ \sqrt{n}, c_1=\frac{1}{2\sqrt{2}}$, correspond to the optimization of <Ref>. We emphasize that in deriving this simplified expression, we have made a heuristic choice. As we will show later, any vector $\vect{f}$ returned by this optimization gives a valid min-tradeoff function. This means that our heuristic choice does not affect the correctness of a min-tradeoff function. However, it might give sub-optimal min-tradeoff functions that lead to looser key rates. We note that it is possible to make further improvements, particularly for optimizing the min-tradeoff function for <Ref>.

The reason that we introduce two constants $c_0$ and $c_1$ is to make our algorithm general enough to allow the construction of crossover min-tradeoff function (which is defined later in <Ref>) as well as the normal min-tradeoff function in the statements of EAT. If our algorithm is used to find a crossover min-tradeoff function $g$, which can be used to reconstruct a min-tradeoff function $f$ by <Ref>, then $\Var{f}$ is upper bounded by $ \frac{1}{\gamma}[\Max{g}-\Min{g}]^2$ according to <Ref>. Moreover, $g(\vect{q}') =f(\vect{q})$ for every $\vect{q} \in \PP(\cX)$, where $\vect{q}'$ is renormalized after removing the position corresponding to the $\perp$ symbol from $\vect{q}$. Thus, it is the case that the problem for finding a crossover min-tradeoff function still has the form of <Ref>. For crossover min-tradeoff functions, these two constants take the following values: $c_0 = 2\sqrt{\ln2}\sqrt{1-2\log(\vAcc\vBar/4)}/ \sqrt{n}$, $c_1 = 1/\sqrt{2\gamma}$.

The optimization problem in <Ref> has an infinite number of constraints that we cannot really handle since the constraint needs to be held for every density operator. However, we can use the Fenchel duality Fenchel duality(see <Ref>) to show it is the dual problem of some primal problem that we can actually solve. Let $\{M_x: x \in \cX\}$ denote the relevant bipartite POVM of a protocol. <Ref> presents a detailed derivation of the primal-dual problem relation including strong duality. The primal problem corresponding to <Ref> is

_ρ, ξ       W(ρ)  - √(c_0^2-[∑_xξ(x)]^2/(4c_1^2))

subject to         (ρ)=1

-ξ(x) ≤(ρM_x) - q_0(x)≤ξ(x)

∑_x ξ(x) ≤2c_0 c_1

ρ≥0  ,  ξ ∈^  .

We note that the primal problem in <Ref> is very similar to the primal problem in the asymptotic case in <Ref>, but the difference is that the state $\rho$ is not required to reproduce the statistics $\vect{q}_0$ exactly. Instead there is a penalty term in the objective function when $\Tr[\rho M_x] \neq \q_0(x)$ and the additional constraint ensures that the penalty term is well-defined. We also note that one may need to use the perturbed version of $W$. The same perturbation procedure used for <Ref> is applicable here for the function $W$. For simplicity of the presentation, we ignore the perturbation here.

To solve the primal problem in <Ref>, it is often useful to use the gradient information. As the gradient of $W(\rho)$ is already discussed in the previous algorithm (including necessary perturbation), we just write the derivative of $\sqrt{c_0^2-\Big[\sum_{j}\vect{\xi}(j)\Big]^2/(4c_1^2)}$ with respect to $\vect{\xi}(k)$ here as

∂/∂ξ(k) √(c_0^2-(∑_jξ(j))^2/(4c_1^2)) = -1/4 c_0^2 c_1^2 1/√(1-[∑_j ξ(j)]^2/(4c_0^2c_1^2)) ∑_j ξ(j)  .

We can follow a similar two-step procedure as in [Winick et al., 2018] to solve the primal problem in <Ref>. In the first step, we try to obtain a near-optimal solution $\rho^\star$ and in the second step, we solve the dual problem of the linearization of the objective function at the point $\rho^\star$. The dual problem of the linearization at a point $\rho^\star \in \DM(Q_i)$ is

_f       f   ·q_0 -  c_0 √(1+ c_1^2 [max(f) - min(f)]^2)

∑_x f(x) M_x ≤∇W(ρ^⋆)  .
We rewrite this problem as an SDP by introducing slack variables $u, v, t$:

_f,u,v,t       f ·q_0  -t

∑_x f(x) M_x ≤∇W(ρ^⋆)

v1 ≤f ≤u1

t- c_0     c_0c_1(u-v)

c_0c_1(u-v)     t+c_0
≥0  .

We now present our second algorithm for constructing min-tradeoff function in <Ref>.
The second algorithm for constructing min-tradeoff functions

$\vect{q}_0$     A given probability distribution in $\mbP(\cX)$

$c_0, c_1$     Two constants related to the EAT correction terms

$\{M_x: x \in \cX\}$     Bipartite POVM used for testing

$\vect{y^\star}$     A vector in $\mbR^\abs{\cX}$ which defines a min-tradeoff function by $f(\vect{q}) := \langle \vect{q},\vect{y^\star}\rangle $.

* Use either the Frank-Wolfe method or an interior-point method to solve <Ref> and obtain a nearly optimal solution $\rho^\star$.

* Solve the dual SDP problem of the linearization at the point $\rho^\star$ in <Ref> to obtain $\vect{y}^\star=\vect{f}$.

Our next task is to show that <Ref> constructs a valid min-tradeoff function.

Assuming that $\sum_{x} \vect{f}(x) M_{x} \leq \nabla W(\rho^\star)$ is satisfied, the min-tradeoff function $f$ constructed from $\vect{f} = \vect{y}^\star$ returned by <Ref> is a valid min-tradeoff function.

From the assumption  $\sum_{x} \vect{f}(x) M_{x} \leq \nabla W(\rho^\star)$, it follows that for any $\rho \in \DM(Q_i)$,

∑_x f(x) (ρM_x) ≤(ρ∇W(ρ^⋆)) ≤W(ρ),
where the last inequality follows from the linearization of the function $W$ at the point $\rho^\star$ since $W$ is a convex function. We note that this is exactly the condition for a valid min-tradeoff function since the left-hand side is the min-tradeoff function evaluated at the statistics produced by a state $\rho$ and the right-hand side is the conditional entropy evaluated at the state $\rho$. As this inequality is true for any state, it follows that $f(\vect{q}) \leq \min_{\nu \in \Sigma_i(\vect{q})}H(S_i|P_iR)_{\nu}$ for every $\vect{q} \in \mbP(\cX)$ such that $\Sigma_i(\vect{q}) \neq \emptyset$. We also note that if  $\Sigma_i(\vect{q}) = \emptyset$, the minimum on the right-hand side of <Ref> is defined as $\infty$ [Dupuis et al., 2020] so that $f(\vect{q}) \leq \min_{\nu \in \Sigma_i(\vect{q})}H(S_i|P_iR)_{\nu} = \infty$ is still satisfied in this case.

Due to the numerical precision of any solver, $\sum_{x} \vect{f}(x) M_{x} \leq \nabla W(\rho^\star)$ may not be exactly satisfied. In implementation, we relax this constraint by  $\sum_{x} \vect{f}(x) M_{x} + \epsilon \idm \leq \nabla W(\rho^\star)$ for some small $\epsilon$ that is slightly larger than the solver precision. By doing so, we make the value $f(\vect{q})$ smaller than it could be if there were no numerical precision issue. Thus, the correctness is guaranteed even when one takes into account of the numerical precision.

By taking into account some second-order correction terms in the objective function, as we will see later, <Ref> can produce similar or better key rates than <Ref> without optimizing the initial choice of $\vect{q}_0 \in \PP(\cX)$, which can save computational time. Moreover, it is also possible to optimize the choice of $\vect{q}_0$ with this algorithm and choose the best one among all selected choices of $\vect{q}_0$. In addition, as we mentioned previously, this algorithm can be further improved since we made several simplifications and ignored some second-order correction terms. While it is possible to do so, adding back more terms will definitely make the optimization problem more complicated and thus a more sophisticated problem formulation is potentially needed. We leave any potential improvement for a future work.

§.§ Crossover min-tradeoff function

In practice, the number of testing rounds is typically chosen to be a small fraction of the total signals sent in the QKD protocol. When the number of test rounds becomes sufficiently smaller than the total number of signals, the original version of the EAT (<Ref>) is generally dominated by the second-order term because it scales inversely with the testing probability $\gamma$. A solution for this issue is given in Ref. [Dupuis and Fawzi, 2019], where authors of [Dupuis and Fawzi, 2019] present the `crossover min-tradeoff function', which may be used to induce a proper min-tradeoff function that does not generally become dominated by the second-order term when testing probability $\gamma$ is small. For this reason, it is often advantageous to construct the crossover min-tradeoff function first and then reconstruct a normal min-tradeoff function from the crossover version. We review the definitions from [Dupuis and Fawzi, 2019] for completeness of our presentation and refer to <cit.> for further discussion.

A channel with testing probability $\gamma \in [0,1]$ is an EAT channel $\cM_{i,Q_i\to S_iP_iX_i}$ such that $\cX = \cX' \cup \{\perp\}$ and that can be expressed as

\begin{align}
\cM_{i,Q_i\to S_iP_iX_i}(\cdot) = \gamma \cM_{i,Q_i\to S_iP_iX_i}^{\testround}(\cdot) + (1-\gamma) \cM_{i,Q_i\to S_iP_i}^{\genround}(\cdot) \ox \ketbra{\perp}{\perp}_{X_i},
\end{align}

where $\cM_i^{\testround}$ never outputs the symbol $\perp$ on $X_i$.

In our case $\M^{\gen}_{i,Q_i \rightarrow S_iP_i}$
is given by the protocol description where $S_i = \overline A_i$ and $P_i = \tA_i\tB_i$.
The testing map $\M^{\testround}_{i,Q_i\rightarrow S_iP_iX_i}$ is given by $S_i = \ol{A}_i\ol{B}_i$ and $P_i = \wt{A}_{i}\wt{B}_{i}$ as per <Ref>.

Let $\cM_i$ be a channel with testing probability $\gamma$ as defined above. The crossover min-tradeoff function for $\cM_{i}$ is an affine function $g: \PP(\cX') \to \mathbb{R}$ satisfying

\begin{align}
\label{eq: definition of crossover min tradeoff function}
g(\vect{q}') \leq \min_{\nu \in \Sigma_i'(\vect{q}')} H(S_i|P_iR)_{\nu} \quad \forall \vect{q}' \in \PP(\cX'),
\end{align}

where the set of quantum states

\begin{align}
\Sigma_i'(\vect{q}'):= \left\{\nu_{S_iP_iX_iR} = (\cM_i \ox \id_{R})(\omega_{Q_{i}R}): \omega \in \DM(Q_{i}\ox R) \, \& \, [(\cM_i^{\testround} \ox \cI_{R})(\omega_{Q_iR})]_{X_i} = \vect{q}'\right\}.
\end{align}

We note that the difference between the crossover min-tradeoff function and the original min-tradeoff function defined in <Ref> is that we only require the testing rounds to give the correct frequency distribution.

For each $x \in \cX$, let $\delta_{x} \in \PP(\cX)$ denote the frequency distribution with $\delta_x(x)=1$ and $\delta_x(x') = 0$ for all other $x' \in \cX$ such that $x' \neq x$. The crossover min-tradeoff function $g$ automatically defines a min-tradeoff function $f: \PP(\cX) \to \mathbb{R}$ by [Dupuis and Fawzi, 2019]:

\begin{align}\label{eq:crossover_to_normal_min_tradeoff_1}
f(\delta_x) & = \Max{g} + \frac{1}{\gamma} [g(\delta_x) - \Max{g}] \qquad \forall x \in \cX'\\
f(\delta_{\perp}) & = \Max{g} \, . \label{eq:crossover_to_normal_min_tradeoff_2}
\end{align}

Moreover, we have the relations [Dupuis and Fawzi, 2019]:

\begin{align}
\Max{f} & = \Max{g} \label{eq: min crossover min relation 1}\\
\Min{f} & = (1-\frac{1}{\gamma}) \Max{g} + \frac{1}{\gamma} \Min{g} \label{eq: min crossover min relation 2}\\
\MinSigma{f} & \geq \Min{g} \label{eq: min crossover min relation 3}\\
\Var{f} & \leq \frac{1}{\gamma} [\Max{g}-\Min{g}]^2.\label{eq: min crossover min relation 4}
\end{align}

§.§ Procedure for key rate calculation

We now provide an instruction for the finite-key length $\ell$ calculation using <Ref> and <Ref>.

* We first pick a frequency distribution $\vect{q}_0$ and then apply <Ref> to construct a crossover min-tradeoff function $g$. By solving the dual SDP of the linearized problem, the algorithm returns us a list of dual variables, which are coefficients of the min-tradeoff function $g$.

* We construct the min-tradeoff function $f$ needed for EAT by <Ref> and <Ref>, and then compute $\min_{\vect{q} \in \mathcal{Q}} f(\vect{q})$ to get the first-order term $h$.

* We evaluate $\Max{g}$, $\Min{g}$ by simply taking the max and min of coefficients.

* We apply <Ref> with the relations in <Ref> to obtain a lower bound. To do so, we optimize the choice of $\beta$ and $\delta$ in <Ref> using MATLAB built-in fmincon function. This optimization gives us the optimal second-order correction terms for the given choice of min-tradeoff function.

* We repeat this process with a different frequency distribution $\vect{q}_0$ to generate a different min-tradeoff function. We optimize the choice of min-tradeoff functions in a simple heuristic way by picking several different $\vect{q}_0$'s.

Similarly, we can use <Ref> and <Ref>. The procedure is similar to the above except that we do not need to optimize the initial choice $\vect{q}_0$ (although one can still do it if it can give a better choice of the min-tradeoff functions). To apply <Ref>, we also have a similar procedure except that we optimize the choice of $\alpha$ in the statement of <Ref> with MATLAB built-in fminbnd function.

§ EXAMPLES

We first present examples with announcements based on only seeded randomness and then consider an example with more sophisticated announcements. In the first example, we apply our method to the entanglement-based BB84 protocol with an ideal entangled photon source. In the second example, we provide a finite key analysis of six-state four-state protocol [Tannous et al., 2019]. We use both these two examples to demonstrate the effectiveness of our method, compare performances of two algorithms and compare two versions of the EAT (smoothed min-entropy versus sandwiched Rényi entropy). In the third example, we then show the key rates of high-dimensional  protocols with two mutually unbiased bases (MUBs), i.e. analogs of BB84 using qudit systems. We show that for these protocols the Entropy Accumulation Theorem can outperform the postselection technique [Christandl et al., 2009]. In the last example, we show the key rates of the entanglement-based BB84 with a realistic entangled photon source.

In all examples, for the purpose of illustration, we set the overall security parameter to be $\vAcc = 10^{-8}$. To do so, we set $\vSec =\frac{2}{3} \times 10^{-8}$ and $\vEC =  \frac{1}{3} \times 10^{-8}$ in the application of <Ref> and set $\vBar=\vPA=\vEC = \frac{1}{3} \times 10^{-8}$. In the case of postselection technique, we evenly distribute the overall security parameter $\ve$ among all contributing factors. We note that it is possible to perform an optimization over the individual security parameters. However, the results would be similar. For the simplicity of calculation, we fix the choice. We also remark that our implementation allows us to define the acceptance set $\Q$ (see <Ref>) as $\Q = \{F\in \mbP(\cX) : \norm{F-\bar{F}}_1 \leq \xi_t \}$, where $\bar{F}$ is the expected frequency distribution in an honest implementation and $\xi_t$ is the acceptance threshold. Key rates for small $\xi_t$'s drop (but insignificantly) compared to the case with $\xi_t=0$. In all plots presented here, to illustrate main ideas without complicating the calculation, we choose $\xi_t=0$; that is, $\Q$ contains a single frequency distribution. To estimate the cost of error correction $\leak_{\vEC}$, we set $\leak_{\vEC}=n f_{\EC}H(Z|\hat{Z}) + \log(2/\vEC)$, where $f_{\EC}$ is the inefficiency of an error correction code and $H(Z|\hat{Z})$ is the von Neumann entropy of Alice's key (in a single round) conditioned on Bob's guess $\hat{Z}$. In the simulation, we set $f_{\EC} = 1.16$ for all examples.

We highlight that we optimize both $\beta$ and $\delta$ in the statement of <Ref> when we use the key-length expression from this theorem. Similarly, we optimize the choice of $\alpha$ in the statement of <Ref> when using it. As discussed previously, this optimization is done with Matlab's fmincon function for the former case and fminbnd function for the latter case.

§.§ Qubit-based BB84

We apply our method to analyze a simple entanglement-based BB84 example based on the qubit implementation to compare different EAT statements and two algorithm variants for the construction of min-tradeoff functions. We assume that Alice's system and Bob's system are qubits and do not consider loss for this example.

§.§.§ Protocol description and simulation

We consider the following setup for this protocol:

(1) Alice chooses the $Z$ basis with a probability $p_z$ and the $X$ basis with a probability $1-p_z$. Bob chooses to measure in the $Z$ basis with a probability $p_z$ and in $X$ basis with a probability $1-p_z$.

(2) Key-generation rounds are where they both choose $Z$ basis. The testing rounds are where they both choose $X$ basis. They discard rounds with mismatched basis choices.

(3) They perform parameter estimation before error correction. For parameter estimation, we use the phase error POVM $\{E_X, \idm-E_X\}$ where $E_X$ is the $X$-basis error operator. This corresponds to statistics $\{e_x, 1-e_x\}$ where $e_x$ is the $X$-basis error rate.

We note that in this protocol setup, the testing probability $\gamma$ is given by the probability that both Alice and Bob choose the $X$ basis, that is, $\gamma = (1-p_z)^2$. The sifting factor for the key rate is $p_z^2$. We consider an efficient version of BB84 [Lo et al., 2005] by choosing $p_z$ to be close to $1$. This also corresponds to infrequent testing in our setup. We remark that since basis choices are made based on seeded random numbers and they are chosen independently in each round, their announcements trivially satisfy the Markov condition.

In our simulation, we use the depolarizing channel to model noises. The simulated state that we use to calculate the observed statistics is

\begin{equation}\label{eq:rho_sim_dp}
\begin{aligned}
\rho^{\text{sim}} = (1-\frac{3}{2}Q) \dyad{\Phi^+}{\Phi^+} + \frac{Q}{2}(\dyad{\Phi^-}{\Phi^-}+\dyad{\Psi^+}{\Psi^+} + \dyad{\Psi^-}{\Psi^-}),
\end{aligned}
\end{equation}
where $\ket{\Phi^+}, \ket{\Phi^-},\ket{\Psi^+}$ and $\ket{\Psi^-}$ are Bell states, and $Q$ is the quantum bit error rate. The statistics $\vect{q}_0$ that we need to give as an input to the min-tradeoff function construction algorithm is then given by $\vect{q}_0(j) = \Tr(\rho^{\text{sim}}M_j)$ for Alice and Bob's joint POVM $\{M_j\}$.

§.§.§ Results

Key rate versus the number of signals for the qubit BB84 protocol to compare two algorithms for the generation of min-tradeoff functions. The quantum bit error rate is set to $Q = 0.01$ in the simulation. The red circle marker corresponds to <Ref> while the green star marker corresponds to <Ref>. The key rate formula is based on <Ref>. Other protocol parameters are optimized as described in the main text.

When applying <Ref> to the finite-key rate calculation, we optimize the min-tradeoff functions by choosing different $\vect{q}_0 = (Q, 1-Q)$ where $Q$ is searched over the interval $[0.005, 0.07]$ with a step size $0.005$. For each min-tradeoff function generated from a particular value of $Q$, we calculate the key rate, which is the key length $\ell$ divided by the total number of signals $n$. We then choose the maximum key rate among all possible choices of min-tradeoff functions generated in this way. This way of coarse-grained search over $\vect{q}_0$ is a heuristic approach to optimize the choice of min-tradeoff functions. We find these choices of $\vect{q}_0$ in general give us good results. However, a more sophisticated optimization over $\vect{q}_0$ might potentially improve the results presented here.

For <Ref>, we use the interior-point method from Matlab's fmincon function for the first step and then use CVX for the linearized dual problem. We note that we can also use the Frank-Wolfe algorithm for the first step instead of the and the interior-point method. When we do so, results are similar (slightly worse) for this example.

For both algorithms, we optimize $p_z$ by optimizing $\gamma =(1-p_z)^2 = 10^{-k}$ where $k$ is chosen from the interval $[2,4]$ with a step size of $0.1$. For block sizes larger than or equal to $10^{10}$, we allow $p_z$ to be closer to 1 by searching $k$ in the interval $[3,7]$ with a step size of $0.2$. Again, those choices are heuristic and could be potentially improved. Nevertheless, they are sufficient for our purpose.

Key rate versus the number of signals for the qubit BB84 protocol to compare different second-order correction terms using <Ref>. The quantum bit error rate is set to $Q = 0.01$ in the simulation. The red circle marker corresponds to the key rate formula given in <Ref> [Dupuis, 2021] while the green star marker corresponds to the key rate formula from <Ref> [Dupuis and Fawzi, 2019].

In <Ref>, we compare the key rates obtained from these two algorithms with <Ref>. Interestingly, both algorithms give similar results while <Ref> seems to be slightly better in terms of the smallest number of signals for nonzero key rates. Intuitively, we expect <Ref> to behave better as it takes into account some second-order correction terms, while <Ref> only looks for the min-tradeoff function that gives the highest leading-order term. As we perform an optimization of the choice of min-tradeoff function by different initial $\vect{q}_0$'s for <Ref>, we observe that the optimal finite key rate from <Ref> is often given by a min-tradeoff function that does not give the highest value for the leading-order term. Due to the optimization of $\vect{q}_0$, the running time of <Ref> is much longer than that of <Ref>.

In <Ref>, we compare key rates given by <Ref> when we use <Ref>. One can see that <Ref> gives better key rates. This confirms our conjecture that the EAT based on the sandwiched $\alpha$-Rényi entropy is tighter than the EAT based on the smooth min-entropy for lower-order correction terms. The intuition for this is that the Entropy Accumulation Theorem for smooth entropies is first derived in terms of $H_{\alpha}$ sandwiched Rényi entropies and then converted to statements about smooth entropies [Dupuis et al., 2020, Dupuis and Fawzi, 2019]. It follows that avoiding the conversion to smooth entropies should only improve the key rate.

§.§ Six-state four-state protocol

Another interesting example is the six-state four-state protocol [Tannous et al., 2019]. In the free space implementation of QKD protocols with the polarization encoding, there is naturally one axis that is stable against turbulence while other axes are slowly drifting. The idea of reference-frame-independent QKD [Laing et al., 2010] was motivated to address this issue and it was shown that such a protocol can be robust to slow drifts. The basic idea is that if the reference frame drift can be described by a unitary rotation, by using the information from an additional basis, one can effectively undo this unitary rotation. Here we consider the six-state four-state protocol [Tannous et al., 2019] which has the reference-frame-independent feature. In particular, we consider the entanglement-based version and assume Alice and Bob have qubits. We do not consider losses in this example.

§.§.§ Protocol and simulation

We analyze the entanglement-based version of the six-state four-state protocol [Tannous et al., 2019] assuming that Alice and Bob each receive a qubit in each round for simplicity of calculation. In this protocol, Alice measures the state in one of the $X, Y$ and $Z$ bases according to the probability distribution $((1-p_z)/2,(1-p_z)/2, p_z)$, while Bob measures in one of $X$ and $Z$ bases with the probability distribution $(1-p_z, p_z)$. Similarly to the previous qubit BB84 example, when both Alice and Bob choose the $Z$ basis, this round is used for key generation. When Alice chooses $X$ or $Y$ basis and Bob chooses $X$ basis, this round is used for parameter estimation. All other rounds are discarded. We consider an efficient version by setting $p_z$ to be close to $1$. In the testing step of the protocol, we use the POVM that contains error rates in the $XX$ and $YX$ bases.

For the simulation, we assume the $Z$ basis is free of misalignment. The misalignment happens in the $X$-$Y$ plane of the Bloch sphere. Thus, on top of the qubit depolarizing channel, we also apply a unitary rotation along the $Z$ axis to Bob's qubit in order to model the misalignment. We choose the angle of rotation to be  $11^{\circ}$ in the simulation. The state used to obtain the observed statistics from this simulation is

ρ^sim = (_A e^iθσ_Z) ρ^dp(_A e^-iθσ_Z),
where $\sigma_Z$ is the Pauli-$Z$ matrix, $\theta$ is the angle of rotation and $\rho^{\text{dp}}$ is the state given in <Ref> (that is, the simulated state in the qubit-based BB84 example).

§.§.§ Results

In the application of <Ref> to the finite-key rate calculation, we optimize the min-tradeoff functions by choosing different $\vect{q}_0$'s. We adopt a heuristic approach to optimize the choice of min-tradeoff functions. Each $\vect{q}_0$ is created by choosing a different depolarizing probability $Q$, which is searched over the interval $[0.005, 0.07]$ with a step size $0.005$. It is a heuristic choice that serves our purpose. For each min-tradeoff function generated from a particular value of $Q$, we calculate the key rate and then choose the maximum key rate among them. For <Ref>, we use same procedure as for the qubit BB84 example in <Ref> including the optimization over the choice of $p_z$.

Key rate versus the number of signals for the six-state four-state protocol with two algorithms. The quantum bit error rate is set to $Q = 0.01$ in the simulation. This plot is obtained by using the key rate formula given in <Ref> [Dupuis, 2021]. The red circle marker corresponds to the min-tradeoff function construction by <Ref>  while the green star marker corresponds to the min-tradeoff function construction by <Ref>.

In <Ref>, we compare two algorithms for the min-tradeoff function construction. For this plot, similar to qubit-based BB84 example, we perform additional initial point $\q_0$ optimization for <Ref> while we do not optimize $\q_0$ for <Ref>.  Like <Ref>, both algorithms give similar key rates.

Key rate versus the number of signals for the six-state four-state protocol with different second-order correction terms. The quantum bit error rate is set to $Q = 0.01$ in the simulation. This plot is obtained by using <Ref>. The red circle marker corresponds to the key rate formula given in <Ref> [Dupuis, 2021] while the green star marker corresponds to the key rate formula from <Ref> [Dupuis and Fawzi, 2019].

In <Ref>, we compare key rates for <Ref> and observe the same behavior as the qubit-based BB84 example in <Ref>. As explained in the qubit-based BB84 example in <Ref>, this behavior is not surprising since the sandwiched Rényi entropy was used in the middle step of the proofs of <Ref> in Refs. [Dupuis et al., 2020, Dupuis and Fawzi, 2019] before converting to the smooth min-entropy by an additional inequality. One would expect that bypassing the smooth min-entropy gives tighter key rates due to the removal of an inequality.

§.§ High-dimensional 2-MUB protocol

To demonstrate an advantage of our approach in the EAT framework, we analyze an interesting family of protocols which are the high-dimensional analog of the BB84 protocol. In BB84, two mutually unbiased bases (MUBs) are used. We consider qudit systems with 2 MUBs. We compare our calculation with the postselection technique [Christandl et al., 2009] combined with the numerical approach of [George et al., 2021]. We use this example to demonstrate that EAT can give better key rates compared to the postselection technique [Christandl et al., 2009], especially when the dimension $\dim(\cH_{AB})$ in the protocol is large.

§.§.§ Protocol and simulation

To properly define the protocol setup, recall that the discrete Weyl operators are defined as

U_jk = ∑_s=0^d-1ω^sk s+js
for $j,k \in \{0,1,\dots, d-1\}$ where $\omega = e^{2\pi i /d}$ is a $d$th root of unity. We note that $U_{01}$ is the generalized Pauli-$Z$ matrix and $U_{10}$ is the generalized Pauli-$X$ matrix. We define the qudit version of $Z$ and $X$ operators as $Z:=U_{01}$ and $X:=U_{10}$. The generalized Bell states are

|Φ_jk⟩ =1/√(d) ∑_s= 0^d-1 ω^sk |s, s+j⟩ = U_jk |Φ_00⟩.
In the 2-MUB protocol, Alice measures in the eigenbasis of either $U_{01}$ or $U_{10}$. Bob similarly measures in the eigenbasis of either $U_{01}^*$ or $U_{10}^*$. The eigenbasis of the operator $Z:=U_{01}$ is the computational basis $\{\ket{s}: 0\leq s \leq d-1\}$. The eigenbasis of the operator $X:=U_{10}$ is $\{\ket{\psi^X_j}: 0 \leq j \leq d-1\}$ where

|ψ^X_j⟩ := ∑_s=0^d-1ω^-js/√(d)|s⟩.
They each choose to measure in the $Z$ basis with the probability $p_z$ and choose to measure in the $X$ basis with the probability $1-p_z$. In the classical phase, Alice and Bob announce their basis choices and discard rounds with mismatched bases.  We allow an asymmetric basis choice, i.e., setting $p_z$ close to 1. In this protocol, all public announcements are based on seeded randomness. For simplicity of calculation, the testing rounds are those when they both choose $X$ basis and the key generation rounds are rounds when they both choose $Z$ basis.

It is interesting to note that the state $\ket{\Phi_{00}} = \frac{1}{\sqrt{d}}\sum_s \ket{s,s}$ is invariant under any $U_{jk} \ox U^*_{jk}$. In an honest implementation, the source is supposed to prepare the state $\ket{\Phi_{00}}$, and then to distribute one half to Alice and the other half to Bob. If the quantum channel is ideal, then they are supposed to obtain perfectly correlated results just like the qubit case.

Following the reasoning of [Kraus et al., 2005, Renner et al., 2005], Alice's and Bob's joint density operator can be taken as diagonal in the generalized Bell basis:

ρ_AB^BG=∑_j,k λ_jkΦ_jkΦ_jk,

λ_jk = 1/d (∑_s q_1s^(sj-k d) + q_01^(j)-1)
with $q_{jk}^{(i)}$ being the $i$th entry of the error vector $\vect{q}_{jk}$. See also [Sheridan and Scarani, 2010] for a detailed discussion. For our purpose of simulating the frequency distribution $\vect{q}_0$ needed for <Ref> or <Ref>, we take the simulation state $\rho_{AB}^{\text{sim}}$ used to generate the full statistics as $\rho_{AB}^{\text{sim}}=\rho_{AB}^{\text{BG}}$.

We follow the simulation in [Sheridan and Scarani, 2010] by considering the following observation for error vector $\vect{q}_{jk}$ in each basis $U_{jk}$, which is based on the natural generalization of the qubit depolarizing channel with a depolarizing probability $Q$:

q_jk(Q) := {1-Q, Q/(d-1), …, Q/(d-1)}.

§.§.§ Results

2-MUB protocols with qudits for various values of dimension $d$. The depolarizing probability is set to $Q = 0.01$ in the simulation. The calculation is done with <Ref> and the finite-key rate formula is from <Ref> [Dupuis, 2021]. The calculation of postselection technique is done using the numerical approach of [George et al., 2021] in combination of [Christandl et al., 2009]. The asymptotic key rate formula is given in [Ferenczi and Lütkenhaus, 2012, Sheridan and Scarani, 2010].

In <Ref>, we compare our results using <Ref> [Dupuis, 2021] with results obtained by the postselection technique [Christandl et al., 2009] for 2-MUB protocols in dimensions $d = 2,3,5$ and $7$. We note that 2-MUB protocols exist in any dimensions $d \geq 2$ and our proof method can work for any dimension. Here, we restrict to prime dimensions due to our choice of data simulation method. For both EAT and the postselection technique, we optimize the probability of choosing $Z$ basis. The probability of testing is set to $\gamma = (1-p_z)^2$. We optimize the probability of choosing $Z$-basis in the same way as in the qubit-based BB84 example.

It can be seen that both EAT and postselection technique can approach the expected asymptotic key rate in the infinite-key limit. Also, our method based on EAT outperforms the postselection technique for 2-MUB protocols in any dimensions. We also observe that for larger dimensions, our method can give much higher key rate than the postselection technique for small block sizes. This makes our method attractive since small block sizes are of particular interests for experimental implementations.

In the same plot, we also show the asymptotic key rate for 2-MUB protocol. The asymptotic key rate formula is given in [Ferenczi and Lütkenhaus, 2012, Sheridan and Scarani, 2010]. Both our method and the postselection technique can approach the asymptotic key rate for sufficiently large block size. We also note that for block size larger than $10^{17}$, there seems to be a small constant deviation from the asymptotic key rate in both postselection technique and our method. This deviation is mainly due to our optimization over $p_z$, which is done by choosing a set of values. The asymptotic key rate formula that we use assumes that we can set $p_z$ to be arbitrarily close to $1$ such that the sifting factor is $1$. On the other hand, numerical optimization over $p_z$ in our method cannot take $p_z$ too close to one. The reason for our EAT method is that our testing probability is set to be $(1-p_z)^2$. When the testing probability is small, the variance of the min-tradeoff function, $\Var{f}$, becomes large as shown in <Ref>. Since $\Var{f}$ shows up in the second-order correction term, for a fixed block size, there is always a limit on how small the testing probability $\gamma$ can be before we start to lose key rates due to its adverse effect on the second-order correction term. For a fair comparison between our EAT approach and the postselection technique, we also use the same optimization of $p_z$ in the calculation with the postselection technique.

§.§ BB84 with a realistic spontaneous parametric downconversion source

We consider an example where the Markov chain conditions are not simply based on seeded randomness. This example considers an optical implementation of entanglement-based BB84. The photon-pair source is a spontaneous parametric downconversion source where there is a non-negligible probability that the source emits vacuum or more than one photon pair. Due to photon loss during the transmission and non-unity detector efficiencies, there are no-detection events. In the protocol, Alice and Bob announce these events and discard the corresponding rounds. We need to verify that this type of announcements do not violate the Markov chain conditions.

§.§.§ Protocol and simulation method

In this protocol, a type-II parametric down-conversion (PDC) source emits a state with polarization encoding [Kok and Braunstein, 2000, Ma et al., 2007] which is

\begin{equation}
\begin{aligned}
\ket{\Psi} = (\cosh(\chi))^{-2} \sum_{n=0}^{\infty} \sqrt{n+1}\tanh^n(\chi)\ket{\Phi_n}
\end{aligned}
\end{equation}
where $\ket{\Phi}_n$ is the state of an $n$-photon pair which can be written as

\begin{equation}
\begin{aligned}
\ket{\Phi_n} = \frac{1}{\sqrt{n+1}}\sum_{m=0}^{n} (-1)^m \ket{n-m,m}_a\ket{m,n-m}_b.
\end{aligned}
\end{equation}
The average number of photon pairs generated by one pump pulse is $2\lambda$, where $\lambda = \sinh(\chi)$. In this protocol, Alice and Bob each have a set of single-photon detectors. We consider the BB84 detector setup with a passive basis choice; that is, each measurement setup consists of an initial 50/50 beam splitter and each output port of this beam splitter is directed to a polarizing beam splitter with two single-photon detectors. We assume Alice's two detectors have the same detector efficiency $\eta_A$ and the same dark count probability $Y_{0A}$. Similarly, we assume that Bob's two detectors have the same detector efficiency $\eta_B$ and the same dark count probability $Y_{0B}$. Using the similar choice as in other examples, whenever Alice and Bob choose $X$-basis, the round is used for testing. The key generation round is when they both choose $Z$-basis. Their probabilities of choosing $Z$ basis is $p_{zA}$ and $p_{zB}$, respectively. The probability of testing is set to $\gamma = (1-p_{zA})(1-p_{zB})$.

Our simulation is based on [Ma et al., 2007]. In this simulation, there are three main contributions to quantum bit error rate: (i) background counts of detectors, which are random noises with $e_0=1/2$; (ii) intrinsic detector error $e_d$, which is the probability that a photon enters the erroneous detector and is used to characterized the alignment and stability of optical system between Alice's and Bob's detection systems; (iii) errors due to multiphoton-pair states: (a) Alice and Bob may detect different photon pairs and (b) double clicks from detectors. Alice and Bob assign a random bit for each double-click event in order to use the squashing model [Beaudry et al., 2008, Gittsovich et al., 2014].

In particular, the overall gain, $Q_{\lambda}$, as a function of the average number of photon, $\lambda$, in each mode, dark counts and detector efficiencies is given by <cit.>

\begin{equation}
\begin{aligned}
Q_{\lambda} = 1 - \frac{1-Y_{0A}}{(1+\eta_A \lambda)} - \frac{1-Y_{0B}}{(1+\eta_B \lambda)} +\frac{(1-Y_{0A})(1-Y_{0B})}{(1+\eta_A \lambda + \eta_B \lambda - \eta_A \eta_B \lambda)^2}.
\end{aligned}
\end{equation}

The overall quantum bit error rate ($E_{\lambda}$) is given by <cit.>

\begin{equation}
\begin{aligned}
E_{\lambda}Q_{\lambda} = e_0 Q_{\lambda} - \frac{2(e_0-e_d)\eta_A\eta_B\lambda(1+\lambda)}{(1+\eta_A\lambda)(1+\eta_B\lambda)(1+\eta_A\lambda + \eta_B\lambda - \eta_A \eta_B \lambda)}.
\end{aligned}
\end{equation}

To reduce the number of free parameters in the protocol setup, we set $p_{zA} = p_{zB} =p_z$ and the testing probability is set to $\gamma = (1-p_z)^2$. We optimize the choice of $p_z$ in the same way as in <Ref>.

§.§.§ Assumption on announcements

We need to verify for Markov chain conditions that the probability of a detection event only depends on the total photon number, but not on the particular $n$-photon state. We show that this holds when Alice's (Bob's) detectors consist of two single-photon detectors with an identical detection efficiency $\eta_A$ ($\eta_B$), and a basis-independent dark count probability $Y_{0A}$ ($Y_{0B}$). We note that the measurement performed by Bob (Alice) is block diagonal in the total photon number basis, as is the case in all discrete-variable protocols.

Under our assumption about the detectors, we can treat all the imperfections of detectors as a part of the quantum channel and then assume ideal detectors in our analysis. Doing so only strengthens Eve's power. After assigning double-click events to random bits, we note that the measurement setup in this protocol admits a squashing model [Beaudry et al., 2008, Gittsovich et al., 2014]. In our analysis, we can use the effective qubit measurement for Alice (Bob) as the target measurement. This target measurement acts on the Hilbert space that consists of a one-dimensional vacuum space and a two-dimensional qubit space. In particular, the announcement about detection and no-detection corresponds to the POVM $\{M_{\text{det}},M_{\text{no-det}}\}$, which is defined as

M_det =
0     0     0

0     1     0

0     0     1
,   	M_no-det =
1     0     0

0     0     0

0     0     0
where they are represented in the basis $\{\ket{\text{vac}},\ket{0},\ket{1}\}$. Here $\ket{\text{vac}}$ is the vacuum state and $\ket{0},\ket{1}$ are the computational basis states of a qubit. Clearly, this POVM is weekly dependent according to <Ref>. Thus, this announcement is allowed in applying <Ref>.

§.§.§ Results

Key rate per signal sent versus the number of signals for BB84 with a spontaneous parametric downconversion source for various distances between Alice and Bob. This plot is obtained with <Ref> and <Ref>. Parameters are specified in the main text.

In <Ref>, we show the key rate of this protocol for different distances ($L$ in kilometers) between Alice and Bob. We assume the source is located in the middle and at an equal distance from Alice and Bob. We choose detector efficiencies $\eta_A = \eta_B = 0.8$ and dark counts $Y_{0A} = Y_{0B} =10^{-7}$ for the simulation in this plot.[This choice of detector parameters may be realized by superconducting nanowire single-photon detectors. However, the purpose here is to demonstrate that our method can handle some imperfections and loss. Our method also has limitations in the amount of loss it can handle.] We also set the intrinsic detector error $e_d$ as $1\%$. On one hand, we can see that our method works for optical implementations from this figure. On the other hand, as the distance between Alice and Bob increases, the minimal number of signals for positive key rate also increases significantly and the key rate drops quickly. In our key rate expression from <Ref> (also from <Ref>), the term $-n\gamma \log(\abs{\cA})$ decreases the key length and becomes more problematic for this protocol since the entropy only accumulates in rounds where both Alice and Bob successfully detected photons. However, this term does not scale with the probability of detection. For long distances, this seems to suggest that the cost for parameter estimation is higher than the entropy accumulated from rounds with successful detection. Unfortunately, this counter-intuitive effect comes from the limitation of our proof method in dealing with parameter estimation registers. We hope that a better approach to handle the information leakage from parameter estimation step can be found in the future to significantly improve the key rate.

§ DISCUSSION AND CONCLUSION