Share on Facebook Tweet on Twitter Share on LinkedIn Share by email
Differential Privacy Under Continual Observation

Cynthia Dwork, Moni Naor, Toniann Pitassi, and Guy N. Rothblum

Abstract

Differential privacy is a recent notion of privacy tailored to privacy-preserving data analysis [11]. Up to this point, research on differentially private data analysis has focused on the setting of a trusted curator holding a large, static, data set; thus every computation is a "one-shot" object: there is no point in computing something twice, since the result will be unchanged, up to any randomness introduced for privacy.

However, many applications of data analysis involve repeated computations, either because the entire goal is one of monitoring, e.g., of traffic conditions, search trends, or incidence of influenza, or because the goal is some kind of adaptive optimization, e.g., placement of data to minimize access costs. In these cases, the algorithm must permit continual observation of the system's state. We therefore initiate a study of differential privacy under continual observation. We identify the problem of maintaining a counter in a privacy preserving manner and show its wide applicability to many different problems.

Details

Publication typeInproceedings
Published inSTOC '10: Proceedings of the 42nd ACM symposium on Theory of computing
URLhttp://doi.acm.org/10.1145/1806689.1806787
Pages715--724
OrganizationACM
PublisherAssociation for Computing Machinery, Inc.
> Publications > Differential Privacy Under Continual Observation