Paper 2024/2059

Minimizing the Use of the Honest Majority in YOSO MPC with Guaranteed Output Delivery

James Hsin-yu Chiang, ETH Zurich

Divya Ravi, University of Amsterdam

Jure Sternad, Aarhus University

Sophia Yakoubov, Aarhus University

Abstract

Cleve (STOC 86) shows that an honest majority is necessary for MPC with guaranteed output delivery. In this paper, we show that while an honest majority is indeed necessary, its involvement can be minimal. We demonstrate an MPC protocol with guaranteed output delivery, the majority of which is executed by a sequence of committees with dishonest majority; we leverage one committee with an honest majority, each member of which does work independent of the circuit size. Our protocol has the desirable property that every participant speaks only once (YOSO, Crypto 2021). As a building block of independent interest, we introduce public computation, which is essentially privacy-free MPC with guaranteed output delivery (akin to smart contracts realized on blockchains). We instantiate public computation on a public bulletin board in three different ways (with different assumption / round / space utilization trade-offs).

@misc{cryptoeprint:2024/2059,
      author = {Rishabh Bhadauria and James Hsin-yu Chiang and Divya Ravi and Jure Sternad and Sophia Yakoubov},
      title = {Minimizing the Use of the Honest Majority in {YOSO} {MPC} with Guaranteed Output Delivery},
      howpublished = {Cryptology {ePrint} Archive, Paper 2024/2059},
      year = {2024},
      url = {https://eprint.iacr.org/2024/2059}
}