Paper 2019/1044

Verifiable Registration-Based Encryption

Rishab Goyal and Satyanarayana Vusirikala


In a recent work, Garg, Hajiabadi, Mahmoody, and Rahimi (TCC 18) introduced a new encryption framework, which they referred to as Registration-Based Encryption (RBE). The central motivation behind RBE was to provide a novel methodology for solving the well-known key-escrow problem in Identity-Based Encryption (IBE) systems. Informally, in an RBE system there is no private-key generator unlike IBE systems, but instead it is replaced with a public key accumulator. Every user in an RBE system samples its own public-secret key pair, and sends the public key to the accumulator for registration. The key accumulator has no secret state, and is only responsible for compressing all the registered user identity-key pairs into a short public commitment. Here the encryptor only requires the compressed parameters along with the target identity, whereas a decryptor requires supplementary key material along with the secret key associated with the registered public key. The initial construction by Garg et al. (TCC 18) based on standard assumptions only provided weak efficiency properties. In a follow-up work by Garg, Hajiabadi, Mahmoody, Rahimi, and Sekar (PKC 19), they gave an efficient RBE construction from standard assumptions. However, both these works considered the key accumulator to be honest which might be too strong an assumption in real-world scenarios. In this work, we initiate a formal study of RBE systems with malicious key accumulators. To that end, we introduce a strengthening of the RBE framework which we call Verifiable RBE (VRBE). A VRBE system additionally gives the users an extra capability to obtain short proofs from the key accumulator proving correct (and unique) registration for every registered user as well as proving non-registration for any yet unregistered identity. We construct VRBE systems which provide succinct proofs of registration and non-registration from standard assumptions (such as CDH, Factoring, LWE). Our proof systems also naturally allow a much more efficient audit process which can be perfomed by any non-participating third party as well. A by-product of our approach is that we provide a more efficient RBE construction than that provided in the prior work of Garg et al. (PKC 19). And, lastly we initiate a study on extension of VRBE to a wider range of access and trust structures.

Available format(s)
Public-key cryptography
Publication info
Public Key EncryptionRegistration based EncryptionKey Escrow Problem
Contact author(s)
satya @ cs utexas edu
rgoyal @ cs utexas edu
2019-09-18: received
Short URL
Creative Commons Attribution


      author = {Rishab Goyal and Satyanarayana Vusirikala},
      title = {Verifiable Registration-Based Encryption},
      howpublished = {Cryptology ePrint Archive, Paper 2019/1044},
      year = {2019},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.