Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published April 2013 | public
Journal Article

A Learning Theory Approach to Noninteractive Database Privacy

Abstract

In this article, we demonstrate that, ignoring computational constraints, it is possible to release synthetic databases that are useful for accurately answering large classes of queries while preserving differential privacy. Specifically, we give a mechanism that privately releases synthetic data useful for answering a class of queries over a discrete domain with error that grows as a function of the size of the smallest net approximately representing the answers to that class of queries. We show that this in particular implies a mechanism for counting queries that gives error guarantees that grow only with the VC-dimension of the class of queries, which itself grows at most logarithmically with the size of the query class. We also show that it is not possible to release even simple classes of queries (such as intervals and their generalizations) over continuous domains with worst-case utility guarantees while preserving differential privacy. In response to this, we consider a relaxation of the utility guarantee and give a privacy preserving polynomial time algorithm that for any halfspace query will provide an answer that is accurate for some small perturbation of the query. This algorithm does not release synthetic data, but instead another data structure capable of representing an answer for each query. We also give an efficient algorithm for releasing synthetic data for the class of interval queries and axis-aligned rectangles of constant dimension over discrete domains.

Additional Information

© 2013 ACM. Received September 2011; revised July 2012; accepted January 2013. The work of A. Blum was supported in part by the National Science Foundation under grants CCF-0514922 and CCF-0830540. The work of K. Ligett was supported in part by an NSF Grasuate Research Fellowship, an NSF Computing Innovation Fellowship (NSF Award CCF-0937060), an NSF Mathematical Sciences Postdoctoral Fellowship (NSF Award DMS-1004416), NSF CCF-0910940, and the Charles Lee Powell Foundation. The work of A. Roth was supported in part by an NSF Graduate Research Fellowship, an NSF CAREER award, and NSF grants CCF-1101389 and CNS-1065060. We thank David Abraham, Cynthia Dwork, Shiva Kasiviswanathan, Adam Meyerson, Ryan O'Donnell, Sofya Raskhodnikova, Amit Sahai, and Adam Smith for many useful discussions.

Additional details

Created:
August 19, 2023
Modified:
October 24, 2023