Document Open Access Logo

Differential Secrecy for Distributed Data and Applications to Robust Differentially Secure Vector Summation

Author Kunal Talwar

PDF
Thumbnail PDF

File

LIPIcs.FORC.2022.7.pdf
  • Filesize: 0.7 MB
  • 16 pages

Document Identifiers

Author Details

Kunal Talwar
  • Apple, Cupertino, CA, USA

Acknowledgements

We would like to thank Ulfar Erlingsson for many helpful discussions, and the anonymous referees for their feedback.

Cite AsGet BibTex

Kunal Talwar. Differential Secrecy for Distributed Data and Applications to Robust Differentially Secure Vector Summation. In 3rd Symposium on Foundations of Responsible Computing (FORC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 218, pp. 7:1-7:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.FORC.2022.7

Abstract

Computing the noisy sum of real-valued vectors is an important primitive in differentially private learning and statistics. In private federated learning applications, these vectors are held by client devices, leading to a distributed summation problem. Standard Secure Multiparty Computation protocols for this problem are susceptible to poisoning attacks, where a client may have a large influence on the sum, without being detected. In this work, we propose a poisoning-robust private summation protocol in the multiple-server setting, recently studied in PRIO [Henry Corrigan-Gibbs and Dan Boneh, 2017]. We present a protocol for vector summation that verifies that the Euclidean norm of each contribution is approximately bounded. We show that by relaxing the security constraint in SMC to a differential privacy like guarantee, one can improve over PRIO in terms of communication requirements as well as the client-side computation. Unlike SMC algorithms that inevitably cast integers to elements of a large finite field, our algorithms work over integers/reals, which may allow for additional efficiencies.

Subject Classification

ACM Subject Classification
  • Security and privacy → Privacy-preserving protocols
Keywords
  • Zero Knowledge
  • Secure Summation
  • Differential Privacy

Metrics

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

References

  1. Naman Agarwal, Ananda Theertha Suresh, Felix Xinnan X Yu, Sanjiv Kumar, and Brendan McMahan. cpsgd: Communication-efficient and differentially-private distributed sgd. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett, editors, Advances in Neural Information Processing Systems 31, pages 7564-7575. Curran Associates, Inc., 2018. URL: http://papers.nips.cc/paper/7984-cpsgd-communication-efficient-and-differentially-private-distributed-sgd.pdf.
  2. Michael Backes, Aniket Kate, Sebastian Meiser, and Tim Ruffing. Secrecy without perfect randomness: Cryptography with (bounded) weak sources. In Tal Malkin, Vladimir Kolesnikov, Allison Bishop Lewko, and Michalis Polychronakis, editors, Applied Cryptography and Network Security, pages 675-695, Cham, 2015. Springer International Publishing. Google Scholar
  3. B. Balle, J. Bell, A. Gascón, and Kobbi Nissim. Private summation in the multi-message shuffle model. ArXiv, abs/2002.00817, 2020. Google Scholar
  4. Borja Balle, James Bell, Adrià Gascón, and Kobbi Nissim. The privacy blanket of the shuffle model. In Alexandra Boldyreva and Daniele Micciancio, editors, Advances in Cryptology - CRYPTO 2019, pages 638-667, Cham, 2019. Springer International Publishing. Google Scholar
  5. Amos Beimel, Kobbi Nissim, and Eran Omri. Distributed private data analysis: Simultaneously solving how and what. In David Wagner, editor, Advances in Cryptology - CRYPTO 2008, pages 451-468, Berlin, Heidelberg, 2008. Springer Berlin Heidelberg. Google Scholar
  6. James Bell, K. A. Bonawitz, Adrià Gascón, Tancrède Lepoint, and Mariana Raykova. Secure single-server aggregation with (poly)logarithmic overhead. Cryptology ePrint Archive, Report 2020/704, 2020. URL: https://eprint.iacr.org/2020/704.
  7. Andrea Bittau, Úlfar Erlingsson, Petros Maniatis, Ilya Mironov, Ananth Raghunathan, David Lie, Mitch Rudominer, Ushasree Kode, Julien Tinnes, and Bernhard Seefeld. Prochlo: Strong privacy for analytics in the crowd. In Proceedings of the 26th Symposium on Operating Systems Principles, SOSP '17, pages 441-459, New York, NY, USA, 2017. Association for Computing Machinery. URL: https://doi.org/10.1145/3132747.3132769.
  8. Keith Bonawitz, Vladimir Ivanov, Ben Kreuter, Antonio Marcedone, H. Brendan McMahan, Sarvar Patel, Daniel Ramage, Aaron Segal, and Karn Seth. Practical secure aggregation for privacy-preserving machine learning. In Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security, CCS '17, pages 1175-1191, New York, NY, USA, 2017. Association for Computing Machinery. URL: https://doi.org/10.1145/3133956.3133982.
  9. Dan Boneh, Elette Boyle, Henry Corrigan-Gibbs, Niv Gilboa, and Yuval Ishai. Zero-knowledge proofs on secret-shared data via fully linear pcps. Cryptology ePrint Archive, Report 2019/188, 2019. URL: https://ia.cr/2019/188.
  10. Clément L. Canonne, Gautam Kamath, and Thomas Steinke. The discrete gaussian for differential privacy, 2020. URL: http://arxiv.org/abs/2004.00010.
  11. T. H. Hubert Chan, Elaine Shi, and Dawn Song. Privacy-preserving stream aggregation with fault tolerance. In Angelos D. Keromytis, editor, Financial Cryptography and Data Security, pages 200-214, Berlin, Heidelberg, 2012. Springer Berlin Heidelberg. Google Scholar
  12. Albert Cheu, Adam Smith, and Jonathan Ullman. Manipulation attacks in local differential privacy, 2019. URL: http://arxiv.org/abs/1909.09630.
  13. Albert Cheu, Adam Smith, Jonathan Ullman, David Zeber, and Maxim Zhilyaev. Distributed differential privacy via shuffling. In Yuval Ishai and Vincent Rijmen, editors, Advances in Cryptology - EUROCRYPT 2019, pages 375-403, Cham, 2019. Springer International Publishing. Google Scholar
  14. Henry Corrigan-Gibbs and Dan Boneh. Prio: Private, robust, and scalable computation of aggregate statistics. In 14th USENIX Symposium on Networked Systems Design and Implementation (NSDI 17), pages 259-282, Boston, MA, 2017. USENIX Association. URL: https://www.usenix.org/conference/nsdi17/technical-sessions/presentation/corrigan-gibbs.
  15. Cynthia Dwork, Krishnaram Kenthapadi, Frank McSherry, Ilya Mironov, and Moni Naor. Our data, ourselves: Privacy via distributed noise generation. In Advances in Cryptology (EUROCRYPT 2006), volume 4004 of Lecture Notes in Computer Science, pages 486-503. Springer Verlag, May 2006. URL: https://www.microsoft.com/en-us/research/publication/our-data-ourselves-privacy-via-distributed-noise-generation/.
  16. Cynthia Dwork and Aaron Roth. The algorithmic foundations of differential privacy. Found. Trends Theor. Comput. Sci., 9(3-4):211-407, August 2014. Google Scholar
  17. Ú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 Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '19, pages 2468-2479, USA, 2019. Society for Industrial and Applied Mathematics. Google Scholar
  18. Vitaly Feldman, Audra McMillan, and Kunal Talwar. Hiding among the clones: A simple and nearly optimal analysis of privacy amplification by shuffling. In Proceedings of the 62nd Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2021. arXiv:2012.12803 [cs.LG]. Google Scholar
  19. Badih Ghazi, Ravi Kumar, Pasin Manurangsi, Rasmus Pagh, and Amer Sinha. Differentially private aggregation in the shuffle model: Almost central accuracy in almost a single message. In Marina Meila and Tong Zhang, editors, Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pages 3692-3701. PMLR, 18-24 July 2021. URL: https://proceedings.mlr.press/v139/ghazi21a.html.
  20. Badih Ghazi, Pasin Manurangsi, Rasmus Pagh, and Ameya Velingker. Private aggregation from fewer anonymous messages. In Anne Canteaut and Yuval Ishai, editors, Advances in Cryptology - EUROCRYPT 2020, pages 798-827, Cham, 2020. Springer International Publishing. Google Scholar
  21. Slawomir Goryczka and Li Xiong. A comprehensive comparison of multiparty secure additions with differential privacy. IEEE Transactions on Dependable and Secure Computing, 14:463-477, 2017. Google Scholar
  22. Vipul Goyal, Ilya Mironov, Omkant Pandey, and Amit Sahai. Accuracy-privacy tradeoffs for two-party differentially private protocols. In CRYPTO, pages 298-315. Springer, 2013. URL: https://doi.org/10.1007/978-3-642-40041-4_17.
  23. Y. Ishai, E. Kushilevitz, R. Ostrovsky, and A. Sahai. Cryptography from anonymity. In 2006 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS'06), pages 239-248, 2006. Google Scholar
  24. P. Kairouz, S. Oh, and P. Viswanath. Differentially private multi-party computation. In 2016 Annual Conference on Information Science and Systems (CISS), pages 128-132, March 2016. URL: https://doi.org/10.1109/CISS.2016.7460489.
  25. Peter Kairouz, Sewoong Oh, and Pramod Viswanath. Secure multi-party differential privacy. In C. Cortes, N. D. Lawrence, D. D. Lee, M. Sugiyama, and R. Garnett, editors, Advances in Neural Information Processing Systems 28, pages 2008-2016. Curran Associates, Inc., 2015. URL: http://papers.nips.cc/paper/6004-secure-multi-party-differential-privacy.pdf.
  26. B. Laurent and P. Massart. Adaptive estimation of a quadratic functional by model selection. Ann. Statist., 28(5):1302-1338, October 2000. URL: https://doi.org/10.1214/aos/1015957395.
  27. Andrew McGregor, Ilya Mironov, Toniann Pitassi, Omer Reingold, Kunal Talwar, and Salil Vadhan. The limits of two-party differential privacy. In 51st Annual Symposium on Foundations of Computer Science, pages 81-90. IEEE, 2010. Google Scholar
  28. Ilya Mironov, Omkant Pandey, Omer Reingold, and Salil Vadhan. Computational differential privacy. In Shai Halevi, editor, Advances in Cryptology - CRYPTO 2009, pages 126-142, Berlin, Heidelberg, 2009. Springer Berlin Heidelberg. Google Scholar
  29. Jinhyun So, Basak Guler, and A. Salman Avestimehr. Turbo-aggregate: Breaking the quadratic aggregation barrier in secure federated learning, 2020. URL: http://arxiv.org/abs/2002.04156.
  30. Úlfar Erlingsson, Vitaly Feldman, Ilya Mironov, Ananth Raghunathan, Shuang Song, Kunal Talwar, and Abhradeep Thakurta. Encode, shuffle, analyze privacy revisited: Formalizations and empirical evaluation, 2020. URL: http://arxiv.org/abs/2001.03618.
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