In this work, we describe a new efficient ABE scheme for a family of branching programs with short secret keys and from a mild assumption. In particular, in our construction 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 the standard Learning With Errors (LWE) problem with approximation factors $n^{\omega(1)}$. Previous constructions relied on $n^{O(\log n)}$ approximation factors of LWE (resulting in less efficient parameters instantiation) 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.
Category / Keywords: public-key cryptography / LWE, Attribute-Based Encryption, Branching Programs, Efficient Original Publication (with minor differences): IACR-ASIACRYPT-2015 Date: received 9 Oct 2014, last revised 19 Aug 2015 Contact author: dhinakaran2705 at gmail com Available format(s): PDF | BibTeX Citation Version: 20150819:162121 (All versions of this report) Short URL: ia.cr/2014/819 Discussion forum: Show discussion | Start new discussion