Computer Science ›› 2020, Vol. 47 ›› Issue (4): 270-277.doi: 10.11896/jsjkx.190400098

• Information Security • Previous Articles     Next Articles

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

CLC Number: 

  • 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] TANG Ling-tao, WANG Di, ZHANG Lu-fei, LIU Sheng-yun. Federated Learning Scheme Based on Secure Multi-party Computation and Differential Privacy [J]. Computer Science, 2022, 49(9): 297-305.
[2] HUANG Jue, ZHOU Chun-lai. Frequency Feature Extraction Based on Localized Differential Privacy [J]. Computer Science, 2022, 49(7): 350-356.
[3] WANG Jian. Back-propagation Neural Network Learning Algorithm Based on Privacy Preserving [J]. Computer Science, 2022, 49(6A): 575-580.
[4] WANG Mei-shan, YAO Lan, GAO Fu-xiang, XU Jun-can. Study on Differential Privacy Protection for Medical Set-Valued Data [J]. Computer Science, 2022, 49(4): 362-368.
[5] KONG Yu-ting, TAN Fu-xiang, ZHAO Xin, ZHANG Zheng-hang, BAI Lu, QIAN Yu-rong. Review of K-means Algorithm Optimization Based on Differential Privacy [J]. Computer Science, 2022, 49(2): 162-173.
[6] DONG Xiao-mei, WANG Rui, ZOU Xin-kai. Survey on Privacy Protection Solutions for Recommended Applications [J]. Computer Science, 2021, 48(9): 21-35.
[7] SUN Lin, PING Guo-lou, YE Xiao-jun. Correlation Analysis for Key-Value Data with Local Differential Privacy [J]. Computer Science, 2021, 48(8): 278-283.
[8] ZHANG Xue-jun, YANG Hao-ying, LI Zhen, HE Fu-cun, GAI Ji-yang, BAO Jun-da. Differentially Private Location Privacy-preserving Scheme withSemantic Location [J]. Computer Science, 2021, 48(8): 300-308.
[9] CHEN Tian-rong, LING Jie. Differential Privacy Protection Machine Learning Method Based on Features Mapping [J]. Computer Science, 2021, 48(7): 33-39.
[10] WANG Le-ye. Geographic Local Differential Privacy in Crowdsensing:Current States and Future Opportunities [J]. Computer Science, 2021, 48(6): 301-305.
[11] PENG Chun-chun, CHEN Yan-li, XUN Yan-mei. k-modes Clustering Guaranteeing Local Differential Privacy [J]. Computer Science, 2021, 48(2): 105-113.
[12] LEI Yang, JIANG Ying. Anomaly Judgment of Directly Associated Nodes Under Cloud Computing Environment [J]. Computer Science, 2021, 48(1): 295-300.
[13] WU Ying-jie, HUANG Xin, GE Chen, SUN Lan. Adaptive Parameter Optimization for Real-time Differential Privacy Streaming Data Publication [J]. Computer Science, 2019, 46(9): 99-105.
[14] LIN Lang, ZHANG Zi-li. Bayesian Structure Learning Based on Physarum Polycephalum [J]. Computer Science, 2019, 46(9): 206-210.
[15] LI Lan, YANG Chen, WANG An-fu. Study on Selection of Privacy Parameters ε in Differential Privacy Model [J]. Computer Science, 2019, 46(8): 201-205.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!