| Title | : | Attribute Based Encryption for Nondeterministic Finite Automata from LWE |
| Speaker | : | Monosij Maitra (IITM) |
| Details | : | Thu, 25 Jul, 2019 2:00 PM @ AM Turing Hall |
| Abstract: | : | Attribute based Encryption (ABE), first introduced in the seminal work of Sahai and Waters in 2005, enables fine grained access control on encrypted data. In ABE, a ciphertext of a message m is labelled with a public attribute x and secret keys are labelled with functions f. While this is traditionally known as key-policy ABE (KP-ABE) in the literature, the alternate notion of ciphertext-policy ABE (CP-ABE) requires secret keys to correspond to attributes and ciphertexts to correspond to functions (or policies). In both cases, decryption yields the hidden message m if and only if the attribute satisfies the function f, namely f(x) = 1. In most constructions, the function f embedded in the key is represented as a circuit. Circuits, though powerful, are a non-uniform model of computation which requires different representations for different input lengths. This forces the scheme to provide multiple function keys for the same function as the input length varies. ABE schemes, where the function is represented as a circuit, have received a lot of attention in the recent years. But very little is known about support for uniform models of computation, where we have such constructions from standard assumptions. In 2012, Waters provided a construction of KP-ABE for Deterministic Finite Automata (DFA) from parametrized "q-type" assumptions over bilinear maps. Generalizing this construction to Nondeterministic Finite Automata (NFA), without of course incurring an exponential blow-up in machine size, was left as an explicit open problem in the same work. Constructions from other standard assumptions in pairings or lattices were also out of reach. In our work, we construct the first symmetric-key KP-ABE scheme for NFA from the learning with errors (LWE) assumption. Our scheme supports unbounded length inputs, unbounded length NFAs and unbounded key requests. We also generalize our results to obtain the first constructions of predicate encryption, bounded key functional encryption schemes and reusable garbled NFAs from LWE. In terms of lower bounds, we show that secret key functional encryption even for DFAs, with security against unbounded key requests implies indistinguishability obfuscation (iO) for circuits. This is based on a joint work with Shweta Agrawal and Shota Yamada and will be presented at Crypto 2019. If time permits, we will also mention about a follow-up work that is in submission right now, where we obtain interesting results in the pairing based setting. In particular, we obtain the first KP-ABE and CP-ABE schemes for DFA from decisional linear (DLIN) assumption. As before, these constructions also support unbounded inputs, machines and key requests. We present simple compilers to embed any DFA computation into monotone span programs (MSP). This lets us compose existing constructions of unbounded KP-ABE and CP-ABE for MSP (modified suitably) in a simple and modular way to obtain KP-ABE for DFA. Moreover, we obtain CP-ABE for DFA for the first time using our building blocks essentially in a symmetric way. This is also a joint work with Shweta Agrawal and Shota Yamada. |
