research-article

Public Access

Securely Sampling Biased Coins with Applications to Differential Privacy

Authors:

Jeffrey Champion,

Jonathan UllmanAuthors Info & Claims

CCS '19: Proceedings of the 2019 ACM SIGSAC Conference on Computer and Communications Security

Pages 603 - 614

https://doi.org/10.1145/3319535.3354256

Published: 06 November 2019 Publication History

Abstract

We design an efficient method for sampling a large batch of d independent coins with a given bias p ∈ [0,1]. The folklore secure computation method for doing so requires O(lambda + log d) communication and computation per coin to achieve total statistical difference 2-lambda. We present an exponential improvement over the folklore method that uses just O(log(lambda+log d)) gates per coin when sampling d coins with total statistical difference 2-lambda. We present a variant of our work that also concretely beats the folklore method for lambda ≥ 60 which are parameters that are often used in practice. Our new technique relies on using specially designed oblivious data structures to achieve biased coin samples that take an expected 2 random bits to sample. Using our new sampling technique, we present an implementation of the differentially private report-noisy-max mechanism (a more practical implementation of the celebrated exponential mechanism) as a secure multi-party computation. Our benchmarks show that one can run this mechanism on a domain of size d=212 in 6 seconds and up to d=219 in 14 minutes. As far as we know, this is the first complete distributed implementation of either of these mechanisms.

Supplementary Material

WEBM File (p603-champion.webm)

Download
117.91 MB

References

[1]

Balamurugan Anandan and Chris Clifton. Laplace noise generation for two-party computational differential privacy. In 2015 13th Annual Conference on Privacy, Security and Trust (PST), 2015.

[2]

Gilles Barthe, George Danezis, Benjamin Grégoire, César Kunz, and Santiago Zanella-Beguelin. Verified computational differential privacy with applications to smart metering. In 2013 IEEE 26th Computer Security Foundations Symposium, pages 287--301. IEEE, 2013.

Digital Library

[3]

Andrea Bittau, Ulfar Erlingsson, Petros Maniatis, Ilya Mironov, Ananth Raghunathan, David Lie, Mitch Rudominer, Usharsee Kode, Julien Tinnes, and Bernhard Seefeld. PROCHLO: Strong privacy for analytics in the crowd. In Proceedings of the Symposium on Operating Systems Principles (SOSP), 2017.

Digital Library

[4]

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. IACR Cryptology ePrint Archive, 2017.

[5]

Avrim Blum, Katrina Ligett, and Aaron Roth. A learning theory approach to noninteractive database privacy. J. ACM, 60(2):12, 2013.

Digital Library

[6]

Raghav Bhaskar, Srivatsan Laxman, Adam Smith, and Abhradeep Thakurta. Discovering frequent patterns in sensitive data. In Proceedings of the 16th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 503--512. ACM, 2010.

Digital Library

[7]

Amos Beimel, Kobbi Nissim, and Eran Omri. Distributed private data analysis: Simultaneously solving how and what. In Annual International Cryptology Conference, pages 451--468. Springer, 2008.

Digital Library

[8]

T.-H. Hubert Chan, Mingfei Li, Elaine Shi, and Wenchang Xu. Differentially private continual monitoring of heavy hitters from distributed streams. In Privacy Enhancing Technologies - 12th International Symposium, PETS 2012, Vigo, Spain, July 11--13, 2012. Proceedings, pages 140--159, 2012.

[9]

Ruichuan Chen, Alexey Reznichenko, Paul Francis, and Johanes Gehrke. Towards statistical queries over distributed private user data. In Presented as part of the 9th USENIX Symposium on Networked Systems Design and Implementation (NSDI 12), pages 169--182, 2012.

[10]

T-H Hubert Chan, Elaine Shi, and Dawn Song. Private and continual release of statistics. ACM Transactions on Information and System Security (TISSEC), 14(3):26, 2011.

[11]

Cagdas Calik, Meltem Sönmez Turan, and René Peralta. The multiplicative complexity of 6-variable boolean functions. 2018.

[12]

Jack Doerner and abhi shelat. Scaling oram for secure computation. In ACM CCS'17, 2017.

[13]

John C Duchi, Michael I Jordan, and Martin J Wainwright. Local privacy and statistical minimax rates. In Foundations of Computer Science (FOCS), 2013 IEEE 54th Annual Symposium on, pages 429--438. IEEE, 2013.

Digital Library

[14]

Cynthia Dwork, Krishnaram Kenthapadi, Frank McSherry, Ilya Mironov, and Moni Naor. Our data, ourselves: Privacy via distributed noise generation. In EUROCRYPT, 2006.

Digital Library

[15]

Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In Theory of Cryptography Conference (TCC), 2006.

Digital Library

[16]

Cynthia Dwork and Aaron Roth. The algorithmic foundations of differential privacy. Foundations and Trends in Theoretical Computer Science, 9(3--4):211--407, 2014.

[17]

Fabienne Eigner, Aniket Kate, Matteo Maffei, Francesca Pampaloni, and Ivan Pryvalov. Differentially private data aggregation with optimal utility. In Proceedings of the 30th Annual Computer Security Applications Conference, pages 316--325. ACM, 2014.

Digital Library

[18]

Úlfar Erlingsson, Vasyl Pihur, and Aleksandra Korolova. RAPPOR: Randomized aggregatable privacy-preserving ordinal response. In ACM Conference on Computer and Communications Security (CCS), 2014.

[19]

Vipul Goyal, Dakshita Khurana, Ilya Mironov, Omkant Pandey, and Amit Sahai. Do distributed differentially-private protocols require oblivious transfer? In 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016, July 11--15, 2016, Rome, Italy, 2016.

[20]

Vipul Goyal, Ilya Mironov, Omkant Pandey, and Amit Sahai. Accuracy-privacy tradeoffs for two-party differentially private protocols. In Advances in Cryptology - CRYPTO 2013 - 33rd Annual Cryptology Conference, Santa Barbara, CA, USA, August 18--22, 2013. Proceedings, Part I, 2013.

[21]

Oded Goldreich and Rafail Ostrovsky. Software Protection and Simulation on Oblivious RAMs. Journal of the ACM, 43(3), 1996.

Digital Library

[22]

Moritz Hardt, Katrina Ligett, and Frank McSherry. A simple and practical algorithm for differentially private data release. In Advances in Neural Information Processing Systems 25: 26th Annual Conference on Neural Information Processing Systems 2012. Proceedings of a meeting held December 3--6, 2012, Lake Tahoe, Nevada, United States., pages 2348--2356, 2012.

[23]

Samuel Haney, Ashwin Machanavajjhala, John M Abowd, Matthew Graham, Mark Kutzbach, and Lars Vilhuber. Utility cost of formal privacy for releasing national employer-employee statistics. In Proceedings of the 2017 ACM International Conference on Management of Data, pages 1339--1354. ACM, 2017.

Digital Library

[24]

Xi He, Ashwin Machanavajjhala, Cheryl Flynn, and Divesh Srivastava. Composing differential privacy and secure computation: A case study on scaling private record linkage. arXiv preprint arXiv:1702.00535, 2017.

[25]

Shiva Prasad Kasiviswanathan, Homin K. Lee, Kobbi Nissim, Sofya Raskhodnikova, and Adam Smith. What can we learn privately? In Foundations of Computer Science (FOCS). IEEE, 2008.

[26]

Steve Lu and Rafail Ostrovsky. Garbled ram revisited, part ii. Cryptology ePrint Archive, Report 2014/083, 2014.

[27]

Ilya Mironov. On significance of the least significant bits for differential privacy. In Proceedings of the 2012 ACM Conference on Computer and cCommunications Security (CCS). ACM, 2012.

Digital Library

[28]

Andrew McGregor, Ilya Mironov, Toniann Pitassi, Omer Reingold, Kunal Talwar, and Salil Vadhan. The limits of two-party differential privacy. In Foundations of Computer Science (FOCS), 2010 51st Annual IEEE Symposium on, pages 81--90. IEEE, 2010.

Digital Library

[29]

Ilya Mironov, Omkant Pandey, Omer Reingold, and Salil Vadhan. Computational differential privacy. In Advances in Cryptology-CRYPTO 2009, pages 126--142. Springer, 2009.

Digital Library

[30]

Frank McSherry and Kunal Talwar. Mechanism design via differential privacy. In IEEE Foundations of Computer Science (FOCS), 2007.

Digital Library

[31]

Martin Pettai and Peeter Laud. Combining differential privacy and secure multiparty computation. In ACSAC 2015, pages 421--430, New York, NY, USA, 2015. ACM.

Digital Library

[32]

Sarvar Patel, Giuseppe Persiano, Mariana Raykova, and Kevin Yeo. Panorama: Oblivious ram with logarithmic overhead. In 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), pages 871--882. IEEE, 2018.

[33]

Vibhor Rastogi and Suman Nath. Differentially private aggregation of distributed time-series with transformation and encryption. In Proceedings of the 2010 ACM SIGMOD International Conference on Management of data, pages 735--746. ACM, 2010.

Digital Library

[34]

Elaine Shi, T.-H. Hubert Chan, Eleanor G. Rieffel, Richard Chow, and Dawn Song. Privacy-preserving aggregation of time-series data. In Proceedings of the Network and Distributed System Security Symposium, (NDSS) 2011, 2011.

