International Association
for Cryptologic Research

Registration-based encryption (RBE) is a primitive that aims to offer what identity-based encryption (IBE) offers without the so-called key-escrow problem. In RBE parties who wish to join the system will generate their own secret and public keys and register their public keys to a transparent party called key curator (KC) who does not have any secret state. The initial constructions of RBE made \emph{non-black-box} use of building block primitives, due to their use of either indistinguishability obfuscation or some garbling scheme. More recently, it was shown how to achieve \emph{black-box} constructions of (variants of) RBE and even stronger primitives based on \emph{bilinear maps} in which the RBE is relaxed to have a CRS whose length can \emph{grow} with the number of registered identities. Making cryptographic constructions in general, and RBE in particular, black-box is an important step as it can play a significant role in its efficiency and potential deployment. Hence, in this work we ask: \emph{what are the minimal assumptions for black-box constructions of RBE?} Particularly, can we black-box construct RBE schemes from the same assumptions used for public-key encryption or simpler algebraic assumptions that hold in the generic group model? In this work, we prove the first black-box separation results for RBE beyond the separations that follow from the observation that RBE black-box implies public-key encryption. In particular, we answer both of the questions above negatively and prove that neither trapdoor permutations nor (even Shoup's) generic group model can be used as the sole source of hardness for building RBE schemes. More generally, we prove that a relaxation of RBE in which all the keys are registered and compressed at the same time is already too complex to be built from either of the above-mentioned primitives in a black-box way. At a technical level, using compression techniques, we prove lemmas in the TDP and GGM oracle settings that prove the following intuitive yet useful fact: that compact strings cannot signal too many trapdoors, even if their generation algorithm takes exponential time. Due to their generality, our lemmas could be of independent interest and find more applications.

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.