Document Open Access Logo

On Differentially Private Counting on Trees

Authors Badih Ghazi , Pritish Kamath , Ravi Kumar , Pasin Manurangsi , Kewen Wu

PDF

File

Thumbnail PDF
PDF
LIPIcs.ICALP.2023.66.pdf
  • Filesize: 0.96 MB
  • 18 pages

Document Identifiers

Related Versions

Subject Classification

ACM Subject Classification
  • Theory of computation → Theory of database privacy and security
Keywords
  • Differential Privacy
  • Algorithms
  • Trees
  • Hierarchies

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Abstract

We study the problem of performing counting queries at different levels in hierarchical structures while preserving individuals' privacy. Motivated by applications, we propose a new error measure for this problem by considering a combination of multiplicative and additive approximation to the query results. We examine known mechanisms in differential privacy (DP) and prove their optimality, under this measure, in the pure-DP setting. In the approximate-DP setting, we design new algorithms achieving significant improvements over known ones.

Cite As Get BibTex

Badih Ghazi, Pritish Kamath, Ravi Kumar, Pasin Manurangsi, and Kewen Wu. On Differentially Private Counting on Trees. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 66:1-66:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023) https://doi.org/10.4230/LIPIcs.ICALP.2023.66

Author Details

Badih Ghazi
  • Google, Mountain View, CA, US
Pritish Kamath
  • Google, Mountain View, CA, US
Ravi Kumar
  • Google, Mountain View, CA, US
Pasin Manurangsi
  • Google, Bangkok, Thailand
Kewen Wu
  • University of California at Berkeley, CA, US

Funding

  • Wu, Kewen: Most of this work was done while at Google.

Acknowledgements

KW wants to thank Xin Lyu for helpful references on the sparse vector technique. We thank anonymous ITCS'23 and ICALP'23 reviewers for helpful feedback.

References

  1. John Abowd, Daniel Kifer, Brett Moran, Robert Ashmead, Philip Leclerc, William Sexton, Simson Garfinkel, and Ashwin Machanavajjhala. Census topdown: Differentially private data, incremental schemas, and consistency with public knowledge, 2019. Available at URL: https://github.com/uscensusbureau/census2020-das-e2e/blob/master/doc/20190711_0945_Consistency_for_Large_Scale_Differentially_Private_Histograms.pdf.
  2. John M. Abowd, Robert Ashmead, Ryan Cumings-Menon, Simson L. Garfinkel, Micah Heineck, Christine Heiss, Robert Johns, Daniel Kifer, Philip Leclerc, Ashwin Machanavajjhala, Brett Moran, William Sexton, Matthew Spence, and Pavel Zhuravlev. The 2020 census disclosure avoidance system TopDown algorithm. Harvard Data Sci. Rev., 2022. Special Issue 2. Google Scholar
  3. John M Abowd and Ian M Schmutte. An economic analysis of privacy protection and statistical accuracy as social choices. Amer. Econ. Rev., 109(1):171-202, 2019. Google Scholar
  4. Apple Differential Privacy Team. Learning with privacy at scale. Apple ML J., 2017. Google Scholar
  5. Aditya Bhaskara, Daniel Dadush, Ravishankar Krishnaswamy, and Kunal Talwar. Unconditional differentially private mechanisms for linear queries. In STOC, pages 1269-1284, 2012. Google Scholar
  6. Jaroslaw Blasiok, Mark Bun, Aleksandar Nikolov, and Thomas Steinke. Towards instance-optimal private query release. In SODA, pages 2480-2497, 2019. Google Scholar
  7. Jean Bolot, Nadia Fawaz, Shanmugavelayutham Muthukrishnan, Aleksandar Nikolov, and Nina Taft. Private decayed predicate sums on streams. In ICDT, pages 284-295, 2013. Google Scholar
  8. Mark Bun, Kobbi Nissim, Uri Stemmer, and Salil P. Vadhan. Differentially private release and learning of threshold functions. In FOCS, pages 634-649, 2015. Google Scholar
  9. Mark Bun, Jonathan R. Ullman, and Salil P. Vadhan. Fingerprinting codes and the price of approximate differential privacy. SIAM J. Comput., 47(5):1888-1938, 2018. URL: https://doi.org/10.1137/15M1033587.
  10. T.-H. Hubert Chan, Elaine Shi, and Dawn Song. Private and continual release of statistics. ACM Trans. Inf. Syst. Secur., 14(3):26:1-26:24, 2011. URL: https://doi.org/10.1145/2043621.2043626.
  11. Aloni Cohen, Moon Duchin, J. N. Matthews, and Bhushan Suwal. Census topdown: The impacts of differential privacy on redistricting. In FORC, pages 5:1-5:22, 2021. Google Scholar
  12. Aloni Cohen, Moon Duchin, JN Matthews, and Bhushan Suwal. Private Numbers in Public Policy: Census, Differential Privacy, and Redistricting. Harvard Data Sci. Rev., 2022. Google Scholar
  13. Graham Cormode, Cecilia M. Procopiuc, Divesh Srivastava, Entong Shen, and Ting Yu. Differentially private spatial decompositions. In ICDE, pages 20-31, 2012. Google Scholar
  14. Bolin Ding, Janardhan Kulkarni, and Sergey Yekhanin. Collecting telemetry data privately. In NeurIPS, pages 3571-3580, 2017. Google Scholar
  15. Irit Dinur and Kobbi Nissim. Revealing information while preserving privacy. In PODS, pages 202-210, 2003. Google Scholar
  16. Cynthia Dwork. Differential privacy: A survey of results. In TAMC, pages 1-19, 2008. Google Scholar
  17. Cynthia Dwork, Krishnaram Kenthapadi, Frank McSherry, Ilya Mironov, and Moni Naor. Our data, ourselves: Privacy via distributed noise generation. In EUROCRYPT, pages 486-503, 2006. Google Scholar
  18. Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam D. Smith. Calibrating noise to sensitivity in private data analysis. J. Priv. Confidentiality, 7(3):17-51, 2016. URL: https://doi.org/10.29012/jpc.v7i3.405.
  19. Cynthia Dwork, Frank McSherry, and Kunal Talwar. The price of privacy and the limits of LP decoding. In STOC, pages 85-94, 2007. Google Scholar
  20. Cynthia Dwork, Moni Naor, Toniann Pitassi, and Guy N. Rothblum. Differential privacy under continual observation. In STOC, pages 715-724, 2010. URL: https://doi.org/10.1145/1806689.1806787.
  21. Cynthia Dwork, Moni Naor, Omer Reingold, and Guy N. Rothblum. Pure differential privacy for rectangle queries via private partitions. In ASIACRYPT, pages 735-751, 2015. Google Scholar
  22. Cynthia Dwork, Moni Naor, Omer Reingold, Guy N. Rothblum, and Salil P. Vadhan. On the complexity of differentially private data release: efficient algorithms and hardness results. In STOC, pages 381-390, 2009. Google Scholar
  23. Cynthia Dwork and Aaron Roth. The algorithmic foundations of differential privacy. Found. Trends Theor. Comput. Sci., 9(3-4):211-407, 2014. URL: https://doi.org/10.1561/0400000042.
  24. Alexander Edmonds, Aleksandar Nikolov, and Jonathan R. Ullman. The power of factorization mechanisms in local and central differential privacy. In STOC, pages 425-438, 2020. Google Scholar
  25. Alessandro Epasto, Jieming Mao, Andres Munoz Medina, Vahab Mirrokni, Sergei Vassilvitskii, and Peilin Zhong. Differentially private continual releases of streaming frequency moment estimations. In ITCS, pages 48:1-48:24, 2023. Google Scholar
  26. Hendrik Fichtenberger, Monika Henzinger, and Wolfgang Ost. Differentially private algorithms for graphs under continual observation. In ESA, pages 42:1-42:16, 2021. Google Scholar
  27. Quan Geng, Wei Ding, Ruiqi Guo, and Sanjiv Kumar. Tight analysis of privacy and utility tradeoff in approximate differential privacy. In AISTATS, pages 89-99, 2020. Google Scholar
  28. Moritz Hardt and Kunal Talwar. On the geometry of differential privacy. In STOC, pages 705-714, 2010. Google Scholar
  29. Monika Henzinger, Jalaj Upadhyay, and Sarvagya Upadhyay. Almost tight error bounds on differentially private continual counting. In SODA, pages 5003-5039, 2023. Google Scholar
  30. James Honaker. Efficient use of differentially private binary trees. In TPDP, 2015. Google Scholar
  31. Peter Kairouz, Brendan McMahan, Shuang Song, Om Thakkar, Abhradeep Thakurta, and Zheng Xu. Practical and private (deep) learning without sampling or shuffling. In ICML, pages 5213-5225, 2021. Google Scholar
  32. Haim Kaplan, Katrina Ligett, Yishay Mansour, Moni Naor, and Uri Stemmer. Privately learning thresholds: Closing the exponential gap. In COLT, pages 2263-2285, 2020. Google Scholar
  33. Troy Lee, Adi Shraibman, and Robert Spalek. A direct product theorem for discrepancy. In CCC, pages 71-80, 2008. Google Scholar
  34. Chao Li, Gerome Miklau, Michael Hay, Andrew McGregor, and Vibhor Rastogi. The matrix mechanism: optimizing linear counting queries under differential privacy. VLDB J., 24(6):757-781, 2015. URL: https://doi.org/10.1007/s00778-015-0398-x.
  35. Roy Mathias. The hadamard operator norm of a circulant and applications. SIAM J. Matr. Anal. Appl., 14(4):1152-1167, 1993. Google Scholar
  36. Jiří Matoušek, Aleksandar Nikolov, and Kunal Talwar. Factorization norms and hereditary discrepancy. Intl. Math. Res. Not., 2020(3):751-780, 2018. Google Scholar
  37. Aleksandar Nikolov. An improved private mechanism for small databases. In ICALP, pages 1010-1021, 2015. Google Scholar
  38. Aleksandar Nikolov. Private query release via the Johnson-Lindenstrauss transform. In SODA, pages 4982-5002, 2023. Google Scholar
  39. Aleksandar Nikolov, Kunal Talwar, and Li Zhang. The geometry of differential privacy: the sparse and approximate cases. In STOC, pages 351-360, 2013. Google Scholar
  40. Wahbeh H. Qardaji, Weining Yang, and Ninghui Li. Differentially private grids for geospatial data. In ICDE, pages 757-768, 2013. Google Scholar
  41. Salil P. Vadhan. The complexity of differential privacy. In Yehuda Lindell, editor, Tutorials on the Foundations of Cryptography, pages 347-450. Springer International Publishing, 2017. URL: https://doi.org/10.1007/978-3-319-57048-8_7.
  42. Yonghui Xiao, Li Xiong, Liyue Fan, Slawomir Goryczka, and Haoran Li. DPCube: Differentially private histogram release through multidimensional partitioning. Trans. Data Priv., 7(3):195-222, 2014. Google Scholar
  43. Jun Zhang, Xiaokui Xiao, and Xing Xie. Privtree: A differentially private algorithm for hierarchical decompositions. In SIGMOD, pages 155-170, 2016. Google Scholar
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact