Pan-Private Streaming Algorithms

By Cynthia Dwork, Moni Naor, Toniann Pitassi, Guy N. Rothblum, Sergey Yekhanin. 2010

186 citations recorded by the source corpus.

How researchers see this paper

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

In Privacy & Security

Citations in the corpus

Privacy Amplification by Decentralization (2020, methodology): “By leveraging the fact that the view of each user u is restricted to the values taken by the token at each of its K visits to u , combined with advanced composition (Dwork et al., 2010b), we have the following result (see Appendix A for the proof).”
Collecting Telemetry Data Privately (2017, background): “in Blowﬁsh privacy [20] which protects only a speciﬁed subset of pairs of neighborhood databases to trade-off privacy for utility. On a different but relevant line of work about streaming model of DP [14], the event-level private counting problem under continual observation is studied [11], with alm”
Local, Private, Efficient Protocols for Succinct Histograms (2015, background): “Running many copies of the protocol for unique heavy hitters in parallel, we can recover the list of heavy hitters.”
RAPPOR: Randomized Aggregatable Privacy-Preserving Ordinal Response (2014, background): “Although it does not operate under the same local model as RAPPOR, recent work by [14] on pan-private streaming and by [13] on privacy under continual observation introduces additional ideas relevant for the longitudinal data collection with privacy.”
Distributed Private Heavy Hitters (2012, background): “Also, [DNP + 10, MMNW11] work in the centralized setting, but demand pan-privacy , which roughly requires that the internal state of the algorithm itself remain diﬀerentially private.”
Connecting Robust Shuffle Privacy and Pan-Privacy (2020, background): “Dwork, Naor, Pitassi, Rothblum, and Yekhanin [19] introduced pan-privacy and, for a data domain of size k , showed how to pan-privately count distinct elements to additive accuracy O ( √ k/ε ).”
Analyzing Information Leakage of Updates to Natural Language Models (2019, background): “Pan-privacy [7], on the other hand, studies the problem of maintaining differential privacy when an attacker observes snapshots of the internal state of a DP algorithm between updates.”
Differentially Private Data Publishing and Analysis: A Survey (2017, background): “This type of data can be simplified as a bit string f0; 1g and each 1 in the stream represents the occurrence of an event [25].”
The Algorithmic Foundations of Differential Privacy (2014, background): “The pan-private density estimation, as well as a low-memory variant using hashing, appear in [27].”
Pan-Private Uniformity Testing (2019, background): “[26] studied streams where each element is a (user, value) pair and a neighboring stream may replace all values contributed by any one user.”
Efficient Differentially Private F0 Linear Sketching (2020, background): “Already the seminal paper on pan-privacy [16] discusses differentially private streaming algorithms for F 0 on insertion-only streams.”
Heavy Hitter Estimation over Set-Valued Data with Local Differential Privacy (2016, background): “In [11], private estimation of frequent elements from stream data is studied in a setting called ”pan-privacy”, which can be considered as a variant of the LDP model.”
Private Hypothesis Selection (2019, background): “Under various notions of pan-privacy [89] and the shuffled model [90], [91], which are intermediate to local and central differential privacy, the sample complexity of m-wise simple hypothesis testing (the easier version of hypothesis selection, where the unknown distribution is equal to one of the ”
The Limits of Two-Party Differential Privacy (2010, unknown): “There are connections between two-party differential privacy and pan-privacy [ 30 ].”