Paper 2026/2205

DKG Is All You Need

Abstract

We construct the first Batched Threshold Encryption scheme with a \emph{transparent} setup where public parameters are \emph{independent} of the batch size. As a result batches of arbitrary sizes can be decrypted, without imposing an a priori fixed bound. We prove security under a constant size assumption -- the decisional bilinear square Diffie--Hellman assumption. Setup is just a distributed key generation protocol to sample secret shares of a random value. Ciphertexts consist of two $\mathbb{G}_1$ elements, one $\mathbb{G}_2$ element and the encrypted message, plus a NIZK for CCA security (two $\mathbb{F}$ elements with a sigma protocol). Partial decryptions are a single $\mathbb{G}_1$ element, computed with one scalar multiplication. Decrypting a batch of $B$ ciphertexts costs $O(B)$ pairings and $O(B\log^2 B)$ group operations. In the ramp setting, with a gap between the reconstruction threshold $t$ and corruption threshold $f$ as in consensus protocols with $n\ge3f+1$, we construct a pairing-free batched threshold encryption scheme from DDH whose partial decryptions are $2B/(t-f)$ group elements, and reduce the aggregation cost of our pairing-based scheme to $O(B\log^2(B/(t-f)))$ group operations.

Note: Revision: added appendices 1) a pairing-free BTE from DDH 2) faster aggregation for the pairing-based scheme, both in the ramp setting