# A High-Utility Differentially Private Mechanism for Space Information Networks
## 3 Proposed Mechanism
### Privacy Analyses
Therefore,  
\[Pr\{Lap_{i}(\bar{D}_{i+x})=a_{i}=q(\bar{D}_{i+x})+\sqrt{B_{n-1}}l_{i}\}=\frac{ e}{2c}e^{-\frac{e(Lap_{i}(\bar{D}_{i+x})-q(\bar{D}_{i+x}))}{c\sqrt{B_{n-1}}}} \tag{25}\]  
Similarly, When a record \(x\) is not in dataset \(\bar{D}_{i}\), we have  
\[Pr\{Lap_{i}(D_{i-x})=a_{i}=q(D_{i-x})+\sqrt{B_{n-1}}l_{i}\}=\frac{e}{2c}e^{- \frac{e(Lap_{i}(D_{i-x})-q(D_{i-x}))}{c\sqrt{B_{n-1}}}} \tag{26}\]  
Therefore, we have  
\[ \begin{array}{ll}&\frac{Pr\{Lap_{i}(\bar{D}_{i+x})=a_{i}\}}{Pr\{Lap_{i}(\bar {D}_{i-x})=a_{i}\}}\\ &=\ e^{\frac{e(Lap_{i}(\bar{D}_{i-x})-q(\bar{D}_{i-x}))}{c\sqrt{B_{n-1}}}-\frac {e(Lap_{i}(\bar{D}_{i+x})-q(\bar{D}_{i+x}))}{c\sqrt{B_{n-1}}}}\\ &=\ e^{\frac{e(|Lap_{i}(D_{i-x})-q(\bar{D}_{i+x})|-Lap_{i}(\bar{D}_{i+x})-q( \bar{D}_{i+x})|)}{c\sqrt{B_{n-1}}}}\\ &=\ e^{\frac{e(|Lap_{i}-q(\bar{D}_{i-x})|-|a_{i}-q(\bar{D}_{i+x})|)}{c\sqrt{B_{ n-1}}}}\\ &\leq\ e^{\frac{e(|Lap_{i}-q(\bar{D}_{i-x})-q+q(\bar{D}_{i+x})|)}{c\sqrt{B_{ n-1}}}}\\ &=\ e^{\frac{eLRS_{x}}{c\sqrt{B_{n-1}}}}\end{array}  \tag{27}\]  
Let \(M_{i}\) represent local differentially private mechanism used by the \(i\)th satellite. We have  
\[\begin{array}{ll}&Pr\{M_{i}(D_{i+x})=a_{i}\}\\ &=\ Pr\{S(D_{i+x})=\bar{D}_{i+x}\}Pr\{Lap_{i}(\bar{D}_{i+x})=a_{i}\}+Pr\{S(D_ {i+x})=\bar{D}_{i-x}\}Pr\{Lap_{i}(\bar{D}_{i-x})=a_{i}\}\\ &=\ \pi_{x}Pr\{S(D_{i-x})=\bar{D}_{i-x}\}Pr\{Lap_{i}(\bar{D}_{i+x})=a_{i}\}+(1- \pi_{x})Pr\{S(D_{i-x})=\bar{D}_{i-x}\}Pr\{Lap_{i}(\bar{D}_{i-x})=a_{i}\}\\ &\leq\ \pi_{x}Pr\{S(D_{i-x})=\bar{D}_{i-x}\}e^{\frac{eLRS_{x}}{c\sqrt{B_{n-1}}}}Pr \{Lap_{i}(\bar{D}_{i-x})=a_{i}\}+(1-\pi_{x})Pr\{S(D_{i-x})=\bar{D}_{i-x}\}Pr\{ Lap_{i}(\bar{D}_{i-x})=a_{i}\}\\ &=\ (1-\pi_{x}+\pi_{x}e^{\frac{eLRS_{x}}{c\sqrt{B_{n-1}}}})Pr\{S(D_{i-x})=\bar{D }_{i-x}\}Pr\{Lap_{i}(\bar{D}_{i-x})=a_{i}\}\\ &\\[ \begin{array}{l}1-\pi_{x}+\pi_{x}e^{\frac{LRS_{x}}{\varepsilon\sqrt{\pi_{n-1}}}} \\ =\ 1-\frac{1-e^{\varepsilon}}{1-e^{\varepsilon\frac{LRS_{x}}{\varepsilon}}}+ \frac{1-e^{\varepsilon\frac{LRS_{x}}{\varepsilon}}}{1-e^{\varepsilon\frac{LRS_ {x}}{\varepsilon}}}e^{\varepsilon\frac{LRS_{x}}{\varepsilon\sqrt{\pi_{n-1}}}} \\ \leq\ 1-\frac{1-e^{\varepsilon}}{1-e^{\varepsilon\frac{LRS_{x}}{ \varepsilon}}}+\frac{1-e^{\varepsilon}}{1-e^{\varepsilon\frac{LRS_{x}}{ \varepsilon}}}e^{\varepsilon\frac{LRS_{x}}{\varepsilon}}e^{\varepsilon\frac{ LRS_{x}}{\varepsilon}\sqrt{\pi_{n-1}}}\\ =\ 1+(e^{\varepsilon}-1)\frac{1-e^{\varepsilon\frac{LRS_{x}}{ \varepsilon}}}{1-e^{\varepsilon\frac{LRS_{x}}{\varepsilon}}}\\ \leq\ 1+(e^{\varepsilon}-1)\frac{1-e^{\varepsilon\frac{LRS_{x}}{ \varepsilon}}}{1-e^{\varepsilon}}\\ =\ e^{\varepsilon\frac{LRS_{x}}{\varepsilon\sqrt{\pi_{n-1}}}}\end{array}  \tag{29}\]  
For \(LRS_{x}<c_{i}\), the \(\pi_{x}=1\) we have  
\[ \begin{array}{l}1-\pi_{x}+\pi_{x}e^{\varepsilon\frac{LRS_{x}}{ \varepsilon\sqrt{\pi_{n-1}}}}\\ =\ e^{\varepsilon\frac{LRS_{x}}{\varepsilon\sqrt{\pi_{n-1}}}}\\ \leq\ e^{\varepsilon\frac{LRS_{x}}{\varepsilon\sqrt{\pi_{n-1}}}}\end{array}  \tag{30}\]  
Therefore, we have  
\[ \begin{array}{l}Pr\{M_{i}(D_{i+x})=a\}\leq e^{\varepsilon\frac{LRS_{x}}{ \varepsilon\sqrt{\pi_{n-1}}}}Pr\{M_{i}(D_{i-x})=a\}\end{array}  \tag{31}\]  
For the symmetry, we have  
\[ \begin{array}{l}Pr\{M_{i}(D_{i-x})=a\}\leq e^{\varepsilon\frac{-LRS_{x}}{ \varepsilon\sqrt{\pi_{n-1}}}}Pr\{M_{i}(D_{i+x})=a\}\end{array}  \tag{32}\]  
Therefore, the mechanism \(M_{i}\) is a \(e^{\frac{LRS_{x}}{\varepsilon\sqrt{\pi_{n-1}}}}\) differentially private mechanism. That is, the output of each satellite satisfies \(e^{\frac{\varepsilon\varepsilon\sqrt{\pi_{n-1}}}{1-e^{\varepsilon\sqrt{\pi_{n-1 }}}}}\) differential privacy. According to Theorem 1 and Theorem 2, the proposed mechanism is hierarchical in terms of privacy guarantee. Specifically, the privacy guarantee between each satellite and the master satellite is \(e^{\varepsilon\frac{LRS_{x}}{\varepsilon\sqrt{\pi_{n-1}}}}\). Moreover, the privacy guarantee between the whole system and the user is \(\varepsilon\).