TY - GEN
T1 - Scalable Private Set Union from Symmetric-Key Techniques
AU - Kolesnikov, Vladimir
AU - Rosulek, Mike
AU - Trieu, Ni
AU - Wang, Xiao
N1 - Publisher Copyright:
© 2019, International Association for Cryptologic Research.
PY - 2019
Y1 - 2019
N2 - 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*, 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 220 and using a single thread, our protocol requires 238 s 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 s, a factor of 18.25x 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,600x for large instances.
AB - 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*, 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 220 and using a single thread, our protocol requires 238 s 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 s, a factor of 18.25x 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,600x for large instances.
UR - http://www.scopus.com/inward/record.url?scp=85076999046&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85076999046&partnerID=8YFLogxK
U2 - 10.1007/978-3-030-34621-8_23
DO - 10.1007/978-3-030-34621-8_23
M3 - Conference contribution
AN - SCOPUS:85076999046
SN - 9783030346201
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 636
EP - 666
BT - Advances in Cryptology – ASIACRYPT 2019 - 25th International Conference on the Theory and Application of Cryptology and Information Security, Proceedings
A2 - Galbraith, Steven D.
A2 - Moriai, Shiho
PB - Springer Science and Business Media Deutschland GmbH
T2 - 25th Annual International Conference on the Theory and Applications of Cryptology and Information Security, ASIACRYPT 2019
Y2 - 8 December 2019 through 12 December 2019
ER -