Can math help us understand the limits of privacy for social network sites? From an article in Technology Review this week:
Today, Aleksandra Korolova at Stanford University with Ashwin Machanavajjhala and Atish Das Sarmait [have] worked out a fundamental limit to the level of privacy that is possible when social networks are mined for recommendations.
That’s quite a task given that there are various different approaches to making recommendations. However, Korolova, Machanavajjhala and Sarmait have come up with a general model that captures the essence of the problem.
Their approach is to consider a general graph consisting of various nodes and the links between them. This may be network in which the nodes are books, say, and a link between two nodes represents the purchase of one book by the owner of another. The team consider all these links to be private information.
Korolova, Machanavajjhala and Sarmait then consider an attacker who wants to work out the existence of a link in the graph from a particular recommendation. So given the knowledge that people who bought book x also bought book y, is it possible to determine a purchase decision made by a specific individual?
To do this, Korolova, Machanavajjhala and Sarmait define a privacy differential as the ratio of the likelihoods that the website makes such a recommendation with the using the private purchase decision in question and without it.
The question they then ask is to what extent can recommendaitons be made while preserving this privacy differential.
It turns out that there is a trade off between the accuracy of the recommendation and the privacy of the network. So a loss of privacy is inevitable for a good recommendation engine.
Read more on Technology Review.