International Association for Cryptologic Research

International Association
for Cryptologic Research


Paper: Bounded Collusion ABE for TMs from IBE

Rishab Goyal , Massachusetts Institute of Technology
Ridwan Syed , UT Austin
Brent Waters , UT Austin and NTT Research
Search ePrint
Search Google
Conference: ASIACRYPT 2021
Abstract: 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.
Video from ASIACRYPT 2021
  title={Bounded Collusion ABE for TMs from IBE},
  author={Rishab Goyal and Ridwan Syed and Brent Waters},