Edit-Neighboring Data Streams and Privacy under Continual Observation

Differential privacy under Continual Observation (CO) quantifies the loss in privacy that occurs when outputs generated using a stream of sensitive input data are published in the online setting. In prior work, this formulation requires that any private mechanism when given as input two neighboring streams that differ in the value of at most one stream element must generate output streams that are almost indistinguishable.

In this paper, we consider a more general notion of privacy wherein an individual's decision to participate in the data collection process may potentially shift the entire stream by a time-step. We define a new notion of edit-neighboring streams that captures this scenario. Our findings are as follows.

First, we prove that on a stream of length T , no additive-noise mechanism achieves additive error less than Ω(minT 1/3 /ε 2/3 , T ) when required to be ε-DP under CO for edit-neighboring streams. In particular, this includes state-of-the-art continual counters constructed via the factorization mechanism that in the standard neighboring setting incur only polylogarithmic additive error.

Second, we construct the first mechanisms with polylogarithmic additive error for our more stringent notion of privacy. We show that we can recover the same additive error as in the standard notion of privacy albeit with worse constant coefficients for both arbitrary input streams and sparse streams.

Third, we show that the notion of edit-neighboring streams inhabits a 'sweet-spot' in terms of generality and additive error incurred. More precisely, we show that the even more general notion of prefix-sum neighboring streams-which arises naturally in reductions for problems under CO-must incur additive error scaling as Ω(minT 1/3 /ε 2/3 , T ) for any mechanism that is ε-DP under continual observation.

Finally, we show empirically on synthetic data that when compared with prior work, our mechanism achieves a superior trade-off between the success probability of a simple distinguishing attack, and the additive error incurred by the respective mechanisms.