On the Effectiveness of k-Anonymity Against Traffic Analysis and Surveillance

Abstract

The goal of most research on anonymity, including all currently used systems for anonymity, is to achieve anonymity through unlinkability: an adversary should not be able to determine the correspondence between the input and output messages of the system. An alternative anonymity goal is unobservability: an adversary should not be able to determine who sends and who receives messages. We study the effect of k-anonymity, a weak form of unobservability, on two types of attacks against systems that provide only unlinkability.