A Round-Optimal Near-Linear Third-Party Private Set Intersection Protocol
摘要
Third-party private set intersection (PSI) enables two parties, each holding a private set to compute their intersection and reveal the result only to an inputless third party. In this paper, we present an efficient round-optimal third-party PSI protocol. Our work is motivated by real-world applications such as contact tracing whereby expedition is essential while concurrently preserving privacy. Our construction only requires 2 communication rounds and attains a near-linear computational complexity of \(O(n^{1+\varepsilon })\) for large dataset size n, where \(\varepsilon >0\) is any fixed constant. Our improvements stem from algorithmic changes and the incorporation of new techniques to achieve a tight asymptotic bound. Furthermore, we also present a third-party PSI cardinality protocol which has not been explored in prior third-party PSI work. In a third-party PSI cardinality setting, only the third-party obtains the size of the intersection and nothing else. Our construction to achieve the cardinality functionality attains a quasilinear computational complexity for the third-party.