Enabling Rich Statistical Analyses with Differential Privacy | Hacker News Reader

Enabling Rich Statistical Analyses with Differential Privacy

nist.gov

56 pointsoedmarap16 comments

Back when I worked for the state (of North Carolina), I did a lot of public data reporting for state-run education programs (e.g., community colleges, public universities). Our system had access to enrollment and graduation data from those programs, as well as wage data on everybody working in North Carolina in a job covered by the state's unemployment insurance program (which was most jobs). We could therefore report on things like how many people were studying what subjects at what institutions, what the X-year graduation rates were, how much money people were making Y-years after graduation, what industries they were employed in, etc. It was an extremely cool data set.

Of course, the major concern in publishing that data was precisely this - people's income is super sensitive. If there was some program at some university that only graduated one student in a particular year, you couldn't report the average wage outcomes for that program, because you'd essentially be putting that student's salary online for everybody to see. Instead of adding randomness to the data, as described here, we'd simply hide any information that was based on 3 or less individuals, or which could be entered into a mathematical formula to enable you to DERIVE information on 3 or less individuals.

For example, suppose you reported the mean salary of everybody who graduated with an art degree from community colleges in 2010, then reported the mean salary for everybody who graduated with an art degree from each individual community college in 2010. Suppose further that one of those individual community colleges only had a single art degree graduate and you hid the data. Under those conditions, somebody could still do some simple algebra to calculate the hidden value. So you'd have to hide the value from a second community college to prevent somebody from working out the unknown value at the first.

As you reported more and more data across a higher and higher number of dimensions, the problem grew more and more complex. It actually ended up being really cool to reason about, and we developed both a greedy heuristic and a binary-integer-programming approach to solving to near or true optimality, respectively.

The challenge, as you suggest, is that "reasoning" about things gets really complicated and at least partially a matter of "gut feel."

There's a fascinating story from the 1990s when Massachusetts released anonymized state employee hospital records for medical research. They only included date of birth, gender, and zip code along with the actual medical information. An MIT grad student at the time--she's now a Harvard professor--Latanya Sweeney informed William Weld, the governer of MA at the time, that she had his medical records. She had done a linkage attack using voter database registration. (She subsequently did other research in this area and has a tool on her site where you can see if you could be uniquely identified in the same way. I can as I live in a fairly small town.)

Hey, you stopped when you got to the really good part. The NIST article series talks about adding noise to counts that would reveal too much information about individuals in the counted population. I took your art degree example to say that one needs to look across all dimensions of units in a count to check for information leakage, not just the in counted-by dimension. I am just not making the leap from there to either a greedy heurstic or a binary-integer-programming approach. Would you mind elaborating a little?

Sure. But to see it, we'll have to expand the example a little. Suppose you release the average salary for people that got an associates degree from the community college system - just a single number. Then you release that number broken down by campus. Then you release it for all campuses together, but broken down by subject area. Then you do it broken down by all campuses AND all subject areas. Then by all campuses, subject areas, and industry of employment. Etc. Ad nauseum.

Now suppose you had one person who got an associate's in art from campus X. You hide that value. But you now need to go searching across multiple dimensions to find "buddy cells" to suppress. You need to make sure that you suppress the value of associate's in art, but from a different campus. And you need to suppress the value of associate's from the same campus, but in a different subject. Otherwise, somebody can algebra-out the originally suppressed value. The more dimensions you have, the more you have to search across to hide data.

But here's where the optimization goal comes in - you don't like hiding data. You want to release as much data as possible. So you want to find a way to release the maximum amount of data while still protecting individual privacy.

The greedy approach is to go through every suppressed cell and make sure that it has a "buddy" cell across every possible dimension of aggregation. If it does NOT have a buddy cell, then select the cell in that dimension based on the smallest number of people, and suppress that one as well. But now you have to make sure that THAT cell is protected and can't be algebra'd-out, so you have to cycle through again. You keep doing this, always selecting the smallest possible buddy cells, until you have at least 2 cells suppressed across any dimension that can be aggregated.

Of course, if you really want to release as much data as possible, you can treat it as a binary integer programming problem where your goal is to minimize the sum of the N of data underlying suppressed cells and your decision variables are whether or not to suppress a given cell...

I hope that helps?

That was great, thank you for the detailed follow up.

The process of only releasing information that describes groups of people is more broadly known as k-anonymity [1]. This comment does a pretty good job of describing its appeal (it makes some intuitive sense, and it's better than doing nothing) and drawbacks (it's vulnerable to side information, releasing even two k-anonymous outputs can reveal a lot of information, and it can get pretty complicated).

