Paper 2014/622

Fully Secure Attribute Based Encryption from Multilinear Maps

Sanjam Garg, Craig Gentry, 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.