The Optimal Noise Distribution for Privacy Preserving in Mobile Aggregation Applications

Abstract

In emerging mobile aggregation applications (e.g., large-scale mobile survey), individual privacy is a crucial factor to determine the effectiveness, for which the noise-addition method (i.e., a random noise value is added to the true value) is a simple yet powerful approach. However, improper additive noise could result in bias for the aggregate result. It demands an optimal noise distribution to reduce the deviation. In this paper, we develop a mathematical framework to derive the optimal noise distribution that provides privacy protection under the constraint of a limited value deviation. Specifically, we first derive a generic system dynamic function that the optimal noise distribution must satisfy and further investigate two special cases for the distribution of the original value (i.e., Gaussian and truncated Gaussian distribution). Our theoretical and numerical analysis suggests that the Gaussian distribution is the optimal solution for the Gaussian input and the asymptotically optimal solution for the truncated Gaussian input.

1. Introduction

With the advance of information age, data aggregation has been widely used in daily life and commercial applications. Even some companies such as Canalys make a living from providing all kinds of statistics. In aggregation applications the server wishes to distill valuable aggregate statistics from a mass of individual data. For example, CarTel [1] learns the traffic condition from the road information collected by mobile phones. BikeNet [2] measures air and road condition to guide cyclists, where all the data is contributed by users' devices.

However, the individual privacy may be violated during the aggregation. The server is able to obtain the individual data of participants from inputs. Nevertheless, much of this information is private for individuals, such as health condition and income, especially in the presence of curious server or data abuse. Actually the server only needs to know the aggregate result without knowing the individual data. Thus, in aggregation applications, calculating the aggregate statistics without compromising individual privacy is an important challenge.

Secure Multiparty Computation (SMC) is a good choice to solve this problem. It usually uses cryptographic methods, doing operations on ciphertext domain. However, it also has many limitations. Firstly, because of the huge overhead, SMC is not suitable for large-scale systems. Secondly, most of SMC methods need collaboration of parties, which is not suitable for some circumstances where collaboration is not easy (e.g., in wireless network, the node may not connect with others at all times). Thirdly, both encryption/decryption and communication are high-power consumption operations, which limit SMC deployed in energy-sensitive devices (e.g., sensor or phone). Therefore, SMC is not suitable for the large-scale energy-constraint environments such as large-scale mobile survey applications. Furthermore, brute force attack is powerful to cryptographic methods if the plaintext space is small. Some of the methods such as [3] get the aggregate result based on this property. On the contrary, noise addition, which prevents the adversary from getting the accurate individual data values, is a simple but effective method. Compared to SMC, it is much simpler and efficient, especially in this environment. Without collaboration with others, each participant only adds noise into his data independently before updating. However, in this method, how to choose the noise distribution is a headache. Improper additive noise could result in bias for the aggregate result. It demands an optimal noise distribution which provides the best protection to individual privacy while the aggregate result has tolerable bias. However, the optimal noise distribution is not evident. Usually the noise distribution is proposed directly (usually homogeneous noise or Gaussian noise) without any explanation.

In aggregation applications the accuracy of result and the privacy of individuals are two main concerned issues. Our goal is to find out the optimal noise distribution in noise addition method, where the individual privacy is protected best under the given accuracy requirement. The main contributions of this paper are as follows.

• (1)

We formulate the accuracy and privacy metrics by mean and variance and mutual information, respectively, which are the foundations for choosing proper noise distribution.

(2)

Based on the accuracy and privacy metrics, we develop a mathematical framework to derive the optimal noise distribution.

(3)

We get the generic system dynamic function that the optimal noise distribution must satisfy, where the input is the distribution of original individual data.

(4)

We solve the problem for two input cases. For the Gaussian input, we get the theoretical optimal solution. For the truncated Gaussian distribution input, firstly we point out when it can be approximated by Gaussian distribution, so that the solution of the Gaussian distribution input can be employed directly. Then for the arbitrary truncated Gaussian input, we point out Gaussian distribution is the asymptotically optimal solution.

The rest of the paper is organized as follows. Related work is introduced in Section 2. We formulate the problem in Section 3. In Section 4 we give the general solution and investigate the Gaussian input. In Section 5 the truncated Gaussian input is analyzed in the details. In Section 6 we numerically verify the conclusions and compare the privacy-preserving capability of three proposed noise distributions. At last the paper is concluded in Section 7.

2. Related Work

SMC enables parties to calculate the result by collaboration based on their own data without compromising others' privacy. However it has lots of limitations. In [4] a secure sum protocol was depicted, where the summation is calculated serially which would spend too much time in large-scale systems. Another protocol [3] was proposed, which allows the untrusted server to calculate the summation. It requires that the sum of the keys of parties is $\mathrm{0}$ . If one of the partiez leaves in the process, which is a common case in large-scale systems, the summation cannot be calculated. Jung et al. [5] proposed a linear time protocol without secure channel, but it still needs lots of communications among parties. Meanwhile, in these methods each party has to communicate with others and do lots of mathematical operations, both of which are high-power consumption operations. Although CPDA [6] reduces the communication overhead of SMC for wireless sensor networks, it is still much more complex than other methods. So SMC is not suitable for energy-constrained devices.

In ad hoc network, some other methods are exploited to protect the privacy during data aggregation while trying to reduce the energy cost. A cryptology-based aggregation approach is proposed in [7], which leverages a simple secure additively homomorphic stream cipher, but it requires that all the nodes must share their keys to the sink node, so that the sink node could decrypt the encrypted aggregate result. In SMART [6], the original data is sliced into several pieces and recombined randomly. This method calculates the summation securely, but the communication cost rises several times. GP2S [8] is based on the data generation. It replaces the original data by an integer range, by which the data collector plots the histogram without the accurate original value. However, the summation calculated by the histogram is not accurate.

Noise addition has been studied for many years in secure data mining [9]. It prevents the adversary from getting the accurate individual data values. Plenty of schemes are proposed to preserve the privacy of individual records. Most of them such as [10, 11] are not claimed whether their methods are optimal. Furthermore, they utilize the covariance of data in the database, which needs the party who adds the noise to know the global information of data. In some schemes the noise is added without concerning the covariance of the data, but the uniform distribution or Gaussian distribution is directly declared [12, 13]. In [14] the authors considered the optimal randomization given the bias of results, but they did not solve it. Meanwhile, some researchers [12, 15] found the original data distribution can be restructured by perturbed values, but the individual privacy is not violated yet. To the best of our knowledge, there is no work completely focusing on the optimization of the noise addition scheme.

There are several different measures of privacy. In [12] the privacy is measured by “confidence interval.” If the data concerned x is in the interval $I(x)$ with at least certain probability $c\%$ , the length of interval $\left|I(x)\right|$ is treated as a privacy measure. However, this measure is not accurate. Mutual information or differential entropy in Shannon's information theory is another much more popular privacy metric [15]. It indicates the average privacy supporting by mathematical theory. Renyi entropy (an extension of Shannon entropy) is also used to measure privacy [16], but it is too complex and does not have obvious physical meaning.

In recent years differential privacy [17] is a hot noise addition technology protecting the individual privacy in data mining. It guarantees the accuracy of statistical result while avoiding individual record disclosure. Ghosh et al. [18] found out the optimized noise distribution that provides most accurate result under the given privacy requirement. However, differential privacy is against the adversary that obtains individual record from different statistic results. In our situation, the adversary can get the individual records directly, and we only focus on one aggregation process.

3. Problem Formulation

In this section, firstly we introduce some aggregation applications where the violation of individual privacy potentially exists and noise addition method is appropriate. Then we quantify the accuracy and privacy requirements. Finally, based on the measurements the optimization problem is presented.

3.1. Applications

The individual privacy is potentially threatened in statistics aggregation applications. There are many examples, including

• (i)

sensor network aggregation; in sensor network applications, many energy-constrained sensors are widely deployed to monitor the surrounding environment and send data to the central server for aggregation. However, the data from individual sensor may contain privacy-sensitive information, especially if the sensors are deployed in personal space, confidential institution, or across multiple companies. So energy-efficient privacy protection in aggregation is an important issue;

(ii)

mobile survey applications; in these applications, tens of thousands of participants exist and the phones are energy-constrained. The overall results are distilled from a large amount of individual information collected by mobile phones. However, the individual privacy may be violated during information collection.

