research-article

Public Access

Honeycrisp: large-scale differentially private aggregation without a trusted core

Authors:

Brett Hemenway Falk,

Andreas HaeberlenAuthors Info & Claims

SOSP '19: Proceedings of the 27th ACM Symposium on Operating Systems Principles

Pages 196 - 210

https://doi.org/10.1145/3341301.3359660

Published: 27 October 2019 Publication History

Abstract

Recently, a number of systems have been deployed that gather sensitive statistics from user devices while giving differential privacy guarantees. One prominent example is the component in Apple's macOS and iOS devices that collects information about emoji usage and new words. However, these systems have been criticized for making unrealistic assumptions, e.g., by creating a very high "privacy budget" for answering queries, and by replenishing this budget every day, which results in a high worst-case privacy loss. However, it is not obvious whether such assumptions can be avoided if one requires a strong threat model and wishes to collect data periodically, instead of just once.

In this paper, we show that, essentially, it is possible to have one's cake and eat it too. We describe a system called Honeycrisp whose privacy cost depends on how often the data changes, and not on how often a query is asked. Thus, if the data is relatively stable (as is likely the case, e.g., with emoji and word usage), Honeycrisp can answer periodic queries for many years, as long as the underlying data does not change too often. Honeycrisp accomplishes this by using a) the sparse-vector technique, and b) a combination of cryptographic techniques to enable global differential privacy without a trusted party. Using a prototype implementation, we show that Honeycrisp is efficient and can scale to large deployments.

References

[1]

G. Ács and C. Castelluccia. I have a DREAM! (DiffeRentially privatE smArt Metering). In Proc. International Workshop on Information Hiding, 2011.

[2]

M. R. Albrecht, R. Player, and S. Scott. On the concrete hardness of learning with errors. Journal of Mathematical Cryptography, 9:169--203, 2015.

[3]

A. Aly, M. Keller, D. Rotaru, P. Scholl, N. P. Smart, and T. Wood. SCALE-MAMBA software. https://homes.esat.kuleuven.be/~nsmart/SCALE/, 2018.

[4]

Apple. Apple reports first quarter results. Press release, February 2018; https://www.apple.com/newsroom/2018/02/apple-reports-first-quarter-results/.

[5]

Apple. Differential privacy. https://images.apple.com/privacy/docs/Differential_Privacy_Overview.pdf.

[6]

Apple. Reports on government information requests. https://www.apple.com/legal/transparency/report-pdf.html.

[7]

Apple. A message to our customers. https://www.apple.com/customer-letter/, Feb. 2016.

[8]

Apple Differential Privacy Team. Learning with privacy at scale. Apple Machine Learning Journal, 1(8), Dec. 2017.

[9]

E. K. B. Laurie, A. Langley. Certificate transparency. RFC 6962, RFC Editor, June 2013.

[10]

E. Ben-Sasson, A. Chiesa, E. Tromer, and M. Virza. Succinct non-interactive zero knowledge for a Von Neumann architecture. In Proc. USENIX Security, 2014.

Digital Library

[11]

A. Bhowmick, J. Duchi, J. Freudiger, G. Kapoor, and R. Rogers. Protection against reconstruction and its applications in private federated learning. arXiv:1812.00984 [cs, stat], Dec. 2018.

[12]

V. Bindschaedler, S. Rane, A. E. Brito, V. Rao, and E. Uzun. Achieving differential privacy in secure multiparty data aggregation protocols on star networks. In Proc. CODASPY, Mar. 2017.

Digital Library

[13]

A. Bittau, U. Erlingsson, P. Maniatis, I. Mironov, A. Raghunathan, D. Lie, M. Rudominer, U. Kode, J. Tinnes, and B. Seefeld. PROCHLO: Strong privacy for analytics in the crowd. In Proc. SOSP, Oct. 2017.

Digital Library

[14]

K. Bonawitz, H. Eichner, W. Grieskamp, D. Huba, A. Ingerman, V. Ivanov, C. M. Kiddon, J. Konecny, S. Mazzocchi, B. McMahan, T. V. Overveldt, D. Petrou, D. Ramage, and J. Roselander. Towards federated learning at scale: System design. In Proc. SysML, 2019.

[15]

K. Bonawitz, V. Ivanov, B. Kreuter, A. Marcedone, H. B. McMahan, S. Patel, D. Ramage, A. Segal, and K. Seth. Practical secure aggregation for privacy-preserving machine learning. In Proc. CCS, 2017.

