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
MTZ-Fachkongress

Antriebe und Energiesysteme von morgen


Austausch von Automobil- und Energiewirtschaft

Am 14./15. Mai geht es in Chemnitz um die Mobilitätswende durch Elektro- und Wasserstofffahrzeuge.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
Efficient, Reusable Fuzzy Extractors from LWE Kapitel lesen Erstes Kapitel lesen

2017 | OriginalPaper | Buchkapitel

On the Optimality of the Exponential Mechanism

verfasst von : Francesco Aldà, Hans Ulrich Simon

Erschienen in: Cyber Security Cryptography and Machine Learning

Verlag: Springer International Publishing

Einloggen

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

search-config
loading …

Abstract

In this work, we investigate one of the most renowned tools used in differential privacy, namely the exponential mechanism. We first study the optimality of the error introduced by the exponential mechanism in the average-case scenario, when the input/output universe of the mechanism can be modeled as a graph where each node is associated with a database. By leveraging linear programming theory, we provide some regularity conditions on the graph structure under which the exponential mechanism minimizes the average error. Moreover, we give a toy example in which the optimality is preserved (up to a constant factor) even if these regularity conditions hold only to a certain extent. Finally, we prove the worst-case optimality of the exponential mechanism when it is used to release the output of a sorting function.

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 Building Regular Registers with Rational Malicious Servers and Anonymous Clients
Nächstes Kapitel On Pairing Inversion of the Self-bilinear Map on Unknown Order Groups
Fußnoten
1
(C5) collapses to (C4) for normalized feasible solutions.
 
Literatur
1.
Aldà, F., Simon, H.U.: A lower bound on the release of differentially private integer partitions. Inf. Process. Lett. (2017, submitted)
2.
3.
Blocki, J., Datta, A., Bonneau, J.: Differentially private password frequency lists. In: Proceedings of the 23rd Annual Network and Distributed System Security Symposium (2016)
4.
Blum, A., Ligett, K., Roth, A.: A learning theory approach to non-interactive database privacy. J. ACM 60(2), 12 (2013)
5.
Brenner, H., Nissim, K.: Impossibility of differentially private universally optimal mechanisms. In: Proceedings of the 51st Annual IEEE Symposium on Foundations of Computer Science, pp. 71–80 (2010)
6.
7.
Duchi, J.C., Jordan, M.I., Wainwright, M.J.: Local privacy and statistical minimax rates. In: Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science, pp. 429–438 (2013)
8.
Dwork, C., McSherry, F., Nissim, K., Smith, A.: Calibrating noise to sensitivity in private data analysis. In: Halevi, S., Rabin, T. (eds.) TCC 2006. LNCS, vol. 3876, pp. 265–284. Springer, Heidelberg (2006). doi:10.​1007/​11681878_​14 CrossRef
9.
Dwork, C., McSherry, F., Talwar, K.: The price of privacy and the limits of LP decoding. In: Proceedings of the 39th Annual ACM Symposium on Theory of Computing, pp. 85–94 (2007)
10.
Geng, Q., Kairouz, P., Oh, S., Viswanath, P.: The staircase mechanism in differential privacy. IEEE J. Sel. Top. Sign. Process. 9(7), 1176–1184 (2015)
11.
Ghosh, A., Roughgarden, T., Sundararajan, M.: Universally utility-maximizing privacy mechanisms. In: Proceedings of the 41st Annual ACM Symposium on Theory of Computing, pp. 351–360 (2009)
12.
Hall, R., Rinaldo, A., Wasserman, L.: Random differential privacy. J. Priv. Confidentiality 4(2), 43–59 (2012)
13.
Hardt, M., Talwar, K.: On the geometry of differential privacy. In: Proceedings of the 42nd ACM Symposium on Theory of Computing, pp. 705–714 (2010)
14.
Hsu, J., Roth, A., Roughgarden, T., Ullman, J.: Privately solving linear programs. In: Esparza, J., Fraigniaud, P., Husfeldt, T., Koutsoupias, E. (eds.) ICALP 2014. LNCS, vol. 8572, pp. 612–624. Springer, Heidelberg (2014). doi:10.​1007/​978-3-662-43948-7_​51
15.
Kairouz, P., Oh, S., Viswanath, P.: Extremal mechanisms for local differential privacy. In: Advances in Neural Information Processing Systems, pp. 2879–2887 (2014)
16.
Kasiviswanathan, S.P., Lee, H.K., Nissim, K., Raskhodnikova, S., Smith, A.: What can we learn privately. SIAM J. Comput. 40(3), 793–826 (2011)MathSciNetCrossRefMATH
17.
Koufogiannis, F., Han, S., Pappas, G.J.: Optimality of the Laplace mechanism in differential privacy. arXiv preprint arXiv:​1504.​00065 (2015)
18.
McGregor, A., Mironov, I., Pitassi, T., Reingold, O., Talwar, K., Vadhan, S.: The limits of two-party differential privacy. In: Proceedings of the 51st Annual IEEE Symposium on Foundations of Computer Science, pp. 81–90 (2010)
19.
McSherry, F., Talwar, K.: Mechanism design via differential privacy. In: Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science, pp. 94–103 (2007)
Metadaten
Titel
On the Optimality of the Exponential Mechanism
verfasst von
Francesco Aldà
Hans Ulrich Simon
Copyright-Jahr
2017
Buch
Cyber Security Cryptography and Machine Learning

Print ISBN: 978-3-319-60079-6

Electronic ISBN: 978-3-319-60080-2

Copyright-Jahr: 2017

DOI
https://doi.org/10.1007/978-3-319-60080-2_5

Premium Partner

    Bildnachweise