Honest Majority GOD MPC with \(O(\textsf{depth}(C))\) Rounds and Low Online Communication
摘要
In the context of secure multiparty computation (MPC) protocols with guaranteed output delivery (GOD) for the honest majority setting, the state-of-the-art in terms of communication is the work of (Goyal et al. CRYPTO’20), which communicates O(n|C|) field elements, where |C| is the size of the circuit being computed and n is the number of parties. Their round complexity, as usual in secret-sharing based MPC, is proportional to $$O(\textsf{depth}(C))$$ , but only in the optimistic case where there is no cheating. Under attack, the number of rounds can increase to $$\varOmega (n^2)$$ before honest parties receive output, which is undesired for shallow circuits with $$\textsf{depth}(C)\ll n^2$$ . In contrast, other protocols that only require $$O(\textsf{depth}(C))$$ rounds even in the worst case exist, but the state-of-the-art from (Choudhury and Patra, Transactions on Information Theory, 2017) still requires $$\varOmega (n^4|C|)$$ communication in the offline phase, and $$\varOmega (n^3|C|)$$ in the online (for both point-to-point and broadcast channels). We see there exists a tension between efficient communication and number of rounds. For reference, the recent work of (Abraham et al., EUROCRYPT’23) shows that for perfect security and $$t