Paper 2026/2814

Registration-based Encryption with Logarithmic Registration

Abstract

Registration-based encryption (RBE) preserves IBE's identity-only encryption interface while eliminating key escrow: users generate their own keys, and a Key Curator manages only registered public keys. However, this design introduces a new challenge: user registration, since every joining user rrequires KC to update the registry. Although theoretical RBE constructions achieve polylogarithmic registration, they rely on costly cryptographic techniques and remain impractical. In existing deployable black-box RBE, registration takes $O(\sqrt{N})$ time ($N$ denotes the maximum user capacity). This gap between theoretical registration efficiency and deployability makes registration a key performance bottleneck for large-scale deployments of pairing-based RBE. This work presents a black-box pairing-based RBE construction under the decisional $(R,S,T,f)$-Diffie-Hellman assumption. Build on the multilinear tree, when registering a user's public key, KC updates only the corresponding root-to-leaf path associated with the user. Therefore, registration in our construction takes $O(\log \sqrt{N})$ time for the maximum user capacity $N$. Moreover, we provides membership and non-membership verification, and their batch verification supports to check registration status of multiple users. Experiments show registration and key generation complete in milliseconds when $N=10^7$. Compared with Glaeser et al. (CCS'23), our scheme accelerates registration by up to \(158\times\) and key generation by up to \(230\times\) with practical overheads.