# Incorporating Zero-Probability Constraints to Device-Independent Randomness
Expansion

Chun-Yu Chen  Institute of Information Science, Academia Sinica, Taipei 115,
Taiwan  Department of Physics and Center for Quantum Frontiers of Research &
Technology (QFort), National Cheng Kung University, Tainan 701, Taiwan  Kai-
Siang Chen  Department of Physics and Center for Quantum Frontiers of Research
& Technology (QFort), National Cheng Kung University, Tainan 701, Taiwan  Kai-
Min Chung  Institute of Information Science, Academia Sinica, Taipei 115,
Taiwan  Min-Hsiu Hsieh  Hon Hai (Foxconn) Research Institute, Taipei, Taiwan
Yeong-Cherng Liang<EMAIL_ADDRESS>Department of Physics and Center
for Quantum Frontiers of Research & Technology (QFort), National Cheng Kung
University, Tainan 701, Taiwan  Physics Division, National Center for
Theoretical Sciences, Taipei 106, Taiwan  Gelo Noel M. Tabia  gelonoel-
<EMAIL_ADDRESS>Department of Physics and Center for Quantum Frontiers of
Research & Technology (QFort), National Cheng Kung University, Tainan 701,
Taiwan  Physics Division, National Center for Theoretical Sciences, Taipei
106, Taiwan

###### Abstract

One of the distinguishing features of quantum theory is that its measurement
outcomes are usually unpredictable or, equivalently, random. Moreover, this
randomness is certifiable with minimal assumptions in the so-called device-
independent (DI) paradigm, where a device’s behavior does not need to be
presupposed but can be verified through the statistics it produces. In this
work, we explore various forms of randomness that are certifiable in this
setting, where two users can perform two binary-outcome measurements on their
shared entangled state. In this case, even though the Clauser-Horne-Shimony-
Holt (CHSH) Bell-inequality violation is a pre-requisite for the generation of
DI certifiable randomness, the CHSH value alone does not generally give a
tight bound on the certifiable randomness. Here, we determine the certifiable
randomness when zero-probability constraints are incorporated into the task of
DI randomness expansion for the standard local and global randomness and the
so-called ”blind” randomness. Asymptotically, we observe consistent
improvements in the amount of DI certifiable randomness (of all kinds) as we
increase the number zero constraints for a wide range of given CHSH Bell
violations. However, if we further optimize over the allowed CHSH values, then
benefits of these additional constraints over the standard CHSH-based protocol
are only found in the case of global and blind randomness. In contrast, in the
regimes of finite data, these zero constraints only give a slight improvement
in the local randomness rate when compared with all existing protocols.

##  I Introduction

In quantum cryptography [1], the device-independent [2, 3] (DI) paradigm
offers a very attractive alternative to conventional schemes as it requires
only a minimal set of assumptions for its security analysis [4, 5, 6, 7].
Indeed, as was first made explicit by Ekert [4], the violation of a Bell
inequality [8] implies that that measurement outcome could not have existed
before the measurement, thus leaving nothing for the adversary to eavesdrop.
For example, in the simplest two-party Bell scenario, the family of Clauser-
Horne-Shimony-Holt (CHSH) Bell inequalities [9] completely characterize [10]
the set of correlations admitting a local-hidden-variable model. Thus, it is
natural that the CHSH parameter plays a crucial role in many DI cryptographic
tasks including quantum key distribution [4, 11, 12, 13, 14, 15, 16] and
random number generation [17, 13, 18, 19].

Regarding single-party (local) randomness, a maximally CHSH-violating
correlation yields up to 1 bit of maximum randomness [17]. However, for two-
party (global) randomness, other Bell inequalities [20, 21, 22] have been
found to give better randomness generation rate. Beyond these randomness
forms, Miller and Shi [23] introduced the concept of “blind”
randomness,111Though in [23], the authors used the term “local” randomness, it
may cause confusion since “local” randomness was already used to indicate the
randomness from a single party. As a result, we follow the term “blind”
randomness used in [24]. signifying the unpredictability of one party’s
outcome even when given the other party’s input and output. Clearly, this
gives a strengthened version of local randomness. At the same time, this less-
explored notion of randomness allows the design of cryptographic protocols for
mistrustful collaborations, enabling parties to work toward a common objective
without relying on mutual trust, for instance, in the certified deletion task
[25]. To this end, the work by Metger et al. [24] (see also [26, Figure 2])
demonstrated that the (maximal) CHSH violation alone can only certify about
0.6-bit of blind randomness in the asymptotic limit.

Several questions naturally follow. For example, could we improve the
certifiable randomness for each type if we stay within the simplest Bell
scenario? For global randomness, the maximal amount of 2-bit is known [22] to
be certifiable using a family of self-testing [5, 27] quantum correlations,
but not from the CHSH violation alone. After all, these self-testing
correlations do not maximally violate the CHSH Bell inequality but rather a
different family of Bell inequalities [22]. Indeed, more randomness can
generally be certified from the same data if we use the full correlation [28,
29] or consider several Bell estimators simultaneously [30]. Alternatively,
one can also hope to gain a better certification by imposing further
constraints in addition to the CHSH Bell value. The intuition here is that if
the additional constraints do not, a priori, exclude a self-testing
correlation, then it may improve the certifiable randomness by restricting the
possible eavesdropping strategies of the adversaries.

Coming back to Bell experiments, we remind that no-signaling conditions [31,
32] have to be enforced for any meaningful DI randomness generation.
Mathematically, these conditions define a set of correlations called the “no-
signaling” ($\mathcal{NS}$) polytope. Interestingly, even though
$\mathcal{NS}$ differs from the quantum ($\mathcal{Q}$) set of correlations,
they share [33] some nontrivial, common boundaries, which can be characterized
by the number of zeros appearing in the correlation vector and their relative
positions [34, Table V]. An example of such a correlation is the one
exhibiting the well-known Hardy paradox [35]. In general, the correlation that
violates the CHSH Bell-inequality maximally within each class is even known to
exhibit robust self-testing [34, Table VI]. Given that certain quantum
correlations lying on these common boundaries are [36] useful for the task of
randomness amplification [37], one may also wonder whether they can similarly
provide an advantage for the task of DI randomness generation.

In this work, we study (1) the amount of DI randomness that can be extracted
for a given CHSH value when the various zero-probability constraints of [34]
are incorporated, and (2) the amount of DI randomness extractable when we
employ the CHSH-maximizing quantum strategy within each class. For the former,
we evaluate randomness in the asymptotic limit as von Neumann entropy through
the Brown-Fawzi-Fawzi (BFF21) method [38] whereas for the latter, we work in
finite regimes as smooth min-entropy by applying the generalized entropy
accumulation theorem (GEAT) [24]. The dual variables in the semidefinite
program (SDP) for the asymptotic rate computation with the BFF21 method can be
used to construct the min-tradeoff function, a necessary component in any
approach that involves entropy accumulation. In standard DI quantum key
distribution or a DI randomness expansion protocol, testing rounds are used to
estimate the Bell value and this serves as the spot-checking method embedded
in the protocol. Here, we follow [19] to convert the min-tradeoff function
into a “crossover” min-tradeoff function [39] that accounts for entropy that
can be accumulated from both testing rounds and non-testing rounds. By
meticulously evaluating the required quantities of the min-tradeoff function,
we can establish bounds on the finite rate for various types of randomness.

##  II Preliminaries

###  II.1 Security definition

Two parameters are relevant for describing the security of a randomness
expansion protocol: soundness and completeness.

A protocol is said to be $\epsilon_{\mathrm{s}}$-sound if the final state
$\rho_{KE}=\sum_{k\in\mathcal{K}}|k\rangle\langle k|\otimes\rho^{k}_{E}$ of
the output system $K$ and the adversary’s side information $E$ (including both
quantum and classical parts) follows

$\Pr[\mathrm{NonAbort}]\frac{1}{2}\|\rho_{KE|\mathrm{NonAbort}}-\mu_{K}\otimes\rho_{E}\|_{1}\leq\epsilon_{\mathrm{s}},$
(1)

where $\Pr[\mathrm{NonAbort}]$ is the probability of the protocol is not
aborted after checking the termination criteria, $\rho_{KE|\mathrm{NonAbort}}$
is the normalized state conditioned on the non-aborting event,
$\mu_{K}=\frac{1}{|\mathcal{K}|}\mathds{1}$ is the maximally mixed state on
$\mathcal{H}_{K}$, and $\|\sigma\|_{1}=\Tr\sqrt{\sigma^{\dagger}\sigma}$ is
the Schatten 1-norm.

A protocol is said to have $\epsilon_{\mathrm{c}}$-complete if, in the honest
implementation, the aborting probability is bounded

$\Pr[\mathrm{Abort}|\mathrm{Honest}]\leq\epsilon_{\mathrm{c}}.$ (2)

###  II.2 Entropic quantities

We define the different entropic quantities that are useful to quantify the
amount of randomness extracted from the source $K$ against given side
information $E$.

The first entropic quantity is conditional von Neumann entropy, which
describes the averaged extractable randomness or in other words the
extractable randomness in the asymptotic limit. For a bipartite state
$\rho_{KE}$ of the source $K$ and side information $E$ on
$\mathcal{H}_{K}\otimes\mathcal{H}_{E}$, the conditional von Neumann entropy
$H(K|E)_{\rho}$ on $\rho_{KE}$ is defined as

$H(K|E)_{\rho}:=H(\rho_{KE})-H(\rho_{E}).$

The other entropic quantity we consider in our work is the smooth min-entropy
$H_{\mathrm{min}}^{\epsilon}(K|E)_{\rho}$. Before defining this useful
quantity, let’s first introduce another meaningful quantity, min-entropy
$H_{\mathrm{min}}(K|E)_{\rho}$, that quantifies the extractable randomness in
the worst case.

$H_{\mathrm{min}}(K|E)_{\rho}:=\sup_{\sigma_{E}}\sup\\{\lambda\in\mathbb{R}\mid\rho_{KE}\leq
e^{-\lambda}\mathds{1}_{K}\otimes\sigma_{E}\\},$

for any sub-normalized state $\rho_{KE}\preceq 1$. Especially, when
$\rho_{KE}$ is a classical-quantum (cq) state, i.e.,
$\rho_{KE}=\sum_{k\in\mathcal{K}}|k\rangle\langle k|_{K}\otimes\rho^{k}_{E}$,
with the classical variable $K\in\mathcal{K}$, min-entropy can be interpreted
in terms of guessing probability

$H_{\mathrm{min}}(K|E)_{\rho}=-\log p_{\mathrm{guess}}(K|E)_{\rho},$

where the guessing probability is defined as [40, 18]

$p_{\mathrm{guess}}(K|E)_{\rho}=\sup_{E^{k}}\sum_{k\in\mathcal{K}}\Pr(K=k)_{\rho}\Tr[E^{k}\rho_{E|K=k}],$

where $\Pr(K=k)_{\rho}=\Tr[\rho^{k}_{E}]$ is the probability of measuring $k$
on the system $K$, $\rho_{E|K=k}$ is the normalized version of $\rho^{k}_{E}$,
and $\\{E^{k}\\}_{k}$ is a set of positive operator-valued measures (POVMs)
acting on system $E$ and $\rho_{E|K=k}$ is the normalized post-measurement
state after performing the measurement on $K$ and getting outcome $k$.

Associated with the min-entropy definition, the smooth min-entropy can be
defined as 222This definition follows Tomamichel’s book [41]; however, other
papers may use a different distance metric, e.g., in [42], they use trace
distance
$\Delta(\rho,\sigma)=\frac{1}{2}\|\rho-\sigma\|_{1}+\frac{1}{2}|\Tr(\rho-\sigma)|$
to define the $\epsilon$-ball, which is also fine, since we can bound the
radius of the ball with different metrics by the inequality
$\Delta(\rho,\sigma)\leq D(\rho,\sigma)\leq\sqrt{2\Delta(\rho,\sigma)}$

$H_{\mathrm{min}}^{\epsilon}(K|E)_{\rho}:=\max_{\tilde{\rho}_{KE}\in\mathfrak{B}^{\epsilon}(\rho_{KE})}H_{\mathrm{min}}(K|E)_{\tilde{\rho}},$

where $\mathfrak{B}^{\epsilon}(\rho_{KE})=\\{\tilde{\rho}_{KE}\mid
D(\tilde{\rho}_{KE},\rho_{KE})\leq\epsilon\\}$, and
$D(\rho,\sigma)=\sqrt{1-\left(\Tr|\sqrt{\rho}\sqrt{\sigma}|+\sqrt{(1-\Tr\rho)(1-\Tr\sigma)}\right)^{2}}$
is the purified distance. Note that by taking the limit $\epsilon\to 0$, we
have $\lim_{\epsilon\to
0}H_{\mathrm{min}}^{\epsilon}(K|E)_{\rho}=H_{\mathrm{min}}(K|E)_{\rho}$. The
$\epsilon$ parameter allows us to inspect the states around the state
$\rho_{KE}$ we assumed or observed. Smooth min-entropy simply takes the best
state that gives the largest worst-case randomness.

To design a practical DI randomness expansion protocol, it is necessary to
confine our attention to a finite number of variables. Consider a protocol
generating $n$ outputs sequentially $K^{n}=K_{1}K_{2}...K_{n}$. The associated
side information becomes $E_{n}=I^{n}E^{\prime}_{n}$, where
$I^{n}=I_{1}I_{2}...I_{n}$ and $I_{k}$ refers to the classical side
information generated in the $k$-th round, and $E^{\prime}_{n}$ is the quantum
side information after $n$ rounds. The amount of randomness stemming from this
$n$-round sequential protocol can be quantified through the smooth min-
entropy,
$H_{\mathrm{min}}^{\epsilon}(K^{n}|I^{n}E^{\prime}_{n}){\rho_{K^{n}I^{n}E^{\prime}_{n}}}$.

