DCWHome

In the recent few years we have witnessed some exciting advances in the formal treatment of privacy in data, both in definitional work and in algorithmic analysis techniques. These advances make it possible to publish accurate analysis results while preserving privacy in a very strong sense, allowing mining and analysis of the global trends in large data collections of medical data, web and search related data, economic date etc. In addition to these discoveries, some relationships have been uncovered between data privacy and other areas such as computational learning and computational game theory. These encouraging results suggest that this line of research in privacy may have both practical and theoretical bearings.

Central to the formal work on privacy is a definition that captures an intuitive, notion of individual protection - differential privacy (aka epsilon-privacy). Following the practice evolved in the theoretical research of cryptography, differential privacy is a guarantee in face of any realizable attacker. It stipulates that what the attacker sees - i.e. the outcome of the analysis - should not be sensitive to any individual's value. A corollary is that any individual should not be significantly affected by the inclusion of their data in the analysis.

Somewhat surprisingly, differential privacy does allow performing useful computations over data and publishing their results. This is generally achieved by modifying an analysis, in way of inserting specially crafted noise, so that (i) the final outcome satisfies the definition of differential privacy, and (ii) is a faithful approximation of the outcome computed by the original analysis. Our current inventory of analyses spans the computation of simple statistics to datamining and learning tasks.

The theoretical cryptographic research has dramatically influenced the practice of constructing cryptosystems. One would hope that the theoretical research in private data analysis would similarly interact with the practice of enhancing privacy in data, e.g. as is relevant for census and other statistical data. A `practical' question here is whether it is possible to bridge the differences between the notion of differential privacy (together with the techniques developed for constructing efficient private data analyses) and the more traditional statistical disclosure limitation (SDL) techniques. It seems that an understanding of privacy in small datasets is important here because of the costs in obtaining data samples.