nach oben

Erschienen in:

2016 | OriginalPaper | Buchkapitel

Concentrated Differential Privacy: Simplifications, Extensions, and Lower Bounds

verfasst von : Mark Bun, Thomas Steinke

Erschienen in: Theory of Cryptography

Verlag: Springer Berlin Heidelberg

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

“Concentrated differential privacy” was recently introduced by Dwork and Rothblum as a relaxation of differential privacy, which permits sharper analyses of many privacy-preserving computations. We present an alternative formulation of the concept of concentrated differential privacy in terms of the Rényi divergence between the distributions obtained by running an algorithm on neighboring inputs. With this reformulation in hand, we prove sharper quantitative results, establish lower bounds, and raise a few new questions. We also unify this approach with approximate differential privacy by giving an appropriate definition of “approximate concentrated differential privacy”.

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 Separating Computational and Statistical Differential Privacy in the Client-Server Model

Nächstes Kapitel Strong Hardness of Privacy from Weak Traitor Tracing

The privacy loss is a random variable which quantifies how much information is revealed about an individual by a computation involving their data; it depends on the outcome of the computation, the way the computation was performed, and the information that the individual wants to hide. We discuss it informally in this introduction and define it precisely in Definition 2 on p. 637.

In particular, consider answering k statistical queries on a dataset of n individuals by adding noise drawn from \(\mathcal {N}(0,(\sigma /n)^2)\) independently for each query. Each individual query satisfies \((O(\sqrt{\log (1/\delta )}/\sigma ),\delta )\)-differential privacy for any \(\delta >0\). Applying the advanced composition theorem shows that the composition of all k queries satisfies \((O(\sqrt{k} \log (1/\delta )/\sigma ),(k+1)\delta )\)-differential privacy for any \(\delta >0\). However, it is well-known that this bound can be improved to \((O(\sqrt{k \log (1/\delta )}/\sigma ),\delta )\)-differential privacy.

Rényi divergence has a parameter \(\alpha \in (1,\infty )\) which allows it to interpolate between KL-divergence (\(\alpha \!\rightarrow \! 1\)) and max-divergence (\(\alpha \!\rightarrow \! \infty \)). It should be thought of as a measure of dissimilarity between distributions. We define it formally in Sect. 2. Throughout, we assume that all logarithms are natural unless specified otherwise — that is, base \(e \approx 2.718\).

For clarity of exposition, we consider only \(\rho \)-zCDP in the introduction and give more general statements for \((\xi ,\rho )\)-zCDP later. We also believe that having a one-parameter definition is desirable.

