# Technical Program

## Paper Detail

 Paper ID P.8.5 Paper Title Private Set Intersection Using Multi-Message Symmetric Private Information Retrieval Authors Zhusheng Wang, University of Maryland, United States; Karim Banawan, Alexandria University, Egypt; Sennur Ulukus, University of Maryland, United States Session P.8: Private Information Retrieval I Presentation Lecture Track Cryptography, Security and Privacy Manuscript Click here to download the manuscript Virtual Presentation Click here to watch in the Virtual Symposium Abstract 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$.