0
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ My case is similar to what you've mentioned with a small difference. The server may use any mapping to map different $f_i$s to different positions and then send some information to the user to construct a similar mapping. The user can find his file's position on the new map, and this value will be a row number to be used to query a database. $\endgroup$ – mahdi Jul 27 '20 at 7:38
  • $\begingroup$ Why only sending $k$ couldn't help the user to find the file's position? If the user knows $k$, he can simply hash with $H$ and the use $k$-bit prefix to find the location. $\endgroup$ – mahdi Jul 27 '20 at 7:43
  • $\begingroup$ The reason I need perfect hash functions is that I want to prevent collisions with the smallest hash size. To prevent collisions using cryptographic hash functions, you need a big hash size which is not suitable for my use case. $\endgroup$ – mahdi Jul 27 '20 at 7:48
  • $\begingroup$ @mahdi You don't send $k$, you send the first $k$ bits of each hash. And as I show in my answer you cannot do better, asymptotically, with the above requirements. The data sent by the server must contain the full information of the permutation since the user could have any of the files. If you want to save bits you have to allow more back and forth communication. $\endgroup$ – orlp Jul 27 '20 at 11:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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