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

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Honest Majority GOD MPC with  \(O(\textsf{depth}(C))\) Rounds and Low Online Communication

  • Amit Agarwal,
  • Alexander Bienstock,
  • Ivan Damgård,
  • Daniel Escudero

摘要

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