Paper 2023/171

On Differential Privacy and Adaptive Data Analysis with Bounded Space

Itai Dinur, Ben-Gurion University of the Negev
Uri Stemmer, Tel Aviv University, Google Research
David P. Woodruff, Carnegie Mellon University
Samson Zhou, UC Berkeley, Rice University

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.

Available format(s)
Publication info
A major revision of an IACR publication in EUROCRYPT 2023
differential privacyadaptive data analysisspace complexityleakage-resilient cryptography
Contact author(s)
dinuri @ bgu ac il
2023-02-15: approved
2023-02-11: received
See all versions
Short URL
Creative Commons Attribution


      author = {Itai Dinur and Uri Stemmer and David P. Woodruff and Samson Zhou},
      title = {On Differential Privacy and Adaptive Data Analysis with Bounded Space},
      howpublished = {Cryptology ePrint Archive, Paper 2023/171},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.