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 n ≥ Ω̃ d log |Q| α2ε This bound is optimal up to poly-logarithmic factors, as demonstrated by the Private Multi-plicative Weights algorithm (Hardt and Rothblum, FOCS’10). In particular, our lower bound is the first to show that the sample complexity required for accuracy and (ε, δ)-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 | = 2k(dk)) 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 differen-tially private data release. We also give a new method for combining certain types of sample complexity lower bounds into stronger lower bounds