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 learn no information about the underlying plaintext. Our first result is a 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. We prove security under the Decisional Bilinear $q$-Power Diffie-Hellman assumption in asymmetric pairing groups and provide an implementation in Rust to show that our scheme outperforms prior work. 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: Added helper aided decryption and implementation Added discussion on concurrent work