Journal of Computer Science and Technology ›› 2022, Vol. 37 ›› Issue (2): 369-388.doi: 10.1007/s11390-020-0193-z

Special Issue: Computer Networks and Distributed Computing; Theory and Algorithms

• Computer Networks and Distributed Computing • Previous Articles     Next Articles

Differential Privacy via a Truncated and Normalized Laplace Mechanism

William Croft1, Jörg-Rüdiger Sack1, and Wei Shi2        

  1. 1School of Computer Science, Carleton University, Ottawa K1S 5B6, Canada
    2School of Information Technology, Carleton University, Ottawa K1S 5B6, Canada
  • Received:2019-11-27 Revised:2020-08-18 Accepted:2020-08-20 Online:2022-03-31 Published:2022-03-31
  • Contact: William Croft
  • About author:William Croft is a Ph.D. candidate at Carleton University, Ottawa, in the School of Computer Science. He completed his M.Sc. (2015) and his B.Sc. (2013) in computer science at Carleton University, Ottawa. In 2017, he received the Natural Sciences and Engineering Research Council (NSERC) Alexander Graham Bell Canada Graduate Scholarship. His graduate research focuses on the topic of data privacy.

When querying databases containing sensitive information, the privacy of individuals stored in the database has to be guaranteed. Such guarantees are provided by differentially private mechanisms which add controlled noise to the query responses. However, most such mechanisms do not take into consideration the valid range of the query being posed. Thus, noisy responses that fall outside of this range may potentially be produced. To rectify this and therefore improve the utility of the mechanism, the commonly-used Laplace distribution can be truncated to the valid range of the query and then normalized. However, such a data-dependent operation of normalization leaks additional information about the true query response, thereby violating the differential privacy guarantee. Here, we propose a new method which preserves the differential privacy guarantee through a careful determination of an appropriate scaling parameter for the Laplace distribution. We adapt the privacy guarantee in the context of the Laplace distribution to account for data-dependent normalization factors and study this guarantee for different classes of range constraint configurations. We provide derivations of the optimal scaling parameter (i.e., the minimal value that preserves differential privacy) for each class or provide an approximation thereof. As a result of this work, one can use the Laplace distribution to answer queries in a range-adherent and differentially private manner. To demonstrate the benefits of our proposed method of normalization, we present an experimental comparison against other range-adherent mechanisms. We show that our proposed approach is able to provide improved utility over the alternative mechanisms.

Key words: differential privacy; Laplace mechanism; query range constraint ;

[1] Dwork C. Differential privacy. In Proc. the 33rd International Colloquium on Automata, Languages and Programming, July 2006, pp.1-12. DOI: 10.1007/11787006_1.
[2] Ghosh A, Roughgarden T, Sundararajan M. Universally utility-maximizing privacy mechanisms. SIAM Journal on Computing, 2012, 41(6): 1673-1693. DOI: 10.1137/09076828X.
[3] McSherry F, Talwar K. Mechanism design via differential privacy. In Proc. the 48th Annual IEEE Symposium on Foundations of Computer Science, October 2007, pp.94-103. DOI: 10.1109/FOCS.2007.66.
[4] Liu F. Statistical properties of sanitized results from differentially private Laplace mechanism with bounding constraints. arXiv:1607.08554, 2018., Dec. 2021.
[5] Adam N R, Worthmann J C. Security-control methods for statistical databases: A comparative study. ACM Computing Surveys, 1989, 21(4): 515-556. DOI: 10.1145/76894.76895.
[6] Dwork C, Roth A. The algorithmic foundations of differential privacy. Foundations and Trends® in Theoretical Computer Science, 2014, 9(3/4): 211-407. DOI: 10.1561/0400000042.
[7] Dwork C. Differential privacy: A survey of results. In Proc. the 5th International Conference on Theory and Applications of Models of Computation, April 2008, pp.1-19. DOI: 10.1007/978-3-540-79228-4_1.
[8] Nguyen H H, Kim J, Kim Y. Differential privacy in practice. Journal of Computing Science and Engineering, 2013, 7(3): 177-186. DOI: 10.5626/JCSE.2013.7.3.177.
[9] Barak B, Chaudhuri K, Dwork C, Kale S, McSherry F, Talwar K. Privacy, accuracy, and consistency too: A holistic solution to contingency table release. In Proc. the 26th ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, June 2007, pp.273-282. DOI: 10.1145/1265530.1265569.
[10] Hay M, Rastogi V, Miklau G, Suciu D. Boosting the accuracy of differentially private histograms through consistency. Proceedings of the Very Large Data Base Endowment, 2010, 3(1/2): 1021-1032. DOI: 10.14778/1920841.1920970.
[11] Lee J, Wang Y, Kifer D. Maximum likelihood postprocessing for differential privacy under consistency constraints. In Proc. the 21st ACM International Conference on Knowledge Discovery and Data Mining, August 2015, pp.635-644. DOI: 10.1145/2783258.2783366.
[12] Gupte M, Sundararajan M. Universally optimal privacy mechanisms for minimax agents. In Proc. the 29th ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, June 2010, pp.135-145. DOI: 10.1145/1807085.1807105.
[13] Cormode G, Kulkarni T, Srivastava D. Constrained private mechanisms for count data. In Proc. the 34th IEEE International Conference on Data Engineering, April 2018, pp.845-856. DOI: 10.1109/ICDE.2018.00081.
[14] Holohan N, Antonatos S, Braghin S, Aonghusa P M. The bounded Laplace mechanism in differential privacy. Journal of Privacy and Confidentiality, 2019, 10(1): Article No. 1. DOI: 10.29012/jpc.715.
[15] Geng Q, Ding W, Guo R, Kumar S. d Laplacian mechanism for approximate differential privacy. arXiv:1810.00877v1, 2018., Dec. 2021.
[16] Awan J, Slavkovic A. Differentially private uniformly most powerful tests for binomial data. In Proc. the 31st Annual Conference on Neural Information Processing Systems, December 2018, pp.4208-4218.
[17] Corless R, Gonnet G, Hare D, Jeffrey D, Knuth D. On the Lambert W function. Advances in Computational Mathematics, 1996, 5(1): 329-359. DOI: 10.1007/BF02124750.
[18] Mitchell T. Generative and discriminative classifiers: Naive Bayes and logistic regression. In Machine Learning, Mitchell T (ed.), McGraw Hill, 2017, pp.1-17.
[19] Vaidya J, Shafiq B, Basu A, Hong Y. Differentially private Naive Bayes classification. In Proc. the 2013 IEEE/WIC/ACM International Joint Conferences on Web Intelligence and Intelligent Agent Technologies, November 2013, pp.571-576. DOI: 10.1109/WI-IAT.2013.80.
[1] Jian-Zhe Zhao, Xing-Wei Wang, Ke-Ming Mao, Chen-Xi Huang, Yu-Kai Su, and Yu-Chen Li. Correlated Differential Privacy of Multiparty Data Release in Machine Learning [J]. Journal of Computer Science and Technology, 2022, 37(1): 231-251.
[2] Xiang Chen, Dun Zhang, Zhan-Qi Cui, Qing Gu, Xiao-Lin Ju. DP-Share: Privacy-Preserving Software Defect Prediction Model Sharing Through Differential Privacy [J]. Journal of Computer Science and Technology, 2019, 34(5): 1020-1038.
[3] Ning Wang, Yu Gu, Jia Xu, Fang-Fang Li, Ge Yu. Differentially Private Event Histogram Publication on Sequences over Graphs [J]. , 2017, 32(5): 1008-1024.
Full text



