Paper 2021/499

Optimizing Registration Based Encryption

Kelong Cong, Karim Eldefrawy, and Nigel P. Smart

Abstract

The recent work of Garg et al. from TCC'18 introduced the notion of registration based encryption (RBE). The principal motivation behind RBE is to remove the key escrow problem of identity based encryption (IBE), where the IBE authority is trusted to generate private keys for all the users in the system. Although RBE has excellent asymptotic properties, it is currently impractical. In our estimate, ciphertext size would be about 11 terabytes in an RBE deployment supporting 2 billion users. Motivated by this observation, our work attempts to reduce the concrete communication and computation cost of the current state-of-the-art construction. Our contribution is two-fold. First, we replace Merkle trees with crit-bit trees, a form of PATRICIA trie, without relaxing any of the original RBE efficiency requirements introduced by Garg et al. This change reduces the ciphertext size by 15% and the computation cost of decryption by 30%. Second, we observe that increasing RBE's public parameters by a few hundred kilobytes could reduce the ciphertext size by an additional 50%. Overall, our work decreases the ciphertext size by 57.5%.