We propose a construction of Attribute-Based Encryption for deterministic finite automata with bounded input length from lattices. The security of our construction can be reduced to the hardness of learning with errors LWE problem in the selective security model.#R##N##R##N#The main technique in our scheme is a novel way to securely encode the deterministic finite automata and the input string as a "matrix ribbon" that closely mimics the structure of the tape and supports simple operations that rely only on traditional preimage sampling on lattices.#R##N##R##N#Our result is the first direct construction of key-policy attribute-based encryption for deterministic finite automata. Comparing with the existing indirect constructions from lattices, our scheme is conceptually simpler and also more efficient.
['Xavier Boyen', 'Qinyi Li']
Attribute-Based Encryption for Finite Automata from LWE