计算机科学 ›› 2020, Vol. 47 ›› Issue (4): 270-277.doi: 10.11896/jsjkx.190400098

• 信息安全 • 上一篇    下一篇

基于图论与互信息量的差分隐私度量模型

王毛妮1,2, 彭长根1,2, 何文竹1,2, 丁兴1,2, 丁红发3   

  1. 1 贵州大学计算机科学与技术学院公共大数据国家重点实验室 贵阳550025;
    2 贵州大学密码学与数据安全研究所 贵阳550025;
    3 贵州财经大学信息学院 贵阳550025
  • 收稿日期:2019-04-17 出版日期:2020-04-15 发布日期:2020-04-15
  • 通讯作者: 丁红发(hongfa.ding@foxmail.com)
  • 基金资助:
    国家自然科学基金(U1836205,61662009,61772008,11761020);贵州省科技计划项目(黔科合重大专项字3001;黔科合重大专项字3007;黔科合重大专项字3002;黔科合支撑2004;黔科合支撑2159;贵州省教育厅青年科技人才成长项目(黔教合KY字171)

Privacy Metric Model of Differential Privacy via Graph Theory and Mutual Information

WANG Mao-ni1,2, PENG Chang-gen1,2, HE Wen-zhu1,2, DING Xing1,2, DING Hong-fa3   

  1. 1 Sate Key Laboratory of Pubic Big Data,College of Computer Science and Technology,Guizhou University,Guiyang 550025,China;
    2 Institute of Cryptography and Data Security,Guizhou University,Guiyang 550025,China;
    3 School of Information,Guizhou University of Finance and Economics,Guiyang 550025,China
  • Received:2019-04-17 Online:2020-04-15 Published:2020-04-15
  • Contact: DING Hong-fa,born in 1988,doctor,is a member of China Computer Federation.His main research interests include privacy and data security.
  • About author:WANG Mao-ni,born in 1994,graduate student.Her main research interests include privacy and data security.
  • Supported by:
    This work was supported by the National Natural Science Foundation of China(U1836205,61662009,61772008,11761020),Science and Techno-logy Program of Guizhou Province(Guizhou-Science-Contract-Major-Program 3001,Guizhou-Science-Contract-Major-Program 3007,Guizhou-Science-Contract-Major-Program 3002,Guizhou-Science-Contract-Support 2004,Guizhou-Science-Contract-Support 2159,and Youth Science and Technology Talents Development Project of Guizhou Education Department(Guizhou-Education-Contract171)

摘要: 差分隐私是数据发布、数据挖掘领域内隐私保护的重要工具,但其强度和效果仅能后验评估,且高度依赖于经验性选择的隐私预算。文中提出一种基于图论和互信息量的差分隐私量化模型和隐私泄露量计算方法。利用信息论通信模型重构了差分隐私保护框架,构造了差分隐私信息通信模型和隐私度量模型;基于图的距离正则和点传递提出隐私泄露互信息量化方法,证明并计算了差分隐私泄露量的信息量上界。分析和对比表明,该隐私泄露上界与原始数据集的属性数量、属性值数量以及隐私预算参数具有较好的函数关系,且计算限制条件较少。文中所提方法优于现有方法,能够为差分隐私算法的设计及评价、隐私泄露风险评估提供理论支撑。

关键词: 差分隐私, 汉明图, 互信息, 隐私度量, 隐私泄露

Abstract: Differential privacy is an important tool for privacy preserving in many fields,such as data publishing and data mining.However,the strength and effectiveness of differential privacy cannot be evaluated previously,and highly rely on empirical selection of privacy budget.To this end,a privacy metric model and a privacy leakage method via graph theory and mutual information were proposed.This work models differential privacy as an information theoretic communication channel,and constructs an information channel and privacy metric model for differential privacy.Then,a mutual information based privacy metric method is proposed by employing the distance-regular and vertex-transitive of graphs,the upper bound of this metric is proofed,and an explicit formula is proposed for the bound.Delicate analysis and comparison show that the proposed upper bound has a function relationship limited by fewer computational constraints among the original dataset’s attributes,attribute values and privacy budget.This work benefits more than related works,and provides theoretical foundation for algorithm design,algorithm evaluation,and privacy assessment.

Key words: Differential privacy, Hamming graph, Mutual information, Privacy leakage, Privacy metric

中图分类号: 

  • TP309
[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
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!