Welcome to the resource topic for 2024/566
Title:
A Near-Linear Quantum-Safe Third-Party Private Set Intersection Protocol
Authors: Foo Yee Yeo, Jason H. M. Ying
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.
ePrint: https://eprint.iacr.org/2024/566
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .