December  2020, 2(4): 429-442. doi: 10.3934/fods.2020020

Observations on the bias of nonnegative mechanisms for differential privacy

Dept. of Mathematics and Statistics, Maynooth University, Co. Kildare, Ireland & Lero, the Science Foundation Ireland Research Centre for Software

* Corresponding author: Oliver Mason

Received  August 2020 Revised  December 2020 Published  December 2020

Fund Project: This work is supported by SFI grant 13/RC/2094

We study two methods for differentially private analysis of bounded data and extend these to nonnegative queries. We first recall that for the Laplace mechanism, boundary inflated truncation (BIT) applied to nonnegative queries and truncation both lead to strictly positive bias. We then consider a generalization of BIT using translated ramp functions. We explicitly characterise the optimal function in this class for worst case bias. We show that applying any square-integrable post-processing function to a Laplace mechanism leads to a strictly positive maximal absolute bias. A corresponding result is also shown for a generalisation of truncation, which we refer to as restriction. We also briefly consider an alternative approach based on multiplicative mechanisms for positive data and show that, without additional restrictions, these mechanisms can lead to infinite bias.

Citation: Aisling McGlinchey, Oliver Mason. Observations on the bias of nonnegative mechanisms for differential privacy. Foundations of Data Science, 2020, 2 (4) : 429-442. doi: 10.3934/fods.2020020
References:
[1]

J. M. Abowd, The U.S. Census Bureau adopts differential privacy, in Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, (2018), 2867. doi: 10.1145/3219819.3226070.  Google Scholar

[2]

J. Domingo-Ferrer and J. Soria-Comas, From t-closeness to differential privacy and vice versa in data anonymization, Knowledge Based Systems, 74 (2015), 151-158.  doi: 10.1016/j.knosys.2014.11.011.  Google Scholar

[3]

C. Dwork, Differential privacy, Automata, languages and programming. Part II, Lecture Notes in Comput. Sci., Springer, Berlin, 4052 (2006), 1–12. doi: 10.1007/11787006_1.  Google Scholar

[4]

C. DworkF. McSherryK. Nissim and A. Smith, Calibrating noise to sensitivity in private data analysis, Theory of Cryptography, 3876 (2006), 265-284.  doi: 10.1007/11681878_14.  Google Scholar

[5]

C. Dwork and A. Roth, The algorithmic foundations of differential privacy, Found. Trends Theor. Comput. Sci., 9 (2013), 211-487.  doi: 10.1561/0400000042.  Google Scholar

[6]

F. Fioretto, P. Van Hentenryck and K. Zhu, Differential privacy of hierarchical census data: An optimization approach, arXiv: 2006.15673, (2020). Google Scholar

[7] G. R. Grimmett and D. R. Stirzaker, Probability and Random Processes, Oxford University Press, New York, 2001.   Google Scholar
[8]

R. HallL. Wasserman and A. Rinaldi, Random differential privacy, Journal of Privacy and Confidentiality, 4 (2013), 43-59.  doi: 10.29012/jpc.v4i2.621.  Google Scholar

[9]

N. Holohan, S. Antonatos, S. Braghin and P. Mac Aonghusa, The bounded Laplace mechanism in differential privacy, Journal of Privacy and Confidentiality, 10 (2020). doi: 10.29012/jpc.715.  Google Scholar

[10]

N. HolohanD. J. Leith and O. Mason, Differential privacy in metric spaces: Numerical, categorical and functional data under the one roof, Inform. Sci., 305 (2015), 256-268.  doi: 10.1016/j.ins.2015.01.021.  Google Scholar

[11]

N. HolohanD. J. Leith and O. Mason, Optimal differentially private mechanisms for randomised response, IEEE Transactions on Information Forensics and Security, 12 (2017), 2726-2735.  doi: 10.1109/TIFS.2017.2718487.  Google Scholar

[12]

K. KalantariL. Sankar and A. Sarwate, Robust privacy-utility tradeoffs under differential privacy and hamming distortion, IEEE Transactions on Information Forensics and Security, 13 (2019), 2816-2830.  doi: 10.1109/TIFS.2018.2831619.  Google Scholar

[13]

J. Le Ny and G. J. Pappas, Privacy-preserving release of aggregate dynamic models, in Proceedings of HiCoNS, 2013. Google Scholar

[14]

F. Liu, Statistical properties of sanitized results from differentially private Laplace mechanism with bounding constraints, preprint, arXiv: 1607.08554. Google Scholar

[15]

F. Liu, Generalized Gaussian mechanism for differential privacy, IEEE Transactions on Knowledge and Data Engineering, 31 (2019), 747-756.  doi: 10.1109/TKDE.2018.2845388.  Google Scholar

[16]

L.-J. LiuH. R. Karimi and X. Zhao, New approaches to positive observer design for discrete-time positive linear systems, J. Franklin Inst., 355 (2018), 4336-4350.  doi: 10.1016/j.jfranklin.2018.04.015.  Google Scholar

