## 3 Proof of security of BB84 against collective attacks
### Calculating and bounding the trace norm for one bit: the Biham basis.
Moreover, the final key bit \(k\) can be written as \((c+i_{\xi})\cdot v_{r+1}\) and using (36), we get  
\[\widetilde{\rho}_{0}-\widetilde{\rho}_{1} =\frac{1}{2^{n-r-1}}\sum_{c\in C}(-1)^{(c+i_{\xi})\cdot v_{r+1}}| \psi_{c+i_{\xi}}^{\mathbf{b}^{\prime}}\rangle\langle\psi_{c+i_{\xi}}^{ \mathbf{b}^{\prime}}|\] \[=\frac{1}{2^{n-r-1}}\sum_{c\in C}(-1)^{(c+i_{\xi})\cdot v_{r+1}} \sum_{m\in V_{r}^{c}}(-1)^{(c+i_{\xi})\cdot m}|\eta_{m}\rangle\sum_{m^{\prime} \in V_{r}^{c}}(-1)^{(c+i_{\xi})\cdot m^{\prime}}\langle\eta_{m^{\prime}}|\]  
which can be written as  
\[\widetilde{\rho}_{0}-\widetilde{\rho}_{1}=\frac{1}{2^{n-r-1}}\sum_{m,m^{ \prime}\in V_{r}}(-1)^{(m+m^{\prime}+v_{r+1})\cdot i_{\xi}}\left(\sum_{c\in C }(-1)^{(m+m^{\prime}+v_{r+1})\cdot c}\right)|\eta_{m}\rangle\langle\eta_{m^{ \prime}}|. \tag{37}\]  
**Lemma 4**. : _For every Linear Code \(C\),_  
\[\sum_{c\in C}(-1)^{c\cdot w}=\left\{ \begin{array}{cc}|C|&w\in C^{\perp}\\ 0&else,\end{array} \right.\]Proof. : If \(w\in C^{\perp}\) then \(c\cdot w=0\) for every \(c\in C\) by the definition of \(C^{\perp}\). Otherwise, let \(\{\beta_{1}\ldots\beta_{k}\}\) be a basis of \(C\) over \(\mathbf{F}_{2}\). Every codeword \(c\in C\) can be written in a unique way as a linear combination \(c=\alpha_{1}\beta_{1}+\ldots+\alpha_{k}\beta_{k}\) with \((\alpha_{1},\ldots,\alpha_{k})\in\mathbf{F}_{2}^{k}\). Since \(w\
otin C^{\perp}\) there is \(i\) such that \(\beta_{i}\cdot w\
eq 0\). Assume _wlg_ that \(\beta_{1}\cdot w=1\); then  
\[\sum_{c\in C}(-1)^{c\cdot w} =\sum_{(\alpha_{1},\ldots,\alpha_{k})\in\mathbf{F}_{2}^{k}}(-1)^{ (\alpha_{1}\beta_{1}+\ldots+\alpha_{k}\beta_{k})\cdot w}\] \[=[(-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\]  
By Lemma 4, the parenthesized factor in the right-hand side of (37) is zero unless \(m+m^{\prime}+v_{r+1}\in C^{\perp}=V_{r}\), however, \(m,m^{\prime},v_{r+1}\in V_{r}^{c}\), and so is their sum. Thus, when the parenthesized factor is not zero, \(m+m^{\prime}+v_{r+1}\) must equal 0, since \(V_{r}\cap V_{r}^{c}=\{0\}\). The resulting sum must equal \(|C|=2^{n-r}\). The equality \(m+m^{\prime}+v_{r+1}=0\) rewrites as \(m^{\prime}=m+v_{r+1}\) and (37) reduces to  
\[\widetilde{\rho}_{0}-\widetilde{\rho}_{1} =2\sum_{m\in V_{r}^{c}}(-1)^{(m+(m+v_{r+1})+v_{r+1})\cdot i_{ \xi}}|\eta_{m}\rangle\langle\eta_{m+v_{r+1}}|\] \[=2\sum_{m\in V_{r}^{c}}|\eta_{m}\rangle\langle\eta_{m+v_{r+1}}|.\]  
Therefore we conclude that  
\[\frac{1}{2}\operatorname{tr}|\widetilde{\rho}_{0}-\widetilde{\rho}_{1}|= \operatorname{tr}\left|\sum_{m\in V_{r}^{c}}|\eta_{m}\rangle\langle\eta_{m+v_ {r+1}}|\right|. \tag{38}\]  
By Lemma 3, \(\langle\eta_{m}|\eta_{n}\rangle=0\) if \(m\
eq n\) with \(m,n\in V_{r}^{c}\). If we let \(\langle\eta_{m}|\eta_{m}\rangle=d_{\eta_{m}}^{2}\) we get, \(\sum_{m\in V_{r}^{c}}d_{\eta_{m}}^{2}=1\) by (36). Let us rewrite the \(|\eta_{m}\rangle\) for \(m\in V_{r}^{c}\) as \(|\eta_{m}\rangle=d_{\eta_{m}}|\hat{\eta}_{m}\rangle\) with \(\langle\hat{\eta}_{m}|\hat{\eta}_{n}\rangle=\delta_{m,n}\) for \(m,n\in V_{r}^{c}\). It is known that for any operator \(A\), \(|A|=\sqrt{A^{\dagger}A}\) and thus  
Footnote ∥: Here \(A\) is Hermitian, therefore \(|A|=\sqrt{AA^{\dagger}}\). \[\operatorname{tr}\left|\sum_{m\in V_{r}^{c}}|\eta_{m}\rangle \langle\eta_{m+v_{r+1}}\right| =\operatorname{tr}\sqrt{\sum_{m\in V_{r}^{c}}|\eta_{m}\rangle \langle\eta_{m+v_{r+1}}|\sum_{m^{\prime}\in V_{r}^{c}}|\eta_{m^{\prime}+v_{r+1 }}\rangle\langle\eta_{m^{\prime}}|}\] \[=\operatorname{tr}\sqrt{\sum_{m,m^{\prime}\in V_{r}^{c}}|\eta_{m }\rangle\langle\eta_{m+v_{r+1}}|\eta_{m^{\prime}+v_{r+1}}\rangle\langle\eta_{m^ {\prime}}|}\] \[=\operatorname{tr}\sqrt{\sum_{m\in V_{r}^{c}}d_{\eta_{m+v_{r+1}}} d_{\eta_{m}}^{2}|\hat{\eta}_{m}\rangle\langle\hat{\eta}_{m}|}\] \[=\sum_{m\in V_{r}^{c}}d_{\eta_{m+v_{r+1}}}d_{\eta_{m}}\]  
where the last equation follows directly from the spectral decomposition that figures under the square root.