Cryptography Reference
In-Depth Information
Obviously, Prob(H
b
(ξ
i
) = H
b
(ξ
j
)⊕1) =
2
−2
−81
.
The above results can be combined to formulate the following theorem.
Theorem 10.3.4. For 1024τ + 10 ≤j < i < 1024τ + 511,
[ψ
i
]
b
= [ψ
j
]
b
Prob
= r
b
,
where
<
:
2
+ 2
−81
if b = 0;
1
2
if b = 1;
r
b
=
2
+
2
−81
1
(approximately)
if 2 ≤ b≤ 31.
9
Proof:
[ψ
i
]
b
= [ψ
j
]
b
Prob
[ψ
i
]
b
⊕[ψ
j
]
b
= H
b
(ξ
i
)⊕H
b
(ξ
j
)
= Prob
Prob(H
b
(ξ
i
) = H
b
(ξ
j
)) +
[ψ
i
]
b
⊕[ψ
j
]
b
= H
b
(ξ
i
)⊕H
b
(ξ
j
)⊕1
Prob
Prob(H
b
(ξ
i
) = H
b
(ξ
j
)⊕1).
Substitute values from Lemma 10.3.2 and Corollary 10.3.3 to get the final
expression.
For the special case of b = 0, there exists a distinguisher based on the bias
1
2
+2
−81
in the equality of the LSB's of ψ
i
and ψ
j
. This is exactly the same as
Wu's distinguisher described in the previous section. The above results show
that we can also mount a distinguisher of around the same order for each of
the 30 bits corresponding to b = 2,3,...,31 based on the bias
2
+
2
−81
9
.
Two random 32-bit integers are expected to match in 16 bit positions. It is
easy to show that if one performs a bitwise comparison of the 32-bit elements
([ψ
i
]
31
,[ψ
i
]
30
,...,[ψ
i
]
0
)
ψ
i
=
([ψ
j
]
31
,[ψ
j
]
30
,...,[ψ
j
]
0
)
and ψ
j
=
in HC-128, where 1024τ + 10 ≤ j < i < 1024τ + 511, then the expected
number of matches between the corresponding bits is more than 16, and to
be specific, is approximately 16 +
1
12
2
−79
.
Theorem 10.3.5. For 1024τ + 10 ≤ j < i < 1024τ + 511, the expected
number of bits where the two 32-bit integers ψ
i
and ψ
j
match is approximately
16 +
1
12
2
−79
.
Proof: Let m
b
= 1, if [ψ
i
]
b
= [ψ
j
]
b
; otherwise, let m
b
= 0, 0 ≤ b ≤ 31.
Hence, the total number of matches is given by
31
M =
m
b
.
b=0
From Theorem 10.3.4, we have Prob(m
b
= 1) = r
b
. Hence, E(m
b
) = r
b
and