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.