1
$\begingroup$

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:

  1. 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?

  2. 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:

  1. 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.
Improve this question
$\endgroup$
2
  • $\begingroup$ Do you have a reference? Perfect hash functions in computer science, as normally studied, have nothing to do with cryptography and don't promise to provide any privacy or any other security properties. $\endgroup$
    – D.W.
    Sep 17, 2014 at 4:18
  • $\begingroup$ I know that phfs have not been studied for privacy. But since they are somehow based on hash functions, I was wondering what information the index can leak. $\endgroup$
    – pAkY88
    Sep 17, 2014 at 7:37

1 Answer 1

Reset to default
6
$\begingroup$

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?

Improve this answer
$\endgroup$
5
  • $\begingroup$ Hi Guut Boy, I think you definitely got the point. Actually I had the same intuition: it depends on the hash function(s) used to build the (M)PHF. In particular I'm looking at this method homepages.dcc.ufmg.br/~nivio/papers/cikm07.pdf which makes use of linear hash functions over Galois field 2. What can you say about the properties of this family of hash functions? $\endgroup$
    – pAkY88
    Sep 17, 2014 at 8:52
  • $\begingroup$ Well, I haven't read the paper, just the abstract so I can not say much. I don't know very much about perfect hash functions either apart from the definition. One thing that caught my eye is that they say that the function is only perfect for sets in the billion of values. That may not be enough. If the server knows x is in a set of only a few billion it could probably find x with brute force. $\endgroup$
    – Guut Boy
    Sep 17, 2014 at 9:08
  • $\begingroup$ Again, I should say, perfect hash functions are not meant to provide security, so I am a little confused why you would want to use them in the first place. You should ask your self if there is really any property of perfect hash functions that are desirable for this application? It is not clear to me that that is the case. $\endgroup$
    – Guut Boy
    Sep 17, 2014 at 9:12
  • $\begingroup$ The goal is to allow the user to check whether an item $x$ is in a set $S$ of size $n$. If the item is in the set, then privacy is not needed. On the other hand, if the item is NOT in the set, we do NOT want to disclose the item to the server. That's why I though of phfs. If the domain size of $x$ is much much larger than $n$, there will be a huge number of elements $x'$ that are not in $S$ and are mapped to the same index $i$ ($H(x') = i$). Therefore (not sure), given $i$, the server may not be able to say much about $x$, so $i$ would not leak much. $\endgroup$
    – pAkY88
    Sep 17, 2014 at 9:56
  • 3
    $\begingroup$ Still it is not clear how you are using the properties of a phf. Like I said above, I think what you need is a collision resistant hash function, not a perfect hash function. With a collision resistant hash function there may be collisions, but the user will never be able to find one (roughly speaking). $\endgroup$
    – Guut Boy
    Sep 17, 2014 at 10:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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