(2026-03) Practically Efficient Linear-Time Protocols for Server-Aided Private Set Union and Third Party Private Set Operations
2026-03-12
We present protocols for server-aided private set union (PSU), third-party private set difference (TP-PSD) and third-party private symmetric difference (TP-PSymD). In a third-party setting, the receiver who obtains the output is an external inputless party with two other participating input parties. The protocols for third-party private set operations presented in this work are significantly more efficient than that of Yeo and Ying (USENIX ’25). Our results improve upon the above work in both the computational complexity and practical performances. Moreover, our protocols demonstrate practical gains by achieving substantially quicker running times as well as the ability to run on much larger sets. Our server-aided private set union protocol is several times faster than existing state-of-the-art two-party private set union protocols.