Release time:2025-03-31

Hits:

DOI number:10.1007/978-981-99-8721-4

Journal:Advances in Cryptology – ASIACRYPT 2023: 29th International Conference on the Theory and Application of Cryptology and Information Security, Guangzhou, China, December 4–8, 2023, Proceedings, Part I

Place of Publication:Guangzhou, China

Key Words:Multi-query secret-shared private membership test, Private set union, Multi-party secret-shared shuffle

Abstract:Multi-party private set union (MPSU) allows parties, each holding a dataset of known size, to compute the union of their sets without revealing any additional information. Although two-party PSU has made rapid progress in recent years, applying its effective techniques to the multi-party setting would render information leakage and thus cannot be directly extended. Existing MPSU protocols heavily rely on computationally expensive public-key operations or generic secure multi-party computation techniques, which are not scalable. In this work, we present a new efficient framework of MPSU from multi-party secret-shared shuffle and a newly introduced protocol called multi-query secret-shared private membership test (mq-ssPMT). Our MPSU is mainly based on symmetric-key operations and is secure against any semi-honest adversary that does not corrupt the leader and clients simultaneously. We also propose new frameworks for computing other multi-party private set operations (MPSO), such as the intersection, and the cardinality of the union and the intersection, meeting the same security requirements. We demonstrate the scalability of our MPSU protocol with an implementation and a comparison with the state-of-the-art MPSU. Experiments show that when computing on datasets of elements, our protocol is faster than the state-of-the-art MPSU, and the improvement becomes more significant as the set size increases. To the best of our knowledge, ours is the first protocol that reports on large-size experiments. For 7 parties with datasets of elements each, our protocol requires only 46 s.

Co-author:Ying Gao

First Author:Xiang Liu

Indexed by:会议论文

Correspondence Author:Ying Gao

Page Number:237–271

ISSN No.:978-981-99-8720-7

Translation or Not:no

Date of Publication:2023-12-18