International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Honest Majority GOD MPC with O(depth(C)) Rounds and Low Online Communication

Authors:
Amit Agarwal , University of Illinois Urbana Champaign, Champaign, USA
Alexander Bienstock , J.P. Morgan AI Research & J.P. Morgan AlgoCRYPT CoE, New York, USA
Ivan Damgård , Aarhus University, Aarhus, USA
Daniel Escudero , J.P. Morgan AI Research & J.P. Morgan AlgoCRYPT CoE, New York, USA
Download:
Search ePrint
Search Google
Presentation: Slides
Conference: ASIACRYPT 2024
Abstract: 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(depth(C)), but only in the optimistic case where there is no cheating. Under attack, the number of rounds can increase to \Omega(n^2) before honest parties receive output, which is undesired for shallow circuits with depth(C) << n^2. In contrast, other protocols that only require O(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 \Omega(n^4|C|) communication in the offline phase, and \Omega(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
BibTeX
@inproceedings{asiacrypt-2024-34613,
  title={Honest Majority GOD MPC with O(depth(C)) Rounds and Low Online Communication},
  publisher={Springer-Verlag},
  author={Amit Agarwal and Alexander Bienstock and Ivan Damgård and Daniel Escudero},
  year=2024
}