Local Differential Privacy for Evolving Data

By Matthew Joseph, Aaron Roth, Jonathan Ullman, Bo Waggoner. 2018

98 citations recorded by the source corpus.

There are now several large scale deployments of differential privacy used to collect statistical information about users. However, these deployments periodically recollect the data and recompute the statistics using algorithms designed for a single use. As a result, these systems 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 technique for local differential privacy that makes it possible to maintain up-to-date statistics over time, with privacy guarantees that degrade only in the number of changes in the underlying distribution rather than the number of collection periods. We use our technique for tracking a changing statistic in the setting where users are partitioned into an unknown collection of groups, and at every time period each user draws a single bit from a common (but changing) group-specific distribution. We also provide an application to frequency and heavy-hitter estimation.

Subfields: Artificial Intelligence, Electrical and Electronic Engineering, Transportation

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Electrical and Electronic Engineering

In Transportation

Aleksandra Korolova

Citations in the corpus

The power of synergy in differential privacy: Combining a small curator with local randomizers (2019, background): “The adoption of the local model by major industry players has motivated a line of research in the theory of local di ﬀ erential privacy (e.g., [9, 8, 16, 59, 40, 42, 41]).”
Honeycrisp: large-scale differentially private aggregation without a trusted core (2019, background): “More recent theoretical work tackles similar challenges of infrequently changing data – [45] assumes that the data is drawn from some set of underlying distributions that aren’t changing, while [31] assumes that individuals’ data aren’t changing very frequently – by contrast Honeycrisp only makes as”
Amplification by Shuffling: From Local to Central Differential Privacy via Anonymity (2018, methodology): “Motivated by similar issues, in a recent work Joseph et al. [JRUW18] consider the problem of tracking a distribution that changes only a small number of times.”
The Role of Interactivity in Local Differential Privacy (2019, background): “Ullman [30] and Daniely and Feldman [12] later expanded this result to a larger class (1)Not every protocol is 1-compositional: an exception is [23].”
Consistent and Accurate Frequency Oracles under Local Differential Privacy (2019, background): “, finding heavy hitters [5–7, 17, 35], frequent itemset mining [27, 36], releasing marginals under LDP [9, 28, 40], keyvalue pair estimation [39], evolving data monitoring [15, 20], and empirical risk minimization [30, 31].”
Locally Differentially Private Heavy Hitter Identification (2017, background): “For example, mean estimation [11], [27], frequent itemset mining [29], [37], releasing marginals under LDP [10], [30], [41], key-value pair estimation [40], evolving data monitoring [15], [22], and empirical risk minimization [31], [32].”