Cryptography Reference
In-Depth Information
If j
r
= i
r
+ 1, then the equivalent conditions in Lemma 5.4.4 correspond
to a Finney state. In the following results, one should exclude this case to
get better accuracy. However, this does not have much effect on the order of
probabilities, and further makes the calculations more cumbersome. So the
exclusion of Finney states is not considered in Lemma 5.4.4.
The above result leads to the following.
Theorem 5.4.5. P(j
r+2
= 2i
r
+ 4−j
r
) =
2
N
, r ≥ 0.
Proof: The event
(j
r+2
= 2i
r
+ 4−j
r
)
can occur in the following two ways:
Case I: S
r
[i
r+1
] = i
r
−j
r
+ 2 and hence by Lemma 5.4.4,
j
r+2
2j
r+1
−j
r
=
2(i
r
+ 2)−j
r
=
2i
r
+ 4−j
r
.
=
The contribution of this part is
1
N
.
P(S
r
[i
r+1
] = i
r
−j
r
+ 2) =
Case II: S
r
[i
r+1
] = i
r
−j
r
+ 2, but j
r+2
still equals 2i
r
+ 4 −j
r
due to
random association. From Lemma 5.4.4, we have
(S
r
[i
r+1
] = i
r
−j
r
+ 2)
=⇒ (j
r+2
= 2j
r+1
−j
r
).
Assuming that j
r+2
takes the other N − 1 values (except 2j
r+1
−j
r
)
uniformly at random, we have the contribution of this part as
+ 2)
1
N −1
1−
1
N
1
N −1
P(S
r
[i
r+1
] = i
r
−j
r
=
1
N
.
=
Adding the above two contributions, we get the result.
The above result implies that for any r ≥ 0, (j
r+2
|j
r
) is not distributed
uniformly at random in Z
N
. A closer look reveals that in this process the
keystream output during PRGA leaks information about the index j. To
prove this, we first need the following result.
Theorem 5.4.6. P(j
r+2
= i
r+2
+ j
r+1
−j
r
) =
2
N
, r ≥ 0.
