The Library
The complexity of verifying loop-free programs as differentially private
Tools
Tools
Tools
Gaboardi, Marco, Nissim, Kobbi and Purser, David (2020) The complexity of verifying loop-free programs as differentially private. In: 47th International Colloquium on Automata, Languages and Programming, 08-11 Jul 2020 doi:10.4230/LIPIcs.ICALP.2020.129
|
PDF
WRAP-complexity-verifying-loop-free-programs-differentially-private-Purser-2020.pdf - Published Version - Requires a PDF viewer. Available under License Creative Commons Attribution. Download (703Kb) | Preview |
|
![[img]](http://wrap.warwick.ac.uk/style/images/fileicons/application_pdf.png) |
PDF
WRAP-complexity-verifying-loop-free-programs-differentially-private-Purser-2020.pdf - Accepted Version Embargoed item. Restricted access to Repository staff only - Requires a PDF viewer. Download (641Kb) |
Official URL: https://doi.org/10.4230/LIPIcs.ICALP.2020.129
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 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.
| Item Type: | Conference Item (Paper) | |||||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software | |||||||||
| Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | |||||||||
| Library of Congress Subject Headings (LCSH): | Computer security, Computer networks -- Security measures, Computer software -- Verification, Stochastic programming, Computational complexity | |||||||||
| Publisher: | LIPIcs–Leibniz International Proceedings in Informatics | |||||||||
| Official Date: | 29 June 2020 | |||||||||
| Dates: |
|
|||||||||
| DOI: | 10.4230/LIPIcs.ICALP.2020.129 | |||||||||
| Status: | Not Peer Reviewed | |||||||||
| Publication Status: | Published | |||||||||
| Access rights to Published version: | Open Access (Creative Commons) | |||||||||
| Date of first compliant deposit: | 13 May 2020 | |||||||||
| Date of first compliant Open Access: | 16 July 2020 | |||||||||
| RIOXX Funder/Project Grant: |
|
|||||||||
| Conference Paper Type: | Paper | |||||||||
| Title of Event: | 47th International Colloquium on Automata, Languages and Programming | |||||||||
| Type of Event: | Conference | |||||||||
| Date(s) of Event: | 08-11 Jul 2020 | |||||||||
| Related URLs: | ||||||||||
| Open Access Version: |
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |
Downloads
Downloads per month over past year