In these large-scale energy-constrained applications, the server should know the aggregate results, which are distilled from the information of individuals. However, the individual privacy may be violated during the collection. Noise addition technology, which protects the individual privacy by adding noise into the individual data, is a simple but efficient method in these applications, where it can be employed independently by individual devices without collaboration and the operations are energy-efficient compared with SMC. To describe the problem more accurately, in the following we formulate the problem in mathematical way.

3.2. Accuracy and Privacy Measurement

Suppose that there are n users with values $x_i$ , $i=\mathrm{1,2},\dots ,n$ , and a server calculating aggregate statistics. In this paper, we mainly focus on a simple but common statistic problem called summation. The server processes the aggregation function $\text{sum}(v)={\sum }_{i=\mathrm{1}}^n{x}_i$ . Of course there are several other aggregation types. Besides summation, Popa et al. [19] list other classes such as average, standard deviation, and count. All of them can be constructed by summation, as outlined in Table 1.

Table 1

Aggregation function list.

Aggregation function	Construction with summation $\text{sum}(v)$
Count: $\text{count}(v)$	The value of each individual is $\mathrm{1}$
Average: $\text{avg}(v)$	$\text{sum}(v)/\text{count}(v)$
Standard deviation: $\text{std}(v)$	$\sqrt{\text{avg}(v^{\mathrm{2}})-\text{avg}(v{)}^{\mathrm{2}}}$

There are two parties threatening the individual privacy. One is the server, who would get the individual data by aggregation. The other is the eavesdropper, who could capture the packets from the participants to the server. Both of them (named attacker) can get the individual value, which is regarded as the individual privacy.

To protect the individual privacy in the process of aggregating statistics, user $u_i$ adds random noise $\hspace{0.17em}\hspace{0.17em}{z}_i$ into his/her true value $\hspace{0.17em}\hspace{0.17em}{x}_i$ . Instead of $x_i$ , $u_i$ contributes the perturbed value $\hspace{0.17em}\hspace{0.17em}{y}_i=x_i+z_i$ to the server. The information that the attacker knows most is all the perturbed values and the scheme by which the noise is generated. So we suppose the attacker knows $y_i$ and the distributions of $y_i$ and $z_i$ . He tries to get $x_i$ based on the information he knows. The aim of the noise is to prevent the attacker from getting the accurate true value.

Obviously different noise distributions have different privacy protection capability. To protect the true value, how to choose a good noise distribution is the key issue. Noise $Z_i$ is a random variable with the probability density function (pdf) $f_{Z_i}$ . To meet the requirements of accuracy and privacy, $f_{Z_i}$ should satisfy

• (1)

accuracy requirement; the difference of $\sum Y_i$ and $\sum X_i$ is small;

(2)

privacy requirement; the confusion of the true value is evident.

The first requirement guarantees that the aggregate result does not deviate from the true result too much. The second one guarantees the individual privacy is not violated. If the attacker gets the user's value, he still doubts it because of the existence of noise.

3.2.1. Accuracy Measurement

For accuracy requirement, we define the difference

$$\begin{array}{cc}& M_n={\displaystyle \sum }_{i=\mathrm{1}}^n{Y}_i-{\displaystyle \sum }_{i=\mathrm{1}}^n{X}_i={\displaystyle \sum }_{i=\mathrm{1}}^n{Z}_i,\end{array}$$

(1)

where n is the number of participants. Ideally $M_n$ is constantly equal to zero, but it is impossible. Due to the fact that $Z_{\mathrm{1}},\dots ,Z_n$ are random variables, $M_n$ also is a random variable, with the expectation $E(M_n)$ and the variance $D(M_n)$ . $Z_{\mathrm{1}},Z_{\mathrm{2}},\dots ,Z_n$ are independent, where $Z_i$ has the expectation ${\mu }_{Z_i}$ and the variance ${\sigma }_{Z_i}^{\mathrm{2}}$ , respectively. If they satisfy Lindeberg's condition [20], $M_n$ obeys Gaussian distribution regardless of the distributions of individual noise. It is only decided by the expectation and the variance; that is, $E(M_n)={\sum }_{i=\mathrm{1}}^n{\mu }_{Z_i}$ and $D(M_n)={\sum }_{i=\mathrm{1}}^n{\sigma }_{Z_i}^{\mathrm{2}}$ . We try to keep $M_n$ small with high probability. It requires $E(M_n)=\mathrm{0}$ and $D(M_n)$ is small. Therefore, we quantify the accuracy requirement $\hspace{0.17em}\hspace{0.17em}U$ as

$$\begin{array}{cc}& U=\frac{D\left(M_n\right)}{n}=\frac{\mathrm{1}}{n}{\displaystyle \sum }_{i=\mathrm{1}}^n{\sigma }_{Z_i}^{\mathrm{2}},\end{array}$$

(2)

with an additional condition $E(M_n)=\mathrm{0}$ . It measures the average deviation tolerance of the perturbed result from the true result. Suppose that $Z_{\mathrm{1}},\dots ,Z_n$ are independent and identically distributed random variables with the expectation ${\mu }_Z$ and the variance ${\sigma }_Z^{\mathrm{2}}$ . The accuracy requirement U is simplified as

$$\begin{array}{cc}& U={\sigma }_Z^{\mathrm{2}},\end{array}$$

(3)

with ${\mu }_Z=\mathrm{0}$ .

U measures the average deviation tolerance of the perturbed result from the true result by the variance of the noise distribution. If two zero-mean noise distribution $f_{Z_i}$ and $f_{Z_j}$ satisfy $U_i<U_j$ , it means that $f_{Z_i}$ guarantees the accuracy of result better.

3.2.2. Privacy Measurement

Consider

$$\begin{array}{cc}& Y=X+Z,\end{array}$$

(4)

where Y, X, and Z are random variables which delegate perturbed value, true value, and noise, respectively. Z is independent of X. Suppose that the adversary knows the distribution of Z. It is reasonable that any user including malicious user knows it to generate noise. Because of the perturbation of noise z, the adversary is uncertain about x when he gets y. We use Shannon's information entropy to measure the uncertainty. Suppose that the adversary gets $Y=y$ , the uncertainty of X is measured by $H(X\mid Y=y)=-{\sum }_x{P}_{X\mid Y}(x\mid y)\log P_{X\mid Y}(x\mid y)$ . The larger $H(X\mid Y=y)$ is, the better the privacy protection is provided at $Y=y$ .

For different y, $H(X\mid Y=y)$ is different. We use the average $H(X\mid Y=y)$ to quantify the privacy protection strength (denoted by V) of the noise; that is,

$$\begin{array}{cc}& V={\displaystyle \sum }_{y}H\left(X\mid Y=y\right)P_Y\left(y\right)=H\left(X\mid Y\right).\end{array}$$

(5)

$H(X\mid Y)$ denotes the average uncertainty of the true value when the perturbed value is captured. The larger V is, the higher the average uncertainty is.

Generally speaking, for noise addition technology, the accuracy and the privacy are in contradiction. High accuracy leads to low privacy protection strength, and vice versa. However, for a given accuracy level, different $f_Z$ usually has different privacy protection capability. Thus how to optimize the noise distribution that provides the best privacy protection under the accuracy constraint is the key problem.

3.3. Optimization Problem Formulation

For convenience, in the following we consider the continuous distributions. The discrete distribution can be regarded as the approximation of the corresponding continuous distribution. Consider the formulation $Y=X+Z$ , where X and Z are random variables with pdf $f_X(x)$ and pdf $\hspace{0.17em}\hspace{0.17em}{f}_Z(z)$ , respectively. We will find the optimal $f_Z$ providing the best privacy protection while guaranteeing that the result has an acceptable deviation; that is, ${\max }_{f_Z(z)}V=H(X\mid Y)$ . Consider the optimization problem

$$\begin{array}{l}\underset{f_Z\left(z\right)}{\max }\phantom{vv}V=H\left(X\mid Y\right)\\ \text{s}.\text{t}.\phantom{\text{vv}}\mathrm{\hspace{0.17em}\hspace{0.17em}}U={\sigma }_Z^{\mathrm{2}}⩽{\sigma }_m^{\mathrm{2}}\\ \phantom{vvvvv}E\left(Z\right)=\mathrm{0},\end{array}$$

(6)

where ${\sigma }_m^{\mathrm{2}}$ is the accuracy requirement bound required by applications.

Consider

$$\begin{array}{cc}& H\left(X\mid Y\right)=H\left(X\right)-I(X;Y).\end{array}$$

(7)

Since $f_X(x)$ is deterministic, $H(X)$ is a constant. Thus the optimization problem is translated to

