Cryptography Reference
In-Depth Information
Definition 8.4.4. (Candidate Pair) An ordered pair (u,v) is called a can-
didate pair, if u appears N + 1 rounds after v in the keystream and both u,v
come from the same index in the respective permutations.
Definition 8.4.5. (Conflict Set) A set {(u,v
1
),(u,v
2
)} of two candidate
pairs is called a conflict set, if v
1
= v
2
and it is not known whether v
1
=
suc
1
(u) or v
2
= suc
1
(u).
Definition 8.4.6. (Resolved Pair) A candidate pair (u,v) is called a re-
solved pair for a permutation P, if it is known that v = suc
1
(u).
Definition 8.4.7. (Resolved Permutation) A permutation P of size N is
said to be resolved, if for each element u in P, suc
1
(u) is known, or in other
words, if N −1 many distinct candidate pairs are resolved.
Since the permutation has N distinct elements, knowledge of N − 1 suc-
cessors for any N−1 elements reveals the successor of the remaining element.
Definition 8.4.8. (Partially Resolved Permutation) A permutation P
of size N is said to be partially resolved, if for some element u in P, suc
1
(u)
is not known, or in other words, if less than N − 1 many distinct candidate
pairs are resolved.
Definition 8.4.9. Given two partially resolved permutations P
1
and P
2
of
the same N elements, we say P
1
>P
2
or P
1
= P
2
or P
1
< P
2
, if the number
of resolved pairs for P
1
is more than or equal to or less than the number of
resolved pairs for P
2
respectively.
In the analysis of this section and the next, without loss of generality we
assume that j
G
is stuck at x = 0 from round 1 onwards. Since the index i
visits 0 to N − 1 cyclically, similar results hold for x = 0 also, which will be
discussed in Section 8.4.3.
Table 8.1 illustrates the structure of the permutation under the above fault
model at different rounds of the PRGA.
Proposition 8.4.10. Suppose the permutation after round ρN of the PRGA,
ρ ≥ 0, is
S
ρN
= < b
0
,b
1
,...,b
N−1
> .
Then the permutation after round ρN + y of the PRGA, 1 ≤ y ≤ N − 1, is
given by
S
ρN+y
= < b
y
,b
0
,...,b
y−1
,b
y+1
,...,b
N−1
> .
Proof: We prove it by induction on y.
Base Case: When y = 1, the deterministic index i
G
takes the value 1. So,
b
0
,b
1
are swapped and
S
ρN+1
= < b
1
,b
0
,b
2
,...,b
N−1
> .
Hence the result holds for y = 1.
