Paper 2016/959

Impossibility of Simulation Secure Functional Encryption Even with Random Oracles

Shashank Agrawal, Venkata Koppula, and Brent Waters

Abstract

In this work we study the feasibility of achieving simulation security in functional encryption (FE) in the random oracle model. Our main result is negative in that we give a functionality for which it is impossible to achieve simulation security even with the aid of random oracles. We begin by giving a formal definition of simulation security that explicitly incorporates the random oracles. Next, we show a particular functionality for which it is impossible to achieve simulation security. Here messages are interpreted as seeds to a (weak) pseudorandom function family F and private keys are ascribed to points in the domain of the function. On a message s and private key x one can learn F(s,x). We show that there exists an attacker that makes a polynomial number of private key queries followed by a single ciphertext query for which there exists no simulator. Our functionality and attacker access pattern closely matches the standard model impossibility result of Agrawal, Gorbunov, Vaikuntanathan and Wee (CRYPTO 2013). The crux of their argument is that no simulator can succinctly program in the outputs of an unbounded number of evaluations of a pseudorandom function family into a bounded size ciphertext. However, their argument does not apply in the random oracle setting since the oracle acts as an additional conduit of information which the simulator can program. We overcome this barrier by proposing an attacker who decrypts the challenge ciphertext with the secret keys issued earlier without using the random oracle, even though the decryption algorithm may require it. This involves collecting most of the useful random oracle queries in advance, without giving the simulator too many opportunities to program. We note that our negative result contradicts a theorem of De Caro et al. (CRYPTO 2013) (as originally stated) which claims that random oracles can transform any indistinguishability secure functional encryption system into one that is simulation secure. De Caro et. al subsequently revised their work to show such a transformation from a new indistinguishability definition called functional encryption ”for circuits with random oracle gates”. An implication of our result when combined with theirs is that this new definition of functional encryption for circuits with random oracle gates is impossible to achieve even when all algorithms have access to a random oracle. On the flip side, we demonstrate the utility of the random oracle in simulation security. Given only public key encryption and low-depth PRGs we show how to build an FE system that is simulation secure for any poly-time attacker that makes an unbounded number of message queries, but an a-priori bounded number of key queries. This bests what is possible in the standard model where it is only feasible to achieve security for an attacker that is bounded both in the number of key and message queries it makes. We achieve this by creating a system that leverages the random oracle to get one-key security and then adapt previously known techniques to boost the system to resist up to q queries. Finally, we ask whether it is possible to achieve simulation security for an unbounded number of messages and keys, but where all key queries are made after the message queries. We show this too is impossible to achieve using a different twist on our first impossibility result.

Note: added a paragraph on alternate approach