Paper 2004/328

Security Analysis of a 2/3-rate Double Length Compression Function in Black-Box Model

Mridul Nandi, Wonil Lee, Kouichi Sakurai, and Sangjin Lee

Abstract

In this paper, we propose a $2/3$-rate double length compression function and study its security in black-box model. We prove that to get a collision attack for the compression function requires $\mathrm{\Omega }(2^{2n/3})$ queries, where $n$ is the single length output size. Thus, it has better security than a most secure single length compression function. This construction is more efficient than the construction given in~\cite{Hirose04}. Also the three computations of underlying compression functions can be done in parallel. The proof idea uses a concept of computable message which can be helpful to study security of other constructions like ~\cite{Hirose04},~\cite{Lucks04},~\cite{Nandi04} etc.