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.
