Loading [MathJax]/jax/output/SVG/jax.js
We use cookies to improve your experience with our site.

Indexed in:

SCIE, EI, Scopus, INSPEC, DBLP, CSCD, etc.

Submission System
(Author / Reviewer / Editor)
Advanced Search
Volume 37 Issue 2
March  2022
Turn off MathJax
Article Contents
Abstract
References
Related Articles
Supplements
William Croft, Jörg-Rüdiger Sack, Wei Shi. Differential Privacy via a Truncated and Normalized Laplace Mechanism[J]. Journal of Computer Science and Technology, 2022, 37(2): 369-388. DOI: 10.1007/s11390-020-0193-z
Citation: William Croft, Jörg-Rüdiger Sack, Wei Shi. Differential Privacy via a Truncated and Normalized Laplace Mechanism[J]. Journal of Computer Science and Technology, 2022, 37(2): 369-388. DOI: 10.1007/s11390-020-0193-z
shu

Differential Privacy via a Truncated and Normalized Laplace Mechanism

  • 1School of Computer Science, Carleton University, Ottawa K1S 5B6, Canada
    2School of Information Technology, Carleton University, Ottawa K1S 5B6, Canada

More Information
  • Author Bio:

    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.

  • Received Date: November 26, 2019
  • Revised Date: August 17, 2020
  • Accepted Date: August 19, 2020
  • Published Date: March 30, 2022
    Abstract
  • 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.

    • FullText(HTML)
    • References (19)
  • [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. https://arxiv.org/abs/1607.08554, 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. https://arxiv.org/abs/1810.00877v1, 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.
    • Relative Articles

  • Related Articles

    [1]Peng-Cheng Zhao, Li-Jie Xu, Jia Xu. Personalized Privacy-Preserving Routing Mechanism Design in Payment Channel Network[J]. Journal of Computer Science and Technology, 2024, 39(6): 1380-1400. DOI: 10.1007/s11390-024-2635-5
    [2]Ning Wang, Yu Gu, Jia Xu, Fang-Fang Li, Ge Yu. Differentially Private Event Histogram Publication on Sequences over Graphs[J]. Journal of Computer Science and Technology, 2017, 32(5): 1008-1024. DOI: 10.1007/s11390-017-1778-z
    [3]Yi-Fei Chen, Xiao-Lin Qin, Liang Liu, Bo-Han Li. Fuzzy Distance-Based Range Queries over Uncertain Moving Objects[J]. Journal of Computer Science and Technology, 2012, (2): 376-396. DOI: 10.1007/s11390-012-1229-9
    [4]Yi-Fei Chen, Xiao-Lin Qin, Liang Liu. Uncertain Distance-Based Range Queries over Uncertain Moving Objects[J]. Journal of Computer Science and Technology, 2010, 25(5): 982-998. DOI: 10.1007/s11390-010-1078-3
    [5]Bin Wang, Xiao-Chun Yang, Guo-Ren Wang, Ge Yu, Lei Chen, X. Sean Wang, Xue-Min Lin. Continually Answering Constraint kk-{\it\bfseries NN} Queries in Unstructured P2P Systems[J]. Journal of Computer Science and Technology, 2008, 23(4): 538-556.
    [6]Hong Gao, Jian-Zhong Li. Parallel Data Cube Storage Structure for Range Sum Queries and Dynamic Updates[J]. Journal of Computer Science and Technology, 2005, 20(3): 345-356.
    [7]Lin Xueyin, Chen Xiangrong, Zhu Zhigang, Shi Dingji. Range Information Propagation Transform[J]. Journal of Computer Science and Technology, 1998, 13(5): 438-447.
    [8]Hock C. Chan. Translational Semantics for a Conceptual Level Query Language[J]. Journal of Computer Science and Technology, 1995, 10(2): 175-187.
    [9]Li Tianzhu. A Study of Optimization and Rule/Goal Graph for a Logical Query[J]. Journal of Computer Science and Technology, 1992, 7(4): 356-362.
    [10]Li Jianzhong. Range Query Processing in Multidisk Systems[J]. Journal of Computer Science and Technology, 1992, 7(4): 316-327.
    • Supplements (2)

  • Others

Catalog

    Get Citation
    PDF
    XML
    Read Online
    Article views (178) PDF downloads (0) Cited by()
    Related

    Copyright ©2025 JCST, All Rights Reserved     京ICP备05002829号-1

    Institute of Computing Technology, Chinese Academy of Sciences
    P.O. Box 2704, Beijing 100190, P.R. China

    Tel.: 86-10-62610746 E-mail: jcst@ict.ac.cn

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return