Paper 2022/1037

RPM: Robust Anonymity at Scale

Donghang Lu, Purdue University West Lafayette
Aniket Kate, Purdue University West Lafayette

This work presents RPM, a scalable anonymous communication protocol suite using secure multiparty computation (MPC) with the offline-online model. We generate random, unknown permutation matrices in a secret-shared fashion and achieve improved (online) performance and the lightest communication and computation overhead for the clients compared to the state of art robust anonymous communication protocols. Using square-lattice shuffling, we make our protocol scale well as the number of clients increases. We provide three protocol variants, each targeting different input volumes and MPC frameworks/libraries. Besides, due to the modular design, our protocols can be easily generalized to support more MPC functionalities and security properties as they get developed. We also illustrate how to generalize our protocols to support two-way anonymous communication and secure sorting. We have implemented our protocols using the MP-SPDZ library suit and the benchmark illustrates that our protocols achieve unprecedented online phase performance with practical offline phases.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. The 23rd Privacy Enhancing Technologies Symposium
secure multiparty computationsecure mixingsecure permutationanonymous communication
Contact author(s)
lu562 @ purdue edu
aniket @ purdue edu
2022-12-22: revised
2022-08-10: received
See all versions
Short URL
Creative Commons Attribution


      author = {Donghang Lu and Aniket Kate},
      title = {RPM: Robust Anonymity at Scale},
      howpublished = {Cryptology ePrint Archive, Paper 2022/1037},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.