International Association
for Cryptologic Research

In an Attribute-Based Encryption (ABE) a ciphertext, encrypting message $\\mu$, is associated with a public attribute vector $\\vecx$ and a secret key $\\sk_P$ is associated with a predicate $P$. The decryption returns $\\mu$ if and only if $P(\\vecx) = 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(\\secp)$, where $\\secp$ is the security parameter. Our construction is secure assuming $n^{\\omega(1)}$-hardness of standard Learning With Errors (LWE) problem, resulting in small ring modulo. Previous constructions relied on $n^{O(\\log n)}$-hardness of LWE (resulting in large ring modulo) or had large secret keys of size $|P| \\times \\poly(\\secp)$. 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.