Paper 2026/1558

Verifiable Outsourced BTE with Silent Setup: Achieving Constant-Rate Batched Delegation

Abstract

Batched threshold encryption (BTE) is a novel public-key paradigm in which, once a batch of $B$ ciphertexts is designated, a decrypter evaluates them using decryption key shares generated by decryption committee nodes via threshold reconstruction. To mitigate Miner Extractable Value (MEV) attacks in fully decentralized environments like blockchains, it is essential to guarantee mempool privacy while supporting a silent setup that allows decentralized key generation among decryption nodes. Furthermore, to efficiently process large batches of ciphertexts, an outsourcing mechanism that delegates heavy decryption computations to a cloud server is indispensable. In this paper, we observe that naively adding decryption outsourcing to a threshold batched identity-based encryption with silent setup (TBIBE-SS) scheme of Gong et al.~(EUROCRYPT 2026) causes the outsourcing communication overhead to scale undesirably with the number of decryption nodes. To overcome this limitation, we introduce a partial re-randomization technique--replacing conventional full re-randomization--and incorporate a handle-based oracle query mechanism into the security model. Based on these techniques, we propose a communication-efficient outsourced TBIBE-SS (O-TBIBE-SS) scheme and formally prove its security. We then combine our O-TBIBE-SS scheme with additional cryptographic primitives to construct a verifiable outsourced BTE-SS (VOBTE-SS) scheme, which supports both delegated decryption and verifiability of outsourced computation, proving its security under an augmented threat model. Our VOBTE-SS scheme represents the first construction to achieve efficient batched decryption outsourcing in terms of both communication and computation overhead within decentralized environments.