International Association for Cryptologic Research

International Association
for Cryptologic Research

Crypto 2024

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


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.

Publication

Crypto 2024

Paper

Artifact

Artifact number
crypto/2024/a4

Artifact published
August 15, 2024

README

ZIP (16 KB)  

View on Github

License
This work is licensed under the MIT License.


BibTeX How to cite

Garg, S., Kolonelos, D., Policharla, G., Wang, M. (2024). Threshold Encryption with Silent Setup. In: Reyzin, L., Stebila, D. (eds) Advances in Cryptology – Crypto 2024. Lecture Notes in Computer Science, vol. 14926. Springer, Cham. https://doi.org/10.1007/978-3-031-68394-7_12. Artifact available at https://artifacts.iacr.org/crypto/2024/a4