Previous Privatization Techniques

Differential privacy is certainly not the first technique that has been developed to analyze data while protecting individuals in the data. Consider a situation where a researcher releases aggregate statistics about hospital patients over the past year. For example, the researcher publishes a paper stating that there have been 3 cases of a particular type of cancer in that hospital this year. On the surface, you may assume this is safe - there were no names, addresses, social security numbers, or other sensitive personally identifiable aspects released about these patients.

Previously, standard privatization techniques relied on anonymization to protect privacy - for example, removing or modifying the names of individuals. This is insufficient and can lead to privacy leakages. Consider the case of Dr. Latanya Sweeney who, while still a graduate student, purchased Massachusetts voter registration information and was able to identify the governor of Massachusetts within anonymized medical data. ¹⁰ She was able to due this by isolating those individuals in the data with the same attributes as the governor, finding that “six people had [the governor’s] particular birthdate, only three of them were men, and, he was the only one in his 5-digit zip code.”¹¹

This work led Sweeney to the discovery that many people are uniquely identifiable using only these three pieces of information: birthdate, government-recorded gender, and zip code. ¹² A 2006 study estimated that about 63% of the US population can be uniquely identified from these three attributes, ¹³ while 44% of the population in the 2010 census is identifiable via census block, age, and sex. ¹⁴

To protect against vulnerabilities like this, Sweeney introduced k-anonymity in 2002. K-anonymity is a generalized protection against this specific type of identification. The “k” in k-anonymity refers to its central principle - that an individual cannot be distinguished from at least k-1 other individuals in the dataset. Using the Massachusetts scenario, this would mean a hypothetical scenario where Sweeney could not distinguish between the governor and k-1 other individuals in the voter roll, preventing her from re-identifying his medical records. Thus, k-anonymity has vulnerabilities to linking - if an attribute is considered non-identifying, but can be linked to another dataset, it can become an identifying attribute and lead to privacy violations.

The two major attacks on k-anonymity are:

Homogeneity attack

This attack takes advantage of a situation where the data has many identical values. Consider a situation where a hostile actor knows that someone has been admitted to the hospital on a certain date, and looks at the admission logs. If everyone admitted to the hospital on that day had cancer, then the attacker has learned that this individual has cancer. Clearly, this attack relied on the homogeneity of the data - if everyone admitted on that date had a different disease, then the attacker would have learned nothing.

Background knowledge attack

This attack relies on the attacker knowing things about the individual that are not present in the relevant dataset. For example, if the attacker wants to know what type of cancer the individual has, and knows that the hospital admissions were all for prostate or cervical cancer, then the attacker simply needs to know whether the individual has a prostate or a cervix in order to learn their cancer diagnosis with certainty. ¹⁵

As you can see, k-anonymity does not always prevent a bad actor from identifying individuals in a dataset. Even if the data is sufficiently heterogeneous to not fall victim to a homogeneity attack, with the availability of third-party data for sale, the risk of a linkage attack is significant. Methods that suppress individual features in a dataset are not sufficient to guarantee privacy.

Differential privacy gives a more general definition of privacy than techniques like k-anonymity. Instead of focusing on removing or anonymizing certain attributes from a dataset, it gives an analyst a probabilistic guarantee about an attacker’s ability to learn if a certain individual was in a dataset or not. In data privacy, implementation is key to guaranteeing protection - a flawed implementation can leak information and cause privacy violations. With this in mind, the next section will introduce several libraries for conducting DP data analysis.

Available Tools

This is fundamentally a book about understanding and implementing differential privacy, meaning that the software packages are of central importance. Luckily, there are already high-quality open source tools available for working with data in a differentially private manner.

The majority of the code examples you will see in this book are written in the OpenDP Library and SmartNoise. The OpenDP Library provides a flexible suite of lower-level functions for building differentially private data analysis pipelines, while SmartNoise contains higher-level abstractions.

The OpenDP Library

The OpenDP Library is a “modular collection of statistical algorithms” that follow differentially private principles. It can be used to build differentially private data analysis pipelines using a number of different models of privacy. The library is implemented in Rust, with bindings in Python for ease of use. The architecture of the OpenDP Library is based on a conceptual framework for expressing privacy-aware computations. ¹⁶

The following OpenDP Library sample, taken from the documentation, creates a chain of three operations and applies them to a dataset:

import opendp.prelude as dp

# construct the query
dp_sum = (
  dp.space_of(list[float]) >>         # public knowledge
  dp.t.then_clamp(bounds=(0., 5.)) >> # stable transformation
  dp.t.then_sum() >>                  # stable transformation
  dp.m.then_laplace(scale=5.)         # private mechanism
)

# evaluate the privacy expenditure
max_contributions = 1
print("epsilon:", dp_sum.map(d_in=max_contributions))

# make a DP release
mock_dataset = [0.7, -0.3, 1., -1.]
print("DP sum release:", dp_sum(arg=mock_dataset))

The OpenDP Library is part of the larger OpenDP Project, a community effort to build trustworthy, open source software tools for analysis of private data. The full documentation for OpenDP can be found at https://docs.opendp.org.

SmartNoise

