research-article

Free access

Secure multi-party computation of differentially private median

AUTHORs:

Florian KerschbaumAuthors Info & Claims

SEC'20: Proceedings of the 29th USENIX Conference on Security Symposium

Article No.: 121, Pages 2147 - 2164

Published: 12 August 2020 Publication History

PDF eReader Publisher Site

Abstract

In this work, we consider distributed private learning. For this purpose, companies collect statistics about telemetry, usage and frequent settings from their users without disclosing individual values. We focus on rank-based statistics, specifically, the median which is more robust to outliers than the mean.

Local differential privacy, where each user shares locally perturbed data with an untrusted server, is often used in private learning but does not provide the same accuracy as the central model, where noise is applied only once by a trusted server. Existing solutions to compute the differentially private median provide good accuracy only for large amounts of users (local model), by using a trusted third party (central model), or for a very small data universe (secure multiparty computation).

We present a multi-party computation to efficiently compute the exponential mechanism for the median, which also supports, e.g., general rank-based statistics (e.g., pth-percentile, interquartile range) and convex optimizations for machine learning. Our approach is efficient (practical running time), scaleable (sublinear in the data universe size) and accurate, i.e., the absolute error is smaller than comparable methods and is independent of the number of users, hence, our protocols can be used even for a small number of users. In our experiments we were able to compute the differentially private median for 1 million users in 3 minutes using 3 semi-honest computation parties distributed over the Internet.

References

[1]

WWDC 2016. Engineering privacy for your users, 2016.

[2]

John M. Abowd. The u.s. census bureau adopts differential privacy. In Proceedings of the annual ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, KDD, 2018.

Digital Library

[3]

Gagan Aggarwal, Nina Mishra, and Benny Pinkas. Secure computation of the median (and other elements of specified ranks). Journal of Cryptology, 2010.

Digital Library

[4]

Dima Alhadidi, Noman Mohammed, Benjamin CM Fung, and Mourad Debbabi. Secure distributed framework for achieving e-differential privacy. In International Symposium on Privacy Enhancing Technologies Symposium, PETS, 2012.

Digital Library

[5]

Mehrdad Aliasgari, Marina Blanton, Yihua Zhang, and Aaron Steele. Secure computation on floating point numbers. NDSS, 2013.

[6]

Abdelrahaman Aly, Marcel Keller, Dragos Rotaru, Peter Scholl, Nigel P. Smart, and Tim Wood. Scale-mamba documentation. https://homes.esat.kuleuven.be/~nsmart/SCALE/, 2020.

[7]

Abdelrahaman Aly and Nigel P Smart. Benchmarking privacy preserving scientific operations. In International Conference on Applied Cryptography and Network Security, ACNS, 2019.

Digital Library

[8]

Amazon.com. Amazon Web Services. https://aws.amazon.com/ec2/pricing/on-demand/.

[9]

Victor Balcer and Albert Cheu. Separating local & shuffled differential privacy via histograms, 2019.

[10]

Raef Bassily, Adam Smith, and Abhradeep Thakurta. Private empirical risk minimization: Efficient algorithms and tight error bounds. In Annual IEEE Symposium on Foundations of Computer Science, FOCS, 2014.

Digital Library

[11]

Donald Beaver. Efficient multiparty protocols using circuit randomization. In Annual International Cryptology Conference, CRYPTO, 1991.

[12]

Rikke Bendlin, Ivan Damgård, Claudio Orlandi, and Sarah Zakarias. Semi-homomorphic encryption and multiparty computation. In Annual International Conference on the Theory and Applications of Cryptographic Techniques, EUROCRYPT, 2011.

[13]

Jeremy Bernstein, Yu-Xiang Wang, Kamyar Azizzadenesheli, and Anima Anandkumar. signsgd: Compressed optimisation for non-convex problems. arXiv preprint arXiv:1802.04434, 2018.

[14]

Jonas Böhler and Florian Kerschbaum. Secure sublinear time differentially private median computation. In Network and Distributed Systems Security Symposium, NDSS, 2020.

[15]

Andrea Bittau, Ulfar 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 Symposium on Operating Systems Principles, SOSP, 2017.

Digital Library

[16]

