24 Jul 2014 - Marco Gaboardi

C. Dwork, Differential Privacy, Proceedings of the 33rd International Colloquium on Automata, Languages and Programming (invited), 2006

Abstract

In 1977 Dalenius articulated a desideratum for statistical databases: nothing about an individual should be learnable from the database that cannot be learned without access to the database. We give a general impossibility result showing that a formalization of Dalenius’ goal along the lines of semantic security cannot be achieved. Contrary to intuition, a variant of the result threatens the privacy even of someone not in the database. This state of affairs suggests a new measure, dif- ferential privacy, which, intuitively, captures the increased risk to one’s privacy incurred by participating in a database. The techniques devel- oped in a sequence of papers [8, 13, 3], culminating in those described in [12], can achieve any desired level of privacy under this measure. In many cases, extremely accurate information about the database can be provided while simultaneously ensuring very high levels of privacy.