TY - GEN
T1 - Dependent differential privacy for correlated data
AU - Zhao, Jun
AU - Zhang, Junshan
AU - Poor, H. Vincent
N1 - Publisher Copyright:
© 2017 IEEE.
PY - 2017/7/2
Y1 - 2017/7/2
N2 - Many organizations maintain large collections of personal information. Clearly, sharing personal data may endanger the privacy of users whose data is shared. To rigorously evaluate the privacy and the utility of data publishing, the notion of differential privacy (DP) has received much attention. However, it has been shown that DP may not work well for databases with tuple correlations, which arise from various behavioral, social, and genetic relationships between users. DP masks only the presence of those records received from each user, but does not mask statistical trends that may reveal information about each user. This distinction leads to the degradation of privacy expectations in a social sense, since an adversary may still combine a query response with tuple correlation to learn about a user's data. To extend differential privacy for correlated data, prior work has investigated various privacy metrics. Nevertheless, these privacy metrics either assume background knowledge of the adversary or lack effective and general achieving mechanisms. To overcome these limitations, this paper formalizes the notion of dependent differential privacy (DDP) such that under any tuple correlation, almost no sensitive information about any user can be leaked because of answering a query. This DDP guarantee applies to any data correlation and is independent of the adversary's knowledge. It is shown that this DDP notion can be quantitatively deduced by DP with a stronger privacy parameter, where the difference between the privacy parameters of DDP and DP depends on the correlation between data tuples. Further, various mechanisms for achieving DDP are presented. These mechanisms are computationally efficient and achieve higher utilities than mechanisms introduced in prior work to address tuple correlations. As a representative example, for data correlations modeled by an n-tuple Markov chain and a query with constant global sensitivity, the amount of noise in a Laplace mechanism proposed here does not scale with n, whereas the level of the noise added by the state-of-the-art mechanism of Liu et al. scales linearly with n, so the proposed mechanism achieves higher utility than that of the state-of-the-art.
AB - Many organizations maintain large collections of personal information. Clearly, sharing personal data may endanger the privacy of users whose data is shared. To rigorously evaluate the privacy and the utility of data publishing, the notion of differential privacy (DP) has received much attention. However, it has been shown that DP may not work well for databases with tuple correlations, which arise from various behavioral, social, and genetic relationships between users. DP masks only the presence of those records received from each user, but does not mask statistical trends that may reveal information about each user. This distinction leads to the degradation of privacy expectations in a social sense, since an adversary may still combine a query response with tuple correlation to learn about a user's data. To extend differential privacy for correlated data, prior work has investigated various privacy metrics. Nevertheless, these privacy metrics either assume background knowledge of the adversary or lack effective and general achieving mechanisms. To overcome these limitations, this paper formalizes the notion of dependent differential privacy (DDP) such that under any tuple correlation, almost no sensitive information about any user can be leaked because of answering a query. This DDP guarantee applies to any data correlation and is independent of the adversary's knowledge. It is shown that this DDP notion can be quantitatively deduced by DP with a stronger privacy parameter, where the difference between the privacy parameters of DDP and DP depends on the correlation between data tuples. Further, various mechanisms for achieving DDP are presented. These mechanisms are computationally efficient and achieve higher utilities than mechanisms introduced in prior work to address tuple correlations. As a representative example, for data correlations modeled by an n-tuple Markov chain and a query with constant global sensitivity, the amount of noise in a Laplace mechanism proposed here does not scale with n, whereas the level of the noise added by the state-of-the-art mechanism of Liu et al. scales linearly with n, so the proposed mechanism achieves higher utility than that of the state-of-the-art.
KW - Data correlation
KW - Differential privacy
KW - Laplace mechanisms
KW - Markov chains
UR - http://www.scopus.com/inward/record.url?scp=85050544492&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85050544492&partnerID=8YFLogxK
U2 - 10.1109/GLOCOMW.2017.8269219
DO - 10.1109/GLOCOMW.2017.8269219
M3 - Conference contribution
AN - SCOPUS:85050544492
T3 - 2017 IEEE Globecom Workshops, GC Wkshps 2017 - Proceedings
SP - 1
EP - 7
BT - 2017 IEEE Globecom Workshops, GC Wkshps 2017 - Proceedings
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 2017 IEEE Global Telecommunications Conference, GC 2017
Y2 - 4 December 2017 through 8 December 2017
ER -