Mix networks are a cornerstone of anonymous communication, protecting users' relationships by relaying their messages through a series of mix nodes. To accommodate large payloads, deployed systems rely on message fragmentation, but this seemingly benign feature unwittingly opens a subtle door for adversaries. In this paper, we show that fragmentation enables adversaries to tag messages by suppressing single fragments and thereby break sender-recipient unlinkability, striking at the core privacy guarantee of mix networks. We demonstrate the practicality of this attack on Nym, a real-world deployed mix network. To address this threat, we design a lightweight mitigation that incurs only little overhead in both packet size and processing time. We provide a formal model of fragmentation in mix networks and prove that our mitigation restores unlinkability in this model.

Anonymous communication is vital for enabling individuals to participate in social discourse without fear of marginalization or persecution. An important but often overlooked part of anonymous communication is the bootstrapping of new communication channels. If Alice wants to communicate with Bob, she must first learn his in-system identifier. In synchronous designs, message exchange is only possible once both communication partners have agreed to communicate. Thus, Alice must notify Bob of her intent, Bob must learn her in-system identifier, and Bob must acknowledge her notification. This bootstrapping process is generally assumed to occur out-of-band, but if it discloses metadata, communication partners are revealed even if the channel itself is fully anonymized. We propose Sabot, the first anonymous bootstrapping protocol that achieves both strong cryptographic privacy guarantees and bandwidth-efficient communication. In Sabot, clients cooperatively generate a private relationship matrix, which encodes who wants to contact whom. Clients communicate with k ≥ 2 servers to obtain ''their'' part of the matrix and augment the received information using Private Information Retrieval (PIR) to learn about their prospective communication partners. Compared to previous solutions, Sabot achieves stronger privacy guarantees and reduces the bandwidth overhead by an order of magnitude.

Mix networks allow communication with strong anonymity guarantees. In theory, mix networks can scale indefinitely, as additional nodes can be added to the network to support new users. However, one factor that limits scalability in current designs is the need for all clients to know both the identity and the key of every available mix node. In circuit-based onion routing, a mechanism that does not require this knowledge to be globally available exists, but it relies on the interactivity of the circuit construction to keep its security guarantees. We therefore set out to investigate whether we can transfer such a mechanism to the context of message-based mix networks. In this paper, we propose Aimless Onions, the first mix format that enables clients to create onions in a mix network without knowing which nodes are available. Rather than downloading topology information, clients only need to acquire constant-size public parameters. Thus, Aimless Onions overcomes an important scalability limitation in mix networks, while retaining the same security guarantees as the state of the art. Using Aimless Onions, clients sending 25 messages per hour save 74% of bandwidth compared to using Spinx packets and topology information download, even at today's network sizes.

Mix networks are a well-known technique to hide communication metadata, but incur a high overhead especially in group communication settings. This hinders their adoption in real-world usage, as group communication makes up a big part of modern communication patterns. In this paper, we introduce "PolySphinx", a mix format that is a step towards efficient anonymous multicasting and allows a mix node to replicate the message payload to multiple recipients. We prove that PolySphinx does not compromise on the anonymity offered to users, while considerably reducing the latency of group messages: In a group with 25 members, the average latency drops from 6.1s using the state-of-the-art Rollercoaster approach to 4.1s using PolySphinx.

Publish/Subscribe systems like Twitter and Reddit let users communicate with many recipients without requiring prior personal connections. The content that participants of these systems publish and subscribe to is typically public, but they may nevertheless wish to remain anonymous. While many existing systems allow users to omit explicit identifiers, they do not address the obvious privacy risks of being associated with content that may contain a wide range of sensitive information. We present 2PPS (Twice-Private Publish-Subscribe), the first pub/sub protocol to deliver strong provable privacy protection for both publishers and subscribers, leveraging Distributed Point Function-based secret sharing for publishing and Private Information Retrieval for subscribing. 2PPS does not require trust in other clients and its privacy guarantees hold as long as even a single honest server participant remains. Furthermore, it is scalable and delivers latency suitable for microblogging applications. A prototype implementation of 2PPS can handle 100,000 concurrent active clients with 5 seconds end-to-end latency and significantly lower bandwidth requirements than comparable systems.