research-article

Secure multiparty aggregation with differential privacy: a comparative study

Authors:

Slawomir Goryczka,

Vaidy SunderamAuthors Info & Claims

EDBT '13: Proceedings of the Joint EDBT/ICDT 2013 Workshops

Pages 155 - 163

https://doi.org/10.1145/2457317.2457343

Published: 18 March 2013 Publication History

Abstract

This paper considers the problem of secure data aggregation in a distributed setting while preserving differential privacy for the aggregated data. In particular, we focus on the secure sum aggregation. Security is guaranteed by secure multiparty computation protocols using well known security schemes: Shamir's secret sharing, perturbation-based, and various encryption schemes. Differential privacy of the final result is achieved by distributed Laplace perturbation mechanism (DLPA). Partial random noise is generated by all participants, which draw random variables from Gamma or Gaussian distributions, such that the aggregated noise follows Laplace distribution to satisfy differential privacy. We also introduce a new efficient distributed noise generation scheme with partial noise drawn from Laplace distributions.

We compare the protocols with different privacy mechanisms and security schemes in terms of their complexity and security characteristics. More importantly, we implemented all protocols, and present an experimental comparison on their performance and scalability in a real distributed environment.

References

[1]

Report of the August 2010 Multi-Agency Workshop on InfoSymbiotics/DDDAS, The Power of Dynamic Data Driven Applications Systems. Workshop sponsored by: Air Force Office of Scientific Research and National Science Foundation.

[2]

G. Ács and C. Castelluccia. I have a DREAM!: differentially private smart metering. In Proc. of the 13th Intl Conf. on Information Hiding, IH, pages 118--132, 2011.

Digital Library

[3]

J. Ahrens and U. Dieter. Computer methods for sampling from gamma, beta, Poisson and bionomial distributions. Computing, 12:223--246, 1974.

[4]

M. Ben-Or, S. Goldwasser, and A. Wigderson. Completeness theorems for non-cryptographic fault-tolerant distributed computation. In STOC, pages 1--10, 1988.

Digital Library

[5]

G. E. P. Box and M. E. Muller. A note on the generation of random normal deviates. The Annals of Mathematical Statistics, 29(2):610--611, 1958.

[6]

J. Burke, D. Estrin, M. Hansen, A. Parker, N. Ramanathan, S. Reddy, and M. B. Srivastava. Participatory sensing. In Workshop on World-Sensor-Web (WSW): Mobile Device Centric Sensor Networks and Applications, 2006.

[7]

M. Burkhart, M. Strasser, D. Many, and X. Dimitropoulos. SEPIA: Privacy-preserving aggregation of multi-domain network events and statistics. In 19th USENIX Security Symposium, August 2010.

Digital Library

[8]

C. Castelluccia, A. C.-F. Chan, E. Mykletun, and G. Tsudik. Efficient and provably secure aggregation of encrypted data in wireless sensor networks. ACM Trans. Sen. Netw., 5(3):20:1--20:36, June 2009.

Digital Library

[9]

C. Castelluccia, E. Mykletun, and G. Tsudik. Efficient aggregation of encrypted data in wireless sensor networks. In Proc. of the The 2nd Annual Intl Conf. on Mobile and Ubiquitous Systems: Networking and Services, MOBIQUITOUS, pages 109--117, 2005.

Digital Library

[10]

O. Catrina and A. Saxena. Secure computation with fixed-point numbers. In Proc. of the 14th Intl Conf. on Financial Cryptography and Data Security, FC, pages 35--50, 2010.

Digital Library

[11]

C. Clifton, M. Kantarcioglu, J. Vaidya, X. Lin, and M. Y. Zhu. Tools for privacy preserving distributed data mining. SIGKDD Explor. Newsl., 4:28--34, 2002.

Digital Library

[12]

R. Cramer, I. Damgård, and J. B. Nielsen. Multiparty computation from threshold homomorphic encryption. In EUROCRYPT, pages 280--299, 2001.

Digital Library

[13]

