V}F_{\mathrm{obj}}({\theta_{A}},(r_{Z},r_{X}),\rho_{AB}),$ (106)

because the minimum of an affine function over the convex hull of a set $V$ is
always attained at an extremal point (which will be a point in $V$). To apply
this result, we start with a simple choice of the set $V$ (for instance, in
our code we use $V=\\{(1,0),(1,1),(-1,1),(-1,0)\\}$) and find the point in $V$
that yields the minimum value. We then delete this point and replace it with
two other points such that
$S_{\put(1.5,2.5){\oval(4.0,4.0)[r]}\phantom{\circ}}$ is still contained in
the convex hull, and iterate this process until a sufficiently tight bound is
obtained (for instance, by checking that there is a feasible point of the
optimization that is sufficiently close to the lower bound we have obtained).

###  5.3 Minimization over states

The minimization over states can be tackled by expressing it as a convex
optimization and applying the _Frank-Wolfe algorithm_ [FW56], as was observed
in [WLC18]. For completeness, we now describe the method, with minor
modifications and clarifications for our specific scenario. We emphasize that
while this procedure is numerical, the bounds it returns are _secure_ , in the
sense that it will never over-estimate the true value of the minimization
problem.

We observe that (for fixed measurements, parametrized as described above) the
minimization over states is the minimization of the convex function

$\displaystyle
f_{\mathrm{obj}}(\rho)\coloneqq\left(\sum_{x\in\\{0,1\\}}xD(\mathcal{G}({\rho})\|\mathcal{Z}_{x}(\mathcal{G}({\rho})))\right)-\vec{\lambda}\cdot\operatorname{Tr}\\!\left[\vec{\Gamma}({\theta_{A}},(r_{Z},r_{X}))\rho\right].$
(107)

This function is differentiable for all $\rho$ such that
$\mathcal{G}(\rho)>0$, with [WLC18]191919The notation here follows that used
in [WLC18], in which for a function $f$ defined on matrices parametrized by
their matrix entries
($\rho=\sum_{jk}\rho_{jk}\left|j\right>\\!\left<k\right|$), its derivative is
$\nabla f(\rho)\coloneqq\sum_{jk}(\partial
f/\partial\rho_{jk})\left|j\right>\\!\left<k\right|$. Denoting the tangent to
the graph of $f$ at $\rho$ as $t_{\rho}$, this definition of $\nabla f$
satisfies $t_{\rho}(\rho+\Delta)=f(\rho)+\operatorname{Tr}\\!\left[(\nabla
f(\rho))^{T}\Delta\right]$.

$\displaystyle(\nabla
f_{\mathrm{obj}}(\rho))^{T}=\left(\sum_{x\in\\{0,1\\}}x\mathcal{G}^{\dagger}\\!\left(\log\mathcal{G}(\rho)-\log\mathcal{Z}_{x}(\mathcal{G}(\rho))\right)\right)-\vec{\lambda}\cdot\vec{\Gamma}({\theta_{A}},(r_{Z},r_{X})),$
(108)

where $\mathcal{G}^{\dagger}$ is the adjoint channel of $\mathcal{G}$. In
practice, we will not need to explicitly compute $\mathcal{G}^{\dagger}$,
because all subsequent arguments rely only on “inner products”
$\operatorname{Tr}\\!\left[(\nabla f_{\mathrm{obj}}(\rho))^{T}\sigma\right]$,
which can be rewritten as

$\displaystyle\operatorname{Tr}\\!\left[(\nabla
f_{\mathrm{obj}}(\rho))^{T}\sigma\right]=\operatorname{Tr}\\!\left[\left(\sum_{x\in\\{0,1\\}}x\left(\log\mathcal{G}(\rho)-\log\mathcal{Z}_{x}(\mathcal{G}(\rho))\right)\mathcal{G}(\sigma)\right)-\vec{\lambda}\cdot\vec{\Gamma}({\theta_{A}},(r_{Z},r_{X}))\sigma\right].$
(109)

We also note that the optimization domain is a set defined by PSD constraints
(namely, $\rho$ of the form (95) with $\rho\geq 0$ and
$\operatorname{Tr}\\!\left[\rho\right]=1$), which means that optimizing any
affine function over this set is an SDP, which can be efficiently solved and
bounded [BV04] via its dual value. Together with the explicit expression (108)
for the derivative of the objective function, this makes the optimization
problem here a prime candidate for the Frank-Wolfe algorithm [FW56], which
yields _secure_ lower bounds on the true minimum value of the optimization.

The Frank-Wolfe algorithm is based on a simple geometric insight: for any
point in the domain of a convex function $f_{\mathrm{obj}}$, the tangent
hyperplane (or a supporting hyperplane, if $f_{\mathrm{obj}}$ is not
differentiable at that point) to the graph of $f_{\mathrm{obj}}$ at that point
yields an affine lower bound on $f_{\mathrm{obj}}$. Hence if we can minimize
affine functions over the optimization domain, then any such tangent
hyperplane lets us obtain a lower bound on the minimum of $f_{\mathrm{obj}}$
on the domain. In addition, it intuitively seems that taking the tangent at
points closer to the true optimal solution should yield tighter lower bounds
(though there are some technical caveats). Thus in principle, one could simply
perform some heuristic computations to get an estimate of where the true
minimum lies, then take the tangent at that estimate and obtain the
corresponding lower bound. For this optimization, however, we found that the
results were fairly sensitive to deviations from the true optimum. To get the
bounds to converge, we found it more efficient to use the standard algorithm,
which (under mild assumptions) can be proven to converge in order $O(1/k)$
after $k$ iterations:

Frank-Wolfe algorithm (As presented in [WLC18])

Let the domain of optimization be $\mathcal{D}$ and the acceptable gap between
the feasible values and the lower bounds be $\epsilon_{\mathrm{tol}}>0$.

1.Set $k=0$ and heuristically find
$\rho_{0}\coloneqq\arg\min_{\rho\in\mathcal{D}}f_{\mathrm{obj}}(\rho)$.

2.Solve the SDP  $\displaystyle\min_{\Delta}\operatorname{Tr}\\!\left[(\nabla
f_{\mathrm{obj}}(\rho_{k}))^{T}\Delta\right]\text{ s.t.
}\rho_{k}+\Delta\in\mathcal{D},$ (110) which returns a feasible point
$\Delta^{*}$ as well as a dual value $-\epsilon\leq 0$ that lower-bounds the
true minimum of the SDP.

3.If $\epsilon\leq\epsilon_{\mathrm{tol}}$ then stop and return
$f_{\mathrm{obj}}(\rho_{k})-\epsilon$ as a lower bound on the optimization.

4.Otherwise, heuristically find
$\mu^{*}\coloneqq\arg\min_{\mu\in(0,1)}f_{\mathrm{obj}}(\rho_{k}+\mu\Delta^{*})$.

5.Set $\rho_{k+1}=\rho_{k}+\mu^{*}\Delta^{*}$, $k\leftarrow k+1$ and return to
Step 2.

Geometrically, the SDP in Eq. (110) corresponds to considering the tangent to
$f_{\mathrm{obj}}$ at $\rho_{k}$ and computing the maximum amount by which it
can decrease (as compared to its value at $\rho_{k}$) over the domain
$\mathcal{D}$. As described earlier, this bounds the maximum amount by which
$f_{\mathrm{obj}}$ can decrease from $f_{\mathrm{obj}}(\rho_{k})$ over
$\mathcal{D}$.

In our application of the Frank-Wolfe algorithm, there is the technical issue
that if $\mathcal{G}(\rho_{k})$ is singular (or has negative eigenvalues, from
numerical imprecision), then the derivative at $\rho_{k}$ (Eq. (108)) is ill-
behaved. To cope with this, we used the heuristic solution of simply replacing
$\rho_{k}$ with $(1-\delta)\rho_{k}+\delta\mathbb{U}$ in Step 2, where
$\delta\coloneqq\max(\operatorname{eigenvalues}(-\mathcal{G}(\rho_{k}))\cup\\{10^{-14}\\})$.
Note that this does not affect the _security_ of the result, since it merely
corresponds to taking a tangent at a slightly different point, which still
yields a valid lower bound. On the other hand, it could possibly affect the
theoretical convergence rates, but in practice this did not appear to pose a
significant problem in our setting. (In [WLC18], this issue is addressed by
analyzing a “perturbed” version of the optimization and applying a continuity
bound, but we found that for the level of accuracy we desired in this work,
the admissible perturbation values are too small to cope with the negative
eigenvalues that occur.)

###  5.4 Overall algorithm

Putting the above results together, we see that for any set of intervals
$[\theta_{j}-\delta_{j},\theta_{j}+\delta_{j}]$ such that
$[0,\pi]\subseteq\bigcup_{j}[\theta_{j}-\delta_{j},\theta_{j}+\delta_{j}]$,
and set $V$ such that
$S_{\put(1.5,2.5){\oval(4.0,4.0)[r]}\phantom{\circ}}\subseteq\operatorname{Conv}(V)$,
we have

$\displaystyle\min_{\rho_{AB}}\min_{{\theta_{B}}}\min_{{\theta_{A}}}F_{\mathrm{obj}}({\theta_{A}},{\theta_{B}},\rho_{AB})$
$\displaystyle\geq\min_{\rho_{AB}}\min_{{\theta_{B}}}\min_{j}F_{\mathrm{obj}}(\theta_{j},{\theta_{B}},\rho_{AB})-\epsilon_{\mathrm{con}}(\delta_{j})$
$\displaystyle=\min_{j}\min_{\rho_{AB}}\min_{(r_{Z},r_{X})\in
S_{\put(1.5,2.5){\oval(4.0,4.0)[r]}\phantom{\circ}}}F_{\mathrm{obj}}(\theta_{j},(r_{Z},r_{X}),\rho_{AB})-\epsilon_{\mathrm{con}}(\delta_{j})$
$\displaystyle\geq\min_{j}\min_{\rho_{AB}}\min_{(r_{Z},r_{X})\in
V}F_{\mathrm{obj}}(\theta_{j},(r_{Z},r_{X}),\rho_{AB})-\epsilon_{\mathrm{con}}(\delta_{j})$
$\displaystyle=\min_{j}\min_{(r_{Z},r_{X})\in
V}\min_{\rho_{AB}}F_{\mathrm{obj}}(\theta_{j},(r_{Z},r_{X}),\rho_{AB})-\epsilon_{\mathrm{con}}(\delta_{j}).$
(111)

We can refine the intervals $[\theta_{j}-\delta_{j},\theta_{j}+\delta_{j}]$
and set $V$ by the iterative processes described above, with the innermost
minimization over $\rho_{AB}$ being handled by the Frank-Wolfe algorithm. It
is clearly possible to swap the order of $\min_{j}$ and
$\min_{(r_{Z},r_{X})\in V}$ in the last line; however, some heuristic plots of
the objective function suggest that performing the optimizations in the order
shown here is slightly faster.

To see that this expression can converge to a tight bound, observe that the
first inequality in (111) becomes arbitrarily tight as we choose smaller
values of $\delta_{j}$. For the second inequality, note that the described
algorithm chooses $V$ in such a way that the minimum over $V$ approaches the
minimum over $S_{\put(1.5,2.5){\oval(4.0,4.0)[r]}\phantom{\circ}}$, hence this
inequality also becomes arbitrarily tight.

In general, the above approach faces the difficulty that it needs to optimize
over the choice of Lagrange multipliers $\vec{\lambda}$. Given that our
approach for solving (111) for a specific choice of Lagrange multipliers is
already highly computationally intensive (requiring about $5000$ core-hours to
achieve the level of accuracy in the bounds (117) below for each value of
$p$), it would be impractical to also optimize over the Lagrange multipliers
while doing so. It is more feasible to first optimize the Lagrange multipliers
while using a simple heuristic algorithm to estimate the minimizations, then
certify the final result using our approach for solving (111). (This is
essentially the same perspective as presented in [SBV+21].)

We remark that this approach can also yield arbitrarily tight bounds for DIRE,
where the goal would typically be [AFRV19, BRC20] to find lower bounds on
(weighted sums of) “two-party entropies” $H(A_{x}B_{y}|E)$. This is because by
the same arguments as above, we have
$H(A_{x}B_{y}|E)=D({\rho}_{AB}\|\mathcal{Z}_{xy}({\rho}_{AB}))$ [Col12,
TSG+19], where

$\displaystyle\mathcal{Z}_{xy}(\sigma_{AB})$
$\displaystyle\coloneqq\sum_{ab}({P}_{a|x}\otimes{P}_{b|y})\sigma_{AB}({P}_{a|x}\otimes{P}_{b|y}).$
(112)

(Here we omit the parts corresponding to noisy preprocessing, since it is not
applied in randomness expansion.) This expression can be bounded in the same
way as we have just described above, though the objective function would no
longer be affine with respect to $(r_{Z},r_{X})$, and hence the optimization
over Bob’s measurements would also have to be approached using a continuity
bound. Our approach should yield a substantial improvement over previous
results, which are restricted to the CHSH inequality and only bound the
entropy of one party’s outputs [LLR+19], or which consider the full
distribution and bound the entropy of both outputs but use inequalities that
are not tight [BRC20, TSG+19, BFF21]. In addition, the fact that it allows for
the random-key-measurement approach could yield further improvements, though
there are some technicalities that we address at the end of Sec. 6.2.

