Paper 2014/622

Fully Secure Attribute Based Encryption from Multilinear Maps

Sanjam Garg, Craig Gentry, Shai Halevi, and Mark Zhandry


We construct the first fully secure attribute based encryption (ABE) scheme that can handle access control policies expressible as polynomial-size circuits. Previous ABE schemes for general circuits were proved secure only in an unrealistic selective security model, where the adversary is forced to specify its target before seeing the public parameters, and full security could be obtained only by complexity leveraging, where the reduction succeeds only if correctly guesses the adversary’s target string x*, incurring a 2^{|x^*|} loss factor in the tightness of the reduction. At a very high level, our basic ABE scheme is reminiscent of Yao’s garbled circuits, with 4 gadgets per gate of the circuit, but where the decrypter in our scheme puts together the appropriate subset of gate gadgets like puzzle pieces by using a cryptographic multilinear map to multiply the pieces together. We use a novel twist of Waters’ dual encryption methodology to prove the full security of our scheme. Most importantly, we show how to preserve the delicate information-theoretic argument at the heart of Waters’ dual system by enfolding it in an information-theoretic argument similar to that used in Yao’s garbled circuits.

Available format(s)
Public-key cryptography
Publication info
Preprint. MINOR revision.
attribute based encryptionadaptive securitymultilinear maps
Contact author(s)
mzhandry @ stanford edu
2014-08-13: received
Short URL
Creative Commons Attribution


      author = {Sanjam Garg and Craig Gentry and Shai Halevi and Mark Zhandry},
      title = {Fully Secure Attribute Based Encryption from Multilinear Maps},
      howpublished = {Cryptology ePrint Archive, Paper 2014/622},
      year = {2014},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.