Sanjam Garg
UC Berkeley

Dimitris Kolonelos
IMDEA Software Institute, Universidad Politécnica de Madrid

Guru-Vamsi Policharla
UC Berkeley

Mingyuan Wang
UC Berkeley

Keywords: Threshold Encryption, Silent Setup, Flexible Broadcast Encryption

Abstract

We build a concretely efficient threshold encryption scheme where the joint public key of a set of parties is computed as a deterministic function of their locally computed public keys, enabling a 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 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 t = 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 ≈ 8x larger than an ElGamal ciphertext.