SmartNoise is a collaboration between Microsoft, Harvard’s Institute for Quantitative Social Science (IQSS), and the School of Engineering and Applied Sciences (SEAS) as part of the Open Differential Privacy (OpenDP) initiative. The project aims to connect solutions from the research community with the lessons learned from real-world deployments to make differential privacy broadly accessible.

Building upon the foundation of the OpenDP library, the SmartNoise SDK includes two Python packages:

• smartnoise-sql: Allows data owners to run differentially private SQL queries. This package is useful when generating reports or data cubes over tabular data stored in SQL databases or Spark, or when the dataset is very large.

• smartnoise-synth: Provides utilities for generating differentially private synthetic datasets. Useful when you can’t predict the workload in advance and want to be able to share data that is structurally similar to the real data with collaborators.

Both of these packages focus on the global model of differential privacy, as opposed to the local model. In the global Differential Privacy model, a trusted data collector is presumed to have access to unprotected data and wishes to protect public releases of information.

Tumult Labs

Tumult Core is a set of components for building differentially private computations. Tumult Analytics is a Python library, built on top of Tumult Core, that allows the user to perform differentially private queries on tabular data. Tumult has also created an online platform for both batch and interactive data analysis. In May 2023, Tumult and Google announced a strategic partnership integrating Tumult’s differential privacy techniques into Google’s BigQuery platform. This allows BigQuery users to easily make differentially private queries on the platform by adding a differential privacy clause to their query. In other words, you only have to add WITH DIFFERENTIAL PRIVACY to your SELECT statement along with several options in order to make the query differentially private:

SELECT
  WITH DIFFERENTIAL_PRIVACY
    OPTIONS(epsilon=1.0, delta=.01, privacy_unit_column=id)
    item,
    AVG(quantity) average_sales
FROM inventory
GROUP BY item;

OPACUS

Opacus is a library for training differentially private PyTorch models. Training a DP model with Opacus requires minimal code changes, and in many cases does not have a significant impact on training performance. The library also supports online tracking of the privacy budget.

Tensorflow Privacy

Tensorflow Privacy (also known as TF Privacy) was created by Google Research. The library includes DP implementations of TensorFlow Optimizers for training ML. TF Privacy was designed so that users can train DP models with TensorFlow by changing a minimal amount of code. Differentially private implementations of some Keras models are available as well.

Diffprivlib

Diffprivlib, from IBM, is a “general-purpose library for experimenting with” differential privacy. The library has Python bindings that can be used to compare DP and non-DP ML models, and to build DP-preserving applications. It includes a variety of mechanisms, including differentially private implementations of common scikit-learn machine learning models.

If you have a background with scikit-learn, this code sample from the Diffprivlib documentation will likely seem familiar:

from diffprivlib.models import GaussianNB

clf = GaussianNB()
clf.fit(X_train, y_train)

The U.S. Census

Differential privacy made the jump from theory to application relatively quickly - in 2018, the U.S. Census announced that it would privatize the results of the End-to-End (E2E) Census Test. ¹⁷ This process, was a practice run for future Censuses, and systems that passed validation in 2018 were expected to be put into production for the 2020 Census. In light of the vulnerabilities pointed out by the database reconstruction theorem of Nissim and Dinur, the Census decided to build a differentially private statistical publication system. The stakes here were real - the data in question is used to construct legislative districts and ensure that the 1965 Voting Rights Act is being followed.

In 2021, the State of Alabama sued the U.S. Census for its use of differential privacy, alleging that the Census was providing “manipulated redistricting data to the States.” ¹⁸ There is prior precedent for the U.S. Census to introduce techniques to protect individual privacy. For example, in 1930, Census releases stopped including data from small areas to protect residents in sparsely-populated regions from being re-identified. A panel of three judges ultimately rejected Alabama’s complaint, responding that the state had no claim of harm stemming from skewed results since they had yet to be released. ¹⁹

²⁰

Differential privacy, though a relatively recent development, has led to the creation of powerful tools for analyzing sensitive data. It is not enough to simply remove sensitive attributes from data, nor is it sufficient to anonymize data in order to protect privacy. Relatively simple methods can be used to re-identify individuals in a dataset, for example, cross-referencing demographic information with voter rolls in order to identify patients in a medical dataset. With the weaknesses of previous privatization techniques in mind, you can begin to weigh your options so that you will be able to safely work with sensitive data in the future. The goal of this book is that, upon completing it, you will have a firm grasp of the concepts behind differential privacy and also feel confident and prepared to work with sensitive data without falling into common traps.

Each chapter has a set of exercises at the end - these exercises are divided between conceptual, theoretical, and programming. A conceptual question will ask you to answer a “why” question in sentences. These questions will probe whether you understand the fundamentals that have been covered in the chapter. Theoretical questions will rely on mathematical reasoning - sometimes it will involve solving a problem, other times proving a theorem. Programming questions will challenge you to implement concepts in Python with the OpenDP Library. All questions are answered at the end of the book, with explanations and further comments.

In the next chapter, you will follow a real-world scenario that demonstrates the risks of non-private statistical releases. Though the stakes are relatively low (an exam score), the principles are the same for more sensitive types of data. This chapter will motivate the ways that a seemingly innocuous action can lead to the indirect disclosure of information. From there, you will dive deeper into the theory and application of differential privacy - what it guarantees, what it doesn’t, and how to analyze data with privacy guarantees in mind.