Updatable private set intersection and beyond: Efficient constructions via circuit private set intersection

Private Set Intersection (PSI) has been widely studied, deployed, and demonstrated through various reallife use cases such as mobile private contact discovery, privacy-preserving contact tracing, etc. Nevertheless, the majority of existing solutions typically assume that the underlying datasets are static and require a fresh execution of PSI at each time the datasets are updated over time. In this work, similar to a recent solution by Badrinaryanan et. al’ (ASIACRYPT 2024), we investigate the problem of designing efficient and secure updatable PSIs in the honestbut-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 two privacy leakages and further propose to mitigate them thanks to the use of circuit PSIs, which are variants of PSI protocols that instead of outputting the resulting intersection, output the secret shares of the intersection and nothing more, combined with secure shuffling when needed. We construct a generic framework for PSI over updated sets which can use any circuit-PSI. Additionally, we show that this framework can easily be extended to a protocol that outputs the cardinality of the intersection instead of the intersection, itself. Finally, we provide an indepth discussion on the feasibility of circuit PSI over updated sets, with the main challenges to overcome and solutions for some particular cases. Our solutions are implemented in Rust and their performance is compared with the state of the art, achieving an improvement of 11× to 40× in updatable PSI and 14× to 107× in updatable cardinality PSI in computation time. The proposed framework is also demonstrated through a real-life use case, namely, a spam detection filter.