We only discuss bounds on the upper tail of Z. We can obtain similar bounds on the lower tail of \(Z=\mathsf {PrivLoss}\left( M(x)\Vert M(x')\right) \) by considering \(Z'=\mathsf {PrivLoss}\left( M(x')\Vert M(x)\right) \).

Although Dwork and Rothblum’s work only appeared publicly in March 2016, they shared a preliminary draft of their paper with us before we commenced this work. As such, our ideas are heavily inspired by theirs.

We use “concentrated differential privacy” (CDP) to refer to the underlying concept formalized by both definitions.

[BLR13]

Blum, A., Ligett, K., Roth, A.: A learning theory approach to noninteractive database privacy. J. ACM 60(2), 12 (2013)MathSciNetCrossRefMATH

[BNS13]

Beimel, A., Nissim, K., Stemmer, U.: Private learning and sanitization: pure vs. approximate differential privacy. In: Raghavendra, P., Raskhodnikova, S., Jansen, K., Rolim, J.D.P. (eds.) APPROX/RANDOM -2013. LNCS, vol. 8096, pp. 363–378. Springer, Heidelberg (2013). doi:10.1007/978-3-642-40328-6_26 CrossRef

[BNS16]

Bun, M., Nissim, K., Stemmer, U.: Simultaneous private learning of multiple concepts. In: Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science, ITCS 2016, pp. 369–380. ACM, New York (2016)

[BUV14]

Bun, M., Ullman, J., Vadhan, S.P.: Fingerprinting codes and the price of approximate differential privacy. In: Symposium on Theory of Computing, STOC 2014, New York, NY, USA, 31 May - 03 June 2014, pp. 1–10 (2014)

[De12]

De, A.: Lower bounds in differential privacy. In: Cramer, R. (ed.) TCC 2012. LNCS, vol. 7194, pp. 321–338. Springer, Heidelberg (2012). doi:10.1007/978-3-642-28914-9_18 CrossRef

[DKM+06]

Dwork, C., Kenthapadi, K., McSherry, F., Mironov, I., Naor, M.: Our data, ourselves: privacy via distributed noise generation. In: Vaudenay, S. (ed.) EUROCRYPT 2006. LNCS, vol. 4004, pp. 486–503. Springer, Heidelberg (2006). doi:10.1007/11761679_29 CrossRef

[DL09]

Dwork, C., Lei, J.: Differential privacy and robust statistics. In: Proceedings of the 41st Annual ACM Symposium on Theory of Computing, STOC 2009, Bethesda, MD, USA, 31 May - 2 June 2009, pp. 371–380 (2009)

[DMNS06]

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

[DR16]

Dwork, C., Rothblum, C.: Concentrated differential privacy. CoRR, abs/1603.01887 (2016)

[DRV10]

Dwork, C., Rothblum, G.N., Vadhan, S.P.: Boosting and differential privacy. In: IEEE Symposium on Foundations of Computer Science (FOCS 2010), pp. 51–60. IEEE, 23–26 October 2010

[HT10]

Hardt, M., Talwar, K.: On the geometry of differential privacy. In: Proceedings of the Forty-Second ACM Symposium on Theory of Computing, STOC 2010, pp. 705–714, New York, NY, USA. ACM (2010)

[KOV15]

Kairouz, P., Oh, S., Viswanath, P.: The composition theorem for differential privacy. In: Proceedings of the 32nd International Conference on Machine Learning, ICML 2015, Lille, France, pp. 1376–1385, 6–11 July 2015

[MMP+10]

McGregor, A., Mironov, I., Pitassi, T., Reingold, O., Talwar, K., Vadhan, S.P.: The limits of two-party differential privacy. In: 51th Annual IEEE Symposium on Foundations of Computer Science, FOCS 23–26, 2010, Las Vegas, Nevada, USA, pp. 81–90, October 2010

[MT07]

McSherry, F., Talwar, K.: Mechanism design via differential privacy. In: 48th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2007, pp. 94–103, October 2007

[MV16]

Murtagh, J., Vadhan, S.P.: The complexity of computing the optimal composition of differential privacy. In: Proceedings of Theory of Cryptography - 13th International Conference, TCC2016-A, Tel Aviv, Israel, 10-13 January 2016, Part I, pp. 157–175 (2016)

[Ren61]

Rényi, A.: On measures of entropy, information. In: Proceedings of the Fourth Berkeley Symposium on Mathematical Statistics, Probability: Contributions to the Theory of Statistics, vol. 1, pp. 547–561. University of California Press (1961)

[SU15a]

Steinke, T., Ullman, J.: Between pure and approximate differential privacy. CoRR, abs/1501.06095 (2015)

[SU15b]

Steinke, T., Ullman, J.: Interactive fingerprinting codes, the hardness of preventing false discovery. In: COLT (2015). http://arXiv.org/abs/1410.1228

[Tar08]

Tardos, G.: Optimal probabilistic fingerprint codes. J. ACM 55(2), 10 (2008)MathSciNetCrossRefMATH

[Ull13]

Ullman, J.: Answering n \(\{\)2+ o (1)\(\}\) counting queries with differential privacy is hard. In: Proceedings of the Forty-Fifth Annual ACM Symposium on Theory of Computing, pp. 361–370. ACM (2013)

[vEH14]

van Erven, T., Harremos, P.: Rényi divergence and kullback-leibler divergence. IEEE Trans. Inf. Theory 60(7), 3797–3820 (2014)CrossRef

Titel: Concentrated Differential Privacy: Simplifications, Extensions, and Lower Bounds
verfasst von: Mark Bun
Thomas Steinke
Verlag: Springer Berlin Heidelberg
Buch: Theory of Cryptography
Print ISBN: 978-3-662-53640-7

Electronic ISBN: 978-3-662-53641-4

Copyright-Jahr: 2016
DOI: https://doi.org/10.1007/978-3-662-53641-4_24

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

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

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"