Cryptology ePrint Archive: Report 2014/622

Fully Secure Attribute Based Encryption from Multilinear Maps

Sanjam Garg and Craig Gentry and Shai Halevi and Mark Zhandry

Abstract: 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.

Category / Keywords: public-key cryptography / attribute based encryption, adaptive security, multilinear maps

Date: received 13 Aug 2014

Contact author: mzhandry at stanford edu

Available format(s): PDF | BibTeX Citation

Version: 20140813:235325 (All versions of this report)

Short URL: ia.cr/2014/622

Discussion forum: Show discussion | Start new discussion