Adaptive Preimage Resistance and Permutation-based Hash Functions

Jooyoung Lee; Je Hong Park

Paper 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 $2 n$ -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.

Metadata

Available format(s): PDF
Publication info: Published elsewhere. Unknown where it was published
Keywords: hash function indifferentiability blockcipher provable security
Contact author(s): jlee05 @ ensec re kr
History: 2009-05-22: last of 4 revisions; 2009-02-10: received; See all versions
Short URL: https://ia.cr/2009/066
License: CC BY

BibTeX

@misc{cryptoeprint:2009/066,
      author = {Jooyoung Lee and Je Hong Park},
      title = {Adaptive Preimage Resistance and Permutation-based Hash Functions},
      howpublished = {Cryptology {ePrint} Archive, Paper 2009/066},
      year = {2009},
      url = {https://eprint.iacr.org/2009/066}
}