###  II.3 Types of randomness

Let $\mathcal{G}$ be a bipartite nonlocal game defined by the input sets
$\mathcal{X}\times\mathcal{Y}$ with $\mathcal{X}=\\{X\\}$,
$\mathcal{Y}=\\{Y\\}$, and the outcome sets $\mathcal{A}\times\mathcal{B}$,
with $\mathcal{A}=\\{A\\}$, $\mathcal{B}=\\{B\\}$, all linked to a winning
condition function
$\omega:\mathcal{X}\times\mathcal{Y}\times\mathcal{A}\times\mathcal{B}\mapsto\mathbb{R}$.
We explore three distinct types of randomness. These types are classified by
the target system $K$ where the randomness is extracted from, and the
adversary’s quantum side information $E^{\prime}$ and classical side
information $I$. The amount of randomness can be described by the entropic
quantity in the following form 333We write in the form of the von Neumann
entropy, however, this can be adapted to other kinds of entropic quantities
with the same target system and conditional systems.

$H(K|IE^{\prime})_{\rho_{KIE^{\prime}}}.$

Local randomness is a type of randomness when only one party’s outcome is
considered as the source for randomness generation, e.g., $K=A$, and the
classical side information is $I=XY$. The relevant entropic quantity for local
randomness is $H(A|XYE^{\prime})$.

Global randomness is a type of randomness when considering randomness
extracted from both parties’ outcomes $K=AB$. With the same classical side
information specified as in the local randomness case, i.e., $I=XY$, the
relevant entropic quantity for global randomness is $H(AB|XYE^{\prime})$.

The aforementioned types of randomness are the standard DI randomness,
restricting the adversary from directly participating in the nonlocal game.
That is the adversary is prohibited from directly accessing outputs from any
of the parties. The randomness under this scenario has been proposed and
discussed for a long time [7, 17, 43].

Apart from the standard types of randomness, another type of randomness called
Blind randomness was proposed [23, 25] to consider a different scenario where
the adversary is allowed to be part of the parties in the game, i.e., has the
capability to either generate or acquire the outcome from one or more than one
of the parties. The randomness is computed against other parties’ side
information. For instance, in the CHSH game, if we consider extracting
randomness from Alice’s outcome $K=A$, then, Bob’s outcome $B$ is assumed to
be part of the adversary’s classical side information $I=XYB$, and the quantum
side information $E^{\prime}$ also extends to the part of the bipartite state
that is used to generate Bob’s outcome $B$. In this case, the relevant
entropic quantity is $H(A|BXYE^{\prime})$. Essentially, this scenario
introduces the idea of mistrust between the parties.

###  II.4 Extractor

To complete the randomness expansion protocol, an indispensable tool is
required to extract randomness from a classical source that may be correlated
with quantum side information, i.e., the quantum-proof strong extractor [44].

######  Definition 1.

[44, Lemma 3.5] For any input source $X\in\mathcal{X}$ in the form of a cq
state $\rho_{XE}$ with quantum side information $E$ satisfying
$H_{\mathrm{min}}^{\epsilon}(X|E)_{\rho}\geq k_{\mathrm{EXT}}$, after applying
a quantum-proof $(k_{\mathrm{EXT}},\epsilon_{\mathrm{EXT}})$-strong extractor,
$\mathrm{EXT}:\mathcal{X}\times\mathcal{Y}\to\mathcal{Z}$, with seed
$Y\in\mathcal{Y}$, the extractor generates output $Z\in\mathcal{Z}$. The state
$\rho_{ZYE}$ satisfies

$\frac{1}{2}\|\rho_{ZYE}-\mu_{Z}\otimes\mu_{Y}\otimes\rho_{E}\|_{1}\leq\epsilon_{\mathrm{EXT}}+2\epsilon,$
(3)

where $\mu_{Z}$ ($\mu_{Y}$) is the maximally mixed state on the Hilbert space
$\mathcal{H}_{Z}$ ($\mathcal{H}_{Y}$).

There are multiple ways to construct a quantum-proof strong extractor, a well-
known construction is using two-universal hash functions or
$\delta_{\mathrm{h}}$-almost two-universal hash functions [45], while another
construction called Trevisan’s extractor [44] provides a way to build an
extractor consuming a shorter seed. For completeness, we describe the quantum-
proof extractor with $\delta_{\mathrm{h}}$-almost two-universal hash functions
as an example in the Appendix A.

##  III Protocol

The nonlocal game corresponding to the correlations from one of the no-
signaling boundary (NSB) classes [34] can be constructed by the CHSH game with
zero-probability constraints. To this end, consider the CHSH nonlocal game
$\mathcal{G}$ with the inputs $x,y\in\\{0,1\\}$ chosen according the uniform
probability distribution $P(x,y)=\frac{1}{4}$ for all $x,y\in\\{0,1\\}$, and
the outputs $a,b\in\\{0,1\\}$. The winning condition function is defined as

$\omega(x,y,a,b)=xy\oplus a\oplus b=\begin{cases}1,\ &\text{win},\\\ 0,\
&\text{loose}.\end{cases}$ (4)

The classes of zero-probability constrained quantum correlations [34] are
defined as

$\displaystyle\mathcal{Q}_{3a}=\\{$ $\displaystyle\vec{P}\in\mathcal{Q}\mid$
(5) $\displaystyle P(0,0|0,0)=P(1,1|1,0)=P(1,1|0,1)=0\\},$
$\displaystyle\mathcal{Q}_{3b}=\\{$ $\displaystyle\vec{P}\in\mathcal{Q}\mid$
$\displaystyle P(0,0|0,0)=P(1,1|0,0)=P(1,0|1,1)=0\\},$
$\displaystyle\mathcal{Q}_{2a}=\\{$ $\displaystyle\vec{P}\in\mathcal{Q}\mid
P(0,0|0,0)=P(1,1|0,0)=0\\},$ $\displaystyle\mathcal{Q}_{2b}=\\{$
$\displaystyle\vec{P}\in\mathcal{Q}\mid P(0,0|0,0)=P(1,1|1,0)=0\\},$
$\displaystyle\mathcal{Q}_{2c}=\\{$ $\displaystyle\vec{P}\in\mathcal{Q}\mid
P(0,0|0,0)=P(1,0|1,1)=0\\},$ $\displaystyle\mathcal{Q}_{1}=\\{$
$\displaystyle\vec{P}\in\mathcal{Q}\mid P(0,0|0,0)=0\\}.$

We herein also define the sets of input-output tuples for zero-probability
constraints

$\mathcal{S}_{\kappa}=\\{(a,b,x,y)|\vec{P}\in\mathcal{Q}_{\kappa},P(a,b|x,y)=0\\},$
(6)

where $\kappa$ denotes the class of the zero-probability constrained quantum
correlations. For example, for class 2a, the set is
$\mathcal{S}_{2a}=\\{(0,0,0,0),(1,1,0,0)\\}$; for class 3b, the set is
$\mathcal{S}_{3b}=\\{(0,0,0,0),(1,1,0,0),(1,0,1,1)\\}$.

In practice, it is impossible to achieve zero-probability constraints due to
noise and device imperfections, so we consider the relaxation of these
constraints with a small tolerable error $\eta_{\mathrm{z}}$, i.e.,
$\forall\vec{P}\in\widetilde{\mathcal{Q}}^{\eta_{\mathrm{z}}}_{\kappa}$,
$P(a,b|x,y)\leq\eta_{\mathrm{z}}$ for all $(a,b,x,y)\in\mathcal{S}_{\kappa}$,
where $\widetilde{\mathcal{Q}}^{\eta_{\mathrm{z}}}_{\kappa}$ is the relaxed
version of $\mathcal{Q}_{\kappa}$.

We state the steps of DI randomness generation protocol for three types of
randomness with chosen class $\kappa$ in Protocol 1. Among these classes, it
turns out that the best protocols for both local and global randomness in
terms of the maximal asymptotic rate are given by $\kappa=\text{2a}$, while
$\kappa=\text{3b}$ provides the optimal asymptotic rate for blind randomness.

To demonstrate the realization of Protocol 1, we describe the quantum strategy
that maximizes the CHSH winning probability for class 2a and class 3b as
follows:

$\displaystyle\ket{\Psi}$
$\displaystyle=\cos\theta\ket{01}+\sin\theta\ket{10},$ (7) $\displaystyle
A_{0}$ $\displaystyle=B_{0}=\sigma_{z},$ $\displaystyle A_{1}$
$\displaystyle=\cos 2\alpha\sigma_{z}-\sin 2\alpha\sigma_{x},$ $\displaystyle
B_{1}$ $\displaystyle=\cos 2\beta\sigma_{z}-\sin 2\beta\sigma_{x},$

where the parameters
$\theta=\frac{\pi}{4},\alpha=-\frac{5\pi}{6},\beta=\frac{\pi}{6}$ for class
2a; $\alpha=\beta\approx 0.6354$, $\theta=\tan^{-1}(\tan\alpha\tan\beta)$ for
class 3b (see Table 2 or [34, Section III]) for the realization of all the
classes.)

######  Protocol 1.

DI randomness generation protocol with
zero-probability constraints. 1. Alice and Bob decide which type of randomness
they want to generate $\chi=\begin{cases}\text{0, for local randomness,}\\\
\text{1, for global randomness,}\\\ \text{2, for blind
randomness.}\end{cases}$ They also decide which class of zero-probability
constraints, $\kappa$, they want to apply. 2. For each round
$i\in\\{1,2,...,n\\}$ (a) Alice chooses $T_{i}\in\\{0,1\\}$ with probability
$P(T_{i}=1)=\gamma$. For $T_{i}=1$, Alice selects $X_{i}=x,Y_{i}=y$ according
to the probability distribution $P(x,y)=\frac{1}{4}$, for all
$x,y\in\\{0,1\\}$; if $T_{i}=0$, Alice sets $X_{i}=x^{*},Y_{i}=y^{*}$. (b)
Alice inputs $X_{i}$ into her device and sends $Y_{i}$ to Bob. Alice computes
her output $A_{i}$ and i. if $\chi=2$, she requests Bob to return his output
$B_{i}$ all the time. ii. otherwise, she only asks Bob to return when
$T_{i}=1$. (c) If $T_{i}=1$, Alice computes
$C_{\omega,i}=\omega(X_{i},Y_{i},A_{i},B_{i})$ and sets
$C_{z,(a^{\prime},b^{\prime},x^{\prime},y^{\prime}),i}=\delta_{a^{\prime},A_{i}}\delta_{b^{\prime},B_{i}}\delta_{x^{\prime},X_{i}}\delta_{y^{\prime},Y_{i}}$
for all
$(a^{\prime},b^{\prime},x^{\prime},y^{\prime})\in\mathcal{S}_{\kappa}$; if
$T_{i}=0$, Alice sets
$C_{\omega,i}=C_{z,(a^{\prime},b^{\prime},x^{\prime},y^{\prime}),i}=\perp$ for
all $(a^{\prime},b^{\prime},x^{\prime},y^{\prime})\in\mathcal{S}_{\kappa}$. 3.
After $n$ rounds, Alice checks
$\absolutevalue{\\{i:C_{\omega,i}=1\\}}\geq(w_{\mathrm{exp}}-w_{\mathrm{tol}})\gamma
n$ and
$\absolutevalue{\\{i:C_{z,(a^{\prime},b^{\prime},x^{\prime},y^{\prime}),i}\\}}\leq\eta_{\mathrm{z}}\gamma
n$ for all
$(a^{\prime},b^{\prime},x^{\prime},y^{\prime})\in\mathcal{S}_{\kappa}$. She
aborts if any one of the checks is not satisfied. 4. If the protocol is not
aborted, Alice defines the target source $K_{i}$ and public information
$I_{i}$ in each round based on $\chi$ (a) if $\chi=0$, she sets $K_{i}=A_{i}$
and $I_{i}=X_{i}Y_{i}$. (b) if $\chi=1$, she sets $K_{i}=A_{i}B_{i}$ and
$I_{i}=X_{i}Y_{i}$. (c) if $\chi=2$, she sets $K_{i}=A_{i}$ and
$I_{i}=X_{i}Y_{i}B_{i}$. Then, Alice computes $k_{\mathrm{EXT}}$ such that
$H_{\mathrm{min}}^{\epsilon}(K^{n}|I^{n}E^{\prime})\geq k_{\mathrm{EXT}}$, and
applies a quantum-proof $(k_{\mathrm{EXT}},\epsilon_{\mathrm{EXT}})$-strong
randomness extractor to extract $\lfloor
k_{\mathrm{EXT}}-\Delta_{\mathrm{EXT}}\rfloor$ bits from
$\\{K_{i}\\}_{i,T_{i}=0}$.

##  IV Finite Analysis on Randomness

