Fuzzy private matching (extended abstract)
conference paper
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. [9] 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. © 2008 IEEE.
TNO Identifier
240954
Source title
3rd International Conference on Availability, Security, and Reliability, ARES 2008, 4 - 7 March 2008, Barcelona, Spain
Pages
327-334
Files
To receive the publication files, please send an e-mail request to TNO Repository.