In this work, we have adapted the EAT to entanglement-based device-dependent QKD protocols. To do so, we introduced new tools. First, we constructed new sufficient conditions on the public announcements of the protocol to guarantee the Markov conditions necessary for the EAT. These conditions capture the intuition that if Eve would always know some information for each round of the protocol, then announcing that information cannot change the security. The interesting point is that this guarantees the Markov conditions on Eve's optimal attack.

Second, we proposed two variants of a numerical algorithm to construct min-tradeoff functions, both of which are efficient and one which considers second-order effects. Both methods build off of previous work [Coles et al., 2016, Winick et al., 2018], but the ability to construct min-tradeoff functions that take into account second-order correction information is novel and we expect could be useful in other settings. We note this second-order correction algorithm relies on using Fenchel duality, which to the best of our knowledge has not been used in quantum information theory previously.

Third, we derived our key length bound (<Ref>) using Dupuis' privacy amplification for sandwiched Rényi entropies $H^{\uparrow}_{\alpha}$ [Dupuis, 2021]. In that work, Dupuis demonstrates one can obtain simpler error exponents for privacy amplification using the Rényi version of the EAT along with his Rényi leftover hashing lemma <cit.> than if one were to apply the smooth min-entropy leftover hashing lemma [Renner, 2005]. Here we have shown an alternative advantage: by avoiding the conversion of the Rényi EAT into smooth min-entropy terms, we can tighten our bound on the key rate.

We then apply our methods to several examples. First, we applied it to ideal qubit-based BB84 and six-state four-state protocols where we show the application of both our min-tradeoff construction algorithms and that using our Rényi entropy rate improves the finite-size key rate to considering the smooth min-entropy rate, at least in the current proof method. We next considered the high-dimensional two mutually unbiased bases protocols which exemplified an improvement in the key rate over the postselection technique [Christandl et al., 2009], an alternative proof method for coherent-attack security which is limited in how it scales with respect to the dimension of Alice and Bob's quantum states. This confirms there is a regime in which the postselection technique is “loose”, further suggesting the importance of the application of the EAT. Lastly, we demonstrate our method for an optical implementation. This example demonstrates that our method is also applicable to practical protocols instead of restricting to theoretically simple ones. On the other hand, due to unsatisfactory results in small block sizes, we also observe that the EAT currently appears to require more improvements in handling loss and noise in order to have good key rates for experimentally feasible block sizes.

Given these results, it is natural to consider where improvements might be made or further avenues to explore. First and foremost, we note that we were restricted to considering entanglement-based protocols as we need the entanglement-based protocol framework to use our algorithms. In previous work [George et al., 2021], this has not been limiting as we could use the source-replacement scheme [Curty et al., 2004, Ferenczi and Lütkenhaus, 2012] to convert prepare-and-measure protocols to entanglement-based ones. However, it is not clear how the source-replacement scheme interacts with the Markov chain requirements for the EAT, which is why this work is restricted to entanglement-based protocols. Second, we have seen that while the EAT scales well in terms of the dimension of the states, it seems limited by loss and noise. In particular, the ability to handling high loss parameter regime is of particular interest for realistic implementations. As such, a natural question is to try and find ways to make the EAT more robust to loss and noise, at least in the device-dependent setting.

§ ACKNOWLEDGMENTS

I.G. thanks Frédéric Dupuis and Marco Tomamichel for helpful discussions. The authors thank Jamie Sikora for helpful suggestions on numerical optimization and thank Ernest Y. -Z Tan for technical suggestions given an earlier draft. The work has been performed at the Institute for Quantum Computing (IQC), University of Waterloo, which is supported by Innovation, Science and Economic Development Canada. J.L. acknowledges the support of Mike and Ophelia Lazaridis Fellowship from IQC. I.G. acknowledges the support of an Illinois Distinguished Fellowship. The research has been supported by Natural Sciences and Engineering Research Council of Canada (NSERC) under the Discovery Grants Program, Grant No. 341495, and by NSERC under the Collaborative Research and Development Program, Grant No. CRDP J 522308-17. Financial support for this work has been partially provided by Huawei Technologies Canada Co., Ltd.

[Bennett and Brassard, 1984]
Charles H. Bennett and Gilles Brassard.
Quantum cryptography: Public key distribution and coin tossing.
In Proceedings of IEEE International Conference on Computers,
Systems and Signal Processing, pages 175–179, New York, 1984. IEEE.
URL <https://doi.org/10.1016/j.tcs.2014.05.025>.

[Ekert, 1991]
Artur K. Ekert.
Quantum cryptography based on Bell's theorem.
Phys. Rev. Lett., 670 (6):0 661, 1991.

[Scarani et al., 2009]
V. Scarani, H. Bechmann-Pasquinucci, N. J. Cerf, M. Dušek,
N. Lütkenhaus, and M. Peev.
The security of practical quantum key distribution.
Rev. Mod. Phys., 81:0 1301, 2009.

[Xu et al., 2020]
Feihu Xu, Xiongfeng Ma, Qiang Zhang, Hoi-Kwong Lo, and Jian-Wei Pan.
Secure quantum key distribution with realistic devices.
Rev. Mod. Phys., 920 (2):0 025002, 2020.

[Pirandola et al., 2020]
S. Pirandola, U. L. Andersen, L. Banchi, M. Berta, D. Bunandar, R. Colbeck,
D. Englund, T. Gehring, C. Lupo, C. Ottaviani, J. Pereira, M. Razavi, J. S.
Shaari, M. Tomamichel, V. C. Usenko, G. Vallone, P. Villoresi, and
P. Wallden.
Advances in quantum cryptography.
Adv. Opt. Photon., 12:0 1012–1236, 2020.

[Boaron et al., 2018]
Alberto Boaron, Gianluca Boso, Davide Rusca, Cédric Vulliez, Claire
Autebert, Misael Caloz, Matthieu Perrenoud, Gaëtan Gras, Félix
Bussières, Ming-Jun Li, Daniel Nolan, Anthony Martin, and Hugo Zbinden.
Secure quantum key distribution over 421 km of optical fiber.
Phys. Rev. Lett., 1210 (19):0 190502, 2018.

[Fang et al., 2020]
Xiao-Tian Fang, Pei Zeng, Hui Liu, Mi Zou, Weijie Wu, Yan-Lin Tang, Ying-Jie
Sheng, Yao Xiang, Weijun Zhang, Hao Li, Zhen Wang, Lixing You, Hao Chen
Ming-Jun Li, Yu-Ao Chen, Qiang Zhang, Cheng-Zhi Peng, Xiongfeng Ma, Teng-Yun
Chen, and Jian-Wei Pan.
Implementation of quantum key distribution surpassing the linear
rate-transmittance bound.
Nat. Photonics, 140 (7):0 422–425, 2020.

[Liao et al., 2017]
Sheng-Kai Liao, Wen-Qi Cai, Wei-Yue Liu, Liang Zhang, Yang Li, Ji-Gang Ren,
Juan Yin, Qi Shen, Yuan Cao, Zheng-Ping Li, Feng-Zhi Li, Xia-Wei Chen, Li-Hua
Sun, Jian-Jun Jia, Jin-Cai Wu, Xiao-Jun Jiang, Jian-Feng Wang, Yong-Mei
Huang, Qiang Wang, Yi-Lin Zhou, Lei Deng, Tao Xi, Lu Ma, Tai Hu, Qiang Zhang,
Yu-Ao Chen, Nai-Le Liu, Xiang-Bin Wang, Zhen-Cai Zhu, Chao-Yang Lu, Rong Shu,
Cheng-Zhi Peng, Jian-Yu Wang, and Jian-Wei Pan.
Satellite-to-ground quantum key distribution.
Nature, 5490 (7670):0 43–47, 2017.

[Bedington et al., 2017]
Robert Bedington, Juan Miguel Arrazola, and Alexander Ling.
Progress in satellite quantum key distribution.
npj Quantum Inf., 30 (1):0 1–13, 2017.

[Sibson et al., 2017]
P. Sibson, C. Erven, M. Godfrey, S. Miki, T. Yamashita, M. Fujiwara, M. Sasaki,
H. Terai, M. G. Tanner, C. M. Natarajan, R. H. Hadfield, J. L. O’Brien,
and M. G. Thompson.
Chip-based quantum key distribution.
Nat. Commun., 80 (1):0 13984, 2017.

[Zhang et al., 2019]
G. Zhang, J. Y. Haw, H. Cai, F. Xu, S. M. Assad, J. F. Fitzsimons, X. Zhou,
Y. Zhang, S Yu, J Wu, W. Ser, L. C. Kwek, and A. Q. Liu.
An integrated silicon photonic chip platform for continuous-variable
quantum key distribution.
Nat. Photonics, 130 (12):0 839–842, 2019.

[Wei et al., 2020]
Kejin Wei, Wei Li, Hao Tan, Yang Li, Hao Min, Wei-Jun Zhang, Hao Li, Lixing
You, Zhen Wang, Xiao Jiang, Teng-Yun Chen, Sheng-Kai Liao, Cheng-Zhi Peng,
Feihu Xu, and Jian-Wei Pan.
High-speed measurement-device-independent quantum key distribution
with integrated silicon photonics.
Phys. Rev. X, 100 (3):0 031030, 2020.

[Renner, 2005]
Renato Renner.
Security of Quantum Key Distribution.
PhD thesis, ETH Zürich, Zürich, Switzerland, 2005.
URL <https://arxiv.org/abs/quant-ph/0512258>.

[Christandl et al., 2009]
Matthias Christandl, Robert König, and Renato Renner.
Postselection technique for quantum channels with applications to
quantum cryptography.
Phys. Rev. Lett., 102:0 020504, 2009.

[Dupuis et al., 2020]
Frederic Dupuis, Omar Fawzi, and Renato Renner.
Entropy accumulation.
Commun. Math. Phys., 379:0 867–913, 2020.

[Dupuis and Fawzi, 2019]
Frédéric Dupuis and Omar Fawzi.
Entropy accumulation with improved second-order term.
IEEE Trans. Inf. Theory, 65:0 7596–7612, 2019.

[Arnon-Friedman et al., 2018]
Rotem Arnon-Friedman, Frédéric Dupuis, Omar Fawzi, Renato Renner, and
Thomas Vidick.
Practical device-independent quantum cryptography via entropy
Nature communications, 90 (1):0 459, 2018.

[Arnon-Friedman et al., 2019]
Rotem Arnon-Friedman, Renato Renner, and Thomas Vidick.
Simple and tight device-independent security proofs.
SIAM J. Comput., 480 (1):0 181–225, 2019.

[Nadlinger et al., 2021]
D. P. Nadlinger, P. Drmota, B. C. Nichol, G. Araneda, D. Main, R. Srinivas,
D. M. Lucas, C. J. Ballance, K. Ivanov, E. Y-Z. Tan, P. Sekatski, R. L.
Urbanke, R. Renner, N. Sangouard, and J-D. Bancal.
Device-independent quantum key distribution.
arXiv:2109.14600, 2021.
URL <https://arxiv.org/abs/2109.14600>.

[Zhang et al., 2021]
Wei Zhang, Tim van Leent, Kai Redeker, Robert Garthoff, Rene Schwonnek, Florian
Fertig, Sebastian Eppelt, Valerio Scarani, Charles C. W. Lim, and Harald
Experimental device-independent quantum key distribution between
distant users.
arXiv:2110.00575, 2021.
URL <https://arxiv.org/abs/2110.00575>.

[Liu et al., 2021]
Wen-Zhao Liu, Yu-Zhe Zhang, Yi-Zheng Zhen, Ming-Han Li, Yang Liu, Jingyun Fan,
Feihu Xu, Qiang Zhang, and Jian-Wei Pan.
High-speed device-independent quantum key distribution against
collective attacks.
arXiv:2110.01480, 2021.
URL <https://arxiv.org/abs/2110.01480>.

[Barrett et al., 2013]
Jonathan Barrett, Roger Colbeck, and Adrian Kent.
Memory attacks on device-independent quantum cryptography.
Phys. Rev. Lett., 110:0 010503, Jan 2013.

[Brown et al., 2021]
Peter Brown, Hamza Fawzi, and Omar Fawzi.
Computing conditional entropies for quantum correlations.
Nat. Commun., 12:0 575, 2021.

[Coles et al., 2016]
Patrick J. Coles, Eric M. Metodiev, and Norbert Lütkenhaus.
Numerical approach for unstructured quantum key distribution.
Nat. Commun., 7:0 11712, 2016.

[Winick et al., 2018]
Adam Winick, Norbert Lütkenhaus, and Patrick J. Coles.
Reliable numerical key rates for quantum key distribution.
Quantum, 2:0 77, 2018.

[Dupuis, 2021]
Frédéric Dupuis.
Privacy amplification and decoupling without smoothing.
arXiv:2105.05342, 2021.
URL <https://arxiv.org/abs/2105.05342>.

[Tannous et al., 2019]
Ramy Tannous, Zhangdong Ye, Jeongwan Jin, Katanya B. Kuntz, Norbert
Lütkenhaus, and Thomas Jennewein.
Demonstration of a 6 state-4 state reference frame independent
channel for quantum key distribution.
Appl. Phys. Lett., 115:0 211103, 2019.

[Ferenczi and Lütkenhaus, 2012]
Agnes Ferenczi and Norbert Lütkenhaus.
Symmetries in quantum key distribution and the connection between
optimal attacks and optimal cloning.
Phys. Rev. A, 85:0 052310, 2012.

[Tomamichel, 2016]
Marco Tomamichel.
Quantum Information Processing with Finite Resources.
Springer International Publishing, 2016.
All equation numbers and theorem numbers cited in this work refer to
the fourth arXiv version of this cited work:

[Tomamichel, 2012]
Marco Tomamichel.
A Framework for Non-Asymptotic Quantum Infomration Theory.
PhD thesis, ETH Zürich, Zürich, Switzerland, 2012.
URL <https://arxiv.org/abs/1203.2142>.

[Portmann and Renner, 2014]
Christopher Portmann and Renato Renner.
Cryptographic security of quantum key distribution.
arXiv preprint arXiv:1409.3525, 2014.

[Sutter, 2018]
David Sutter.
Approximate quantum markov chains.
In Approximate Quantum Markov Chains, pages 75–100. Springer,

[Devetak and Winter, 2005]
Igor Devetak and Andreas Winter.
Distillation of secret key entanglement from quantum states.
Proc. R. Soc. A, 461:0 207–235, 2005.

[George et al., 2021]
Ian George, Jie Lin, and Norbert Lütkenhaus.
Numerical calculations of the finite key rate for general quantum key
distribution protocols.
Phys. Rev. Research, 3:0 013274, 2021.

[Watrous, 2018]
John Watrous.
The Theory of Quantum Information.
Cambridge University Press, Cambridge, UK, 2018.
ISBN 1107180562.

[Lo et al., 2005]
Hoi-Kwong Lo, H. F. Chau, and M. Ardehali.
Efficient quantum key distribution scheme and a proof of its
unconditional security.
J. Cryptol., 18:0 133–165, 2005.

[Laing et al., 2010]
Anthony Laing, Valerio Scarani, John G. Rarity, and Jeremy L. O’Brien.
Reference-frame-independent quantum key distribution.
Phys. Rev. A, 820 (3):0 012304, 2010.

[Kraus et al., 2005]
Barbara Kraus, Nicolas Gisin, and Renato Renner.
Lower and upper bounds on the secret-key rate for quantum key
distribution protocols using one-way classical communication.
Phys. Rev. Lett., 950 (8):0 080501, 2005.

[Renner et al., 2005]
Renato Renner, Nicolas Gisin, and Barbara Kraus.
Information-theoretic security proof for quantum-key-distribution
Phys. Rev. A, 720 (1):0 012332, 2005.

[Sheridan and Scarani, 2010]
Lana Sheridan and Valerio Scarani.
Security proof for quantum key distribution using qudit systems.
Phys. Rev. A, 820 (3):0 030301(R), 2010.

[Kok and Braunstein, 2000]
Pieter Kok and Samuel L. Braunstein.
Postselected versus nonpostselected quantum teleportation using
parametric down-conversion.
Phys. Rev. A, 610 (4):0 042304, 2000.

[Ma et al., 2007]
Xiongfeng Ma, Chi-Hang Fred Fung, and Hoi-Kwong Lo.
Quantum key distribution with entangled photon sources.
Phys. Rev. A, 76:0 012307, 2007.

[Beaudry et al., 2008]
Normand J. Beaudry, Tobias Moroder, and Norbert Lütkenhaus.
Squashing models for optical measurements in quantum communication.
Phys. Rev. Lett., 101:0 093601, 2008.

[Gittsovich et al., 2014]
O. Gittsovich, N. J. Beaudry, V. Narasimhachar, R. R. Alvarez, T. Moroder, and
N. Lütkenhaus.
Squashing models for detectors and applications to quantum key
distribution protocols.
Phys. Rev. A, 89:0 012325, 2014.

[Curty et al., 2004]
Marcos Curty, Maciej Lewenstein, and Norbert Lütkenhaus.
Entanglement as precondition for secure quantum key distribution.
Phys. Rev. Lett., 92:0 217903, 2004.

[Dupuis, 2015]
Frédéric Dupuis.
Chain rules for quantum rényi entropies.
Journal of Mathematical Physics, 560 (2):0
022203, 2015.

[Tomamichel and Leverrier, 2017]
Marco Tomamichel and Anthony Leverrier.
A largely self-contained and complete security proof for quantum key
Quantum, 1:0 14, 2017.

[Cover and Thomas, 2005]
Thomas M. Cover and Joy A. Thomas.
Elements of Information Theory, Second Edition.
John Wiley & Sons, 2005.
ISBN 0471241954.

[Romik, 2000]
Dan Romik.
Stirling's approximation for n!: the ultimate short proof?
The American Mathematical Monthly, 1070 (6):0
556–557, 2000.

[Borwein and Lewis, 2006]
Jonathan Borwein and Adrian S. Lewis.
Convex Analysis and Nonlinear Optimization: Theory and
Springer-Verlag, New York, USA, 2006.

§ A SUFFICIENT CONDITION FOR THE MARKOV CHAIN CONDITION

In this section, we prove <Ref> from the main text which gives sufficient conditions for ensuring the Markov chain conditions hold on the optimal attack. We note the statement in this section (<Ref>) includes an additional equivalent condition which is quick to verify and so may be of use.

Recall that we consider EAT channels with a special tensor product structure. We consider $n$ CPTP maps $\widetilde\cM_i:Q_i \rightarrow S_iP_iX_i$ acting in tensor product on the $n$ independent systems $\{Q_i\}_i$. The maps are defined by the POVM $\{M_{sp}\}$ such that

\begin{equation}
\widetilde\cM_i (\rho) = \sum_{s,p}\Tr[ \rho M_{sp}] \ketbra{s,p}_{S_iP_i} \otimes \ketbra{t(s,p)}_{X_i}\,.
\end{equation}