The asymptotic rates for all classes are calculated using the BFF21 method
[38] (see also Appendix C) with uniform input probability, i.e.,
$P(x,y)=\frac{1}{4}$ for all $x,y\in\\{0,1\\}$, tolerable winning probability
deviation $w_{\mathrm{tol}}=2\times 10^{-5}$,444That is even when
$w_{\mathrm{exp}}$ is set at the quantum bound, we still allow the winning
probability in the range
$[w_{\mathrm{exp}}-w_{\mathrm{tol}},w_{\mathrm{exp}}]$. and tolerable error
for zero probability $\eta_{\mathrm{z}}=10^{-10}$. In Table 1, we provide the
maximum asymptotic rates based on the maximal quantum-achievable winning
probability for each class 555Note that the values listed in Table 1 are not
very tight because of the tradeoff taken between numerical precision and the
feasibility of the solver for the whole class. In particular, we choose the
Mosek solver parameter that describes the allowable gap between the primal and
dual solutions equal to $10^{-6}$. For CHSH, the local value is analytically
given by [17] as 1. (see Table 2 for the quantum-achievable winning
probability of each class.)

Class | Local | Global | Blind
---|---|---|---
CHSH | 0.9981 | 1.5816 | 0.5823
1 | 0.9958 | 1.6770 | 0.7381
2a | 0.9992 | 1.7964 | 0.7962
2b | 0.9450 | 1.5963 | 0.7914
2bswap | 0.9977 | 1.5963 | 0.6501
2c | 0.9329 | 1.7028 | 0.7806
3a | 0.9497 | 1.5448 | 0.7444
3b | 0.9777 | 1.6852 | 0.9238
Table 1: Maximal asymptotic rate (conditional von Neumann entropy, $H(K|E)$)
of all types of randomness for each class with protocol parameters:
$w_{\mathrm{tol}}=2\times 10^{-5}$, and $\eta_{\mathrm{z}}=10^{-10}$ with
eighteen-term Gauss-Radau quadrature. Note that 2bswap is the party-swapped
version of class 2b.

The curves of the asymptotic DI randomness rate as a function of the CHSH
winning probability for all classes are shown in Fig. 1.

(a) Local randomness

(b) Global randomness

(c) Blind randomness

Figure 1: The asymptotic rate (conditional von Neumann entropy, $H(K|E)$) of
(a) local (b) global and (c) blind randomness with optimal choice of the
inputs over CHSH winning probability. The rates are computed in NPA level 2
plus $ABZ^{(\dagger)},ABZ^{\dagger}Z,ABZZ^{\dagger}$ types of moments with
Gauss-Radau quadrature containing $m=12$ terms.

To determine the finite rate of randomness, we utilize the GEAT (see Appendix
D.) Essentially, the GEAT establishes a lower bound on the smooth min-entropy
for an $n$-round scenario. The bound on the smooth min-entropy is obtained by
subtracting round-dependent correction terms from the worst-case von Neumann
entropy. These correction terms rely on specific properties of the min-
tradeoff function and the security parameters.

In Appendix E, we systematically outline the construction of the min-tradeoff
function, which is derived from the Lagrange dual function of the semidefinite
program (SDP) for conditional von Neumann entropy (asymptotic rate)
computation.

For a spot-checking embedded protocol, the min-tradeoff function needs to
include results from both testing and non-testing rounds. This kind of min-
tradeoff function called crossover min-tradeoff function can be constructed
from the original min-tradeoff function that only contains the testing rounds.
The transformation of the min-tradeoff function into its crossover version is
demonstrated in Appendix F.

With all the required ingredients in place, we can numerically derive the
lower bounds on the smooth min-entropy for various types of randomness. Taking
the input randomness consumption into account, we illustrate the finite rate
of Protocol 1 in Fig. 2 with the formula stated in Theorem 1.

######  Theorem 1 (Security and finite rate of Protocol 1).

Given $w_{\mathrm{exp}}\in[w_{C},w_{Q}]$, $\gamma\in(0,1]$,
$\nu^{\prime}\in[0,1]$, and
$\epsilon,w_{\mathrm{tol}},\eta_{\mathrm{z}},\beta\in(0,1)$, Protocol 1 is
$\epsilon_{\mathrm{s}}$-sound and $\epsilon_{\mathrm{c}}$-complete, where
$\epsilon_{\mathrm{s}}=\epsilon_{\mathrm{EXT}}+2\epsilon$ and
$\epsilon_{\mathrm{c}}=1-(1-e^{-2w_{\mathrm{tol}}^{2}n})(1-e^{-2\eta_{\mathrm{z}}^{\prime
2}n})^{n_{\mathrm{zero}}}$, $n_{\mathrm{zero}}$ is the number of zero-
probability constraints depending on the choice of the classes $\kappa$. The
finite rate is given by

$r(n,w_{\mathrm{exp}},\gamma,\epsilon,w_{\mathrm{tol}},\eta_{\mathrm{z}},\lambda,\beta,\nu^{\prime})=\\\
h(w_{\mathrm{exp}}-w_{\mathrm{tol}})-\Delta-\Delta_{\mathrm{EXT}}-\Delta_{\mathrm{inp}},$
(8)

where $\Delta$ is finite-rate correction term, $\Delta_{\mathrm{EXT}}$ is the
extractor entropy loss, and $\Delta_{\mathrm{inp}}$ is the randomness
consumption to generate inputs. $\Delta$ is given below

$\displaystyle\Delta=$ $\displaystyle\frac{\ln 2}{2}\beta\left[\log
9+V\right]^{2}$ (9)
$\displaystyle-\frac{1}{n}\bigl{[}\frac{1+\beta}{\beta}\log(1-\sqrt{1-\epsilon^{2}})+\frac{1+2\beta}{\beta}\log\Pr[\Omega]\bigr{]}$
$\displaystyle-\frac{1}{6\ln
2}\frac{\beta^{2}}{(1-\beta)^{3}}\zeta^{\beta}\ln^{3}(\zeta+e^{2}),$

where $V=\sqrt{2+D-\min_{\nu\in[1-w_{Q},w_{Q}]}\lambda^{2}(\nu-\nu_{0})^{2}}$,
$\gamma_{0}=\frac{1-\gamma}{\gamma}$,
$\nu_{0}=\frac{1}{2\gamma}-\gamma_{0}\nu^{\prime}$,
$D=\frac{\lambda^{2}}{4\gamma^{2}}-\frac{\gamma_{0}}{\gamma}\lambda^{2}(1-\nu^{\prime})\nu^{\prime}$,
$\zeta=2^{2+\lambda(\gamma_{0}(1-\nu^{\prime})+w_{Q})}$, $w_{C}$ and $w_{Q}$
are classical and quantum bound of the game.

Eq.(15) gives the extractor entropy loss for the extractor built based on the
$\delta_{\mathrm{h}}$-almost hashing.

The input randomness consumption is given

$\Delta_{\mathrm{inp}}=\gamma H_{\mathrm{sh}}(p)+H_{\mathrm{sh}}(\gamma),$
(10)

where $H_{\mathrm{sh}}$ is Shannon entropy.

The derivation of the security and finite-rate correction term in Theorem 1
can be found in Appendix G.

To demonstrate the security of the Protocol 1, we set the smoothness
$\epsilon=10^{-12}$ and the extractor parameter
$\epsilon_{\mathrm{EXT}}\leq\epsilon\times 10^{-3}$. The soundness of Protocol
1 is $\epsilon_{\mathrm{s}}=\epsilon_{\mathrm{EXT}}+2\epsilon\approx 2\times
10^{-12}$. By choosing the tolerable winning probability deviation
$w_{\mathrm{tol}}=10^{-4}$ and tolerable error for zero probability
$\eta_{\mathrm{z}}=10^{-3}$, the completeness of Protocol 1 is
$\epsilon_{\mathrm{c}}=0.8223$ for $n=10^{7}$.

Since the extractor entropy loss $\Delta_{\mathrm{EXT}}$ is independent of the
number of rounds $n$, we neglect it in our computation for convenience. The
finite rates of global randomness for Protocol 1 are illustrated in Fig. 2(b).
The standard CHSH and the $\delta$-family Bell inequality 666The
$\delta$-family Bell is in the following form, $\langle
A_{0}B_{0}\rangle+\frac{1}{\sin\delta}(\langle A_{0}B_{1}\rangle+\langle
A_{1}B_{0}\rangle)-\frac{1}{\cos 2\delta}\langle A_{1}B_{1}\rangle$. [22] are
included for comparison. All the lines are computed with the tolerable
deviation $w_{\mathrm{tol}}=10^{-4}$, and $\delta=\pi/6$. We choose two
different zero-probability tolerance $\eta_{\mathrm{z}}=10^{-3},\ 10^{-9}$ to
show the robustness of Protocol 1.

(a) Local randomness

(b) Global randomness

(c) Blind randomness

Figure 2: Finite rates of (a) local (b) global and (c) blind randomness for
Protocol 1 with zero-probability constraints, class 2a for (a) and (b), class
3b for (c), compared to the standard CHSH-game-based protocol and the one
relying on WBC $I_{\delta}$ with $\delta=\pi/6$. Two different zero-
probability tolerances $\eta_{\mathrm{z}}=10^{-3},10^{-9}$ and a fixed winning
probability tolerance $w_{\mathrm{tol}}=10^{-4}$ are considered.

Other types of randomness and the finite analysis of other classes are shown
in Appendix H.

##  V Concluding remarks

The amount of DI randomness for a given CHSH score is generally not tight. In
this work, we have shown how improvements in the asymptotic rates across all
forms of randomness can be achieved for a wide range of CHSH scores by
incorporating the zero-probability constraints classified in [34], see Fig. 1.
In particular, for the case of blind randomness, when relying solely on the
CHSH score, the rate becomes zero when the score (winning probability) drops
below 0.81. In contrast, for all the other protocols that incorporate these
additional zero-probability constraints, the rate reaches zero only at the
classical bound of 0.75. However, if one further optimizes the rate over the
range of CHSH scores allowed, then an obvious advantage in the DI randomness
generation rate persists solely for the blind and global randomness (see Table
1).

Next, we focus on the quantum strategy from each class that maximizes the DI
randomness generation rate, via Protocol 1, for all types of randomness. For
completeness, we also compare the best (finite) rates achievable from these
classes against those obtained from the quantum strategy maximizing the CHSH
Bell-inequality violation and the $\delta$-family inequality of [22] with
$\delta=\pi/6$. As expected from the asymptotic results, we see from Fig. 2 a
general advantage from a protocol with additional zero-probability constraints
against the standard CHSH protocol for all three types of randomness. However,
these advantages are, at the same time, inferior to those brought by the
protocol [22] of employing the $I_{\delta}$ inequality. The only exception to
this observation is for the single-party (local) randomness, where our
protocol offers a slight improvement in the minimal rounds required to observe
a nonzero generation rate.

Our results suggest that when there is a limitation on the number of rounds,
it may be possible to explore different numbers of zero-probability
constraints and various tolerable levels to attain a higher rate. However, to
actually take advantage of our observation, it is clear that one should
perform further analysis by taking into account also other imperfections, such
as losses, that are, unfortunately, very common in photonic experiments.

###### Acknowledgements.

We thank Stefan Bauml for helpful discussions on the entropy accumulation
theorem. This work is partially supported by the National Science and
Technology Council (NSTC, formerly Ministry of Science and Technology), Taiwan
(Grants No. 109-2112-M006-010-MY3, 112-2119-M001-004, 112-2119-M001-006,
112-2628-M006-007-MY4).

