Cryptography Reference
In-Depth Information
Case II.a We would have S
r−1
[r − 1] = r − 1, if the index r − 1 is not
touched during the rounds i = 0,...,r − 2. This happens with proba-
bility (
N−1
N
)
r−1
.
Case II.b Following Theorem 3.1.5, The event S
r−1
[y] = f
y
happens with
a probability (
N−y
N
)
[
y(y+1)
) (
N−1
N
+r−1]
+
1
N
. For small values of y,
2
N
)
[
y(y+1
2
+r−2]
(obtained by
considering the event A
y
only in the proof of Lemma 3.1.3), which gives
a simpler expression. For good approximation, we restrict y in [0,31].
this is approximately equal to (
N−y
N
) (
N−1
Case II.c In the r-th round (when i = r−1), j
r
becomes y with probability
1
N
.
Thus,
(S
r
[S
r
[y]] = f
y
)∧(S
r
[y] = r−1)
P
[
y(y+1)
2
r−1
+r−2]
1
N
N −1
N
N −y
N
N −1
N
=
y(y+1)
2
+2r−3
1
N
N −y
N
N −1
N
=
.
Adding the contributions of Cases I and II, we get
y(y+1)
2
+2r−3
N −2
N
1
N
N −y
N
N −1
N
q
r
(y) =
q
r−1
(y) +
.
The recurrence in Lemma 3.1.16 and the base case in Lemma 3.1.15
completely specify the probabilities q
r
(y) for all y in [0,...,31] and r in
[y + 1,...,N].
Now let us see what happens after the complete KSA.
Theorem 3.1.17. For 0 ≤ y ≤ 31,
y(y+1)
2
+2(N−2)
P(S
N
[S
N
[y]] = f
y
) ≈
y
N
N −1
N
y(y+1)
2
−y+2(N−1)
+
1
N
N −1
N
y(y+1)
2
+2N−3
N −y−1
N
N −y
N
N −1
N
+
Proof: Approximating (
N−2
N
) by (
N−1
N
)
2
, the recurrence in Lemma 3.1.16
can be rewritten as
y(y+1)
2
2
+2r−3
N −1
N
1
N
N −y
N
N − 1
N
q
r
(y) =
q
r−1
(y) +
,
