Towards a causality based analysis of anonymity protection in indeterministic mix systems

Mixes are well known techniques providing strong traffic information protection on the network level. The main problem of all “practical” Mixes is their leakage of some information to the passive global attacker. Accumulating this information allows disclosing the communication patterns of the users and hence undo the traffic protection. There are two main approaches known in the literature that evaluate this information flow which are known as Disclosure attacks and Statistical Disclosure attacks. Disclosure attacks are based on logical inferences from causalities in a deterministic Mix system and therefore analyse more simple anonymity models, but reveal exact information. In contrast to this, statistical approaches apply to more complex anonymity models, but are error prone. Such a model covers indeterministic Mix systems that add distortions to causalities in it. A combination of those two approaches should benefit from their strengths and find ways of getting around their weaknesses. In this paper we propose such an idea by extending the Hitting-Set Attack (a fast version of the Disclosure attack) to indeterministic Mixes. We show the benefit of deploying causalities despite distortions by including statistical measures, i.e. our approach reveals the exact set of friends of a user (say Alice) of any accuracy.