Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Bücher
Zeitschriften
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
ATZ-Fachkongress

Chassis.tech plus 2024


4 Kongresse in einer Veranstaltung

Treffen Sie in München die Fachleute von Chassis, Lenkung, Bremsen sowie Reifen/Räder.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
Compact Adaptively Secure ABE for from k-Lin Kapitel lesen Erstes Kapitel lesen

2019 | OriginalPaper | Buchkapitel

Distributed Differential Privacy via Shuffling

verfasst von : Albert Cheu, Adam Smith, Jonathan Ullman, David Zeber, Maxim Zhilyaev

Erschienen in: Advances in Cryptology – EUROCRYPT 2019

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

We consider the problem of designing scalable, robust protocols for computing statistics about sensitive data. Specifically, we look at how best to design differentially private protocols in a distributed setting, where each user holds a private datum. The literature has mostly considered two models: the “central” model, in which a trusted server collects users’ data in the clear, which allows greater accuracy; and the “local” model, in which users individually randomize their data, and need not trust the server, but accuracy is limited. Attempts to achieve the accuracy of the central model without a trusted server have so far focused on variants of cryptographic multiparty computation (MPC), which limits scalability.
In this paper, we initiate the analytic study of a shuffled model for distributed differentially private algorithms, which lies between the local and central models. This simple-to-implement model, a special case of the ESA framework of [5], augments the local model with an anonymous channel that randomly permutes a set of user-supplied messages. For sum queries, we show that this model provides the power of the central model while avoiding the need to trust a central server and the complexity of cryptographic secure function evaluation. More generally, we give evidence that the power of the shuffled model lies strictly between those of the central and local models: for a natural restriction of the model, we show that shuffled protocols for a widely studied selection problem require exponentially higher sample complexity than do central-model protocols.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Jetzt informieren
Vorheriges Kapitel Linear Equivalence of Block Ciphers with Partial Non-Linear Layers: Application to LowMC
Nächstes Kapitel Lower Bounds for Differentially Private RAMs
Fußnoten
1
Variations on this idea based on onion routing allow the user to specify a secret path through a network of mixes.
 
2
These works assume that the dataset x consists of independent samples from some distribution \(\mathcal {D}\), and define accuracy for selection with respect to mean of that distribution. By standard arguments, a lower bound for the distributional version implies a lower bound for the version we have defined.
 
3
The idea is to simulate multiple rounds of our protocol for binary sums, one round per dimension.
 
4
Note that changing one user’s data can only change two entries of their local histogram, so we only have to scale \(\varepsilon ,\delta \) by a factor of 2 rather than a factor that grows with D.
 
