Ignoring computational constraints, this problem can be solved even when $X$ and $Q$ are exponentially large and $n$ is just a small polynomial; however, all algorithms with remotely similar guarantees run in exponential time. There have been several results showing that, under the strong assumption of indistinguishability obfuscation (iO), no efficient differentially private algorithm exists when $X$ and $Q$ can be exponentially large. However, there are no strong separations between information-theoretic and computationally efficient differentially private algorithms under any standard complexity assumption.
In this work we show that, if one-way functions exist, there is no general purpose differentially private algorithm that works when $X$ and $Q$ are exponentially large, and $n$ is an arbitrary polynomial. In fact, we show that this result holds even if $X$ is just subexponentially large (assuming only polynomially-hard one-way functions). This result solves an open problem posed by Vadhan in his recent survey.
Category / Keywords: differential privacy, one-way functions, traitor tracing, functional encryption Date: received 13 Nov 2017, last revised 30 May 2018 Contact author: luke at cs columbia edu Available format(s): PDF | BibTeX Citation Note: Minor typo fixes Version: 20180531:005036 (All versions of this report) Short URL: ia.cr/2017/1107 Discussion forum: Show discussion | Start new discussion