# Strong Hardness of Privacy from Weak Traitor Tracing

## Author(s): Kowalczyk, Lucas; Malkin, Tal; Ullman, Jonathan; Zhandry, Mark

DownloadTo refer to this page use:

`http://arks.princeton.edu/ark:/88435/pr1954c`

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 π·βππ 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 πΜ (π7) queries on a data universe X of size 2π such that no poly(π,π) time differentially private algorithm takes a dataset π·βππ and outputs accurate answers to every query in Q. 2. For every n, there is a family Q of 2π queries on a data universe X of size πΜ (π7) such that no poly(π,π) time differentially private algorithm takes a dataset π·βππ 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 πΊΜ (π2) queries on an exponential size data universe, and one that answers exponentially many queries on a data universe of size πΊΜ (π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. |

Publication Date: | 2016 |

Citation: | Kowalczyk, Lucas, Tal Malkin, Jonathan Ullman, and Mark Zhandry. "Strong Hardness of Privacy from Weak Traitor Tracing." In Theory of Cryptography Conference (2016): pp. 659-689. doi:10.1007/978-3-662-53641-4_25 |

DOI: | 10.1007/978-3-662-53641-4_25 |

ISSN: | 0302-9743 |

EISSN: | 1611-3349 |

Pages: | 659 - 689 |

Type of Material: | Conference Article |

Journal/Proceeding Title: | Theory of Cryptography Conference |

Version: | Author's manuscript |

Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.