Private Set Intersection: A Multi-Message Symmetric Private Information Retrieval Perspective

DOI10.1109/TIT.2021.3125006zbMATH Open1495.68050arXiv1912.13501OpenAlexW3210888078MaRDI QIDQ5080042

Karim Banawan, Zhusheng Wang, Sennur Ulukus

Publication date: 30 May 2022

Published in: IEEE Transactions on Information Theory (Search for Journal in Brave)

Abstract: We study the problem of private set intersection (PSI). In this problem, there are two entities $E_i$, for $i=1,2$, each storing a set $mathcal{P}_i$, whose elements are picked from a finite field $mathbb{F}_K$, on $N_i$ replicated and non-colluding databases. It is required to determine the set intersection $mathcal{P}_{1}capmathcal{P}_2$ without leaking any information about the remaining elements to the other entity with the least amount of downloaded bits. 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 derive the information-theoretic sum capacity of MM-SPIR, $C_{MM-SPIR}$. We show that with $K$ messages, $N$ databases, and the size of the desired message set $P$, the exact capacity of MM-SPIR is $C_{MM-SPIR}=1-frac1N$ when $PleqK-1$, provided that the entropy of the common randomness $S$ satisfies $H(S)geqfracPN-1$ per desired symbol. This result implies that there is no gain for MM-SPIR over successive single-message SPIR (SM-SPIR). For the MM-SPIR problem, we present a novel capacity-achieving scheme that builds on the near-optimal scheme of Banawan-Ulukus originally proposed for the multi-message PIR (MM-PIR) problem without database privacy constraints. Surprisingly, our scheme here is exactly optimal for the MM-SPIR problem for any $P$, in contrast to the scheme for the MM-PIR problem, which was proved only to be near-optimal. Our scheme is an alternative to the SM-SPIR scheme of Sun-Jafar. Based on this capacity result for MM-SPIR, and after addressing the added requirements in its conversion to the PSI problem, we show that the optimal download cost for the PSI problem is $minleftleftlceilfrac{P}_1{N}_2{N}_2-1ightceil,leftlceilfrac{P}_2{N}_1{N}_1-1ightceilight$, where $P_i$ is the cardinality of set $mathcal{P}_i$

Full work available at URL: https://arxiv.org/abs/1912.13501

Mathematics Subject Classification ID

Information storage and retrieval of data (68P20) Privacy of data (68P27)

Related Items (1)

Quantum multi-party private set intersection using single photons

This page was built for publication: Private Set Intersection: A Multi-Message Symmetric Private Information Retrieval Perspective