International Association for Cryptologic Research

International Association
for Cryptologic Research


Threshold Encryption with Silent Setup

Sanjam Garg , UC Berkeley
Dimitris Kolonelos , IMDEA Software Institute, Universidad Polit├ęcnica de Madrid
Guru Vamsi Policharla , UC Berkeley
Mingyuan Wang , UC Berkeley
Search ePrint
Search Google
Conference: CRYPTO 2024
Abstract: We build a concretely efficient threshold encryption scheme where the joint public key of a set of parties is computed as a \emph{deterministic} function of their locally computed public keys, enabling a \emph{silent} setup phase. By eliminating interaction from the setup phase, our scheme immediately enjoys several highly desirable features such as asynchronous setup, multiverse support, and dynamic threshold. Prior to our work, the only known constructions of threshold encryption with silent setup relied on heavy cryptographic machinery such as indistinguishability Obfuscation or witness encryption for all of $\mathsf{NP}$. Our core technical innovation lies in building a special purpose witness encryption scheme for the statement ``at least $t$ parties have signed a given message''. Our construction relies on pairings and is proved secure in the Generic Group Model. Notably, our construction, restricted to the special case of threshold $\thres=1$, gives an alternative construction of the (flexible) distributed broadcast encryption from pairings, which has been the central focus of several recent works. We implement and evaluate our scheme to demonstrate its concrete efficiency. Both encryption and partial decryption are constant time, taking $<7\,$ms and $<1\,$ms, respectively. For a committee of $1024$ parties, the aggregation of partial decryptions takes $<200\,$ms, when all parties provide partial decryptions. The size of each ciphertext is $\approx 8\times$ larger than an ElGamal ciphertext.
  title={Threshold Encryption with Silent Setup},
  author={Sanjam Garg and Dimitris Kolonelos and Guru Vamsi Policharla and Mingyuan Wang},