# A High-Utility Differentially Private Mechanism for Space Information Networks
## 2 Background Knowledge
### Differential Privacy  
Differential privacy is a method of protecting data sharing. It may be accomplished by withholding personally identifiable information about particular people and just giving statistical data that can be used to define the database as a whole. Differential privacy is the theory that if the impact of inserting a single random replacement in the database is tiny enough, the query result cannot be utilized to infer a lot about a specific person and so offers privacy. The following is a formal definition of differential privacy.  
\[Pr\{A(D)=O\}\leq e^{\epsilon}\cdot Pr\{A(D^{\prime})=O\} \tag{1}\]  
The two output distributions derived for a randomized algorithm \(A\) acting on two neighboring data sets, \(D\) and \(D^{\prime}\), are identical. The randomized algorithm indicates that given a specific input, the algorithm's output is not a fixed value but follows a particular probability distribution.  
Differential privacy is also the state-of-the-art technology of privacy preservation. There are various differentially private mechanisms for various application scenarios. It is not only in SINs but also in other scenarios in healthcare, finance, insurance, and public safety, where differential privacy technologies are needed to protect clients' private information. For instance, a significant proportion of CTs collected by patients are awaiting analysis and diagnosis by physicians because of the recent COVID-19 pandemic. Based on CT pictures, an AI system may assess whether a patient has COVID-19 (positive or negative). The hospital gives computer vision technology-equipped third-party professional organization access to the tagged data, which includes the patient's name, gender, and even address. It would compromise the patient's privacy and maybe breach various data protection laws and regulations while significantly increasing the diagnosis's accuracy and effectiveness. Differentiated privacy aims to safeguard patient privacy while developing deep-learning models for hospitals. Google employs localized differential privacy to gather data on the Chrome browser used by more than 14 million people daily. Apple safeguards user privacy on iOS and macOS via localized differential privacy approaches. The sampling and aggregation method, the Laplace mechanism for distributed systems, and other differentially private techniques that may be used in a distributed setting are the main topics of this work.  
Laplace mechanism [25]. The outcome of the Laplace mechanism \(M\) is Equation (2) for a given database \(D\), a query \(q\), and privacy budget \(\epsilon\).  
\[M(q,D,\epsilon)=q(D)+Lap(0,\frac{\Delta D}{\epsilon}) \tag{2}\]  
Here, \(\epsilon\) is the privacy budget, which controls the privacy guarantee of differentially private mechanisms. Specifically, the privacy guarantee is stronger when the value of privacy budget is smaller. \(Lap(0,\Delta D/\epsilon)\) represents a number (which is named noise in the context of differential privacy) from the Laplace distribution with location parameter \(0\) and scale parameter \(\Delta D/\epsilon\). Global sensitivity, also known as \(\Delta D\), measures the largest difference brought on by the presence or absence of a single data record.  
Global sensitivity [21]. The global sensitivity indicated by \(\Delta D\) for a given database \(D\) and query \(q\) may be determined using Equation (3).  
\[\Delta D=\max_{D\sim D^{\prime}}|q(D)-q(D^{\prime})| \tag{3}\]  
Here, \(D^{\prime}\) is the dataset that is different from \(D\) on only one data record.  
Sample and aggregation mechanism. The sample and aggregation mechanism based on random sampling method was proposed by [PERSON] et al. [22]. This mechanism is shown in Figure 2. The target queries are calculated across each of the \(n\) subsets of the dataset. An aggregation function computes the outcome in a way that satisfies differential privacy.