$$\begin{array}{l}\underset{f_Z\left(z\right)}{\min }\phantom{viv}I(X;Y)\\ \text{s}.\text{t}.\mathrm{\hspace{0.17em}\hspace{0.17em}}\phantom{\text{v}}{\displaystyle \int }{f}_Z\left(z\right)z^{\mathrm{2}}dz⩽{\sigma }_m^{\mathrm{2}}\\ \phantom{s.t.\mathrm{\hspace{0.17em}\hspace{0.17em}}\phantom{\text{v}}}{\displaystyle \int }{f}_Z\left(z\right)z\hspace{0.17em}dz=\mathrm{0}\\ \phantom{s.t.\mathrm{\hspace{0.17em}\hspace{0.17em}}\phantom{\text{v}}}{\displaystyle \int }{f}_Z\left(z\right)dz=\mathrm{1}.\end{array}$$

(8)

4. Problem Solution

To solve the problem proposed in the above section, firstly we investigate the general solution. Then for the special case that the original data obeys Gaussian distribution, the further result is shown.

4.1. General Solution

To solve problem (8), firstly we consider a more general problem

$$\begin{array}{l}\underset{f_{Y\mid X}\left(y\mid x\right)}{\min }\phantom{vvv}I(X;Y)\\ \mathrm{\hspace{0.17em}\hspace{0.17em}}\phantom{\text{v}}\text{s}.\text{t}.\phantom{\mathrm{\hspace{0.17em}\hspace{0.17em}}\text{vv}}{\displaystyle \int }{\displaystyle \int }{f}_X\left(x\right)f_{Y\mid X}\left(y\mid x\right){\left(y-x\right)}^{\mathrm{2}}dx\hspace{0.17em}dy⩽{\sigma }_m^{\mathrm{2}}\\ \phantom{s.t.\mathrm{\hspace{0.17em}\hspace{0.17em}}\text{vvivv}}{\displaystyle \int }{f}_{Y\mid X}\left(y\mid x\right)\left(y-x\right)dy=\mathrm{0}\\ \phantom{s.t.\mathrm{\hspace{0.17em}\hspace{0.17em}}\text{vvivv}}{\displaystyle \int }{f}_{Y\mid X}\left(y\mid x\right)dy=\mathrm{1},\end{array}$$

(9)

where $Y=Z+X$ . If Z is independent of X, we have

$$\begin{array}{cc}& f_{Y\mid X}\left(y\mid x\right)=f_{Y-X\mid X}(y-x\mid x)=f_{Z\mid X}\left(z\mid x\right)=f_Z\left(z\right).\end{array}$$

(10)

The constraints become

$$\begin{array}{cc}& {\displaystyle \int }{\displaystyle \int }{f}_X\left(x\right)f_{Y|X}\left(y\mid x\right){\left(y-x\right)}^{\mathrm{2}}dx\hspace{0.17em}dy={\displaystyle \int }{f}_Z\left(z\right)z^{\mathrm{2}}dz\\ {\displaystyle \int }{f}_X\left(x\right)f_{Y\mid X}\left(y\mid x\right)(y-x)dy={\displaystyle \int }{f}_Z\left(z\right)z\hspace{0.17em}dz\\ {\displaystyle \int }{f}_{Y\mid X}\left(y\mid x\right)dy={\displaystyle \int }{f}_Z\left(z\right)dz.\end{array}$$

(11)

This problem is translated to problem (8). In other words, the problem (8) is a special case of problem (9).

The mutual information $I(X;Y)$ is

$$\begin{array}{l}I\left(X;Y\right)={\displaystyle \int }{\displaystyle \int }{f}_{X,Y}\left(x,y\right)\log \frac{f_{X,Y}\left(x,y\right)}{f_X\left(x\right)f_Y\left(y\right)}dx\hspace{0.17em}dy\\ ={\displaystyle \int }{\displaystyle \int }{f}_X\left(x\right)f_{Y\mid X}\left(y\mid x\right)\log \frac{f_{Y\mid X}\left(y\mid x\right)}{f_Y\left(y\right)}dx\hspace{0.17em}dy,\end{array}$$

(12)

where $f_Y(y)={\int }_X‍f_X(x)f_{Y\mid X}(y\mid x)dx$ .

We use the method of Lagrange multipliers to find the solution. Set up the functional

$$\begin{array}{l}J={\displaystyle \int }{\displaystyle \int }{f}_X\left(x\right)f_{Y\mid X}\left(y\mid x\right)\log \frac{f_{Y\mid X}\left(y\mid x\right)}{f_Y\left(y\right)}dy\hspace{0.17em}dx\\ \hspace{1em}+\lambda {\displaystyle \int }{\displaystyle \int }{f}_X\left(x\right)f_{Y\mid X}\left(y\mid x\right){\left(y-x\right)}^{\mathrm{2}}dy\hspace{0.17em}dx\\ \hspace{1em}+{\displaystyle \int }u\left(x\right){\displaystyle \int }{f}_{Y\mid X}\left(y\mid x\right)\left(y-x\right)dy\hspace{0.17em}dx\\ \hspace{1em}+{\displaystyle \int }v\left(x\right){\displaystyle \int }{f}_{Y\mid X}\left(y\mid x\right)dy\hspace{0.17em}dx.\end{array}$$

(13)

Differentiating with respect to $f_{Y\mid X}(y\mid x)$ , we have

$$\begin{array}{l}\frac{\partial J}{\partial f_{Y\mid X}\left(y\mid x\right)}\\ \hspace{1em}=f_X\left(x\right)\log \frac{f_{Y\mid X}\left(y\mid x\right)}{f_Y\left(y\right)}+f_X\left(x\right)\mathrm{\hspace{0.17em}\hspace{0.17em}}\\ \hspace{1em}\hspace{1em}-{\displaystyle \int }‍f_X\left(x^{\prime }\right)f_{Y\mid X}\left(y\mid x^{\prime }\right)\frac{\mathrm{1}}{f_Y\left(y\right)}{f}_X\left(x\right)d{x}^{\prime }\\ \hspace{1em}\hspace{1em}+\lambda f_X\left(x\right){\left(y-x\right)}^{\mathrm{2}}+u\left(x\right)(y-x)+v\left(x\right)\\ \hspace{1em}=f_X\left(x\right)\log \frac{f_{Y\mid X}\left(y\mid x\right)}{f_Y\left(y\right)}+\lambda f_X\left(x\right){\left(y-x\right)}^{\mathrm{2}}\\ \hspace{1em}\hspace{1em}+u\left(x\right)(y-x)+v\left(x\right)\\ \hspace{1em}=\mathrm{0}.\end{array}$$

(14)

Setting $\omega (x)=u(x)/f_X(x)$ and $\tau (x)=v(x)/f_X(x)$ ,

$$\begin{array}{l}{f}_X\left(x\right)[\log \frac{f_{Y\mid X}\left(y\mid x\right)}{f_Y\left(y\right)}+\lambda {\left(y-x\right)}^{\mathrm{2}}\\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}+\omega \left(x\right)\left(y-x\right)+\tau \left(x\right)\phantom{\frac{f_{Y\mid X}\left(yx\right)}{f_Y\left(y\right)}}]=\mathrm{0}.\end{array}$$

(15)

Thus

$$\begin{array}{cc}& f_{Y\mid X}\left(y\mid x\right)=f_Y\left(y\right)e^{-\lambda {\left(y-x\right)}^{\mathrm{2}}-\omega \left(x\right)(y-x)-\tau \left(x\right)}.\end{array}$$

(16)

Here we get the expression of $f_{Y\mid X}(y\mid x)$ . In problem (8), $Y=X+Z$ and Z is independent of X. From (16),

$$\begin{array}{cc}& f_Z\left(z\right)=f_Y(x+z)e^{-\lambda z^{\mathrm{2}}-\omega \left(x\right)z-\tau \left(x\right)}.\end{array}$$

(17)

Z and X are independent; for any x, $f_Z(z)$ is unchangeable. $f_Z(z)$ can be calculated by fixing x (e.g., $x=\mathrm{0}$ ). So $f_Z(z)$ is simplified as $f_Z(z)=f_Y(z)e^{-\lambda z^{\mathrm{2}}-\omega (\mathrm{0})z-\tau (\mathrm{0})}$ , where λ, $\omega (\mathrm{0})$ , and $\tau (\mathrm{0})$ are constants for fixed $f_X$ . For convenience, $\omega (\mathrm{0})$ and $e^{-\tau (\mathrm{0})}$ are abbreviated as ω and C. Therefore, we have the following theorem.

