Top

Published in:

2018 | OriginalPaper | Chapter

Bisimilarity Distances for Approximate Differential Privacy

Authors : Dmitry Chistikov, Andrzej S. Murawski, David Purser

Published in: Automated Technology for Verification and Analysis

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

Differential privacy is a widely studied notion of privacy for various models of computation. Technically, it is based on measuring differences between probability distributions. We study \(\epsilon ,\delta \)-differential privacy in the setting of labelled Markov chains. While the exact differences relevant to \(\epsilon ,\delta \)-differential privacy are not computable in this framework, we propose a computable bisimilarity distance that yields a sound technique for measuring \(\delta \), the parameter that quantifies deviation from pure differential privacy. We show this bisimilarity distance is always rational, the associated threshold problem is in NP, and the distance can be computed exactly with polynomially many calls to an NP oracle.

Dont have a licence yet? Then find out more about our products and how to get one now:

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!

inform now

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!

inform now

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!

inform now

previous chapter Temporal Logic Verification of Stochastic Systems Using Barrier Certificates

next chapter A Symbolic Algorithm for Lazy Synthesis of Eager Strategies

A pseudometric must satisfy \(m(x,x)=0\), \(m(x,y)=m(y,x)\) and \(m(x,z)\le m(x,y)+m(y,z)\). For metrics, one additionally requires that \(m(x,y)=0\) should imply \(x=y\).

More precisely, the existence of such a procedure would be a breakthrough in the computational complexity theory, showing that \(\mathbf {NP} = \exists \mathbb R\). This would imply that a multitude of problems in computational geometry could be solved using SAT solvers [11, 24]. Unlike for \( bd _\alpha \), variable assignments in these problems may need to be irrational, even if all numbers in the input data are integer or rational.

Albarghouthi, A., Hsu, J.: Synthesizing coupling proofs of differential privacy. Proc. ACM Program. Lang. 2, 58:1–58:30 (2018)CrossRef

Bacci, G., Bacci, G., Larsen, K.G., Mardare, R.: On-the-fly exact computation of bisimilarity distances. In: Piterman, N., Smolka, S.A. (eds.) TACAS 2013. LNCS, vol. 7795, pp. 1–15. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-36742-7_1CrossRefMATH

Baier, C., Katoen, J.P.: Principles of Model Checking. MIT Press, Cambridge (2008)

Barthe, G., Espitau, T., Grégoire, B., Hsu, J., Stefanesco, L., Strub, P.-Y.: Relational reasoning via probabilistic coupling. In: Davis, M., Fehnker, A., McIver, A., Voronkov, A. (eds.) LPAR 2015. LNCS, vol. 9450, pp. 387–401. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-48899-7_27CrossRefMATH

Barthe, G., Köpf, B., Olmedo, F., Zanella Béguelin, S.: Probabilistic relational reasoning for differential privacy. In: POPL, pp. 97–110. ACM (2012)

Billingsley, P.: Probability and Measure, 2nd edn. Wiley, New York (1986)

van Breugel, F.: Probabilistic bisimilarity distances. ACM SIGLOG News 4(4), 33–51 (2017)

van Breugel, F., Sharma, B., Worrell, J.: Approximating a behavioural pseudometric without discount for probabilistic systems. In: Seidl, H. (ed.) FoSSaCS 2007. LNCS, vol. 4423, pp. 123–137. Springer, Heidelberg (2007). https://doi.org/10.1007/978-3-540-71389-0_10CrossRef

van Breugel, F., Worrell, J.: An algorithm for quantitative verification of probabilistic transition systems. In: Larsen, K.G., Nielsen, M. (eds.) CONCUR 2001. LNCS, vol. 2154, pp. 336–350. Springer, Heidelberg (2001). https://doi.org/10.1007/3-540-44685-0_23CrossRef

10.

van Breugel, F., Worrell, J.: The complexity of computing a bisimilarity pseudometric on probabilistic automata. In: van Breugel, F., Kashefi, E., Palamidessi, C., Rutten, J. (eds.) Horizons of the Mind. A Tribute to Prakash Panangaden. LNCS, vol. 8464, pp. 191–213. Springer, Cham (2014). https://doi.org/10.1007/978-3-319-06880-0_10CrossRef

11.

Cardinal, J.: Computational geometry column 62. SIGACT News 46(4), 69–78 (2015)MathSciNetCrossRef

12.

