Paper 2018/273

Towards Attribute-Based Encryption for RAMs from LWE: Sub-linear Decryption, and More

Prabhanjan Ananth, Xiong Fan, and Elaine Shi

Abstract

Attribute based encryption (ABE) is an advanced encryption system with a built-in mechanism to generate keys associated with functions which in turn provide restricted access to encrypted data. Most of the known candidates of attribute based encryption model the functions as circuits. This results in significant efficiency bottlenecks, especially in the setting where the function associated with the ABE key is represented by a random access machine (RAM) and a database, with the runtime of the RAM program being sublinear in the database size. In this work we study the notion of attribute based encryption for random access machines (RAMs), introduced in the work of Goldwasser, Kalai, Popa, Vaikuntanathan and Zeldovich (Crypto 2013). We present a construction of attribute based encryption for RAMs satisfying sublinear decryption complexity assuming learning with errors; this is the first construction based on standard assumptions. Previously, Goldwasser et al. achieved this result based on non-falsifiable knowledge assumptions. We also consider a dual notion of ABE for RAMs, where the database is in the ciphertext and we show how to achieve this dual notion, albeit with large attribute keys, also based on learning with errors.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published by the IACR in ASIACRYPT 2019
Keywords
attribute-based encryptionRAMsLWE
Contact author(s)
xfan @ cs cornell edu
History
2020-08-04: last of 3 revisions
2018-03-22: received
See all versions
Short URL
https://ia.cr/2018/273
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2018/273,
      author = {Prabhanjan Ananth and Xiong Fan and Elaine Shi},
      title = {Towards Attribute-Based Encryption for RAMs from LWE: Sub-linear Decryption, and More},
      howpublished = {Cryptology ePrint Archive, Paper 2018/273},
      year = {2018},
      note = {\url{https://eprint.iacr.org/2018/273}},
      url = {https://eprint.iacr.org/2018/273}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.