## 1 Introduction
### A Formal Description of the BB84 Protocol  
Let us describe the BB84 protocol we shall use in this paper.  
1. [PERSON] and [PERSON] agree on a large number \(n\), an error threshold \(p_{a}\) and on a linear error-correctioncode \(C\) with parity check matrix \(P_{C}\) of order \(r\times n\). They agree as well on a linear key-generation function (privacy amplification) represented by a matrix \(P_{K}\) of order \(m\times n\). Those matrices can be publicly known beforehand or they can be determined during the protocol and sent over the classical channel. The \((r+m)\times n\) matrix whose rows are those of \(P_{C}\) and \(P_{K}\) put together is required to be of rank \(r+m\).
2. [PERSON] randomly chooses \(2n\)-bit strings \(\mathbf{i},\mathbf{b}\in\mathbf{F}_{2}^{2n}\), where \(\mathbf{F}_{2}\) denotes the two element field, with elements \(\{0,1\}\), i.e. the field of integers modulo 2. [PERSON] encodes the state \(|\mathbf{i}^{\mathbf{b}}\rangle=|i_{1}^{b_{1}}\rangle\ldots|i_{2n}^{b_{2n}}\rangle\) and sends it to [PERSON] over the quantum channel, one qubit at a time. Each time [PERSON] receives a qubit he informs [PERSON], yet he doesn't measure itSS Footnote §: Here we assume that [PERSON] delays measuring each qubit till after learning its basis. In the more realistic case in which [PERSON] cannot wait with his measurement, or in case some qubits are lost, [PERSON] needs to send more qubits to make sure that \(2n\) qubits are obtained (in [PERSON]’s bases) as required.
3. [PERSON] publicly sends [PERSON] the string \(\mathbf{b}\). [PERSON] applies \(H^{\mathbf{b}}=H^{b_{1}}\otimes\ldots\otimes H^{b_{2n}}\) to his state, so that if [PERSON] had the state \(|\mathbf{i}^{\mathbf{b}}\rangle\), once he performs \(H^{\mathbf{b}}\) he possesses the state \(|\mathbf{i}\rangle=|i_{1}\ldots i_{2n}\rangle\). [PERSON] then measures these qubits in the computation basis. We denote by \(\mathbf{i}^{B}\) the string measured by [PERSON]. If there is no noise and no eavesdropping, he gets exactly the bitstring \(\mathbf{i}\) sent by [PERSON].
4. [PERSON] randomly chooses \(n\)-bits that will be used to detect eavesdropping. This is done by choosing a \(2n\)-bit string that has exactly \(n\) ones. Formally, [PERSON] chooses \(\mathbf{s}\in\mathbf{F}_{2}^{2n}\) such that \(|\mathbf{s}|=n\). [PERSON] publicly sends [PERSON] \(\mathbf{s}\). The bits indexed by \(j\in[1\ \ldots\ 2n]\) such that \(s_{j}=0\) are used for testing, while the rest are used for generating the final key (via error correction and privacy amplification). We denote the appropriate substrings of \(\mathbf{i},\mathbf{b}\) that are relevant for the testing by \(\mathbf{i}_{\bar{\mathbf{s}}}\) and \(\mathbf{b}_{\bar{\mathbf{s}}}\), while the substrings relevant for creating the key are denoted \(\mathbf{i}_{\mathbf{s}}\) and \(\mathbf{b}_{\mathbf{s}}\).
5. For each \(j\in[1\ \ldots\ 2n]\) such that \(s_{j}=0\), [PERSON] and [PERSON] publish the value of the \(j\)th-bit. [PERSON] and [PERSON] compare those bit values, and if more than \(np_{a}\) bits mismatch, they abort the protocol. The pre-fixed protocol parameter \(p_{a}\) is actually the ratio of allowed bit-flips on the testing bits.
6. [PERSON] and [PERSON] keep the values of the remaining \(n\) bits secret. [PERSON]'s string is denoted \(\mathbf{x}=\mathbf{i}_{\mathbf{s}}\) and named the _information string_. The corresponding bitstring on [PERSON]'s side is denoted \(\mathbf{x}^{B}\).
7. [PERSON] sends [PERSON] the \(r\)-bit error-correction string \(\boldsymbol{\xi}=\mathbf{x}P_{C}^{\mathrm{T}}\) (where \(P_{C}^{\mathrm{T}}\) is the transpose of the parity check matrix). [PERSON] uses \(\boldsymbol{\xi}\) to correct his string \(\mathbf{x}^{B}\). The string \(\boldsymbol{\xi}\) is called the _syndrome_ of the string \(\mathbf{x}\) (with regard to \(P_{C}\)).
8. [PERSON] and [PERSON] compute the \(m\)-bit final key \(\mathbf{k}=\mathbf{x}P_{K}^{\mathrm{T}}\).