In this work, we study the communication complexity of constant-round secure multiparty computation (MPC) against a fully malicious adversary and consider both the honest majority setting and the dishonest majority setting. In the (strong) honest majority setting (where \(t=(1/2-\epsilon )n\) for a constant \(\epsilon \) ), the best-known result without relying on FHE is given by Beck et al. (CCS 2023) based on the LPN assumption that achieves \(O(|C|\kappa )\) communication, where \(\kappa \) is the security parameter and the achieved communication complexity is independent of the number of participants. In the dishonest majority setting, the best-known result is achieved by Goyal et al. (ASIACRYPT 2024), which requires \(O(|C|n\kappa )\) bits of communication and is based on the DDH and LPN assumptions. In this work, we achieve the following results: (1) For any constant \(\epsilon <1\) , we give the first constant-round MPC in the dishonest majority setting for corruption threshold \(t<(1-\epsilon )n\) with \(O(|C|\kappa +D (n+\kappa )^2\kappa +n^3)\) communication assuming random oracles and oblivious transfers, where D is the circuit depth. (2) We give the first constant-round MPC in the standard honest majority setting (where \(t=(n-1)/2\) ) with \(O(|C|\kappa +D (n+\kappa )^2\kappa +n^3)\) communication only assuming random oracles. Unlike most of the previous constructions of constant-round MPCs that are based on multiparty garbling, we achieve our result by letting each party garble his local computation in a non-constant-round MPC that meets certain requirements. We first design a constant-round MPC that achieves \(O(|C|\kappa + Dn^2\kappa )\) communication assuming random oracles in the strong honest majority setting of \(t=n/4\) . Then, we combine the party virtualization technique and the idea of MPC-in-the-head to boost the corruption threshold to \(t<(1-\epsilon )n\) for any constant \(\epsilon <1\) assuming oblivious transfers to achieve our first result. Finally, our second result is obtained by instantiating oblivious transfers using a general honest-majority MPC and the OT extension technique built on random oracles.

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

Towards Building Scalable Constant-Round MPC from Minimal Assumptions via Round Collapsing

  • Vipul Goyal,
  • Junru Li,
  • Rafail Ostrovsky,
  • Yifan Song

摘要

In this work, we study the communication complexity of constant-round secure multiparty computation (MPC) against a fully malicious adversary and consider both the honest majority setting and the dishonest majority setting. In the (strong) honest majority setting (where \(t=(1/2-\epsilon )n\) for a constant \(\epsilon \) ), the best-known result without relying on FHE is given by Beck et al. (CCS 2023) based on the LPN assumption that achieves \(O(|C|\kappa )\) communication, where \(\kappa \) is the security parameter and the achieved communication complexity is independent of the number of participants. In the dishonest majority setting, the best-known result is achieved by Goyal et al. (ASIACRYPT 2024), which requires \(O(|C|n\kappa )\) bits of communication and is based on the DDH and LPN assumptions. In this work, we achieve the following results: (1) For any constant \(\epsilon <1\) , we give the first constant-round MPC in the dishonest majority setting for corruption threshold \(t<(1-\epsilon )n\) with \(O(|C|\kappa +D (n+\kappa )^2\kappa +n^3)\) communication assuming random oracles and oblivious transfers, where D is the circuit depth. (2) We give the first constant-round MPC in the standard honest majority setting (where \(t=(n-1)/2\) ) with \(O(|C|\kappa +D (n+\kappa )^2\kappa +n^3)\) communication only assuming random oracles. Unlike most of the previous constructions of constant-round MPCs that are based on multiparty garbling, we achieve our result by letting each party garble his local computation in a non-constant-round MPC that meets certain requirements. We first design a constant-round MPC that achieves \(O(|C|\kappa + Dn^2\kappa )\) communication assuming random oracles in the strong honest majority setting of \(t=n/4\) . Then, we combine the party virtualization technique and the idea of MPC-in-the-head to boost the corruption threshold to \(t<(1-\epsilon )n\) for any constant \(\epsilon <1\) assuming oblivious transfers to achieve our first result. Finally, our second result is obtained by instantiating oblivious transfers using a general honest-majority MPC and the OT extension technique built on random oracles.