Strong Hardness of Privacy from Weak Traitor Tracing

Lucas Kowalczyk, Tal Malkin, Jonathan Ullman +1

Despite much study, the computational complexity of differential privacy remains poorly understood. In this paper we consider the computational complexity of accurately answering a…