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

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.