An efficient bloom filter based solution for multiparty private matching

Abstract

The issue of privacy becomes more and more important. On the other hand, online collaboration among different parties is almost unavoidable. How to allow collaboration while protecting one's privacy is an important problem and attracted a lot of attention. Unfortunately, most of the problems in this area still remain unsolved. In this paper, we investigate one of the fundamental problems called multiparty private matching in which N users want to compute the set of records that are present in everyone's database without revealing unnecessary information such as records not in others' databases or any intermediate resulting sets. Existing solutions are either inefficient or require a mediator. We propose a bloom-filter based solution, which does not require a trusted third party and is more efficient than all existing solutions. We also show that although bloom filter may return false positive, the probability of getting false positive can be set to very low that could still be useful to a lot of applications.