Linear Private Set Union from Multi-Query Reverse Private Membership Test

Cong Zhang; Yu Chen; Weiran Liu; Min Zhang; Dongdai Lin

Paper 2022/358

Linear Private Set Union from Multi-Query Reverse Private Membership Test

Cong Zhang, State Key Laboratory of Information Security, Institute of Information Engineering, Chinese Academy of Sciences, Beijing 100093, China; School of Cyber Security, University of Chinese Academy of Sciences, Beijing 100049, China

Yu Chen, School of Cyber Science and Technology, Shandong University, Qingdao 266237, China; State Key Laboratory of Cryptology, P.O. Box 5159, Beijing 100878, China; Key Laboratory of Cryptologic Technology and Information Security, Ministry of Education, Shandong University, Qingdao 266237, China

Weiran Liu, Alibaba Group (China)

Min Zhang, School of Cyber Science and Technology, Shandong University, Qingdao 266237, China; State Key Laboratory of Cryptology, P.O. Box 5159, Beijing 100878, China; Key Laboratory of Cryptologic Technology and Information Security, Ministry of Education, Shandong University, Qingdao 266237, China

Dongdai Lin

Abstract

Private set union (PSU) protocol enables two parties, each holding a set, to compute the union of their sets without revealing anything else to either party. So far, there are two known approaches for constructing PSU protocols. The first mainly depends on additively homomorphic encryption (AHE), which is generally inefficient since it needs to perform a non-constant number of homomorphic computations on each item. The second is mainly based on oblivious transfer and symmetric-key operations, which is recently proposed by Kolesnikov et al. (ASIACRYPT 2019). It features good practical performance, which is several orders of magnitude faster than the first one. However, neither of these two approaches is optimal in the sense that their computation and communication complexity are not both , where is the size of the set. Therefore, the problem of constructing the optimal PSU protocol remains open. In this work, we resolve this open problem by proposing a generic framework of PSU from oblivious transfer and a newly introduced protocol called multi-query reverse private membership test (mq-RPMT). We present two generic constructions of mq-RPMT. The first is based on symmetric-key encryption and general 2PC techniques. The second is based on re-randomizable public-key encryption. Both constructions lead to PSU with linear computation and communication complexity. We implement our two PSU protocols and compare them with the state-of-the-art PSU. Experiments show that our PKE-based protocol has the lowest communication of all schemes, which is lower depending on set size. The running time of our PSU scheme is faster than that of state-of-the-art depending on network environments.

Metadata

Available format(s): PDF
Category: Cryptographic protocols
Publication info: Published elsewhere. USENIX Security 2023
Contact author(s): zhangcong @ iie ac cn
yuchen prc @ gmail com
weiran lwr @ alibaba-inc com
zm_min @ mail sdu edu cn
ddlin @ iie ac cn
History: 2022-12-02: last of 3 revisions; 2022-03-18: received; See all versions
Short URL: https://ia.cr/2022/358
License: CC BY

BibTeX

@misc{cryptoeprint:2022/358,
      author = {Cong Zhang and Yu Chen and Weiran Liu and Min Zhang and Dongdai Lin},
      title = {Linear Private Set Union from Multi-Query Reverse Private Membership Test},
      howpublished = {Cryptology {ePrint} Archive, Paper 2022/358},
      year = {2022},
      url = {https://eprint.iacr.org/2022/358}
}