Paper 2025/1254

Threshold Batch Identity-based Encryption without Epochs

Abstract

Suppose Alice holds a master secret key $\mathsf{sk}$ in an identity-based encryption scheme. For a given set of identities $\mathcal{I}$, Alice wants to create a short pre-decryption key that lets anyone decrypt the ciphertexts encrypted under any identity in $\mathcal{I}$ and nothing else. This problem is called batch identity-based encryption (batch IBE). When the secret key $\mathsf{sk}$ is shared among a number of decryption parties, the problem is called threshold batch identity-based encryption. This question comes up in the context of an encrypted mempool where the goal is to publish a short pre-decryption key that can be used to decrypt all ciphertexts in a block. Prior work constructed batch IBE schemes with some limitations. In this work, we construct new batch IBE and threshold batch IBE schemes. We first observe that a key-policy ABE (KP-ABE) scheme directly gives a batch IBE scheme. However, the best KP-ABE schemes happen to be lattice-based, and do not thresholdize efficiently. We then use very different techniques to construct a new lattice-based batch IBE scheme. Our construction employs a recent preimage sampler due to Waters, Wee, and Wu. Along the way, we develop a two-round protocol for preimage lattice sampling when the lattice trapdoor is secret shared among the participants.