How Differential Privacy Works

Okay, it’s time for another installment in my Privacy Enhancing Technologies series. Let’s talk about how we can preserve individual privacy in a vast set of data using a mathematical technique called Differential Privacy.

A Face in the Crowd

Let’s say you have a big stack of data about people. The US census data is a good example. The raw data has identifying information… name, address, birth date, etc. The requirement to collect census data is right there in the US Constitution: Article 1, Section 2. We want to use that data to make important calculations – but (crucially) we don’t want just anyone to be able to identify any individual in the data set. That would violate their privacy. We want to share data without sharing secrets. It would be like blurring the faces of a crowd shot so you can’t recognize faces, but could still count the number of people wearing hats.

Now, you could try to construct some sort of limited interface to this data that only lets you ask general questions about aggregate statistics, without asking for information about a particular person in the data set. However, a clever person could still potentially single out a specific entry with some clever queries. Think of crafting several questions that would return information about a subset of the data, and crafting these subsets so that after enough queries only one person would exist in all the subsets. And often all we really want to know is: is this person even in the data set? We want to protect against that, as well.

Finding the Needle in the Haystack

Here’s a contrived example. I’m not allowed to ask about individual people, but I can ask unlimited questions about groups of people. Let’s say I want to know what my elderly neighbor Alice’s salary is. I can ask successive questions to determine this:

1. How many people live in this neighborhood? → 36
2. How many are female? → 16
3. How many are age 80 or older? → 3
4. How many females are age 80 or older? → 1
5. What’s the household income of females over 80? → $32,000

I never asked about Alice specifically, and yet I was still able to ask a set of questions that let me determine her specific salary. Think of this as generating a set of Venn diagrams that eventually only overlap at a single entry.

A famous example of re-identifying supposedly anonymized data is the Netflix Prize competition. They released “de-identified” data containing 100 million rankings from 500,000 Netflix users, challenging people to help them improve their movie recommendation algorithm. Despite their efforts to remove all identifying information, a clever researcher was able to identify many of the people’s data by cross-referencing with other public datasets. This is, in fact, a common way to re-identify people in supposedly scrubbed data.

Adding Noise to Data

Differential Privacy (DP) protects individuals by making it mathematically uncertain whether any one person’s data is in the dataset. That is, it’s not enough to just make it hard to identify a specific person in the dataset – you want to make it uncertain whether that person is even in the data set at all. We do this by essentially adding “noise” to the data in a methodical way, such that the aggregate statistics that we care about don’t change, but individual entries are “fuzzed” to the point of being unrecognizable. So we can still ask general questions and get accurate, meaningful answers, but we can’t slice and dice the data to identify individual entries.

How do we do this? There are two main methods: central and local differential privacy. With central differential privacy, the original, raw data with personally identifiable information (PII) is kept in a vault and an interface is provided for people to run general, aggregate queries. (This is how the US census data is handled.) You can actually create a mathematically defined “privacy budget” to limit how much someone can learn from the data. With central DP, the data is randomly altered in a coordinated way so that the overall, aggregate statistics that we care about don’t change that much.

With local DP, the user data is actually altered before it’s ever submitted. Apple actually does this with its emoji statistics and Google uses DP for some Chome statistics. This is much more private since the identifiable information never actually leaves the device. However, the mathematical techniques required to twiddle the data locally in a predictable and statistically controlled way can lead to less accuracy.

An Example of Differential Privacy

For example, if I could see a census record that includes sex, age and race for my neighborhood, I might be able to uniquely identify a Hispanic female who is 32. There may be only one person who matches all three things. But let’s say everyone rolls a die before submitting their age data, and fudges their age based on the result… for 1, 2 or 3, add that amount to your age; for 4, 5 or 6, subtract 1, 2 or 3 from your age. This woman (or her device) rolls a 5, and so submits her age as 30 instead of 32. It’s wrong. But if everyone does this, the fudge factors will statistically average out with a large enough sample. The average age of people in my neighborhood should still be very close to accurate.

If you want to learn more, check out this video explainer that talks about how the 2020 US census data is protected with differential privacy. It gets a little “mathy” at times, but overall it’s still helpful.