On the privacy of perfect hash functions 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$?


EDIT:


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.
The definition of perfect hash functions do not have any security/cryptographic requirements. For example, the hash function that simply outputs the first n bits of any string is a perfect hash function on the set of n bit strings. Obviously this function does not hide the input at all. 

So the answer to your questions is that it depends on the hash function. It being a perfect hash function alone (minimal or otherwise) does not guarantee any privacy at all. Neither does it say anything about what happens outside of the set for which the function is perfect. That means if the users hashes a value outside of this set it may well result in a collision with value in the set. Such a collision is easy to construct for the hash function I mention above.

On the other hand, if the reason you want to use a perfect hash function is that there are no collisions, you might as well use a cryptographic, collision resistant hash function instead. In this case there is basically no way for user to find a value outside of the set that collides with one in the set. 

If using a collision resistant hash function in your protocol is enough for secure private set-intersection is a more complicated question. It essentially depends on your security assumptions and the flavor of PSI you want: Is the server malicious? Is the client? Should both parties learn if there is an intersection or not?