Paper 2013/090

Functional Encryption Supporting Recursive Languages

Somindu C. Ramanna and Palash Sarkar


We provide a construction for functional encryption over the set of recursive languages. In this scheme, a secret key $\sk_{\mathcal{M}}$ encodes a halting double-stack deterministic pushdown automaton (2DPDA) $\mathcal{M}$ that accepts by final state. Encryption algorithm takes a message $m$ and a string $w$ as input and outputs a ciphertext $\cipher$. A user possessing $\sk_{\mathcal{M}}$ can decrypt $\cipher$ only if $\mathcal{M}$ accepts $w$. Halting 2DPDAs can simulate halting deterministic Turing machines and hence our construction essentially covers all recursive languages. The construction is built upon Waters' bilinear pairing-based functional encryption scheme over regular languages. The main technical novelty is in handling stack contents and $\lambda$-transitions (i.e., transitions that do not advance the input pointer) of the automata. This is reflected both in the construction and the security arguments. The scheme is shown to be selectively secure based on the decision $\ell$-expanded bilinear Diffie-Hellman exponent assumption introduced by Waters.

Available format(s)
-- withdrawn --
Public-key cryptography
Publication info
Published elsewhere. Unknown where it was published
functional encryptionrecursive languagespushdown automata
Contact author(s)
somindu_r @ isical ac in
2013-03-20: withdrawn
2013-02-20: received
See all versions
Short URL
Creative Commons Attribution
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.