Lower Bounds on Assumptions Behind Registration-Based Encryption

Mohammad Hajiabadi, Mohammad Mahmoody, Wei Qi, Sara Sarfaraz

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Scopus citations


Registration-based encryption (RBE) [11] is a primitive that aims to offer what identity-based encryption (IBE) [2] 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 non-black-box use of building block primitives, due to their use of either indistinguishability obfuscation [11] or some garbling scheme [12]. More recently, it was shown [14, 17] how to achieve black-box constructions of (variants of) RBE and even stronger primitives based on bilinear maps in which the RBE is relaxed to have a CRS whose length can 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: 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.

Original languageEnglish (US)
Title of host publicationTheory of Cryptography - 21st International Conference, TCC 2023, Proceedings
EditorsGuy Rothblum, Hoeteck Wee
PublisherSpringer Science and Business Media Deutschland GmbH
Number of pages29
ISBN (Print)9783031486173
StatePublished - 2023
Event21st International conference on Theory of Cryptography Conference, TCC 2023 - Taipei, Taiwan, Province of China
Duration: Nov 29 2023Dec 2 2023

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume14370 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference21st International conference on Theory of Cryptography Conference, TCC 2023
Country/TerritoryTaiwan, Province of China

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • General Computer Science

Cite this