This is of a kind with several other very successful de-anonymization efforts in the past few years.
There's probably some clever way to express the general problem in information theory terms and prove that any set of data with certain characteristics must be de-anonymizable to some given extent. 6 billion people in the world is still just about 33 bits to uniquely identify an individual (and of course generally we're not talking global population), and so even a very small number of bits that can be correlated back to the real world in arbitrarily clever ways will reveal real-world identities in a putatively anonymous data set. It wouldn't take much to clean that up into a mathematically rigorous statement; no matter how you slice it, low tens of bits will tend to identify people and that's a low threshold.
Well, that was easy; my work here is done. Now if you'll excuse me, I'm off to prove white is black and get myself killed on the next zebra crossing.
I'm browsing through there and see you've got good coverage on HN already. Is your thesis available publicly anywhere? I'd be interested in reading the full-strength version.
The rest of my thesis is (almost literally) a concatenation of several of my papers, most of which I've covered on my blog; a quick list is here: http://randomwalker.info/publications/
Comments
This is of a kind with several other very successful de-anonymization efforts in the past few years.
There's probably some clever way to express the general problem in information theory terms and prove that any set of data with certain characteristics must be de-anonymizable to some given extent. 6 billion people in the world is still just about 33 bits to uniquely identify an individual (and of course generally we're not talking global population), and so even a very small number of bits that can be correlated back to the real world in arbitrarily clever ways will reveal real-world identities in a putatively anonymous data set. It wouldn't take much to clean that up into a mathematically rigorous statement; no matter how you slice it, low tens of bits will tend to identify people and that's a low threshold.
Indeed.
Some academic with too much time on his hands wrote an entire Ph.D thesis on that very idea [hint: me :-)] http://33bits.org/about/
Well, that was easy; my work here is done. Now if you'll excuse me, I'm off to prove white is black and get myself killed on the next zebra crossing.
I'm browsing through there and see you've got good coverage on HN already. Is your thesis available publicly anywhere? I'd be interested in reading the full-strength version.
The introductory chapter of my thesis is available as a standalone document here: http://randomwalker.info/misc/thesis-intro.pdf It's a bit dull and academic.
The rest of my thesis is (almost literally) a concatenation of several of my papers, most of which I've covered on my blog; a quick list is here: http://randomwalker.info/publications/