概率系统差分隐私研究综述

曹永知

PDF(745 KB)
PDF(745 KB)
广州大学学报(自然科学版) ›› 2019, Vol. 18 ›› Issue (4) : 75-82.

概率系统差分隐私研究综述

  • 曹永知
作者信息 +

A survey on differential privacy in probabilistic systems

  • CAO Yong-zhi
Author information +
History +

摘要

尽管大数据分析在许多领域展现出巨大价值,但目前大数据的发展仍然面临着诸多问题,隐私保护便是公认的关键问题之一.在大数据背景下,数据间存在着复杂的关联性.为防止攻击者利用先验知识获取隐私,Dwork提出了差分隐私概念.近年来,差分隐私受到了广泛关注,成为有望解决数据隐私问题的一个重要研究方向.值得注意的是,在诸如执行MapReduce计算的Airavat等系统中,差分隐私技术仅用于构件层面.显然,保护单个构件的隐私并不意味着保护了整个系统的隐私.为此,国内外许多学者从系统层面研究了隐私保护.文章在简要回顾传统差分隐私提出的背景、定义及理论方面的进展后,从形式化方法的视角,综述概率系统差分隐私的最新研究进展和研究方向,以期促进该领域的进一步研究.

Abstract

Although big data analysis has shown great value in some fields, the current development of big data is still faced with many problems. Among others, privacy preserving is recognized as a key issue. In the context of big data, there is an intricate relevance among data. To prevent an attacker from acquiring privacy by using a priori knowledge, Dwork proposed the concept of differential privacy. In recent years, differential privacy has been broadly concerned and has become an important research field to solve the privacy problem in the context of big data. However, it is worth noting that, in some systems such as Airavat performing MapReduce computations, the differential privacy technology is only used in some components. Clearly, preserving the privacy of components is not sufficient for the privacy preserving of an entire system. To this end, some scholars have made many efforts to ensure privacy at the system level. In this paper, after briefly reviewing the background, definition, and theoretical progress of the classical differential privacy, we survey the latest developments and research directions of differential privacy in probabilistic systems from the perspective of formal methods, with a view to promoting further research in this field.

关键词

隐私保护 / 差分隐私 / 形式化方法 / 概率自动机 / 概率标号迁移系统 / 概率进程代数 / 马尔可夫链 / 模型检测

Key words

privacy preserving / differential privacy / formal methods / probabilistic automaton / probabilistic labelled transition system / probabilistic process algebra / Markov chain / model checking

引用本文

导出引用
曹永知. 概率系统差分隐私研究综述. 广州大学学报(自然科学版). 2019, 18(4): 75-82
CAO Yong-zhi. A survey on differential privacy in probabilistic systems. Journal of Guangzhou University(Natural Science Edition). 2019, 18(4): 75-82

参考文献

