The Algorithmic Foundations of Differential Privacy

所需积分/C币:41 2018-03-15 22:05:47 1.29MB PDF
收藏 收藏
举报

差分隐私基础 Dwork
4 Releasing Linear Queries with Correlated Error 66 4.1 An offline algorithm Smallb 70 4.2 An online mechanism: private multiplicative weights 76 4.3 Bibliographical notes 86 5 Generalizations 88 5.1 Mechanisms via ar-nets 5.2 The iterative construction mechanism 91 5.3 Connections 109 5.4 Bibliographical notes 115 6 Boosting for Queries 117 6. 1 The boosting for queries algorithm 119 6.2 Base synopsis generators 6.3 Bibliographical notes 139 7 When Worst-Case Sensitivity is Atypical 40 7. 1 Subsample and aggregate 140 7.2 Propose-test-Release 113 7.3 Stability and privacy 150 8 Lower Bounds and Separation Results 158 8. 1 Reconstruction attacks 159 8.2 Lower bounds for differential privacy 164 8.3 Bibliographic notes 170 9 Differential Privacy and Computational Complexity 172 9. 1 Polynomial time curators 174 9.2 Some hard-to-Syntheticize distributions 177 9.3 Polynomial time adversaries 185 9.4 Bibliographic notes 187 10 Differential Privacy and Mechanism Design 189 10.1 Differential privacy as a solution concept 191 10.2 Differential privacy as a tool in mechanism design 193 10.3 Mechanism design for privacy aware agents 204 10.4 Bibliographical notes 11 Differential Privacy and Machine Learning 216 11.1 The sample complexity of differentially private machine learning 219 11.2 Differentially private online learning 222 11.3 Empirical risk minimization 227 11.4 Bibliographical notes .230 12 Additional Models 231 12. 1 The local model 232 12.2 Pan-private streaming model 237 12.3 Continual observation 240 12.4 Average case error for query release 248 12.5 Bibliographical notes 252 13 Reflections 254 13.1 Toward practicing privacy 254 13.2 The differential privacy lens 258 A ppen 260 a The gaussian mechanism 261 A 1 Bibliographic notes 266 B Composition Theorems for(E, 8)-DP 267 B. 1 Extension of theorem 3.16 267 Acknowledgments 269 References 270 Abstract The problem of privacy-prcscrving data analysis has a long history spanning multiple disciplines. As electronic data about individuals becomes increasingly detailed, and as technology enables ever more powerful collection and curation of these data, the need increases for a robust, meaningful, and mathematically rigorous definition of privacy together with a computationally rich class of algorithms that satisfy this definition. Differential Privacy is such a definition After motivating and discussing the meaning of differential privacy, the preponderance of this monograph is devoted to fundamental tech niques for achieving differential privacy, and application of these tech niques in creative combinations, using the query-release problem as an ongoing example. a key point is that, by rethinking the computational goal, one can often obtain far better results than would be achieved by methodically replacing each step of a non-private computation with a differentially private implementation. Despite some astonishingly pow erful computational results, there are still fundamental limitations not just on what can be achieved with differential privacy but on what can bc achicved with any mcthod that protects against a complcte breakdown in privacy. Virtually all the algorithms discussed herein maintain differential privacy against adversaries of arbitrary compu- tational power. Certain algorithms are computationally intensive, oth- ers are efficient. Computational complexity for the adversary and the ,lgorithm are both discussed We then turn from fundamentals to applications other than query release, discussing differentially private methods for mechanism design and machine learning. The vast majority of the literature on differen tially private algorithms considers a single, static, database that is sub jcct to many analyscs. Diffcrcntial privacy in other modcls, including distributed databases and computations on data streams is discussed Finally, we note that this work is meant as a thorough introduc- tion to the problems and techniques of diffcrcntial privacy, but is not ntended to be an exhaustive survey- there is by now a vast amount of work in differential privacy, and we can cover only a small portion of it C. Dwork and A. Roth. The Algorithmic Foundations of differential Privacy. Foun dations and Trends@ in'Theoretica l Computer Science, vol ,nos.3-4,pp.2l1-407, 2014. DOI:10.1561/040000042 Preface Thc problem of privacy-proscrving data analysis has a long history spanning multiple disciplines. As electronic data about individuals Become es increasingly detailed, and as technology enables ever more powerful collection and curation of these data, the need increases for a robust, meaningful, and mathematically rigorous definition of privacy, together with a computationa.l ly rich class of algorithms that sat isfy this definition. Differential Privacy is such a definition After motivating and discussing the meaning of differential privacy, the preponderance of the book is devoted to fundamental techniques for achieving diferential privacy, and applicalion of these lechniques in crcativc combinations(Scctions 3-7), using the qucry-rclcase problcm as an ongoing example. a key point is that, by rethinking the com- putational goal, one can often obtain far better results than would be achieved by methodically replacing each step of a non-private compu- tation with a differentially private implementation Despite some astonishingly powerful computational results, there are still fundamental limitations- not just on what can be achieved with differential privacy but on what can be achieved with any method that protects against a complete breakdown in privacy( Section 8) Virtually all the algorithms discussed in this book maintain diffcrcntial privacy against adversaries of arbitrary computati lona power. Certain algorithms are computationally intensive, others are efficient. Coinpulalional complexity for Che adversary and the algo- rithm arc both discusscd in Scction 9 In Sections 10 and ll we turn from fundamentals to applications other than query-release, discussing differentially private methods for mechanism design and machine learning. The vast majority of the lit erature on differentially private algorithms considers a single. static database that is subject to many analyses. Differential privacy in other models, including distributed databases and computations on data streams is discussed in Section 12 Finally. we note that this book is meant as a thorough introduc- Lion to the problems and techniques of diferential privacy, but is Ilot intended to be an exhaustive survey there is by now a vast amount of work in differential privacy, and we can cover only a small portion of it The Promise of Differential Privacy Differential privacy"describes a promise, made by a data holder, or curator, to a data subject: " You will not be affected adversely or oth- erwise, by allowing your data to be used in any study or analysis no matter what other studies, data sets, or information sources, are available At their best, differentially private database mechanisms can make confidential data widely available for accurate data analysis without resorting to data clean rooms, data usage agreements, data pro tection plans, or restricted views. Nonetheless, data utility will eventu- ally be consumed: the Fundamental law of Information Recovery states that overly accurate answers to too many questions will destroy privacy in a spectacular way. I The goal of algorithmic research on differential privacy is to postpone this inevitability as long as possible Differential privacy addresses the paradox of learning nothing about an individual while learning useful information about a population. A medical database may teach us that smoking causes cancer, affecting an insurance conpally's view of a Smokers long-berIn Inedical costs Has the smoker becn harmed by the analysis? Perhaps his insurance This result, proved in Section 8.1, applies to all techniques for privacy-preserving data analysis, and not just to differential privacy The Promise of Differential Privacy premiums may rise, il the insurer knows he sinokes. He may also be helped- learning of his health risks, hc enters a smoking cessation program. Has the smokers privacy been compromised? It is certainly che case that more is known about him after the study than was known before, but was his information "leaked"? Differential privacy will take the view that it was not, with the rationale that the impact on the smoker is the same independent of whether or not he was in the study It is the conclusions reached in the study that affect the smoker, not his presence or absence in the data set Differential privacy ensures that the same conclusions, for example SInoking causes cancer, will be reached, independent of whether any individual opts into or opts out of the data set. Specifically, it ensures that any sequence of outputs (responses to queries) is"essentially equally likely to occur, independent of the presence or absence of any individual. Here, the probabilities are taken over random choices made by the privacy mechanism(something controlled by the data curator) and the term"essentially" is captured by a parameter, E. a smaller a will yield better privacy (and less accurate responses) Diffcrcntial privacy is a dcfinition, not an algorithm. For a given computational task T and a given value of e there will be many differ entially private algorithms for achieving T in an E-differentially private manner. Some will have better accuracy than others. When e is small finding a highly accurate E-differentially private algorithm for T can be difficult, much as finding a numerically stable algorithm for a specific computational task can require effort 1.1 Privacy-preserving data analysis Differential privacy is a definition of privacy tailored to the problem of privacy-preserving dala analysis. We brielly address some concerns with other approaches to this problem Data Cannot be Fully Anonymized and Remain Useful. Generally speaking, the richor the data, the morc intercsting and uscful it is This has led to notions of“ anonymization”and“ removal of person ally identifiable infornation, where the hope is that portions of the

