Skip to content Skip to navigation
University of Warwick
  • Study
  • |
  • Research
  • |
  • Business
  • |
  • Alumni
  • |
  • News
  • |
  • About

University of Warwick
Publications service & WRAP

Highlight your research

  • WRAP
    • Home
    • Search WRAP
    • Browse by Warwick Author
    • Browse WRAP by Year
    • Browse WRAP by Subject
    • Browse WRAP by Department
    • Browse WRAP by Funder
    • Browse Theses by Department
  • Publications Service
    • Home
    • Search Publications Service
    • Browse by Warwick Author
    • Browse Publications service by Year
    • Browse Publications service by Subject
    • Browse Publications service by Department
    • Browse Publications service by Funder
  • Help & Advice
University of Warwick

The Library

  • Login
  • Admin

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. doi:10.1007/978-3-030-01090-4_12 ISSN 0302-9743.

[img]
Preview
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

Request Changes to record.

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, Engineering and Medicine > 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:
DateEvent
30 September 2018Available
27 June 2018Accepted
Volume: 11138
Page Range: pp. 194-210
DOI: 10.1007/978-3-030-01090-4_12
Status: Peer Reviewed
Publication Status: Published
Reuse Statement (publisher, data, author rights): 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
Date of first compliant deposit: 27 July 2018
Date of first compliant Open Access: 15 February 2019
RIOXX Funder/Project Grant:
Project/Grant IDRIOXX Funder NameFunder ID
EP/L016400/1[EPSRC] Engineering and Physical Sciences Research Councilhttp://dx.doi.org/10.13039/501100000266
Doctoral Training in Urban Science[EPSRC] Engineering and Physical Sciences Research Councilhttp://dx.doi.org/10.13039/501100000266
IE161701[RS] Royal Societyhttp://dx.doi.org/10.13039/501100000288
UNSPECIFIEDLeverhulme Trusthttp://dx.doi.org/10.13039/501100000275
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 View Item

Downloads

Downloads per month over past year

View more statistics

twitter

Email us: wrap@warwick.ac.uk
Contact Details
About Us