Paper 2024/1936

Free Linear Online Phase for Secure Multiparty Shuffle

Abstract

Shuffling is a fundamental operation in secure multiparty computation (MPC). However, the best-known maliciously secure $n$-party $m$-element shuffle protocols still incur at least $n^2 m$ online communication and computation, which exceeds the best-known $O(nm)$ result for the semi-honest additive secret sharing setting. In this paper, we formalize the permute-in-turn paradigm for building MPC shuffle protocols from MPC permutation protocols, which captures the methodology implicitly adopted in most prior works. By further extending and enhancing this paradigm, we present generic transformations from semi-honest (resp.\ malicious) MPC permutation protocols to semi-honest (resp.\ malicious) MPC shuffle protocols that shuffle $m$ items among $n$ parties using only $O(n^2+nm)$ online computation and communication. Our transformation is for free in two senses: it preserves the overall asymptotic complexity of the natural approach of performing $n$ MPC permutations and yields an online phase with linear communication and computation complexity, while freeing the online phase of the shuffle protocol from depending on the implementation of the underlying MPC permutation protocol. This decoupling allows future work to optimize permutation protocols independently while benefiting all shuffle constructions following the paradigm. Our results immediately yield the first maliciously secure shuffle with linear online communication and computation, under both additive secret sharing and Shamir secret sharing, improving upon the previous bounds of $O(Bn^2 m)$ and $O(n^2 m \log m)$, respectively. We formally prove semi-honest and universally composable (UC) security corresponding transformations. Our prototype demonstrates an over $20\times$ improvement in online efficiency over prior state-of-the-art protocols when shuffling $m=2^{12}$ items among $n=15$ parties, with over $150\times$ online communication savings and only a $1.1\times$ slowdown in the offline phase. Given the widespread use of shuffling in MPC, our techniques are broadly applicable to practical protocols.

Note: Revised.