Differential Privacy: From Theory to Practice

Over the last decade, differential privacy (DP) has emerged as the de facto standard privacy notion for research in privacy-preserving data analysis and publishing. The DP notion offers strong privacy guarantee and has been applied to many data analysis tasks.

This Synthesis Lecture is the first of two volumes on differential privacy. This lecture differs from the existing books and surveys on differential privacy in that we take an approach balancing theory and practice. We focus on empirical accuracy performances of algorithms rather than asymptotic accuracy guarantees. At the same time, we try to explain why these algorithms have those empirical accuracy performances. We also take a balanced approach regarding the semantic meanings of differential privacy, explaining both its strong guarantees and its limitations.

We start by inspecting the definition and basic properties of DP, and the main primitives for achieving DP. Then, we give a detailed discussion on the the semantic privacy guarantee provided by DP and the caveats when applying DP. Next, we review the state of the art mechanisms for publishing histograms for low-dimensional datasets, mechanisms for conducting machine learning tasks such as classification, regression, and clustering, and mechanisms for publishing information to answer marginal queries for high-dimensional datasets. Finally, we explain the sparse vector technique, including the many errors that have been made in the literature using it.

The planned Volume 2 will cover usage of DP in other settings, including high-dimensional datasets, graph datasets, local setting, location privacy, and so on. We will also discuss various relaxations of DP.

在過去的十年中，差分隱私（DP）已成為隱私保護數據分析和發布研究的事實上標準隱私概念。差分隱私概念提供了強大的隱私保證，並已應用於許多數據分析任務。

這本綜合講座是關於差分隱私的兩卷中的第一卷。這本講座與現有的差分隱私書籍和調查不同，我們採取了一種平衡理論和實踐的方法。我們專注於算法的實際準確性表現，而不是漸進準確性保證。同時，我們試圖解釋為什麼這些算法具有這些實際準確性表現。我們還對差分隱私的語義含義採取了平衡的方法，解釋了它的強大保證和限制。

我們首先檢查DP的定義和基本屬性，以及實現DP的主要基本元素。然後，我們詳細討論了DP提供的語義隱私保證以及應用DP時的注意事項。接下來，我們回顧了用於低維數據集的直方圖發布機制，用於進行機器學習任務（如分類、回歸和聚類）的機制，以及用於回答高維數據集的邊緣查詢的信息發布機制。最後，我們解釋了稀疏向量技術，包括在文獻中使用該技術時出現的許多錯誤。

計劃中的第二卷將涵蓋DP在其他場景中的應用，包括高維數據集、圖數據集、本地環境、位置隱私等。我們還將討論DP的各種放寬。