On the Power of Rewinding Simulators in Functional Encryption.
Angelo De, Vincenzo Iovino · 2013
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 sky can com-pute 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 indistin-guishability 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 re-sults, 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 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