Cryptography, Security and Privacy
Private Information Retrieval I

Private Set Intersection Using Multi-Message Symmetric Private Information Retrieval

Zhusheng Wang, Karim Banawan, Sennur Ulukus

Date & Time

01:00 am – 01:00 am


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

Session Chair

Anand Sarwate

Rutgers, The State University of New Jersey