Asymmetric distances for approximate differential privacy
Differential privacy is a widely studied notion of privacy for various models of computation, based on measuring differences between probability distributions. We consider (epsilon,delta)-differential privacy in the setting of labelled Markov chains. For a given epsilon, the parameter delta can be c...
| Main Authors: | , , |
|---|---|
| Format: | Conference item |
| Published: |
Schloss Dagstuhl - Leibniz-Zentrum für Informatik
2019
|
| _version_ | 1797093100373409792 |
|---|---|
| author | Chistikov, D Murawski, A Purser, D |
| author_facet | Chistikov, D Murawski, A Purser, D |
| author_sort | Chistikov, D |
| collection | OXFORD |
| description | Differential privacy is a widely studied notion of privacy for various models of computation, based on measuring differences between probability distributions. We consider (epsilon,delta)-differential privacy in the setting of labelled Markov chains. For a given epsilon, the parameter delta can be captured by a variant of the total variation distance, which we call lv_{alpha} (where alpha = e^{epsilon}). First we study lv_{alpha} directly, showing that it cannot be computed exactly. However, the associated approximation problem turns out to be in PSPACE and #P-hard. Next we introduce a new bisimilarity distance for bounding lv_{alpha} from above, which provides a tighter bound than previously known distances while remaining computable with the same complexity (polynomial time with an NP oracle). We also propose an alternative bound that can be computed in polynomial time. Finally, we illustrate the distances on case studies. |
| first_indexed | 2024-03-07T03:55:29Z |
| format | Conference item |
| id | oxford-uuid:c2bb8a8a-a4e8-41af-8f7b-c0f6fa981999 |
| institution | University of Oxford |
| last_indexed | 2024-03-07T03:55:29Z |
| publishDate | 2019 |
| publisher | Schloss Dagstuhl - Leibniz-Zentrum für Informatik |
| record_format | dspace |
| spelling | oxford-uuid:c2bb8a8a-a4e8-41af-8f7b-c0f6fa9819992022-03-27T06:10:59ZAsymmetric distances for approximate differential privacyConference itemhttp://purl.org/coar/resource_type/c_5794uuid:c2bb8a8a-a4e8-41af-8f7b-c0f6fa981999Symplectic Elements at OxfordSchloss Dagstuhl - Leibniz-Zentrum für Informatik2019Chistikov, DMurawski, APurser, DDifferential privacy is a widely studied notion of privacy for various models of computation, based on measuring differences between probability distributions. We consider (epsilon,delta)-differential privacy in the setting of labelled Markov chains. For a given epsilon, the parameter delta can be captured by a variant of the total variation distance, which we call lv_{alpha} (where alpha = e^{epsilon}). First we study lv_{alpha} directly, showing that it cannot be computed exactly. However, the associated approximation problem turns out to be in PSPACE and #P-hard. Next we introduce a new bisimilarity distance for bounding lv_{alpha} from above, which provides a tighter bound than previously known distances while remaining computable with the same complexity (polynomial time with an NP oracle). We also propose an alternative bound that can be computed in polynomial time. Finally, we illustrate the distances on case studies. |
| spellingShingle | Chistikov, D Murawski, A Purser, D Asymmetric distances for approximate differential privacy |
| title | Asymmetric distances for approximate differential privacy |
| title_full | Asymmetric distances for approximate differential privacy |
| title_fullStr | Asymmetric distances for approximate differential privacy |
| title_full_unstemmed | Asymmetric distances for approximate differential privacy |
| title_short | Asymmetric distances for approximate differential privacy |
| title_sort | asymmetric distances for approximate differential privacy |
| work_keys_str_mv | AT chistikovd asymmetricdistancesforapproximatedifferentialprivacy AT murawskia asymmetricdistancesforapproximatedifferentialprivacy AT purserd asymmetricdistancesforapproximatedifferentialprivacy |