Cryptology ePrint Archive: Report 2021/709

Bounded Collusion ABE for TMs from IBE

Rishab Goyal and Ridwan Syed and Brent Waters

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.

Category / Keywords: public-key cryptography / ABE, TMs, Uniform Model, IBE, RAM

Original Publication (in the same form): IACR-ASIACRYPT-2021

Date: received 27 May 2021, last revised 14 Sep 2021

Contact author: goyal at utexas edu, bwaters at cs utexas edu

Available format(s): PDF | BibTeX Citation

Note: Full version of the Asiacrypt 2021 paper.

Version: 20210914:234210 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]