4.3 Experimental CKA
67
Appendix
In this Appendix we prove the security of the general CKA protocol described in
Sect. 4.2.1, as stated in Lemma 4.1. A similar proof can be found in [13].
4.4 Finite-key Security of CKA
Proof We first show that the CKA scheme of Sect. 4.2.1 is ε EC -correct. Recall that
Alice and the Bobs check if the output of the EC is successful. They do so by
comparing the hashes h A and h B i (for i = 1, . . . , N − 1) obtained by applying the
same two-universal hash function on Alice’s raw key R
n
A and on the Bobs’ guesses
ˆ
R
n
A i
, respectively. Each hash is log((N − 1)/ε EC ) bits long.
According to Definition 2.11, the probability that two b-bit outputs of a randomlypicked hash function coincide, given that the inputs are different, is given by: 2
−b .
If there exists a hash h B i such that h B i = h A , the protocol aborts and outputs the
trivial keys s A = s B 1 = · · · = s B N −1 =⊥. This implies that the following event has
probability zero: Pr[s A = s B i , h A = h B i ] = 0 and thus Pr[s A = s B i ] = Pr[s A = s B i ,
h A = h B i ]. Then the CKA is proved to be ε EC -correct, according to Definition 4.1,
by the following chain of inequalities:
Pr[∪
N −1
i=1 s A = s B i ] = Pr[∪
N −1
i=1 (s A = s B i , h A = h B i )]
≤
N −1
i=1
Pr[s A = s B i , h A = h B i ]
≤
N −1
i=1
Pr[h A = h B i , R
n
A = ˆ
R
n
A i
]
≤
N −1
i=1
Pr[h A = h B i |R
n
A = ˆ
R
n
A i
]
≤
N −1
i=1
2
−−log
N −1
ε EC
≤ (N − 1)
ε EC
N − 1
≤ ε EC .
(4.13)
In the above derivation the first inequality is due to the union bound, the second
holds because the final keys s A and s B i are obtained from R
n
A and ˆ
R
n
A i
with another
two-universal hash function, and the fourth inequality follows from Definition 2.11.
67
Appendix
In this Appendix we prove the security of the general CKA protocol described in
Sect. 4.2.1, as stated in Lemma 4.1. A similar proof can be found in [13].
4.4 Finite-key Security of CKA
Proof We first show that the CKA scheme of Sect. 4.2.1 is ε EC -correct. Recall that
Alice and the Bobs check if the output of the EC is successful. They do so by
comparing the hashes h A and h B i (for i = 1, . . . , N − 1) obtained by applying the
same two-universal hash function on Alice’s raw key R
n
A and on the Bobs’ guesses
ˆ
R
n
A i
, respectively. Each hash is log((N − 1)/ε EC ) bits long.
According to Definition 2.11, the probability that two b-bit outputs of a randomlypicked hash function coincide, given that the inputs are different, is given by: 2
−b .
If there exists a hash h B i such that h B i = h A , the protocol aborts and outputs the
trivial keys s A = s B 1 = · · · = s B N −1 =⊥. This implies that the following event has
probability zero: Pr[s A = s B i , h A = h B i ] = 0 and thus Pr[s A = s B i ] = Pr[s A = s B i ,
h A = h B i ]. Then the CKA is proved to be ε EC -correct, according to Definition 4.1,
by the following chain of inequalities:
Pr[∪
N −1
i=1 s A = s B i ] = Pr[∪
N −1
i=1 (s A = s B i , h A = h B i )]
≤
N −1
i=1
Pr[s A = s B i , h A = h B i ]
≤
N −1
i=1
Pr[h A = h B i , R
n
A = ˆ
R
n
A i
]
≤
N −1
i=1
Pr[h A = h B i |R
n
A = ˆ
R
n
A i
]
≤
N −1
i=1
2
−−log
N −1
ε EC
≤ (N − 1)
ε EC
N − 1
≤ ε EC .
(4.13)
In the above derivation the first inequality is due to the union bound, the second
holds because the final keys s A and s B i are obtained from R
n
A and ˆ
R
n
A i
with another
two-universal hash function, and the fourth inequality follows from Definition 2.11.