Post-Quantum Private Set Intersection for Small Sets

Abstract: Are private set intersection (PSI) protocols ready for the post-quantum future? The leading PSI protocol for small sets (Rosulek & Trieu 2021) relies heavily on Diffie-Hellman techniques and is therefore vulnerable to quantum attacks. In this talk, we describe how to modify the protocol to make it compatible with post-quantum KEMs like ML-KEM. Interestingly, in the post-quantum setting, the symmetric-key primitives become the performance bottleneck. Along the way, we also introduce new abstractions for oblivious key-value stores that make the analysis of these kinds of PSI protocols more modular. We achieve PSI from standardized post-quantum primitives with latency as low as 0.25 ms/item and communication as low as 1.67 KiB/item.

Joint work: Junxin Liu, Mike Rosulek, Ni Trieu.

Suggested readings

• Compact and Malicious Private Set Intersection for Small Sets (ia.cr/2021/1159)
• Post-Quantum Private Set Intersection for Small Sets (ia.cr/2026/1985)