Paper 2024/1446

Updatable Private Set Intersection Revisited: Extended Functionalities, Deletion, and Worst-Case Complexity

Saikrishna Badrinarayanan, LinkedIn (United States)
Peihan Miao, Brown University
Xinyi Shi, Brown University
Max Tromanhauser, Brown University
Ruida Zeng, Brown University
Abstract

Private set intersection (PSI) allows two mutually distrusting parties each holding a private set of elements, to learn the intersection of their sets without revealing anything beyond the intersection. Recent work (Badrinarayanan et al., PoPETS'22) initiates the study of updatable PSI (UPSI), which allows the two parties to compute PSI on a regular basis with sets that constantly get updated, where both the computation and communication complexity only grow with the size of the small updates and not the large entire sets. However, there are several limitations of their presented protocols. First, they can only be used to compute the plain PSI functionality and do not support extended functionalities such as PSI-Cardinality and PSI-Sum. Second, they only allow parties to add new elements to their existing set and do not support arbitrary deletion of elements. Finally, their addition-only protocols either require both parties to learn the output or only achieve low complexity in an amortized sense and incur linear worst-case complexity. In this work, we address all the above limitations. In particular, we study UPSI with semi-honest security in both the addition-only and addition-deletion settings. We present new protocols for both settings that support plain PSI as well as extended functionalities including PSI-Cardinality and PSI-Sum, achieving one-sided output (which implies two-sided output). In the addition-only setting, we also present a protocol for a more general functionality Circuit-PSI that outputs secret shares of the intersection. All of our protocols have worst-case computation and communication complexity that only grow with the set updates instead of the entire sets (except for a polylogarithmic factor). We implement our new UPSI protocols and compare with the state-of-the-art protocols for PSI and extended functionalities. Our protocols compare favorably when the total set sizes are sufficiently large, the new updates are sufficiently small, or in networks with low bandwidth.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
A minor revision of an IACR publication in ASIACRYPT 2024
Keywords
Private Set IntersectionSecure Two-Party ComputationOblivious Data Structure
Contact author(s)
bsaikrishna7393 @ gmail com
peihan_miao @ brown edu
xinyi_shi @ brown edu
max_tromanhauser @ brown edu
ruida_zeng @ brown edu
History
2024-09-20: revised
2024-09-17: received
See all versions
Short URL
https://ia.cr/2024/1446
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2024/1446,
      author = {Saikrishna Badrinarayanan and Peihan Miao and Xinyi Shi and Max Tromanhauser and Ruida Zeng},
      title = {Updatable Private Set Intersection Revisited: Extended Functionalities, Deletion, and Worst-Case Complexity},
      howpublished = {Cryptology {ePrint} Archive, Paper 2024/1446},
      year = {2024},
      url = {https://eprint.iacr.org/2024/1446}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.