Document Open Access Logo

Pure Differentially Private Summation from Anonymous Messages

Authors Badih Ghazi, Noah Golowich, Ravi Kumar, Pasin Manurangsi, Rasmus Pagh, Ameya Velingker

PDF
Thumbnail PDF

File

LIPIcs.ITC.2020.15.pdf
  • Filesize: 0.64 MB
  • 23 pages

Document Identifiers

Author Details

Badih Ghazi
  • Google Research, Mountain View, CA, USA
Noah Golowich
  • Google Research, Mountain View, CA, USA
  • MIT, Cambridge, MA, USA
Ravi Kumar
  • Google Research, Mountain View, CA, USA
Pasin Manurangsi
  • Google Research, Mountain View, CA, USA
Rasmus Pagh
  • Google Research, Mountain View, CA, USA
  • IT University of Copenhagen, Denmark
  • Basic Algorithms Research Copenhagen, Denmark
Ameya Velingker
  • Google Research, Mountain View, CA, USA

Funding

  • Golowich, Noah: Supported at MIT by a Fannie & John Hertz Foundation Fellowship, an MIT Akamai Fellowship, and an NSF Graduate Fellowship.

Acknowledgements

We are grateful to Borja Balle, Kunal Talwar, and Vitaly Feldman for helpful discussions.

Cite AsGet BibTex

