# Secure bound analysis of quantum key distribution with non-uniform random
seed of privacy amplification

Bingze Yan Yucheng Qiao Qiong Li Haokun Mao

## Abstract

Precise quantum key distribution (QKD) secure bound analysis is essential for
practical QKD systems. The effect of uniformity of random number seed for
privacy amplification is not considered in existing secure bound analysis. In
this paper, we propose and prove the quantum leftover hash lemma with non-
uniform random number seeds based on the min-entropy, and we give a precise
QKD secure bound analysis with non-uniform random number seeds on this basis.
We take the two-decoy BB84 protocol as an example to simulate the effect of
random number seed uniformity on the secure bound of a QKD system. The
experimental results indicate that when the average min-entropy of the random
number generator is below 0.95, the secure bound of a QKD system will be
seriously affected.

## Introduction

Quantum key distribution (QKD) technology provides secure communication
service with information-theoretic security [1]. As the development of QKD
technology, QKD has moved towards the practical stage. The pracical security
of QKD systems has gradually attracted researcher’s attention, and many ideal
assumptions in QKD security analysis are found unsatisfied in practical QKD
systems[2, 3, 4]. One of these assumptions is that the random number seeds
used for privacy amplification in a QKD system must be strictly uniformly
distributed, and this is very difficult to guarantee in an actual system[5].
This gap may seriously affect the security of privacy amplification, which in
turn seriously affects the secure bound of QKD. However, the exact extent of
this impact has not been analyzed.

Privacy amplification is a necessary part of a QKD system. It is the art of
distilling a information-theoretic secure key from a partially secure string
with a hash function by public discussion between two parties [6]. In order to
ensure the security of keys, the hash function must be randomly selected from
a universal hash family with random number seeds in the existing PA secure
proof [5]. Hayashi et al. quantifies the uniformity of random number seeds
with min-entropy, and analyzes the effect of min-entropy of random number
seeds on privacy amplification security under classical information theory[7].
However, there is still a lack of security analysis under quantum information
theory and analysis of the impact of random seed min-entropy on secure bound
of QKD.

Aiming at this problem, this paper proposes and proves the quantum leftover
hash lemma with non-uniform random number seeds, and analyzes a precise QKD
secure bound with non-uniform random number seeds.

In order to further analyze the influence of PA random number seeds on the
secure key rate of QKD systems, we investigate the average min-entropy of
random number generators in existing QKD systems. We find that most systems do
not give the average minimum entropy of their random seeds. Therefore, we
investigated and tested the min-entropy of some commonly used random number
generators in QKD systems. We found that these random number generators could
not achieve the perfect minimum entropy, so they would have a obvious impact
on the secure key rate.

## Results

### Quantum leftover hash lemma with non-uniform random seeds

We discussed the security of QKD under quantum information theory and
universal composable security. The security of a QKD protocol should be
considered on the secrecy and correctness.

Suppose the information possessed by the eavesdropper is $E$, then a key
relative to the eavesdropping information $E$ can be called
${\epsilon}_{sec}-$ secrecy, when the statistical distance between the key and
a key that is uniformly distributed and independent of $E$ is less than
${\epsilon}_{sec}$:

$\frac{1}{2}{\left\|{{\rho_{{\rm{SE}}}}-{S_{U}}\otimes{\rho_{E}}}\right\|_{1}}\leq{\epsilon_{sec}}.$
(1)

In universal composable security theory, key correctness represents the
probability that $S_{A}$ and $S_{B}$ are different:

${Pr}[S_{A}\neq S_{B}]\leq\epsilon_{cor}$ (2)

Considering both secrecy and correctness, when the key is
$\epsilon_{sec}$-secrecy and $\epsilon_{cor}$-correctness, the key is
$\overline{\epsilon}-$secure:

$\overline{\epsilon}=\epsilon_{sec}+\epsilon_{cor}.$ (3)

We proposed and proved the quantum leftover hash lemma with non-uniform random
seeds under quantum information theory and universal composable security:

Theorem 1 (Quantum Leftover Hash Lemma With Non-Uniform Random Seeds) Let
$F_{R}$ be a universal hashing family of functions from $X$ to $S$, $f_{r}$ is
a hash function randomly selected from $F_{R}$ with random seeds
$R\in\\{0,1\\}^{\alpha}$, $|F_{R}|=2^{\alpha}$ and $P_{F_{R}}$ satisfies
$H_{min}(P_{F_{R}})\geq\beta$, and $s=f_{r}(x)$. Let
${\rho_{XE}}=\sum\limits_{x}{\left|x\right\rangle{{\left\langle
x\right|}_{X}}\otimes\rho_{E}^{[x]}}$ and cq-states
${\rho_{{F_{R}}{\rm{S}}E}}=\sum\limits_{{f_{r}}}{\sum\limits_{\rm{s}}{{P_{{F_{R}}}}\left|{{f_{r}}}\right\rangle\langle{f_{r}}{|_{{F_{R}}}}\otimes}}\left|s\right\rangle\langle
s{|_{S}}\otimes\rho_{E}^{\left[{{f_{r}},s}\right]}$. Then for any
$\epsilon\geq 0$,

$\Delta=\sum\limits_{{f_{r}}}{{P_{{F_{R}}}}({f_{r}}){D_{u}}{{(S|E)}_{{\rho^{[{f_{r}}]}}}}}\leq\frac{1}{2}\times{2^{\alpha-\beta}}\times{2^{-\frac{1}{2}(H_{\min}^{\varepsilon}({\rho_{{\rm{XE}}}}\left|E\right.)-l)}}+\varepsilon,$
(4)

where $E$ is the side information of eavesdropper.

More importantly, we further analyzed the effect of random number seed
uniformity on the secure bound of a QKD protocol, and the secure bound of a
QKD system with non-uniform random number seed is obtained as follow,

$l\leq
H_{\min}^{\varepsilon}({\rho_{SE^{\prime}}}\left|{E^{\prime}}\right.)-lea{k_{EC}}-2{\log_{2}}\frac{1}{{2(\varepsilon_{sec}-\varepsilon)}}-\log_{2}{\frac{2}{\epsilon_{cor}}}-(\alpha-\beta).$
(5)

For further analyzing the influence of PA random number seeds on the secure
key rate of QKD systems, we investigated and tested the min-entropy of some
commonly used random number generators in QKD systems as shown in Table 1.

Table 1: The average min-entropy of common random number generator Random Number Generator | Type | Refer/Test | Test Scale | Average Min-entropy
---|---|---|---|---
IDQ Quantis-PCIe-40M | QRNG | Test | 100Mb | 0.990
MATLAB unifrnd | PRNG | Test | 100Mb | 0.988
Random.org | TRNG | Refer | – | 0.931
Intel DRNG | TRNG | Refer | – | 0.930

We refer to a typical decoy BB84 protocol to experiment the effect of random
number min-entropy on the QKD secure key rate. The experiment result is
indicated as Fig. 1 and Fig. 2.

Figure 1: The relation between random uniformity and SKR under different
distances Figure 2: The relation between random uniformity and SKR under
different distances

The above experimental results indicate that, (1) the average min-entropy of
the random number generator is below 0.95, the secure bound of a QKD system
will be seriously affected; (2) Most commonly used random number generators in
a QKD system will influence the secret key rate of QKD seriously.

## Methods

The proof of quantum leftover hash lemma with non-uniform random seeds is
given as below.

Theorem 1 (Quantum Leftover Hash Lemma With Non-Uniform Random Seeds) Let
$F_{R}$ be a universal hashing family of functions from $X$ to $S$, $f_{r}$ is
a hash function randomly selected from $F_{R}$ with random seeds
$R\in\\{0,1\\}^{\alpha}$, $|F_{R}|=2^{\alpha}$ and $P_{F_{R}}$ satisfies
$H_{min}(P_{F_{R}})\geq\beta$, and $s=f_{r}(x)$. Let
${\rho_{XE}}=\sum\limits_{x}{\left|x\right\rangle{{\left\langle
x\right|}_{X}}\otimes\rho_{E}^{[x]}}$ and cq-states
${\rho_{{F_{R}}{\rm{S}}E}}=\sum\limits_{{f_{r}}}{\sum\limits_{\rm{s}}{{P_{{F_{R}}}}\left|{{f_{r}}}\right\rangle\langle{f_{r}}{|_{{F_{R}}}}\otimes}}\left|s\right\rangle\langle
s{|_{S}}\otimes\rho_{E}^{\left[{{f_{r}},s}\right]}$. Then for any
$\epsilon\geq 0$,

$\Delta=\sum\limits_{{f_{r}}}{{P_{{F_{R}}}}({f_{r}}){D_{u}}{{(S|E)}_{{\rho^{[{f_{r}}]}}}}}\leq\frac{1}{2}\times{2^{\alpha-\beta}}\times{2^{-\frac{1}{2}(H_{\min}^{\varepsilon}({\rho_{{\rm{XE}}}}\left|E\right.)-l)}}+\varepsilon,$
(6)

where $E$ is the side information of eavesdropper.

###### Proof.

For,

$\Delta=\sum\limits_{{f_{r}}}{{P_{{F_{R}}}}({f_{r}}){D_{u}}{{(S|E)}_{{\rho^{[{f_{r}}]}}}}},$
(7)

As $P_{F_{R}}$ satisfies $H_{min}(P_{F_{R}})\geq\beta$, then for any
${{P_{{F_{R}}}}({f_{r}})}$, it satisfies ${{P_{{F_{R}}}}({f_{r}})}\leq
2^{-\beta}$, then,

$\Delta=\sum\limits_{{f_{r}}}{{P_{{F_{R}}}}({f_{r}}){D_{u}}{{(S|E)}_{{\rho^{[{f_{r}}]}}}}}\leq\sum\limits_{{f_{r}}}{{2^{-\beta}}{D_{u}}{{(S|E)}_{{\rho^{[{f_{r}}]}}}}}={2^{\alpha-\beta}}\sum\limits_{{f_{\rm{r}}}}{{2^{-\alpha}}{D_{u}}{{(S|E)}_{{\rho^{[{f_{r}}]}}}}},$
(8)

Since the set sizes of $F_{R}$ and $F_{U}$ are the same as $2^{\alpha}$, and
the uniform distribution of $F_{U}$ satisfies $P_{F_{u}}(f_{u})=2^{-\alpha}$,
it can be obtained:

$\Delta=\sum\limits_{{f_{r}}}{{P_{{F_{R}}}}({f_{r}}){D_{u}}{{(S|E)}_{{\rho^{[{f_{r}}]}}}}}\leq{2^{\alpha-\beta}}\sum\limits_{{f_{\rm{u}}}}{{P_{{F_{u}}}}({f_{u}}){D_{u}}{{(S|E)}_{{\rho^{[{f_{u}}]}}}}}={2^{\alpha-\beta}}{D_{u}}{(S|{F_{u}}E)_{\rho}}.$
(9)

Further, according to Lemma 1, the upper limit of $\Delta$ can be obtained as:

$\Delta=\sum\limits_{{f_{r}}}{{P_{{F_{R}}}}({f_{r}}){D_{u}}{{(S|E)}_{{\rho^{[{f_{r}}]}}}}}\leq\frac{1}{2}\times{2^{\alpha-\beta}}\times{2^{-\frac{1}{2}(H_{\min}^{\varepsilon}({\rho_{{\rm{XE}}}}\left|E\right.)-l)}}+\varepsilon$
(10)

∎

In the above proof, this paper adopts the method of directly scaling
${{D_{u}}{{(S|F_{u}E)}_{\rho}}}$ to find its upper limit. Another more
intuitive way is to directly scale the maximum collision probability of the
approximate general hash to find the upper limit. The specific process is as
follows.

First, according to the following lemma, the upper limit of
${{D_{u}}{{(S|F_{u}E)}_{\rho}}}$ can be obtained.

######  Lemma 1.

Let ${\rho_{AB}}\in{S_{\leq}}({{\bf{{\rm H}}}_{AB}})$,
${\tau_{B}}\in{S_{\leq}}({{\bf{{\rm H}}}_{B}})$ and
$\sup\\{{\tau_{B}}\\}\supseteq\sup\\{{\rho_{B}}\\}$, then,

${{D_{u}}{{(S|FE)}_{\rho}}}\leq\frac{1}{2}\sqrt{{d_{A}}{\Gamma_{C}}({\rho_{AB}}|{\tau_{B}})-tr({\rho_{B}}\tau_{B}^{-1/2}{\rho_{B}}\tau_{B}^{-1/2})},$
(11)

where $d_{A}$ is the set size of $A$.

According to Lemma 1, the upper limit of ${{D_{u}}{{(S|F_{R}E)}_{\rho}}}$ can
be obtained,

${{D_{u}}{{(S|F_{R}E)}_{\rho}}}\leq\frac{1}{2}\sqrt{{2^{l}}{\Gamma_{C}}({\rho_{FSE}}|{\rho_{F}}\otimes{\tau_{E}})-tr({\rho_{E}}\tau_{E}^{-1/2}{\rho_{E}}\tau_{E}^{-1/2})}.$
(12)

Then, by scaling ${{\Gamma_{C}}({\rho_{FSE}}|{\rho_{F}}\otimes{\tau_{E}})}$ to
find its upper limit, it can get,

$\begin{array}[]{*{20}{l}}{{\Gamma_{C}}({\rho_{{F_{R}}SE}}|{\rho_{F}}\otimes{\tau_{E}})}\\\
{=\sum\limits_{f\in{F_{R}}}{{P_{{F_{R}}}}}\sum\limits_{z}{tr\left({\left|{{f_{r}}}\right\rangle\langle{f_{r}}{|_{{F_{R}}}}\otimes\left|s\right\rangle\langle
s{|_{S}}\otimes\rho_{E}^{\left[{{f_{r}},s}\right]}\tau_{E}^{-1/2}\rho_{E}^{\left[{{f_{r}},s}\right]}\tau_{E}^{-1/2}}\right)}}\\\
{=\mathop{\rm{E}}\limits_{{f_{r}}\in{F_{R}}}\left[{\sum\limits_{z}{tr\left({\rho_{E}^{\left[{{f_{r}},s}\right]}\tau_{E}^{-1/2}\rho_{E}^{\left[{{f_{r}},s}\right]}\tau_{E}^{-1/2}}\right)}}\right]}\\\
{=\sum\limits_{x,x^{\prime}}{\mathop{\rm{E}}\limits_{{f_{r}}\in{F_{R}}}\left[{\sum\limits_{z}{{\delta_{{f_{r}}(x)=z}}{\delta_{{f_{r}}(x^{\prime})=z}}}}\right]}tr\left({\rho_{E}^{\left[x\right]}\tau_{E}^{-1/2}\rho_{E}^{\left[{x^{\prime}}\right]}\tau_{E}^{-1/2}}\right).}\end{array}$
(13)

According to the definition of the $\delta$-almost universal family, when the
random number seed satisfies the uniform distribution, the above expectation
satisfies $\mathop{\rm
E}\limits_{f\in{F_{u}}}\left[{\sum\limits_{z}{{\delta_{f(x)=z}}{\delta_{f(x^{\prime})=z}}}}\right]\leq\delta$.
When the random number seed does not satisfy the uniform distribution, it can
be scaled to get:

$\begin{array}[]{*{20}{l}}{\mathop{\rm{E}}\limits_{{f_{r}}\in{F_{R}}}\left[{\sum\limits_{z}{{\delta_{{f_{r}}(x)=z}}{\delta_{{f_{r}}(x^{\prime})=z}}}}\right]}\\\
{=\sum\limits_{{f_{r}}\in{F_{R}}}{{P_{{F_{R}}}}}\left[{\sum\limits_{z}{{\delta_{{f_{r}}(x)=z}}{\delta_{{f_{r}}(x^{\prime})=z}}}}\right]}\\\
{\leq\sum\limits_{{f_{r}}\in{F_{R}}}{{2^{-\beta}}}\left[{\sum\limits_{z}{{\delta_{{f_{r}}(x)=z}}{\delta_{{f_{r}}(x^{\prime})=z}}}}\right]}\\\
{={2^{\alpha-\beta}}\sum\limits_{{f_{r}}}{{2^{-\alpha}}}\left[{\sum\limits_{z}{{\delta_{{f_{r}}(x)=z}}{\delta_{{f_{r}}(x^{\prime})=z}}}}\right]}\\\
{\leq{2^{\alpha-\beta}}\times\delta}\end{array}$ (14)

According to this result, the upper limit of
${\Gamma_{C}}({\rho_{{F_{R}}SE}}|{\rho_{{F_{R}}}}\otimes{\tau_{E}})$ is,

${\Gamma_{C}}({\rho_{{F_{R}}SE}}|{\rho_{{F_{R}}}}\otimes{\tau_{E}})\leq{\Gamma_{C}}({\rho_{XE}}\left|{{\tau_{E}}}\right.)+{2^{\alpha-\beta}}\times\delta\times{\rm{tr}}\left({{\rho_{E}}\tau_{E}^{-1/2}{\rho_{E}}\tau_{E}^{-1/2}}\right).$
(15)

Let ${\rho_{E}}={\tau_{E}}$, the formula can be further simplified as:

${\Gamma_{C}}({\rho_{{F_{R}}SE}}|{\rho_{{F_{R}}}}\otimes{\tau_{E}})\leq{\Gamma_{C}}({\rho_{XE}}\left|{{\tau_{E}}}\right.)+{2^{\alpha-\beta}}\times\delta\times{\rm{tr}}{\rho_{E}}.$
(16)

Then,

${{D_{u}}{{(S|F_{R}E)}_{\rho}}}\leq\frac{1}{2}\sqrt{{2^{l}}{\Gamma_{C}}({\rho_{XE}}\left|{{\rho_{E}}}\right.)+\left({{2^{\alpha-\beta}}\times\delta\times{2^{l}}-1}\right){\rm{tr}}{\rho_{E}}}.$
(17)

Substitute the smoothed minimum entropy, $\delta=2^{-l}$ and
$\rm{tr}{\rho_{E}}$, we can get,

$\Delta=\sum\limits_{{f_{r}}}{{P_{{F_{R}}}}({f_{r}}){D_{u}}{{(S|E)}_{{\rho^{[{f_{r}}]}}}}}\leq\frac{1}{2}\sqrt{{2^{l-{H_{{{\min}^{\varepsilon}}}}({\rho_{{\rm{XE}}}}\left|E\right.)}}+{2^{\alpha-\beta}}-1}+\varepsilon$
(18)

Comparing this upper limit with the upper limit in the proof, it can be found
that this upper limit is much higher than the upper limit in the proof,
indicating that although the scaling idea of this method is more obvious, the
scaling method in the proof in this paper obtains a tighter upper limit.

## References

  * [1] Bennett, Charles and Brassard, G.  Quantum cryptography: Public key distribution and coin tossing.  _Theoretical Computer Science - TCS_ 560, 175–179 (1984).
  * [2] Tomamichel, M., Lim, C. C. W., Gisin, N. & Renner, R.  Tight finite-key analysis for quantum cryptography.  _Nature Communications_ 3, 634 (2012).  1103.4130.
  * [3] Gottesman, D., Hoi-Kwonglo, L. O., Lütkenhaus, N. & Preskill, J.  Security of quantum key distribution with imperfect devices.  _Quantum Information and Computation_ 4, 325–360 (2004).  0212066.
  * [4] Tamaki, K., Curty, M. & Lucamarini, M.  Decoy-state quantum key distribution with a leaky source.  _New Journal of Physics_ 18, 065008 (2016).
  * [5] Tomamichel, M., Schaffner, C., Smith, A. & Renner, R.  Leftover hashing against quantum side information.  _IEEE Transactions on Information Theory_ 57, 5524–5535 (2011).  1002.2436.
  * [6] Bennett, C. H., Brassard, G., Crkpeau, C., Maurer, U. M. & Member, S.  Generalized privacy amplification.  _Information Theory, IEEE Transactions on_ 41, 1915–1923 (1995).  URL http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=476316.
  * [7] Hayashi, M. & Tsurumaru, T.  More Efficient Privacy Amplification with Less Random Seeds via Dual Universal Hash Function.  _IEEE Transactions on Information Theory_ 62, 2213–2232 (2016).  arXiv:1311.5322v5.