Digital Library

[16]

E. Boyle, G. Couteau, N. Gilboa, Y. Ishai, L. Kohl, and P. Scholl. Efficient pseudorandom correlation generators: Silent OT extension and more. IACR Cryptology ePrint Archive, 2019:448, 2019.

[17]

C. Buckler. Average page weight increases 15% in 2014, Dec. 2014. https://www.sitepoint.com/average-page-weight-increases-15-2014/.

[18]

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

[19]

T.-H. H. Chan, E. Shi, and D. Song. Private and Continual Release of Statistics. ACM Trans. Inf. Syst. Secur., 14(3):26:1--26:24, Nov. 2011.

Digital Library

[20]

R. Chen, A. Reznichenko, P. Francis, and J. Gehrke. Towards statistical queries over distributed private user data. In Proc. NSDI, 2012.

Digital Library

[21]

A. R. Chowdhury, C. Wang, X. He, A. Machanavajjhala, and S. Jha. Outis: Crypto-Assisted Differential Privacy on Untrusted Servers. arXiv:1902.07756 [cs], Feb. 2019.

[22]

H. Corrigan-Gibbs and D. Boneh. Prio: Private, robust, and scalable computation of aggregate statistics. In Proc. NSDI, Mar. 2017.

[23]

I. Damgård, V. Pastro, N. Smart, and S. Zakarias. Multiparty computation from somewhat homomorphic encryption. In Proc. CRYPTO. 2012.

Digital Library

[24]

G. Danezis, C. Fournet, M. Kohlweiss, and S. Zanella-Béguelin. Smart meter aggregation via secret-sharing. In Proc. SEGS, 2013.

Digital Library

[25]

Y. Desmedt and Y. Frankel. Threshold cryptosystems. In Proc. CRYPTO, 1989.

Digital Library

[26]

C. Dwork, F. McSherry, K. Nissim, and A. Smith. Calibrating Noise to Sensitivity in Private Data Analysis. In Proc. TCC, 2006.

Digital Library

[27]

C. Dwork, M. Naor, O. Reingold, G. N. Rothblum, and S. Vadhan. On the complexity of differentially private data release: Efficient algorithms and hardness results. In Proc. STOC, 2009.

Digital Library

[28]

C. Dwork and A. Roth. The Algorithmic Foundations of Differential Privacy. Now Publishers Inc, Aug. 2014.

[29]

C. Dwork, G. N. Rothblum, and S. Vadhan. Boosting and differential privacy. In Proc. FOCS, 2010.

Digital Library

[30]

J. Eisenstein. What to do about bad language on the internet. NAACL-HLT, 2013(4):359--369, June 2013.

[31]

U. Erlingsson, V. Feldman, I. Mironov, A. Raghunathan, K. Talwar, and A. Thakurta. Amplification by shuffling: From local to central differential privacy via anonymity. In Proc. SODA, 2019.

[32]

U. Erlingsson, V. Pihur, and A. Korolova. RAPPOR: Randomized aggregatable privacy-preserving ordinal response. In Proc. CCS, 2014.

Digital Library

[33]

G. Fanti, V. Pihur, and U. Erlingsson. Building a RAPPOR with the Unknown: Privacy-Preserving Learning of Associations and Data Dictionaries. arXiv:1503.01214 [cs], Mar. 2015.

[34]

B. Ford, P. Srisuresh, and D. Kegel. Peer-to-peer communication across network address translators. In Proc. USENIX ATC, 2005.

[35]

M. J. Freedman and R. Morris. Tarzan: A peer-to-peer anonymizing network layer. In Proc. CCS, 2002.

Digital Library

[36]

D. Froelicher, P. Egger, J. S. Sousa, J. L. Raisaro, Zhicong Huang, C. Mouchet, B. Ford, and J.-P. Hubaux. UnLynx: A Decentralized System for Privacy-Conscious Data Sharing. In Proc. PETS, Oct. 2017.

[37]

Y. Gilad, R. Hemo, S. Micali, G. Vlachos, and N. Zeldovich. Algorand: Scaling Byzantine agreements for cryptocurrencies. In Proc. SOSP, 2017.

Digital Library

[38]

S. Goryczka and L. Xiong. A comprehensive comparison of multi-party secure additions with differential privacy. IEEE Transactions on Dependable and Secure Computing, 14(5):463--477, 2017.

