How does a perfect hash function work? According to wikipedia, a perfect hash function is a hash function that uses algorithms that has a certain random aspect to their logic. It is suppose to be collision-free.

However due to the pigeon hole principle where given a set of all possible preimages M &amp; a set S where S is the set of all possible hash values resulting from H(M) = (S) &amp; set M is bigger than set S. How does a perfect hash function have collision-resistant in this case?



Based on the answer given by poncho the pre-images are known beforehand &amp; thus the hash function is structured in such a way that there exist a unique hash value for each message. However my confusion exist is that given a message space where each message is for example at least (4 bits long = 16 possibilities) &amp; the hash value is return as (2 bits long = 4 possibilities) value. How can this still possibly be collision-resistant?

Summary, in a perfect hash function:


Must the bit length of the hash value be long enough to cover N number of messages?
Does it not simply make a perfect hash function as a specified lookup table for a set of predetermined message?


Another side question is in the wikipedia page there is a mention of a minimal perfect hash function. Is a hash function that distributes the hash value uniformly across S (Where S is the set containing all possible Hash value resulting from message space M)
How does a perfect hash function have collision-resistant in this case?


Well, when we select a perfect hash function, we take as inputs a set of messages $M_1, M_2, M_3, ..., M_n$, and use them to select a hash function for which $H(M_i) \ne H(M_j)$ (if $i \ne j$)

Now, according to the pigeon hole principle, the output of $H$ must be at least $\log_2 n$ bits long; as $n$ is typically not that huge, that is not a practical problem.

Now, there may be messages $M$ not in the original set for which $H(M) = H(M_i)$ for some $i$; that's ok, as the collision freeness of the perfect hashing function is defined only for the original set of messages, not any additional messages.

And, as cryptostatis has mentioned, we don't have much use for perfect hashing functions in cryptography.  We do use collision resistant hash functions; however by that, we mean that while collisions $H(M) = H(M')$ do exist, it is difficult to find them.