A First Step in Facilitating Searches for Bad Guys with Minimal Harm to the Privacy of the Good Guys

In a recent article in Proceedings of the National Academy of Sciences entitled "Private algorithms for the protected in social network search", Kearns et al describe algorithms for searching social networks that distinguish between good guys (those whose privacy should not be violated or violated only minimally) and bad guys (those who have fewer or lesser privacy rights).

The abstract is as follows:

Motivated by tensions between data privacy for individual citizens and societal priorities such as counterterrorism and the containment of infectious disease, we introduce a computational model that distinguishes between parties for whom privacy is explicitly protected, and those for whom it is not (the targeted subpopulation). The goal is the development of algorithms that can effectively identify and take action upon members of the targeted subpopulation in a way that minimally compromises the privacy of the protected, while simultaneously limiting the expense of distinguishing members of the two groups via costly mechanisms such as surveillance, background checks, or medical testing. Within this framework, we provide provably privacy-preserving algorithms for targeted search in social networks. These algorithms are natural variants of common graph search methods, and ensure privacy for the protected by the careful injection of noise in the prioritization of potential targets. We validate the utility of our algorithms with extensive computational experiments on two large-scale social network datasets.

The paper concludes that

...despite the fact that using network analysis to identify members of a targeted population is intrinsically contrary to the privacy of the targeted individuals, we have shown that there is no inherent reason why informational privacy guarantees cannot be given to individuals who are not members of the targeted population, and that these privacy guarantees need not severely harm our ability to find targeted individuals.

This conclusion does NOT mean that good guys suffer zero loss of privacy or that there is zero loss of effectiveness in searching for bad guys. But it does mean that the tradeoff can be made explictly, which is a step beyond where we are today.

This paper presents a proof of concept, but as the paper itself notes, it is not a complete solution to the practical problem. More research of this sort is thus needed.