Our work establishes a connection between these questions by giving a compiler that transforms any IND-secure FE scheme for general circuits into one that is SIM-secure for general circuits.
1) In the random oracle model, our resulting scheme is SIM-secure for an unbounded number of ciphertexts and key-derivation queries. We achieve this result by starting from an IND-secure FE scheme for general circuits with random oracle gates.
2) In the standard model, our resulting scheme is secure for a bounded number of ciphertexts and non-adaptive key-derivation queries (i.e., those made before seeing the challenge ciphertexts), but an unbounded number of adaptive key-derivation queries. These parameters match the known impossibility results for SIM-secure FE and improve upon the parameters achieved by Gorbunov et al. [CRYPTO'12].
The techniques for our compiler are inspired by constructions of non-committing encryption [Nielsen -- CRYPTO '02] and the celebrated Feige-Lapidot-Shamir paradigm [FOCS'90] for obtaining zero-knowledge proof systems from witness-indistinguishable proof systems.
Our compiler in the standard model requires an IND-secure FE scheme for general circuits, it leaves open the question of whether we can obtain SIM-secure FE for special cases of interest under weaker assumptions. To this end, we next show that our approach leads to a direct construction of SIM-secure hidden vector encryption (an important special case of FE that generalizes anonymous identity-based encryption). The scheme, which is set in composite order bilinear groups under subgroup decision assumptions, achieves security for a bounded number of ciphertexts but unbounded number of both non-adaptive and adaptive key-derivation queries, again matching the known impossibility results. In particular, to our knowledge this is the first construction of SIM-secure FE (for any non-trivial functionality) in the standard model handling an unbounded number of adaptive key-derivation queries.
Finally, we revisit the negative results for SIM-secure FE. We observe that the known results leave open the possibility of achieving SIM-security for various natural formulations of security (such as non-black-box simulation for non-adaptive adversaries). We settle these questions in the negative, thus providing essentially a full picture of the (un)achievability of SIM-security.Category / Keywords: Functional Encryption, Simulation-Based Security, Random Oracle Model Publication Info: this is an IACR version of a Crypto 2013 paper Date: received 9 Jun 2013, last revised 5 Dec 2016 Contact author: abhishek at cs jhu edu Available format(s): PDF | BibTeX Citation Note: This is the full version of the paper Version: 20161205:173116 (All versions of this report) Short URL: ia.cr/2013/364 Discussion forum: Show discussion | Start new discussion