# Information Security and Cryptography Research Group

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

### Ueli Maurer and Stefano Tessaro

Advances in Cryptology — CRYPTO 2007, Lecture Notes in Computer Science, Springer-Verlag, vol. 4622, pp. 187–204, Aug 2007, Full version available from http://eprint.iacr.org/2007/229.

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}(\mathbf{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.

## BibTeX Citation

@inproceedings{MauTes07,
author       = {Ueli Maurer and Stefano Tessaro},
title        = {Domain Extension of Public Random Functions: Beyond the Birthday Barrier},
editor       = {Alfred Menezes},
booktitle    = {Advances in Cryptology --- CRYPTO 2007},
pages        = {187--204},
series       = {Lecture Notes in Computer Science},
volume       = {4622},
year         = {2007},
month        = {8},
note         = {Full version available from http://eprint.iacr.org/2007/229},
publisher    = {Springer-Verlag},
}