Paper 2007/229

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.

Metadata
Available format(s)
PDF PS
Publication info
Published elsewhere. Appears at CRYPTO 2007. This is the full version.
Keywords
Hash FunctionsDomain ExtensionIndifferentiabilityBirthday Barrier
Contact author(s)
tessaros @ inf ethz ch
History
2007-06-19: received
Short URL
https://ia.cr/2007/229
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2007/229,
      author = {Ueli Maurer and Stefano Tessaro},
      title = {Domain Extension of Public Random Functions: Beyond the Birthday Barrier},
      howpublished = {Cryptology ePrint Archive, Paper 2007/229},
      year = {2007},
      note = {\url{https://eprint.iacr.org/2007/229}},
      url = {https://eprint.iacr.org/2007/229}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.