Functional encryption for cascade automata

We introduce a Functional Encryption (FE) scheme for the class of languages accepted by extended automata. In an extended automaton, n Deterministic Finite Automata (DFA), each with at most q states, are linked in a cascade such that in each transition the i-th DFA performs its own transition and outputs an input symbol for DFA number i + 1 mod n. Our scheme encrypts a message m with a word w and the resulting ciphertext can be decrypted only by a key that is associated with an automaton that accepts w. Our scheme has key size O ( n q 2 ), while the ciphertext length and encryption and decryption times are O ( n | w | ). Our scheme is significantly more efficient than previous proposals, e. g. Waters (Crypto'12), for interesting applications of FE for regular languages such as accepting a word in a regular language only if it is accompanied by a standard public key signature on that word.

Authors

• Dan Brownstein
• Shlomi Dolev
• Niv Gilboa

Keywords

• Functional encryption