on Information Theory

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

Plan Ahead

2021 IEEE International Symposium on Information Theory

**11-16 July 2021 ** | **Melbourne, Victoria, Australia**