[name=Theorem]thm [name=Lemma]lemm [name=Proposition]prop

# A coherence-based game and applications to semi-device-independent quantum
key distribution

Mário Silva  Université de Lorraine, CNRS, Inria, LORIA, F-54000 Nancy, France
<EMAIL_ADDRESS>Ricardo Faleiro<EMAIL_ADDRESS>Instituto
de Telecomunicações, 1049-001, Lisbon, Portugal  Paulo Mateus  Instituto de
Telecomunicações, 1049-001, Lisbon, Portugal  Departamento de Matemática,
Instituto Superior Técnico, Avenida Rovisco Pais 1049-001, Lisbon, Portugal
Emmanuel Zambrini Cruzeiro  Instituto de Telecomunicações, 1049-001, Lisbon,
Portugal
<EMAIL_ADDRESS>
###### Abstract

Semi-device-independent quantum key distribution aims at reaching a compromise
between the highest level of security, device-independence, and experimental
feasibility. Semi-quantum key distribution is an interesting approach whose
purpose is to reduce the quantum technological requirements of users, whilst
still guaranteeing security, in order to develop simple and hardware fault-
tolerant quantum key distribution protocols. In this work, we introduce a
coherence-based semi-quantum, semi-device-independent, quantum key
distribution protocol where users only need to implement classical operations
i.e. fixed basis detections, and prove its security in the bounded quantum
storage model. The protocol is based on the noise-robust version of a
coherence equality game that witnesses different types of coherence.

##  1 Introduction

Modern cryptosystems based on the hardness of computational assumptions are
vulnerable to developments of computational power and new algorithms,
particularly when considering quantum computers [1, 2]. Quantum cryptography
offers a solution to this problem by providing information security based on
the laws of quantum mechanics, so that protocols are resistant to any attack,
no matter how much computational power is allowed.

However, in a practical scenario, the users are usually incapable of verifying
that their devices follow the description of the protocol and must trust their
manufacturer. Not only could it be difficult to create devices that perfectly
satisfy the assumptions of the protocol, but it could also be the case that
the devices have been maliciously constructed. Quantum cryptography as
originally introduced, e.g. BB84 [3], had been predicated on assumptions about
the internal description of the physical systems, such as the source and
detectors, which opens the door to various side channel attacks. However, in
1998, Mayers and Yao put forth the concept of self-testing [4, 5], ensuring
that, if certain statistical tests are met, then the source could be
guaranteed to satisfy the desired assumptions, e.g. for quantum key
distribution (QKD). Thanks to this property, two users may certify on their
own whether their apparatus are functioning as they should. This is the key
idea behind device-independent (DI) QKD, which aims at unconditional security
in the presence of imperfect, or maliciously designed, devices.

DI QKD is the golden standard of QKD: it provides unconditional security based
on the laws of physics [6, 7]. Device-independence also finds other
applications in cryptography: random number generation [8, 9], position
verification [10], coin flipping [11], and authorization to private databases
[12]. DI QKD, for now, remains extremely challenging. The first proof-of-
principle experiments were performed only very recently [13, 14, 15], almost
40 years after the invention of BB84.

It then becomes naturally interesting to study scenarios which may reach a
compromise between experimental challenge and security: for example, by
assuming than the users have a partial description of the devices – say, one
device is trusted while the other is not. These are called semi-device-
independent (SDI) protocols. Existing approaches include: bounding the
dimension of the states [16, 17, 18, 19], bounding the expectation value of
some appropriate operator, e.g energy [20], bounding the information content
of quantum states [21, 22], or their overlap [23].

Another interesting question is whether all the aspects of a (semi-)device-
independent protocol must be quantum in order to guarantee security. Semi-
quantum (SQ) cryptography [24] attempts to answer this question. There, one is
interested in minimizing the quantum technological requirements of the systems
and/or users involved in the protocol without compromising security. One way
to do this is to limit Alice or Bob to a single measurement basis, for
instance, or force them to only perform detection or reflection of photons
[25, 26].

In this work, we take a first step towards the intersection of semi-device-
independent and semi-quantum protocols. The security proof for our QKD
protocol relies on specific properties of the detection operators used by
Alice and Bob in their respective labs, but the source and measurements
controlled by the outside servers remain unspecified, and Alice and Bob need
only to implement simple single-basis measurements.

The protocol is based on a generalization of the Coherence Equality (CE) game
introduced by del Santo and Dakić [27] to a noise-robust version. The security
of the protocol is obtained from the optimal quantum bounds of the users’
performance in the game [8], constrained by a noise parameter, in order to
prevent the use of resources that trivialize the game.

We can consider two equivalent alternatives of constraining the resource from
the noise parameter. In the first, we bound Alice’s and Bob’s detection
probabilities in the first stage of the protocol when both decide to measure
the particle. In the second, we implement the constraint directly on the
elements of the density matrix describing the quantum state. We adopt the
latter description in order to compute the lower and upper bounds of the CE
game, but we define the QKD protocol according to the former since it is the
actual approach that the users would operationally verify the constraint in a
semi-device-independent and semi-quantum way.

The paper is organized as follows. In Section 2, we introduce the scenario and
describe the quantum correlations it exhibits, namely we determine the optimal
quantum bounds using lower [28] and upper bounding techniques. We further
interpret the game as a coherence witness, and discuss the role of randomness
in the game. In Section 3, we introduce the SDI SQKD protocol and prove the
security of the protocol in the bounded quantum storage model. Finally, we
present our conclusions in Section 4.

##  2 The Coherence Equality game

###  2.1 Scenario and basic definitions

The scenario is depicted in Fig.1. An untrusted source sends a (quantum) state
$\rho_{\text{AB}}$ to Alice and Bob’s labs. Alice and Bob are allowed to
perform a local single basis measurement on their side of the system, where
they either block the path possibly taken by the particle, or leave it
undisturbed. Their actions are governed by random bits $x$ and $y$,
respectively for Alice and Bob, such that $0$ corresponds to leaving the path
undisturbed and $1$ to blocking it. In the case where they block the path,
they use a single photon detector to determine whether any particles were
present on their side, or not. This information is given by output bits
$\alpha,\beta$, for Alice and Bob, respectively, — where $0$ corresponds to no
particle detected and $1$ to at least one particle detected. Finally, Alice
and Bob either send their part of the initial system undisturbed, or a vacuum
state produced from blocking, to the untrusted servers $S_{A},S_{B}$,
respectively, where a generalized quantum measurement can be performed. The
final measurements then produce outcomes $a,b$, for Alice, Bob, respectively,
and they win the game if $a\oplus b=x\oplus y$. The statistics of such an
experiment can be described by a probability distribution $p(ab|xy)$, and we
consider the following linear functional of the probabilities, giving the
winning probability of the game

$P_{\text{win}}:=\frac{1}{4}\sum_{x,y}\mathbf{1}_{a\oplus b=x\oplus
y}\,p(ab|xy),$ (1)

where $\mathbf{1}_{F}$ is 1 whenever $F$ holds and 0 otherwise.

Figure 1: Diagram of the Coherence Equality game, for each of the four equally
probable detection configurations: Alice and Bob do not try to detect, for
$x=y=0$ (top-left); Alice tries to detect and Bob does not, for $x=1$ and
$y=0$ (top-right); Bob tries to detect and Alice does not, for $x=0$ and $y=1$
(bottom-left); Alice and Bob both try to detect, for $x=y=1$ (bottom-right).
The detections occur inside the trusted labs of each player (light gray
regions), and are represented by the blocks in dark gray. The detection
process has two input states: the unknown state from the source and an
ancillary input state, always initialized at $0$; and a single output given by
the classical bit ($\alpha$ for Alice and $\beta$ for Bob), informing if the
detection was successful or unsuccessful. When the detection is attempted,
whether it may be successful or not, the quantum system is blocked from its
original path (represented by the ground symbol) and a vacuum state
$\outerproduct{0}{0}$ is communicated to the servers instead. In the case
where no detection is attempted, the original state proceeds undisturbed to
the untrusted servers, and the classical system remains unchanged. The servers
$S_{A},S_{B}$ are constrained by the no-signalling condition which forbids
them from communicating their final measurement results, i.e bits $a,b$, but
can have shared randomness or entanglement.

