Security of Permutation-based Compression Function lp 231

Jooyoung Lee; Daesung Kwon

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 functions provable 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: 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},
      url = {https://eprint.iacr.org/2009/145}
}