It would be convenient for future analysis if it were possible to develop
closed-form expressions for $\breve{r}_{p}$ (as was done in [HST+20, WAP21,
SBV+21]), rather than the computationally intensive numerical approaches shown
above. However, this appears to be rather challenging, as noted in [WAP21]. In
particular, we found numerical evidence against the conjecture proposed in
[SGP+21] that the minimum in (81) (when restricted to qubit strategies) can
always be attained by states such that $\rho_{AB}$ is of rank $2$. (A similar
observation was reported in [WAP21].) More precisely, in the process of
heuristically solving the optimizations in order to estimate suitable choices
of $\lambda$, we discovered that if we imposed the additional restriction that
$\rho_{AB}$ has rank $2$, there was a small but numerically significant
difference as compared to the results without this restriction. (The states
that heuristically approach the minimum in the latter indeed tend to have two
very small eigenvalues, but it appears that these eigenvalues cannot be
reduced exactly to zero.) This suggests that the aforementioned conjecture is
not true after all, which poses a challenge for closed-form analysis because
the eigenvalues involved in computing the entropy are genuinely roots of a
fourth-degree polynomial (in [HST+20, SBV+21], a key element of the analysis
was to argue that it suffices to consider rank-$2$ $\rho_{AB}$, simplifying
the expression for the eigenvalues).

###  5.5 Resulting bounds

(a) $p=0$ (b) $p=0.2$

Figure 4: The solid lines are the certified lower bounds we obtained (Eq.
(117)), while the points indicate the results of heuristically solving the
optimization (81) over qubit states and measurements (with just the CHSH value
as the constraint). As previously discussed, the tight bound in each case
would be given by the convex envelope of the curve traced out by the points,
assuming that the heuristics have found the true minimum. However, we can see
that in each case that curve appears to be nonconvex over the interval
$[2,2.75]$ (approximately), and its convex envelope would be affine over that
interval — specifically, it would be given by the linear interpolation between
the feasible points at the ends of that interval. The certified bound is
almost flush with this linear interpolation, indicating that it is basically
tight over this interval.

In Fig. 4, we show the affine bounds certified by our method when the only
constraint imposed is the CHSH value (which is what is relevant for Protocol
3). More precisely, we consider the described optimization with a single
constraint corresponding to the operator

$\displaystyle\Gamma({\theta_{A}},{\theta_{B}})=A_{0}\otimes
B_{0}+A_{0}\otimes B_{1}+A_{1}\otimes B_{0}-A_{1}\otimes B_{1},$ (113)

with the constraint value $\nu$ being the CHSH value. (As previously
mentioned, this can be implemented in the formulation where are 4 constraint
operators $\Gamma_{x,y}({\theta_{A}},{\theta_{B}})$ by simply restricting to
Lagrange-multiplier choices of the form
$(\lambda_{00},\lambda_{01},\lambda_{10},\lambda_{11})=(\lambda,\lambda,\lambda,-\lambda)$.)
Each choice of the associated Lagrange multiplier $\lambda$ yields an affine
lower bound of the form ${\lambda}{\nu}+c_{{\lambda}}$, as noted in Eq. (83).
Importantly, some heuristic computations (also observed in [SGP+21] for the
$p=0$ case) suggest that the true bound $\breve{r}_{p}({\nu})$ in this
situation is in fact affine over a wide range of CHSH values — we show this in
Fig. 4, which displays the results of heuristic minimizations compared to our
certified bound in some cases. In particular, this range on which the bound is
affine covers all currently experimentally reasonable values. This has the
implication that there is a single ${\lambda}$ that yields an affine lower
bound which is equal to $\breve{r}_{p}({\nu})$ (i.e. it is tight) over this
entire range; specifically, it is simply the value of ${\lambda}$
corresponding to the gradient of $\breve{r}_{p}({\nu})$ in this range. This
greatly simplifies our task since we only need to solve the optimization for
this specific value of ${\lambda}$.

We focused on several values of noisy preprocessing, ranging from $p=0$ to
$p=0.45$. In each case, we first solved the minimization (84) heuristically
for some selection of values of ${\lambda}$, in order to estimate the choice
of $\lambda$ that yields a tight bound over the range of CHSH values in which
$\breve{r}_{p}({\nu})$ is affine. Then using our algorithm to get certified
bounds on the corresponding $c_{\lambda}$ in (84), we arrived at the final
bounds

$\displaystyle\begin{gathered}\breve{r}_{0}({\nu})\geq
1.190(\nu-2)-0.00454,\qquad\breve{r}_{0.2}({\nu})\geq 0.327(\nu-2)+0.72063,\\\
\breve{r}_{0.3}({\nu})\geq
0.139(\nu-2)-0.88051,\qquad\breve{r}_{0.4}({\nu})\geq
0.0341(\nu-2)+0.97055,\\\ \breve{r}_{0.45}({\nu})\geq
0.00855(\nu-2)+0.992487,\end{gathered}$ (117)

some of which are shown in Fig. 4 (to express the bounds as functions of
winning probability $w$ instead, as we require for other figures, simply
replace $\nu$ in each expression with $8w-4$). From the $p=0.3$ bound, we
obtain the depolarizing-noise threshold of $9.33\%$ mentioned previously.
However, we were unable to obtain better thresholds using the higher values of
$p$, for reasons we shall now discuss.

###  5.6 Optimality of results

For each of the bounds in Eq. (117), there is a feasible point of the
optimization for $c_{\lambda}$ which yields a value within $0.005$ (or less,
for higher values of $p$) of the certified results shown in Eq. (117), so
these bounds on entropy are very close to optimal in terms of absolute error.
In terms of the depolarizing-noise thresholds that they yield, taking the
convex envelope of some of the feasible points shown in Fig. 4 yields the
result that the thresholds for $p=0.2$ and $p=0.3$ cannot be improved by more
than about $0.1$ percentage points, so those thresholds are very close to
optimal as well. However, larger values of $p$ face the issue that the
asymptotic keyrates become extremely low, which makes the horizontal
intercepts (i.e. the depolarizing-noise threshold) very sensitive to changes
in $\breve{r}_{p}$ — even a small absolute error in this bound results in a
significant change in the threshold value. Therefore, the thresholds we
obtained from the certified bounds with $p=0.4$ and $p=0.45$ in Eq. (117) were
only $9.32\%$ and $9.10\%$ respectively, worse than the results for $p=0.3$.
Heuristic computations suggest that the true thresholds for those cases might
be approximately $9.46\%$ and $9.50\%$ respectively, but using our algorithm
to certify these values would require it to converge to tolerances that
currently appear impractical. Hence a different approach may be needed to find
the true thresholds for these values of $p$. From a practical perspective
though, such improvements may be of limited use, because the very low
asymptotic rates mean that the finite-size keyrate would likely be zero until
extremely large sample sizes.

In any case, we note that for depolarizing noise at least, the threshold value
cannot be improved much further by _any_ protocol choices within the framework
we have presented in this section, e.g. by using the full distribution as
constraints (which also encompasses the use of modified CHSH inequalities
[WAP21, SBV+21]), or adjusting the values of $x$. This is essentially because
our bounds are very close to the linear interpolation between the points
$(2,h_{2}(p))$ and $(2\sqrt{2},1)$ (as can be seen from Fig. 4). Intuitively
speaking, the bound on the entropy against Eve in the depolarizing-noise
scenario cannot exceed this linear interpolation (because Eve can always
perform classical mixtures of strategies in order to attain every point on
this linear interpolation), which means that our bounds are close to the
highest bounds that are even possible in principle.

Making this reasoning quantitative, we can obtain an explicit upper bound on
the depolarizing-noise threshold. (We highlight that because we will do so by
constructing an extremely generic attack, this upper bound holds for _all_
protocols of this form, regardless of choices of parameters such as the input
distributions and noisy preprocessing. To some extent, it is surprising that
there even exist any protocols that achieve thresholds close to the upper
bounds implied by such a generic attack.) We first recall that (as defined in
Sec. 3.3) the measurement statistics in the depolarizing-noise model are given
by real projective measurements on the Werner state
$\varrho_{q}\coloneqq(1-2q)\left|\Phi^{+}\right>\\!\left<\Phi^{+}\right|+2q\,\mathbb{I}/4$.
It is known [AGT06, Kri79] that these measurement statistics can be reproduced
by a local-hidden-variable (LHV) model as soon as the state does not violate
the CHSH inequality, i.e. for $q\geq q_{2}\coloneqq{(2-\sqrt{2})}/{4}\approx
14.6\%$.202020In fact, this is also true in a more general context where the
honest parties have _any_ number of real projective measurements on the Werner
state, via the value of the second Grothendieck constant $K_{G}(2)=\sqrt{2}$
[AGT06, Kri79]. For general (i.e. not necessarily real) projective
measurements the analogous value is known to satisfy $q_{3}\lesssim 15.9\%$,
as follows from the best known bound on the third Grothendieck constant
$K_{G}(3)$ [HQV+17].

In the device-independent setting, the existence of an LHV model yields an
attack for Eve that gives her full knowledge of the measurement outcomes. This
means that for any depolarizing-noise value $q$, we can construct the
following attack for Eve: first, she generates a classical ancilla bit which
is equal to $0$ with probability $\mu\coloneqq(q_{2}-q)/q_{2}$. If the bit is
equal to $0$, Alice and Bob’s devices simply perform the honest measurements
on the maximally entangled state $\Phi^{+}$. Otherwise, the devices implement
an LHV model that yields the same statistics as the honest measurements
performed on the Werner state $\varrho_{q_{2}}$, but which gives Eve full
knowledge of the outcomes. This attack indeed reproduces the statistics
corresponding to depolarizing noise $q$, since
$\mu\left|\Phi^{+}\right>\\!\left<\Phi^{+}\right|+(1-\mu)\varrho_{q_{2}}=\varrho_{q}$
and the second strategy produces the same statistics as the honest
measurements performed on $\varrho_{q_{2}}$.

In the two cases, the entropies of Alice’s outputs after noisy preprocessing
are $H(\hat{A}_{x}|\tilde{E})_{\mathrm{triv}}=1$ (i.e. Eve’s side-information
is trivial since the Alice-Bob state is pure) and
$H(\hat{A}_{x}|\tilde{E})_{\mathrm{LHV}}=h_{2}(p)$ (i.e. the uncertainty
arises purely from the noisy preprocessing) respectively, where $\tilde{E}$
denotes Eve’s side-information excluding the ancilla bit. Incorporating the
ancilla bit into Eve’s side-information $E$, this attack achieves

$\displaystyle H(\hat{A}_{x}|E)=\mu
H(\hat{A}_{x}|\tilde{E})_{\mathrm{triv}}+(1-\mu)H(\hat{A}_{x}|\tilde{E})_{\mathrm{LHV}}=\frac{q_{2}-q}{q_{2}}+\frac{q}{q_{2}}h_{2}(p).$
(118)

This expression hence serves as an upper bound on the best possible lower
bound we could derive on the conditional entropy against Eve. Also, the
conditional entropy against Bob’s output (for Bob’s optimal key-generation
measurements on Werner states) is simply

$\displaystyle H(\hat{A}_{x}|B_{x})=h_{2}(p+(1-2p)q).$ (119)

Recalling that the asymptotic keyrate is given by the Devetak-Winter bound
[DW05] (up to the sifting-related weights $x$ [SGP+21]), this yields a simple
upper bound on the critical value of $q$ that still allows a positive
asymptotic keyrate (for protocols of this form, i.e. applying noisy
preprocessing, random key measurements, and considering the full output
distribution, but only using one-way error correction):

$\displaystyle q_{\textrm{att}}(p)\coloneqq$
$\displaystyle\max\bigg{\\{}q\,\bigg{|}\,\sum_{x}x(H(\hat{A}_{x}|E)-H(\hat{A}_{x}|B_{x}))\geq
0\bigg{\\}}$ $\displaystyle=$
$\displaystyle\max\left\\{q\,\middle|\,\frac{q_{2}-q}{q_{2}}+\frac{q}{q_{2}}h_{2}(p)-h_{2}(p+(1-2p)q)\geq
0\right\\},$ (120)

where in the first line the entropies refer to those of the attack we have
described. We observe numerically that this upper bound is increasing with
respect to $p$, so we have $q_{\textrm{att}}(p)\leq q_{\textrm{att}}(p\to
1/2)$. In the limit $p\to 1/2$ we can write $p=1/2-\delta$ and expand the
expression in small $\delta$ to find

$q_{\textrm{att}}\\!\left(p\to\frac{1}{2}\right)=\frac{1+4q_{2}-\sqrt{8q_{2}+1}}{8q_{2}}=1-\frac{\sqrt{7+4\sqrt{2}}-1}{2\sqrt{2}}\approx
9.57\%.$ (121)

Hence for protocols of the form described in this work, it is not possible for
the depolarizing-noise threshold to exceed this value. For the parameter
choice $p=0.3$, we have $q_{\textrm{att}}(0.3)\approx 9.51\%$, which is close
to the threshold of $9.33\%$ for which we could certify a positive
keyrate.212121These two thresholds cannot match exactly, because the feasible
points shown in Fig. 4 also imply that the tight bound $\breve{r}_{p}({\nu})$
is not _exactly_ equal to the linear interpolation between $(2,h_{2}(p))$ and
$(2\sqrt{2},1)$, which essentially corresponds to the attack we describe here.