There are some noticeable differences between our setup and the original setup
of del Santo and Dakić [27]. To start, in the original setup Alice and Bob
perform the final measurements, whereas the blocking is done by some neutral
Referees. In our case, since we want to limit the powers of Alice and Bob, we
have placed them in the role of randomly blocking the channels, whereas some
untrusted servers $S_{A}$ and $S_{B}$ can perform the final measurements.
Furthermore, Alice and Bob receive one bit of information each when
blocking/detecting. Finally, and more crucially, in [27] it was assumed that
the source was verified and only outputted a single photon, meaning that there
was exactly a single photon shared between the labs. Instead, here, we
consider the possibility of an untrusted source outputting any number of
photons, thus allowing more than one photon per and between labs. Alice and
Bob will constrain these multi-photon correlations that may arise through a
statistical constraint, called the single-detection constraint. This
constraint can be operationally verified via their detection results, when
both attempt a detection inside their lab.

###  2.2 The game in two stages

The game can naturally be separated into two stages. In the first stage, Alice
or Bob may choose to detect their particle. They use single-particle detectors
that only need to reliably distinguish between vacuum and non-vacuum states.
These measurements can be represented by the detection operators
$D_{\alpha|x},D_{\beta|y}$ where, for $x,y=1:$

$\left\\{D_{0|1}=\outerproduct{0}{0};\;D_{1|1}=\sum_{i=1}^{i=d}\outerproduct{i}{i}\right\\}$
(2)

where $d$ corresponds to the number of photons allowed per lab, which implies
a $d+1$ dimensional system in each lab, that is, taking into account the
vacuum state. It should be noted that since the measurements are destructive,
whenever a detection is attempted the post-measurement state will be always
set to $\outerproduct{0}{0}$, regardless of the particular outcome observed
(see Fig. 1).

When the users choose not to block ($x,y=0$), they simply act with the
appropriately normalized identity operator on their subsystems,

$D_{0|0}=\frac{\mathds{1}}{d+1}$ (3)

Therefore, after passing through Alice’s and Bob’s labs, for inputs $x,y$, the
original state $\rho_{AB}$ is transformed into $\rho_{xy}$, for
$\rho_{00}=\rho_{AB};\;\rho_{01}=\Tr_{B}{(\rho_{AB})}\otimes\outerproduct{0}{0}_{B};\;\rho_{10}=\outerproduct{0}{0}_{A}\otimes\Tr_{A}{(\rho_{AB})};\;\rho_{11}=\outerproduct{0}{0}_{A}\otimes\outerproduct{0}{0}_{B}$.
In this way, the coherence equality game can alternatively be understood as a
game played by the servers, where they receive quantum inputs instead of
classical ones, which accounts for the difficulty of computing the equality
$a\oplus b=x\oplus y$, otherwise trivial for classical inputs.

The probability distribution describing the statistics for this first step of
the protocol via the Born rule, is defined as

$\tilde{p}(\alpha\beta|xy)=\text{Tr}[\rho D_{\alpha|x}\otimes D_{\beta|y}].$
(4)

Furthermore, the single-detection condition will appropriately constrain some
of the probability distributions, namely it demands that,

$\tilde{p}(1,1|1,1)\leq d_{\epsilon}.$ (5)

That is, the probability of both Alice and Bob detecting a non-vacuum state in
each of their labs is bounded by $d_{\epsilon}$. Thus, in our scenario, we
consider general multi-photon states by replacing the single-particle
condition with a single-detection condition, which can be verified by the
users.

In the second stage of the game the state $\rho_{xy}$ is forwarded to the
external servers $S_{A}$ and $S_{B}$, where each server may apply a Positive
Operator-Valued Measure (POVM), which is a set of positive semidefinite
operators $\\{A_{a}\\}_{a=1}^{A}$ for Alice’s server, and
$\\{B_{b}\\}_{b=1}^{B}$ for Bob’s, that sum to the identity.

$\displaystyle A_{a}\geq 0,\quad\forall
a,\qquad\sum_{a=1}^{n_{A}}A_{a}=\mathds{1},$ (6) $\displaystyle B_{b}\geq
0,\quad\forall b,\qquad\sum_{b=1}^{n_{B}}B_{b}=\mathds{1}$ (7)

where $n_{A},n_{B}$ are the number of possible outcomes for each POVM,
respectively.

Finally, for this stage the probability distribution is computed via the Born
rule as,

$p(ab|xy)=\text{Tr}[\rho_{xy}A_{a}\otimes B_{b}]$ (8)

The problem we wish to solve is to maximize the linear functional Eq. (1) over
the states and POVMs. This represents an instance of Semidefinite Programming
(SDP), and can therefore be efficiently solved for a fixed dimension $d$.

In the following paragraph we describe an equivalent formulation of the single
detection constraint, which will provide a useful perspective for the
calculation of the quantum bounds.

Regarding the constraint imposed by Eq. (5), one can alternatively consider
that the above condition imposes a direct constraint on the elements of the
state $\rho^{(d)}$, describing $d-$photons per lab, instead of restricting the
first-stage operational statistics. This will be fruitful to optimize the
quantum model (over states and measurements) in order to find the maximum
winning probability of the CE game. According to this perspective, we omit
from the description the outcomes $\alpha$, $\beta$, and merely use the
blocking operators to create the four states $\rho_{xy}$, from a state
$\rho^{(d)}$ having some appropriate matrix elements bounded. The elements we
wish to bound in $\rho^{(d)}$ are $\\{\rho_{(i,i)}|\;i\in\mathcal{I}_{d}\\}$,
where $\mathcal{I}_{d}$ is a set that specifies the amplitude elements
corresponding to more than one excitation per party for the $d$ photon case,
i.e.

$\mathcal{I}_{d}=\left\\{\left[\alpha(d+1)+2,(\alpha+1)(d+1)\right]|\;\alpha\in[d]\right.\\}.$

The single-detection constraint will then bound the sum of those elements,
i.e.

$\sum_{i\in\mathcal{I}_{d}}\rho_{i,i}\leq d_{\epsilon}.$ (9)

That is, it demands that the total probability of having simultaneously non-
vacuum states in each lab is bounded. It is easy to show that for a generic
two-qubit state (i.e. $d=1$), this constraint yields $\rho_{(4,4)}\leq
d_{\epsilon}$, where $\rho_{(4,4)}$ is the element corresponding to the state
$\outerproduct{11}{11}$. Furthermore, if we demand that $d_{\epsilon}=0$ then
this leads to $\rho_{(4,4)}=0$, which recovers the single-particle condition.

###  2.3 Boundary of the quantum set

The most general bi-partite pure state in an $n\otimes n$ dimensional Hilbert
space is given by

$\ket{\Psi_{n}}=C_{00}\ket{00}+\sum_{i\in[n]}C_{i0}\ket{i0}+\\\
\sum_{j\in[n]}C_{0j}\ket{0j}+\sum_{i,j\in[n]\times[n]}C_{ij}\ket{ij}.$ (10)

It is straightforward to see that the ideal strategy for coherence equality
game requires one photon per lab, since it is the most economical way to
guarantee that Alice and Bob win with certainty. In fact, having more than one
photon in each lab is inconsequential for the performance in the coherence
equality game — say, either Alice and Bob have one photon each, in which case
they always win and thus dispense the need for more photons, or if Alice does
not have any photons in her lab, then regardless of whether Bob has just a
single photon or more they can only win half the time since Alice’s best
strategy will always be a random guess. This suggests that, in the quantum
case one can consider a simpler state than the previous general state as an
equivalent resource, obtained by assuming that any $\ket{n}$ for $n\geq 1$ can
be mapped to $\ket{1}$, yielding a general two-qubit pure state,

$|\psi\rangle=c_{00}|00\rangle+c_{01}|01\rangle+c_{10}|10\rangle+c_{11}|11\rangle$
(11)

