Paper 2015/664

Secure Multi-Party Shuffling

Mahnush Movahedi, Jared Saia, and Mahdi Zamani


In secure multi-party shuffling, multiple parties, each holding an input, want to agree on a random permutation of their inputs while keeping the permutation secret. This problem is important as a primitive in many privacy-preserving applications such as anonymous communication, location-based services, and electronic voting. Known techniques for solving this problem suffer from poor scalability, load-balancing issues, trusted party assumptions, and/or weak security guarantees. In this paper, we propose an unconditionally-secure protocol for multi-party shuffling that scales well with the number of parties and is load-balanced. In particular, we require each party to send only a polylogarithmic number of bits and perform a polylogarithmic number of operations while incurring only a logarithmic round complexity. We show security under universal composability against up to about n/3 fully-malicious parties. We also provide simulation results showing that our protocol improves significantly over previous work. For example, for one million parties, when compared to the state of the art, our protocol reduces the communication and computation costs by at least three orders of magnitude and slightly decreases the number of communication rounds.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. Major revision. SIROCCO 2015
Multi-Party Computation
Contact author(s)
zamani @ cs unm edu
2015-07-05: received
Short URL
Creative Commons Attribution


      author = {Mahnush Movahedi and Jared Saia and Mahdi Zamani},
      title = {Secure Multi-Party Shuffling},
      howpublished = {Cryptology ePrint Archive, Paper 2015/664},
      year = {2015},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.