Here's some backstory, from the 1990s when the Massachusetts' Group Insurance Commission released "anonymized" health data:
''At the time GIC released the data, William Weld, then Governor of Massachusetts, assured the public that GIC had protected patient privacy by deleting identifiers. In response, then-graduate student Sweeney started hunting for the Governor’s hospital records in the GIC data. She knew that Governor Weld resided in Cambridge, Massachusetts, a city of 54,000 residents and seven ZIP codes. For twenty dollars, she purchased the complete voter rolls from the city of Cambridge, a database containing, among other things, the name, address, ZIP code, birth date, and sex of every voter. By combining this data with the GIC records, Sweeney found Governor Weld with ease. Only six people in Cambridge shared his birth date, only three of them men, and of them, only he lived in his ZIP code. In a theatrical flourish, Dr. Sweeney sent the Governor’s health records (which included diagnoses and prescriptions) to his office.''
I had to deal with the converse of the problem when I was working for a company that ran the vehicle smog checking for the state of Illinois. A driver's license id was composed of birthdate, sex, and some location information (I dont remember exactly what) for the reasons mentioned by jdp23 it worked quite well, except for identical twins, who had the same driver's license id. (Registrations ofter were processed by hand at drug stores. The driver's license was used to disambiguate ambiguous renewals.)
The state of Texas complicated things by allowing a family to have the same license plate for all their cars. One family had seven vehicles, all with the same license plate number. Florida would issue the same plate to complete strangers. One man arrested with great drama, because a bank robber (or some such undesirable) had the same (legal) plates.
My GF has such a common name that her doctor has to check which one of three she is. The last time she tried to get her driver's license renewed online, she was told she had to go to the DMV in person. She asked why and was told she was a "Code 5". She reported to the DMV and told the woman that she was a Code 5. There dropped jaws and a hurried conference with a supervisor who called Sacramento and had a lengthy conversation with comments like, "Yes I'm sure. She's right here." Finally she got impatient and asked, "What's Code 5?"
The clerk said, "You're dead and it was verified by medical personnel." She did eventually get her license renewed. Officially I live with a zombie. It isnt as bad as the movies portray.
My wife had her wallet stolen on the T (in Boston) once, which would have been manageable but for the fact that Massachusetts driver's license ID's were your Social Security number. The thief (or someone) then used her SSN to open a series of credit cards and rack up a bunch of charges—computers, car repairs, etc.—the aftermath of which took at least a few hundred hours of hassle spread over three or four years to clear up. (Getting our first mortgage somewhere in there made it even more painful.) Mercifully, it eventually cleared up.
MA driver's licenses no longer use SSN as far as we can tell.
Including birth year helps significantly. Assuming an even distribution of births, you'd expect 54000/365 ~ 148/day. Then knowing gender lets you cut that in half. Dividing again by the age distribution of voters gets that down to a reasonable number.
This is sort of the reverse of the "curse of dimensionality", for those interested in machine learning (http://en.wikipedia.org/wiki/Curse_of_dimensionality). From an ML perspective, as you add dimensions to a dataset, the amount of data you'd need to accurately model the data without overfitting (i.e. without memorizing specific details of the sample rather than underlying trends) grows very fast, because due to the combinatorics you end up with extremely sparse coverage of the overall possibility space even with huge data sets.
The reverse of that phenomenon is that, given a data set in a high-dimensional space (even 3 dimensions, if each dimension has more than a few bits of entropy), it will cover the dimensions very sparsely (even if it's large!), and therefore it's relatively easy to recover specific details of the sample from the aggregate statistics.
The Curse of Dimensionality is a key piece of knowledge to keep in mind anytime you're building some software that searches/sorts/filters/etc. a large dataset and your users keep asking for things like "but I want to search based on <some new thing>!"
Someone has to be the gatekeeper on your dimensions.
I should run that on the Israeli population census - which has been illegally leaked several times [1].
The ZIP codes in Israel are per-street, not city. Given Israel's population of just under 8M, I believe a very high percentage (95% <) of unique people can be found.
Then there are those of us who have unique enough names that you can pretty much look us up and find there's only two in the whole US (and we're related). Having been a DBA at one point, it's always fun to tell folks that "really, if you just search for my name I guarantee you'll find me faster". Heck in most cases a search in a system that separates first and last names will let me be found with just my first name. If it weren't for that lousy Welsh actor, that would work on Google also (although full name turns me up as most of the front page).
My point is that this shouldn't be THAT surprising. I suspect full name and gender would uniquely identify a fair portion of the US as well. We're not as homogenous as some societies and I think this proves it...
Birth location =/= mailing address zipcode. Babies are usually born in hospitals, and thus parents from many areas concentrate in one specific building. When you re-distribute these births out to their respective homes around the county, the zip code becomes much more important.
In towns like mine, however, 40,000 people share the same zip code with the hospital. I'm sure there are quite a few more town like mine throughout the US.
US pop in 2000: 280,000,000 —
US births in 2000: 4,000,000 —
US births per day: 10,958 —
Fraction of US pop that 40,000 represents: 0.0001428 —
Number of births per day for the 40,000: 1.56
That seems inline with the conclusion of the paper. See any mistakes?
October 8th is an odd date. Since it's my birthday as well (long before 1990 though) I have taken note that I run across very few with that birthday, let alone early October birthdays. Is it statistically a low-birth month? I'd love to know.
On a side note, Happy 21st Birthday in just over a month!
These days it doesn't surprise me, it seems like doctors are willing to induce at the drop of the hat these days. So why not to keep their holiday clear.
October 8th? It seems like a decent % of people share your birthday (me among them). Certainly feels like a weird to me. How many thousand people read a page (given that it has a moderate up-vote)?
Putting it to a non-scientific test, where I grew up is within the zip code of 98632. From the 2000 census there are 47,202 within that zip code. This is probably a good average city for America - not too big, not too small. Based on the fact that there are 366 possible (year excluded) birthdays (I'm including Feb. 29th) and only two genders, just about the best I can do for uniquely identifying people in that county is 1 in 64. Add in the year and what I would assume is an even population between the ages of 1 to 50 and that gets you closer to 1:1. Not bad.
A zip code with large populations probably are more around 50% than 87%, and obviously the reverse is true as well. I wonder what the population size for a zip code would have to be to be really close to 100%. Just throwing some numbers in a calculator I'd guess at 15-20k people would be damn close. So 10k is probably just about a unique identifier.
I didn't at first to show the 1:64, and then I added the year (well 50 of them) to show how I got closer to the 87% with my extremely un-scientific and fuzzy math.
Using the tools at USPS.com, I could find examples where ZIP+4 was unique down to just 6 apartments in a dense neighborhood. Just type in a street name with lots of apartment buildings on it.
Longview probably just has the one zip code. Seattle has 59, for just over 10000 average per zip code, so we up here are probably a bit worse in a big city.
Worse or better? With only 10k per zip you'd get very close to a 100% unique identifier.
I realized after looking at both Portland and Seattle zip codes that they seem to be distributed better than the less dense areas so you do have very few zip codes over 20k.
While I find this fascinating, I'm sure this is old news to people in the business, like the people that run the grocery/chain store savings programs.
What I'd be really interested to see is why this works, and what it tells us about distribution of population by zip code. I'd imagine the places where this doesn't work as well, are the most densely populated zip codes, where the likely hood of duplicates on the given key increases, but I would never have guessed that the accuracy would be anywhere near 87%. (maybe there's alot more zipcodes than what I thought? maybe they used zip+4?)
Simple information theory; in a world of 6 billion people, 33 bits serves to uniquely identify anyone. 33 bits is a really low bar. It works because it can't hardly help but to work, sort of like the birthday paradox. In the US with approx 312 million (wikipedia) that's approximately 28.2 bits.
It doesn't tell us much about zip code distribution because zip codes are chosen to have approx the same number of people in each. As it turns out, that's exactly how you'd go about maximizing the amount of information the zip code carries... which is unsurprising since that's the entire purpose of a zip code. Gender is almost exactly one bit, and date of birth is 15ish bits with some bad uniformity assumptions, zip is another 15ish with bad uniformity assumptions[1], that's 31-ish total, subtract off 3-ish for the bad assumptions and you get 28, which covers 2^28 = 268,435,456 people, which is pretty close to the number cited (.87 times 312,000,000 = 271,440,000). I'll cop to tuning the fudge factor of three bits to nicely match the number given, but the bit count itself just comes from the space of possibilities.
In general, if you model this as an N balls in M bins problem, then even when N == M, you'd expect a fair amount of anonyonomity preserving collisions. Maybe 1/2 of people would collide. As we then double the number of bins, we'd roughly expect the number of collisions to be cut in half.
If you imagine putting 100 balls (people) into 800 = 100 * 2^3 bins (number of different birthday-zip-gender encodings) at random, about 1/8 of the bins will have more than one ball (person) [okay, this estimate is somewhat off by a smallish constant factor, it's only true that the 100th ball tossed will collide with probability 99/800 ~= 1/8 if there were no existing collisions, and the earlier balls thrown have less to collide with], and not be uniquely identifiable.
> Simple information theory; in a world of 6 billion people, 33 bits serves to uniquely identify anyone. 33 bits is a really low bar. It works because it can't hardly help but to work, sort of like the birthday paradox. In the US with approx 312 million (wikipedia) that's approximately 28.2 bits.
It's a powerful idea. I wrote a whole essay analyzing the anime _Death Note_ using the 33 bits idea (http://www.gwern.net/Death%20Note%20Anonymity) and I'm sure that's not even the tip of the iceberg.
The US population is 300 million and there's about 43,000 zip codes in the US. Assuming an even distribution, that's about 7,000 people per zip code. Cut it down to just one gender and we're at 3,500. The probability of a chosen person in that group having a a unique birthday is (364/365)^3500 = 0.0068%. Now, if we say that the person could have been born in one of the past sixty years, we get (21914/21915)^3500 = 85% as the probability that this person has been uniquely identified.
Birth date is pretty granular as well. A quick trip to the interwebs gives about 11k-12k people born each day, or 6k of each gender. There are 100k possible ZIP codes. The birth dates aren't evenly distributed, but they're reasonably close. The ZIP codes probably have a lot of clumping, but in dense urban areas they usually start cutting the areas into smaller pieces. The long tail of ZIP codes is probably well-populated. Out of 6k boys and 6k girls that share a birth date, expecting 5k of each to happen to land a unique ZIP out of 100k sounds reasonable to me.
Point of interest: there are 100K possible ZIP codes but only 42K-ish are actually in use in the US. Not that I think this makes it unreasonable for 5K of each to land unique ZIPs.
It turns out that zip codes aren't as populous as you might imagine.
As of the Y2K census, only a dozen zip codes have over 100,000 residents -- 80% of all zip codes have less than 15,000 residents, with the median zip code at 2,500.
Some zip codes have zero residents -- a few large office buildings have their own zip codes, but nobody actually has a home address there. Examples: the Empire State Building, the Pentagon, the former World Trade Center, IRS tax processing centers.
This is an interesting statistic for another reason aside from de-anonymization, particularly directory listing applications. A lot of web sites have url's to access the user's profile page by their username. For popular sites, it's always a rush to register "yourname" as a username so that you can get website.com/<yourname>. Inevitably, your name gets registered by some one else and you're stuck picking a nick name or appending a randomized letter set to it.
I've been pondering a useful way to have /<yourname>in a URL, so that everyone with that name can use the url containing it without collisions. Of course, I always end up with something like website.com/a3fx/<yourname>. Which is arbitrary, and ugly. However, with this stat it seems we have something close to a non colliding, pretty, meaningful addressing scheme. Ie: website.com/<dob>/<gender>/<zip>/<yourname>, sure it's a bit long but it provides assurance you're getting who you think your getting.
A problem with that is that people move, so zip codes change. You could fix that by substituting artificial, user-chosen groupings for zip codes if you used enough of them to have a similar distribution. Users could pick a grouping based on their interests, and you could even keep the geographical aspect of it by treating them as "neighborhoods". People who play the stock market could choose WallStreet, science fiction fans could choose Area51, wine aficionados could choose NapaValley, and so on.
I agree. That said, using actual gender rather than assigned sex only serves to identify people more uniquely. I wonder if that would have an appreciable effect on the stats or if it would fall within error bars.
You'd have to have a pretty long dropdown menu in the data-mining centers for all the genders people self-identify these days. Some people might be uniquely identifiable on that value alone.
If we want more anonymized datasets, maybe we should be asking for approx. age or year of birth instead. I doubt that most things that ask for DOB need anything more than granular than that.
No, we should be asking for exact age and year, and then jittering each part of it by plus/minus 2 at random. Won't affect the data analysis, but will increase the anonymity considerably.
I wish. Unfortunately, most sites need this for legal reasons, to determine whether or not the user is above or below a certain age.
One could theoretically ask "how old are you" but then you don't know when to lift limitations. Say a user joins six months before their 18th birthday. Are you going to block 18+ content for a whole year from then?
How many sites filter content based on age and really do so selectively based on a birthdate? Most age verifications, even ones that request a date, seem to be just asking the question, "Are you of legal age?"
(I prefer websites just ask that binary question, like this brewery - http://www.newbelgium.com - instead of making me waste time with a date input.)
This might work well in a fixed database, but it would not work in real life since people change zip codes when they move every couple of years, or have more than one zip code (home, office).
The only way to identify people in real life is to issue them a public ID number that can be used in conjunction with a private ID number (SS#).
Gender is a bit of a stretch, if technically changeable. I don't know much on the subject but I would wager that the proportion of people who have changed gender is not statistically significant enough to change the 87% figure.
Do we know if she took into account population migration / movement? Looking at the description it doesn't look like it, but I'd be really curious to see how that affects the stat. Or how the stat changes if the zip code is tied to the person's DOB. In that scenario it probably drops a lot, because (I'm assuming) most people are born in a hospital, and there isn't a hospital in every zip code. So to my first comment on population movement, maybe that's actually a representation of the effect of population migration / movement. Cool.
About a year ago, I did a project for de-duping customer entered contact info. We had less than 100k records for any particular region (Bay Area, New York, etc.) From what I recall, we were able to confirm identity in about 80% of cases using Name, DOB, and zip code.
By far the best metric is phone number, that bumped us up over 97%. If the comparison was limited to only three metrics, then we would use Name, DOB, and phone number. In reality, we also compare zip code, street address, and contacts (like friends on facebook), in that order.
It would be interesting to see if on average, people change their phone number less often than their name (marriage) or address (renters).
''At the time GIC released the data, William Weld, then Governor of Massachusetts, assured the public that GIC had protected patient privacy by deleting identifiers. In response, then-graduate student Sweeney started hunting for the Governor’s hospital records in the GIC data. She knew that Governor Weld resided in Cambridge, Massachusetts, a city of 54,000 residents and seven ZIP codes. For twenty dollars, she purchased the complete voter rolls from the city of Cambridge, a database containing, among other things, the name, address, ZIP code, birth date, and sex of every voter. By combining this data with the GIC records, Sweeney found Governor Weld with ease. Only six people in Cambridge shared his birth date, only three of them men, and of them, only he lived in his ZIP code. In a theatrical flourish, Dr. Sweeney sent the Governor’s health records (which included diagnoses and prescriptions) to his office.''
Source: http://arstechnica.com/tech-policy/news/2009/09/your-secrets...