IACR News item: 20 February 2013
Somindu C. Ramanna, Palash Sarkar
ePrint ReportIn 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.
Additional news items may be found on the IACR news page.