Paper 2019/629

Attribute Based Encryption (and more) for Nondeterministic Finite Automata from LWE

Shweta Agrawal, Monosij Maitra, and Shota Yamada


Constructing Attribute Based Encryption (ABE) [SW05] for uniform models of computation from standard assumptions, is an important problem, about which very little is known. The only known ABE schemes in this setting that i) avoid reliance on multilinear maps or indistinguishability obfuscation, ii) support unbounded length inputs and iii) permit unbounded key requests to the adversary in the security game, are by Waters from Crypto, 2012 [Wat12] and its variants. Waters provided the first ABE for Deterministic Finite Automata (DFA) satisfying the above properties, from a parametrized or ``q-type'' assumption over bilinear maps. Generalizing this construction to Nondeterministic Finite Automata (NFA) was left as an explicit open problem in the same work, and has seen no progress to date. Constructions from other assumptions such as more standard pairing based assumptions, or lattice based assumptions has also proved elusive. In this work, we construct the first symmetric key attribute based encryption scheme for nondeterministic finite automata (NFA) from the learning with errors (LWE) assumption. Our scheme supports unbounded length inputs as well as unbounded length machines. In more detail, secret keys in our construction are associated with an NFA M of unbounded length, ciphertexts are associated with a tuple (x;m) where x is a public attribute of unbounded length and m is a secret message bit, and decryption recovers m if and only if M(x) = 1. Further, we leverage our ABE to achieve (restricted notions of) attribute hiding analogous to the circuit setting, obtaining the first predicate encryption and bounded key functional encryption schemes for NFA from LWE. We achieve machine hiding in the single/bounded key setting to obtain the first reusable garbled NFA from standard assumptions. 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 suggests a barrier in achieving full fledged functional encryption for NFA.

Note: Full version

Available format(s)
Public-key cryptography
Publication info
A major revision of an IACR publication in CRYPTO 2019
Non-determinisitic Finite AutomataAttribute based EncrytionPredicate EncryptionFunctional EncryptionLWE
Contact author(s)
shweta a @ gmail com
monosij maitra @ gmail com
shota yamada enc @ gmail com
yamada-shota @ aist go jp
2019-08-21: revised
2019-06-03: received
See all versions
Short URL
Creative Commons Attribution


      author = {Shweta Agrawal and Monosij Maitra and Shota Yamada},
      title = {Attribute Based Encryption (and more) for Nondeterministic Finite Automata from LWE},
      howpublished = {Cryptology ePrint Archive, Paper 2019/629},
      year = {2019},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.