...展开详情
试读 127P The Algorithmic Foundations of Differential Privacy
立即下载 低至0.43元/次 身份认证VIP会员低至7折
一个资源只可评论一次,评论内容不能少于5个字
weixin_41634896 很好的书,推荐
2019-07-21
回复
关注 私信 TA的资源
上传资源赚积分,得勋章
最新推荐
The Algorithmic Foundations of Differential Privacy 41积分/C币 立即下载
1/127
The Algorithmic Foundations of Differential Privacy第1页
The Algorithmic Foundations of Differential Privacy第2页
The Algorithmic Foundations of Differential Privacy第3页
The Algorithmic Foundations of Differential Privacy第4页
The Algorithmic Foundations of Differential Privacy第5页
The Algorithmic Foundations of Differential Privacy第6页
The Algorithmic Foundations of Differential Privacy第7页
The Algorithmic Foundations of Differential Privacy第8页
The Algorithmic Foundations of Differential Privacy第9页
The Algorithmic Foundations of Differential Privacy第10页
The Algorithmic Foundations of Differential Privacy第11页
The Algorithmic Foundations of Differential Privacy第12页
The Algorithmic Foundations of Differential Privacy第13页
The Algorithmic Foundations of Differential Privacy第14页
The Algorithmic Foundations of Differential Privacy第15页
The Algorithmic Foundations of Differential Privacy第16页
The Algorithmic Foundations of Differential Privacy第17页
The Algorithmic Foundations of Differential Privacy第18页
The Algorithmic Foundations of Differential Privacy第19页
The Algorithmic Foundations of Differential Privacy第20页

试读结束, 可继续阅读

41积分/C币 立即下载 >