Separating Oblivious and Adaptive Differential Privacy under Continual Observation
2026-03-11 • Cryptography and Security
Cryptography and SecurityData Structures and Algorithms
AI summaryⓘ
The authors address a question about privacy when data comes in over time and outputs are shared continuously. They distinguish two scenarios: one where the data stream is fixed beforehand (oblivious) and another where the data can change based on previous outputs (adaptive). They show a clear difference between these settings using a specific problem, proving that in the oblivious case, privacy and accuracy can be maintained for a very long time, but in the adaptive case, accuracy breaks down quickly. Their results build on previous work about correlated data queries.
differential privacycontinual observationstreaming algorithmsoblivious settingadaptive settingprivacy guaranteescorrelated vector queriesaccuracystreaming data
Authors
Mark Bun, Marco Gaboardi, Connor Wagaman
Abstract
We resolve an open question of Jain, Raskhodnikova, Sivakumar, and Smith (ICML 2023) by exhibiting a problem separating differential privacy under continual observation in the oblivious and adaptive settings. The continual observation (a.k.a. continual release) model formalizes privacy for streaming algorithms, where data is received over time and output is released at each time step. In the oblivious setting, privacy need only hold for data streams fixed in advance; in the adaptive setting, privacy is required even for streams that can be chosen adaptively based on the streaming algorithm's output. We describe the first explicit separation between the oblivious and adaptive settings. The problem showing this separation is based on the correlated vector queries problem of Bun, Steinke, and Ullman (SODA 2017). Specifically, we present an $(\varepsilon,0)$-DP algorithm for the oblivious setting that remains accurate for exponentially many time steps in the dimension of the input. On the other hand, we show that every $(\varepsilon,δ)$-DP adaptive algorithm fails to be accurate after releasing output for only a constant number of time steps.