Welcome to the resource topic for 2024/1712
Title:
Low-Communication Updatable PSI from Asymmetric PSI and PSU
Authors: Guowei Ling, Peng Tang, Weidong Qiu
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{GitHub - ShallMate/upsi}{GitHub - ShallMate/upsi}.
ePrint: https://eprint.iacr.org/2024/1712
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .