Paper 2024/566 Original: eprint.iacr.org/2024/566 ↗
A Round-Optimal Near-Linear Third-Party Private Set Intersection Protocol
Abstract
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.
Metadata
- Available format(s)
PDF- Category
- Cryptographic protocols
- Publication info
- Preprint.
- History
- 2025-07-18: last updated
- 2024-04-12: published
- Short URL
- https://ia.cr/2024/566
- License
- https://creativecommons.org/licenses/by-nc-nd/4.0/
BibTeX
@misc{cryptoeprint:2024/566,
author = {Foo Yee Yeo and Jason H. M. Ying},
title = {A Round-Optimal Near-Linear Third-Party Private Set Intersection Protocol},
howpublished = {Cryptology {ePrint} Archive, Paper 2024/566},
year = {2024},
url = {https://eprint.iacr.org/2024/566}
}