Paper 2019/645

Attribute Based Encryption for Deterministic Finite Automata from DLIN

Shweta Agrawal, Monosij Maitra, and Shota Yamada


Waters [Crypto, 2012] provided the first attribute based encryption scheme ABE for Deterministic Finite Automata (DFA) from a parametrized or ``q-type'' assumption over bilinear maps. Obtaining a construction from static assumptions has been elusive, despite much progress in the area of ABE. In this work, we construct the first attribute based encryption scheme for DFA from static assumptions on pairings, namely, the DLIN assumption. Our scheme supports unbounded length inputs, unbounded length machines and unbounded key requests. In more detail, secret keys in our construction are associated with a DFA $M$ of unbounded length, ciphertexts are associated with a tuple $(x, b)$ where $x$ is a public attribute of unbounded length and $b$ is a secret message bit, and decryption recovers $b$ if and only if $M(x)=1$. Our techniques are at least as interesting as our final result. We present a simple compiler that combines constructions of unbounded ABE schemes for monotone span programs (MSP) in a black box way to construct ABE for DFA. In more detail, we find a way to embed DFA computation into monotone span programs, which lets us compose existing constructions (modified suitably) of unbounded key-policy ABE (kpABE) and unbounded ciphertext-policy ABE (cpABE) for MSP in a simple and modular way to obtain key-policy ABE for DFA. Our construction uses its building blocks in a symmetric way -- by swapping the use of the underlying kpABE and cpABE, we also obtain a construction of ciphertext-policy ABE for DFA. Our work extends techniques developed recently by Agrawal, Maitra and Yamada [Crypto 2019], which show how to construct ABE that support unbounded machines and unbounded inputs by combining ABE schemes that are bounded in one co-ordinate. At the heart of our work is the observation that unbounded, multi-use ABE for MSP already achieve most of what we need to build ABE for DFA.

Available format(s)
Public-key cryptography
Publication info
A minor revision of an IACR publication in TCC 2019
Attribute-based encryptiondeterministic finite automatadecisional linear assumption
Contact author(s)
shweta a @ gmail com
monosij maitra @ gmail com
yamada-shota @ aist go jp
2019-09-20: last of 4 revisions
2019-06-04: received
See all versions
Short URL
Creative Commons Attribution


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