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 Early access  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.

[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.

[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.

[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.

[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.

[6]

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

[7] G. R. Grimmett and D. R. Stirzaker, Probability and Random Processes, Oxford University Press, New York, 2001. 
[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.

[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.

[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.

[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.

[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.

[13]

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

[14]

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

[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.

[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.

[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.

[18]

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

[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.

[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.

[21]

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

[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.

[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).

[24]

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

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.

[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.

[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.

[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.

[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.

[6]

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

[7] G. R. Grimmett and D. R. Stirzaker, Probability and Random Processes, Oxford University Press, New York, 2001. 
[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.

[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.

[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.

[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.

[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.

[13]

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

[14]

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

[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.

[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.

[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.

[18]

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

[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.

[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.

[21]

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

[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.

[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).

[24]

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

[1]

Yinnian He, R. M.M. Mattheij. Reformed post-processing Galerkin method for the Navier-Stokes equations. Discrete and Continuous Dynamical Systems - B, 2007, 8 (2) : 369-387. doi: 10.3934/dcdsb.2007.8.369

[2]

Jinghong Liu, Yinsuo Jia. Gradient superconvergence post-processing of the tensor-product quadratic pentahedral finite element. Discrete and Continuous Dynamical Systems - B, 2015, 20 (2) : 495-504. doi: 10.3934/dcdsb.2015.20.495

[3]

Chengtao Yong, Yan Huo, Chunqiang Hu, Yanfei Lu, Guanlin Jing. A real-time aggregate data publishing scheme with adaptive ω-event differential privacy. Mathematical Foundations of Computing, 2018, 1 (3) : 295-309. doi: 10.3934/mfc.2018014

[4]

Yunmei Lu, Mingyuan Yan, Meng Han, Qingliang Yang, Yanqing Zhang. Privacy preserving feature selection and Multiclass Classification for horizontally distributed data. Mathematical Foundations of Computing, 2018, 1 (4) : 331-348. doi: 10.3934/mfc.2018016

[5]

Sarai Hedges, Kim Given. Addressing confirmation bias in middle school data science education. Foundations of Data Science, 2022  doi: 10.3934/fods.2021035

[6]

Weidong Bao, Wenhua Xiao, Haoran Ji, Chao Chen, Xiaomin Zhu, Jianhong Wu. Towards big data processing in clouds: An online cost-minimization approach. Big Data & Information Analytics, 2016, 1 (1) : 15-29. doi: 10.3934/bdia.2016.1.15

[7]

Min-Fan He, Li-Ning Xing, Wen Li, Shang Xiang, Xu Tan. Double layer programming model to the scheduling of remote sensing data processing tasks. Discrete and Continuous Dynamical Systems - S, 2019, 12 (4&5) : 1515-1526. doi: 10.3934/dcdss.2019104

[8]

José Ángel Cid, Luís Sanchez. Nonnegative oscillations for a class of differential equations without uniqueness: A variational approach. Discrete and Continuous Dynamical Systems - B, 2020, 25 (2) : 545-554. doi: 10.3934/dcdsb.2019253

[9]

Yuhua Sun. On the uniqueness of nonnegative solutions of differential inequalities with gradient terms on Riemannian manifolds. Communications on Pure and Applied Analysis, 2015, 14 (5) : 1743-1757. doi: 10.3934/cpaa.2015.14.1743

[10]

Amir Khan, Asaf Khan, Tahir Khan, Gul Zaman. Extension of triple Laplace transform for solving fractional differential equations. Discrete and Continuous Dynamical Systems - S, 2020, 13 (3) : 755-768. doi: 10.3934/dcdss.2020042

[11]

William Guo. The Laplace transform as an alternative general method for solving linear ordinary differential equations. STEM Education, 2021, 1 (4) : 309-329. doi: 10.3934/steme.2021020

[12]

Yanyan Hu, Fubao Xi, Min Zhu. Least squares estimation for distribution-dependent stochastic differential delay equations. Communications on Pure and Applied Analysis, 2022, 21 (4) : 1505-1536. doi: 10.3934/cpaa.2022027

[13]

Luca Calatroni, Bertram Düring, Carola-Bibiane Schönlieb. ADI splitting schemes for a fourth-order nonlinear partial differential equation from image processing. Discrete and Continuous Dynamical Systems, 2014, 34 (3) : 931-957. doi: 10.3934/dcds.2014.34.931

[14]

Rod Cross, Hugh McNamara, Leonid Kalachev, Alexei Pokrovskii. Hysteresis and post Walrasian economics. Discrete and Continuous Dynamical Systems - B, 2013, 18 (2) : 377-401. doi: 10.3934/dcdsb.2013.18.377

[15]

Arni S.R. Srinivasa Rao, Masayuki Kakehashi. Incubation-time distribution in back-calculation applied to HIV/AIDS data in India. Mathematical Biosciences & Engineering, 2005, 2 (2) : 263-277. doi: 10.3934/mbe.2005.2.263

[16]

Jijun Liu, Gen Nakamura. Recovering the boundary corrosion from electrical potential distribution using partial boundary data. Inverse Problems and Imaging, 2017, 11 (3) : 521-538. doi: 10.3934/ipi.2017024

[17]

Ruinian Li, Yinhao Xiao, Cheng Zhang, Tianyi Song, Chunqiang Hu. Cryptographic algorithms for privacy-preserving online applications. Mathematical Foundations of Computing, 2018, 1 (4) : 311-330. doi: 10.3934/mfc.2018015

[18]

Archana Prashanth Joshi, Meng Han, Yan Wang. A survey on security and privacy issues of blockchain technology. Mathematical Foundations of Computing, 2018, 1 (2) : 121-147. doi: 10.3934/mfc.2018007

[19]

Toyohiko Aiki. The position of the joint of shape memory alloy and bias springs. Discrete and Continuous Dynamical Systems - S, 2011, 4 (2) : 239-246. doi: 10.3934/dcdss.2011.4.239

[20]

Dominique Zosso, Jing An, James Stevick, Nicholas Takaki, Morgan Weiss, Liane S. Slaughter, Huan H. Cao, Paul S. Weiss, Andrea L. Bertozzi. Image segmentation with dynamic artifacts detection and bias correction. Inverse Problems and Imaging, 2017, 11 (3) : 577-600. doi: 10.3934/ipi.2017027

 Impact Factor: 

Metrics

  • PDF downloads (176)
  • HTML views (351)
  • Cited by (0)

Other articles
by authors

[Back to Top]