International Association for Cryptologic Research

International Association
for Cryptologic Research


Constant Input Attribute Based (and Predicate) Encryption from Evasive and Tensor LWE

Shweta Agrawal , IIT Madras, Chennai
Mélissa Rossi , ANSSI, Paris
Anshu Yadav , IIT Madras, Chennai
Shota Yamada , AIST, Tokyo
DOI: 10.1007/978-3-031-38551-3_17 (login may be required)
Search ePrint
Search Google
Presentation: Slides
Conference: CRYPTO 2023
Abstract: Constructing advanced cryptographic primitives such as obfuscation or broadcast encryption from standard hardness assumptions in the post quantum regime is an important area of research, which has met with limited success despite significant effort. It is therefore extremely important to find new, simple to state assumptions in this regime which can be used to fill this gap. An important step was taken recently by Wee (Eurocrypt '22) who identified two new assumptions from lattices, namely evasive LWE and tensor LWE, and used these to construct broadcast encryption and ciphertext policy attribute based encryption for P with optimal parameters. Independently, Tsabary formulated a similar assumption and used it to construct witness encryption (Crypto '22). Following Wee's work, Vaikuntanathan, Wee and Wichs independently provided a construction of witness encryption (Asiacrypt '22). In this work, we advance this line of research by providing the first construction of multi-input attribute based encryption (miABE) for the function class NC_1 for any constant arity from evasive LWE. Our construction can be extended to support the function class P} by using evasive and a suitable strengthening of tensor LWE. In more detail, our construction supports k encryptors, for any constant k, where each encryptor uses the master secret key msk to encode its input (x_i, m_i), the key generator computes a key sk_f for a function f \in NC_1 and the decryptor can recover (m_1,...,m_k) if and only if f(x_1,...,x_k)=1. The only known construction for miABE for NC_1 by Agrawal, Yadav and Yamada (Crypto '22) supports arity 2 and relies on pairings in the generic group model (or with a non-standard knowledge assumption) in addition to LWE. Furthermore, it is completely unclear how to go beyond arity 2 using this approach due to the reliance on pairings. Using a compiler from Agrawal, Yadav and Yamada (Crypto '22), our miABE can be upgraded to multi-input predicate encryption for the same arity and function class. Thus, we obtain the first constructions for constant-arity predicate and attribute based encryption for a generalized class such as NC_1 or P from simple assumptions that may be conjectured post-quantum secure. Along the way, we show that the tensor LWE assumption can be reduced to standard LWE in an important special case which was not known before. This adds confidence to the plausibility of the assumption and may be of wider interest.
  title={Constant Input Attribute Based (and Predicate) Encryption from Evasive and Tensor LWE},
  author={Shweta Agrawal and Mélissa Rossi and Anshu Yadav and Shota Yamada},