[1] 冯登国, 张敏, 李昊. 大数据安全与隐私保护[J]. 计算机学报, 2014, 37(1): 246-258.
[2] 赵岑, 李梦然, 金日峰. 大数据时代关于隐私的思考[J]. 科学通报, 2015, 60(5): 450-452.
[3] 吴小同. 大数据环境下隐私保护及其关键技术研究[D]. 南京: 南京大学, 2017.
[4] 黄刘生, 田苗苗, 黄河. 大数据隐私保护密码技术研究综述[J]. 软件学报, 2015, 26(4): 945-959.
[5] 孟小峰, 慈祥. 大数据管理:概念、技术与挑战[J]. 计算机研究与发展, 2013, 50(1): 146-169.
[6] 孟小峰, 张啸剑. 大数据隐私管理[J]. 计算机研究与发展, 2015,52(2): 265-281.
[7] 高强, 张凤荔, 王瑞锦,等. 轨迹大数据: 数据处理关键技术研究综述[J]. 软件学报, 2017, 28(4): 959-992.
[8] 李昊, 张敏, 冯登国, 等. 大数据访问控制研究[J]. 计算机学报, 2017, 40(1): 72-91.
[9] 王璐, 孟小峰. 位置大数据隐私保护研究综述[J]. 软件学报, 2014, 25(4): 693-712.
[10]Wang Q, Zhang Y, Lu X, et al. Real-time and spatio-temporal crowd-sourced social network data publishing with differential privacy[J]. IEEE Transactions on Dependable & Secure Computing, 2018, 15(4): 591-606.
[11]Zhang H, Shu Y C, Cheng P, et al. Privacy and performance trade-off in cyber-physical systems[J]. IEEE Network, 2016, 30(2): 62-66.
[12]黄学臻. 隐私保护数据发布的模型与方法研究[D]. 北京:北京交通大学, 2015.
[13]Dwork C. Differential privacy[C]∥Proceedings of the 33rd International Colloquium on Automata, Languages and Programming. Berlin, Heidelberg: Springer, 2006, 26(2): 1-12.
[14]Dwork C, Roth A. The algorithmic foundations of differential privacy[J]. Foundations & Trends® in Theoretical Computer Science, 2014, 9(3-4): 211-407.
[15]Dwork C. Differential privacy: A survey of results[C]∥ International Conference on Theory and Applications of Models of Computation. Berlin, Heidelberg: Springer, 2008:1-19.
[16]仝伟, 毛云龙, 陈庆军,等. 抗大数据分析的隐私保护: 研究现状与进展[J]. 网络与信息安全学报, 2016, 2(4): 44-55.
[17]李效光, 李晖, 李凤华,等. 差分隐私综述[J]. 信息安全学报, 2018, 3(5): 96-108.
[18]朱天清, 何木青, 邹德清. 基于差分隐私的大数据隐私保护[J]. 信息安全研究, 2015, 1(3): 224-229.
[19]李杨, 温雯, 谢光强. 差分隐私保护研究综述[J]. 计算机应用研究, 2012, 29(9): 3201-3205.
[20]高志强, 王宇涛. 差分隐私技术研究进展[J]. 通信学报, 2017, 38(Z1): 151-155.
[21]Zhu T, Li G, Zhou W, et al. Differentially private data publishing and analysis: A survey[J]. IEEE Transactions on Knowledge Data Engineering, 2017, 29(8): 1619-1638.
[22]熊平, 朱天清, 王晓峰. 差分隐私保护及其应用[J]. 计算机学报, 2014, 37(1): 101-122.
[23]霍峥, 孟小峰. 轨迹隐私保护技术研究[J]. 计算机学报, 2011, 34(10): 1820-1830.
[24]叶青青, 孟小峰, 朱敏杰, 等. 本地化差分隐私研究综述[J]. 软件学报, 2018, 29(7): 159-183.
[25]Barthe G, Fong N, Gaboardi M, et al. Advanced probabilistic couplings for differential privacy[C]∥Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security. New York: ACM, 2016: 55-67.
[26]Dankar F K, Emam K E. Practicing differential privacy in health care: A review[J]. Transactions on Data Privacy, 2013, 6(1): 35-67.
[27]Apple. Engineering privacy for your users[EB/OL]. (2016-07-09). https://developer.apple.com/videos/play/wwdc2016/709/.
[28]Erlingsson ú, Pihur V, Korolova A. Rappor: Randomized aggregatable privacy-preserving ordinal response[C]∥Proceedings of the 2014 ACM SIGSAC Conference on Computer and Communications Security. New York:ACM, 2014: 1054-1067.
[29]Tang J, Korolova A, Bai X L, et al. Privacy loss in Apple's implementation of differential privacy on MacOS 10.12[EB/OL]. CoRR, 2017, abs/1709.02753.
[30]Roy I, Setty S T V, Kilzer A, et al. Airavat: Security and privacy for MapReduce[C]∥Proceedings of the 7th USENIX Symposium on Networked Systems Design and Implementation. 2010, 10: 297-312.
[31]Dwork C, Naor M, Pitassi T, et al. Differential privacy under continual observation[C]∥Proceedings of the Forty-Second ACM Symposium on Theory of Computing. New York:ACM, 2010: 715-724.
[32]Chen W E, Cao Y Z, Wang H P. Conditional anonymity with non-probabilistic adversary[J]. Information Science, 2015, 324: 32-43.
[33]Palamidessi C. Anonymity in probabilistic and nondeterministic systems[J]. Electronic Notes in Theoretical Computer Science, 2006, 162: 277-279.
[34]Weinberg Z, Wang J, Yegneswaran V, et al. StegoTorus: A camouflage proxy for the Tor anonymity system[C]∥Proceedings of the 2012 ACM Conference on Computer and Communications Security. New York:ACM, 2012: 109-120.
[35]Andrés M E. Quantitative analysis of information leakage in probabilistic and nondeterministic systems[EB/OL]. CoRR, 2011, abs/1111.2760.
[36]Mittal P, Borisov N. Information leaks in structured peer-to-peer anonymous communication systems[J]. ACM Transactions on Information & System Security, 2012, 15(1): 5.
[37]Cao Y Z. Reliability of mobile processes with noisy channels[J]. IEEE Transactions on Computers, 2012, 61(9): 1217-1230.
[38]Pendleton M, Garcia-Lebron R, Cho J H, et al. A survey on systems security metrics[J]. ACM Computing Surveys, 2017, 49(4): 62.
[39]Soria-Comas J, Domingo-Ferrer J. Big data privacy: Challenges to privacy principles and models[J]. Data Science and Engineering, 2016, 1(1): 21-28.
[40]Gaboardi M, Haeberlen A, Hsu J, et al. Linear dependent types for differential privacy[C]∥ACM SIGPLAN Notices. New York:ACM, 2013, 48(1): 357-370.
[41]Ye H, Cheng X, Yuan M, et al. A survey of security and privacy in big data[C]∥International Symposium on Communications & Information Technologies. Piscataway: IEEE, 2016: 268-272.
[42]Mayer-Schönberger V, Cukier K. Big data: A revolution that will transform how we live, work, and think[M]. Boston: Houghton Mifflin Harcourt, 2013.
[43]Aggarwal C C, Philip S Y. A general survey of privacy-preserving data mining models and algorithms[M]. Boston: Springer, 2008: 11-52.
[44]Fung B C M, Wang K, Chen R, et al. Privacy-preserving data publishing: A survey of recent developments[J]. ACM Computing Surveys, 2010, 42(4): 1-53.
[45]周水庚, 李丰, 陶宇飞,等. 面向数据库应用的隐私保护研究综述[J]. 计算机学报, 2009, 32(5): 847-861.
[46]Machanavajjhala A, Gehrke J, Kifer D, et al. I-diversity: Privacy beyond k-anonymity[C]∥22nd International Conference on Data Engineering (ICDE'06). Piscataway: IEEE, 2006: 24.
[47]Sweeney L. K-anonymity: A model for protecting privacy[J]. International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems, 2002, 10(5): 557-570.
[48]王智慧, 许俭, 汪卫.等. 一种基于聚类的数据匿名方法[J]. 软件学报, 2010, 21(4): 680-693.
[49]Jagadish H V, Gehrke J, Labrinidis A, et al. Big data and its technical challenges[J]. Communications of the ACM, 2014, 57(7): 86-94.
[50]Lin C, Wang P Y, Song H B, et al. A differential privacy protection scheme for sensitive big data in body sensor networks[J]. Annals of Telecommunications, 2016, 71(9/10): 465-475.
[51]Dwork C, McSherry F, Nissim K, et al. Calibrating noise to sensitivity in private data analysis[C]∥Theory of Cryptography Conference. Berlin, Heidelberg: Springer, 2006: 265-284.
[52]Geng Q, Viswanath P. The optimal mechanism in differential privacy: Multidimensional Setting[C]∥2014 IEEE International Symposium on Information Theory. Piscataway: IEEE, 2014: 2371-2375.
[53]Geng Q, Viswanath P. Optimal noise adding mechanisms for approximate differential privacy[J]. IEEE Transactions on Information Theory, 2016, 62(2): 952-969.
[54]Barthe G, Gaboardi M, Hsu J, et al. Programming language techniques for differential privacy[J]. ACM SIGLOG News, 2016, 3(1): 34-53.
[55]Reed J, Pierce B C. Distance makes the types grow stronger: A calculus for differential privacy[C]∥ACM SIGPLAN Notices. New York:ACM, 2010, 45(9): 157-168.
[56]Banerjee S, Hegde N, Massoulié L. The price of privacy in untrusted recommender systems[J]. IEEE Journal of Selected Topics in Signal Processing, 2015, 9(7): 1319-1331.
[57]Friedman A, Berkovsky S, Kaafar M A. A differential privacy framework for matrix factorization recommender systems[J]. User Model and User-Adapted Interaction, 2016, 26(5): 425-458.
[58]Naveed M, Ayday E, Clayton E W, et al. Privacy in the genomic era[J]. ACM Computing Surveys, 2015, 48(1): 1-44.
[59]Task C, Clifton C. A guide to differential privacy theory in social network analysis[C]∥2012 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining. Piscataway: IEEE, 2012: 411-417.
[60]Zhao Y, Wang X, Jiang X, et al. Choosing blindly but wisely: Differentially private solicitation of DNA datasets for disease marker discovery[J]. Journal of the American Medical Informatics Association: JAMIA, 2015, 22(1): 100-108.
[61]Kargl F, Friedman A, Boreli R. Differential privacy in intelligent transportation systems[C]∥Proceedings of the Sixth ACM Conference on Security and Privacy in Wireless and Mobile Networks. New York: ACM, 2013: 107-112.
[62]Mir D J, Isaacman S, Cáceres R, et al. Dp-where: Differentially private modeling of human mobility[C]∥2013 IEEE International Conference on Big Data. Piscataway: IEEE, 2013: 580-588.
[63]Fan L, Xiong L. An adaptive approach to real-time aggregate monitoring with differential privacy[J]. IEEE Transactions on Knowledge & Data Engineering, 2014, 26(9): 2094-2106.
[64]Ny J L, Pappas G J. Differentially private filtering[J]. IEEE Transactions on Automatic Control, 2014, 59(2): 341-354.
[65]Bun M M. New separations in the complexity of differential privacy[D]. Boston: Harvard University, 2016.
[66]Hardt M, Talwar K. On the geometry of differential privacy[C]∥Proceedings of the Forty-Second ACM Symposium on Theory of Computing. New York:ACM, 2010: 705-714.
[67]Mcsherry F, Talwar K. Mechanism design via differential privacy[C]∥ 2007 IEEE 48th Annual Symposium on Foundations of Computer Science. Piscataway: IEEE, 2007, 7: 94-103.
[68]Li N, Qardaji W, Su D, et al. Membership privacy: A unifying framework for privacy definitions[C]∥Proceedings of the 2013 ACM SIGSAC Conference on Computer & Communications Security. New York:ACM, 2013: 889-900.
[69]Duchi J C, Jordan M I, Wainwright M J. Local privacy and statistical minimax rates[C]∥2013 IEEE 54th Annual Symposium on Foundations of Computer Science. Piscataway: IEEE, 2013: 429-438.
[70]Chatzikokolakis K, Andrés M E, Bordenabe N E, et al. Broadening the scope of differential privacy using metrics[C]∥ International Symposium on Privacy Enhancing Technologies Symposium. Berlin, Heidelberg: Springer,2013: 82-102.
[71]Dwork C, Rothblum G N. Concentrated differential privacy[EB/OL]. CoRR, 2016, abs/1603.01887.
[72]Soria-Comas J, Domingo-Ferrer J, Sánchez D, et al. Individual differential privacy: A utility-preserving formulation of differential privacy guarantees[J]. IEEE Transactions on Information Forensics & Security, 2017, 12(6): 1418-1429.
[73]Tschantz M C, Datta A, Kaynar D. Differential privacy for probabilistic systems[R]. Technical Report CMU-CyLab-09-008, CyLab, Carnegie Mellon University, 2009.
[74]Tschantz M C, Kaynar D, Datta A. Formal verification of differential privacy for interactive systems[J]. Electronic Notes in Theoretical Computer Science, 2011, 276:61-79.
[75]Tschantz M C, Kaynar D, Datta A. Formal verification of differential privacy for interactive systems[EB/OL]. CoRR, 2011, abs/1101.2819.
[76]Xu L L. Modular reasoning about differential privacy in a probabilistic process calculus[C]∥International Symposium on Trustworthy Global Computing.Berlin, Heidelberg: Springer, 2012: 198-212.
[77]许丽丽, 并发系统差分隐私的形式化验证[D]. 北京: 中国科学院大学, 2014.
[78]Xu L L, Chatzikokolakis K, Lin H M. Metrics for differential privacy in concurrent systems[C]∥International Conference on Formal Techniques for Distributed Objects, Components, and Systems. Berlin, Heidelberg: Springer, 2014: 199-215.
[79]Xu L L, Lin H M. Complete proof systems for amortised probabilistic bisimulations[J]. Journal of Computer Science and Technology, 2016, 31(2): 300-316.
[80]Desharnais J, Jagadeesan R, Gupta V, et al. The metric analogue of weak bisimulation for probabilistic processes[C]∥Proceedings of the 17th Annual IEEE Symposium on Logic in Computer Science. Piscataway: IEEE, 2002: 413-422.
[81]Gruska D. Differential privacy and security[J]. Fundam Inform, 2016, 143(1/2): 73-87.
[82]Yang J N, Cao Y Z, Wang H P. Differential privacy in probabilistic systems[J]. Information and Computation, 2017, 254: 84-104.
[83]杨建楠, 概率系统中的差分隐私[D]. 北京: 北京大学, 2019.
[84]Liu D, Wang B Y, Zhang L. Model checking differentially private properties[C]∥Asian Symposium on Programming Languages and Systems. Cham: Springer, 2018: 394-414.
[85]Castiglioni V, Chatzikokolakis K, Palamidessi C. A logical characterization of differential privacy via behavioral metrics[C]∥International Conference on Formal Aspects of Component Software. Cham: Springer, 2018: 75-96.
[86]Huang Z, Wang Y, Mitra S, et al. On the cost of differential privacy in distributed control systems[C]∥Proceedings of the 3rd International Conference on High Confidence Networked Systems. New York:ACM, 2014: 105-114.
[87]Zhang D, Kifer D. LightDP: Towards automating differential privacy proofs[C]∥ACM SIGPLAN Notices. New York:ACM, 2017, 52(1): 888-901.
[88]Albarghouthi A, Hsu J. Synthesizing coupling proofs of differential privacy[C]∥Proceedings of the ACM on Programming Languages. New York: ACM, 2018, DOI: 10.1145/3158146.

基金

国家自然科学基金资助项目(61772035)
PDF(745 KB)

473

Accesses

0

Citation

Detail

段落导航
相关文章

/