Differential privacy solves these problems because it gives mathematical bounds for the amount of privacy lost. If you take part in two 0.5-differentially private computations, the probability of any event becomes at most e times more or less probable as a result of those computations. Of course, differential privacy has a lot of work left to do before it's feasible to just insert it into general data analysis, but it's slowly moving along that road.

[1] https://en.wikipedia.org/wiki/K-anonymity

One of the interesting insights in differential privacy is that to provide privacy protections that can't be reverse-engineered, the process has to be random rather than deterministic. The sort of algorithm that OP describes is really neat, but in addition to what dp_throw says, deterministic algorithms like this that choose how to anonymize things based on private data can reveal information about that private data in the very way that they format the final data. (This may be less relevant in the case at hand, but consider a setting where it would be sensitive to know if someone is in the database at all, e.g., a medical study.)

Differential privacy if I understand correctly has an upper limit on how many analyses can be performed before there is a privacy risk and the data must be destroyed. For official statistics and scientific research this is often not an acceptable tradeoff.

Releasing any data or statistic based on sensitive data--even once--bears a privacy risk. The primary purpose of differential privacy is to quantify that risk, both for a single release of data and over many releases of data.

As for the number of analyses you can run, that depends on what you mean. You're right that differential privacy won't allow you to set up a database of _confidential data_ that can be arbitrarily queried infinitely many times with any meaningful privacy guarantee, but this is in no way unique to differential privacy.

What you can do with differential privacy is release noisy statistics once and let researchers use those statistics for arbitrarily many analyses. This is what the 2020 US Census is doing, for example.

This conundrum can be resolved by generating synthetic datasets resembling true data. The definition of differential privacy doesn't distinguish between algorithm output types, which can be a single number as well as a whole dataset. The algorithms get a lot more complicated, of course, and quantifying data utility isn't simple either.

Just to add to the nice responses from lomereiter and georgefox, I think the common response to

> For official statistics and scientific research this is often not an acceptable tradeoff

is that differential privacy is the best known method for rigorously accounting for privacy risks. It's possible to argue that differential privacy is too strong (and plenty of people have), but to the best of my knowledge, systems that say "you don't need DP - we'll answer lots of database queries without DP and still prevent deanonymization" usually end up getting broken. A good example of this is the (repeated) breaking of Diffix [1], a system that attempts to provide privacy without using differential privacy.

So differential privacy is, I think, a good starting point if privacy is critical to your application. It does not offer much guidance for when you should decide privacy is critical, or when the utility of an application outweighs the need for privacy.

For example, many social science researchers have criticized the US Census for using differential privacy in the 2020 census. It's consistent to say "it's way more important to have accurate counts for all of the decisions made using census data -- let's not try too hard to be private". It's also consistent to say "privacy is important, so we should use a rigorous notion like differential privacy". It's not consistent to say "private is important, but let's just use some heuristics and hope for the best", which is what the census had largely been doing until 2020.

[1] https://differentialprivacy.org/diffix-attack/

Yes, you're absolutely right. In our case, we were effectively doing one massive annual dump of this data into an online tool (vs. multiple releases of k-anonymous data), so we didn't have to worry about the more complicated cases of two separate data releases causing disclosures.

(That, and the regulations that governed our program said to suppress cells based on 3 or less individuals... so, that's what we had to do.)

There's a whole field of software built around this called statistical disclosure control.

Most national statistics bureaus have datasets like the one you describe (usually referred to as microdata), kept in pseudonymous form and with strict access controls.

This article seems to be about adding noise to queries in order to remove identifying information.

Another really nice approach is https://en.wikipedia.org/wiki/Local_differential_privacy which randomises the data before it's even recorded.

A classic example is asking someone a sensitive question, like whether they use some illegal drug. To record the responses, we do the following:

- Ask the question

- Toss a coin

- If heads, toss the coin again then write down the participant's answer

- If tails, toss the coin again and write down 'yes' if it's heads or 'no' if it's tails

This way, each participant has plausible deniability, since their record has a 50% chance of coming from a coin toss, regardless of whether it's 'yes' or 'no'. Yet we can still estimate the prevalence from this dataset, by taking into account that around 1/4 of responses are fake 'yes' and around 1/4 are fake 'no'. For example, if we see 75% no and 25% yes we know there is a low prevalence of 'yes'.

Also note that we always toss the coin twice: hence a distant observer wouldn't know whether we've just written down a real or fake response.

More privacy (LDP model) == less utility

Sure, but that's always the tradeoff. If we know in advance what the data will be used for, we can choose an approach which allows that; although it may prevent subsequent 'fishing expeditions'. Note that GDPR already requires the purpose and scope of personal data collection to be specified in advance, so it's not an unrealistic requirement.

Reply on news.ycombinator.com