Paper 2014/819

Riding on Asymmetry: Efficient ABE for Branching Programs

Sergey Gorbunov and Dhinakaran Vinayagamurthy


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.

Available format(s)
Public-key cryptography
Publication info
A minor revision of an IACR publication in ASIACRYPT 2015
LWEAttribute-Based EncryptionBranching ProgramsEfficient
Contact author(s)
dhinakaran2705 @ gmail com
2015-08-19: revised
2014-10-12: received
See all versions
Short URL
Creative Commons Attribution


      author = {Sergey Gorbunov and Dhinakaran Vinayagamurthy},
      title = {Riding on Asymmetry: Efficient ABE for Branching Programs},
      howpublished = {Cryptology ePrint Archive, Paper 2014/819},
      year = {2014},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.