Purser, David (2020) On the complexity of verifying differential privacy. PhD thesis, University of Warwick.

Preview

PDF WRAP_Theses_Purser_2020.pdf - Submitted Version - Requires a PDF viewer. Download (2098Kb) | Preview

Request Changes to record.

Abstract

This thesis contributes to the understanding of the computational complexity of verifying differential privacy. The problem is considered in two constrained, but expressive, models; namely labelled Markov chains and randomised circuits.

In the setting of labelled Markov chains (LMC) it is shown that most relevant decision problems are undecidable when considered directly and exactly. Given an LMC, and an ε, consider the problem of finding the least value of δ such that the chain is (ε, δ)-differentially private. Finding this value of δ can be expressed as a variant of the total variation distance. Whilst finding the exact value is not possible, it can be approximated, with a complexity between #P and PSPACE. Instead, bisimilarity distances are studied as over-estimate of δ, which can be computed in polynomial time assuming access to an NP oracle and a slightly weaker distance can be computed in polynomial time.

One may also wish to estimate the minimal value of ε such that the LMC is ε-differentially private. The question of whether such an ε even exists is studied through the big-O problem. That is, does there exist a constant C such that the probability of each word in one system is at most C times the probability in the other machine. However in general this problem is undecidable but can be decided on unary chains (and is coNP-complete). On chains with bounded language (that is, when there exists w_1,…..,w_m in Σ such that all words are of the form w_1^*…w_m^*) the problem is decidable subject to Schanuel’s conjecture by invoking the first order theory of the reals with exponential function. The minimal such constant C corresponds exactly to exp(ε) and approximating this value is not possible, even when the value is known to exist. A bisimilarity distance to over-estimate exp(ε) can be computed in PSPACE.

In the setting of randomised circuits, the complexity of verifying pure differential privacy is fully captured as coNP^#P-complete; formalising the intuition that differential privacy is universal quantification followed by a condition on probabilities. However verifying approximate differential privacy is between coNP^#P and coNP^#P^#P, and coNP^#P-complete when the number of output bits is small (poly-logarithmic) relative to the total size of the circuit. Further, each parameter cannot be approximated given the other in polynomial time (assuming P not equal to NP).

Item Type:	Thesis or Dissertation (PhD)
Subjects:	Q Science > QA Mathematics Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software
Library of Congress Subject Headings (LCSH):	Data protection -- Mathematics, Markov processes, Computational complexity, Computer security -- Mathematics
Official Date:	June 2020
Dates:	Date Event June 2020 UNSPECIFIED
Institution:	University of Warwick
Theses Department:	Department of Computer Science
Thesis Type:	PhD
Publication Status:	Unpublished
Supervisor(s)/Advisor:	Murawski, Andrzej S. ; Chistikov, Dmitry ; Cormode, Graham, 1977-
Format of File:	pdf
Extent:	ix, 186 leaves : illustrations
Language:	eng

Request changes or add full text files to a record

Repository staff actions (login required)

View Item

Downloads