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

Ferran Alborch; Tom Chauvier; Antonio Faonio; Alexandre Fontaine; Ferhat Karakoç; Alptekin Küpçü; Camille Malek; Melek Önen

Paper 2025/2147

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

Ferran Alborch

, EURECOM

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.

Metadata

Available format(s): PDF
Category: Cryptographic protocols
Publication info: Published elsewhere. Minor revision. ACNS 2026
Keywords: private set intersection updated or dynamic datasets extended functionalities
Contact author(s): ferran alborch @ eurecom fr
antonio faonio @ eurecom fr
ferhat karakoc @ ericsson com
akupcu @ ku edu tr
camille malek @ tutamail com
melek onen @ eurecom fr
History: 2026-04-23: revised; 2025-11-24: received; See all versions
Short URL: https://ia.cr/2025/2147
License: CC BY

BibTeX

@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}
}