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.

Anonymous metadata-private voice call protocols suffer from high delays and so far cannot provide group call functionality. Anonymization inherently yields delay penalties, and scaling signalling and communication to groups of users exacerbates this situation. Our protocol Pirates employs PIR, improves parallelization and signalling, and is the first group voice call protocol that guarantees the strong anonymity notion of communication unobservability. Implementing and measuring a prototype, we show that Pirates with a single server can support group calls with three group members from an 11 concurrent users with mouth-to-ear latency below 365 ms, meeting minimum ITU requirements as the first anonymous voice call system. Increasing the number of servers enables bigger group sizes and more participants.

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.

In areas such as manufacturing or logistics, it is beneficial for everyone to share access capacity with others. Increased efficiency increases profits, lowers prices for consumers, and reduces environmental impact. However, in order to share a resource such as manufacturing capacity, suitable partners must be found. Ideally, a centralized exchange is used to find partners, but this comes with privacy risks. Since participants in the exchange are competitors, they can use information about someone else’s capacity to their disadvantage, e.g., by undercutting the prices of an already poorly performing competitor to drive it out of business. In this paper, we show that such an exchange can be set up without compromising the privacy of its participants. We formalize privacy goals in the context of resource sharing via an indistinguishability game. We also propose Bazaar, a protocol that allows participants to find suitable matches while satisfying our formal privacy goals.