Badih Ghazi, Noah Golowich, Ravi Kumar, Pasin Manurangsi, Rasmus Pagh, and Ameya Velingker. Pure Differentially Private Summation from Anonymous Messages. In 1st Conference on Information-Theoretic Cryptography (ITC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 163, pp. 15:1-15:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.ITC.2020.15

Abstract

The shuffled (aka anonymous) model has recently generated significant interest as a candidate distributed privacy framework with trust assumptions better than the central model but with achievable error rates smaller than the local model. In this paper, we study pure differentially private protocols in the shuffled model for summation, a very basic and widely used primitive. Specifically: - For the binary summation problem where each of n users holds a bit as an input, we give a pure ε-differentially private protocol for estimating the number of ones held by the users up to an absolute error of O_{ε}(1), and where each user sends O_{ε}(log n) one-bit messages. This is the first pure protocol in the shuffled model with error o(√n) for constant values of ε. Using our binary summation protocol as a building block, we give a pure ε-differentially private protocol that performs summation of real numbers in [0, 1] up to an absolute error of O_{ε}(1), and where each user sends O_{ε}(log³ n) messages each consisting of O(log log n) bits. - In contrast, we show that for any pure ε-differentially private protocol for binary summation in the shuffled model having absolute error n^{0.5-Ω(1)}, the per user communication has to be at least Ω_{ε}(√{log n}) bits. This implies (i) the first separation between the (bounded-communication) multi-message shuffled model and the central model, and (ii) the first separation between pure and approximate differentially private protocols in the shuffled model. Interestingly, over the course of proving our lower bound, we have to consider (a generalization of) the following question that might be of independent interest: given γ ∈ (0, 1), what is the smallest positive integer m for which there exist two random variables X⁰ and X^1 supported on {0, … , m} such that (i) the total variation distance between X⁰ and X^1 is at least 1 - γ, and (ii) the moment generating functions of X⁰ and X^1 are within a constant factor of each other everywhere? We show that the answer to this question is m = Θ(√{log(1/γ)}).

Subject Classification

ACM Subject Classification
  • Security and privacy → Privacy-preserving protocols
  • Mathematics of computing → Probabilistic algorithms
  • Theory of computation → Communication complexity
Keywords
  • Pure differential privacy
  • Shuffled model
  • Anonymous messages
  • Summation
  • Communication bounds

Metrics

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

Related Versions

References

  1. Martín Abadi, Andy Chu, Ian J. Goodfellow, H. Brendan McMahan, Ilya Mironov, Kunal Talwar, and Li Zhang. Deep learning with differential privacy. In CCS, pages 308-318, 2016. URL: https://doi.org/10.1145/2976749.2978318.
  2. John M Abowd. The US Census Bureau adopts differential privacy. In KDD, pages 2867-2867, 2018. Google Scholar
  3. Shweta Agrawal, Craig Gentry, Shai Halevi, and Amit Sahai. Discrete Gaussian leftover hash lemma over infinite domains. In ASIACRYPT, pages 97-116, 2013. URL: https://doi.org/10.1007/978-3-642-42033-7_6.
  4. Apple Differential Privacy Team. Learning with privacy at scale. Apple Machine Learning Journal, 2017. Google Scholar
  5. Victor Balcer and Albert Cheu. Separating local & shuffled differential privacy via histograms. arXiv: 1911.06879, 2019. Google Scholar
  6. Borja Balle, James Bell, Adrià Gascón, and Kobbi Nissim. Differentially private summation with multi-message shuffling. arXiv: 1906.09116, 2019. Google Scholar
  7. Borja Balle, James Bell, Adrià Gascón, and Kobbi Nissim. Improved summation from shuffling. arXiv: 1909.11225, 2019. Google Scholar
  8. Borja Balle, James Bell, Adrià Gascón, and Kobbi Nissim. The privacy blanket of the shuffle model. In CRYPTO, pages 638-667, 2019. URL: https://doi.org/10.1007/978-3-030-26951-7_22.
  9. Borja Balle, James Bell, Adrià Gascón, and Kobbi Nissim. Private summation in the multi-message shuffle model. arXiv: 2002.00817, 2020. Google Scholar
  10. Amos Beimel, Kobbi Nissim, and Eran Omri. Distributed private data analysis: Simultaneously solving how and what. In CRYPTO, pages 451-468, 2008. Google Scholar
  11. Andrea Bittau, Úlfar Erlingsson, Petros Maniatis, Ilya Mironov, Ananth Raghunathan, David Lie, Mitch Rudominer, Ushasree Kode, Julien Tinnés, and Bernhard Seefeld. Prochlo: Strong privacy for analytics in the crowd. In SOSP, pages 441-459, 2017. Google Scholar
  12. Avrim Blum, Katrina Ligett, and Aaron Roth. A learning theory approach to non-interactive database privacy. In STOC, pages 609-618, 2008. Google Scholar
  13. Mark Bun, Jelani Nelson, and Uri Stemmer. Heavy hitters and the structure of local privacy. In PODS, pages 435-447, 2018. Google Scholar
  14. T.-H. Hubert Chan, Elaine Shi, and Dawn Song. Optimal lower bound for differentially private multi-party aggregation. In ESA, pages 277-288, 2012. URL: https://doi.org/10.1007/978-3-642-33090-2_25.
  15. Albert Cheu, Adam D. Smith, Jonathan Ullman, David Zeber, and Maxim Zhilyaev. Distributed differential privacy via shuffling. In EUROCRYPT, pages 375-403, 2019. URL: https://doi.org/10.1007/978-3-030-17653-2_13.
  16. Anindya De. Lower bounds in differential privacy. In TCC, pages 321-338, 2012. URL: https://doi.org/10.1007/978-3-642-28914-9_18.
  17. Bolin Ding, Janardhan Kulkarni, and Sergey Yekhanin. Collecting telemetry data privately. In NIPS, pages 3571-3580, 2017. Google Scholar
  18. 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
  19. Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In TCC, pages 265-284, 2006. Google Scholar
  20. Úlfar Erlingsson, Vitaly Feldman, Ilya Mironov, Ananth Raghunathan, Shuang Song, Kunal Talwar, and Abhradeep Thakurta. Encode, shuffle, analyze privacy revisited: Formalizations and empirical evaluation. arXiv:2001.03618, 2020. Google Scholar
  21. Úlfar Erlingsson, Vitaly Feldman, Ilya Mironov, Ananth Raghunathan, Kunal Talwar, and Abhradeep Thakurta. Amplification by shuffling: From local to central differential privacy via anonymity. In SODA, pages 2468-2479, 2019. Google Scholar
  22. Úlfar Erlingsson, Vasyl Pihur, and Aleksandra Korolova. RAPPOR: Randomized aggregatable privacy-preserving ordinal response. In CCS, pages 1054-1067, 2014. Google Scholar
  23. Craig Gentry, Chris Peikert, and Vinod Vaikuntanathan. Trapdoors for hard lattices and new cryptographic constructions. In STOC, pages 197-206, 2008. URL: https://doi.org/10.1145/1374376.1374407.
  24. Badih Ghazi, Noah Golowich, Ravi Kumar, Pasin Manurangsi, Rasmus Pagh, and Ameya Velingker. Pure differentially private summation from anonymous messages. arXiv: 2002.01919, 2020. URL: http://arxiv.org/abs/2002.01919.
  25. Badih Ghazi, Noah Golowich, Ravi Kumar, Rasmus Pagh, and Ameya Velingker. On the power of multiple anonymous messages. Cryptology ePrint Archive, Report 2019/1382, 2019. Google Scholar
  26. Badih Ghazi, Pasin Manurangsi, Rasmus Pagh, and Ameya Velingker. Private aggregation from fewer anonymous messages. arXiv: 1909.11073, 2019. Google Scholar
  27. Badih Ghazi, Rasmus Pagh, and Ameya Velingker. Scalable and differentially private distributed aggregation in the shuffled model. arXiv: 1906.08320, 2019. Google Scholar
  28. Andy Greenberg. Apple’s "differential privacy" is about collecting your data - but not your data. Wired, June, 13, 2016. Google Scholar
  29. Moritz Hardt and Guy N. Rothblum. A multiplicative weights mechanism for privacy-preserving data analysis. In FOCS, pages 61-70, 2010. Google Scholar
  30. Moritz Hardt and Kunal Talwar. On the geometry of differential privacy. In STOC, pages 705-714, 2010. Google Scholar
  31. Yuval Ishai, Eyal Kushilevitz, Rafail Ostrovsky, and Amit Sahai. Cryptography from anonymity. In FOCS, pages 239-248, 2006. Google Scholar
  32. Peter Kairouz, H. Brendan McMahan, Brendan Avent, Aurélien Bellet, Mehdi Bennis, Arjun Nitin Bhagoji, Keith Bonawitz, Zachary Charles, Graham Cormode, Rachel Cummings, Rafael G. L. D'Oliveira, Salim El Rouayheb, David Evans, Josh Gardner, Zachary Garrett, Adrià Gascón, Badih Ghazi, Phillip B. Gibbons, Marco Gruteser, Zaid Harchaoui, Chaoyang He, Lie He, Zhouyuan Huo, Ben Hutchinson, Justin Hsu, Martin Jaggi, Tara Javidi, Gauri Joshi, Mikhail Khodak, Jakub Konečný, Aleksandra Korolova, Farinaz Koushanfar, Sanmi Koyejo, Tancrède Lepoint, Yang Liu, Prateek Mittal, Mehryar Mohri, Richard Nock, Ayfer Özgür, Rasmus Pagh, Mariana Raykova, Hang Qi, Daniel Ramage, Ramesh Raskar, Dawn Song, Weikang Song, Sebastian U. Stich, Ziteng Sun, Ananda Theertha Suresh, Florian Tramèr, Praneeth Vepakomma, Jianyu Wang, Li Xiong, Zheng Xu, Qiang Yang, Felix X. Yu, Han Yu, and Sen Zhao. Advances and open problems in federated learning. arXiv: 1912.04977, 2019. Google Scholar
  33. Shiva Prasad Kasiviswanathan, Homin K. Lee, Kobbi Nissim, Sofya Rashkodnikova, and Adam Smith. What can we learn privately? In FOCS, pages 531-540, 2008. Google Scholar
  34. Jakub Konečny, H Brendan McMahan, Felix X Yu, Peter Richtárik, Ananda Theertha Suresh, and Dave Bacon. Federated learning: Strategies for improving communication efficiency. arXiv: 1610.05492, 2016. Google Scholar
  35. Daniele Micciancio and Oded Regev. Worst-case to average-case reductions based on Gaussian measures. SICOMP, 37(1):267-302, 2007. URL: https://doi.org/10.1137/S0097539705447360.
  36. Ilya Mironov. Rényi differential privacy. In CSF, pages 263-275, 2017. URL: https://doi.org/10.1109/CSF.2017.11.
  37. Aleksandar Nikolov, Kunal Talwar, and Li Zhang. On the geometry of differential privacy: the sparse and approximate cases. In STOC, pages 351-360, 2013. Google Scholar
  38. Stephen Shankland. How Google tricks itself to protect Chrome user privacy. CNET, October, 2014. Google Scholar
  39. Thomas Steinke and Jonathan Ullman. Between pure and approximate differential privacy. arXiv: 1501.06095, 2015. Google Scholar
  40. Salil Vadhan. The Complexity of Differential Privacy, pages 347-450. Springer International Publishing, 2017. Google Scholar
  41. Stanley L Warner. Randomized response: A survey technique for eliminating evasive answer bias. JASA, 60(309):63-69, 1965. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

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