Paper 2026/2698

Batched Identity-Based Encryption with Succinct Publicly Verifiable Subset Deletion

Abstract

Batched identity-based encryption (BIBE) compresses a bounded set of identities into a succinct public digest, and provides a single secret key for decrypting ciphertexts associated with identities in the set. We introduce batched identity-based encryption with succinct publicly verifiable subset deletion (BIBE-SPVD), which allows a holder of polynomially many quantum ciphertexts to certify deletion of any chosen subset using a single succinct classical certificate while preserving the usability of the remaining ciphertexts. We first construct a classical BIBE from identity-based encryption with puncturable master secret key, somewhere statistically binding (SSB) hashing, and indistinguishability obfuscation. We then equip this scheme with publicly verifiable certified-everlasting deletion, using a generic compiler specialized to the BIBE functionality. Finally, individual deletion certificates are aggregated using a somewhere-extractable batch argument. For each ciphertext position, the corresponding statement requires a valid deletion certificate precisely when that position belongs to the deleted subset. The identity digest and batch key remain succinct, and for \(N\) ciphertexts the aggregate deletion certificate has size \(poly(\lambda,\log N)\), independent of the number deleted.