I. Damgård and M. Jurik. A generalisation, a simplification and some applications of Paillier's probabilistic public-key system. In Proc. of the 4th Intl Workshop on Practice and Theory in Public Key Cryptography: Public Key Cryptography, PKC, pages 119--136, 2001.

Digital Library

[14]

I. Damgård and G. Mikkelsen. Efficient, robust and constant-round distributed rsa key generation. In D. Micciancio, editor, Theory of Cryptography, volume 5978 of Lecture Notes in Computer Science, pages 183--200, 2010.

Digital Library

[15]

C. Dwork. Differential privacy. In Proc. of the 33rd Intl Conf. on Automata, Languages and Programming - Volume Part II, ICALP, pages 1--12, 2006.

Digital Library

[16]

C. Dwork. Differential privacy: a survey of results. In Proc. of the 5th Intl Conf. on Theory and Applications of Models of Computation, TAMC, pages 1--19, 2008.

Digital Library

[17]

C. Dwork. A firm foundation for private data analysis. Communications of the ACM, 54(1):86--95, 2011.

Digital Library

[18]

C. Dwork, K. Kenthapadi, F. McSherry, I. Mironov, and M. Naor. Our data, ourselves: privacy via distributed noise generation. In Proc. of the 24th Annual Intl Conf. on The Theory and Applications of Cryptographic Techniques, EUROCRYPT, pages 486--503, 2006.

Digital Library

[19]

C. Dwork, F. McSherry, K. Nissim, and A. Smith. Calibrating noise to sensitivity in private data analysis. In TCC, pages 265--284, 2006.

Digital Library

[20]

T. El Gamal. A public key cryptosystem and a signature scheme based on discrete logarithms. In Proc. of CRYPTO 84 on Advances in Cryptology, pages 10--18, 1985.

Digital Library

[21]

B. C. M. Fung, K. Wang, R. Chen, and P. S. Yu. Privacy-preserving data publishing: A survey of recent developments. ACM Comput. Surv., 42(4):14:1--14:53, 2010.

Digital Library

[22]

S. L. Garfinkel and M. D. Smith. Guest editors' introduction: Data surveillance. IEEE Security & Privacy, 4(6), 2006.

Digital Library

[23]

C. Gentry. Fully homomorphic encryption using ideal lattices. In STOC, pages 169--178, 2009.

Digital Library

[24]

A. Ghosh, T. Roughgarden, and M. Sundararajan. Universally utility-maximizing privacy mechanisms. In STOC, pages 351--360, 2009.

Digital Library

[25]

O. Goldreich. Foundations of Cryptography: Volume 2, Basic Applications. Cambridge University Press, 2004.

Digital Library

[26]

C. Hazay, G. L. Mikkelsen, T. Rabin, and T. Toft. Efficient RSA key generation and threshold Paillier in the two-party setting. In Proc. of the 12th Conf. on Topics in Cryptology, CT-RSA, pages 313--331, 2012.

Digital Library

[27]

J. Kang, K. Shilton, D. Estrin, J. Burke, and M. Hansen. Self-surveillance privacy. Iowa Law Review, 97, 2012.

[28]

D. Kifer and A. Machanavajjhala. No free lunch in data privacy. In SIGMOD, pages 193--204, 2011.

Digital Library

[29]

S. Kotz, T. Kozubowski, and K. Podgórski. The Laplace Distribution and Generalizations: A Revisit with Applications to Communications, Economics, Engineering, and Finance. Progress in Mathematics Series. Birkhäuser Boston, 2001.

[30]

Y. Lindell and B. Pinkas. Secure multiparty computation for privacy-preserving data mining. IACR Cryptology ePrint Archive, 2008:197, 2008.

[31]

G. Marsaglia and T. A. Bray. A convenient method for generating normal variables. SIAM Review, 6(3):260--264, 1964.

[32]

G. Marsaglia and W. W. Tsang. The Ziggurat method for generating random variables. J. Stat. Softw., 5(8):1--7, 10 2000.

[33]