[1] . Online First Under Construction [J]. Journal of Computer Science and Technology, 0, (): 1 .
[2] Zhi-Neng Chen, Chong-Wah Ngo, Wei Zhang, Juan Cao, Yu-Gang Jiang. Name-Face Association in Web Videos: A Large-Scale Dataset, Baselines, and Open Issues[J]. , 2014, 29(5): 785 -798 .
[3] Fei Xia, De-Jun Jiang, Jin Xiong, Ning-Hui Sun. A Survey of Phase Change Memory Systems[J]. , 2015, 30(1): 121 -144 .
[4] André Brinkmann, Kathryn Mohror, Weikuan Yu, Philip Carns, Toni Cortes, Scott A. Klasky, Alberto Miranda, Franz-Josef Pfreundt, Robert B. Ross, Marc-André Vef. Ad Hoc File Systems for High-Performance Computing[J]. Journal of Computer Science and Technology, 2020, 35(1): 4 -26 .
[5] Yu-Tong Lu, Peng Cheng, Zhi-Guang Chen. Design and Implementation of the Tianhe-2 Data Storage and Management System[J]. Journal of Computer Science and Technology, 2020, 35(1): 27 -46 .
[6] Reza Jafari Ziarani, Reza Ravanmehr. Serendipity in Recommender Systems: A Systematic Literature Review[J]. Journal of Computer Science and Technology, 2021, 36(2): 375 -396 .
[7] Bo-Han Li, Yi Liu, An-Man Zhang, Wen-Huan Wang, Shuo Wan. A Survey on Blocking Technology of Entity Resolution[J]. Journal of Computer Science and Technology, 2020, 35(4): 769 -793 .
[8] Lie-Huang Zhu, Bao-Kun Zheng, Meng Shen, Feng Gao, Hong-Yu Li, Ke-Xin Shi. Data Security and Privacy in Bitcoin System: A Survey[J]. Journal of Computer Science and Technology, 2020, 35(4): 843 -862 .
[9] Dun Liang, Yuan-Chen Guo, Shao-Kui Zhang, Tai-Jiang Mu, Xiaolei Huang. Lane Detection: A Survey with New Results[J]. Journal of Computer Science and Technology, 2020, 35(3): 493 -505 .
[10] Lan Huang, Da-Lin Li, Kang-Ping Wang, Teng Gao, Adriano Tavares. A Survey on Performance Optimization of High-Level Synthesis Tools[J]. Journal of Computer Science and Technology, 2020, 35(3): 697 -720 .

ISSN 1000-9000(Print)

CN 11-2296/TP

Editorial Board
Author Guidelines
Journal of Computer Science and Technology
Institute of Computing Technology, Chinese Academy of Sciences
P.O. Box 2704, Beijing 100190 P.R. China
  Copyright ©2015 JCST, All Rights Reserved