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, 1d) 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