Paper 2022/187

Towards Efficient YOSO MPC Without Setup

Sebastian Kolby and Divya Ravi and Sophia Yakoubov

Abstract

YOSO MPC (Gentry et al., Crypto 2021) is a new MPC framework where each participant can speak at most once. This models an adaptive adversary’s ability to watch the network and corrupt or destroy parties it deems significant based on their communication. By using private channels to anonymous receivers (e.g. by encrypting to a public key whose owner is unknown), the communication complexity of YOSO MPC can scale sublinearly with the total number $N$ of available parties, even when the adversary’s corruption threshold is linear in $N$ (e.g. just under $N/2$). It was previously an open problem whether YOSO MPC can achieve guaranteed output delivery in a constant number of rounds without relying on trusted setup. In this work, we show that this can indeed be accomplished. Using linearly homomorphic encryption and secret sharing, we construct YOSO-LHE, which is the first realistically efficient YOSO MPC protocol that achieves guaranteed output delivery without trusted setup. YOSO-LHE is not itself constant-round; it takes $O(d)$ rounds of communication, where $d$ is the depth of the circuit being computed. However, YOSO-LHE can be used to bootstrap any constant-round YOSO protocol that requires setup, by generating that setup within YOSO-LHE. As long as the complexity of the setup is independent of the circuit to be evaluated, the bootstrapped protocol will be constant-round.