Jeremiah Blocki, Anupam Datta, and Joseph Bonneau. Differentially private password frequency lists. In Network and Distributed Systems Security Symposium, NDSS, 2016.

[17]

Octavian Catrina and Sebastiaan De Hoogh. Improved primitives for secure multiparty integer computation. In International Conference on Security and Cryptography for Networks, SCN, 2010.

[18]

Albert Cheu, Adam Smith, Jonathan Ullman, David Zeber, and Maxim Zhilyaev. Distributed differential privacy via shuffling. In Annual International Conference on the Theory and Applications of Cryptographic Techniques, EUROCRYPT, 2019.

Digital Library

[19]

Amrita Roy Chowdhury, Chenghong Wang, Xi He, Ashwin Machanavajjhala, and Somesh Jha. Crypte: Crypto-assisted differential privacy on untrusted servers. In Proceedings of the annual ACM SIGMOD International Conference on Management of data, SIGMOD, 2020.

[20]

Ivan Damgård, Matthias Fitzi, Eike Kiltz, Jesper Buus Nielsen, and Tomas Toft. Unconditionally secure constant-rounds multi-party computation for equality, comparison, bits and exponentiation. In Theory of Cryptography Conference, TCC, 2006.

Digital Library

[21]

Ivan Damgård, Valerio Pastro, Nigel Smart, and Sarah Zakarias. Multiparty computation from somewhat homomorphic encryption. In Annual International Cryptology Conference, CRYPTO, 2012.

Digital Library

[22]

Jeffrey Dean and Sanjay Ghemawat. Mapreduce: simplified data processing on large clusters. Communications of the ACM, 2008.

Digital Library

[23]

Bolin Ding, Janardhan Kulkarni, and Sergey Yekhanin. Collecting telemetry data privately. In Advances in Neural Information Processing Systems, NIPS, 2017.

[24]

John C Duchi, Michael I Jordan, and Martin J Wainwright. Local privacy and statistical minimax rates. In Annual IEEE Symposium on Foundations of Computer Science, FOCS, 2013.

[25]

Cynthia Dwork. Differential privacy. In International Colloquium on Automata, Languages, and Programming, ICALP, 2006.

[26]

Cynthia Dwork, Krishnaram Kenthapadi, Frank McSherry, Ilya Mironov, and Moni Naor. Our data, ourselves: Privacy via distributed noise generation. In Annual International Conference on the Theory and Applications of Cryptographic Techniques, EUROCRYPT, 2006.

[27]

Cynthia Dwork and Jing Lei. Differential privacy and robust statistics. In Proceedings of the annual ACM symposium on Theory of Computing, STOC, 2009.

Digital Library

[28]

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

[29]

Cynthia Dwork and Aaron Roth. The algorithmic foundations of differential privacy. Foundations and Trends in Theoretical Computer Science, 2014.

Digital Library

[30]

Fabienne Eigner, Aniket Kate, Matteo Maffei, Francesca Pampaloni, and Ivan Pryvalov. Differentially private data aggregation with optimal utility. In Proceedings of the Annual Computer Security Applications Conference, ACSAC, 2014.

Digital Library

[31]

Úlfar Erlingsson, Vasyl Pihur, and Aleksandra Korolova. Rappor: Randomized aggregatable privacy-preserving ordinal response. In Proceedings of the annual ACM conference on computer and communications security, CCS, 2014.

[32]

David Evans, Vladimir Kolesnikov, Mike Rosulek, et al. A pragmatic introduction to secure multi-party computation. Foundations and Trends® in Privacy and Security, 2018.

[33]

Centers for Medicare & Medicaid Services. Complete 2017 program year open payments dataset, 2017.

[34]

Marco Gaboardi, Adam Smith, and Jinhui Xu. Empirical risk minimization in the non-interactive local model of differential privacy.

[35]

Ivan Gazeau, Dale Miller, and Catuscia Palamidessi. Preserving differential privacy under finite precision semantics. In Theoretical Computer Science, TCS, 2016.

[36]

Oded Goldreich. Foundations of Cryptography: Volume 2, Basic Applications. 2009.

[37]

