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.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
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\).
- 2.
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.
References
Albarghouthi, A., Hsu, J.: Synthesizing coupling proofs of differential privacy. Proc. ACM Program. Lang. 2, 58:1–58:30 (2018)
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_1
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_27
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_10
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_23
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_10
Cardinal, J.: Computational geometry column 62. SIGACT News 46(4), 69–78 (2015)
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_4
Chaum, D.: The dining cryptographers problem: Unconditional sender and recipient untraceability. J. Cryptol. 1(1), 65–75 (1988)
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_29
Deng, Y., Du, W.: The Kantorovich metric in computer science: a brief survey. Electron Notes Theor. Comput. Sci. 253(3), 73–82 (2009)
Desharnais, J., Gupta, V., Jagadeesan, R., Panangaden, P.: Metrics for labelled Markov processes. Theor. Comput. Sci. 318(3), 323–354 (2004)
Desharnais, J., Jagadeesan, R., Gupta, V., Panangaden, P.: The metric analogue of weak bisimulation for probabilistic processes. In: LICS, pp. 413–422. IEEE (2002)
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_14
Etessami, K., Yannakakis, M.: On the complexity of Nash equilibria and other fixed points. SIAM J. Comput. 39(6), 2531–2597 (2010)
Grötschel, M., Lovász, L., Schrijver, A.: Geometric Algorithms and Combinatorial Optimization, Algorithms and Combinatorics, vol. 2. Springer, Berlin (1988)
Kantorovich, L.V.: On the translocation of masses. Doklady Akademii Nauk SSSR 37(7–8), 227–229 (1942)
Kiefer, S.: On computing the total variation distance of hidden Markov models. In: ICALP, pp. 130:1–130:13 (2018)
Larsen, K.G., Skou, A.: Bisimulation through probabilistic testing. Inf. Comput. 94(1), 1–28 (1991)
Schaefer, M., Stefankovic, D.: Fixed points, Nash equilibria, and the existential theory of the reals. Theory Comput. Syst. 60(2), 172–193 (2017)
Sontag, E.D.: Real addition and the polynomial hierarchy. IPL 20(3), 115–120 (1985)
Tang, Q., van Breugel, F.: Computing probabilistic bisimilarity distances via policy iteration. In: CONCUR, pp. 22:1–22:15. Leibniz-Zentrum (2016)
Tarski, A.: A lattice-theoretical fixpoint theorem and its applications. Pac. J. Math. 5(2), 285–309 (1955)
Tschantz, M.C., Kaynar, D., Datta, A.: Formal verification of differential privacy for interactive systems. ENTCS 276, 61–79 (2011)
Vadhan, S.P.: The complexity of differential privacy. In: Tutorials on the Foundations of Cryptography, pp. 347–450. Springer, Berlin (2017)
Xu, L.: Formal verification of differential privacy in concurrent systems. Ph.D. thesis, Ecole Polytechnique (Palaiseau, France) (2015)
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_13
Acknowledgment
David Purser gratefully acknowledges funding by the UK Engineering and Physical Sciences Research Council (EP/L016400/1), the EPSRC Centre for Doctoral Training in Urban Science. Andrzej Murawski is supported by a Royal Society Leverhulme Trust Senior Research Fellowship and the International Exchanges Scheme (IE161701).
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2018 Springer Nature Switzerland AG
About this paper
Cite this paper
Chistikov, D., Murawski, A.S., Purser, D. (2018). Bisimilarity Distances for Approximate Differential Privacy. In: Lahiri, S., Wang, C. (eds) Automated Technology for Verification and Analysis. ATVA 2018. Lecture Notes in Computer Science(), vol 11138. Springer, Cham. https://doi.org/10.1007/978-3-030-01090-4_12
Download citation
DOI: https://doi.org/10.1007/978-3-030-01090-4_12
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-01089-8
Online ISBN: 978-3-030-01090-4
eBook Packages: Computer ScienceComputer Science (R0)