I'm digging into the several algorithms for building (Minimal) Perfect Hash Functions. It seems that the recent works provide quite a few very efficient algorithms.
However, I'm wondering how a (M)PHF behaves in case of unsuccessful searches and what level of privacy can guarantee:
What happens if a user computes the hash function over a key which wasn't in the key set used for the creation of the hash function? What result will be returned?
The user wants to run a membership test of $x$ over a set $S$ in a privacy-preserving way. He computes the hash of $x$: $H(x) = i$, and then asks the server to return the key in position $i$. Let's suppose $x$ is not in the key set, did the user leak anything about $x$? What information could the server obtain knowing that the user asked for a key in position $i$?
- Is there any perfect hash function which allows membership tests? Given the phf $H$, a user $U$ would like to test whether $x$ is in the key set.