We present attribute-based encryption schemes for circuits of any arbitrary polynomial size, where the public parameters and the ciphertext grow linearly with the depth of the circuit. Our construction is secure under the standard learning with errors (LWE) assumption. Previous constructions of attribute-based encryption were for Boolean formulas, captured by the complexity class NC1.
In the course of our construction, we present a new framework for constructing ABE schemes. As a by-product of our framework, we obtain ABE schemes for polynomial-size branching programs, corresponding to the complexity class LOGSPACE, under quantitatively better assumptions.Category / Keywords: public-key cryptography / Attribute-Based Encryption, Lattices Publication Info: Full Version of STOC 2013 proceedings Date: received 31 May 2013, last revised 31 May 2013 Contact author: sgorbunov at cs toronto edu Available format(s): PDF | BibTeX Citation Version: 20130603:133554 (All versions of this report) Discussion forum: Show discussion | Start new discussion