Paper 2024/566
A Near-Linear Quantum-Safe 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 efficient third-party PSI protocols, which significantly lower the computational workload compared to prior work. Our work is motivated by real-world applications such as contact tracing whereby expedition is essential while concurrently preserving privacy. Our construction attains a near-linear computational complexity of $O(n^{1+\varepsilon})$ for large dataset size $n$, where $\varepsilon>0$ is any fixed constant, and achieves post-quantum security. For a quantum-safe third-party PSI protocol, this significantly improves upon the current known best of $O(n^{2.5+o(1)})$. Our improvements stem from algorithmic changes and the incorporation of new techniques along with precise parameter selections to achieve a tight asymptotic bound.
Metadata
- Available format(s)
- Category
- Cryptographic protocols
- Publication info
- Preprint.
- Keywords
- private set intersectionPSI
- Contact author(s)
-
fooyee yeo @ seagate com
jasonhweiming ying @ seagate com - History
- 2024-04-12: approved
- 2024-04-12: received
- See all versions
- Short URL
- https://ia.cr/2024/566
- License
-
CC BY-NC-ND
BibTeX
@misc{cryptoeprint:2024/566, author = {Foo Yee Yeo and Jason H. M. Ying}, title = {A Near-Linear Quantum-Safe Third-Party Private Set Intersection Protocol}, howpublished = {Cryptology ePrint Archive, Paper 2024/566}, year = {2024}, note = {\url{https://eprint.iacr.org/2024/566}}, url = {https://eprint.iacr.org/2024/566} }