The Library
Bisimilarity distances for approximate differential privacy
Tools
Tools
Tools
Chistikov, Dmitry, Murawski, Andrzej S. and Purser, David (2018) Bisimilarity distances for approximate differential privacy. In: International Symposium on Automated Technology for Verification and Analysis 2018, Los Angeles, USA, Oct 7-10 2018. Published in: Lecture Notes in Computer Science, 11138 pp. 194-210. ISBN 9783030010898. ISSN 0302-9743. doi:10.1007/978-3-030-01090-4_12
|
PDF
WRAP-bisimilarity-distances-approximate-differential-privacy-Chistikov-2018.pdf - Accepted Version - Requires a PDF viewer. Download (706Kb) | Preview |
Official URL: https://doi.org/10.1007/978-3-030-01090-4_12
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 ∈; δ-differential privacy in the setting of labelled Markov chains. While the exact differences relevant to ∈; δ-differential privacy are not computable in this framework, we propose a computable bisimilarity distance that yields a sound technique for measuring δ, 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.
| Item Type: | Conference Item (Paper) | |||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Alternative Title: | ||||||||||||||||
| Subjects: | Q Science > QA Mathematics | |||||||||||||||
| Divisions: | Faculty of Science > Computer Science | |||||||||||||||
| Library of Congress Subject Headings (LCSH): | Bisimulation, Markov processes | |||||||||||||||
| Series Name: | Lecture Notes in Computer Science | |||||||||||||||
| Journal or Publication Title: | Lecture Notes in Computer Science | |||||||||||||||
| Publisher: | Springer | |||||||||||||||
| Place of Publication: | Cham | |||||||||||||||
| ISBN: | 9783030010898 | |||||||||||||||
| ISSN: | 0302-9743 | |||||||||||||||
| Book Title: | International Symposium on Automated Technology for Verification and Analysis ATVA 2018: Automated Technology for Verification and Analysis | |||||||||||||||
| Official Date: | 30 September 2018 | |||||||||||||||
| Dates: |
|
|||||||||||||||
| Date of first compliant deposit: | 27 July 2018 | |||||||||||||||
| Volume: | 11138 | |||||||||||||||
| Page Range: | pp. 194-210 | |||||||||||||||
| DOI: | 10.1007/978-3-030-01090-4_12 | |||||||||||||||
| Status: | Peer Reviewed | |||||||||||||||
| Publication Status: | Published | |||||||||||||||
| Publisher Statement: | This is the accepted manuscript version of the article. The final version is available online from Springer at: https://doi.org/10.1007/978-3-030-01090-4_12 | |||||||||||||||
| Access rights to Published version: | Restricted or Subscription Access | |||||||||||||||
| Copyright Holders: | © Springer Nature Switzerland AG 2018 | |||||||||||||||
| RIOXX Funder/Project Grant: |
|
|||||||||||||||
| Conference Paper Type: | Paper | |||||||||||||||
| Title of Event: | International Symposium on Automated Technology for Verification and Analysis 2018 | |||||||||||||||
| Type of Event: | Conference | |||||||||||||||
| Location of Event: | Los Angeles, USA | |||||||||||||||
| Date(s) of Event: | Oct 7-10 2018 |
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |
Downloads
Downloads per month over past year
