Welcome to the resource topic for 2024/570
Title:
Large-Scale Private Set Intersection in the Client-Server Setting
Authors: Yunqing Sun, Jonathan Katz, Mariana Raykova, Phillipp Schoppmann, Xiao Wang
Abstract:Private set intersection (PSI) allows two parties to compute the intersection of their sets without revealing anything else. In some applications of PSI, a server holds a large set and needs to run PSI with many clients, each with its own small set. In this setting, however, all existing protocols fall short: they either incur too much cost to compute the intersections for many clients or cannot achieve the desired security requirements.
We design a protocol that particularly suits this setting with simulation-based security against malicious adversaries. In our protocol, the server publishes a one-time, linear-size encoding of its set. Then, multiple clients can each perform a cheap interaction with the server of complexity linear in the size of each client’s set. A key ingredient of our protocol is an efficient instantiation of an oblivious verifiable unpredictable function, which could be of independent interest. To obtain the intersection, the client can download the encodings directly, which can be accelerated via content distribution networks or peer-to-peer networks since the same encoding is used by all clients; alternatively, clients can fetch only the relevant ones using verifiable private information retrieval.
Our implementation shows very high efficiency. For a server holding 10^8 elements and each client holding 10^3 elements, the size of the server’s encoding is 800MB; interacting with each client uses 60MB of communication and runs in under 5s in a WAN network with 120Mbps bandwidth. Compared with the state-of-the-art PSI protocol, our scheme requires only 0.017 USD per client on an AWS server, which is 5x lower.
ePrint: https://eprint.iacr.org/2024/570
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 .