Locally differentially private distributed algorithms for set intersection and union [Letter]
Article
Article Title | Locally differentially private distributed algorithms for set intersection and union [Letter] |
---|---|
ERA Journal ID | 201483 |
Article Category | Article |
Authors | Xue, Qiao (Author), Zhu, Youwen (Author), Wang, Jian (Author), Li, Xingxin (Author) and Zhang, Ji (Author) |
Journal Title | Science China Information Sciences |
Number of Pages | 3 |
Year | 2020 |
Place of Publication | China |
ISSN | 1009-2757 |
1674-733X | |
1862-2836 | |
1869-1919 | |
Digital Object Identifier (DOI) | https://doi.org/10.1007/s11432-018-9899-8 |
Web Address (URL) | https://engine.scichina.com/publisher/scp/journal/SCIS/doi/10.1007/s11432-018-9899-8 |
Abstract | 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. |
ANZSRC Field of Research 2020 | 460402. Data and information privacy |
Byline Affiliations | Nanjing University of Aeronautics and Astronautics, China |
School of Sciences | |
Institution of Origin | University of Southern Queensland |
https://research.usq.edu.au/item/q5q7q/locally-differentially-private-distributed-algorithms-for-set-intersection-and-union-letter
120
total views12
total downloads0
views this month0
downloads this month