QCrypt in Toulouse: Key Distribution

These are notes for the third session of the Quantum Cryptography Workgroup in Toulouse. More info can be found here.

In the previous two sessions we have introduced the fundamental ideas underlying (quantum) cryptography and developed helpful mathematical tools. We now want to distribute actual keys. First classically, then quantumly.

Definition. A key distribution protocol is a protocol that lets Alice and Bob agree on an $m$-bit key $K \in \{0, 1\}^m$. It is

• $\varepsilon$-correct if the protocol succeeds with probability at least $1-\varepsilon$, that is, if Alice and Bob have derived keys $K_A, K_B$ according to the protocol then $\operatorname{Pr}[K_A \neq K_B] \leq \varepsilon$.
• $\varepsilon$-secure if an eavesdropper Eve is almost ignorant about the key, that is $D(\rho_{KE}, I /2^m \otimes \rho_E) \leq \varepsilon$.

Such a protocol may work only under specific assumptions on the communication channels that Bob and Alice have access to. Generally, we will distinguish between the following types of communication channels.

1. Classical channel
2. Classical authenticated channel
3. Classical secret channel
4. Classical secret and authenticated channel
5. Quantum channel

A classical toy protocol

As a warmup, let us consider a purely classical protocol in a toy model. We assume that Alice and Bob have access to a classical authenticated channel (CAC) and want to establish a key over a classical channel to which Eve has limited access in the following sense. If Alice sends a bit $b$ over the channel,

• Bob correctly receives $b$
• Eve receives $b$ with probability $q$ and $1 - b$ with probability $1-q$.

The induced channel Alice $\to$ Eve is also called the binary symmetric channel $\operatorname{BSC}(q)$ in the information theory literature.

Recall the definition of an $\varepsilon$-strong seeded extractor.

Definition. A $(k, \varepsilon)$-strong seeded extractor is a function $\operatorname{Ext}: \{0, 1\}^n \times \{0, 1\}^m \to \{0, 1\}^k$ such that for any qc state with $H_{\text{min}}(X \mid E) \geq k$, $$D(\rho_{\operatorname{Ext}(X, Y)YE}, \frac{I}{2^m} \otimes \rho_{YE}) \leq \varepsilon.$$

Now consider the following protocol.

Protocol 1 – Key distribution over a special channel.

1. Alice chooses $x = x_1 \dots x_n \in \{0, 1\}^n$ uniformly at random and sends the bits $x_i$ over the channel.
2. Alice picks random seed $r \in \{0, 1\}^m$ and applies an $(c, \varepsilon)$-strong seeded extractor to $x$, computing $k = \operatorname{Ext}(x, r) \in \{0, 1\}^\ell$.
3. Alice sends $r$ over the CAC.
4. Bob computes $k = \operatorname{Ext}(x, r)$.

Clearly the protocol is $\varepsilon$-correct, as there are no errors in the communication between Bob and Alice, and they compute the same function to obtain the key $k$.

It is also not hard to see that the protocol is $\varepsilon$-secure. Recall that we introduced randomness extractors as a way to “purify” some shared $k$-bits of entropy between Alice and Bob. Sending bits over a channel to which Eve has only limited access is simply a way of establishing these initial $k$ bits of entropy. The fact that Eve has some knowledge about the seed is unimportant since we use a strong seeded extractor.

We can determine what the constants $c$ and $\ell$ have to be: From Eve’s perspective the cq state of the key shared by Alice and Bob is

$$\rho_K = \bigotimes_{i = 1}^n q \ket{x_i}\bra{x_i} + (1-q) \ket{1 - x_i} \bra{1 - x_i}$$

Assuming $q \leq 1/2$, this state has min entropy

$$H_{\text{min}}(K) = - \log \max p_x = - \log (1-q)^n = -n \log (1-q),$$

