We study the problem of private set intersection (PSI). In PSI, there are two entities, each storing a set $\mathcal{P}_i$, whose elements are picked from a finite set $\mathbb{S}_K$, on $N_i$ replicated and non-colluding databases. It is required to determine the set intersection $\cp_1 \cap \cp_2$ without 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 $C_{MM-SPIR} = 1 - \frac{1}{N}$ when $P \leq K-1$, if the common randomness $S$ satisfies $H(S) \geq \frac{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\left\{\left\lceil\frac{P_1 N_2}{N_2-1}\right\rceil, \left\lceil\frac{P_2 N_1}{N_1-1}\right\rceil\right\}$, where $P_i$ is the cardinality of the set $\cp_i$.


Zhusheng Wang

University of Maryland

Karim Banawan

Alexandria University

Sennur Ulukus

University of Maryland
Private Conversation

Reach out to the speaker privately

Questions & Answers

Post a publicly available question

No questions have been asked.

Session Chair

Anand Sarwate

Rutgers, The State University of New Jersey