## References

  * Gisin  _et al._ [2002] N. Gisin, G. Ribordy, W. Tittel, and H. Zbinden, Rev. Mod. Phys. 74, 145 (2002).
  * Scarani [2012] V. Scarani, Acta Phys. Slovaca 62, 347 (2012).
  * Brunner  _et al._ [2014] N. Brunner, D. Cavalcanti, S. Pironio, V. Scarani, and S. Wehner, Rev. Mod. Phys. 86, 419 (2014).
  * Ekert [1991] A. K. Ekert, Phys Rev Lett 67, 661 (1991).
  * Mayers and Yao [1998] D. Mayers and A. Yao, in  _Proceedings 39th Annual Symposium on Foundations of Computer Science (Cat. No.98CB36280)_ (IEEE, 1998) pp. 503–509.
  * Barrett  _et al._ [2005a] J. Barrett, L. Hardy, and A. Kent, Phys Rev Lett 95, 010503 (2005a).
  * Colbeck [2006] R. Colbeck,  _Quantum And Relativistic Protocols For Secure Multi-Party Computation_ , Phd dissertation, Univ. Cambridge (2006), 0911.3814 .
  * Bell [1964] J. S. Bell, Physics Physique Fizika 1, 195 (1964).
  * Clauser  _et al._ [1969] J. F. Clauser, M. A. Horne, A. Shimony, and R. A. Holt, Phys Rev Lett 23, 880 (1969).
  * Fine [1982] A. Fine, Phys. Rev. Lett. 48, 291 (1982).
  * Masanes [2009] L. Masanes, Phys. Rev. Lett. 102, 140501 (2009).
  * Masanes  _et al._ [2011] L. Masanes, S. Pironio, and A. Acín, Nat. Commun. 2, 1 (2011).
  * Arnon-Friedman  _et al._ [2019] R. Arnon-Friedman, R. Renner, and T. Vidick, SIAM Journal on Computing 48, 181 (2019), https://doi.org/10.1137/18M1174726 .
  * Nadlinger  _et al._ [2022] D. P. Nadlinger, P. Drmota, B. C. Nichol, G. Araneda, D. Main, R. Srinivas, D. M. Lucas, C. J. Ballance, K. Ivanov, E. Y. Z. Tan, P. Sekatski, R. L. Urbanke, R. Renner, N. Sangouard, and J. D. Bancal, Nature 607, 682 (2022).
  * Zhang  _et al._ [2022] W. Zhang, T. van Leent, K. Redeker, R. Garthoff, R. Schwonnek, F. Fertig, S. Eppelt, W. Rosenfeld, V. Scarani, C. C.-W. Lim, and H. Weinfurter, Nature 607, 687 (2022).
  * Tan  _et al._ [2022] E. Y.-Z. Tan, P. Sekatski, J.-D. Bancal, R. Schwonnek, R. Renner, N. Sangouard, and C. C.-W. Lim, Quantum 6, 880 (2022), 2012.08714v4 .
  * Pironio  _et al._ [2010] S. Pironio, A. Acín, S. Massar, A. B. de la Giroday, D. N. Matsukevich, P. Maunz, S. Olmschenk, D. Hayes, L. Luo, T. A. Manning, and C. Monroe, Nature 464, 1021 (2010).
  * Brown  _et al._ [2019] P. J. Brown, S. Ragy, and R. Colbeck, IEEE Trans Inf Theory 66, 2964 (2019).
  * Liu  _et al._ [2021] W.-Z. Liu, M.-H. Li, S. Ragy, S.-R. Zhao, B. Bai, Y. Liu, P. J. Brown, J. Zhang, R. Colbeck, J. Fan, Q. Zhang, and J.-W. Pan, Nat Phys 17, 448 (2021).
  * Acín  _et al._ [2012] A. Acín, S. Massar, and S. Pironio, Phys. Rev. Lett. 108, 100402 (2012).
  * Bourdoncle  _et al._ [2019] B. Bourdoncle, P.-S. Lin, D. Rosset, A. Acín, and Y.-C. Liang, Quantum Sci. Technol. 4, 025007 (2019).
  * Wooltorton  _et al._ [2022] L. Wooltorton, P. Brown, and R. Colbeck, Phys. Rev. Lett. 129, 150403 (2022).
  * Miller and Shi [2017] C. A. Miller and Y. Shi, Quantum Inf Comput 17, 595 (2017).
  * Metger  _et al._ [2022a] T. Metger, O. Fawzi, D. Sutter, and R. Renner, in  _2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS)_ (IEEE, 2022) pp. 844–850.
  * Fu and Miller [2018] H. Fu and C. A. Miller, Phys. Rev. A 97, 032324 (2018).
  * Metger  _et al._ [2022b] T. Metger, O. Fawzi, D. Sutter, and R. Renner, Generalised entropy accumulation, arXiv:2203.04989 (2022b).
  * Šupić and Bowles [2020] I. Šupić and J. Bowles, Quantum 4, 337 (2020).
  * Nieto-Silleras  _et al._ [2014] O. Nieto-Silleras, S. Pironio, and J. Silman, New J. Phys. 16, 013035 (2014).
  * Bancal  _et al._ [2014] J.-D. Bancal, L. Sheridan, and V. Scarani, New J. Phys. 16, 033011 (2014).
  * Nieto-Silleras  _et al._ [2018] O. Nieto-Silleras, C. Bamps, J. Silman, and S. Pironio, New J. Phys. 20, 023049 (2018).
  * Popescu and Rohrlich [1994] S. Popescu and D. Rohrlich, Found. Phys. 24, 379 (1994).
  * Barrett  _et al._ [2005b] J. Barrett, N. Linden, S. Massar, S. Pironio, S. Popescu, and D. Roberts, Phys. Rev. A 71, 022101 (2005b).
  * Goh  _et al._ [2018] K. T. Goh, J. Kaniewski, E. Wolfe, T. Vértesi, X. Wu, Y. Cai, Y.-C. Liang, and V. Scarani, Phys. Rev. A 97, 022104 (2018).
  * Chen  _et al._ [2023] K.-S. Chen, G. N. M. Tabia, C. Jebarathinam, S. Mal, J.-Y. Wu, and Y.-C. Liang, Quantum 7, 1054 (2023).
  * Hardy [1993] L. Hardy, Phys. Rev. Lett. 71, 1665 (1993).
  * Kessler and Arnon-Friedman [2020] M. Kessler and R. Arnon-Friedman, IEEE J. Sel. Areas Commun. 1, 568 (2020).
  * Colbeck and Renner [2012] R. Colbeck and R. Renner, Nat. Phys. 8, 450 (2012).
  * Brown  _et al._ [2021] P. Brown, H. Fawzi, and O. Fawzi, arXiv 10.48550/arXiv.2106.13692 (2021), arXiv:2106.13692v2 [quant-ph] .
  * Dupuis and Fawzi [2018] F. Dupuis and O. Fawzi, arXiv 10.1109/TIT.2019.2929564 (2018), 1805.11652 .
  * Tomamichel and Leverrier [2017] M. Tomamichel and A. Leverrier, Quantum 1, 14 (2017).
  * Tomamichel [2015] M. Tomamichel,  _Quantum Information Processing with Finite Resources_ (Springer International Publishing, Cham, Switzerland, 2015).
  * Renner [2005] R. Renner,  _Security of Quantum Key Distribution_ , Ph.D. thesis, ETH Zurich (2005), quant-ph/0512258 .
  * Colbeck and Kent [2011] R. Colbeck and A. Kent, J Phys A: Math Theor 44, 095305 (2011).
  * De  _et al._ [2012] A. De, C. Portmann, T. Vidick, and R. Renner, SIAM J Comput (2012).
  * Tomamichel  _et al._ [2010] M. Tomamichel, R. Renner, C. Schaffner, and A. Smith, in  _2010 IEEE International Symposium on Information Theory_ (IEEE, 2010) pp. 2703–2707.
  * Hayashi and Tsurumaru [2016] M. Hayashi and T. Tsurumaru, IEEE Trans Inf Theory 62, 2213 (2016).
  * Navascués  _et al._ [2007] M. Navascués, S. Pironio, and A. Acín, Phys Rev Lett 98, 010401 (2007).
  * Navascués  _et al._ [2008] M. Navascués, S. Pironio, and A. Acín, New J Phys 10, 073013 (2008).
  * ApS [2023] M. ApS, MOSEK Fusion API for Python 10.0.40 — MOSEK Fusion API for Python 10.0.40 (2023), [Online; accessed 1. May 2023].
  * peterjbrown519 [2023] peterjbrown519, ncpol2sdpa (2023), [Online; accessed 2\. May 2023].
  * Tan  _et al._ [2021] E. Y.-Z. Tan, R. Schwonnek, K. T. Goh, I. W. Primaatmaja, and C. C.-W. Lim, npj Quantum Inf 7, 1 (2021).
  * Zhou  _et al._ [2017] C. Zhou, P. Xu, W.-S. Bao, Y. Wang, Y. Zhang, M.-S. Jiang, and H.-W. Li, Opt. Express 25, 16971 (2017).
  * Metger and Renner [2022] T. Metger and R. Renner, Security of quantum key distribution from generalised entropy accumulation (2022), arXiv:2203.04993 [quant-ph] .
  * Bardenet and Maillard [2015] R. Bardenet and O.-A. Maillard, Bernoulli 21, 1361 (2015).

##  Appendix A Quantum-proof extractor based on almost two-universal hashing

######  Definition 2 ($\delta_{\mathrm{h}}$-almost two-universal hashing
[46]).

A family $\mathcal{F}:\mathcal{X}\to\mathcal{Y}$ of hash functions is said to
be $\delta_{\mathrm{h}}$-almost two-universal if the following condition hold

$\Pr_{f\in\mathcal{F}}[f(x)=f(x^{\prime})]\leq\frac{\delta_{\mathrm{h}}}{|\mathcal{Y}|}\quad\forall\
x\neq x^{\prime},$ (11)

where the probability is computed uniformly over the family $\mathcal{F}$,
$\delta_{\mathrm{h}}\geq 1$. Especially, when $\delta_{\mathrm{h}}=1$, the
family $F$ is called two-universal hash function family.

######  Lemma 1 (Quantum Leftover Hash Lemma [45]).

Given any $\epsilon^{\prime}>0$, a cq-state
$\rho_{XE}=\sum_{x\in\mathcal{X}}|x\rangle\langle x|\otimes\rho^{x}_{E}$, and
a $\delta_{\mathrm{h}}$-almost two-universal hash family
$\mathcal{F}:\mathcal{X}\to\mathcal{Z}$, where $|\mathcal{Z}|=2^{l}$, if we
apply a hash function on the classical register by uniformly choosing a
function $f$ from the family $\mathcal{F}$, i.e.,
$\rho_{FZE}=\frac{1}{|\mathcal{F}|}\sum_{f\in\mathcal{F}}|f\rangle\langle
f|_{F}\otimes\sum_{x\in\mathcal{X}}|f(x)\rangle\langle
f(x)|_{Z}\otimes\rho^{x}_{E}$, then we have 777In [45], the author uses
$\frac{1}{2}\min_{\begin{subarray}{c}\sigma_{E}\in\mathcal{S}(\mathcal{H}_{E})\\\
\Tr\sigma_{E}=\Tr\rho_{E}\end{subarray}}\|\rho_{AE}-\mu_{A}\otimes\rho_{E}\|_{1}$
instead of the form in the LHS of Eq.(12). While in their proof, they first
take an upper-bound on
$\frac{1}{2}\min_{\begin{subarray}{c}\sigma_{E}\in\mathcal{S}(\mathcal{H}_{E})\\\
\Tr\sigma_{E}=\Tr\rho_{E}\end{subarray}}\|\rho_{AE}-\mu_{A}\otimes\rho_{E}\|_{1}$
as the form of the LHS of Eq.(12). Hence, the quantum leftover hash lemma is
also compatible with this definition.

$\frac{1}{2}\|\rho_{FZE}-\mu_{F}\otimes\mu_{Z}\otimes\rho_{E}\|_{1}\leq\\\
\frac{1}{2}\sqrt{\delta_{\mathrm{h}}-1+2^{l-H_{\mathrm{min}}(X|E)+\log(2/\epsilon^{\prime
2}+1)}}+\epsilon^{\prime},$ (12)

where $F$ is the system that records the choice of the hash function, and
$\mu_{F}$ ($\mu_{Z}$) is the maximally mixed state on the Hilbert space
$\mathcal{H}_{F}$ ($\mathcal{H}_{Y}$).

In Lemma 1, the choice of a hash function from the hash family could be
implemented by an extra random source, which is called the seed and can be
made public. Thus we consider a so-called extractor function with an extra
input as a seed, namely
$\mathrm{EXT}:\mathcal{X}\times\mathcal{Y}\to\mathcal{Z}$, where $\mathcal{X}$
denotes the set of inputs, $\mathcal{Y}$ denotes the set of seeds, and
$\mathcal{Z}$ denotes the set of outputs, and the size of the set of the seeds
is equal to that of the hash function family, i.e.,
$|\mathcal{Y}|=|\mathcal{F}|$.

######  Lemma 2.

A quantum-proof $(k_{\mathrm{EXT}},\epsilon_{\mathrm{EXT}})$-strong extractor,
$\mathrm{EXT}:\mathcal{X}\times\mathcal{Y}\to\mathcal{Z}$, where
$\log|\mathcal{X}|=n,\log|\mathcal{Y}|=d$, and $\log|\mathcal{Z}|=l$, can be
implemented by $\delta_{\mathrm{h}}$-almost two-universal hash function with
the output length

$l=k_{\mathrm{EXT}}-\log(1+\frac{2}{{\epsilon^{\prime}}^{2}})-\log\frac{1}{4{\epsilon^{\prime\prime}}^{2}-\delta_{\mathrm{h}}+1},$
(13)

where $\epsilon_{\mathrm{EXT}}=\epsilon^{\prime}+\epsilon^{\prime\prime}$ and
$\delta_{\mathrm{h}}$ and $\epsilon^{\prime\prime}$ satisfy
$\delta_{\mathrm{h}}\leq 1+4\epsilon^{\prime\prime 2}$.

###### Proof.

First, set the upper bound in Eq.(12) as the security parameter
$\epsilon_{\mathrm{EXT}}$

$\epsilon_{\mathrm{EXT}}=\frac{1}{2}\sqrt{\delta_{\mathrm{h}}-1+2^{l-H_{\mathrm{min}}(X|E)+\log(2/\epsilon^{\prime
2}+1)}}+\epsilon^{\prime}.$

Next, let
$\epsilon^{\prime\prime}=\frac{1}{2}\sqrt{\delta_{\mathrm{h}}-1+2^{l-H_{\mathrm{min}}(X|E)+\log(2/\epsilon^{\prime
2}+1)}}$. The output length is then

$l=H_{\mathrm{min}}(X|E)-\log(1+\frac{2}{{\epsilon^{\prime}}^{2}})-\log\frac{1}{4{\epsilon^{\prime\prime}}^{2}-\delta_{\mathrm{h}}+1}.$
(14)

Finally, with the condition on the state $\rho_{XE}$ of input source $X$ with
side information $E$, $H_{\mathrm{min}}(X|E)\geq k_{\mathrm{EXT}}$, we can
safely substitute the lower bound $k$ into Eq.(14). ∎

######  Fact 1.

A quantum-proof extractor needs to consume entropy to provide security. For
example, in the case of a $(k_{\mathrm{EXT}},\epsilon_{\mathrm{EXT}})$-strong
extractor based on $\delta_{\mathrm{h}}$-almost two-universal hashing, this
consumption of entropy is quantified as

$\Delta_{\mathrm{EXT}}=\log(1+\frac{2}{\epsilon^{\prime
2}})+\log{\frac{1}{4\epsilon^{\prime\prime 2}-\delta_{\mathrm{h}}+1}},$ (15)

where $\epsilon_{\mathrm{EXT}}=\epsilon^{\prime}+\epsilon^{\prime\prime}$ and
$\delta_{\mathrm{h}}$ and $\epsilon^{\prime\prime}$ satisfy
$\delta_{\mathrm{h}}\leq 1+4\epsilon^{\prime\prime 2}$. Given a source with
entropy lower bound, $k_{\mathrm{EXT}}$, the
$(k_{\mathrm{EXT}},\epsilon_{\mathrm{EXT}})$-extractor can extract at most
$k_{\mathrm{EXT}}-\Delta_{\mathrm{EXT}}$ bits from the source.

##  Appendix B Realization of zero-probability constrained quantum
correlations

For our purposes, it is enough to distinguish the classes according to the
number and positions of the zero probabilities.

For each of the no-signaling boundary classes, the quantum correlation that
maximally violates the CHSH inequality has been shown to self-test some
reference states and measurements, which are provided in Table 2. They also
provide some numerical calculations of the robustness of the self-testing
property of each of them.

Classes | State | Extra conditions | $w_{\mathrm{CHSH}}^{\mathrm{max}}$ | $\vec{P}_{\mathrm{CHSH}}^{\mathrm{max}}$
---|---|---|---|---
1 | $\ket{\Psi_{1}}$ | None | $0.8294$ | $\theta=\frac{\pi}{4},\phi\approx 0.2275,\alpha=\beta\approx-0.6403$
2a | $\ket{\Psi_{2}}$ | None | $0.8125$ | $\theta=\frac{\pi}{4},\alpha=-\frac{5\pi}{6},\beta=\frac{\pi}{6}$
2b | $\ket{\Psi_{3}}$ | None | $0.8125$ | $\phi=\beta=\frac{\pi}{4},\alpha=\frac{\pi}{6}$
2c | $\ket{\Psi_{1}}$ | $\phi=\tan^{-1}(\frac{\sin\theta}{\tan\beta}-\tan\alpha\cos\theta)$ | $0.8039$ | $\theta\approx 0.5815,\alpha\approx 0.8068,\beta=\frac{\pi}{2}-\alpha$
3a | $\ket{\Psi_{3}}$ | $\phi=\tan^{-1}(\frac{\tan\beta}{\sin\alpha})$ | $0.7951$ | $\alpha=\beta=\frac{1}{2}\tan^{-1}\left(-2\sqrt{2+\sqrt{5}}\right)$
3b | $\ket{\Psi_{2}}$ | $\theta=\tan^{-1}(\tan\alpha\tan\beta)$ | $0.7837$ | $\alpha=\beta\approx 0.6354$
Alice’s observables: $A_{0}=\sigma_{z},\;A_{1}=\cos 2\alpha\sigma_{z}-\sin
2\alpha\sigma_{x}$
Bob’s observables: $B_{0}=\sigma_{z},\;B_{1}=\cos 2\beta\sigma_{z}-\sin
2\beta\sigma_{x}$
$\ket{\Psi_{1}}=\cos\phi(\cos\theta\ket{01}+\sin\theta\ket{10})+\sin\phi\ket{11}$
$\ket{\Psi_{2}}=\cos\theta\ket{01}+\sin\theta\ket{10}$
$\ket{\Psi_{3}}=\sin\phi(\cos\alpha\ket{01}-\sin\alpha\ket{11})+\cos\phi\ket{10}$
Table 2: Quantum realization of all the classes of zero-probability
constrained quantum correlations in [34].

##  Appendix C Asymptotic rate computation with BFF21 method

In [38], Brown et al. provided a method to numerically find a lower bound on
the von Neumann entropy in the Bell scenario. This method is useful for many
DI cryptography tasks, especially randomness certification. The main idea of
the work is to handle the nonlinear logarithm function by Gauss-Radau
quadrature approximation. Together with the famous Navascués-Pironio-Acín
(NPA) hierarchy [47, 48], they derived a semidefinite program (SDP) which is
tractable with many commercial solvers, including Mosek [49]. Besides, the NPA
hierarchy of the given Bell scenario can be easily constructed by Wittek’s
Python package, ncpol2sdpa888We use the version that Peter Brown currently
maintains. [50]. Here we show the SDP that gives an infimum on the asymptotic
rates of randomness.

In the CHSH scenario, let Alice and Bob’s measurement POVMs be
$\\{\\{M^{a}_{x}\\}_{a}\\}_{x}$ and $\\{\\{N^{b}_{y}\\}_{b}\\}_{y}$
respectively. Choose the Gauss-Radau quadrature approximation with $m$ terms.
We the set of non-Hermitian operators acting on the adversary’s quantum system
$E^{\prime}$ be $\\{Z_{ab}\\}_{ab}$ (or $\\{Z_{a}\\}_{a}$ for the standard
local randomness). The von Neumann entropy can be lower-bounded by

$H(K|IE^{\prime})\geq c_{0}+\sum_{i=1}^{m}c_{i}\Xi_{i},$ (16)

where the coefficients $c_{0}=\sum_{i=1}^{m}c_{i}$,
$c_{i}=\frac{w_{i}}{t_{i}\ln 2}\ \ \forall i\in\\{1,2,...,m\\}$,
$\\{t_{i}\\}^{m}_{i=1}$ and $\\{w_{i}\\}^{m}_{i=1}$ are the nodes and weights
of the Gauss-Radau quadrature of the interval $(0,1]$, and $\Xi_{i}$ is the
SDP corresponding to the $i^{\mathrm{th}}$ term of the quadrature 999In [38],
they claimed the last term of the quadrature of which the node is at the
endpoint 1 can be trivially bounded by some constant, $1/m^{2}\ln 2$, which
may reduce the tightness of the obtained bound. While if one does the
optimization with $t_{m}=1$, the SDP sometimes can not be solved to achieve an
optimal solution. We came out with a way to handle it by changing the endpoint
from 1 to $0.9999$, which can provide a much tighter bound..

$\displaystyle\Xi_{i}=$
$\displaystyle\min_{\\{M^{a}_{x^{*}}\\},\\{N^{b}_{y^{*}}\\},\\{Z_{ab}\\}}\langle
F_{i}(\\{M^{a}_{x^{*}}\\}_{a},\\{N^{b}_{y^{*}}\\}_{b},\\{Z_{ab}\\}_{ab})\rangle$
(17) $\displaystyle s.t.$ $\displaystyle\sum_{abxy}c_{abxy}\langle
M^{a}_{x}N^{b}_{y}\rangle\geq w_{\mathrm{exp}}-w_{\mathrm{tol}}$
$\displaystyle\sum_{abxy}c_{abxy}\langle M^{a}_{x}N^{b}_{y}\rangle\leq
w_{\mathrm{exp}}+w_{\mathrm{tol}}$ $\displaystyle
P(ab|xy)\leq\eta_{\mathrm{z}}\quad\forall(a,b,x,y)\in\mathcal{S}_{\kappa}$
$\displaystyle\sum_{a}M^{a}_{x}=\mathds{1},\sum_{b}N^{b}_{y}=\mathds{1}\quad\forall\
x,y$ $\displaystyle M^{a}_{x}\geq 0,N^{b}_{y}\geq 0\quad\forall\ a,b,x,y$
$\displaystyle\left[\\{M^{a}_{x}\\}_{ax},\\{N^{b}_{y}\\}_{by}\right]=0$
$\displaystyle\left[\\{M^{a}_{x}\\}_{ax},\\{Z^{(\dagger)}_{ab}\\}_{ab}\right]=0$
$\displaystyle\left[\\{N^{b}_{y}\\}_{by},\\{Z^{(\dagger)}_{ab}\\}_{ab}\right]=0.$

Note that the minimization is taken inside the summation in Eq.(17) and thus
we need to compute $m$ SDPs for $m$-term quadrature. In principle, taking the
minimization outside the summation with
$\\{\\{Z^{i}_{ab}\\}_{ab}\\}_{i=1}^{m}$ would provide a tighter bound.
However, this requires much more memory to construct the NPA hierarchy with a
level higher or equal to 2. We follow the way Brown at el. [38] did to make it
more feasible by exchanging the summation and minimization. So, we can reduce
the required memory and still obtain a valid (but looser) lower bound
simultaneously.

For the standard local randomness, all $\\{Z^{(\dagger)}_{ab}\\}_{ab}$ in
Eq.(17) should be replaced with $\\{Z^{(\dagger)}_{a}\\}_{a}$. The objective
function inside the quadrature summation is

$\displaystyle
F_{\mathrm{local},i}(\\{M^{a}_{x^{*}}\\}_{a},\\{N^{b}_{y^{*}}\\}_{b},\\{Z_{a}\\}_{a})=F_{\mathrm{local},i}(\\{M^{a}_{x^{*}}\\}_{a},\\{Z_{a}\\}_{a})$
(18)
$\displaystyle=\sum_{a}\left[M^{a}_{x^{*}}(Z_{a}+Z_{a}^{\dagger}+(1-t_{i})Z_{a}^{\dagger}Z_{a})+t_{i}Z_{a}Z_{a}^{\dagger}\right].$

For the global randomness, the objective function $F_{\mathrm{global},i}$ is

$F_{\mathrm{global},i}(\\{M^{a}_{x^{*}}\\}_{a},\\{N^{b}_{y^{*}}\\}_{b},\\{Z_{ab}\\}_{ab})=\\\
\sum_{ab}\left[M^{a}_{x^{*}}N^{b}_{y^{*}}(Z_{ab}+Z_{ab}^{\dagger}+(1-t_{i})Z_{ab}^{\dagger}Z_{ab})+t_{i}Z_{ab}Z_{ab}^{\dagger}\right].$
(19)

Finally, the $i^{\mathrm{th}}$ term objective function of the blind randomness
is given

$F_{\mathrm{blind},i}(\\{M^{a}_{x^{*}}\\}_{a},\\{N^{b}_{y^{*}}\\}_{b},\\{Z_{ab}\\}_{ab})=\\\
\sum_{ab}\left[M^{a}_{x^{*}}N^{b}_{y^{*}}(Z_{ab}+Z_{ab}^{\dagger}+(1-t_{i})Z_{ab}^{\dagger}Z_{ab})+t_{i}N^{b}_{y^{*}}Z_{ab}Z_{ab}^{\dagger}\right].$
(20)

##  Appendix D Entropy accumulation

The entropy accumulation theorem (EAT) provides a way of bounding the smooth
min-entropy of a set of $n$ random variables $K_{i}$ produced by a sequential
protocol conditioned on some side information $E_{n}$ in terms of the
conditional von Neumann entropies generated in each round. In this work, we
consider the generalized version [24] of EAT, where the model of side
information is relaxed by allowing it to be updated in every round, that is
the side information after the $i^{\mathrm{th}}$ round is $E_{i}$. Suppose
that we represent the protocol as a sequence of quantum channels
$\mathcal{M}_{i}\in\mathrm{CPTP}(R_{i-1}E_{i-1},R_{i}E_{i}K_{i}C_{i})$, where
for a cryptographic scheme, $K_{i}$ represents the output in the
$i^{\mathrm{th}}$ round, $E_{i}$ is the side information leaked to some
adversary Eve after the $i^{\mathrm{th}}$ round, $R_{i}$ corresponds to some
internal system of the device, and $C_{i}$ is classical information used to
determine whether the protocol aborts. However, to be able to accumulate
entropy from every round, the Markov condition is replaced by a certain non-
signaling condition on $\mathcal{M}_{i}$: we require that there exists a
channel $\mathcal{R}_{i}\in\mathrm{CPTP}(E_{i-1},E_{i})$ such that

$\Tr_{K_{i}R_{i}}\circ\mathcal{M}_{i}=\mathcal{R}_{i}\circ\Tr_{R_{i-1}}.$ (21)

Intuitively, this means that all side information about output $K_{i}$ is
already present in $E_{i}$. The non-signaling condition prevents new
information about $K_{i}$ from being leaked from the $R$-systems at a later
round.

To formally state the GEAT with testing, a way to compute the min-entropy
conditioned on some classical statistics, we define some relevant concepts
below.

######  Definition 3 (Frequency distribution).

We denote the frequency of the occurrence of the value $c$ in the sequence
$C^{n}=C_{1}C_{2}...C_{n}$ by

$\mathrm{freq}_{C^{n}}(c)=\frac{\absolutevalue{\\{i\in\\{1,2,...,n\\}\mid
C_{i}=c\\}}}{n}.$ (22)

######  Definition 4 (EAT channels).

Let $\mathcal{M}_{i}\in\mathrm{CPTP}(R_{i-1}E_{i-1},C_{i}K_{i}R_{i}E_{i})$ be
a sequence of completely positive trace-preserving (CPTP) maps for
$i\in\\{1,\ldots,n\\}$, where $C_{i}$ are classical systems with common
alphabet $\mathcal{C}$. We require that these channels satisfy the following
non-signaling condition: defining
$\mathcal{M}^{\prime}_{i}=\Tr_{C_{i}}\circ\mathcal{M}_{i}$, there exists a
channel $\mathcal{T}$ such that
$\mathcal{M}_{n}\circ\cdots\circ\mathcal{M}_{1}=\mathcal{T}\circ\mathcal{M}^{\prime}_{n}\circ\cdots\circ\mathcal{M}^{\prime}_{1}$
and $\mathcal{T}$ has the form

$\mathcal{T}(\omega_{A^{n}E_{n}})=\\\
\sum_{u\in\mathcal{U},v\in\mathcal{V}}(\Pi_{K^{n}}^{(u)}\otimes\Pi_{E_{n}}^{(v)})\omega_{K^{n}E_{n}}(\Pi_{K^{n}}^{(u)}\\\
\otimes\Pi_{E_{n}}^{(v)})\otimes|r(u,v)\rangle\langle r(u,v)|_{C^{n}}\,,$ (23)

