Domain Extension of Public Random Functions: Beyond the Birthday Barrier

A

public

random function is a random function that is accessible by all parties, including the adversary. For example, a (public) random oracle is a public random function {0,1}

*

→{0,1}

n

. The natural problem of constructing a public random oracle from a public random function {0,1}

m

→{0,1}

n

(for some

m

 > 

n

) was first considered at Crypto 2005 by Coron et al. who proved the security of variants of the Merkle-Damgård construction against adversaries issuing up to

O

(2

n

/2

) queries to the construction and to the underlying compression function. This bound is less than the square root of

n

2

m

, the number of random bits contained in the underlying random function.

In this paper, we investigate domain extenders for public random functions approaching optimal security. In particular, for all

ε

 ∈ (0,1) and all functions

m

and ℓ (polynomial in

n

), we provide a construction

C

ε

,

m

,ℓ

(·) which extends a public random function

R

: {0,1}

n

→{0,1}

n

to a function

${\bf C}_{\epsilon,m,\ell}({\bf R}): \{0,1\}^{m(n)} \rightarrow \{0,1\}^{\ell(n)}$

with time-complexity polynomial in

n

and 1/

ε

and which is secure against adversaries which make up to

Θ

(2

n

(1 − 

ε

)

) queries. A central tool for achieving high security are special classes of unbalanced bipartite expander graphs with small degree. The achievability of practical (as opposed to complexity-theoretic) efficiency is proved by a non-constructive existence proof.

Combined with the iterated constructions of Coron et al., our result leads to the first iterated construction of a hash function {0,1}

*

→{0,1}

n

from a component function {0,1}

n

→{0,1}

n

that withstands all recently proposed generic attacks against iterated hash functions, like Joux’s multi-collision attack, Kelsey and Schneier’s second-preimage attack, and Kelsey and Kohno’s herding attacks.