Cryptology ePrint Archive: Report 2009/066

Adaptive Preimage Resistance and Permutation-based Hash Functions

Jooyoung Lee and Je Hong Park

Abstract: In this paper, we introduce a new notion of security, called \emph{adaptive preimage resistance}. We prove that a compression function that is collision resistant and adaptive preimage resistant can be combined with a public random function to yield a hash function that is indifferentiable from a random oracle. Specifically, we analyze adaptive preimage resistance of $2n$-bit to $n$-bit compression functions that use three calls to $n$-bit public random permutations. This analysis also provides a simpler proof of their collision resistance and preimage resistance than the one provided by Rogaway and Steinberger. By using such compression functions as building blocks, we obtain permutation-based pseudorandom oracles that outperform the Sponge construction and the MD6 compression function both in terms of security and efficiency.

Category / Keywords: hash function, indifferentiability, blockcipher, provable security

Date: received 9 Feb 2009, last revised 21 May 2009

Contact author: jlee05 at ensec re kr

Available format(s): PDF | BibTeX Citation

Version: 20090522:050612 (All versions of this report)

Short URL: ia.cr/2009/066

Discussion forum: Show discussion | Start new discussion