PolySphinx: Extending the Sphinx Mix Network with Better Multicast Support

A lot of communication in the modern world happens digitally. However, when used carelessly, such communication channels can leak private information to third parties such as network operators or service providers. While end-to-end encryption can protect the content of messages, metadata such as the sender-recipient relationship is still leaked. One way to preserve privacy are mix networks, as introduced by Chaum, which relay messages over a series of nodes to make them untraceable.
A building block for a mix network is the mix format, which describes how the routing information needs to be packed and encrypted for the mix nodes to consume. Unfortunately, common mix formats are built for one-to-one messaging, even though a lot of communication is done in groups. This makes them inefficient to use.
In this thesis, we will extend the Sphinx mix format with capabilities that make it better suited for multicast messages, for example for group communication, by lowering the latency and the bandwidth requirements for multicast messages.
Our PolySphinx approach allows a mix node to send the same payload to multiple recipients and relies on deterministic key trees that allow the recipient to reconstruct the original message.
... mehr
We also devise and analyse alternative approaches based on key-homomorphic pseudorandom functions and updatable encryption and evaluate them against our PolySphinx suggestion.
Our evaluation shows that we can reduce the latency of multicast messages in a group with 128 members from 34.9 seconds for the naive approach and 8.7 seconds with MultiSphinx to 2.1 seconds with PolySphinx while using less bandwidth in sending the data. This opens up new time-sensitive applications such as collaborative editing or instant messaging to be used with mix networks.