Ring of Gyges: Accountable Anonymous Broadcast via Secret-Shared Shuffle

Anonymous broadcast systems, which enable users to post messages on a public bulletin board while hiding their identities, have been of persistent interest over the years. Recent designs utilizing multi-party computation (MPC) techniques have shown competitive computational efficiency (CCS’20, NDSS’22, PETS’23). However, these systems still fall short in communication overhead, which also dominates the overall performance. Besides, they fail to adequately address threats from misbehaving users, such as repeatedly spamming the system with inappropriate, illegal content. These often undermine the practical adoption of anonymous broadcast systems.
This work presents Gyges, an MPC-based anonymous broadcast system that minimizes its inter-server communication costs while reconciling key anonymity and accountability guarantees. At its crux is an honest-majority four-party secret-shared relay. These relay parties jointly execute two essential protocols: 1) a “silent shuffling” protocol – requiring no online communication but non-interactive, local computation only – that unlinks users from submitted messages to obtain sender anonymity; and 2) a companion fast and lean tracing protocol that, when necessary, relinks a certain shuffled message back to its originator if content violates established moderation policies, without jeopardizing the anonymity of others. Additionally, Gyges adheres to the notion of private robustness to defend against malicious disruptions, while ensuring the guaranteed output delivery and preserving sender anonymity. The system also supports both vertical and horizontal scaling to enhance practical service performance. Our evaluation results show that Gyges outperforms state-of-the-art MPC-based anonymous broadcast systems like Clarion (NDSS’22) and RPM (PETS’23), while its secret-shared tracing technique can swiftly track down misbehaving clients (when necessary), giving orders of magnitude overhead reductions compared to recent traceable mixnets (PETS’24) that offers similar tracking capabilities