Paper 2022/187

Towards Efficient YOSO MPC Without Setup

Sebastian Kolby, Divya Ravi, and Sophia Yakoubov


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.

Available format(s)
Cryptographic protocols
Publication info
Preprint. MINOR revision.
secure computationYOSOround complexityminimizing setup
Contact author(s)
sk @ cs au dk
divya @ cs au dk
sophia yakoubov @ cs au dk
2022-02-20: received
Short URL
Creative Commons Attribution


      author = {Sebastian Kolby and Divya Ravi and Sophia Yakoubov},
      title = {Towards Efficient YOSO MPC Without Setup},
      howpublished = {Cryptology ePrint Archive, Paper 2022/187},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.