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-Damgard 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 ε ∈ (0,1) and all functions m and e (polynomial in n), we provide a construction C_(ε,m,e)(·) which extends a public random function R : {0, 1}~n → {0,1}~n to a function C_(ε,m,e)(R) : {0, 1}~(m(n)) → {0,1}~e(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.