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 ou...

Full description

Saved in:
Bibliographic Details
Published in:Information and computation 2017-08, Vol.255, p.384-407
Main Authors: Brownstein, Dan, Dolev, Shlomi, Gilboa, Niv
Format: Article
Language:English
Subjects:
Functional encryption
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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+1modn. 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(nq2), 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.
ISSN:0890-5401
1090-2651
DOI:10.1016/j.ic.2016.12.005