Cryptography Reference
In-Depth Information
Hence,
(S
y+1
[S
y+1
[y]] = f
y
)∧(S
y+1
[y] = y)
P
y(y+1)
2
y
1
N
N −1
N
N −1
N
=
.
Adding the contributions of Case I (0 ≤ S
y+1
[y] ≤ y − 1) and Case II
(S
y+1
[y] = y), we get
(S
y+1
[S
y+1
[y]] = f
y
)∧(S
y+1
[y] ≤ y)
P
0
1
y(y+1)
2
y−1
y
1
N
N −1
N
N −2
N
N −1
N
@
A
=
y
+
.
For 0 ≤ y ≤ N −1, 1 ≤ r ≤N, let
q
r
(y) = P ((S
r
[S
r
[y]] = f
y
)∧(S
r
[y] ≤r−1)).
Lemma 3.1.16. For 0 ≤ y ≤ 31, y + 2 ≤ r ≤ N, we have
y(y+1)
2
+2r−3
N −2
N
1
N
N −y
N
N −1
N
q
r
(y) =
q
r−1
(y) +
.
Proof: For r ≥ y + 2, the event
(S
r
[S
r
[y]] = f
y
)∧(S
r
[y] ≤r−1)
can occur in two mutually exclusive and exhaustive ways:
Case I: ((S
r
[S
r
[y]] = f
y
)∧(S
r
[y] ≤ r−2)) and
Case II: ((S
r
[S
r
[y]] = f
y
)∧(S
r
[y] = r−1)).
Let us now calculate the contribution of each one separately.
In the r-th round, i = r − 1 ∈ {0,...,r − 2}. Thus, Case I occurs if we
already had
Case I.a ((S
r−1
[S
r−1
[y]] = f
y
)∧(S
r−1
[y] ≤r−2)) and
Case I.b j
r
∈{y,S
r−1
[y]}.
Hence, the contribution of this part is q
r−1
(y)(
N−
N
).
Case II occurs if after the (r−1)-th round, S
r−1
[r−1] = r−1, S
r−1
[y] = f
y
and in the r-th round (i.e., when i = r−1), j
r
= y causing a swap between the
elements at the indices y and r− 1. The probabilities for these three events
are as follows.
