Provably Secure Fair Mutual Private Set Intersection Cardinality Utilizing Bloom Filter

Abstract

The availability of electronic information is necessary in our everyday life. Progressively, often, data needs to be shared among the unreliable entities. In this field, one interesting and common problem occurs when two parties want to secretly determine the intersection or cardinality of intersection of their respective private sets. PSI or its variants are ideal to solve the aforementioned problems. Existing solutions of $\mathsf{mPSI}$ and $\mathsf{mPSI}$-CA mainly use trusted third party to achieve fairness. However, in real life, the unconditional trust is fraught with security risks as the trusted third party may be unfaithful or corrupted. As a consequence, construction of an efficient $\mathsf{mPSI}$-CA preserving fairness remains a challenging problem. In this paper, we address this issue by employing an off-line third party, called arbiter, who is assumed to be semi-trusted in the sense that he does not have access to the private information of the entities while he will follow the protocol honestly. In this work, we design a construction of fair and efficient $\mathsf{mPSI}$-CA utilizing Bloom filter. Our $\mathsf{mPSI}$-CA is proven to be secure in the random oracle model (ROM) and achieves linear communication and computation overheads. A concrete security analysis is provided in malicious environments under the Decisional Diffie-Hellman (DDH) assumption.