If the Ideal random compression functions C is always chosen and kept as a surjective function namely a onto mapping,what about the conclusion?

The writer of 2010/384 gives a conclusion that a narrow-pipe hash function will lose the entropy and the codomain will Reduce.However,the ideal random compression function C is designated by the writer as non-surjective function,if an ideal random compression functions C can always be a surjective function,are those inferences( on narrow-pipe hash functions ) still real?

A new text 2010/652 can thwart the conclusions on narrow-pipe hash functions.



Edited 1 time(s). Last edit at 30-Dec-2010 10:50 by wai2ha.

One of the key questions is that processing the last block with additional bits in a normal iterative hash function,there's the entropy of CV_(L-1) only n bits,namely a n-bit domain X maps to a n-bit codomain Y,the probability of empty set is approximately
e^(-1).

We can always only use one surjection round in the last iteration to recovere the domain $X$ by a sum block $ÓM_(L-1)$(assume the message was L- blocks),whenever the previous reductions were great or not.For the last iteration of a narrow-pipe hash function,the active domain $X$ is at least 2^2n ,then it's the case that the ideal random functions W map the
domain of (n+w)-bit strings $X = {0,1}^(n+w )$ to the domain $Y = {0,1}^n$ ,the probability of empty set is about $e^(-2^w)$,where $w>2n-n=n$.
So,a narrow pipe hash function can easily be amend by a sum block $ÓM_(L-1)$,and the same question in MAC can also be done.I'll expound on 2010/652 before toolong.