# Calibrating the Attack to Sensitivity in Differentially Private Mechanisms
## 2 System Model and Its Components  
In this part, we revisit certain notions from the literature on DP which will also be employed in this paper. These preliminaries will be followed by a detailed definition of the addressed problem. We begin with defining the notion of neighborhood between datasets and sensitivity of DP.  
**Definition 1** (Neighboring datasets).: _Any two datasets that differ only in one row are called neighbors [4]. For two neighboring datasets, the following equality holds_  
\[d(x,\tilde{x})=1 \tag{1}\]  
_where \(d(.,.)\) denotes the Hamming (or \(l_{1}\)) distance between two datasets._  
**Definition 2** (\(L_{1}\) norm sensitivity [7]).: _Global sensitivity, denoted by \(s\) of a function (or a query) \(q\): \(D\to\mathbb{R}^{k}\) is the smallest possible upper bound on the distance between the images of \(q\) when applied to two neighboring datasets, i.e., the \(l_{1}\) distance is bounded by \(\|q(x)-q(\tilde{x})\|_{1}\leq s\)._  
Basically, sensitivity of a DP mechanism is the smallest possible upper bound on the images of a query function for neighbors. Hence it is a function of the type of the query having an opposite relationship with the privacy. Higher sensitivity of the query refers to a stronger requirement for privacy guarantee, consequently more noise is needed to achieve that guarantee.  
**Definition 3** (\((\epsilon,\delta)\)-DP [4]).: _A randomized algorithm \(\mathcal{Y}\) is \((\epsilon,\delta)\)-differentially private if \(\forall S\subseteq Range(\mathcal{Y})\) and for all neighboring datasets \(x\) and \(\tilde{x}\) within the domain of \(\mathcal{Y}\) the following inequality holds._  
\[\Pr[\mathcal{Y}(x)\in S]\leq\Pr[\mathcal{Y}(\tilde{x})\in S]\exp\{\epsilon\}+\delta \tag{2}\]  
Next, we remind the reader of the Laplace distribution and Laplace mechanism. A differentially private system is named after the probability distribution of the perturbation applied onto the query output in the global setting. The Laplace distribution, also known as the double exponential distribution, is defined as  
\[Lap(x;\mu,b)=\frac{1}{2b}\exp\left\{-\frac{|x-\mu|}{b}\right\} \tag{3}\]  
with the location parameter equal to its mean \(\mu\in\mathbb{R}\) and variance \(2b^{2}\) where \(b>0\) denotes the scale parameter.  
**Definition 4**.: _Laplace mechanism [7] is defined for a function (or a query) \(q:D\to\mathbb{R}^{k}\) as follows_  
\[\mathcal{Y}(x,q(.),\epsilon)=q(x)+(Z_{1},\cdots,Z_{k}) \tag{4}\]  
_where \(Z_{i}\sim Lap(b=s/\epsilon)\), \(i=1,\cdots,k\) denote i.i.d. Laplace random variables._  
We will refer to the parameters \(\epsilon\) and \(\delta\) as privacy budget throughout the paper. Next definition reminds the reader of the \(L_{2}\) norm global sensitivity.  
**Definition 5**.: \(L_{2}\) _norm sensitivity denoted \(s\) refers to the smallest possible upper bound on the \(L_{2}\) distance between the images of a query \(q:D\to\mathbb{R}^{k}\) when applied to two neighboring datasets \(\mathbf{X}\) and \(\mathbf{\tilde{X}}\) as_  
\[s=\sup_{d(\mathbf{X},\mathbf{\tilde{X}})=1}||q(\mathbf{X})-q(\mathbf{\tilde{ X}})||_{2}. \tag{5}\]  
**Definition 6**.: _Gaussian mechanism [7] is defined for a function (or a query) \(q:D\rightarrow\mathbb{R}^{k}\) as follows_  
\[\mathcal{M}(\mathbf{X},q(.),\epsilon,\delta)=q(\mathbf{X})+(Z_{1},\cdots,Z_{k}) \tag{6}\]  
_where \(Z_{i}\sim\mathcal{N}(0,\sigma^{2})\), \(i=1,\cdots,k\) denote independent and identically distributed (i.i.d.) Gaussian random variables with the variance \(\sigma_{z}^{2}=\frac{2s^{2}\log(1.25/\delta)}{\epsilon^{2}}\)._  
**Theorem 1** ([4]).: _The Laplace mechanism satisfies \((\epsilon,0)\)-differential privacy._  
**Theorem 2** ([4]).: _For any \(\epsilon,\delta\in(0,1)\), the Gaussian mechanism satisfies \((\epsilon,\delta)\)-differential privacy._  
Application of Gaussian noise results in a more relaxed privacy guarantee contrary to Laplace mechanism, which brings about \((\epsilon,0)\)-DP.