Intuition for Privacy

Differential privacy is a mathematical, quantitative definition of privacy. The definition guarantees privacy for individuals in the data, and any query that is mathematically proven to satisfy this definition is considered differentially private (DP).

To conduct a differentially private analysis, you must first determine your privacy unit. The unit of privacy describes what exactly is being protected. To get started, assume that the unit of privacy is a single individual, who contributes at most one row to the sensitive dataset.

Now consider what amount of risk is acceptable for disclosing information about a single individual. This varies wildly depending on the use-case! If the data is already available to the public, then there is no need to use differentially private methods. However, if a data release could put individuals at severe risk of harm, then you should reconsider releasing data at all. Differentially private methods are used to make releases on data with a risk profile somewhere between these two extremes. The privacy semantics of the query need to be in terms of the same unit of privacy that you selected previously.

The level of privacy afforded to individuals in a dataset under analysis is quantified by a privacy loss parameter. When you invoke a DP query on your data, you are guaranteed that each individual’s influence on the release is bounded by said privacy loss parameter. A privacy loss parameter measures how distinguishable each individual can be in a data release.

One common choice of privacy loss parameter is the scalar, $ϵ$. When $ϵ$ increases, each individual is permitted greater influence on the release, and therefore afforded less privacy. A data release is $ϵ$-differentially private if the DP query used to release it limits each individual’s influence on the output to $ϵ$.

Together, the privacy unit and privacy loss parameter characterize the differential privacy guarantee: when an individual has bounded influence on the dataset, then they also have bounded influence on the data release. For example, a DP library may prove that a carefully-calibrated DP sum satisfies (1 $ϵ$)-differential privacy when each individual may contribute at most 1 row.

The next few sections go into greater detail on how distances are measured between datasets and distributions.

Measuring the Distance Between Databases

Using the two definitions above, you can construct a notion of distance between databases. The symmetric difference tells us the elements appearing in only one of the databases - that is, it returns a set. This set is a representation of how the two databases differ from each other. If we measure the cardinality of this set, we can understand the magnitude of the difference between the databases. In other words, we have a distance between the databases!

Symmetric Distance ($d_{Sym}$)

The symmetric distance between databases X and Y is the number of elements appearing in either X or Y, but not both. Using language from the previous two definitions: the symmetric distance between databases X and Y is the cardinality of the symmetric difference.

For example, consider X = [1,2,4] and Y = [2, 4, 6]. The numbers 2 and 4 appear in both X and Y, so they are not in the symmetric difference. The number 1 appears in X and not Y, and 6 appears in Y and not X, so they are both in the symmetric difference.

Therefore $X▵Y=\{1,6\}$. This set has 2 elements, so the symmetric distance is $d_{Sym}(X,Y)=\left|X▵Y\right|=\left|\{1,6\}\right|=2$.

Figure 3-1. Symmetric Difference between databases X and Y is composed of the elements in X and y that are not part of the intersection $X\cap Y$. There are two elements that are not part of the intersection in the case where $X=\{1,2,4\}$ and $Y=\{2,4,6\}$.

Neighboring (or Adjacent) Databases

Two databases $x$ and $y$ are defined as neighboring if they differ by the addition or subtraction of a single element, i.e. if their symmetric distance is one: $d_{Sym}(x,y)=1$. Mathematically, $x\sim y$ means “x is a neighboring database to y.”

Achieving Differential Privacy: Mechanisms for Output Perturbation

A differentially private mechanism is a randomized computation that has nearly the same output for adjacent datasets. This is sometimes achieved by adding noise to the result of a query. For the differential privacy guarantee to hold, the query must have bounded sensitivity, and the noise must be sampled from a carefully-calibrated distribution. A differentially private mechanism is a function with a mathematically proven privacy guarantee. The function samples from a carefully-calibrated noise distribution that is more concentrated around the exact value.

As discussed before, differential privacy can be achieved via output perturbation. This means that adding “random noise” to query results that have bounded sensitivity can guarantee differentially private protections for individuals in the database. More formally, to guarantee the privacy of individuals in a database $X$, you can add random noise that perturbs the output of the query result $F$.

The random noise should be calibrated to mask the presence or absence of any individual in the database. In other words, any one entry of the database should not affect the output distribution of the algorithm significantly. This means that an adversary, who knows all but one entry in the database, cannot gain significant information about the unknown entry by observing the output of the algorithm.

