An official website of the United States government
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
This content will become publicly available on August 14, 2025
Scalable Private Set Union, with Stronger Security
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
- Award ID(s):
- 1801470
- PAR ID:
- 10546562
- Publisher / Repository:
- USENIX Association
- Date Published:
- ISBN:
- 978-1-939133-44-1
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
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
-
SPRINGER (Ed.)In this work we study the problem of minimizing the round complexity for securely evaluating multiparty functionalities while making black-box use of polynomial time assumptions. In Eurocrypt 2016, Garg et al. showed that assuming all parties have access to a broadcast channel, then at least four rounds of communication are required to securely realize non-trivial functionalities in the plain model. A sequence of works follow-up the result of Garg et al. matching this lower bound under a variety of assumptions. Unfortunately, none of these works make black-box use of the underlying cryptographic primitives. In Crypto 2021, Ishai, Khurana, Sahai, and Srinivasan came closer to matching the four-round lower bound, obtaining a five-round protocol that makes black-box use of oblivious transfer and PKE with pseudorandom public keys. In this work, we show how to realize any input-less functionality (e.g., coin-tossing, generation of key-pairs, and so on) in four rounds while making black-box use of two-round oblivious transfer. As an additional result, we construct the first four-round MPC protocol for generic functionalities that makes black-box use of the underlying primitives, achieving security against non-aborting adversaries. Our protocols are based on a new primitive called list two-party computation. This primitive offers relaxed security compared to the standard notion of secure two-party computation. Despite this relaxation, we argue that this tool suffices for our applications. List two-party computation is of independent interest, as we argue it can also be used for the generation of setups, like oblivious transfer correlated randomness, in three rounds. Prior to our work, generating such a setup required at least four rounds of interactions or a trusted third party.more » « less
-
Cas Cremers and Engin Kirda (Ed.)Vector Oblivious Linear Evaluation (VOLE) supports fast and scalable interactive Zero-Knowledge (ZK) proofs. Despite recent improvements to VOLE-based ZK, compiling proof statements to a control-flow oblivious form (e.g., a circuit) continues to lead to expensive proofs. One useful setting where this inefficiency stands out is when the statement is a disjunction of clauses $$\mathcal{L}_1 \lor \cdots \lor \mathcal{L}_B$$. Typically, ZK requires paying the price to handle all $$B$$ branches. Prior works have shown how to avoid this price in communication, but not in computation. Our main result, $$\mathsf{Batchman}$$, is asymptotically and concretely efficient VOLE-based ZK for batched disjunctions, i.e. statements containing $$R$$ repetitions of the same disjunction. This is crucial for, e.g., emulating CPU steps in ZK. Our prover and verifier complexity is only $$\bigO(RB+R|\C|+B|\C|)$$, where $$|\C|$$ is the maximum circuit size of the $$B$$ branches. Prior works' computation scales in $$RB|\C|$$. For non-batched disjunctions, we also construct a VOLE-based ZK protocol, $$\mathsf{Robin}$$, which is (only) communication efficient. For small fields and for statistical security parameter $$\lambda$$, this protocol's communication improves over the previous state of the art ($$\mathsf{Mac'n'Cheese}$$, Baum et al., CRYPTO'21) by up to factor $$\lambda$$. Our implementation outperforms prior state of the art. E.g., we achieve up to $$6\times$$ improvement over $$\mathsf{Mac'n'Cheese}$$ (Boolean, single disjunction), and for arithmetic batched disjunctions our experiments show we improve over $$\mathsf{QuickSilver}$$ (Yang et al., CCS'21) by up to $$70\times$$ and over $$\mathsf{AntMan}$$ (Weng et al., CCS'22) by up to $$36\times$$.more » « less
-
Outsourcing semiconductor device fabrication can result in malicious insertions and overbuilding of integrated circuits (ICs) by untrusted foundries without the IP owner’s knowledge. Active hardware metering methods attempt to combat IC piracy by requiring fabs to perform an activation protocol with the IP owner for each chip created. In this paper, we have taken a closer look at the IC metering through bus scrambling protocol mentioned in Maes et al., 2009 and we investigate alternatives which employ 1-out of 2 oblivious transfer (OT). Our focus is on Bellare Micali OT and Naor Pinkas OT, which, under certain assumptions, guarantee protection against malicious adversaries. Using OT as an alternative helps with the need to protect the integrity of the private input generated by the chip. Thus, the security of the protocol reduces to the Decisional Diffie Hellman sense. Finally, we discuss possible attacks and show how the proposed protocols could prevent them.more » « less
