Differential Privacy: 6 Key Equations Explained

Differential Privacy is a powerful framework for ensuring privacy in data analysis by adding controlled noise to computations. Its mathematical foundation guarantees that the presence or absence of any individual’s data in a dataset does not significantly affect the outcome of an analysis. Here are six key equations that capture the essence of differential privacy and its mechanisms, along with references to their origins and explanations.

Definition of Differential Privacy

Differential privacy ¹ formalises privacy through the concept of indistinguishability between neighbouring datasets. A mechanism $\mathcal{M}$ satisfies $\epsilon$ -differential privacy if:

Where,

• $Pr$ denotes the probability of an event.
• $D, D'$ : Neighboring datasets differing in one entry.
• $\mathcal{M}$ : The randomized mechanism applied to the dataset.
• $S$ : Subset of possible outputs.
• $\epsilon$ : Privacy budget controlling the privacy-accuracy tradeoff.

This definition ensures that the outputs of $\mathcal{M}$ are statistically indistinguishable for any two neighboring datasets.

Laplace Mechanism

The Laplace mechanism ¹ is a common approach for achieving $\epsilon$ -differential privacy. It adds noise drawn from a Laplace distribution to the output of a function. The amount of noise is determined by the function’s sensitivity and the privacy budget $\epsilon$ , balancing privacy and accuracy. The noise is defined as:

Here:

• $\Delta f = \max_{D, D'} ||f(D) - f(D')||_1$ : Sensitivity of the function $f$ , measuring the maximum difference in output for neighboring datasets.
• $\epsilon$ is privacy budget.

The perturbed result is:

Gaussian Mechanism

For scenarios where a small probability of failure is acceptable, $(\epsilon, \delta)$ -differential privacy can be achieved using the Gaussian mechanism ². The noise is sampled from a normal distribution:

The standard deviation of the noise is calculated as:

Where:

• $\Delta f$ : Sensitivity of the function $f$ .
• $\delta$ : Probability of a privacy failure.
• $\epsilon$ is privacy budget.

The perturbed output is:

When applied iteratively or in compositions, the Gaussian Mechanism aligns well with advanced composition theorems (described below), making it practical for repeated queries. It is particularly useful when the function’s output has high sensitivity or when ( $\epsilon$ , $\delta$ )-differential privacy is needed instead of strict $\epsilon$ -differential privacy.

Composition Theorems

When multiple differentially private mechanisms are applied, the privacy budget accumulates. Differential privacy provides a framework for measuring and bounding the cumulative privacy loss from multiple analyses of information about the same individuals. Two key composition approaches³ are:

Sequential Composition

If $k$ mechanisms $\mathcal{M}_1, \mathcal{M}_2, \dots, \mathcal{M}_k$ are applied, each with privacy guarantees $\epsilon_1, \epsilon_2, \dots, \epsilon_k$ , the total privacy guarantee is:

Suppose a dataset is queried three times using mechanisms with $\epsilon_1 = 0.5$ , $\epsilon_2 = 0.3$ , and $\epsilon_3 = 0.2$ . The total privacy budget consumed is:

This means the combined analysis satisfies $1.0$ -differential privacy.

Advanced Composition

A tighter bound is given by advanced composition, which accounts for small failures:

Suppose a dataset is queried 100 times, each query satisfying $(\epsilon = 0.1, \delta = 10^{-5})$ -differential privacy. Using advanced composition:

1. Calculate the first term:

   $$\sqrt{2 \cdot 100 \cdot \ln(10^5)} \cdot 0.1 = \sqrt{2 \cdot 100 \cdot 11.5129} \cdot 0.1 = \sqrt{2302.58} \cdot 0.1 = 4.8$$

2. Calculate the second term:

   $$100 \cdot 0.01 = 1$$
3. $$\epsilon_{\text{total}} = 4.8 + 1 = 5.8$$

Thus, after 100 queries, the total privacy guarantee is approximately $(\epsilon = 5.8, \delta = 10^{-5})$ .

Comparing Sequential and Advanced Composition

Sensitivity

The sensitivity¹ of a function quantifies its robustness to changes in individual data points. Sensitivity determines the amount of noise required to ensure privacy. Currently, the global and local sensitivity are being mainly used in differential privacy.

Global Sensitivity

Global sensitivity is the maximum change in the output of a function $\Delta f_G$ when applied to any two neighboring datasets $D$ and $D'$ , differing by a single element. For function $\Delta f_G$ , the $\ell_1$ or global sensitivity is defined as:

Where:

• $D, D'$ : Neighboring datasets differing in one record.
• $||\cdot||_1$ : The $\ell_1$ -norm, representing the absolute difference in outputs.

Global sensitivity is the maximum differences in output with consideration of all possible datasets and is therefore only dependent on the query and not the dataset.

Local Sensitivity

Local sensitivity⁴ is a finer measure defined for a specific dataset $D$ . It measures the maximum change in the output of function $\Delta f_{L}$ for all neighboring datasets $D'$ of $D$ :

Local sensitivity attempts to calculate the sensitivity for a local data set, where the possible changes are bound by the local data set and not the universe of all data sets.

While local sensitivity may be smaller than global sensitivity for specific datasets, it is less robust for privacy guarantees since it depends on the specific dataset and not the worst-case scenario.

Sensitivity for Common Functions

1. Counting Queries: For functions that count individuals satisfying a condition, $\Delta f = 1$ .

2. Summation Queries: If data values are bounded (e.g., income within $[0, 100]$ ), the sensitivity is the range of possible values. For summing incomes:

   $$\Delta f = \text{max value} - \text{min value} = 100 - 0 = 100$$

3. Average Queries: Sensitivity for averages depends on both the range of values and the dataset size $n$ :

   $$\Delta f = \frac{\text{max value} - \text{min value}}{n}$$

4. Maximum or Minimum Queries: Sensitivity is the largest possible change in the maximum or minimum when a single data point is added or removed.

Comparing Global Sensitivity vs. Local Sensitivity

Exponential Mechanism

The exponential mechanism⁵ is useful for selecting outputs in a way that prioritizes utility while maintaining privacy. It assigns probabilities to each potential output $r$ based on a utility function $u(D, r)$ :

Where:

• $u(D, r)$ : Utility function representing the quality of $r$ .
• $\Delta u$ : Sensitivity of the utility function.
• $\epsilon$ is the privacy budget.

Unlike mechanisms that add noise to the output (e.g., Laplace Mechanism), the Exponential Mechanism modifies the selection probability, making it suitable when adding noise would render the output meaningless or when the output space is non-numeric. It extends the concept of differential privacy to non-numeric data types and provides a foundation for private data analysis in more complex settings.

Laplace Mechanism vs. Gaussian Mechanism vs. Exponential Mechanism

Conclusion

Differential privacy provides a rigorous mathematical guarantee for protecting individual data in computations. These six equations form the core of differential privacy and its mechanisms. By carefully choosing the noise and parameters, analysts can ensure a balance between privacy and accuracy. Understanding these equations empowers practitioners to implement robust privacy-preserving techniques in real-world applications.

Refrences