In this work, we make progress in this direction by presenting a reduction from iO to a natural form of public-key functional encryption (FE). Specifically, we construct iO for general functions from any single-key FE scheme for NC1 that achieves selective, indistinguishability security against sub-exponential time adversaries. Further, the FE scheme should be compact, namely, the running time of the encryption algorithm must only be a polynomial in the security parameter and the input message length (and not in the function description size or its output length).
We achieve this result by developing a novel arity amplification technique to transform FE for single-ary functions into FE for multi-ary functions (aka multi-input FE). Instantiating our approach with known, non-compact FE schemes, we obtain the first constructions of multi-input FE for constant-ary functions based on standard assumptions.
Finally, as a result of independent interest, we construct a compact FE scheme from randomized encodings for Turing machines and learning with errors assumption.Category / Keywords: foundations / program obfuscation, functional encryption Date: received 27 Feb 2015, last revised 2 Sep 2015 Contact author: prabhanjan va at gmail com, abhishek@cs jhu edu Available format(s): PDF | BibTeX Citation Version: 20150902:225248 (All versions of this report) Short URL: ia.cr/2015/173 Discussion forum: Show discussion | Start new discussion