From these we define the corresponding EAT channels $\cM_i: R_{i-1} \rightarrow R_iS_iP_iX_i$ acting on the quantum systems $R_i = Q_{i+1}^n$, as $\cM_i = \widetilde {\cM}_i \otimes \id_{Q_{i+1}^n}$ (see main text for further details). In this case, it is simple to prove that the output state of the protocol $\rho_{S_1^nP_1^nX_1^nE} = \cM_1\circ \dots \circ \cM_n \otimes \id_E(\rho_{R_0E})$ takes on the simple form

\begin{equation}
\label{eq:OutputStateTensor}
\rho_{S_1^nP_1^nX_1^nE} = \bigotimes_{i=1}^n \widetilde \cM_i \otimes \id_E (\rho_{Q_1^nE})
\end{equation}

where $R_0 = Q_1^n$.

We now want to prove the following proposition.

Let $\{M_{sp}: s \in \cS, p\in \cP\}$ be the POVM associated to a given quantum-to-classical CPTP map $\widetilde \cM_i: Q_i\rightarrow S_iP_iX_i$ and let $M_p := \sum_s M_{sp}$ correspond to the POVM elements of the map $\Tr_{S_iX_i}\circ \widetilde \cM_i: Q_i \rightarrow P_i$. If either <ref> or <ref> below holds for each CPTP map $\widetilde \cM_i$, then without loss of generality the optimal attack by an eavesdropper is of a block-diagonal form such that the Markov chain conditions, <Ref>, hold and so the EAT may be applied (<Ref>).

* condition]condition:A There exists a decomposition $Q_i = \bigoplus_\lambda V^\lambda$ of the space $Q_i$ into orthogonal subspaces $\{V^\lambda\}_\lambda$ such that

(1) For all $(s,p) \in \cS \times \cP$, $M_{sp}$ is block diagonal:  $M_{sp} = \bigoplus_\lambda M^{(\lambda)}_{sp}$, where $M_{sp}^{(\lambda)}$ acts on the subspace $V^\lambda$.

(2) For all $p \in \cP$, $M_p$ is block diagonal and proportional to the identity in each subspace: there exist constants $m_p^\lambda \in [0,1]$ such that $M_p = \bigoplus_\lambda m_p^\lambda \idm_{V^\lambda}$,
where $\idm_{V^\lambda}$ is the identity operator on $V^\lambda$.