so we must choose $c = -n \log (1-q)$. Selecting $\operatorname{Ext}(-, r)$ among a 2-universal family of hash functions, we can choose $\ell$ as large as $-n \log (1-q) - 2\log(1/\varepsilon) - 1$, as seen in the last session.

Remark. Of course the same protocol works for other restrictions on the channel, for example if Eve receives all sent bits correctly but only has limited memory.

The CAC assumption

Before we introduce a key distribution algorithm that works without additional restrictions on potential eavesdroppers, we need to address the assumption that Alice and Bob have access to a classical authenticated channel.

There are generally two approaches to implementing an authenticated channel: Message Authentication Codes (MACs) and Digital Signatures. However, both approaches have drawbacks in a quantum key distribution context. MACs use private key cryptography — so Alice and Bob already need to have a shared private key in advance! Digital Signatures, on the other hand, do not require an established private key, but make use of computational assumptions that generally no longer hold in the quantum era.

Does this mean that the CAC assumption is too strong? The answer is nuanced. Let us take a look at both approaches individually.

MACs

The idea behind message authentication codes is that based on a shared private key, Alice generates a tag for her message. With the same key, Bob can verify the validity of the tag for a given message. Formally, a message authentication code is a pair of functions

• $\operatorname{Tag}\colon \mathcal{M} \times \mathcal{K} \to \mathcal{T}$, which takes a message and a key, and returns a tag.
• $\operatorname{Ver}\colon \mathcal{M} \times \mathcal{K} \times \mathcal{T} \to \{0,1\}$, which takes a message, a key, and a claimed tag for the message. It then returns whether the tag is valid for the message.

Both functions are required to run in polynomial time.

A MAC is correct if $$\operatorname{Ver}(m, k, \operatorname{Tag}(m, k)) = 1.$$

It is secure if, informally speaking, it is impossible for an adversary to generate a new pair of a message and a corresponding valid tag, even if he has access to arbitrarily many valid (message, tag) pairs (except with negligible probability).

Example. An example of a one-time MAC¹ can be constructed using a 2-universal family of hash functions. Given such a family $\mathcal{F} = \{f_i \colon \{0, 1\}^n \to \{0, 1\}^\ell \mid i \in I \}$,

• The key is an element $k \in I$.
• $\operatorname{Tag}(m, k) \coloneqq f_k(m)$.
• $\operatorname{Ver}(m, k, \tau) \coloneqq [f_k(m) = \tau]$.

Obviously this scheme is correct. Moreover it is secure by the 2-universality of $\mathcal{F}$: Suppose an adversary is given a single valid pair $(m, \tau)$. Since $\mathcal{F}$ is in particular $1$-universal, the value of $\tau = f(k, m)$ does not tell them anything about $k$. Hence the only way to generate a new valid pair $(m', \tau')$ is to guess $k$, which is successful with probability

