Cryptography Reference
In-Depth Information
Proof: We would be referring to the events A
1
(y) and A
2
(y) in the proof
of Theorem 4.5.1. From Theorem 4.5.1, we have
N−1
y + 1
N
N −1
N
P (A
1
(y))
=
N−1
N −y
N
N −1
N
and P (A
2
(y))
=
.
For each probability p
yx
in items (1) and (2), we would consider two com-
ponents. The component which comes due to the contributions of the events
A
1
(y),A
2
(y) etc, would be called α
yx
. The other component is due to random
association and is given by (1−α
yx
)
N
. So for each probability p
yx
, deriving
the part α
yx
su
ces, as the total probability can be computed as
α
yx
+ (1−α
yx
)
1
N
=
N −1
1
N
.
α
yx
+
N
Consider the update rule in the KSA:
j
y+1
= j
y
+ S
y
[y] + K[y],
0 ≤ y ≤N −1,
where j
0
= 0.
First, we prove item (1). Since S
0
[0] = 0, we can write j
1
= K[0]. Consid-
ering j
1
= S
−1
N
[0], we have
α
01
= P (A
1
(0))
and considering j
1
= S
N
[0], we have
α
02
= P(A
2
(0)).
Substituting 0 for y in the expressions for P (A
1
(y)) and P (A
2
(y)), we get
the results.
Now, we come to item (2). In the update rule, S
y
[y] can be replaced by y,
assuming that it has not been touched by any one of j
1
,j
2
,...,j
y
in the first
y rounds of the KSA. This happens with a probability
y
N −1
N
,
0 ≤ y ≤N −1.
Assuming S
y
[y] = y, we can write
K[y] = j
y+1
−j
y
−y.
When considering the contribution of A
1
(y) to j
y+1
, the factor (
N−
N
)
y
need
not be taken into account, as the event (S
y
[y] = y) is already contained in
