††thanks: This work was performed while the author was at the
Interdisciplinary Centre for Security Reliability and Trust, University of
Luxembourg, Esch-sur-Alzette, L-4364, Luxembourg. This work is supported by
the Luxembourg National Research Fund, under CORE project Q-CoDe
(CORE17/IS/11689058).

# QKD parameter estimation by two-universal hashing

Dimiter Ostrev  Institute of Communications and Navigation, German Aerospace
Center, Oberpfaffenhofen, 82234 Weßling, Germany

###### Abstract

This paper proposes and proves security of a QKD protocol which uses two-
universal hashing instead of random sampling to estimate the number of bit
flip and phase flip errors. This protocol dramatically outperforms previous
QKD protocols for small block sizes. More generally, for the two-universal
hashing QKD protocol, the difference between asymptotic and finite key rate
decreases with the number $n$ of qubits as $cn^{-1}$, where $c$ depends on the
security parameter. For comparison, the same difference decreases no faster
than $c^{\prime}n^{-1/3}$ for an optimized protocol that uses random sampling
and has the same asymptotic rate, where $c^{\prime}$ depends on the security
parameter and the error rate.

##  1 Introduction

###  1.1 Motivation

Quantum Key Distribution allows two users, Alice and Bob, to agree on a shared
secret key using an authenticated classical channel and a completely insecure
quantum channel. There are information theoretic security proofs for QKD
protocols (for example [20, 19, 11, 8, 2, 24, 23] among many others). Quantum
key distribution has also been realized experimentally and is commercially
available. The rare combination of information theoretic security and
practical achievability has attracted considerable attention to QKD.

A QKD protocol has several important parameters:

  1. 1.

Block size: the number of pairs of qubits that Alice and Bob receive.
Following [23, Part 1], this paper considers entanglement based protocols and
defines the block size as the number of qubits after sifting.

  2. 2.

Output size: the number of bits of secret key that the protocol produces.

  3. 3.

Key rate: the ratio of output size to block size. The higher the key rate is,
the more efficiently the protocol converts the available quantum resource to a
secret key.

  4. 4.

Security level: the distance of the output from an ideal secret key. The lower
the security level, the better the guarantee that no future evolution of the
protocol output and adversary registers will be able to distinguish between
the output and an ideal key.

  5. 5.

Robustness: the amount and type of noise that the protocol can tolerate
without aborting. In particular, the QKD protocol should be able to tolerate
at the very least the imperfections of whatever quantum channel and
entanglement source are used to implement the protocol.

Existing QKD protocols and security proofs exhibit trade-offs between these
parameters: improving the security or robustness of the protocol worsens the
key rate. These trade-offs are particularly severe when the block size is
small. The phenomenon that the key rate of a QKD protocol deteriorates
significantly for small block sizes has been called finite size effect [16,
Sections II-C and IX].

The finite size effect has practical consequences in cases when the
distribution of entangled quantum states is particularly difficult. As an
example, consider the problem of using QKD between users who are far apart on
the surface of the earth. The Micius satellite experiment [26] tried to solve
this problem by using a satellite to distribute entangled photon pairs to two
ground stations that are 1120km apart. However, sending entangled photon pairs
from space to earth is difficult. In the Micius experiment, several nights of
good weather had to pass until the ground stations accumulated sifted block
size 3100. The error rate that the ground stations needed to tolerate was
$4.51\%$. Reference [12] performed a state-of-the-art security analysis on
this data, and concluded that security levels better than around $10^{-6}$
lead to no secret key at all, while at security level $10^{-6}$, only six bits
of secret key are extracted.

The output size and security level achieved in this example are not sufficient
for cryptographic applications. This provides the motivation for the present
paper. Are there QKD protocols and security proofs that achieve a combination
of small block size with output size and security level sufficient for
cryptographic applications?

###  1.2 Contributions

This paper presents the two-universal hashing QKD protocol and proves its
security. The two-universal hashing QKD protocol is an entanglement based
protocol with block size $n$, that can tolerate any combination of up to $r$
bit flip errors and up to $r$ phase flip errors, and at the end extract
$n-2\lceil nh(r/n)+2\log_{2}(1/\epsilon)+5\rceil$ secret key bits, that are
$\epsilon$ close to an ideal secret key.

For small block sizes, the two-universal hashing QKD protocol dramatically
outperforms protocols of the BBM92 type. To illustrate, consider again the
security analysis developed in the sequence of papers [24, 23, 12] applied to
the Micius satellite example.

  1. 1.

Fix the tolerated error rate at $4.51\%$, the security level at $10^{-6}$ and
the output size at 6 bits. The BBM92 type protocol with the security proof
developed in [24, 23, 12] requires block size 3100. The two-universal hashing
protocol requires block size 200.

  2. 2.

Fix the block size at 3100 and fix the error rate at $4.51\%$. The BBM92 type
protocol with the security proof developed in [24, 23, 12] can extract $6$
secret key bits with security level $10^{-6}$. The two universal hashing
protocol can extract $385$ secret key bits with security level $10^{-80}$.

The advantage of the two-universal hashing QKD protocol is particularly
noticeable for small block sizes; however, it is not limited to them. For
fixed error rate $\delta=r/n$ and fixed security parameter $\epsilon$, the
asymptotic rate of this protocol is $1-2h(\delta)$, and the deviation of
finite from asymptotic rate is between $(4\log_{2}(1/\epsilon)+10)/n$ and
$(4\log_{2}(1/\epsilon)+12)/n$. By contrast, the deviation of finite from
asymptotic key rate for the BBM92 type protocol with the security proof [24,
23, 12] is of the form $cn^{-1/3}$, where $c$ depends on the tolerated error
rate and the security level. A discussion of the reasons for the difference in
parameter trade-offs follows.

In the BBM92 type protocol, a random subset of $n_{pe}$ positions is measured
and the outcomes are publicly compared. If the error rate on this subset is
below some threshold $\delta$, then parameter estimation accepts and outputs
the promise that the error rate on the remaining positions is at most
$\delta+\nu$, where $\nu$ is the gap between observed and inferred error rate.
The failure probability for parameter estimation scales roughly as
$exp(-4n_{pe}v^{2})$. To get a sense of this scaling, suppose that the target
failure probability is $e^{-100}$ and that the target gap is $\nu=0.01$. Then,
$n_{pe}$ has to be chosen to be $250000$, clearly orders of magnitude more
than can be afforded for block sizes around 1000 or 10000. Now, consider the
rest of the protocol. Information reconciliation and privacy amplification
have to operate with the promise that the error rate is at most $\delta+\nu$.
Thus, to extract a secret key, information reconciliation and privacy
amplification have to sacrifice a substantial number of positions beyond the
initial $n_{pe}$ sacrificed for parameter estimation.

By contrast, in the two-universal hashing protocol, $2k$ ebits are sacrificed
for parameter estimation. If the test passes, then Alice and Bob know that the
post-parameter-estimation state is a particular Bell state of $n-2k$ ebits;
thus, Alice and Bob do not need to sacrifice any further ebits for information
reconciliation and privacy amplification. Moreover, the scaling of the failure
probability for parameter estimation with the number of sacrificed ebits does
not have the $\nu^{2}$ coefficient in front of the number of sacrificed ebits.

###  1.3 Related work

The present paper builds on a number of previous ideas.

In classical information theory, random linear functions have been used to
obtain ensembles of error correcting codes since the 1950s: see for example
[9, Section 2.1] where the idea was attributed to Elias [7]. Random linear
functions are also a special case of two-universal hash functions and can be
used to authenticate classical messages [6]. Further, [3, Theorem 6], [19,
Section 6.3.2] observed that two-universal hash functions can be used to
achieve information reconciliation with minimum leakage.

In quantum information theory, [1] used a variant of linear two-universal hash
functions to perform entanglement purification. [13] applied the technique of
[1] to construct an LOCC protocol by which Alice and Bob can verify that a
state they received from the adversary was in fact $n$ perfect EPR pairs. [20]
observed that when parameter estimation has already been performed by random
sampling, arguments related to quantum CSS codes [5, 21] can be used to prove
security of a QKD protocol. [11] presented an interesting generalization of
the proof technique of [20] that works also in the case of imperfect devices.
[2] translated the guarantees of classical random sampling to the quantum case
and used this to obtain a QKD security proof. [24, 8] focused on the
performance of QKD for small block sizes, and optimized their protocols by
using random sampling to estimate the number of errors in only one of the
measurement bases, while using a two-universal hash in the information
reconciliation phase to ensure correctness. [23] developed the proof idea of
[24] with much greater mathematical rigour. [12] proved a better random
sampling tail bound and thus obtained better parameter trade-offs than [23].

From the references above, closest to the present paper is [13]. The current
paper develops further the ideas in [13] in the following ways:

  1. 1.

Some mathematical details in the proof of [13] were skipped, other details
were entrusted to the papers on stabilizer codes and entanglement
purification. Further, [13] did not discuss composable security111Frameworks
for composable security were not yet invented at the time of [13]. and did not
give any explicit bounds on the achievable parameters for specific finite
block sizes. The present paper gives a detailed, rigorous and self-contained
proof of composable security, and gives explicit formulas for the achievable
parameters at any finite block size.

  2. 2.

[13] proposed a QKD protocol that employed full error correction with a
stabilizer error correcting code, followed by their verification subroutine;
thus the quantum phase of their protocol required the ability to implement
stabilizer error correcting codes. The present paper relies on quantum CSS
codes to simplify the quantum phase of the protocol as much as possible.

###  1.4 Structure of the paper

The rest of this paper is structured as follows: Section 2 introduces material
that is needed to present and prove the security of the two universal hashing
QKD protocol, including the security and robustness criteria for QKD
protocols, a number of useful lemmas related to the stabilizer formalism, and
a number of useful lemmas about two-universal hashing and random matrices over
the field with two elements. Section 3 presents the two-universal hashing QKD
protocol and shows that it is secure and robust. Section 4 shows that for
fixed security level and tolerated error rate, the finite key rate converges
to the asymptotic rate as $cn^{-1}$ for two-universal hashing and as
$c^{\prime}n^{-1/3}$ for the BBM92 protocol with the security proof developed
in [24, 23, 12]. Section 5 concludes and gives some open problems.

##  2 Preliminaries

This section presents definitions and results that are used to state and prove
the main result on the security and robustness of the two-universal hashing
protocol. Subsection 2.1 recalls the standard security criterion for QKD.
Then, subsection 2.2 contains a number of lemmas related to the stabilizer
formalism; these are used during the security proof. Finally, subsection 2.3
contains lemmas related to two-universal hashing. Subsection 2.3 also
discusses an application of two-universal hashing to approximately compute
certain functions from partial information about the input; this is used
during the security proof.

###  2.1 Security and robustness of quantum key distribution

This section recalls the security and robustness criteria from [19] that
ensure that the key produced by QKD can be used in any application. See [18]
for a proof of the equivalence of this security criterion and security in the
Abstract Cryptography framework for composable security.

As is common in the QKD literature, this paper assumes that the adversary Eve
is active in the quantum phase of the protocol but remains passive during the
classical phase, i.e. Eve eavesdrops the classical communication but does not
attempt to modify or block it. Under this assumption, an entanglement-based
QKD protocol is a completely positive trace preserving map that transforms
input states $\rho_{ABE}$ of Alice, Bob and Eve into output states
$\tilde{\rho}_{W_{A}W_{B}CE}$, where $W_{A},W_{B}$ are registers containing
Alice and Bob’s output: a secret key or indication $\bot$ of protocol abort,
and where $C$ is a register containing a transcript of the classical
communication between Alice and Bob.

Since registers $W_{A},W_{B}$ contain classical values, the final state
$\tilde{\rho}_{W_{A}W_{B}CE}$ can be decomposed as

$\tilde{\rho}_{W_{A}W_{B}CE}=|\bot\bot\rangle\langle\bot\bot|_{W_{A}W_{B}}\otimes\tilde{\rho}_{CE}(\bot)+\sum_{w_{A},w_{B}}|w_{A}w_{B}\rangle\langle
w_{A}w_{B}|_{W_{A}W_{B}}\otimes\tilde{\rho}_{CE}(w_{A},w_{B})$ (1)

This decomposition is used to formulate the definition of security:

######  Definition 1.

A QKD protocol is $\epsilon$ secure if for all input states $\rho_{ABE}$, the
output state $\tilde{\rho}_{W_{A}W_{B}CE}$ is $\epsilon$-close in trace
distance to the corresponding ideal state

$|\bot\bot\rangle\langle\bot\bot|_{W_{A}W_{B}}\otimes\tilde{\rho}_{CE}(\bot)+\sum_{w}\frac{1}{|W|}|ww\rangle\langle
ww|_{W_{A}W_{B}}\otimes(\tilde{\rho}_{CE}-\tilde{\rho}_{CE}(\bot))$ (2)

where $|W|$ denotes the size of the secret key space.

Alternatively, $\epsilon$-security can be further subdivided into requirements
for secrecy and correctness:

######  Definition 2.

A QKD protocol is $\epsilon$ correct if for all input states $\rho_{ABE}$, the
probability

$Pr(W_{A}\neq W_{B})=\sum_{w_{A}\neq w_{B}}Tr(\tilde{\rho}_{CE}(w_{A},w_{B}))$
(3)

that Alice and Bob accept and output different keys is bounded by $\epsilon$.

######  Definition 3.

Alice’s key is $\epsilon$ secret if for all input states $\rho_{ABE}$, the
reduced output state $\tilde{\rho}_{W_{A}CE}$ is $\epsilon$-close in trace
distance to the corresponding ideal state

$|\bot\rangle\langle\bot|_{W_{A}}\otimes\tilde{\rho}_{CE}(\bot)+\sum_{w}\frac{1}{|W|}|w\rangle\langle
w|_{W_{A}}\otimes(\tilde{\rho}_{CE}-\tilde{\rho}_{CE}(\bot))$ (4)

The following lemma establishes the relation between security and correctness
plus secrecy:

######  Lemma 1.

If a QKD protocol is $\epsilon$ secure, then it is $\epsilon$ correct and
Alice’s key is $\epsilon$ secret. Conversely, if the protocol is $\epsilon$
correct and Alice’s key is $\delta$ secret, then the protocol is
$\epsilon+\delta$ secure.

###### Proof.

The forward direction follows from monotonicity of the trace distance and its
interpretation as distinguishing advantage. The reverse direction follows by
considering the hybrid state

$|\bot\bot\rangle\langle\bot\bot|_{W_{A}W_{B}}\otimes\tilde{\rho}_{CE}(\bot)+\sum_{w}|ww\rangle\langle
ww|_{W_{A}W_{B}}\otimes\sum_{w^{\prime}}\tilde{\rho}_{CE}(w,w^{\prime})$ (5)

and the triangle inequality. ∎

Next, note that in the standard definition of QKD security (Definition 1) the
ideal state, beyond being $\epsilon$ close to the real state, satisfies the
following additional conditions:

  1. 1.

The probabilities of accepting and rejecting are the same for the real and
ideal state.

  2. 2.

The real and ideal state differ only in the accept case.

  3. 3.

The sub-normalized reduced density matrix of registers $C,E$ in the accept
case is equal to $\tilde{\rho}_{CE}-\tilde{\rho}_{CE}(\bot)$ for both the real
and the ideal state.

Now, suppose an ideal state is found that is $\epsilon$ close to the real
state, but which does not necessarily satisfy these additional conditions.
This suffices to demonstrate security:

######  Lemma 2.

Suppose that for all input states $\rho_{ABE}$, there exist positive
$\sigma_{CE}^{accept}$ and $\sigma_{CE}^{reject}$ such that
$Tr(\sigma_{CE}^{accept})+Tr(\sigma_{CE}^{reject})=1$ and such that the output
state $\tilde{\rho}_{W_{A}W_{B}CE}$ is $\epsilon$-close in trace distance to

$|\bot\bot\rangle\langle\bot\bot|_{W_{A}W_{B}}\otimes\sigma_{CE}^{reject}+\sum_{w}\frac{1}{|W|}|ww\rangle\langle
ww|_{W_{A}W_{B}}\otimes\sigma_{CE}^{accept}$ (6)

Then, the protocol is $2\epsilon$ secure.

###### Proof.

By assumption,

$\frac{1}{2}\|\tilde{\rho}_{CE}(\bot)-\sigma_{CE}^{reject}\|_{1}\\\
+\frac{1}{2}\sum_{w_{A},w_{B}}\left\|\tilde{\rho}_{CE}(w_{A},w_{B})-\frac{1}{|W|}\mathbf{1}(w_{A}=w_{B})\sigma_{CE}^{accept}\right\|_{1}\leq\epsilon$
(7)

From the triangle inequality it follows that

$\frac{1}{2}\left(\|\tilde{\rho}_{CE}(\bot)-\sigma_{CE}^{reject}\|_{1}+\left\|\tilde{\rho}_{CE}-\tilde{\rho}_{CE}(\bot)-\sigma_{CE}^{accept}\right\|_{1}\right)\leq\epsilon$
(8)

The lemma then follows by another application of the triangle inequality. ∎

Finally, note that a protocol that always aborts is secure, but not useful.
For a useful QKD protocol, the probability of acceptance is bounded below by
$1-\delta$ for some $\delta\in(0,1)$ on a suitable class of input states. In
the present paper, robustness of the two-universal hashing protocol is shown
by giving explicit bounds on the probability of acceptance as a function of
the input state.

###  2.2 The Pauli group and the Bell basis

This section presents a number of useful lemmas related to the stabilizer
formalism [10, 4].

Denote the Pauli matrices by

$\sigma_{1}=\begin{pmatrix}0&1\\\
1&0\end{pmatrix},\;\;\;\sigma_{2}=\begin{pmatrix}0&-i\\\
i&0\end{pmatrix},\;\;\;\sigma_{3}=\begin{pmatrix}1&0\\\ 0&-1\end{pmatrix}$ (9)

Let $\mathbb{F}_{2}$ denote the field with two elements, $\mathbb{F}_{2}^{n}$
denote the $n$-dimensional vector space over this field, and
$\mathbb{F}_{2}^{n\times m}$ denote the space of $n$ by $m$ matrices over
$\mathbb{F}_{2}$. For a row vector $u\in\mathbb{F}_{2}^{1\times n}$, denote

$\sigma_{1}^{u}=\sigma_{1}^{u_{1}}\otimes\dots\sigma_{1}^{u_{n}},\;\;\;\sigma_{3}^{u}=\sigma_{3}^{u_{1}}\otimes\dots\otimes\sigma_{3}^{u_{n}}$
(10)

The Pauli group on $n$ qubits is

$G_{n}=\\{\omega\sigma_{1}^{u}\sigma_{3}^{v}:\omega\in\\{\pm 1,\pm
i\\},u,v\in\mathbb{F}_{2}^{1\times n}\\}$ (11)

Matrix multiplication of elements of $G_{n}$ can be performed in terms of
$u,v,\omega$:

$(\omega\sigma_{1}^{u}\sigma_{3}^{v})(\omega^{\prime}\sigma_{1}^{u^{\prime}}\sigma_{3}^{v^{\prime}})=\omega\omega^{\prime}(-1)^{v\cdot
u^{\prime}}\sigma_{1}^{u+u^{\prime}}\sigma_{3}^{v+v^{\prime}}$ (12)

This also shows that the map
$\mathcal{F}:G_{n}\rightarrow\mathbb{F}_{2}^{1\times 2n}$ given by

$\mathcal{F}(\omega\sigma_{1}^{u}\sigma_{3}^{v})=\begin{pmatrix}u&v\end{pmatrix}$
(13)

is a group homomorphism.

Any element of the Pauli group squares to either $I$ or $-I$; any two elements
$g,g^{\prime}$ of the Pauli group satisfy

$gg^{\prime}=(-1)^{\mathcal{F}(g)\mathcal{S}\mathcal{F}(g^{\prime})^{T}}g^{\prime}g$
(14)

where $\mathcal{S}\in\mathbb{F}_{2}^{2n\times 2n}$ is the matrix with block
form

$\mathcal{S}=\begin{pmatrix}0&I_{n}\\\ I_{n}&0\end{pmatrix}$ (15)

Say that a tuple of elements of the Pauli group

$\vec{g}=\begin{pmatrix}g_{1}\\\ \vdots\\\ g_{m}\end{pmatrix}$ (16)

is independent if the row vectors
$\mathcal{F}(g_{i})\in\mathbb{F}_{2}^{1\times 2n}$ are linearly independent.
Given such an independent tuple and given any $x\in\mathbb{F}_{2}^{m}$, it is
possible to find $g\in G_{n}$ such that

$\forall i,\;\;gg_{i}=(-1)^{x_{i}}g_{i}g$ (17)

by solving the corresponding linear system of equations over $\mathbb{F}_{2}$.

A tuple of independent commuting self-adjoint elements of the Pauli group
$\vec{g}=(g_{1},\dots g_{m})^{T}$ defines a projective measurement on its
joint eigenspaces. The measurement outcomes can be indexed by
$x\in\mathbb{F}_{2}^{m}$ and the corresponding projections are given by

$P(\vec{g},x)=2^{-m}\prod_{j=1}^{m}(I+(-1)^{x_{j}}g_{j})$ (18)

The projections $P(\vec{g},x)$ form a complete set of orthogonal projections.
The elements of the Pauli group map these projections to each other under
conjugation, as can be seen from Lemma 3 below. Therefore, the projections
$P(\vec{g},x)$ all have the same rank $2^{n-m}$.

######  Lemma 3.

For all tuples $\vec{g}=(g_{1}\dots g_{m})^{T}$ of independent commuting self-
adjoint elements of $G_{n}$, for all $h\in G_{n}$, for all
$x\in\mathbb{F}_{2}^{m}$,

$P(\vec{g},x)h=hP(\vec{g},x+\mathcal{F}(\vec{g})\mathcal{S}\mathcal{F}(h)^{T})$
(19)

where

$\mathcal{F}(\vec{g})=\begin{pmatrix}\mathcal{F}(g_{1})\\\ \vdots\\\
\mathcal{F}(g_{m})\end{pmatrix}$ (20)

is the matrix with rows $\mathcal{F}(g_{1}),\dots,\mathcal{F}(g_{m})$.

###### Proof.

$P(\vec{g},x)h=2^{-m}\left(\prod_{j=1}^{m}(I+(-1)^{x_{j}}g_{j})\right)h\\\
=2^{-m}h\left(\prod_{j=1}^{m}(I+(-1)^{x_{j}+\mathcal{F}(g_{j})\mathcal{S}\mathcal{F}(h)^{T}}g_{j})\right)=hP(\vec{g},x+\mathcal{F}(\vec{g})\mathcal{S}\mathcal{F}(h)^{T})$
(21)

∎

Now, take a tuple $\vec{g}$ of $m$ independent commuting self-adjoint
elements, take $k\leq m$ and take a full rank matrix
$L\in\mathbb{F}_{2}^{k\times m}$. The matrix $L$ transforms the tuple
$\vec{g}$ to the $k$-tuple

$L\vec{g}=L\begin{pmatrix}g_{1}\\\ \vdots\\\
g_{m}\end{pmatrix}=\begin{pmatrix}\prod_{j=1}^{m}g_{j}^{L_{1j}}\\\ \vdots\\\
\prod_{j=1}^{m}g_{j}^{L_{kj}}\end{pmatrix}$ (22)

The tuple $L\vec{g}$ also consists of independent commuting self-adjoint
elements. The transformation of $\vec{g}$ to $L\vec{g}$ satisfies

$M(L\vec{g})=(ML)\vec{g}$ (23)

for any $\vec{g}$, $L$, $M$ of compatible size. The matrix
$\mathcal{F}(L\vec{g})$ can be expressed in terms of the matrix
$\mathcal{F}(\vec{g})$:

$\mathcal{F}(L\vec{g})=\begin{pmatrix}\mathcal{F}(\prod_{j=1}^{m}g_{j}^{L_{1j}})\\\
\vdots\\\
\mathcal{F}(\prod_{j=1}^{m}g_{j}^{L_{kj}})\end{pmatrix}=\begin{pmatrix}\sum_{j=1}^{m}L_{1j}\mathcal{F}(g_{j})\\\
\vdots\\\
\sum_{j=1}^{m}L_{kj}\mathcal{F}(g_{j})\end{pmatrix}=L\mathcal{F}(\vec{g})$
(24)

The measurement projections of $L\vec{g}$ can be expressed in terms of the
measurement projections of $\vec{g}$.

######  Lemma 4.

For all $n\geq m\geq k\geq 1$, for all tuples $\vec{g}$ of $m$ independent
commuting self-adjoint elements of $G_{n}$, for all full rank
$L\in\mathbb{F}_{2}^{k\times m}$, for all $y\in\mathbb{F}_{2}^{k}$,

