文章基本信息

标题：Asymmetric Distances for Approximate Differential Privacy
本地全文：下载
作者：Dmitry Chistikov ; Andrzej S. Murawski ; David Purser 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2019
卷号：140
页码：1-17
DOI：10.4230/LIPIcs.CONCUR.2019.10
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：Bisimilarity distances; Differential privacy; Labelled Markov chains