Free Linear Online Phase for Secure Multiparty Shuffle

본문 미리보기

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 ac