Paper 2021/1290

Large-Scale Non-Interactive Threshold Cryptosystems in the YOSO Model

Andreas Erwig, TU Darmstadt
Sebastian Faust, TU Darmstadt
Siavash Riahi, TU Darmstadt

A $(t,n)$-public key threshold cryptosystem allows distributing the execution of a cryptographic task among a set of $n$ parties by splitting the secret key required for the computation into $n$ shares. A subset of at least $t+1$ honest parties is required to execute the task of the cryptosystem correctly, while security is guaranteed as long as at most $t < \frac{n}{2}$ parties are corrupted. Unfortunately, traditional threshold cryptosystems do not scale well, when executed at large-scale (e.g., in the Internet-environment). In such settings, a possible approach is to select a subset of $n$ players (called a committee) out of the entire universe of $N\gg n$ parties to run the protocol. If done naively, however, this means that the adversary's corruption power does not scale with $N$ as otherwise, the adversary would be able to corrupt the entire committee. A beautiful solution for this problem is given by Benhamouda et al. (TCC 2020) who present a novel form of secret sharing, where the efficiency of the protocol is \emph{independent} of $N$, but the adversarial corruption power \emph{scales} with $N$ (a.k.a. fully mobile adversary). They achieve this through a novel mechanism that guarantees parties in a committee to stay anonymous -- also referred to as the YOSO (You Only Speak Once) model -- until they start to interact within the protocol. In this work, we initiate the study of large-scale threshold cryptography in the YOSO model of communication. We formalize and present novel protocols for distributed key generation, threshold encryption, and signature schemes that guarantee security in large-scale environments. A key challenge in our analysis is that we cannot use the secret sharing protocol of Benhamouda et al. as a black-box to construct our schemes, and instead we require a more generalized version, which may be of independent interest. Finally, we show how our protocols can be concretely instantiated in the YOSO model, and discuss interesting applications of our schemes.

Available format(s)
Public-key cryptography
Publication info
Contact author(s)
andreas erwig @ tu-darmstadt de
sebastian faust @ tu-darmstadt de
siavash riahi @ tu-darmstadt de
2022-11-19: last of 6 revisions
2021-09-24: received
See all versions
Short URL
Creative Commons Attribution


      author = {Andreas Erwig and Sebastian Faust and Siavash Riahi},
      title = {Large-Scale Non-Interactive Threshold Cryptosystems in the YOSO Model},
      howpublished = {Cryptology ePrint Archive, Paper 2021/1290},
      year = {2021},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.