Unbalanced Private Set Union with Reduced Computation and Communication
Open Access
- 2 December 2024
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 1434-1447
Abstract
Private set union (PSU) is a cryptographic protocol that allows two parties to compute the union of their sets without revealing anything else. Despite some efficient PSU protocols that have been proposed, they mainly focus on the balanced setting, where the sets held by the parties are of similar size. Recently, Tu et al. (CCS 2023) proposed the first unbalanced PSU protocol which achieves sublinear communication complexity in the size of the larger set. In this paper, we are interested in improving the efficiency of the unbalanced PSU protocol. We find that oblivious key-value store (OKVS) data structure plays an essential role in the most recently proposed PSU constructions and formalize unbalanced PSU as an OKVS decoding process with sublinear communication. Our key insight lies in when OKVS satisfies sparsity property, obtaining the necessary decoding information precisely aligns with the batch private information retrieval (BatchPIR) problem. We give two concrete constructions of unbalanced PSU protocols based on different OKVS encoding strategies. The first is based on oblivious PRF (OPRF) and a newly introduced cryptographic protocol called permuted private equality test, while the second is based on re-randomizable public key encryption. Both our two constructions achieve sublinear communication complexity in the size of the larger set. We implement our two unbalanced PSU protocols and compare them with the state-of-the-art unbalanced PSU of Tu et al. Experiments show that our protocols achieve a 1.3-5.6\times speedup in running time and 2.1-11.8× shrinking in communication cost, depending on set sizes and network environments.Keywords
This publication has 26 references indexed in Scilit:
- PIRANA: Faster Multi-query PIR via Constant-weight Codes2024
- VOLE-PSI: Fast OPRF and Circuit-PSI from Vector-OLE2021
- Private Set Operations from Oblivious Switching2021
- Secure Multiparty Computation for Cooperative Cyber Risk Assessment2016
- More efficient oblivious transfer and extensions for faster secure computation2013
- Privacy-Preserving Set Operations2005
- Batch codes and their applications2004
- Foundations of Cryptography2004
- Cuckoo hashingJournal of Algorithms, 2004
- A public key cryptosystem and a signature scheme based on discrete logarithmsIEEE Transactions on Information Theory, 1985