skip to main content
US FlagAn official website of the United States government
dot gov icon
Official websites use .gov
A .gov website belongs to an official government organization in the United States.
https lock icon
Secure .gov websites use HTTPS
A lock ( lock ) or https:// means you've safely connected to the .gov website. Share sensitive information only on official, secure websites.

Attention:

The NSF Public Access Repository (PAR) system and access will be unavailable from 11:00 PM ET on Friday, July 11 until 2:00 AM ET on Saturday, July 12 due to maintenance. We apologize for the inconvenience.

Explore Research Products in the PAR
It may take a few hours for recently added research products to appear in PAR search results.


Title: Shuffle-based Private Set Union: Faster and More Secure
Private Set Union (PSU) allows two players, the sender and the receiver, to compute the union of their input datasets with- out revealing any more information than the result. While it has found numerous applications in practice, not much research has been carried out so far, especially for large datasets. In this work, we take shuffling technique as a key to design PSU protocols for the first time. By shuffling receiver’s set, we put forward the first protocol, denoted as $$\Pi^R_{PSU}$$, that eliminates the expensive operations in previous works, such as additive homomorphic encryption and repeated operations on the receiver’s set. It outperforms the state-of-the-art design by Kolesnikov et al. (ASIACRYPT 2019) in both efficiency and security; the unnecessary leakage in Kolesnikov et al.’s design, can be avoided in our design. We further extend our investigation to the application scenarios in which both players may hold unbalanced input datasets. We propose our second protocol $$\Pi^S_{PSU}$$, by shuffling the sender’s dataset. This design can be viewed as a dual version of our first protocol, and it is suitable in the cases where the sender’s input size is much smaller than the receiver’s. Finally, we implement our protocols $$\Pi^R_{PSU}$$ and $$\Pi^S_{PSU}$$ in C++ on big datasets, and perform a comprehensive evaluation in terms of both scalability and parallelizability. The results demonstrate that our design can obtain a 4-5X improvement over the state-of-the-art by Kolesnikov et al. with a single thread in WAN/LAN settings.  more » « less
Award ID(s):
1801470
PAR ID:
10352922
Author(s) / Creator(s):
; ; ; ;
Date Published:
Journal Name:
31st USENIX Security Symposium (USENIX Security 22)
Page Range / eLocation ID:
2947-2964
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. ; ; ; ; (, 31st USENIX Security Symposium (USENIX Security 22))
    Private Set Union (PSU) allows two players, the sender and the receiver, to compute the union of their input datasets with- out revealing any more information than the result. While it has found numerous applications in practice, not much re- search has been carried out so far, especially for large datasets. In this work, we take shuffling technique as a key to de- sign PSU protocols for the first time. By shuffling receiver’s set, we put forward the first protocol, denoted as ΠRPSU, that eliminates the expensive operations in previous works, such as additive homomorphic encryption and repeated operations on the receiver’s set. It outperforms the state-of-the-art design by Kolesnikov et al. (ASIACRYPT 2019) in both efficiency and security; the unnecessary leakage in Kolesnikov et al.’s design, can be avoided in our design. We further extend our investigation to the application sce- narios in which both players may hold unbalanced input datasets. We propose our second protocol ΠSPSU, by shuffling the sender’s dataset. This design can be viewed as a dual ver- sion of our first protocol, and it is suitable in the cases where the sender’s input size is much smaller than the receiver’s. Finally, we implement our protocols ΠRPSU and ΠSPSU in C++ on big datasets, and perform a comprehensive evaluation in terms of both scalability and parallelizability. The results demonstrate that our design can obtain a 4-5× improvement over the state-of-the-art by Kolesnikov et al. with a single thread in WAN/LAN settings. 
    more » « less
  2. ; ; ; (, USENIX Association)
    Private Set Union (PSU) protocol allows parties, each hold- ing an input set, to jointly compute the union of the sets without revealing anything else. In the literature, scalable PSU protocols follow the “split-execute-assemble” paradigm (Kolesnikov et al., ASIACRYPT 2019); in addition, those fast protocols often use Oblivious Transfer as building blocks. Kolesnikov et al. (ASIACRYPT 2019) and Jia et al. (USENIX Security 2022), pointed out that certain security issues can be introduced in the “split-execute-assemble” paradigm. In this work, surprisingly, we observe that the typical way of invoking Oblivious Transfer also causes unnecessary leakage, and only the PSU protocols based on additively homomor- phic encryption (AHE) can avoid the leakage. However, the AHE-based PSU protocols are far from being practical. To bridge the gap, we also design a new PSU protocol that can avoid the unnecessary leakage. Unlike the AHE- based PSU protocols, our new construction only relies on symmetric-key operations other than base OTs, thereby being much more scalable. The experimental results demonstrate that our protocol can obtain at least 873.74× speedup over the best-performing AHE-based scheme. Moreover, our per- formance is comparable to that of the state-of-the-art PSU protocol (Chen et al., USENIX Security 2023), which also suffers from the unnecessary leakage. 
    more » « less
  3. ; ; (, Springer)
    Structure-Aware private set intersection (sa-PSI) is a variant of PSI where Alice’s input set A has some publicly known structure, Bob’s input B is an unstructured set of points, and Alice learns the intersection A ∩ B. sa-PSI was recently introduced by Garimella et al. (Crypto 2022), who described a semi-honest protocol with communication that scales with the description size of Alice’s set, instead of its cardinality. In this paper, we present the first sa-PSI protocol secure against malicious adversaries. sa-PSI protocols are built from function secret sharing (FSS) schemes, and the main challenge in our work is ensuring that multiple FSS sharings encode the same structured set. We do so using a cut-and-choose approach. In order to make FSS compatible with cut-and-choose, we introduce a new variant of function secret sharing, called derandomizable FSS (dFSS). We show how to construct dFSS for union of geometric balls, leading to a malicious-secure sa-PSI protocol where Alice’s input is a union of balls. We also improve prior FSS constructions, giving asymptotic improvements to semi-honest sa-PSI. 
    more » « less
  4. ; ; (, Proceedings on Privacy Enhancing Technologies)
    This paper studies a multi-party private set union (mPSU), a fundamental cryptographic problem that allows multiple parties to compute the union of their respective datasets without revealing any additional information. We propose an efficient mPSU protocol which is secure in the presence of any number of colluding semi-honest participants. Our protocol avoids computationally expensive homomorphic operations or generic multi-party computation, thus providing an efficient solution for mPSU. The crux of our protocol lies in the utilization of new cryptographic tool, namely, Membership Oblivious Transfer (mOT). We believe that the mOT may be of independent interest. We implement our mPSU protocol and evaluate its performance. Our protocol shows an improvement of up to $80.84 times$ in terms of running time and $405.73 times$ bandwidth cost compared to the existing state-of-the-art protocols. 
    more » « less
  5. ; (, Proceedings on Privacy Enhancing Technologies)
    Mazurek, Michelle L; Sherr, Micah. (Ed.)
    This work presents RPM, a scalable anonymous communication protocol suite using secure multiparty computation (MPC) with the offline-online model. We generate random, unknown permutation matrices in a secret-shared fashion and achieve improved (online) performance and the lightest communication and computation overhead for the clients compared to the state of art robust anonymous communication protocols. Using square-lattice shuffling, we make our protocol scale well as the number of clients increases. We provide three protocol variants, each targeting different input volumes and MPC frameworks/libraries. Besides, due to the modular design, our protocols can be easily generalized to support more MPC functionalities and security properties as they get developed. We also illustrate how to generalize our protocols to support two-way anonymous communication and secure sorting. We have implemented our protocols using the MP-SPDZ library suit and the benchmark illustrates that our protocols achieve unprecedented online phase performance with practical offline phases. 
    more » « less
  • Citation Formats
  • MLA
  • APA
  • Chicago
  • BibTeX
  • Save / Share this Record
  • Send to Email