Paper 2013/752

On the Power of Rewinding Simulators in Functional Encryption

Angelo De Caro and Vincenzo Iovino

Abstract

In a seminal work, Boneh, Sahai and Waters (BSW, for short) [TCC’11] showed that for functional encryption the indistinguishability notion of security (IND-Security) is weaker than simulation-based security (SIM-Security), and that SIM-Security is in general impossible to achieve. This has opened up the door to a plethora of papers showing feasibility and new impossibility results. Nevertheless, the quest for better definitions that (1) overcome the limitations of IND-Security and (2) the impossibility result of BSW, is still open. In this work, we exploit efficient rewinding black-box simulators to argue security. We put forth a new SIM-Security notion that, though it is weaker than the previous ones, it is still sufficiently strong to not meet pathological schemes as it is the case for IND-Security (that is implied by the new definition). This is achieved by retaining a strong simulation-based flavour but adding more rewinding power to the simulator having care to guarantee that it can not learn more than what the adversary would learn in any run of the experiment. Surprisingly, our new definition, that we call rewinding simulation-based security (RSIM-Security), overcomes the BSW impossibility result. Moreover, we show that: (1) IND-Security is equivalent to RSIM-Security for Attribute-Based Encryption in the standard model. Previous results showed (unconditional) impossibility results in the standard model. (2) Notwithstanding, we show that for notable class of predicates (including Anonymous IBE, Inner-Product over Z2 and others), IND-Security is equivalent to RSIM-Security in the standard model. Previous results showed impossibility results for the standard model and the positive results were for the random oracle model or for more restricted settings. Our definition shares the same spirit of an independent work of Agrawal, Agrawal, Badri- narayanan, Kumarasubramanian, Prabhakaran and Sahai (EPRINT archive, 2013). We think that our work makes a significant step in providing an achievable simulation-based definition for important primitives like (Anonymous) IBE, and showing that for these primitives there are no pathological schemes, thus it is of great theoretical and practical relevance.

Note: Corrected a bug and added comparison to concurrent works