Cryptology ePrint Archive: Report 2014/819

Riding on Asymmetry: Efficient ABE for Branching Programs

Sergey Gorbunov and Dhinakaran Vinayagamurthy

Abstract: In an Attribute-Based Encryption (ABE) scheme the ciphertext encrypting a 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 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:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]