Scalable Multi-party Private Set Union from Multi-Query Secret-Shared Private Membership Test

DOI码：

10.1007/978-981-99-8721-4

发表刊物：

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

刊物所在地：

Guangzhou, China

关键字：

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

摘要：

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.

合写作者：

Ying Gao

第一作者：

Xiang Liu

论文类型：

会议论文

通讯作者：

Ying Gao

页面范围：

237–271

ISSN号：

978-981-99-8720-7

是否译文：

否

发表时间：

2023-12-18