Oded Goldreich, Silvio Micali, and AviWigderson. How to play any mental game. In Proceedings of the annual ACM symposium on Theory of Computing, STOC, 1987.

Digital Library

[38]

Slawomir Goryczka and Li Xiong. A comprehensive comparison of multiparty secure additions with differential privacy. IEEE transactions on Dependable and Secure Computing, 2017.

Digital Library

[39]

Xi He, Ashwin Machanavajjhala, Cheryl Flynn, and Divesh Srivastava. Composing differential privacy and secure computation: A case study on scaling private record linkage. In Proceedings of the annual ACM conference on Computer and Communications Security, CCS, 2017.

Digital Library

[40]

Justin Hsu, Sanjeev Khanna, and Aaron Roth. Distributed private heavy hitters. In International Colloquium on Automata, Languages, and Programming, ICALP, 2012.

[41]

Christina Ilvento. Implementing the exponential mechanism with base-2 differential privacy, 2019.

[42]

Kaggle.com. Walmart supply chain: Import and shipment. https://www.kaggle.com/sunilp/walmart-supply-chain-data/data, 2018. Retrieved: October, 2019.

[43]

Liina Kamm. Privacy-preserving statistical analysis using secure multi-party computation. PhD thesis, PhD thesis, University of Tartu, 2015.

[44]

Shiva Prasad Kasiviswanathan, Homin K Lee, Kobbi Nissim, Sofya Raskhodnikova, and Adam Smith. What can we learn privately? SIAM Journal on Computing, 2011.

Digital Library

[45]

Marcel Keller. Mp-spdz: A versatile framework for multi-party computation. Cryptology ePrint Archive, Report 2020/521, 2020. https://eprint.iacr.org/2020/521.

[46]

Marcel Keller, Valerio Pastro, and Dragos Rotaru. Overdrive: making spdz great again. In Annual International Conference on the Theory and Applications of Cryptographic Techniques, EUROCRYPT, 2018.

[47]

Marcel Keller, Dragos Rotaru, Nigel P Smart, and Tim Wood. Reducing communication channels in mpc. In International Conference on Security and Cryptography for Networks, SCN, 2018.

Digital Library

[48]

Ninghui Li, Min Lyu, Dong Su, and Weining Yang. Differential privacy: From theory to practice. Synthesis Lectures on Information Security, Privacy, & Trust, 2016.

[49]

Yehuda Lindell and Benny Pinkas. A proof of security of yao's protocol for two-party computation. Journal of Cryptology, 2009.

Digital Library

[50]

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

Digital Library

[51]

Frank McSherry. Privacy integrated queries: an extensible platform for privacy-preserving data analysis. In Proceedings of the annual ACM SIGMOD International Conference on Management of data, SIGMOD, 2009.

Digital Library

[52]

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

Digital Library

[53]

Ilya Mironov. On significance of the least significant bits for differential privacy. In Proceedings of the annual ACM conference on computer and communications security, CCS, 2012.

Digital Library

[54]

Ilya Mironov, Omkant Pandey, Omer Reingold, and Salil Vadhan. Computational differential privacy. In Annual International Cryptology Conference, CRYPTO, 2009.

Digital Library

[55]

Jack Murtagh and Salil Vadhan. The complexity of computing the optimal composition of differential privacy. In Theory of Cryptography Conference, TCC, 2016.

Digital Library

[56]

Seth Neel, Aaron Roth, Giuseppe Vietri, and Zhiwei Steven Wu. Differentially private objective perturbation: Beyond smoothness and convexity, 2019.

[57]

Jesper Buus Nielsen, Peter Sebastian Nordholt, Claudio Orlandi, and Sai Sheshank Burra. A new approach to practical active-secure two-party computation. In Annual International Cryptology Conference, CRYPTO, 2012.

Digital Library

[58]

Kobbi Nissim, Sofya Raskhodnikova, and Adam Smith. Smooth sensitivity and sampling in private data analysis. In Proceedings of the annual ACM symposium on Theory of Computing, STOC, 2007.

Digital Library

[59]

Martin Pettai and Peeter Laud. Combining differential privacy and secure multiparty computation. In Proceedings of the Annual Computer Security Applications Conference, ACSAC, 2015.

Digital Library

