International Association for Cryptologic Research

International Association
for Cryptologic Research


Paper: Multi-Input Attribute Based Encryption and Predicate Encryption

Shweta Agrawal , IIT Madras
Anshu Yadav , IIT Madras
Shota Yamada , AIST
Search ePrint
Search Google
Presentation: Slides
Conference: CRYPTO 2022
Abstract: Motivated by several new and natural applications, we initiate the study of multi-input predicate encryption (${\sf miPE}$) and further develop multi-input attribute based encryption (${\sf miABE}$). Our contributions are: 1. {\it Formalizing Security:} We provide definitions for ${\sf miABE}$ and ${\sf miPE}$ in the {symmetric} key setting and formalize security in the standard {\it indistinguishability} (IND) paradigm, against {\it unbounded} collusions. 2. {\it Two-input ${\sf ABE}$ for ${\sf NC}_1$ from ${\sf LWE}$ and Pairings:} We provide the first constructions for two-input {\it key-policy} ${\sf ABE}$ for ${\sf NC}_1$ from ${\sf LWE}$ and pairings. Our construction leverages a surprising connection between techniques recently developed by Agrawal and Yamada (Eurocrypt, 2020) in the context of succinct {\it single}-input {\it ciphertext-policy} ${\sf ABE}$, to the seemingly unrelated problem of {\it two}-input {\it key-policy} ${\sf ABE}$. Similarly to Agrawal-Yamada, our construction is proven secure in the bilinear generic group model. By leveraging inner product functional encryption and using (a variant of) the KOALA knowledge assumption, we obtain a construction in the standard model analogously to Agrawal, Wichs and Yamada (TCC, 2020). 3. {\it Heuristic two-input ${\sf ABE}$ for ${\sf P}$ from Lattices:} We show that techniques developed for succinct single-input ciphertext-policy ${\sf ABE}$ by Brakerski and Vaikuntanathan (ITCS 2022) can also be seen from the lens of ${\sf miABE}$ and obtain the first two-input key-policy ${\sf ABE}$ from lattices for ${\sf P}$. 4. {\it Heuristic three-input ${\sf ABE}$ and ${\sf PE}$ for ${\sf NC}_1$ from Pairings and Lattices:} We obtain the first {\it three}-input ${\sf ABE}$ for ${\sf NC}_1$ by harnessing the powers of both the Agrawal-Yamada and the Brakerski-Vaikuntanathan constructions. 5. {\it Multi-input ${\sf ABE}$ to multi-input ${\sf PE}$ via Lockable Obfuscation:} We provide a generic compiler that lifts multi-input ${\sf ABE}$ to multi-input $\PE$ by relying on the hiding properties of Lockable Obfuscation (${\sf LO}$) by Wichs-Zirdelis and Goyal-Koppula-Waters (FOCS 2018), which can be based on ${\sf LWE}$. Our compiler generalises such a compiler for single-input setting to the much more challenging setting of multiple inputs. By instantiating our compiler with our new two and three-input ${\sf ABE}$ schemes, we obtain the first constructions of two and three-input ${\sf PE}$ schemes. Our constructions of multi-input ${\sf ABE}$ provide the first improvement to the compression factor of {\it non-trivially exponentially efficient Witness Encryption} defined by Brakerski et al. (SCN 2018) without relying on compact functional encryption or indistinguishability obfuscation. We believe that the unexpected connection between succinct single-input ciphertext-policy ${\sf ABE}$ and multi-input key-policy ${\sf ABE}$ may lead to a new pathway for witness encryption. We remark that our constructions provide the first candidates for a nontrivial class of ${\sf miFE}$ without needing ${\sf LPN}$ or low depth ${\sf PRG}$. \keywords{Multi-input \and Attribute Based Encryption \and Predicate Encryption.}
Video from CRYPTO 2022
  title={Multi-Input Attribute Based Encryption and Predicate Encryption},
  author={Shweta Agrawal and Anshu Yadav and Shota Yamada},