Updatable Private Set Intersection
summary
Defines updatable PSI protocols that make per-run cost scale with the update size, presenting three semi-honest constructions: two addition-only (two-sided O(n) communication and one-sided O(n log N) amortized), and a weak-deletion sliding window. Then gives worst-case one-sided protocols for plain, cardinality, sum and circuit PSI with O(n log n) costs. Implements a path-ORAM-style oblivious store plus homomorphic checks and an OKVS+VOLE pipeline (batched OPRF) to minimize public-key work; works but leaks under adaptively chosen updates and can be slower than VOLE PSI when updates are not tiny.
AI-written summary · about
chapters (11)
- 0:00Introduction to updatable private set intersection
- 3:02Motivation for updatable PSI
- 7:42Limitations of initial work
- 10:11Diffie-Hellman PSI approach
- 14:27Streaming PSI security issues
- 16:40Two-sided output PSI design
- 19:38One-sided output oblivious DS
- 23:16VOLE-based PSI overview
- 26:12Making VOLE-based PSI updatable
- 29:46Open problems and future work
- 30:49Summary
related talks
22mScalable Zero-Knowledge Protocols From Vector-OLE
28mProving Obliviousness of Probabilistic Algorithms with Formal Verification
48mFormal Modelling of Information-flow Control Systems: Some Lessons Learned
44mIOP based Zero-Knowledge Proofs
33mInteraction Preserving Compilers for Secure Computation
51mDistributed Zero-Knowledge Proofs and Applications to Secure Computation
23mRecent progress in MPC-in-the-Head protocols
30mKEYNOTE Building Succinct Arguments from Ideal Hash Functions