Paper 2023/941

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

Shweta Agrawal, IIT Madras, Chennai
Melissa Rossi, ANSSI, Paris
Anshu Yadav, IIT Madras, Chennai
Shota Yamada, AIST, Tokyo

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 ${\sf LWE}$ and tensor ${\sf LWE}$, and used these to construct broadcast encryption and ciphertext policy attribute based encryption for ${\sf 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 (${\sf MIABE}$) for the function class ${\sf NC_1}$ for any constant arity from evasive ${\sf LWE}$. Our construction can be extended to support the function class ${\sf P}$ by using evasive and a suitable strengthening of tensor ${\sf LWE}$. In more detail, our construction supports $k$ encryptors, for any constant $k$, where each encryptor uses the master secret key ${\sf msk}$ to encode its input $(\mathbf{x}_i, m_i)$, the key generator computes a key ${\sf sk}_f$ for a function $f \in {\sf NC}_1$ and the decryptor can recover $(m_1,\ldots,m_k)$ if and only if $f(\mathbf{x}_1,\ldots,\mathbf{x}_k)=1$. The only known construction for ${\sf MIABE}$ for ${\sf 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 ${\sf 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 ${\sf 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 ${\sf NC}_1$ or ${\sf P}$ from simple assumptions that may be conjectured post-quantum secure. Along the way, we show that the tensor ${\sf LWE}$ assumption can be reduced to standard ${\sf 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.

Note: 2024/05/15 Changed the statement of Lemma 3.4 and fixed the bug in the proof.

Available format(s)
Cryptographic protocols
Publication info
A major revision of an IACR publication in CRYPTO 2023
multi-input attribute based encryptionmulti-input predicate encryptionevasive LWEtensor LWE
Contact author(s)
shweta @ cse iitm ac in
melissa rossi @ ssi gouv fr
anshu yadav06 @ gmail com
yamada-shota @ aist go jp
2024-05-15: revised
2023-06-16: received
See all versions
Short URL
Creative Commons Attribution


      author = {Shweta Agrawal and Melissa Rossi and Anshu Yadav and Shota Yamada},
      title = {Constant Input Attribute Based (and Predicate) Encryption from Evasive and Tensor {LWE}},
      howpublished = {Cryptology ePrint Archive, Paper 2023/941},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.