Functional Encryption for Regular
Languages
Brent Waters (
Abstract:
We provide a functional encryption system that supports functionality for
regular languages. In our system a secret key is associated with a
Deterministic Finite Automata (DFA) $M$. A ciphertext
encrypts a message m and is associated with an arbitrary length string w. A
user is able to decrypt the ciphertext if and only
if the DFA M associated with his private key accepts the string w.
Compared with other known functional encryption systems, this is the first
system where the functionality is capable of recognizing an unbounded
language. For example, in (Key-Policy) Attribute-Based Encryption (ABE) a
private key SK is associated with a single boolean
formula which operates over a fixed number of boolean
variables from the ciphertext. In contrast, in our
system a DFA M will meaningfully operate over an arbitrary length input w.
We propose a system that utilizes bilinear groups. Our solution is a
"public index" system, where the message m is hidden, but the
string w is not. We prove security in the selective model under a variant of
the decision n-Bilinear Diffie-Hellman Exponent
(BDHE) assumption that we call the decision n-Expanded BDHE problem.