[39]

A. Haeberlen, B. C. Pierce, and A. Narayan. Differential privacy under fire. In Proc. USENIX Security, Aug. 2011.

Digital Library

[40]

S. Halevi, Y. Lindell, and B. Pinkas. Secure computation on the web: Computing without simultaneous interaction. In Proc. CRYPTO, 2011.

[41]

S. Halevi, Y. Lindell, and B. Pinkas. Secure computation on the web: Computing without simultaneous interaction. IACR ePrint 2011/157, 2011.

[42]

S. Hohenberger, S. Myers, R. Pass, and a. shelat. ANONIZE: A large-scale anonymous survey system. In Proc. IEEE S&P, 2014.

Digital Library

[43]

J. Hsu, M. Gaboardi, A. Haeberlen, S. Khanna, A. Narayan, B. C. Pierce, and A. Roth. Differential privacy: An economic method for choosing epsilon. In Proc. CSF, July 2014.

Digital Library

[44]

M. Jawurek and F. Kerschbaum. Fault-tolerant privacy-preserving statistics. In Proc. PETS, 2012.

Digital Library

[45]

M. Joseph, A. Roth, J. Ullman, and B. Waggoner. Local Differential Privacy for Evolving Data. In Proc. NIPS, 2018.

[46]

M. Joye and B. Libert. A Scalable Scheme for Privacy-Preserving Aggregation of Time-Series Data. In Proc. FC, 2013.

[47]

M. Kraitsberg, Y. Lindell, V. Osheter, N. P. Smart, and Y. T. Alaoui. Adding distributed decryption and key generation to a ring-lwe based cca encryption scheme. In Australasian Conference on Information Security and Privacy, pages 192--210. Springer, 2019.

Digital Library

[48]

B. Kreuter, A. Shelat, and C.-H. Shen. Billion-gate secure computation with malicious adversaries. In Proc. USENIX Security, 2012.

[49]

KU Leuven COSIC. SCALE-MAMBA. https://github.com/KULeuven-COSIC/SCALE-MAMBA.

[50]

K. Kursawe, G. Danezis, and M. Kohlweiss. Privacy-friendly aggregation for the smart-grid. In Proc. PETS, 2011.

[51]

S. Le Blond, D. Choffnes, W. Zhou, P. Druschel, H. Ballani, and P. Francis. Towards efficient traffic-analysis resistant anonymity networks. SIGCOMM Comput. Commun. Rev., 43(4):303--314, Aug. 2013.

Digital Library

[52]

I. Leontiadis, K. Elkhiyaoui, M. Önen, and R. Molva. PUDA - Privacy and unforgeability for data aggregation. In Proc. CANS, 2015.

[53]

LWE estimator tool. https://bitbucket.org/malb/lwe-estimator/, commit 3019847.

[54]

V. Lyubashevsky, C. Peikert, and O. Regev. On ideal lattices and learning with errors over rings. In Proc. EUROCRYPT, 2010.

Digital Library

[55]

F. McSherry. Privacy integrated queries. In Proc. SIGMOD, 2009.

Digital Library

[56]

L. Melis, G. Danezis, and E. De Cristofaro. Efficient Private Statistics with Succinct Sketches. In Proc. NDSS, 2016.

[57]

R. C. Merkle. A Digital Signature Based on a Conventional Encryption Function. In Proc. CRYPTO, Berlin, Heidelberg, 1987.

[58]

I. Mironov. On significance of the least significant bits for differential privacy. In Proc. CCS, 2012.

Digital Library

[59]

I. Morris. Apple Has Sold 1.2 Billion iPhones Worth $738 Billion In 10 Years. Forbes. June 29, 2017. https://www.forbes.com/sites/ianmorris/2017/06/29/apple-has-sold-1-2-billion-iphones-worth-738-billion-in-10-years/.

[60]

A. Narayan and A. Haeberlen. DJoin: Differentially private join queries over distributed databases. In Proc. OSDI, 2012.

Digital Library

[61]

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

Digital Library

[62]

A. Papadimitriou, A. Narayan, and A. Haeberlen. DStress: Efficient differentially private computations on distributed data. In Proc. EuroSys, 2017.

Digital Library

[63]

R. A. Popa, A. J. Blumberg, H. Balakrishnan, and F. H. Li. Privacy and accountability for location-based aggregate statistics. In Proc. CCS, 2011.