$$\Pr_{i \in I} [f_i(m') = \tau' \mid f_i(m) = \tau] = \frac{\Pr_{i \in I}[f_i(m') = \tau' \land f_i(m) = \tau]}{\Pr_{i \in I}[f_i(m) = \tau]} = \frac{2^{-2\ell}}{2^{-\ell}} = 2^{-\ell}.$$

For maximal security, one would choose $\ell$ to be as large as possible, i.e. $\ell = n$. Note, however, that any $1$-universal family of hash functions $\{0,1\}^n \to \{0, 1\}^\ell$ needs to have at least $2^\ell$ elements, so the key needs to have length $\log |\mathcal{F}| = n$, that is, be just as long as the message.

Under the assumption that one-way functions exist², one can find secure MACs that use shorter keys or allow reusing a key arbitrarily many times.

In the context of key distribution algorithms, however, the conceptual problem that Alice and Bob need to already share a private key remains.

Digital Signatures

As opposed to MACs, digital signatures make use of public-key cryptography. The idea is that Alice generates a pair $(k_{pub}, k_{priv}) \in \mathcal{K} \times \mathcal{K}'$ of a public and a private key. Alice keeps her private key secret and shares her public key. A digital signature scheme is then a pair of functions

• $\operatorname{Sign}\colon \mathcal{M} \times \mathcal{K}' \to \mathcal{S}$, which takes a message and a private key, and outputs a signature.
• $\operatorname{Ver}\colon \mathcal{M} \times \mathcal{K} \times \mathcal{S} \to \{0, 1\}$, which takes a message, a public key, and a claimed signature and outputs whether the signature is valid.

Both functions are required to run in polynomial time, $\operatorname{Sign}$ may be probabilistic.

The scheme is correct if $$\operatorname{Pr} [\operatorname{Ver}(m, k_{pub}, \operatorname{Sign}(m, k_{priv}) = 1] = 1.$$

Security is defined similarly as for MACs.

Example. A common digital signature scheme³ is based on RSA. Here we choose two large primes $p, q$ and let $N = pq$. We then choose a positive integer $e$ and compute a $d$ such that $ed \equiv 1 \mod \varphi(N)$. The public key is $(N, e)$, the private key is $d$. We then let

$$\operatorname{Sign}(m, d) \coloneqq \eta(m)^d$$ $$\operatorname{Ver}(m, (N, e), \sigma) \coloneqq [\sigma^e \equiv \eta(m) \mod N],$$

where $\eta$ is an embedding of the message space into $\mathbb{Z}$.

Of course, the above algorithm is no longer secure in a post-quantum setting. An obvious idea is to base the signature scheme on a post-quantum cryptographic algorithm like LWE instead. However, these types of algorithms are exactly what quantum key distribution is supposed to replace!

A slightly more convincing argument for digital signatures is that keys generated by a quantum key distribution protocol enjoy everlasting security, even if the authentication scheme underlying the CAC is broken afterwards. It suffices for the CAC to remain authenticated for the duration of the protocol, which is at most on the order of seconds. The signature scheme used to implement it may hence not necessarily need to be provably secure as long as it is “strong enough”.

The BB-84 quantum key distribution protocol

As an example of an actual quantum key distribution protocol, we look at the well-known BB84 protocol, proposed by Bennett and Brassard in 1984.

Protocol 2 – BB-84.

1. Fix a large integer $n$ and let $N = 4n$.
2. Alice chooses strings $x = x_1 \dots x_N \in \{0, 1\}^N$ and $\theta = \theta_1 \dots \theta_N \in \{0, 1\}^N$ uniformly at random. She sends Bob each bit $x_i$ by encoding as a quantum state according to $\theta_i$ as $H^{\theta_i} \ket{x_i}$.
3. Bob chooses a string $\tilde{\theta} = \tilde{\theta}_1 \dots \tilde{\theta}_N \in \{0, 1\}^N$ uniformly at random, and measures the $i$th received qubit in the basis corresponding to $\tilde{\theta}_i$. This yields a string $\tilde{x} = \tilde{x}_1 \dots \tilde{x}_N$.
4. Bob tells Alice over the CAC that he has received and measured all the qubits.
5. Alice and Bob exchange their basis strings $\theta, \tilde{\theta}$ over the CAC.
6. Alice and Bob discard all bits $i$ of $x$ and $\tilde{x}$ respectively where $\theta_i \neq \tilde{\theta}_i$, yielding strings $x'$ and $\tilde{x}'$
7. Alice and Bob check for eavesdroppers:
   1. Alice picks a random subset $T \subseteq \{i \in [N] \mid \theta_i = \tilde{\theta}_i\}$ and tells Bob $T$ over the CAC.
   2. Alice and Bob exchange $x_T$ and $\tilde{x}_T$ over the CAC. They compute the number of errors $W = |\{i \in T \mid x_i \neq \tilde{x}_i \}|$.
   3. If $W > 0$, Alice and Bob abort the protocol. Otherwise they proceed with the strings $x'' = x'_{S \setminus T}$ and $\tilde{x}'' = \tilde{x}'_{S \setminus T}$.
8. Alice and Bob perform privacy amplification: Alice picks a random seed $r$ and computes $k = \operatorname{Ext}(x'', r)$. She then sends $r$ to Bob, who computes $k = \operatorname{Ext}(\tilde{x}'', r)$.

Consider the following example run of the protocol.

It is not hard to see that the protocol is correct. Clearly, when $\theta_i$ and $\tilde{\theta}_i$ agree then so will $x_i$ and $\tilde{x}_i$. It follows that $x'' = \tilde{x''}$ and hence $\operatorname{Ext}(x'', r) = \operatorname{Ext}(\tilde{x}'', r)$.

Security of BB-84

The security of BB-84 is intuitively clear: If Eve tries to measure Alice’s qubit in a basis that does not agree with the one that Alice used for the encoding, she will introduce an error in Bob’s measurement with probability $1/2$. The requirement that the error rate be $0$ on a random subset of qubits of size $\approx N/4$ then lower-bounds the min-entropy $H_{\text{min}}(X'' \mid E)$. A round of privacy amplification then extracts a key that Eve is ignorant about.

In this sense, the general idea mirrors our toy protocol.

Formalising this idea is more involved, in particular because Eve might apply more involved attacks like entangling her system with the sent qubits. In fact it is so difficult that it took more than 20 years to give a proof that does not only work asymptotically. We will show security asymptotically in a restricted case.

To simplify the analysis, we first adapt the protocol somewhat. We assume that Alice and Bob share an EPR pair, and Alice measures her part of the state in some choice of basis to obtain the random string $x$. We also allow a non-zero error rate in step 7.

Protocol 3 – Purified BB-84

1. Fix a large integer $n$ and let $N = 4n$
2. Alice prepares $N$ EPR pairs and sends the second qubit to Bob respectively.
3. Alice chooses a string $\theta = \theta_1 \dots \theta_N \in \{0, 1\}^N$ uniformly at random. She then measures the first qubit of the $i$th EPR pair in the $Z$ or $X$ basis depending on $\theta_i$ to obtain a random string $x = x_1 \dots x_N \in \{0, 1\}^N$.
4. Bob chooses a string $\tilde{\theta} = \tilde{\theta}_1 \dots \tilde{\theta}_N \in \{0, 1\}^N$ uniformly at random, and measures the second qubit of the $i$th EPR pair in the basis corresponding to $\tilde{\theta}_i$. This yields a string $\tilde{x} = \tilde{x}_1 \dots \tilde{x}_N$.
5. Bob tells Alice over the CAC that he has measured all the qubits.
6. Alice and Bob exchange their basis strings $\theta, \tilde{\theta}$ over the CAC.
7. Alice and Bob discard all bits $i$ of $x$ and $\tilde{x}$ respectively where $\theta_i \neq \tilde{\theta}_i$, yielding strings $x'$ and $\tilde{x}'$
8. Alice and Bob check for eavesdroppers:
   1. Alice picks a random subset $T \subseteq \{i \in [N] \mid \theta_i = \tilde{\theta}_i\}$ and tells Bob $T$ over the CAC.
   2. Alice and Bob exchange $x_T$ and $\tilde{x}_T$ over the CAC. They compute the error rate $\delta = W/|T|$, where $W = |\{i \in T \mid x_i \neq \tilde{x}_i \}|$.
   3. If $\delta$ is too large, Alice and Bob abort the protocol.
9. Alice and Bob perform privacy amplification on the remaining bits.

Note that the use of entangled states is equivalent to the original approach. Moreover, the weakened requirements on the error rate make Protocol 3 generally less secure than Protocol 2. If we can prove security for this modified protocol, then the original protocol must also be secure.

Next, we significantly increase the power of an eavesdropper. We assume that it is Eve who initially prepares a state $\rho_{ABE}$, whose $A$ and $B$ systems consist of $n$ qubits respectively, that she distributes to Alice and Bob. Alice and Bob then proceed as usual with the measurements on their respective qubits.

If $\rho_{ABE} = \ket{\Psi^+}\bra{\Psi^+}^{\otimes N} \otimes \rho_E$ we just recover Protocol 3.

Any possible attack (excluding side-channel attacks) can be modeled as Eve simply distributing a specific $\rho_{ABE}$. On the other hand, not every state $\rho_{ABE}$ can be achieved by only interacting with the qubits sent over the channel. Eve’s power has strictly increased.

We will show that despite this additional power given to Eve, the protocol is still secure, assuming $\rho_{ABE}$ is not entangled between rounds. When there are no restrictions on $\rho_{ABE}$ the protocol is still secure, but the analysis becomes too complicated to cover here.

To show that Protocol 3 is secure, it suffices to show that it is able to detect whether $\rho_{ABE}$ is close enough to $\ket{\Psi^+}\bra{\Psi^+}^{\otimes N} \otimes \rho_E$. The obvious way Alice and Bob could verify this is to add an initial step to the protocol as follows:

0. After receiving $\rho_{ABE}$ from Eve, Alice and Bob jointly measure their qubit pairs using the POVM $\{\ket{\Psi^+}\bra{\Psi^+}, I - \ket{\Psi^+} \bra{\Psi^+}\}$. If for some $\delta \ll 1$ more than $\delta n$ of the pairs are found not to be in state $\ket{\Psi^+}$, Alice and Bob abort the protocol.

Such a step would also make step 7 of Protocol 3 redundant. Of course this hypothetical step 0 is impossible to implement, because Alice and Bob can only perform local measurements on their respective systems. We argue that step 7 is essentially equivalent to step 0.

Lemma 1. Let $\rho_{ABE}$ be a tripartite state, where $A$ and $B$ are systems of a single qubit. Then the probability that respective measurements of systems $A$ and $B$ in the computational basis result in matching outcomes is exactly $\operatorname{Tr} (\Pi_1 \rho_{AB})$, where $$\Pi_1 = \ket{\Psi^+}\bra{\Psi^+} + \ket{\Psi^-}\bra{\Psi^-}.$$ Similarly, the probability that the outcomes match when measuring in the Hadamard basis is $\operatorname{Tr} (\Pi_2\rho_{AB})$, where $$\Pi_2 = \ket{\Psi^+}\bra{\Psi^+} + \ket{\Phi^+}\bra{\Phi^+}.$$

Proof.

The probability of matching measurement outcomes in the computational basis is given by $$P_{\text{match}} = \braket{00 | \rho_{AB} | 00} + \braket{11 | \rho_{AB} | 11} = \operatorname{Tr} ((\ket{00}\bra{00} + \ket{11}\bra{11})\rho_{AB})$$ and we have $$\ket{\Psi^+}\bra{\Psi^+} + \ket{\Psi^-}\bra{\Psi^-}$$ $$= \frac{1}{2}(\ket{00}\bra{00} + \ket{00}\bra{11} + \ket{11}\bra{00} + \ket{11}\bra{11} + \ket{00}\bra{00} - \ket{00}\bra{11} - \ket{11}\bra{00} + \ket{11}\bra{11})$$ $$= \ket{00}\bra{00} + \ket{11}\bra{11}.$$ Completely analogous, in the Hadamard basis we have $$P_{\text{match}} = \operatorname{Tr}((\ket{++}\bra{++} + \ket{--}\bra{--})\rho_{AB})$$ and $$\ket{\Psi^+}\bra{\Psi^+} + \ket{\Phi^+}\bra{\Phi^+} = \ket{++}\bra{++} + \ket{--}\bra{--}.$$

Now consider an arbitrary $\rho_{ABE}$ that we assume to be of the form $\bigotimes_i \rho_{A_iB_iE_i}$. Expressing the $AB$-marginal of a single round in the Bell basis yields

$$\rho_{A_iB_i} = q_{00}\ket{\Psi^+}\bra{\Psi^+} + q_{01}\ket{\Psi^-}\bra{\Psi^-} + q_{10}\ket{\Phi^+}\bra{\Phi^+} + q_{11}\ket{\Phi^-}\bra{\Phi^-} + \text{c. t.}$$

The probability that the POVM in step 0 measures $\ket{\Psi^+}$ is $q_{00}$, while by Lemma 1 the probability $p_i$ of succeeding in step 7 of Protocol 3 is given by

$$p_i = \frac{1}{2} + \frac{1}{4}(\operatorname{Tr}(\Pi_1 \rho_{A_iB_i}) + \operatorname{Tr}(\Pi_2 \rho_{A_iB_i})) = \frac{1}{2} + \frac{1}{2}q_{00} + \frac{1}{4}(q_{01} + q_{10}) \leq \frac{1}{2}q_{00} + 1.$$

In other words $q_{00} \geq 2p_i - 1$, so if the probability of success in step 7 is close to one, say $1-\delta$, then the overlap with $\ket{\Psi^+}\bra{\Psi^+}$ is correspondingly large, $q_{00} \geq 1 - 2\delta$. Of course the converse holds trivially.

However, this does not yet prove that step 0 and step 7 are essentially equivalent. This is because step 7 only tests a subset $T$ of the qubits. Intuitively however, since $T$ is chosen randomly, this testing step should upper bound the number of errors on the remaining qubits as well. We can make this precise through a Hoeffding-type inequality.

Lemma 2 (Tomamichel & Leverrier). Let $m = k + \ell$ and consider binary random variables $Z_1, \dots, Z_m$. Let $T$ be a uniformly random subset of $\{1, \dots, m\}$ of size $k$. Then for any $\delta, \nu > 0$, it holds that $$\Pr \left[\sum_{j \in T} Z_j \leq \delta k \land \sum_{j \in [m] \setminus T} Z_j \geq (\delta + \nu)n \right] \geq \exp\left(-2 \nu^2 \frac{k^2 \ell}{(k + \ell)(k + 1)}\right).$$

We will let $Z_i$ denote the indicator random variable such that $Z_i = 1$ if $x'_i \neq \tilde{x}'_i$ in step 7 of Protocol 3. We then let $m = 2n$, $k = \ell = n$ and $\nu = \delta = \delta_c$ where $\delta_c$ is the largest tolerated error rate in step 7c. In the asymptotic limit, we may assume that the $T$ chosen in step 7a has size exactly $2n/2$, hence Lemma 2 applies. We thus get the bound

$$\Pr \left[\neg \text{ABORT} \land \sum_{[2n] \setminus T} Z_j \geq 2\delta_c n \right] = \Pr \left[\sum_{j \in T} Z_j \leq \delta_c n \land \sum_{[2n] \setminus T} Z_j \geq 2 \delta_c n \right] \leq \exp (-\delta_c^2 \frac{n^2}{n+1}) \leq \exp(-\delta_c n),$$

which vanishes as $n \to \infty$.

It follows that step 7 implies that the error rate on the whole qubit string is sufficiently low, which by our previous observations implies that the overlap of $\rho_{AB}$ with $\ket{\Psi^+}\bra{\Psi^+}^{\otimes N}$ is sufficiently high. This completes the asymptotic security proof of Protocol 3 in the restricted threat model. Since Protocol 3 is less secure than Protocol 2, we can conclude the security of BB-84.

Information Reconciliation

Until now, we assumed that all communication is error-free. Of course this is not the case, in particular not in the quantum case. Do our protocols break in the presence of errors?

The answer is no, because we can perform error correction. In fact, since we distribute classical bitstrings, we may view the quantum protocol as a lossy classical channel and simply do classical error correction afterwards. There are many performant classical error correction codes.

The general idea is that Alice sends a message $x_A$ to Bob through a lossy channel, who receives it as $x_B = x_A + s$, where $s$ is a string of errors. They then exchange some additional information over the channel that allows Bob to make an estimate $\hat{x}_A$ of $x_A$ based on $x_B$.

Definition. An information reconciliation protocol for $x_A$, $x_B$ lets Bob recover an estimate $\hat{x}_A$ of $x_A$ given $x_B$.

• It is $\varepsilon$-correct if $\operatorname{Pr}[x_A \neq \hat{x}_A] \leq \varepsilon$.
• It leaks $k$ bits if the total length of the messages exchanged over the channel is $k$.

In the context of key distribution it is important to limit the number of bits a protocol leaks. This is because any leaked bits reduce the min-entropy of the key. Concretely, we have

$$H_{\text{min}}(X \mid EC) \geq H_{\text{min}}(X \mid E) - |C|,$$

so if we leak $k$ bits, we can still be sure to have lost at most $k$ bits of min-entropy.

An important class of information reconciliation protocols are built on linear codes.

Definition. An $(n, k)$ $q$-ary linear code is a $k$ dimensional subspace of $\mathbb{F}_q^n$.

A linear code $C$ is also induced by a parity-check matrix $H \in \mathbb{F}_q^{m \times n}$ by letting $C = \operatorname{ker} H$. The syndrome of a message $v \in \mathbb{F}_q^n$ is then given by $Hv$.

Protocol 4 – Information Reconciliation through Linear Codes.

Let $H$ be a parity-check matrix. Assume Alice has sent a string $x_A \in \{0, 1\}^n \cong \mathbb{F}_2^n$ that Bob received as $x_B = x_A + s$.

1. Alice sends $c_A = Hx_A$ over the public channel.
2. Bob computes $c_B = Hx_B$ and the syndrome $c_s = Hs = c_A + c_B$ of $s$.
3. Based on the syndrome $c_s$ and the parity-check matrix $H$, Bob determines an estimate $\hat{s}$ of $s$.
4. Bob computes $\hat{x}_A = x_B + \hat{s}$.

If $H \in \mathbb{F}_2^{m \times n}$ induces an $(n, k)$ binary linear code, then Protocol 4 leaks $m$ bits, where $m$ can be chosen as low as $n - k$. Of course, the larger our code and hence the smaller the syndrome, the harder the error-estimation becomes.

The correctness completely depends on the chosen code.

Example.

Consider the $(3, 2)$ binary linear code given by the parity-check matrix

$$H = \begin{pmatrix} 1 & 1 & 0 \\ 0 & 1 & 1 \end{pmatrix},$$

where Bob’s error-estimation is based on the following table.

Syndrome	Error Estimate
00	000
01	001
10	100
11	010

Then Bob can correct any error of at most one bit-flip. Consequently, the code leaks $2$ bits and is $\varepsilon$-correct for $$\varepsilon = \Pr[\text{\# errors} \leq 1] = (1-p)^3 + 3 p(1-p)^2,$$ where $p$ is the probability of a single bit-flip occurring (assuming uncorrelated errors).

There is a theoretical minimum to the number of bits leaked for optimal information reconciliation. Suppose $x_A$ and $x_B$ are sampled bitwise from some joint probability distribution $P_{X_AX_B}$. Then the theoretical minimum number of bits that have to be leaked is

$$n H(X_A \mid X_B).$$

The efficiency of information reconciliation protocols is usually given in terms of a constant $\xi > 1$ which says that the protocol leaks approximately

$$\xi \cdot nH(X_A \mid X_B)$$

bits.

Examples of codes that are widely in use are LDPC codes, for which $\xi$ is between $\approx 1.03$ and $\approx 1.1$.