Note that differential privacy is a characteristic of a query (or more generally, an algorithm). However, throughout this book the term differentially private data release will be used to refer to the output of differentially privacy queries (or algorithms).

As described in chapter 2, the purpose of a differential privacy mechanism is to extract information from a database while hiding the presence or absence of any individual. Differential privacy mechanisms allow data analysts to learn insights from a population while preserving the privacy of individuals.

Example: Returning to the Classroom

Suppose there exist two databases $X$ and $Y$ that differ by exactly one student, via either addition or subtraction of a single student.

Using the student dataset, we will define $X$ as the database with all students, and $Y$ as the database $X$ minus student #0. Just like chapter 2, the teacher wants to release the average exam score to the students. This time, they make a DP release of a statistic on $X$ and display the result to the students.

From the student’s perspective, they should not be able to distinguish if the mechanism was applied to $X$ or $Y$. Moreover, this distinction should hold true for the removal or addition of all possible students.

Figure 3-4. Differential Privacy mechanisms applied to neighboring databases should result in indistinguishable results.

Why do we use the concept of two adjacent databases?

The concept of neighboring databases helps rationalize about how much an individual can contribute to the output of a query. This concept will help you understand how to construct a mechanism that will mask the presence or absence of any individual.

privacy loss parameter: $ϵ$

The second parameter we need to define is the privacy loss parameter $ϵ$, which quantifies the privacy loss of a differentially private data release. When you mask the presence of individuals in a dataset using differential privacy, you can define how strong this masking is via the privacy loss parameter $ϵ$.

You can think of $ϵ$ as a dial. The lower the $ϵ$, the less information about individuals you are allowing to “leak” into the query answer. This means that a lower $ϵ$ will result in drawing noise from a Laplace distribution that has a wider probability density distribution.

Example 1: Differentially Private Counts

The SmartNoise library works as a wrapper for the OpenDP Library that simplifies common database queries, such as counts, sums and averages.

SmartNoise requires the trusted curator to load the dataset, specify dataset metadata, and choose the privacy loss parameters. The library automatically calculates the sensitivity based on the dataset metadata and query. Although the library offers default mechanisms for each query type, the user can easily change the desired mechanism.

We will use the student dataset ⁴ in our examples in this chapter.

import pandas as pd

df = pd.read_csv('student.csv') ## load the dataset

In order to use the SmartNoise SQL library, you need to specify dataset metadata via a yaml file. The metadata describes the data types of columns, and some additional metadata depending on the data type. For numeric columns, the metadata should include the lower and the upper values in the column. For categorical columns, the metadata should include the cardinality of the categorical variable.

Database:
    MySchema:
        MyTable:
            row_privacy: True
            age:
                type: int
                lower: 15
                upper: 25

            G3:
                type: int
                lower: 0
                upper: 20

            famsize:
                cardinality: 2
                type: string

            school:
                cardinality: 2
                type: string

            absences:
                type: int
                lower: 0
                upper: 50

To load the data, you need to define three things: the path to the yaml file, a per-query privacy loss parameter, and the pandas dataframe.

Recall that the Laplace mechanism satisfies $ϵ$-differential privacy. The following example sets the per-query privacy loss parameter $ϵ$ to 1.

>>> from importlib.metadata import metadata
>>> from snsql.sql._mechanisms.base import Mechanism
>>> from snsql import Privacy
>>> from snsql import from_df
>>> from snsql.sql.privacy import Stat


>>> metadata = 'student.yaml' ## load metadata
>>> privacy = Privacy(epsilon=1.0) ## set privacy loss parameter
>>> reader = from_df(df, privacy=privacy, metadata=metadata)
## initialize the method from_df to query pandas dataframes

The total privacy loss will increase by $ϵ$ each time you execute a query on ``reader``. You can adaptively set the privacy loss parameter of each query by creating new readers.

Once the data is initialized by the SmartNoise Library, you can construct queries using SQL syntax to query the dataframe.

You can use ``privacy.mechanisms.map`` to define which differential privacy mechanism to use in the data analysis.

The following executes a count query to get the number of students in the dataframe.

query = 'SELECT Count(*) AS students FROM MySchema.MyTable' ## define the desired query

privacy.mechanisms.map[Stat.count] = Mechanism.laplace
print("Running query with Laplace mechanism for count:")
print(privacy.mechanisms.map[Stat.count])
print(reader.execute_df(query))