Theorem 1.

Given the accuracy requirement ${\sigma }_m^{\mathrm{2}}$ , the noise providing the best privacy protection has the pdf

$$\begin{array}{cc}& f_Z\left(z\right)=C{f}_Y\left(z\right)e^{-\lambda z^{\mathrm{2}}-\omega z},\end{array}$$

(18)

where $f_Y(z)=\int ‍f_X(x)f_Z(z-x)dx$ , and λ, ω, and C are related to the constraints $\int ‍f_Z(z)z^{\mathrm{2}}dz={\sigma }_m^{\mathrm{2}}$ , $\int ‍f_Z(z)z\hspace{0.17em}dz=\mathrm{0}$ , and $\int ‍f_Z(z)dz=\mathrm{1}$ , respectively.

Based on the theorem the corresponding system diagram is constructed in Figure 1, where $f_X$ is the input and $f_Z$ is the output. The system contains two operations. One is convolution of the input and the output. The other is multiplication of the convolution result and the factor “ $C{e}^{-\lambda z^{\mathrm{2}}-\omega z}$ .”

Figure 1

The system diagram.

From the theorem and system diagram, the optimal noise distribution is determined by the distribution of the original value. Therefore, for different aggregation application, the optimal noise distribution may be different.

$I(X;Y)$ is a convex function of $f_{Y\mid X}(y\mid x)$ in problem (9) [21], so problem (8) also is a convex optimization problem. The constraints satisfy the sufficient conditions of KKT approach (inequality constraint is a continuously differentiable convex function; the equality constraints are affine functions [22]). If we find one $f_Z$ satisfying (18), it is the global optimal solution. So given the distribution of original value $f_X$ , we only try to find a solution for (18), that is, the optimal noise distribution.

4.2. Gaussian Distribution Input

Generally for different input $f_X(x)$ , the output $f_Z(z)$ is different. We consider a special but popular case that X follows Gaussian distribution.

When $X~N({\mu }_X,{\sigma }_X^{\mathrm{2}})$ , it is easy to check that $Z~N(\mathrm{0},{\sigma }_m^{\mathrm{2}})$ is a solution of (18), where

$$\begin{array}{cc}& \lambda =\frac{\mathrm{1}}{\mathrm{2}}(\frac{\mathrm{1}}{{\sigma }_m^{\mathrm{2}}}-\frac{\mathrm{1}}{{\sigma }_m^{\mathrm{2}}+{\sigma }_X^{\mathrm{2}}}),\\ \omega =\frac{{\mu }_X}{{\sigma }_m^{\mathrm{2}}+{\sigma }_X^{\mathrm{2}}},\\ C=\sqrt{\frac{{\sigma }_m^{\mathrm{2}}}{{\sigma }_m^{\mathrm{2}}+{\sigma }_X^{\mathrm{2}}}}·e^{-\left({\mu }_X^{\mathrm{2}}/\mathrm{2}\left({\sigma }_m^{\mathrm{2}}+{\sigma }_X^{\mathrm{2}}\right)\right)}.\end{array}$$

(19)

Thus $f_Z(z)=(\mathrm{1}/{\sigma }_m)\varphi (z/{\sigma }_m)$ is the solution of problem (8), where $\varphi (x)=(\mathrm{1}/\sqrt{\mathrm{2}\pi })e^{-(x^{\mathrm{2}}/\mathrm{2})}$ . Therefore we have the following theorem.

Theorem 2.

When X obeys Gaussian distribution, the noise which obeys Gaussian distribution with the expectation $\mathrm{0}$ and the variance ${\sigma }_m^{\mathrm{2}}$ protects the individual privacy best.

5. Truncated Gaussian Distribution Input

In practice, X usually has maximum and minimum bounds. For example, the person's height has a maximum bound and is not less than $\mathrm{0}$ . The examination score usually is in $[\mathrm{0,100}]$ . So we consider the truncated Gaussian distribution in the range $[a,b]$ . In Section 5.1 we investigate the condition that the truncated Gaussian distribution can be approximated by Gaussian distribution, so that Theorem 2 can be applied directly. In Section 5.2 we revise the condition, making it much more accurate. However, not all the truncated Gaussian distribution can be approximated by Gaussian distribution. In Section 5.3, for the arbitrary truncated Gaussian distribution we find Gaussian distribution still is a nearly optimal noise distribution.

5.1. Approximation Condition

We use the metric $ℐ(f,\widehat{f})$ [15] to measure the difference of two distributions, where

$$\begin{array}{cc}& ℐ(f,\widehat{f})=\frac{\mathrm{1}}{\mathrm{2}}{\displaystyle \int }\left|f\left(x\right)-\widehat{f}\left(x\right)\right|dx.\end{array}$$

(20)

This difference metric measures the overlap of the two distributions, which lies in the interval $[\mathrm{0,1}]$ . The smaller $ℐ(f,\widehat{f})$ is, the more overlap the two distributions have, and the more similar they are. $ℐ(f,\widehat{f})=\mathrm{0}$ implies that the two distributions are exactly the same, while $ℐ(f,\widehat{f})=\mathrm{1}$ means there is no overlap between them.

Suppose $G(x)=(\mathrm{1}/\sigma )\varphi ((x-\mu )/\sigma )$ . $T(x)$ is a pdf of the truncated Gaussian distribution over $[a,b]$ ; that is,

$$\begin{array}{cc}& T\left(x\right)=\frac{\left(\mathrm{1}/\sigma \right)\varphi \left(\left(x-\mu \right)/\sigma \right)}{\mathrm{\Phi }\left(\left(b-\mu \right)/\sigma \right)-\mathrm{\Phi }\left(\left(a-\mu \right)/\sigma \right)},\end{array}$$

(21)

where $\mathrm{\Phi }(·)$ is the cumulative distribution function of the standard normal distribution.

When $ℐ(T,G)⩽\eta$ , $T(x)$ can be approximated by $G(x)$ , where

$$\begin{array}{l}ℐ\left(T,G\right)\\ \hspace{1em}=\frac{\mathrm{1}}{\mathrm{2}}{{\displaystyle \int }}_a^b\left|T\left(x\right)-G\left(x\right)\right|dx+\frac{\mathrm{1}}{\mathrm{2}}{{\displaystyle \int }}_{-\infty }^{a}G\left(x\right)dx\\ \hspace{1em}\hspace{1em}+\frac{\mathrm{1}}{\mathrm{2}}{{\displaystyle \int }}_b^{\infty }G\left(x\right)dx\\ \hspace{1em}=\frac{\mathrm{1}}{\mathrm{2}}{{\displaystyle \int }}_a^b\frac{\mathrm{1}}{\sigma }\varphi \left(\frac{x-\mu }{\sigma }\right)\\ \hspace{1em}\hspace{1em}\times \left(\frac{\mathrm{1}}{\mathrm{\Phi }\left((b-\mu )/\sigma \right)-\mathrm{\Phi }\left((a-\mu )/\sigma \right)}-\mathrm{1}\right)dx\\ \hspace{1em}\hspace{1em}+\frac{\mathrm{1}}{\mathrm{2}}\mathrm{\Phi }\left(\frac{a-\mu }{\sigma }\right)+\frac{\mathrm{1}}{\mathrm{2}}\mathrm{\Phi }\left(\frac{\mu -b}{\sigma }\right)\\ \hspace{1em}=\frac{\mathrm{1}}{\mathrm{2}}\left(\mathrm{1}-\mathrm{\Phi }\left(\frac{b-\mu }{\sigma }\right)+\mathrm{\Phi }\left(\frac{a-\mu }{\sigma }\right)\right)+\frac{\mathrm{1}}{\mathrm{2}}\mathrm{\Phi }\left(\frac{a-\mu }{\sigma }\right)\\ \hspace{1em}\hspace{1em}+\frac{\mathrm{1}}{\mathrm{2}}\mathrm{\Phi }\left(\frac{\mu -b}{\sigma }\right)\\ \hspace{1em}=\mathrm{\Phi }\left(\frac{a-\mu }{\sigma }\right)+\mathrm{\Phi }\left(\frac{\mu -b}{\sigma }\right).\end{array}$$

(22)

This metric is equivalent to Kullback-Leibler divergence $D_{\text{KL}}(T\parallel G)$ , where