where $|c_{00}|^{2}+|c_{01}|^{2}+|c_{10}|^{2}+|c_{11}|^{2}=1$, and
$|c_{00}|^{2}=|C_{00}|^{2},|c_{10}|^{2}=\sum_{i}|C_{i0}|^{2},|c_{10}|^{2}=\sum_{j}|C_{0j}|^{2},$
and $|c_{11}|^{2}=\sum_{i,j}|C_{ij}|^{2}$. Indeed, qubits are optimal in our
problem, thus there is no loss of generality by considering Eq. (11),
something we verified this numerically for small dimensions.

We intend to maximise Eq. (1). First, we note that real states and
measurements are sufficient for optimality, as in the case of Bell
inequalities [29, 30].

Additionally, note that for fixed $d_{\epsilon}$, the strongest correlations
can be achieved with a state that saturates the constraint $\rho_{44}\leq
d_{\epsilon}$. Indeed, reducing $\rho_{44}$ can only lead to weaker
correlations. It is straightforward to note this since for the problem at hand
$|11\rangle$ is optimal, i.e. achieves 100$\%$ success probability.

Furthermore, we assume Alice and Bob use the same measurement operators111Note
this marks a strong difference between the CE game and Bell nonlocal games,
where in the latter non-commuting measurements are typically required for
optimality of a quantum behaviour., described by the following equatorial
projections on the Bloch sphere

$M_{a}=\frac{1}{2}\Big{(}\mathds{1}+(-1)^{a}(n_{x}X+\sqrt{1-n_{x}^{2}}Z)\Big{)},$
(12)

where we have used the fact that $n_{z}=\sqrt{1-n_{x}^{2}}$, since for
equatorial projections $n_{y}=0$. Finally, we assume that $c_{01}=c_{10}$,
since the game is symmetric with respect to both the players’ and servers’
operations and outputs.

We have verified that all the above assumptions give rise to the optimal
solution using the SDP solver SDPT3 [31]. Taking all of them into account, the
simplest form of an optimal state to play the CE game is given by

$c_{00}|00\rangle+c_{01}(|01\rangle+|10\rangle)+\sqrt{d_{\epsilon}}|11\rangle.$
(13)

Using the simplified form of the state and of the measurement, the
optimization problem reduces to

$\displaystyle P_{\text{win}}$
$\displaystyle=\frac{1}{8}\Big{[}2c_{00}\sqrt{d_{\epsilon}}n_{x}^{2}-8c_{01}\sqrt{d_{\epsilon}}n_{x}\sqrt{1-n_{x}^{2}}$
$\displaystyle-(1+3d_{\epsilon})(n_{x}^{2}-2)+4c_{01}^{2}(1+n_{x}^{2})$
$\displaystyle+c_{00}^{2}(2+n_{x}^{2})\Big{]}$ (14)

subject to

$c_{00}^{2}+2c_{01}^{2}=1-d_{\epsilon}.$ (15)

The problem can be readily converted into a polynomial optimization problem,
which can then be efficiently solved using lower and upper bounding
procedures, thereby ensuring convergence to a global maximum. We use an SDP
see-saw [32] for the lower bounds, and YALMIP [33] for the upper bounds, to
show optimality of our results. The boundary of the quantum set is given by
the full line shown in Fig. 2.

Figure 2: Optimal quantum bounds for the winning probability give by different
types of coherent resources. The dotted line corresponds to the classical,
non-coherent, case. The dashed line is the optimal bound for separable
coherent states. Finally, the full line shows the optimum, attained using
entangled coherent states.

###  2.4 Coherence witness and analytic solutions

Through the introduction of the $d_{\epsilon}$ parameter, we are able to
identify three distinct classes of coherence resources which form a strict
hierarchy in terms of their performance in the CE game. The three classes are:

  1. 1.

Entangled coherent states:

$\sqrt{x(d_{\epsilon})}\ket{00}+{\sqrt{d_{\epsilon}}\ket{11}}\\\
+\sqrt{\frac{1-d_{\epsilon}-x(d_{\epsilon})}{2}}\left(\ket{01}+\ket{10}\right).$
(16)

  2. 2.

Separable coherent states:

$(\sqrt{1-{d_{\epsilon}}}\ket{0}+\sqrt{d_{\epsilon}}\ket{1}){\otimes\ket{1}}.$
(17)

  3. 3.

Mixed non-coherent states:

$({1-d_{\epsilon}})\outerproduct{10}{10}+d_{\epsilon}\outerproduct{11}{11}.$
(18)

For the entangled coherent states (Eq.16), $x(d_{\epsilon})$ represents the
analytic expression of a function of $d_{\epsilon}$ obtained by solving the
equations in Appendix A.

In this way, the game can also be interpreted as coherence witness, allowing
the certification between three different types of coherence resources, as
given by Alice and Bob’s ability to win the game and $d_{\epsilon}$. Although
the type of coherence witnessed is not basis-invariant [34, 35], as it
pertains a basis of occupation modes and is not invariant under unitaries, it
may still be of interest since a description in terms of occupation modes is
naturally adopted when analysing quantum optics experiments.

It is worthy to point out that for $d_{\epsilon}=0$, separable coherent and
mixed non-coherent states reduce to pure non-coherent states, meaning that the
previous resources can only be defined for positive values of $d_{\epsilon}$,
and that only entangled coherent states and pure non-coherent states were
considered in the original model [27] i.e. for $d_{\epsilon}=0$. In Fig. 3 we
show how the entanglement of the optimal coherent states behaves as a function
of $d_{\epsilon}$. The entanglement is maximum for $d_{\epsilon}=0$,
corresponding to the state $\ket{\psi}=(\ket{01}+\ket{10})/{\sqrt{2}}$, and
reaches zero for $d_{\epsilon}=1$ corresponding to the separable state
$\ket{11}$.

Figure 3: The entropy of entanglement, measured in bits, of the optimal
entangled coherent states that reach the maximum winning probability (the
solid line in Figure 2), as a function of $d_{\epsilon}$.

Regarding the separable coherent states and mixed non-coherent states,
trivially they will have no entanglement for any value of $d_{\epsilon}$. As
such, only the entangled coherent states can give rise to genuine randomness,
and only these will be useful for the purposes of the QKD protocol we present
next. We show this explicitly in Fig. 5 by plotting the relationship between
$H_{min}$ as a function of the winning probability, for various values of
$d_{\epsilon}$.

###  2.5 Randomness in the CE game

As we have seen, for certain values of $d_{\epsilon}$ and $P_{\text{win}}$ the
game can certify that the source is sending a particle in a superposition to
Alice and Bob’s labs, that is, an entangled coherent state is being used as a
resource. This suggests that, in this case, Alice and Bob’s detection outcomes
may have some randomness. In order to verify this, we employ SDP techniques to
maximize Alice’s (or alternatively Bob’s) marginal probability when she
attempts a detection, i.e. $p(\alpha|x=1)$, as a function of the winning
probability $P_{\text{win}}$ and $d_{\varepsilon}$. The maximum of the
marginal will also be an upper-bound on the guessing probability of an
adversary, which we refer to as $P_{g}(P_{\text{win}},d_{\epsilon})$. The
bounds are presented in Fig.4.

Figure 4: Upper bound on the guessing probability of Alice’s outcome, as a
function of $P_{\textup{win}}$ up to
$\textup{Max}(P_{\textup{win}}(d_{\epsilon}))$, for $d_{\epsilon}$ taking
values $0,0.01,0.05,0.1,0.2,$ and $0.5$, from left to right.

We verify that for values of the winning probability that surpass the
separable-coherent bound, at which point one requires entanglement, the
detection of a particle by Alice becomes random, and the greater the gap from
the separable-coherent bound the less predictable it is. Also, this
relationship is stronger for smaller values of the noise-parameter
$d_{\epsilon}$. Alternatively this bound can be represented by the min-
entropy,
$H_{\min}(P_{\textup{win}},d_{\epsilon})=-\log_{2}(P_{g}(P_{\text{win}},d_{\epsilon}))$,
and is plotted in Figure 5.

Figure 5: Randomness shared between Alice and Bob, measured in bits by the
min-entropy ($H_{\min}$), as a function of $P_{\textup{win}}$ up to
$\textup{Max}(P_{\textup{win}}(d_{\epsilon}))$, for $d_{\epsilon}$ taking
values $0,0.01,0.05,0.1,0.2,$ and $0.5$, from left to right.

The min-entropy takes positive values precisely when the probability surpasses
the optimal bound achievable by the separable coherent resources. These
results highlight an important feature of the game, that a set of state and
measurements $(\rho,M_{A}^{a},M_{B}^{b})$ picked by some adversary cannot
simultaneously be used to win the CE game arbitrarily well and allow the
outcomes $\alpha$ and $\beta$ to be completely predictable. We capture this
feature of the game in the following proposition.

proplemmasdpNoGo Consider $P_{g}(P_{\text{win}},d_{\epsilon})$, the upper-
bound on an adversary guessing probability of the players’ detection outcomes.
Then, for any given round $i$ in the protocol, the following three conditions
cannot simultaneously hold:

  1. 1.

The no-signalling condition is satisfied and our assumptions for Alice’s and
Bob’s detectors are correct.

  2. 2.

The set $S_{i}=(\rho,M_{A}^{a},M_{B}^{b})_{i}$ of the state and measurement
operators picked by an adversary wins game with probability at least
$P_{\text{win}}$, and satisfies the single-detection condition with
probability at least $1-d_{\epsilon}$.

  3. 3.

There is an outcome $\alpha^{\prime}\in\\{0,1\\}$ such that
$p(\alpha=\alpha^{\prime}|x=1)>P_{g}(P_{\text{win}},d_{\epsilon})$.

###### Proof.

The first condition is assumed to hold in a correct implementation of the
setup, under which the incompatibility between the second and third conditions
comes directly from the bounds on the detection probability (see Fig.4 and
Fig.5). ∎

##  3 QKD protocol

The protocol consists of $m$ rounds (with indices in
$[m]\equiv\\{1,\dots,m\\}$), where Alice and Bob uniformly and randomly choose
their respective inputs, $x,y\in\\{0,1\\}$. The set $\mathbf{D}$ consists of
the indices of the rounds where both Alice and Bob chose to attempt detection,
i.e. $x=y=1$. To perform the step of classical post-processing, Alice chooses
a random subset $\mathbf{B}$ of $\mathbf{D}$ with size $\gamma|\mathbf{D}|$,
where $\gamma>0$ is small. With the outcome information of set $\mathbf{B}$,
Alice and Bob estimate the single-detection parameter $d_{\epsilon}$ (Equation
20) and with the totality of the $m$ rounds they compute the winning
probability $P_{\text{win}}$ for the coherence equality game (Equation 19).

From the observed values of $P_{\text{win}}$ and $d_{\epsilon}$, for a given
security parameter $\mu$, Alice and Bob compute a key of size
$\kappa|\mathbf{D}|$ that is secure against a memory bounded eavesdropper with
probability $1-\mu$, and we show that $\kappa$ is positive for certain values
of $P_{\text{win}}$ and $d_{\epsilon}$.

###  3.1 Protocol description

An untrusted source sends a quantum state to Alice’s and Bob’s labs, and Alice
(resp. Bob) randomly chooses to either attempt to detect the particle ($x=1$,
resp. $y=1$) or do nothing ($x=0$, resp. $y=0$). Attempting to detect returns
an output $\alpha$ (resp. $\beta$) which indicates whether or not the particle
was detected. Alice (resp. Bob) then sends their half of the state to the
untrusted server $S_{A}$ (resp. $S_{B}$), which output outcomes $a$ (resp.
$b$), as represented in Figure 1.

The precise steps of the protocol are as follows:

  1. 1.

Take as input parameters $\mu,\eta$. For each round $i\in[m]$, Alice and Bob
receive state $\rho_{i}$ from a source and randomly choose to either detect or
do nothing, according to their secret bits $x_{i},y_{i}$ respectively. In case
they attempt detection, they receive outcomes $\alpha_{i},\beta_{i}$, and
every round they receive outcomes $a_{i},b_{i}$ from the untrusted servers.

  2. 2.

Alice and Bob share their choices of inputs, $X$ and $Y$ respectively, and the
outputs $A,B$ from their respective servers $S_{A}$ and $S_{B}$ on a public
authenticated channel.

  3. 3.

Alice chooses a random set B as a fraction $\gamma$ of the rounds in D, where
D is the set of rounds $i$ such that $x_{i}=y_{i}=1$, i.e. when both Alice and
Bob chose detection, and share the outcomes $\alpha,\beta$ of their
detections.

  4. 4.

From their input choices and from the outputs of $S_{A}$ and $S_{B}$, $A$ and
$B$ respectively, Alice and Bob calculate the fraction of rounds winning the
CE game,

$\hat{P}_{\text{win}}=\frac{1}{m}\sum_{i\in[m]}\mathbf{1}_{a_{i}\oplus
b_{i}=x_{i}\oplus y_{i}},$ (19)

and the fraction of rounds not satisfying the single-particle condition,
estimated from the public results of rounds in B,

$\hat{d_{\epsilon}}\equiv\frac{1}{|\mathbf{B}|}\sum_{i\in\mathbf{B}}\mathbf{1}_{\alpha_{i}=\beta_{i}=1}.$
(20)

  5. 5.

Bob inverts the bits of his set of detection results, $\beta$.222This step is
necessary, since up to here $\alpha$ and $\beta$ are expected to be anti-
correlated. Using the information of rounds in B, Alice and Bob perform
_information reconciliation_. If the fraction of agreement between their
results is smaller than $\eta$, they abort the protocol, otherwise, Bob
communicates $\ell=H(1.1\eta)|\mathbf{D}|+\log(2/\varepsilon)$ bits of
information to Alice.

  6. 6.

For the security parameter $\mu$, determine
$\kappa(\widetilde{P}_{\text{win}},\tilde{d_{\epsilon}},\mu)$ such that, with
probability at least $1-\mu$, the protocol is secure and they obtain

$\kappa|\mathbf{D}|-\ell+O(\log 1/\varepsilon)$ (21)

bits of secret key.

###  3.2 Security of the protocol

In this subsection we give the assumptions made in the security of the
protocol, as well as a sketch of the security proof, which is found integrally
in the Appendix. We have elected to simply show a sketch of the proof since it
follows the standard techniques of security proofs in the SDI-QKD literature,
with the major difference being the bound on the min-entropy of Alice’s and
Bob’s results derived from their playing of the CE game with the servers.

####  3.2.1 Safety assumptions

The protocol is not universally composable as we assume that Eve cannot try to
estimate the results in Alice’s and Bob’s labs after getting partial
information about them (i.e. after the round of information reconciliation).
This is referred to as the “bounded quantum storage” model as it is equivalent
to considering that Eve has some space or time bound on her quantum memory
forcing her to perform all her measurements before Alice and Bob share any
information about their results.

We do not assume that the devices behave identically and independently in each
round, and allow for internal memory that takes into account all previous
rounds. Alice and Bob should also be able to ensure that their devices
function as particle detectors, following the requirements given in Equation
2, and to verify from timing constraints that the quantum measurements
performed by the servers are spacelike separated in order to respect the non-
signalling condition.

####  3.2.2 Safety proof sketch

The safety of the protocol is based on the fact that a set of state and
measurements $(\rho,M_{A}^{a},M_{B}^{b})$ picked by the adversary cannot
simultaneously be used to win at the CE game and allow for Alice and Bob’s
detection outcome bits $\alpha$ and $\beta$ to be completely predictable. This
feature of the game is captured in Proposition 5, which places a bound on the
information that Eve can obtain on the detection results of Alice and Bob,
whenever both decide to attempt detection in their labs.

To apply Proposition 5, we use the results obtained by Alice and Bob in their
$m$ rounds of the CE game to estimate the behavior of the setup.

In the case of $P_{\text{win}}$, Alice and Bob can estimate their knowledge of
the devices by sharing the entirety of the rounds (values of $x,y,a,b$) and
applying the Azuma-Hoeffding inequality [36]. We show that they can apply
their estimation to the detection rounds in Lemma B. For the case of
$d_{\epsilon}$, they must use a subset of the detection rounds so as not to
lose the entire key. They can still estimate their knowledge using a Chernoff
bound and the Azuma-Hoeffding inequality (Lemmas B and B).

From the results of Lemmas B and B, Alice and Bob obtain values
$\widetilde{P}_{\text{win}},\widetilde{d_{\epsilon}}$ bounding the behaviour
of whole setup. These two parameters can be used to lower-bound the amount of
private information between them, as enunciated in the following theorem,
which is proven in full in the Appendix, and along the lines of [8, Section
A.2].

[Bound on the min-entropy]thmthmboundminentropy

Let $\mu>0$ be a safety parameter and assume that the protocol does not abort,
and let $\widehat{P}_{\text{win}},\hat{d_{\epsilon}}$ be the observed values
for the CE game and single-particle probabilities. Then there exists a choice
of values $\widetilde{P}_{\text{win}}<\hat{P}_{\text{win}}$ and
$\widetilde{d_{\epsilon}}>\widehat{d_{\epsilon}}$ such that, with probability
at least $1-\mu$, we have that

$H_{{\min}}(\alpha_{\mathbf{D}}|ABXY)\geq
H_{\min}(\widetilde{P}_{\text{win}},\tilde{d_{\epsilon}})|\mathbf{D}|.$

The main result of the security proof is the result of step 6 of the protocol,
i.e. the privacy amplification step.

[Privacy amplification]thmthmprivacyamplification After $m$ rounds, assume
that the protocol does not abort and let $\mu:=e^{-c_{0}m}>0$ be a security
parameter, for $c_{0}>0$. Then, for any $\varepsilon>0$ with probability at
least $1-\mu$, Alice and Bob can perform information reconciliation by sharing
$\ell$ bits of information and performing privacy amplification to obtain

$\kappa|\mathbf{D}|-\ell+O(\log 1/\varepsilon)$

secure bits of information, where $\kappa$ is a constant that only depends on
the values observed for $P_{\text{win}},d_{\epsilon}$ and the security
parameter $\mu$.

##  4 Conclusion

We introduced a noise-robust generalization of the Coherence Equality game and
used SDP techniques in order to compute its optimal quantum bounds as a
function of the noise parameter. We were able to identify three distinct
classes of coherence resources in the game: non-coherent states, separable
coherent states, and entangled coherent states, and computed individually the
bounds for all these (see Fig. 2). Accordingly, the game can be interpreted as
a coherence witness allowing for the certification of the type of coherence
resource used and consequently of entanglement, whose values we compute for
the optimal bound achieved by the entangled coherent states (see Fig. 3).

We further introduced a SDI QKD protocol, based on the Coherence Equality
game, where Alice and Bob need only to implement fixed basis measurements. Our
protocol, although not proven to be unconditionally secure like other state of
the art DI and SDI QKD protocols, is relevant mainly as a proof-of-concept for
the unification of both frameworks of device-independent and semi-quantum key
distribution. The novelty relies in using a coherence based game, rather than
the usual Bell tests, as a basis for the security of the protocol. This allows
for the certification on quantum correlations with fixed single-basis
measurements, both for Alice and Bob. The security proof follows closely the
standard approach found in [8], which allows one to establish the security of
the protocol, in the quantum-bounded storage model, from the performance in
the game. In fact, although we cast the game within a QKD protocol, because
the security proof comes from a bound on the guessing probability the game
could also be straightforwardly interpreted as a protocol for random number
generation.

## Acknowledgements

M.S. acknowledges the Calouste Gulbenkian Foundation for its scholarship
program New Talents in Quantum Technologies, and would like to thank Nikola
Paunković for fruitful discussion on the work of del Santo and Dakić.

R.F. would like to thank Flavio del Santo, and Borivojie Dakić for insightful
discussions regarding the nature of the coherence equality game. RF
acknowledges funding from FCT/MCTES through national funds and when applicable
EU funds under the project UIDB/50008/2020, and the QuantaGENOMICS project,
through the EU H2020 QuantERA II Programme.

E.Z.C. thanks the support from Fundação para a Ciência e a Tecnologia (FCT,
Portugal) through project UIDB/50008/2020.

This work was supported in part by the QuantaGENOMICS project, through the EU
H2020 QuantERA II Programme, Grant Agreement No 101017733, and by funding
organisations, The Foundation for Science and Technology – FCT
(QuantERA/0001/2021), Agence Nationale de la Recherche - ANR, and State
Research Agency – AEI.

## References

  * [1] M. S. Sharbaf, “Quantum cryptography: An emerging technology in network security,” in 2011 IEEE International Conference on Technologies for Homeland Security (HST), pp. 13–19, 2011.
  * [2] P. W. Shor, “Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer,” SIAM J. Comput., 26(5), 1484–1509, 1997.
  * [3] C. Bennett and G. Brassard, “Quantum cryptography: Public key distribution and coin tossing,” Proceedings of IEEE International Conference on Computers, Systems, and Signal Processing, p. 175–179, 1984.
  * [4] D. Mayers and A. Yao, “Quantum cryptography with imperfect apparatus,” in Proceedings of the 39th Annual Symposium on Foundations of Computer Science, FOCS ’98, (USA), p. 503, IEEE Computer Society, 1998.
  * [5] D. Mayers and A. Yao, “Self testing quantum apparatus,” Quantum Info. Comput., vol. 4, p. 273–286, July 2004.
  * [6] U. Vazirani and T. Vidick, “Fully device-independent quantum key distribution,” Physical Review Letters, vol. 113, Sep 2014.
  * [7] R. Arnon-Friedman, F. Dupuis, O. Fawzi, R. Renner, and T. Vidick, “Practical device-independent quantum cryptography via entropy accumulation,” Nature communications, vol. 9, no. 1, pp. 1–11, 2018.
  * [8] 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 et al., “Random numbers certified by bell’s theorem,” Nature, vol. 464, p. 1021–1024, Apr 2010.
  * [9] A. Acín, S. Massar, and S. Pironio, “Randomness versus nonlocality and entanglement,” Phys. Rev. Lett., vol. 108, p. 100402, Mar 2012.
  * [10] J. Ribeiro, L. P. Thinh, J. Kaniewski, J. Helsen, and S. Wehner, “Device independence for two-party cryptography and position verification with memoryless devices,” Phys. Rev. A, vol. 97, p. 062307, Jun 2018.
  * [11] N. Aharon, A. Chailloux, I. Kerenidis, S. Massar, S. Pironio, and J. Silman, “Weak coin flipping in a device-independent setting,” in Revised Selected Papers of the 6th Conference on Theory of Quantum Computation, Communication, and Cryptography - Volume 6745, pg.1–12, TQC 2011, 2011.
  * [12] R. Faleiro and M. Goulão, “Device-independent quantum authorization based on the Clauser-Horne-Shimony-Holt game,” Phys. Rev. A, vol. 103, p. 022430, Feb 2021.
  * [13] D. P. Nadlinger, P. Drmota, B. C. Nichol, G. Araneda, D. Main, R. Srinivas, D. M. Lucas, C. J. Ballance, K. Ivanov, E. Tan, et al., “Device-independent quantum key distribution,” arXiv preprint arXiv:2109.14600, 2021.
  * [14] W. Zhang, T. van Leent, K. Redeker, R. Garthoff, R. Schwonnek, F. Fertig, S. Eppelt, W. Rosenfeld, V. Scarani, C. C.-W. Lim, et al., “A device-independent quantum key distribution system for distant users,” Nature, vol. 607, no. 7920, pp. 687–691, 2022.
  * [15] W.-Z. Liu, Y.-Z. Zhang, Y.-Z. Zhen, M.-H. Li, Y. Liu, J. Fan, F. Xu, Q. Zhang, and J.-W. Pan, “Toward a photonic demonstration of device-independent quantum key distribution,” Physical Review Letters, vol. 129, no. 5, p. 050502, 2022.
  * [16] M. Pawłowski and N. Brunner, “Semi-device-independent security of one-way quantum key distribution,” Phys. Rev. A, vol. 84, p. 010302, Jul 2011.
  * [17] A. Chaturvedi, M. Ray, R. Veynar, and M. Pawłowski, “On the security of semi-device-independent QKD protocols,” Quantum Information Processing, vol. 17, p. 131, Apr 2018.
  * [18] A. Tavakoli, J. m. k. Kaniewski, T. Vértesi, D. Rosset, and N. Brunner, “Self-testing quantum states and measurements in the prepare-and-measure scenario,” Phys. Rev. A, vol. 98, p. 062307, Dec 2018.
  * [19] A. Tavakoli, “Semi-device-independent certification of independent quantum state and measurement devices,” Phys. Rev. Lett., vol. 125, p. 150503, Oct 2020.
  * [20] T. Van Himbeeck, E. Woodhead, N. J. Cerf, R. García-Patrón, and S. Pironio, “Semi-device-independent framework based on natural physical assumptions,” Quantum, vol. 1, p. 33, Nov. 2017.
  * [21] A. Tavakoli, E. Z. Cruzeiro, J. B. Brask, N. Gisin, and N. Brunner, “Informationally restricted quantum correlations,” Quantum, vol. 4, p. 332, 2020.
  * [22] A. Tavakoli, E. Z. Cruzeiro, E. Woodhead, and S. Pironio, “Informationally restricted correlations: a general framework for classical and quantum systems,” Quantum, vol. 6, p. 620, 2022.
  * [23] W. Shi, Y. Cai, J. B. Brask, H. Zbinden, and N. Brunner, “Semi-device-independent characterization of quantum measurements under a minimum overlap assumption,” Physical Review A, vol. 100, no. 4, p. 042108, 2019.
  * [24] H. Iqbal and W. O. Krawec, “Semi-quantum cryptography,” Quantum Information Processing, vol. 19, p. 97, Feb. 2020.
  * [25] M. Boyer, R. Gelles, D. Kenigsberg, and T. Mor, “Semiquantum key distribution,” Phys. Rev. A, vol. 79, p. 032341, Mar 2009.
  * [26] F. Massa, P. Yadav, A. Moqanaki, W. O. Krawec, P. Mateus, N. Paunković, A. Souto, and P. Walther, “Experimental Quantum Cryptography With Classical Users,” arXiv e-prints, p. arXiv:1908.01780, Aug. 2019.
  * [27] F. Del Santo and B. Dakić, “Coherence equality and communication in a quantum superposition,” Physical Review Letters, vol. 124, May 2020.
  * [28] L. Vandenberghe and S. Boyd, “Semidefinite programming,” SIAM Rev., vol. 38, pp. 49–95, Mar. 1996.
  * [29] K. F. Pál and T. Vértesi, “Efficiency of higher-dimensional hilbert spaces for the violation of bell inequalities,” Physical Review A, vol. 77, no. 4, p. 042105, 2008.
  * [30] M. McKague, M. Mosca, and N. Gisin, “Simulating quantum systems using real hilbert spaces,” Physical review letters, vol. 102, no. 2, p. 020505, 2009\.
  * [31] K.-C. Toh, M. J. Todd, and R. H. Tütüncü, “Sdpt3—a matlab software package for semidefinite programming, version 1.3,” Optimization methods and software, vol. 11, no. 1-4, pp. 545–581, 1999.
  * [32] R. F. Werner and M. M. Wolf, “Bell inequalities and entanglement,” arXiv preprint quant-ph/0107093, 2001.
  * [33] J. Lofberg, “Yalmip: A toolbox for modeling and optimization in matlab,” in 2004 IEEE international conference on robotics and automation (IEEE Cat. No. 04CH37508), pp. 284–289, IEEE, 2004.
  * [34] S. Designolle, R. Uola, K. Luoma, and N. Brunner, “Set coherence: Basis-independent quantification of quantum coherence,” Phys. Rev. Lett., vol. 126, p. 220404, Jun 2021.
  * [35] R. Wagner, R. S. Barbosa, and E. F. Galvão, “Inequalities witnessing coherence, nonlocality, and contextuality,” 2022.
  * [36] K. Azuma, “Weighted sums of certain dependent random variables,” Tohoku Math. J. (2), vol. 19, no. 3, pp. 357–367, 1967.
  * [37] R. Renner, Security of Quantum Key Distribution.  PhD thesis, Swiss Federal Institute of Technology Zurich, September 2005\.
  * [38] R. Konig, R. Renner, and C. Schaffner, “The operational meaning of min- and max-entropy,” IEEE Transactions on Information Theory, vol. 55, p. 4337–4347, Sep 2009.

##  Appendix A Analytical solution to the noise-robust CE game

We take Eq. (2.3), and derive it versus $c_{00}$, $c_{01}$, and $n_{x}$. To
find the maximum, we impose that each derivatives must equal zero. We solve
the first two for $c_{00}$ and $c_{01}$ respectively, to obtain

$c_{00}=-\frac{d_{\epsilon}^{1/2}n_{x}^{2}}{2+n_{x}^{2}},$ (22)

and

$c_{01}=\frac{d_{\epsilon}^{1/2}n_{x}\sqrt{1-n_{x}^{2}}}{1+n_{x}^{2}}.$ (23)

We substitute these into the third derivative, and find the following equation
for $n_{x}$,

$n_{x}(4+28d_{\epsilon}+(12+24d_{\epsilon})n_{x}^{2}+(13+4d_{\epsilon})n_{x}^{4}+6n_{x}^{6}+n_{x}^{8})=0$
(24)

Using the same substitution for the normalization condition, we obtain another
polynomial equation,

$4-4d_{\epsilon}+(12-20d_{\epsilon})n_{x}^{2}+(13-14d_{\epsilon})n_{x}^{4}+(6-2d_{\epsilon})n_{x}^{6}+n_{x}^{8}=0$
(25)

The solution to Eqs. (24) and (25) is an analytical solution333The solution
does not seem to have a compact explicit expression. to the optimization
problem considered in the main text, i.e. the SDP maximizing the noise-robust
CE game success probability with a quantum model. Using Eq. (22), one then
readily obtains $x(d_{\epsilon})\equiv c_{00}^{2}(\epsilon)$.

##  Appendix B Security proof

In this section, we show that the QKD protocol is secure given the assumptions
in Subsection 3.2.1, with a linear key rate and in the presence of noise. The
main result is the following theorem.

###### Proof.

Follows from Theorems B and 3.2.2, and the result on information
reconciliation, Theorem B.1. ∎

Since the proof of Theorem B.1, which pertains to the information
reconciliation part of the final result, is not unique to this protocol and
follows closely the standard approach found in the literature [37], we will
state the theorem and proof it separately in Subsection B.1.

Now we start by recalling the relation between the min-entropy and the amount
of private information that Alice and Bob can extract by classical
communication, expressed in the following theorem.

[Privacy amplification [38]] Suppose that there is an information
reconciliation protocol requiring at most $\ell$ bits of communication. Then,
for any $\varepsilon>0$, there is a privacy amplification protocol which
extracts

$H_{\min}(\alpha_{\mathbf{D}}|\mathcal{E^{\prime}})-\ell+O(\log
1/\varepsilon)$ (26)

bits of key.

To establish how the CE game provides a bound on the min-entropy
$H_{\min}(\alpha_{\mathbf{D}}|\mathcal{E}^{\prime})$, we start by considering
a property of each round of the raw key generation, guaranteed by Proposition
1, which we restate once again.

The following results are the steps needed to ensure that Alice and Bob have
enough statistical information at the end of the protocol to apply Proposition
5, taking into consideration that their devices and the adversary do not
necessarily act the same way in every round. In fact, we allow the behavior at
round $i$ to be a function of all inputs and outputs up to round $i-1$,
represented by the variable
$W^{i}:=(X^{<i},Y^{<i},A^{<i},B^{<i},\alpha^{<i},\beta^{<i})$.

Using the Azuma-Hoeffding inequality, we see that, for a large number of
rounds, the observed behavior of the devices is close to their expected
behavior, on average over all rounds.

Let $\hat{P}_{\textup{win}}$ be the estimated winning probability for the CE
game. Then

$\Pr(\frac{1}{m}\sum_{i=1}^{m}{P}_{\textup{win}}(W^{i})\leq\hat{P}_{\textup{win}}-\varepsilon)\leq\exp{-\frac{m\varepsilon^{2}}{32(1+\textup{Max}({P}_{\textup{win}}))^{2}}}.$

