Scalable Private Set Union from Symmetric-Key Techniques

Vladimir Kolesnikov, Mike Rosulek, Ni Trieu, Xiao Wang

Research output: Chapter in Book/Report/Conference proceedingConference contribution

19 Scopus citations


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.

Original languageEnglish (US)
Title of host publicationAdvances in Cryptology – ASIACRYPT 2019 - 25th International Conference on the Theory and Application of Cryptology and Information Security, Proceedings
EditorsSteven D. Galbraith, Shiho Moriai
PublisherSpringer Science and Business Media Deutschland GmbH
Number of pages31
ISBN (Print)9783030346201
StatePublished - 2019
Externally publishedYes
Event25th Annual International Conference on the Theory and Applications of Cryptology and Information Security, ASIACRYPT 2019 - Kobe, Japan
Duration: Dec 8 2019Dec 12 2019

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume11922 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference25th Annual International Conference on the Theory and Applications of Cryptology and Information Security, ASIACRYPT 2019

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)


Dive into the research topics of 'Scalable Private Set Union from Symmetric-Key Techniques'. Together they form a unique fingerprint.

Cite this