1. bookVolume 2021 (2021): Issue 1 (January 2021)
Journal Details
First Published
16 Apr 2015
Publication timeframe
4 times per year
access type Open Access

Differential Privacy at Risk: Bridging Randomness and Privacy Budget

Published Online: 09 Nov 2020
Volume & Issue: Volume 2021 (2021) - Issue 1 (January 2021)
Page range: 64 - 84
Received: 31 May 2020
Accepted: 16 Sep 2020
Journal Details
First Published
16 Apr 2015
Publication timeframe
4 times per year

The calibration of noise for a privacy-preserving mechanism depends on the sensitivity of the query and the prescribed privacy level. A data steward must make the non-trivial choice of a privacy level that balances the requirements of users and the monetary constraints of the business entity.

Firstly, we analyse roles of the sources of randomness, namely the explicit randomness induced by the noise distribution and the implicit randomness induced by the data-generation distribution, that are involved in the design of a privacy-preserving mechanism. The finer analysis enables us to provide stronger privacy guarantees with quantifiable risks. Thus, we propose privacy at risk that is a probabilistic calibration of privacy-preserving mechanisms. We provide a composition theorem that leverages privacy at risk. We instantiate the probabilistic calibration for the Laplace mechanism by providing analytical results.

Secondly, we propose a cost model that bridges the gap between the privacy level and the compensation budget estimated by a GDPR compliant business entity. The convexity of the proposed cost model leads to a unique fine-tuning of privacy level that minimises the compensation budget. We show its effectiveness by illustrating a realistic scenario that avoids overestimation of the compensation budget by using privacy at risk for the Laplace mechanism. We quantitatively show that composition using the cost optimal privacy at risk provides stronger privacy guarantee than the classical advanced composition. Although the illustration is specific to the chosen cost model, it naturally extends to any convex cost model. We also provide realistic illustrations of how a data steward uses privacy at risk to balance the trade-off between utility and privacy.


[1] Martin Abadi, Andy Chu, Ian Goodfellow, H Brendan McMahan, Ilya Mironov, Kunal Talwar, and Li Zhang. Deep learning with differential privacy. In Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, pages 308–318, 2016.10.1145/2976749.2978318Search in Google Scholar

[2] Gergely Acs, Claude Castelluccia, and Rui Chen. Differentially private histogram publishing through lossy compression. In Data Mining (ICDM), 2012 IEEE 12th International Conference on, pages 1–10. IEEE, 2012.Search in Google Scholar

[3] RA Askey and AB Olde Daalhuis. Generalized hypergeo-metric functions and meijer g-function. NIST handbook of mathematical functions, pages 403–418, 2010.Search in Google Scholar

[4] Raef Bassily, Adam Groce, Jonathan Katz, and Adam Smith. Coupled-worlds privacy: Exploiting adversarial uncertainty in statistical data privacy. In 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, pages 439–448. IEEE, 2013.10.1109/FOCS.2013.54Search in Google Scholar

[5] Mark Bun and Thomas Steinke. Concentrated differential privacy: Simplifications, extensions, and lower bounds. CoRR, 2016.10.1007/978-3-662-53641-4_24Search in Google Scholar

[6] Kamalika Chaudhuri, Claire Monteleoni, and Anand D Sarwate. Differentially private empirical risk minimization. Journal of Machine Learning Research, 12(Mar):1069–1109, 2011.Search in Google Scholar

[7] Yiling Chen, Stephen Chong, Ian A Kash, Tal Moran, and Salil Vadhan. Truthful mechanisms for agents that value privacy. ACM Transactions on Economics and Computation (TEAC), 4(3):13, 2016.10.1145/2892555Search in Google Scholar

[8] Damien Desfontaines and Balázs Pejó. Sok: Differential privacies. Proceedings on Privacy Enhancing Technologies, 2020(2):288–313, 2020.Search in Google Scholar

[9] Cynthia Dwork, Krishnaram Kenthapadi, Frank McSherry, Ilya Mironov, and Moni Naor. Our data, ourselves: Privacy via distributed noise generation. In Eurocrypt, volume 4004, pages 486–503. Springer, 2006.10.1007/11761679_29Search in Google Scholar

[10] Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In Theory of Cryptography Conference, pages 265–284. Springer, 2006.10.1007/11681878_14Search in Google Scholar

[11] Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating Noise to Sensitivity in Private Data Analysis, pages 265–284. Springer Berlin Heidelberg, Berlin, Heidelberg, 2006.10.1007/11681878_14Search in Google Scholar

[12] Cynthia Dwork, Aaron Roth, et al. The algorithmic foundations of differential privacy. Foundations and Trends® in Theoretical Computer Science, 9(3–4):211–407, 2014.10.1561/0400000042Search in Google Scholar

[13] Cynthia Dwork and Guy N Rothblum. Concentrated differential privacy. arXiv preprint arXiv:1603.01887, 2016.Search in Google Scholar

[14] Simson L Garfinkel, John M Abowd, and Sarah Powazek. Issues encountered deploying differential privacy. arXiv preprint arXiv:1809.02201, 2018.Search in Google Scholar

[15] Arpita Ghosh and Aaron Roth. Selling privacy at auction. Games and Economic Behavior, 91:334–346, 2015.10.1016/j.geb.2013.06.013Search in Google Scholar

[16] Rob Hall, Alessandro Rinaldo, and Larry Wasserman. Random differential privacy. Journal of Privacy and Confidentiality, 4(2):43–59, 2012.10.29012/jpc.v4i2.621Search in Google Scholar

[17] Rob Hall, Alessandro Rinaldo, and Larry Wasserman. Differential privacy for functions and functional data. Journal of Machine Learning Research, 14(Feb):703–727, 2013.Search in Google Scholar