Finally, it is worth noting that while the main focus of this work is
depolarizing noise applied to the statistics corresponding to the ideal CHSH
measurements on $\Phi^{+}$, the above analysis in fact generalizes to a
substantially larger family of scenarios. Specifically, the same analysis
applies for depolarizing noise applied to the statistics from any number of
real projective measurements on $\Phi^{+}$, since the results of [AGT06,
Kri79] yield the required LHV models.222222A more general consideration would
be the scenario of depolarizing noise applied to the statistics from an
arbitrary two-qubit state, but it is not immediately obvious whether the
thresholds in [AGT06, Kri79, HQV+17] apply to such states as well, so we leave
this for future work. (If Bob performs suboptimal generation measurements,
then Eq. (119) still holds as a lower bound, so the argument carries through.)
In addition, replacing $q_{2}$ with $q_{3}$ straightforwardly provides a
threshold of $q\lesssim 10.01\%$ for all possible projective measurements on
that state, via the respective known bound in [HQV+17]. (Note that in all such
cases where there are more than 2 possible measurements, there is no “qubit
reduction” to make it easier to derive corresponding lower bounds, and hence
the lower bounds have also not been very thoroughly explored.) An interesting
further consideration is the case of general POVM measurements. Here, a rather
loose bound $q_{\textrm{POVM}}\lesssim 27.3\%$ is also known [HQV+17] for the
threshold that allows an LHV description. However, pure POVMs on qubits can
involve up to four outcomes, opening up the possibility of more general noisy
preprocessing — all doubly stochastic maps on probability vectors with four
outcomes. We thus leave it for future work.

The above argument relies on the fact that depolarizing-noise statistics can
be obtained by simple mixtures of “extremal” strategies. This is not
necessarily the case for other noise models, such as limited detection
efficiency in photonic experiments. Therefore, the same argument cannot be
directly applied to obtain upper bounds on the thresholds for such forms of
noise.

##  6 Possible modifications

###  6.1 Coordinating input choices by public communication

The random-key-measurement protocol has the drawback that the keyrate is
effectively halved, since the generation rounds have “mismatched” inputs
approximately half the time. It would be helpful to find a way to work around
this issue. One possible approach could be to observe that in [AFRV19], it was
assumed that the following operations can be performed in each round: the
devices receive some shares of a quantum state, then232323The assumption being
made here is that since the quantum states are now entirely in the possession
of Alice and Bob, the test/generation decision can no longer affect the
distributed state — if the distributed state could depend on whether it is a
test or generation round, the protocol would be trivially insecure. Alice and
Bob publicly communicate to come to an agreement on _both_ of their input
choices, and finally they supply these inputs to their devices. (This was
necessary in [AFRV19] because Alice and Bob’s actions in that DIQKD protocol
require both of them to know whether it is a test or generation round. In
fact, our analysis can be viewed as the first EAT-based security proof for a
“genuinely sifting-based” DIQKD protocol, in the sense that Alice and Bob do
not coordinate which rounds are test rounds, and simply choose their inputs
independently.) If we assume that this is also possible in our scenario, then
Alice and Bob could coordinate their inputs in the generation rounds instead
of choosing them independently, thereby avoiding the sifting factor.

Unfortunately, it does not seem clear if such a proposal is entirely plausible
in near-term experimental implementations. This is because it relies on the
devices being able to store the quantum state for long enough for Alice and
Bob to agree on their choice of inputs, which is potentially challenging for
current Bell-test implementations. As an alternative, we propose the following
potential modification to the DIQKD protocol in [AFRV19] — instead of agreeing
on the test rounds via public communication, Alice and Bob could use a small
amount of pre-shared key to choose which rounds are test rounds, in the same
way as in DIRE (for details on the amount of pre-shared key required, see the
DIRE protocols in [AFRV19, BRC20] or the discussion in Sec. 6.2 below). This
approach would essentially be a “key expansion” protocol that requires a small
amount of pre-shared key to initialize. We remark that this is not a dramatic
change in perspective, because a common method to authenticate channels
(namely, message authentication codes) relies on having a small amount of pre-
shared key, so the assumed existence of authenticated channels in the DIQKD
protocol is likely to require some pre-shared key in any case.

However, this basic notion cannot immediately be generalized to Protocol 3
here, since requiring Alice and Bob to choose uniformly distributed “matching”
inputs in the generation rounds would require a large amount of pre-shared key
(roughly $(1-\gamma)n$ bits). Fortunately, in the following section, we
propose a variation which overcomes this difficulty by “recovering” the
entropy in the pre-shared key, thereby still achieving net key expansion.

###  6.2 Protocol using pre-shared key

Here we describe a variant protocol that avoids the sifting factor _without_
requiring the brief quantum storage described above, through the use of a
fairly long pre-shared key. The limitation of this variant is that the net
increase in secret key is just a (constant) fraction of the amount of pre-
shared key; however, the _rate_ of net key generation does not have the
sifting factor of $1/2$. Informally, the idea is to simply use the pre-shared
key as Alice’s input string $\mathbf{X}$, which allows Bob to choose his
generation inputs to match Alice’s. Just as importantly, this also allows them
to (almost) entirely omit the public announcement of their inputs — hence
$\mathbf{X}$ remains private, and with some care it can be incorporated into
the final key without losing the entropy it “contains”.

We now describe this idea in detail as Protocol 6.2 below, followed by its
security proof. The protocol supposes that Alice and Bob hold a pre-shared
(uniform) key of $n$ bits, which we shall simply denote as $\mathbf{X}$, since
it will be exactly the string that Alice uses as her inputs. The appropriate
value of $\ell_{\mathrm{key}}$ to choose will be described later in Theorem 3.
2

This protocol proceeds the same way as Protocol 3, except for the following
changes:

  * •

In each round, Alice’s input $X_{j}$ is determined from the pre-shared key
$\mathbf{X}$, instead of being generated randomly in that round. Bob’s input
$Y_{j}$ is generated as follows: with probability $\gamma$ he chooses a
uniformly random $Y_{j}\in\\{2,3\\}$, otherwise Bob chooses $Y_{j}=X_{j}$. In
addition, he generates another register $Y^{\prime}_{j}$ which equals $Y_{j}$
when $Y_{j}\in\\{2,3\\}$ and equals $\perp$ otherwise.

  * •

Alice and Bob do not publicly announce the strings $\mathbf{X}\mathbf{Y}$.
Instead, Bob only announces the string ${\mathbf{Y}^{\prime}}$.242424It might
be possible to consider a slight variant which omits this step. However,
knowing ${\mathbf{Y}^{\prime}}$ allows Alice to compute $\mathbf{Y}$, which
may be relevant for error correction since it allows Alice to distinguish the
test and generation rounds. In any case, it seems unclear whether the entropy
of ${\mathbf{Y}^{\prime}}$ can be usefully extracted even if it is kept
secret, since Alice does not have access to it in that case. Additionally, the
sifting step is unnecessary, since there will be no rounds such that
$Y_{j}\in\\{0,1\\}$ and $X_{j}\neq Y_{j}$.

  * •

Privacy amplification is performed on the strings $\mathbf{A}\mathbf{X}$ and
$\tilde{\mathbf{A}}\mathbf{X}$ instead of $\mathbf{A}$ and
$\tilde{\mathbf{A}}$.

To prove the security of this protocol, we can simply follow almost exactly
the same security proof as for Protocol 3, with some changes we shall now
describe. Firstly, the value of $h_{\mathrm{hon}}$ (to be used when computing
$\mathrm{EC}_{\mathrm{max}}$) is replaced by

$\displaystyle\tilde{h}_{\mathrm{hon}}=H(A_{j}|B_{j}X_{j}Y_{j})_{\mathrm{hon}}$
$\displaystyle=\frac{1-\gamma}{2}\sum_{z\in\\{0,1\\}}H(A_{j}|B_{j};X_{j}=Y_{j}=z)_{\mathrm{hon}}$
$\displaystyle\qquad+\frac{\gamma}{4}\sum_{x\in\\{0,1\\},y\in\\{2,3\\}}H(A_{j}|B_{j};X_{j}=x,Y_{j}=y)_{\mathrm{hon}},$
(122)

since the probabilities of $X_{j}=Y_{j}=z$ for $z\in\\{0,1\\}$ are now
${(1-\gamma)}/{2}$. (Note that no error-correction information needs to be
sent from Alice to Bob regarding $\mathbf{X}$, since both of them have a copy
of that string.)

Also, since the strings used in the privacy-amplification step are now
$\mathbf{A}\mathbf{X}$ and $\tilde{\mathbf{A}}\mathbf{X}$, this means that we
need an equivalent of Eq. (78), with
$H_{\mathrm{min}}^{\epsilon_{s}^{\prime}}(\mathbf{A}{\mathbf{B}^{\prime}}\mathbf{X}|{\mathbf{Y}^{\prime}}E)$
in place of
$H_{\mathrm{min}}^{\epsilon_{s}^{\prime}}(\mathbf{A}{\mathbf{B}^{\prime}}|\mathbf{X}\mathbf{Y}E)$.
To obtain this, we note that we can simply construct a virtual protocol in the
analogous way to Protocol $1^{\prime}$, then consider the same EAT channels
$\mathcal{M}_{j}$ as before, but instead we shall identify $C^{\prime}_{j}$
with $D_{j}$, $A_{j}B^{\prime}_{j}X_{j}$ with $S_{j}$, and $Y^{\prime}_{j}$
with $T_{j}$ in Definition 10. The Markov conditions are again fulfilled,
since $Y^{\prime}_{j}$ is generated by trusted randomness in each round and
independent of all previous data. To find an appropriate min-tradeoff function
for these channels, we note that the output
$(\mathcal{M}_{j}\otimes\mathcal{I}_{R})(\omega_{R_{j-1}R})$ of channel
$\mathcal{M}_{j}$ always satisfies

$\displaystyle H(X_{j}|Y^{\prime}_{j}R)=H(X_{j})=1,$ (123)

because $X_{j}$ is produced by trusted randomness independent of
$Y^{\prime}_{j}R$. Therefore, we can use the chain rule to write

$\displaystyle H(A_{j}B^{\prime}_{j}X_{j}|Y^{\prime}_{j}R)$
$\displaystyle=H(X_{j}|Y^{\prime}_{j}R)+H(A_{j}B^{\prime}_{j}|X_{j}Y^{\prime}_{j}R)$
$\displaystyle\geq 1+(1-\gamma)r_{p}(w)+\gamma r_{0}(w)$
$\displaystyle\coloneqq 1+\tilde{g}(w),$ (124)

where the function $\tilde{g}$ (in contrast to $g$) does not have the factor
of $1/2$ introduced by sifting, since Alice does not “erase” the outputs of
any rounds. We can thus construct a new min-tradeoff function
$\tilde{f}_{\mathrm{min}}$ in the same way as in Sec. 4.3.1, but using
$1+\tilde{g}(w)$ in place of $g(w)$.252525We remark that if we think of this
replacement as happening in two steps, first replacing $g$ by $\tilde{g}$ and
then adding a “constant offset” of $1$, then the latter has no effect on
$\operatorname{Var}_{\mathcal{Q}_{f}}(f_{\mathrm{min}})$ or the difference
$\operatorname{Max}(f_{\mathrm{min}})-\operatorname{Min}_{\mathcal{Q}_{f}}(f_{\mathrm{min}})$,
and hence does not change the finite-size correction to the keyrate except
indirectly via changing the system dimensions and the range of $\beta$.
However, the first step of replacing $g$ by $\tilde{g}$ does slightly increase
the finite-size correction (since $\tilde{g}$ has a somewhat larger range).
The rest of the proof then proceeds as before, leading to the following
security statement:

######  Theorem 3.

Protocol 6.2 has the same security guarantees as those described in Theorem 1,
except with the following changes:

  * •

$\beta$ is chosen to be in $[1+\tilde{g}(0),1+\tilde{g}(1)]$ instead.

  * •

$h_{\mathrm{hon}}$ is replaced by $\tilde{h}_{\mathrm{hon}}$ as specified in
Eq. (122).

  * •

In Eq. (33) for $\ell_{\mathrm{key}}$,
$g(w_{\mathrm{exp}}-\delta_{\mathrm{tol}})$ is replaced by
$1+\tilde{g}(w_{\mathrm{exp}}-\delta_{\mathrm{tol}})$, and the values of $V$
and $K_{\alpha}$ are replaced by

$\displaystyle\begin{aligned}
\tilde{V}&\coloneqq\sqrt{\operatorname{Var}_{\mathcal{Q}_{f}}(\tilde{f}_{\mathrm{min}})+2}+\log
289,\\\ \tilde{K}_{\alpha}&\coloneqq\frac{2^{(\alpha-1)(2\log
12+\operatorname{Max}(\tilde{f}_{\mathrm{min}})-\operatorname{Min}_{\mathcal{Q}_{f}}(\tilde{f}_{\mathrm{min}}))}}{6(2-\alpha)^{3}\ln
2}\ln^{3}\left(2^{2\log
12+\operatorname{Max}(\tilde{f}_{\mathrm{min}})-\operatorname{Min}_{\mathcal{Q}_{f}}(\tilde{f}_{\mathrm{min}})}+e^{2}\right),\end{aligned}$
(125)

where $\tilde{f}_{\mathrm{min}}$ is a function that satisfies

$\displaystyle\begin{gathered}\operatorname{Max}(\tilde{f}_{\mathrm{min}})=1+\frac{1}{\gamma}\tilde{g}(1)+\left(1-\frac{1}{\gamma}\right)\beta,\qquad\operatorname{Min}_{\mathcal{Q}_{f}}(\tilde{f}_{\mathrm{min}})=1+\tilde{g}\\!\left(\frac{2-\sqrt{2}}{4}\right),\\\
\operatorname{Var}_{\mathcal{Q}_{f}}(\tilde{f}_{\mathrm{min}})\leq\frac{2-\sqrt{2}}{4\gamma}\min\left\\{\Delta_{0}^{2},\Delta_{1}^{2}\right\\}+\frac{2+\sqrt{2}}{4\gamma}\max\left\\{\Delta_{0}^{2},\Delta_{1}^{2}\right\\},\text{
where }\Delta_{w}\coloneqq\beta-1-\tilde{g}(w).\end{gathered}$ (128)

