Differential Privacy

Over the past ten years, differential privacy (DP) has become the leading privacy standard in research on analysing and publishing sensitive data. It offers strong guarantees and has been applied to a wide range of data analysis tasks.

This lecture is the first of two volumes. It stands apart from existing books and surveys by balancing theory with practice. It judges algorithms by their empirical accuracy rather than asymptotic bounds, and it tries to explain why they perform as they do. It also treats the meaning of DP even-handedly, covering both its strengths and its limits.

The opening chapters cover the definition, basic properties and main techniques for achieving DP. Next comes a detailed look at the semantic privacy guarantee and the pitfalls of applying DP in practice. Later chapters review current mechanisms for publishing histograms on low-dimensional data, for machine learning tasks such as classification, regression and clustering, and for answering marginal queries on high-dimensional data. The book ends with the sparse vector technique and the many errors in the literature that have used it.

The planned second volume will address DP in other settings, including high-dimensional data, graph data, the local setting and location privacy, and will also examine relaxations of DP.