Functional Encryption for Regular Languages

Brent Waters

Paper 2012/384

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, 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 l-Bilinear Diffie-Hellman Exponent (BDHE) assumption that we call the decision l-Expanded BDHE problem.

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: Published elsewhere. Full version of CRYPTO 2012 paper
Keywords: Functional Encryption
Contact author(s): bwaters @ cs utexas edu
History: 2012-07-12: received
Short URL: https://ia.cr/2012/384
License: CC BY

BibTeX

@misc{cryptoeprint:2012/384,
      author = {Brent Waters},
      title = {Functional Encryption for Regular Languages},
      howpublished = {Cryptology ePrint Archive, Paper 2012/384},
      year = {2012},
      note = {\url{https://eprint.iacr.org/2012/384}},
      url = {https://eprint.iacr.org/2012/384}
}