0
$\begingroup$

About collision-resistant hash functions, in Katz's Introduction to Modern Cryptography,

6.1 Definitions

Hash functions are simply functions that take inputs of some length and compress them into short, fixed-length outputs. The classic use of (non- cryptographic) hash functions is in data structures, where they can be used to build hash tables that enable O(1) lookup time when storing a set of elements. Specifically, if the range of the hash function H is of size N, then element x is stored in row H(x) of a table of size N. To retrieve x, it suffices to compute H(x) and probe that row of the table for the elements stored there. A good hash function for this purpose is one that yields few collisions, where a collision is a pair of distinct elements x and x0 for which H(x) = H(x0); in this case we also say that x and x0 collide. (When a collision occurs, two elements end up being stored in the same cell, increasing the lookup time.)

Collision-resistant hash functions are similar in spirit; again, the goal is to avoid collisions. However, there are fundamental differences. For one, the desire to minimize collisions in the setting of data structures becomes a requirement to avoid collisions in the setting of cryptography. Furthermore, in the context of data structures we assume that the set of elements being hashed is chosen independently of H and without any intention to cause collisions. In the context of cryptography, in contrast, we are faced with an adversary who may select elements with the explicit goal of causing collisions. This means that collision-resistant hash functions are much harder to design.

About the concept of perfect hashing, in CLRS' Introduction to Algorithms:

11.5 Perfect hashing

We call a hashing technique perfect hashing if O(1) memory accesses are required to perform a search in the worst case.

To create a perfect hashing scheme, we use two levels of hashing, with universal hashing at each level. The first level is essentially the same as for hashing with chaining: we hash the n keys into m slots using a hash function h carefully selected from a family of universal hash functions. Instead of making a linked list of the keys hashing to slot j , however, we use a small secondary hash table S j with an associated hash function h j . By choosing the hash functions h j carefully, we can guarantee that there are no collisions at the secondary level.

and in https://en.wikipedia.org/wiki/Perfect_hash_function

In computer science, a perfect hash function h for a set S is a hash function that maps distinct elements in S to a set of m integers, with no collisions. In mathematical terms, it is an injective function.

Is it correct that in Katz's book, a collision-resistant hash function means exactly a collision-free hash function? (I think so.)

Is a perfect hash function in Wikipedia the same as a collision-resistant hash function in Katz's book? (I think so.)

Is a perfect hash function in CLRS' book the same as a collision-resistant hash function in Katz's book? (CLRS defines a perfect hash function in terms of the complexity of memory access being O(1), and implements a perfect hash function as a collision-resistant hash function, so I think that a collision-resistant hash function is also a perfect hash function, but am not sure if a perfect hash function is necessarily collision-resistant.)

Is a perfect hash function in CLRS' book the same as a perfect hash function in Wikipedia?

Thanks.

$\endgroup$
1

1 Answer 1

3
$\begingroup$

Is it correct that in Katz's book, a collision-resistant hash function means exactly a collision-free hash function?

No. There are two different concepts at play here. A cryptographic hash function provides guarantees such as collision-resistance, but hash functions used in data structures are not cryptographic hash functions. For algorithms we really just want a nice efficient way to map some input into a memory location/integer/etc.

Cryptographic hash functions map arbitrary sized inputs to a fixed finite output space, so in fact, there will be infinite collisions. It is just computationally infeasible to find one.

In mathematical terms, it is an injective function.

Hash functions in cryptography are not injective because, as mentioned above, the output space is much smaller than the input space. So they're certainly not the same as perfect hash functions.

Is a perfect hash function in CLRS' book the same as a perfect hash function in Wikipedia?

Yes, in both these cases, the hash functions are collision-free (no collisions exist).

$\endgroup$

Your Answer

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

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