[18] Wassily Hoeffding. Probability inequalities for sums of bounded random variables. In The Collected Works of Wassily Hoeffding, pages 409–426. Springer, 1994.10.1007/978-1-4612-0865-5_26Search in Google Scholar

[19] Justin Hsu, Marco Gaboardi, Andreas Haeberlen, Sanjeev Khanna, Arjun Narayan, Benjamin C Pierce, and Aaron Roth. Differential privacy: An economic method for choosing epsilon. In Computer Security Foundations Symposium (CSF), 2014 IEEE 27th, pages 398–410. IEEE, 2014.Search in Google Scholar

[20] Wolfram Research, Inc. Mathematica, Version 10. Champaign, IL, 2014.Search in Google Scholar

[21] Philippe Jorion. Value at risk: The new benchmark for managing financial risk, 01 2000.Search in Google Scholar

[22] Peter Kairouz, Sewoong Oh, and Pramod Viswanath. The composition theorem for differential privacy. In International conference on machine learning, pages 1376–1385, 2015.Search in Google Scholar

[23] Daniel Kifer and Bing-Rong Lin. An axiomatic view of statistical privacy and utility. Journal of Privacy and Confidentiality, 4(1), 2012.10.29012/jpc.v4i1.610Search in Google Scholar

[24] Daniel Kifer and Ashwin Machanavajjhala. A rigorous and customizable framework for privacy. In Proceedings of the 31st ACM SIGMOD-SIGACT-SIGAI symposium on Principles of Database Systems, pages 77–88. ACM, 2012.10.1145/2213556.2213571Search in Google Scholar

[25] Jaewoo Lee and Chris Clifton. How much is enough? choosing ɛ for differential privacy. In International Conference on Information Security, pages 325–340. Springer, 2011.10.1007/978-3-642-24861-0_22Search in Google Scholar

[26] Katrina Ligett, Seth Neel, Aaron Roth, Bo Waggoner, and Steven Z Wu. Accuracy first: Selecting a differential privacy level for accuracy constrained erm. In Advances in Neural Information Processing Systems, pages 2563–2573, 2017.Search in Google Scholar

[27] Ashwin Machanavajjhala, Daniel Kifer, John Abowd, Johannes Gehrke, and Lars Vilhuber. Privacy: Theory meets practice on the map. In Data Engineering, 2008. ICDE 2008. IEEE 24th International Conference on, pages 277–286. IEEE, 2008.10.1109/ICDE.2008.4497436Search in Google Scholar

[28] Pascal Massart et al. The tight constant in the dvoretzkykiefer-wolfowitz inequality. The annals of Probability, 18(3):1269–1283, 1990.10.1214/aop/1176990746Search in Google Scholar

[29] Sebastian Meiser. Approximate and probabilistic differential privacy definitions. IACR Cryptology ePrint Archive, 2018:277, 2018.Search in Google Scholar

[30] James P Moriarty, Megan E Branda, Kerry D Olsen, Nilay D Shah, Bijan J Borah, Amy E Wagie, Jason S Egginton, and James M Naessens. The effects of incremental costs of smoking and obesity on health care costs among adults: a 7-year longitudinal study. Journal of Occupational and Environmental Medicine, 54(3):286–291, 2012.Search in Google Scholar

[31] Kevin P. Murphy. Machine Learning: A Probabilistic Perspective. The MIT Press, 2012.Search in Google Scholar

[32] Kobbi Nissim, Sofya Raskhodnikova, and Adam Smith. Smooth sensitivity and sampling in private data analysis. In Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, pages 75–84. ACM, 2007.10.1145/1250790.1250803Search in Google Scholar

[33] Nicolas Papernot, Martín Abadi, Úlfar Erlingsson, Ian J. Goodfellow, and Kunal Talwar. Semi-supervised knowledge transfer for deep learning from private training data. In 5th International Conference on Learning Representations, ICLR 2017, Toulon, France, April 24-26, 2017, Conference Track Proceedings. OpenReview.net, 2017.Search in Google Scholar

[34] Nicolas Papernot, Shuang Song, Ilya Mironov, Ananth Raghunathan, Kunal Talwar, and Úlfar Erlingsson. Scalable private learning with PATE. CoRR, abs/1802.08908, 2018.Search in Google Scholar

[35] Athanasios Papoulis and S Unnikrishna Pillai. Probability, random variables, and stochastic processes. Tata McGraw-Hill Education, 2002.Search in Google Scholar

[36] Balazs Pejo, Qiang Tang, and Gergely Biczok. Together or alone: The price of privacy in collaborative learning. Proceedings on Privacy Enhancing Technologies, 2019(2):47–65, 2019.Search in Google Scholar

[37] William H Press. Numerical recipes 3rd edition: The art of scientific computing. Cambridge university press, 2007.Search in Google Scholar

[38] Benjamin IP Rubinstein and Francesco Aldà. Pain-free random differential privacy with sensitivity sampling. In International Conference on Machine Learning, pages 2950–2959, 2017.Search in Google Scholar

[39] Steven Ruggles, Katie Genadek, Ronald Goeken, Josiah Grover, and Matthew Sobek. Integrated public use microdata series: Version 6.0 [dataset], 2015.Search in Google Scholar

[40] Aleksei Triastcyn and Boi Faltings. Federated learning with bayesian differential privacy. arXiv preprint arXiv:1911.10071, 2019.Search in Google Scholar

[41] Jun Zhang, Zhenjie Zhang, Xiaokui Xiao, Yin Yang, and Marianne Winslett. Functional mechanism: regression analysis under differential privacy. Proceedings of the VLDB Endowment, 5(11):1364–1375, 2012.Search in Google Scholar

Recommended articles from Trend MD

Plan your remote conference with Sciendo