**Domain Extension of Public Random Functions: Beyond the Birthday Barrier**

*Ueli Maurer and Stefano Tessaro*

**Abstract: **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\}^{*} \to \{0,1\}^n$. The
natural problem of constructing a public random oracle from a public
random function $\{0,1\}^{m} \to \{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 $n2^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
$\epsilon \in (0,1)$ and all functions $m$ and $\ell$ (polynomial in
$n$), we provide a construction $\mathbf{C}_{\epsilon,m,\ell}(\cdot)$
which extends a public random function $\mathbf{R}: \{0,1\}^{n} \to
\{0,1\}^n$ to a function $\mathbf{C}_{\epsilon,m,\ell}(\R):
\{0,1\}^{m(n)} \to \{0,1\}^{\ell(n)}$ with time-complexity polynomial
in $n$ and $1/\epsilon$ and which is secure against adversaries which
make up to $\Theta(2^{n(1-\epsilon)})$ 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\}^{*} \to \{0,1\}^n$ from a component
function $\{0,1\}^{n} \to \{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.

**Category / Keywords: **Hash Functions, Domain Extension, Indifferentiability, Birthday Barrier

**Publication Info: **Appears at CRYPTO 2007. This is the full version.

**Date: **received 12 Jun 2007

**Contact author: **tessaros at inf ethz ch

**Available format(s): **Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation

**Version: **20070619:194820 (All versions of this report)

**Short URL: **ia.cr/2007/229

[ Cryptology ePrint archive ]