Paper 2016/118

Circuit-ABE from LWE: Unbounded Attributes and Semi-Adaptive Security

Zvika Brakerski and Vinod Vaikuntanathan


We construct an LWE-based key-policy attribute-based encryption (ABE) scheme that supports attributes of unbounded polynomial length. Namely, the size of the public parameters is a fixed polynomial in the security parameter and a depth bound, and with these fixed length parameters, one can encrypt attributes of arbitrary length. Similarly, any polynomial size circuit that adheres to the depth bound can be used as the policy circuit regardless of its input length (recall that a depth $d$ circuit can have as many as $2^d$ inputs). This is in contrast to previous LWE-based schemes where the length of the public parameters has to grow linearly with the maximal attribute length. We prove that our scheme is semi-adaptively secure, namely, the adversary can choose the challenge attribute after seeing the public parameters (but before any decryption keys). Previous LWE-based constructions were only able to achieve selective security. (We stress that the complexity leveraging technique is not applicable for unbounded attributes.) We believe that our techniques are of interest at least as much as our end result. Fundamentally, selective security and bounded attributes are both shortcomings that arise out of the current LWE proof techniques that program the challenge attributes into the public parameters. The LWE toolbox we develop in this work allows us to "delay" this programming. In a nutshell, the new tools include a way to generate an a-priori unbounded sequence of LWE matrices, and have fine-grained control over which trapdoor is embedded in each and every one of them, all with succinct representation.

Note: Typo fixed.

Available format(s)
Public-key cryptography
Publication info
Preprint. MINOR revision.
attribute-based encryption
Contact author(s)
vinodv @ mit edu
2016-03-13: revised
2016-02-11: received
See all versions
Short URL
Creative Commons Attribution


      author = {Zvika Brakerski and Vinod Vaikuntanathan},
      title = {Circuit-ABE from LWE: Unbounded Attributes and Semi-Adaptive Security},
      howpublished = {Cryptology ePrint Archive, Paper 2016/118},
      year = {2016},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.