Running query with Laplace mechanism for count:
Mechanism.laplace
   students
0       650

The result of the private count query is 650 students. The same query without privacy preserving mechanisms would return a result of 649 students.

query = 'SELECT SUM(absences) AS sum_absences FROM MySchema.MyTable '

privacy.mechanisms.map[Stat.sum_int] = Mechanism.laplace
print("Running query with Laplace mechanism for count:")
print(privacy.mechanisms.map[Stat.sum_int])
print(reader.execute_df(query))

Running query with default mechanisms:
Mechanism.geometric
   sum_absences
0    2192

Example 4: Multiple Queries from a Single Database

Using the same dataframe from the previous examples, let’s query the average grade for exam 3 (column G3). Now, there are two different partitions of the data: Students whose family size is greater than 3, and students whose family size is less than or equal to 3.

>>> query = 'SELECT famsize as Family_Size, AVG(G3) AS average_score
    FROM MySchema.MyTable GROUP BY famsize'
>>> print("Running query with default mechanisms:")
>>> res = reader.execute_df(query)
>>> print(res)

Running query with default mechanisms:
  Family_Size  average_score
0         GT3      11.825019
1         LE3      12.018476

Now let’s try another partition of the data: Students from school GP, and students from school MS.

query = 'SELECT school, AVG(G3) AS average_score FROM MySchema.MyTable GROUP BY school'
print("Running query with default mechanisms:")
print(reader.execute_df(query))

Running query with default mechanisms:
  school  average_score
0     GP      12.755956
1     MS      10.721144

Now let’s calculate the privacy loss after the two queries above.

The first query returns the average score for two group of students. Both queries utilize the Laplace mechanism with privacy loss parameter $ϵ$ = 1. From the definition of parallel composition, a sequence of $ϵ$-differentially privacy queries applied to disjoint partitions of a dataset provides $ϵ$-differential privacy. Note that in this case $ϵ$ is the same for each query, so $\underset{i}{max}{ϵ}_i=ϵ$.

The second query also provides the average score for two disjoint groups of students. Just like the first query, it provides $ϵ$-differential privacy with $ϵ$ = 1.

Finally, the final privacy guarantee can be computed using sequential composition. Given that we have a sequence of two queries that provides $ϵ$-differential privacy, the final privacy guarantee will be $2ϵ$-differential privacy.

Differentially private data releases are immune to Post-processing

Theorem: Let $ℳ$ be an $ϵ$-differentially private mechanism and $g:R\to R^{\text{'}}$ be an arbitrary mapping. Then the composition $g\circ ℳ$ is $ϵ$-differentially private.

With an understanding of these definitions and theorems, you are ready to dive into use cases and deeper theories in differential privacy. By now, you should be comfortable answering basic questions about a DP data analysis approach: Does noise from a particular distribution satisfy DP? Is the sensitivity of a mechanism small enough to allow for meaningful noise addition? Is the sensitivity even defined? You should also understand what DP guarantees (and what it doesn’t), and how your epsilon changes the output of your DP data release.

In the next chapter, you will build on your solid foundation in the basics of DP. This chapter will cover notions that generalize adjacency and sensitivity, to scenarios where two datasets can differ by more than a single value. In this case, you will want to answer a more general question: given a change in the input of my analysis, what is maximum change in its output?

Exercises

1. Given X = [1,2,3,4,5,6,7,8,9,10], calculate COUNT(X).

   1. Calculate COUNT(Y) for each adjacent dataset Y.

   2. Using the previous two results, verify that the sensitivity of COUNT is 1.

2. What is the sensitivity (in terms of the absolute distance) of the following functions, where x is a binary array of size n:

   1. $f\left(x\right)={\Sigma }_{i=1}^{n}2·x_i+1$

   2. $f\left(x\right)={\Sigma }_{i=1}^n{x}_i^2$

3. Which privacy loss parameter provides stronger privacy guarantees: $ϵ=0.1$ or $ϵ=1$?

4. Using the SmartNoise Library and the Student dataset, make the following queries:

   1. With a privacy loss parameter of $ϵ=0.1$, query the number of students that study in school GP.

   2. With a privacy loss parameter of $ϵ=1.0$, query the average score of students in school GP with Family = GT3 and with Family = LE3.