Paper 2021/1290

Large-Scale Non-Interactive Threshold Cryptosystems Through Anonymity

Andreas Erwig, Sebastian Faust, and Siavash Riahi


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 that parties in a committee stay anonymous until they start to interact within the protocol. In this work, we initiate the study of large-scale threshold cryptosystems. We present novel protocols for distributed key generation, threshold encryption, and signature schemes that guarantee security in large-scale environments with complexity independent of $N$. One of our key contributions is to show how one can transform a scheme which is only secure against static adversaries to a large-scale threshold cryptosystem via anonymity and prove that it is secure against a fully mobile adversary. We believe that our framework and proof techniques can be used in the future to design and prove schemes secure in the large-scale setting.

Available format(s)
Public-key cryptography
Publication info
Preprint. Minor revision.
Contact author(s)
andreas erwig @ tu-darmstadt de
siavash riahi @ tu-darmstadt de
2022-01-30: last of 3 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 Through Anonymity},
      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.