46
3 Introducing Quantum Key Distribution
The correctness definition implies that the protocol always outputs identical keys for
Alice and Bob, except for probability at most ε cor .
The secrecy statement is a bit more involved. A real QKD protocol is ε sec -secret if
it is ε sec -indistinguishable from an ideal QKD protocol. By definition, the ideal QKD
protocol acts exactly like the real protocol but it always outputs a perfectly secret key
for Alice, i.e. a uniformly distributed key independent of Eve’s knowledge, whenever
the real protocol does not abort [7, 13]. This is formalized by stating that the output
states of the real and ideal protocol are given by (we ignore Bob’s system):
ρ
real
S A E tot
= Pr
| ⊥⊥⊥⊥ | S A ⊗ ρ E tot | + Pr[] ρ S A E tot |
ρ
ideal
S A E tot
= Pr
| ⊥⊥⊥⊥ | S A ⊗ ρ E tot | + Pr[] ω S A ⊗ ρ E tot | ,
(3.31)
where is the event that the protocol aborts. The real and ideal protocol are ε sec -
indistinguishable if their output states (3.31) are such,
5 i.e. when (Definition 2.14):
T (ρ
real
S A E tot
, ρ
ideal
S A E tot
) ≤ ε sec .
(3.32)
One can easily verify that (3.32) reduces to the condition (3.30) by using the definition
of trace distance (Definition 2.13), since the abortion component of the two states in
(3.31) cancels out when taking the difference.
The secrecy of Alice’s key s A alone does not guarantee that even Bob’s key s B
is secret, unless we combine it with a statement on the correctness of the protocol.
Therefore we define the security of a QKD protocol as follows.
Definition 3.3 (Security) A QKD protocol is said to be ε tot -secure if it is ε cor -correct
and ε sec -secret, with ε tot ≥ ε cor + ε sec .
Note that a trivial protocol that always aborts and outputs s A = s B =⊥ is secure
according to the above definitions. Thus, another important feature of a QKD protocol
is its completeness, i.e. the existence of an honest implementation of the protocol
such that the probability of not aborting is Pr[] ≥ 1 − ε c , for some small ε c .
We also remark that the Definitions 3.1, 3.2 and 3.3 are composable. This means
that when a QKD protocol—proven secure according to these definitions—is composed with another cryptographic task, the security of their combination can be
inferred based on their individual security proofs and does not require a separate
new proof. This is particularly relevant for QKD, which is often composed with
one-time pads as discussed in Sect. 3.1.
Lemma 3.1 (Security of QKD) The general QKD protocol of Sect. 3.3.1 is ε tot -
secure, with ε tot ≥ ε EC + 2ε + ε PA .
5 More precisely, the two protocols are ε sec -indistinguishable if the distinguishing advantage of an
unbounded distinguisher, attempting to distinguish the real and ideal protocol, is upper bounded
by ε sec . In [13] the authors show that such distinguishing advantage reduces to the trace distance
between the output states of the protocols.
3 Introducing Quantum Key Distribution
The correctness definition implies that the protocol always outputs identical keys for
Alice and Bob, except for probability at most ε cor .
The secrecy statement is a bit more involved. A real QKD protocol is ε sec -secret if
it is ε sec -indistinguishable from an ideal QKD protocol. By definition, the ideal QKD
protocol acts exactly like the real protocol but it always outputs a perfectly secret key
for Alice, i.e. a uniformly distributed key independent of Eve’s knowledge, whenever
the real protocol does not abort [7, 13]. This is formalized by stating that the output
states of the real and ideal protocol are given by (we ignore Bob’s system):
ρ
real
S A E tot
= Pr
| ⊥⊥⊥⊥ | S A ⊗ ρ E tot | + Pr[] ρ S A E tot |
ρ
ideal
S A E tot
= Pr
| ⊥⊥⊥⊥ | S A ⊗ ρ E tot | + Pr[] ω S A ⊗ ρ E tot | ,
(3.31)
where is the event that the protocol aborts. The real and ideal protocol are ε sec -
indistinguishable if their output states (3.31) are such,
5 i.e. when (Definition 2.14):
T (ρ
real
S A E tot
, ρ
ideal
S A E tot
) ≤ ε sec .
(3.32)
One can easily verify that (3.32) reduces to the condition (3.30) by using the definition
of trace distance (Definition 2.13), since the abortion component of the two states in
(3.31) cancels out when taking the difference.
The secrecy of Alice’s key s A alone does not guarantee that even Bob’s key s B
is secret, unless we combine it with a statement on the correctness of the protocol.
Therefore we define the security of a QKD protocol as follows.
Definition 3.3 (Security) A QKD protocol is said to be ε tot -secure if it is ε cor -correct
and ε sec -secret, with ε tot ≥ ε cor + ε sec .
Note that a trivial protocol that always aborts and outputs s A = s B =⊥ is secure
according to the above definitions. Thus, another important feature of a QKD protocol
is its completeness, i.e. the existence of an honest implementation of the protocol
such that the probability of not aborting is Pr[] ≥ 1 − ε c , for some small ε c .
We also remark that the Definitions 3.1, 3.2 and 3.3 are composable. This means
that when a QKD protocol—proven secure according to these definitions—is composed with another cryptographic task, the security of their combination can be
inferred based on their individual security proofs and does not require a separate
new proof. This is particularly relevant for QKD, which is often composed with
one-time pads as discussed in Sect. 3.1.
Lemma 3.1 (Security of QKD) The general QKD protocol of Sect. 3.3.1 is ε tot -
secure, with ε tot ≥ ε EC + 2ε + ε PA .
5 More precisely, the two protocols are ε sec -indistinguishable if the distinguishing advantage of an
unbounded distinguisher, attempting to distinguish the real and ideal protocol, is upper bounded
by ε sec . In [13] the authors show that such distinguishing advantage reduces to the trace distance
between the output states of the protocols.