Strong hardness of privacy from weak traitor tracing

Lucas Kowalczyk, Tal Malkin, Jonathan Ullman, Mark Zhandry

Research output: Chapter in Book/Report/Conference proceedingConference contribution

6 Scopus citations

Abstract

A central problem in differential privacy is to accurately answer a large family Q of statistical queries over a data universe X. A statistical query on a dataset D ∈ X n asks “what fraction of the elements of D satisfy a given predicate p on X?” Ignoring computational constraints, it is possible to accurately answer exponentially many queries on an exponential size universe while satisfying differential privacy (Blum et al., STOC’08). Dwork et al. (STOC’09) and Boneh and Zhandry (CRYPTO’14) showed that if both Q and X are of polynomial size, then there is an efficient differentially private algorithm that accurately answers all the queries. They also proved that if Q and X are both exponentially large, then under a plausible assumption, no efficient algorithm exists. We show that, under the same assumption, if either the number of queries or the data universe is of exponential size, then there is no differentially private algorithm that answers all the queries. Specifically, we prove that if one-way functions and indistinguishability obfuscation exist, then: 1. For every n, there is a family Q of Õ(n 7 ) queries on a data universe X of size 2 d such that no poly(n, d) time differentially private algorithm takes a dataset D ∈ X n and outputs accurate answers to every query in Q. 2. For every n, there is a family Q of 2 d queries on a data universe X of size Õ(n 7 ) such that no poly(n, d) time differentially private algorithm takes a dataset D ∈ X n and outputs accurate answers to every query in Q. In both cases, the result is nearly quantitatively tight, since there is an efficient differentially private algorithm that answers Ω (n 2 ) queries on an exponential size data universe, and one that answers exponentially many queries on a data universe of size Ω(n 2 ). Our proofs build on the connection between hardness of differential privacy and traitor-tracing schemes (Dwork et al., STOC’09; Ullman, STOC’13). We prove our hardness result for a polynomial size query set (resp., data universe) by showing that they follow from the existence of a special type of traitor-tracing scheme with very short ciphertexts (resp., secret keys), but very weak security guarantees, and then constructing such a scheme.

Original languageEnglish (US)
Title of host publicationTheory of Cryptography - 14th International Conference, TCC 2016-B, Proceedings
EditorsAdam Smith, Martin Hirt
PublisherSpringer Verlag
Pages659-689
Number of pages31
ISBN (Print)9783662536407
DOIs
StatePublished - Jan 1 2016
Event14th International Conference on Theory of Cryptography, TCC 2016-B - Beijing, China
Duration: Oct 31 2016Nov 3 2016

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume9985 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other14th International Conference on Theory of Cryptography, TCC 2016-B
CountryChina
CityBeijing
Period10/31/1611/3/16

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Strong hardness of privacy from weak traitor tracing'. Together they form a unique fingerprint.

Cite this