More Web Proxy on the site http://driver.im/

research-article

Public Access

The limits of pan privacy and shuffle privacy for learning and estimation

Authors:

Jonathan UllmanAuthors Info & Claims

STOC 2021: Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing

Pages 1081 - 1094

https://doi.org/10.1145/3406325.3450995

Published: 15 June 2021 Publication History

Abstract

There has been a recent wave of interest in intermediate trust models for differential privacy that eliminate the need for a fully trusted central data collector, but overcome the limitations of local differential privacy. This interest has led to the introduction of the shuffle model (Cheu et al., EUROCRYPT 2019; Erlingsson et al., SODA 2019) and revisiting the pan-private model (Dwork et al., ITCS 2010). The message of this line of work is that, for a variety of low-dimensional problems—such as counts, means, and histograms—these intermediate models offer nearly as much power as central differential privacy. However, there has been considerably less success using these models for high-dimensional learning and estimation problems.

In this work we prove the first non-trivial lower bounds for high-dimensional learning and estimation in both the pan-private model and the general multi-message shuffle model. Our lower bounds apply to a variety of problems—for example, we show that, private agnostic learning of parity functions over d bits requires Ω(2^d/2) samples in these models, and privately selecting the most common attribute from a set of d choices requires Ω(d^1/2) samples, both of which are exponential separations from the central model.

References

[1]

Kareem Amin, Matthew Joseph, Jieming Mao, Jacob D. Abernethy, and Shivani Agarwal. 2020. Pan-Private Uniformity Testing. In Conference on Learning Theory, COLT 2020, 9-12 July 2020, Virtual Event [Graz, Austria]. Proceedings of Machine Learning Research. 125, PMLR. Pages 183–218. arxiv:1911.01452

[2]

Victor Balcer, Albert Cheu, Yael Tauman Kalai, Adam D. Smith, and Daniel Wichs. 2020. Separating Local & Shuffled Differential Privacy via Histograms. In 1st Conference on Information-Theoretic Cryptography, ITC 2020, June 17-19, 2020, Boston, MA, USA. LIPIcs. 163, Schloss Dagstuhl - Leibniz-Zentrum für Informatik. Pages 1:1–1:14. https://doi.org/10.4230/LIPIcs.ITC.2020.1

[3]

Victor Balcer, Albert Cheu, Matthew Joseph, Jieming Mao, and Dániel Marx. 2021. Connecting Robust Shuffle Privacy and Pan-Privacy. In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, Virtual Conference, January 10 - 13, 2021. SIAM. Pages 2384–2403. https://doi.org/10.1137/1.9781611976465.142

[4]

