Cryptography Reference
In-Depth Information
From the end of round τ + 1 to the end of the KSA, f
0
remains in index τ
and the value τ remains in index 0 with probability (
N−2
N
)
N−τ−1
. Thus,
τ
1
N
N−τ−1
N −2
N
N −2
N
P ((S
N
[0] = τ)∧(S
N
[τ] = f
0
))
=
N−1
1
N
N −2
N
=
= β
1
(say).
In the first round of the PRGA,
j
1
= 0 + S
0
[1]
= S
N
[1].
From Corollary 5.6.4, we have
P(S
N
[1] = 0)
= γ
1
N−2
N−1
1
N
N −1
N
1
N
N −1
N
−
1
N
N −1
N
=
+
.
If S
N
[1] = 0, then j
1
= 0 and
= S
1
S
1
[1] + S
1
[j
1
]
z
1
= S
1
S
0
[1] + S
0
[j
1
]
= S
1
[0 + τ]
= S
1
[τ].
Since τ = 0, the swap of the values at the indices 0 and 1 does not move the
value at the index τ. Thereby
S
1
[τ] = S
0
[τ] = S
N
[τ] = f
0
and z
1
= f
0
with probability
β
1
γ
1
= δ
1
(say).
Since, τ can take values 1,2,3,...,N −1, the total probability is δ
1
(N −1).
Substituting the values of β
1
,γ
1
,δ
1
, we get the probability that the event
(z
1
= f
0
) occurs in the above path is
1
N−1
γ
1
.
N −1
N
N −2
N
p =
If the above path is not followed, still there is (1 − p)
N
probability
of occurrence of the event due to random association. Adding these two
probabilities, we get the result.
