Paper 2021/1349

Updatable Private Set Intersection

Saikrishna Badrinarayanan, Peihan Miao, and Tiancheng Xie


Private set intersection (PSI) allows two mutually distrusting parties each with a set as input, to learn the intersection of both their sets without revealing anything more about their respective input sets. Traditionally, PSI studies the static setting where the computation is performed only once on both parties' input sets. We initiate the study of updatable private set intersection (UPSI), which allows parties to compute the intersection of their private sets on a regular basis with sets that also constantly get updated. We consider two specific settings. In the first setting called UPSI with addition, parties can add new elements to their old sets. We construct two protocols in this setting, one allowing both parties to learn the output and the other only allowing one party to learn the output. In the second setting called UPSI with weak deletion, parties can additionally delete their old elements every $t$ days. We present a protocol for this setting allowing both parties to learn the output. All our protocols are secure against semi-honest adversaries and have the guarantee that both the computational and communication complexity only grow with the set updates instead of the entire sets. Finally, we implement our UPSI with addition protocols and compare with the state-of-the-art PSI protocols. Our protocols compare favorably when the total set size is sufficiently large, the new updates are sufficiently small, or in networks with low bandwidth.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. 22nd Privacy Enhancing Technologies Symposium (PETS 2022)
Private Set IntersectionSecure Two-Party ComputationNew Protocols
Contact author(s)
bsaikrishna7393 @ gmail com
peihan @ uic edu
tianc x @ berkeley edu
2021-12-21: last of 2 revisions
2021-10-07: received
See all versions
Short URL
Creative Commons Attribution


      author = {Saikrishna Badrinarayanan and Peihan Miao and Tiancheng Xie},
      title = {Updatable Private Set Intersection},
      howpublished = {Cryptology ePrint Archive, Paper 2021/1349},
      year = {2021},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.