Paper 2026/760

A Simple Batched Threshold Encryption Scheme

Abstract

Batched threshold encryption allows any $t$-out-of-$N$ parties in a committee to decrypt a batch of $B$ ciphertexts using sub-linear $o(NB)$ communication, while ensuring that any subset of $<t$ colluding parties learns no information about the underlying plaintext. Our first result is a simple batched threshold encryption scheme that is censorship resistant, avoids epoch restrictions, and achieves quasi-linear $O(B\log B)$ decryption complexity in the batch size $B$. Our scheme has the shortest ciphertext among all known constructions: $|\mathbb{G}_1| + |\mathbb{G}_T|$ for CPA security, with CCA security adding only $2|\mathbb{F}|$ via a simulation-extractable NIZK. However, our scheme requires an interactive setup phase (involving secure multiplications) and secret keys held by the committee grow linearly with the batch size. We prove security under the Decisional Bilinear $B$-Power Diffie-Hellman assumption in asymmetric pairing groups and provide an implementation in Rust to show that our scheme outperforms prior work. We also construct a variant of simple BTE, which allows for a tradeoff between secret-key size and censorship resistance. For any $\delta \leq B$, this variant reduces the size of the secret key held by each party from $O(B) \to O(\delta)$, and the decryption key from $O(BN) \to O(B + \delta N)$, but this comes at the cost of restricting a ciphertext encrypted with index $\mathsf{idx}$ to batch positions $i\in[B]$ satisfying $|i-\mathsf{idx}|<\delta$. Our second result is a new approach for verifying decryption in batched threshold encryption which enables a helper party (that carries out decryption) to provide hints that allow a verifier to check that decryption was carried out correctly using only MSMs and hashes. Concretely, we observe a $114.1\times$ speedup when verifying decryption of 2048 ciphertexts when compared against local decryption. Our approach is quite general and can be applied to other pairing-based advanced encryption schemes such as Timelock Encryption and Silent Threshold Encryption that can be cast as witness encryption schemes.

Note: Update 1: Added helper aided decryption and implementation Added discussion on concurrent work Update 2: Added Indexed Simple BTE