Cryptology ePrint Archive: Report 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.

Category / Keywords: hash functions, provable security

Original Publication (with minor differences): Information Processing Letters
DOI: 10.1016/j.ipl.2014.02.008

Date: received 29 Mar 2009, last revised 3 Mar 2014

Contact author: jlee05 at sejong ac kr

Available format(s): PDF | BibTeX Citation

Version: 20140303:130454 (All versions of this report)

Short URL: ia.cr/2009/145

Discussion forum: Show discussion | Start new discussion