[17]

F. McSherry and K. Talwar, Mechanism design via Differential Privacy, in Proceedings of 48th Annual Symposium of Foundations of Computer Science, (2007), 94–103. doi: 10.1109/FOCS.2007.66.  Google Scholar

[18]

P. Sadeghi, S. Asoodeh and F. du Pin Calmon, Differentially private mechanisms for count queries, arXiv: 2007.09374, (2020). Google Scholar

[19]

J. Soria-Comas and J. Domingo-Ferrer, Optimal data independent noise for differential privacy, Inform. Sci., 250 (2013), 200-214.  doi: 10.1016/j.ins.2013.07.004.  Google Scholar

[20]

J. Soria-ComasJ. Domingo-FerrerD. Sánchez and D. Megias, Individual differential privacy: A utility-preserving formulation of differential privacy guarantees, IEEE Tran. Information Forensics and Data Security, 12 (2017), 1418-1429.  doi: 10.1109/TIFS.2017.2663337.  Google Scholar

[21]

V. Torra, Data Privacy: Foundations, New Developments and the Big Data Challenge, Springer-Verlag, 2017. doi: 10.1007/978-3-319-57358-8.  Google Scholar

[22]

A. Triastcyn and B. Faltings, Bayesian differential privacy for machine learning, in Proceedings of the 37th International Conference on Machine Learning, (2020), 9583–9592. Google Scholar

[23]

E. Valcher and A. Rantzer, A tutorial on positive systems and large scale control, in Proceedings of IEEE Conf. on Dec. and Cont., (2018). Google Scholar

[24]

K. Zhu, P. Van Hentenryck and F. Fioretto, Bias and variance of post-processing in differential privacy, arXiv: 2010.04327, (2020). Google Scholar

show all references

References:
[1]

J. M. Abowd, The U.S. Census Bureau adopts differential privacy, in Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, (2018), 2867. doi: 10.1145/3219819.3226070.  Google Scholar

[2]

J. Domingo-Ferrer and J. Soria-Comas, From t-closeness to differential privacy and vice versa in data anonymization, Knowledge Based Systems, 74 (2015), 151-158.  doi: 10.1016/j.knosys.2014.11.011.  Google Scholar

[3]

C. Dwork, Differential privacy, Automata, languages and programming. Part II, Lecture Notes in Comput. Sci., Springer, Berlin, 4052 (2006), 1–12. doi: 10.1007/11787006_1.  Google Scholar

[4]

C. DworkF. McSherryK. Nissim and A. Smith, Calibrating noise to sensitivity in private data analysis, Theory of Cryptography, 3876 (2006), 265-284.  doi: 10.1007/11681878_14.  Google Scholar

[5]

C. Dwork and A. Roth, The algorithmic foundations of differential privacy, Found. Trends Theor. Comput. Sci., 9 (2013), 211-487.  doi: 10.1561/0400000042.  Google Scholar

[6]

F. Fioretto, P. Van Hentenryck and K. Zhu, Differential privacy of hierarchical census data: An optimization approach, arXiv: 2006.15673, (2020). Google Scholar

[7] G. R. Grimmett and D. R. Stirzaker, Probability and Random Processes, Oxford University Press, New York, 2001.   Google Scholar
[8]

R. HallL. Wasserman and A. Rinaldi, Random differential privacy, Journal of Privacy and Confidentiality, 4 (2013), 43-59.  doi: 10.29012/jpc.v4i2.621.  Google Scholar

[9]

N. Holohan, S. Antonatos, S. Braghin and P. Mac Aonghusa, The bounded Laplace mechanism in differential privacy, Journal of Privacy and Confidentiality, 10 (2020). doi: 10.29012/jpc.715.  Google Scholar

[10]

N. HolohanD. J. Leith and O. Mason, Differential privacy in metric spaces: Numerical, categorical and functional data under the one roof, Inform. Sci., 305 (2015), 256-268.  doi: 10.1016/j.ins.2015.01.021.  Google Scholar

[11]

N. HolohanD. J. Leith and O. Mason, Optimal differentially private mechanisms for randomised response, IEEE Transactions on Information Forensics and Security, 12 (2017), 2726-2735.  doi: 10.1109/TIFS.2017.2718487.  Google Scholar

[12]

K. KalantariL. Sankar and A. Sarwate, Robust privacy-utility tradeoffs under differential privacy and hamming distortion, IEEE Transactions on Information Forensics and Security, 13 (2019), 2816-2830.  doi: 10.1109/TIFS.2018.2831619.  Google Scholar

[13]

J. Le Ny and G. J. Pappas, Privacy-preserving release of aggregate dynamic models, in Proceedings of HiCoNS, 2013. Google Scholar

[14]

F. Liu, Statistical properties of sanitized results from differentially private Laplace mechanism with bounding constraints, preprint, arXiv: 1607.08554. Google Scholar

[15]

