Separating Oblivious and Adaptive Differential Privacy under Continual Observation

Computer Science > Cryptography and Security [Submitted on 11 Mar 2026 (v1), last revised 3 Apr 2026 (this version, v2)] Separating Oblivious and Adaptive Differential Privacy under Continual Observation Mark Bun, Marco Gaboardi, Connor Wagaman 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,\delta)-DP adaptive algorithm fails to be accurate after releasing output for only a constant number of time steps. Subjects: Cryptography and Security (cs.CR); Data Structures and Algorithms (cs.DS) Cite as: arXiv:2603.11029 [cs.CR]   (or arXiv:2603.11029v2 [cs.CR] for this version)   https://doi.org/10.48550/arXiv.2603.11029 Focus to learn more Submission history From: Connor Wagaman [view email] [v1] Wed, 11 Mar 2026 17:51:35 UTC (37 KB) [v2] Fri, 3 Apr 2026 00:04:26 UTC (37 KB) Access Paper: HTML (experimental) view license Current browse context: cs.CR < prev   |   next > new | recent | 2026-03 Change to browse by: cs cs.DS References & Citations NASA ADS Google Scholar Semantic Scholar Export BibTeX Citation Bookmark Bibliographic Tools Bibliographic and Citation Tools Bibliographic Explorer Toggle Bibliographic Explorer (What is the Explorer?) Connected Papers Toggle Connected Papers (What is Connected Papers?) Litmaps Toggle Litmaps (What is Litmaps?) scite.ai Toggle scite Smart Citations (What are Smart Citations?) Code, Data, Media Demos Related Papers About arXivLabs Which authors of this paper are endorsers? | Disable MathJax (What is MathJax?)