计算机科学 ›› 2020, Vol. 47 ›› Issue (4): 270-277.doi: 10.11896/jsjkx.190400098
王毛妮1,2, 彭长根1,2, 何文竹1,2, 丁兴1,2, 丁红发3
WANG Mao-ni1,2, PENG Chang-gen1,2, HE Wen-zhu1,2, DING Xing1,2, DING Hong-fa3
摘要: 差分隐私是数据发布、数据挖掘领域内隐私保护的重要工具,但其强度和效果仅能后验评估,且高度依赖于经验性选择的隐私预算。文中提出一种基于图论和互信息量的差分隐私量化模型和隐私泄露量计算方法。利用信息论通信模型重构了差分隐私保护框架,构造了差分隐私信息通信模型和隐私度量模型;基于图的距离正则和点传递提出隐私泄露互信息量化方法,证明并计算了差分隐私泄露量的信息量上界。分析和对比表明,该隐私泄露上界与原始数据集的属性数量、属性值数量以及隐私预算参数具有较好的函数关系,且计算限制条件较少。文中所提方法优于现有方法,能够为差分隐私算法的设计及评价、隐私泄露风险评估提供理论支撑。
中图分类号:
[1]LIANG Y,POOR H V,SHAMAI S.Information theoretic security[J].Foundations and Trends in Communications and Information Theory,2009,5(4/5):355-580. [2]CHAKRABORTY B,SADHYA D,VERMA S,et al.Information Theoretic Analysis of Privacy in a Multiple Query-Response Based Differentially Private Framework[C]//International Conference on Communication,Networks and Computing.Singapore:Springer,2018:262-272. [3]PADAKANDLA A,KUMAR P R,SZPANKOWSKI W.TheTrade-off between Privacy and Fidelity via Ehrhart Theory[J].arXiv:1803.03611,2018. [4]MIRONOV I.Rényi differential privacy[C]//2017 IEEE 30th Computer Security Foundations Symposium (CSF).IEEE,2017:263-275. [5]DALENIUS T.Towards a methodology for statistical disclosure control[J].Statistic Tidskrift,1977,15(2):429-444. [6]SWEENEY L.k-anonymity:A model for protecting privacy[J].International Journal of Uncertainty,Fuzziness and Knowledge-Based Systems,2002,10(5):557-570. [7]MACHANAVAJJHALA A,GEHRKE J,KIFER D,et al.l-diversity:Privacy beyond k-anonymity[C]//22nd International Conference on Data Engineering (ICDE’06).IEEE,2006:24-24. [8]DWORK C.Differential privacy[M]//Encyclopedia of Cryptography and Security.Boston,MA:Springer,2011:338-340. [9]DWORK C,MCSHERRY F,NISSIM K,et al.Calibrating noise to sensitivity in private data analysis[C]//Theory of cryptography conference.Berlin:Springer,2006:265-284. [10]MCSHERRY F,TALWAR K.Mechanism Design via Differential Privacy[C]//IEEE 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2007).ACM,2007:94-103. [11]ROTH A,ROUGHGARDEN T.Interactive privacy via the median mechanism[C]//Proceedings of the Forty-second ACM Symposium on Theory of Computing.ACM,2010:765-774. [12]HARDT M,ROTHBLUM G N.A multiplicative weights mechanism for privacy-preserving data analysis[C]//2010 IEEE 51st Annual Symposium on Foundations of Computer Science.IEEE,2010:61-70. [13]COVER T M,THOMAS J A.Information Theory and Statics//Elements of Theory.Hoboken,NJ:Wiley-Blockwell,2006:279-355. [14]DIAZ C,SEYS S,CLAESSENS J,et al.Towards measuring anonymity[C]//International Workshop on Privacy Enhancing Technologies.Berlin:Springer,2002:54-68. [15]PENG C G,DING H F,ZHU Y J,et al.Information entropy model of privacy protection and its measurement method[J].Journal of Software,2016,27(8):1891-1903. [16]WAGNER I,ECKHOFF D.Technical privacy metrics:a systematic survey[J].ACM Computing Surveys (CSUR),2018,51(3):1-45. [17]HEUSSER J,MALACARIA P.Applied quantitative information flow and statistical databases[C]//International Workshop on Formal Aspects in Security and Trust.Berlin:Springer,2009:96-110. [18]CLARKSON M R,SCHNEIDER F B.Quantification of integrity[J].Mathematical Structures in Computer Science,2015,25(2):207-258. [19]ALVIM M S,CHATZIKOKOLAKIS K,DEGANO P,et al.Differential Privacy versus Quantitative Information Flow[J].ar-Xiv:1012.4250,2010. [20]ALVIM M S,ANDRÉS M E,CHATZIKOKOLAKIS K,et al.Differential privacy:on the trade-off between utility and information leakage[C]//International Workshop on Formal Aspects in Security and Trust.Berlin:Springer,2011:39-54. [21]BARTHE G,KOPF B.Information-theoretic bounds for differentially private mechanisms[C]//2011 IEEE 24th Computer Security Foundations Symposium.IEEE,2011:191-204. [22]WANG W,LEI Y,ZHANG J.On the Relation Between Identifiability,Differential Privacy,and Mutual-Information Privacy[J].IEEE Transactions on Information Theory,2016,62(9):5018-5029. [23]CUFF P,YU L.Differential privacy as a mutual informationconstraint[C]//Proceedings of the 2016 ACM SIGSAC Confe-rence on Computer and Communications Security.ACM,2016:43-54. [24]DWORK C.A firm foundation for private data analysis[J].Communications of the ACM,2011,54(1):86-95. [25]BONDY J A,MURTY U S R.Graph theory with applications[M].London:Macmillan,1976. [26]BROUWER A E,HAEMERS W H.Distance-regular graphs[M]//Spectra of Graphs.New York:Springer,2012:177-185. |
[1] | 汤凌韬, 王迪, 张鲁飞, 刘盛云. 基于安全多方计算和差分隐私的联邦学习方案 Federated Learning Scheme Based on Secure Multi-party Computation and Differential Privacy 计算机科学, 2022, 49(9): 297-305. https://doi.org/10.11896/jsjkx.210800108 |
[2] | 黄觉, 周春来. 基于本地化差分隐私的频率特征提取 Frequency Feature Extraction Based on Localized Differential Privacy 计算机科学, 2022, 49(7): 350-356. https://doi.org/10.11896/jsjkx.210900229 |
[3] | 王健. 基于隐私保护的反向传播神经网络学习算法 Back-propagation Neural Network Learning Algorithm Based on Privacy Preserving 计算机科学, 2022, 49(6A): 575-580. https://doi.org/10.11896/jsjkx.211100155 |
[4] | 王美珊, 姚兰, 高福祥, 徐军灿. 面向医疗集值数据的差分隐私保护技术研究 Study on Differential Privacy Protection for Medical Set-Valued Data 计算机科学, 2022, 49(4): 362-368. https://doi.org/10.11896/jsjkx.210300032 |
[5] | 孔钰婷, 谭富祥, 赵鑫, 张正航, 白璐, 钱育蓉. 基于差分隐私的K-means算法优化研究综述 Review of K-means Algorithm Optimization Based on Differential Privacy 计算机科学, 2022, 49(2): 162-173. https://doi.org/10.11896/jsjkx.201200008 |
[6] | 董晓梅, 王蕊, 邹欣开. 面向推荐应用的差分隐私方案综述 Survey on Privacy Protection Solutions for Recommended Applications 计算机科学, 2021, 48(9): 21-35. https://doi.org/10.11896/jsjkx.201100083 |
[7] | 孙林, 平国楼, 叶晓俊. 基于本地化差分隐私的键值数据关联分析 Correlation Analysis for Key-Value Data with Local Differential Privacy 计算机科学, 2021, 48(8): 278-283. https://doi.org/10.11896/jsjkx.201200122 |
[8] | 张学军, 杨昊英, 李桢, 何福存, 盖继扬, 鲍俊达. 融合语义位置的差分私有位置隐私保护方法 Differentially Private Location Privacy-preserving Scheme withSemantic Location 计算机科学, 2021, 48(8): 300-308. https://doi.org/10.11896/jsjkx.200900198 |
[9] | 陈天荣, 凌捷. 基于特征映射的差分隐私保护机器学习方法 Differential Privacy Protection Machine Learning Method Based on Features Mapping 计算机科学, 2021, 48(7): 33-39. https://doi.org/10.11896/jsjkx.201200224 |
[10] | 王乐业. 群智感知中的地理位置本地化差分隐私机制:现状与机遇 Geographic Local Differential Privacy in Crowdsensing:Current States and Future Opportunities 计算机科学, 2021, 48(6): 301-305. https://doi.org/10.11896/jsjkx.201200223 |
[11] | 彭春春, 陈燕俐, 荀艳梅. 支持本地化差分隐私保护的k-modes聚类方法 k-modes Clustering Guaranteeing Local Differential Privacy 计算机科学, 2021, 48(2): 105-113. https://doi.org/10.11896/jsjkx.200700172 |
[12] | 雷阳, 姜瑛. 云计算环境下关联节点的异常判断 Anomaly Judgment of Directly Associated Nodes Under Cloud Computing Environment 计算机科学, 2021, 48(1): 295-300. https://doi.org/10.11896/jsjkx.191200186 |
[13] | 吴英杰, 黄鑫, 葛晨, 孙岚. 差分隐私流数据实时发布中的自适应参数优化 Adaptive Parameter Optimization for Real-time Differential Privacy Streaming Data Publication 计算机科学, 2019, 46(9): 99-105. https://doi.org/10.11896/j.issn.1002-137X.2019.09.013 |
[14] | 林朗, 张自力. 基于多头绒泡菌的贝叶斯网络结构学习 Bayesian Structure Learning Based on Physarum Polycephalum 计算机科学, 2019, 46(9): 206-210. https://doi.org/10.11896/j.issn.1002-137X.2019.09.030 |
[15] | 李兰, 杨晨, 王安福. 差分隐私模型中隐私参数ε的选取研究 Study on Selection of Privacy Parameters ε in Differential Privacy Model 计算机科学, 2019, 46(8): 201-205. https://doi.org/10.11896/j.issn.1002-137X.2019.08.033 |
|