Private Set Intersection Using Multi-Message Symmetric Private Information Retrieval
Zhusheng Wang, Karim Banawan, Şennur Ulukuş · 2020
We study the problem of private set intersection (PSI). In PSI, there are two entities, each storing a set Pi, whose elements are picked from a finite set SK, on Nireplicated and non-colluding databases. It is required to determine the set intersection P1∩P2without leaking any information about the remaining elements to the other entity. We first show that the PSI problem can be recast as a multi-message symmetric private information retrieval (MM-SPIR) problem. Next, as a stand-alone result, we show that the exact capacity of MM-SPIR is CMM-SPIR= 1 - 1/N when P ≤ K - 1, if the common randomness S satisfies H(S) ≥ P/N-1 per desired symbol. This result implies that there is no gain for MM-SPIR over successive single-message SPIR. We present a novel capacity-achieving scheme which builds seamlessly over the multi-message PIR (MM-PIR) scheme. Based on this capacity result for the MM-SPIR problem, we show that the optimal download cost for the PSI problem is given by min{[P1N2/N2-1],[P2N1/N1-1]}, where P i is the cardinality of the set Pi.