Review of Popular Algorithms for Differential Privacy
Ninghui Li, Tianhao Wang · 2024
In this chapter, we review mechanisms (sometimes also called primitives or tools) for satisfying the classic notion of differential privacy (DP). These mechanisms can be categorized into two groups: Laplace mechanism (Section 4.1 ) and Gaussian mechanism (Section 4.2 ) add noise to a numerical value to satisfy DP. These can be used to get a noisy subpopulation count. Exponential mechanism (Section 4.3 ), Noisy Max (Section 4.4 ), sparse vector technique (Section 4.5 ), and frequency oracles (Section 4.7 ) can be seen as probabilistic selection mechanisms that outputs one element from a pre-defined set of possible outputs. For example, to identify which marginals deviate the most from an analyst’s prior. Note that the selection process is more general since we can define the set of selection candidates as all possible noisy numerical values, and outputting one element from the set can be seen as outputting one noisy value. See detailed discussion in Section 4.6 .