**The Design Principle of Hash Function with Merkle-Damgård Construction**

*Duo Lei, Da Lin2, Li Chao, Keqin Feng, and Longjiang Qu*

**Abstract: ** The paper discusses the security of
hash function with Merkle-Damgård construction and provides
the complexity bound of finding a collision
and primage of hash function based on the condition probability of
compression function $y=F(x,k)$. we make a conclusion that in
Merkle-Dammaård construction, the requirement of free start
collision resistant and free start collision resistant on
compression function is not necessary and it is enough if the
compression function with properties of fix start collision
resistant and fix start preimage resistant. However, the condition
probability $P_{Y|X=x}(y)$ and $P_{Y|K=k}(y)$ of compression
function $y=F(x,k)$ have much influence on the security of the hash
function. The best design of compression function should have
properties of that $P_{Y|X=x}(y)$ and $P_{Y|K=k}(y)$ are both
uniformly distributed for all $x$ and $k$. At the end of the paper,
we discussed the block cipher based hash function, point out among
the the 20 schemes, selected by PGV\cite{Re:Preneel} and
BPS\cite{Re:JBlack}, the best scheme is block cipher itself, if the
block cipher with perfect security and perfect key distribution.

**Category / Keywords: **secret-key cryptography / Hash functions, Block ciphers, complexity theory

**Date: **received 5 Apr 2006, last revised 11 May 2006

**Contact author: **duoduolei at 163 com

**Available format(s): **PDF | BibTeX Citation

**Note: **The paper has not been submited. The result of the paper is different from traditional understading of compression function of hash function. We expect any comment on the paper.

**Version: **20060512:054103 (All versions of this report)

**Short URL: **ia.cr/2006/135

**Discussion forum: **Show discussion | Start new discussion

[ Cryptology ePrint archive ]