Cryptography Reference
In-Depth Information
S
κ
[κ] has remained κ so far. Further, suppose that S
N
[3] = 0 holds. Hence
S
N
[2] = κ, S
N
[k] = f
2
and S
N
[3] = 0 at the end of the KSA. In the second
round of the PRGA, S
1
[2] = κ is swapped with a more or less random location
S
1
[l]. Therefore, S
2
[l] = κ and j
2
= l. In the next round, i
3
= 3 and points
to S
2
[3] = 0. Hence j
G
does not change from its value in the previous round
and so j
3
= l = j
2
. Thus, S
2
[l] = κ is swapped with S
2
[3] = 0, and one has
S
3
[l] = 0 and S
3
[3] = κ. The output z
3
is now
S
3
[S
3
[i
3
] + S
3
[j
3
]]
= S
3
[κ + 0]
= S
3
[κ]
= f
2
.
Along the same line of argument given above, the general proof for any r
depends on P(S
N
[r] = 0). Recall that Item (2) of Theorem 3.2.11 presents
an explicit formula for the probabilities P(S
N
[u] = v), v ≤ u. Plugging in r
for u and 0 for v, we can state the following corollary.
Corollary 5.6.4. For 0 ≤r ≤ N −1, P(S
N
[r] = 0) = γ
r
, where
N−1−r
N−r
1
N
N −1
N
1
N
N −1
N
−
1
N
N −1
N
γ
r
=
+
.
Theorem 5.6.5. P(z
1
= f
0
)
2
N−1
γ
1
+
N −1
N
N −2
N
1
N
,
=
where
N−2
N−1
1
N
N −1
N
1
N
N − 1
N
−
1
N
N − 1
N
γ
1
=
+
.
Proof: Substituting r = 1,y = 0 in Proposition 3.1.5, we have
P(S
1
[0] = f
0
) = 1.
After the first round, suppose that the index 0 is touched for the first time by
j
τ+1
in round τ + 1 of the KSA and due to the swap the value f
0
is moved to
the index τ, 1 ≤ τ ≤ N −1 and also prior to this swap the value at the index
τ was τ itself, which now comes to the index 0. This means that from round
1 to round τ (both inclusive), the pseudo-random index j has not taken the
values 0 and τ. So, after round τ + 1,
P ((S
τ+1
[0] = τ)∧(S
τ+1
[τ] = f
0
))
= P ((S
τ
[0] = f
0
)∧(S
τ
[τ] = τ) ∧(j
τ+1
= 0))
τ
1
N −2
N
=
N
.