[60]

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

Digital Library

[61]

Indrajit Roy, Srinath TV Setty, Ann Kilzer, Vitaly Shmatikov, and Emmett Witchel. Airavat: Security and privacy for mapreduce.

[62]

Adi Shamir. How to share a secret. Communications of the ACM, 1979.

Digital Library

[63]

Adam Smith, Abhradeep Thakurta, and Jalaj Upadhyay. Is interaction necessary for distributed private learning? In IEEE Symposium on Security and Privacy, SP, 2017.

[64]

Gaurav Sood. California Public Salaries Data, 2018.

[65]

Hassan Takabi, Samir Koppikar, and Saman Taghavi Zargar. Differentially private distributed data analysis. In IEEE International Conference on Collaboration and Internet Computing, CIC, 2016.

[66]

Apple's Differential Privacy Team. Learning with privacy at scale, 2017.

[67]

Machine Learning Group ULB. Credit card fraud detection, 2018.

[68]

Andrew Chi-Chih Yao. How to generate and exchange secrets. In Annual IEEE Symposium on Foundations of Computer Science, FOCS, 1986.

Cited By

Zhao YDu JChen J(2024)Scenario-based Adaptations of Differential Privacy: A Technical SurveyACM Computing Surveys10.1145/365115356:8(1-39)Online publication date: 26-Apr-2024
https://dl.acm.org/doi/10.1145/3651153
Böhler JKerschbaum FKim YKim JVigna GShi E(2021)Secure Multi-party Computation of Differentially Private Heavy HittersProceedings of the 2021 ACM SIGSAC Conference on Computer and Communications Security10.1145/3460120.3484557(2361-2377)Online publication date: 12-Nov-2021
https://dl.acm.org/doi/10.1145/3460120.3484557

Index Terms

Secure multi-party computation of differentially private median

Index terms have been assigned to the content through auto-classification.

Recommendations

Secure Multi-party Computation of Differentially Private Heavy Hitters
CCS '21: Proceedings of the 2021 ACM SIGSAC Conference on Computer and Communications Security

Private learning of top-k, i.e., the k most frequent values also called heavy hitters, is a common industry scenario: Companies want to privately learn, e.g., frequently typed new words to improve suggestions on mobile devices, often used browser ...
Secure Two-Party Differentially Private Data Release for Vertically Partitioned Data

Privacy-preserving data publishing addresses the problem of disclosing sensitive data when mining for useful information. Among the existing privacy models, $(\epsilon)$-differential privacy provides one of the strongest privacy guarantees. In this paper,...
Leveraging the "Multi" in secure multi-party computation
WPES '03: Proceedings of the 2003 ACM workshop on Privacy in the electronic society

Secure Multi-Party Computation enables parties with private data to collaboratively compute a global function of their private data, without revealing that data. The increase in sensitive data on networked computers, along with improved ability to ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

SEC'20: Proceedings of the 29th USENIX Conference on Security Symposium

August 2020

2809 pages

ISBN:978-1-939133-17-5

Program Chairss:
Srdjan Capkun
ETH Zurich
,
Franziska Roesner
University of Washington

Copyright © 2020.

Sponsors

Facebook
Microsoft
IBM
ByteDance
Google Inc.

Publisher

USENIX Association

United States

Publication History

Published: 12 August 2020

Qualifiers

Research-article

Acceptance Rates

Overall Acceptance Rate 40 of 100 submissions, 40%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
59
Total Downloads

Downloads (Last 12 months)24
Downloads (Last 6 weeks)2

Reflects downloads up to 14 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Zhao YDu JChen J(2024)Scenario-based Adaptations of Differential Privacy: A Technical SurveyACM Computing Surveys10.1145/365115356:8(1-39)Online publication date: 26-Apr-2024
https://dl.acm.org/doi/10.1145/3651153
Böhler JKerschbaum FKim YKim JVigna GShi E(2021)Secure Multi-party Computation of Differentially Private Heavy HittersProceedings of the 2021 ACM SIGSAC Conference on Computer and Communications Security10.1145/3460120.3484557(2361-2377)Online publication date: 12-Nov-2021
https://dl.acm.org/doi/10.1145/3460120.3484557

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