Borja Balle, James Bell, Adri\`a Gascón, Kobbi Nissim, Alexandra Boldyreva, and Daniele Micciancio. 2019. The Privacy Blanket of the Shuffle Model. In Advances in Cryptology - CRYPTO 2019 - 39th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 18-22, 2019, Proceedings, Part II. Lecture Notes in Computer Science. 11693, Springer. Pages 638–667. https://doi.org/10.1007/978-3-030-26951-7_22

Digital Library

[5]

Borja Balle, James Bell, Adri\`a Gascón, Kobbi Nissim, Jay Ligatti, Xinming Ou, Jonathan Katz, and Giovanni Vigna. 2020. Private Summation in the Multi-Message Shuffle Model. In CCS '20: 2020 ACM SIGSAC Conference on Computer and Communications Security, Virtual Event, USA, November 9-13, 2020. ACM. Pages 657–676. https://doi.org/10.1145/3372297.3417242

Digital Library

[6]

Raef Bassily and Adam Smith. 2015. Local, private, efficient protocols for succinct histograms. In ACM Symposium on Theory of Computing. STOC '15. ACM. Pages 127–135. https://doi.org/10.1145/2746539.2746632

Digital Library

[7]

Amos Beimel, Iftach Haitner, Kobbi Nissim, Uri Stemmer, Rafael Pass, and Krzysztof Pietrzak. 2020. On the Round Complexity of the Shuffle Model. In Theory of Cryptography - 18th International Conference, TCC 2020, Durham, NC, USA, November 16-19, 2020, Proceedings, Part II. Lecture Notes in Computer Science. 12551, Springer. Pages 683–712. https://doi.org/10.1007/978-3-030-64378-2_24

Digital Library

[8]

Amos Beimel, Kobbi Nissim, and Eran Omri. 2008. Distributed private data analysis: Simultaneously solving how and what. In International Cryptology Conference. CRYPTO '08. Springer. Pages 451–468. https://doi.org/10.1007/978-3-540-85174-5_25

Digital Library

[9]

Andrea Bittau, \'Ulfar Erlingsson, Petros Maniatis, Ilya Mironov, Ananth Raghunathan, David Lie, Mitch Rudominer, Ushasree Kode, Julien Tinnes, and Bernhard Seefeld. 2017. PROCHLO: Strong Privacy for Analytics in the Crowd. In ACM Symposium on Operating Systems Principles. SOSP '17. ACM. Pages 441–459. https://doi.org/10.1145/3132747.3132769

Digital Library

[10]

Mark Bun, Cynthia Dwork, Guy N Rothblum, and Thomas Steinke. 2018. Composable and versatile privacy via truncated CDP. In Annual ACM Symposium on Theory of Computing. STOC '18. ACM. Pages 74–86. https://doi.org/10.1145/3188745.3188946

Digital Library

[11]

Mark Bun, Gautam Kamath, Thomas Steinke, and Zhiwei Steven Wu. 2019. Private Hypothesis Selection. In Advances in Neural Information Processing Systems. NeurIPS '19. Pages 156–167. arxiv:1905.13229

[12]

Mark Bun, Thomas Steinke, Martin Hirt, and Adam D. Smith. 2016. Concentrated Differential Privacy: Simplifications, Extensions, and Lower Bounds. In Theory of Cryptography - 14th International Conference, TCC 2016-B, Beijing, China, October 31 - November 3, 2016, Proceedings, Part I. Lecture Notes in Computer Science. 9985, Pages 635–658. https://doi.org/10.1007/978-3-662-53641-4_24

Digital Library

[13]

Mark Bun, Jonathan Ullman, and Salil Vadhan. 2014. Fingerprinting Codes and the Price of Approximate Differential Privacy. In ACM Symposium on the Theory of Computing. STOC '14. ACM. Pages 1–10. https://doi.org/10.1145/2591796.2591877

Digital Library

[14]

T.-H. Hubert Chan, Elaine Shi, and Dawn Song. 2012. Optimal Lower Bound for Differentially Private Multiparty Aggregation. In European Symposium on Algorithms. ESA '12. Pages 277–288. https://eprint.iacr.org/2012/373

[15]

Lijie Chen, Badih Ghazi, Ravi Kumar, Pasin Manurangsi, and James R. Lee. 2021. On Distributed Differential Privacy and Counting Distinct Elements. In 12th Innovations in Theoretical Computer Science Conference, ITCS 2021, January 6-8, 2021, Virtual Conference. LIPIcs. 185, Schloss Dagstuhl - Leibniz-Zentrum für Informatik. Pages 56:1–56:18. https://doi.org/10.4230/LIPIcs.ITCS.2021.56

[16]

Albert Cheu, Adam D. Smith, Jonathan R. Ullman, David Zeber, Maxim Zhilyaev, Yuval Ishai, and Vincent Rijmen. 2019. Distributed Differential Privacy via Shuffling. In Advances in Cryptology - EUROCRYPT 2019 - 38th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Darmstadt, Germany, May 19-23, 2019, Proceedings, Part I. Lecture Notes in Computer Science. 11476, Springer. Pages 375–403. https://doi.org/10.1007/978-3-030-17653-2_13

Digital Library

[17]

Irit Dinur and Kobbi Nissim. 2003. Revealing information while preserving privacy. In Proceedings of the 22nd ACM Symposium on Principles of Database Systems. PODS '03. ACM. Pages 202–210. https://doi.org/10.1145/773153.773173

Digital Library

[18]

Jinshuo Dong, Aaron Roth, and Weijie J Su. 2019. Gaussian differential privacy. arXiv preprint arXiv:1905.02383, 2019. arxiv:1905.02383

[19]

John Duchi, Michael Jordan, and Martin Wainwright. 2013. Local Privacy and Statistical Minimax Rates. In IEEE Symposium on Foundations of Computer Science. FOCS '13. IEEE Computer Society. Pages 429–438. https://doi.org/10.1109/FOCS.2013.53

Digital Library

[20]

John Duchi and Ryan Rogers. 2019. Lower bounds for locally private estimation via communication complexity. In Annual Conference on Learning Theory. COLT '19. JMLR.org. Pages 1161–1191. arxiv:1902.00582

[21]

John C. Duchi and Feng Ruan. 2018. The Right Complexity Measure in Locally Private Estimation: It is not the Fisher Information. arXiv preprint arXiv:1806.05756, 2018.

[22]

Cynthia Dwork, Krishnaram Kenthapadi, Frank McSherry, Ilya Mironov, Moni Naor, and Serge Vaudenay. 2006. Our Data, Ourselves: Privacy Via Distributed Noise Generation. In Advances in Cryptology - EUROCRYPT 2006, 25th Annual International Conference on the Theory and Applications of Cryptographic Techniques. Lecture Notes in Computer Science. 4004, Springer. Pages 486–503. https://doi.org/10.1007/11761679_29

Digital Library

[23]

Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. 2006. Calibrating Noise to Sensitivity in Private Data Analysis. In Conference on Theory of Cryptography. TCC '06. Springer. Pages 265–284. https://doi.org/10.1007/11681878_14

Digital Library

[24]

Cynthia Dwork, Moni Naor, Toniann Pitassi, Guy N Rothblum, and Sergey Yekhanin. 2010. Pan-Private Streaming Algorithms. In Innovations in Computer Science. ICS '10. Tsinghua University Press. Pages 66–80.

[25]

Cynthia Dwork and Guy N Rothblum. 2016. Concentrated differential privacy. arXiv preprint arXiv:1603.01887, 2016. arxiv:1603.01887

[26]

Cynthia Dwork, Adam Smith, Thomas Steinke, and Jonathan Ullman. 2017. Exposed! A Survey of Attacks on Private Data. Annual Review of Statistics and Its Application, 4, 2017. Pages 61–84.

[27]

Cynthia Dwork, Adam Smith, Thomas Steinke, Jonathan Ullman, and Salil Vadhan. 2015. Robust Traceability from Trace Amounts. In IEEE Symposium on Foundations of Computer Science. FOCS '15. IEEE Computer Society. https://doi.org/10.1109/FOCS.2015.46

Digital Library

[28]

Alexander Edmonds, Aleksandar Nikolov, Jonathan R. Ullman, Konstantin Makarychev, Yury Makarychev, Madhur Tulsiani, Gautam Kamath, and Julia Chuzhoy. 2020. The power of factorization mechanisms in local and central differential privacy. In Proccedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, Chicago, IL, USA, June 22-26, 2020. ACM. Pages 425–438. https://doi.org/10.1145/3357713.3384297

Digital Library

[29]

\'Ulfar Erlingsson, Vitaly Feldman, Ilya Mironov, Ananth Raghunathan, Kunal Talwar, and Abhradeep Thakurta. 2019. Amplification by Shuffling: From Local to Central Differential Privacy via Anonymity. In ACM-SIAM Symposium on Discrete Algorithms. SODA '19. ACM. Pages 2468–2479. https://doi.org/10.1137/1.9781611975482.151

[30]

Badih Ghazi, Noah Golowich, Ravi Kumar, Pasin Manurangsi, Rasmus Pagh, and Ameya Velingker. 2020. Pure Differentially Private Summation from Anonymous Messages. In 1st Conference on Information-Theoretic Cryptography. ITC '20. Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.ITC.2020.15

[31]

Badih Ghazi, Noah Golowich, Ravi Kumar, Rasmus Pagh, and Ameya Velingker. 2020. On the Power of Multiple Anonymous Messages. In Foundations of Responsible Computing. FORC '20. arxiv:1908.11358

[32]

Badih Ghazi, Ravi Kumar, Pasin Manurangsi, and Rasmus Pagh. 2020. Private Counting from Anonymous Messages: Near-Optimal Accuracy with Vanishing Communication Overhead. In Proceedings of the 37th International Conference on Machine Learning, ICML 2020, 13-18 July 2020, Virtual Event. Proceedings of Machine Learning Research. 119, PMLR. Pages 3505–3514. http://proceedings.mlr.press/v119/ghazi20a.html

[33]

Badih Ghazi, Pasin Manurangsi, Rasmus Pagh, and Ameya Velingker. 2020. Private Aggregation from Fewer Anonymous Messages. In Annual Conference on the Theory and Applications of Cryptographic Techniques. EUROCRYPT '20. Pages 798–827. https://doi.org/10.1007/978-3-030-45724-2_27

Digital Library

[34]

Badih Ghazi, Rasmus Pagh, and Ameya Velingker. 2019. Scalable and Differentially Private Distributed Aggregation in the Shuffled Model. CoRR, abs/1906.08320, 2019. arxiv:1906.08320

[35]

Sivakanth Gopi, Gautam Kamath, Janardhan Kulkarni, Aleksandar Nikolov, Zhiwei Steven Wu, Huanyu Zhang, Jacob D. Abernethy, and Shivani Agarwal. 2020. Locally Private Hypothesis Selection. In Conference on Learning Theory, COLT 2020, 9-12 July 2020, Virtual Event [Graz, Austria]. Proceedings of Machine Learning Research. 125, PMLR. Pages 1785–1816. arxiv:2002.09465

[36]

Moritz Hardt and Guy Rothblum. 2014. A Multiplicative Weights Mechanism for Privacy-Preserving Data Analysis. In IEEE Symposium on Foundations of Computer Science. FOCS '10. IEEE Computer Society. Pages 61–70. https://doi.org/10.1109/FOCS.2010.85

Digital Library

[37]

Matthew Joseph, Janardhan Kulkarni, Jieming Mao, and Zhiwei Steven Wu. 2018. Locally Private Gaussian Estimation. arXiv preprint arXiv:1811.08382, 2018.

[38]

Matthew Joseph, Jieming Mao, Seth Neel, and Aaron Roth. 2019. The role of interactivity in local differential privacy. In IEEE Symposium on Foundations of Computer Science. FOCS '19. IEEE Computer Society. Pages 94–105. https://doi.org/10.1109/FOCS.2019.00015

[39]

Peter Kairouz, Sewoong Oh, and Pramod Viswanath. 2015. The composition theorem for differential privacy. In International Conference on Machine Learning. ICML '15. PMLR. Pages 1376–1385. arxiv:1311.0776

[40]

Shiva Prasad Kasiviswanathan, Homin K. Lee, Kobbi Nissim, Sofya Raskhodnikova, and Adam Smith. 2008. What Can We Learn Privately? In IEEE Symposium on Foundations of Computer Science. FOCS '08. IEEE Computer Society. Pages 531–540. https://doi.org/10.1109/FOCS.2008.27

Digital Library

[41]

Michael Kearns. 1998. Efficient noise-tolerant learning from statistical queries. J. ACM, 45, 6, 1998. Pages 983–1006. https://doi.org/10.1145/293347.293351

Digital Library

[42]

Andrew McGregor, Ilya Mironov, Toniann Pitassi, Omer Reingold, Kunal Talwar, and Salil P. Vadhan. 2010. The Limits of Two-Party Differential Privacy. In 51th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2010, October 23-26, 2010, Las Vegas, Nevada, USA. IEEE Computer Society. Pages 81–90. https://doi.org/10.1109/FOCS.2010.14

Digital Library

[43]

Frank McSherry and Kunal Talwar. 2007. Mechanism Design via Differential Privacy. In IEEE Symposium on Foundations of Computer Science. FOCS '07. IEEE Computer Society. Pages 94–103. https://doi.org/10.1109/FOCS.2007.41

Digital Library

[44]

Darakhshan Mir, Shan Muthukrishnan, Aleksandar Nikolov, and Rebecca N Wright. 2011. Pan-private algorithms via statistics on sketches. In ACM Symposium on Principles of Database Systems. PODS '11. ACM. Pages 37–48. arxiv:1009.1544

Digital Library

[45]

Ilya Mironov. 2017. Rényi differential privacy. In IEEE Computer Security Foundations Symposium. CSF '17. IEEE Computer Society. Pages 263–275. arxiv:1702.07476

[46]

Thomas Steinke, Jonathan R. Ullman, and Chris Umans. 2017. Tight Lower Bounds for Differentially Private Selection. In 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, October 15-17, 2017. FOCS '17. IEEE Computer Society. Pages 552–563.

[47]

Jonathan Ullman. 2018. Tight Bounds for Locally Differentially Private Selection. arXiv preprint arXiv:1802.02638, 2018.

Cited By

Asi HFeldman VNelson JNguyen HTalwar KZhou SSalakhutdinov RKolter ZHeller KWeller AOliver NScarlett JBerkenkamp F(2024)Private vector mean estimation in the shuffle modelProceedings of the 41st International Conference on Machine Learning10.5555/3692070.3692147(1945-1970)Online publication date: 21-Jul-2024
https://dl.acm.org/doi/10.5555/3692070.3692147
Damgård IKeller HNelson BOrlandi CPagh RChua TNgo CKa-Wei Lee RKumar RLauw H(2024)Differentially Private Selection from Secure Distributed ComputingProceedings of the ACM Web Conference 202410.1145/3589334.3645435(1103-1114)Online publication date: 13-May-2024
https://dl.acm.org/doi/10.1145/3589334.3645435
Alon BNaor MOmri EStemmer U(2024)MPC for Tech Giants (GMPC): Enabling Gulliver and the Lilliputians to Cooperate AmicablyAdvances in Cryptology – CRYPTO 202410.1007/978-3-031-68397-8_3(74-108)Online publication date: 16-Aug-2024
https://doi.org/10.1007/978-3-031-68397-8_3
Show More Cited By

Index Terms

The limits of pan privacy and shuffle privacy for learning and estimation

Recommendations

Enhanced Privacy Bound for Shuffle Model with Personalized Privacy
CIKM '24: Proceedings of the 33rd ACM International Conference on Information and Knowledge Management

The shuffle model of Differential Privacy (DP) is an enhanced privacy protocol which significantly amplifies the central DP guarantee by anonymizing and shuffling the local randomized data. Yet, deriving a tight privacy bound is challenging due to its ...
Tight Differential Privacy Guarantees for the Shuffle Model with k-Randomized Response
Foundations and Practice of Security
Abstract
Most differentially private algorithms assume a central model in which a reliable third party inserts noise to queries made on datasets, or a local model where the data owners directly perturb their data. However, the central model is vulnerable ...
Bounded privacy-utility monotonicity indicating bounded tradeoff of differential privacy mechanisms
Abstract
Differential privacy can achieve the tradeoff between privacy and utility by using privacy metric and utility metric. However, since privacy metric and utility metric may not be bounded, differential privacy can not provide the bounded tradeoff. ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

STOC 2021: Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing

June 2021

1797 pages

ISBN:9781450380539

DOI:10.1145/3406325

General Chair:
Samir Khuller
Northwestern University, USA
,
Program Chair:
Virginia Vassilevska Williams
Massachusetts Institute of Technology, USA

Copyright © 2021 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 15 June 2021

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

NSF

Conference

STOC '21

Sponsor:

SIGACT

STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing

June 21 - 25, 2021

Virtual, Italy

Acceptance Rates

Overall Acceptance Rate 1,469 of 4,586 submissions, 32%

Upcoming Conference

STOC '25

Sponsor:
sigact

57th Annual ACM Symposium on Theory of Computing (STOC 2025)

June 23 - 27, 2025

Prague , Czech Republic

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

8
Total Citations
View Citations
363
Total Downloads

Downloads (Last 12 months)78
Downloads (Last 6 weeks)11

Reflects downloads up to 06 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Asi HFeldman VNelson JNguyen HTalwar KZhou SSalakhutdinov RKolter ZHeller KWeller AOliver NScarlett JBerkenkamp F(2024)Private vector mean estimation in the shuffle modelProceedings of the 41st International Conference on Machine Learning10.5555/3692070.3692147(1945-1970)Online publication date: 21-Jul-2024
https://dl.acm.org/doi/10.5555/3692070.3692147
Damgård IKeller HNelson BOrlandi CPagh RChua TNgo CKa-Wei Lee RKumar RLauw H(2024)Differentially Private Selection from Secure Distributed ComputingProceedings of the ACM Web Conference 202410.1145/3589334.3645435(1103-1114)Online publication date: 13-May-2024
https://dl.acm.org/doi/10.1145/3589334.3645435
Alon BNaor MOmri EStemmer U(2024)MPC for Tech Giants (GMPC): Enabling Gulliver and the Lilliputians to Cooperate AmicablyAdvances in Cryptology – CRYPTO 202410.1007/978-3-031-68397-8_3(74-108)Online publication date: 16-Aug-2024
https://doi.org/10.1007/978-3-031-68397-8_3
Jain PRaskhodnikova SSivakumar SSmith AKrause ABrunskill ECho KEngelhardt BSabato SScarlett J(2023)The price of differential privacy under continual observationProceedings of the 40th International Conference on Machine Learning10.5555/3618408.3619005(14654-14678)Online publication date: 23-Jul-2023
https://dl.acm.org/doi/10.5555/3618408.3619005
Wang SLuo XQian YZhu YChen KChen QXin BYang W(2023)Shuffle Differential Private Data Aggregation for Random PopulationIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2023.324754134:5(1667-1681)Online publication date: 1-May-2023
https://dl.acm.org/doi/10.1109/TPDS.2023.3247541
Jurado MGonze RAlvim MPalamidessi C(2023)Analyzing the Shuffle Model Through the Lens of Quantitative Information Flow2023 IEEE 36th Computer Security Foundations Symposium (CSF)10.1109/CSF57540.2023.00033(423-438)Online publication date: Jul-2023
https://doi.org/10.1109/CSF57540.2023.00033
Ding QSun KJiang LZhou HZhou C(2023)Differentially Private Probabilistic Social Choice in the Shuffle ModelIntegrated Uncertainty in Knowledge Modelling and Decision Making10.1007/978-3-031-46775-2_4(37-48)Online publication date: 2-Nov-2023
https://dl.acm.org/doi/10.1007/978-3-031-46775-2_4
Beimel AHaitner INissim KStemmer U(2020)On the Round Complexity of the Shuffle ModelTheory of Cryptography10.1007/978-3-030-64378-2_24(683-712)Online publication date: 16-Nov-2020
https://dl.acm.org/doi/10.1007/978-3-030-64378-2_24

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents