Cryptology ePrint Archive: Report 2013/752

On the Power of Rewinding Simulators in Functional Encryption

Angelo De Caro and Vincenzo Iovino

Abstract: In the recent years, functional encryption (FE) has received a lot of attention due to its versatility and unique challenges it poses. In FE, a receiver with secret-key $sk_y$ can compute from an encryption of $x$ the value $F(y,x)$ for some functionality $F$. The seminal work of Boneh, Sahai and Waters [TCC'11] showed that for functional encryption the indistinguishability notion of security (IND-Security) is weaker then simulation-based and, moreover, showed that simulation-based security is impossible to achieve even in weaker settings. This has opened up the door to a plethora of papers, showing feasibility and new impossibility results, having in common the pursuit of a reasonable and achievable simulation-based security definition.

With the same aim, in this work, we propose a new simulation-based security definition that we call {\em rewinding simulation-based security} (RSIM-Security). Rewinding arguments have been used in all sorts of interactive protocols and have been shown to be highly useful to argue security. We exploit this power allowing the simulator to rewind the adversary under specific constraints. Specifically, the simulator will be able to rewind the adversary an arbitrary number of times under the constraint that the simulator does not learn more information about the challenge messages than the adversary. Notice that, we still restrict the simulator to be {\em efficient}. Under our new definition we show that:

(1) IND-Security is equivalent to RSIM-Security for {\em predicate encryption with public-index} (i.e. Attribute-Based Encryption) in the {\em standard model}. Previous results showed impossibility results in the standard model.

This {\em equivalence} is the best one can hope for general functionalities due to the counterexample of Boneh \etal.

(2) Notwithstanding, we show that for specific (private-index) functionalities (e.g., Anonymous IBE, inner-product over $\Z_2$, any family of circuits in $\NC_0$, and monotone conjunctive Boolean formulae) IND-Security is equivalent to RSIM-Security in the standard model. Previous results showed impossibility results in the standard model and the positive results were set either in the random oracle or in more restricted security definitions.

(3) On the negative side, we show that our security definition cannot be achieved by functional encryption schemes for general functionalities (specifically, functionalities that compute a pseudo-random function) in the adaptive setting. The argument we use is to some extent the {\em dual} of that used by Agrawal, Gorbunov, Vaikuntanathan, and Wee [CRYPTO'13] in the non-adaptive setting.

(4) We complete the picture showing the achievability of unbounded simulation (USIM) answering positively to a question posed by Agrawal, Gorbunov, Vaikuntanathan and Wee [CRYPTO 2013].

Category / Keywords: public-key cryptography, functional encryption

Date: received 14 Nov 2013, last revised 17 Nov 2013

Contact author: iovino at dia unisa it

Available format(s): PDF | BibTeX Citation

Version: 20131118:064556 (All versions of this report)

Discussion forum: Show discussion | Start new discussion


[ Cryptology ePrint archive ]