F. Liu, Generalized Gaussian mechanism for differential privacy, IEEE Transactions on Knowledge and Data Engineering, 31 (2019), 747-756.  doi: 10.1109/TKDE.2018.2845388.  Google Scholar

[16]

L.-J. LiuH. R. Karimi and X. Zhao, New approaches to positive observer design for discrete-time positive linear systems, J. Franklin Inst., 355 (2018), 4336-4350.  doi: 10.1016/j.jfranklin.2018.04.015.  Google Scholar

[17]

F. McSherry and K. Talwar, Mechanism design via Differential Privacy, in Proceedings of 48th Annual Symposium of Foundations of Computer Science, (2007), 94–103. doi: 10.1109/FOCS.2007.66.  Google Scholar

[18]

P. Sadeghi, S. Asoodeh and F. du Pin Calmon, Differentially private mechanisms for count queries, arXiv: 2007.09374, (2020). Google Scholar

[19]

J. Soria-Comas and J. Domingo-Ferrer, Optimal data independent noise for differential privacy, Inform. Sci., 250 (2013), 200-214.  doi: 10.1016/j.ins.2013.07.004.  Google Scholar

[20]

J. Soria-ComasJ. Domingo-FerrerD. Sánchez and D. Megias, Individual differential privacy: A utility-preserving formulation of differential privacy guarantees, IEEE Tran. Information Forensics and Data Security, 12 (2017), 1418-1429.  doi: 10.1109/TIFS.2017.2663337.  Google Scholar

[21]

V. Torra, Data Privacy: Foundations, New Developments and the Big Data Challenge, Springer-Verlag, 2017. doi: 10.1007/978-3-319-57358-8.  Google Scholar

[22]

A. Triastcyn and B. Faltings, Bayesian differential privacy for machine learning, in Proceedings of the 37th International Conference on Machine Learning, (2020), 9583–9592. Google Scholar

[23]

E. Valcher and A. Rantzer, A tutorial on positive systems and large scale control, in Proceedings of IEEE Conf. on Dec. and Cont., (2018). Google Scholar

[24]

K. Zhu, P. Van Hentenryck and F. Fioretto, Bias and variance of post-processing in differential privacy, arXiv: 2010.04327, (2020). Google Scholar

[1]

Lekbir Afraites, Abdelghafour Atlas, Fahd Karami, Driss Meskine. Some class of parabolic systems applied to image processing. Discrete & Continuous Dynamical Systems - B, 2016, 21 (6) : 1671-1687. doi: 10.3934/dcdsb.2016017

[2]

Habib Ammari, Josselin Garnier, Vincent Jugnon. Detection, reconstruction, and characterization algorithms from noisy data in multistatic wave imaging. Discrete & Continuous Dynamical Systems - S, 2015, 8 (3) : 389-417. doi: 10.3934/dcdss.2015.8.389

[3]

Jaume Llibre, Luci Any Roberto. On the periodic solutions of a class of Duffing differential equations. Discrete & Continuous Dynamical Systems - A, 2013, 33 (1) : 277-282. doi: 10.3934/dcds.2013.33.277

[4]

Marion Darbas, Jérémy Heleine, Stephanie Lohrengel. Numerical resolution by the quasi-reversibility method of a data completion problem for Maxwell's equations. Inverse Problems & Imaging, 2020, 14 (6) : 1107-1133. doi: 10.3934/ipi.2020056

[5]

Wolf-Jüergen Beyn, Janosch Rieger. The implicit Euler scheme for one-sided Lipschitz differential inclusions. Discrete & Continuous Dynamical Systems - B, 2010, 14 (2) : 409-428. doi: 10.3934/dcdsb.2010.14.409

[6]

Nhu N. Nguyen, George Yin. Stochastic partial differential equation models for spatially dependent predator-prey equations. Discrete & Continuous Dynamical Systems - B, 2020, 25 (1) : 117-139. doi: 10.3934/dcdsb.2019175

[7]

Bin Pei, Yong Xu, Yuzhen Bai. Convergence of p-th mean in an averaging principle for stochastic partial differential equations driven by fractional Brownian motion. Discrete & Continuous Dynamical Systems - B, 2020, 25 (3) : 1141-1158. doi: 10.3934/dcdsb.2019213

[8]

Xiaoming Wang. Quasi-periodic solutions for a class of second order differential equations with a nonlinear damping term. Discrete & Continuous Dynamical Systems - S, 2017, 10 (3) : 543-556. doi: 10.3934/dcdss.2017027

[9]

Zhiming Guo, Zhi-Chun Yang, Xingfu Zou. Existence and uniqueness of positive solution to a non-local differential equation with homogeneous Dirichlet boundary condition---A non-monotone case. Communications on Pure & Applied Analysis, 2012, 11 (5) : 1825-1838. doi: 10.3934/cpaa.2012.11.1825

 Impact Factor: 

Metrics

  • PDF downloads (58)
  • HTML views (101)
  • Cited by (0)

Other articles
by authors

[Back to Top]