A Learning Theory Approach to Non-Interactive Database Privacy

Avrim Blum, Katrina Ligett, Aaron Roth

[PDF]

We consider the problem of non-interactive database privacy: how can we release useful information about a database while preserving differential privacy? Motivated by learning theory, we circumvent existing lower bounds by considering usefulness relative to a concept class. We say that a sanitized database is useful with respect to a class of functions C, if every query in C gives approximately the same answer whether evaluated on the sanitized database or the real database. We show that it is possible to release a privacy-preserving database that is useful for any concept class with polynomial VC-dimension. Our proof, however, does not necessarily yield an efficient algorithm. We then give efficient algorithms to privately release databases useful for axis-aligned rectangles of constant dimension, and halfspaces (according to a relaxed definition of usefulness). The general question of computational efficiency is left open.