International Association
for Cryptologic Research

Registration-based encryption (Garg, Hajiabadi, Mahmoody, Rahimi, TCC'18) is a primitive that aims to offer what identity-based encryption offers without the key-escrow problem. In RBE, parties generate their secret keys, a key curator (KC) manages the public keys and updates the compact public parameter, and everyone can use the updated public parameter to securely encrypt messages for individuals. A major downside of RBE is that parties might need to periodically receive extra information from the KC, called decryption updates, that help them decrypt successfully. Current RBE schemes with n registered parties require \Omega(log n) number of updates while the public parameter is of length poly(log n). This leads to the following natural question: are so many decryption updates necessary for RBE schemes? Indeed, it would be desirable to have RBEs with only a constant number of updates. In this paper, we prove almost tight lowerbounds for the number of updates in RBE schemes. More generally, we prove a trade-off between the number of updates in RBEs and the length of the public parameter, as long as the update times are fixed, which is a natural property that holds for all known RBE constructions. In particular, we prove that for any RBE scheme for n \geq \binom{k+d}{d+1} identities and d updates that arrive at fixed times, the public parameter needs to be of length \Omega(k). In particular, our lower bound shows that RBE systems with public parameters of length poly(\log n) require almost logarithmic \Omega(log n / log log n) number of updates.