M. Mun, S. Reddy, K. Shilton, N. Yau, J. Burke, D. Estrin, M. Hansen, E. Howard, R. West, and P. Boda. PEIR, the personal environmental impact report, as a platform for participatory sensing systems research. In Proc. of the 7th Intl Conf. on Mobile Systems, Applications, and Services, MobiSys, 2009.

Digital Library

[34]

T. Nishide and K. Sakurai. Distributed Paillier cryptosystem without trusted dealer. In Y. Chung and M. Yung, editors, Information Security Applications, volume 6513 of Lecture Notes in Computer Science, pages 44--60, 2011.

Digital Library

[35]

P. Paillier. Public-key cryptosystems based on composite degree residuosity classes. In EUROCRYPT, pages 223--238, 1999.

Digital Library

[36]

T. B. Pedersen, Y. Saygin, and E. Savaş. Secret Sharing vs. Encryption-based Techniques For Privacy Preserving Data Mining. In Proc. of UNECE/Eurostat Work Session on SDC, 2007.

[37]

V. Rastogi and S. Nath. Differentially private aggregation of distributed time-series with transformation and encryption. In SIGMOD, pages 735--746, 2010.

Digital Library

[38]

R. L. Rivest, A. Shamir, and L. Adleman. A method for obtaining digital signatures and public-key cryptosystems. Communications of the ACM, 21(2):120--126, 1978.

Digital Library

[39]

A. Shamir. How to share a secret. Communications of the ACM, 22(11):612--613, 1979.

Digital Library

[40]

E. Shi, T.-H. H. Chan, E. G. Rieffel, R. Chow, and D. Song. Privacy-preserving aggregation of time-series data. In NDSS, 2011.

[41]

K. Shilton. Four billion little brothers?: privacy, mobile phones, and ubiquitous data collection. CACM, 52:48--53, 2009.

Digital Library

[42]

J. Vaidya and C. Clifton. Privacy-preserving data mining: Why, how, and when. IEEE Security & Privacy, 2(6):19--27, 2004.

Digital Library

[43]

M. van Dijk, C. Gentry, S. Halevi, and V. Vaikuntanathan. Fully homomorphic encryption over the integers. In EUROCRYPT, pages 24--43, 2010.

Digital Library

[44]

A. C. Yao. How to generate and exchange secrets. In Proc. of the 27th Annual Symposium on Foundations of Computer Science, pages 162--167. IEEE, 1986.

Digital Library

Cited By

Chu TLaoutaris N(2024)FedQV: Leveraging Quadratic Voting in Federated LearningProceedings of the ACM on Measurement and Analysis of Computing Systems10.1145/36560068:2(1-36)Online publication date: 29-May-2024
https://dl.acm.org/doi/10.1145/3656006
Hu RGuo YGong Y(2024)Federated Learning With Sparsified Model Perturbation: Improving Accuracy Under Client-Level Differential PrivacyIEEE Transactions on Mobile Computing10.1109/TMC.2023.334328823:8(8242-8255)Online publication date: Aug-2024
https://doi.org/10.1109/TMC.2023.3343288
Zhang CYang SMao LNing H(2024)Anomaly detection and defense techniques in federated learning: a comprehensive reviewArtificial Intelligence Review10.1007/s10462-024-10796-157:6Online publication date: 23-May-2024
https://doi.org/10.1007/s10462-024-10796-1
Show More Cited By

Index Terms

Secure multiparty aggregation with differential privacy: a comparative study

Recommendations

Combining Differential Privacy and Secure Multiparty Computation
ACSAC '15: Proceedings of the 31st Annual Computer Security Applications Conference

We consider how to perform privacy-preserving analyses on private data from different data providers and containing personal information of many different individuals. We combine differential privacy and secret sharing based secure multiparty ...
Achieving Differential Privacy in Secure Multiparty Data Aggregation Protocols on Star Networks
CODASPY '17: Proceedings of the Seventh ACM on Conference on Data and Application Security and Privacy

