Local Differential Privacy for Evolving Data
Matthew Joseph, Aaron Roth, Jonathan Ullman, Bo Waggoner
There are now several large scale deployments of differential privacy used to
track statistical information about users. However, these systems
periodically recollect the data and recompute the statistics using algorithms
designed for a single use and as a result do not provide meaningful privacy
guarantees over long time scales. Moreover, existing techniques to mitigate
this effect do not apply in the "local" model of differential privacy that
these systems use.
In this paper, we introduce a new local differential
privacy technique to maintain persistently up-to-date statistics over time,
with privacy guarantees scaling only with the number of changes in the
underlying distribution rather than the number of collection periods.
The key ideas include batching time into epochs---varying the epoch
size allows us to trade off accuracy against frequency of updates---and a
protocol for users to "vote" to update out-of-date statistics while losing
very little privacy. We prove our main results for the setting where users
hold a single bit, redrawn at every time period, from a common (but changing)
distribution; however, our framework is quite general and we give an
application to frequency and heavy-hitter estimation.