$P(L\vec{g},y)=\sum_{x\in\mathbb{F}_{2}^{m}:Lx=y}P(\vec{g},x)$ (25)

###### Proof.

Take any $i\in\\{1,\dots k\\}$, any $x\in\mathbb{F}_{2}^{m}$ such that $Lx=y$.
Then,

$\left(\prod_{j=1}^{m}g_{j}^{L_{ij}}\right)P(\vec{g},x)=\left(\prod_{j=1}^{m}g_{j}^{L_{ij}}\right)\left(2^{-m}\prod_{j=1}^{m}(I+(-1)^{x_{j}}g_{j})\right)\\\
=(-1)^{\sum_{j=1}^{m}L_{ij}x_{j}}P(\vec{g},x)=(-1)^{y_{i}}P(\vec{g},x)$ (26)

Then, for any $x\in\mathbb{F}_{2}^{m}$ such that $Lx=y$,
$P(L\vec{g},y)P(\vec{g},x)=P(\vec{g},x)$ holds. Since
$\\{P(\vec{g},x):Lx=y\\}$ is a collection of $2^{m-k}$ orthogonal projections
of rank $2^{n-m}$ and since $P(L\vec{g},y)$ has rank $2^{n-k}$, the lemma
follows. ∎

The maximally entangled state in $\mathbb{C}^{2^{n}}\otimes\mathbb{C}^{2^{n}}$
is

$|\psi\rangle=2^{-n/2}\sum_{z\in\mathbb{F}_{2}^{n}}|zz\rangle$ (27)

The collection

$|\psi_{\alpha\beta}\rangle=I\otimes\sigma_{1}^{\alpha^{T}}\sigma_{3}^{\beta^{T}}|\psi\rangle,\;\;\alpha,\beta\in\mathbb{F}_{2}^{n}$
(28)

is the Bell basis of $\mathbb{C}^{2^{n}}\otimes\mathbb{C}^{2^{n}}$.

First, the maximally entangled state has the properties:

######  Lemma 5.

For all matrices $M\in\mathbb{C}^{2^{n}\times 2^{n}}$, $M\otimes
I|\psi\rangle=I\otimes M^{T}|\psi\rangle$ and $\langle\psi|I\otimes
M|\psi\rangle=2^{-n}Tr(M)$.

###### Proof.

Follows by expanding $M$ in the computational basis. ∎

Pauli group measurements acting on Bell basis states satisfy the following:

######  Lemma 6.

For all tuples $\vec{g}$ of independent self-adjoint commuting elements of
$G_{n}$ such that the associated projections $P(\vec{g},x)$ have only real
entries when expressed as matrices in the computational basis, for all
$\alpha,\beta\in\mathbb{F}_{2}^{n}$, for all $x,y\in\mathbb{F}_{2}^{m}$,

$(P(\vec{g},x)\otimes
P(\vec{g},y))|\psi_{\alpha\beta}\rangle=\mathbf{1}\left(x=y+\mathcal{F}(\vec{g})\mathcal{S}\begin{pmatrix}\alpha\\\
\beta\end{pmatrix}\right)P(\vec{g},x)\otimes I|\psi_{\alpha\beta}\rangle$ (29)

where for an expression that takes the values true or false,
$\mathbf{1}(expression)$ takes the corresponding values 1 or 0.

###### Proof.

Follows from Lemma 3 and the relation $M\otimes I|\psi\rangle=I\otimes
M^{T}|\psi\rangle$ ∎

The QKD security proof also uses the following lemma. It gives two equivalent
expressions for the projection on the subspace of
$\mathbb{C}^{2^{n}}\otimes\mathbb{C}^{2^{n}}$ that corresponds to a specific
pattern of bit flip errors or a specific pattern of phase flip errors.

######  Lemma 7.

For all $n$, for all $\alpha,\beta\in\mathbb{F}_{2}^{n}$,

$\displaystyle\sum_{\beta^{\prime}\in\mathbb{F}_{2}^{n}}|\psi_{\alpha\beta^{\prime}}\rangle\langle\psi_{\alpha\beta^{\prime}}|$
$\displaystyle=\sum_{z_{A}\in\mathbb{F}_{2}^{n}}|z_{A},z_{A}+\alpha\rangle\langle
z_{A},z_{A}+\alpha|$ (30)
$\displaystyle\sum_{\alpha^{\prime}\in\mathbb{F}_{2}^{n}}|\psi_{\alpha^{\prime}\beta}\rangle\langle\psi_{\alpha^{\prime}\beta}|$
$\displaystyle=\sum_{x_{A}\in\mathbb{F}_{2}^{n}}H^{\otimes
2n}|x_{A},x_{A}+\beta\rangle\langle x_{A},x_{A}+\beta|H^{\otimes 2n}$ (31)

###### Proof.

Let $e_{1},\dots e_{n}$ denote the standard basis of $\mathbb{F}_{2}^{1\times
n}$. For $i\in\\{1,3\\}$ and $R\in\\{A,B\\}$, let $\vec{\sigma}^{R}_{i}$
denote the tuple $\sigma_{i}^{e_{1}},\dots\sigma_{i}^{e_{n}}$ acting on
register $R$, and let $\vec{\sigma}_{i}^{AB}$ denote the tuple
$\sigma_{i}^{e_{1}}\otimes\sigma_{i}^{e_{1}},\dots,\sigma_{i}^{e_{n}}\otimes\sigma_{i}^{e_{n}}$.
Note that for all $\alpha,\beta$,

$|\alpha\beta\rangle\langle\alpha\beta|_{AB}=P\left(\begin{pmatrix}\vec{\sigma}_{3}^{A}\\\
\vec{\sigma}_{3}^{B}\end{pmatrix},\begin{pmatrix}\alpha\\\
\beta\end{pmatrix}\right)\;;\;|\psi_{\alpha\beta}\rangle\langle\psi_{\alpha\beta}|=P\left(\begin{pmatrix}\vec{\sigma}_{3}^{AB}\\\
\vec{\sigma}_{1}^{AB}\end{pmatrix},\begin{pmatrix}\alpha\\\
\beta\end{pmatrix}\right)$ (32)

The first relation of Lemma 7 now follows from

$\begin{pmatrix}I&I\end{pmatrix}\begin{pmatrix}\vec{\sigma}_{3}^{A}\\\
\vec{\sigma}_{3}^{B}\end{pmatrix}=\begin{pmatrix}I&0\end{pmatrix}\begin{pmatrix}\vec{\sigma}_{3}^{AB}\\\
\vec{\sigma}_{1}^{AB}\end{pmatrix}$ (33)

and Lemma 4. The second relation follows similarly. ∎

###  2.3 Approximately computing certain functions from only a two-universal
hash of the input

Take any subset $S\subset\mathbb{F}_{2}^{n}$. Consider the function
$f_{S}:\mathbb{F}_{2}^{n}\rightarrow S\cup\\{\bot\\}$ given by

$f_{S}(\alpha)=\begin{cases}\alpha&\text{if }\alpha\in S\\\
\bot&\text{otherwise}\end{cases}$ (34)

If $\alpha$ specifies errors, then $f_{S}$ computes whether $\alpha$ belongs
to a set $S$ of acceptable errors, if so computes the entire string $\alpha$,
and otherwise outputs an error message. It is very convenient to have
functions of this form when constructing QKD protocols and security proofs.

It turns out that it is possible to approximately compute $f_{S}(\alpha)$
given only a two universal hash of the input. Recall [6, 25]:

######  Definition 4.

A family of functions $\mathbf{H}$ from finite set $\mathbf{X}$ to finite set
$\mathbf{Y}$ is two-universal with collision probability at most $\epsilon$ if
for all $x\neq x^{\prime}\in\mathbf{X}$,

$\Pr_{h\leftarrow\mathbf{H}}(h(x)=h(x^{\prime}))\leq\epsilon$ (35)

where the probability is taken over $h$ chosen uniformly from $\mathbf{H}$. If
no explicit value is specified for the collision probability bound, then the
default value $\epsilon=1/|\mathbf{Y}|$ is taken.

Now, let $\mathbf{H}$ be a two-universal family from $\mathbb{F}_{2}^{n}$ to
some finite set $\mathbf{Y}$ with collision probability bound $\epsilon$. Let
$S=\\{s_{1},\dots,s_{m}\\}$. Consider the function
$g_{S}:\mathbf{H}\times\mathbf{Y}\rightarrow S\cup\\{\bot\\}$ given by the
deterministic algorithm:

  1. 1.

On input $h,y$,

  2. 2.

For $i=1,\dots,m$, if $h(s_{i})=y$, output $s_{i}$ and stop.

  3. 3.

Output $\bot$.

Then:

######  Theorem 1.

For all $n\in\mathbb{N}$, for all $\epsilon$, for all two-universal families
$\mathbf{H}:\mathbb{F}_{2}^{n}\rightarrow\mathbf{Y}$ with collision
probability bound $\epsilon$, for all subsets $S\subset\mathbb{F}_{2}^{n}$,
for all $\alpha\in\mathbb{F}_{2}^{n}$,

$\Pr_{h\leftarrow\mathbf{H}}(f_{S}(\alpha)\neq
g_{S}(h,h(\alpha)))\leq\epsilon|S|$ (36)

###### Proof.

The event

$f_{S}(\alpha)\neq g_{S}(h,h(\alpha))$ (37)

implies the event

$\exists s\in S\backslash\\{\alpha\\}:h(s)=h(\alpha)$ (38)

The union bound and Definition 4 give

$\Pr_{h\leftarrow\mathbf{H}}(f_{S}(\alpha)\neq
g_{S}(h,h(\alpha)))\leq\epsilon|S|$ (39)

∎

The remainder of this section specializes Theorem 1 to the case that the
family $\mathbf{H}$ is a family of matrices over $\mathbb{F}_{2}$, and the set
$S$ is a Hamming Ball.

First, consider the following useful lemmas about random matrices over the
field with two elements.

Recall a property of random linear functions:

######  Lemma 8.

Let $L$ be uniformly random in $\mathbb{F}_{2}^{k\times n}$, and take any
fixed $x\in\mathbb{F}_{2}^{n}-\\{0\\}$. Then, $\Pr_{L}(Lx=0)=2^{-k}$.

###### Proof.

Take $i$ such that $x_{i}=1$. Then, $Lx=L_{i}+L_{-i}x_{-i}$, where $L_{i}$ is
the $i$-th column of $L$ and where $L_{-i},x_{-i}$ are formed from $L,x$ by
omitting the $i$-th column and $i$-th entry respectively. Now, $L_{i}$ is
uniform over $\mathbb{F}_{2}^{k}$ and independent from $L_{-i}$, so $Lx$ is
also uniform over $\mathbb{F}_{2}^{k}$. ∎

Thus, for all $y\neq z\in\mathbb{F}_{2}^{n}$, $\Pr_{L}(Ly=Lz)=2^{-k}$, so
random linear functions are two-universal.

Later on, it will be more convenient to select matrices not from all of
$\mathbb{F}_{2}^{k\times n}$, but from the subset consisting of those matrices
of rank $k$. This subset also satisfies the two-universal condition, as the
following two lemmas show.

######  Lemma 9.

For all integers $n\geq k\geq 1$, the number of rank $k$ matrices in
$\mathbb{F}_{2}^{k\times n}$ is $\prod_{i=1}^{k}(2^{n}-2^{i-1})$

###### Proof.

Given $i-1$ linearly independent rows, there are $2^{n}-2^{i-1}$ ways to
choose the $i$-th row outside their span. ∎

######  Lemma 10.

Take $k\leq n$, let $L$ be a uniformly random rank $k$ matrix in
$\mathbb{F}_{2}^{k\times n}$ and take any $x\in\mathbb{F}_{2}^{n}-\\{0\\}$.
Then $\Pr_{L}(Lx=0)=\frac{2^{n-k}-1}{2^{n}-1}<2^{-k}$

###### Proof.

Take invertible $M\in\mathbb{F}_{2}^{n\times n}$ such that
$Mx=(1,0,\dots,0)^{T}$. Then $\Pr(Lx=0)=\Pr(LM^{-1}Mx=0)$. Now, find the
probability that the first column of $LM^{-1}$ is zero. Note that $LM^{-1}$ is
also uniformly distributed over the rank $k$ matrices in
$\mathbb{F}_{2}^{k\times n}$, so the probability its first column is zero is
the number of rank $k$ matrices in $\mathbb{F}_{2}^{k\times(n-1)}$ divided by
the number of rank $k$ matrices in $\mathbb{F}_{2}^{k\times n}$. Lemma 9
implies:

