Cryptology ePrint Archive: Report 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.

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