## 2 Preliminaries
### Differential Privacy  
Differential privacy is a widely used standard to guarantee privacy in data analysis. The main idea of DP is to consider a thought experiment in which we compare how an algorithm behaves on a dataset \(D_{1}\) with the way it behaves on a hypothetical dataset \(D_{2}\), in which one person's record has been removed or added. These two datasets are considered \"neighbors\" in the dataset space. Hence, we say that an algorithm is differentially private if running the algorithm on two neighboring datasets yields roughly the same distribution of outcomes. In other words, differential privacy ensures that the outcomes of \(M\) are approximately the same whether or not the person \(i\) joins the dataset. Formally, DP is defined by [PERSON] et al. in 2006 [28] as follows.  
**Definition 1**.: _A randomized function \(M\) gives \((\epsilon,\delta)\)-differential privacy if for all datasets \(D_{1}\) and \(D_{2}\) differing on at most one element, and all \(S\subset Range(M)\),_  
\[Pr[M(D_{1})\in S]\leq e^{\epsilon}\times Pr[M(D_{2})\in S]+\delta \tag{1}\]  
In the Definition 1, \(\epsilon\) is a non-negative real number that determines the level of privacy protection provided by the algorithm. A lower value of \(\epsilon\) corresponds to a stronger privacy guarantee. The value of \(\delta\) is a small positive real number that represents the probability of any failure of the definition. When \(\delta\) is set to 0, it is referred to as pure differential privacy.  
Three major properties arise directly from this definition: composition, post-processing, and group privacy. These properties are the key to design powerful algorithm from basic mechanisms:  
* Composition: offers a way to bound privacy cost of answering multiple queries on the same data.
* Post-processing: ensures that the privacy guarantees of a differential privacy mechanism remain unchanged even if the output is further processed or analyzed.  
* Group privacy: this definition can be extended to group privacy by considering two datasets differing on at most \(k\) records instead of 1 record.  
As stated in the definition, DP is a property of an algorithm \(M\). There are several methods to achieve DP based on adding noise to the input data, the output data, or the intermediate result. The noise can be generated using different mechanisms, the well-known ones are the Laplace mechanism, the Gaussian mechanism, and the exponential mechanism.  
Two main settings are discussed in the literature for differential privacy: the centralized DP (CDP) and the local DP (LDP). In CDP, the noise is added by a centralized server that collects first the data then applies the mechanism. In LDP, the noise is added at the client level before collecting the data. LDP offers stronger privacy guarantees, as the noise is added closer to the source of the data. Additionally, a hybrid setting called the shuffle model is also explored in the literature. The shuffle model aims to combine the benefits of both CDP and LDP. In this setting, privacy is enhanced through anonymization achieved by shuffling the data. The noise is added centrally by a shuffler before passing the data to the analyst server, which enables the system to attain the performance advantages of CDP while maintaining the privacy guarantees provided by LDP.