Cryptology ePrint Archive: Report 2015/664

Secure Multi-Party Shuffling

Mahnush Movahedi and Jared Saia and Mahdi Zamani

Abstract: 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.

Category / Keywords: cryptographic protocols / Multi-Party Computation

Original Publication (with major differences): SIROCCO 2015

Date: received 2 Jul 2015

Contact author: zamani at cs unm edu

Available format(s): PDF | BibTeX Citation

Version: 20150705:175937 (All versions of this report)

Short URL: ia.cr/2015/664

Discussion forum: Show discussion | Start new discussion