[35]

Elaine Shi, T.-H. Hubert Chan, Emil Stefanov, and Mingfei Li. Oblivious RAM with o((logn)3) worst-case cost. In Advances in Cryptology - ASIACRYPT 2011 - 17th International Conference on the Theory and Application of Cryptology and Information Security, Seoul, South Korea, December 4--8, 2011. Proceedings, pages 197--214, 2011.

Digital Library

[36]

Kunal Talwar, Abhradeep Thakurta, and Li Zhang. Nearly optimal private LASSO. In Advances in Neural Information Processing Systems, NIPS, pages 3025--3033, 2015.

[37]

Abhradeep Guha Thakurta, Andrew H Vyrros, Umesh S Vaishampayan, Gaurav Kapoor, Julien Freudiger, Vivek Rangarajan Sridhar, and Doug Davidson. Learning new words, May 9 2017. US Patent 9,645,998.

[38]

Abhradeep Guha Thakurta, Andrew H Vyrros, Umesh S Vaishampayan, Gaurav Kapoor, Julien Freudinger, Vipul Ved Prakash, Arnaud Legendre, and Steven Duplinsky. Emoji frequency detection and deep link frequency, July 11 2017. US Patent 9,705,908.

[39]

Jonathan Ullman. Tight lower bounds for locally differentially private selection. arXiv preprint arXiv:1802.02638, 2018.

[40]

Salil Vadhan. The complexity of differential privacy. http://privacytools. seas. harvard. edu/publications/complexity-differential-privacy, 2016.

[41]

Ladislaus von Bortkiewicz. Das gesetz der kleinen zahlen [the law of small numbers], 1898.

[42]

Stanley L Warner. Randomized response: A survey technique for eliminating evasive answer bias. Journal of the American Statistical Association, 60(309):63--69, 1965.

[43]

Xiao Wang, T.-H. Hubert Chan, and Elaine Shi. Circuit ORAM: on tightness of the goldreich-ostrovsky lower bound. In Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security, Denver, CO, USA, October 12--6, 2015, pages 850--861, 2015.

Digital Library

[44]

Samee Zahur and David Evans. Circuit structures for improving efficiency of security and privacy tools. IEEE S & P, pages 493--507, 2013.

Digital Library

[45]

Samee Zahur and David Evans. Obliv-c: A language for extensible data-oblivious computation. Cryptology ePrint Archive, Report 2015/1153, 2015.

Cited By

Agarwal APeceny SRaykova MSchoppmann PSeth K(2024)Communication-Efficient Secure Logistic Regression2024 IEEE 9th European Symposium on Security and Privacy (EuroS&P)10.1109/EuroSP60621.2024.00031(440-467)Online publication date: 8-Jul-2024
https://doi.org/10.1109/EuroSP60621.2024.00031
Luo QWang YYi KWang SLi F(2023)Secure Sampling for Approximate Multi-party Query ProcessingProceedings of the ACM on Management of Data10.1145/36173391:3(1-27)Online publication date: 13-Nov-2023
https://dl.acm.org/doi/10.1145/3617339
Wei CYu RFan YChen WWang TMeng WJensen CCremers CKirda E(2023)Securely Sampling Discrete Gaussian Noise for Multi-Party Differential PrivacyProceedings of the 2023 ACM SIGSAC Conference on Computer and Communications Security10.1145/3576915.3616641(2262-2276)Online publication date: 15-Nov-2023
https://dl.acm.org/doi/10.1145/3576915.3616641
Show More Cited By

Index Terms

Securely Sampling Biased Coins with Applications to Differential Privacy
1. Mathematics of computing
  1. Probability and statistics
    1. Probabilistic algorithms
2. Security and privacy
  1. Security services
    1. Privacy-preserving protocols

Recommendations

Securely Sampling Discrete Gaussian Noise for Multi-Party Differential Privacy
CCS '23: Proceedings of the 2023 ACM SIGSAC Conference on Computer and Communications Security

Differential Privacy (DP) is a widely used technique for protecting individuals' privacy by limiting what can be inferred about them from aggregate data. Recently, there have been efforts to implement DP using Secure Multi-Party Computation (MPC) to ...
Secure Multiparty Sampling of a Biased Coin for Differential Privacy
Computer Security. ESORICS 2023 International Workshops
Abstract
Sampling a biased coin is a key primitive in designing secure multiparty computation (MPC) for differentially private mechanisms. We explore privately sampling a biased coin from l unbiased coins and offer an unconditionally secure MPC protocol ...
Privacy Amplification by Sampling under User-level Differential Privacy
SIGMOD

Random sampling is an effective tool for reducing the computational costs of query processing in large databases. It has also been used frequently for private data analysis, in particular, under differential privacy (DP). An interesting phenomenon that ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

