Arvind Narayanan and Vitaly Shmatikov. Robust De-anonymization of Large Sparse Datasets. Proceedings of the 2008 IEEE Symposium on Security and Privacy (S&P 2008).
Microsoft which sponsors the award had this to say about this year's winners:
"The films we watch, the products we buy and the subjects that interest us can tell others a lot about who we are — information that, rightly, we might wish to keep to ourselves. The internet, to which we entrust so much of this information, works because of our faith in the confidentiality of the behaviours we exhibit and in a shared sense of responsibility. Work from three teams, recognised today in the Microsoft-sponsored Privacy Enhancing Technology Awards, suggests that more can be done to ensure that people can be confident that their privacy will be protected online.
Arvind Narayanan and Vitaly Shmatikov, researchers at the University of Texas, began looking into large, publicly available data sets that were cleansed of names or other personally identifiable information. They very quickly discovered a major privacy risk — anonymised data sets could be used to re-identify individuals using efficient algorithms. They took the theory and tested it in reality, examining anonymised movie ratings and dates of rating for 500,000 users published by a major online movie rental service. Narayanan and Shmatikov found that they could identify a user's ratings record with only five to ten educated guesses relating to some of those ratings. Narayanan and Shmatikov proceeded to develop a theory that shows how this applies to other data sets such as an online store's purchasing records.
Their work, which earned them the overall 2008 PET award, shows the danger in releasing apparently anonymised data without better methods to ensure that it can't be compromised. Their research will be invaluable in promoting and informing the development of ways to release data with provable privacy guarantees...
Runners-up Steven J. Murdoch and Piotr Zieliński of Cambridge University also uncovered possible dangers to our online anonymity. Their paper discusses and analyses, for the first time, the possibility of surveillance at internet exchanges (IXes). High volumes of traffic pass through these exchanges when travelling from one network to another, making them an ideal point from which to gather surveillance data. Murdoch and Zieliński first showed that a single IX could observe a large fraction of traffic on the experimental Tor network, a distributed network of relays that bounces traffic around the internet to facilitate anonymous access to information. Despite the fact that the amount of data was overwhelming, Murdoch and Zielinski's study looked into how much they could learn about users from only a snapshot of the surveillance data gathered.
Using techniques that are realistic with today's network technology, they showed that this method of looking at a small sample of data was surprisingly effective and could uncover a lot of information about Tor users. This research is notable because it could change the way researchers think of the security of network privacy systems, and is likely to be influential in future research about internet surveillance."One of the runners up, Steven J. Murdoch notes his and his colleagues success at Light Blue Touchpaper.