Paper Info
Title
Verifiable differential privacy.
Abstract
Working with sensitive data is often a balancing act between privacy and integrity concerns. Consider, for instance, a medical researcher who has analyzed a patient database to judge the effectiveness of a new treatment and would now like to publish her findings. On the one hand, the patients may be concerned that the researcher's results contain too much information and accidentally leak some private fact about themselves; on the other hand, the readers of the published study may be concerned that the results contain too little information, limiting their ability to detect errors in the calculations or flaws in the methodology. This paper presents VerDP, a system for private data analysis that provides both strong integrity and strong differential privacy guarantees. VerDP accepts queries that are written in a special query language, and it processes them only if a) it can certify them as differentially private, and if b) it can prove the integrity of the result in zero knowledge. Our experimental evaluation shows that VerDP can successfully process several different queries from the differential privacy literature, and that the cost of generating and verifying the proofs is practical: for example, a histogram query over a 63,488-entry data set resulted in a 20 kB proof that took 32 EC2 instances less than two hours to generate, and that could be verified on a single machine in about one second.
Year
DOI
Venue
2015
10.1145/2741948.2741978
EuroSys
Keywords
Field
DocType
internet of things,wireless sensor networks
Publication,Query language,Differential privacy,Computer science,Computer security,Verifiable secret sharing,Mathematical proof,If and only if,Zero-knowledge proof,Wireless sensor network
Conference
Citations 
PageRank 
References 
0
0.34
35
Authors
4
Name
Order
Citations
PageRank
Arjun Narayan11997.10
Ariel Feldman200.34
Antonis Papadimitriou3253.52
Andreas Haeberlen4150597.07