Dedicated Conventional Cryptographic Primitives - A Classical Introduction to Cryptography: Applications for Communications Security - page 86

q ( q − 1)

We have at most terms in I . Hence

2

q ( q − 1)

Pr[Coll] ≤ max

{ ( i , j ) , ( r , s ) }∈ I

Pr[MinColl i , j , r , s ] .

2

(We need this inequality because it is easier to upper bound the probability of a nontrivial
collision when we know that there is no sub-nontrivial collisions.)

For { ( i , j ) , ( r , s ) }∈ I , let us consider the MinColl i , j , r , s event. We assume without

loss of generality that s ≤ j . Since we have no previous collision we must have m i , j =

m r , s . We cannot have j = 1 (otherwise s = j = 1, but C ( m i , 1 ) = C ( m r , 1 ) is either

trivial or impossible). Thus j > 1 and the event is

C ( U i , j − 1 ) ⊕ m i , j = U r , s .

( i , j ) ( i , j )

If we have a collision U i , j − 1 = U i , j with ( i , j − 1) = and ∈

c ( { ( i , j ) , ( r , s ) } ), it must be trivial (otherwise the U i , j = U r , s collision is not mini-

mal) which means j = 1, i =

j − r , and m i , 1 || ... || m i , j − 1 = m r , 1 || ... || m r , j − 1 .If

s U i , s which is nontrivial, which

contradicts the minimality of the initial collision. Thus we must have s

< j we have U i , j = U r , s and U r , s = U i , s thus U i , j =

=

j , but the

trivial collision U i , j − 1 = U r , j − 1 make a nontrivial collision U i , j =

U r , s impossible.

Therefore U i , j − 1 is equal to no U i , j for ( i , j ) ∈ c ( i , j , r , s ) \ { ( i , j − 1) } .

This implies that the marginal distribution of C ( U i , j − 1 ) with the knowledge of
all previous U i , j and their C -images is uniform among a set of at least N − q + 1

1

elements. Hence Pr[MinColl i , j , r , s ] ≤

N − q . Finally,

q q ( q − 1) 1 q ( q + 1) 1

Pr( E ) ≤

q +

×

q =

×

N − 2 N − 2 N − q

3.4.5 MAC from Stream Ciphers

Traditional hash functions must have improbable collisions. A traditional way to study
regular hash functions in computer science is to consider the function as a random
variable: we do not have a fixed hash function, but a family of hash functions, and
we pick one at random. Hence we must consider the probability that H ( x )

H ( y )
for any different x and y , over the distribution of H . Following Carter and Wegman in
Ref. [42], we say that a random hash function H is

=

ε -universal if for any x = y we have

Pr[ H ( x ) = H ( y )] ≤ ε.