$\Pr(LM^{-1}Mx=0)=\frac{\prod_{i=1}^{k}(2^{n-1}-2^{i-1})}{\prod_{i=1}^{k}(2^{n}-2^{i-1})}=\frac{2^{n-k}-1}{2^{n}-1}<2^{-k}$
(40)

completing the proof of Lemma 10. ∎

Interestingly, the collision probability bound
$\epsilon=\frac{2^{n-k}-1}{2^{n}-1}$ achieved by the full rank matrices is the
lowest possible for a two-universal family
$\mathbb{F}_{2}^{n}\rightarrow\mathbb{F}_{2}^{k}$. This follows from a slight
strengthening of [6, Proposition 1]:

######  Lemma 11.

For every family $\mathbf{H}$ (not necessarily two-universal) of functions
from finite set $\mathbf{X}$ to finite set $\mathbf{Y}$, there exist $x\neq
x^{\prime}\in\mathbf{X}$ such that

$\Pr_{h\leftarrow\mathbf{H}}(h(x)=h(x^{\prime}))\geq\frac{\frac{|\mathbf{X}|}{|\mathbf{Y}|}-1}{|\mathbf{X}|-1}$
(41)

###### Proof.

Follow the same proof as [6] until the point they apply the pigeonhole
principle. At that point, observe that the number of non-zero terms in the sum
is not only less than $|\mathbf{X}|^{2}$, as they say there, but is in fact at
most $|\mathbf{X}|(|\mathbf{X}|-1)$.

In more detail, for $h\in\mathbf{H},x,x^{\prime}\in\mathbf{X}$, define

$\delta_{h}(x,x^{\prime})=\begin{cases}1&\text{if }x\neq x^{\prime}\wedge
h(x)=h(x^{\prime})\\\ 0&\text{otherwise}\end{cases}$ (42)

For every $h\in\mathbf{H}$ partition
$\mathbf{X}=\cup_{y\in\mathbf{Y}}h^{-1}(y)$ then observe that

$\sum_{x,x^{\prime}\in\mathbf{X}}\delta_{h}(x,x^{\prime})=\sum_{y\in\mathbf{Y}}|h^{-1}(y)|(|h^{-1}(y)|-1)\geq\frac{|\mathbf{X}|^{2}}{|\mathbf{Y}|}-|\mathbf{X}|$
(43)

by the quadratic mean-arithmetic mean inequality. Now, sum over
$h\in\mathbf{H}$:

$\sum_{h\in\mathbf{H}}\sum_{x,x^{\prime}\in\mathbf{X}}\delta_{h}(x,x^{\prime})=\sum_{x,x^{\prime}\in\mathbf{X}}\sum_{h\in\mathbf{H}}\delta_{h}(x,x^{\prime})\geq|\mathbf{H}|(\frac{|\mathbf{X}|^{2}}{|\mathbf{Y}|}-|\mathbf{X}|)$
(44)

Now, $\sum_{h\in\mathbf{H}}\delta_{h}(x,x^{\prime})$ is non-zero only when
$x\neq x^{\prime}$. Then, there exist $x\neq x^{\prime}$ such that

$\sum_{h\in\mathbf{H}}\delta_{h}(x,x^{\prime})\geq|\mathbf{H}|\frac{\frac{|\mathbf{X}|}{|\mathbf{Y}|}-1}{|\mathbf{X}|-1}$
(45)

∎

Later results will also use the fact that a row submatrix of a random
invertible matrix has the uniform distribution over full rank matrices:

######  Lemma 12.

Take any integers $n\geq k\geq 1$, and any $S\subset\\{1,\dots,n\\}$ of size
$k$. Let $L$ be uniformly distributed over invertible matrices in
$\mathbb{F}_{2}^{n\times n}$. Let $L_{S}$ denote the matrix formed by rows of
$L$ with indices in $S$. Then, $L_{S}$ is uniformly distributed over full rank
matrices in $\mathbb{F}_{2}^{k\times n}$.

###### Proof.

Pick any fixed full rank $\Lambda\in\mathbb{F}_{2}^{k\times n}$. Compute
$\Pr(L_{S}=\Lambda)$ as the number of ways to choose the remaining rows of
$L$, which is $\prod_{i=1}^{n-k}(2^{n}-2^{k+i-1})$ divided by the number of
invertible matrices in $\mathbb{F}_{2}^{n\times n}$, which is
$\prod_{i=1}^{n}(2^{n}-2^{i-1})$. Thus,

$\Pr(L_{S}=\Lambda)=\frac{\prod_{i=1}^{n-k}(2^{n}-2^{k+i-1})}{\prod_{i=1}^{n}(2^{n}-2^{i-1})}=\frac{1}{\prod_{i=1}^{k}(2^{n}-2^{i-1})}$
(46)

Thus, $L_{S}$ is uniform over the full rank matrices in
$\mathbb{F}_{2}^{k\times n}$. ∎

Applying Theorem 1 when the set $S$ is a Hamming ball requires a bound on the
size of Hamming balls. For $x,y\in\mathbb{F}_{2}^{n}$, let
$d_{H}(x,y)=|\\{i:x_{i}\neq y_{i}\\}|$ denote the Hamming distance between
them. Let $B_{n}(x,r)$ denote the Hamming ball of radius $r$ around $x$. Then:

######  Lemma 13.

For all $n,r\in\mathbb{N}$ such that $2r\leq n$, for all
$x\in\mathbb{F}_{2}^{n}$, $|B_{n}(x,r)|<2^{nh(r/n)}$

###### Proof.

$|B_{n}(x,r)|2^{-nh(r/n)}=\sum_{i=0}^{r}{n\choose
i}\left(\frac{r}{n}\right)^{r}\left(\frac{n-r}{n}\right)^{n-r}\\\
\leq\sum_{i=0}^{r}{n\choose
i}\left(\frac{r}{n}\right)^{i}\left(\frac{n-r}{n}\right)^{n-i}<\sum_{i=0}^{n}{n\choose
i}\left(\frac{r}{n}\right)^{i}\left(\frac{n-r}{n}\right)^{n-i}=1$ (47)

∎

From Theorem 1, Lemma 10 and Lemma 13 deduce:

######  Corollary 1.

For all $n,k,r\in\mathbb{N}$ with $2r\leq n$ and $k\leq n$, for all
$\alpha\in\mathbb{F}_{2}^{n}$,

$\Pr_{L}(f_{B_{n}(0,r)}(\alpha)\neq g_{B_{n}(0,r)}(L,L\alpha))<2^{-k+nh(r/n)}$
(48)

where $L$ is chosen uniformly from the full rank matrices in
$\mathbb{F}_{2}^{k\times n}$.

##  3 The two-universal hashing QKD protocol and its security

Consider the following family $\pi(n,k,r)$ of entanglement-based QKD
protocols, parameterized by $n,k,r\in\mathbb{N}$. The interpretation of the
parameters is the following: $n$ is the number of qubits that each of Alice
and Bob receive, $k$ is the size of each of their syndrome measurements and
$n-2k$ is the size of their output secret key, and $r$ is the maximum number
of bit flip or phase flip errors on which the protocol does not abort. The
protocols output a secret key with security guarantees when $2nh(r/n)<2k<n$.

It will be clear throughout that the size of the two syndrome measurements can
vary independently, and so can the maximum number of tolerated bit flip and
phase flip errors, but that would lead to overly complex notation, with five
parameters $n,k,k^{\prime},r,r^{\prime}$, so it is not pursued explicitly
below.

  1. 1.

Alice and Bob each receive an $n$ qubit state from Eve, and they inform each
other that the states have been received.

  2. 2.

Alice and Bob publicly choose a random invertible $L\in\mathbb{F}_{2}^{n\times
n}$. Let $L_{1},L_{2},L_{3}$ be the matrices formed by the first $k$ rows, the
second $k$ rows, and the last $n-2k$ rows of $L$. Let $M=(L^{-1})^{T}$, and
let $M_{1},M_{2},M_{3}$ be the matrices formed by the first $k$, second $k$,
and last $n-2k$ rows of $M$. $L_{1}$, $M_{2}$ are the parity check matrices of
a CSS code. $L_{3},M_{3}$ contain information about the logical $Z$ and $X$
operators on the codespace.

  3. 3.

Alice applies the isometry $\sum_{z}|z,L_{1}z\rangle_{AU^{\prime}_{A}}\langle
z|_{A}$ and Bob applies the isometry
$\sum_{z}|z,L_{1}z\rangle_{BU^{\prime}_{B}}\langle z|_{B}$. This can be done
by preparing $k$ ancilla qubits in state $0$ and applying a CNOT gate for each
entry $L_{1}(i,j)$ that equals 1.

  4. 4.

Alice and Bob measure all qubits in registers $A,B$ in the
$|+\rangle,|-\rangle$ basis, obtaining outcomes $x_{A},x_{B}$. Alice and Bob
measure all qubits in registers $U^{\prime}_{A},U^{\prime}_{B}$ in the
computational basis, obtaining outcomes $u_{A},u_{B}$.

  5. 5.

Alice and Bob compute $v_{A}=M_{2}x_{A}$, $v_{B}=M_{2}x_{b}$,
$w_{A}=M_{3}x_{A}$, $w_{B}=M_{3}x_{B}$.

  6. 6.

Alice and Bob discard registers $A,B,U^{\prime}_{A},U^{\prime}_{B}$.

  7. 7.

Alice and Bob discard $x_{A},x_{B}$, keeping only $v_{A},v_{B},w_{A},w_{B}$.
Thus, in effect, Alice and Bob erase $M_{1}x_{A},M_{1}x_{B}$. Note that the
post measurement states in registers $A,B$, as well as $x_{A},x_{B}$ have to
be discarded in such a way that Eve cannot get them.

  8. 8.

Alice and Bob announce $u_{A},u_{B},v_{A},v_{B}$. Alice and Bob compute
$s=g_{B_{n}(0,r)}(L_{1},u_{A}+u_{B})$ and
$t=g_{B_{n}(0,r)}(M_{2},v_{A}+v_{B})$.

  9. 9.

If both of $s,t$ are not $\bot$, then Alice takes $w_{A}$ to be the output
secret key, and Bob takes $w_{B}+M_{3}t$ to be the output secret key.

As is usual in the literature on QKD, the protocol assumes that classical
communication takes place over an authenticated channel. Unconditionally
secure message authentication with composable security in the Abstract
Cryptography framework can be obtained from a short secret key [17], or using
an advantage in channel noise [15].

If it is desired that the classical communication is minimized, then the
following exchange of messages suffices: Bob confirms to Alice that he has
received the qubits, Alice sends to Bob $L,u_{A},v_{A}$, Bob informs Alice
whether both of $s,t$ are not $\bot$. However, the initial formulation above
better emphasizes the symmetry of the protocol, and makes clear that it is not
important to keep the values $u_{B},v_{B},s,t$ secret.

The following theorem establishes the security and robustness of the protocols
$\pi(n,k,r)$.

######  Theorem 2.

Take any $n,k,r\in\mathbf{N}$ such that $2nh(r/n)<2k<n$. Then, the protocol
$\pi(n,k,r)$ is $2^{-k/2+nh(r/n)/2+5/2}$ secure.

Moreover, for any input state $\rho_{AB}$, the probability that $\pi(n,k,r)$
accepts on input $\rho_{AB}$ is $2^{-k/2+nh(r/n)/2+3/2}$ close to
$Tr(\Pi_{n,r}\rho_{AB}\Pi_{n,r})$, where $\Pi_{n,r}$ is the projection on the
subspace of systems $AB$ spanned by the Bell states with at most $r$ bit flip
and at most $r$ phase flip errors.

###  3.1 Proof of Theorem 2

The main idea of the proof of Theorem 2 is that the real values
$g_{B_{n}(0,r)}(L_{1},u_{A}+u_{B})$ and $g_{B_{n}(0,r)}(M_{2},v_{A}+v_{B})$
computed during the protocol can be replaced by the corresponding ideal values
$f_{B_{n}(0,r)}(\alpha),f_{B_{n}(0,r)}(\beta)$. From now on, use shorthand
notation and skip the subscript $B_{n}(0,r)$, thus writing $f$ for
$f_{B_{n}(0,r)}$ and $g$ for $g_{B_{n}(0,r)}$.

