Fingerprinting codes and the price of approximate differential privacy

We show new lower bounds on the sample complexity of ( ε, δ )-differentially private algorithms that accurately answer large sets of counting queries. A counting query on a database D ∈ ({0, 1} d ) n has the form "What fraction of the individual records in the database satisfy the property q ?" We show that in order to answer an arbitrary set Q of » nd counting queries on D to within error ± α it is necessary that [EQUATION] This bound is optimal up to poly-logarithmic factors, as demonstrated by the Private Multiplicative Weights algorithm (Hardt and Rothblum, FOCS'10). It is also the first to show that the sample complexity required for ( ε, δ )-differential privacy is asymptotically larger than what is required merely for accuracy, which is O (log | Q |/ α 2 ). In addition, we show that our lower bound holds for the specific case of k -way marginal queries (where | Q | = 2 k ( d/k )) when α is a constant. Our results rely on the existence of short fingerprinting codes (Boneh and Shaw, CRYPTO'95; Tardos, STOC'03), which we show are closely connected to the sample complexity of differentially private data release. We also give a new method for combining certain types of sample complexity lower bounds into stronger lower bounds.

Authors

• Mark Bun
• Jonathan R. Ullman
• Salil P. Vadhan

Keywords

• differential privacy
• fingerprinting codes