Overall, recalling that Protocol 3 required $n$ bits of pre-shared key, we see
that the _net_ gain of secret key bits in Protocol 6.2 is larger than that of
Protocol 3 by a factor of approximately (ignoring the changes to the finite-
size corrections)

$\displaystyle\frac{n\left(\tilde{g}(w_{\mathrm{exp}}-\delta_{\mathrm{tol}})-\tilde{h}_{\mathrm{hon}}\right)}{n\Big{(}g(w_{\mathrm{exp}}-\delta_{\mathrm{tol}})-h_{\mathrm{hon}}\Big{)}}\approx
2,$ (129)

since it avoids the sifting factor. Informally, by keeping $\mathbf{X}$ secret
and incorporating it in the privacy amplification step, we have “recovered”
the entropy that was present in the original pre-shared key.262626Note that
the underlying idea here critically relies on the fact that the bound $r_{p}$
is for the entropy of the output strings _conditioned on $X_{j}$_. This
allowed us to use the chain rule to obtain Eq. (68), which eventually led to
the result that the seed entropy contained in $\mathbf{X}$ simply “adds on” to
the entropy of the output strings in the original Protocol 3. If $r_{p}$ had
been a bound on, for instance, $H(A_{j}|Y^{\prime}_{j}R)$ instead of
$H(A_{j}|X_{j}Y^{\prime}_{j}R)$, this argument would not have worked.

In practice, including the string $\mathbf{X}$ in privacy amplification
essentially doubles the input size for the hash function in that step, which
raises its computational difficulty substantially (though not insurmountably).
One might wonder whether it would be possible to bypass this aspect — for
instance, by simply performing privacy amplification on $\mathbf{A}$ and
$\tilde{\mathbf{A}}$ as before, then appending $\mathbf{X}$ to the output. At
first glance, this approach might appear plausible, since $\mathbf{X}$ is not
announced in Protocol 6.2. Unfortunately, it seems unclear how to certify that
the publicly communicated error-correction string $\mathbf{L}$ is independent
of $\mathbf{X}$ (in fact, it seems unlikely that this is true). Hence the idea
of simply appending $\mathbf{X}$ may not be secure. By instead incorporating
it in privacy amplification in the specified manner, Protocol 6.2 ensures that
the entropy of $\mathbf{X}$ is securely “extracted” into the final key.

As previously mentioned, the net increase in secret key given by one instance
of Protocol 6.2 is limited to a fraction of the amount of pre-shared key.
However, it is possible in principle to recursively run Protocol 6.2 in order
to achieve unbounded key expansion — one can use the key generated by one
instance of Protocol 6.2 to run it again with a longer pre-shared key and
larger $n$ (since the security definition is composable, the soundness
parameter will only increase additively in this process [PR14]). We stress
that in doing so, one must always incorporate the seed into the privacy-
amplification step exactly as specified in Protocol 6.2 — in particular, this
means that the _entire_ key changes with every iteration, instead of simply
having some new bits appended. Some care is necessary regarding device memory
across instances of this recursive procedure — while it does not seem to be
directly vulnerable to the memory attack of [BCK13]272727This is because the
only public communication in Protocol 6.2 that can leak any information is the
error-correction string (all other public communication is based on trusted
randomness). In our security proof, we have bounded the min-entropy leakage at
this step simply via the length of this string, without any assumptions about
its structure, and hence we can still obtain a secure bound on the min-entropy
of the input for privacy amplification in the final protocol instance. Note
that this claim is strictly restricted to device reuse following the recursive
process specified here — once any key bits have been used for any other
purpose, the attack again becomes a potential concern if the devices are
reused., it is still important to ensure that the states measured in each
instance of the protocol are independent of the key generated in the preceding
instance, since this key is used to choose the device inputs (which must be
independent of the state in order for our security arguments to hold). Again,
this relies on the notion that the registers measured by the devices do not
contain information about the key generated in the preceding instance.

There is another potential variant of this idea where a pre-shared key is
instead used to generate _both_ input strings $\mathbf{X}$ and $\mathbf{Y}$,
and the input-choice announcement is omitted entirely, with privacy
amplification being performed on $\mathbf{A}\mathbf{X}\mathbf{Y}$ and
$\tilde{\mathbf{A}}\mathbf{X}\mathbf{Y}$. This can be done by using $\kappa
h_{2}(\gamma)n$ bits to choose the test rounds approximately according to the
desired IID distribution of test rounds, then using $\kappa^{\prime}\gamma n$
bits to set the value of $Y_{j}$ in the test rounds, where
$\kappa,\kappa^{\prime}>1$ are constants that can be chosen such that the
approximations to the desired distributions are sufficiently accurate (see the
randomness-expansion protocols in [AFRV19, BRC20] for a more complete
description of this process based on the _interval algorithm_), and $n$ bits
to set the value of $X_{j}$ in all rounds.282828We break up the use of the
seed into separate processes because it allows for better efficiency as
compared to directly approximating the desired distribution of
$\mathbf{X}\mathbf{Y}$ — with the approach we describe, the “inefficiency”
prefactors $\kappa,\kappa^{\prime}$ of the interval algorithm only appear on
the $h_{2}(\gamma)n,\gamma n$ terms instead of the full entropy of
$\mathbf{X}\mathbf{Y}$. This would hence require $(1+\kappa
h_{2}(\gamma)+\kappa^{\prime}\gamma)n$ bits of seed randomness. A similar
argument as above could then be performed by noting that (for $X_{j}Y_{j}$
generated according to the ideal distribution) we have
$H(X_{j}Y_{j})=1+h_{2}(\gamma)+\gamma$, so most of the seed entropy can be
“recovered”, up to the losses from the $\kappa,\kappa^{\prime}$ factors.
However, tracking the effects of using the interval algorithm to approximate
the ideal distribution is cumbersome (albeit possible), and it is unclear if
this variant offers any immediate advantage over Protocol 6.2 for DIQKD —
though it may be useful for protocols that use other Bell inequalities or non-
uniform input distributions, as mentioned in Sec. 4.4.

On the other hand, it appears that this variant may have potential for the
purposes of DIRE instead. The main reason why the random-key-measurement
approach in [SGP+21] could not be easily generalized to DIRE is that in order
for Alice to select a uniformly random input in every round, she requires a
(local) source of $n$ random bits, which is a free resource in DIQKD but not
in DIRE — if a proposed DIRE protocol consumes more random bits than it
produces, then it has failed to achieve randomness _expansion_ 292929There is,
however, the related but distinct task of device-independent randomness
_generation_ [ZSB+20] (where the goal is to produce private randomness from an
unbounded supply of public randomness that is independent from the devices),
in which this would not be an issue.. However, the protocol proposed in this
section has the property that it “recovers” the entropy contained in the seed,
which means that one can afford to use much larger seeds while still obtaining
a net increase in secret key. Explicitly, the application of this idea to DIRE
would hence be as follows: one begins with $2n$ random bits, which are then
used as the input strings303030For DIRE based on the CHSH inequality, Bob only
requires two possible measurements instead of the four required for the DIQKD
protocol here. $\mathbf{X}\mathbf{Y}$ to the devices over $n$ rounds to obtain
outputs $\mathbf{A}\mathbf{B}$. Modelling this process using EAT channels in a
manner similar to above (see e.g. [LLR+19] for details), for each round we
would have

$\displaystyle H(A_{j}B_{j}X_{j}Y_{j}|R)$
$\displaystyle=H(X_{j}Y_{j}|R)+H(A_{j}B_{j}|X_{j}Y_{j}R)$
$\displaystyle=2+H(A_{j}B_{j}|X_{j}Y_{j}R),$ (130)

which (given a bound on $H(A_{j}B_{j}|X_{j}Y_{j}R)$) allows one to bound the
smoothed min-entropy of $\mathbf{A}\mathbf{B}\mathbf{X}\mathbf{Y}$ conditioned
on $E$. By performing privacy amplification on
$\mathbf{A}\mathbf{B}\mathbf{X}\mathbf{Y}$, one “recovers” all the entropy in
the seed, due to the $H(X_{j}Y_{j}|R)$ term in the above equation. Overall,
this proposed protocol allows one to use the improved entropy rate provided by
the random-key-measurement approach [SGP+21], in the context of DIRE instead
of DIQKD.

###  6.3 Collective attacks

As a reference to compare our results against, we could consider whether a
longer secure key could be obtained under the _collective-attacks_ assumption,
which is the assumption that the device behaviour is IID in each round of the
protocol (though Eve can still store quantum information for arbitrary
periods).313131To be precise, we mean that the part of the state held by Alice
and Bob’s devices is IID across the rounds, and in each round the devices have
the same set of possible measurements. Since all purifications are
isometrically equivalent, without loss of generality we can suppose that Eve
also holds an IID purification of the Alice-Bob state. To this end, we derive
the following theorem, with the proof given in Appendix C:

######  Theorem 4.

Take any
$\epsilon^{\mathrm{com}}_{\mathrm{EC}},\epsilon^{\mathrm{com}}_{\mathrm{PE}},\epsilon_{\mathrm{PA}},\epsilon_{\mathrm{h}},\epsilon_{s}\in(0,1]$,
$\gamma\in(0,1)$, $p\in[0,1/2]$, and
$\delta_{\mathrm{IID}}\in[0,w_{\mathrm{exp}}-\delta_{\mathrm{tol}})$. Define

$\displaystyle\epsilon_{\mathrm{IID}}\coloneqq
B_{n,1-(w_{\mathrm{exp}}-\delta_{\mathrm{tol}}-\delta_{\mathrm{IID}})\gamma}(\left\lfloor(1-(w_{\mathrm{exp}}-\delta_{\mathrm{tol}})\gamma)n\right\rfloor).$
(131)

Under the collective-attacks assumption, Protocol 3 is
$(\epsilon^{\mathrm{com}}_{\mathrm{EC}}+\epsilon^{\mathrm{com}}_{\mathrm{PE}})$-complete
and
$(\max\\{\epsilon_{\mathrm{IID}},\epsilon_{\mathrm{PA}}+2\epsilon_{s}\\}+2\epsilon_{\mathrm{h}})$-sound
when performed with any choice of $\mathrm{EC}_{\mathrm{max}}$ and
$\delta_{\mathrm{tol}}$ such that Eq. (14) and Eq. (32) hold, and
$\ell_{\mathrm{key}}$ satisfying

$\displaystyle\ell_{\mathrm{key}}\leq
ng(w_{\mathrm{exp}}-\delta_{\mathrm{tol}}-\delta_{\mathrm{IID}})-\sqrt{n}\,(2\log
5)\sqrt{\log\frac{2}{\epsilon_{s}^{2}}}-\mathrm{EC}_{\mathrm{max}}-\left\lceil\log\left(\frac{1}{\epsilon_{\mathrm{h}}}\right)\right\rceil-2\log\frac{1}{\epsilon_{\mathrm{PA}}}+2.$
(132)

However, the above theorem is simply a statement for Protocol 3 under the
assumption of collective attacks, and that protocol does not fully exploit
some implications of that assumption. For instance, in Theorem 4 there is
implicitly an $O(\gamma)$ subtractive penalty to the keyrates (which was also
present in Theorem 1323232In fact, Theorem 1 has another $O(\gamma)$
subtractive penalty from the use of the bound (68), but this was due to the
technical limitations of the EAT and the fact that the bounds (69) and (72)
are slightly suboptimal.) caused by having to include the test-round data in
the $\mathrm{EC}_{\mathrm{max}}$ term. Yet under the collective-attacks
assumption, the test rounds are completely independent of the generation
rounds, which implies that the effect of $\gamma$ should instead be to reduce
the keyrate by a _multiplicative_ factor of $(1-\gamma)$. Importantly, in the
latter case it is possible to choose arbitrarily large test probabilities
$\gamma$ without necessarily making the keyrates negative, which can
dramatically improve the statistical bounds for parameter estimation. To
formalize this idea, we consider Protocol 4 below, which attempts to minimize
the finite-size correction as much as possible using the most optimistic
assumptions that have been discussed thus far.
3

This protocol proceeds the same way as Protocol 3, except for the following
changes:

  * •

Instead of independently choosing whether each round is a test or generation
round, Alice chooses a uniformly random subset of size $m$ as test rounds
before the protocol begins, and we define $\gamma$ as the value $m/n$. Alice
also prepares the strings $\mathbf{X}\mathbf{Y}$ in advance, by choosing
$X_{j}=Y_{j}\in\\{0,1\\}$ uniformly at random in the generation rounds, and
choosing $X_{j}\in\\{0,1\\},Y_{j}\in\\{2,3\\}$ uniformly at random in the test
rounds.

  * •

In each round, Alice and Bob briefly store their received quantum states
instead of immediately measuring them. Alice then publicly announces
$X_{j}Y_{j}$, which Alice and Bob then use as the inputs to their
devices.333333Here, in our attempt to minimize the finite-size effects, we are
following the [AFRV19] assumption mentioned previously: Alice and Bob can
briefly store their received quantum states, in a manner such that the public
communication cannot affect the stored states.

  * •

In the error-correction step, Alice does not send error-correction data (and a
corresponding hash) for the full string $\mathbf{A}$, but rather only the
subset of it consisting of the generation rounds, denoted as $\mathbf{A}_{g}$.
Bob’s guess for this string will be denoted as $\tilde{\mathbf{A}}_{g}$. The
values of $\mathbf{A}$ in the test rounds, denoted as $\mathbf{A}_{t}$, are
sent directly to Bob without compression or encryption, and Bob uses this
string for parameter estimation.

  * •