Literatur
1.
Abowd, J.M.: The U.S. census bureau adopts differential privacy. In: Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining KDD 2018, pp. 2867–2867. ACM, New York (2018)
2.
Bafna, M., Ullman, J.: The price of selection in differential privacy. In: Conference on Learning Theory, pp. 151–168 (2017)
3.
Bassily, R., Smith, A.: Local, private, efficient protocols for succinct histograms. In: Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, pp. 127–135. ACM (2015)
4.
5.
Bittau, A., et al.: PROCHLO: strong privacy for analytics in the crowd. In: Proceedings of the Symposium on Operating Systems Principles (SOSP) (2017)
6.
Bonawitz, K., et al.: Practical secure aggregation for privacy preserving machine learning. IACR Cryptology ePrint Archive (2017)
7.
Bun, M., Nelson, J., Stemmer, U.: Heavy hitters and the structure of local privacy. In: ACM SIGMOD/PODS Conference International Conference on Management of Data (PODS 2018) (2018)
8.
9.
10.
Chaum, D.L.: Untraceable electronic mail, return addresses, and digital pseudonyms. Commun. ACM 24(2), 84–90 (1981)CrossRef
11.
Corrigan-Gibbs, H., Boneh, D.: Prio: private, robust, and scalable computation of aggregate statistics. In: Proceedings of the 14th USENIX Conference on Networked Systems Design and Implementation NSDI 2017, pp. 259–282. USENIX Association, Berkeley, CA, USA (2017)
12.
Duchi, J.C., Jordan, M.I., Wainwright, M.J.: Local privacy and statistical minimax rates. In: 2013 IEEE 54th Annual Symposium on Foundations of Computer Science (FOCS), pp. 429–438. IEEE (2013)
13.
14.
15.
Dwork, C., Rothblum, G.N., Vadhan, S.P.: Boosting and differential privacy. In: FOCS, pp. 51–60. IEEE (2010)
16.
Erlingsson, U., Feldman, V., Mironov, I., Raghunathan, A., Talwar, K., Thakurta, A.: Amplification by shuffling: From local to central differential privacy by anonymity. In: Proceedings of the 30th Annual ACM-SIAM Symposium on Discrete Algorithms. SODA 2019 (2019)CrossRef
17.
Erlingsson, Ú., Pihur, V., Korolova, A.: RAPPOR: randomized aggregatable privacy-preserving ordinal response. In: ACM Conference on Computer and Communications Security (CCS) (2014)
18.
Evfimievski, A., Gehrke, J., Srikant, R.: Limiting privacy breaches in privacy preserving data mining. In: PODS, pp. 211–222. ACM (2003)
19.
van den Hooff, J., Lazar, D., Zaharia, M., Zeldovich, N.: Vuvuzela: scalable private messaging resistant to traffic analysis. In: Proceedings of the 25th Symposium on Operating Systems Principles SOSP 2015, pp. 137–152. ACM, New York (2015)
20.
Kasiviswanathan, S.P., Lee, H.K., Nissim, K., Raskhodnikova, S., Smith, A.: What can we learn privately? In: Foundations of Computer Science (FOCS). IEEE (2008)
21.
Kasiviswanathan, S.P., Smith, A.: On the ‘semantics’ of differential privacy: A bayesian formulation. CoRR arXiv:​0803.​39461 [cs.CR] (2008)
22.
Kearns, M.J.: Efficient noise-tolerant learning from statistical queries. In: STOC, pp. 392–401. ACM, 16–18 May 1993
23.
Kwon, A., Lazar, D., Devadas, S., Ford, B.: Riffle: an efficient communication system with strong anonymity. PoPETs 2016(2), 115–134 (2016)
24.
McMillan, R.: Apple tries to peek at user habits without violating privacy. Wall Street J. (2016)
25.
McSherry, F., Talwar, K.: Mechanism design via differential privacy. In: IEEE Foundations of Computer Science (FOCS) (2007)
26.
Shi, E., Chan, T.H., Rieffel, E.G., Chow, R., Song, D.: Privacy-preserving aggregation of time-series data. In: Proceedings of the Network and Distributed System Security Symposium (NDSS 2011) (2011)
27.
Smith, A.: Differential privacy and the secrecy of the sample (2009)
28.
Steinke, T., Ullman, J.: Tight lower bounds for differentially private selection. In: 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), pp. 552–563. IEEE (2017)
29.
Thakurta, A.G., et al.: Learning new words. US Patent 9,645,998, 9 May 2017
30.
Tyagi, N., Gilad, Y., Leung, D., Zaharia, M., Zeldovich, N.: Stadium: a distributed metadata-private messaging system. In: Proceedings of the 26th Symposium on Operating Systems Principles SOSP 2017, pp. 423–440. ACM, New York (2017)
31.
Ullman, J.: Tight lower bounds for locally differentially private selection. CoRR abs/1802.02638 (2018)
32.
33.
Warner, S.L.: Randomized response: a survey technique for eliminating evasive answer bias. J. Am. Stat. Assoc. 60(309), 63–69 (1965)CrossRef
Metadaten
Titel
Distributed Differential Privacy via Shuffling
verfasst von
Albert Cheu
Adam Smith
Jonathan Ullman
David Zeber
Maxim Zhilyaev
Copyright-Jahr
2019
Buch
Advances in Cryptology – EUROCRYPT 2019

Print ISBN: 978-3-030-17652-5

Electronic ISBN: 978-3-030-17653-2

Copyright-Jahr: 2019

DOI
https://doi.org/10.1007/978-3-030-17653-2_13

Premium Partner

    Bildnachweise