Periscoping: Private Key Distribution for Large-Scale Mixnets

Mix networks, or mixnets, are one of the fundamental building blocks of anonymity systems. To defend against epistemic attacks, existing free-route mixnet designs require all clients to maintain a consistent, up-to-date view of the entire key directory. This, however, inevitably raises the performance concern under system scale-out: in a larger mixnet, a client will consume more bandwidth for updating keys in the background.

This paper presents Periscoping, a key distribution protocol for mixnets at scale. Periscoping relaxes the download-all requirement for clients. Instead, it allows a client to selectively download a constant number of entries of the key directory, while guaranteeing the privacy of selections. Periscoping achieves this goal via a novel Private Information Retrieval scheme, constructed based on constrained Pseudorandom Functions. Moreover, the protocol is integrated seamlessly into the mixnet operations, readily applicable to existing mixnet systems as an extension at a minimal cost. Our experiments show that, with millions of mixes, it can reduce the traffic load of a mixnet by orders of magnitude, at a minor computational and bandwidth overhead.

Consider a mixnet with 7,000 mixes and 3 million users, at the scale of Tor [17] as of July, 2023 [18]. The key directory can be well over 2.5 MB [19]. If we require every user to maintain a copy, the average download traffic on a single mix for a round of key pair refresh is about 1 TB.

If the mixnet were to grow 10×, the overall bandwidth usage would be 100×, limiting its practicality. Worse yet, recent mixnet systems can be of an even larger scale. For example, Mycelium [13] employs millions of user devices as mixes, whose scale is three orders of magnitudes higher than that of Tor. It distributes keys to clients using the Telescoping technique [17], which is clearly one of the factors behind its high end-to-end message delivery latencies (in hours). Key distribution in Tor. Tor has two major distinctions from a mixnet: (a) it reuses a chain of relays (called a circuit) for the entire session of a conversation, and (b) a circuit has much fewer relays (typically 3). Before sending a message, Tor has a dedicated circuit-building phase, which involves a multi-round interactive protocol to exchange keys among users and relays, i.e., Telescoping [17]. Such a protocol would be unaffordable in a mixnet that has a much longer path (typically ≤ 10), used in the one-off manner. As a result, although Tor faces a similar scalability problem, the solutions are not directly applicable.

For example, the state-of-the-art WalkingOnion [19] protocol optimizes the Telescoping technique, by reliably outsourcing next-hop selection to relays. Indeed, it is efficient for circuitbuilding, but too expensive to apply in a mixnet. PIR-Tor [20] and ConsenSGX [21] employ computationally private information retrieval [22]-an expensive cryptographic method-to obliviously access the mixnet key directory. Despite inefficiency for mixnets, they inspire our design of Periscoping, to be discussed in Sec. III-B.

Mix (l-1) … …

Bob's Pseudonym