Updatable Private Set Intersection from Symmetric-Key Techniques

Private set intersection (PSI) has become extremely practical, in large part due to the fact that modern protocols rely almost exclusively on cheap, symmetric-key cryptography. The same cannot be said for the variant of PSI called updatable PSI (UPSI; Badrinarayanan et al., PoPETS 2022), where parties’ input sets evolve over time, and the cost of re-computing the intersection depends only on the changes to their sets. In existing UPSI protocols, the number of public-key operations scales with the number of items.

In this work, we introduce the first UPSI protocol that largely avoids public-key operations. In fact, our protocol uses mostly the same protocol tools/techniques that have been so successful in making (plain) PSI truly practical. By leveraging symmetric-key primitives, our implementation achieves orders-of-magnitude improvements over prior work.

Additionally, we observe that existing UPSI security proofs do not consider an adversary who can choose protocol inputs adaptively (i.e., choose which items to add to the set the current epoch based on the adversary’s view in previous epochs). We observe that several existing UPSI protocols are trivially broken by such adaptive input selection (even with semi-honest corruption). Several variants of our protocol are secure in the presence of adaptively chosen inputs.

Along the way, we also introduce a new and cleaner abstraction for a common idiom of using an oblivious key-value store (OKVS; Garimella et al., Crypto 2021) to represent a set of items. Our new abstraction, called affine set encoding, may be of independent interest.