Cryptography Reference
In-Depth Information
Proof: First, let us calculate the following conditional probability.
P(z
r
= 0 | S
r−1
[r] = r)
= P
S
r
[S
r
[r] + S
r−1
[r]] = 0 | S
r−1
[r] = r
S
r
[S
r
[r] + r] = 0 | S
r−1
[r] = r
= P
N−1
S
r
[x + r] = 0 & S
r
[r] = x | S
r−1
[r] = r
=
P
x=0
N−1
S
r
[x + r] = 0 & S
r
[r] = x
=
P
.
(6.1)
x=0
Observe that S
r−1
[r] = r gets swapped to produce the new state S
r
and so
we can claim the independence of S
r
[r] and S
r−1
[r].
Now, let us compute P(S
r
[x + r] = 0 & S
r
[r] = x) = P(S
r
[x + r] =
0) P(S
r
[r] = x | S
r
[x + r] = 0). If there exists any bias in the event
(S
r
[x+r] = 0), it must have originated from a similar bias in (S
0
[x+r] = 0)
(similar to the case of (S
r−1
[r] = r) in Lemma 6.2.5). However, P(S
0
[x+r] =
0) =
1
N
by Theorem 3.2.3, and thus we can safely assume S
r
[x + r] to be
random as well. This provides us with P(S
r
[x + r] = 0) =
1
N
.
For P(S
r
[r] = x|S
r
[x+r] = 0), observe that when x = 0, the indices x+r
and r in the state S
r
point to the same location, and the events (S
r
[x+r] =
S
r
[r] = 0) and (S
r
[r] = x = 0) denote identical events. So in this case,
P(S
r
[r] = x | S
r
[x + r] = 0) = 1. On the other hand, when x = 0, the
indices x + r and [r] refer to two distinct locations in the permutation S
r
,
containing two different values. In this case,
P(S
r
[r] = x | S
r
[x + r] = 0) = P(S
r
[r] = x | x = 0) =
1
N −1
.
The randomness assumption of S
r
[r] for x = 0 falls back upon the randomness
assumption of j
r
, the value at which index comes to index r due to the swap.
According to the discussion above, we obtain
1
N
1
N
1 =
if x = 0,
S
r
[x + r] = 0 & S
r
[r] = x
P
=
1
N
1
1
N(N−1)
N−1
=
if x = 0.
(6.2)
Substituting these probability values in Equation (6.1), we get
z
r
= 0 | S
r−1
[r] = r
P
N−1
S
r
[x + r] = 0 & S
r
[r] = x
=
P
x=0
N−1
1
N
+
1
N(N −1)
=
x=1
N
+ (N −1)
1
1
2
N
.
=
N(N −1)
=
