## 3 Proof of security of BB84 against collective attacks
### Calculating and bounding the trace norm for one bit: the Biham basis.
Using the fact that \(V_{r}^{c}=V_{r+1}^{c}\cup\left(v_{r+1}+V_{r+1}^{c}\right)\) and that this union is disjoint, we deduce  
\[\frac{1}{2}\operatorname{tr}|\widetilde{\rho}_{0}-\widetilde{\rho}_{1}|=2\sum _{m\in V_{r+1}^{c}}d_{\eta_{m}}d_{\eta_{m+v_{r+1}}}. \tag{39}\]  
In order to bound this result we use the following Lemma,  
Let \(\mathbf{c}=\mathbf{i}+\mathbf{i}^{B}\), the exclusive-or of the \(2n\)-bit string sent by [PERSON] and of the one measured by [PERSON]. Each index \(1\leq l\leq 2n\) such that \(c_{l}=1\) corresponds to a mismatch in [PERSON]'s bit value with respect to the value sent by [PERSON]. If \(s_{l}=1\) the bit is an \"information bit\" and if \(s_{l}=0\) it is a \"test bit\". The corresponding \"error on the information bits\" is thus \(\mathbf{c_{s}}\) and the error on the test bits is \(\mathbf{c_{s}}\). The random variable corresponding to \(\mathbf{c_{s}}\) and \(\mathbf{c_{s}}\) are denoted \(\mathbf{C}_{I}\) and \(\mathbf{C}_{T}\) respectively; they depend on \(\mathbf{b}\) and \(\mathbf{s}\). In order to lighten the notation, we will write \(P[\mathbf{C}_{I}=\mathbf{c_{s}}\mid\mathbf{b},\mathbf{s}]\) to mean the probability that the error string on the bits such that \(s_{i}=1\) be \(\mathbf{c_{s}}\) conditional to [PERSON] having used the basis string \(\mathbf{b}\) and the selection string \(\mathbf{s}\). As a consequence, \(P[\mathbf{C}_{I}=\mathbf{c_{s}}\mid\mathbf{b}+\mathbf{s},\mathbf{s}]\) denotes the probability that the error string on information bits be \(\mathbf{c_{s}}\) if the selection string is \(\mathbf{s}\) and the basis string is \(\mathbf{b}+\mathbf{s}\), i.e. is just the same as \(\mathbf{b}\) but all the bases corresponding to the positions selected by \(\mathbf{s}\) (of the information bits) are replaced by their conjugates. Equations (31) and (41) can now be rewritten more cleanly as  
\[=[(-1)^{0}+(-1)^{1}]\sum_{(\alpha_{2},\ldots,\alpha_{k})\in \mathbf{F}_{2}^{k-1}}(-1)^{(\alpha_{2}\beta_{2}+\ldots+\alpha_{k}\beta_{k}) \cdot w}=0.\qed\]0 \[=[(-1)^{0}+(-1)^{1}]\sum_{(\alpha_{2},\ldots,\alpha_{k})\in \mathbf{F}_{2}^{k-1}}(-1)^{(\alpha_{2}\beta_{2}+\ldots+\alpha_{k}\beta_{k}) \cdot w}=0.\qed\]1  
where in the right hand side of (42) we use the fact that qubits are attacked independently, the error on information bits thus being independent of the error \(\mathbf{c_{s}}\) on test bits. Equation (43) was derived for a (virtual) flat attack associated to \(\mathbf{b}\). That flat attack had the same \(\widehat{\rho}_{0}\) and \(\widehat{\rho}_{1}\) as the original attack, and could only give a lower error rate in the conjuguate bases. As a consequence equation (43) also holds for the original attack \(U\) and from now on, the probability of error on the right-hand side will be understood to be the one induced by the original attack \(U=U_{1}\otimes\ldots\otimes U_{2n}\). For any such fixed attack \(U\), [PERSON]'s information depends only on the syndrome \(\boldsymbol{\xi}\), the characteristic string \(\mathbf{s}\) for the information bits, and the corresponding bases of the information string \(\mathbf{b_{s}}\) (yet, as said, we use the entire \(2n\)-bit string \(\mathbf{b}\)). **Corollary 6**. : _For a \(1\)-bit key \(k\),_  
\[=[(-1)^{0}+(-1)^{1}]\sum_{(\alpha_{2},\ldots,\alpha_{k})\in \mathbf{F}_{2}^{k-1}}(-1)^{(\alpha_{2}\beta_{2}+\ldots+\alpha_{k}\beta_{k}) \cdot w}=0.\qed\]2  
_where \(\mathbf{K}\) is the random variable giving as output key \(k\) and \(\mathbf{E}\) is the random variable corresponding to the outputs of [PERSON]'s (optimal) measurement._  
Proof. : This follows from the fact that \(SD(\widehat{\rho}_{0},\widehat{\rho}_{1})\) is [PERSON]'s accessible information on \(k\) if she holds \(\widehat{\rho}_{k}\) given by (32). These states correspond to [PERSON]'s state when [PERSON] encodes the key-bit \(k\) assuming [PERSON] learns \(\boldsymbol{\xi}\), \(\mathbf{b}\) and \(\mathbf{s}\).