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.
Anonymous Traitor Tracing: How to Embed Arbitrary Information in a Key
In a traitor tracing scheme, each user is given a different decryption key. A content distributor can encrypt digital content using a public encryption key
and each user in the system can decrypt it using her decryption key. Even if a coalition of users combines their decryption keys and constructs some "pirate decoder"
that is capable of decrypting the content, there is a public tracing algorithm that is guaranteed to recover the identity of at least one of the users in the coalition
given black-box access to such decoder.
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: