Paper 2025/165

SLIDE: Shuffle Shamir Secret Shares Uniformly with Linear Online Communication and Guaranteed Output Delivery

Abstract

We revisit shuffle protocols for Shamir secret sharing. Existing constructions either produce a non-uniform shuffle or incur high communication and round complexity, in some cases exponential in the number of parties. We propose two new shuffle protocols that achieve uniform shuffle with communication complexity $O\!\left(\frac{k + l}{\log k} \, n^2 m \log m\right)$ for shuffling rows of an $m\times l$ matrix shared among $n$ parties, where $k\leq m$ is a tunable parameter that balances communication and computation. The first protocol is concretely more efficient, while the second achieves the best-known $O(nml)$ online communication and $O(n)$ rounds. Both constructions enjoy an ideal property of guaranteed output delivery (GOD). In terms of both overall and online communication, our protocols improve upon the state of the art for shuffle protocols based on Shamir secret sharing. Our key technical ingredient is a novel permutation sharing technique that represents a permutation by smaller permutation matrices. Once permutations are shared, applying them becomes significantly cheaper, enabling a highly efficient online phase. The first protocol applies independent secret permutations from all parties in sequence, while the second protocol builds on the shuffle correlation technique of Gao et al., achieving $O(nml)$ online complexity. We further extend shuffle correlation to support GOD with linear online communication, an extension has not been previously explored, As a result, we obtain SLIDE, the first shuffle protocol achieving both $O(nml)$ online communication and guaranteed output delivery. Our constructions rely only on the most basic primitives of Shamir secret sharing over any field $\mathbb{F}$ with $\lvert\mathbb{F}\rvert > n$. Since shuffle is a fundamental building block for higher-level MPC primitives such as sorting and oblivious data structures, our results are broadly applicable and can accelerate many real-world applications of secure multiparty computation.

Note: Enhance our protocol to achieve guaranteed output delivery (GOD)