Paper 2019/883

HoneyBadgerMPC and AsynchroMix: Practical AsynchronousMPC and its Application to Anonymous Communication

Donghang Lu, Thomas Yurek, Samarth Kulshreshtha, Rahul Govind, Rahul Mahadev, Aniket Kate, and Andrew Miller


Multiparty computation as a service (MPSaaS) is a promising approach for building privacy-preserving communication systems.However, in this paper, we argue that existing MPC implementations are inadequate for this application as they do not address fairness, let alone robustness. Even a single malicious server can cause the protocol to abort while seeing the output for itself, which in the context of an anonymous communication service would create a vulnerability to censorship and deanonymization attacks. To remedy this we propose a new MPC implementation, HoneyBadgerMPC, that combines a robust online phase with an optimistic offline phase that is efficient enough to run continuously alongside the online phase. We use HoneyBadgerMPC to develop an application case study, called AsynchroMix, that provides an anonymous broadcast functionality. AsynchroMix features a novel MPC program that trades off between computation and communication, allowing for low-latency message mixing in varying settings. In a cloud-based distributed benchmark with 100 nodes, we demonstrate mixing a batch of 512 messages in around 20 seconds and up to 4096 messages in around two minutes.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. ACM CCS 2019
multiparty computationrobustness
Contact author(s)
soc1024 @ illinois edu
2019-08-01: received
Short URL
Creative Commons Attribution


      author = {Donghang Lu and Thomas Yurek and Samarth Kulshreshtha and Rahul Govind and Rahul Mahadev and Aniket Kate and Andrew Miller},
      title = {HoneyBadgerMPC and AsynchroMix: Practical AsynchronousMPC and its Application to Anonymous Communication},
      howpublished = {Cryptology ePrint Archive, Paper 2019/883},
      year = {2019},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.