Cryptography Reference
In-Depth Information
Theorem 5.6.6. For 3 ≤ r ≤N, P(z
r
= f
r−1
)
0
1
[
r(r−1)
2
+r]
N −1
N
N −r
N
N −r + 1
N
N −1
N
1
N
@
A
≈
+
N−r
r−2
γ
r
+
N −2
N
N −3
N
1
N
,
where
N−1−r
N−r
1
N
N −1
N
1
N
N −1
N
−
1
N
N −1
N
γ
r
=
+
.
Proof: Substituting y = r−1 in Theorem 3.1.5, we have
P(S
r
[r−1] = f
r−1
) = α
r
,
where for 1 ≤r ≤ N,
[
r(r−1)
2
+r]
N −r + 1
N
N −1
N
+
1
N
.
After round r, suppose that the index r − 1 is touched for the first time by
j
τ+1
in round τ + 1 of the KSA and due to the swap the value f
r−1
is moved
to the index τ, r ≤ τ ≤ N − 1 and also prior to this swap the value at the
index τ was τ itself, which now comes to the index r − 1. This means that
from round r + 1 to round τ (both inclusive), the pseudo-random index j has
not taken the values r−1 and τ. So, after round τ + 1,
α
r
≈
P ((S
τ+1
[r−1] = τ)∧(S
τ+1
[τ] = f
r−1
))
= P ((S
τ
[r−1] = f
r−1
)∧(S
τ
[τ] = τ)∧(j
τ+1
= r−1))
τ−r
1
N −2
N
N
.
From the end of round τ + 1 until the end of the KSA, f
r−1
remains in index
τ and the value τ remains in index r−1 with probability (
N−2
N
= α
r
)
N−τ−1
. Thus,
P ((S
N
[r−1] = τ)∧(S
N
[τ] = f
r−1
))
τ−r
1
N
N−τ−1
N −2
N
N −2
N
= α
r
N−r−1
1
N
N −2
N
= α
r
= β
r
(say).
Also, from Corollary 5.6.4, we have
P(S
N
[r] = 0)
= γ
r
N−1−r
N−r
1
N
N −1
N
1
N
N −1
N
−
1
N
N −1
N
=
+
.
