Multi-input Attribute Based Encryption and Predicate Encryption

Motivated by several new and natural applications, we initiate the study of multi-input predicate encryption (miPE) and further develop multi-input attribute based encryption (miABE). Our contributions are:

1. Formalizing Security: We provide definitions for miABE and miPE in the symmetric key setting and formalize security in the standard indistinguishability (IND) paradigm, against unbounded collusions. 2. Two-input ABE for NC1 from LWE and Pairings: We provide the first constructions for two-input key-policy ABE for NC1 from LWE and pairings. Our construction leverages a surprising connection between techniques recently developed by Agrawal and Yamada (Eurocrypt, 2020) in the context of succinct single-input ciphertextpolicy ABE, to the seemingly unrelated problem of two-input keypolicy 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. Heuristic two-input ABE for P from Lattices: We show that techniques developed for succinct single-input ciphertext-policy ABE by Brakerski and Vaikuntanathan (ITCS 2022) can also be seen from the lens of miABE and obtain the first two-input key-policy ABE from lattices for P. 4. Heuristic three-input ABE and PE for NC1 from Pairings and Lattices: We obtain the first three-input ABE for NC1 by harnessing the powers of both the Agrawal-Yamada and the Brakerski-Vaikuntanathan constructions. 5. Multi-input ABE to multi-input PE via Lockable Obfuscation: We provide a generic compiler that lifts multi-input ABE to multi-input PE by relying on the hiding properties of Lockable Obfuscation (LO) by Wichs-Zirdelis and Goyal-Koppula-Waters (FOCS 2018), which can be based on 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 threeinput ABE schemes, we obtain the first constructions of two and three-input PE schemes.