###### Proof.

Similar argument to [8, Section A.2]. Consider the random variable

$\hat{P}_{i}=4\times\mathbf{1}_{a_{i}\oplus b_{i}=x_{i}\oplus y_{i}}.$ (27)

Its expectation conditioned on the past $W^{i}$ is equal to
$\mathds{E}(\hat{P}_{i}|W^{i})=P(W^{i})$. The observed value for the CE game
is $\hat{P}=\frac{1}{m}\sum_{i=1}^{m}\hat{P}_{i}$. Consider now the random
variable $Z^{k}=\sum_{i=1}^{k}(P_{i}-P(W^{i}))$. It is true that
$(i)\,|Z^{k}|<\infty$, and that
$(ii)\,\mathds{E}(Z^{k}|W^{1},\dots,W^{j})=\mathds{E}(Z^{k}|W^{j})=Z^{j}$, for
$j\leq k$. Therefore the sequence $\\{Z^{k}:\,k\geq 1\\}$ is a martingale with
respect to the sequence $\\{W^{k}:\,k\geq 2\\}$.

The range of the martingale increments is bounded by $|P_{i}-P(W_{i})|\leq
4\,(1+\textup{Max}({P}_{\textup{win}}))$. Applying the Azuma-Hoeffding
inequality completes the proof. ∎

Now, we wish to show that not only is the observed behavior valid on average
over all rounds, but that it remains so when we look only at the rounds where
Alice and Bob generate the key, i.e. the rounds in $\mathbf{D}$. Since these
rounds are chosen uniformly at random, we can apply a Chernoff bound and see
that this is indeed true.

Let $\mathbf{D}$ be the set of detection rounds used for the raw key and
$\hat{P}_{win}$ the estimated winning probability for the CE game. Then we
have that

$\displaystyle\Pr(\frac{1}{|\mathbf{D}|}\sum_{i\in\mathbf{D}}P_{\text{win}}(W^{i})\geq(1-\delta)(\hat{P}_{win}-\varepsilon))$
(28) $\displaystyle\geq
1-\exp(-m\frac{\delta^{2}}{8}(\hat{P}_{win}-\varepsilon))-\exp(-\frac{m\varepsilon^{2}}{32(1+\textup{Max}({P}_{\textup{win}}))^{2}}).$
(29)

###### Proof.

Consider the events, for $\delta>0$,

$\displaystyle
E_{1}:=\frac{1}{m}\sum_{i=1}^{m}P_{\text{win}}(W^{i})>\hat{P}_{win}-\varepsilon,$
(30) $\displaystyle
E_{2}:=\frac{1}{|\mathbf{D}|}\sum_{i\in\mathbf{D}}P_{\text{win}}(W^{i})\geq(1-\delta)(\hat{P}_{win}-\varepsilon).$
(31)

We have that $P(E_{2})\geq P(E_{2}\land E_{1})=P(E_{2}|E_{1})P(E_{1})$. From
Lemma B it follows that $P(E_{1})\geq 1-\delta_{1}$. A bound for
$P(E_{2}|E_{1})$ is given by a Chernoff bound,

$\displaystyle\Pr(\frac{1}{|\mathbf{D}|}\sum_{i\in\mathbf{D}}P_{\text{win}}(W^{i})\geq(1-\delta)\frac{1}{m}\sum_{i=1}^{m}P_{\text{win}}(W^{i}))\geq
1-\exp{-|\mathbf{D}|\frac{\delta^{2}}{2}\frac{1}{m}\sum_{i=1}^{m}P_{\text{win}}(W^{i})}.$
(32)

Conditioning on $E_{1}$, we can write

$\displaystyle\frac{1}{|\mathbf{D}|}\sum_{i\in\mathbf{D}}P_{\text{win}}(W^{i}|E_{1})$
$\displaystyle\geq(1-\delta)\frac{1}{m}\sum_{i=1}^{m}P_{\text{win}}(W^{i}|E_{1})$
(33) $\displaystyle>(1-\delta)(\hat{P}_{win}-\varepsilon)$ (34)

and therefore

$\displaystyle\Pr(\frac{1}{|\mathbf{D}|}\sum_{i\in\mathbf{D}}P_{\text{win}}(W^{i})\geq(1-\delta)(\hat{P}_{win}-\varepsilon)\bigg{|}E_{1})$
$\displaystyle\geq
1-\exp{-|\mathbf{D}|\frac{\delta^{2}}{2}\frac{1}{m}\sum_{i=1}^{m}P_{\text{win}}(W^{i}|E_{1})}$
(35)
$\displaystyle>1-\exp{-|\mathbf{D}|\frac{\delta^{2}}{2}(\hat{P}_{win}-\varepsilon)},$
(36)

which concludes the proof. ∎

Since our upper bound is a function also of the single-detection probability,
we must carry out a similar analysis over $\hat{d_{\epsilon}}$. There is a
small distinction at the end which is that we cannot use the information of
all the rounds to estimate the single-detection probability, since that would
simply release the entire raw key. Instead, we sacrifice a fraction $\gamma$
chosen randomly from the key, achieve similar conclusions about the rounds
$\mathbf{B}$ and then use a Chernoff bound in relation to the full detection
set $\mathbf{D}$.

Let $\hat{d_{\epsilon}}$ be the observed value for the single-detection
condition, taking the detection results of rounds in $\mathbf{B}$. Then

$\Pr(\bigg{|}\frac{1}{|\mathbf{B}|}\sum_{i\in\mathbf{B}}d_{\epsilon}(W^{i})-\hat{d_{\epsilon}}\bigg{|}\geq\varepsilon)\leq
2\exp{-\frac{|\mathbf{B}|\varepsilon^{2}}{8}}.$ (37)

###### Proof.

Comes directly from applying the Azuma-Hoeffding inequality. ∎

Let $\mathbf{B}$ be the subset of detection rounds $\mathbf{D}$ used in
estimating $\hat{d_{\epsilon}}$, such that
$|\mathbf{B}|=\gamma|\mathbf{D}|=\gamma m/4$. Then, for
$\varepsilon,\delta>0$,

$\displaystyle\Pr(\frac{\hat{d_{\epsilon}}+\varepsilon}{1-\delta}>\frac{1}{|\mathbf{D}|}\sum_{i\in\mathbf{D}}d_{\epsilon}(W^{i}))$
(38) $\displaystyle\geq
1-\exp{-\frac{\delta^{2}}{8}\gamma^{2}m(\hat{d_{\epsilon}}-\varepsilon)}-2\exp{-\frac{\gamma
m\varepsilon^{2}}{32}}.$ (39)

###### Proof.

Same argument as Lemma B. Consider the events

$\displaystyle
F_{1}:=\bigg{|}\frac{1}{|\mathbf{B}|}\sum_{i\in\mathbf{B}}d_{\epsilon}(W^{i})-\hat{d_{\epsilon}}\bigg{|}<\varepsilon,$
(40) $\displaystyle
F_{2}:=\frac{\hat{d_{\epsilon}}+\varepsilon}{1-\delta}>\frac{1}{|\mathbf{D}|}\sum_{i\in\mathbf{D}}d_{\epsilon}(W^{i}).$
(41)

The probability $P(F_{1})\geq 1-\delta_{1}$ is given by Lemma B. Conditioning
on $F_{1}$, the probability $P(F_{2}|F_{1})$ is given by a Chernoff bound:

$\displaystyle\Pr(\frac{1}{|\mathbf{B}|}\sum_{i\in\mathbf{B}}d_{\epsilon}(W^{i})>(1-\delta)\frac{1}{|\mathbf{D}|}\sum_{i\in\mathbf{D}}d_{\epsilon}(W^{i})\bigg{|}F_{1})$
$\displaystyle\geq
1-\exp{-\frac{\delta^{2}}{2}\frac{|\mathbf{B}|}{|\mathbf{D}|}\sum_{i\in\mathbf{D}}d_{\epsilon}(W^{i}|F_{1})}$
(42) $\displaystyle\geq
1-\exp{-\frac{\delta^{2}}{2}\frac{|\mathbf{B}|^{2}}{|\mathbf{D}|}(\hat{d_{\epsilon}}-\varepsilon)}.$
(43)

