Paper 2021/499

Optimizing Registration Based Encryption

Kelong Cong, Karim Eldefrawy, and Nigel P. Smart


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%.

Available format(s)
Public-key cryptography
Publication info
Published elsewhere. Minor revision. IMA CC 2021
Contact author(s)
kelong cong @ esat kuleuven be
karim eldefrawy @ sri com
nigel smart @ kuleuven be
2021-09-27: revised
2021-04-19: received
See all versions
Short URL
Creative Commons Attribution


      author = {Kelong Cong and Karim Eldefrawy and Nigel P.  Smart},
      title = {Optimizing Registration Based Encryption},
      howpublished = {Cryptology ePrint Archive, Paper 2021/499},
      year = {2021},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.