Hardness of Non-Interactive Differential Privacy from One-Way Functions.
Lucas Kowalczyk, Tal Malkin, Jonathan Ullman, Daniel Wichs · IACR Cryptology ePrint Archive · 2017
A central challenge in differential privacy is to design computationally efficient non-interactive algorithms that can answer large numbers of statistical queries on a sensitive dataset. That is, we would like to design a differentially private algorithm that takes a dataset \(D \in X^n\) consisting of some small number of elements n from some large data universe X, and efficiently outputs a summary that allows a user to efficiently obtain an answer to any query in some large family Q.