License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2020.129
URN: urn:nbn:de:0030-drops-125362
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/12536/
Gaboardi, Marco ;
Nissim, Kobbi ;
Purser, David
The Complexity of Verifying Loop-Free Programs as Differentially Private
Abstract
We study the problem of verifying differential privacy for loop-free programs with probabilistic choice. Programs in this class can be seen as randomized Boolean circuits, which we will use as a formal model to answer two different questions: first, deciding whether a program satisfies a prescribed level of privacy; second, approximating the privacy parameters a program realizes. We show that the problem of deciding whether a program satisfies ε-differential privacy is coNP^#P-complete. In fact, this is the case when either the input domain or the output range of the program is large. Further, we show that deciding whether a program is (ε,δ)-differentially private is coNP^#P-hard, and in coNP^#P for small output domains, but always in coNP^{#P^#P}. Finally, we show that the problem of approximating the level of differential privacy is both NP-hard and coNP-hard. These results complement previous results by Murtagh and Vadhan [Jack Murtagh and Salil P. Vadhan, 2016] showing that deciding the optimal composition of differentially private components is #P-complete, and that approximating the optimal composition of differentially private components is in P.
BibTeX - Entry
@InProceedings{gaboardi_et_al:LIPIcs:2020:12536,
author = {Marco Gaboardi and Kobbi Nissim and David Purser},
title = {{The Complexity of Verifying Loop-Free Programs as Differentially Private}},
booktitle = {47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)},
pages = {129:1--129:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-138-2},
ISSN = {1868-8969},
year = {2020},
volume = {168},
editor = {Artur Czumaj and Anuj Dawar and Emanuela Merelli},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/12536},
URN = {urn:nbn:de:0030-drops-125362},
doi = {10.4230/LIPIcs.ICALP.2020.129},
annote = {Keywords: differential privacy, program verification, probabilistic programs}
}
|
Keywords: |
|
differential privacy, program verification, probabilistic programs |
|
Collection: |
|
47th International Colloquium on Automata, Languages, and Programming (ICALP 2020) |
|
Issue Date: |
|
2020 |
|
Date of publication: |
|
29.06.2020 |
