Towards Provably-Secure Scalable Anonymous Broadcast

We devise a scalable and provably-secure protocol for fully-anonymous broadcast in large-scale networks. Similar to the dining cryptographers networks (DCNETS), our algorithm uses secure multi-party computation (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(n²) 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 adversary. We further assume that this adversary is computationally unbounded, and thus make no cryptographic hardness assumptions.