Private messaging has seen widespread interest in recent years. With End-to-End encryption widely deployed, users expect their messaging to be private.
This is in stark contrast to reality, where metadata analysis is used for anything from targeted advertising to mass and targeted surveillance. To prevent metadata collection against both service providers and a suffficiently capable adversary so-called anonymous communication networks have been proposed. Their goal is to unlink a message being routed with it's sender and receiver, while still traversing from sender to receiver. Not-so recent revelations about state-level actors have shown that an adversary passively monitoring all network links is not unreasonable. Mix networks have been proposed to use onion encryption in addition to delaying a message at each hop to mix it with other messages. This, by its very nature, introduces delays, in contrast of todays low-latency Instant Messaging.
This work analyzes if mix networks can still cover the Instant Messaging use case to protect against metadata analysis and ensure a private messaging. From a theoretical framework of anonymity provided by a network, this work goes in detailled discussion about threat modelling and examines Instant Messaging constraints and idiosyncrasies and tries to reconcile these with the underlying properties of mix networks.