Bits needed to send parameters of perfect hash functions

Question

Suppose that there is a server that has $n$ files. The server is used to construct a perfect hash function for those files and then the computed parameters will be sent to a user. These parameters will be used by the user to compute the hash of a certain file in order to find its position between files on the main server. The question is that how many bits are needed to be transmitted between the server and the user? Is that in order of $O(n)$? Can anybody suggest a specific algorithm with its parameters and communication cost?

Answer 1

If I understand you correctly, the following is the case:

1. The server has $n$ files in some order $f_1, f_2, \dots, f_n$.
2. The user also has exactly one of those files, $f_u$, but does not know $u$.
3. The user and server agree on some protocol beforehand, which does not depend on any of the $f$.
4. The server gets to communicate some bits of information to the user once, and only in this direction.
5. From this information the user must be able to find integer $k$ such that $f_k = f_u$.

---

Based on the above I would choose some strong cryptographic hashing function $H$, and use it to hash all files on the server. Take the $k$-bit prefix of this hash such that all prefixes are unique. Send these in the correct order for $O(kn)$ total complexity.

How big does $k$ need to be in practice? The chance that the first hash is not a duplicate is $1$, the second $1- \frac{1}{2^k}$ chance, the third $1- \frac{2}{2^k}$, etc. We find that none are duplicates as $\prod_{i=0}^{n-1} (1 - i/2^k) \approx e^{-n^2/2^{k+1}}$ by the Birthday paradox. Let's say we're okay with constant chance of failure $\epsilon$, and thus we want $e^{-n^2/2^{k+1}} > 1-\epsilon$, which gives $k \in O(\log(n))$.

Thus our solution uses $O(n \log n)$ bits. You can't beat this (asymptotically) either, because a full permutation worth of information needs to be transferred, which takes $O(\log n!) = O(n \log n)$ bits.