Cryptography Reference
In-Depth Information
and
S
y+1
[S
y+1
[y]]
= S
y+1
[x]
= S
y
[x]
= f
y
.
Following Lemma 3.1.3, this happens with probability
1+
y(y+1)
2
N −1
N
1
N
.
P(E
y
) =
+
For small values of y, this is approximately equal to
y(y+1)
2
N −1
N
P(A
y
) =
,
which gives a simpler expression (see the proof of Lemma 3.1.3 for the
definitions of the events E
y
and A
y
). We consider 0 ≤ y ≤ 31 for good
approximation.
Considering the events I.a, I.b, I.c and I.d to be independent, we have
P
(S
y+1
[S
y+1
[y]] = f
y
)∧(S
y+1
[y] = x)
y(y+1)
2
x
1
N
y−x−1
N −2
N
N −2
N
N −1
N
=
y(y+1)
2
y−1
1
N
N −2
N
N −1
N
=
.
Summing for all x in [0,...,y−1], we have
P
(S
y+1
[S
y+1
[y]] = f
y
)∧(S
y+1
[y] ≤ y−1)
y(y+1)
2
y−1
y
N
N −2
N
N −1
N
=
.
Next, suppose S
y+1
[y] = y. Now S
y+1
[S
y+1
[y]] can be equal to f
y
, if all of
the following three events occur.
1
Case II.a f
y
has to be equal to y. This happens with probability
N
.
Case II.b Index y is not touched by j in any of the first y rounds. This
happens with probability (
N−1
N
)
y
.
Case II.c In the (y + 1)-th round, j
y+1
= f
y
so that there is no swap. This
happens approximately with probability (
N−1
N
)
y(y+1)
(as explained in
2
Case I.d above).
