International Association for Cryptologic Research

International Association
for Cryptologic Research


Certifying Private Probabilistic Mechanisms

Zoë Ruha Bell , University of California, Berkeley
Shafi Goldwasser , University of California, Berkeley
Michael P. Kim , Cornell University
Jean-Luc Watson , University of California, Berkeley
Search ePrint
Search Google
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{}.
  title={Certifying Private Probabilistic Mechanisms},
  author={Zoë Ruha Bell and Shafi Goldwasser and Michael P. Kim and Jean-Luc Watson},