Paper 2026/1452

Labeled Multi-Key Batched IBE

Abstract

We study Batched IBE through the lens of Multi-Message Signatures -- a natural extension of standard digital signatures in which a single signing operation signs an entire vector of messages at once. A public open algorithm then derives an opening for each message, allowing anyone to verify that an individual message was signed. First we show that Multi-Message Signatures are essential by constructing a Multi-Message Signature scheme from every Batched IBE scheme with a sufficiently large plaintext space. We then show how to construct a Batched IBE scheme from a Multi-Message Signature with deterministic verification given an extractable witness encryption for the verification relation, similar to the duality between IBE and digital signatures. Such a witness encryption scheme can be instantiated efficiently for the special case of linearly-verifiable pairing based multi-message signatures. Next we analyze existing constructions of Batched IBE and extract linearly-verifiable Multi-Message Signatures which provide us with valuable insight into the inner workings of various Batched IBE schemes. Leveraging these insights, we construct the first Batched IBE scheme supporting $q$ key queries per label with an $O(qB)$ CRS size and constant size ciphertexts.