where $\\{\Pi_{K^{n}}^{(u)}\\}$ and $\\{\Pi_{E_{n}}^{(v)}\\}$ are families of
mutually orthogonal projectors on $K_{i}$ and $E_{i}$, and
$r:\mathcal{U}\times\mathcal{V}\to\mathcal{C}$ is a deterministic function.
Intuitively, this condition says that the classical statistics can be
reconstructed via projective measurements on systems $K^{n}$ and $E_{n}$ at
the end of the protocol. In particular, this requirement is always satisfied
if the statistics are computed from classical information contained in $K^{n}$
and $E_{n}$. Note that the statistics are still generated in a round-by-round
manner; Eq. (23) merely asserts that they could have been reconstructed from
the final state.

Let $\mathbb{P}$ be the set of probability distributions on the alphabet
$\mathcal{C}$ of $C_{i}$, and let $\tilde{E}_{i-1}$ be a system isomorphic to
$R_{i-1}E_{i-1}$. For any $q\in\mathbb{P}$ we define the set of states

$\Sigma_{i}(q)=\\\
\bigl{\\{}\nu_{C_{i}K_{i}R_{i}E_{i}\tilde{E}_{i-1}}=\mathcal{M}_{i}(\omega_{R_{i-1}E_{i-1}\tilde{E}_{i-1}})\,|\,\nu_{C_{i}}=q\bigr{\\}}\
,$ (24)

where $\nu_{C_{i}}$ denotes the probability distribution over $\mathcal{C}$
with the probabilities given by $\Pr[c]=\bra{c}\nu_{C_{i}}\ket{c}$. In other
words, $\Sigma_{i}(q)$ is the set of states that can be produced at the output
of the channel $\mathcal{M}_{i}$ and whose reduced state on $C_{i}$ is equal
to the probability distribution $q$.

######  Definition 5 (Min-tradeoff function).

A function $f:\mathbb{P}\to\mathbb{R}$, where $\mathbb{P}$ represents all
valid probability distributions, is called a _min-tradeoff function_ for
$\\{\mathcal{M}_{i}\\}$ if it satisfies

$\displaystyle
f(q)\leq\min_{\nu\in\Sigma_{i}(q)}H(K_{i}|E_{i}\tilde{E}_{i-1})_{\nu}\quad\forall
i=1,\dots,n\,.$ (25)

Note that if $\Sigma_{i}(q)=\emptyset$, then $f(q)$ can be chosen arbitrarily.
Our result will depend on some simple properties of the min-tradeoff function,
namely the maximum and minimum of $f$, the minimum of $f$ over valid
distributions, and the maximum variance of $f$:

$\displaystyle\mathrm{Max}(f)$ $\displaystyle:=\max_{q\in\mathbb{P}}f(q),$
$\displaystyle\mathrm{Min}(f)$ $\displaystyle:=\min_{q\in\mathbb{P}}f(q),$
$\displaystyle\mathrm{Min}_{\Sigma}(f)$
$\displaystyle:=\min_{q:\Sigma(q)\neq\emptyset}f(q),$
$\displaystyle\mathrm{Var}_{\Sigma}(f)$
$\displaystyle:=\max_{q:\Sigma(q)\neq\emptyset}\sum_{c\in\mathcal{C}}q(c)f^{2}(\delta_{c})-(\sum_{c\in\mathcal{C}}q(c)f(\delta_{c}))^{2},$

and let $\mathrm{Min}_{\Sigma}(f)=-\infty,\mathrm{Var}_{\Sigma}(f)=\infty$ if
$\Sigma(q)=\emptyset$.

######  Theorem 2 (GEAT).

[24, Theorem 4.3] Consider a sequence of channels
$\mathcal{M}_{i}\in\mathrm{CPTP}(R_{i-1}E_{i-1},\allowbreak
C_{i}K_{i}R_{i}E_{i})$ for $i\in\\{1,\dots,n\\}$, where $C_{i}$ are classical
systems with common alphabet $\mathcal{C}$ and the sequence
$\\{\mathcal{M}_{i}\\}$ satisfies Eq. (23) and the non-signaling condition:
for each $\mathcal{M}_{i}$, there exists a channel
$\mathcal{R}_{i}\in\mathrm{CPTP}(E_{i-1},E_{i})$ such that
$\Tr_{K_{i}R_{i}C_{i}}\circ\mathcal{M}_{i}=\mathcal{R}_{i}\circ\Tr_{R_{i-1}}$.
Let $\epsilon\in(0,1)$, $\alpha\in(1,3/2)$, $\Omega\subset\mathcal{C}^{n}$,
$\rho_{R_{0}E_{0}}$ is the initial state entering the sequence of channels,
and $f$ be an affine min-tradeoff function with
$h=\min_{c^{n}\in\Omega}f(\mathrm{freq}_{c^{n}})$. Then,

$H_{\mathrm{min}}^{\epsilon}(K^{n}|E_{n})_{\mathcal{M}_{n}\circ\dots\circ\mathcal{M}_{1}(\rho_{R_{0}E_{0}})_{|\Omega}}\\\
\geq n\,h-n\,\frac{\alpha-1}{2-\alpha}\,\frac{\ln(2)}{2}V^{2}\\\
-\frac{g(\epsilon)+\alpha\log(1/\Pr_{\rho}[\Omega])}{\alpha-1}-n\,\left(\frac{\alpha-1}{2-\alpha}\right)^{2}K^{\prime}(\alpha)\,,$
(26)

where $\Pr[\Omega]$ is the probability of observing event $\Omega$, and with
$d_{K}=\max_{i}\dim(K_{i})$,

$\displaystyle g(\epsilon)$ $\displaystyle=-\log(1-\sqrt{1-\epsilon^{2}})\,,$
$\displaystyle V$
$\displaystyle=\log(2d_{A}^{2}+1)+\sqrt{2+\mathrm{Var}{f}}\,,$ $\displaystyle
K^{\prime}(\alpha)$ $\displaystyle=\frac{(2-\alpha)^{3}}{6(3-2\,\alpha)^{3}\ln
2}\,2^{\frac{\alpha-1}{2-\alpha}(2\log
d_{A}+\mathrm{Max}{f}-\mathrm{Min}_{\Sigma}(f))}$
$\displaystyle\quad\cdot\ln^{3}\left(2^{2\log
d_{A}+\mathrm{Max}{f}-\mathrm{Min}_{\Sigma}(f)}+e^{2}\right).$

##  Appendix E Construction of min-tradeoff function

Our construction of the min-tradeoff function is based on the idea of the
Lagrange dual function of the optimization problem for the single-round
entropy [51, 16].

The Lagrange dual function for the $i^{\mathrm{th}}$ SDP inside the summation
of Eq.(17) is

$\displaystyle g_{i}(w_{\mathrm{exp}},w_{\mathrm{tol}},\eta_{\mathrm{z}})=$
$\displaystyle\sup_{\vec{\lambda}_{\mathrm{win}}^{i},\vec{\lambda}_{\mathrm{z}}^{i}}\min_{M,N,Z^{i}}F_{i}(M,N,Z^{i})$
(27)
$\displaystyle-\lambda_{\mathrm{win,1}}^{i}\left(\expectationvalue{\Gamma_{\mathrm{win}}(M,N)}-w_{\mathrm{exp}}+w_{\mathrm{tol}}\right)$
$\displaystyle+\lambda_{\mathrm{win,2}}^{i}\left(\expectationvalue{\Gamma_{\mathrm{win}}(M,N)}-w_{\mathrm{exp}}-w_{\mathrm{tol}}\right)$
$\displaystyle-\vec{\lambda}_{\mathrm{z}}^{i}\cdot\left(\vec{\eta}_{\mathrm{z}}-\expectationvalue{\vec{\Gamma}_{\mathrm{z}}(M,N)}\right),$

where $\vec{\lambda}_{\mathrm{win}}$ and $\vec{\lambda}_{\mathrm{z}}$ are dual
variables, $M$ and $N$ denote the sets of POVMs $\\{M^{a}_{x}\\}_{ax}$ and
$\\{N^{b}_{y}\\}_{by}$ and $Z^{i}=\\{Z^{i}_{ab}\\}_{ab}$,
$\Gamma_{\mathrm{win}}(M,N)=\sum_{abxy}M^{a}_{x}N^{b}_{y}$, and
$\Gamma_{\mathrm{zero,i}}=P(a_{i}b_{i}|x_{i}y_{i})$ for all
$(a_{i},b_{i}|x_{i},y_{i})\in\mathcal{S}_{\kappa}$.

Let $g_{\vec{\lambda}_{\mathrm{win}}^{i},\vec{\lambda}_{\mathrm{z}}^{i}}$ be
the function with given $\vec{\lambda}_{\mathrm{win}}^{i}$ and
$\vec{\lambda}_{\mathrm{z}}^{i}$. By the duality of SDP (Eq.(16)), we can
bound the von Neumann entropy with
$\\{g_{\vec{\lambda}_{\mathrm{win}}^{i,*},\vec{\lambda}_{\mathrm{z}}^{i,*}}\\}_{i}$:

$\inf_{M,N,Z}H(K|IE^{\prime})\geq c_{m}+\sum^{m-1}_{i=1}c_{i}\Xi^{*}_{i}\geq
c_{m}+\sum^{m-1}_{i=1}c_{i}g_{\vec{\lambda}_{\mathrm{win}}^{i,*},\vec{\lambda}_{\mathrm{z}}^{i,*}},$
(28)

where $\Xi^{*}_{i}$ denote the optimal solution of the corresponding SDP
(Eq.(17)) and
$g_{\vec{\lambda}_{\mathrm{win}}^{i,*},\vec{\lambda}_{\mathrm{z}}^{i,*}}$ is
the function with the optimal dual variables
$\vec{\lambda}_{\mathrm{win}}^{*}$ and $\vec{\lambda}_{\mathrm{z}}^{*}$. The
min-tradeoff function can be chosen as

$f(w_{\mathrm{exp}},w_{\mathrm{tol}},\eta_{\mathrm{z}})=c_{m}+\sum^{m-1}_{i=1}c_{i}g_{\vec{\lambda}_{\mathrm{win}}^{i,*},\vec{\lambda}_{\mathrm{z}}^{i,*}}.$

To simplify the expression of the min-tradeoff function, we first put
$\lambda_{\mathrm{win,1}}^{i}$ and $\lambda_{\mathrm{win,2}}^{i}$ together as
$\lambda_{\mathrm{win}}^{i}=\lambda_{\mathrm{win,1}}^{i}-\lambda_{\mathrm{win,2}}^{i}$,
and define
$\lambda_{\mathrm{win}}:=\sum^{m-1}_{i}c_{i}\lambda_{\mathrm{win}}^{i}$ and
$\vec{\lambda}_{\mathrm{z}}:=\sum^{m-1}_{i}c_{i}\vec{\lambda}_{\mathrm{z}}^{i}$.
The min-tradeoff function then becomes

$f(w_{\mathrm{exp}},w_{\mathrm{tol}},\eta_{\mathrm{z}})=c_{m}+\sum^{m-1}_{i=1}c_{i}\cdot\tilde{f}_{i}\\\
\approx\sup_{\\{\vec{\lambda}_{\mathrm{win}}^{i}\\}_{i},\\{\vec{\lambda}_{\mathrm{z}}^{i}\\}_{i}}\lambda_{\mathrm{win}}\cdot(w_{\mathrm{exp}}-w_{\mathrm{tol}})-\vec{\lambda}_{\mathrm{z}}\cdot\vec{\eta}_{\mathrm{z}}\quad+C_{\lambda_{\mathrm{win}},\vec{\lambda}_{\mathrm{z}}},$
(29)

where

$\displaystyle C_{\lambda_{\mathrm{win}},\vec{\lambda}_{\mathrm{z}}}$
$\displaystyle=c_{m}+\sum^{m-1}_{i=1}c_{i}\cdot\min_{M,N,Z^{i}}\Bigl{\\{}g_{i}(M,N,Z^{i})$
$\displaystyle-\lambda_{\mathrm{win}}^{i}\expectationvalue{\Gamma_{\mathrm{win}}(M,N)}+\vec{\lambda}_{\mathrm{z}}^{i}\cdot\expectationvalue{\vec{\Gamma}_{\mathrm{z}}(M,N)}\Bigr{\\}}.$

Here we drop the terms $-2\lambda_{\mathrm{win,2}}w_{\mathrm{tol}}$ by the
fact that taking out the constraint
$\expectationvalue{\Gamma_{\mathrm{win}}(M,N)}\leq
w_{\mathrm{exp}}+w_{\mathrm{tol}}$ from Eq.(17) does not significantly affect
the optimal solution, that is
$\lambda_{\mathrm{win,2}}\ll\lambda_{\mathrm{win,1}}$ and also
$w_{\mathrm{tol}}<w_{\mathrm{exp}}$. Finally, given
$w_{\mathrm{tol}},\eta_{\mathrm{z}}\in(0,1)$, and let
$\nu=w_{\mathrm{exp}}-w_{\mathrm{tol}}$, we construct the min-tradeoff
function as

$f(\nu)=\lambda_{\mathrm{win}}\cdot\nu-\vec{\lambda}_{\mathrm{z}}\cdot\vec{\eta}_{\mathrm{z}}+C_{\lambda_{\mathrm{win}},\vec{\lambda}_{\mathrm{z}}}.$
(30)

To further simplify the last term,
$C_{\lambda_{\mathrm{win}},\vec{\lambda}_{\mathrm{z}}}$, we consider the
maximum winning probability and minimum zero probability among all the $(m-1)$
optimizations:

