A Logical Characterization of Differential Privacy - Laboratoire d'informatique de l'X (LIX) Accéder directement au contenu
Article Dans Une Revue Science of Computer Programming Année : 2020

A Logical Characterization of Differential Privacy

Résumé

Differential privacy is a formal definition of privacy ensuring that sensitive information relative to individuals cannot be inferred by querying a database. In this paper, we exploit a modeling of this framework via labeled Markov Chains (LMCs) to provide a logical characterization of differential privacy: we consider a probabilistic variant of the Hennessy-Milner logic and we define a syntactical distance on for-mulae in it measuring their syntactic disparities. Then, we define a trace distance on LMCs in terms of the syntactic distance between the sets of formulae satisfied by them. We prove that such distance corresponds to the level of privacy of the LMCs. Moreover, we use the distance on for-mulae to define a real-valued semantics for them, from which we obtain a logical characterization of weak anonymity: the level of anonymity is measured in terms of the smallest formula distinguishing the considered LMCs. Then, we focus on bisimulation semantics on nondeterministic probabilistic processes and we provide a logical characterization of generalized bisimulation metrics, namely those defined via the generalized Kantorovich lifting. Our characterization is based on the notion of mimicking formula of a process and the syntactic distance on formulae, where the former captures the observable behavior of the corresponding process and allows us to characterize bisimilarity. We show that the generalized bisimulation distance on processes is equal to the syntactic distance on their mimicking formulae. Moreover, we use the distance on mimicking formulae to obtain bounds on differential privacy.
Fichier principal
Vignette du fichier
facs18.pdf (501.6 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-02423048 , version 1 (23-12-2019)

Identifiants

Citer

Valentina Castiglioni, Konstantinos Chatzikokolakis, Catuscia Palamidessi. A Logical Characterization of Differential Privacy. Science of Computer Programming, 2020, 188, pp.102388. ⟨10.1016/j.scico.2019.102388⟩. ⟨hal-02423048⟩
184 Consultations
216 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More