### 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.

Available format(s)
Category
Public-key cryptography
Publication info
A minor revision of an IACR publication in ASIACRYPT 2015
Keywords
LWEAttribute-Based EncryptionBranching ProgramsEfficient
Contact author(s)
dhinakaran2705 @ gmail com
History
2015-08-19: revised
See all versions
Short URL
https://ia.cr/2014/819

CC BY

BibTeX

@misc{cryptoeprint:2014/819,
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{https://eprint.iacr.org/2014/819}},
url = {https://eprint.iacr.org/2014/819}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.