$\displaystyle\gamma_{\mathrm{win}}^{*}$
$\displaystyle=\max_{i}\gamma_{\mathrm{win}}^{i},$
$\displaystyle\gamma_{\mathrm{zero,j}}^{*}$
$\displaystyle=\min_{i}\gamma_{\mathrm{zero,j}}^{i},\
j=1,...|\mathcal{S}_{\kappa}|,$

where $\gamma_{\mathrm{win}}^{i}$ is the winning probability
$\expectationvalue{\Gamma_{\mathrm{win}}(M,N)}$ evaluated after solving the
$i$th optimization problem, and
$\gamma_{\mathrm{zero,j}}^{i}=P(a^{\prime}b^{\prime}|x^{\prime}y^{\prime})=\expectationvalue{\Gamma_{\mathrm{zero,j}}(M,N)}$
denotes the probability of the input-output combination
$(a^{\prime},b^{\prime},x^{\prime},y^{\prime})\in\mathcal{S}_{\kappa}$
evaluated after solving the $i$th optimization problem. Using the following
facts:

$\displaystyle-\sum^{m-1}_{i=1}c_{i}\lambda_{\mathrm{win}}^{i}\gamma_{\mathrm{win}}^{i}$
$\displaystyle\geq-\sum^{m-1}_{i=1}c_{i}\lambda_{\mathrm{win}}^{i}\gamma_{\mathrm{win}}^{*}=-\lambda_{\mathrm{win}}\gamma_{\mathrm{win}}^{*},$
$\displaystyle\sum^{m-1}_{i=1}c_{i}\vec{\lambda}_{\mathrm{z}}^{i}\cdot\vec{\gamma}_{\mathrm{z}}^{i}$
$\displaystyle\geq\sum^{m-1}_{i=1}c_{i}\vec{\lambda}_{\mathrm{z}}^{i}\cdot\vec{\gamma}_{\mathrm{z}}^{*}=\vec{\lambda}_{\mathrm{z}}\cdot\vec{\gamma}_{\mathrm{z}}^{*}.$

We obtain a shortened expression for
$C_{\lambda_{\mathrm{win}},\vec{\lambda}_{\mathrm{z}}}$:

$C_{\lambda_{\mathrm{win}},\vec{\lambda}_{\mathrm{z}}}=-\lambda_{\mathrm{win}}\gamma_{\mathrm{win}}^{*}+\vec{\lambda}_{\mathrm{z}}\cdot\vec{\gamma}_{\mathrm{z}}^{*}+c_{m}+\sum^{m-1}_{i=1}c_{i}\cdot\Xi_{i}^{*}.$
(31)

##  Appendix F Cross-over min-tradeoff function

To properly account for how the statistics observed would extend to the non-
testing (generation) rounds, we need to modify the min-tradeoff function to
the so-called “crossover” min-tradeoff function [39] that weighs the
contributions from both testing and generation rounds. By the requirement that
the properties of the min-tradeoff function have to hold for the testing-round
channel, we can construct the crossover min-tradeoff function associated with
the testing ratio $\gamma$ [39, 19, 16].

######  Lemma 3 (Crossover min-tradeoff function [19]).

Let $\mathcal{C}=\\{0,1\\}$,
$\mathcal{C}^{\prime}=\mathcal{C}\cup\\{\perp\\}$, and
$q\in\mathbb{P}(\mathcal{C})$,
$q^{\prime}\in\mathbb{P}(\mathcal{C}^{\prime})$, where
$q^{\prime}(\perp)=(1-\gamma)$ and $q^{\prime}(c)=\gamma q(c)$. The crossover
min-tradeoff function corresponding to the infrequent-sampling channel
$\mathcal{M}_{i}$ with sampling (testing) probability $\gamma$ is

$\displaystyle
f_{\gamma}(\delta_{c})=\begin{cases}\frac{1}{\gamma}f(\delta_{c})+(1-\frac{1}{\gamma})f_{\perp}&c\in\mathcal{C}/\\{\perp\\},\\\
f_{\perp}&c=\perp,\end{cases}$ (32)

which satisfies

$\displaystyle
f_{\gamma}(q^{\prime})=\sum_{c\in\mathcal{C}^{\prime}}q^{\prime}(c)f_{\gamma}(\delta_{c})$
(33)
$\displaystyle=(1-\gamma)f_{\perp}+\gamma\sum_{c\neq\perp}q(\delta_{c})(\frac{1}{\gamma}f(\delta_{c})+(1-\frac{1}{\gamma})f_{\perp})=f(q),$

where $f_{\perp}\in[\mathrm{Min}(f),\mathrm{Max}(f)]$ can be chosen so that it
optimizes the extractable rate.

######  Lemma 4 (Properties of the crossover min-tradeoff function).

The properties of the crossover min-tradeoff function defined in Lemma 3 can
be parameterized as follows.

$\displaystyle\mathrm{Max}(f_{\gamma})$
$\displaystyle=(1-\frac{1}{\gamma})\lambda\nu^{\prime}+\frac{\lambda}{\gamma}+C_{\lambda},$
(34) $\displaystyle\mathrm{Min}_{\Sigma^{\gamma}}(f_{\gamma})$
$\displaystyle\geq(1-w_{Q})\lambda+C_{\lambda},$
$\displaystyle\mathrm{Var}_{\Sigma^{\gamma}}(f_{\gamma})$
$\displaystyle=\max_{\nu\in[1-w_{Q},w_{Q}]}-\lambda^{2}(\nu-\nu_{0})^{2}+D,$

where the set of state
$\Sigma^{\gamma}(q)=\\{\omega_{A_{i}C_{i}R_{i}E_{i}\tilde{E}_{i-1}}=\mathcal{M}_{i}(\omega_{R_{i-1}E_{i-1}\tilde{E}_{i-1}})\mid\omega_{C_{i}}(c=\perp)=(1-\gamma),\
\omega_{C_{i}}(c\neq\perp)=\gamma q(c)\\}$, $w_{Q}=\frac{2+\sqrt{2}}{4}$,
$\nu_{0}=\frac{1}{2\gamma}+(1-\frac{1}{\gamma})\nu^{\prime}$, and
$D=\frac{\lambda^{2}}{4\gamma^{2}}+\frac{1}{\gamma}(1-\frac{1}{\gamma})\lambda^{2}(1-\nu^{\prime})\nu^{\prime}$
with $\nu^{\prime}\in[0,1]$.

###### Proof.

Following the steps shown in [19], we first write the properties of the
crossover min-tradeoff function as follows.

$\displaystyle\mathrm{Max}(f_{\gamma})$
$\displaystyle=\max\left\\{\frac{1}{\gamma}\mathrm{Max}(f)+(1-\frac{1}{\gamma})f_{\perp},f_{\perp}\right\\},$
(35) $\displaystyle\mathrm{Min}_{\Sigma^{\gamma}}(f_{\gamma})$
$\displaystyle=\mathrm{Min}_{\Sigma}(f),$
$\displaystyle\mathrm{Var}_{\Sigma^{\gamma}}(f_{\gamma})$
$\displaystyle=\max_{q:\Sigma^{\gamma}(q)\neq\emptyset}\gamma\sum_{c\neq\perp}q(c)f_{\gamma}^{2}(\delta_{c})+(1-\gamma)f_{\perp}^{2}-f^{2}(q).$

Since $f_{\perp}\in[\mathrm{Min}(f),\mathrm{Max}(f)]$, we redefine
$f_{\perp}=\lambda\nu^{\prime}+C_{\lambda}$ with $\nu^{\prime}\in[0,1]$. We
can simplify the first quantity.

$\displaystyle\mathrm{Max}(f_{\gamma})$
$\displaystyle=\max\left\\{\frac{1}{\gamma}(\lambda+C_{\lambda})+(1-\frac{1}{\gamma})f_{\perp},f_{\perp}\right\\}$
(36)
$\displaystyle=\max\left\\{f_{\perp}+\frac{1}{\gamma}(1-\nu^{\prime})\lambda,f_{\perp}\right\\}$
$\displaystyle=f_{\perp}+\frac{1}{\gamma}(1-\nu^{\prime})\lambda$
$\displaystyle=(1-\frac{1}{\gamma})\lambda\nu^{\prime}+\frac{\lambda}{\gamma}+C_{\lambda}.$

The third equation holds by the fact that $\gamma>0,\lambda>0$ and
$1-\nu^{\prime}\geq 0$.

For the second equation in Eq.(34), the minimum is taken over the set
$\Sigma^{\gamma}$, that the equality holds according to Eq.(33).

To prove the last equation in Eq.(34), first we compute the expression with a
summation:

$\displaystyle S=\sum_{c\neq\perp}q(c)f_{\gamma}^{2}(\delta_{c})=\nu
f_{\gamma}^{2}(\delta_{1})+(1-\nu)f_{\gamma}^{2}(\delta_{0})$
$\displaystyle=\nu\left[f_{\perp}+\frac{1}{\gamma}(1-\nu^{\prime})\lambda\right]^{2}+(1-\nu)\left(f_{\perp}-\frac{1}{\gamma}\nu^{\prime}\lambda\right)^{2}$
$\displaystyle=\nu\left[2f_{\perp}+\frac{1}{\gamma}(1-2\nu^{\prime})\lambda\right]\cdot\frac{\lambda}{\gamma}+\left(f_{\perp}-\frac{1}{\gamma}\nu^{\prime}\lambda\right)^{2}.$
(37)

The second line holds by the fact that

$\displaystyle f_{\gamma}(\delta_{1})$
$\displaystyle=\frac{1}{\gamma}(\lambda+C_{\lambda})+(1-\frac{1}{\gamma})f_{\perp}$
$\displaystyle=f_{\perp}+\frac{1}{\gamma}(1-\nu^{\prime})\lambda,$
$\displaystyle f_{\gamma}(\delta_{0})$
$\displaystyle=\frac{1}{\gamma}C_{\lambda}+(1-\frac{1}{\gamma})f_{\perp}$
$\displaystyle=f_{\perp}-\frac{1}{\gamma}\nu^{\prime}\lambda.$

For a distribution in the set $\Sigma^{\gamma}$, the winning probability
satisfies $\nu\in[1-w_{Q},w_{Q}]$, where $w_{Q}=(2+\sqrt{2})/4$. Put Eq.(37)
back to the third equation in Eq.(35), we have

$\displaystyle\mathrm{Var}_{\Sigma^{\gamma}}(f_{\gamma})=$
$\displaystyle\max_{\nu\in[1-w_{Q},w_{Q}]}\lambda\nu\left[2f_{\perp}+\frac{1}{\gamma}(1-2\nu^{\prime})\lambda\right]$
(38)
$\displaystyle+\gamma\left(f_{\perp}-\frac{1}{\gamma}\nu^{\prime}\lambda\right)^{2}+(1-\gamma)f^{2}_{\perp}-(\lambda\nu+C_{\lambda})^{2}$
$\displaystyle=$
$\displaystyle\max_{\nu\in[1-w_{Q},w_{Q}]}-\lambda^{2}\nu^{2}+\lambda^{2}\left[2\nu^{\prime}+\frac{1}{\gamma}(1-2\nu^{\prime})\right]\nu$
$\displaystyle+\left(f^{2}_{\perp}-2\nu^{\prime}\lambda
f_{\perp}+\frac{\nu^{\prime 2}\lambda^{2}}{\gamma}-C_{\lambda}^{2}\right).$

Eq.(38) is a quadratic function of $\nu$, and therefore we can rewrite it as

$\mathrm{Var}_{\Sigma^{\gamma}}(f_{\gamma})=\max_{\nu\in[1-w_{Q},w_{Q}]}-\lambda^{2}(\nu-\nu_{0})^{2}+D,$
(39)

where
$\nu_{0}=\nu^{\prime}+\frac{1}{\gamma}(\frac{1}{2}-\nu^{\prime})=\frac{1}{2\gamma}+(1-\frac{1}{\gamma})\nu^{\prime}$
and

$\displaystyle D=$ $\displaystyle
f^{2}_{\perp}-2\lambda\nu^{\prime}f_{\perp}+\frac{1}{\gamma}\lambda^{2}\nu^{\prime
2}-C_{\lambda}^{2}+\lambda^{2}\nu^{2}_{0}$ $\displaystyle=$
$\displaystyle(\lambda^{2}\nu^{\prime 2}+2\lambda
C_{\lambda}\nu^{\prime}+C_{\lambda}^{2})-2\lambda\nu^{\prime}(\lambda\nu^{\prime}+C_{\lambda})$
$\displaystyle+\frac{1}{\gamma}\lambda^{2}\nu^{\prime
2}-C_{\lambda}^{2}+\lambda^{2}\left[\frac{1}{2\gamma}+(1-\frac{1}{\gamma})\nu^{\prime}\right]^{2}$
$\displaystyle=$
$\displaystyle-\left(1-\frac{1}{\gamma}\right)\lambda^{2}\nu^{\prime 2}$
$\displaystyle+\lambda^{2}\left[\frac{1}{4\gamma^{2}}+\frac{1}{\gamma}(1-\frac{1}{\gamma})\nu^{\prime}+(1-\frac{1}{\gamma})^{2}\nu^{\prime
2}\right]$ $\displaystyle=$
$\displaystyle\frac{\lambda^{2}}{4\gamma^{2}}+\frac{1}{\gamma}(1-\frac{1}{\gamma})\lambda^{2}(1-\nu^{\prime})\nu^{\prime}.$

