Rollercoaster: An Efficient Group-Multicast Scheme for Mix Networks

Authors: 

Daniel Hugenroth, Martin Kleppmann, and Alastair R. Beresford, University of Cambridge

Abstract: 

Mix network designs such as Loopix provide strong metadata anonymity guarantees that are crucial across many applications. However, because they limit the rate at which messages can be sent by each user, they incur high delays when sending many messages to multiple recipients—for instance, in decentralised collaborative apps.

In this paper we present an efficient multicast scheme named Rollercoaster that reduces the time for delivering a message to all members of a group of size m from O(m) to O(log m). Rollercoaster can be deployed without modifications to the underlying mix network, allowing it to benefit from the anonymity set provided by existing users. We further develop an extension that achieves the same asymptotic guarantees in the presence of unreliable group members.

While the scheme is applicable to many mix network designs, we evaluate it for the Loopix network, which is the most advanced and practical design to date. For this evaluation we developed a network simulator that allows fast, reproducible, and inspectable runs while eliminating external influences.

Open Access Media

USENIX is committed to Open Access to the research presented at our events. Papers and proceedings are freely available to everyone once the event begins. Any video, audio, and/or slides that are posted after the event are also free and open to everyone. Support USENIX and our commitment to Open Access.

BibTeX
@inproceedings {274618,
author = {Daniel Hugenroth and Martin Kleppmann and Alastair R. Beresford},
title = {Rollercoaster: An Efficient Group-Multicast Scheme for Mix Networks},
booktitle = {30th {USENIX} Security Symposium ({USENIX} Security 21)},
year = {2021},
isbn = {978-1-939133-24-3},
pages = {3433--3450},
url = {https://www.usenix.org/conference/usenixsecurity21/presentation/hugenroth},
publisher = {{USENIX} Association},
month = aug,
}

Presentation Video