Cryptography Reference
In-Depth Information
3. the value x at which j
G
remains stuck.
We here sketch the modification corresponding to Step 5 of the algorithm
PartResolvePerm as well as Step 3 of algorithm ResolveConflicts), where y
varies from 1 to N−2. In Section 8.4.1, j
G
was assumed to be stuck at 0 from
round r
st
= 1, when i
st
was also 1. Thus, it was already known in advance
that the candidate pairs (z
(ρ+1)N+(y+1)
,z
ρN+y
), for y = N −1,N (i.e., when
the deterministic index i
G
takes the values j
G
− 1,j
G
), should be ignored.
On the contrary, here both r
st
and i
st
are unknown. In order to process the
keystream bytes using the algorithms PartResolvePerm and ResolveConflicts,
we need to initialize ρ to 0 at the point j
G
gets stuck and from that point
onwards the keystream bytes are named as z
1
,z
2
,... and so on. Given j
G
is
stuck at an unknown value x, when the deterministic index i
G
would take the
values x−1 and x, the two corresponding candidate pairs should be ignored.
However, these two cases cannot be identified and eliminated here, as x is not
known. Hence, in Step 5 of the algorithm PartResolvePerm and Step 3 of
algorithm ResolveConflicts, we should consider that y varies from 1 to N for
each value of ρ ∈{0,1,...,R−3} and y varies from 1 to N −1 for ρ = R−2.
In this modified approach, utilizing all the RN keystream bytes yields a
total of (R−1)N−1 candidate pairs. Following the same line of arguments as
in Theorem 8.4.14, we get the expected number of unassigned entries in the
array Next just before the execution of Step 3 of InvertStuckPRGA as
(R−1)N−1
N −1
N
A
′
= N
which, for large N (such as N = 256), is approximately equal to
(R−1)(N−2)
N −1
N
A = N
.
Since we get two additional wrong entries in each of the R−1 runs, the num-
ber of conflict sets would increase by 2(R − 1) from the value estimated in
Theorem 8.4.16. Thus, the modified upper bound on the expected number
of conflict sets after the execution of the PartResolvePerm algorithm, when
the candidate pairs are formed by considering all the keystream bytes in each
run, is given by (R−1)(2 +
N−
N
). Observe that the bound is still O(R) as
in Theorem 8.4.16. However, since i
st
and x are not known, we need to run
Step 4 of the ConstructPerm Algorithm for each possible value of i
st
and x in
{0,...,N −1}, until Step 6 of ConstructPerm reveals the true initial permu-
tation. Thus, we need at most N
2
executions of Step 4 of ConstructPerm for
each of the ⌈A⌉! resolved permutations, where
(R−1)(N−2)
N −1
N
A = N
.