CCS '19: Proceedings of the 2019 ACM SIGSAC Conference on Computer and Communications Security

November 2019

2755 pages

ISBN:9781450367479

DOI:10.1145/3319535

General Chairs:
Lorenzo Cavallaro
King's College London, UK
,
Johannes Kinder
Bundeswehr University Munich, Germany
,
Program Chairs:
XiaoFeng Wang
Indiana University, USA
,
Jonathan Katz
George Mason University, USA

Copyright © 2019 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

SIGSAC: ACM Special Interest Group on Security, Audit, and Control

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 06 November 2019

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

National Science Foundation

Conference

CCS '19

Sponsor:

SIGSAC

CCS '19: 2019 ACM SIGSAC Conference on Computer and Communications Security

November 11 - 15, 2019

London, United Kingdom

Acceptance Rates

CCS '19 Paper Acceptance Rate 149 of 934 submissions, 16%;

Overall Acceptance Rate 1,261 of 6,999 submissions, 18%

Upcoming Conference

CCS '25

Sponsor:
sigsac

ACM SIGSAC Conference on Computer and Communications Security

October 13 - 17, 2025

Taipei , Taiwan

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

12
Total Citations
View Citations
1,154
Total Downloads

Downloads (Last 12 months)136
Downloads (Last 6 weeks)19

Reflects downloads up to 18 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Agarwal APeceny SRaykova MSchoppmann PSeth K(2024)Communication-Efficient Secure Logistic Regression2024 IEEE 9th European Symposium on Security and Privacy (EuroS&P)10.1109/EuroSP60621.2024.00031(440-467)Online publication date: 8-Jul-2024
https://doi.org/10.1109/EuroSP60621.2024.00031
Luo QWang YYi KWang SLi F(2023)Secure Sampling for Approximate Multi-party Query ProcessingProceedings of the ACM on Management of Data10.1145/36173391:3(1-27)Online publication date: 13-Nov-2023
https://dl.acm.org/doi/10.1145/3617339
Wei CYu RFan YChen WWang TMeng WJensen CCremers CKirda E(2023)Securely Sampling Discrete Gaussian Noise for Multi-Party Differential PrivacyProceedings of the 2023 ACM SIGSAC Conference on Computer and Communications Security10.1145/3576915.3616641(2262-2276)Online publication date: 15-Nov-2023
https://dl.acm.org/doi/10.1145/3576915.3616641
Yang JXiang LYu JWang XGuo BLi ZLi B(2023)Matrix Gaussian Mechanisms for Differentially-Private LearningIEEE Transactions on Mobile Computing10.1109/TMC.2021.309331622:2(1036-1048)Online publication date: 1-Feb-2023
https://doi.org/10.1109/TMC.2021.3093316
Eriguchi RIchikawa AKunihiro NNuida K(2023)Efficient Noise Generation Protocols for Differentially Private Multiparty ComputationIEEE Transactions on Dependable and Secure Computing10.1109/TDSC.2022.322756820:6(4486-4501)Online publication date: Nov-2023
https://doi.org/10.1109/TDSC.2022.3227568
Shen ZZhong TSun HQi B(2023)RRN: A differential private approach to preserve privacy in image classificationIET Image Processing10.1049/ipr2.1278417:7(2192-2203)Online publication date: 20-Mar-2023
https://doi.org/10.1049/ipr2.12784
Choi SDachman-Soled DGordon SLiu LYerukhimovich A(2023)Secure Sampling with Sublinear CommunicationTheory of Cryptography10.1007/978-3-031-22365-5_13(348-377)Online publication date: 1-Jan-2023
https://doi.org/10.1007/978-3-031-22365-5_13
Maddock SCormode GWang TMaple CJha SYin HStavrou ACremers CShi E(2022)Federated Boosted Decision Trees with Differential PrivacyProceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security10.1145/3548606.3560687(2249-2263)Online publication date: 7-Nov-2022
https://dl.acm.org/doi/10.1145/3548606.3560687
Munilla Garrido GSedlmeir JBabel M(2022)Towards Verifiable Differentially-Private PollingProceedings of the 17th International Conference on Availability, Reliability and Security10.1145/3538969.3538992(1-11)Online publication date: 23-Aug-2022
https://dl.acm.org/doi/10.1145/3538969.3538992
Byrd DMugunthan VPolychroniadou ABalch T(2022)Collusion Resistant Federated Learning with Oblivious Distributed Differential PrivacyProceedings of the Third ACM International Conference on AI in Finance10.1145/3533271.3561754(114-122)Online publication date: 2-Nov-2022
https://dl.acm.org/doi/10.1145/3533271.3561754
Show More Cited By

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