Paper 2022/1505

Efficient Registration-Based Encryption

Noemi Glaeser, Max Planck Institute for Security and Privacy, University of Maryland, College Park
Dimitris Kolonelos, IMDEA Software Institute, Universidad Politécnica de Madrid
Giulio Malavolta, Bocconi University, Max Planck Institute for Security and Privacy
Ahmadreza Rahimi, Max Planck Institute for Security and Privacy

Registration-based encryption (RBE) was recently introduced as an alternative to identity-based encryption (IBE), to resolve the key-escrow problem: In RBE, the trusted authority is substituted with a weaker entity, called the key curator, who has no knowledge of any secret key. Users generate keys on their own and then publicly register their identities and their corresponding public keys to the key curator. RBE is a promising alternative to IBE, retaining many of its advantages while removing the key-escrow problem, the major drawback of IBE. Unfortunately, all existing constructions of RBE use cryptographic schemes in a non black-box way, which makes them prohibitively expensive. It has been estimated that the size of an RBE ciphertext would be in the order of terabytes (though no RBE has even been implemented). In this work, we propose a new approach to construct RBE, from standard assumptions in bilinear groups. Our scheme is black-box and it is concretely highly efficient—a ciphertext is 914 bytes. To substantiate this claim, we implemented a prototype of our scheme and we show that it scales to millions of users. The public parameters of the scheme are on the order of kilobytes. The most expensive operation (registration) takes at most a handful of seconds, whereas the encryption and decryption runtimes are on the order of milliseconds. This is the first-ever implementation of an RBE scheme and demonstrates that the practical deployment of RBE is already possible with today’s hardware.

Available format(s)
Public-key cryptography
Publication info
Published elsewhere. Minor revision. ACM CCS 2023
Registration-Based EncryptionIdentity-Based EncryptionRBEIBEVector commitments
Contact author(s)
nglaeser @ umd edu
dimitris kolonelos @ imdea org
giulio malavolta @ hotmail it
ahmadreza rahimi @ mpi-sp org
2023-09-20: last of 2 revisions
2022-11-01: received
See all versions
Short URL
Creative Commons Attribution


      author = {Noemi Glaeser and Dimitris Kolonelos and Giulio Malavolta and Ahmadreza Rahimi},
      title = {Efficient Registration-Based Encryption},
      howpublished = {Cryptology ePrint Archive, Paper 2022/1505},
      year = {2022},
      doi = {10.1145/3576915.3616596},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.