International Association
for Cryptologic Research

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.

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 notable classes of predicates (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].