The last equation holds by combining
$-(1-\frac{1}{\gamma})\lambda^{2}\nu^{\prime 2}$ and
$(1-\frac{1}{\gamma})^{2}\lambda^{2}\nu^{\prime 2}$ together as
$-\frac{1}{\gamma}(1-\frac{1}{\gamma})\lambda^{2}\nu^{\prime 2}$. ∎

##  Appendix G Protocol security and finite rate lower bound

In Protocol 1, given $w_{\mathrm{exp}}\in[w_{C},w_{Q}]$, $\gamma\in(0,1]$,
$\nu^{\prime}\in[0,1]$, and
$\epsilon,w_{\mathrm{tol}},\eta_{\mathrm{z}},\beta\in(0,1)$, the lower bound
on the smooth min-entropy can be derived by directly applying the GEAT
(Theorem 2.)

$H_{\mathrm{min}}^{\epsilon}(K^{n}|I^{n}E^{\prime}_{n})\geq
h(w_{\mathrm{exp}}-w_{\mathrm{tol}})-\Delta.$ (40)

$\Delta$ is given below

$\displaystyle\Delta=$ $\displaystyle\frac{\ln 2}{2}\beta\left[\log
9+V\right]^{2}$
$\displaystyle-\frac{1}{n}\bigl{[}\frac{1+\beta}{\beta}\log(1-\sqrt{1-\epsilon^{2}})+\frac{1+2\beta}{\beta}\log\Pr[\Omega]\bigr{]}$
$\displaystyle-\frac{1}{6\ln
2}\frac{\beta^{2}}{(1-\beta)^{3}}\zeta^{\beta}\ln^{3}(\zeta+e^{2}),$

where $\beta=\frac{\alpha-1}{2-\alpha}=\frac{1}{2-\alpha}-1\in(0,1)$,
$V=\sqrt{2+D-\min_{\nu\in[1-w_{Q},w_{Q}]}\lambda^{2}(\nu-\nu_{0})^{2}}$,
$\gamma_{0}=\frac{1-\gamma}{\gamma}$,
$\nu_{0}=\frac{1}{2\gamma}-\gamma_{0}\nu^{\prime}$,
$D=\frac{\lambda^{2}}{4\gamma^{2}}-\frac{\gamma_{0}}{\gamma}\lambda^{2}(1-\nu^{\prime})\nu^{\prime}$,
$\zeta=2^{2+\lambda(\gamma_{0}(1-\nu^{\prime})+w_{Q})}$, and $H_{\mathrm{sh}}$
is Shannon entropy. For the CHSH game, $w_{C}=0.75$ and
$w_{Q}=(2+\sqrt{2})/4$.

###### Proof.

To map the systems described in Theorem 2, we first combine all the
statistical checks in the $i^{\mathrm{th}}$ round
$C_{i}=(C_{\omega,i},\vec{C}_{3b,i})$, where
$\vec{C}_{3b,i}=(C_{3b,i}[00|00],C_{3b,i}[11|00],C_{3b,i}[10|11])$. The system
records the adversary’s total side information as $E_{i}=I^{i}T^{i}E^{\prime
i}$, where $I_{i}$ contains all the classical side information except the
round mark for testing or generation $T^{i}$. Denote the devices’ internal
memory as $R_{i}$. The non-signaling condition can be verified by constructing
the map $\mathcal{R}_{i}\in\mathrm{CPTP}(E_{i-1},E_{i})$ with the isometries
creating Eve’s classical side information $I_{i}$.

Then by employing Theorem 2 with the properties of the min-tradeoff function
shown in Lemma 4, we can derive Eq.(40). ∎

To prove the security of the protocol, we need concentration inequality to
upper-bound the completeness. For convenience, we choose Hoeffding’s
inequality, while in principle other concentration inequalities, such as
Serfling’s inequality [52], Bernstein’s inequality [53], and Chernoff’s bound
[16], can also be used to derive the completeness bound.

Hoeffding’s inequality [54, Proposition 1.2] Consider a finite sequence
$x^{N}=x_{1}x_{2}...x_{N}$ with the mean $\mu=\frac{1}{N}\sum^{N}_{i=1}x_{i}$.
If the $n$ samples drawn without replacement from the sequence $x^{N}$ is
denoted by $X^{n}=X_{1}X_{2}...X_{n}$, then given $\epsilon>0$, we have

$\Pr[\frac{1}{n}\sum^{n}_{i=1}X_{i}-\mu\geq\epsilon]\leq\exp\left(-\frac{2n{\epsilon}^{2}}{{(b-a)}^{2}}\right),\\\
$ (41)
$\Pr[\mu-\frac{1}{n}\sum^{n}_{i=1}X_{i}\geq\epsilon]\leq\exp\left(-\frac{2n{\epsilon}^{2}}{{(b-a)}^{2}}\right),$
(42)

where $a=\min x_{i}$ and $b=\max x_{i}$.

######  Theorem 3 (Security of Protocol 1).

Protocol 1 Given the protocol parameters,
$(n,\gamma,w_{\mathrm{exp}},w_{\mathrm{tol}},\eta_{\mathrm{z}},\epsilon,\epsilon_{\mathrm{EXT}})$,
Protocol 1 is $\epsilon_{\mathrm{s}}$-sound and
$\epsilon_{\mathrm{c}}$-complete, where
$\epsilon_{\mathrm{s}}=\epsilon_{\mathrm{EXT}}+2\epsilon$ and
$\epsilon_{\mathrm{c}}=1-(1-e^{-2w_{\mathrm{tol}}^{2}n})(1-e^{-2\eta_{\mathrm{z}}^{\prime
2}n})^{n_{\mathrm{zero}}}$, $n_{\mathrm{zero}}$ is the number of zero-
probability constraints depending on the choice of the classes $\kappa$.

###### Proof.

Consider the event of non-aborting $\Omega=[\text{NonAbort}]=[\text{Pass win-
probability check}]\cup[\text{Pass zero-probability checks}]$. If any one of
the checks does not pass, then set the key register
$\rho_{K^{n}}=(|\perp\rangle\langle\perp|)^{\otimes n}$, where
$\bra{k^{n}}(\ket{\perp})^{\otimes n}=0$ for all $k^{n}\in\\{0,1\\}^{n}$. The
final state of Protocol 1 can be written as

$\rho_{K^{n}E}=\Pr[\Omega]\rho_{K^{n}E_{|\Omega}}+(1-\Pr[\Omega])(|\perp\rangle\langle\perp|)^{\otimes
n}\otimes\rho_{E_{|\neg\Omega}}.$ (43)

If the smooth min-entropy
$H_{\mathrm{min}}^{\epsilon}(K^{n}|E)_{\rho_{K^{n}E_{|\Omega}}}$ is lower-
bounded by $k_{\mathrm{EXT}}$, the soundness of Protocol 1 is guaranteed by
Lemma 1 after applying a $(k_{\mathrm{EXT}},\epsilon_{\mathrm{EXT}})$-strong
extractor

$\frac{1}{2}\|\rho_{K^{n}E_{|\Omega}}-\mu_{K}\otimes\rho_{E_{|\Omega}}\|_{1}\leq\epsilon_{\mathrm{EXT}}+2\epsilon,$
(44)

where $\mu_{K}=\frac{1}{|\mathcal{K}|}\mathds{1}$ is the maximally mixed state
on $\mathcal{H}_{K}$. And by the definition of soundness (Eq.(1)) and the fact
that $\Pr[\Omega]\leq 1$, we can choose
$\epsilon_{\mathrm{s}}=\epsilon_{\mathrm{EXT}}+2\epsilon$.

We derive the completeness by bounding the aborting probability due to the i)
check of the score $C_{\omega}^{n}$ and ii) check of the zero-probability
constraints $\vec{C}_{3b}^{n}$, taking $\kappa=3b$ for example 101010For other
classes, different the number of zero-probability constraints would
approximately give a different scaling parameter for the zero-probability
constraint related aborting probability..

By Heoffding’s inequality (42), let $c^{N}$ be the results of $N$ rounds of
the nonlocal game: $c_{i}=1$ ($c_{i}=0$) if the players win (lose) the
$i^{\mathrm{th}}$ round of the game. Take large enough $N$ such that the
statistics of $c^{N}$ reflect nearly the true probability distribution, and
$w_{\mathrm{exp}}=\mathbb{E}[c]$ is the expectation value of the winning
probability. If in the experiment, we only run $n$ rounds of the nonlocal game
and the results of that $n$ rounds as $C^{n}$. The aborting probability can be
upper-bounded by

$\Pr[\mathrm{aborted\ by\ score\
check}]=\Pr\left[\mu-\frac{1}{n}\sum_{i}C_{i}>w_{\mathrm{tol}}\right]\\\
\leq\epsilon_{\mathrm{c}}\leq e^{-2w_{\mathrm{tol}}^{2}n},$ (45)

where $\frac{1}{n}\sum_{i}C_{i}$ is the observed winning probability.

Similarly, let $c^{N}$ be the occurrence of one of the input-output
combinations $(a,b,x,y)\in\mathcal{S}_{\kappa}$ in $N$ rounds of the nonlocal
game. Take large enough $N$ such that the statistics of $c^{N}$ reflect nearly
the true probability distribution, and $\mu=\mathbb{E}[c]$ is close to the
expectation value of the probability, $P(a,b|x,y)$. If in the experiment, we
only run $n$ rounds of the nonlocal game, and denote the occurrence of
$(a,b,x,y)$ in that $n$ rounds as $C^{n}$. Then, the aborting probability due
to the zero probability check can be upper-bounded by applying Hoeffding’s
inequality (41),

$\Pr[\mathrm{aborted\ by\ one\ zero\ check}]\\\
=\Pr[\frac{1}{n}\sum_{i}C_{i}-\mu\geq\eta_{\mathrm{z}}^{\prime}]\leq
e^{-2\eta_{\mathrm{z}}^{\prime 2}n},$

where the equality $\mu+\eta_{\mathrm{z}}^{\prime}=\eta_{\mathrm{z}}$ holds
and $\eta_{\mathrm{z}}$ is the zero tolerance level for Protocol 1. Since
$\mu>0$ and $\eta_{\mathrm{z}}^{\prime}>0$, the value,
$\eta_{\mathrm{z}}^{\prime}$ is strictly smaller than $\eta_{\mathrm{z}}$.
Since there are three zero-probability constraints in class 3b, the effective
completeness for all the zero-probability checks can be bounded by

$\epsilon_{\mathrm{c}}^{\mathrm{z}}\leq 1-(1-e^{-2\eta_{\mathrm{z}}^{\prime
2}n})^{3}.$ (46)

Combine Eq.(45) and Eq.(46) together with the fact that for two events
$\Omega_{A}$ and $\Omega_{B}$,
$\Pr[\Omega_{A}\cap\Omega_{B}]\geq\Pr[\Omega_{A}]\Pr[\Omega_{B}]$, we have the
non-aborting probability conditioned on the honest behavior
$\Pr[NonAbort|Honest]\equiv\Pr[\Omega_{|Hon}]$:

$\displaystyle\Pr[\Omega_{|Hon}]$ $\displaystyle=\Pr[(\mathrm{pass\ win\
check})\cap(\mathrm{pass\ zero\ check})]$ (47)
$\displaystyle\geq\Pr[\mathrm{pass\ win\ check}]\Pr[\mathrm{pass\ zero\
check}]$ $\displaystyle=(1-\Pr[\mathrm{aborted\ by\ win\ check}])$
$\displaystyle\quad\cdot(1-\Pr[\mathrm{aborted\ by\ zero\ check}])$
$\displaystyle\geq(1-\epsilon_{\mathrm{c}}^{\mathrm{w}})(1-\epsilon_{\mathrm{c}}^{\mathrm{z}})$
$\displaystyle\geq(1-e^{-2w_{\mathrm{tol}}^{2}n})(1-e^{-2\eta_{\mathrm{z}}^{\prime
2}n})^{3}.$

We obtain the aborting probability of the protocol under the honest
implementation:

$\displaystyle\Pr[\mathrm{Abort}|\mathrm{Honest}]$
$\displaystyle=1-\Pr[\Omega_{|Hon}]$ (48) $\displaystyle\leq
1-(1-e^{-2w_{\mathrm{tol}}^{2}n})(1-e^{-2\eta_{\mathrm{z}}^{\prime 2}n})^{3}.$

∎

##  Appendix H Numerical implementation and results

Fix the protocol parameter $w_{\mathrm{tol}}=10^{-4}$ and $\epsilon=10^{-12}$.
Two variables still need to be optimized, i) $\nu^{\prime}$ from the
construction of crossover min-tradeoff function and ii) $\beta=$ which is
directly related to the order $\alpha$ of the $\alpha$-Renyi entropy. For each
fixed number of rounds $N$, we scan through the valid ranges,
$\nu^{\prime}\in[0,1]$ and $\beta\in(0,1)$, to find the values that lead to
the highest rates. As an illustration of this procedure, we plot the resulting
heat map in Fig 3 to show the optimization of $\beta$.

Figure 3: Scanning $\beta$ at optimal $\nu^{\prime}$. The hotter color
indicates a higher rate.

We use Eq.(47) to upper-bound the non-aborting probability $\Pr[\Omega]$
instead of
$1-\epsilon_{\mathrm{c}}^{\mathrm{w}}-\epsilon_{\mathrm{c}}^{\mathrm{z}}$, and
taking $\eta_{\mathrm{z}}^{\prime}=\eta_{\mathrm{z}}/2$ for convenience.

The comparison of Protocol 1, CHSH, and the $\delta$-family Bell inequality
[22] for single-party and blind randomness with maximal winning probability
are shown in Fig. 2.