Fingerprinting codes and the price of approximate differential privacy

• DOI: 10.1145/2591796.2591877
• Publication Date: 2015-10-01T12:01:58Z
• Authors: Mark Bun; Jonathan Ullman; Salil Vadhan
• Keywords: Differential Privacy; Fraction (chemistry); Sample (material); Sample complexity

We show new lower bounds on the sample complexity of (ε, δ)-differentially private algorithms that accurately answer large sets counting queries. A query a database D ∈ ({0, 1}d)n has form "What fraction individual records in satisfy property q?" order to an arbitrary set Q » nd queries within error ±α it is necessary