Zoë Bell
University of California, Berkeley

Shafi Goldwasser
University of California, Berkeley

Michael P. Kim
Cornell University

Jean-Luc Watson
University of California, Berkeley

Keywords: proof systems, commitment schemes, differential privacy

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 probabilistic mechanisms, whose output must be drawn according to precise, and sometimes secret, distributions. The Differential Privacy (DP) case is particularly illustrative: a cheating curator could answer queries according to an overly-accurate mechanism, and privacy violations could go undetected. The need for effective enforcement raises the central question of our paper: Can we efficiently certify the output of a probabilistic mechanism enacted by an untrusted party? To this end:

1. We introduce two new notions: Certified Probabilistic Mechanisms (CPM) and 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 secret parameters of the mechanism. 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.

2. 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 functional commitment scheme with perfect hiding and additive homomorphic properties that we construct on top of Pedersen commitments.

3. 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 noninteractive certification of queries. For example, we show that CDP queries over a US Census Public Use Microdata Sample (PUMS) [22] (n = 7000) can be completed in only 1.6 ms and verified in just 38 µs. Our implementation is available in open source at https://anonymous.4open.science/r/certified-dp-174.