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

PDF
WRAP_Theses_Purser_2020.pdf  Submitted Version  Requires a PDF viewer. Download (2098Kb)  Preview 
Official URL: http://webcat.warwick.ac.uk/record=b3520159
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 overestimate 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 bigO 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 coNPcomplete). On chains with bounded language (that is, when there exists w1;…..;wm EΣ 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 overestimate exp(ε) can be computed in PSPACE.
In the setting of randomised circuits, the complexity of verifying pure differential privacy is fully captured as coNP#Pcomplete; 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#Pcomplete when the number of output bits is small (polylogarithmic) relative to the total size of the circuit. Further, each parameter cannot be approximated given the other in polynomial time (assuming P 6= 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: 


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:  
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
Downloads per month over past year