Secure multi-party shuffling with optimal communication

Abstract In this paper, we consider a secure multi-party shuffling (MPS), in which multiple participants provide private datasets and enable to obtain secret shared values of randomly permuted whole dataset while protecting the privacy of each individual input and the permutation. MPS stands as a foundational tool for the randomized algorithm, with broad utility in a large amount of domains, offering enhancements in privacy while concurrently reducing costs. And its applications encompass machine learning, secure function evaluation, and anonymous communication. Recently, Chase, Ghosh, and Poburinnaya (2020 Secret-shared shuffle. Advances in Cryptology-ASIACRYPT 2020: 26th International Conference on the Theory and Application of Cryptology and Information Security, Daejeon, South Korea, December 7-11, 2020, Proceedings, Part III 26, pp. 342-372. Springer.) introduced an innovative two-party protocol known as SSS, where participants can effectively produce additive secret shares of a shuffled dataset while preserving the privacy. Indeed, this approach transforms challenge of shuffling a dataset into the task of shuffling pseudorandom values, leading to a significant enhancement in both communication and computation efficiency. We would like to generalize the SSS in Chase, Ghosh, and Poburinnaya (2020 Secret-shared shuffle. Advances in Cryptology-ASIACRYPT 2020: 26th International Conference on the Theory and Application of Cryptology and Information Security, Daejeon, South Korea, December 7-11, 2020, Proceedings, Part III 26, pp. 342-372. Springer.) to a novel multi-party variant, all while maintaining its efficiency. However, it turns out that this is not straightforward. Specifically, the communication complexity is trivially blown up about $O(m^{3}n\log n)$, where $m$ denotes the number of participants and $n$ denotes the length of message. We further reduce the cost to be linear in the number of participants. Moreover, our novel MPS operates within the preprocessing model, with the security against static semi-honest adversaries. Furthermore, our protocols rely exclusively on the oblivious transfer during the preprocessing phase and symmetric-key primitives in online phase to avoid the comparatively heavy public-key operations associated with previous MPS protocols.