Paper 2009/145

Security of Permutation-based Compression Function lp 231

Jooyoung Lee and Daesung Kwon

Abstract

In this paper, we study security of a certain class of permutation-based compression functions. Denoted lp 231 by Rogaway and Steinberger, they are 2n-to-n-bit compression functions using three calls to a single $n$-bit random permutation. We prove that lp 231 is asymptotically preimage resistant up to 2^{2n/3}/n query complexity and collision resistant up to 2^{n/2}/n^{1+e} query complexity for any e>0. Based on a single permutation, lp 231 provides both efficiency and almost optimal collision security.

Metadata
Available format(s)
PDF
Publication info
Published elsewhere. Minor revision. Information Processing Letters
DOI
10.1016/j.ipl.2014.02.008
Keywords
hash functionsprovable security
Contact author(s)
jlee05 @ sejong ac kr
History
2014-03-03: last of 2 revisions
2009-03-31: received
See all versions
Short URL
https://ia.cr/2009/145
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2009/145,
      author = {Jooyoung Lee and Daesung Kwon},
      title = {Security of Permutation-based Compression Function lp 231},
      howpublished = {Cryptology ePrint Archive, Paper 2009/145},
      year = {2009},
      doi = {10.1016/j.ipl.2014.02.008},
      note = {\url{https://eprint.iacr.org/2009/145}},
      url = {https://eprint.iacr.org/2009/145}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.