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 $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.

Metadata
Available format(s)
PDF
Publication info
Published elsewhere. Unknown where it was published
Keywords
hash functionindifferentiabilityblockcipherprovable 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
Creative Commons Attribution
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},
      note = {\url{https://eprint.iacr.org/2009/066}},
      url = {https://eprint.iacr.org/2009/066}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.