Bob’s accept condition is instead to check that
$\operatorname{hash}(\mathbf{A}_{g})=\operatorname{hash}(\tilde{\mathbf{A}}_{g})$
and $\operatorname{freq}_{\mathbf{c}_{t}}(1)\geq
w_{\mathrm{exp}}-\delta_{\mathrm{tol}}$ hold, where $\mathbf{C}_{t}$ denotes
the substring of $\mathbf{C}$ corresponding to the test rounds (in particular,
this means the frequencies are computed with respect to a string of length
$\gamma n$, not $n$).

  * •

Privacy amplification is performed only on the strings $\mathbf{A}_{g}$ and
$\tilde{\mathbf{A}}_{g}$.

For this protocol, the value of $\mathrm{EC}_{\mathrm{max}}$ is to be computed
based only on the number of generation rounds, since error correction is
performed on the string $\mathbf{A}_{g}$ rather than $\mathbf{A}$. Focusing on
the best possible theoretical bounds from Sec. 3.1, this means we take
$\mathrm{EC}_{\mathrm{max}}$ to be given by Eq. (15) with

$\displaystyle
H_{\mathrm{max}}^{\tilde{\epsilon}_{s}}(\mathbf{A}|\mathbf{B}\mathbf{X}\mathbf{Y})_{\mathrm{hon}}\leq(1-\gamma)nh_{\mathrm{hon}}+\sqrt{(1-\gamma)n}\,(2\log
5)\sqrt{\log\frac{2}{\tilde{\epsilon}_{s}^{2}}},$ (133)

where

$\displaystyle
h_{\mathrm{hon}}=\sum_{z\in\\{0,1\\}}\frac{1}{2}H(A_{j}|B_{j};X_{j}=Y_{j}=z)_{\mathrm{hon}},$
(134)

since the test rounds are excluded. With this value of
$\mathrm{EC}_{\mathrm{max}}$ in mind, we can state the security guarantees of
this protocol, with the proof given in Appendix D (note that the dependence on
several security parameters here is somewhat different as compared to the
previous theorems):

######  Theorem 5.

Take any
$\epsilon^{\mathrm{com}}_{\mathrm{EC}},\epsilon^{\mathrm{com}}_{\mathrm{PE}},\epsilon_{\mathrm{PA}},\epsilon_{\mathrm{h}},\epsilon_{s}\in(0,1]$,
$\gamma\in(0,1)$, $p\in[0,1/2]$, and
$\delta_{\mathrm{IID}}\in[0,w_{\mathrm{exp}}-\delta_{\mathrm{tol}})$. Define

$\displaystyle\epsilon_{\mathrm{IID}}\coloneqq B_{\gamma
n,1-w_{\mathrm{exp}}+\delta_{\mathrm{tol}}+\delta_{\mathrm{IID}}}(\left\lfloor(1-w_{\mathrm{exp}}+\delta_{\mathrm{tol}})\gamma
n\right\rfloor).$ (135)

Under the collective-attacks assumption, Protocol 4 is
$(\epsilon^{\mathrm{com}}_{\mathrm{EC}}+\epsilon^{\mathrm{com}}_{\mathrm{PE}})$-complete
and
$(\max\\{\epsilon_{\mathrm{IID}},\epsilon_{\mathrm{PA}}+2\epsilon_{s}\\}+\epsilon_{\mathrm{h}})$-sound
when performed with $\mathrm{EC}_{\mathrm{max}}$ defined in terms of
$\epsilon^{\mathrm{com}}_{\mathrm{EC}}$ as described above, and
$\delta_{\mathrm{tol}},\ell_{\mathrm{key}}$ satisfying

$\displaystyle\epsilon^{\mathrm{com}}_{\mathrm{PE}}$ $\displaystyle\geq
B_{\gamma
n,w_{\mathrm{exp}}}(\left\lfloor(w_{\mathrm{exp}}-\delta_{\mathrm{tol}})\gamma
n\right\rfloor),$ (136) $\displaystyle\ell_{\mathrm{key}}$
$\displaystyle\leq(1-\gamma)nr_{p}(w_{\mathrm{exp}}-\delta_{\mathrm{tol}}-\delta_{\mathrm{IID}})-\sqrt{(1-\gamma)n}\,(2\log
5)\sqrt{\log\frac{2}{\epsilon_{s}^{2}}}$
$\displaystyle\qquad-\mathrm{EC}_{\mathrm{max}}-\left\lceil\log\left(\frac{1}{\epsilon_{\mathrm{h}}}\right)\right\rceil-2\log\frac{1}{\epsilon_{\mathrm{PA}}}+2.$
(137)

(a) [RBG+17] parameters, $p=0$ (b) [RBG+17] parameters, $p=0.03$ (with
heuristic $r_{p}$)

Figure 5: Finite-size keyrates as a function of number of rounds in Protocol 4
(see Theorem 5), using honest devices following the estimated parameters in
[MDR+19] for the loophole-free Bell test in [HBD+15], for $p=0$ and $p=0.03$
(the latter is a rough estimate of the choice of $p$ which yields the highest
asymptotic keyrate for these experimental parameters). Note that the latter
graph is computed using a heuristic estimate of $r_{p}$ rather than a
certified bound. The error-correction protocol is taken to satisfy Eqs. (15)
and (133). The colours correspond to soundness parameters of
$\epsilon^{\mathrm{sou}}=10^{-3}$, $10^{-6}$, and $10^{-9}$ for black, blue,
and red respectively, and the completeness parameter is
$\epsilon^{\mathrm{com}}=10^{-2}$ in all cases. The horizontal line denotes
the asymptotic keyrate. All other parameters in Theorem 5 were numerically
optimized. The required number of rounds to achieve positive keyrate is
substantially lower than Protocol 3 (see Fig. 2).

In Fig. 5, we plot the results of Theorem 5, focusing on the [RBG+17]
experiment. This protocol has improved finite-size performance as compared to
the original Protocol 3 (under the collective-attacks assumption) due to at
least two factors. Firstly, we can potentially use larger $\gamma$ values, as
previously mentioned (some of the points shown in the figure correspond to
values ranging up to $\gamma\approx 0.3$). Secondly, we find that for fixed
values of
$\gamma,n,w_{\mathrm{exp}},\delta_{\mathrm{tol}},\delta_{\mathrm{IID}}$, the
binomial-distribution bounds for this protocol (Eqs. (135) and (136)) are
typically several orders of magnitude better than their counterparts for
Protocol 3 (Eqs. (146) and (44)). Intuitively, this arises because in Protocol
3, the number of test rounds is itself a random variable, hence increasing the
variance in e.g. the number of rounds where $C_{j}=1$. Practically speaking,
this means Protocol 3 requires noticeably larger values of
$\delta_{\mathrm{tol}}$ and $\delta_{\mathrm{IID}}$ in order to achieve given
completeness and soundness parameters, hence reducing the keyrate by a
nontrivial amount.

However, we see that even with the optimistic assumptions that yield Theorem
5, the keyrate for the estimated experimental parameters we consider only
becomes positive at fairly large $n$. This indicates that substantial further
work is necessary in order to achieve a demonstration of positive finite-size
keyrates.

##  7 Conclusion and further work

In this work, we have performed a finite-size analysis for a protocol that
combines several of the most promising approaches towards improving keyrates
for DIQKD. Furthermore, we develop an algorithm that computes arbitrarily
tight lower bounds on the asymptotic keyrates for protocols of this form (i.e.
allowing for noisy preprocessing and random key measurements, but restricted
to one-way error correction), which applies to all 2-input 2-output scenarios.
This allows us to prove a new threshold of $9.33\%$ for noise tolerance in the
depolarizing-noise model, and we show (see Sec. 5.6) that for one-way
protocols, any further improvements on this threshold can only be fairly
small. Finally, we propose a modified protocol, based on a pre-shared key,
that overcomes the disadvantage of the sifting factor in random-key-
measurement protocols.

We remark that while the finite-size analysis shown here is for a protocol
based on the CHSH inequality, our algorithm for the asymptotic keyrates
applies more generally to 2-input 2-output scenarios. If some exploration with
this algorithm suggests that an improvement can be obtained by using an
inequality other than CHSH, then it would not be difficult to modify the
finite-size analysis for such an inequality, as was done in e.g. [BRC20] for
DIRE (essentially, it would just correspond to having a different bound
$r_{p}$).

However, our results show that for the NV-centre experiment in [HBD+15] and
the cold-atom experiment in [RBG+17], an impractically large sample size (for
those implementations) would still be needed in order to achieve a positive
finite-size keyrate, even if one makes the optimistic assumption of collective
attacks. A significant question that remains to be addressed is that of
photonic experiments [SMSC+15, GVW+15], which achieve lower CHSH values but
much larger sample sizes. Unfortunately, for photonic experiments the
heuristic results in [SGP+21] suggest that the random-key-measurement approach
is less useful in improving the keyrate, because the experimental parameters
that achieve maximal CHSH value also tend to result in higher error
probability (with respect to Bob’s outputs) for one of Alice’s measurements
than the other. Despite this challenge, we note that there is much freedom in
parameter optimization for photonic experiments [MSS20], and given the
algorithm we developed here for bounding the asymptotic keyrates, it is now
possible to analyze variants such as choosing different amounts of noisy
preprocessing for the two key-generating measurements. We aim to continue
studying this in future work.

As another extension of our work, our algorithm for bounding the asymptotic
DIQKD keyrates also applies to DIRE. Since the results it returns are
arbitrarily tight and easily incorporated into the EAT, this could be combined
with the finite-size analysis of [BRC20, LLR+19] to improve the results of
those works — the proof methods used there yield slightly suboptimal keyrates,
in that they either bound the min-entropy rather than the von Neumann entropy
[BRC20], or they only bound the entropy of one party’s outputs and are
restricted to the CHSH inequality [LLR+19]. Our algorithm would yield tight
bounds on the two-party von Neumann entropy for 2-input 2-output Bell
inequalities; furthermore, it allows the possibility of using the random-key-
measurement approach (by applying the pre-shared key proposal) to improve the
keyrates.

## Acknowledgements

We are very grateful to Peter Brown for detailed information on the finite-
size analysis in [BRC20, LLR+19], as well as Omar Fawzi and Frédéric Dupuis
for discussions on the entropy accumulation theorem. We also thank Koon Tong
Goh and Ignatius W. Primaatmaja for helpful discussion and feedback.

E. Y.-Z. T. and R. R. are supported by the Swiss National Science Foundation
(SNSF) via the National Center for Competence in Research for Quantum Science
and Technology (QSIT), the Air Force Office of Scientific Research (AFOSR) via
grant FA9550-19-1-0202, and the QuantERA project eDICT. P. S. is supported by
by the Swiss National Science Foundation (SNSF). C. C.-W. L is supported by
the National Research Foundation (NRF) Singapore, under its NRF Fellowship
programme (NRFF11-2019-0001) and Quantum Engineering Programme 1.0 (QEP-P2).

## Computational platform

Computations were performed using the MATLAB package YALMIP [Löf04] with the
solver MOSEK [MOS19]. Some of the calculations reported here were performed
using the Euler cluster at ETH Zürich.

