Locally differentially private distributed algorithms for set intersection and union [Letter]

Locally differentially private distributed algorithms for set intersection and union [Letter]

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.