Digital Library

[64]

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

Digital Library

[65]

I. S. Reed and G. Solomon. Polynomial codes over certain finite fields. SIAM Journal, 8(2):300--304, 1960.

[66]

A. Roth and T. Roughgarden. Interactive privacy via the median mechanism. In Proc. STOC, 2010.

Digital Library

[67]

E. Roth, D. Noble, B. H. Falk, and A. Haeberlen. Honeycrisp: Large-scale differentially private aggregation without a trusted core (extended version). Technical Report MS-CIS-19-03, University of Pennsylvania, Sept. 2019.

[68]

I. Roy, S. Setty, A. Kilzer, V. Shmatikov, and E. Witchel. Airavat: Security and privacy for MapReduce. In Proc. NSDI, 2010.

Digital Library

[69]

A. Shamir. How to share a secret. CACM, 22(11):612--613, 1979.

Digital Library

[70]

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

[71]

E. Syta, P. Jovanovic, E. K. Kogias, N. Gailly, L. Gasser, I. Khoffi, M. J. Fischer, and B. Ford. Scalable bias-resistant distributed randomness. In Proc. IEEE S&P, 2017.

[72]

J. Tang, A. Korolova, X. Bai, X. Wang, and X. Wang. Privacy loss in Apple's implementation of differential privacy on MacOS 10.12, 2017. https://arxiv.org/pdf/1709.02753.pdf.

[73]

X. Wang, S. Ranellucci, and J. Katz. Global-scale secure multiparty computation. In Proc. CCS, 2017.

Digital Library

[74]

T. Wolverton. iPhone sales crater 15% in Apple's worst holiday results in a decade, and the forecast looks just as grim. Business Insider, Jan 2019. https://www.businessinsider.com/apple-q1-2019-earnings-iphone-sales-revenue-eps-analysis-2019-1.

[75]

A. Yao. Protocols for secure computations (extended abstract). In Proc. FOCS, 1982.

Cited By

Zhou ZChen HChen LZhang DWu CLiu XKhan M(2024)NetDP: In-Network Differential Privacy for Large-Scale Data ProcessingIEEE Transactions on Green Communications and Networking10.1109/TGCN.2024.34327818:3(1076-1089)Online publication date: Sep-2024
https://doi.org/10.1109/TGCN.2024.3432781
Liu QYan YLigeti PJin Y(2024)A Secure Federated Data-Driven Evolutionary Multi-Objective Optimization AlgorithmIEEE Transactions on Emerging Topics in Computational Intelligence10.1109/TETCI.2023.33135558:1(191-205)Online publication date: Feb-2024
https://doi.org/10.1109/TETCI.2023.3313555
Ngong IGibson NNear J(2024)Olympia: A Simulation Framework for Evaluating the Concrete Scalability of Secure Aggregation Protocols2024 IEEE Conference on Secure and Trustworthy Machine Learning (SaTML)10.1109/SaTML59370.2024.00033(534-551)Online publication date: 9-Apr-2024
https://doi.org/10.1109/SaTML59370.2024.00033
Show More Cited By

Recommendations

Computing Join Aggregates over Private Tables
DaWaK '07: Proceedings of the 9th international conference on Data Warehousing and Knowledge Discovery

We propose a privacy-preserving protocol for computing aggregation queries over the join of private tables. In this problem, several parties wish to share aggregated information over the join of their tables, but want to conceal the details that ...
Personalised anonymity for microdata release

Individual privacy protection in the released data sets has become an important issue in recent years. The release of microdata provides a significant information resource for researchers, whereas the release of person‐specific data poses a threat to ...
A privacy framework: indistinguishable privacy
EDBT '13: Proceedings of the Joint EDBT/ICDT 2013 Workshops

In this paper we illustrate a privacy framework named Indistinguishable Privacy. Indistinguishable privacy could be deemed as the formalization of the existing privacy definitions in privacy preserving data publishing as well as secure multi-party ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SOSP '19: Proceedings of the 27th ACM Symposium on Operating Systems Principles

October 2019

615 pages

ISBN:9781450368735

DOI:10.1145/3341301

General Chairs:
Tim Brecht
University of Waterloo
,
Carey Williamson
University of Calgary

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

SIGOPS: ACM Special Interest Group on Operating Systems

In-Cooperation

USENIX Assoc: USENIX Assoc

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 27 October 2019

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Research-article

