Cryptography Reference
In-Depth Information
Proof: We have s
u
= h
1
(P[u⊟ 12])⊕P[u] and s
v
= h
1
(P[v ⊟ 12])⊕P[v].
Thus,
s
u
⊕s
v
=
h
1
(P[u ⊟ 12])⊕h
1
(P[v ⊟ 12])
⊕(P[u]⊕P[v]).
The term
h
1
(P[u ⊟ 12]) ⊕h
1
(P[v ⊟ 12])
vanishes if and only if s
u
⊕s
v
=
P[u]⊕P[v].
Assume that the array P from which the input to the function h
1
is selected
and the array Q from which the output of h
1
is chosen contain uniformly
distributed 32-bit elements. The notations h and U are used in Lemma 10.4.2,
which is in a more general setting than just HC-128; these may be considered
to model h
1
and Q respectively for HC-128.
Lemma 10.4.2. Let h(x) = U[x
(0)
] + U[x
(2)
+ 2
m
] be an n-bit to n-bit map-
ping, where each entry of the array U is an n-bit number, U contains 2
m+1
many elements and x
(0)
and x
(2)
are two disjoint m-bit segments from the n-
bit input x. Suppose x and x
′
are two n-bit random inputs to h. Assume that
the entries of U are distributed uniformly at random. Then for any collection
of t distinct bit positions {b
1
,b
2
,...,b
t
}⊆{0,1,...,n−1}, 0 ≤t ≤ n,
t
[h(x)]
b
l
= [h(x
′
)]
b
l
Prob
= γ
m,t
l=0
where γ
m,t
= 2
−2m
+ (1−2
−2m
)2
−t
.
Proof: Each value v ∈ [0,2
n
−1] can be expressed as the modulo 2
n
sum
of two integers a,b ∈ [0,2
n
− 1] in exactly 2
n
ways, since for each choice of
a ∈ [0,2
n
− 1], the choice of b is fixed as b = (v − a) mod 2
n
. It is given
that each U[α] is uniformly distributed over [0,2
n
− 1]. Thus, for uniformly
random α,β ∈ [0,2
m+1
− 1], the sum (U[α] + U[β]) mod 2
n
is also uniformly
distributed and so is any collection of t bits of the sum.
Now, h(x) = U[x
(0)
] + U[x
(2)
+ 2
m
] and h(x
′
) = U[x
′(0)
] + U[x
′(2)
+ 2
m
]
can be equal in bit positions b
1
,b
2
,...,b
t
in the following two ways.
Case I: x
(0)
= x
′(0)
and x
(2)
= x
′(2)
. This happens with probability 2
−m
2
−m
.
Case II: The event “x
(0)
= x
′(0)
and x
(2)
= x
′(2)
” does not happen and still
U[x
(0)
] + U[x
(2)
+ 2
m
]
U[x
′(0)
] + U[x
′(2)
+ 2
m
]
match in the t
bits due to random association. This happens with probability (1 −
2
−2m
)2
−t
.
and
Adding the two components, we get the result.
γ
m,t
depends only on m,t and not on n, as is expected from the particular
form of h
1
(.) that uses only 2m bits from its n-bit random input. For HC-128,
we have n = 32 and m = 8. For the equality of the whole output word of
h
1
(.), one needs to set t = n = 32. Thus, Prob(h
1
(x) = h
1
(x
′
)) = γ
8,32
=