* condition]condition:B For all $s \in \cS$, $p,p' \in \cP$, $M_{sp}$ and $M_{p'}$ commute: $[M_{sp},M_{p'}] = 0$.

Furthermore, condition:A and condition:B are equivalent.

The statement of <Ref> just states <ref> in <Ref> under the name of `weakly dependent' (<Ref>), which is of primary interest. While equivalent, <ref> is stated here as it could be of use when one knows the measurement operators, as it is then easy to check <ref> to determine if <Ref> may be applied.

One way to prove the EAT theorem applies under <ref> or <ref> would be to show the output state in <Ref> satisfies the Markov chain conditions, but this does not work in general. Instead, we show that we can assume the initial state is of a certain block diagonal form without loss of generality due to the block diagonal structure of the EAT channels (<Ref>). Then we show that this block diagonal form satisfies the Markov chain conditions (Proof of <Ref>), and, as assuming this form was without loss of generality, this is sufficient. The reduction to a quantum state with block-diagonal structure is well-known in discrete-variable QKD where the measurement operators that model single-photon detectors are block diagonal in the total photon number basis. In such a setting, this block diagonal structure implies Eve's optimal attack includes implementing a QND measurement on the total number of photons before sending out the states, thereby resulting in the state being block-diagonal without loss of generality. One may view <Ref> and <Ref> as a generalization of such a method, but with the further insight that such structure implies the Markov chain conditions hold.

Let each $\widetilde \cM_i$ be a quantum-to-classical CPTP map whose associated POVM elements are block diagonal; i.e., for each $i$ there exists a decomposition $Q_i = \bigoplus_\lambda V^\lambda$ such that $M_{sp}  =\bigoplus _{\lambda} M_{sp}^{(\lambda)}$ with $M_{sp}^{(\lambda)}$ acting on $V^\lambda$. Then for any initial state $\rho_{Q_1^nE}$, there exists another state $\nu_{Q_1^nE'}$ such that

(1) the state $\nu_{Q_1^nE'}$ has the block diagonal form

\begin{equation}
\label{eq:block_attack}
\nu_{Q_1^{n}E\Lambda_1^{n}} = \sum_{\vect{\lambda} = (\lambda_1,\cdots \lambda_n)} \rho_{Q_1^nE}{(\vect{\lambda})} \otimes \ketbra{ \vect{\lambda}}_{\Lambda_1^n}\,,
\end{equation}
where Eve's registers $E' = (E,\Lambda_1,\cdots \Lambda_n)$ are composed of a quantum memory $E$ and $n$ classical registers $\Lambda_i$ indicating the subspace, so that, for all $\vect{\lambda}$, the state $\Tr_E[\rho_{Q_1^nE}{(\vect{\lambda})}]$ is defined on $V^{\vect{\lambda}} := \bigotimes_i V^{\lambda_i}$, and

(2) the output states $\nu_{S_1^nP_1^nX_1^nE'}$ and $\rho_{S_1^nP_1^nX_1^nE}$ are related by

\begin{equation}
\label{eq: block_attack_trace}
\Tr_{\Lambda_1^n} [\nu_{S_1^nP_1^nX_1^nE\Lambda_1^n}] = \rho_{S_1^nP_1^nX_1^nE}\,.
\end{equation}

To construct the state $\nu_{Q_1^nE'}$ from the state $\rho_{Q_1^nE}$, we consider the dephasing map $\Delta_i: Q_i \rightarrow  Q_i\Lambda_i$

\begin{equation}
\Delta_i(\rho) = {\sum}_\lambda P_\lambda \rho P_\lambda \otimes \ketbra{\lambda}_{\Lambda_i}\,,
\end{equation}
where $P_\lambda$ is a projector on the subspace $V^\lambda$. This map $\Delta_i$ projects the state onto each subspace $V^\lambda$ without affecting the coherence inside the subspace $V^\lambda$ and writes the result in $\Lambda_i$.  We then define $\nu_{Q_1^nE'} := \nu_{Q_1^nE\Lambda_1^n} := \left(\bigotimes_i \Delta_i\otimes \id_E\right)(\rho_{Q_1^nE})$. The state $\nu_{Q_1^n E \Lambda_1^n}$ is indeed of the form <Ref>, as required.

Because of the block diagonal structure of the maps $\widetilde\cM_i$, it is simple to see that the dephasing map does not affect the measurement statistics. We can observe that the maps $\Delta_i$ and $\widetilde\cM_i$ are related by $\Tr_{\Lambda_i} \circ \widetilde \cM_i \circ \Delta_{i} =  \widetilde \cM_i \circ \Tr_{\Lambda_i} \circ \Delta_{i} = \widetilde \cM_i$. Consequently, we have
_Λ_1^n [ν_S_1^nP_1^nX_1^nEΛ_1^n]
= _Λ_1^n ∘(⊗_i _i ⊗𝕀_EΛ_1^n)∘(⊗_i Δ_i ⊗𝕀_E)(ρ_Q_1^nE)

= (⊗_i _i ⊗𝕀_E)(ρ_Q_1^nE)

=: ρ_S_1^nP_1^nX_1^nE.

Let $\rho_{Q_1^nE}$ be some initial state used in the EAT (<Ref>). We assume that the maps $\widetilde \cM_i$ satisfy the <ref> instead of the Markov chain conditions. Let us show that the Markov chain conditions follow from this condition.

Using the block diagonal structure of <ref>, we can use <Ref> to show that there exists a block diagonal state $\nu_{Q_1^nE'}$ with the same passing probability $\nu[\Omega] = \rho[\Omega]$, which satisfies $H_{\min}^\epsilon(S_i^n|P_i^nE)_{\rho_{|\Omega}} \geq H_{\min}^\epsilon(S_i^n|P_i^nE')_{\nu_{|\Omega}}$. Indeed, this follows by using <Ref> and the strong subadditivity of smooth min-entropies. We conclude that whatever min-entropy lower-bound statement holds for $\nu_{Q_1^nE'}$ must also hold for $\rho_{Q_1^nE}$.

To prove <Ref>, we then show that the new state $\nu_{Q_1^nE}$ satisfies the Markov chain conditions in <Ref>. We can do this by showing that given the state $\nu_{S_1^{i-1} P_1^{i-1} E'}$, there exists a recovery map $\mathcal R_{P_iE\leftarrow E'}$ which acts on Eve's registers $E' = (E,\Lambda_1^n)$ and recovers the register $P_i$, i.e., $\mathcal R (\nu_{S_1^{i-1} P_1^{i-1} E'}) = \nu_{S_1^{i-1} P_1^{i} E}$.  Since the POVM elements $M_{p}$ are proportional to the identity in every subspace $V^\lambda$, the probability distribution of $P_i$ only depends on the subspace $V^\lambda$, which is indicated in Eve's register $\Lambda_i$. This means the variable $P_i$ can therefore be recovered from $\Lambda_i$ by simply generating it with the distribution $\Pr_{P}(p|\lambda) = m_{p}^\lambda$. Moreover, as we have shown the Markov chain conditions for $\nu_{Q^{n}_{1}E'}$ and without loss of generality, Eve can only do better using a state of the form $\nu$, we can conclude we may use the EAT (<Ref>) to prove security.

Having shown that the Markov chain conditions follow from <ref>, it remains to show that condition:A and condition:B are equivalent. To do so, we first note that the commutation relation $[M_{sp},M_{p'}] = 0$ in <ref> is a direct consequence of the block diagonal conditions in condition:A. Conversely, we note that by construction the POVM elements $M_p$'s are linear combinations of the measurement operators $M_{sp}$'s. Therefore, the commutation relation in <ref> implies the commutation relation $[M_p,M_{p'}] = 0$ for all $p,p' \in \cP$. This consequently implies the existence of a joint basis that simultaneously diagonalizes the operators $M_p$'s. We can thus find an orthogonal decomposition $V^\lambda$ so that $M_p = \bigoplus_\lambda m_p^\lambda \idm_{V^\lambda}$. Using the commutation relation in <ref> a second time implies that the operators $M_{sp}$ must be block diagonal along the same subspaces $V^{\lambda}$'s.

We note this proof does not change for Rényi entropies as they also satisfy strong subadditivity.

§ SECURITY OF QKD USING EAT WITHOUT SMOOTHING

In this appendix, we present the necessary technical lemmas and the resulting proof for <Ref>. The primary tool is Dupuis' recent result on applying privacy amplification without smoothing [Dupuis, 2021]. However, we will also need to prove a max-tradeoff function upper bound on $H^{\uparrow}_{\alpha}(S_{1}^{n}|P_{1}^{n}E)_{\rho_{|\Omega}}$. We note that in the original work [Dupuis et al., 2020] a max-tradeoff function upper bound for $H^{\uparrow}_{\alpha}$ is implied to be straightforward given the max-tradeoff result presented in said work and simply not presented because upper bounding an alternative entropy will result in a tighter bound on $H^{\ve}_{\max}$ <cit.>. For completeness, we present our proof of such a bound. Throughout this appendix we present results using the Greek letters $(\alpha,\beta,...)$ that will be ultimately used in our key length security result rather than always using $\alpha$ for the Rényi entropy, so that it is easier to see how the results combine. We refer to <Ref> for a summary of common notations. We do however use $A_{i}$ and $B_{i}$ rather than $S_{i}$ and $P_{i}$ respectively from the main text.

§.§ Background Rényi divergence results

Here we present the special cases of the Rényi entropy chain rules which we will need in this section. We refer to <Ref> for basic entropic notation used in this work.

Let $\rho_{ABC} \in \Density(ABC)$, $\tau_{C} \in \Density(C)$, $\alpha,\beta,\gamma \in (1/2,1) \cup (1,\infty)$ such that $\frac{\alpha}{\alpha-1} = \frac{\beta}{\beta-1} + \frac{\gamma}{\gamma-1}$.

* Case 1: If $(\alpha-1)(\beta-1)(\gamma-1) > 0$,   $ H_{\beta}^{\uparrow}(A|BC)_{\rho} \leq H_{\alpha}(\rho_{ABC}||\tau_{C}) - H_{\gamma}(\rho_{BC}||\tau_{C}) \ . $

* Case 2: If $(\alpha-1)(\beta-1)(\gamma-1) < 0$,   $ H_{\alpha}(\rho_{ABC}||\tau_{C}) \leq H^{\uparrow}_{\beta}(A|BC)_{\rho} + H_{\gamma}(\rho_{BC}||\tau_{C}) \ . $

In Ref. [Dupuis, 2015], the result is presented with the product $(\alpha-1)(\beta-1)(\gamma-1)$ to be bounded by one rather than zero. If one checks the conditions used to derive the theorem (<cit.>), it only depends on the sign of the product. This has been realized in previous works, e.g. [Tomamichel, 2016].

Let $\rho_{ABC} \in \Density(ABC)$, $\tau_{C} \in \Density(C)$. Let $\alpha,\beta,\delta,\eta,\gamma,\zeta \in (1/2,1) \cup (1,\infty)$.

* Let $(\eta-1)(\delta-1)(\zeta-1) > 0$, $\frac{\eta}{\eta-1} = \frac{\delta}{\delta-1} + \frac{\zeta}{\zeta-1}$ and $B$ be a trivial (one-dimensional) register. Then
$ H_{\delta}^{\uparrow}(A|C)_{\rho} \leq H_{\eta}(\rho_{AC}||\tau_{C}) + D_{\zeta}(\rho_{C}||\tau_{C}) \ . $

* Let $(\alpha-1)(\beta-1)(\delta-1) < 0$ and $\frac{\beta}{\beta-1} = \frac{\alpha}{\alpha-1} + \frac{\delta}{\delta-1}$. Then $H^{\uparrow}_{\beta}(AB|C)_{\rho} \leq H^{\uparrow}_{\alpha}(A|BC)_{\rho} + H^{\uparrow}_{\delta}(B|C)_{\rho} \ . $

Item 1 follows from Item 1 of <Ref> by noting if $B$ is trivial, the $B$ register may be dropped. Because $H_{\gamma}(\rho_{BC}||\tau_{C}) = -D_{\gamma}(\rho_{C}|| \idm_{\mathbb{C}} \otimes \tau_{C})$, the negative signs cancel. Dropping the register $B$ and setting $\beta \to \delta$, $\alpha \to \eta$, and $\gamma \to \zeta$ completes the proof. Item 2 follows from Item 2 of <Ref> by letting $\tau_{C}$ be the optimizer for $H^{\uparrow}_{\alpha}(AB|C)_{\rho}$. Then by definition, $H^{\uparrow}_{\gamma}(B|C)_{\rho} \geq H_{\gamma}(\rho_{BC}||\tau_{C})$. Relabeling by $\alpha \to \beta$, $\beta \to \alpha$,  $\gamma \to \delta$ completes the proof.

§.§ Applying privacy amplification without smoothing

In Ref. [Dupuis, 2021], it was shown that privacy amplification could be performed without smoothing. While it was stated as holding for strongly 2-universal hashing functions, it is straightforward to show that the proof is the same for a general family of 2-universal hash functions. Recall that a family of 2-universal hash functions is the pair $(p_{F},\cF)$ where $\cF$ is a set of functions from discrete alphabet $\cX$ to discrete alphabet $\cZ$ and $p_{f}$ is a probability distribution over $\cF$ such that $\Pr_{f}[f(x) = f(x')] \leq |\cZ|^{-1}$ for all $x \neq x' \in \cX$. Altering notation to better fit for our purposes, Theorem 8 of Ref. [Dupuis, 2021] is in terms of $\mathbb{E}_{f \in \cF} \left \| \rho_{ZE}^{f} - \frac{1}{|\{0,1\}^{\ell}|} \mathbb{1}_{Z} \otimes \rho_{E} \right \|_{1}$ where $\rho^{f}_{ZE}$ is $\rho_{XE}$ after the hash function $f$ has been applied to register $X$ and $\cZ = \{0,1\}^{\ell}$. Using that announcing the choice of hash function $f \in \cF$ will make the state block diagonal in the register $F$ that stores this announcement, it is clear that

\begin{align*}
\|\rho_{ZEF} - \frac{1}{|\{0,1\}^{\ell}|} \mathbb{1}_{Z} \otimes \rho_{EF} \|_{1} &= \sum_{f} p(f) \|\rho^{f}_{ZE} -  \frac{1}{|\{0,1\}^{\ell}|} \mathbb{1}_{Z} \otimes \rho_{E} \|_{1} \\
&= \mathbb{E}_{f} \|\rho^{f}_{ZE} - \frac{1}{|\{0,1\}^{\ell}|} \mathbb{1}_{Z} \otimes \rho_{E} \|_{1} \ ,
\end{align*}

so we state the result in the fashion more commonly used in QKD.

Let $\rho_{XE} \in \mathrm{D}(XE)$ be a classical-quantum state where $X \cong \mathbb{C}^{|\cX|}$ where $\cX$ is some finite set. Let $(p_{f},\cF)$ be a family of two-universal hash functions from $\cX \to \cZ$ and $\cZ = \{0,1\}^{\ell}$. Let $\alpha \in (1,2)$. Then

\begin{align*}
\left \| \rho_{ZEF} - \frac{1}{|\{0,1\}^{\ell}|} \mathbb{1}_{Z} \otimes \rho_{EF} \right \|_{1} \leq  2^{\frac{2}{\alpha} - 1} \cdot 2^{\frac{1-\alpha}{\alpha} \left( H_{\alpha}^{\uparrow}(X|E)_{\rho} - \ell \right)} \ ,
\end{align*}

where $F$ is the register storing the announcement of the hash function.

From this we obtain the following corollary immediately.

Let $\rho_{XE{|\Omega}} \in \mathrm{D}(XE)$ be a classical-quantum state. Let $\varepsilon_{sec} := \frac{1}{2} \cdot 2^{\frac{2}{\alpha} - 1} \cdot 2^{\frac{1-\alpha}{\alpha} \left( H_{\alpha}^{\uparrow}(X|E)_{\rho} - \ell \right)}$ where $\alpha \in (1,2)$. Then for an $\varepsilon_{sec}$-secret key, the length of the key, $\ell$, must satisfy the following bound:

\begin{align*}
\ell \leq H^{\uparrow}_{\alpha}(X|E)_{\rho} - \frac{\alpha}{\alpha-1}\log(\frac{1}{\vSec}) + 2\ .
\end{align*}

Starting from how we defined $\vSec$:

\begin{align*}
& \vSec \leq 2^{\frac{2}{\alpha} - 2} \cdot 2^{\frac{1-\alpha}{\alpha} \left( H_{\alpha}^{\uparrow}(X|E)_{\rho} - \ell \right)} \\
\Rightarrow & \log(\vSec) \leq \frac{2}{\alpha} - 2 + \frac{1-\alpha}{\alpha} \left( H_{\alpha}^{\uparrow}(X|E)_{\rho} - \ell \right) \\
\Rightarrow & \frac{1-\alpha}{\alpha}\ell \leq \frac{2}{\alpha} - 2 + \frac{1-\alpha}{\alpha} H_{\alpha}^{\uparrow}(X|E)_{\rho} + \log(\frac{1}{\vSec})\\
\Rightarrow & \ell \leq H^{\uparrow}_{\alpha}(X|E)_{\rho} + \frac{\alpha}{1-\alpha}\log(\frac{1}{\vSec}) + 2 \ .
\end{align*}

Pulling a negative sign out of the $\frac{\alpha}{1-\alpha}$ term completes the proof.

Note we added the $\frac{1}{2}$ term in defining $\vSec$ because trace distance should be divided by two for the operational interpretation.

§.§ Entropy Accumulation Theorem for upper bound on Lg

In this section we prove an upper bound on $H^{\uparrow}_{\delta}$ in terms of a max-tradeoff function. While almost all of the work is done by [Dupuis et al., 2020], we split it into two pieces as we will need to use a chain rule and also as it allows us to specify what results of [Dupuis et al., 2020] we use at each step. As explained earlier, this result is implied to be expected to exist in some form in <cit.>. We present it in its entirety for rigour.

As we switched the secret and public register notation, we emphasize in the current notation the Markov conditions are:

\begin{align}\label{eqn:Markov_cond_alt}
A_1^{i-1} \leftrightarrow B_1^{i-1}  E \leftrightarrow B_{i} \qquad \forall i \in \{1, \ldots, n\} \ .
\end{align}

We proceed by using the original entropy price function which we know is sub-optimal in the second-order terms, but that will not matter for our purposes. For every $i$, we use a CPTP map $\mathcal{D}_{i}: X_{i} \to X_{i}D_{i}\overline{D}_{i}$

$$ \mathcal{D}_{i}(W_{X_{i}}) = \sum_{x \in \cX} \bra{x} W_{X_{i}} \ket{x} \dyad{x} \otimes \tau(x)_{D_{i}\overline{D}_{i}} \ , $$

where $\tau(x)_{D_{i}\ol{D}_{i}}$ is such that $H(D_{i}|\ol{D}_{i})_{\tau(x)} = \overline{g} -f(\delta_{x})$, $f$ is a min-tradeoff function, $[g_{\min},g_{\max}]$ is the smallest real interval containing $f(\PP(\cX))$ and $\overline{g} := (g_{\min} + g_{\max})/2$. This is possible by letting $\tau(x)_{D_{i}\overline{D}_{i}}$ be a mixture of the maximally entangled state and the maximally mixed state. Following the argument from <cit.>, this can be done if $|D_{i}| \leq \exp(\lceil \|\nabla f\|_{\infty} \rceil)$. We also note the general definition $\ol{\rho} := (\cD_{n} \circ \hdots \circ \cD_{1})(\rho)$. With all of this specified, we begin with our equivalent of Claim 4.6 of [Dupuis et al., 2020].

Let $\delta \in [1/2,\infty)$. Assuming the Markov chain conditions are satisfied [<Ref>], then

$$ H^{\uparrow}_{\delta}(A^{n}_{1}|B^{n}_{1}E)_{\rho_{|\Omega}} \leq H^{\uparrow}_{\delta}(A^{n}_{1}D^{n}_{1}|B^{n}_{1}E\ol{D}^{n}_{1})_{\overline{\rho}_{|\Omega}} + nh - n\ol{g} \ ,$$

where $h \in \mathbb{R}$ that satisfies the conditions assumed in <Ref> and $\ol{g}$ is as defined above.

First note that

$$ \overline{\rho}_{A^{n}_{1}X^{n}_{1}B^{n}_{1}E\overline{D}^{n}_{1}|\Omega} = \frac{1}{\rho[\Omega]} \sum_{x^{n}_{1} \in \Omega} \dyad{x^{n}_{1}} \otimes \rho_{A^{n}_{1}B^{n}_{1}E,x^{n}_{1}} \otimes \Tr_{D^{n}_{1}}(\tau(x^{n}_{1})_{D^{n}_{1}\ol{D}^{n}_{1}}) \ . $$

Note that $\Tr_{D_{i}}(\tau(x_{i})_{D_{i}\ol{D}_{i}}) = \frac{1}{\abs{\ol{D}_{i}}} \idm_{\ol{D}_{i}}$ for all $i$ and $x_{i}$ because $\tau(x_{i})$ is a mixture of the maximally mixed and maximally entangled state. It follows we know that register is independent of the rest of the registers and that

\begin{align}\label{eq:marginal_indep} \overline{\rho}_{A^{n}_{1}X^{n}_{1}B^{n}_{1}E\overline{D}^{n}_{1}|\Omega} = \frac{1}{\rho[\Omega]} \sum_{x^{n}_{1} \in \Omega} \dyad{x^{n}_{1}} \otimes \rho_{A^{n}_{1}B^{n}_{1}E,x^{n}_{1}} \otimes \overline{\rho}_{\ol{D}^{n}_{1}} \ .
\end{align}

It follows the state is invariant under tracing off $\overline{\rho}_{\ol{D}^{n}_{1}}$ and re-appending it. Denote this map $\mathcal{R}$. By data-processing,

\begin{align}\label{lemma1-entprice1:ineq}
-D_{\delta}(\rho_{A^{n}_{1}X^{n}_{1}B^{n}_{1}E\ol{D}^{n}_{1}}||\idm_{A^{n}_{1}X^{n}_{1}}\otimes \sigma_{B^{n}_{1}E\ol{D}^{n}_{1}})_{\ol{\rho}_{|\Omega}} \, \leq & \, -D_{\delta}(\mathcal{R}(\rho_{A^{n}_{1}X^{n}_{1}B^{n}_{1}E\ol{D}^{n}_{1}})||\mathcal{R}(\idm_{A^{n}_{1}X^{n}_{1}}\otimes  \sigma_{B^{n}_{1}E\ol{D}^{n}_{1}}))_{\ol{\rho}_{|\Omega}} \nonumber \\
= & \,
-D_{\delta}(\rho_{A^{n}_{1}X^{n}_{1}B^{n}_{1}E\ol{D}^{n}_{1}}||\idm_{A^{n}_{1}X^{n}_{1}} \otimes \ol{\sigma}_{B^{n}_{1}E\ol{D}^{n}_{1}})_{\ol{\rho}_{|\Omega}} \ ,
\end{align}

where $\ol{\sigma}_{B^{n}_{1}E\ol{D}^{n}_{1}}= \sigma_{B^{n}_{1}E} \otimes \ol{\rho}_{\ol{D}^{n}_{1}}$. This implies that $H^{\uparrow}_{\delta}(A^{n}_{1}X^{n}_{1}|B^{n}_{1}E\ol{D}^{n}_{1})_{\overline{\rho}_{|\Omega}}$ is obtained by a maximizer of the form $\ol{\sigma}_{B^{n}_{1}E\ol{D}^{n}_{1}}$.

Next we recall Lemma 3.1 of [Dupuis et al., 2020] (with terms moved around):

$$ -D_{\delta}(\rho_{A_{1}B}||\mathbb{1}_{A_{1}} \otimes \sigma_{B}) +  H_{\delta}(A_{2}|A_{1}B)_{\nu} = -D_{\delta}(\rho_{A_{1}A_{2}B}||\mathbb{1}_{A_{1}A_{2}} \otimes \sigma_{B})  \ , $$

for any $\sigma_{B}$ where

\begin{align*}
\nu_{A_{1}A_{2}B} = \nu^{\frac{1}{2}}_{A_{1}B}\rho_{A_{2}|A_{1}B}\nu^{\frac{1}{2}}_{A_{1}B} \, \text{ where } \, \nu_{A_{1}B} = \frac{\left(\rho^{\frac{1}{2}}_{A_{1}B}\sigma_{B}^{\frac{1-\alpha}{\alpha}}\rho^{\frac{1}{2}}_{A_{1}B} \right)^{\alpha}}{\tr\left(\rho^{\frac{1}{2}}_{A_{1}B}\sigma_{B}^{\frac{1-\alpha}{\alpha}}\rho^{\frac{1}{2}}_{A_{1}B} \right)^{\alpha}} \ .
\end{align*}
Making the substitutions $A_{1} = A^{n}_{1}X^{n}_{1}$, $A_{2} = D^{n}_{1}$, $B=B^{n}_{1}E\overline{D}^{n}_{1}$ and letting $\sigma = \ol{\sigma}_{B^{n}_{1}E\ol{D}^{n}_{1}}$ be the optimizer of $H^{\uparrow}_{\delta}(A^{n}_{1}X^{n}_{1}|B^{n}_{1}E\ol{D}^{n}_{1})_{\ol{\rho}_{|\Omega}}$, we obtain

\begin{align*}
H^{\uparrow}_{\delta}(A^{n}_{1}X^{n}_{1}|B^{n}_{1}E\ol{D}^{n}_{1})_{\overline{\rho}_{|\Omega}} + H_{\delta}(D^{n}_{1}|A^{n}_{1}X^{n}_{1}B^{n}_{1}E\ol{D}^{n}_{1})_{\nu} & = -D_{\delta}(\overline{\rho}_{A^{n}_{1}X^{n}_{1}D^{n}_{1}B^{n}_{1}E\overline{D}^{n}_{1}|\Omega} || \mathbb{1}_{A^{n}_{1}X^{n}_{1}D^{n}_{1}} \otimes \ol{\sigma}_{B^{n}_{1}E\ol{D}^{n}_{1}}) \\
& \leq H^{\uparrow}_{\delta}(A^{n}_{1}X^{n}_{1}D^{n}_{1}|B^{n}_{1}E\overline{D}^{n}_{1})_{\overline{\rho}_{|\Omega}} \ ,
\end{align*}

where the second inequality is by the definition of $H^{\uparrow}_{\delta}$. Now the goal is to simplify.

* $H^{\uparrow}_{\delta}(A^{n}_{1}X^{n}_{1}|B^{n}_{1}E\ol{D}^{n}_{1})_{\overline{\rho}_{|\Omega}} = H^{\uparrow}_{\delta}(A^{n}_{1}|B^{n}_{1}E)_{\rho_{|\Omega}}$ as <cit.> allows us to remove the $X^{n}_{1}$ register and $\ol{D}^{n}_{1}$ is independent of everything as shown in <Ref>.

* $H_{\delta}(D^{n}_{1}|A^{n}_{1}X^{n}_{1}B^{n}_{1}E\overline{D}^{n}_{1})_{\nu} = H_{\delta}(D^{n}_{1}|\ol{D}^{n}_{1}X^{n}_{1})_{\nu}$ as <cit.> still holds because our $\nu$ is of the same form.

* $H^{\uparrow}_{\delta}(A^{n}_{1}X^{n}_{1}D^{n}_{1}|B^{n}_{1}E\ol{D}^{n}_{1})_{\overline{\rho}_{|\Omega}} = H^{\uparrow}_{\delta}(A^{n}_{1}D^{n}_{1}|B^{n}_{1}E\ol{D}^{n}_{1})_{\overline{\rho}_{|\Omega}}$ by <cit.>, as the proof for this equation still holds in our setting.

Therefore we have simplified to

\begin{align*}
H^{\uparrow}_{\delta}(A^{n}_{1}|B^{n}_{1}E)_{\rho_{|\Omega}} + H_{\delta}(D^{n}_{1}|\ol{D}^{n}_{1}X^{n}_{1})_{\nu} \leq H^{\uparrow}_{\delta}(A^{n}_{1}D^{n}_{1}|B^{n}_{1}E\ol{D}^{n}_{1})_{\ol{\rho}_{|\Omega}} \ .
\end{align*}

Using the fact that $H_{\delta}(D^{n}_{1}|\ol{D}^{n}_{1}X^{n}_{1})_{\nu} \geq n\overline{g} - nh$ as before <cit.> and by pushing that term over to the other side,

\begin{align*}
H^{\uparrow}_{\delta}(A^{n}_{1}|B^{n}_{1}E)_{\rho_{|\Omega}}  \leq H^{\uparrow}_{\delta}(A^{n}_{1}D^{n}_{1}|B^{n}_{1}E\ol{D}^{n}_{1})_{\ol{\rho}_{|\Omega}} - n\ol{g} + nh \ .
\end{align*}

Let $\delta \in (1/2,1)$, $\eta \in (1,1+2/V)$, $\zeta \in (1/2,1) \cup (1,\infty)$,  such that $\frac{\eta}{\eta-1} = \frac{\delta}{\delta-1} + \frac{\zeta}{\zeta-1}$ and $(\eta-1)(\delta-1)(\zeta-1) > 0$. Assuming the Markov chain conditions are satisfied [<Ref>], then

\begin{align*}H^{\uparrow}_{\delta}(A^{n}_{1}|B^{n}_{1}E)_{\rho_{|\Omega}} \leq nh - \frac{\delta}{1-\delta}\log(\rho[\Omega]) + n\frac{\eta - 1}{4}V^{2} \ ,
\end{align*}

where $V := 2\lceil \|\nabla f\|_{\infty} \rceil + 2\log(1+2d_{A})$.

Combining <Ref> with <cit.> applied to $\ol{\rho}$, which we can do by requiring $\delta \in (1/2,1)$ and noting $\ol{\rho} = \rho[\Omega]\ol{\rho}_{|\Omega} + (\ol{\rho} - \rho[\Omega]\ol{\rho}_{|\Omega})$,
one obtains

$$ H^{\uparrow}_{\delta}(A^{n}_{1}|B^{n}_{1}E)_{\rho_{|\Omega}} \leq H^{\uparrow}_{\delta}(A^{n}_{1}D^{n}_{1}|B^{n}_{1}E\ol{D}^{n}_{1})_{\overline{\rho}} - \frac{\delta}{\delta-1}\log(\frac{1}{\rho[\Omega]}) + nh - n\ol{g} \ .$$

Next we use <Ref> Item 1 with the substitutions $A = A^{n}_{1}D^{n}_{1}$, $C = B^{n}_{1}E\overline{D}^{n}_{1}$, $\tau_{C} = \ol{\rho}_{B^{n}_{1}E\overline{D}^{n}_{1}}$, where we will require $\eta \in (1,1 + 1/\log(1+d_{A}d_{D}))$.

\begin{align*}
H^{\uparrow}_{\delta}(A^{n}_{1}D^{n}_{1}|B^{n}_{1}E\ol{D}^{n}_{1})_{\overline{\rho}} \leq  H_{\eta}(A^{n}_{1}D^{n}_{1}|B^{n}_{1}E\ol{D}^{n}_{1})_{\overline{\rho}} + D_{\gamma}(\ol{\rho}_{B^{n}_{1}E\ol{D}^{n}_{1}}||\ol{\rho}_{B^{n}_{1}E\ol{D}^{n}_{1}} )
=  H_{\eta}(A^{n}_{1}D^{n}_{1}|B^{n}_{1}E\ol{D}^{n}_{1})_{\overline{\rho}} \ ,
\end{align*}

where the equality is by positive definiteness of Rényi divergences.
This gives us

$$H^{\uparrow}_{\delta}(A^{n}_{1}|B^{n}_{1}E)_{\rho_{|\Omega}} \leq  H_{\eta}(A^{n}_{1}D^{n}_{1}|B^{n}_{1}E\ol{D}^{n}_{1})_{\overline{\rho}} -  \frac{\delta}{\delta-1}\log(\frac{1}{\rho[\Omega]}) + nh - n\ol{g} \ .$$

We just need to bound the $H_{\eta}$ term, which follows the same type of argument as leading to <cit.>, as noted at the end of the proof of <cit.>. We have

\begin{align*}
H_{\eta}(A^{n}_{1}D^{n}_{1}|B^{n}_{1}E\ol{D}^{n}_{1})_{\overline{\rho}} & \leq \sum_{i} \underset{\omega_{R_{i-1}R}}{\sup} H_{\eta}(A_{i}D_{i}|B_{i}\overline{D}_{i}R)_{(\mathcal{D}_{i}\circ \mathcal{M}_{i})(\omega)} \\
&  \leq \sum_{i} \underset{\omega_{R_{i-1}R}}{\sup} H(A_{i}D_{i}|B_{i}\overline{D}_{i}R)_{(\mathcal{D}_{i}\circ \mathcal{M}_{i})(\omega)} + n(\eta - 1)\log^{2}(1+2d_{A}d_{D}) \\
& \leq \sum_{i} \underset{\omega_{R_{i-1}R}}{\sup} H(A_{i}D_{i}|B_{i}\overline{D}_{i}R)_{(\mathcal{D}_{i}\circ \mathcal{M}_{i})(\omega)} + n\frac{\eta-1}{4}V^{2} \ ,
\end{align*}

where the first line is because the Markov conditions are satisfied even including the $D_{i}\ol{D}_{i}$ registers due to our assumption that the Markov conditions in <Ref> hold[We omit the proof of this implication; see the proof of <cit.> which contains proof of this.] so we can apply <cit.>, the second is by applying <cit.> which we can do by our restriction on $\eta$, and the third is by definition of $V$. Lastly one can show $H(A_{i}D_{i}|B_{i}\ol{D}_{i}R)_{(\mathcal{D}_{i}\circ \mathcal{M}_{i})(\omega)} \leq \ol{g}$ <cit.>. Combining these points gets us our theorem.

§.§ QKD security proof with Rényi entropies

We now can present the proof of <Ref>. In the main text we present physical and virtual QKD protocols (<Ref> and <Ref> respectively). As explained in the main text, they are equivalent and so the following security proof holds for both. From a technical viewpoint, we use the EAT which holds for sequential processes, so the security is most directly proven for the virtual QKD protocol because it is sequential.

By the equivalence of <Ref> and <Ref>, which is by construction, proving the security of <Ref> is equivalent to proving the security of <Ref>. We refer to <Ref> in the proof, but this is just for the ease of the reader to link to the main text and <Ref>'s sequential presentation. Let $\Omega'$ be the event that <Ref> does not abort (i.e. $\Omega$ is satisfied) and error correction verification accepts (i.e.  $\hash(\mathbf{Z}) = \hash(\mathbf{\widehat{Z}})$). Let $\Omega''$ be the event that <Ref> does not abort and error correction verification passes. Let $\tilde{\rho}_{|\Omega''}$ be the output of the <Ref> conditioned on not aborting and error correction verification passing and $\rho_{|\Omega'}$ be the output of <Ref> conditioned on not aborting and error correction verification passing.

Fundamentally, we are interested in the entropy of the raw key which excludes the registers discarded in the general sifting step or the registers used for parameter estimation. As defined in <Ref>, $\mathbf{Z} \equiv \ol{A}^{n}_{1} \setminus (\ol{A}_{\mathcal{S}} \cup \ol{A}_{\mathcal{T}})$. However, we note that Alice announces $\ol{A}_{\mathcal{T}}$ in <Ref>, making it part of what is conditioned on, and $\ol{A}_{\mathcal{S}}$ is determined entirely by the registers $\widetilde{A}^{n}_{1}$, $\widetilde{B}^{n}_{1}$, and $T^{n}_{1}$. In other words, it is clear by <Ref> that there exists a deterministic function $f$ which can reconstruct $\ol{A}_{\cS},\ol{A}_{\cT}$ using a map of the form $\sum_{(s,p)} \dyad{s} \otimes \dyad{p} (\cdot) \dyad{s} \otimes \dyad{p} \otimes \dyad{f(s,p)}_{\ol{A}_{\cS}\ol{A}_{\cT}}$. Therefore, by <cit.>,

$$ H_{\alpha}^{\uparrow}(\mathbf{Z}|\widetilde{A}^{n}_{1}\widetilde{B}^{n}_{1} T^{n}_{1} \ol{A}_{\mathcal{T}} C E)_{\tilde{\rho}_{|\Omega''}} = H_{\alpha}^{\uparrow}(\ol{A}^{n}_{1}|\widetilde{A}^{n}_{1}\widetilde{B}^{n}_{1} T^{n}_{1} \ol{A}_{\mathcal{T}} C E)_{\tilde{\rho}_{|\Omega''}} \ . $$

We can handle the classical communication cost of error correction by <cit.>:

\begin{align}
H^{\uparrow}_{\alpha}(\ol{A}^{n}_{1}|\widetilde{A}^{n}_{1}\widetilde{B}^{n}_{1} T^{n}_{1} \ol{A}_{\mathcal{T}} C E)_{\tilde{\rho}_{|\Omega''}} &\geq H^{\uparrow}_{\alpha}(\ol{A}^{n}_{1}|\widetilde{A}^{n}_{1}\widetilde{B}^{n}_{1} T^{n}_{1} \ol{A}_{\mathcal{T}} E)_{\tilde{\rho}_{|\Omega''}} - {\leak}_{\vEC} \\
& = H^{\uparrow}_{\alpha}(\ol{A}^{n}_{1}|\widetilde{A}^{n}\widetilde{B}^{n} T^{n}_{1} \ol{A}_{\mathcal{T}} E)_{\rho_{|\Omega'}} - {\leak}_{\vEC} \label{eqn:alt_thm_starting_point}
\end{align}

where $C$ is the register storing the classical communication due to error correction, and the equality comes from noting that $\rho_{\ol{A}^{n}_{1}\widetilde{A}^{n}_{1}\widetilde{B}^{n}_{1}T^{n}_{1}X^{n}_{1}E{|\Omega'}} = \tilde{\rho}_{\ol{A}^{n}_{1}\widetilde{A}^{n}_{1}\widetilde{B}^{n}_{1}T^{n}_{1}X^{n}_{1}E{|\Omega''}}$. We stress that Bob's private register, $\ol{B}^{n}_{i}$, for both the EAT and the QKD protocol, is excluded in the equality as they differ. We note that $\ol{A}_{\mathcal{T}}$ is conditioned upon as Alice publicly announced it, but $X^{n}_{1}$ is not conditioned upon as Bob computes it locally and does not need to announce it unless aborting.

With all of this addressed, the entropy term that we would like to calculate to perform privacy amplification is

\begin{align}\label{eq:goal_without_smoothing}
H^{\uparrow}_{\alpha}(\ol{A}^{n}_{1}|\widetilde{A}^{n}_{1}\widetilde{B}^{n}_{1} T^{n}_{1} \ol{A}_{\mathcal{T}} E)_{\rho_{|\Omega'}} \ .
\end{align}
This imposes one major difficulty: We need to find a way to relate this term to the term $H^{\uparrow}_{\beta}(\ol{A}^{n}_{1} \ol{B}^{n}_{1}|\widetilde{A}^{n}\widetilde{B}^{n} T^{n}_{1} E)_{\rho_{|\Omega'}}$ on the left-hand side of <Ref>, where the Entropy Accumulation Theorem can be applied.

Following derivations in the DI-QKD setting [Arnon-Friedman et al., 2018], but also handling the $\ol{A}_{\mathcal{T}}$ register, we use the following series of claims:

\begin{align}
H^{\uparrow}_{\alpha}(\ol{A}^{n}_{1}|\widetilde{A}^{n}_{1} \widetilde{B}^{n}_{1} T^{n}_{1} \ol{A}_{\mathcal{T}} E)_{\rho_{|\Omega'}}
&\geq H^{\uparrow}_{\alpha}(\ol{A}^{n}_{1}|\widetilde{A}^{n}_{1} \widetilde{B}^{n}_{1} T^{n}_{1} \ol{A}_{\mathcal{T}} \ol{B}^{n}_{1} E)_{\rho_{|\Omega'}}  \notag \\
&\geq H^{\uparrow}_{\beta}(\ol{A}^{n}_{1} \ol{B}^{n}_{1} \ol{A}_{\cT}|\widetilde{A}^{n}_{1}\widetilde{B}^{n}_{1} T^{n}_{1} E)_{\rho_{|\Omega'}} - H^{\uparrow}_{\delta}(\ol{B}^{n}_{1}\ol{A}_{\cT}|\widetilde{A}^{n}_{1}\widetilde{B}^{n}_{1} T^{n}_{1} E)_{\rho_{|\Omega'}} \notag \\
& \geq 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'}} - H^{\uparrow}_{\delta}(\ol{B}^{n}_{1}\ol{A}_{\cT}| T^{n}_{1} E)_{\rho_{|\Omega'}}
\label{eqn:mid_inequality} \ .
\end{align}

The first inequality is the data processing inequality for sandwiched Rényi entropies <cit.> for the specific choice of tracing out the $\ol{B}^{n}_{1}$ register. The second inequality is Case 2 of <Ref> with the substitutions $A = \ol{A}^{n}_{1}$, $B = \ol{A}_{\cT}\ol{B}^{n}_{1}$, $C = \wt{A}^{n}_{1}\wt{B}^{n}_{1}T^{n}_{1}E$, where we also demand $\alpha \in(1,2)$, $\delta \in (1/2,1)$. The last inequality is again using the data-processing inequality for the $H^{\uparrow}_\delta$ term and <cit.> for the $H^{\uparrow}_\beta$ term using that $\ol{A}_{\cT}$ may be generated using a deterministic mapping from $\ol{A}^{n}_{1}$ and $T^{n}_{1}$.

As <Ref> includes the term in <Ref>, we need to bound the $H^{\uparrow}_{\delta}$ term in <Ref>. We will do this using <Ref>. We use the replacements $A_{i} = \ol{A}_{\cT_{i}}\ol{B}_{i}$, $B_{i} = T_{i}$, and $E = E$, from which it is clear how to define the EAT maps for this process. We note it is okay to use $\ol{A}_{\mathcal{T}}$ as we may treat it as if it were actually $n$ registers where it is $\perp$ whenever $T_{i} \neq 0$. The Markov conditions trivially hold since $T_{i}$ uses seeded randomness. Then using the fact that $\ol{A}_{\cT_{i}}\ol{B}_{i} = \perp \times \perp$ except when $T_{i}=1$ which happens with probability $\gamma$, we construct the max-tradeoff function analytically by the following observation:

\begin{align}\label{eq:maxtradeoffconstruction}
H(\ol{A}_{\cT_{i}} \ol{B}_{i}|T_{i}R')_{\cM_{i}(\omega)} & \leq H(\ol{A}_{\cT_{i}}\ol{B}_{i}|T_{i})_{\cM_{i}(\omega)}\notag\\
& = (1-\gamma)H(\ol{A}_{\cT_{i}}\ol{B}_{i}|T_{i}=0)_{\cM_{i}(\omega)} + \gamma H(\ol{A}_{\cT_{i}}\ol{B}_{i}|T_{i}=1)_{\cM_{i}(\omega)} \notag \\
& \leq \gamma \log|\mathcal{A} \times \mathcal{B}|
\end{align}

where $\mathcal{A}$ and $\mathcal{B}$ are the alphabets of private outcomes Bob utilizes during parameter estimation. This tells us we can let the max-tradeoff function  $f_{\max}(\vect{q}) = \gamma \log |\mathcal{A} \times \mathcal{B}|$ for all $\vect{q} \in \mathbb{P}(\cX)$. This also implies $\|\nabla f_{\max}\|_{\infty} = 0$. Note that for <Ref> to hold, we require $\delta \in (1/2,1)$, which is why we demanded this in the first chain rule. Therefore, using <Ref>
we get

\begin{align}\label{eq:deltamaxtradeoff}
& H^{\uparrow}_{\delta}(\ol{A}_{\cT} \ol{B}^{n}_{1}|T^{n}_{1} E)_{\rho_{|\Omega'}} \leq n\gamma\log|\mathcal{A} \times \mathcal{B}| - \frac{\delta}{1-\delta}\log(\vAcc) + n(\eta-1)\log(1+2d_{S})
\end{align}

where we have replaced $\rho[\Omega]$ with $\rho[\Omega']$ and then assumed $\vAcc \leq \rho[\Omega']$.[Note in principle this is a free parameter, but it does imply a lower bound on the probability that the input will pass parameter estimation and error correction verification, which is why we label it $\vAcc$ for accept.] We have also defined $d_{S} = (|\cA|+1)(|\cB|+1)$.

Combining <Ref> and <Ref>,

\begin{align*}
H^{\uparrow}_{\alpha}(\ol{A}^{n}_{1}| \widetilde{A}^{n}_{1} \widetilde{B}^{n}_{1} T^{n}_{1} \ol{A}_{\mathcal{T}} E)_{\rho_{|\Omega'}}
&\geq 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\gamma\log|\mathcal{A} \times \mathcal{B}| \notag\\
& \hspace{0.75cm}
+\frac{\delta}{1-\delta}\log(\vAcc) - n(\eta-1)\log(1+2d_{S}) \ .
\end{align*}

We now apply the equivalent of <Ref> to the $H_{\beta}^{\uparrow}$ term. We can do this by our restriction on $\beta$ earlier along with noting on the relevant marginal that any frequency distribution $\q$ accepted in the event $\Omega'$ is by definition also accepted in the event $\Omega$ so the value of $h$ will hold. Therefore, the only formal change in <Ref> is using the replacement $\vEA \to \vAcc$. Therefore, we have that either the input state aborts with probability greater than $1-\vAcc$ or

\begin{equation}
\begin{aligned}
H^{\uparrow}_{\alpha}(\ol{A}^{n}_{1}| \widetilde{A}^{n}_{1} \widetilde{B}^{n}_{1} T^{n}_{1} \ol{A}_{\mathcal{T}} E)_{\rho_{|\Omega'}}
&>  n h - n \frac{(\beta-1)\ln 2}{2}V^{2} - \frac{\beta}{\beta-1} \log \frac{1}{\vAcc} - n(\beta-1)^{2} K_{\beta} \notag \\
& \hspace{0.75cm} - n\gamma\log|\mathcal{A} \times \mathcal{B}|
+ \frac{\delta}{1-\delta}\log(\vAcc) \notag \\
& \hspace{1.25cm} - n(\eta-1)\log(1+2d_{S}) \ .
\end{aligned}
\end{equation}

Grouping terms, the $\vAcc$ correction term is of the form $\frac{\beta-\delta}{(\beta+1)(1-\delta)}\log(\vAcc)$. Then, plugging this back into <Ref> and applying the leftover hash lemma for non-smooth entropies [Dupuis, 2021], <Ref>, resolves everything except that one has many conditions on $\alpha,\beta,\delta,\gamma,\eta,\zeta$.

To get the simplified conditions on $\alpha,\beta,\delta,\gamma,\eta,\zeta$ in the theorem, note the conditions on $\alpha,\beta,\delta$ are satisfied for $\beta \in (1,2),\delta \in (1/2,1), \alpha = \frac{-\beta +\delta}{-1+2\delta-\beta\delta}$. The conditions on $\delta \in (1/2,1),\eta \in (1,1+\log^{-1}(1+d_{S})),\zeta \in (1/2,1) \cup (1,\infty)$ are satisfied for the whole relevant range so long as $\zeta = \frac{-\delta + \eta}{-1+2\eta-\delta\eta}$, which does not enter into our key length. Finally, we note that $\eta > 1$, $\log(1+2d_{S}) > 1$, so $-n(\eta-1)\log(1+2d_{S}) < 0$, so this term is always a penalty on the key rate. In principle we would need to minimize $\eta$, but noting that $-n(\eta-1)\log(1+2d_{S})$ goes to $0$ as $\eta$ goes to $1$, and $\eta$ is free to tend towards $1$, we choose $\eta$ such that $-n(\eta-1)\log(1+2d_{S}) = -1$.

Lastly, we need to explain the security claim in the statement of the theorem. There are two cases. Either $\rho[\Omega] < \vAcc$ or $\rho[\Omega] \geq \vAcc$. If $\rho[\Omega] < \vAcc$, then for that input, the security is trivially bounded by $\vAcc$ by using <Ref> with the replacement $\Pr(\text{accept}) = \rho[\Omega] < \vAcc$. Therefore the focus is on the case $\rho[\Omega] \geq \vAcc$. First we consider the secrecy. Starting from the subnormalized state[Subnormalization is due to aborting the protocol on the input.] $\rho_{S_{A}EF}$ where $S_{A}:= h(\mathbf{Z})$ is the hashed key, $h$ is the hash function, and $F$ is the announcement of the hash function,

\begin{align*}
\frac{1}{2} \| \rho_{S_{A}EF} - |S_{A}|^{-1}\idm_{S_{A}} \otimes \rho_{EF} \|_{1}
= \frac{1}{2} \rho[\Omega'] \| \rho_{S_{A}F_{|\Omega'}} - |S_{A}|^{-1}\idm_{S_{A}} \otimes \rho_{EF_{|\Omega'}} \|_{1}
\leq \rho[\Omega'] \vSec \leq \vSec \ ,
\end{align*}

where we started from the subnormalized state, normalized it by the condition of passing, and in the last line used that <Ref> tells us the trace norm divided by two is at most $\vSec$. Therefore any input such that $\rho[\Omega'] \geq \vAcc$, the key is $\vSec$-secret.  Finally, we need to address correctness which is an upper bound on $\Pr[S_{A} \neq S_{B} \, \& \Omega']$. By the analysis of error correction verification using 2-universal hash functions [Renner, 2005], $\vEC$ is exactly what bounds this term, so we have the key is $\vEC$-correct. Therefore, when $\rho[\Omega'] \geq \vAcc$, the key is $\vSec + \vEC$-secure. Combining these points, we have the protocol is $\max\{\vAcc,\vSec+\vEC\}$-secure. Finally, noting that if $\vAcc < \vEC + \vSec$ you could increase to $\vAcc = \vEC + \vSec$ to increase the key length without changing the security claim, so without loss of generality $\vAcc \geq \vEC + \vSec$. As such, we can just say the protocol is $\vAcc$-secure.

We remark on an alternative key length that may be obtained largely following the same proof that allows us to express things in terms of $\vEA$ directly. This does not seem to provide a clear advantage over the previous proof. As such, we note that the use of <cit.> could presumably be replaced by <cit.> for the smoothed version, but we omit such a proof in this work.

Consider any QKD protocol which follows <Ref> and satisfies <Ref>. $\vEA,\vSec,\vEC \in (0,1]$, $\vECRob\in[0,1]$, such that $\vEA \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 $\vEA$-secure for key length

\begin{equation}\label{eq:KeyLength_without_smoothing_alt}
\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(\ve_{\mathrm{sec}}\cdot (1-\vECRob)) + 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.

We largely follow the previous proof with some modifications which we explain. We start at <Ref>. First we note that $\rho_{|\Omega} =\rho[\Omega'|\Omega]\rho_{|\Omega'} + (\rho_{|\Omega}-\rho[\Omega'|\Omega]\rho_{|\Omega'})$, where $[\Omega'|\Omega]$ denotes the event $\Omega'$ occurring conditioned on $\Omega$ occurring, i.e. the probability that error correction succeeds given we pass parameter estimation.[As the notation is a slight abuse of notation from conditional probability which would have $\rho[\text{EC accepts}|\Omega]$, we clarify. Recall one starts with the output after error correction $\rho$. We can partition the total state according to the events error correction and parameter estimation pass, $\Omega'$, just parameter estimation passes, $\Omega \setminus \Omega'$, and everything else, so that $\rho = \rho[\Omega']\rho_{|\Omega'} + \rho[\Omega\setminus \Omega']\rho_{\Omega \setminus \Omega'} + (\rho - \rho[\Omega']\rho_{|\Omega'} + \rho[\Omega\setminus \Omega']\rho_{\Omega \setminus \Omega'})$. Then by definition, $\rho_{|\Omega} = \rho[\Omega]^{-1}(\rho[\Omega']\rho_{|\Omega'} + \rho[\Omega' \setminus \Omega] \rho_{|\Omega' \setminus \Omega})$. Recalling $\Omega'$ is $\Omega$ and error correction passes, we can think of $\rho[\Omega'|\Omega]:=\rho[\Omega']/\rho[\Omega]$ as the probability of error correction passing given parameter estimation.] Moreover, since ultimately $\alpha > 1$ will always hold on the conditions that complete the proof, we can apply <cit.> to determine

\begin{align*}
H^{\uparrow}_{\alpha}(\ol{A}^{n}_{1}|\widetilde{A}^{n}\widetilde{B}^{n} T^{n}_{1} \ol{A}_{\mathcal{T}} E)_{\rho_{|\Omega'}} & \geq H^{\uparrow}_{\alpha}(\ol{A}^{n}_{1}|\widetilde{A}^{n}\widetilde{B}^{n} T^{n}_{1} \ol{A}_{\mathcal{T}} E)_{\rho_{|\Omega}} - \frac{\alpha}{\alpha-1}\log(\frac{1}{\rho[\Omega'|\Omega]}) \\
& \geq  H^{\uparrow}_{\alpha}(\ol{A}^{n}_{1}|\widetilde{A}^{n}\widetilde{B}^{n} T^{n}_{1} \ol{A}_{\mathcal{T}} E)_{\rho_{|\Omega}} + \frac{\alpha}{\alpha-1}\log(1-\vECRob)
\end{align*}

where the second inequality follows from the assumption $\rho[\Omega'|\Omega] \geq 1-\vECRob$.[The choice of notation is as follows. The $\ve$-robustness of a protocol on an input $\rho$ is the probability of it aborting on that input [Renner, 2005]. Ideally, we want our error correction scheme to be $0$-robust whenever parameter estimation has passed, i.e. $\rho[\Omega'|\Omega] = 1$ is the ideal case. As such, the assumption we have made is roughly that if parameter estimation passes, then the error correction will be $\vECRob$-robust.] Everything through <Ref> is the same argument but with $\rho_{|\Omega}$. The only change this results in is that any term with $\vAcc \to \vEA$. Since we consider $\rho_{|\Omega}$, we can apply <Ref> directly, so we replace $\vAcc$ in previous proof with $\vEA$ again. Combining things and simplifying the greek alphabet parameters is the largely the same as before. This completes the proof.

As for the security claim. We split into two cases in the same fashion. In the case $\rho[\Omega] < \vEA$, the state is trivially $\vEA$ secure. In the case $\rho[\Omega] \geq \vEA$, we have identical analysis to the previous case. The correctness argument is the same as before, so the security claim is $\ve = \max\{\vEA,\vSec+\vEC\}$.

§ RELATION BETWEEN FIXED-LENGTH AND PROBABILISTIC ROUND-BY-ROUND PARAMETER ESTIMATION PROTOCOLS

In this appendix we provide the proof of <Ref>. Effectively, we need to describe the QKD protocol in enough detail that we can view the output as a (somewhat complicated) CQ state whose probability of certain sequences can be determined using the structure of the protocol. To do this, we first describe the general description of a device-dependent QKD protocol through the parameter estimation step in the most explicit formal fashion, i.e. in terms of conditional states. We then show how this relates to the output of the EAT subprotocol, and finally we relate conditional states of these two cases. This allows us to determine exactly how the security parameter relates in the two cases. We stress that the notation in this appendix slightly differs from that of the rest of the paper so as to keep things concise. In this appendix, we use registers $Q_AQ_B$ instead of register $Q$ to separate Alice's and Bob's registers. We try to keep the notation as close to the main text for consistency.

As explained in <Ref>, since we are considering device-dependent QKD protocols, we may make the assumption that the measurements by Alice and Bob are performed in an $n$-fold manner, i.e. $\mathcal{E}^{M} = \Phi_{\mathcal{P}}^{\otimes n}$ where $\Phi_{\mathcal{P}} : Q_AQ_B \to \mathbb{C}^{\abs{\cA \times \cB}}$ where, following the notation of <Ref>, $\cA \times \cB$ is a joint finite alphabet of Alice and Bob's outcomes for parameter estimation, and we dropped the subscript $i$ from the Hilbert spaces as traditionally device-dependent QKD assumes the dimension to be fixed in each round. Given this assumption, we may write the output state of the measurement as

\begin{align*}
(\mathcal{E}^{M} \otimes \id_{E})(\rho_{Q^{n}_{A,1} Q^{n}_{B,1}E}) = \sum_{(a^{n}_{1},b^{n}_{1},p^{n}_{1})} \dyad{a^{n}_{1}} \otimes \dyad{b^{n}_{1}} \otimes \dyad{p^{n}_{1}} \otimes \rho_{E}^{(a^{n}_{1},b^{n}_{1},p^{n}_{1})} \ ,
\end{align*}

where $a_{i}$, $b_{i}$ are outcomes of Alice's and Bob's private registers and outcomes of all public registers of the $i^{\text{th}}$ round are grouped as $p_{i}$, and $\rho_{E}^{(a^{n}_{1},b^{n}_{1},p^{n}_{1})}$ is the (subnormalized) conditional state of Eve.

Next Alice and Bob perform parameter estimation.[In <Ref>, sifting and the key map happen each round along with parameter estimation. In Renner's original framework [Renner, 2005], it is not the case as the sifting and key map happen afterwards in the blockwise processing, which is the reason for this discrepancy from the main text.] Canonically the assumption is they are going to pick a random subset of the $n$ signals of size $m$ and announce their respective outcomes on those $m$ rounds.[This is equivalent to applying a random permutation and then performing parameter estimation on the first $m$ indices, but to match the EAT, we do not reformat in this manner. We note an alternative model one might propose that seems to be intuitive is to perform probabilistic round-by-round testing, count the total number of tests at the end, and then a posteriori treat the protocol as having picked that many tests. This does not fit into a pre-existing universally composable security proof for fixed-length testing. In particular, it does not fit into the security proof method of [Renner, 2005].] Finally they decide if they continue the protocol or not based on those outcomes. That is, they have some set of observed sequences $\mathcal{Q} \subset {\cX'}^{\times m}$ which they accept on, where $\cX'$ is as defined in <Ref>. It follows that one could split $\mathcal{E}^{PE}$ as a channel which generates which rounds to test, a map where they make their announcements, and a map where they abort if the observations are not in a set of pre-agreed upon acceptable observations $\mathcal{Q}$:

$$ \mathcal{E}^{PE} = \mathcal{E}^{\mathcal{Q}} \circ \mathcal{E}^{PE,ann} \circ \mathcal{E}^{PE, test gen} \ . $$

Note that while fundamentally $\mathcal{Q}$ is a set of sequences of length $m$, $x^{m}_{1} \in {\cX'}^{\times m}$, it can trivially be extended to a set of sequences of length $n$, $x_{1}^{n} \in (\cX' \cup \{\perp\})^{\times n}$, which better matches the EAT and is denoted $\Omega$. In the case that it is a set of sequences of length $n$, it only makes sense for all sequences in $\Omega$ to have $n-m$ of the entries be the $\perp$ symbol. To match with EAT we mean this event $\Omega$ than aligns properly with extending $\cQ$.

Having completed the explanation of the protocol, we can see the natural definitions for these maps are:

$$ \mathcal{E}^{PE, test gen}(\alpha) = \frac{1}{|T_m|} \sum_{t^{n}_{1} \in T_{m}} \dyad{t^{n}_{1}} $$

where $T_{m} = \{x \in \{0,1\}^{n} : \text{Hamming Weight}(x) = m \}$.

\begin{align*}
\mathcal{E}^{PE,ann}(\rho_{A^{n}_{1}B^{n}_{1}T^{n}_{1}}) =& \sum_{(a^{n}_{1},b^{n}_{1},t^{n}_{1})} \dyad{\mathrm{x}^{\times n}(a^{n}_{1},b^{n}_{1},t^{n}_{1},p^{n}_{1})}_{X^{n}_{1}} \otimes \dyad{a^{n}_{1}} \\
& \hspace{6cm} \otimes \dyad{b^{n}_{1}} \otimes \dyad{p^{n}_{1}} \otimes \rho_{E}^{(a^{n}_{1},b^{n}_{1},p^{n}_{1})}
\end{align*}

where $\mathrm{x}(a_{i},b_{i},t_{i},p_{i}) = (a_{i} \times b_{i}) \in \cA \times \cB$ when $t_{i} = 1$ and otherwise equals $\perp$, i.e. $\mathrm{x}$ is the deterministic announcement function due to testing that constructs $x_{i} \in \cX$.

$$ \mathcal{E}^{\mathcal{Q}}(\rho_{X^{n}_{1}}) = \sum_{x^{n}_{1} \in \Omega} \dyad{x^{n}_{1}}\rho_{X^{n}_{1}}\dyad{x^{n}_{1}} \ ,$$

where we the event $\Omega$ as the set of sequences of length $n$ that satisfy $\mathcal{Q}$ as stated earlier.

Since $p_{i}$ is a function of $(a_{i},b_{i},t_{i})$ by construction of <Ref> and $x_{i}$ is a function of $(a_{i},b_{i},t_{i},p_{i})$, we are interested in the set $\{(a^{n}_{1},b^{n}_{1},t^{n}_{1}) \text{ such that } x^{n}_{1} \in \Omega \text{ with non-zero probability}\}$. Throughout, when we write a summation over something of the form  “$(a^{n}_{1},b^{n}_{1},t^{n}_{1}) : x^{n}_{1} \in \Omega$," we are indicating the set of sequences that result in $x^{n}_{1} \in \Omega$. Therefore, combining all of this, we find the output state after parameter estimation is

\begin{align*}
\widetilde{\rho}^{out}
=& \frac{1}{|T_{m}|} \sum_{\substack{(a^{n}_{1},b^{n}_{1},t^{n}_{1}) \, : x^{n}_{1} \in \Omega}} \dyad{\mathrm{x}^{\times n}(a^{n}_{1},b^{n}_{1},t^{n}_{1},p^{n}_{1})}_{X^{n}_{1}} \otimes \dyad{a^{n}_{1}} \\
& \hspace{5cm} \otimes \dyad{b^{n}_{1}} \otimes \dyad{p^{n}_{1}} \otimes \dyad{t^{n}_{1}} \otimes  \rho_{E}^{(a^{n}_{1},b^{n}_{1},p^{n}_{1})} \ ,
\end{align*}

where $ \widetilde{\rho}^{out} = (\mathcal{E}^{PE,ann} \circ \mathcal{E}^{PE,test gen} \circ \mathcal{E}^{M} \otimes \id_{E})(\rho_{Q^{A,n}_{1}{Q}^{B,n}_{1}E})$. We stress by construction of $\Omega$, that any element of $(a^{n}_{1},b^{n}_{1},t^{n}_{1}) : x^{n}_{1} \in \Omega$ has $t^{n}_{1} \in T_{m}$, which is why we don't restrict the space $T^{n}$. We will define the final output after sifting and the key map (but prior to error correction) as

\begin{align*}
\rho^{out}
=& \frac{1}{|T_{m}|} \sum_{(\hat{a}^{n}_{1},\hat{b}^{n}_{1},t^{n}_{1}) : x^{n}_{1} \in \Omega} \dyad{\mathrm{x}^{\times n}(\hat{a}^{n}_{1}, \hat{b}^{n}_{1},t^{n}_{1},p^{n}_{1})}_{X^{n}_{1}} \otimes \dyad{\hat{a}^{n}_{1}} \\
& \hspace{5cm}\otimes \dyad{\hat{b}^{n}_{1}} \otimes \dyad{p^{n}_{1}} \otimes \dyad{t^{n}_{1}} \otimes  \rho_{E}^{(\hat{a}^{n}_{1},\hat{b}^{n}_{1},p^{n}_{1})} \ ,
\end{align*}

where hats denoted updated registers, and the reason that we can define $\mathrm{x}$ on the updated sequence is that by assumption testing commutes with sifting and the key map, given the registers $T^{n}_{1}$.

This completes our account of the output state of parameter estimation in the fixed-length device-dependent QKD protocol. However, we will need these extra definitions when comparing to the output of the EAT protocol:

\begin{equation}
\begin{aligned}
\rho^{out}_{|\Omega_{sub}} = (\mathcal{E}^{\mathcal{Q}} \otimes \id_{E})(\rho^{out}) \qquad
\rho^{out}_{|\Omega} = \frac{1}{\Tr(\rho^{out}_{\Omega_{sub}})} \rho^{out}_{\Omega_{sub}} \ .
\end{aligned}
\end{equation}

Using the same notation as we did for the fixed-length device-dependent QKD protocol, it is straightforward from the effective tensor product structure of device-dependent QKD (<Ref>) that the output of the EAT protocol can be written as:

\begin{align*}
\rho_{EAT}^{out} =& \sum_{(\hat{a}^{n}_{1},\hat{b}^{n}_{1},t^{n}_{1}): x^{n}_{1} \in \Omega} \dyad{\mathrm{x}^{\times n}(\hat{a}^{n}_{1}, \hat{b}^{n}_{1},t^{n}_{1},p^{n}_{1})}_{X^{n}_{1}} \otimes \dyad{\hat{a}^{n}_{1}} \\
& \hspace{5cm} \otimes \dyad{\hat{b}^{n}_{1}} \otimes \dyad{p^{n}_{1}} \otimes \dyad{t^{n}_{1}} \otimes  \rho_{E}^{(\hat{a}^{n}_{1},\hat{b}^{n}_{1},p^{n}_{1})} \ .
\end{align*}

Our interest is then proving the relation of $\rho^{out}_{EAT}$ to $\rho^{out}$ to prove <Ref>.

Ultimately we need to argue about the probabilities of given sequences conditioned on passing, so we start by simplifying the joint probability of the sequences. For notational simplicity in this proof,  we let

$$\hat{r}_{i} := (\hat{a}_{i},\hat{b}_{i},p_{i}) \quad i \in [n] \hspace{5mm}\text{and}\hspace{5mm} \widehat{\cS}_{|\Omega} := \{(x^{n}_{1},r^{n}_{1},t^{n}_{1}) : x^{n}_{1} \in \Omega \} \ , $$

and $r_{i}$, $\cS_{|\Omega}$ are defined the same way but with the un-updated $a_{i},b_{i}$.
First consider $\rho^{in} \equiv \rho_{Q^{n}_{A,1} Q^{n}_{B,1}E}$ to the fixed-length protocol that satisfies data partitioning as in <Ref> (so that we consider the same announcement structure between the two settings for fair comparison). Then, for any non-zero probability sequence, we have:

\begin{align*}
\Pr(x^{n}_{1},r^{n}_{1},t^{n}_{1})
=  \Pr(r^{n}_{1},t^{n}_{1})
=  \Pr(t^{n}_{1})\Pr(r^{n}_{1})
=  \frac{1}{|T_{m}|}\Pr(r^{n}_{1}) \ ,
\end{align*}

where the first equality is because $x^{n}_{1}$ is produced by a deterministic function of the other sequences, the second equality is because $t^{n}_{1}$ is determined independent of the other sequences, and the third equality is because $t^{n}_{1}$ was uniformly chosen from the set $T_{m}$. Note that sifting and the key map, while deterministic, are not bijective in general. However, since accepting or not accepting a sequence is a deterministic function given $x^{n}_{1}$ which is a deterministic function of $(r^{n}_{1},t^{n}_{1})$ and doesn't change under updating, we have

\begin{align*}
\sum_{ (x^{n}_{1},\hat{r}^{n}_{1},t^{n}_{1}) \in \cS_{|\Omega}} \Pr(x^{n}_{1},\hat{r}^{n}_{1},t^{n}_{1})
=\sum_{ (x^{n}_{1},r^{n}_{1},t^{n}_{1}) \in \cS_{|\Omega}} \Pr(x^{n}_{1},r^{n}_{1},t^{n}_{1})
= \frac{1}{|T_{m}|} \sum_{(x^{n}_{1},r^{n}_{1},t^{n}_{1}) \in \cS_{|\Omega}} \Pr(x^{n}_{1}|r^{n}_{1},t^{n}_{1})\Pr(r^{n}_{1}) \ .
\end{align*}

Now we consider the EAT protocol. Note that the sequence $t^{n}_{1}$ is an i.i.d. sequence generated from sampling the distribution $Q =(1-\gamma , \gamma)^{T},$ whose probability is determined by the method of types. Following the notation used in [Cover and Thomas, 2005], we have $\Pr(t^{n}) = Q^{n}(t^{n}_{1})$ for any binary sequence $t^{n}_{1}$ sampled from $Q$ $n$ times. It follows,

\begin{align*}
\Pr(r^{n}_{1},t^{n}_{1})
=  \Pr(t^{n}_{1})\Pr(r^{n}_{1})
= Q^{n}(t^{n}_{1})\Pr(r^{n}_{1})  \ ,
\end{align*}

which, again using that acceptance is a deterministic function of  $(r^{n}_{1},t^{n}_{1})$,

\begin{align*}
\sum_{(x^{n}_{1},\hat{r}^{n}_{1},t^{n}_{1}) : x^{n}_{1} \in \Omega} \Pr(x^{n}_{1},\hat{r}^{n}_{1},t^{n}_{1})
=& \sum_{(x^{n}_{1},\hat{r}^{n}_{1},t^{n}_{1}) : x^{n}_{1} \in \Omega} \Pr(x^{n}_{1}|r^{n}_{1},t^{n}_{1})\Pr(r^{n}_{1},t^{n}_{1}) \\
=& \sum_{(x^{n}_{1},r^{n}_{1},t^{n}_{1}): x^{n}_{1} \in \Omega} Q^{n}(t^{n}_{1})\Pr(x^{n}_{1}|r^{n}_{1},t^{n}_{1})\Pr(r^{n}_{1}) \ ,
\end{align*}

where in the first line we stress we have kept the sum indexing over the non-updated registers, so the sum is independent of how they get updated conditioned on $x^{n}_{1} \in \Omega$. By <cit.>, we know $Q^{n}(t^{n}_{1}) = 2^{-n\left(H(f_{t}) - D(f_{t}||Q)\right)}$ where $f_{t}$ is the frequency distribution over $T$ induced by $t^{n}_{1}$ (i.e. the type). Therefore, if ${t}^{n}_{1}$ has Hamming weight $m$, since $m$ is defined as $m = \gamma n$, we have $Q^{n}({t}^{n}_{1}) = 2^{-nh(\gamma)}$ as the relative entropy term is zero, where $h(\cdot)$ is the binary entropy function. As a sequence will only be accepted if $t^{n}_{1}$ has Hamming weight $m$ and $x^{n}_{1}$ is acceptable, we have that

\begin{align*}
\rho^{out}_{EAT}[\Omega] & = \Tr(\sum_{(x^{n}_{1},\hat{r}^{n}_{1},t^{n}_{1}) \in \widehat{\cS}_{|\Omega}} \Pr(x^{n}_{1},\hat{r}^{n}_{1},t^{n}_{1}) \dyad{x^{n}_{1},\hat{r}^{n}_{1},t^{n}_{1}} \otimes \hat{\rho}_{E}^{(\hat{r}^{n}_{1})}) \\
& = \sum_{(x^{n}_{1},\hat{r}^{n}_{1},t^{n}_{1}) \in \widehat{\cS}_{|\Omega}} \Pr(x^{n}_{1},\hat{r}^{n}_{1},t^{n}_{1}) \\
& = 2^{-nh(\gamma)} \sum_{(x^{n}_{1},\hat{r}^{n}_{1},t^{n}_{1}) \in \cS_{|\Omega}} \Pr(x^{n}_{1}|r^{n}_{1},t^{n}_{1})\Pr(r^{n}_{1}) \\
& = 2^{-nh(\gamma)} |T_{m}| \sum_{(x^{n}_{1},\hat{r}^{n}_{1},t^{n}_{1}) \in \cS_{|\Omega}} \frac{1}{|T_{m}|} \Pr(x^{n}_{1}|r^{n}_{1},t^{n}_{1})\Pr(r^{n}_{1}) \\
& = 2^{-nh(\gamma)} |T_{m}| \Tr(\sum_{(x^{n}_{1},\hat{r}^{n}_{1},t^{n}_{1}) \in \widehat{\cS}_{|\Omega}} \Pr(x^{n}_{1},\hat{r}^{n}_{1},t^{n}_{1}) \dyad{x^{n}_{1}\hat{r}^{n}_{1},t^{n}_{1}} \otimes \hat{\rho}_{E}^{(\hat{r}^{n}_{1})}) \\
&= 2^{-nh(\gamma)} \binom{n}{m} \rho^{out}[\Omega] \ ,
\end{align*}

where the last line is because there are $\binom{n}{m}$ $n$-length bit strings with Hamming weight $m$.

To see that $\rho^{out}_{EAT|\Omega} = \rho^{out}_{|\Omega}$, we make the following observations:

* The set of sequences $(a^{n}_{1},b^{n}_{1},p^{n}_{1},t^{n}_{1})$ allowed by $\Omega$ is exactly the same in both cases.

* For any tuple of sequences $(a^{n}_{1},b^{n}_{1},p^{n}_{1})$, $p(a^{n}_{1},b^{n}_{1},p^{n}_{1})$ is the same for both protocols given that $\rho^{in}$ is the same and the measurement and announcement procedures are the same— it is just the distribution over $\Pr(t^{n}_{1})$ that differs.

* For every allowed tuple of sequences, the probability $\Pr(t^{n}_{1})$ is a fixed (uniform) value. Specifically, for allowed tuples of sequences, $\Pr(t^{n}_{1}) = 2^{-nh(\gamma)}$ for EAT, but $\Pr(t^{n}_{1}) =\frac{1}{|T_{m}|}$ for fixed test length. While the fixed value differs in the two cases, it cancels under the renormalization of conditioning the state on the allowed tuples of sequences.[For a simple example, imagine we have the two states: $\rho_{1} = y p_{00} \dyad{00} + x p_{01} \dyad{01} + x p_{10} \dyad{10} + z p_{11} \dyad{11}$ and $\rho_{2} = y' p_{00} \dyad{00} + x' p_{01} \dyad{01} + x' p_{10} \dyad{10} + z' p_{11} \dyad{11}$. Say we condition only on the strings of Hamming weight one. Then, we have $\rho_{1|\Omega} = \frac{1}{xp_{01} + xp_{10}}(x p_{01} \dyad{01} + x p_{10} \dyad{10})$ and $\rho_{2|\Omega} = \frac{1}{x'p_{01} + x'p_{10}}(x' p_{01} \dyad{01} + x' p_{10} \dyad{10})$. These conditional states are the same because the renormalization cancels the fixed (but different) pre-factor $x$ (resp. $x'$) for all the strings we are interested in.]

It therefore follows under the renormalization that the distribution over the sequences in both cases is identical (and $\rho_{E}^{(a^{n}_{1},b^{n}_{1},p^{n}_{1})}$ for each sequence is the same too since both are based on $(a^{n}_{1},b^{n}_{1},p^{n}_{1})$ followed by the introduction of an independent sequence and then deterministic functions).

Note this equivalence was able to be derived in effect because the testing in both cases is independent and the probability is uniform over sequences contained in the event $\Omega$ in question beyond the conditional probabilities that arise from the measurement, and since the measurements and announcements are the same process in both cases, this is not altered.

Finally, we explain the derivation of the bound presented below <Ref>:

\begin{align*}
\log( \vBar \rho^{out}_{EAT}[\Omega]) &= \log(\vBar) + \log(2^{-nh(\gamma)} {n \choose m} \rho^{out}[\Omega]) \\
&= \log(\vBar \rho^{out}[\Omega]) - nh(\gamma) + \log{n \choose m} \\
&\geq \log(\vBar \rho^{out}[\Omega]) + \log( \frac{e^2}{\sqrt{2\pi}} \sqrt{\gamma(1-\gamma)n}) \\
& = \log(\vBar \vPE) + \log( \frac{e^2}{\sqrt{2\pi}} \sqrt{\gamma(1-\gamma)n})     \ ,
\end{align*}

where the inequality follows from using  $\sqrt{2\pi} n^{n+1/2}e^{-n}\leq n! \leq en^{n+1/2}e^{-n}$  [Romik, 2000] to bound ${n \choose m}$.

§ SECURITY OF QKD USING EAT WITH SMOOTHING

In this section we present the security proof for smooth min-entropy rather than sandwiched Rényi entropies.

§.§ Background smooth entropy results

For completeness, in this section we present the max-tradeoff function and original version of the EAT [Dupuis et al., 2020] for max-tradeoff functions which we make use of in the security proof in this Section. Likewise, we give an account of the Leftover Hashing Lemma [Renner, 2005] and how it is applied in <Ref>.

We first state the min-tradeoff function in terms of smooth min-entropy.

Consider EAT channels $\cM_{1},...,\cM_{n}$ and $\rho_{S^{n}_{1}P^{n}_{1}X^{n}_{1}E}$ as defined in <Ref> such that it satisfies the Markov conditions [<Ref>]. Let $h \in \mathbb{R}$, $\alpha \in (1,2)$, $f$ be a min-tradeoff function for $\cM_1,\dots,\cM_n$,  and let $\bar{\varepsilon} \in (0,1)$. Let $S_{i}$ always be classical. Then, for any event $\Omega \subseteq \cX^n$ that implies $f(\freq{X_1^n}) \geqslant h$,

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

holds for

\begin{align}
V &= \sqrt{\Var{f}+2} + \log(2d_{S}^{2}+1) \; \label{eq: EAT constant V_EATv2} \\
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_EATv2}
\end{align}

where $\Max{f})$, $\Min{f}$, $\mathrm{Min}_{\Sigma}(f)$ and $\mathrm{Var}(f)$ are defined in <Ref> and $d_S = \max_{i\in [n]} |S_i|$ is the maximum dimension of the systems $S_i$.

Moreover, for a specific choice of $\alpha \in (1,2)$ [Dupuis and Fawzi, 2019],

\begin{align*}
H_{\min}^{\bar{\varepsilon}}(S_1^n | P_1^n E)_{\rho_{|\Omega}} & > n h - c \sqrt{n} - c'
\end{align*}

where $c$ and $c'$ are functions of $\vBar$, $d_{S}$, $\rho[\Omega]$, and properties of the tradeoff function as follows:

\begin{align}
c &= \sqrt{2 \ln 2} \left( \log (2d_S^2+1) + \sqrt{2 + \Var{f}} \right) \sqrt{ 1-2\log (\bar{\varepsilon} \rho[\Omega])}\; \label{eq:EAT_constant1} \\
c' &= \frac{35(1-2\log (\bar{\varepsilon} \rho[\Omega]))}{\left( \log(2 d_S^2 + 1) + \sqrt{2+\Var{f}} \right)^2} 2^{\log d_S + \Max{f} -  \MinSigma{f} } \ln^3\left( 2^{ \log d_S + \Max{f} -  \MinSigma{f}} + e^2 \right) \label{eq:EAT_constant2} \ .
\end{align}

Next we recall the notion of max-tradeoff function.

Following the notation of <Ref>. An affine function $f$ on $\mathbb{P}(\cX)$ is called max-tradeoff function $f$ for an EAT Channel $\cM_{i}$ if it satisfies

\begin{align*}
f(\vect{q}) \geq  \underset{\nu \in \Sigma_{i}(\vect{q})}{\sup} H(S_{i}|P_{i}R)_{\nu}, \hspace{.5cm} \forall \vect{q} \in \mathbb{P}(\cX) \ .
\end{align*}

We now state the EAT for max-tradeoff functions from [Dupuis et al., 2020].

Let $\mathcal{M}_1,\dots,\mathcal{M}_n$ be EAT channels and $\rho_{S_1^n P_1^n X_1^n E}$ be of the form in <Ref> which satisfies the Markov conditions from <Ref>. Let  $h \in \mathbb{R}$, let $f$ be an affine max-tradeoff function for $\mathcal{M}_1,\dots,\mathcal{M}_n$,  and let  $\bar{\varepsilon} \in (0,1)$. Then, for any event $\Omega \subseteq \mathcal{X}^n$ that implies $f(\freq{X_1^n}) \leqslant h$,

\begin{align}
H_{\max}^{\bar{\varepsilon}}(S_1^n | P_1^n E)_{\rho_{|\Omega}} & < n h +  c \sqrt{n}
\end{align}

holds for $c = 2 \bigl(\log (1+2 d_S) + \left\lceil \| \nabla f \|_\infty \right\rceil  \bigr) \sqrt{1- 2 \log (\bar{\varepsilon} \rho[\Omega])}$, where $d_S:= \max_{i\in [n]}\{|S_i|\}$.

This completes the statement of the EAT for max-tradeoff functions. We now turn our attention to the Leftover Hashing Lemma (LHL). The LHL tells us that applying a two-universal hash function to a somewhat secret string constructs a shorter $\varepsilon$-secret key. The notion of secrecy is measured by distance from uniformity given Eve's side-information.

Let $\rho_{XE} \in \mathrm{D}(XE)$ be a classical-quantum state where $X \cong \mathbb{C}^{|\Sigma|}$ where $\Sigma$ is some finite set. Let $\mathcal{F}$ be a family of two-universal hash functions from $\Sigma \to \{0,1\}^{\ell}$ and $\varepsilon > 0$. Then

\begin{align*}
\frac{1}{2} \left \| \rho_{F(X)EF} - \frac{1}{|\{0,1\}^{\ell}|} \mathbb{1}_{F(X)} \otimes \rho_{EF} \right \|_{1} \leq \varepsilon + 2^{- \frac{1}{2} (H^{\varepsilon'}_{\min}(X|E) - \ell - 2)} \ .
\end{align*}

From this we obtain the following corollary immediately.

Let $\rho_{XE} \in \mathrm{D}(XE)$ be a classical-quantum state. Let $\varepsilon_{sec} := \varepsilon' + 2^{- \frac{1}{2} (H^{\varepsilon'}_{\min}(X|E) - \ell - 2)}$ and $\varepsilon' > 0$. Let $\vPA := \varepsilon_{sec} - \varepsilon' > 0$. Then for an $\varepsilon_{sec}$-secret key, the length of the key, $\ell$, must satisfy the following bound:

\begin{align*}
\ell \leq H^{\varepsilon'}_{\min}(X|E) - 2\log(\frac{2}{\vPA}) \ .
\end{align*}

§.§ Technical lemmas for smooth entropy key rate

The following lemma shows that generating a classical register from the classical side information does not change the value of the smooth min-entropy.

For any CQ state $\rho_{AB} = \sum_i p_i \rho_A^i \ox \dyad{i}_B$ and $\rho_{ABC} = \sum_i p_i \rho_A^i \ox \dyad{i}_B \ox \dyad{f(i)}_C$ with a given function $f$, it holds that

\begin{align}
H_{\min}^{\varepsilon}(A|B) = H_{\min}^{\varepsilon}(A|BC).
\end{align}

This can be seen by defining isometry $V:\ket{i}_B \to \ket{i}_B\ket{f(i)}_C$. Then $\rho_{ABC} = V\rho_{AB}V^\dagger$. The result  then holds by the fact that the smooth min-entropy is invariant under local isometries <cit.>. Note that this holds for any function $f$ which may not necessarily be deterministic one (c.f. <cit.>).

Consider a CCQ state $\rho_{XPE} = \sum_{(x,p)} \dyad{x}{x} \otimes \dyad{p}{p} \otimes \rho_{E}^{(x,p)}$. Consider another classical register $Y$ which be constructed using a deterministic function on the registers $X$ and $P$, i.e. $f: X \times P \to Y$. That is, there exists an isometry, $V \equiv \sum_{(x,p)} \dyad{x} \otimes \dyad{p}{p} \otimes \ket{f(x,p)}_{Y}$ reconstructing $Y$ from $X$ and $P$. Then

\begin{align}
H^{\ve}_{\min}(YX|PE)_{V \rho V^{\dagger}} = H^{\ve}_{\min}(X|PE)_{\rho} \ .
\end{align}

To prove this proposition, we simply prove
\begin{align}
& H^{\ve}_{\min}(YX|PE)_{V \rho V^{\dagger}} \geq H^{\ve}_{\min}(X|PE)_{\rho} \label{eqn:propProofGoal1} \ ,\\
& H^{\ve}_{\min}(YX|PE)_{V \rho V^{\dagger}} \leq H^{\ve}_{\min}(X|PE)_{\rho} \ . \label{eqn:propProofGoal2}
\end{align}

We start with <Ref> as it is straightforward using previous results. Namely, we see:

\begin{align}
H^{\ve}_{\min}(YX|PE)_{V \rho V^{\dagger}} \geq H^{\ve}_{\min}(X|PE)_{V\rho V^{\dagger}} = H^{\ve}_{\min}(X|PE)_{\rho} \ .
\end{align}

The first inequality comes from the fact that the entropy of a classical register is non-negative <cit.>. The equality follows from noting that $\Tr_{Y} (V \rho V^{\dagger}) = \rho.$ Therefore we can focus on the other direction of the inequality.

By combining <cit.> we note the definition of the smooth min-entropy terms we are concerned with:

\begin{align}
H^{\ve}_{\min}(YX|PE)_{V\rho V^{\dagger}} & := \underset{\overline{\rho} \in \mathcal{B}^{\ve}(V \rho V^{\dagger})}{\max} \,
\underset{\overline{M}_{PE} \in \Density_{\leq}(PE) }{\max} \max \left\{\overline{\lambda} \in \mathbb{R} : \mathbb{1}_{Y} \otimes \mathbb{1}_{X} \otimes 2^{-\overline{\lambda}} \overline{M}_{PE} \geq  \overline{\rho}_{YXPE} \right\} \\
H^{\ve}_{\min}(X|PE)_{\rho} & := \underset{\widetilde{\rho} \in \mathcal{B}^{\ve}(\rho)}{\max} \, \underset{\widetilde{M}_{PE} \in \Density_{\leq}(PE) }{\max} \max \left\{ \widetilde{\lambda} \in \mathbb{R} : \mathbb{1}_{X} \otimes 2^{- \widetilde{\lambda}} \widetilde{M}_{PE} \geq  \widetilde{\rho}_{XPE} \right\} \ ,
\end{align}

where $\Density_{\leq}$ is the set of sub-normalized states.
One can see from these definitions it would be sufficient to show the optimal solution for
$H^{\ve}_{\min}(YX|PE)_{V\rho V^{\dagger}}$ is a feasible solution for  $H^{\ve}_{\min}(X|PE)_{\rho}$ to prove <Ref>. Suppose the optimal solution of $ H^{\ve}_{\min}(YX|PE)_{V\rho V^{\dagger}}$ is taken at  $(\overline{\lambda}, \overline{M}_{PE}, \overline{\rho}_{YXPE})$ where $\overline{\rho}_{YXPE}$ is chosen as a CCCQ state by <cit.>. This gives

\begin{align}
\mathbb{1}_{Y} \otimes \mathbb{1}_{X} \otimes 2^{- \overline{\lambda}}  \overline{M}_{PE} \geq  \overline{\rho}_{YXPE}:= \sum_{(y,x,p)}
\dyad{y} \otimes \dyad{x} \otimes \dyad{p} \otimes \overline{\rho}^{(y,x,p)}_{E} \ .
\end{align}

Applying the pinching map $\Delta_P(\cdot):= \sum_p \ket{p}\bra{p} \cdot \ket{p}\bra{p}$ on both sides, we get

\begin{align}
\sum_{(y,x,p)}  \dyad{y} \otimes \dyad{x} \otimes  \dyad{p} \ox 2^{- \overline{\lambda}} \overline{M}_{E}^{(p)} \geq  \sum_{(y,x,p)}
\dyad{y} \otimes \dyad{x} \otimes \dyad{p} \otimes \overline{\rho}^{(y,x,p)}_{E},
\end{align}

with $\overline{M}_{E}^{(p)}:= \<p|\overline{M}_{PE}|p\>$. We can further `un-compute' $Y$ by applying $V^\dagger \cdot V$ on both sides,

\begin{align}
\sum_{(x,p)} \dyad{x} \otimes  \dyad{p} \ox 2^{- \overline{\lambda}} \overline{M}_{E}^{(p)} \geq  \sum_{(x,p)} \dyad{x} \otimes \dyad{p} \otimes \overline{\rho}^{(f(x,p),x,p)}_{E},
\end{align}

which is equivalent to

\begin{align}
\mathbb{1}_{X} \ox 2^{- \overline{\lambda}} \sum_p \dyad{p} \ox  \overline{M}_{E}^{(p)} \geq  V^\dagger \overline{\rho}_{YXPE} V \ .
\end{align}

Since $V^\dagger \cdot V$ is a CPTNI map, we know that the purified distance cannot increase under this map. Therefore,

\begin{align}
P(V^\dagger \overline{\rho}_{YXPE} V, \rho_{XPE}) \leq P(\overline{\rho}_{YXPE}, V\rho_{XPE}V^\dagger) \leq \ve,
\end{align}
where the second inequality follows by the assumption of $\overline{\rho}_{YXPE}$. Thus, it is the case that $(\overline{\lambda},\sum_p \dyad{p} \ox  \overline{M}_{E}^{(p)}, V^\dagger \overline{\rho}_{YXPE} V)$ is a feasible solution for $H^{\ve}_{\min}(X|PE)_{\rho}$, which implies <Ref>.

§.§ Entropy Accumulation subprotocol with smoothing

Here we present the equivalent of <Ref>. The proof is the same as in the main text except that we need to use the smooth min-entropy EAT (<Ref>).

Consider the entropy accumulation protocol defined in <Ref> where the announcements $\widetilde{A}_i$'s and $\widetilde{B}_i$'s satisfy <Ref>. 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(\q) \geq h$ for all $\q \in \mathcal{Q}$ where $f$ is the min-tradeoff function generated by <Ref> or <Ref>. Then for any $\alpha \in (1,2)$, $\vEA,\vBar \in (0,1)$, either the protocol aborts with probability greater than $1-\vEA$, or

\begin{align}\label{eq:entropyRate_with_smoothing}
H^{\vBar}_{\min}(\overline{A}^{n}_{1} \overline{B}^{n}_{1}| \widetilde{A}^{n}_{1} \widetilde{B}^{n}_{1} T^{n}_{1} E)_{\rho_{|\Omega}} > n h -n \frac{(\alpha-1)\ln 2}{2}V^{2} - \frac{1}{\alpha-1} \log \frac{2}{\vBar^{2} \vEA^{2}} - n(\alpha-1)^{2} K_{\alpha}
\end{align}

where $V$ and $K_{\alpha}$ are given by <Ref>  and we replace $\rho[\Omega]$ by $\vEA$.

Moreover, the bound can be further optimized by using <Ref> and optimizing over $\alpha$.

§.§ QKD security proof with smooth entropies

Here we present the equivalent of <Ref>. The proof is similar, but we include it for completeness.

Consider any QKD protocol which follows <Ref> and satisfies <Ref>. Let $\vBar,\vPA,\vEC,\vAcc \in (0,1)$ such that $\vAcc \geq \vBar + \vPA + \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>. For $\alpha \in (1,2)$, the QKD protocol is $\vAcc$-secure for key length

\begin{align}
\label{eq:KeyLength_with_smoothing}
\ell &\leq nh - {\leak}_{\vEC} - n\frac{(\alpha-1)\ln 2}{2}V^{2} - n(\alpha-1)^{2}K_{\alpha} - n\gamma \log(|\cA||\cB|) \notag \\
& \hspace{.25cm} - 2\sqrt{n}\log(1+2d_{S})\sqrt{1-2\log(\vBar/4 \cdot \vAcc)} - \frac{1}{\alpha-1}\log \frac{32}{(\vBar \cdot \vAcc)^{2}}  \\
& \hspace{.5cm} -2\log(1-\sqrt{1-(\vBar/4)^{2}}) - 2\log(2/\vPA)  \notag
\end{align}

where $V$ and $K_{\alpha}$ are given by <Ref>,
$\mathcal{A}$ and $\mathcal{B}$ are the alphabets of private outcomes Alice and Bob will announce excluding the symbol $\perp$, $d_{S} = (|\cA|+1)(|\cB|+1)$, $\leak_{\vEC}$ is the amount of information leaked during error correction.

By the equivalence of <Ref> and <Ref>, which is by construction, proving the security of <Ref> is equivalent to proving the security of <Ref>. We refer to <Ref> in the proof, but this is just for the ease of the reader to link to the main text and <Ref>'s sequential presentation. Let $\Omega'$ be the event that <Ref> does not abort (i.e. $\Omega$ is satisfied) and error correction succeeds (i.e. $\hash(\mathbf{Z}) = \hash(\mathbf{\widehat{Z}})$). Let $\Omega''$ be the event that <Ref> does not abort and error correction verification succeeds. Let $\tilde{\rho}_{|\Omega''}$ be the output of the <Ref> conditioned on not aborting and error correction succeeding and $\rho_{|\Omega'}$ be the output of <Ref> conditioned on not aborting and error correction being applied and succeeding.

Fundamentally, we are interested in the entropy of the raw key which excludes the sifted registers or the registers used for parameter estimation. As defined in <Ref>, $\mathbf{Z} \equiv \ol{A}^{n}_{1} \setminus (\ol{A}_{\mathcal{S}} \cup \ol{A}_{\mathcal{T}})$. However, we note that Alice announces $\ol{A}_{\mathcal{T}}$, making it part of what is conditioned on, and $\ol{A}_{\mathcal{S}}$ is determined entirely by the registers $\wt{A}^{n}_{1}$, $\wt{B}^{n}_{1}$, and $T^{n}_{1}$. Therefore, by <Ref>, we can conclude:

$$ H_{\min}^{\vBar}(\mathbf{Z}|\wt{A}^{n}_{1}\wt{B}^{n}_{1} T^{n}_{1} \ol{A}_{\mathcal{T}} C E)_{\tilde{\rho}_{|\Omega''}} = H_{\min}^{\vBar}(\ol{A}^{n}_{1}|\wt{A}^{n}_{1}\wt{B}^{n}_{1} T^{n}_{1} \ol{A}_{\mathcal{T}} C E)_{\tilde{\rho}_{|\Omega''}} \ . $$

We can handle the classical communication cost of error correction by <cit.>:

\begin{align}
H^{\vBar}_{\min}(\ol{A}^{n}_{1}|\wt{A}^{n}_{1}\wt{B}^{n}_{1} T^{n}_{1} \ol{A}_{\mathcal{T}} C E)_{\tilde{\rho}_{|\Omega''}} &\geq H^{\vBar}_{\min}(\ol{A}^{n}_{1}|\wt{A}^{n}_{1}\wt{B}^{n}_{1} T^{n}_{1} \ol{A}_{\mathcal{T}} E)_{\tilde{\rho}_{|\Omega''}} - {\leak}_{\vEC} \\
& = H^{\vBar}_{\min}(\ol{A}^{n}_{1}|\wt{A}^{n}\wt{B}^{n} T^{n}_{1} \ol{A}_{\mathcal{T}} E)_{\rho_{|\Omega'}} - {\leak}_{\vEC}
\end{align}

where $C$ is the register storing the classical communication due to error correction, and the equality comes from noting that $\rho_{\ol{A}^{n}_{1}\wt{A}^{n}_{1}\wt{B}^{n}_{1}T^{n}_{1}X^{n}_{1}E_{|\Omega'}} = \tilde{\rho}_{\ol{A}^{n}_{1}\wt{A}^{n}_{1}\wt{B}^{n}_{1}T^{n}_{1}X^{n}_{1}E_{|\Omega''}}$. We stress that Bob's private register, $\ol{B}^{n}_{i}$, for both the EAT and the QKD protocol, is excluded in the equality as they differ. We note that $\ol{A}_{\mathcal{T}}$ is conditioned upon as Alice publicly announced it, but $X^{n}_{1}$ is not conditioned upon as Bob computes it locally and does not need to announce it unless aborting.

With all of this addressed, we can conclude that we would like to do privacy amplification using the smooth min-entropy term:

\begin{align}
\label{eq:goal}
H^{\vBar}_{\min}(\ol{A}^{n}_{1}|\wt{A}^{n}_{1}\wt{B}^{n}_{1} T^{n}_{1} \ol{A}_{\mathcal{T}} E)_{\rho_{|\Omega'}} \ .
\end{align}

This imposes one major difficulty: we need to find a way to relate this to the term $H^{\vBar}_{\min}(\ol{A}^{n}_{1} \ol{B}^{n}_{1}|\wt{A}^{n}\wt{B}^{n} T^{n}_{1} E)_{\rho_{|\Omega'}}$ on the left-hand side of <Ref>.

Following derivations in the DI-QKD setting [Arnon-Friedman et al., 2018], but also handling the $\ol{A}_{\mathcal{T}}$ register, we use the following series of claims:

\begin{align}
& H^{\vBar}_{\min}(\ol{A}^{n}_{1}|\wt{A}^{n}_{1} \wt{B}^{n}_{1} T^{n}_{1} \ol{A}_{\mathcal{T}} E)_{\rho_{|\Omega'}} \notag \\
\geq & H^{\vBar}_{\min}(\ol{A}^{n}_{1}|\wt{A}^{n}_{1} \wt{B}^{n}_{1} \ol{A}_{\cT} \ol{B}^{n}_{1} T^{n}_{1} \ol{A}_{\mathcal{T}} E)_{\rho_{|\Omega'}} \notag \\
\geq & H^{\vBar/4}_{\min}(\ol{A}^{n}_{1} \ol{B}^{n}_{1} \ol{A}_\cT |\wt{A}^{n}_{1}\wt{B}^{n}_{1} T^{n}_{1} E)_{\rho_{|\Omega'}} - H^{\vBar/4}_{\max}(\ol{B}^{n}_{1}\ol{A}_{\cT}|\wt{A}^{n}_{1}\wt{B}^{n}_{1} T^{n}_{1} E)_{\rho_{|\Omega'}}  - 2 \log \left( 1 - \sqrt{1-(\vBar/4)^2} \right) \notag \\
\geq & H^{\vBar/4}_{\min}(\ol{A}^{n}_{1} \ol{B}^{n}_{1} |\wt{A}^{n}_{1}\wt{B}^{n}_{1} T^{n}_{1} E)_{\rho_{|\Omega'}} - H^{\vBar/4}_{\max}(\ol{B}^{n}_{1}\ol{A}_{\cT}|T^{n}_{1} E)_{\rho_{|\Omega'}} - 2 \log \left( 1 - \sqrt{1-(\vBar/4)^2} \right) \ .
\end{align}

The first inequality holds by data-processing. The second inequality follows from <cit.>. The third inequality comes from data-processing for the smooth max-entropy term and applying <Ref> to remove $\ol{A}_{\cT}$ in the smooth min-entropy term. More specifically, the strong subadditivity follows from the data-processing inequality of smooth max-entropy of <cit.> where we have applied the partial trace map on the side information.

Now all that is left is to bound the max-entropy term using the original version of EAT (<Ref>) [Dupuis et al., 2020]. To do this we use the EAT in the form of <Ref> with the replacements $S_{i} \to \ol{A}_{\cT_{i}}\ol{B}_{i}$, $P_{i} \to T_{i}$, and $E \to E$. We note it is okay to use $\ol{A}_{\mathcal{T}}$ as we may treat it as if it were actually $n$ registers where it is $\perp$ whenever $T_{i} \neq 0$. The Markov conditions trivially hold since $T_{i}$ uses seeded randomness. Then using the fact that $\ol{A}_{\cT_{i}}\ol{B}_{i} = \perp \times \perp$ except when $T_{i}=1$ which happens with probability $\gamma$, we construct the max-tradeoff function analytically by the following observation:

\begin{align}\label{eq:maxtradeoffconstruction_with_smoothing}
H(\ol{A}_{\cT_{i}} \ol{B}_{i}|T_{i}R')_{\cM_{i}(\omega)} & \leq H(\ol{A}_{\cT_{i}}\ol{B}_{i}|T_{i})_{\cM_{i}(\omega)}\notag\\
& = (1-\gamma)H(\ol{A}_{\cT_{i}}\ol{B}_{i}|T_{i}=0)_{\cM_{i}(\omega)} + \gamma H(\ol{A}_{\cT_{i}}\ol{B}_{i}|T_{i}=1)_{\cM_{i}(\omega)} \notag \\
& \leq \gamma \log|\mathcal{A} \times \mathcal{B}|
\end{align}

where $\mathcal{A}$ and $\mathcal{B}$ are the alphabets of private outcomes Bob utilizes during parameter estimation. This tells us we can let the max-tradeoff function $f_{\max}(\vect{q}) = \gamma \log |\mathcal{A} \times \mathcal{B}|$ for all $\vect{q} \in \mathbb{P}(\cX)$. This also implies $\|\nabla f_{\max}\|_{\infty} = 0$. Therefore, using this with <Ref>
we get

\begin{align}
& H^{\vBar/4}_{\max}(\ol{B}^{n}_{1}\ol{A}_{\cT}|T^{n}_{1} E)_{\rho_{|\Omega'}} \leq n\gamma\log|\mathcal{A} \times \mathcal{B}| + \sqrt{n} 2\log(1+2 d_{S})\sqrt{1-2\log(\vBar/4 \cdot \vAcc)}
\end{align}

where we have assumed $\rho[\Omega'] \geq \vAcc$, and $d_{S} := (|\cA|+1)(|\cB|+1)$ using that $|\ol{B}_{i}|=|\cB|+1, |\ol{A}_{\cT,i}|=|\cA|+1$.

We now put all of these together to get the following:

\begin{align}
H^{\vBar}_{\min}(\ol{A}^{n}_{1}| \wt{A}^{n}_{1} \wt{B}^{n}_{1} T^{n}_{1} \ol{A}_{\mathcal{T}} E)_{\rho_{|\Omega'}}
&\geq H^{\vBar/4}_{\min}(\ol{A}^{n}_{1} \ol{B}^{n}_{1}|\wt{A}^{n}_{1} \wt{B}^{n}_{1} T^{n}_{1} E)_{\rho_{|\Omega'}} -\leak_{\vEC}  -n\gamma\log(|\mathcal{A} \times \mathcal{B}|) \notag\\ & \hspace{0.75cm}
- 2\sqrt{n}\log(1+2d_{S})\sqrt{1-2\log(\vBar/4 \cdot \vAcc)} \notag\\  &\hspace{1cm}  - 2 \log \left( 1 - \sqrt{1-(\vBar/4)^2} \right) \ .
\end{align}

We now apply <Ref> to the right-hand-side min-entropy term (with appropriate choice of $\vBar/4$ and $\vEA \to \vAcc$) so that we have that either the input state aborts with probability greater than $1-\vAcc$ or

\begin{equation}
\begin{aligned}
& H^{\vBar}_{\min}(\ol{A}^{n}_{1}| \wt{A}^{n}_{1} \wt{B}^{n}_{1} T^{n}_{1} \ol{A}_{\mathcal{T}} E)_{\rho_{|\Omega'}} \\
& \geq  nh - \leak_{\vEC} -n \frac{(\alpha-1)\ln 2}{2}V^{2} - n(\alpha-1)^{2} K_{\alpha} -n\gamma\log(|\mathcal{A} \times \mathcal{B}|) \\
& \hspace{0.5cm} -2\sqrt{n}\log(1+2 d_{S})\sqrt{1-2\log(\vBar/4 \cdot \vAcc)} - 2 \log \left( 1 - \sqrt{1-(\vBar/4)^2} \right) \\
& \hspace{1cm}  - \frac{1}{\alpha-1} \log \frac{32}{(\vBar \cdot \vAcc)^{2}} \ .
\end{aligned}
\end{equation}

Applying the leftover hash lemma [Renner, 2005] (<Ref>) completes the proof.

The proof of the security claim is nearly identical to the non-smooth case. We consider two mutually exclusive and exhaustive cases. When $\rho[\Omega] < \vAcc$, then the output is trivially $\vAcc$-secure. Now consider $\rho[\Omega]$. Starting from the subnormalized state[Subnormalization is due to aborting the protocol on the input] $\rho_{S_{A}EF}$ where $S_{A}:= h(\mathbf{Z})$ is the hashed key, $h$ is the hash function, and $F$ is the announcement of the hash function,

\begin{align*}
\frac{1}{2} \| \rho_{S_{A}EF} - |S_{A}|^{-1}\idm_{S_{A}} \otimes \rho_{EF} \|_{1}
=& \frac{1}{2} \rho[\Omega'] \| \rho_{S_{A}F_{|\Omega'}} - |S_{A}|^{-1}\idm_{S_{A}} \otimes \rho_{EF_{|\Omega'}} \|_{1} \\
\leq& \frac{1}{2}\| \rho_{S_{A}F_{|\Omega'}} - |S_{A}|^{-1}\idm_{S_{A}} \otimes \rho_{EF_{|\Omega'}} \|_{1} \ , \\
\leq& \vSec = \vBar + \vPA
\end{align*}

where the second inequality is by <ref> along with the definition of $\vSec$ in <Ref> by choosing $\ve' \to \vBar$. The final inequality is by the definition $\vPA := \vSec - \ve'$ in <Ref>. The correctness argument is the same as in the unsmoothed proof. Therefore we the key is $\max\{\vAcc,\vBar+\vPA+\vEC\}$-secure. As in the previous proofs, note that if $\vAcc < \vBar+\vPA+\vEC$, you could improve the key rate without changing the security claim by setting $\vAcc = \vBar + \vPA + \vEC$. This completes the proof.

§ KEY RATE OPTIMIZATION BASED ON QUANTUM CONDITIONAL ENTROPY

We find a way to represent Eve's conditional states in terms of Alice's and Bob's joint state and express the quantum conditional entropy $H(S_i|P_iR)$ with those conditional states. (We use register $R$ to refer to Eve's register in a single round as depicted in <Ref>.) We then show this function is convex. We write the objective function based on the quantum conditional entropy as

W(ρ)   := H(S_i|P_iR)_ρ,
for $\rho \in \DM(Q_i)$. <Ref> gives us a more explicit expression of $W(\rho)$ in terms of $\rho \in \DM(Q_i)$ and Alice's and Bob's joint POVM. The convexity of $W(\rho)$ is given in <Ref>.
We now prove <Ref>.

Recall from the definition of conditional entropy that for a classical-quantum state $\rho_{S_iP_iR} = \sum_{s,p} \dyad{s}{s}_{S_i} \otimes \dyad{p}{p}_{P_i} \otimes \rho_R^{(s,p)}$, we have $H(S_i|P_iR) = \sum_{s,p} H(\rho_R^{(s,p)}) - \sum_p H(\rho_R^{(p)})$, where $\rho_R^{(p)} = \sum_{s} \rho_R^{(s,p)}$. We need to find the marginal states $\rho_R^{(s,p)} = \Tr_{AB}[ (M_{sp} \otimes \idm_R) \rho_{Q_iR}]$. Without loss of generality, we can write the purifying state as $\rho_{Q_iR} = \dyad{\psi}{\psi}$, where $\ket{\psi} = \sqrt{\rho}\otimes \idm_R \ket{\Phi^+}$ and $\ket{\Phi^+} = \sum_j \ket{j}_{Q_i}\ket{j}_R$, from which we find

ρ_R^(s,p)    = _Q_i[ (M_sp ⊗_R) ρ_Q_iR]

= _Q_i[(√(ρ)M_sp√(ρ) ⊗_R) Φ^+Φ^+]

= ∑_s,p (√(ρ)M_sp√(ρ))^T  .
By the fact that for any operator $A$, $(A^\dagger A)$ and $(A^\dagger A)^T$ have the same spectrum, it is the case that $H(\rho_R^{(s,p)}) = H\Big([(\sqrt{\rho}K_{sp}) (K_{sp}\sqrt{\rho})]^T\Big) = H(K_{sp} \rho K_{sp})= H(K_{sp} \rho K_{sp}^{\dagger})$ and a similar expression holds for $H(\rho_R^{(p)})$.

The function $W(\rho)$ is convex.

Let $\bar \rho_Q = \sum_\lambda p_\lambda \rho^\lambda_Q$ be a convex decomposition of $\bar \rho_Q$. We want to show that
∑_λp_λ W(ρ_Q^λ) ≥W(ρ̅_Q) .

Let $\rho_{QR}^\lambda$ be the purification of $\rho^\lambda_Q$. From these, we define the state $\rho_{QR\Lambda} = \sum_\lambda p_{\lambda} \rho^\lambda_{QR} \otimes \ketbra \lambda_\Lambda$, which satisfies $\Tr_{R\Lambda}[\rho_{QR\Lambda}] = \bar \rho_Q$. Then
∑_λp_λ W(ρ_Q^λ)    := ∑_λp(λ) H(S|PR)_⊗𝕀_R(ρ^λ_QR)

= H(S|PRΛ)_⊗𝕀_RΛ(ρ_QRΛ)

:= W(ρ̅_Q)

where $\bar \rho_{QR}$ is the purification of $\bar \rho_Q$ and where the inequality comes from subadditivity because the entropy will be minimized when Eve holds a purification of $\bar\rho_Q$.

The physical intuition of the proof is the fact that if Eve has a family of states $\rho_{Q}^\lambda$ that she sends out with probability $p(\lambda)$, while keeping their purification, then that attack will be suboptimal. This is because it is better to send out the average state $\bar \rho_Q = \sum_\lambda p(\lambda)\rho_Q^\lambda$ and keep the corresponding purification, as this produces the same measurement statistics and Eve holds more information about the state.

As mentioned in the main text, we need to introduce a small perturbation to guarantee that the gradient $\nabla W(\rho)$ is well-defined for any $\rho \geq 0$. To do so, we introduced the perturbed objective function $W_\epsilon(\rho)$, which is

\begin{align}
W_\epsilon(\rho)= \sum_{s,p} H\left(\cK^\epsilon_{sp}(\rho)\right) - \sum_p H\left( \cK^\epsilon_p(\rho)\right).
\end{align}
Then the gradient $\nabla W_\epsilon(\rho)$ always exists for all $\rho \geq  0$:

\begin{align}
\nabla W_\epsilon(\rho) = - \sum_{s,p} (\cK^\epsilon_{sp})^\dagger \left[\log \cK^\epsilon_{sp}(\rho) \right] + \sum_p (\cK_{p}^\epsilon)^\dagger \left[\log \cK^\epsilon_p(\rho)\right].
\end{align}

By <cit.>, we know that

\begin{align}
\norm{\cK_{sp}(\rho) - \cK_{sp}^\epsilon(\rho)}_1  \leq \epsilon(d-1) \quad \text{and} \quad \norm{\cK_{p}(\rho) - \cK_{p}^\epsilon(\rho)}_1 \leq \epsilon(d-1).
\end{align}

By the continuity of von Neumann entropy (known as Fannes' inequality), it holds for any $\epsilon \in (0,1/(e(d-1))]$ [Here $e$ is the base of the natural logarithm.] and any density operator $\rho$,

\begin{align}
\left|H\left(\cK_{sp}(\rho)\right) - H\left(\cK_{sp}^\epsilon(\rho)\right)\right| \leq \zeta_\epsilon \quad \text{and}\quad
\left|H\left(\cK_p(\rho)\right) - H\left(\cK_p^\epsilon(\rho)\right)\right| \leq \zeta_\epsilon.
\end{align}

with $\zeta_\epsilon = \epsilon(d-1)\log \frac{d}{\epsilon(d-1)}$. Thus we have <Ref> after taking the worst-case scenario among all contributing terms.

§ PROOF FOR THE SECOND ALGORITHM CONSTRUCTION

§.§ Basic definitions

For completeness, we review some basic definitions. In this appendix, $f, g, h$ denote some general functions. Readers are cautioned not to confuse them with min-tradeoff functions used in the main text.

For a set $C \subseteq \mbR^n$, the affine hull of $C$, denoted by $\aff(C)$, is defined as

(C) = {∑_i=1^k θ_i x_i:  x_1, …, x_k ∈C, ∑_i=1^k θ_i = 1  for some k ∈}.

We note that the affine hull is the smallest affine set that contains $C$.

The relative interior of a set $C \subseteq \mbR^n$, denoted by $\relint(C)$ is defined as

(C) ={x ∈C: B_r(x) ∩(C) ⊆C  for some  r > 0 },
where $B_r(x)$ is a ball centered at $x$ with a radius $r$.

It is often convenient to let a function $f$ be defined over the entire $\mbR^n$ and let it take the value $+\infty$ outside its domain which is denoted by $\dom(f)$. It is thus interesting to talk about the extended-value extension.

extended-value extension
If $f:\dom(f)\subseteq\mbR^n \rightarrow \mbR$ is convex, we define its extended-value extension $\tilde{f}: \mbR^n \rightarrow \mbR \cup \{+\infty\}$ by

f̃(x)  =
f(x)     x∈(f)

+ ∞    x∉(f).

It is sometimes useful to define the domain of an extension as

(f̃)={x ∈^n: f̃(x) < ∞}.

§.§ Fenchel duality

We review one form of duality called Fenchel duality that is relevant for our algorithm. See [Borwein and Lewis, 2006] for details about Fenchel duality.

Fenchel conjugate
The Fenchel conjugate of a function $h: \mbR^n \rightarrow [-\infty, +\infty]$ is the function $h^*: \mbR^n  \rightarrow [-\infty, +\infty]$ defined by

h^*(v) = sup_x ∈^n {⟨v, x ⟩- h(x)}.

We now state Fenchel's duality theorem <cit.> with the condition for strong duality replaced by <Ref> according to <cit.>.

Fenchel duality
For given functions $f: \mbR^n \rightarrow (-\infty, +\infty]$ and $g: \mbR^m \rightarrow (-\infty, +\infty]$ and a (bounded) linear map $A: \mbR^n \rightarrow \mbR^m$, let $p, d \in [-\infty, +\infty]$ be primal and dual values in the following Fenchel problems:

\begin{align}
p &= \inf_{x \in \mbR^n} \{f(x)+g(Ax)\} \label{eq:fenchel_primal}, \\
d  &= \sup_{v \in \mbR^m} \{-f^*(A^{\dagger}v) - g^*(-v)\} \label{eq:fenchel_dual}.
\end{align}
These values satisfy the weak duality $p \geq d$.

If $f$ and $g$ are convex and satisfy the condition

((g)) ∩A ((f)) ≠∅,
where $A \relint(\dom(f))  = \{Ax: x \in \relint(\dom(f)) \}$, then the strong duality holds; i.e., $p=d$, and the supremum in the dual problem [<Ref>] is attained if $d < + \infty$. $\relint$: relative interior

We note that although the formulation of this theorem is for unconstrained optimization, one can easily handle constrained optimization by the extended-value extension. Similarly, one can define an indicator function for a set $C$ by

δ_C(x) =
0      if   x ∈C

∞     if   x ∉C,

and use this indicator function to convert a constraint set $C$ into a part of the objective function.

§.§ Deriving dual problem of  <Ref>

In this section, let $\cH$ be a Hilbert space and define a map that stores the measurement outcomes of the POVM $\{M_{\lambda}\}$ with associated alphabet $\cX$ for outcomes as

Φ_(σ) = ∑_λ∈ ( σM_λ) |λ⟩.
Let $W$ be the quantum conditional entropy function in <Ref>. Let $m= \abs{\cX}$ be the number of outcomes. We define the set

_:={f ∈^m: f ·Φ_(ρ) ≤W(ρ)  ∀ρ∈()}.
It is also easy to see that $\cF_\dual$ is a convex set. Moreover, we can write the indicator function [see <Ref>] for the set $\cF_\dual$ in a useful way by the following lemma.

Let $\delta_{\cF_\dual}$ be the indicator function for the set $\cF_\dual$. Then,

sup_ρ{⟨f,Φ_(ρ) ⟩- W(ρ): ρ∈()}=δ__(f)    ∀f ∈^m.

Let $\alpha(\vect{f}) :=	\sup_{\rho}\{\langle \vect{f},\Phi_{\vect{\cM}}(\rho) \rangle - W(\rho): \rho \in \pos(\cH)\}$.

If $\vect{f} \in \cF_\dual$, then $\langle \vect{f},\Phi_{\vect{\cM}}(\rho) \rangle - W(\rho) \leq 0$ for any $\rho \in \DM(\cH)$. As any positive operator can be scaled from $\rho \in \DM(\cH)$ by a non-negative coefficient, it is the case that $\alpha \leq 0$. Thus, $\alpha(\vect{f}) = 0$ with $\rho = 0$.

If  $\vect{f} \not\in \cF_\dual$, then there exists $\rho_0 \in \DM(\cH)$ such that $\langle \vect{f},\Phi_{\vect{\cM}}(\rho_0) \rangle - W(\rho_0) > 0$. Let $\gamma = \langle \vect{f},\Phi_{\vect{\cM}}(\rho_0) \rangle - W(\rho_0)$ and $\rho_{\beta} = \beta \rho_0$ with $\beta \geq 0$. We notice that $W(\beta \rho) = \beta W(\rho)$ for any $\beta \geq 0$. Because $\Phi_{\vect{\cM}}$ is linear, with $\rho_\beta$, it is the case that $\alpha(\vect{f}) > \beta \gamma$. With $\beta \rightarrow \infty$, $\alpha(\vect{f}) \rightarrow \infty$. Thus, <Ref> holds.

To derive the dual problem of <Ref>, we first compute the Fenchel conjugate of two functions that will become useful.

For $c_0\geq 0$ and $c_1 >0$, let $s: \mbR \rightarrow \mbR\  \cup \{+\infty\}$ be defined as

s(x) =
-√(c_0^2 - x^2/c_1^2)       if  x ≤c_0 c_1,

∞     otherwise.

The Fenchel conjugate function of $s$ is

s^*(y) = c_0 √(1+c_1^2y^2).

By <Ref>, the conjugate function of $s$ is

s^*(y)    = sup_x ∈ {xy - s(x)}

=sup_x ∈ {xy + √(c_0^2 - x^2/c_1^2): x ≤c_0c_1}
By a simple calculation to optimize over $x$, it is easy to verify that <Ref> is indeed the conjugate function of $s$.[To find the supremum, one can solve case by case for two cases: $x\geq 0$ and $x < 0$. For each case, one looks for a solution of $x$ where the derivative is zero by simple computation. Then, one verifies that both solutions in these two cases lead to the same optimal value which is indeed the supremum.]

For $c_0\geq 0$ and $c_1 >0$, let $\cE(\vect{\lambda}): \mbR^m \rightarrow \mbR  \ \cup \{+\infty\}$ be defined as

(λ) =

s(λ_1/2)      if  ∑_x λ(x)=0

∞     otherwise,

where $s$ is defined in <Ref>. Then $\cE$ is a convex function and its conjugate function $\cE^*(\vect{f})$ is $\cE^*(\vect{f}) = s^*(\max(\vect{f})-\min(\vect{f}))$, that is,

^*(f) =  c_0 √(1+c_1^2[max(f)-min(f)]^2) .

The convexity of $\cE$ follows from the convexity of $s$ and the convexity of the set $\{\vect{\lambda} \in \mbR^m: \sum_{x} \vect{\lambda}(x) = 0\}$. From <Ref>,

^*(f)    = sup_λ∈^m {⟨λ, f⟩- (λ)}

= sup_λ∈^m {⟨λ, f⟩- s(λ_1/2):  ∑_x λ(x)=0 }

= sup_λ∈^m {⟨λ, f⟩+ √(c_0^2 - λ_1^2/(4c_1^2)): λ_1 ≤2c_0c_1,    ∑_x λ(x)=0 }
Let $\vect{\lambda_+}$ be defined as $\vect{\lambda_+}(x) = \max(\vect{\lambda}(x),0)$ and  $\vect{\lambda_-}$ be defined as $\vect{\lambda_-}(x) = \max(-\vect{\lambda}(x),0)$. Then, it is clear that $\vect{\lambda} = \vect{\lambda_+} - \vect{\lambda_1}$ and $\norm{\vect{\lambda}}_1 =\norm{\vect{\lambda_+}}_1  +\norm{\vect{\lambda_-}}_1$. The condition $\sum_{x}\vect{\lambda}(x)=0$ implies $\norm{\vect{\lambda_+}}_1  = \norm{\vect{\lambda_-}}_1  = \frac{1}{2}\norm{\vect{\lambda}}_1.$ Thus,

^*(f)    = sup_λ_+∈^m
λ_- ∈^m {⟨f, λ_+⟩- ⟨f, λ_-⟩+ √(c_0^2 - λ_+_1^2/c_1^2): λ_+_1 = λ_-_1 ≤c_0c_1, λ_+ ≥0, λ_- ≥0 }

=sup_λ_+∈^m, v ∈ {  ⟨f, λ_+⟩- v min(f)	+ √(c_0^2 - v^2/c_1^2):
0 ≤v = λ_+_1 ≤c_0c_1, λ_+ ≥0 }

= sup_v ∈  {  v[max(f) - min(f)]	+ √(c_0^2 - v^2/c_1^2):
0 ≤v ≤c_0c_1 }

= sup_v ∈  {  v[max(f) - min(f)]	+ √(c_0^2 - v^2/c_1^2):
v ≤c_0c_1 }

= sup_v ∈  {  v[max(f) - min(f)] - s(v)}

= s^*(max(f) - min(f)).
In the second line above, we optimize $\vect{\lambda_-}$ and the optimal value is achieved when $\vect{\lambda_-}$ contains a single nonzero entry in the position corresponding to $\min(\vect{f})$. In the third line, we optimize $\vect{\lambda_+}$ and the optimal value is achieved when $\vect{\lambda_+}$ contains a single nonzero entry in the position corresponding to $\max(\vect{f})$. In the fourth line, we drop the constraint $v \geq 0$ since the optimal value is always achieved when $v \geq 0$ due to the fact $\max(\vect{f}) - \min(\vect{f}) \geq 0$. In the fifth line, we use the definition of $s$. The last line follows from the definition of $s^*$.

Let $c_0\geq 0$ and $c_1 >0$ be constants. For the problem

h_(q_0):=	   _ρ         W(ρ) + √(c_0^2 - q_0- Φ_(ρ)_1^2/(4c_1^2))

(ρ) = 1

q_0- Φ_(ρ)_1 ≤2c_0c_1

its Fenchel dual problem is

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

f ·Φ_(ρ) ≤W(ρ)   ∀ρ∈().
Moreover, if there exists $\sigma \in \DM(\cH)$ such that $\Phi_{\vect{\cM}}(\sigma) = \vect{q}_0$, then $h_{\primal}(\vect{q}_0)= 	h_{\dual}(\vect{q}_0)$.

We introduce the indicator function $\delta_{\pos(\cH)}$ for the set $\pos(\cH)$ (see <Ref>). We identify any $\rho \in \pos(\cH)$ as an element in $\mbR^n$ for $n=4\dim(\cH)^2$ by representing $\rho$ with its real and imaginary parts, and then applying an appropriate vectorization of $\rho$. Similarly, we abuse the notation $\Phi_{\vect{\cM}}$ and let it denote the corresponding linear map from $\mbR^n$ to $\mbR^m$ where $m$ is the number of POVM elements for this measurement map. To apply <Ref>, we define $f(\rho)= W(\rho) + \delta_{\pos(\cH)}(\rho)$, $g(\vect{\lambda}) = \cE(\vect{\lambda}-\vect{q}_0)$ and let $\Phi_{\vect{\cM}}$ play the role of $A$ in the theorem. We first calculate $f^*$ and $g^*$:

\begin{align}
f^*(Z) &= \sup_{\rho} \{\langle Z, \rho \rangle - f(\rho)\} \notag \\
&= \sup_{\rho} \{\langle Z, \rho \rangle - W(\rho): \rho \in \pos(\cH)\} \\
g^*(\vect{f}) &=  \sup_{\vect{\lambda}} \{\langle \vect{f}, \vect{\lambda} \rangle -\cE(\vect{\lambda}-\vect{q_0})\}\notag \\
&=  \sup_{\vect{\lambda'}} \{\langle \vect{f}, \vect{\lambda'}  \rangle + \langle \vect{f}, \vect{q_0} \rangle -\cE(\vect{\lambda'})\}\notag \\
&= \cE^*(\vect{f}) + \langle  \vect{f},\vect{q_0} \rangle.
\end{align}

Because $\sum_x \vect{q_0}(x) = 1$ and $\sum_x \Phi_{\vect{\cM}}(\rho) (x)= 1$ for $\Tr(\rho)=1$, one can use the definition of $f$ and $\cE$ to rewrite the problem in <Ref> as

h_(q_0)   = inf_ρ∈^n { f(ρ) + (Φ_(ρ)-q_0) }

= inf_ρ∈^n{f(ρ)+ g(Φ_(ρ))}.

We then use the indicator function for the set $\cF_\dual$ and the conjugate function $\cE^*$ of $\cE$ to rewrite <Ref> as

h_(q_0)   =sup_f	{- ⟨q_0, -f ⟩- ^*(f) - δ__(f)}

= sup_f	{-g^*(-f) - δ__(f)}.
By <Ref>, $\delta_{\cF_\dual}(\vect{f})= \sup_{\rho}\{ \langle \vect{f},\Phi_{\vect{\cM}}(\rho) \rangle  - W(\rho): \rho \in \pos(\cH)\}.$ Using this substitution, we find

h_(q_0)	   = sup_f ∈^m{-sup_ρ{⟨f,Φ_(ρ) ⟩-W(ρ): ρ∈() }- g^*(-f) }

= sup_f ∈^m{-sup_ρ{⟨Φ_^†(f), ρ⟩-W(ρ): ρ∈() }- g^*(-f) }

= sup_f ∈^m{-f^*(Φ_^†(f))- g^*(-f)}.
Therefore, the optimization problem in <Ref> is the dual problem of the optimization problem in <Ref>.

To show $h_{\primal}(\vect{q}_0)= 	h_{\dual}(\vect{q}_0)$, we just need to verify the condition

((g)) ∩Φ_ ((f)) ≠∅.
From the definition of domain [see <Ref>],
(g)    = {λ ∈^m: ∑_xλ(x)=1, λ-q_0_1 ≤2c_0c_1}

(f)     =  {ρ∈^n: ρ≥0}
It is clear that $ \vect{q}_0 \in \relint(\dom(g))$. Moreover, there exists some $\epsilon >0$ such that $(1-\epsilon)\vect{q}_0 + \epsilon \vect{1}/m \in \relint(\dom(g))$. We now show that $ (1-\epsilon)\vect{q}_0 + \epsilon \vect{1}/m \in \Phi_{\vect{\cM}} \relint(\dom(f))$. By the assumption, there exists $\sigma \in \DM(\cH)$ such that $\Phi_{\vect{\cM}}(\sigma) = \vect{q}_0$.  Then for any $\delta > 0$, it is the case that $\cD_\delta(\sigma) \in \relint(\dom(f))$. In particular, $\cD_\epsilon(\sigma) \in \relint(\dom(f))$. Since $\Phi_{\vect{\cM}}(\cD_\epsilon(\sigma) ) = (1-\epsilon)\vect{q}_0 + \epsilon \vect{1}/m$, it is the case that  $(1-\epsilon)\vect{q}_0 + \epsilon \vect{1}/m \in \Phi_{\vect{\cM}} \relint(\dom(f))$. Therefore, <Ref> holds. We conclude that $h_{\primal}(\vect{q}_0)= h_{\dual}(\vect{q}_0)$.

Since we establish that $h_{\primal}(\vect{q}_0)= 	h_{\dual}(\vect{q}_0)$, we can now solve the primal problem in <Ref>. The difficulty is that the objective function is not differentiable at points where$\Phi_{\vect{\cM}}(\rho) = \vect{q}_0$. Since many standard solvers handle differentiable functions more effectively, we introduce a slack variable and rewrite the problem to an equivalent one according to the following lemma.

The following optimization problem

h̃_(q_0):=   	_ρ, ξ        W(ρ) - √(c_0^2 - (∑_xξ(x))^2/(4c_1^2))

-ξ ≤Φ_(ρ) - q_0 ≤ξ

∑_x ξ(x) ≤2c_0c_1

(ρ) = 1

ρ≥0,  ξ ∈^
has the same optimal value as the problem in <Ref>, that is, $\tilde{h}_\primal(\vect{q}_0)=h_\primal(\vect{q}_0).$

We first notice that the function $- \sqrt{c_0^2 - t^2/(4c_1^2)}$ is a monotonically non-decreasing function of $0 \leq t \leq 2c_0c_1$. For $\vect{\xi} \geq 0, \norm{\vect{\xi}}_1 = \sum_j\vect{\xi}(j).$ The condition  $-\vect{\xi} \leq \Phi_{\vect{\cM}}(\rho) - \vect{q_0} \leq \vect{\xi}$ implies that $\vect{\xi} \geq 0$ and $\norm{\vect{\xi}}_1 \geq \norm{\vect{q}_0- \Phi_{\vect{\cM}}(\rho)}_1$. Thus, it is clear that $\tilde{h}_\primal(\vect{q}_0) \geq h_\primal(\vect{q}_0)$. Let $\rho^\star$ be an optimal solution for $h_\primal(\vect{q}_0)$ and let $\vect{\xi}^\star(j) := \abs{\vect{q}_0(j)- \Phi_{\vect{\cM}}(\rho^\star)(j)}$. Then $\norm{\vect{\xi}^\star}_1 = \norm{\vect{q}_0- \Phi_{\vect{\cM}}(\rho^\star)}_1 \leq 2c_0c_1.$ This implies, $(\rho^\star, \vect{\xi}^\star)$ is a feasible solution for $\tilde{h}_\primal(\vect{q}_0)$ that achieves the same objective function value as $h_\primal(\vect{q}_0)$. Therefore, $\tilde{h}_\primal(\vect{q}_0) \leq h_\primal(\vect{q}_0)$. We conclude that $\tilde{h}_\primal(\vect{q}_0)=h_\primal(\vect{q}_0).$