# Notes on Security Analysis

This page summarises the proof and derivation of the various security analysis results presented in "Tight finite-key analysis for quantum cryptography" [1].

## Eq. (6) - Quantum Leftover Hash Lemma
This section summarises the derivation of the Quantum Leftover Hash Lemma, Eq. (6) in Ref. [1]. The Quantum Leftover Hash Lemma is derived by Tomamichel et al. in Ref. [2], and Eq. (6) in Ref. [1] is the direct application of Theorem 6 from Ref. [2].

### Brief introduction
Alice computes a $\Delta$-secret key $\mathcal{S}$ of length $l$ from $\mathbf{X}$ by applying a universal ₂ hash function. $E'$ refers to Eve's information before classical post-processing, and $E'$ is before privacy amplification.

Ref. [2] provides a security analysis of such a QKD protocol by analysing the quantity $D_u(\mathcal{S}|FE')$, which quantities the distance from uniform of $\mathcal{S}$ conditioned on $FE'$ and where $\mathcal{S} = f(\mathbf{X})$ is obtained after universal₂ hash function.

### Notations and properties
The distance from uniform of A conditioned B is defined as
\begin{equation} \tag{1}
D_u(A|B)_{\rho} := \min_{\sigma_B}{ \frac{1}{2} || \rho_{AB} - \omega_A \otimes \sigma_B ||_1}.
\end{equation}

The collision entropy A conditioned on B of a state $\rho_{AB}$ given $\sigma_B$ is $-\log \Gamma_C(\rho_{AB}|\sigma_b)$, where
\begin{equation} \tag{2}
\Gamma_C(\rho_{AB}|\sigma_B) := \operatorname{tr} \left( \rho_{AB} \left(\mathbb{1}_A \otimes \sigma_B^{-1/2} \right) \right)^2.
\end{equation}

The purified distance $P$ is defined in terms of the generalised fidelity, $\bar{F}$.
\begin{equation} \tag{3}
P(\rho, \tau) := \sqrt{1 - \bar{F}(\rho, \tau)^2},
\end{equation}
where
\begin{equation} \tag{4}
\bar{F}(\rho, \tau) := \operatorname{tr}|\sqrt{\rho}\sqrt{\tau}| + \sqrt{(1 - \operatorname{tr} \rho)(1 - \operatorname{tr} \tau)} .
\end{equation}

Let $\mathcal{E}$ be a trace nonincreasing completely positive map, then the purified distance cannot be increasing [3].
\begin{equation} \tag{5}
P(\rho, \tau) \geq P(\mathcal{E}(\rho), \mathcal{E}(\tau))
\end{equation}

The $\epsilon$-ball of states close to $\rho \in \mathcal{S}_{\leq}(\mathcal{H})$ is defined as [2]
\begin{equation} \tag{6}
\mathcal{B}^{\epsilon}(\rho) := \{\tilde{\rho} \in \mathcal{S}_{\leq}(\mathcal{H}): P(\rho, \tilde{\rho}) \leq{\epsilon}\},
\end{equation}
where $\mathcal{S}_{\leq}(\mathcal{H})$ is the set of sub-normalised sates.

And privacy amplification can only decrease the purified distance [2].
\begin{equation} \tag{7}
||\rho_{FSE'} - \tilde{\rho}_{FSE'}||_1 \leq P(\rho_{FSE'}, \tilde{\rho}_{FSE'}) \leq P(\rho_{XE'}, \tilde{\rho}_{XE'}) \leq \epsilon
\end{equation}

### Lemmas and Theorems from Ref. [2]

Lemma 3, Ref. [2]: Let $\rho_{AB} \in \mathcal{S}_{\leq}(\mathcal{H_{AB}})$ be a classical-quantum state. Then, there exists a state $\sigma_B \in \mathcal{S}_=(\mathcal{H}_B)$
\begin{equation} \tag{8}
\Gamma_C(\rho_{AB}|\sigma_B) \leq 2^{-H_{min}(A|B)_{\rho}}
\end{equation}

Lemma 4, Ref. [2]: Let $\rho_{AB} \in \mathcal{S}_{\leq}(\mathcal{H_{AB}})$ and $\tau_{B} \in \mathcal{S}_{\leq}(\mathcal{H_{B}})$ with $\operatorname{supp} \{\tau_B\} \supseteq \operatorname{supp} \{\rho_B\}$, then
\begin{equation} \tag{9}
D_u(A|B)_\rho \leq \frac{1}{2} \sqrt{2^l \Gamma_C(\rho_{AB}|\tau_B) - \operatorname{tr}(\rho_B \tau_B^{-1/2} \rho_B \tau_B^{-1/2})}.
\end{equation}

Lemma 5, Ref. [2]

\begin{equation} \tag{10}
\Gamma_C(\rho_{FSE'}|\rho_F \otimes \tau_{E'}) \leq \Gamma_C(\rho_{XE'}|\tau_{E'}) + 2^{-l}\operatorname{tr}(\rho_{E'} \tau_{E'}^{-1/2} \rho_{E'} \tau_{E'}^{-1/2})
\end{equation}

Theorem 6, Ref. [2]:
For the case of $\epsilon = 0$, Lemma 4 and Lemma 5. can be applied to obtain a bound to $D_u(\mathcal{S} |FE')_\rho$.
\begin{equation} \tag{11}
\begin{aligned}
2D_u(\mathcal{S}|FE')_\rho & \leq \sqrt{2^l \Gamma_C(\rho_{FSE'}|\rho_F \otimes \tau_{E'}) - \operatorname{tr}(\rho_{E'} \tau_{E'}^{-1/2} \rho_{E'} \tau_{E'}^{-1/2})} \\
& \leq \sqrt{2^l \Gamma_C(\rho_{XE'}|\tau_{E'})}.
\end{aligned}
\end{equation}

Then, with a proper choice of of $\tau_{E'}$, we have
\begin{equation} \tag{12}
2D_u(\mathcal{S}|FE') \leq \sqrt{2^{l-H^{\epsilon}_{min}(\mathbf{X}|E')_{\rho}}}.
\end{equation}

Next, consider the case for $\epsilon \geq 0$ and let $\tilde{\sigma}_{FE'}$ be the state that minimises the distance from uniform $D_u(\mathcal{S}|FE')_{\tilde{\rho}}$. Then,
\begin{equation} \tag{13}
\begin{aligned}
2D_u(\mathcal{S}|FE') & \leq ||\rho_{FSE'} - \omega_S \otimes \tilde{\sigma}_{FE'}||_1 \\
& \leq ||\rho_{FSE'} - \tilde{\rho}_{FSE'}||_1 + ||\tilde{\rho}_{FSE'} - \omega_S \otimes \tilde{\sigma}_{FE'}||_1 \\
& \leq 2 \epsilon + 2D_u(\mathcal{S} | FE')_{\tilde{\rho}}.
\end{aligned}
\end{equation}

And applying Eq. (12) to $\tilde{\rho}_{FSE'}$, we get
\begin{equation} \tag{14}
\begin{aligned}
D_u(\mathcal{S}|FE')_{\rho} & \leq \epsilon + \frac{1}{2} \sqrt{2^{l - H_{min}(\mathbf{X}|E')_{\tilde{\rho}}}}\\
& = \epsilon + \frac{1}{2} \sqrt{2^{l-H^{\epsilon}_{min}(\mathbf{X}|E')_{\rho}}}.
\end{aligned}
\end{equation}

### $\Delta$-secret key
A secret key is called $\Delta$-secret [1] if
\begin{equation} \tag{15}
\min_{\sigma_E}{ \frac{1}{2} || \rho_{SE} - \omega_S \otimes \sigma_E ||_1 \leq \Delta}.
\end{equation}

In terms of the quantity $D_u$, $\Delta$ can also be interpreted as the upper bound to the distance of the secret key conditioned on $E$.
\begin{equation} \tag{16}
D_u(\mathcal{S}|FE') = D_u(\mathcal{S}|E) \leq \Delta
\end{equation}

Therefore, the results of Theorem 6 is directly applicable to the protocol which gives us Eq. (6) from Ref. [1].
\begin{equation} \tag{17}
\Delta = \epsilon + \frac{1}{2} \sqrt{2^{l-H^{\epsilon}_{min}(\mathbf{X}|E')}}
\end{equation}

## References
[1] Marco Tomamichel, Charles Ci Wen Lim, Nicolas Gisin, and Renato Renner. Tight finite-key analysis for quantum cryptography. Nat Commun, 3(1):634, January 2012.

[2] Marco Tomamichel, Christian Schaffner, Adam Smith, and Renato Renner. Leftover Hashing Against Quantum Side Information. IEEE Trans. Inform. Theory, 57(8):5524–5535, August 2011.

[3] Marco Tomamichel, Roger Colbeck, and Renato Renner. Duality Between Smooth Min- and Max-Entropies. IEEE Trans. Inform. Theory, 56(9):4674–4681, September 2010.