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
Search WWH ::




Custom Search