Download Embed
Moni Naor
The Weizmann Institute of Science
November 23, 2009

Research in the area of privacy of data analysis has been flourishing recently, with a rigorous notion such as differential privacy regarding the desired level of privacy and sanitizing algorithms matching the definition for many problems. Most of the work in the area assumes that the data to be sanitized is fixed. However, many applications of data analysis involve computations of changing data, 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 this talk I will describe work on providing guarantees for dynamically changing data. Issues that arise include:

  • How to provide privacy even when the algorithm has to constantly output the current value of some function of the data (Continual Observation)
  • How to assure privacy even when the internal state of the sanitizer may be leaked (Pan Privacy). Here we aim to design algorithms that never store sensitive information about individuals, so in particular collectors of confidential data cannot be pressured to permit data to be used for purposes other than that for which they were collected.

One problem we will concentrate on is that of providing a a public `counter' that counts the number of times a resource has been accessed, but does not leak any information about the presence or absence of individual increments.

Based on joint papers with Cynthia Dwork, Toni Pitassi, Guy Rothblum and Sergey Yekhanin.