Paper 2024/2059 Original: eprint.iacr.org/2024/2059 ↗
Minimizing the Use of the Honest Majority in YOSO MPC with Guaranteed Output Delivery
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).
Metadata
- Available format(s)
PDF- Category
- Cryptographic protocols
- Publication info
- Preprint.
- History
- 2026-04-21: last updated
- 2024-12-20: published
- Short URL
- https://ia.cr/2024/2059
- License
- https://creativecommons.org/licenses/by/4.0/
BibTeX
@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}
}