We consider the problem of privacy-preserving data aggregation in a star network topology, i.e., several untrusting participants connected to a single aggregator. We require that the participants do not discover each other's data, and the service ...
Efficient Noise Generation to Achieve Differential Privacy with Applications to Secure Multiparty Computation
Financial Cryptography and Data Security
Abstract
This paper studies the problem of constructing secure multiparty computation protocols whose outputs satisfy differential privacy. We first provide a general framework for multiparty protocols generating shares of noise drawn from distributions ... $^{}$

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Other conferences

EDBT '13: Proceedings of the Joint EDBT/ICDT 2013 Workshops

March 2013

423 pages

ISBN:9781450315999

DOI:10.1145/2457317

General Chair:
Giovanna Guerrini
Università di Genova, Italy

Copyright © 2013 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]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 18 March 2013

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Research-article

Conference

EDBT/ICDT '13

EDBT/ICDT '13: Joint 2013 EDBT/ICDT Conferences

March 18 - 22, 2013

Genoa, Italy

Acceptance Rates

EDBT '13 Paper Acceptance Rate 7 of 10 submissions, 70%;

Overall Acceptance Rate 7 of 10 submissions, 70%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

44
Total Citations
View Citations
763
Total Downloads

Downloads (Last 12 months)72
Downloads (Last 6 weeks)3

Reflects downloads up to 10 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Chu TLaoutaris N(2024)FedQV: Leveraging Quadratic Voting in Federated LearningProceedings of the ACM on Measurement and Analysis of Computing Systems10.1145/36560068:2(1-36)Online publication date: 29-May-2024
https://dl.acm.org/doi/10.1145/3656006
Hu RGuo YGong Y(2024)Federated Learning With Sparsified Model Perturbation: Improving Accuracy Under Client-Level Differential PrivacyIEEE Transactions on Mobile Computing10.1109/TMC.2023.334328823:8(8242-8255)Online publication date: Aug-2024
https://doi.org/10.1109/TMC.2023.3343288
Zhang CYang SMao LNing H(2024)Anomaly detection and defense techniques in federated learning: a comprehensive reviewArtificial Intelligence Review10.1007/s10462-024-10796-157:6Online publication date: 23-May-2024
https://doi.org/10.1007/s10462-024-10796-1
Tang PChen RSu SGuo SJu LLiu G(2023)Multi-Party Sequential Data Publishing Under Differential PrivacyIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2023.324166135:9(9562-9577)Online publication date: 1-Sep-2023
https://doi.org/10.1109/TKDE.2023.3241661
Eltaras TSabry FLabda WAlzoubi KAHMEDELTARAS Q(2023)Efficient Verifiable Protocol for Privacy-Preserving Aggregation in Federated LearningIEEE Transactions on Information Forensics and Security10.1109/TIFS.2023.327391418(2977-2990)Online publication date: 1-Jan-2023
https://dl.acm.org/doi/10.1109/TIFS.2023.3273914
Liu JZhang LLv CYu TFreris NLi X(2023)TPMDP: Threshold Personalized Multi-party Differential Privacy via Optimal Gaussian Mechanism2023 IEEE 20th International Conference on Mobile Ad Hoc and Smart Systems (MASS)10.1109/MASS58611.2023.00027(161-169)Online publication date: 25-Sep-2023
https://doi.org/10.1109/MASS58611.2023.00027
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
Zhuo MHuang WLiu LZhou STian Z(2022)A High-Utility Differentially Private Mechanism for Space Information NetworksRemote Sensing10.3390/rs1422584414:22(5844)Online publication date: 18-Nov-2022
https://doi.org/10.3390/rs14225844
Bao EZhu YXiao XYang YOoi BTan BAung K(2022)Skellam mixture mechanismProceedings of the VLDB Endowment10.14778/3551793.355179815:11(2348-2360)Online publication date: 1-Jul-2022
https://dl.acm.org/doi/10.14778/3551793.3551798
Humphries TAkhavan Mahdavi RVeitch SKerschbaum FYin HStavrou ACremers CShi E(2022)Selective MPCProceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security10.1145/3548606.3560559(1459-1472)Online publication date: 7-Nov-2022
https://dl.acm.org/doi/10.1145/3548606.3560559
Show More Cited By

View Options

Get Access

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

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents