Implementing PSI: From Elliptic Curves to Oblivious Transfer and Distance-Aware Extensions

Abstract. Private Set Intersection (PSI) enables multiple parties to securely compute the intersection of their private datasets without revealing any additional information. This talk provides a comprehensive overview of three prominent PSI paradigms covering both exact and approximate matching scenarios. It begins with elliptic curve Diffie–Hellman (EC-DH) based PSI tailored for small sets, emphasizing its compactness and efficiency. Next, we explore high-performance OT-based PSI constructions that utilize batched oblivious pseudorandom functions (OPRFs) to achieve scalability and speed for large datasets. Finally, the talk introduces distance-aware oblivious transfer protocols designed for fuzzy PSI, which relax exact matching requirements to proximity-based comparisons, broadening PSI's applicability to noisy, real-world data. Throughout the presentation, we highlight strategies to accelerate PSI performance by experimenting with implementations of core cryptographic primitives. By examining practical optimizations in elliptic curve computations, OT extensions, and distance-aware OT techniques, we show how these foundational components can significantly improve the performance of PSI systems in practice.

Suggested readings: ia.cr/2025/996, ia.cr/2021/266, ia.cr/2021/1159

[Slides]