The steps of the proof of Theorem 2 are the propositions below. Start by
writing the action of the protocol as an isometry followed by a partial trace.

######  Proposition 1.

Let $\mathcal{E}_{real}$ be the completely positive trace preserving
transformation applied by the first eight steps of the protocol. Then, for all
input states $\rho_{ABE}$ to the protocol, the output state
$\mathcal{E}_{real}(\rho_{ABE})$ of the classical registers
$\mathbf{L},U_{A},U_{B},V_{A},V_{B},W_{A},W_{B},S,T$ and the quantum register
of Eve equals

$Tr_{AB\mathbf{L^{\prime}}S^{\prime}T^{\prime}U^{\prime}_{A}U^{\prime}_{B}V^{\prime}_{A}V^{\prime}_{B}W^{\prime}_{A}W^{\prime}_{B}}\mathcal{W}\mathcal{V}_{real}\mathcal{U}_{real}\left(\rho\otimes|\mathcal{L}\rangle\langle\mathcal{L}|\right)\mathcal{U}_{real}^{\dagger}\mathcal{V}_{real}^{\dagger}\mathcal{W}^{\dagger}$
(49)

where

$|\mathcal{L}\rangle=\sum_{L}\sqrt{p_{L}}|LL\rangle_{\mathbf{LL^{\prime}}}$
(50)

is a purification of the choice of random matrix $L$, where

$\mathcal{U}_{Real}=\sum_{L,z_{A},z_{B}}|L\rangle\langle
L|_{\mathbf{L}}\otimes|z_{A}z_{B}\rangle\langle z_{A}z_{B}|_{AB}\\\
\otimes|L_{1}z_{A},L_{1}z_{A},L_{1}z_{B},L_{1}z_{B},g(L_{1},L_{1}(z_{A}+z_{B})),g(L_{1},L_{1}(z_{A}+z_{B}))\rangle_{U_{A}U^{\prime}_{A}U_{B}U^{\prime}_{B}SS^{\prime}}$
(51)

is an isometry that captures the measurement through which Alice and Bob
obtain the values $u_{A}=L_{1}z_{A}$ and $u_{B}=L_{1}z_{B}$ as well as the
subsequent computation of the value $s=g(L_{1},L_{1}(z_{A}+z_{B}))$, where

$\mathcal{V}_{Real}=\sum_{L,x_{A},x_{B}}|L\rangle\langle
L|_{\mathbf{L}}\otimes\left(H^{\otimes 2n}|x_{A}x_{B}\rangle\langle
x_{A}x_{B}|H^{\otimes 2n}\right)_{AB}\\\
\otimes|M_{2}x_{A},M_{2}x_{A},M_{2}x_{B},M_{2}x_{B},g(M_{2},M_{2}(x_{A}+x_{B})),g(M_{2},M_{2}(x_{A}+x_{B}))\rangle_{V_{A}V^{\prime}_{A}V_{B}V^{\prime}_{B}TT^{\prime}}$
(52)

is an isometry that captures the measurement through which Alice and Bob
obtain the values $v_{A}=M_{2}x_{A}$ and $v_{B}=M_{2}x_{B}$ as well as the
subsequent computation of the value $t=g(M_{2},M_{2}(x_{A}+x_{B}))$ and where

$\mathcal{W}=\sum_{L,x_{A},x_{B}}|L\rangle\langle
L|_{\mathbf{L}}\otimes\left(H^{\otimes 2n}|x_{A}x_{B}\rangle\langle
x_{A}x_{B}|H^{\otimes 2n}\right)_{AB}\\\
\otimes|M_{3}x_{A},M_{3}x_{A},M_{3}x_{B},M_{3}x_{B}\rangle_{W_{A}W^{\prime}_{A}W_{B}W^{\prime}_{B}}$
(53)

is an isometry that captures the measurement through which Alice and Bob
obtain the values $w_{A}=M_{3}x_{A}$ and $w_{B}=M_{3}x_{B}$.

###### Proof.

Recall the Stinespring dilation theorem [22]. Systematically express each step
of the protocol as an isometry followed by a partial trace.

The step in which Alice and Bob choose the random matrix $L$ can be expressed
as preparing the purification $|\mathcal{L}\rangle_{\mathbf{LL^{\prime}}}$ and
then taking $Tr_{\mathbf{L^{\prime}}}$.

The steps in which Alice and Bob apply the isometry

$\sum_{z_{A},z_{B}}|z_{A},z_{B},L_{1}z_{A},L_{1}z_{B}\rangle_{ABU^{\prime}_{A}U^{\prime}_{B}}\langle
z_{A},z_{B}|_{AB}$ (54)

then measure registers $U^{\prime}_{A},U^{\prime}_{B}$ in the computational
basis, discarding the post-measurement state and keeping only the outcome,
then compute the value $s$ can be expressed by the isometry
$\mathcal{U}_{real}$ followed by
$Tr_{S^{\prime}U^{\prime}_{A}U^{\prime}_{B}}$.

The steps in which Alice and Bob measure the qubits in $A,B$ in the
$|+\rangle,|-\rangle$ basis obtaining $x_{A},x_{B}$, then compute
$v_{A},v_{B},w_{A},w_{B},t$, then discard the post-measurement state of the
qubits in $A,B$ and the outcomes $x_{A},x_{B}$ can be expressed by the product
of isometries $\mathcal{W}\mathcal{V}_{real}$ followed by
$Tr_{ABT^{\prime}V^{\prime}_{A}V^{\prime}_{B}W^{\prime}_{A}W^{\prime}_{B}}$.

Finally, note that all the partial trace operations can be commuted to the
end. ∎

Next, note that $\mathcal{U}_{real}$ can be approximated by an ideal isometry
followed by a simulator isometry.

######  Proposition 2.

Let

$\mathcal{U}_{ideal}=\sum_{\alpha,\beta}|\psi_{\alpha\beta}\rangle\langle\psi_{\alpha\beta}|_{AB}\otimes|f(\alpha),f(\alpha)\rangle_{SS^{\prime}}$
(55)

This ideal isometry computes whether the number of bit flip errors is
acceptable and if so it computes the entire string of bit flip error
positions.

Let

$\mathcal{U}_{simulator}=\sum_{L,z_{A},z_{B}}|L\rangle\langle
L|_{\mathbf{L}}\otimes|z_{A}z_{B}\rangle\langle z_{A}z_{B}|_{AB}\\\
\otimes|L_{1}z_{A},L_{1}z_{A},L_{1}z_{B},L_{1}z_{B}\rangle_{U_{A}U^{\prime}_{A}U_{B}U^{\prime}_{B}}$
(56)

This isometry captures the measurement through which Alice and Bob obtain the
values $u_{A}=L_{1}z_{A}$ and $u_{B}=L_{1}z_{B}$.

Then:

$\left(\langle\mathcal{L}|\mathcal{U}_{ideal}^{\dagger}\mathcal{U}_{simulator}^{\dagger}\right)\left(\mathcal{U}_{real}|\mathcal{L}\rangle\right)\geq(1-2^{-k+nh(r/n)})I_{AB}$
(57)

###### Proof.

Simplify:

$\mathcal{U}_{simulator}^{\dagger}\mathcal{U}_{real}=\sum_{L,z_{A},z_{B}}|L\rangle\langle
L|_{\mathbf{L}}\otimes|z_{A}z_{B}\rangle\langle z_{A}z_{B}|_{AB}\\\
\otimes|g(L_{1},L_{1}(z_{A}+z_{B})),g(L_{1},L_{1}(z_{A}+z_{B}))\rangle_{SS^{\prime}}$
(58)

Therefore,

$\left(\langle\mathcal{L}|\mathcal{U}_{ideal}^{\dagger}\mathcal{U}_{simulator}^{\dagger}\right)\left(\mathcal{U}_{real}|\mathcal{L}\rangle\right)\\\
=\sum_{L,z_{A},z_{B},\alpha,\beta}p_{L}|\psi_{\alpha\beta}\rangle\langle\psi_{\alpha\beta}|_{AB}|z_{A}z_{B}\rangle\langle
z_{A}z_{B}|_{AB}\langle f(\alpha)|g(L_{1},L_{1}(z_{A}+z_{B}))\rangle_{S}$ (59)

Now, apply Lemma 7:

$\sum_{L,z_{A},z_{B},\alpha}p_{L}\left(\sum_{\beta}|\psi_{\alpha\beta}\rangle\langle\psi_{\alpha\beta}|_{AB}\right)|z_{A}z_{B}\rangle\langle
z_{A}z_{B}|_{AB}\langle f(\alpha)|g(L_{1},L_{1}(z_{A}+z_{B}))\rangle_{S}\\\
=\sum_{L,z_{A},z_{B},\alpha,z^{\prime}_{A}}p_{L}|z^{\prime}_{A},z^{\prime}_{A}+\alpha\rangle\langle
z^{\prime}_{A},z^{\prime}_{A}+\alpha|_{AB}|z_{A}z_{B}\rangle\langle
z_{A}z_{B}|_{AB}\langle f(\alpha)|g(L_{1},L_{1}(z_{A}+z_{B}))\rangle_{S}\\\
=\sum_{z_{A},z_{B}}|z_{A}z_{B}\rangle\langle
z_{A}z_{B}|_{AB}\sum_{L}p_{L}\langle
f(z_{A}+z_{B})|g(L_{1},L_{1}(z_{A}+z_{B}))\rangle\\\
=\sum_{z_{A},z_{B}}|z_{A}z_{B}\rangle\langle
z_{A}z_{B}|_{AB}\Pr_{L}(f(z_{A}+z_{B})=g(L_{1},L_{1}(z_{A}+z_{B})))$ (60)

Now, the marginal distribution of $L_{1}$ is uniform over the rank $k$
matrices in $\mathbb{F}_{2}^{k\times n}$ because $L$ is selected uniformly
among invertible matrices in $\mathbb{F}_{2}^{n\times n}$ (Lemma 12). Complete
the proof of Proposition 2 by applying Corollary 1. ∎

Next, perform the same approximation for $\mathcal{V}_{real}$.

######  Proposition 3.

Let

$\mathcal{V}_{ideal}=\sum_{\alpha,\beta}|\psi_{\alpha\beta}\rangle\langle\psi_{\alpha\beta}|_{AB}\otimes|f(\beta),f(\beta)\rangle_{TT^{\prime}}$
(61)

This ideal isometry computes whether the number of phase flip errors is
acceptable and if so it computes the entire string of phase flip error
positions.

Let

$\mathcal{V}_{simulator}=\sum_{L,x_{A},x_{B}}|L\rangle\langle
L|_{\mathbf{L}}\otimes\left(H^{\otimes 2n}|x_{A}x_{B}\rangle\langle
x_{A}x_{B}|H^{\otimes 2n}\right)_{AB}\\\
\otimes|M_{2}x_{A},M_{2}x_{A},M_{2}x_{B},M_{2}x_{B}\rangle_{V_{A}V^{\prime}_{A}V_{B}V^{\prime}_{B}}$
(62)

This isometry captures the measurement through which Alice and Bob obtain the
values $v_{A}=M_{2}x_{A}$ and $v_{B}=M_{2}x_{B}$.

Then:

$\left(\langle\mathcal{L}|\mathcal{V}_{ideal}^{\dagger}\mathcal{V}_{simulator}^{\dagger}\right)\left(\mathcal{V}_{real}|\mathcal{L}\rangle\right)\geq(1-2^{-k+nh(r/n)})I_{AB}$
(63)

###### Proof.

As in the proof of Proposition 2, use Lemma 7 to compute

$\left(\langle\mathcal{L}|\mathcal{V}_{ideal}^{\dagger}\mathcal{V}_{simulator}^{\dagger}\right)\left(\mathcal{V}_{real}|\mathcal{L}\rangle\right)\\\
=\sum_{x_{A},x_{B}}\left(H^{\otimes 2n}|x_{A}x_{B}\rangle\langle
x_{A}x_{B}|H^{\otimes
2n}\right)_{AB}\Pr_{L}(f(x_{A}+x_{B})=g(M_{2},M_{2}(x_{A}+x_{B})))$ (64)

Now, $M=(L^{-1})^{T}$ is uniformly distributed over invertible matrices in
$\mathbb{F}_{2}^{n\times n}$, so Lemma 12 and Corollary 1 complete the proof.
∎

Next, observe that:

######  Proposition 4.

$\mathcal{U}_{simulator}\mathcal{V}_{real}=\mathcal{V}_{real}\mathcal{U}_{simulator}$

###### Proof.

Rewrite:

$\mathcal{U}_{simulator}=\sum_{L,z_{A},z_{B}}|L\rangle\langle
L|_{\mathbf{L}}\otimes|z_{A}z_{B}\rangle\langle
z_{A}z_{B}|_{AB}\otimes|L_{1}z_{A},L_{1}z_{A},L_{1}z_{B},L_{1}z_{B}\rangle_{U_{A}U^{\prime}_{A}U_{B}U^{\prime}_{B}}\\\
=\sum_{L,u_{A},u_{B}}|L\rangle\langle
L|_{\mathbf{L}}\otimes|u_{A},u_{A},u_{B},u_{B}\rangle_{U_{A}U^{\prime}_{A}U_{B}U^{\prime}_{B}}\\\
\otimes\left(\sum_{z_{A}:L_{1}z_{A}=u_{A}}|z_{A}\rangle\langle
z_{A}|\right)_{A}\otimes\left(\sum_{z_{B}:L_{1}z_{B}=u_{B}}|z_{B}\rangle\langle
z_{B}|\right)_{B}\\\ =\sum_{L,u_{A},u_{B}}|L\rangle\langle
L|_{\mathbf{L}}\otimes|u_{A},u_{A},u_{B},u_{B}\rangle_{U_{A}U^{\prime}_{A}U_{B}U^{\prime}_{B}}\otimes
P(L_{1}(\vec{\sigma}_{3}),u_{A})_{A}\otimes
P(L_{1}(\vec{\sigma}_{3}),u_{B})_{B}$ (65)

where the last step uses Lemma 4 and the notation of Section 2.2 for the tuple
$\vec{\sigma}_{3}$ of single qubit $\sigma_{3}$ operations.

Similarly, rewrite

