Practical Two-Party Secret-Shared Joins for SQL Analytics

Abstract.  In this presentation, we describe practical protocols for secure SQL-style joins on secret-shared databases in the semi-honest two-party setting. Our goal is to let two parties compute joins without revealing raw records, while keeping both inputs and outputs secret-shared so results can be reused in later privacy-preserving queries. We present two protocols: a one-to-one join for unique keys with linear time and constant rounds, and a one-to-many join that supports duplicate keys with near-linear scaling. Our key technical ideas are an efficient secret-shared permutation primitive and a strong pseudorandom function protocol adapted to the semi-honest two-party setting. We explain how these components improve practical performance for two-party secure computation. We also summarize implementation and benchmark results, including million-row experiments and support for chained operations such as filtering and grouped aggregation.

Joint work: Srinivasan Raghuraman, Peter Rindal, Harshal Shah

Suggested readings

• Two-Party Secret Shared Joins (ia.cr/2025/702)

• Efficient Permutation Correlations and Batched Random Access for Two-Party Computation (ia.cr/2024/547)

• Improved Alternating Moduli PRFs and Post-Quantum Signatures (ia.cr/2024/582)