SCIENCE CHINA Information Sciences, https://doi.org/10.1007/s11432-018-9899-8

Locally Differentially Private Distributed Algorithms for Set Intersection and Union

More info


Privacy-preserving distributed set intersection and union (PPSI, PPSU) have received much attention in recent years because of their wide applications. Most of existing solutions utilize secure multiparty computation protocols (SMCP) to settle the problem, but the SMCP methods are expensive in computation and communication. Even worse, most SMCP methods hardly continue to work if some participants disconnect. In this paper, we consider a distributed model where each data owner has a secret set. Then, we design effective and high-efficiency PPSI/PPSU mechanisms under local differential privacy (LDP), which are suitable for normal sets and multisets. In our proposed schemes, each data owner first sanitizes his own set locally to protect sensitive information. Then, the collector gathers these sanitized datasets from data owners, and estimates the intersection and union from the sanitized sets. Through theoretical analysis, we prove the designed schemes satisfy LDP. Further, we show that our schemes can tolerate the disconnection of some data owners and resist collusion attack of participants. In addition, our schemes have low computation and communication costs. Finally, we evaluate the proposed schemes by conducting extensive experiments, which confirm the effectiveness and efficiency of our schemes.

Funded by

This work is partly supported by the National Key Research and Development Program of China (No. 2017YFB0802300), and the Natural Science Foundation of China (No. 61602240).

Copyright 2019 Science China Press Co., Ltd. 《中国科学》杂志社有限责任公司 版权所有