Paper 2025/2147

Updatable Private Set Intersection and Beyond: Efficient Constructions via Circuit Private Set Intersection

Tom Chauvier, EURECOM

Antonio Faonio, EURECOM

Alexandre Fontaine, EURECOM

Ferhat Karakoç, Ericsson Research

Alptekin Küpçü, Koç University

Camille Malek, EURECOM

Melek Önen, EURECOM

Abstract

Private Set Intersection (PSI) has been widely studied, deployed, and demonstrated on static datasets. In this work, we investigate the problem of designing efficient and secure updatable PSIs in the honest-but-curious model by adopting the approach of executing a small number of PSIs over smaller sets instead of one PSI over the entire updated sets. We first identify that existing constructions suffer from privacy leakages and further propose to mitigate them thanks to the use of circuit PSIs, which are variants of PSI protocols that output the secret shares of the intersection instead of outputting the resulting intersection, combined with secure shuffling when needed. We construct a generic framework for PSI over updated sets and show that this framework can easily be extended to a protocol that outputs the cardinality of the intersection instead of the intersection itself.

@misc{cryptoeprint:2025/2147,
      author = {Ferran Alborch and Tom Chauvier and Antonio Faonio and Alexandre Fontaine and Ferhat Karakoç and Alptekin Küpçü and Camille Malek and Melek Önen},
      title = {Updatable Private Set Intersection and Beyond: Efficient Constructions via Circuit Private Set Intersection},
      howpublished = {Cryptology {ePrint} Archive, Paper 2025/2147},
      year = {2025},
      url = {https://eprint.iacr.org/2025/2147}
}