Paper 2024/1936

Free Linear Online Phase for Secure Multiparty Shuffle

Abstract

Shuffling is a fundamental operation in secure multiparty computation (MPC), yet existing maliciously secure protocols for shuffling $m$ elements among $n$ parties require at least $n^2m$ online communication and computation, compared with $O(nm)$ in the semi-honest additive-sharing setting. We formalize and extend the \emph{permute-in-turn paradigm}, which constructs MPC shuffles from permutation protocols, capturing the methodology adopted in most prior works. Our generic transformations achieve semi-honest or malicious security with only $O(C_{\mathrm{BC}}+nm)$ online communication and computation, where $C_{\mathrm{BC}}$ is the cost of one parallel broadcast (allowing unanimous abort). Our transformations are \emph{for free} in two senses: they yield linear online phases without exceeding the overall asymptotic cost of applying $n$ MPC permutations, while \emph{freeing} the online phase of the shuffle protocol from dependence on the MPC permutation protocol. This decoupling allows future work to optimize permutation protocols independently while benefiting all MPC shuffle protocols that follow the paradigm. Instantiated with additive and Shamir secret sharing, our transformations yield the first maliciously secure shuffles with $O(C_{\mathrm{BC}}+nm)$ online cost, improving previous bounds of $O(Bn^2m)$ and $O(n^2m\log m)$, respectively, where $B$ is a cut-and-choose parameter. We formally prove semi-honest and universally composable (UC) security for the corresponding transformations. For $m=2^{12}$ and $n=15$, our prototype achieves over $60\times$ lower online runtime and $120\times$ lower online communication than prior work, with only a $1.3\times$ increase in total runtime.

Note: Revised and extended results to ring.