Paper 2025/2254 Original: eprint.iacr.org/2025/2254 ↗

Multi-Party Private Join

Abstract

A multi-party private join (MPPJ) protocol enables multiple source parties to provide a receiver party with the inner joins over their respective datasets, while revealing as little information as possible. There is currently no protocol that directly and efficiently enables such a MPPJ beyond the two- or three-party setting. The presently known protocols either achieve weaker functionality (e.g., multi- party private set intersection protocols) or more general ones (e.g., private-join-compute and generic secure multi-party computation protocols) and are therefore more costly to run for the sources. This work formally introduces MPPJ as an explicit goal, and proposes an efficient, helper-assisted protocol that achieves 𝑛-party inner joins with small leakage and close-to-optimal overhead for the sources. Specifically, for 𝑛 databases with 𝑚 rows, it requires only a single 𝑂 (𝑚) upload from the sources to the helper, and a single 𝑂 (𝑛 · 𝑚) download from the helper to the receiver. Moreover, the helper is entirely oblivious: it enables the efficiency and simplicity goals we are striving for, but it does not learn anything about the computation it facilitates. We formally model and prove the security of our protocol from standard assumptions, in the passive-adversary model. Then, we provide an open-source implementation and an extensive performance evaluation. According to our experiments, our protocol requires 1.02 to 20 times less communication than a current private-join-compute protocol (with no computation over the join) for 2 to 6 parties and input database sizes from 1.5K to 250K records. Finally, we demonstrate the versatility of our approach by extending our protocol to threshold-joins.