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 known impossibility results, is still open. In this work, we explore the benefits and the limits of using efficient rewinding black-box simulators to argue security. To do so, we introduce a new simulation-based security definition, that we call rewinding simulation-based security (RSIM-Security), that is weaker than the previous ones but it is still sufficiently strong to not meet pathological schemes as it is the case for IND-Security (that is implied by the RSIM). 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. What we found is that for RSIM the BSW impossibility result does not hold and that IND-Security is equivalent to RSIM-Security for Attribute-Based Encryption in the standard model. Nevertheless, we prove that there is a setting where rewinding simulators are of no help. The adversary can put in place a strategy that forces the simulator to rewind continuously.

Note: In press

Metadata
Available format(s)
PDF
Publication info
Published elsewhere. Minor revision. Design, Codes and Cryptography
Keywords
Functional EncryptionSimulation-Based SecurityRewinding
Contact author(s)
vinciovino @ gmail com
History
2016-08-09: last of 9 revisions
2013-11-17: received
See all versions
Short URL
https://ia.cr/2013/752
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2013/752,
      author = {Angelo De Caro and Vincenzo Iovino},
      title = {On the Power of Rewinding Simulators in Functional Encryption},
      howpublished = {Cryptology ePrint Archive, Paper 2013/752},
      year = {2013},
      note = {\url{https://eprint.iacr.org/2013/752}},
      url = {https://eprint.iacr.org/2013/752}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.