Paper 2021/709

Bounded Collusion ABE for TMs from IBE

Rishab Goyal, Ridwan Syed, and Brent Waters


We give an attribute-based encryption system for Turing Machines that is provably secure assuming only the existence of identity-based encryption (IBE) for large identity spaces. Currently, IBE is known to be realizable from most mainstream number theoretic assumptions that imply public key cryptography including factoring, the search Diffie-Hellman assumption, and the Learning with Errors assumption. Our core construction provides security against an attacker that makes a single key query for a machine $T$ before declaring a challenge string $w^*$ that is associated with the challenge ciphertext. We build our construction by leveraging a Garbled RAM construction of Gentry, Halevi, Raykova, and Wichs; however, to prove security we need to introduce a new notion of security called iterated simulation security. We then show how to transform our core construction into one that is secure for an a-priori bounded number $q = q(\lambda)$ of key queries that can occur either before or after the challenge ciphertext. We do this by first showing how one can use a special type of non-committing encryption to transform a system that is secure only if a single key is chosen before the challenge ciphertext is declared into one where the single key can be requested either before or after the challenge ciphertext. We give a simple construction of this non-committing encryption from public key encryption in the Random Oracle Model. Next, one can apply standard combinatorial techniques to lift from single-key adaptive security to $q$-key adaptive security.

Note: Full version of the Asiacrypt 2021 paper.

Available format(s)
Public-key cryptography
Publication info
Published by the IACR in ASIACRYPT 2021
Contact author(s)
goyal @ utexas edu
bwaters @ cs utexas edu
2021-09-14: revised
2021-05-28: received
See all versions
Short URL
Creative Commons Attribution


      author = {Rishab Goyal and Ridwan Syed and Brent Waters},
      title = {Bounded Collusion ABE for TMs from IBE},
      howpublished = {Cryptology ePrint Archive, Paper 2021/709},
      year = {2021},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.