## References

  * [AFRV19] Rotem Arnon-Friedman, Renato Renner and Thomas Vidick  “Simple and Tight Device-Independent Security Proofs”  In _SIAM Journal on Computing_ 48.1 Society for Industrial & Applied Mathematics (SIAM), 2019, pp. 181–225  DOI: 10.1137/18m1174726
  * [AGT06] Antonio Acín, Nicolas Gisin and Benjamin Toner  “Grothendieck’s constant and local models for noisy entangled quantum states”  In _Physical Review A_ 73 American Physical Society, 2006, pp. 062105  DOI: 10.1103/PhysRevA.73.062105
  * [BCK13] Jonathan Barrett, Roger Colbeck and Adrian Kent  “Memory Attacks on Device-Independent Quantum Cryptography”  In _Physical Review Letters_ 110 American Physical Society, 2013, pp. 010503  DOI: 10.1103/PhysRevLett.110.010503
  * [BFF21] Peter Brown, Hamza Fawzi and Omar Fawzi  “Computing conditional entropies for quantum correlations”  In _Nature Communications_ 12.1 Springer ScienceBusiness Media LLC, 2021  DOI: 10.1038/s41467-020-20018-1
  * [BHK05] Jonathan Barrett, Lucien Hardy and Adrian Kent  “No Signaling and Quantum Key Distribution”  In _Physical Review Letters_ 95 American Physical Society, 2005, pp. 010503  DOI: 10.1103/PhysRevLett.95.010503
  * [BRC20] P. J. Brown, S. Ragy and R. Colbeck  “A Framework for Quantum-Secure Device-Independent Randomness Expansion”  In _IEEE Transactions on Information Theory_ 66.5, 2020, pp. 2964–2987  DOI: 10.1109/TIT.2019.2960252
  * [BV04] Stephen Boyd and Lieven Vandenberghe  “Convex Optimization”  Cambridge University Press, 2004  DOI: 10.1017/CBO9780511804441
  * [CMA+13] B. G. Christensen, K. T. McCusker, J. B. Altepeter, B. Calkins, T. Gerrits, A. E. Lita, A. Miller, L. K. Shalm, Y. Zhang, S. W. Nam, N. Brunner, C. C. W. Lim, N. Gisin and P. G. Kwiat  “Detection-Loophole-Free Test of Quantum Nonlocality, and Applications”  In _Physical Review Letters_ 111 American Physical Society, 2013, pp. 130406  DOI: 10.1103/PhysRevLett.111.130406
  * [Col06] Roger Colbeck  “Quantum And Relativistic Protocols For Secure Multi-Party Computation”  In _arXiv:0911.3814v2 [quant-ph]_ , 2006  URL: https://arxiv.org/abs/0911.3814v2
  * [Col12] P. J. Coles  “Unification of different views of decoherence and discord”  In _Physical Review A_ 85.4, 2012, pp. 042103  DOI: 10.1103/PhysRevA.85.042103
  * [DF19] F. Dupuis and O. Fawzi  “Entropy accumulation with improved second-order term”  In _IEEE Transactions on Information Theory_ , 2019, pp. 1–1  DOI: 10.1109/TIT.2019.2929564
  * [DFR20] Frédéric Dupuis, Omar Fawzi and Renato Renner  “Entropy Accumulation”  In _Communications in Mathematical Physics_ 379.3 Springer ScienceBusiness Media LLC, 2020, pp. 867–913  DOI: 10.1007/s00220-020-03839-5
  * [DW05] Igor Devetak and Andreas Winter  “Distillation of secret key and entanglement from quantum states”  In _Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences_ 461.2053, 2005, pp. 207–235  DOI: 10.1098/rspa.2004.1372
  * [FW56] Marguerite Frank and Philip Wolfe  “An algorithm for quadratic programming”  In _Naval Research Logistics Quarterly_ 3.1-2 Wiley, 1956, pp. 95–110  DOI: 10.1002/nav.3800030109
  * [GMR+13] Marissa Giustina, Alexandra Mech, Sven Ramelow, Bernhard Wittmann, Johannes Kofler, Jörn Beyer, Adriana Lita, Brice Calkins, Thomas Gerrits, Sae Woo Nam, Rupert Ursin and Anton Zeilinger  “Bell violation using entangled photons without the fair-sampling assumption”  In _Nature_ 497.7448 Springer ScienceBusiness Media LLC, 2013, pp. 227–230  DOI: 10.1038/nature12012
  * [GVW+15] Marissa Giustina, Marijn A. M. Versteegh, Sören Wengerowsky, Johannes Handsteiner, Armin Hochrainer, Kevin Phelan, Fabian Steinlechner, Johannes Kofler, Jan-Åke Larsson, Carlos Abellán, Waldimar Amaya, Valerio Pruneri, Morgan W. Mitchell, Jörn Beyer, Thomas Gerrits, Adriana E. Lita, Lynden K. Shalm, Sae Woo Nam, Thomas Scheidl, Rupert Ursin, Bernhard Wittmann and Anton Zeilinger  “Significant-Loophole-Free Test of Bell’s Theorem with Entangled Photons”  In _Physical Review Letters_ 115 American Physical Society, 2015, pp. 250401  DOI: 10.1103/PhysRevLett.115.250401
  * [HBD+15] B. Hensen, H. Bernien, A. E. Dréau, A. Reiserer, N. Kalb, M. S. Blok, J. Ruitenberg, R. F. L. Vermeulen, R. N. Schouten, C. Abellán, W. Amaya, V. Pruneri, M. W. Mitchell, M. Markham, D. J. Twitchen, D. Elkouss, S. Wehner, T. H. Taminiau and R. Hanson  “Loophole-free Bell inequality violation using electron spins separated by 1.3 kilometres”  In _Nature_ 526, 2015, pp. 682–686  DOI: 10.1038/nature15759
  * [HQV+17] Flavien Hirsch, Marco Túlio Quintino, Tamás Vértesi, Miguel Navascués and Nicolas Brunner  “Better local hidden variable models for two-qubit Werner states and an upper bound on the Grothendieck constant $K_{G}(3)$”  In _Quantum_ 1 Verein zur Förderung des Open Access Publizierens in den Quantenwissenschaften, 2017, pp. 3  DOI: 10.22331/q-2017-04-25-3
  * [HST+20] M. Ho, P. Sekatski, E. Y.-Z. Tan, R. Renner, J.-D. Bancal and N. Sangouard  “Noisy Preprocessing Facilitates a Photonic Realization of Device-Independent Quantum Key Distribution”  In _Physical Review Letters_ 124.23 American Physical Society (APS), 2020  DOI: 10.1103/physrevlett.124.230502
  * [JMS20] Rahul Jain, Carl A. Miller and Yaoyun Shi  “Parallel Device-Independent Quantum Key Distribution”  In _IEEE Transactions on Information Theory_ 66.9 Institute of ElectricalElectronics Engineers (IEEE), 2020, pp. 5567–5584  DOI: 10.1109/tit.2020.2986740
  * [Kri79] J.L Krivine  “Constantes de Grothendieck et fonctions de type positif sur les sphères”  In _Advances in Mathematics_ 31.1 Elsevier BV, 1979, pp. 16–30  DOI: 10.1016/0001-8708(79)90017-3
  * [LLR+19] Wen-Zhao Liu, Ming-Han Li, Sammy Ragy, Si-Ran Zhao, Bing Bai, Yang Liu, Peter J. Brown, Jun Zhang, Roger Colbeck, Jingyun Fan, Qiang Zhang and Jian-Wei Pan  “Device-independent randomness expansion against quantum side information”  In _arXiv:1912.11159v1 [quant-ph]_ , 2019  URL: https://arxiv.org/abs/1912.11159v1
  * [Löf04] Johan Löfberg  “YALMIP : A toolbox for modeling and optimization in MATLAB”  In _Proceedings of the CACSD Conference_ , 2004  DOI: 10.1109/CACSD.2004.1393890
  * [LZL+18] Yang Liu, Qi Zhao, Ming-Han Li, Jian-Yu Guan, Yanbao Zhang, Bing Bai, Weijun Zhang, Wen-Zhao Liu, Cheng Wu, Xiao Yuan, Hao Li, W. J. Munro, Zhen Wang, Lixing You, Jun Zhang, Xiongfeng Ma, Jingyun Fan, Qiang Zhang and Jian-Wei Pan  “Device-independent quantum random-number generation”  In _Nature_ 562.7728 Springer ScienceBusiness Media LLC, 2018, pp. 548–551  DOI: 10.1038/s41586-018-0559-3
  * [MDR+19] G. Murta, S. B. Dam, J. Ribeiro, R. Hanson and S. Wehner  “Towards a realization of device-independent quantum key distribution”  In _Quantum Science and Technology_ 4.3 IOP Publishing, 2019, pp. 035011  DOI: 10.1088/2058-9565/ab2819
  * [MOS19] MOSEK ApS  “The MOSEK optimization toolbox for MATLAB manual. Version 8.1.”, 2019  URL: https://docs.mosek.com/8.1/toolbox/index.html
  * [MSS20] Alexey A. Melnikov, Pavel Sekatski and Nicolas Sangouard  “Setting Up Experimental Bell Tests with Reinforcement Learning”  In _Physical Review Letters_ 125 American Physical Society, 2020, pp. 160401  DOI: 10.1103/PhysRevLett.125.160401
  * [NSPS14] O. Nieto-Silleras, S. Pironio and J. Silman  “Using complete measurement statistics for optimal device-independent randomness evaluation”  In _New Journal of Physics_ 16.1 IOP Publishing, 2014, pp. 013035  DOI: 10.1088/1367-2630/16/1/013035
  * [PAB+09] Stefano Pironio, Antonio Acín, Nicolas Brunner, Nicolas Gisin, Serge Massar and Valerio Scarani  “Device-independent quantum key distribution secure against collective attacks”  In _New Journal of Physics_ 11.4, 2009, pp. 045021  DOI: 10.1088/1367-2630/11/4/045021
  * [PAM+10] S. Pironio, A. Acín, S. Massar, A. Boyer Giroday, D. N. Matsukevich, P. Maunz, S. Olmschenk, D. Hayes, L. Luo, T. A. Manning and C. Monroe  “Random numbers certified by Bell’s theorem”  In _Nature_ 464.7291 Springer ScienceBusiness Media LLC, 2010, pp. 1021–1024  DOI: 10.1038/nature09008
  * [PR14] Christopher Portmann and Renato Renner  “Cryptographic security of quantum key distribution”  In _arXiv:1409.3525v1 [quant-ph]_ , 2014  URL: https://arxiv.org/abs/1409.3525v1
  * [RBG+17] Wenjamin Rosenfeld, Daniel Burchardt, Robert Garthoff, Kai Redeker, Norbert Ortegel, Markus Rau and Harald Weinfurter  “Event-Ready Bell Test Using Entangled Atoms Simultaneously Closing Detection and Locality Loopholes”  In _Physical Review Letters_ 119.1 American Physical Society (APS), 2017  DOI: 10.1103/physrevlett.119.010402
  * [Ren05] Renato Renner  “Security of Quantum Key Distribution”, 2005  DOI: 10.3929/ethz-a-005115027
  * [RR12] J. M. Renes and R. Renner  “One-Shot Classical Data Compression With Quantum Side Information and the Distillation of Common Randomness or Secret Keys”  In _IEEE Transactions on Information Theory_ 58.3, 2012, pp. 1985–1991  DOI: 10.1109/TIT.2011.2177589
  * [RW05] Renato Renner and Stefan Wolf  “Simple and Tight Bounds for Information Reconciliation and Privacy Amplification”  In _Advances in Cryptology — ASIACRYPT 2005_ Springer, 2005, pp. 199–216  URL: https://link.springer.com/chapter/10.1007/11593447_11
  * [SBPC+09] Valerio Scarani, Helle Bechmann-Pasquinucci, Nicolas J. Cerf, Miloslav Dušek, Norbert Lütkenhaus and Momtchil Peev  “The security of practical quantum key distribution”  In _Reviews of Modern Physics_ 81 American Physical Society, 2009, pp. 1301–1350  DOI: 10.1103/RevModPhys.81.1301
  * [SBV+21] Pavel Sekatski, Jean-Daniel Bancal, Xavier Valcarce, Ernest Y.-Z. Tan, Renato Renner and Nicolas Sangouard  “Device-independent quantum key distribution from generalized CHSH inequalities”  In _Quantum_ 5 Verein zur Forderung des Open Access Publizierens in den Quantenwissenschaften, 2021, pp. 444  DOI: 10.22331/q-2021-04-26-444
  * [Sca12] Valerio Scarani  “The device-independent outlook on quantum physics (lecture notes on the power of Bell’s theorem)”  In _Acta Physica Slovaca_ 62, 2012, pp. 347–409  URL: http://www.physics.sk/aps/pubs/2012/aps-12-04/aps-12-04.pdf
  * [SGP+21] René Schwonnek, Koon Tong Goh, Ignatius W. Primaatmaja, Ernest Y.-Z. Tan, Ramona Wolf, Valerio Scarani and Charles C.-W. Lim  “Device-independent quantum key distribution with random key basis”  In _Nature Communications_ 12.1 Springer ScienceBusiness Media LLC, 2021  DOI: 10.1038/s41467-021-23147-3
  * [SLT+18] Lijiong Shen, Jianwei Lee, Le Phuc Thinh, Jean-Daniel Bancal, Alessandro Cerè, Antia Lamas-Linares, Adriana Lita, Thomas Gerrits, Sae Woo Nam, Valerio Scarani and Christian Kurtsiefer  “Randomness Extraction from Bell Violation with Continuous Parametric Down-Conversion”  In _Physical Review Letters_ 121 American Physical Society, 2018, pp. 150402  DOI: 10.1103/PhysRevLett.121.150402
  * [SMSC+15] Lynden K. Shalm, Evan Meyer-Scott, Bradley G. Christensen, Peter Bierhorst, Michael A. Wayne, Martin J. Stevens, Thomas Gerrits, Scott Glancy, Deny R. Hamel, Michael S. Allman, Kevin J. Coakley, Shellee D. Dyer, Carson Hodge, Adriana E. Lita, Varun B. Verma, Camilla Lambrocco, Edward Tortorici, Alan L. Migdall, Yanbao Zhang, Daniel R. Kumor, William H. Farr, Francesco Marsili, Matthew D. Shaw, Jeffrey A. Stern, Carlos Abellán, Waldimar Amaya, Valerio Pruneri, Thomas Jennewein, Morgan W. Mitchell, Paul G. Kwiat, Joshua C. Bienfang, Richard P. Mirin, Emanuel Knill and Sae Woo Nam  “Strong Loophole-Free Test of Local Realism”  In _Physical Review Letters_ 115 American Physical Society, 2015, pp. 250402  DOI: 10.1103/PhysRevLett.115.250402
  * [SR08] Valerio Scarani and Renato Renner  “Security Bounds for Quantum Cryptography with Finite Resources”  In _Theory of Quantum Computation, Communication, and Cryptography_ Berlin, Heidelberg: Springer Berlin Heidelberg, 2008, pp. 83–95  DOI: 10.1007/978-3-540-89304-2˙8
  * [TCR09] M. Tomamichel, R. Colbeck and R. Renner  “A Fully Quantum Asymptotic Equipartition Property”  In _IEEE Transactions on Information Theory_ 55.12, 2009, pp. 5840–5847  DOI: 10.1109/TIT.2009.2032797
  * [TL17] Marco Tomamichel and Anthony Leverrier  “A largely self-contained and complete security proof for quantum key distribution”  In _Quantum_ 1 Verein zur Förderung des Open Access Publizierens in den Quantenwissenschaften, 2017, pp. 14  DOI: 10.22331/q-2017-07-14-14
  * [TMMP+17] Marco Tomamichel, Jesus Martinez-Mateo, Christoph Pacher and David Elkouss  “Fundamental finite key limits for one-way information reconciliation in quantum key distribution”  In _Quantum Information Processing_ 16.11 Springer ScienceBusiness Media LLC, 2017  DOI: 10.1007/s11128-017-1709-5
  * [Tom16] Marco Tomamichel  “Quantum Information Processing with Finite Resources”  Springer International Publishing, 2016  DOI: 10.1007/978-3-319-21891-5
  * [TSG+19] Ernest Y.-Z. Tan, René Schwonnek, Koon Tong Goh, Ignatius William Primaatmaja and Charles C.-W. Lim  “Computing secure key rates for quantum key distribution with untrusted devices”  In _arXiv:1908.11372v2 [quant-ph]_ , 2019  URL: https://arxiv.org/abs/1908.11372v2
  * [VDT+13] Alexander Vitanov, Frédéric Dupuis, Marco Tomamichel and Renato Renner  “Chain Rules for Smooth Min- and Max-Entropies”  In _IEEE Transactions on Information Theory_ 59.5 Institute of ElectricalElectronics Engineers (IEEE), 2013, pp. 2603–2612  DOI: 10.1109/tit.2013.2238656
  * [VV14] Umesh Vazirani and Thomas Vidick  “Fully Device-Independent Quantum Key Distribution”  In _Physical Review Letters_ 113 American Physical Society, 2014, pp. 140501  DOI: 10.1103/PhysRevLett.113.140501
  * [WAP21] Erik Woodhead, Antonio Acín and Stefano Pironio  “Device-independent quantum key distribution with asymmetric CHSH inequalities”  In _Quantum_ 5 Verein zur Forderung des Open Access Publizierens in den Quantenwissenschaften, 2021, pp. 443  DOI: 10.22331/q-2021-04-26-443
  * [WLC18] A. Winick, N. Lütkenhaus and P. J. Coles  “Reliable numerical key rates for quantum key distribution”  In _Quantum_ 2, 2018, pp. 77  DOI: 10.22331/q-2018-07-26-77
  * [WTH+11] Severin Winkler, Marco Tomamichel, Stefan Hengl and Renato Renner  “Impossibility of Growing Quantum Bit Commitments”  In _Physical Review Letters_ 107 American Physical Society, 2011, pp. 090502  DOI: 10.1103/PhysRevLett.107.090502
  * [ZKB18] Yanbao Zhang, Emanuel Knill and Peter Bierhorst  “Certifying quantum randomness by probability estimation”  In _Physical Review A_ 98 American Physical Society, 2018, pp. 040304  DOI: 10.1103/PhysRevA.98.040304
  * [ZS13] A. M. Zubkov and A. A. Serov  “A Complete Proof of Universal Inequalities for the Distribution Function of the Binomial Law”  In _Theory of Probability & Its Applications_ 57.3 Society for Industrial & Applied Mathematics (SIAM), 2013, pp. 539–544  DOI: 10.1137/s0040585x97986138
  * [ZSB+20] Yanbao Zhang, Lynden K. Shalm, Joshua C. Bienfang, Martin J. Stevens, Michael D. Mazurek, Sae Woo Nam, Carlos Abellán, Waldimar Amaya, Morgan W. Mitchell, Honghao Fu, Carl A. Miller, Alan Mink and Emanuel Knill  “Experimental Low-Latency Device-Independent Quantum Randomness”  In _Physical Review Letters_ 124 American Physical Society, 2020, pp. 010505  DOI: 10.1103/PhysRevLett.124.010505

