Cryptography Reference
In-Depth Information
Remark 8.4.13. At the point j
G
gets stuck, the permutation S
G
can be
considered to be a random permutation. Thus each byte of the first run, af-
ter j
G
got stuck, can be assumed to be chosen uniformly at random from
{0,...,N − 1}. Since we use sets of two consecutive runs for collecting the
candidate pairs, the values in each such pair can also be regarded uniformly
random for estimating the expected numbers of distinct candidate pairs and
conflict sets. Extensive experimentations also confirm this randomness as-
sumption, which is followed in the technical results in the rest of this section.
Theorem 8.4.14. The expected number of unassigned entries in the ar-
ray Next after the execution of the PartResolvePerm algorithm is N
(
N−1
N
)
(R−1)(N−2)
.
Proof: The candidate pairs are of the form
(z
(ρ+1)N+(y+1)
,z
ρN+y
),
0 ≤ρ ≤ R−2,1 ≤ y ≤ N −2.
Thus, each distinct value of
z
ρN+y
,
0 ≤ρ ≤ R−2,1 ≤ y ≤ N −2,
would give rise to a candidate pair and hence assign exactly one entry of the
array Next.
Let x
u
= 1, if the value u does not occur in any of the (R−1)(N−2) many
keystream bytes z
ρN+y
, 0 ≤ ρ ≤ R−2, 1 ≤ y ≤ N −2; otherwise, let x
u
= 0,
0 ≤u ≤N −1. Hence, the total number of values that did not occur in those
N−1
keystream bytes is given by X =
x
u
. Assuming that each keystream byte
u=0
is uniformly randomly distributed in {0,...,N −1}, we have
(R−1)(N−2)
N −1
N
P(x
u
= 1) =
.
Thus,
(R−1)(N−2)
N −1
N
E(x
u
) =
and
N−1
E(X)
=
E(x
u
)
u=0
(R−1)(N−2)
N −1
N
= N
.
Corollary 8.4.15. The expected number of distinct candidate pairs after the
execution of the PartResolvePerm algorithm is N
1−(
N−1
N
)
(R−1)(N−2)
.
