On the complexity of verifying differential privacy
David Purser · Warwick Research Archive Portal (University of Warwick) · 2020
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).