$$\begin{array}{l}{D}_{\text{KL}}\left(T\parallel G\right)\\ \hspace{1em}={{\displaystyle \int }}_{-\infty }^{+\infty }T\left(x\right)\log \frac{T\left(x\right)}{G\left(x\right)}dx\\ \hspace{1em}={{\displaystyle \int }}_a^{b}T\left(x\right)\log \frac{\mathrm{1}}{\mathrm{\Phi }\left((b-\mu )/\sigma \right)-\mathrm{\Phi }\left(\left(a-\mu \right)/\sigma \right)}dx\\ \hspace{1em}=-\log \left[\mathrm{1}-\left(\mathrm{\Phi }\left(\frac{a-\mu }{\sigma }\right)+\mathrm{\Phi }\left(\frac{\mu -b}{\sigma }\right)\right)\right]\\ \hspace{1em}=-\log \left(\mathrm{1}-ℐ\left(T,G\right)\right).\end{array}$$

(23)

$D_{\text{KL}}(T\parallel G)$ is the increasing function of $ℐ(T,G)$ , so the two metrics are the same.

Since $ℐ(T,G)⩽\eta$ , we have $\mathrm{0}⩽\mathrm{\Phi }((a-\mu )/\sigma )⩽\eta$ and $\mathrm{0}⩽\mathrm{\Phi }((\mu -b)/\sigma )⩽\eta -\mathrm{\Phi }((a-\mu )/\sigma )$ . So $[a,b]$ satisfies

$$\begin{array}{cc}& a⩽\mu +\sigma {\mathrm{\Phi }}^{-\mathrm{1}}\left(\eta \right),\\ b⩾\mu -\sigma {\mathrm{\Phi }}^{-\mathrm{1}}\left(\eta -\mathrm{\Phi }\left(\frac{a-\mu }{\sigma }\right)\right).\end{array}$$

(24)

Given $x<\mathrm{0}$ , there is lower and upper bounds for $\mathrm{\Phi }(x)$ , that is, $-(x/(\mathrm{1}+x^{\mathrm{2}}))·(\mathrm{1}/\sqrt{\mathrm{2}\pi })e^{(-x^{\mathrm{2}}/\mathrm{2})}$   <   $\mathrm{\Phi }(x)<-(\mathrm{1}/x)·(\mathrm{1}/\sqrt{\mathrm{2}\pi })e^{(-x^{\mathrm{2}}/\mathrm{2})}$ . When $x^{\mathrm{2}}\gg \mathrm{1}$ , $\mathrm{\Phi }(x)\approx -(\mathrm{1}/x)·(\mathrm{1}/\sqrt{\mathrm{2}\pi })e^{(-x^{\mathrm{2}}/\mathrm{2})}$ . Thus

$$\begin{array}{cc}& \log \mathrm{\Phi }\left(x\right)=-\frac{\mathrm{1}}{\mathrm{2}}{x}^{\mathrm{2}}-\log (-x)-\frac{\mathrm{1}}{\mathrm{2}}\log \mathrm{2}\pi .\end{array}$$

(25)

When $x\ll \mathrm{0}$ , $x^{\mathrm{2}}\gg \log (-x)$ . So

$$\begin{array}{cc}& x=-\sqrt{\log \frac{\mathrm{1}}{\mathrm{2}\pi {\mathrm{\Phi }}^{\mathrm{2}}\left(x\right)}}.\end{array}$$

(26)

Therefore, given the bound of the difference metric $\eta \to \mathrm{0}$ , ${\mathrm{\Phi }}^{-\mathrm{1}}(\eta )\ll \mathrm{0}$ . For (24) and (26), the range $[a,b]$ satisfies

$$\begin{array}{l}a⩽\mu -\sigma \sqrt{\log \frac{\mathrm{1}}{\mathrm{2}\pi {\eta }^{\mathrm{2}}}},\\ b⩾\mu +\sqrt{{\left(a-\mu \right)}^{\mathrm{2}}-\mathrm{2}{\sigma }^{\mathrm{2}}\log \left(e^{-\left(\mathrm{1}/\mathrm{2}\right)\left[{\left({\mathrm{\Phi }}^{-\mathrm{1}}\left(\eta \right)\right)}^{\mathrm{2}}-{\left(\left(a-\mu \right)/\sigma \right)}^{\mathrm{2}}\right]}-\mathrm{1}\right)}\\ =\mu +\sigma \sqrt{\mathrm{2}\log \frac{\mathrm{1}}{\sqrt{\mathrm{2}\pi }\eta -e^{-\left(\mathrm{1}/\mathrm{2}\right){\left((a-\mu )/\sigma \right)}^{\mathrm{2}}}}}.\end{array}$$

(27)

If $ℐ(T,G)=\eta$ , the length of $[a,b]$ is

$$\begin{array}{l}{L}_{\eta }=\left|b-a\right|⩽\sigma \sqrt{\mathrm{2}\log \frac{\mathrm{1}}{\sqrt{\mathrm{2}\pi }\eta -e^{-\left(\mathrm{1}/\mathrm{2}\right){\left((a-\mu )/\sigma \right)}^{\mathrm{2}}}}}\\ \hspace{1em}\hspace{1em}+\sigma \sqrt{\log \frac{\mathrm{1}}{\mathrm{2}\pi {\eta }^{\mathrm{2}}}}.\end{array}$$

(28)

For a fixed η, from $\partial L_{\eta }/\partial a=\mathrm{0}$ , we get the minimum $L_{\eta }$ as

$$\begin{array}{cc}& \min L_{\eta }=\mathrm{2}\sigma \sqrt{\log \frac{\mathrm{2}}{\pi {\eta }^{\mathrm{2}}}}=\mathrm{2}\left(\mu -a\right),\end{array}$$

(29)

where

$$\begin{array}{cc}& a⩽\mu -\sigma \sqrt{\log \frac{\mathrm{2}}{\pi {\eta }^{\mathrm{2}}}},\\ b⩾\mu +\sigma \sqrt{\log \frac{\mathrm{2}}{\pi {\eta }^{\mathrm{2}}}}.\end{array}$$

(30)

In this case $\mu =(b\hspace{0.17em}+\hspace{0.17em}a)/\mathrm{2}$ . The expectation and the variance of $T(x)$ are

$$\begin{array}{l}{E}_T\left(X\right)=\mu +\sigma \frac{\varphi \left((a-\mu )/\sigma \right)-\varphi \left((b-\mu )/\sigma \right)}{\mathrm{\Phi }\left((b-\mu )/\sigma \right)-\mathrm{\Phi }\left(\left(a-\mu \right)/\sigma \right)}=\mu ,\\ D_T\left(X\right)\\ \hspace{1em}={\sigma }^{\mathrm{2}}(\phantom{\frac{\varphi \left((a-\mu )/\sigma \right)-\varphi \left((b-\mu )/\sigma \right)}{\mathrm{\Phi }\left((b-\mu )/\sigma \right)-\mathrm{\Phi }\left((a-\mu )/\sigma \right)}}\mathrm{1}+\left(\frac{a-\mu }{\sigma }\varphi \left(\frac{a-\mu }{\sigma }\right)-\frac{b-\mu }{\sigma }\varphi \left(\frac{b-\mu }{\sigma }\right)\right)\\ \hspace{1em}\hspace{1em}\phantom{\mathrm{1}+\mathrm{1}+\mathrm{1}+}\times {\left(\mathrm{\Phi }\left(\frac{b-\mu }{\sigma }\right)-\mathrm{\Phi }\left(\frac{a-\mu }{\sigma }\right)\right)}^{-1}\\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}-{\left(\frac{\varphi \left(\left(a-\mu \right)/\sigma \right)-\varphi \left(\right(b-\mu )/\sigma )}{\mathrm{\Phi }\left(\left(b-\mu \right)/\sigma \right)-\mathrm{\Phi }(\left(a-\mu )/\sigma \right)}\right)}^{\mathrm{2}})\\ \hspace{1em}={\sigma }^{\mathrm{2}}\left(\mathrm{1}-\sqrt{\log \frac{\mathrm{2}}{\pi {\eta }^{\mathrm{2}}}}\frac{\eta }{\mathrm{1}-\eta }\right).\end{array}$$

(31)

Since ${\lim }_{\eta \to \mathrm{0}}\sqrt{\log (\mathrm{2}/\pi {\eta }^{\mathrm{2}})}(\eta /(\mathrm{1}-\eta ))=\mathrm{0}$ , $D_T(X)={\sigma }^{\mathrm{2}}$ .

