Paper 2024/1712

Low-Communication Updatable PSI from Asymmetric PSI and PSU

Abstract

Private Set Intersection (PSI) allows two mutually untrusted parties to compute the intersection of their private sets without revealing additional information. In general, PSI operates in a static setting, where the computation is performed only once on the input sets of both parties. Badrinarayanan et al. (\textit{PoPETs} 2022) initiated the study of Updatable PSI (UPSI), which extends this capability to dynamically updating sets, enabling both parties to securely compute the intersection as their sets are modified while incurring significantly less overhead than re-executing a conventional PSI. However, existing UPSI protocols either do not support arbitrary deletion of elements or incur high computational and communication overhead. In this work, we combine asymmetric PSI with Private Set Union (PSU) to present a novel UPSI protocol. Our UPSI protocol supports arbitrary additions and deletions of elements, offering a flexible approach to update sets. Furthermore, our protocol enjoys extremely low communication overhead, scaling linearly with the size of the update set while remaining independent of the total set size. We implement our protocol and compare it against state-of-the-art conventional PSI and UPSI protocols. Experimental results demonstrate that our UPSI protocol incurs $587$ to $755$ times less communication overhead than the recently proposed UPSI protocol (\textit{AsiaCrypt} 2024) that supports arbitrary additions and deletions. Moreover, our UPSI protocol has a significant advantage in low-bandwidth environments due to the exceptionally low communication overhead. Specifically, with an input size of $2^{22}$ and the size of the addition/deletion set being $2^{10}$, the existing UPSI protocol requires approximately $1650.45$, $1789.5$, and $3458.1$ seconds at bandwidths of $200$ Mbps, $50$ Mbps, and $5$ Mbps, respectively, whereas our UPSI protocol only requires around $13.01$, $13.75$, and $22.53$ seconds under the same conditions. Our open-source implementation is available at: \href{https://github.com/ShallMate/upsi}{https://github.com/ShallMate/upsi}.