Cryptology ePrint Archive: Report 2021/1685

Divide and Funnel: a Scaling Technique for Mix-Networks

Debajyoti Das and Sebastian Meiser and Esfandiar Mohammadi and Aniket Kate

Abstract: While many anonymous communication (AC) protocols have been proposed to provide anonymity over the internet, scaling to a large number of users while remaining provably secure is challenging. We tackle this challenge by proposing a new scaling technique to improve the scalability/anonymity of AC protocols that distributes the computational load over many nodes without completely disconnecting the paths different messages take through the network. We demonstrate that our scaling technique is useful and practical through a core sample AC protocol, Streams, that offers provable security guarantees and scales for a million messages. The scaling technique ensures that each node in the system does the computation-heavy public key operation only for a tiny fraction of the total messages routed through the Streams network while maximizing the mixing/shuffling in every round.

We demonstrate Streams' performance through a prototype implementation. Our results show that Streams can scale well even if the system has a load of one million messages at any point in time. Streams maintains a latency of $16$ seconds while offering provable ``one-in-a-billion'' unlinkability, and can be leveraged for applications such as anonymous microblogging and network-level anonymity for blockchains. We also illustrate by examples that our scaling technique can be useful to many other AC protocols to improve their scalability and privacy, and can be interesting to protocol developers.

Category / Keywords: anonymity, mixnet, protocol

Date: received 22 Dec 2021

Contact author: debajyoti das at esat kuleuven be, smeiser at visa com, esfandiar mohammadi at uni-luebeck de, aniket at purdue edu

Available format(s): PDF | BibTeX Citation

Version: 20211222:174726 (All versions of this report)

Short URL: ia.cr/2021/1685


[ Cryptology ePrint archive ]