Technical Program

Paper Detail

Paper IDP.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$.

Plan Ahead


2021 IEEE International Symposium on Information Theory

11-16 July 2021 | Melbourne, Victoria, Australia

Visit Website!