The Library
Asymmetric distances for approximate differential privacy
Tools
Chistikov, Dmitry, Murawski, Andrzej S. and Purser, David (2019) Asymmetric distances for approximate differential privacy. In: 30th International Conference on Concurrency Theory (CONCUR 2019), Amsterdam, Netherlands, 27-30 Aug 2019, 140 pp. 1-17. ISBN 9783959771214. doi:10.4230/LIPIcs.CONCUR.2019.10 ISSN 1868-8969.
|
PDF
WRAP-asymmetric-distances-approximate-differential-privacy-Purser-2019.pdf - Accepted Version - Requires a PDF viewer. Available under License Creative Commons Attribution 4.0. Download (1824Kb) | Preview |
Official URL: https://doi.org/10.4230/LIPIcs.CONCUR.2019.10
Abstract
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.
Item Type: | Conference Item (Paper) | ||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software | ||||||||||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science Faculty of Science, Engineering and Medicine > Science > Mathematics |
||||||||||||
Library of Congress Subject Headings (LCSH): | Bisimulation, Markov processes, Privacy -- Mathematical models, Computer systems -- Verification | ||||||||||||
Publisher: | Schloss Dagstuhl – Leibniz-Zentrum für Informatik | ||||||||||||
ISBN: | 9783959771214 | ||||||||||||
ISSN: | 1868-8969 | ||||||||||||
Official Date: | 20 August 2019 | ||||||||||||
Dates: |
|
||||||||||||
Volume: | 140 | ||||||||||||
Page Range: | pp. 1-17 | ||||||||||||
Article Number: | 10 | ||||||||||||
DOI: | 10.4230/LIPIcs.CONCUR.2019.10 | ||||||||||||
Status: | Peer Reviewed | ||||||||||||
Publication Status: | Published | ||||||||||||
Access rights to Published version: | Open Access (Creative Commons) | ||||||||||||
Description: | LIPIcs–Leibniz International Proceedings in Informatics series |
||||||||||||
Date of first compliant deposit: | 5 July 2019 | ||||||||||||
Date of first compliant Open Access: | 21 August 2019 | ||||||||||||
RIOXX Funder/Project Grant: |
|
||||||||||||
Conference Paper Type: | Paper | ||||||||||||
Title of Event: | 30th International Conference on Concurrency Theory (CONCUR 2019) | ||||||||||||
Type of Event: | Conference | ||||||||||||
Location of Event: | Amsterdam, Netherlands | ||||||||||||
Date(s) of Event: | 27-30 Aug 2019 | ||||||||||||
Related URLs: |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |
Downloads
Downloads per month over past year