28
2 Elements of Quantum Information Theory
The goal of privacy amplification (PA) is to extract a secret key S by applying a
random function F on K : S = F(K ). We define a key to be secret if it is distributed
uniformly and is independent of Eve’s quantum side information E.
Ideally, PA is successful if the quantum state describing Alice’s key S and Eve’s
side information E F (we allow Eve to know which function Alice applied on her
key K ) is given by:
ρ SE F = ω S ⊗ ρ E F ,
(2.68)
where the state of the secret key S is uniformly distributed over the possible final
keys s ∈ S of Alice:
ω S =
1
|S|
s∈S
|ss |.
(2.69)
Indeed, in ρ SE F Eve’s system is no longer correlated with the state |s of Alice’s key
after PA, hence the key S is secret.
In reality, we relax the claim on the success of PA by allowing the final state
ρ SE F to be “almost” indistinguishable from the ideal scenario given by the r.h.s. of
(2.68). Specifically, we require ρ SE F to be ε-indistinguishable (see Sect. 2.11) from
ω S ⊗ ρ E F . This translates to an upper bound on the trace distance between the two
states (c.f. Sect. 2.11):
T (ρ SE F , ω S ⊗ ρ E F ) ≤ ε.
(2.70)
In order for Alice to achieve the PA goal stated in (2.70), she applies to her key K
a hash function f from a two-universal family: f ∈ R F , where “∈ R ” indicates that
the function is randomly picked, with probability 1/ |F |, from the family F .
Definition 2.11 (Two-universal family [4, 15]) A family of hash functions F =
{ f s.t. f : K → S} is two-universal if, for every pair of keys k 1 , k 2 ∈ K such that
k 1 = k 2 , it holds
3 :
Pr f ∈ R F [ f (k 1 ) = f (k 2 )] ≤
1
|S|
.
(2.71)
The state ρ SE F of Alice’s final key and Eve’s information after PA reads:
ρ SE F =
f ∈F
1
|F |
ρ f (K )E ⊗ | f f | F ,
(2.72)
where the state ρ f (K )E is obtained from ρ K E in (2.57) by specifically applying the
hash function f to the key K , and is given by:
3 Note that the number of functions in a two-universal family, |F |, must be in general larger than the
number of keys they can generate, |S|. Indeed: Pr f ∈ R F [ f (k 1 ) = f (k 2 )] =
|{ f ∈F : f (k1)= f (k2)}|
|F |
≤
1
|S| , which implies that |F | ≥ |S|.
2 Elements of Quantum Information Theory
The goal of privacy amplification (PA) is to extract a secret key S by applying a
random function F on K : S = F(K ). We define a key to be secret if it is distributed
uniformly and is independent of Eve’s quantum side information E.
Ideally, PA is successful if the quantum state describing Alice’s key S and Eve’s
side information E F (we allow Eve to know which function Alice applied on her
key K ) is given by:
ρ SE F = ω S ⊗ ρ E F ,
(2.68)
where the state of the secret key S is uniformly distributed over the possible final
keys s ∈ S of Alice:
ω S =
1
|S|
s∈S
|ss |.
(2.69)
Indeed, in ρ SE F Eve’s system is no longer correlated with the state |s of Alice’s key
after PA, hence the key S is secret.
In reality, we relax the claim on the success of PA by allowing the final state
ρ SE F to be “almost” indistinguishable from the ideal scenario given by the r.h.s. of
(2.68). Specifically, we require ρ SE F to be ε-indistinguishable (see Sect. 2.11) from
ω S ⊗ ρ E F . This translates to an upper bound on the trace distance between the two
states (c.f. Sect. 2.11):
T (ρ SE F , ω S ⊗ ρ E F ) ≤ ε.
(2.70)
In order for Alice to achieve the PA goal stated in (2.70), she applies to her key K
a hash function f from a two-universal family: f ∈ R F , where “∈ R ” indicates that
the function is randomly picked, with probability 1/ |F |, from the family F .
Definition 2.11 (Two-universal family [4, 15]) A family of hash functions F =
{ f s.t. f : K → S} is two-universal if, for every pair of keys k 1 , k 2 ∈ K such that
k 1 = k 2 , it holds
3 :
Pr f ∈ R F [ f (k 1 ) = f (k 2 )] ≤
1
|S|
.
(2.71)
The state ρ SE F of Alice’s final key and Eve’s information after PA reads:
ρ SE F =
f ∈F
1
|F |
ρ f (K )E ⊗ | f f | F ,
(2.72)
where the state ρ f (K )E is obtained from ρ K E in (2.57) by specifically applying the
hash function f to the key K , and is given by:
3 Note that the number of functions in a two-universal family, |F |, must be in general larger than the
number of keys they can generate, |S|. Indeed: Pr f ∈ R F [ f (k 1 ) = f (k 2 )] =
|{ f ∈F : f (k1)= f (k2)}|
|F |
≤
1
|S| , which implies that |F | ≥ |S|.