Riding on Asymmetry: Efficient ABE for Branching Programs.
Sergey V Gorbunov, Dhinakaran Vinayagamurthy · 2014
In an Attribute-Based Encryption (ABE) a ciphertext, encrypting message µ, is associated with a public attribute vector x and a secret key skP is associated with a predicate P. The decryption returns µ if and only if P (x) = 1. ABE provides efficient and simple mechanism for data sharing supporting fine-grained access control. Moreover, it is used as a critical component in constructions of succinct functional encryption, reusable garbled circuits, token-based obfuscation and more. In this work, we describe a new efficient ABE scheme for a family of branching programs with short secret keys over a small ring. In particular, in our constriction the size of the secret key for a branching program P is |P |+poly(λ), where λ is the security parameter. Our construction is secure assuming nω(1)-hardness of standard Learning With Errors (LWE) problem, resulting in small ring modulo. Previous constructions relied on nO(logn)-hardness of LWE (resulting in large ring modulo) or had large secret keys of size |P |×poly(λ). We rely on techniques developed by Boneh et al. (EUROCRYPT’14) and Brakerski et al. (ITCS’14) in the context of ABE for circuits and fully-homomorphic encryption.