Paper 2023/1077

Taming Adaptivity in YOSO Protocols: The Modular Way

Ran Canetti, Boston University
Sebastian Kolby, Aarhus University
Divya Ravi, Aarhus University
Eduardo Soria-Vazquez, Technology Innovation Institute
Sophia Yakoubov, Aarhus University

YOSO-style MPC protocols (Gentry et al., Crypto'21), are a promising framework where the overall computation is partitioned into small, short-lived pieces, delegated to subsets of one-time stateless parties. Such protocols enable gaining from the security benefits provided by using a large community of participants where "mass corruption" of a large fraction of participants is considered unlikely, while keeping the computational and communication costs manageable. However, fully realizing and analyzing YOSO-style protocols has proven to be challenging: While different components have been defined and realized in various works, there is a dearth of protocols that have reasonable efficiency and enjoy full end to end security against adaptive adversaries. The YOSO model separates the protocol design, specifying the short-lived responsibilities, from the mechanisms assigning these responsibilities to machines participating in the computation. These protocol designs must then be translated to run directly on the machines, while preserving security guarantees. We provide a versatile and modular framework for analyzing the security of YOSO-style protocols, and show how to use it to compile any protocol design that is secure against static corruptions of $t$ out of $c$ parties, into protocols that withstand adaptive corruption of $T$ out of $N$ machines (where $T/N$ is closely related to $t/c$, specifically when $t/c<0.5$, we tolerate $T/N \leq 0.29$) at overall communication cost that is comparable to that of the traditional protocol even when $c << N$. Furthermore, we demonstrate how to minimize the use of costly non-committing encryption, thereby keeping the computational and communication overhead manageable even in practical terms, while still providing end to end security analysis. Combined with existing approaches for transforming stateful protocols into stateless ones while preserving static security (e.g. Gentry et al. 21, Kolby et al. 22), we obtain end to end security.

Note: Fixed error in Delete and Ready commands in F_ra

Available format(s)
Cryptographic protocols
Publication info
YOSOAdaptive SecurityUC
Contact author(s)
canetti @ bu edu
sk @ cs au dk
divya @ cs au dk
eduardo soria-vazquez @ tii ae
sophia yakoubov @ cs au dk
2023-07-24: last of 2 revisions
2023-07-11: received
See all versions
Short URL
Creative Commons Attribution


      author = {Ran Canetti and Sebastian Kolby and Divya Ravi and Eduardo Soria-Vazquez and Sophia Yakoubov},
      title = {Taming Adaptivity in YOSO Protocols: The Modular Way},
      howpublished = {Cryptology ePrint Archive, Paper 2023/1077},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.