Towards Provably-Secure Scalable Anonymous Broadcast.
Mahdi Zamani, Jared Saia, Mahnush Movahedi, Joud S. Khoury · 2013
We devise a scalable and provably-secure protocol for fully-anonymous broadcast in large-scale networks. Similar to the dining cryptographers networks (DC-NETS), our algorithm uses secure multi-party computa-tion (MPC) to ensure anonymity. However, we address the weaknesses of DC-NETS, which are poor scalability and vulnerability to jamming attacks. When compared to the state-of-the-art, our protocol reduces the total bit complexity from O(n2) to Õ(n) per anonymous message sent in a network of size n; total latency increases from O(1) to polylog(n). We assume up to a one third fraction of the parties is controlled by a static Byzantine adver-sary. We further assume that this adversary is compu-tationally unbounded, and thus make no cryptographic hardness assumptions. 1