$\mathcal{V}_{Real}=\sum_{L,x_{A},x_{B}}|L\rangle\langle
L|_{\mathbf{L}}\otimes\left(H^{\otimes 2n}|x_{A}x_{B}\rangle\langle
x_{A}x_{B}|H^{\otimes 2n}\right)_{AB}\\\
\otimes|M_{2}x_{A},M_{2}x_{A},M_{2}x_{B},M_{2}x_{B},g(M_{2},M_{2}(x_{A}+x_{B})),g(M_{2},M_{2}(x_{A}+x_{B}))\rangle_{V_{A}V^{\prime}_{A}V_{B}V^{\prime}_{B}TT^{\prime}}\\\
=\sum_{L,v_{A},v_{B}}|L\rangle\langle L|_{\mathbf{L}}\otimes
P(M_{2}(\vec{\sigma}_{1}),v_{A})_{A}\otimes
P(M_{2}(\vec{\sigma}_{1}),v_{B})_{B}\\\
\otimes|v_{A},v_{A},v_{B},v_{B},g(M_{2},v_{A}+v_{B}),g(M_{2},v_{A}+v_{B}\rangle_{V_{A}V^{\prime}_{A}V_{B}V^{\prime}_{B}TT^{\prime}}$
(66)

where $\vec{\sigma}_{1}$ is the tuple of single qubit $\sigma_{1}$ operations.

Proposition 4 now follows by observing that the elements of the two tuples
$L_{1}(\vec{\sigma}_{3})$ and $M_{2}(\vec{\sigma}_{1})$ commute and therefore
for all $u,v$, the corresponding projections $P(L_{1}(\vec{\sigma}_{3}),u)$
and $P(M_{2}(\vec{\sigma}_{1}),v)$ also commute. ∎

Next, use propositions 1, 2, 3, 4 to construct an ideal transformation that
approximates $\mathcal{E}_{real}$:

######  Proposition 5.

Let $\mathcal{E}_{ideal}$ be the transformation that prepares
$|\mathcal{L}\rangle$, then applies isometries $\mathcal{U}_{ideal}$,
$\mathcal{V}_{ideal}$, $\mathcal{V}_{simulator}$, $\mathcal{U}_{simulator}$,
$\mathcal{W}$, and finally applies
$Tr_{AB\mathbf{L^{\prime}}S^{\prime}T^{\prime}U^{\prime}_{A}U^{\prime}_{B}V^{\prime}_{A}V^{\prime}_{B}W^{\prime}_{A}W^{\prime}_{B}}$.
Then, the diamond distance of $\mathcal{E}_{real}$ and $\mathcal{E}_{ideal}$
is at most $2^{-k/2+nh(r/n)/2+3/2}$.

###### Proof.

Take any input state $\rho_{ABE}$ and purify it to
$|\phi\rangle_{ABEE^{\prime}}$. From Proposition 2 deduce that the fidelity of
$\mathcal{V}_{real}\mathcal{U}_{simulator}\mathcal{U}_{ideal}|\phi\rangle|\mathcal{L}\rangle$
and $\mathcal{V}_{real}\mathcal{U}_{real}|\phi\rangle|\mathcal{L}\rangle$ is
at least $1-2^{-k+nh(r/n)}$. Using the relation of fidelity and trace distance
for pure states [14, Equation 9.99], the trace distance between these two
states is

$\sqrt{1-(1-2^{-k+nh(r/n)})^{2}}\leq 2^{-k/2+nh(r/n)/2+1/2}$ (67)

Next, from Proposition 4 deduce

$\mathcal{V}_{real}\mathcal{U}_{simulator}\mathcal{U}_{ideal}|\phi\rangle|\mathcal{L}\rangle=\mathcal{U}_{simulator}\mathcal{V}_{real}\mathcal{U}_{ideal}|\phi\rangle|\mathcal{L}\rangle$
(68)

Next, from Proposition 3 deduce that the fidelity of

$\mathcal{U}_{simulator}\mathcal{V}_{real}\mathcal{U}_{ideal}|\phi\rangle|\mathcal{L}\rangle$

and

$\mathcal{U}_{simulator}\mathcal{V}_{simulator}\mathcal{V}_{ideal}\mathcal{U}_{ideal}|\phi\rangle|\mathcal{L}\rangle$

is at least $1-2^{-k+nh(r/n)}$, so the trace distance between them is at most
$2^{-k/2+nh(r/n)/2+1/2}$. Finally, from Proposition 1, the triangle inequality
and monotonicity of the trace distance deduce that the trace distance between
$\mathcal{E}_{real}(\rho)$ and $\mathcal{E}_{ideal}(\rho)$ is at most
$2^{-k/2+nh(r/n)/2+3/2}$. ∎

Next, compute the output state of $\mathcal{E}_{ideal}$:

######  Proposition 6.

Take any input state $\rho_{ABE}$ and purify it to
$|\phi\rangle_{ABEE^{\prime}}$. Expand $\phi$ in the Bell basis for Alice and
Bob:

$|\phi\rangle_{ABEE^{\prime}}=\sum_{\alpha,\beta\in\mathbb{F}_{2}^{n}}|\psi_{\alpha\beta}\rangle_{AB}\otimes|\gamma_{\alpha\beta}\rangle_{EE^{\prime}}$
(69)

where $|\gamma_{\alpha\beta}\rangle$ are vectors in Eve’s space that satisfy

$\sum_{\alpha,\beta\in\mathbb{F}_{2}^{n}}\langle\gamma_{\alpha\beta}|\gamma_{\alpha\beta}\rangle=1$
(70)

Then, there exists
$\sigma^{reject}_{LEE^{\prime}STU_{A}V_{A}W_{A}U_{B}V_{B}W_{B}}$ that is
classical on registers $LSTU_{A}V_{A}W_{A}U_{B}V_{B}W_{B}$ and such that at
least one of $ST$ contains $\bot$ and such that

$\mathcal{E}_{ideal}(|\phi\rangle\langle\phi|)=\sigma^{reject}_{LEE^{\prime}STU_{A}V_{A}W_{A}U_{B}V_{B}W_{B}}\\\
+\sum_{L,u_{A},v_{A},w_{A},\alpha,\beta:\alpha,\beta\in
B_{n}(0,r)}p_{L}|L\rangle\langle
L|_{\mathbf{L}}\otimes|\gamma_{\alpha\beta}\rangle\langle\gamma_{\alpha\beta}|_{EE^{\prime}}\otimes|\alpha,\beta\rangle\langle\alpha,\beta|_{ST}\\\
\otimes 2^{-n}|u_{A},v_{A},w_{A}\rangle\langle
u_{A},v_{A},w_{A}|_{U_{A}V_{A}W_{A}}\\\
\otimes|u_{A}+L_{1}\alpha,v_{A}+M_{2}\beta,w_{A}+M_{3}\beta\rangle\langle
u_{A}+L_{1}\alpha,v_{A}+M_{2}\beta,w_{A}+M_{3}\beta|_{U_{B}V_{B}W_{B}}$ (71)

###### Proof.

Simplify:

$\mathcal{V}_{ideal}\mathcal{U}_{ideal}=\sum_{\alpha,\beta}|\psi_{\alpha\beta}\rangle\langle\psi_{\alpha\beta}|\otimes|f(\alpha),f(\alpha),f(\beta),f(\beta)\rangle_{SS^{\prime}TT^{\prime}}$
(72)

Also,

$\mathcal{W}\mathcal{V}_{simulator}\mathcal{U}_{simulator}=\sum_{L,u_{A},u_{B},v_{A},v_{B},w_{A},w_{B}}|L\rangle\langle
L|_{\mathbf{L}}\\\ \otimes P\left(\begin{pmatrix}L_{1}\vec{\sigma}_{3}\\\
M_{2}\vec{\sigma}_{1}\\\
M_{3}\vec{\sigma}_{1}\end{pmatrix},\begin{pmatrix}u_{A}\\\ v_{A}\\\
w_{A}\end{pmatrix}\right)_{A}\otimes
P\left(\begin{pmatrix}L_{1}\vec{\sigma}_{3}\\\ M_{2}\vec{\sigma}_{1}\\\
M_{3}\vec{\sigma}_{1}\end{pmatrix},\begin{pmatrix}u_{B}\\\ v_{B}\\\
w_{B}\end{pmatrix}\right)_{B}\\\
\otimes|u_{A},u_{A},u_{B},u_{B},v_{A},v_{A},v_{B},v_{B},w_{A},w_{A},w_{B},w_{B}\rangle_{U_{A}U^{\prime}_{A}U_{B}U^{\prime}_{B}V_{A}V^{\prime}_{A}V_{B}V^{\prime}_{B}W_{A}W^{\prime}_{A}W_{B}W^{\prime}_{B}}$
(73)

using the notation of section 2.2, the observation that the elements of the
three tuples
$L_{1}\vec{\sigma}_{3},M_{2}\vec{\sigma}_{1},M_{3}\vec{\sigma}_{1}$ are
independent and commute, and Lemma 4.

Next, use Lemma 6 to deduce that

$\mathcal{W}\mathcal{V}_{simulator}\mathcal{U}_{simulator}\mathcal{V}_{ideal}\mathcal{U}_{ideal}|\phi\rangle|\mathcal{L}\rangle\\\
=\sum_{L,u_{A},v_{A},w_{A},\alpha,\beta}\sqrt{p_{L}}|L,L\rangle_{\mathbf{LL^{\prime}}}\otimes
P\left(\begin{pmatrix}L_{1}\vec{\sigma}_{3}\\\ M_{2}\vec{\sigma_{1}}\\\
M_{3}\vec{\sigma}_{1}\end{pmatrix},\begin{pmatrix}u_{A}\\\ v_{A}\\\
w_{A}\end{pmatrix}\right)_{A}|\psi_{\alpha\beta}\rangle_{AB}\otimes|\gamma_{\alpha\beta}\rangle_{EE^{\prime}}\\\
\otimes|u_{A},u_{A},u_{A}+L_{1}\alpha,u_{A}+L_{1}\alpha\rangle_{U_{A}U^{\prime}_{A}U_{B}U^{\prime}_{B}}\\\
\otimes|v_{A},v_{A},v_{A}+M_{2}\beta,v_{A}+M_{2}\beta\rangle_{V_{A}V^{\prime}_{A}V_{B}V^{\prime}_{B}}\\\
\otimes|w_{A},w_{A},w_{A}+M_{3}\beta,w_{A}+M_{3}\beta\rangle_{W_{A}W^{\prime}_{A}W_{B}W^{\prime}_{B}}\\\
\otimes|f(\alpha),f(\alpha),f(\beta),f(\beta)\rangle_{SS^{\prime}TT^{\prime}}$
(74)

Next, break this up into a sum of two sub-normalized vectors
$|\tau_{accept}\rangle$ and $|\tau_{reject}\rangle$, where
$|\tau_{accept}\rangle$ contains those terms of the sum with $\alpha,\beta\in
B_{n}(0,r)$ and $|\tau_{reject}\rangle$ contains all other terms of the sum.
Note that
$Tr_{S^{\prime}T^{\prime}}|\tau_{accept}\rangle\langle\tau_{reject}|=0$ and
deduce

$\mathcal{E}^{ideal}(|\phi\rangle\langle\phi|)=Tr_{AB\mathbf{L^{\prime}}S^{\prime}T^{\prime}U^{\prime}_{A}U^{\prime}_{B}V^{\prime}_{A}V^{\prime}_{B}W^{\prime}_{A}W^{\prime}_{B}}|\tau_{accept}\rangle\langle\tau_{accept}|\\\
+Tr_{AB\mathbf{L^{\prime}}S^{\prime}T^{\prime}U^{\prime}_{A}U^{\prime}_{B}V^{\prime}_{A}V^{\prime}_{B}W^{\prime}_{A}W^{\prime}_{B}}|\tau_{reject}\rangle\langle\tau_{reject}|$
(75)

Take

$\sigma^{reject}_{LEE^{\prime}STU_{A}V_{A}W_{A}U_{B}V_{B}W_{B}}=Tr_{AB\mathbf{L^{\prime}}S^{\prime}T^{\prime}U^{\prime}_{A}U^{\prime}_{B}V^{\prime}_{A}V^{\prime}_{B}W^{\prime}_{A}W^{\prime}_{B}}|\tau_{reject}\rangle\langle\tau_{reject}|$
(76)

Finally, simplify and use Lemma 5 to deduce that

$Tr_{AB\mathbf{L^{\prime}}S^{\prime}T^{\prime}U^{\prime}_{A}U^{\prime}_{B}V^{\prime}_{A}V^{\prime}_{B}W^{\prime}_{A}W^{\prime}_{B}}|\tau_{accept}\rangle\langle\tau_{accept}|\\\
=\sum_{L,u_{A},v_{A},w_{A},\alpha,\beta:\alpha,\beta\in
B_{n}(0,r)}p_{L}|L\rangle\langle L|_{\mathbf{L}}\\\
\otimes|\gamma_{\alpha\beta}\rangle\langle\gamma_{\alpha\beta}|_{EE^{\prime}}\left(\langle\psi_{\alpha\beta}|P\left(\begin{pmatrix}L_{1}\vec{\sigma}_{3}\\\
M_{2}\vec{\sigma_{1}}\\\
M_{3}\vec{\sigma}_{1}\end{pmatrix},\begin{pmatrix}u_{A}\\\ v_{A}\\\
w_{A}\end{pmatrix}\right)_{A}|\psi_{\alpha\beta}\rangle\right)\\\
\otimes|u_{A},v_{A},w_{A}\rangle\langle
u_{A},v_{A},w_{A}|_{U_{A}V_{A}W_{A}}\\\
\otimes|u_{A}+L_{1}\alpha,v_{A}+M_{2}\beta,w_{A}+M_{3}\beta\rangle\langle
u_{A}+L_{1}\alpha,v_{A}+M_{2}\beta,w_{A}+M_{3}\beta|_{U_{B}V_{B}W_{B}}\\\
\otimes|\alpha,\beta\rangle\langle\alpha,\beta|_{ST}\\\
=\sum_{L,u_{A},v_{A},w_{A},\alpha,\beta:\alpha,\beta\in
B_{n}(0,r)}p_{L}|L\rangle\langle
L|_{\mathbf{L}}\otimes|\gamma_{\alpha\beta}\rangle\langle\gamma_{\alpha\beta}|_{EE^{\prime}}\otimes|\alpha,\beta\rangle\langle\alpha,\beta|_{ST}\\\
\otimes 2^{-n}|u_{A},v_{A},w_{A}\rangle\langle
u_{A},v_{A},w_{A}|_{U_{A}V_{A}W_{A}}\\\
\otimes|u_{A}+L_{1}\alpha,v_{A}+M_{2}\beta,w_{A}+M_{3}\beta\rangle\langle
u_{A}+L_{1}\alpha,v_{A}+M_{2}\beta,w_{A}+M_{3}\beta|_{U_{B}V_{B}W_{B}}$ (77)

which completes the proof. ∎

Finally, note that for any input state $\rho_{ABE}$, applying the final step
of the protocol (the correction of $w_{A},w_{B}$ depending on the values
$s,t$) to $\mathcal{E}_{ideal}(\rho)$ produces an ideal state that satisfies
the assumptions of Lemma 2 with $\epsilon=2^{-k/2+nh(r/n)/2+3/2}$; therefore
the protocol is $2^{-k/2+nh(r/n)/2+5/2}$ secure. Moreover, for any input
$\rho_{ABE}=Tr_{E^{\prime}}|\phi\rangle\langle\phi|_{ABEE^{\prime}}$, the
probability that the protocol accepts is within $2^{-k/2+nh(r/n)/2+3/2}$ of

$\sum_{\alpha,\beta\in
B_{n}(0,r)}\langle\gamma_{\alpha\beta}|\gamma_{\alpha\beta}\rangle=Tr\Pi_{n,r}\rho_{AB}\Pi_{n,r}$
(78)

This completes the proof of Theorem 2.

##  4 Comparison with previous work

The introduction illustrated the advantage of two-universal hashing over
random sampling using specific examples. This section reveals the general
pattern behind the examples in the introduction. To study the advantage of the
two-universal hashing protocol for all block sizes, fix values for the
tolerated error rate and security level, and consider key rate as a function
of block size. How fast does key rate converge to the asymptotic value as
block size goes to infinity? Subsection 4.1 gives the rate of convergence for
the two-universal hashing protocol. Subsection 4.2 gives a bound on the rate
of convergence of the random sampling protocol.

###  4.1 Key rate of the two-universal hashing protocols $\pi(n,k,r)$

Given $n$ qubits per side, the target to tolerate $\delta n$ bit flip and
$\delta n$ phase flip errors, and a target security parameter $\epsilon$, it
suffices to choose $k=\lceil nh(\delta)+2\log_{2}(1/\epsilon)+5\rceil$. The
key rate $1-2k/n$ then satisfies:

$1-2h(\delta)-\frac{4\log_{2}(1/\epsilon)+12}{n}\leq 1-\frac{2k}{n}\leq
1-2h(\delta)-\frac{4\log_{2}(1/\epsilon)+10}{n}$ (79)

Therefore, the rate of convergence of the finite to the asymptotic rate is of
the form $cn^{-1}$.

###  4.2 Key rate of the random sampling protocols

The sequence of works [24, 23, 12] develops QKD protocols and security proofs
optimized for the finite key regime. The current evolution of the
entanglement-based protocol can be found in [23, Section 3]; the difference
between [12] and [23] is only in the random sampling tail bound that is used.
For comparison with the present work we take only the case of perfect
measurements in the rectilinear and diagonal basis. A summary of the protocol
in this case is as follows:

  1. 1.

Eve prepares a state of $2n$ qubits and sends $n$ to Alice and $n$ to Bob.

  2. 2.

Alice and Bob agree on a uniformly random choice of either the rectilinear or
the diagonal basis measurement for each pair of qubits.

  3. 3.

Alice and Bob select a uniformly random subset of $n_{pe}$ positions to serve
for parameter estimation, leaving the remaining $n_{rk}=n-n_{pe}$ to serve as
the raw key.

  4. 4.

Alice and Bob compare their outcomes on the parameter estimation positions. If
the error rate on these positions exceeds a threshold $\delta$, Alice and Bob
abort.

  5. 5.

Alice sends a syndrome of her raw key to Bob, and a two-universal hash of her
raw key to Bob. Bob uses the syndrome to correct his raw key, and uses the
hash to verify that the correction was successful. For simplicity, take the
combined length of syndrome and hash to be the theoretical minimum
$n_{rk}h(\delta)-\log_{2}(\epsilon_{ec})$, where $\epsilon_{ec}$ is the
desired bound on the probability that the hash test passes but Bob’s corrected
raw key does not match Alice’s.

  6. 6.

Alice and Bob compress their raw keys to shorter output keys of length
$n_{out}$ using a two-universal family of hash functions.

The security $\epsilon_{qkd}$ of these protocols can be written in the form

$\epsilon_{qkd}=\epsilon_{ec}+\inf_{0<\nu<1/2-\delta}\left(\epsilon_{pa}(\nu)+\epsilon_{pe}(\nu)\right)$
(80)

where $\epsilon_{ec}$ is the desired bound on the correctness of the protocol,
where

$\epsilon_{pa}(\nu)=\frac{1}{2\sqrt{\epsilon_{ec}}}2^{(-n_{rk}(1-h(\delta+\nu)-h(\delta))+n_{out})/2}$
(81)

is a bound on the secrecy of the protocol, and where

$\epsilon_{pe}(\nu)=\inf_{0<\xi<\nu}\epsilon_{pe}(\nu,\xi)$ (82)

comes from a tail bound for random sampling. The precise form of the function
$\epsilon_{pe}(\nu,\xi)$ is given in [12, Lemma 2] and satisfies the equation

$\left(\frac{\epsilon_{pe}(\nu,\xi)}{2}\right)^{2}=exp\left(-\frac{2nn_{pe}\xi^{2}}{n_{rk}+1}\right)+exp\left(-\frac{2(n+2)(n_{rk}^{2}(\nu-\xi)^{2}-1)}{(n(\delta+\xi)+1)(n(1-\delta-\xi)+1)}\right)$
(83)

For the purpose of this section, consider the following lower bound on
$\epsilon_{pe}(\nu)$:

######  Lemma 14.

Suppose $n_{rk}\geq n/2$. Then,

$\epsilon_{pe}(\nu)\geq 2exp(-2n_{pe}\nu^{2})$ (84)

###### Proof.

Take any $\xi\in(0,\nu)$. Note that

$\frac{2nn_{pe}\xi^{2}}{n_{rk}+1}\leq 4n_{pe}\nu^{2}$ (85)

and therefore

$exp\left(-\frac{2nn_{pe}\xi^{2}}{n_{rk}+1}\right)\geq
exp\left(-4n_{pe}\nu^{2}\right)$ (86)

The lemma follows. ∎

The following bound holds on the key rate of the random sampling protocols:

######  Theorem 3.

Fix the block size $n$, the tolerated error rate $\delta$ and the security
level

$\epsilon_{qkd}=\epsilon_{ec}+\inf_{0<\nu<1/2-\delta}\left(\epsilon_{pa}(\nu)+\epsilon_{pe}(\nu)\right)$
(87)

Then, the key rate $n_{out}/n$ is upper bounded by the larger of
$(1-2h(\delta))/2$ and

$(1-2h(\delta))-c_{1}(\epsilon_{qkd},\delta)n^{-1/3}-c_{2}(\epsilon_{qkd})n^{-1}$
(88)

where

$\displaystyle c_{1}(\epsilon_{qkd},\delta)$
$\displaystyle=\frac{3}{2^{5/3}}(1-2h(\delta))^{1/3}\left(\frac{1-h(\delta)}{1/2-\delta}\right)^{2/3}\left(\ln\frac{2}{\epsilon_{qkd}}\right)^{1/3}$
(89) $\displaystyle c_{2}(\epsilon_{qkd})$
$\displaystyle=3\log_{2}(1/\epsilon_{qkd})+3\log_{2}(3)-4$ (90)

###### Proof.

Take the optimal $\nu$. In case $n_{rk}/n<1/2$, then

$\frac{n_{out}}{n}\leq\frac{n_{rk}(1-h(\delta+\nu)-h(\delta))}{n}\leq\frac{1-2h(\delta)}{2}$
(91)

Suppose now that $n_{rk}/n\geq 1/2$. Simplify the problem by eliminating
$\epsilon_{ec}$: note that

$\epsilon_{ec}+\epsilon_{pa}(\nu)=\epsilon_{ec}+\frac{1}{2\sqrt{\epsilon_{ec}}}2^{(-n_{rk}(1-h(\delta+\nu)-h(\delta))+n_{out})/2}\\\
\geq\frac{3}{2^{4/3}}2^{(-n_{rk}(1-h(\delta+\nu)-h(\delta))+n_{out})/3}$ (92)

with equality if and only if

$\epsilon_{ec}=\frac{1}{2^{4/3}}2^{(-n_{rk}(1-h(\delta+\nu)-h(\delta))+n_{out})/3}$
(93)

Use this and Lemma 14 to deduce

$\frac{3}{2^{4/3}}2^{(-n_{rk}(1-h(\delta+\nu)-h(\delta))+n_{out})/3}+2exp(-2n_{pe}\nu^{2})\leq\epsilon_{qkd}$
(94)

From this, deduce further:

$\displaystyle-n_{rk}(1-h(\delta+\nu)-h(\delta))+n_{out}$ $\displaystyle\leq
3\log_{2}\epsilon_{qkd}+4-3\log_{2}(3)$ (95) $\displaystyle-2n_{pe}\nu^{2}$
$\displaystyle\leq\ln(\epsilon_{qkd})-\ln(2)$ (96)

Rewrite the first inequality as

$n_{out}\leq
n(1-2h(\delta))-n_{pe}(1-2h(\delta))-n_{rk}(h(\delta+\nu)-h(\delta))\\\
+3\log_{2}\epsilon_{qkd}+4-3\log_{2}(3)$ (97)

Now, apply the inequality $a+b\geq 3a^{1/3}(b/2)^{2/3}$ to the second and
third term:

$n_{pe}(1-2h(\delta))+n_{rk}(h(\delta+\nu)-h(\delta))\\\
\geq\frac{3}{2^{2/3}}n_{pe}^{1/3}(1-2h(\delta))^{1/3}n_{rk}^{2/3}(h(\delta+\nu)-h(\delta))^{2/3}\\\
\geq\frac{3}{2^{2/3}}n_{pe}^{1/3}(1-2h(\delta))^{1/3}\left(n/2\right)^{2/3}(h(\delta+\nu)-h(\delta))^{2/3}$
(98)

Further, use the line through $(\delta,h(\delta))$ and $(1/2,1)$ to obtain

$h(\delta+\nu)-h(\delta)\geq\nu\frac{1-h(\delta)}{1/2-\delta}$ (99)

then combine this with $n_{pe}\nu^{2}\geq 0.5\ln(2/\epsilon_{qkd})$ to obtain

$n_{pe}^{1/3}(h(\delta+\nu)-h(\delta))^{2/3}\geq\left(\frac{1-h(\delta)}{1/2-\delta}\right)^{2/3}\left(\frac{1}{2}\ln\frac{2}{\epsilon_{qkd}}\right)^{1/3}$
(100)

Thus,

$n_{pe}(1-2h(\delta))+n_{rk}(h(\delta+\nu)-h(\delta))\\\
\geq\frac{3}{2^{5/3}}(1-2h(\delta))^{1/3}\left(\frac{1-h(\delta)}{1/2-\delta}\right)^{2/3}\left(\ln\frac{2}{\epsilon_{qkd}}\right)^{1/3}n^{2/3}$
(101)

Combining with (97) proves the Theorem. ∎

##  5 Conclusion and open problems

The present paper has proposed and proved security of a QKD protocol that uses
two-universal hashing instead of random sampling to perform parameter
estimation. This protocol dramatically outperforms previous QKD protocols for
small block sizes. This provides a new approach in QKD use-cases such as the
Micius satellite example, where the difficulty of accumulating a large enough
block size makes the BBM92 protocol impractical. The quantum phase of the two-
universal hashing protocol is also impractical with current technology.
However, it appears easier to make a moderate advance in ground stations and a
moderate advance in the transmission of entangled photon pairs from space to
earth, rather than to put the entire burden on only one of these approaches.

The first group of open problems are related to the quantum phase of the two-
universal hashing protocol. On the theoretical side, what are the fundamental
trade-offs between the complexity of the quantum phase of a QKD protocol and
its performance? Can good performance be achieved using a simpler quantum
phase than the two-universal hashing protocol? Further, can QKD hardware be
developed capable of more than just single qubit measurements?

Second, the algorithm given in section 2.3 for computing the function
$g_{B_{n}(0,r)}$ is not efficient. This leads to the following open problem:
is there a probability distribution over CSS codes, such that the marginal
distributions of the two parity check matrices satisfy a two-universal hashing
condition with some good collision probability bound, and such that each of
the two parity check matrices has additional structure that allows efficient
computation of $g_{B_{n}(0,r)}$ during the protocol? There is a long history
in information theory of approximating the performance of random codes with
brute force decoding by more structured codes with efficient decoding, so
there is reason to hope that the same can be done in the present case.

Third, the arguments in the present paper are for the case where Alice and Bob
can apply perfect quantum operations. It thus remains an open problem to
generalize the present security proof to the case of imperfect devices.

## References

  * [1] Charles H. Bennett, David P. DiVincenzo, John A. Smolin, and William K. Wootters.  Mixed-state entanglement and quantum error correction.  Phys. Rev. A, 54:3824–3851, Nov 1996.  URL: https://link.aps.org/doi/10.1103/PhysRevA.54.3824, doi:10.1103/PhysRevA.54.3824.
  * [2] Niek J Bouman and Serge Fehr.  Sampling in a quantum population, and applications.  In Annual Cryptology Conference, pages 724–741. Springer, 2010\.  doi:10.1007/978-3-642-14623-7_39.
  * [3] Gilles Brassard and Louis Salvail.  Secret-key reconciliation by public discussion.  In Workshop on the Theory and Application of of Cryptographic Techniques, pages 410–423. Springer, 1993.  doi:10.1007/3-540-48285-7_35.
  * [4] A. R. Calderbank, E. M. Rains, P. W. Shor, and N. J. A. Sloane.  Quantum error correction and orthogonal geometry.  Phys. Rev. Lett., 78:405–408, Jan 1997.  URL: https://link.aps.org/doi/10.1103/PhysRevLett.78.405, doi:10.1103/PhysRevLett.78.405.
  * [5] A. R. Calderbank and Peter W. Shor.  Good quantum error-correcting codes exist.  Phys. Rev. A, 54:1098–1105, Aug 1996.  URL: https://link.aps.org/doi/10.1103/PhysRevA.54.1098, doi:10.1103/PhysRevA.54.1098.
  * [6] J.Lawrence Carter and Mark N. Wegman.  Universal classes of hash functions.  Journal of Computer and System Sciences, 18(2):143–154, 1979.  URL: https://www.sciencedirect.com/science/article/pii/0022000079900448, doi:10.1016/0022-0000(79)90044-8.
  * [7] Peter Elias.  Coding for two noisy channels.  In Colin Cherry, editor, Information Theory, 3rd London Symposium, London, England, Sept. 1955. Butterworth’s scientific publications, 1956.  URL: https://worldcat.org/en/title/562487502, doi:10.1038/176773a0.
  * [8] Chi-Hang Fred Fung, Xiongfeng Ma, and H. F. Chau.  Practical issues in quantum-key-distribution postprocessing.  Physical Review A, 81(1), Jan 2010.  URL: http://dx.doi.org/10.1103/PhysRevA.81.012318, doi:10.1103/physreva.81.012318.
  * [9] Robert G. Gallager.  Low-Density Parity-Check Codes.  The MIT Press, 09 1963.  doi:10.7551/mitpress/4347.001.0001.
  * [10] Daniel Gottesman.  Class of quantum error-correcting codes saturating the quantum hamming bound.  Phys. Rev. A, 54:1862–1868, Sep 1996.  URL: https://link.aps.org/doi/10.1103/PhysRevA.54.1862, doi:10.1103/PhysRevA.54.1862.
  * [11] M Koashi.  Simple security proof of quantum key distribution based on complementarity.  New Journal of Physics, 11(4):045018, apr 2009.  URL: https://dx.doi.org/10.1088/1367-2630/11/4/045018, doi:10.1088/1367-2630/11/4/045018.
  * [12] Charles Ci-Wen Lim, Feihu Xu, Jian-Wei Pan, and Artur Ekert.  Security analysis of quantum key distribution with small block length and its application to quantum space communications.  Physical Review Letters, 126(10), Mar 2021.  URL: http://dx.doi.org/10.1103/PhysRevLett.126.100501, doi:10.1103/physrevlett.126.100501.
  * [13] Hoi-Kwong Lo and H. F. Chau.  Unconditional security of quantum key distribution over arbitrarily long distances.  Science, 283(5410):2050–2056, mar 1999.  URL: https://doi.org/10.1126%2Fscience.283.5410.2050, doi:10.1126/science.283.5410.2050.
  * [14] Michael A. Nielsen and Isaac L. Chuang.  Quantum Computation and Quantum Information.  Cambridge University Press, jun 2012.  URL: https://doi.org/10.1017%2Fcbo9780511976667, doi:10.1017/cbo9780511976667.
  * [15] Dimiter Ostrev.  Composable, unconditionally secure message authentication without any secret key.  In 2019 IEEE International Symposium on Information Theory (ISIT), pages 622–626, 2019.  doi:10.1109/ISIT.2019.8849510.
  * [16] S. Pirandola, U. L. Andersen, L. Banchi, M. Berta, D. Bunandar, R. Colbeck, D. Englund, T. Gehring, C. Lupo, C. Ottaviani, J. L. Pereira, M. Razavi, J. Shamsul Shaari, M. Tomamichel, V. C. Usenko, G. Vallone, P. Villoresi, and P. Wallden.  Advances in quantum cryptography.  Adv. Opt. Photon., 12(4):1012–1236, Dec 2020.  URL: http://opg.optica.org/aop/abstract.cfm?URI=aop-12-4-1012, doi:10.1364/AOP.361502.
  * [17] Christopher Portmann.  Key recycling in authentication.  IEEE Transactions on Information Theory, 60(7):4383–4396, 2014\.  doi:10.1109/TIT.2014.2317312.
  * [18] Christopher Portmann and Renato Renner.  Cryptographic security of quantum key distribution, 2014.  URL: https://arxiv.org/abs/1409.3525, doi:10.48550/ARXIV.1409.3525.
  * [19] Renato Renner.  Security of Quantum Key Distribution.  PhD thesis, ETH Zurich, 2005.  URL: https://arxiv.org/abs/quant-ph/0512258, doi:10.48550/ARXIV.QUANT-PH/0512258.
  * [20] Peter W. Shor and John Preskill.  Simple proof of security of the bb84 quantum key distribution protocol.  Phys. Rev. Lett., 85:441–444, Jul 2000.  URL: https://link.aps.org/doi/10.1103/PhysRevLett.85.441, doi:10.1103/PhysRevLett.85.441.
  * [21] Andrew Steane.  Multiple-particle interference and quantum error correction.  Proceedings of the Royal Society of London. Series A: Mathematical, Physical and Engineering Sciences, 452(1954):2551–2577, 1996.  URL: https://royalsocietypublishing.org/doi/abs/10.1098/rspa.1996.0136, doi:10.1098/rspa.1996.0136.
  * [22] W. Forrest Stinespring.  Positive functions on c*-algebras.  Proceedings of the American Mathematical Society, 6(2):211–216, 1955.  URL: http://www.jstor.org/stable/2032342, doi:10.2307/2032342.
  * [23] Marco Tomamichel and Anthony Leverrier.  A largely self-contained and complete security proof for quantum key distribution.  Quantum, 1:14, Jul 2017.  URL: http://dx.doi.org/10.22331/q-2017-07-14-14, doi:10.22331/q-2017-07-14-14.
  * [24] Marco Tomamichel, Charles Ci Wen Lim, Nicolas Gisin, and Renato Renner.  Tight finite-key analysis for quantum cryptography.  Nature communications, 3(1):1–6, 2012.  doi:10.1038/ncomms1631.
  * [25] Mark N. Wegman and J.Lawrence Carter.  New hash functions and their use in authentication and set equality.  Journal of Computer and System Sciences, 22(3):265–279, 1981.  URL: https://www.sciencedirect.com/science/article/pii/0022000081900337, doi:10.1016/0022-0000(81)90033-7.
  * [26] Juan Yin, Yu-Huai Li, Sheng-Kai Liao, Meng Yang, Yuan Cao, Liang Zhang, Ji-Gang Ren, Wen-Qi Cai, Wei-Yue Liu, Shuang-Lin Li, et al.  Entanglement-based secure quantum cryptography over 1,120 kilometres.  Nature, 582(7813):501–505, 2020.  doi:10.1038/s41586-020-2401-y.