Unfortunately, Differential Privacy proofs can be used to justify applications which turn out to leak privacy when the proofs are shown to be incorrect after the fact, when the data is already out there and the damage already done.
Nevertheless, it is instructive just to see how perilously few queries can be answered before compromise occurs — putting the lie to the irresponsible idea of "anonymization".
1. They should deliberately introduce noise into the raw data. Nazis with the raw census data can spend all month trying to find the two 40-something Jews that data says live on this island of 8400 people, but they were just noise. Or were they? No way to know.
2. Bucket everything and discard all raw data immediately. This hampers future analysis, so the buckets must be chosen carefully, but it is often enough for real statistical work, and often you could just collect data again later if you realise you needed different buckets.
3. They shouldn't collect _anything_ personally identifiable. Hard because this could be almost anything at all. If you're 180cm tall your height doesn't seem personally identifiable, but ask Sun Mingming. If you own a Honda Civic then model of car doesn't seem personally identifiable but ask somebody in a Rolls Royce Wraith Luminary...
e.g from the paper:
"We show that, as a male born on July 31, 1945 and living in Cambridge (02138), the information used by Latanya Sweeney at the time, William Weld was unique with a 58% likelihood (ξx = 0.58 and κx = 0.77), meaning that Latanya Sweeney’s re-identification had 77% chances of being correct. We show that, if his medical records had included number of children—5 for William Weld—, her re-identification would have had 99.8% chances of being correct!"
The antidote of oppression is not the Index statisticum prohibitorum, but quite the opposite, education, and in particular educating about how different each and every one of us is, and yet it doesn't take much to get along well.
The term raises questions: Okay, so, what does it mean? How 'pseudo' is psuedo? And that's the point: When you pseudonimize data, you must ask those questions and there is no black and white anymore.
My go-to example to explain this is very simple: Let's say we reduce birthdate info to just your birthyear, and geoloc info to just a wide area. And then I have an pseudonimized individual who is marked down as being 105 years old.
Usually there's only one such person.
I invite everybody who works in this field to start using the term 'pseudonimization'.
(Or, of course, simply pass a law that entitles them to deport or hold indefinitely anyone who can't prove they're a real Ayrian with only the papers they have on them at the time)
Anonymizing datasets is a weasel term.
The database is secure or it is not. As any database is quite likely insecure, we are doomed.
Number of people >100 in the area: <10
For some kinds of information, like medical records, the information is deadly not to have accurate, but also deadly to have accurate and public. Once the information leaks, employers might decide to not hire high-risk people or insurers might decide to pass over certain people as too costly.
I'm of the opinion "anonymizing" data is something that enables grifting; if enables the collectors to placate the people they are pulling data from, and it allows the grifters to make the argument the information they have means nothing.
Ultimately, I think these organizations should be making sure their information is absolutely accurate, and we should have laws in place, with severe criminal penalties, against the use transfer or use of said information. I would even go so far as to say things like cell phone location records should be fully public as a matter of the law.
Now when you want to get those records, you go to a government website for the "hunt and poke" stuff (e.g. where are my kids going or is my wife spending time with another lover, how long is my commute on average, or where was I at 3 years ago on a day, all sorts of useful questions); the access records are public too.
If you want to study them, you sign a NDA saying you won't, under penalty of severe criminal prosecution, leak the information or use it for criminal purposes. Anyone found having the data and no signed government NDA = instant 20 year prison sentance plus felony conviction.
This way, if, for example, someone signs the NDA and goes on to offer services to executives to help them cherry pick staff, not only does the person offering the under the table services go to jail, but the executive does as well.
When you criminalize certain things, then give the public all the information and tools to do as they see fit, the law works. It's a lot easier to prosecute a company executive for cherry-picking staff with insurance data when the data is well-labeled. It is also a lot easier to sue them when you have an access record that says someone under their employ checked how often you go to a clinic or night club via your cellphone records.
The problem is not going away anyway, and "anonymizing" data to placate our sense of morality isn't going to help. There is no easy technical solution, but if the thinking is not to anonymize but instead track and enforce who has access, things change drastically.
> The source code to reproduce the experiments is available at https://cpg.doc.ic.ac.uk/individual-risk, along with documentation, tests, and examples.
As far as I can tell, the source code is not available, at least not from where the authors suggest.
There are caveats. The exact strength of the privacy guarantee depends on the parameters you use and the number of computations you do, so simply saying "we use a differentially private algorithm" doesn't guarantee privacy in isolation.
Pseudonimization is bad terminology in that it's indistinct from the above, to the point that parent has already mixed the two up while in the process of recommending it. And it'd be worse verbally.
"Pseudo-anonymization" could work, but something like "breakable anonymization" or "partial anonymization" might be better in that it's more obvious to a reader and doesn't rely on familiarity with technical terminology to convey the idea.
I'd go with breakable, myself, since it's most to the point about why it's a problem.
Pseudo is etymologically correct, but that doesn't necessarily help us much when the goal is ratio and ease of understanding by a wide population of readers.
Partial could work in the sense that you did part of the job, which people would hopefully understand is a bit like having locked the back door for the night while leaving the front propped wide open.
And there are probably other good options. If I was writing about this topic often, I'd strongly consider brainstorming a few more and running a user test where I ask random people to explain each term, then go with what consistently gets results closest to what I'm trying to discuss.
You are right that some differential privacy proofs have later been found to be wrong. For example, there is an entire paper about bugs in initial versions of the sparse vector technique [1].
However, I imagine this will evolve the way cryptographic security has evolved: at some point, enough experts have examined algorithm X to be confident about its differential privacy proof; then some experts implement it carefully; and the rest of us use their work because "rolling [our] own" is too tricky.
Or even more briefly, if you want to know how many people in your database have characteristic X, you can compute that number and add Laplace(1/epsilon) noise [2] and output the result. That's epsilon-differentially private. In general, if you're computing a statistic that has sensitivity s (one person can change the statistic by at most s), then adding Laplace(s/epsilon) noise to the statistic makes it epsilon-differentially private (see e.g. Theorem 3.6 here [3]). The intuition is that, by scaling the added noise to the sensitivity, you cover up the presence or absence of any one individual.
[1] https://github.com/frankmcsherry/blog/blob/master/posts/2016...
Why not just ensure that any personally identifiable data is properly bucketed, and discarded if it is too strongly identifiable. If you are storing someone's height, age, and gender, you can just increase the bucket size for those fields until every combination of identifiable fields occurs several times in the dataset. If there are always a few different records with well distributed values for every combination of identifiable fields, you can't infer anything about an individual based on which buckets they fall into.
Remember; fascists don't believe in things because they are true, but because they are a means to an end. Their ultimate goal is authoritarian control, and an administrative mechanism is far more effective toward that goal than a scientific one.
https://www.schneier.com/blog/archives/2019/07/google_releas...
https://www.microsoft.com/en-us/research/project/microsoft-s...
That aside, I would like the option that says "do not collect the data". It wouldn't even be hard.
Sure there is knowledge and advantages in that data, but that doesn't even come close to the benefits of privacy. Think the general public opinion about X is pretty stupid? If so, you'll need it too.
> Homogeneity Attack: This attack leverages the case where all the values for a sensitive value within a set of k records are identical. In such cases, even though the data has been k-anonymized, the sensitive value for the set of k records may be exactly predicted.
> Background Knowledge Attack: This attack leverages an association between one or more quasi-identifier attributes with the sensitive attribute to reduce the set of possible values for the sensitive attribute.
Optimal k-anonymization is also computationally hard [2].
What matters is that this is what most online companies (and their terms of service) would call anonymized data.
Given a source dataset they create a synthetic dataset that has the same statistical properties (as defined at the point the synthetic dataset is created).
I've seen a demo, it's pretty slick https://synthesized.io/
It's possible to learn something by aggregating a bunch of those individually-privatized statistics. Randomized response [1] is a canonical example. More generally, local differential privacy is a stronger privacy model where users privatize their own data before releasing it for (arbitrary) analysis. As you might expect, the stronger privacy guarantee means worse utility, sometimes much worse [2].
edit: shameless plug. check out tonic.ai for a solution to the above problem.
I recommend watching it if you're interested at https://homepages.cwi.nl/~boncz/sigmod-pods2019.html (top-left vid)
(as a side-note Frank McSherry received SIGMOD Test Of Time Award for his Differential Privacy paper at the same conference).
Of the entities that remain, they fall into two buckets: Ones powerful enough that they already have personally identifiable data without the need to deanonymize anonymous data sets and ones small enough that they don't have the capabilities to deanonymize.
If you're a government, you don't need to rely on anonymized data sets, you have the sets with the labels already. If you're a stalker or internet troll or whatever, it's far easier to just pay one of the PI websites $29 to get far more data on a person than any deanonymized dataset will give you.
From an article on the subject:
>Recital 26 of the GDPR defines anonymized data as “data rendered anonymous in such a way that the data subject is not or no longer identifiable.” Although circular, this definition emphasizes that anonymized data must be stripped of any identifiable information, making it impossible to derive insights on a discreet individual, even by the party that is responsible for the anonymization.
Bitcoin for example, uses pseudonyms... not anonymity. A pen name or a hn username is a pseudonym. A voting system needs to be anonymous not pseudo-anonymous^, by using a pseudonym. If each voter had a secret number that is attached to each vote, that is a pseudonym.
"L is 32 years old. She works as a nurse in Moscow." - L is a pseudonym. It isn't anonymous even though the name is ommitted.
^This can get grey, as even a piece of paper with an X on it will carry certain metadata or related data: which voting booth, etc. But, the goal is anonymity. IE, the X cannot be tied to anything else.
For one, that this data is improperly anonymized would make it an easy avenue for malicious nation-state actors to use to track/analyze/destabilize the population. If I am a government with an interest in freaking out the US public, I could quite easily de-anonymize sensitive datasets and begin using them for wide-scale harassment, identity theft, etc. on an automated basis.
The lowering of the bar makes it easier for Johnny Troublemaker to start harassing people based on their PII as well. Instead of paying for the data, just download some datasets and run a Julia notebook against them. Maybe not much changes for the targeted stalking case, but now you can cast a wide net when looking for someone to mess with.
I guess then the interesting question is how high does k have to be to call it anonymous vs pseudonymous.
Also cool: this is how Have I been Pwned v2 works - if you send only the first 5 characters of a hash then it's guaranteed there's hundreds of matches and the server doesn't know the real password that had that hash prefix: https://www.troyhunt.com/ive-just-launched-pwned-passwords-v...
The number of Johnny Troublemakers who are randomly spraying hate based on PII is about the same as the rate of people throwing rocks off highway overpasses onto cars below. It's simply not a significant enough problem to be worth worrying about.
If nothing else, I appreciate the Differential Privacy effort, if only to show the problem space is wicked hard.
I worked in medical records and protecting voter privacy. There's a lot of wishful thinking leading to unsafe practices. Having better models to describe what's what would be nice.
If it is possible, it's not anonymous per GDPR's definition and that is what counts.
The difference is the other proposed alternatives more directly suggest risk is involved.
It's a nice ESL example because technically, I don't think you're suggestion is wrong. In practice I think few would infer its implications.
> My go-to example to explain this is very simple: Let's
> say we reduce birthdate info to just your birthyear,
> and geoloc info to just a wide area. And then I have
> an pseudonimized individual who is marked down as
> being 105 years old.
> Usually there's only one such person.
Source: Pages 96-97 of the combined legislation, available at: https://www.hhs.gov/hipaa/for-professionals/privacy/laws-reg...
You are allowed to roll your own de-identification method, as long as the person doing so is an expert on statistics and de-identification and they document their analysis of why their method is sound. To my knowledge, most entities use the "safe harbor" approach of wiping any data in the legislated blacklist of dimensions.
doesn't clarify how much information you already have about the individual. There is a distinction between being able to identify someone without any prior knowledge about them vs re-identifying them. I don't think the GDPR is clear about that.
Very very close to the existing "deanonymization" which is essentially the opposite.
I think that for any size k less than the total size of the database, it is not anonymous. In cases like this, an overly strict definition favoring privacy is the only way to protect people. Similar to how we call 17 year olds children and treat them as such under law even though a 17 year old is far closer to an 18 year old than they are to a 5 year old (yes, there are some exceptions, but these are all explicitly called out). Another example of such an extreme is concerning falsifying data or making false statements. Even a single such statement, regardless of the number of true statements, destroys credibility once found when trust is extremely important. This is why even a single such statement can get one found in contempt of court or destroy a scientist's entire career (and even cast doubt on peers who were innocent).
Overall it is quite messy because it is a mix of a technical problem with a people problem.
The reason is that you are thinking of an example that's not nicely compatible with differential privacy. The basic examples of DP would be something like a statistical query: approximately how many people gave Movie X three stars? You can ask a bunch of those queries, adding some noise, and be protected against re-identification.
You can still try to release a noisy version of the whole database using DP, but it will be very noisy. A basic algorithm (not good) would be something like
For each entry (person, movie):
with probability 0.02, keep the original rating
otherwise, pick a rating at random
Whenever a large enough database exists with individual data, we are doomed.
https://icml.cc/Conferences/2019/ScheduleMultitrack?event=43... there is a video link on this page
Even aggregated data will loose the anonymisation characteristics when we are speaking of low volumes of data.
Number of cancer patients in the area A: 1 Number of residents in the area A: 1
Wouldn't that require that every field of every record in the database be globally unique?
If something as simple as gender is a field in the database, the best k you could get would be the lowest count of records of each existent gender option.
I think what you're asking for is that any piece of data stored about someone be extensionally equivalent to "this is a human being" and no more which is not very useful (in an information-theoretic sense it has exactly zero use).
Let say that you got 20,000 inhabitants, you'll only need about 14 fields that are binary, much less fields if they are not binary (which is quite likely to happen). You'll most likely already got the gender... Even if you limit the age to 10 possible values, that's equivalent to 3 binary fields!
Would that example fall within the remit you outline and as such - skirt the whole GDPR aspect?
There are problems with Point 3: we're continually surprised with how effectively smart people can identify people in datasets expected to be 'safe'. You've also not accounted for that a collection of non-identifying attributes may become identifying.
That said, the GDPR is largely about prohibiting unnecessary data collection, in the spirit of Point 3. Hopefully it'll help at least a little.
So, I would imagine everyone becomes more powerful over time.
That concerns me most around places that process data for other companies (e.g., Cambridge Analytics, Facebook, Google, Amazon). These places could have access to many different data sets relating to a person, and could potentially combine these data sets to uniquely identify a single individual.
I recently looked at something that I gave a fake zip, birth date, and gender. Based on statistical probabilities it gave a 68% chance of a large data set having 1-anonymity. Wasn't clear what they were considering large, so could be bogus, but if true imagine what could easily be done with 10+ unique fields (e.g., zip, birthdate, gender, married?, # of children, ever smoked?, deductible amount, diabetes?, profession, BMI).
The earlier poster is right, only aggregate data is truly anonymous.