Cryptography Reference
In-Depth Information
Case II: S
ρN
[0] = 0. In this case, it is assumed that z
ρN
takes the value 0
due to random association only.
Combining the above two cases, one gets
P(z
ρN
= 0 | j
ρN
= 0)
= P(S
ρN
[0] = 0)P(z
ρN
= 0 | S
ρN
[0] = 0,j
ρN
= 0)
+P(S
ρN
[0] = 0)P(z
ρN
= 0 | S
ρN
[0] = 0,j
ρN
= 0)
1
N
1−
1
N
1
N
=
1 +
2
N
−
1
N
2
=
≈
2
N
.
= 0. We claim that if S
ρN
[2] = 0,
then z
ρN+2
can never become zero. The reason is as follows. Suppose
S
ρN
[1] = X, which cannot be zero, S
ρN
being a permutation. Further, sup-
pose S
ρN
[j
ρN
+ X] = Y (which is also not zero). In round ρN + 1, i
ρN+1
becomes 1 and
Now, consider the scenario when j
ρN
j
ρN+1
= j
ρN
+ S
ρN
[1]
= j
ρN
+ X.
After the swap, Y comes to index 1 and X goes to index j
ρN
+ X. In round
ρN + 2, i
ρN+2
takes the value 2 and
j
ρN+2
= j
ρN+1
+ S
ρN
[2]
= j
ρN
+ X.
Thus, after the swap, X comes to index 2 and 0 goes to index j
ρN
+X. Hence
the output is
= S
ρN+2
[X + 0]
= S
ρN+2
[X]
=
z
ρN+2
0.
Thus, given j
ρN
= 0, we must have S
ρN
[2] = 0 for z
ρN+2
to be zero. We
assume that given j
ρN
= 0 and S
ρN
[2] = 0, z
ρN+2
is uniformly distributed.
