Fetching the paper…

Reading the bibliography…

2010

Pan-private Algorithms: When Memory Does Not Help

Mir, Darakhshan, Muthukrishnan, S., Nikolov, Aleksandar et al.

Original
PDF
Post on X

Understand

Consider updates arriving online in which the $t$th input is $(i_t,d_t)$, where $i_t$'s are thought of as IDs of users.

Informally, a randomized function $f$ is {\em differentially private} with respect to the IDs if the probability distribution induced by $f$ is not much different from that induced by it on an input in which occurrences of an ID $j$ are replaced with some other ID $k$ Recently, this notion was extended to {\em pan-privacy} where the computation of $f$ retains differential privacy, even if the internal memory of the algorithm is exposed to the adversary (say by a malicious break-in or by fiat by the government).
This is a strong notion of privacy, and surprisingly, for basic counting tasks such as distinct counts, heavy hitters and others, Dwork et al~\cite{dwork-pan} present pan-private algorithms with reasonable accuracy.
The pan-private algorithms are nontrivial, and rely on sampling.

Pan-private Algorithms: When Memory Does Not Help · Around

Built on

Randomized response: A survey technique for eliminating evasive answer bias
Original
S. Warner · 1965
Earlier work this paper cites.
Pseudorandom generators for space-bounded computation
N. Nisan · 1992
Earlier work this paper cites.
Comparing data streams using hamming norms (how to zero in)
Graham Cormode, Mayur Datar, Piotr Indyk, and S. Muthukrishnan · 2003
Earlier work this paper cites.
Revealing information while preserving privacy
Irit Dinur and Kobbi Nissim · 2003
Earlier work this paper cites.
An improved data stream summary: The count-min sketch and its applications
G. Cormode and S. Muthukrishnan · 2005
Earlier work this paper cites.

Similar

Data streams: Algorithms and applications
S. Muthukrishnan · 2005
Cited alongside, same era.
Calibrating noise to sensitivity in private data analysis
Cynthia Dwork, Frank Mcsherry, Kobbi Nissim, and Adam Smith · 2006
Cited alongside, same era.
Stable distributions, pseudorandom generators, embeddings, and data stream computation
Piotr Indyk · 2006
Cited alongside, same era.
The price of privacy and the limits of lp decoding
Cynthia Dwork, Frank McSherry, and Kunal Talwar · 2007
Cited alongside, same era.

Then

Pan-Private Streaming Algorithms
C. Dwork, M. Naor, T. Pitassi, G. Rothblum, and S. Yekhanin · 2010
Closest in time.
Differential privacy in new settings
Cynthia Dwork · 2010
Closest in time.
Stable Distributions - Models for Heavy Tailed Data
J. P. Nolan · 2010
Closest in time.
Differentially private combinatorial optimization
Kunal Talwar, Anupam Gupta, Katrina Ligett, Frank McSherry, and Aaron Roth · 2010
Closest in time.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…