Welcome to the resource topic for 2019/776
Title:
Scalable Private Set Union from Symmetric-Key Techniques
Authors: Vladimir Kolesnikov, Mike Rosulek, Ni Trieu, Xiao Wang
Abstract:We present a new efficient protocol for computing private set union (PSU). Here two semi-honest parties, each holding a dataset of known size (or of a known upper bound), wish to compute the union of their sets without revealing anything else to either party. Our protocol is in the OT hybrid model. Beyond OT extension, it is fully based on symmetric-key primitives. We motivate the PSU primitive by its direct application to network security and other areas. At the technical core of our PSU construction is the reverse private membership test RPMT protocol. In RPMT, the sender with input x^* interacts with a receiver holding a set X. As a result, the receiver learns (only) the bit indicating whether x^* is in X, while the sender learns nothing about the set X. (Previous similar protocols provide output to the opposite party, hence the term "reverse’’ private membership.) We believe our RPMT abstraction and constructions may be a building block in other applications as well. We demonstrate the practicality of our proposed protocol with an implementation. For input sets of size 2^{20} and using a single thread, our protocol requires 238 seconds to securely compute the set union, regardless of the bit length of the items. Our protocol is amenable to parallelization. Increasing the number of threads from 1 to 32, our protocol requires only 13.1 seconds, a factor of 18.25 \times improvement. To the best of our knowledge, ours is the first protocol that reports on large-size experiments, makes code available, and avoids extensive use of computationally expensive public-key operations. (No PSU code is publicly available for prior work, and the only prior symmetric-key-based work reports on small experiments and focuses on the simpler 3-party, 1-corruption setting.)Our work improves reported PSU state of the art by factor up to 7,600\times for large instances.
ePrint: https://eprint.iacr.org/2019/776
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 .