##  Appendix A Alternative map to describe noisy preprocessing

For Pauli measurements in the $X$-$Z$ plane, applying the Pauli $Y$ operator
to the state before the measurement causes the measurement outcome to flip.
Therefore, it can be seen that if one first subjects the state $\rho_{ABE}$ to
the isometry $V_{A}\otimes\mathbb{I}_{BE}$, where

$\displaystyle
V_{A}\left|\psi\right>_{A}=\sqrt{1-p}\left|\psi\right>_{A}\left|0\right>_{T}+\sqrt{p}\,Y\left|\psi\right>_{A}\left|1\right>_{T},$
(138)

then measures $A_{x}$ and directly stores the outcome in $\hat{A}_{x}$, this
produces exactly the same reduced state on the registers $\hat{A}_{x}E$ as the
noisy-preprocessing procedure. Then since
$\left|\hat{\rho}\right>_{ABET}\coloneqq(V_{A}\otimes\mathbb{I}_{BE})\left|\rho\right>_{ABE}$
is a pure state, by the same reasoning as before we have

$\displaystyle
H(\hat{A}_{x}|E)=D(\hat{\rho}_{ABT}\|\widetilde{\mathcal{Z}}_{x}(\hat{\rho}_{ABT}))=D(\widetilde{\mathcal{G}}({\rho}_{AB})\|\widetilde{\mathcal{Z}}_{x}(\widetilde{\mathcal{G}}({\rho}_{AB}))),$
(139)

where

$\displaystyle\widetilde{\mathcal{G}}(\sigma_{AB})$
$\displaystyle\coloneqq(V_{A}\otimes\mathbb{I}_{B})\sigma_{AB}(V_{A}\otimes\mathbb{I}_{B})^{\dagger},$
(140) $\displaystyle\widetilde{\mathcal{Z}}_{x}(\sigma_{ABT})$
$\displaystyle\coloneqq\sum_{a}(P_{a|x}\otimes\mathbb{I}_{BT})\sigma_{ABT}(P_{a|x}\otimes\mathbb{I}_{BT}).$
(141)

This description of noisy preprocessing appears to more specifically exploit
the reduction to Pauli measurements in the 2-input 2-output scenario, and
hence may be less general.

##  Appendix B Alternative continuity bound

In principle we could use the following approach: we first note that an
intermediate step in the derivation of (139) is the relation [Col12]

$\displaystyle
H(\hat{A}_{x}|E)=H(\widetilde{\mathcal{Z}}_{x}(\hat{\rho}_{ABT}))-H(\hat{\rho}_{ABT}),$
(142)

and hence bounding how much $H(\hat{A}_{1}|E)$ changes in terms of the
measurement angle is equivalent to bounding how much
$H(\widetilde{\mathcal{Z}}_{1}(\hat{\rho}_{ABT}))$ changes (since the
$H(\hat{\rho}_{ABT})$ term is independent of the measurement). We introduce
the qubit channel

$\displaystyle\bar{\mathcal{Z}}^{\theta}(\sigma)\coloneqq\sum_{a}P_{a}(\theta)\sigma
P_{a}(\theta),$ (143)

where the projectors $P_{a}(\theta)$ describe a Pauli measurement in the
$X$-$Z$ plane along angle $\theta$, in which case
$\widetilde{\mathcal{Z}}_{1}$ (for measurement angle ${\theta_{A}}$) is
basically the channel $\bar{\mathcal{Z}}^{{\theta_{A}}}$ applied only to the
$A$ system. By the properties of the diamond norm, we have

$\displaystyle\left\lVert\bar{\mathcal{Z}}^{{\theta_{A}}}_{A}(\hat{\rho}_{ABT})-\bar{\mathcal{Z}}^{{\theta_{A}}+\delta}_{A}(\hat{\rho}_{ABT})\right\rVert_{1}\leq\left\lVert\bar{\mathcal{Z}}^{{\theta_{A}}}-\bar{\mathcal{Z}}^{{\theta_{A}}+\delta}\right\rVert_{\diamond}\leq\dim(A)\left\lVert
J(\bar{\mathcal{Z}}^{{\theta_{A}}})-J(\bar{\mathcal{Z}}^{{\theta_{A}}+\delta})\right\rVert_{1},$
(144)

where $J(\mathcal{E})$ denotes the (normalized) Choi state of the channel
$\mathcal{E}$. In this case we have $\dim(A)=2$, and the trace distance
between the Choi states can be computed in closed form (exploiting the fact
that two of the Bell states are simultaneous eigenstates of the two Choi
states). We could then apply the Fannes-Audenaert continuity bound to bound
how much $H(\widetilde{\mathcal{Z}}_{1}(\hat{\rho}_{ABT}))$ (and hence
$H(\hat{A}_{1}|E)$) changes.343434It was also possible to instead bound the
change (in terms of trace distance) of the state on registers $\hat{A}_{x}E$
directly, using a slightly different channel, but it turns out to yield a
slightly worse bound. Unfortunately, the Fannes-Audenaert bound scales poorly
at small values of trace distance, and hence this approach yields a much worse
continuity bound than (103) (in fact, the resulting bound has infinite
derivative with respect to $\delta$ at $\delta=0$).

##  Appendix C Proof of Theorem 4

We observe that the completeness proof from Sec. 4.1 directly applies, since
we have not changed the honest behaviour. As for the soundness proof, we
follow the argument in Sec. 4.2 up until Eq. (52), upon which we again require
a bound on the first term in that equation. To do so, we note that since the
device behaviour is identical in every round, the true CHSH winning
probability for the devices can be denoted as a constant value
$w_{\mathrm{true}}$ (though this value is not directly known to Alice and
Bob). We can thus define the following exhaustive possibilities for the device
behaviour (again, $\rho$ is the state at the end of Protocol $1^{\prime}$):

  1. Case 1:

For the state $\rho$,
$\Pr\\!\left[\Omega_{\mathrm{g}}\land\Omega_{\mathrm{h}}\land\Omega^{\prime}_{\mathrm{PE}}\right]\leq\epsilon_{s}^{2}$.

  2. Case 2:

$w_{\mathrm{true}}<w_{\mathrm{exp}}-\delta_{\mathrm{tol}}-\delta_{\mathrm{IID}}$.

  3. Case 3:

Neither of the above are true.

In case 1, the first term of Eq. (52) is immediately bounded by

$\displaystyle\Pr\\!\left[\Omega_{\mathrm{g}}\land\Omega_{\mathrm{h}}\land\Omega^{\prime}_{\mathrm{PE}}\right]\leq\epsilon_{s}^{2}.$
(145)

In case 2, we observe that in each round, the probability of the CHSH game
being played and the devices winning is $w_{\mathrm{true}}\gamma$. Therefore,
we have

$\displaystyle\Pr\\!\left[\operatorname{freq}_{\mathbf{c}^{\prime}}(1)\geq(w_{\mathrm{exp}}-\delta_{\mathrm{tol}})\gamma\right]$
$\displaystyle=\Pr\\!\left[\operatorname{freq}_{\mathbf{c}^{\prime}}(\neg
1)<1-(w_{\mathrm{exp}}-\delta_{\mathrm{tol}})\gamma\right]$
$\displaystyle\leq\Pr\\!\left[\operatorname{freq}_{\mathbf{c}^{\prime}}(\neg
1)n\leq\left\lfloor(1-(w_{\mathrm{exp}}-\delta_{\mathrm{tol}})\gamma)n\right\rfloor\right]$
$\displaystyle=B_{n,1-w_{\mathrm{true}}\gamma}(\left\lfloor(1-(w_{\mathrm{exp}}-\delta_{\mathrm{tol}})\gamma)n\right\rfloor)$
$\displaystyle\leq\epsilon_{\mathrm{IID}},$ (146)

where the last inequality follows from the fact that we have
$1-w_{\mathrm{true}}\gamma>1-(w_{\mathrm{exp}}-\delta_{\mathrm{tol}}-\delta_{\mathrm{IID}})\gamma$,
and $B_{n,p}(k)\leq B_{n,p^{\prime}}(k)$ for $p\geq p^{\prime}$. (Again, one
could obtain a simpler expression using the multiplicative Chernoff bound,

$\displaystyle\Pr\\!\left[\operatorname{freq}_{\mathbf{c}^{\prime}}(1)\geq(w_{\mathrm{exp}}-\delta_{\mathrm{tol}})\gamma\right]\leq
e^{-\frac{n\gamma\delta_{\mathrm{IID}}^{2}}{3\left(w_{\mathrm{exp}}-\delta_{\mathrm{tol}}-\delta_{\mathrm{IID}}\right)}},$
(147)

but this gives significantly poorer results.) Overall, this allows us to bound
the first term of Eq. (52) in this case by

$\displaystyle\Pr\\!\left[\Omega_{\mathrm{g}}\land\Omega_{\mathrm{h}}\land\Omega^{\prime}_{\mathrm{PE}}\right]\leq\Pr\\!\left[\Omega^{\prime}_{\mathrm{PE}}\right]\leq\Pr\\!\left[\operatorname{freq}_{\mathbf{c}^{\prime}}(1)\geq(w_{\mathrm{exp}}-\delta_{\mathrm{tol}})\gamma\right]\leq\epsilon_{\mathrm{IID}}.$
(148)

As for case 3, we can directly apply the AEP (Corollary 4.10 of [DFR20]) to
obtain the following bound in place of Theorem 2, with the slight difference
that we have not conditioned on $\Omega^{\prime}_{\mathrm{PE}}$ yet:

$\displaystyle
H_{\mathrm{min}}^{\epsilon_{s}}(\mathbf{A}|\mathbf{X}\mathbf{Y}E)_{\rho}>ng(w_{\mathrm{exp}}-\delta_{\mathrm{tol}}-\delta_{\mathrm{IID}})-\sqrt{n}\,(2\log
5)\sqrt{\log\frac{2}{\epsilon_{s}^{2}}}.$ (149)

The remainder of the analysis proceeds very similarly to Sec. 4.2.
Specifically, since we have
$\Pr\\!\left[\Omega_{\mathrm{g}}\land\Omega_{\mathrm{h}}\land\Omega^{\prime}_{\mathrm{PE}}\right]\geq\epsilon_{s}^{2}$
in this case, we can conclude

$\displaystyle
H_{\mathrm{min}}^{\epsilon_{s}}(\mathbf{A}|\mathbf{X}\mathbf{Y}\mathbf{L}E)_{\rho_{\land\Omega_{\mathrm{g}}\land\Omega_{\mathrm{h}}\land\Omega^{\prime}_{\mathrm{PE}}}}$
$\displaystyle\geq
H_{\mathrm{min}}^{\epsilon_{s}}(\mathbf{A}|\mathbf{X}\mathbf{Y}\mathbf{L}E)_{\rho}$
$\displaystyle\geq
H_{\mathrm{min}}^{\epsilon_{s}}(\mathbf{A}|\mathbf{X}\mathbf{Y}E)_{\rho}-\mathrm{EC}_{\mathrm{max}}-\left\lceil\log\left(\frac{1}{\epsilon_{\mathrm{h}}}\right)\right\rceil.$
(150)

Putting this together with Eq. (149), we see that as long as we choose
$\ell_{\mathrm{key}}$ satisfying Eq. (132), we will have

$\displaystyle\frac{1}{2}\left(H_{\mathrm{min}}^{\epsilon_{s}}(\mathbf{A}|\mathbf{X}\mathbf{Y}\mathbf{L}E)_{\rho_{\land\Omega_{\mathrm{g}}\land\Omega_{\mathrm{h}}\land\Omega^{\prime}_{\mathrm{PE}}}}-\ell_{\mathrm{key}}+2\right)\geq\log\frac{1}{\epsilon_{\mathrm{PA}}}.$
(151)

Again noting that
$\Pr\\!\left[\Omega_{\mathrm{g}}\land\Omega_{\mathrm{h}}\land\Omega^{\prime}_{\mathrm{PE}}\right]\geq\epsilon_{s}^{2}$
in this case, the Leftover Hashing Lemma then implies the first term of Eq.
(52) is bounded by

$\displaystyle\frac{1}{2}\left\lVert\mathcal{M}_{\mathrm{PA}}(\rho_{\land\Omega_{\mathrm{g}}\land\Omega_{\mathrm{h}}\land\Omega^{\prime}_{\mathrm{PE}}})_{K_{A}E^{\prime}}-\mathbb{U}_{K_{A}}\otimes\mathcal{M}_{\mathrm{PA}}(\rho_{\land\Omega_{\mathrm{g}}\land\Omega_{\mathrm{h}}\land\Omega^{\prime}_{\mathrm{PE}}})_{E^{\prime}}\right\rVert_{1}$
$\displaystyle\leq{}$ $\displaystyle
2^{-\frac{1}{2}\left(H_{\mathrm{min}}^{\epsilon_{s}}(\mathbf{A}|\mathbf{X}\mathbf{Y}\mathbf{L}E)_{\rho_{\land\Omega_{\mathrm{g}}\land\Omega_{\mathrm{h}}\land\Omega^{\prime}_{\mathrm{PE}}}}-\ell_{\mathrm{key}}+2\right)}+2\epsilon_{s}$
$\displaystyle\leq{}$ $\displaystyle\epsilon_{\mathrm{PA}}+2\epsilon_{s}.$
(152)

Therefore, we finally conclude that under the collective-attacks assumption,
the secrecy condition is satisfied by choosing

$\displaystyle\epsilon^{\mathrm{sec}}_{\mathrm{QKD}}=\max\\{\epsilon_{s}^{2},\epsilon_{\mathrm{IID}},\epsilon_{\mathrm{PA}}+2\epsilon_{s}\\}+\epsilon_{\mathrm{h}}=\max\\{\epsilon_{\mathrm{IID}},\epsilon_{\mathrm{PA}}+2\epsilon_{s}\\}+\epsilon_{\mathrm{h}}.$
(153)

As before, the protocol is $\epsilon_{\mathrm{h}}$-correct, so we conclude
that it is
$(\max\\{\epsilon_{\mathrm{IID}},\epsilon_{\mathrm{PA}}+2\epsilon_{s}\\}+2\epsilon_{\mathrm{h}})$-sound
when performed with $\ell_{\mathrm{key}}$ satisfying Eq. (132).

##  Appendix D Proof of Theorem 5

To prove this theorem, we first observe that the claimed completeness bound
holds because

$\displaystyle\Pr\\!\left[\operatorname{freq}_{\mathbf{c}_{t}}(1)<w_{\mathrm{exp}}-\delta_{\mathrm{tol}}\right]_{\mathrm{hon}}$
$\displaystyle\leq\Pr\\!\left[\operatorname{freq}_{\mathbf{c}_{t}}(1)\gamma
n\leq\left\lfloor(w_{\mathrm{exp}}-\delta_{\mathrm{tol}})\gamma
n\right\rfloor\right]_{\mathrm{hon}}$ $\displaystyle=B_{\gamma
n,w_{\mathrm{exp}}}(\left\lfloor(w_{\mathrm{exp}}-\delta_{\mathrm{tol}})\gamma
n\right\rfloor),$ (154)

and hence by applying the union bound as before, we see that the probability
of the honest protocol aborting is at most
$\epsilon^{\mathrm{com}}_{\mathrm{EC}}+\epsilon^{\mathrm{com}}_{\mathrm{PE}}$.

As for soundness, we follow the argument in Sec. 4 up until Eq. (51), though
it is no longer necessary to introduce the virtual parameter estimation, since
Bob has access to the exact values of $\mathbf{A}_{t}$. We also need to
slightly modify the event definitions (and it is no longer necessary to
consider the event $\Omega^{\prime}_{\mathrm{PE}}$):

$\Omega_{\mathrm{g}}$: $\mathbf{A}_{g}=\tilde{\mathbf{A}}_{g}$

$\Omega_{\mathrm{h}}$:
$\operatorname{hash}(\mathbf{A}_{g})=\operatorname{hash}(\tilde{\mathbf{A}}_{g})$

$\Omega_{\mathrm{PE}}$: $\operatorname{freq}_{\mathbf{c}_{t}}(1)\geq
w_{\mathrm{exp}}-\delta_{\mathrm{tol}}$

Again, the accept condition for this protocol can be stated as the event
$\Omega_{\mathrm{h}}\land\Omega_{\mathrm{PE}}$. For this protocol, we can
prove a bound of the form (51) directly, without splitting it into the terms
in Eq. (52). To do so, denote the state after the parameter-estimation step in
Protocol 4 as $\rho$, and consider the following exhaustive possibilities:

  1. Case 1:

For the state $\rho$,
$\Pr\\!\left[\Omega_{\mathrm{h}}\land\Omega_{\mathrm{PE}}\right]\leq\epsilon_{s}^{2}$.

  2. Case 2:

$w_{\mathrm{true}}<w_{\mathrm{exp}}-\delta_{\mathrm{tol}}-\delta_{\mathrm{IID}}$.

  3. Case 3:

Neither of the above are true.

In case 1, the left-hand-side of Eq. (51) is immediately bounded by
$\epsilon_{s}^{2}$. In case 2, we observe that in each of the $\gamma n$ test
rounds (note that now we focus only on the test rounds, instead of the full
output strings as we did in the previous proofs), the probability of winning
the CHSH game is $w_{\mathrm{true}}$. Therefore, we have

$\displaystyle\Pr\\!\left[\operatorname{freq}_{\mathbf{c}_{t}}(1)\geq
w_{\mathrm{exp}}-\delta_{\mathrm{tol}}\right]$
$\displaystyle=\Pr\\!\left[\operatorname{freq}_{\mathbf{c}_{t}}(0)<1-w_{\mathrm{exp}}+\delta_{\mathrm{tol}}\right]$
$\displaystyle=\Pr\\!\left[\operatorname{freq}_{\mathbf{c}_{t}}(0)\gamma
n<(1-w_{\mathrm{exp}}+\delta_{\mathrm{tol}})\gamma n\right]$
$\displaystyle\leq\Pr\\!\left[\operatorname{freq}_{\mathbf{c}_{t}}(0)\gamma
n\leq\left\lfloor(1-w_{\mathrm{exp}}+\delta_{\mathrm{tol}})\gamma
n\right\rfloor\right]$ $\displaystyle=B_{\gamma
n,1-w_{\mathrm{true}}}(\left\lfloor(1-w_{\mathrm{exp}}+\delta_{\mathrm{tol}})\gamma
n\right\rfloor)$ $\displaystyle\leq\epsilon_{\mathrm{IID}},$ (155)

which allows us to bound the left-hand-side of Eq. (51) in this case by

$\displaystyle\Pr\\!\left[\Omega_{\mathrm{h}}\land\Omega_{\mathrm{PE}}\right]\leq\Pr\\!\left[\Omega_{\mathrm{PE}}\right]=\Pr\\!\left[\operatorname{freq}_{\mathbf{c}_{t}}(1)\geq
w_{\mathrm{exp}}-\delta_{\mathrm{tol}}\right]\leq\epsilon_{\mathrm{IID}}.$
(156)

Finally, for case 3, we note that since Eve’s quantum side-information $E$ is
genuinely in (IID) tensor-product form under the collective-attacks
assumption, we can denote the subsets corresponding to test and generation
rounds as $\mathbf{E}_{t}$ and $\mathbf{E}_{g}$ respectively. The AEP in
[DFR20] then gives

$\displaystyle
H_{\mathrm{min}}^{\epsilon_{s}}(\mathbf{A}_{g}|\mathbf{X}_{g}\mathbf{Y}_{g}\mathbf{E}_{g})_{\rho}>(1-\gamma)nr_{p}(w_{\mathrm{exp}}-\delta_{\mathrm{tol}}-\delta_{\mathrm{IID}})-\sqrt{(1-\gamma)n}\,(2\log
5)\sqrt{\log\frac{2}{\epsilon_{s}^{2}}},$ (157)

and we proceed similarly: since we have
$\Pr\\!\left[\Omega_{\mathrm{h}}\land\Omega_{\mathrm{PE}}\right]\geq\epsilon_{s}^{2}$
in case 3, we can conclude

$\displaystyle
H_{\mathrm{min}}^{\epsilon_{s}}(\mathbf{A}_{g}|\mathbf{A}_{t}\mathbf{X}\mathbf{Y}\mathbf{L}{E})_{\rho_{\land\Omega_{\mathrm{h}}\land\Omega_{\mathrm{PE}}}}$
$\displaystyle\geq
H_{\mathrm{min}}^{\epsilon_{s}}(\mathbf{A}_{g}|\mathbf{A}_{t}\mathbf{X}\mathbf{Y}\mathbf{L}{E})_{\rho}$
$\displaystyle\geq
H_{\mathrm{min}}^{\epsilon_{s}}(\mathbf{A}_{g}|\mathbf{A}_{t}\mathbf{X}\mathbf{Y}{E})_{\rho}-\mathrm{EC}_{\mathrm{max}}-\left\lceil\log\left(\frac{1}{\epsilon_{\mathrm{h}}}\right)\right\rceil$
$\displaystyle=H_{\mathrm{min}}^{\epsilon_{s}}(\mathbf{A}_{g}|\mathbf{X}_{g}\mathbf{Y}_{g}\mathbf{E}_{g})_{\rho}-\mathrm{EC}_{\mathrm{max}}-\left\lceil\log\left(\frac{1}{\epsilon_{\mathrm{h}}}\right)\right\rceil,$
(158)

where the last line holds because the test rounds are independent of the
generation rounds. Hence as long as we choose $\ell_{\mathrm{key}}$ satisfying
Eq. (137), we will have

$\displaystyle\frac{1}{2}\left(H_{\mathrm{min}}^{\epsilon_{s}}(\mathbf{A}_{g}|\mathbf{A}_{t}\mathbf{X}\mathbf{Y}\mathbf{L}{E})_{\rho_{\land\Omega_{\mathrm{h}}\land\Omega_{\mathrm{PE}}}}-\ell_{\mathrm{key}}+2\right)\geq\log\frac{1}{\epsilon_{\mathrm{PA}}}.$
(159)

Again noting that
$\Pr\\!\left[\Omega_{\mathrm{h}}\land\Omega_{\mathrm{PE}}\right]\geq\epsilon_{s}^{2}$
in this case, the Leftover Hashing Lemma then implies

$\displaystyle\frac{1}{2}\left\lVert\mathcal{M}_{\mathrm{PA}}(\rho_{\land\Omega_{\mathrm{h}}\land\Omega_{\mathrm{PE}}})_{K_{A}E^{\prime}}-\mathbb{U}_{K_{A}}\otimes\mathcal{M}_{\mathrm{PA}}(\rho_{\land\Omega_{\mathrm{h}}\land\Omega_{\mathrm{PE}}})_{E^{\prime}}\right\rVert_{1}$
$\displaystyle\leq{}$ $\displaystyle
2^{-\frac{1}{2}\left(H_{\mathrm{min}}^{\epsilon_{s}}(\mathbf{A}_{g}|\mathbf{A}_{t}\mathbf{X}\mathbf{Y}\mathbf{L}{E})_{\rho_{\land\Omega_{\mathrm{h}}\land\Omega_{\mathrm{PE}}}}-\ell_{\mathrm{key}}+2\right)}+2\epsilon_{s}$
$\displaystyle\leq{}$ $\displaystyle\epsilon_{\mathrm{PA}}+2\epsilon_{s}.$
(160)

Therefore, we finally conclude that under the collective-attacks assumption,
the secrecy condition is satisfied by choosing

$\displaystyle\epsilon^{\mathrm{sec}}_{\mathrm{QKD}}=\max\\{\epsilon_{s}^{2},\epsilon_{\mathrm{IID}},\epsilon_{\mathrm{PA}}+2\epsilon_{s}\\}=\max\\{\epsilon_{\mathrm{IID}},\epsilon_{\mathrm{PA}}+2\epsilon_{s}\\}.$
(161)

As before, the protocol is $\epsilon_{\mathrm{h}}$-correct, so we conclude
that it is
$(\max\\{\epsilon_{\mathrm{IID}},\epsilon_{\mathrm{PA}}+2\epsilon_{s}\\}+\epsilon_{\mathrm{h}})$-sound
when performed with $\ell_{\mathrm{key}}$ satisfying Eq. (137).