Strong Hardness of Privacy from Weak Traitor Tracing
Despite much study, the computational complexity of differential privacy remains poorly understood. In this paper we consider the computational complexity of
accurately answering a family Q of statistical queries over a data universe X under differential privacy. A statistical query
on a dataset D∈Xn asks "what fraction of the elements of D satisfy a given predicate p on X?" 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, and if both Q and X are exponential size, then under a plausible assumption, no efficient algorithm exists.
Order-Revealing Encryption and the Hardness of Private Learning
An order-revealing encryption scheme gives a public procedure by which two ciphertexts can be compared to reveal the ordering of their underlying
plaintexts. We show how to use order-revealing encryption to separate computationally efficient PAC learning from efficient (ε,δ)-differentially
private PAC learning. That is, we construct a concept class that is efficiently PAC learnable, but for which every efficient learner fails to be differentially
private. This answers a question of Kasiviswanathan et al. (FOCS `08, SIAM J. Comput. `11).
Multiparty Key Exchange, Efficient Traitor Tracing, and More from Indistinguishability Obfuscation
[PDF]  [ePrint]  [slides]
In this work, we show how to use indistinguishability obfuscation (iO) to build multiparty key exchange,
efficient broadcast encryption, and efficient traitor tracing. Our schemes enjoy several interesting
properties that have not been achievable before: