Fuzzy Private Matching (Extended Abstract)

In the private matching problem, a client and a server each hold a set of n input elements. The client wants to privately compute the intersection of these two sets: he learns which elements he has in common with the server (and nothing more), while the server gains no information at all. In certain applications it would be useful to have a fuzzy private matching protocol that reports a match even if two elements are only similar instead of equal. We consider this fuzzy private matching problem, in a semi-honest environment. First we show that the original solution proposed by Freedman et al. is incorrect. Subsequently we present two fuzzy private matching protocols. The first, simple, protocol has a large bit message complexity. The second protocol improves this, but here the client incurs a $O(n)$ factor time complexity.