Chatzikokolakis, K., Gebler, D., Palamidessi, C., Xu, L.: Generalized bisimulation metrics. In: Baldan, P., Gorla, D. (eds.) CONCUR 2014. LNCS, vol. 8704, pp. 32–46. Springer, Heidelberg (2014). https://doi.org/10.1007/978-3-662-44584-6_4CrossRef

13.

Chaum, D.: The dining cryptographers problem: Unconditional sender and recipient untraceability. J. Cryptol. 1(1), 65–75 (1988)MathSciNetCrossRef

14.

Chen, D., van Breugel, F., Worrell, J.: On the complexity of computing probabilistic bisimilarity. In: Birkedal, L. (ed.) FoSSaCS 2012. LNCS, vol. 7213, pp. 437–451. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-28729-9_29CrossRefMATH

15.

Deng, Y., Du, W.: The Kantorovich metric in computer science: a brief survey. Electron Notes Theor. Comput. Sci. 253(3), 73–82 (2009)CrossRef

16.

Desharnais, J., Gupta, V., Jagadeesan, R., Panangaden, P.: Metrics for labelled Markov processes. Theor. Comput. Sci. 318(3), 323–354 (2004)MathSciNetCrossRef

17.

Desharnais, J., Jagadeesan, R., Gupta, V., Panangaden, P.: The metric analogue of weak bisimulation for probabilistic processes. In: LICS, pp. 413–422. IEEE (2002)

18.

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). https://doi.org/10.1007/11681878_14CrossRef

19.

Etessami, K., Yannakakis, M.: On the complexity of Nash equilibria and other fixed points. SIAM J. Comput. 39(6), 2531–2597 (2010)MathSciNetCrossRef

20.

Grötschel, M., Lovász, L., Schrijver, A.: Geometric Algorithms and Combinatorial Optimization, Algorithms and Combinatorics, vol. 2. Springer, Berlin (1988)CrossRef

21.

Kantorovich, L.V.: On the translocation of masses. Doklady Akademii Nauk SSSR 37(7–8), 227–229 (1942)MathSciNet

22.

Kiefer, S.: On computing the total variation distance of hidden Markov models. In: ICALP, pp. 130:1–130:13 (2018)

23.

Larsen, K.G., Skou, A.: Bisimulation through probabilistic testing. Inf. Comput. 94(1), 1–28 (1991)MathSciNetCrossRef

24.

Schaefer, M., Stefankovic, D.: Fixed points, Nash equilibria, and the existential theory of the reals. Theory Comput. Syst. 60(2), 172–193 (2017)MathSciNetCrossRef

25.

Sontag, E.D.: Real addition and the polynomial hierarchy. IPL 20(3), 115–120 (1985)MathSciNetCrossRef

26.

Tang, Q., van Breugel, F.: Computing probabilistic bisimilarity distances via policy iteration. In: CONCUR, pp. 22:1–22:15. Leibniz-Zentrum (2016)

27.

Tarski, A.: A lattice-theoretical fixpoint theorem and its applications. Pac. J. Math. 5(2), 285–309 (1955)MathSciNetCrossRef

28.

Tschantz, M.C., Kaynar, D., Datta, A.: Formal verification of differential privacy for interactive systems. ENTCS 276, 61–79 (2011)MathSciNetMATH

29.

Vadhan, S.P.: The complexity of differential privacy. In: Tutorials on the Foundations of Cryptography, pp. 347–450. Springer, Berlin (2017)CrossRef

30.

Xu, L.: Formal verification of differential privacy in concurrent systems. Ph.D. thesis, Ecole Polytechnique (Palaiseau, France) (2015)

31.

Xu, L., Chatzikokolakis, K., Lin, H.: Metrics for differential privacy in concurrent systems. In: Ábrahám, E., Palamidessi, C. (eds.) FORTE 2014. LNCS, vol. 8461, pp. 199–215. Springer, Heidelberg (2014). https://doi.org/10.1007/978-3-662-43613-4_13CrossRef

Title: Bisimilarity Distances for Approximate Differential Privacy
Authors: Dmitry Chistikov
Andrzej S. Murawski
David Purser
Publisher: Springer International Publishing
Book: Automated Technology for Verification and Analysis
Print ISBN: 978-3-030-01089-8

Electronic ISBN: 978-3-030-01090-4

Copyright Year: 2018
DOI: https://doi.org/10.1007/978-3-030-01090-4_12

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner