Paper 2013/364

On the Achievability of Simulation-Based Security for Functional Encryption

Angelo De Caro and Vincenzo Iovino Abhishek Jain and Adam O'Neill and Omer Paneth and Giuseppe Persiano

Abstract

Recently, there has been rapid progress in the area of functional encryption (FE), in which a receiver with secret-key Sk_y can compute from an encryption of x the value F(x,y) for some functionality F. Two central open questions that remain are: (1) Can we construct FE secure under an indistinguishability-based (IND) security notion for general circuits? (2) To what extent can we achieve a simulation-based (SIM) security notion for FE? Indeed, it was previously shown that IND-security for FE is too weak for some functionalities [Boneh et al. -- TCC'11, O'Neill -- ePrint '10], but that there exist strong impossibility results for SIM-security [Boneh et al. -- TCC'11, Agrawal et al. -- ePrint 2012]. 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.

Note: This is the full version of the paper