Funding Sources

National Science Foundation

Conference

SOSP '19

Sponsor:

SIGOPS

SOSP '19: ACM SIGOPS 27th Symposium on Operating Systems Principles

October 27 - 30, 2019

Ontario, Huntsville, Canada

Acceptance Rates

Overall Acceptance Rate 174 of 961 submissions, 18%

Upcoming Conference

SOSP '25

Sponsor:
sigops

ACM SIGOPS 31st Symposium on Operating Systems Principles

October 13 - 16, 2025

Seoul , Republic of Korea

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

25
Total Citations
View Citations
1,695
Total Downloads

Downloads (Last 12 months)185
Downloads (Last 6 weeks)27

Reflects downloads up to 20 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Zhou ZChen HChen LZhang DWu CLiu XKhan M(2024)NetDP: In-Network Differential Privacy for Large-Scale Data ProcessingIEEE Transactions on Green Communications and Networking10.1109/TGCN.2024.34327818:3(1076-1089)Online publication date: Sep-2024
https://doi.org/10.1109/TGCN.2024.3432781
Liu QYan YLigeti PJin Y(2024)A Secure Federated Data-Driven Evolutionary Multi-Objective Optimization AlgorithmIEEE Transactions on Emerging Topics in Computational Intelligence10.1109/TETCI.2023.33135558:1(191-205)Online publication date: Feb-2024
https://doi.org/10.1109/TETCI.2023.3313555
Ngong IGibson NNear J(2024)Olympia: A Simulation Framework for Evaluating the Concrete Scalability of Secure Aggregation Protocols2024 IEEE Conference on Secure and Trustworthy Machine Learning (SaTML)10.1109/SaTML59370.2024.00033(534-551)Online publication date: 9-Apr-2024
https://doi.org/10.1109/SaTML59370.2024.00033
Küchler NOpel ELycklama HViand AHithnawi A(2024)Cohere: Managing Differential Privacy in Large Scale Systems2024 IEEE Symposium on Security and Privacy (SP)10.1109/SP54263.2024.00122(991-1008)Online publication date: 19-May-2024
https://doi.org/10.1109/SP54263.2024.00122
Liu SChen LFu Y(2024)Periscoping: Private Key Distribution for Large-Scale MixnetsIEEE INFOCOM 2024 - IEEE Conference on Computer Communications10.1109/INFOCOM52122.2024.10621274(681-690)Online publication date: 20-May-2024
https://doi.org/10.1109/INFOCOM52122.2024.10621274
Liu SCao YMurakami TLiu JYoshikawa M(2024)CARGO: Crypto-Assisted Differentially Private Triangle Counting Without Trusted Servers2024 IEEE 40th International Conference on Data Engineering (ICDE)10.1109/ICDE60146.2024.00136(1671-1684)Online publication date: 13-May-2024
https://doi.org/10.1109/ICDE60146.2024.00136
Riedel PSchick Lvon Schwerin RReichert MSchaudt DHafner A(2024)Comparative analysis of open-source federated learning frameworks - a literature-based survey and reviewInternational Journal of Machine Learning and Cybernetics10.1007/s13042-024-02234-z15:11(5257-5278)Online publication date: 28-Jun-2024
https://doi.org/10.1007/s13042-024-02234-z
Margolin ENewatia KLuo TRoth EHaeberlen ADruschel PKaufmann AMace JFlinn JSeltzer M(2023)Arboretum: A Planner for Large-Scale Federated Analytics with Differential PrivacyProceedings of the 29th Symposium on Operating Systems Principles10.1145/3600006.3624566(451-465)Online publication date: 23-Oct-2023
https://dl.acm.org/doi/10.1145/3600006.3624566
Mangipudi SChuprikov PEugster PViering MSavvides S(2023)Generalized Policy-Based Noninterference for Efficient Confidentiality-PreservationProceedings of the ACM on Programming Languages10.1145/35912317:PLDI(267-291)Online publication date: 6-Jun-2023
https://dl.acm.org/doi/10.1145/3591231
Ma YWoods JAngel SPolychroniadou ARabin T(2023)Flamingo: Multi-Round Single-Server Secure Aggregation with Applications to Private Federated Learning2023 IEEE Symposium on Security and Privacy (SP)10.1109/SP46215.2023.10179434(477-496)Online publication date: May-2023
https://doi.org/10.1109/SP46215.2023.10179434
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