52
3 Introducing Quantum Key Distribution
Recall that at the end of EC, Alice and Bob apply a two-universal hash function
on their raw keys R
n
A and ˆ
R
n
A , obtaining hashes h A and h B of length log(1/ε EC ).
The defining feature of two-universal hash functions is that the probability that two
outputs of length log(1/ε EC ) coincide, given that the inputs are different, is small,
namely: 2
−−log(1/ε EC ) (see Definition 2.11). In formulas, we have that:
Pr[h A = h B , R
n
A = ˆ
R
n
A ] ≤ Pr[h A = h B |R
n
A = ˆ
R
n
A ] ≤ 2
−−log(1/ε EC )
≤ ε EC . (3.47)
Then we observe that the keys s A and s B always coincide when the protocol aborts,
thus Pr[s A = s B , h A = h B ] = 0. By employing (3.47) in the following expression,
we prove that the protocol is ε EC -correct:
Pr[s A = s B ] = Pr[s A = s B , h A = h B ] ≤ Pr[R
n
A = ˆ
R
n
A , h A = h B ] ≤ ε EC . (3.48)
In order to prove the secrecy, we make use of the Quantum Leftover Hash Lemma
[9, 39], which provides the following upper bound:
1
2
ρ S A E tot | − ω S A ⊗ ρ E tot |
≤ 2ε +
1
2
2 −H
ε
min (R
n
A |C E) ,
(3.49)
where is the length of Alice’s key after PA and where we emphasize E tot being
the total information available to Eve. This comprises her purifying system E, the
classical communication C occurred during EC and the knowledge F of the hash
function used in PA: E tot = FC E.
We now employ the following chain-rule for the min-entropy [12]:
H
ε
min (R
n
A |C E) ≥ H
ε
min (R
n
A |E) − log |C|
= H
ε
min (R
n
A |E) − leak EC − log
2
ε EC
,
(3.50)
where log |C| quantifies all the information revealed during EC and is given by
leak EC + log(2/ε EC ) (see the protocol’s description).
By inserting Eq. (3.50) into (3.49) we obtain the following chain of inequalities:
1
2
ρ S A E tot | − ω S A ⊗ ρ E tot |
≤ 2ε +
1
2
2 −(H
ε
min (R
n
A |E)−leak EC −log(2/ε EC ))
≤ 2ε +
1
2
2 log(2 ε PA ) 2
= 2ε + ε PA ,
(3.51)
where we used the key length expression (3.27) in the second inequality. We have
thus proven that the protocol is ε sec -secret, with ε sec ≥ 2ε + ε PA . By combining this
with the correctness proof, we have shown that the protocol is ε tot -secure, with
ε tot ≥ 2ε + ε PA + ε EC . This concludes the proof.
3 Introducing Quantum Key Distribution
Recall that at the end of EC, Alice and Bob apply a two-universal hash function
on their raw keys R
n
A and ˆ
R
n
A , obtaining hashes h A and h B of length log(1/ε EC ).
The defining feature of two-universal hash functions is that the probability that two
outputs of length log(1/ε EC ) coincide, given that the inputs are different, is small,
namely: 2
−−log(1/ε EC ) (see Definition 2.11). In formulas, we have that:
Pr[h A = h B , R
n
A = ˆ
R
n
A ] ≤ Pr[h A = h B |R
n
A = ˆ
R
n
A ] ≤ 2
−−log(1/ε EC )
≤ ε EC . (3.47)
Then we observe that the keys s A and s B always coincide when the protocol aborts,
thus Pr[s A = s B , h A = h B ] = 0. By employing (3.47) in the following expression,
we prove that the protocol is ε EC -correct:
Pr[s A = s B ] = Pr[s A = s B , h A = h B ] ≤ Pr[R
n
A = ˆ
R
n
A , h A = h B ] ≤ ε EC . (3.48)
In order to prove the secrecy, we make use of the Quantum Leftover Hash Lemma
[9, 39], which provides the following upper bound:
1
2
ρ S A E tot | − ω S A ⊗ ρ E tot |
≤ 2ε +
1
2
2 −H
ε
min (R
n
A |C E) ,
(3.49)
where is the length of Alice’s key after PA and where we emphasize E tot being
the total information available to Eve. This comprises her purifying system E, the
classical communication C occurred during EC and the knowledge F of the hash
function used in PA: E tot = FC E.
We now employ the following chain-rule for the min-entropy [12]:
H
ε
min (R
n
A |C E) ≥ H
ε
min (R
n
A |E) − log |C|
= H
ε
min (R
n
A |E) − leak EC − log
2
ε EC
,
(3.50)
where log |C| quantifies all the information revealed during EC and is given by
leak EC + log(2/ε EC ) (see the protocol’s description).
By inserting Eq. (3.50) into (3.49) we obtain the following chain of inequalities:
1
2
ρ S A E tot | − ω S A ⊗ ρ E tot |
≤ 2ε +
1
2
2 −(H
ε
min (R
n
A |E)−leak EC −log(2/ε EC ))
≤ 2ε +
1
2
2 log(2 ε PA ) 2
= 2ε + ε PA ,
(3.51)
where we used the key length expression (3.27) in the second inequality. We have
thus proven that the protocol is ε sec -secret, with ε sec ≥ 2ε + ε PA . By combining this
with the correctness proof, we have shown that the protocol is ε tot -secure, with
ε tot ≥ 2ε + ε PA + ε EC . This concludes the proof.