Therefore, given the difference bound $\eta \to \mathrm{0}$ , if the range $[a,b]$ of $T(x)$ follows the condition (27), $T(x)$ can be approximated by $G(x)=(\mathrm{1}/\sigma )\varphi ((x-\mu )/\sigma )$ . The corresponding optimal noise distribution is Gaussian distribution. In particular, if $\mu =(b+a)/\mathrm{2}$ , the condition can be simplified as (30).

By the analysis in this section, for an aggregation application where the original value obeys the truncated Gaussian distribution, if the distribution satisfies condition (27) or (30), it can be approximated by Gaussian distribution, where Theorem 2 can be used directly.

5.2. Approximation Amendment

From the analysis of Section 5.1, when $L_{\eta }$ reaches the minimum, $|b-\mu |=|a-\mu |=(\mathrm{1}/\mathrm{2})|b-a|$ . Thus the exact $\min L_{\eta }$ (calculated by (24)) is

$$\begin{array}{cc}& \min L_{\eta }=-\mathrm{2}\sigma {\mathrm{\Phi }}^{-\mathrm{1}}\left(\frac{\mathrm{1}}{\mathrm{2}}\eta \right).\end{array}$$

(32)

Equation (29) is the approximate $\min L_{\eta }$ , from which $\min L_{\eta }/\mathrm{2}\sigma =\left|a-\mu \right|/\sigma$ . Figure 2 shows the relationship between minimum length of $[a,b]$ and η. The smaller η is, the larger $\min L_{\eta }/\mathrm{2}\sigma$ is. However, from the figure biases exist between the approximate method and the exact one. The reason is that (29) is based on (26), which contains the approximation that ${(\min L_{\eta }/\mathrm{2}\sigma )}^{\mathrm{2}}\gg \log (\min L_{\eta }/\mathrm{2}\sigma )$ . However, in practice the difference is not large enough, so the bias exists.

Figure 2

The ratio of minimum length of $[a,b]$ to $\mathrm{2}\sigma$ for difference bound η before amendment.

In order to reduce the bias, we revise the condition. Based on (32) without the above approximation, from (25) we have

$$\begin{array}{cc}& {\left(\min \frac{L_{\eta }}{\mathrm{2}\sigma }\right)}_{\mathrm{1}}^{\mathrm{2}}+\mathrm{2}\log \left({\left(\min \frac{L_{\eta }}{\mathrm{2}\sigma }\right)}_{\mathrm{1}}\right)=\log \frac{\mathrm{2}}{\pi {\eta }^{\mathrm{2}}}.\end{array}$$

(33)

In (29), $\min L_{\eta }/\mathrm{2}\sigma$ satisfies

$$\begin{array}{cc}& {\left(\min \frac{L_{\eta }}{\mathrm{2}\sigma }\right)}_{\mathrm{2}}^{\mathrm{2}}=\log \frac{\mathrm{2}}{\pi {\eta }^{\mathrm{2}}}.\end{array}$$

(34)

Here, ${(\min L_{\eta }/\mathrm{2}\sigma )}_{\mathrm{1}}$ and ${(\min L_{\eta }/\mathrm{2}\sigma )}_{\mathrm{2}}$ are exact value and approximate value, respectively. Consider $\eta \in [\mathrm{0.0001,0.05}]$ (which is reasonable that if η is too large, the approximation using normal distribution is useless, while if η is too small, it is hard to find out such a $T(x)$ in practice), $\log (\mathrm{2}/\pi {\eta }^{\mathrm{2}})$ is in the range $[\mathrm{5.54,18.00}]$ . Thus ${(\min L_{\eta }/\mathrm{2}\sigma )}_{\mathrm{2}}-{(\min L_{\eta }/\mathrm{2}\sigma )}_{\mathrm{1}}$ is in the range $[\mathrm{0.32,0.33}]$ . Thus (29) can be revised as

$$\begin{array}{cc}& \min L_{\eta }=\mathrm{2}\sigma \left(\sqrt{\log \frac{\mathrm{2}}{\pi {\eta }^{\mathrm{2}}}}-\mathrm{0.33}\right)\end{array}$$

(35)

and constraint (30) is revised as

$$\begin{array}{cc}& a⩽\mu -\sigma \left(\sqrt{\log \frac{\mathrm{2}}{\pi {\eta }^{\mathrm{2}}}}-\mathrm{0.33}\right),\\ b⩾\mu +\sigma \left(\sqrt{\log \frac{\mathrm{2}}{\pi {\eta }^{\mathrm{2}}}}-\mathrm{0.33}\right).\end{array}$$

(36)

The effect of revision is illustrated in Figure 3, where approximate result is almost the same as the exact one.

Figure 3

The ratio of minimum length of $[a,b]$ to $\mathrm{2}\sigma$ for difference bound η after amendment.

5.3. Arbitrary Truncated Gaussian Distribution Input

In the above analysis, when the truncated Gaussian distribution can be approximated by Gaussian distribution, Theorem 2 can be used directly. However, not all the truncated Gaussian distribution can be approximated by Gaussian distribution. The truncated Gaussian distributions with the variance ${\sigma }^{\mathrm{2}}$ and the expectation $(b+a)/\mathrm{2}$ are in quite a variety of shapes, which are decided by the range $[a,b]$ , where $\mathrm{2}\sqrt{\mathrm{3}}\sigma ⩽\left|b-a\right|<+\infty$ . Specially, when $\left|b-a\right|$ converges to infinity, the truncated Gaussian distribution becomes Gaussian distribution. When $\left|b-a\right|$ equals $\mathrm{2}\sqrt{\mathrm{3}}\sigma$ , the truncated Gaussian distribution becomes homogeneous distribution. If the truncated Gaussian distribution cannot be approximated by Gaussian distribution, does $Z~N(\mathrm{0},{\sigma }_m^{\mathrm{2}})$ remain the optimal noise? Unfortunately, Gaussian distribution is not the solution of (18); that is, Gaussian distribution is not the optimal noise distribution. However, if $Z~N(\mathrm{0},{\sigma }_m^{\mathrm{2}})$ makes $I(X;Y)$ so small that the difference to the minimum $I(X;Y)$ is small enough, it is still a good choice.

Theorem 3.

Suppose that X obeys the truncated Gaussian distribution over $[a,b]$ with the variance ${\sigma }_X^{\mathrm{2}}$ and the expectation $(b+a)/\mathrm{2}$ . $\min I(X;X+Z)$ in problem (8) is only determined by $(b-a)/{\sigma }_X$ and ${\sigma }_X/{\sigma }_m$ .

Proof.

Suppose that two random variables $X_{\mathrm{1}}$ and $X_{\mathrm{2}}$ follow the truncated Gaussian distributions $T_{\mathrm{1}}$ and $T_{\mathrm{2}}$ , respectively, where $T_{\mathrm{1}}$ is over $[a_{\mathrm{1}},b_{\mathrm{1}}]$ with the variance ${\sigma }_{\mathrm{1}}^{\mathrm{2}}$ and the expectation $(b_{\mathrm{1}}+a_{\mathrm{1}})/\mathrm{2}$ , $\hspace{0.17em}\hspace{0.17em}{T}_{\mathrm{2}}$ is over $[a_{\mathrm{2}},b_{\mathrm{2}}]$ with the variance ${\sigma }_{\mathrm{2}}^{\mathrm{2}}$ and the expectation $(b_{\mathrm{2}}+a_{\mathrm{2}})/\mathrm{2}$ , and $(b_{\mathrm{1}}-a_{\mathrm{1}})/{\sigma }_{\mathrm{1}}^{\prime }=(b_{\mathrm{2}}-a_{\mathrm{2}})/{\sigma }_{\mathrm{2}}^{\prime }$ . The expectation only decides the position of the function in coordinate system. It has no effect on entropy and mutual information. For convenience, we suppose that the expectations of two functions are 0 (i.e., ${(b}_{\mathrm{2}}+a_{\mathrm{2}})/\mathrm{2}=(b_{\mathrm{1}}+a_{\mathrm{1}})/\mathrm{2}=\mathrm{0}$ ), so $b_{\mathrm{1}}/{\sigma }_{\mathrm{1}}^{\prime }=-a_{\mathrm{1}}/{\sigma }_{\mathrm{1}}^{\prime }=b_{\mathrm{2}}/{\sigma }_{\mathrm{2}}^{\prime }=-a_{\mathrm{2}}/{\sigma }_{\mathrm{2}}^{\prime }$ . Next, we will prove $\min I(X_{\mathrm{1}};X_{\mathrm{1}}+Z_{\mathrm{1}})=\min I(X_{\mathrm{2}};X_{\mathrm{2}}+Z_{\mathrm{2}})$ , where $Z_{\mathrm{1}}$ and $Z_{\mathrm{2}}$ are random variables with the variances $k{\sigma }_{\mathrm{1}}^{\mathrm{2}}$ and $k{\sigma }_{\mathrm{2}}^{\mathrm{2}}$ (k is a positive number)

$$\begin{array}{cc}& T_{\mathrm{1}}\left(x\right)=\frac{\left(\mathrm{1}/{\sigma }_{\mathrm{1}}^{\prime }\right)\varphi \left(x/{\sigma }_{\mathrm{1}}^{\prime }\right)}{\mathrm{\Phi }\left(b_{\mathrm{1}}/{\sigma }_{\mathrm{1}}^{\prime }\right)-\mathrm{\Phi }\left(a_{\mathrm{1}}/{\sigma }_{\mathrm{1}}^{\prime }\right)},\end{array}$$

(37)

$$\begin{array}{cc}& T_{\mathrm{2}}\left(x\right)=\frac{\left(\mathrm{1}/{\sigma }_{\mathrm{2}}^{\prime }\right)\varphi \left(x/{\sigma }_{\mathrm{2}}^{\prime }\right)}{\mathrm{\Phi }\left(b_{\mathrm{2}}/{\sigma }_{\mathrm{2}}^{\prime }\right)-\mathrm{\Phi }\left(a_{\mathrm{2}}/{\sigma }_{\mathrm{2}}^{\prime }\right)}.\end{array}$$

(38)

Set $c={\sigma }_{\mathrm{2}}^{\prime }/{\sigma }_{\mathrm{1}}^{\prime }$ . On one hand, for any $x_{\mathrm{1}}\in [a_{\mathrm{1}},b_{\mathrm{1}}]$ , there is $x_{\mathrm{2}}=c{x}_{\mathrm{1}}\in [a_{\mathrm{2}},b_{\mathrm{2}}]$ . On the other hand, for any $x_{\mathrm{2}}\in [a_{\mathrm{2}},b_{\mathrm{2}}]$ , there is $x_{\mathrm{1}}=(\mathrm{1}/c)x_{\mathrm{2}}\in [a_{\mathrm{1}},b_{\mathrm{1}}]$ . Thus a one-to-one mapping exists between $X_{\mathrm{1}}$ and $X_{\mathrm{2}}$ .

Consider the two functions (37) and (38). Denominators are equal to each other denoted by M. For any $x_{\mathrm{1}}$ in $[a_{\mathrm{1}},b_{\mathrm{1}}]$ and $x_{\mathrm{2}}=c{x}_{\mathrm{1}}$ ,

$$\begin{array}{cc}& T_{\mathrm{1}}\left(x_{\mathrm{1}}\right)=\frac{\mathrm{1}}{M{\sigma }_{\mathrm{1}}^{\prime }}\varphi \left(\frac{x_{\mathrm{1}}}{{\sigma }_{\mathrm{1}}^{\prime }}\right),\\ T_{\mathrm{2}}\left(x_{\mathrm{2}}\right)=\frac{\mathrm{1}}{M{\sigma }_{\mathrm{2}}^{\prime }}\varphi \left(\frac{x_{\mathrm{2}}}{{\sigma }_{\mathrm{2}}^{\prime }}\right)=\frac{\mathrm{1}}{M{\sigma }_{\mathrm{2}}^{\prime }}\varphi \left(\frac{x_{\mathrm{1}}}{{\sigma }_{\mathrm{1}}^{\prime }}\right).\end{array}$$

(39)

Thus $T_{\mathrm{2}}(x)=(\mathrm{1}/c)T_{\mathrm{1}}((\mathrm{1}/c)x)$ ,

$$\begin{array}{l}{\sigma }_{\mathrm{2}}^{\mathrm{2}}\phantom{\text{v}}={{\displaystyle \int }}_{a_{\mathrm{2}}}^{b_{\mathrm{2}}}{x}^{\mathrm{2}}{T}_{\mathrm{2}}\left(x\right)dx\\ \stackrel{x=c{x}_{\mathrm{1}}}{=}{{\displaystyle \int }}_{a_{\mathrm{1}}}^{b_{\mathrm{1}}}{c}^{\mathrm{2}}{x}_{\mathrm{1}}^{\mathrm{2}}{T}_{\mathrm{1}}\left(x_{\mathrm{1}}\right)d{x}_{\mathrm{1}}\\ \phantom{\text{v}}=c^{\mathrm{2}}{\sigma }_{\mathrm{1}}^{\mathrm{2}}.\end{array}$$

(40)

So ${\sigma }_{\mathrm{2}}/{\sigma }_{\mathrm{1}}={\sigma }_{\mathrm{2}}^{\prime }/{\sigma }_{\mathrm{1}}^{\prime }=c$ .

For any $Z_{\mathrm{1}}$ , the pdf of which is $f_{Z_{\mathrm{1}}}(z)$ with the expectation $\mathrm{0}$ and the variance ${\sigma }_{Z_{\mathrm{1}}}^{\mathrm{2}}=k{\sigma }_{\mathrm{1}}^{\mathrm{2}}$ , we can find $Z_{\mathrm{2}}$ with pdf $f_{Z_{\mathrm{2}}}(z)$ which satisfies $f_{Z_{\mathrm{2}}}(z)=(\mathrm{1}/c)f_{Z_{\mathrm{1}}}((\mathrm{1}/c)z)$ . $f_{Z_{\mathrm{2}}}(z)$ has the expectation $\mathrm{0}$ and the variance ${\sigma }_{Z_{\mathrm{2}}}^{\mathrm{2}}=c^{\mathrm{2}}{\sigma }_{Z_{\mathrm{1}}}^{\mathrm{2}}=k{\sigma }_{\mathrm{2}}^{\mathrm{2}}$ . There is a one-to-one mapping between $f_{Z_{\mathrm{1}}}(z)$ and $f_{Z_{\mathrm{2}}}(z)$ . Thus for any $Z_{\mathrm{1}}$ for $X_{\mathrm{1}}$ , we have corresponding $Z_{\mathrm{2}}$ for $X_{\mathrm{2}}$ .

The entropy satisfies

$$\begin{array}{l}h\left(Z_{\mathrm{2}}\right)=-{\displaystyle \int }{f}_{Z_{\mathrm{2}}}\left(z_{\mathrm{2}}\right)\log f_{Z_{\mathrm{2}}}\left(z_{\mathrm{2}}\right)d{z}_{\mathrm{2}}\\ =-{\displaystyle \int }c\frac{\mathrm{1}}{c}{f}_{Z_{\mathrm{1}}}\left(z_{\mathrm{1}}\right)\log \frac{\mathrm{1}}{c}{f}_{Z_{\mathrm{1}}}\left(z_{\mathrm{1}}\right)d{z}_{\mathrm{1}}\\ =h\left(Z_{\mathrm{1}}\right)+\log c.\end{array}$$

(41)

Supposing that $Y_{\mathrm{1}}=X_{\mathrm{1}}+Z_{\mathrm{1}}$ with pdf $f_{Y_{\mathrm{1}}}(y_{\mathrm{1}})$ and $Y_{\mathrm{2}}=X_{\mathrm{2}}+Z_{\mathrm{2}}$ with pdf $f_{Y_{\mathrm{2}}}(y_{\mathrm{2}})$ ,

$$\begin{array}{l}{f}_{Y_{\mathrm{2}}}\left(y\right)\phantom{\text{vv}}={\displaystyle \int }{T}_{X_{\mathrm{2}}}\left(x\right)f_{Z_{\mathrm{2}}}(y-x)dx\\ \stackrel{x_{\mathrm{1}}=\left(\mathrm{1}/c\right)x}{=}{\displaystyle \int }\frac{\mathrm{1}}{c}{T}_{X_{\mathrm{1}}}\left(x_{\mathrm{1}}\right)\frac{\mathrm{1}}{c}{f}_{Z_{\mathrm{1}}}\left(y_{\mathrm{1}}-x_{\mathrm{1}}\right)c\hspace{0.17em}d{x}_{\mathrm{1}}\\ \phantom{\text{vv}}=\frac{\mathrm{1}}{c}{\displaystyle \int }‍T_{X_{\mathrm{1}}}\left(x_{\mathrm{1}}\right)f_{Z_{\mathrm{1}}}(y_{\mathrm{1}}-x_{\mathrm{1}})d{x}_{\mathrm{1}}\\ \phantom{\text{vv}}=\frac{\mathrm{1}}{c}{f}_{Y_{\mathrm{1}}}\left(y_{\mathrm{1}}\right)\\ \phantom{\text{vv}}=\frac{\mathrm{1}}{c}{f}_{Y_{\mathrm{1}}}\left(\frac{\mathrm{1}}{c}y\right).\end{array}$$

