Updatable Private Set Intersection
Paper: Updatable Private Set Intersection. Saikrishna Badrinarayanan, Peihan Miao, and Tiancheng Xie. 2021
Summary of result (From Table 1)
Summary
| Functionality | Output | Protocol | Comp. Complexity | Comm. Complexity |
|---|---|---|---|---|
| Addition-Only | Two-Sided | Figure 4 | \(O(N')\) | \(O(N')\) |
| Addition-Only | One-Sided | Figure 6 | \(O∗(N'\log{N})\) | \(O∗(N'\log{N})\) |
| Weak Deletion | Two-Sided | Figure 9 | \(O(N'\cdot t)\) | \(O(N'\cdot t)\) |
References
Saikrishna Badrinarayanan, Peihan Miao, and Tiancheng Xie. 2021. “Updatable Private Set Intersection.” https://eprint.iacr.org/2021/1349.