Functional Encryption for Regular Languages

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 CT encrypts a message

m

and is associated with an

arbitrary length

string

w

. A user is able to decrypt the ciphertext CT 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 ℓ-Bilinear Diffie-Hellman Exponent (BDHE) assumption that we call the decision ℓ-Expanded BDHE problem.