(42)

Similarly,

$$\begin{array}{cc}& h\left(Y_{\mathrm{2}}\right)=h\left(Y_{\mathrm{1}}\right)+\log c.\end{array}$$

(43)

Since Z and X are independent,

$$\begin{array}{cc}& I(X_{\mathrm{1}};Y_{\mathrm{1}})=h\left(Y_{\mathrm{1}}\right)-h\left(Z_{\mathrm{1}}\right)=h\left(Y_{\mathrm{2}}\right)-h\left(Z_{\mathrm{2}}\right)=I(X_{\mathrm{2}};Y_{\mathrm{2}}).\end{array}$$

(44)

Suppose that $Z_{m\mathrm{1}}$ minimizes $I(X_{\mathrm{1}};Y_{\mathrm{1}}))$ ; the corresponding $Z_{m\mathrm{2}}$ minimizes $I(X_{\mathrm{2}};Y_{\mathrm{2}})$ too; otherwise we can find another $Z_{m\mathrm{1}}^{\prime }$ that makes $I(X_{\mathrm{1}};Y_{\mathrm{1}})$ smaller. In the above analysis, we only have the constraint that $(b_{\mathrm{1}}-a_{\mathrm{1}})/{\sigma }_{\mathrm{1}}=(b_{\mathrm{2}}-a_{\mathrm{2}})/{\sigma }_{\mathrm{2}}$ . In problem (8) ${\sigma }_m^{\mathrm{2}}$ actually is the variance of optimal $f_Z$ . In this proof we have an implied condition that when $Z_{m\mathrm{1}}$ satisfies the variance condition for $X_{\mathrm{1}}$ ( ${\sigma }_{m\mathrm{1}}^{\mathrm{2}}=k{\sigma }_{\mathrm{1}}^{\mathrm{2}}$ ), $Z_{m\mathrm{2}}$ satisfies it too for $X_{\mathrm{2}}$ ( ${\sigma }_{m\mathrm{2}}^{\mathrm{2}}=k{\sigma }_{\mathrm{2}}^{\mathrm{2}}$ ). Since ${\sigma }_{\mathrm{2}}/{\sigma }_{\mathrm{1}}=c={\sigma }_{Z_{m\mathrm{2}}}/{\sigma }_{Z_{m\mathrm{1}}}$ , ${\sigma }_{\mathrm{2}}/{\sigma }_{Z_{m\mathrm{2}}}={\sigma }_{\mathrm{1}}/{\sigma }_{Z_{m\mathrm{1}}}$ . Therefore when $(b-a)/{\sigma }_X$ and ${\sigma }_X/{\sigma }_m$ are fixed, the minimum of $I(X;Y)$ is a constant.

From Theorem 3 the optimal solution is only determined by $(b-a)$ , ${\sigma }_X$ , and ${\sigma }_m$ . To see the performance that noise obeys Gaussian distribution, the difference between $\min I(X;X+Z)$ and $I(X;X+Z_G)$ is shown in Figure 4, where $Z_G$ obeys Gaussian distribution. From the figure, we find that although Gaussian distribution is not the optimal noise distribution, the deviation to the optimal solution is small. In particular, when $(b-a)/\mathrm{2}{\sigma }_X$ is larger than $\mathrm{3}$ , the bias is very close to $\mathrm{0}$ . For example, when $(b-a)/\mathrm{2}{\sigma }_X$ is $\mathrm{3.05}$ , $I(X;X+Z_G)$ and $\min I(X;X+Z)$ are $\mathrm{0.793214}$ and $\mathrm{0.793210}\mathrm{\hspace{0.17em}\hspace{0.17em}}({\sigma }_X/{\sigma }_Z=\sqrt{\mathrm{2}})$ , $\mathrm{1.161543}$ and $\mathrm{1.161542}\mathrm{\hspace{0.17em}\hspace{0.17em}}({\sigma }_X/{\sigma }_Z=\mathrm{2})$ , and $\mathrm{1.585175}$ and $\mathrm{1.585174}\mathrm{\hspace{0.17em}\hspace{0.17em}}({\sigma }_X/{\sigma }_Z=\mathrm{2}\sqrt{\mathrm{2}})$ . That is because in this case $f_X$ is much like Gaussian distribution. When $(b-a)/\mathrm{2}{\sigma }_X$ is close to $\sqrt{\mathrm{3}}$ , $f_X$ is approximated to homogeneous distribution. The results remain good. For example, when $(b-a)/\mathrm{2}{\sigma }_X$ is $\mathrm{1.76}$ , $I(X;X+Z_G)$ and $\min I(X;X+Z)$ are $\mathrm{0.7850}$ and $\mathrm{0.7848}\mathrm{\hspace{0.17em}\hspace{0.17em}}({\sigma }_X/{\sigma }_Z=\sqrt{\mathrm{2}})$ , $\mathrm{1.1305}$ and $\mathrm{1.1304}\mathrm{\hspace{0.17em}\hspace{0.17em}}({\sigma }_X/{\sigma }_Z=\mathrm{2})$ , and $\mathrm{1.52132}$ and $\mathrm{1.52127}\mathrm{\hspace{0.17em}\hspace{0.17em}}({\sigma }_X/{\sigma }_Z=\mathrm{2}\sqrt{\mathrm{2}})$ . Thus although Gaussian distribution is not the optimal noise distribution when X follows the truncated Gaussian distribution, it is a nearly optimal noise distribution.

Figure 4

The difference between $\min I(X;X+Z)$ and $I(X;X+Z_G)$ where $Z_G$ obeys Gaussian distribution. ${\sigma }_X^{\mathrm{2}}$ and ${\sigma }_Z^{\mathrm{2}}$ are the variances of X and Z, respectively.

6. Numerical Simulation

From Theorem 2, when the original value obeys Gaussian distribution, the optimal noise distribution is Gaussian distribution too. Besides Gaussian distribution, homogeneous distribution (e.g., [12]) and Laplace distribution (e.g., [17]) are also used in noise addition method. Figure 5 shows the privacy-preserving capabilities of these three noise distributions, where $f_X$ is a Gaussian distribution. From the figure, we could find that the mutual information, which measures the privacy protection strength, is the smallest with the Gaussian noise. It means that by adding Gaussian noise, the attacker gets the least information of the true value from the perturbed value. Meanwhile, from the figure, the information leaks less with the increase of the accuracy requirement bound ${\sigma }_m^{\mathrm{2}}$ .

Figure 5

Compare the privacy-preserving capabilities of Gaussian distribution, homogeneous distribution, and Laplace distribution, where $f_X$ is Gaussian distribution with the variance $\mathrm{6400}$ .

Figure 6 illustrates the privacy-preserving capabilities of Gaussian distribution, homogeneous distribution, and Laplace distribution when $f_X$ is a truncated Gaussian distribution. Here we choose $f(x)=((\mathrm{1}/\mathrm{80})\varphi (x/\mathrm{80}))/(\mathrm{\Phi }(\mathrm{300}/\mathrm{80})-\mathrm{\Phi }(-\mathrm{300}/\mathrm{80}))$ as an example, which is in the range of $[-\mathrm{300,300}]$ . From the figure, Gaussian noise is still the best one to protect the individual privacy. The difference to the optimal noise distribution has been shown in Figure 4, from which we find when the original value obeys the truncated Gaussian distribution, Gaussian distribution is still a good noise distribution.

Figure 6

Compare the privacy-preserving capabilities of Gaussian distribution, homogeneous distribution, and Laplace distribution, where $f_X$ is the truncated Gaussian distribution $f(x)=((\mathrm{1}/\mathrm{200})\varphi (x/\mathrm{200}))/(\mathrm{\Phi }(\mathrm{300}/\mathrm{200})-\mathrm{\Phi }(-\mathrm{300}/\mathrm{200}))$ .

7. Conclusion

In this paper, we quantify the accuracy of result and the privacy of individuals. Based on the metrics, we propose the optimization problem, finding out the optimal noise distribution that provides the best privacy protection while maintaining the acceptable deviation from the accurate result. For the special cases that the original data of individuals follows Gaussian distribution and the truncated Gaussian distribution, Gaussian distribution is the optimal distribution and the asymptotically optimal one, respectively.