Cryptography Reference
In-Depth Information
Conditioned on the event that all the values j
1
,j
2
,...,j
y
are different from y,
which happens with probability (
N−
N
)
y
, S
y
[y] remains the same as S
0
[y]. Note
that if at least one of the values j
1
,j
2
,...,j
y
hits the index y, the probability
that S
y
[y] remains the same as S
0
[y] is too small. Hence
y
N −1
N
P(S
y
[y] = S
0
[y]) ≈
.
This completes the proof.
Lemma 3.1.4. Assume that the index j takes its value from Z
N
independently
and uniformly at random at each round of the KSA. Then, for 0 ≤y ≤ r−1,
1 ≤r ≤ N,
r−1
N −y
N
N −1
N
P(S
r
[y] = S
0
[j
y+1
]) ≈
.
Proof: During round y + 1, the value of S
y
[j
y+1
] is swapped into S
y+1
[y].
Now, the index j
y+1
is not involved in any swap during the previous y many
rounds, if it is not touched by the indices {0,1,...,y − 1}, as well as if it is
not touched by the indices {j
1
,j
2
,...,j
y
}. The probability of the former is
(
N−y
N
) and the probability of the latter is (
N−1
N
)
y
. Hence,
y
N −y
N
N −1
N
P(S
y+1
[y] = S
0
[j
y+1
]) ≈
.
After round y + 1, index y is not touched by any of the subsequent r−1−y
many j values with probability (
N−1
N
)
r−1−y
. Hence,
y
r−1−y
N −y
N
N − 1
N
N −1
N
P(S
r
[y] = S
0
[j
y+1
]) ≈
r−1
N −y
N
N − 1
N
=
.
Theorem 3.1.5. Assume that the index j takes its value from Z
N
inde-
pendently and uniformly at random at each round of the KSA. Then, for
0 ≤y ≤ r−1, 1 ≤ r ≤ N,
[
y(y+1)
2
+r]
N −y
N
N −1
N
1
N
,
P(S
r
[y] = f
y
) ≈
+
where
y
y
f
y
= S
0
S
0
[x] +
K[x]
.
x=0
x=0
