Paper 2018/273

Attribute Based Encryption with Sublinear Decryption from LWE

Prabhanjan Ananth and Xiong Fan

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 when the function, associated with the ABE key, admits a RAM program whose runtime is sublinear in the length of the attribute. 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 improves upon the work of Goldwasser et al., who achieved this result based on SNARKs and extractable witness encryption. En route to constructing this primitive, we introduce the notion of controlled homomorphic recoding (CHR) schemes. We present a generic transformation from controlled homomorphic recoding schemes to attribute-based encryption for RAMs and then we show how to instantiate controlled homomorphic recoding schemes based on learning with errors.