[HN Gopher] Enabling Rich Statistical Analyses with Differential...
___________________________________________________________________
Enabling Rich Statistical Analyses with Differential Privacy
Author : oedmarap
Score : 53 points
Date : 2021-02-24 10:41 UTC (12 hours ago)
(HTM) web link (www.nist.gov)
(TXT) w3m dump (www.nist.gov)
| dbatten wrote:
| 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.
| ghaff wrote:
| 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.)
| Tarq0n wrote:
| 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.
| dp_throw wrote:
| 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
| dbatten wrote:
| 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.)
| Tarq0n wrote:
| 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.
| georgefox wrote:
| 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.
| dp_throw wrote:
| 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/
| lomereiter wrote:
| 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.
| georgefox wrote:
| 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.)
| troelsSteegin wrote:
| 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?
| dbatten wrote:
| 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?
| chriswarbo wrote:
| 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.
| amitport wrote:
| More privacy (LDP model) == less utility
___________________________________________________________________
(page generated 2021-02-24 23:02 UTC)