Cryptography Reference
In-Depth Information
Proof: Consider any one of the 512 equations of System (10.16). Since the
sum Q[l
i
] +Q[u
i
] is known, knowledge of one of Q[l
i
], Q[u
i
] reveals the other.
Thus, if we know one word of Q at any index of a connected component,
we can immediately derive the words of Q at all the indices of the same
component. Since this holds for each connected component, we can guess any
one 32-bit word in the largest connected component correctly in 2
32
attempts
and thereby the result follows.
Since the arrays P,Q and the keystream of HC-128 are assumed to be
random, the index graph G can be considered to be a random bipartite graph.
Theoretical analysis of the size distribution of the connected components of
random finite graphs is a vast area of research in applied probability and there
have been several works [29, 65, 85, 125, 176] in this direction under different
graph models. In [176], the model considered is a bipartite graph G(n
1
,n
2
,T)
with n
1
vertices in the first part, n
2
vertices in the second one and the graph
is constructed by T independent trials. Each of them consists of drawing an
edge which joins two vertices chosen independently of each other from distinct
parts. This coincides with the index graph model of Definition 10.5.2 with
n
1
= |V
1
| and T = |E|.
In general, let n
1
≥ n
2
, α =
|, n
2
= |V
2
n
2
n
1
, β = (1 − α) ln n
1
, n = n
1
+ n
2
. Let
ξ
n
1
,n
2
,T
and χ
n
1
,n
2
,T
respectively denote the number of isolated vertices and
the number of connected components in G(n
1
,n
2
,T). We have the following
result from [176].
Proposition 10.5.4. If n → ∞ and (1 + α)T = nlnn + Xn + o(n), where
X is a fixed number, then Prob(χ
n
1
,n
2
,T
= ξ
n
1
,n
2
,T
+ 1) → 1 and for any
k = 0,1,2,..., Prob(ξ
n
1
,n
2
,T
= k)−
λ
k
e
−λ
→ 0, where λ =
e
−X
(1+e
−β
)
1+α
.
k!
In other words, if n is su
ciently large and n
1
,n
2
,T are related by
(1 + α)T = nlnn + Xn + o(n), then the graph contains one giant connected
component and isolated vertices whose number follows a Poisson distribution
with parameter λ given above.
Corollary 10.5.5. If M is the size of the largest component of the index
graph G, then the mean and standard deviation of M is respectively given by
E(M) ≈ 442.59 and sd(M) ≈ 8.33.
Proof: For the index graph of HC-128, n
1
= n
2
= 256, n = n
1
+ n
2
=
512, T = 512, α =
n
2
n
1
= 1, β = (1 − α) ln n
1
= 0. The relation (1 +
α)T = nlnn + Xn + o(n) is equivalent to
(1+α)
n
T = lnn + X +
o(n)
n
. As
o(n)
n
→ 0 and hence X →
(1+α)
n → ∞, the ratio
n
T − lnn. Substituting
α = 1, T = 512 and n = 512, we get X ≈ −4.24. By Proposition 10.5.4,
the limiting distribution of the random variable ξ
n
1
,n
2
,T
is Poisson with mean
(as well as variance) λ =
e
−X
(1+e
−β
)
1+α
≈ e
4.24
≈ 69.41. Moreover, in the
limit, χ
n
1
,n
2
,T
= ξ
n
1
,n
2
,T
+ 1 and this implies that all the vertices except the
isolated ones would be in a single giant component. So M = n−ξ
n
1
,n
2
,T
and
the expectation E(M) = n−E(ξ
n
1
,n
2
,T
) = n −λ ≈ 512 − 69.41 = 442.59.
