Paper 2022/1024

Multi-Input Attribute Based Encryption and Predicate Encryption

Abstract

Motivated by several new and natural applications, we initiate the study of multi-input predicate encryption ($\mathsf{m}\mathsf{i}\mathsf{P}\mathsf{E}$) and further develop multi-input attribute based encryption ($\mathsf{m}\mathsf{i}\mathsf{A}\mathsf{B}\mathsf{E}$). Our contributions are: 1. Formalizing Security: We provide definitions for $$ and $$ in the {symmetric} key setting and formalize security in the standard indistinguishability (IND) paradigm, against unbounded collusions. 2. Two-input $$ for $$ from $$ and Pairings: We provide the first constructions for two-input key-policy $$ for $$ from $$ 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 ciphertext-policy $$, to the seemingly unrelated problem of two-input key-policy $$. 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 $$ for $$ from Lattices: We show that techniques developed for succinct single-input ciphertext-policy $$ by Brakerski and Vaikuntanathan (ITCS 2022) can also be seen from the lens of $$ and obtain the first two-input key-policy $$ from lattices for $$. 4. Heuristic three-input $$ and $$ for $$ from Pairings and Lattices: We obtain the first three-input $$ for $$ by harnessing the powers of both the Agrawal-Yamada and the Brakerski-Vaikuntanathan constructions. 5. Multi-input $$ to multi-input $$ via Lockable Obfuscation: We provide a generic compiler that lifts multi-input $$ to multi-input $$ by relying on the hiding properties of Lockable Obfuscation ($$) by Wichs-Zirdelis and Goyal-Koppula-Waters (FOCS 2018), which can be based on $$. Our compiler generalizes 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 $$ schemes, we obtain the first constructions of two and three-input $$ schemes. Our constructions of multi-input $$ provide the first improvement to the compression factor of 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 $$ and multi-input key-policy $$ may lead to a new pathway for witness encryption.