2
$\begingroup$

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 & a set S where S is the set of all possible hash values resulting from H(M) = (S) & 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 & 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) & 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)

Improve this question
$\endgroup$
2
  • $\begingroup$ This kind of hash function has nothing to do with a cryptographic hash function. A cryptographic hash function is a random oracle which is almost never collision free. $\endgroup$
    – user27950
    Oct 8, 2015 at 17:42
  • $\begingroup$ So aside from brute force there is no possible way to determine if a hash function is collision resistant & the only way is to hash all possible pre-images to see if the hash value are distributed randomly & evenly across the hash value space? $\endgroup$
    – Last
    Oct 8, 2015 at 18:21

2 Answers 2

Reset to default
1
$\begingroup$
  • Must the bit length of the hash value be long enough to cover N number of messages?

Yes.

  • Does it not simply make a perfect hash function as a specified lookup table for a set of predetermined message?

Yes, but it is an efficient lookup table. If you used e.g. binary search for the lookup, you would need space proportional to the concatenation of all the messages/keys in the set. With long keys that is inconvenient. In comparison, a perfect hash function constructed for that set may require only a few bits per key.

Improve this answer
$\endgroup$
3
$\begingroup$

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.

Improve this answer
$\endgroup$
7
  • $\begingroup$ Sorry can you further explain the part where given messages M not in the original set. Here is an example based on my understanding: Hash function: return input % 4; hence effectively i only prepared 4 buckets/hash values. Now lets say a perfect hash function returns a 2 bit hash value (4 factorials). Given a message beyond the intended message space of 4, it will still return a unique hash value? $\endgroup$
    – Last
    Oct 8, 2015 at 18:19
  • $\begingroup$ A perfect hash function isn't really defined for messages not in the set. If you still follow the same algorithm to calculate it for one, you get to keep both pieces if the assumptions break. $\endgroup$
    – otus
    Oct 8, 2015 at 18:38
  • $\begingroup$ Sorry misread, i retract my previous statement, what i meant to ask is for a perfect hash fuction must size of S be equal to size of M to achieve a unique hash value for each corresponding preimage? $\endgroup$
    – Last
    Oct 8, 2015 at 19:48
  • $\begingroup$ "Perfect" means the hash can't assign two pigeons to the same hole, so you need at least as many holes as pigeons. And we knew how many pigeons we had when we designed the hash, so we don't have more holes than pigeons. That is, you can't give me a pigeon that wasn't in the original set and ask me where to put him. As @otus says, the hash is an algorithm, so you can run it on your parrot; but whatever hole it tells you will already have a pigeon in it. $\endgroup$
    – bmm6o
    Oct 9, 2015 at 0:25
  • $\begingroup$ So its kind of like assigning a key to each possible message? $\endgroup$
    – Last
    Oct 9, 2015 at 2:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.