DP With Auxiliary Information: Gaussian Mechanism Versus Laplacian Mechanism

Differential privacy (DP) has been widely used in communication systems, especially those using federated learning or distributed computing. DP comes in the data preparation stage before line coding and transmission. In contrast to the literature where differential privacy is mainly discussed from the point of view of data/computer science, in this paper we approach DP from a perspective that provides a better understanding to the communications engineering community. From this perspective, we show the contrast between the MAP detection problem in communications and the DP problem. In this paper, we consider two DP mechanisms, namely, the Gaussian Mechanism (GM) and the Laplacian Mechanism (LM). We explain why the definition of <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\epsilon$ </tex-math></inline-formula>-DP is associated with the LM, while we must resort to the definition of (<inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\epsilon, \delta$ </tex-math></inline-formula>)-DP if the GM is used. Furthermore, we derive a new lower bound on the perturbation noise required for the GM to guarantee (<inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\epsilon, \delta$ </tex-math></inline-formula>)-DP. Although no closed form is obtained for the new lower bound, a very simple one dimensional search algorithm can be used to achieve the lowest possible noise variance. Since the perturbation noise is known to negatively affect the performance of the data analysis (such as the convergence in federated learning), the new lower bound on the perturbation noise is expected to improve the performance over the classical GM. Moreover, we derive the perturbation noise required for both the LM and the GM in case of the adversary having auxiliary information in the form of the prior probabilities of the different databases. We show that the availability of auxiliary information at the adversary, is equivalent to reducing the tolerable privacy leakage, and hence it requires more perturbation noise. Finally, we analytically derive the border between the region where GM is better to use and the region where LM is better to use.