Cryptography Reference
In-Depth Information
completely known. Clearly, if we know one Q[y], we know all subsequent
Q[y + 12k], for k = 1,2,..., as long as y + 12k ≤ 511. This means k ≤
511−y
12
.
The number m of words of Q that can be determined is then the maximum
allowable value of k, i.e., m = ⌊
511−y
12
⌋.
By recursively applying (10.18) to the words of the Q array determined
from the maximum size connected component of the index graph, we derive
many of around 104(= 512 − 408) unknown words in the array. This is the
Third Phase of the recovery algorithm. If we imagine the words initially
labeled as “known” or “unknown,” then this step can be visualized as prop-
agation of the “known” labels in the forward direction. Even after this step,
some words remain unknown. However, as Theorem 10.5.7 implies, through
this propagation, all the words Q[500],Q[501],...,Q[511] can be “known”
with probability almost 1.
Theorem 10.5.7. After the Third Phase, the expected number of unknown
words among Q[500], Q[501], ..., Q[511] is approximately 8(1−
43
512
)
M
+ 4
(1 −
42
512
)
M
, where M is the size of the largest component of the index graph
G.
Proof: After the Second Phase, exactly M words Q[y
1
], Q[y
2
], ..., Q[y
M
]
are known corresponding to the distinct indices y
1
, y
2
, ..., y
M
in the largest
component C of size M in G. Since G is a random bipartite graph, each of in-
dices y
1
,y
2
,...y
M
can be considered to be drawn from the set {0,1,...,511}
uniformly at random (without replacement). We partition this sample space
into 12 disjoint residue classes modulo 12, denoted by, [0],[1],...,[11]. Then,
each of the indices y
1
,y
2
,...,y
M
can be considered to be drawn from the set
{[0],[1],...,[11]} (this time with replacement; this is a reasonable approxi-
mation because M ≫ 12) with probabilities proportional to the sizes of the
residue classes. Thus, for 1 ≤ j ≤ M, Prob(y
j
43
512
∈ [r]) =
if 0 ≤ r ≤ 7 and
42
512
if 8 ≤r ≤ 11.
Let m
r
= 1, if none of y
1
,y
2
,...,y
M
are from [r]; otherwise, let m
r
= 0.
Hence, the total number of residue classes from which no index is selected is
11
Y =
m
r
. Now, in the Third Phase, we propagate the known labels in the
r=0
forward direction using (10.18) (see Theorem 10.5.6, the Propagation Theo-
rem). The indices {500,501,...,511} are to the extreme right end of the array
Q and hence they also form the set of “last” indices where the propagation
eventually stops. Further, each index in the set {500,501,...,511} belongs
to exactly one of the sets [r]. Hence, the number of unknown words among
Q[500], Q[501], ..., Q[511] is also given by Y .
We have,
(1−
43
512
)
M
for 0 ≤r ≤ 7;
E(m
r
) = Prob(m
r
= 1) =
(1−
42
512
)
M
for 8 ≤r ≤ 11.
