Paper 2022/1285

Lower Bounds for the Number of Decryption Updates in Registration-Based Encryption

Mohammad Mahmoody, University of Virginia
Wei Qi, University of Virginia
Ahmadreza Rahimi, Max Planck Institute for Security and Privacy

Registration-based encryption (Garg, Hajiabadi, Mahmoody, Rahimi, TCC'18) aims to offer what identity-based encryption offers without the key-escrow problem, which refers to the ability of the private-key generator to obtain parties' decryption keys at wish. In RBE, parties generate their own secret and public keys and register their public keys to the key curator (KC) who updates a compact public parameter after each registration. The updated public parameter can then be used to securely encrypt messages to registered identities. A major drawback of RBE, compared with IBE, is that in order to decrypt, parties might need to periodically request so-called decryption updates from the KC. Current RBE schemes require $\Omega(\log n)$ number of updates after $n$ registrations, while the public parameter is of length $\text{poly}(\log n)$. Clearly, it would be highly desirable to have RBEs with only, say, a constant number of updates. This leads to the following natural question: are so many (logarithmic) updates necessary for RBE schemes, or can we decrease the frequency of updates significantly? In this paper, we prove an almost tight lower bound for the number of updates in RBE schemes, as long as the times that parties receive updates only depend on the registration time of the parties, which is a natural property that holds for all known RBE constructions. More generally, we prove a trade-off between the number of updates in RBEs and the length of the public parameter for any scheme with fixed update times. Indeed, we prove that for any such RBE scheme, if there are $n \geq \binom{k+d}{d+1}$ identities that receive at most $d$ updates, the public parameter needs to be of length $\Omega(k)$. As a corollary, we find that RBE systems with fixed update times and public parameters of length $\text{poly} (\log n)$, require $\Omega(\log n/\text{loglog}\ n)$ decryption updates, which is optimal up to a $O(\text{loglog}\ n)$ factor.

Available format(s)
Public-key cryptography
Publication info
Published by the IACR in TCC 2022
Registration-Based Encryption Lower Bounds Efficiency
Contact author(s)
mahmoody @ gmail com
wq4sr @ virginia edu
ahmadreza rahimi @ mpi-sp org
2022-09-28: approved
2022-09-27: received
See all versions
Short URL
Creative Commons Attribution


      author = {Mohammad Mahmoody and Wei Qi and Ahmadreza Rahimi},
      title = {Lower Bounds for the Number of Decryption Updates in Registration-Based Encryption},
      howpublished = {Cryptology ePrint Archive, Paper 2022/1285},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.