The last inequality is obtained by noting that
$\sum_{i\in\mathbf{D}}d_{\epsilon}(W^{i}|F_{1})\geq\sum_{i\in\mathbf{B}}d_{\epsilon}(W^{i}|F_{1})>(\hat{d_{\epsilon}}-\varepsilon)|\mathbf{B}|$.
∎

We are now in position to apply Proposition 5. Knowing, on average over
$\mathbf{D}$, the expected behavior of the devices, Alice and Bob can
calculate a lower bound for a linear key rate.

###### Proof.

This proof follows along the lines of Section A.2 of [8]. Recalling the
relation between min-entropy and guessing probability [38],

$H_{\min}(X|Y)=-\log_{2}P_{g}(X|Y).$ (44)

We are interested in the min-entropy $H_{\min}(\alpha_{\mathbf{D}}|ABXY)$ of
the detection results $\alpha$ of rounds in $\mathbf{D}$, given that Eve has
access to the strings $X,Y,A,B$ of inputs and outputs. Consider the strings
$\alpha^{d}=(\alpha_{i})_{i\in[1..d]}$ where $d$ runs through the indices in
the set $\mathbf{D}$. Similarly, $a^{m},b^{m},x^{m},y^{m}$ where $m$ runs
through all rounds. We have that

$\displaystyle-\log_{2}P(\alpha^{d}|a^{m}b^{m}x^{m}y^{m})$
$\displaystyle=-\log_{2}\prod_{i\in\mathbf{D}}p(\alpha^{i}|a^{i-1}b^{i-1}x^{i-1}y^{i-1}\alpha^{i-1})$
(45) $\displaystyle=-\log_{2}\prod_{i\in\mathbf{D}}p(\alpha^{i}|W^{i})$ (46)
$\displaystyle=\sum_{i\in\mathbf{D}}-\log_{2}p(\alpha^{i}|W^{i}).$ (47)

We can apply Proposition 5 to each of the rounds, and we obtain a constraint
(see Figure 5)

$\displaystyle-\log_{2}P(\alpha^{i}|W^{i})$
$\displaystyle>-\log_{2}P_{g}(P_{\text{win}}(W^{i}),d_{\epsilon}(W^{i}))$ (48)
$\displaystyle=H_{\min}(P_{\text{win}}(W^{i}),d_{\epsilon}(W^{i})).$ (49)

This bound is true conditioned on any measurement of an eavesdropper before
Alice and Bob share any information about their inputs and outputs, since any
outcome of measurement in that case amounts to the preparation of a state to
be used by Alice and Bob, and the bound is independent of the state being
used. Therefore, in this step we assume that the adversary has a bounded
quantum memory and cannot delay her measurements so that they are made after
the parameter estimation step. With this caveat in mind, we can write

$\displaystyle-\log_{2}p(\alpha^{d}|a^{m}b^{m}x^{m}y^{m})$
$\displaystyle\geq\sum_{i\in\mathbf{D}}H_{\min}(P_{\text{win}}(W^{i}),d_{\epsilon}(W^{i}))$
(50)
$\displaystyle\geq|\mathbf{D}|\,H_{\min}\bigg{(}\frac{1}{|\mathbf{D}|}\sum_{i\in\mathbf{D}}P_{\text{win}}(W^{i}),\frac{1}{|\mathbf{D}|}\sum_{i\in\mathbf{D}}d_{\epsilon}(W^{i})\bigg{)}.$
(51)

The last inequality is deduced using the convexity of $f$ and Jensen’s
inequality for two variables.

Let $\mu>0$ be the a security parameter. Using Lemmas B and B, by sharing a
fraction $\gamma>0$ of the results of detection rounds, for $m$ large enough,
we can establish values
$\varepsilon,\delta,\varepsilon^{\prime},\delta^{\prime}>0$ such that, with
probability at least $1-\mu$,

$\displaystyle\frac{1}{|\mathbf{D}|}\sum_{i\in\mathbf{D}}d_{\epsilon}(W^{i})<\frac{\hat{d_{\epsilon}}+\varepsilon}{1-\delta}=:\tilde{d_{\epsilon}}$
(52)
$\displaystyle\frac{1}{|\mathbf{D}|}\sum_{i\in\mathbf{D}}P_{\text{win}}(W^{i})\geq(1-\delta^{\prime})(\hat{P}_{win}-\varepsilon^{\prime})=:\tilde{P}_{win}.$
(53)

Since $f(P_{\text{win}},d_{\epsilon})$ is increasing with $I$ and decreasing
with $d_{\epsilon}$, we have that

$\displaystyle H_{\min}(\alpha_{\mathbf{D}}|ABXY)$
$\displaystyle=-\log_{2}P(\alpha^{d}|a^{m}b^{m}x^{m}y^{m})\geq|\mathbf{D}|\,H_{\min}(\tilde{P}_{win},\tilde{d_{\epsilon}})\equiv|\mathbf{D}|\,\kappa,$
(54)

which concludes the proof. ∎

###  B.1 Max-entropy bound and information reconciliation

Either from eavesdropping or simply noise in the channels, Alice and Bob’s raw
keys will not necessarily match, and so they must reconcile their keys without
making them public. By sharing a small fraction at random, they are able to
bound the max-entropy between them and with high probability obtain an
identical key.

[Bound on the max-entropy] Suppose Alice and Bob do not abort the protocol
after Step 4. Let D be the set of detection rounds. Then, with probability at
least $1-2e^{-\gamma\,\eta\,|\mathbf{D}|/250}$,

$H_{\max}(\beta_{\mathbf{D}}|\alpha_{\mathbf{D}})\leq H(1.1\eta)|\mathbf{D}|,$

where $H(\cdot)$ is the typical binary entropy.

###### Proof.

Let $X=\gamma|\mathbf{D}|\eta_{\mathbf{B}}$ be the observed error rate, and
$\mu=\gamma|\mathbf{D}|\eta_{\mathbf{D}}$ the expected value. Since the
protocol aborts if $\eta_{B}>\eta$, we have that
$\Pr(1.1\eta<\eta_{\mathbf{D}}\land\neg\textrm{aborts})=\Pr(1.1\eta<\eta_{\mathbf{D}}\land\eta_{\mathbf{B}}\leq\eta)\leq
P(1.1\eta_{\mathbf{B}}<\eta_{\mathbf{D}}\land 1.1\eta<\eta_{\mathbf{D}})$.
Using a Chernoff bound, we have that

$\displaystyle\Pr(X<\frac{1}{1.1}\mu\land 1.1\eta<\eta_{\mathbf{D}})$
$\displaystyle\leq\Pr(X<\frac{1}{1.1}\mu\bigg{|}1.1\eta<\eta_{\mathbf{D}})$
(55)
$\displaystyle\leq\exp{-\frac{1}{242}\gamma|\mathbf{D}|\eta_{\mathbf{D}}}$
(56) $\displaystyle\leq\exp{-\frac{1}{250}\gamma|\mathbf{D}|\eta}.$ (57)

Therefore, with probability at least
$1-\exp{-\frac{1}{250}\gamma|\mathbf{D}|\eta}$, the noise rate of $\mathbf{D}$
is at most $1.1\eta$. This implies that, for a fixed $\alpha_{\mathbf{D}}$,
there are at most $2^{|\mathbf{D}|H(1.1\eta)}$ possible values for
$\beta_{\mathbf{D}}$. Using Remark 3.1.4 in [37], we have that
$H_{\max}(\beta_{\mathbf{D}}|\alpha_{\mathbf{D}})\leq H(1.1\eta)|\mathbf{D}|$.
∎

[Information reconciliation] Suppose Alice and Bob do not abort the protocol
after Step 4. Then, for any $\varepsilon>0$, they can perform information
reconciliation on their bit strings $\alpha_{\mathbf{D}},\beta_{\mathbf{D}}$
sacrificing at most the following amount of bits of information

$\ell\leq H(1.1\eta)|\mathbf{D}|+\log(2/\varepsilon).$

###### Proof.

Follows from Lemma 6.3.3 in [37] and Lemma B.1. ∎