On Differential Privacy and Adaptive Data Analysis with Bounded Space
This work addresses foundational issues in privacy-preserving and adaptive data analysis for researchers and practitioners, revealing new space limitations that are incremental but important.
The paper tackles the space complexity of differential privacy and adaptive data analysis, showing that under cryptographic assumptions, a problem requires exponentially more space for private algorithms compared to non-private ones, and that previous lower bounds in adaptive data analysis stem from a space bottleneck rather than a sampling bottleneck.
We study the space complexity of the two related fields of differential privacy and adaptive data analysis. Specifically, (1) Under standard cryptographic assumptions, we show that there exists a problem P that requires exponentially more space to be solved efficiently with differential privacy, compared to the space needed without privacy. To the best of our knowledge, this is the first separation between the space complexity of private and non-private algorithms. (2) The line of work on adaptive data analysis focuses on understanding the number of samples needed for answering a sequence of adaptive queries. We revisit previous lower bounds at a foundational level, and show that they are a consequence of a space bottleneck rather than a sampling bottleneck. To obtain our results, we define and construct an encryption scheme with multiple keys that is built to withstand a limited amount of key leakage in a very particular way.