On Sampling, Anonymization, and Differential Privacy Or, K-Anonymization Meets Differential Privacy

被引:0
作者
Li, Ninghui [1 ]
Qardaji, Wahbeh [1 ]
Su, Dong [1 ]
机构
[1] Purdue Univ, 305 N Univ St, W Lafayette, IN 47907 USA
来源
7TH ACM SYMPOSIUM ON INFORMATION, COMPUTER AND COMMUNICATIONS SECURITY (ASIACCS 2012) | 2012年
基金
美国国家科学基金会;
关键词
Differential Privacy; Anonymization; Data Privacy; ANONYMITY;
D O I
暂无
中图分类号
TP301 [理论、方法];
学科分类号
081202 ;
摘要
This paper aims at answering the following two questions in privacy-preserving data analysis and publishing: What formal privacy guarantee (if any) does k-anonymization provide? How can we benefit from the adversary's uncertainty about the data? We have found that random sampling provides a connection that helps answer these two questions, as sampling can create uncertainty. The main result of the paper is that k-anonymization, when done "safely", and when preceded with a random sampling step, satisfies (epsilon, delta)-differential privacy with reasonable parameters. This result illustrates that "hiding in a crowd of k" indeed offers some privacy guarantees. We point out, however, that almost all existing k-anonymization algorithms in the literature are not "safe". Regarding the second question, we provide both positive and negative results. On the positive side, we show that adding a random-sampling pre-processing step to a differentially-private algorithm can greatly amplify the level of privacy protection. Hence, when given a dataset resulted from sampling, one can utilize a much large privacy budget. On the negative side, any privacy notion that takes advantage of the adversary's uncertainty, likely does not compose.
引用
收藏
页数:11
相关论文
共 50 条
[31]   Satisfying Privacy Requirements Before Data Anonymization [J].
Sun, Xiaoxun ;
Wang, Hua ;
Li, Jiuyong ;
Zhang, Yanchun .
COMPUTER JOURNAL, 2012, 55 (04) :422-437
[32]   Protecting Privacy in Knowledge Graphs With Personalized Anonymization [J].
Hoang, Anh-Tu ;
Carminati, Barbara ;
Ferrari, Elena .
IEEE TRANSACTIONS ON DEPENDABLE AND SECURE COMPUTING, 2024, 21 (04) :2181-2193
[33]   Anonymization Technique For Privacy Preservation In Social Networks [J].
Chavhan, Kalpana ;
Challagidad, Praveen S. .
2021 5TH INTERNATIONAL CONFERENCE ON ELECTRICAL, ELECTRONICS, COMMUNICATION, COMPUTER TECHNOLOGIES AND OPTIMIZATION TECHNIQUES (ICEECCOT), 2021, :131-136
[34]   Fundamental Limits of Location Privacy using Anonymization [J].
Takbiri, Nazanin ;
Houmansadr, Amir ;
Goeckel, Dennis L. ;
Pishro-Nik, Hossein .
2017 51ST ANNUAL CONFERENCE ON INFORMATION SCIENCES AND SYSTEMS (CISS), 2017,
[35]   Practical Anonymization for Protecting Privacy in Combinatorial Maps [J].
Chu, Dandan ;
Li, Yidong ;
Wang, Tao ;
Zhang, Lei ;
Shen, Hong .
2014 15TH INTERNATIONAL CONFERENCE ON PARALLEL AND DISTRIBUTED COMPUTING, APPLICATIONS AND TECHNOLOGIES (PDCAT 2014), 2014, :119-123
[36]   Limits of Location Privacy under Anonymization and Obfuscation [J].
Takbiri, Nazanin ;
Houmansadr, Amir ;
Goeckel, Dennis L. ;
Pishro-Nik, Hossein .
2017 IEEE INTERNATIONAL SYMPOSIUM ON INFORMATION THEORY (ISIT), 2017, :764-768
[37]   Data Anonymization for Privacy Aware Machine Learning [J].
Jaidan, David Nizar ;
Carrere, Maxime ;
Chemli, Zakaria ;
Poisvert, Remi .
MACHINE LEARNING, OPTIMIZATION, AND DATA SCIENCE, 2019, 11943 :725-737
[38]   Situating Anonymization Within a Privacy Risk Model [J].
Shapiro, Stuart S. .
2012 IEEE INTERNATIONAL SYSTEMS CONFERENCE (SYSCON), 2012, :651-656
[39]   Efficient k-Anonymization through Constrained Collaborative Clustering [J].
Zouinina, Sarah ;
Grozavu, Nistor ;
Bennani, Younes ;
Lyhyaoui, Abdelouahid ;
Rogovschi, Nicoleta .
2018 IEEE SYMPOSIUM SERIES ON COMPUTATIONAL INTELLIGENCE (IEEE SSCI), 2018, :405-411
[40]   Definition and Efficient Construction of Encrypted k-anonymization Scheme [J].
Yoshino, Masayuki ;
Suzuki, Takayuki ;
Naganuma, Ken ;
Sato, Hisayoshi .
PROCEEDINGS OF THE 5TH INTERNATIONAL CONFERENCE ON INFORMATION SYSTEMS SECURITY AND PRIVACY (ICISSP), 2019, :293-300