Scalable Private Set Union from Symmetric-Key Techniques

Vladimir Kolesnikov, Mike Rosulek, Ni Trieu, Xiao WangIACR ePrint 2019 · OpenReview

TL;DR

This paper introduces a novel, highly efficient protocol for Private Set Union (PSU) using only symmetric-key cryptography, achieving a massive speedup (up to 7,600x) over prior methods. This advancement makes secure set union practical for large datasets, opening doors for applications in network security and data aggregation.

What Problem Does This Paper Address?

Private Set Union (PSU) is a cryptographic primitive that allows two parties to compute the union of their private datasets without revealing any information beyond the union itself. While Private Set Intersection (PSI) has seen significant research and efficient solutions, PSU has lagged behind, particularly for large datasets. Existing PSU protocols often rely on computationally expensive public-key cryptography, making them impractical for real-world scenarios involving millions of data items. This paper addresses this scalability bottleneck by developing a PSU protocol that is significantly faster and relies primarily on symmetric-key primitives.

Methods

The core of the paper's contribution lies in a new primitive called Reverse Private Membership Test (RPMT). Unlike traditional Private Membership Test (PMT) where the party with the item learns if it's in the other's set, RPMT provides this information to the party holding the set, while the item's owner learns nothing. This "reverse" functionality is crucial for PSU.

The authors build their PSU protocol in stages:

  1. Reverse Private Membership Test (RPMT): They design an efficient RPMT protocol using Oblivious PRF (OPRF) and Private Equality Test (PEQT). The sender provides an item, and the receiver, holding a set, learns if the item is in their set.
  2. Bucketing/Hashing: To handle large datasets efficiently, they employ a hashing technique to distribute items into a smaller number of "bins." This allows them to perform the RPMT protocol on smaller subsets of data within each bin, reducing overall computation. They introduce a clever use of "dummy items" to hide the actual number of items in each bin, preserving privacy.
  3. Optimization: They further optimize the protocol by relaxing the strict security of RPMT for the PSU context. Since the PSU protocol will eventually reveal items not in the intersection, a slightly "leaky" RPMT (where the sender might learn something if their item is not in the receiver's set) is acceptable and leads to further performance gains.

Datasets

Not discussed in the paper. The paper focuses on theoretical protocol design and experimental evaluation using synthetic datasets of varying sizes.

Key Insights and Ideas

  • RPMT is the Key: The invention of Reverse Private Membership Test (RPMT) is a critical insight. By flipping the output recipient of a membership test, they unlock a more natural building block for PSU.
  • Symmetric-Key Power: Demonstrating that efficient PSU can be achieved with only symmetric-key primitives (beyond initial OT extension setup) is a significant departure from prior work and a major performance driver.
  • Bucketing for Scalability: The bucketing/hashing strategy is essential for scaling to large datasets. It breaks down the problem into smaller, manageable subproblems.
  • Dummy Items for Privacy: The use of dummy items to pad bins is an elegant way to hide set sizes and prevent information leakage about bin contents.
  • Contextual Security Relaxation: Recognizing that the overall PSU functionality can tolerate a slightly weaker primitive (like a leaky RPMT) is a smart optimization that significantly boosts performance without compromising the final PSU security.

Key Results

The paper reports dramatic performance improvements:

  • Speedup: Their protocol is up to 7,600x faster than prior state-of-the-art for large datasets (e.g., 2^20 elements).
  • Practicality: For two million-element datasets, their protocol runs in about a minute over a WAN and 13 seconds over a LAN.
  • Parallelization: The protocol scales well with parallelization, achieving an 18.25x speedup by using 32 threads compared to a single thread for a 2^20 dataset.
  • Communication Efficiency: They achieve significantly lower communication costs compared to previous methods, especially for larger datasets. For n=2^18, their protocol requires 652.09 MB, a 6.38x improvement over [DC17].
  • Public Availability: They release their implementation on GitHub, making it a valuable resource for the research community.

Limitations and Future Work

  • Malicious Model: The current protocol is designed for the semi-honest model. The authors acknowledge that the malicious model is the ultimate goal and suggest their work can serve as a stepping stone.
  • Initial OT Extension: While the core protocol uses symmetric-key operations, it still relies on an initial setup involving a small number of public-key operations for Oblivious Transfer (OT) extension.
  • Future Work: The authors suggest exploring optimizations for the malicious model and further refining the hashing and bucketing strategies. They also hint at potential applications of their RPMT primitive beyond PSU.

Summary updated

BibTeX
@article{kolesnikov2019scalable,
  author = {Vladimir Kolesnikov and Mike Rosulek and Ni Trieu and Xiao Wang},
  title = {{Scalable Private Set Union from Symmetric-Key Techniques}},
  journal = {IACR Cryptol. ePrint Arch.},
  year = {2019},
  url = {https://openreview.net/forum?id=pPhf7a1sZOt},
}
Figure