Two Levels are Better than One: Dishonest Majority MPC with $\widetilde{O}(|C|)$ Total Communication

ePrint Report: Two Levels are Better than One: Dishonest Majority MPC with $\widetilde{O}(|C|)$ Total Communication

Alexander Bienstock, Kevin Yeo

In recent years, there has been tremendous progress in improving the communication complexity of dishonest majority MPC. In the sub-optimal corruption threshold setting, where $t<(1-\varepsilon)\cdot n$ for some constant $0<\varepsilon\leq 1/2$, the recent works Sharing Transformation (Goyal $\textit{et al.}$, CRYPTO'22) and SuperPack (Escudero $\textit{et al.}$, EUROCRYPT'23) presented protocols with information-theoretic online phases achieving $O(1)$ communication per multiplication gate, across all parties. …

communication complexity corruption eprint report kevin mpc progress report threshold