CryptoDB
Certifying Private Probabilistic Mechanisms
| Authors: |
|
|---|---|
| Download: | |
| Conference: | CRYPTO 2024 |
| Abstract: | In past years, entire research communities have arisen to address concerns of privacy and fairness in data analysis. At present, however, the public must trust that institutions will re-implement algorithms voluntarily to account for these social concerns. Due to additional cost, widespread adoption is unlikely without effective legal enforcement. A technical challenge for enforcement is that the methods proposed are often \emph{probabilistic mechanisms}, whose output must be drawn according to precise, and sometimes secret, distributions. The Differential Privacy (DP) case is illustrative: if a cheating curator answers queries according to an overly-accurate mechanism, privacy violations could go undetected. This raises our central question: \textit{Can we efficiently certify the output of a probabilistic mechanism enacted by an untrusted party?} To this end: \begin{enumerate} \item We introduce two new notions: {\it Certified Probabilistic Mechanisms} (CPM) and \emph{Random Variable Commitment Schemes} (RVCS). A CPM is an interactive protocol that forces a prover to enact a given probabilistic mechanism or be caught; importantly, the interaction does not reveal the mechanism's secret parameters. An RVCS---a key primitive for constructing CPMs---is a commitment scheme where the verifier is convinced that the commitment is to an RV sampled according to an agreed-upon distribution, but learns nothing else. \item We instantiate the general notion of CPM for the special case of Certifying DP. We build a lightweight, doubly-efficent interactive proof system to certify arbitrary-predicate counting queries released via the DP Binomial mechanism. The construction relies on a commitment scheme with perfect hiding and additive homomorphic properties that can be used to release a broad class of queries about a committed database, constructed on top of Pedersen commitments. \item Finally, we demonstrate the immediate feasibility of Certified DP via a highly-efficient and scalable prototype implementation to answer counting queries of arbitrary predicates. The mechanism is composed of an offline and online stage, where the online phase allows for non-interactive certification of queries. For example, we show that CDP queries over a US Census Public Use Microdata Sample (PUMS)~\cite{census-pums} ($n=7000$) can be completed in only 1.6~ms and verified in just \emph{38~$\mu$s}. Our implementation is available in open source at \url{https://github.com/jlwatson/certified-dp}. |
BibTeX
@inproceedings{crypto-2024-34351,
title={Certifying Private Probabilistic Mechanisms},
publisher={Springer-Verlag},
author={Zoë Ruha Bell and Shafi Goldwasser and Michael P. Kim and Jean-Luc Watson},
year=2024
}