Impossibility of Simulation Secure Functional Encryption Even with Random Oracles

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 fixed 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.

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.

B. Waters—Supported by NSF CNS-1414082, DARPA SafeWare, Microsoft Faculty Fellowship, and Packard Foundation Fellowship.

1 Introduction

The traditional notion of public key encryption systems provide “all or nothing” semantics regarding encrypted data. In such a system a message m is encrypted under a public key, ${\mathsf {pk}}$, to produce a ciphertext ${\mathsf {ct}}$. A user that holds the corresponding secret key can decrypt ${\mathsf {ct}}$ and learn the entire message m, while any other user will not learn anything about the contents of the message. The work of Sahai and Waters [32] conceived cryptosystems that moved beyond these limited semantics to ones where a private key would give a select view of encrypted data. These efforts [13, 25, 32] cumulated in the concept of functional encryption. In a functional encryption system an authority will generate a pair of a public key and master key pair $({\mathsf {pk}},{\mathsf {msk}})$. Any user can encrypt a ciphertext ${\mathsf {ct}}$ using the public key, while the authority can use the master secret key ${\mathsf {msk}}$ to generate a secret key ${\mathsf {sk}}_f$ that is tied to the functionality f. A holder of ${\mathsf {sk}}_f$ can use it to decrypt a ciphertext ${\mathsf {ct}}$, but instead of learning the message m, the decryptor’s decryption will instead output f(m).

One challenge in defining and designing functional encryption (FE) systems is in finding a definition to capture security. The earliest formal definitions of functional encryption [13, 25] (back when the terminology of “predicate encryption” was used) defined security in terms of an indistinguishability game. Briefly, a system is indistinguishability secure if no poly-time attacker that receives secret keys for functions $f_1, \ldots , f_Q$ can distinguish between encryptions of $m_0, m_1$ so long as $f_i(m_0) = f_i(m_1)$ for $i = 1, \ldots , Q$.

Subsequent works [2, 5, 12, 29] aimed to capture various notions of simulation-based security. To achieve simulation one must be able to show that for each attacker there exists a poly-time simulator ${\mathcal {S}}$ that can produce a transcript that emulates the attacker’s real world view, but when only given access to what the evaluation of the secret key functions $f(\cdot )$ were on the attacker’s messages. (We will return to describing simulation-based security in more detail shortly.) While these simulation definitions had the appeal of perhaps capturing a stronger notion of security than the indistinguishability-based ones, they were limited in that multiple works [2, 5, 12, 22, 29] showed that this notion is impossible to achieve in the standard model for even very basic functionalities such as identity-based encryption [11, 33]. The only exception being in the restricted case where the attacker is only allowed to access an a-priori bounded number of secret keys [20].

While these results essentially put a hard stop on realizing (collusion-resistant) simulation security in the standard model, the door to leveraging the random oracle model [6] still remained wide open. Notably, Boneh, Sahai and Waters [12] building on techniques from non-committing encryption [28] showed that the random oracle could be leveraged to turn any indistinguishability secure public index FE scheme into one that was simulation secure. Recall that a public index scheme is one where an encrypted message is split into a hidden payload and a non-hidden index and the secret key operates only on the index. The set of such schemes includes identity-based encryption [11, 33] and attribute-based encryption [32]. Thus, they showed that introducing a random oracle was enough to circumvent their own standard model IBE result. In this work we wish to understand what are the possibilities and limitations (if any) for using random oracles to achieve simulation security in FE systems. Our work begins with the question:

$$\begin{aligned} \begin{array}{cl} &{} Is~ it~ possible~ to~ achieve~ simulation~ secure~ functional~encryption \\ &{} \qquad \quad \quad ~ for~ any~ functionality~ in~ the~ random ~oracle ~model? \end{array} \end{aligned}$$

Our main result is to show that there exist functionalities for which there cannot exist a simulation secure functional encryption system even in the random oracle model.

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 beats 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 by repurposing our main impossibility result to the new setting.

1.1 Our Main Impossibility Result

We show the impossibility result for the case where messages are interpreted as keys or seeds to a (weak) Pseudo Random Function (PRF) [18] family and secret keys are points in the domain of the PRF. Agrawal, Gorbunov, Vaikuntanathan and Wee [2] showed that such a functionality could not be simulation secure in the standard model. Here we show that this limitation holds even with the introduction of random oracles.

We begin our exposition by describing the definition of simulation security in a little more depth and briefly overviewing the AGVW impossibility analysis.

Simulation Security. Simulation security for FE is defined by means of real and ideal experiments. In the real experiment, an adversary ${\mathcal {A}}$ gets secret keys for functions f and ciphertexts for challenge messages m of its choice. The secret key queries can either be sent before the challenge messages (also referred to as pre-challenge queries) or after the challenge messages (post challenge queries). In the ideal world, on the other hand, a simulator ${\mathcal {S}}$ needs to generate challenge ciphertexts and keys given only the minimal information. In particular, when ${\mathcal {A}}$ requests that a challenge message m be encrypted, ${\mathcal {S}}$ only gets f(m) on all the pre-challenge functions f queried by ${\mathcal {A}}$ (instead of m itself), and must generate a ciphertext that ${\mathcal {A}}$ cannot distinguish from the one in the real world. Similarly, when ${\mathcal {A}}$ makes a post-challenge key query for $f'$, ${\mathcal {S}}$ must generate a secret key given just $f'$, $f'(m)$ for all challenge messages m.

An FE scheme is $({q_{{\mathsf {pre}}}}, {q_{{\mathsf {chal}}}}, {q_{{\mathsf {post}}}})$-simulation secure if it can withstand adversaries that make at most ${q_{{\mathsf {pre}}}}$ pre-challenge key queries, ${q_{{\mathsf {chal}}}}$ challenge encryption requests, and ${q_{{\mathsf {post}}}}$ post-challenge key queries. Ideally, one would like to capture all polynomial-time adversaries, who can make any number of queries they want. However, even simple functionalities like identity-based encryption do not have a scheme secure against an arbitrary number of encryption requests followed by one key query, i.e., IBE does not have a $(0, {\mathsf {poly}}, 1)$-simulation secure scheme [5, 12] in the standard model. Here ${\mathsf {poly}}$ denotes that any number of encryption requests can be made, as long as there is a polynomial bound on them.

AGVW Impossibility. A different kind of impossibility was shown by Agrawal et al. [2]. They interpret messages as seeds to a weak pseudorandom family ${\mathsf {wPRF}}$¹ and secret keys as points in the domain of the family. When a ciphertext for s is decrypted with a secret key for x, the output is ${\mathsf {wPRF}}(s, x)$. They show that there does not exist a simulation-secure FE scheme for this family that can tolerate adversaries which can make an arbitrary number of pre-challenge key queries and then request for the encryption of just one message (i.e., (${\mathsf {poly}}, 1, 0$)-simulation security). Intuitively, when the adversary outputs a message s in the ideal world, the simulator gets ${\mathsf {wPRF}}(s,x_1), \ldots , {\mathsf {wPRF}}(s,x_q)$ (if q is the number of post-challenge key queries), which is computationally indistinguishable from q uniformly random strings. The simulator must output a ciphertext ${\mathsf {ct}}$ now that decrypts correctly with all the keys issued before. Note that when the keys were issued, simulator had no information about s, so it must somehow compress q random strings into ${\mathsf {ct}}$. However, as Agrawal et al. show, the output of a pseudo-random function family is incompressible. Thus, by choosing a large enough q, they arrive at the impossibility result.

Random Oracle Model. In the random oracle model though, Agrawal et al.’s impossibility argument breaks down. Informally speaking, the random oracle acts as an additional conduit of information which the simulator can program even after ${\mathsf {ct}}$ appears. For instance, if the decryption algorithm makes RO queries, then the simulator could program such queries when adversary tries to decrypt ${\mathsf {ct}}$ with the secret keys issued earlier. Indeed, Boneh et al. show that their $(0, {\mathsf {poly}}, 1)$ impossibility for IBE can be circumvented by employing RO in the encryption and decryption algorithms.

Thus we need a very different approach. We would like to build an adversary ${\mathcal {A}}^\star$ that “cuts off” RO in the decryption process, and is able to work without it. This involves a delicate balancing act between cutting off too early and too late. In one extreme case, if ${\mathcal {A}}^\star$ does not invoke RO at all and makes up its own responses, then these would not match with the actual RO responses in encryption and key generation. Thus decryption would always fail in both the real and ideal worlds, and there will be no distinction between them. On the other extreme, if ${\mathcal {A}}^\star$ just used the RO all the way through, it would provide the simulator enough opportunity to program in the desired information. (As a result, we will not be able to use the incompressibility of ${\mathsf {wPRF}}$.)

At a high level, our approach is similar to the Impagliazzo-Rudich “heavy-query” algorithm [23]. First, there is an initial learning phase where ${\mathcal {A}}^\star$ will build a list of “high frequency” random oracle queries and responses associated with each secret key and the challenge ciphertext. Later the attacker will be able to use this list to replace the use of the actual random oracle during decryption. If some query is not found in the list, then ${\mathcal {A}}^\star$ will choose a random value for it on its own. Informally, we get the following result:

Theorem 1

(Main Theorem, informal). There does not exist a $({\mathsf {poly}}, 1, 0)$-simulation secure FE scheme for the class of (weak) pseudo-random functions in the random oracle model.

Related Work. This bears a resemblance to the work of Canetti, Kalai and Paneth [15] who show impossibility of VBB obfuscation even with ROs. In their case they show that any obfuscated program that uses the RO can be translated into one that does not need it. They do this by collecting the frequently used RO queries and bundling this with the core obfuscated code. On one hand, these queries do not give any information about the program, but on the other, result in an obfuscation that is only approximately correct. Such imperfect correctness, however, is enough to invoke the impossibility of Bitansky and Paneth [9].

One might ask if we can show whether RO can be dispensed with in any simulation secure FE in a similar way. If we could establish this, then prior impossibility results [2, 5, 12] would imply RO impossibility as well. The answer to this is negative as we recall that Boneh, Sahai and Waters [12] showed specific functionalities that were impossible to simulate in the standard model, but possible to be simulation secure using random oracle. Therefore we cannot always remove the random oracle and must develop a more nuanced approach: we need to build a specific adversary for which simulation does not work.

In a recent work [27], Mahmoody et al. show that there is no fully black-box construction of indistinguishability obfuscation (iO) from any primitive implied by a random oracle in a black-box way. In light of recent FE to iO transformations [3, 10], one might wonder if this rules out FE schemes in the RO model. However, these transformations are non-black box.

High Level Description of Impossibility. Recall that we want to design an adversary ${\mathcal {A}}^\star$ that will build a list of “high frequency” random oracle queries and responses associated with each secret key and the challenge ciphertext. It will use this list later in the decryption phase to “cut-off” the random oracle at an appropriate time.

${\mathcal {A}}^\star$ starts off by querying the key-generation oracle at random points $x_1, \ldots , x_q$ in the domain of ${\mathsf {wPRF}}$, and gets ${\mathsf {sk}}_1, \ldots , {\mathsf {sk}}_q$ in return. The RO queries made by the key-generation oracle are hidden from the adversary, so ${\mathcal {A}}^\star$ tries to find them by encrypting several randomly chosen seeds using the master public key, and then decrypting them with ${\mathsf {sk}}_1, \ldots , {\mathsf {sk}}_q$.² The RO queries made during the decryption process are recorded in a list $\varGamma$. The hope is that $\varGamma$ will capture the RO queries that were made in generating a key ${\mathsf {sk}}_i$.

Note that one cannot hope to capture all RO queries required for decryption: Suppose a polynomial number Y of high frequency queries associated with ${\mathsf {sk}}_i$ is collected, but there is an RO call that is made during key-generation which is used during 1/2Y fraction of the decryptions. Then it will be the case that with some non-negligible probability, $\varGamma$ will fail to aid in the decryption of the challenge ciphertext with ${\mathsf {sk}}_i$. Instead of trying to solve this issue, we make our analysis work with a decryption that might fail some of the time. For this purpose, we extend the incompressibility argument of Agrawal et al. to work even for approximate compression.

We are not quite done yet. Even though we have captured most of the hidden RO queries involved in key-generation that are also needed for decryption, we still need to capture those that are involved in the encryption of the challenge message, as they are also hidden and may be required during decryption.³ Suppose ${\mathcal {A}}^\star$ outputs a randomly chosen seed $s^\star$ as the challenge message, and gets ${\mathsf {ct}}^\star$ in return. In order to find out RO queries associated with ${\mathsf {ct}}^\star$, ${\mathcal {A}}^\star$ cannot generate secret keys on its own (like in the pre-challenge phase when it generated ciphertexts); it must make-do with the secret keys ${\mathsf {sk}}_1, \ldots , {\mathsf {sk}}_q$ that were issued earlier. Thus, the idea is to decrypt ${\mathsf {ct}}^\star$ with some fraction $\delta$ of the keys using RO, recording the queries in the list $\varGamma$. It then cuts off the random oracle, and decrypts ${\mathsf {ct}}^\star$ with the remaining keys using the list $\varGamma$. If a query is not found in $\varGamma$, then a random value is used for it (as well as recorded in $\varGamma$ for consistent responses in future). The adversary outputs 1 if a large fraction of these decryptions are correct; that is, if the decryption of ${\mathsf {ct}}^{\star }$ using ${\mathsf {sk}}_i$ outputs ${\mathsf {wPRF}}(s^{\star }, x_i)$.

In the real world, as we will see, the adversary outputs 1 with noticeable probability. On the other hand, we show that in the ideal world, the adversary outputs 1 only with negligible probability. For the adversary to output 1 in the ideal world, the simulator needs to somehow program the ciphertext and the post-challenge random oracle queries so that a large number of decryptions succeed. The only opportunity a simulator has of programming post-challenge RO responses is when $\delta$ fraction of the keys are used for decrypting ${\mathsf {ct}}^\star$. By choosing $\delta$ appropriately, we can ensure that the simulator is not able to program the RO queries to the extent that most of the remaining decryptions succeed.

Looking Back. A simulator’s success in the RO model depends on when it comes to know what to program and how much can it program. When dealing with the attacker ${\mathcal {A}}^\star$ described above, it gets a large amount of information, ${\mathsf {wPRF}}(s^\star , x_1), \ldots , {\mathsf {wPRF}}(s^\star , x_q)$, only in the challenge phase. Since all the key queries come before that, programming the secret keys is ruled out. If there was no random oracle, then the only possible avenue to program is the challenge ciphertext, but AGVW shows that it is not possible to compress so much information into a small ciphertext. Now with the random oracle, it might have been possible to program this information if there were many RO queries after the challenge phase. However, our adversary makes only a bounded number of post-challenge RO queries, and as a result, it is not possible to program all of $\left\{ {\mathsf {wPRF}}(s^\star , x_i)\right\}$ in these RO responses.

An Alternative Approach to Proving Impossibility. Concurrent to our work, Bitansky, Lin and Paneth [7] showed an alternate approach for removing random oracles. Unlike our current impossibility, their approach requires multiple ciphertexts. We sketch the main ideas here.

This approach uses a notion of obfuscation called ‘exponentially-efficient obfuscation’, introduced by Lin et al. [26]. An exponentially-efficient obfuscator is allowed to run in subexponential time, and the obfuscated program is also allowed to be subexponential in the input length. For security, Lin et al. considered the $i{\mathcal {O}}$ equivalent, where the obfuscation of two functionally identical programs should be computationally indistinguishable. However, one can even consider simulation based notions where the output of the obfuscator can be simulated by a simulator having only black box access to the program.

In a recent work, Bitansky et al. [8] showed that IND-secure functional encryption can be used to construct exponentially-efficient indistinguishability obfuscation [26] in a black-box manner. While there exist other transformations from FE to obfuscation [3, 10], the BNPW transformation is the only known black-box transformation, and this is important when studying FE or obfuscation in the random oracle model. Using the BNPW transformation, one can argue that simulation secure FE in the random oracle model implies simulation-secure exponentially-efficient obfuscation in the random oracle model. Therefore, to rule out FE in the random oracle model, it suffices to show that there exist certain functionalities for which we cannot obtain simulation-secure exponentially-efficient obfuscation in the random oracle model.

This can be achieved using the techniques of Canetti et al. [15], who showed an impossibility result for VBB obfuscation in the random oracle model. Canetti et al. showed that if there exists a VBB obfuscator in the random oracle model, then there exists an ‘approximate’ VBB obfuscator in the standard model. A similar argument can be used to show that if there exists simulation-secure exponentially efficient obfuscation in the random oracle model, then there exists approximately correct simulation-secure exponentially-efficient obfuscator in the standard model.

Finally, one needs to show that it is impossible to construct approximately correct simulation-secure exponentially-efficient obfuscators for certain function classes. This argument is similar to the incompressibility argument that we use. Let C be a circuit that performs PRF evaluation, and consider the obfuscation of C. A simulator must output an obfuscation given only black box access to the PRF function, which in turn is indistinguishable from a truly random function. Therefore, the simulator must output a subexponential sized string that approximately explains a truly random function, which is impossible.

1.2 A New Possibility Result in the Random Oracle Model

Now that we know that simulation security is impossible for unbounded queries even in the random oracle model, we turn to asking whether this model can be leveraged to support simulation security in any situations where it is impossible in the standard model. We already have one such example from the work of Boneh et al. [12] which gives both a standard model impossibility and a random oracle feasibility result for public index schemes. Thus, we are interested in new examples that go beyond the public index class. In this paper, we show the following possibility result:

Theorem 2

(Possibility, informal). There exists a simulation secure FE scheme for the class of all polynomial-depth circuits in the random oracle model secure against any poly-time attacker who makes an unbounded number of messages queries, but an a-priori bounded number of key queries, based on semantically-secure public-key encryption and pseudo-random generators computable by low-depth circuits.

Recall that such a security notion cannot be achieved even for the simple functionality of IBE in the standard model [12].

One-Bounded FE. Our starting point is a one-bounded simulation-secure FE scheme for all circuits, i.e., a scheme where the attacker can only make one key query, based just on the semantic security of public-key encryption. Our scheme is a variant of the Sahai-Seyalioglu [31]. Let ${\mathcal {C}}$ be a family of circuits wherein each circuit can be represented using t bits. Suppose $U_x$ is a universal circuit that takes a $C \in {\mathcal {C}}$ as input, and outputs C(x). The set-up algorithm of our FE scheme generates 2t key pairs of a semantically-secure public-key encryption scheme. The 2t public keys $({\mathsf {pk}}_{1, 0}, {\mathsf {pk}}_{1, 1}), \ldots , ({\mathsf {pk}}_{t, 0}, {\mathsf {pk}}_{t, 1})$ form the master public key, and the 2t private keys $({\mathsf {sk}}_{1, 0}, {\mathsf {sk}}_{1, 1}) \ldots , ({\mathsf {sk}}_{t, 0}, {\mathsf {sk}}_{t, 1})$ are kept secret. In order to encrypt a message x, a garbled circuit for $U_x$ is generated. Suppose $w_{i, b}$ for $i = 1, \ldots , t$ and $b = 0, 1$ are the wire-labels of $U_x$ for its t input bits. Then the $(i, b)^{th}$ component of the ciphertext consists of two parts: an encryption of a random value $r_{i, b}$ under ${\mathsf {pk}}_{i, b}$, and $w_{i, b}$ blinded with the hash of $r_{i, b}$. The key for a circuit C represented using bits $\beta _1, \ldots , \beta _t$ is simply the private keys corresponding to those bits, i.e., ${\mathsf {sk}}_{\beta _1}, \ldots , {\mathsf {sk}}_{\beta _t}$.

It is easy to see that the one-bounded FE scheme is correct. Specifically, the secret key for C will allow one to recover $r_{i, \beta _i}$ for $i = 1, \ldots , t$. Then by running the hash function on these values, the $w_{i, \beta _i}$ can be unblinded and used to evaluate the garbled circuit.

Let us now see how a simulator ${\mathcal {S}}$ can generate ciphertexts and a key from the right distribution in the ideal world. If the only allowed key query is made before the challenge phase for a circuit C, then ${\mathcal {S}}$ just runs the normal key generation algorithm, and later when adversary outputs a challenge message $x^\star$, it can generate a garbled circuit using just $C(x^\star )$.⁴ When the adversary’s key query is after the challenge message, however, ${\mathcal {S}}$ does not get any information in the challenge phase. In particular, it does not know which universal circuit to garble. Here the random oracle allows the simulator to defer making a decision until after the key query is made. It can set the second part of the (i, b)th ciphertext component to be a random number $z_{i, b}$ because, intuitively, adversary does not know $r_{i, b}$ (it is encrypted) so a hash of it is completely random. When adversary queries with a circuit C afterwards, simulator can program the random oracle’s response on $r_{i, b}$ to be $z_{i, b} \oplus w_{i, b}$, so that decryption works out properly.

Bounded Collusion FE. Using the one-bounded scheme in a black-box way, we can design an FE scheme secure against any a-priori bounded collusions for the class $\textsf {NC1}$, using Gorbunov et al.’s [20] transformation. While their transformation was proved secure for only one challenge message, we show that the same ideas also work for unbounded number of challenge messages. If the underlying one-bounded scheme is secure against any number of challenge messages, then so is the scheme obtained after applying their transformation.

Related Work. Sahai and Seyalioglu [31] were the first to use randomized encodings to design an FE system. Their scheme can issue one key non-adaptively for any function. Our one-bounded scheme can be seen as an extension of theirs to additionally support post-challenge key query. The random oracle allows a simulator to not commit to any value in the ciphertext until the function evaluation is made available.

Goldwasser et al. [19] also designed an FE system that can issue one pre-challenge key. Their scheme has succinct ciphertexts (independent of circuit size) but security is proved under stronger assumptions.

Iovino and Zebroski [24] present two results on simulation-secure FE in the public-key setting. First, they have a construction for a bounded number of challenge ciphertexts and pre-challenge key queries (and unbounded post-challenge queries), where key size grows with number of challenge ciphertexts but the ciphertext size is constant. The encryption/decryption time grows with the number of pre-challenge key queries. The second construction is for bounded key queries and challenge ciphertexts, but with constant size keys and ciphertexts. Here the encryption/decryption times depend on the bound on number of key queries and challenge ciphertexts. Both these results use extractability obfuscation. Our positive result presents a construction where the number of challenge ciphertexts is unbounded, but key queries are bounded. Therefore, our positive result and the results of Iovino and Zebroski are incomparable. Moreover, our construction only requires PKE and low-depth PRGs, whereas their constructions require stronger assumptions.

1.3 Another Impossibility Result

A natural question to ask is whether we can construct a simulation secure FE scheme in the random oracle model that can handle unbounded ciphertext queries, followed by an unbounded number of post-challenge key queries. We show that this is also impossible, assuming the existence of weak pseudorandom functions.

Theorem 3

There does not exist a $(0, {\mathsf {poly}}, {\mathsf {poly}})$-simulation secure FE scheme for the class of (weak) pseudo-random functions in the random oracle model.

Once again we interpret messages as seeds to a weak PRF family ${\mathsf {wPRF}}$ and secret keys as points in the domain of the PRF. A very different way to attack an FE scheme is needed though because no key query can be made before the challenge phase.

The new attacker ${\mathcal {A}}^\star$ starts off by outputting randomly chosen seeds $s_1, \ldots , s_k$ for ${\mathsf {wPRF}}$, and gets ciphertexts ${\mathsf {ct}}_1, \ldots , {\mathsf {ct}}_k$ in return. The RO queries made in the encryption process are hidden from ${\mathcal {A}}^\star$, and it might need some of them later during decryption. So, it requests secret keys for randomly chosen points $x_1, \ldots , x_q$, and gets ${\mathsf {sk}}_1, \ldots , {\mathsf {sk}}_q$ in return. Then it decrypts every ${\mathsf {ct}}_i$ with ${\mathsf {sk}}_j$ and records the RO queries made in a list $\varGamma$. An important point to note here is that the simulator gets some information about the seeds chosen earlier when key-queries are made. Specifically, it gets ${\mathsf {wPRF}}(s_1, x_j), \ldots , {\mathsf {wPRF}}(s_k, x_j)$ when $x_j$ is the query.

${\mathcal {A}}^\star$ now picks a random point $x^*$ and requests a secret key for it. The goal is to use the key obtained, say ${\mathsf {sk}}^*$, to decrypt the challenge ciphertexts ${\mathsf {ct}}_1, \ldots , {\mathsf {ct}}_k$ later. But, in order to do so, ${\mathcal {A}}^\star$ also needs to find out the RO queries made during key-generation that may also be required for decryption. To solve this problem, we use the same idea as in the previous impossibility result: encrypt some random seeds on your own and decrypt them with ${\mathsf {sk}}^*$, while adding the RO queries made to $\varGamma$.

Finally, ${\mathcal {A}}^\star$ decrypts ${\mathsf {ct}}_1, \ldots , {\mathsf {ct}}_k$ with ${\mathsf {sk}}^*$ without invoking the random oracle, using the list $\varGamma$ instead. In the real world, at least a constant fraction of the decryptions succeed. The analysis is similar to that of the previous impossibility result, but with the role of ciphertext and key reversed. The ideal world analysis, on the other hand, need more care because of two reasons. First, as pointed out earlier, some information about the seeds $s_1, \ldots , s_k$ is leaked when post-challenge key queries are made. Second, the simulator needs to compress the evaluation of ${\mathsf {wPRF}}$ on seeds $s_1, \ldots , s_k$ and a common point $x^*$, instead of one seed and multiple points as in the $({\mathsf {poly}}, \mathsf {1}, \mathsf {0})$ impossibility. At the same time, however, the only opportunity a simulator has of programming RO responses after learning ${\mathsf {wPRF}}(s_1, x^*), \ldots , {\mathsf {wPRF}}(s_k, x^*)$ is when ciphertexts for random seeds are decrypted with ${\mathsf {sk}}^*$ with the help of RO. So, it is conceivable that one can exploit the security of ${\mathsf {wPRF}}$ to argue that it is impossible to compress ${\mathsf {wPRF}}(s_1, x^*), \ldots , {\mathsf {wPRF}}(s_k, x^*)$ into a small key and a small number of RO responses. We show that this is indeed the case in the full version [1].

1.4 Relation to De Caro et al. and Functional Encryption for Circuits with Random Oracle Gates

At the time of the initial posting of our work, De Caro et al. [16] stated (Theorem 3) that indistinguishability security for FE schemes in the random oracle model implied simulation security, resulting in an apparent discrepancy with our results. After our work was posted we contacted the authors to point out this dissonance. The authors informed us that they had earlier become aware of an issue with the theorem statement, but had not yet prepared an update to their posting. They stated that they intended to update it to a statement that indistinguishability-based definition of “functional encryption for circuits with random oracle gates” implied simulation security.

At the time, the notion of functional encryption for circuits with random oracle gates had not previously appeared in the literature and we were unable to deduce the intended definition from the phrase. Subsequently, the authors provided a revision which defined the concept and provided a transformation in the random oracle model which showed this new notion implies (regular) simulation security [17]. However, since our work shows such a notion is impossible to achieve, this must imply that this indistinguishability notion of “functional encryption for circuits with random oracle gates” was impossible to realize to begin with.

Despite sharing the term random oracle the new concept proposed in their revision is quite different than how the random oracle model was proposed [6]. Recall, that a cryptographic system built in the random oracle model will have the same algorithms and definitions as the standard model counterpart with the exception that each algorithm is allowed oracle access to a random function. We emphasize that the random oracle model in of itself is not impossible, it is just simply a different model.⁵ Prior works would typically first establish provable security in the random oracle model and then apply the heuristic of replacing the random oracle calls with those to a hash function. It is this last step where security can actually be lost; in some cases no matter what the hash function is [14]. The concept of IND-FE in the random oracle model is not impossible to achieve (as far as we know), but we show that it is still insufficient to get simulation security. This impossibility holds for the random oracle model itself and is completely independent of the hash function replacement heuristic.

In the concept of functional encryption with random oracle gates as defined in the revision of [17] the random oracle is not just used as a tool to help augment functional encryption, but actually incorporated into a definition of functional encryption as the descriptions of a functionality f will depend on the random oracle. (Due to space limitations we refer the reader to [17] for a detailed description of the new definition.) As a simple argument will show, this new indistinguishability notion, unlike standard FE in the random oracle model, is impossible to begin with. So the addition of random oracle gates to FE circuits moves one to a primitive that is unachievable.

The combination of our simulation impossibility results with the implications from [17] imply this new notion of indistinguishability FE with random oracle gates is impossible to achieve. However, there is a much simpler and direct argument, which we provide in the full version of our paper [1].

1.5 Interpreting Our Impossibility Results

Impossibility results for simulation secure functional encryption in the standard model were already known before our work. If we take any FE system secure in the Random Oracle Model and then take the heuristic of replacing the oracle calls with some hash function family, then we have a standard model FE scheme. We know this new system to be impossible to be simulation secure from prior work. So a natural question to ask is what new interpretations does our result provide. We believe there are two main points here.

First, an interpretation of our result is understanding FE in idealized models. While the random oracle model is closely associated with the random oracle heuristic (i.e. replacing oracle calls with hash functions), there are different possible ways to try to “instantiate” a cryptosystem described in the random oracle model. One possibility is to replace calls to the random oracle with secure hardware tokens. Another could be a use of a blockchain.

In addition, in the interest of getting a better and deeper scientific understanding it is useful to map out cryptography in both the standard and random oracle models. There has been precedent for this in our community. For example, the Boneh et al. [12] paper which gave some examples of schemes (simulation secure FE schemes where the adversary sends unbounded challenge messages, followed by one key query) that were possible in the random oracle model, but impossible otherwise. Going further out, to best understand non-committing encryption it is useful to know both that it is impossible in the standard model and that it is possible in the RO model.

Secondly, we also posit that there may be some forms of security that lie in between simulation security and indistinguishability security, but that are hard for us to understand or formally define. Suppose there did exist an FE scheme that was simulation secure in the RO model, and one did apply the random oracle heuristic to it. It is possible that even if this new scheme is not simulation secure, the transformation could result in some gain of security. Perhaps this gain in security might even be what is right or needed for a particular application. One example is that while the Fiat-Shamir heuristic applied to zero knowledge protocol does not give a simulation secure NIZK, but might give the right form of security needed for a particular application (e.g. its use in some cryptocurrency).

2 Preliminaries

We use $\lambda$ to denote the security parameter. Let [n] denote the set $\left\{ 1, 2, \ldots , n\right\}$. If A is an algorithm, then $a \leftarrow A(\cdot )$ or $A(\cdot ) \rightarrow a$ denote that a is the output of running A on the specified inputs. If ${\mathcal {D}}$ is a distribution, then $s \leftarrow {\mathcal {D}}$ denotes that s is a sample drawn according to it. Also, $x {\mathop {\leftarrow }\limits ^{{\mathrm{R}}}}X$ denotes drawing a value x uniformly at random from the set X.

For two distribution ensembles ${\mathcal {X}}= \left\{ {\mathcal {X}}_\lambda \right\} _{\lambda \in {\mathbb {N}}}$ and ${\mathcal {Y}}= \left\{ {\mathcal {Y}}_\lambda \right\} _{\lambda \in {\mathbb {N}}}$, we use ${\mathcal {X}}{\mathop {\approx }\limits ^{{\mathrm{c}}}}{\mathcal {Y}}$ to denote that ${\mathcal {X}}$ is computationally indistinguishable from ${\mathcal {Y}}$. Lastly, for two vectors $u = (u_1, \ldots , u_n)$ and $v = (v_1, \ldots , v_n)$, their Hamming distance ${\mathsf {HD}}(u, v)$ is defined to be the number of points where they don’t match, i.e., the size of set $\left\{ i \in [n] \, | \, u_i \ne v_i\right\}$.

2.1 Weak Pseudo-Random Functions

Our impossibility results rely on the existence of circuit families whose output cannot be compressed by a significant amount. In Sect. 4, we will show that a specific circuit family built from pseudo-random functions (PRFs) is not compressible. In fact, like Gorbunov et al. [20], a weaker type of PRF where adversary only gets evaluation at random points suffices for our purpose.

Definition 1

(Weak PRFs). Let n, m, p be polynomials in $\lambda$. Let ${\mathsf {wPRF}}= \{{\mathsf {wPRF}}_\lambda \}_{\lambda \in {\mathbb {N}}}$ be a family of efficiently computable functions such that ${\mathsf {wPRF}}_\lambda : \{0, 1\}^{n(\lambda )} \times \{0, 1\}^{m(\lambda )} \rightarrow \{0, 1\}^{p(\lambda )}$, where the first input is called the seed. Pick a seed $s {\mathop {\leftarrow }\limits ^{{\mathrm{R}}}}\{0, 1\}^{n(\lambda )}$ and $\ell +1$ points $x_1, \ldots , x_{\ell }, x^\star {\mathop {\leftarrow }\limits ^{{\mathrm{R}}}}\{0, 1\}^{m(\lambda )}$. Let $D_\ell$ be the $\ell$-tuple of values $(x_1, {\mathsf {wPRF}}_\lambda (s, x_1)), \ldots , (x_{\ell }, {\mathsf {wPRF}}_\lambda (s, x_{\ell }))$. Then the ${\mathsf {wPRF}}$ family is a weak pseudo-random function family if for every $\ell$ polynomial in $\lambda$,

$$\begin{aligned} \{D_\ell , x^\star , {\mathsf {wPRF}}_\lambda (s, x^\star )\}_{\lambda \in {\mathbb {N}}} \quad {\mathop {\approx }\limits ^{{\mathrm{c}}}}\quad \{D_\ell , x^\star , r\}_{\lambda \in {\mathbb {N}}}, \end{aligned}$$

where r is a random string of length $p(\lambda )$.

Below we present two alternate definitions of security for a weak pseudorandom family. The first one is a standard definition for PRFs/weak PRFs, while the second one is introduced for our final impossibility result. They both follow from Definition 1 above through simple hybrid arguments.

Definition 2

(Weak PRFs, many points). Let ${\mathsf {wPRF}}= \{{\mathsf {wPRF}}_\lambda \}_{\lambda \in {\mathbb {N}}}$ be a family as in Definition 1. Pick $s {\mathop {\leftarrow }\limits ^{{\mathrm{R}}}}\{0, 1\}^{n(\lambda )}$, $x_1, \ldots , x_{\ell } {\mathop {\leftarrow }\limits ^{{\mathrm{R}}}}\{0, 1\}^{m(\lambda )}$, and $r_1, \ldots , r_{\ell } {\mathop {\leftarrow }\limits ^{{\mathrm{R}}}}\{0, 1\}^{p(\lambda )}$. Then the ${\mathsf {wPRF}}$ family is a weak PRF family for many points if for every $\ell$ polynomial in $\lambda$,

$$\begin{aligned} \{(x_1, {\mathsf {wPRF}}_\lambda (s, x_1)), \ldots , (x_{\ell }, {\mathsf {wPRF}}_\lambda (s, x_{\ell }))\}_{\lambda \in {\mathbb {N}}} \quad {\mathop {\approx }\limits ^{{\mathrm{c}}}}\quad \{(x_1, r_1), \ldots , (x_{\ell }, r_{\ell })_{\lambda \in {\mathbb {N}}}. \end{aligned}$$

Definition 3

(Weak PRFs, many seeds with aux). Let ${\mathsf {wPRF}}= \{{\mathsf {wPRF}}_\lambda \}_{\lambda \in {\mathbb {N}}}$ be a family as in Definition 1. Pick k seeds $s_1, \ldots , s_k {\mathop {\leftarrow }\limits ^{{\mathrm{R}}}}\{0, 1\}^{n(\lambda )}$ and $\ell +1$ points $x_1, \ldots , x_{\ell }, x^\star {\mathop {\leftarrow }\limits ^{{\mathrm{R}}}}\{0, 1\}^{m(\lambda )}$. Let $D_{k, \ell }$ be the $k \cdot \ell$-tuple of values $(x_1, {\mathsf {wPRF}}_\lambda (s_1, x_1)),$ $\ldots ,$ $(x_{\ell }, {\mathsf {wPRF}}_\lambda (s_1, x_{\ell })),$ $\ldots ,$ $(x_1, {\mathsf {wPRF}}_\lambda (s_k, x_1)), \ldots , (x_{\ell }, {\mathsf {wPRF}}_\lambda (s_k, x_{\ell }))$. Then the ${\mathsf {wPRF}}$ family is a weak PRF family for many seeds with auxiliary information if for every $k, \ell$ polynomial in $\lambda$,

$$\begin{aligned} \{D_{k, \ell }, x^\star , {\mathsf {wPRF}}_\lambda (s_1, x^\star ), \ldots , {\mathsf {wPRF}}_\lambda (s_k, x^\star )\}_{\lambda \in {\mathbb {N}}} \quad {\mathop {\approx }\limits ^{{\mathrm{c}}}}\quad \{D_{k, \ell }, x^\star , r_1, \ldots , r_k\}_{\lambda \in {\mathbb {N}}}, \end{aligned}$$

where $r_1, \ldots , r_k$ are random strings of length $p(\lambda )$.

2.2 Randomized Encodings

We use decomposable randomized encodings [20] to simplify the description of our FE schemes. They are known to exist for all circuits due to the works of [4, 34].

Definition 4

(Randomized Encodings). Let ${\mathcal {C}}= \left\{ {\mathcal {C}}_{\lambda }\right\} _{\lambda }$ be a family of circuits, where each circuit $C \in {\mathcal {C}}_{\lambda }$ takes an $n(\lambda )$ bit input and produces an $m(\lambda )$ bit output. A decomposable randomized encoding ${\mathsf {RE}}$ of ${\mathcal {C}}$ consists of two ${\mathsf {PPT}}$ algorithms:

• ${\mathsf {RE.Encode}}(1^\lambda , C):$ It takes a circuit $C \in {\mathcal {C}}_{\lambda }$ as input, and outputs a randomized encoding $((w_{1,0}, w_{1, 1}), \ldots , (w_{n(\lambda ), 0}, w_{n(\lambda ), 1}))$.

• ${\mathsf {RE.Decode}}(1^\lambda , ({\tilde{w}}_1, \ldots , {\tilde{w}}_{n(\lambda )})):$ It takes an encoding $({\tilde{w}}_1, \ldots , {\tilde{w}}_{n(\lambda )})$ and outputs $y \in \{0,1\}^{m(\lambda )} \cup \{\perp \}$.

Correctness. Let $C \in {\mathcal {C}}_{\lambda }$ be any circuit, and let $((w_{1,0}, w_{1,1}), \ldots , (w_{n,0}, w_{n,1})) \leftarrow {\mathsf {RE.Encode}}(1^{\lambda }, C)$. For any input $x \in \{0,1\}^{n(\lambda )}$, ${\mathsf {RE.Decode}}(1^{\lambda }, (w_{1, x_1}, \ldots , w_{n(\lambda ), x_{n(\lambda )}})) = C(x)$.

Security. To define the security of such a scheme, consider the following two distributions:

• ${\mathsf {Real}}^{\mathsf {RE}}_{\mathcal {A}}(\lambda )$. Run ${\mathcal {A}}(1^\lambda )$ to get a $C \in {\mathcal {C}}_{\lambda }$ and an $x \in \{0, 1\}^{n(\lambda )}$. Then run ${\mathsf {RE.Encode}}$ on input C to get an encoding $((w_{1,0}, w_{1, 1}), \ldots , (w_{n(\lambda ), 0}, w_{n(\lambda ), 1}))$. Output $\{w_{i, x_i}\}_{i \in [n(\lambda )]}$.

• ${\mathsf {Ideal}}^{\mathsf {RE}}_{\mathcal {S}}(\lambda )$. Run ${\mathcal {A}}(1^\lambda )$ to get a $C \in {\mathcal {C}}_{\lambda }$ and an $x \in \{0, 1\}^{n(\lambda )}$. Output ${\mathcal {S}}(1^\lambda , C, C(x))$.

A randomized encoding scheme ${\mathsf {RE}}$ is secure if for every ${\mathsf {PPT}}$ adversary ${\mathcal {A}}$, there exists a ${\mathsf {PPT}}$ simulator ${\mathcal {S}}$ such that

$$\begin{aligned} {\mathsf {Real}}^{\mathsf {RE}}_{\mathcal {A}}(\lambda ) {\mathop {\approx }\limits ^{{\mathrm{c}}}}{\mathsf {Ideal}}^{\mathsf {RE}}_{\mathcal {S}}(\lambda ). \end{aligned}$$

3 Functional Encryption in the Random Oracle Model

A functional encryption scheme for a function space ${\mathbb {F}}= \{{\mathbb {F}}_\lambda \}_{\lambda \in {\mathbb {N}}}$ and a message space ${\mathcal {X}}= \{{\mathcal {X}}_\lambda \}_{\lambda \in {\mathbb {N}}}$ in the random oracle model consists of four ${\mathsf {PPT}}$ algorithms that have access to a random oracle ${\mathcal {O}}: \{0, 1\}^{\ell (\lambda )} \rightarrow \{0, 1\}^{m(\lambda )}$, where $\ell$ and m are polynomials. The algorithms are described as follows:

• ${\mathsf {Setup}}^{\mathcal {O}}(1^\lambda )$: It takes the security parameter (in unary representation) as input and outputs a public key ${\mathsf {pk}}$ and a master secret key ${\mathsf {msk}}$.

• ${\mathsf {KeyGen}}^{\mathcal {O}}({\mathsf {msk}}, f)$: It takes the master secret key ${\mathsf {msk}}$ and a circuit $f \in {\mathbb {F}}_\lambda$ as inputs, and outputs a secret key ${\mathsf {sk}}_f$ for the circuit.

• ${\mathsf {Encrypt}}^{\mathcal {O}}({\mathsf {pk}}, x)$: It takes the public key ${\mathsf {pk}}$ and a value $x \in {\mathcal {X}}_\lambda$ as inputs, and outputs a ciphertext ${\mathsf {ct}}_x$.

• ${\mathsf {Decrypt}}^{\mathcal {O}}({\mathsf {pk}}, {\mathsf {sk}}, {\mathsf {ct}})$: It takes the public key ${\mathsf {pk}}$, a secret key ${\mathsf {sk}}$, and a ciphertext ${\mathsf {ct}}$ as inputs, and outputs a value y or $\perp$.

Correctness. The four algorithms defined above must satisfy the following correctness property. For all values of the security parameter $\lambda$, for every $f \in {\mathbb {F}}_\lambda$ and $x \in {\mathcal {X}}_\lambda$, all random oracles ${\mathcal {O}}$, and all $({\mathsf {pk}}, {\mathsf {msk}})$ output by ${\mathsf {Setup}}^{\mathcal {O}}(1^\lambda )$,

$$\begin{aligned} {\mathsf {Decrypt}}^{\mathcal {O}}({\mathsf {pk}}, {\mathsf {KeyGen}}^{\mathcal {O}}({\mathsf {msk}}, f), {\mathsf {Encrypt}}^{\mathcal {O}}({\mathsf {pk}}, x)) = f(x). \end{aligned}$$

Without loss of generality, we can assume ${\mathsf {Decrypt}}$ to be deterministic.

One could consider weaker notions of correctness where a negligible probability of error is allowed.

Statistical Correctness. For all values of the security parameter $\lambda$, for every $f \in {\mathbb {F}}_\lambda$ and $x \in {\mathcal {X}}_\lambda$, all random oracles ${\mathcal {O}}$,

$$\begin{aligned} \Pr \left[ {\mathsf {Decrypt}}^{{\mathcal {O}}}\left( {\mathsf {pk}}, {\mathsf {sk}}, {\mathsf {ct}} \right) = f(x) : \begin{array}{l} ({\mathsf {pk}}, {\mathsf {msk}}) \leftarrow {\mathsf {Setup}}^{{\mathcal {O}}}(1^{\lambda }) \\ {\mathsf {sk}}\leftarrow {\mathsf {KeyGen}}^{{\mathcal {O}}}\left( {\mathsf {msk}},f \right) \\ {\mathsf {ct}}\leftarrow {\mathsf {Encrypt}}^{{\mathcal {O}}}\left( {\mathsf {pk}}, x \right) \\ \end{array}\right] \ge 1-{\mathsf {negl}}(\lambda ) \end{aligned}$$

3.1 Simulation-Based Security

Definition 5

(Experiments). Let ${\mathsf {FE}}= ({\mathsf {Setup}}, {\mathsf {KeyGen}}, {\mathsf {Encrypt}}, {\mathsf {Decrypt}})$ be a functional encryption scheme. For any ${\mathsf {PPT}}$ algorithms ${\mathcal {A}}= ({\mathcal {A}}_1, {\mathcal {A}}_2)$ and ${\mathcal {S}}= ({\mathcal {S}}_1, {\mathcal {S}}_2, {\mathcal {S}}_3, {\mathcal {S}}_4)$, Fig. 1 defines two experiments ${\mathsf {Real}}^{\mathsf {FE}}_{\mathcal {A}}(\lambda )$ and ${\mathsf {Ideal}}^{\mathsf {FE}}_{{\mathcal {A}}, {\mathcal {S}}}(\lambda )$. In the figure, $q_c$ denotes the length of challenge message vector $\mathbf {x}$ output by ${\mathcal {A}}_1$ and $q_1$ denotes the number of key generation queries made before that.

Fig. 1.

Real and ideal experiments.

Definition 6

(Admissibility). An adversary ${\mathcal {A}}= ({\mathcal {A}}_1, {\mathcal {A}}_2)$ is $({q_{{\mathsf {pre}}}}(\lambda ), {q_{{\mathsf {chal}}}}(\lambda ), {q_{{\mathsf {post}}}}(\lambda ))$-admissible if in any run of the experiments ${\mathsf {Real}}_{\mathcal {A}}(1^\lambda )$ and ${\mathsf {Ideal}}_{{\mathcal {A}}, {\mathcal {S}}}(1^\lambda )$, ${\mathcal {A}}_1$ and ${\mathcal {A}}_2$ make at most ${q_{{\mathsf {pre}}}}(\lambda )$ and ${q_{{\mathsf {post}}}}(\lambda )$ key generation queries, respectively, and ${\mathcal {A}}_1$ outputs at most ${q_{{\mathsf {chal}}}}(\lambda )$ challenge messages.

An adversary ${\mathcal {A}}$ is $({\mathsf {poly}}, {q_{{\mathsf {chal}}}}(\lambda ), {q_{{\mathsf {post}}}}(\lambda ))$-admissible if in any run of the experiments ${\mathsf {Real}}_{\mathcal {A}}(1^\lambda )$ and ${\mathsf {Ideal}}_{{\mathcal {A}}, {\mathcal {S}}}(1^\lambda )$, ${\mathcal {A}}_1$ is allowed to make an unbounded (but polynomial) number of pre-challenge key queries, ${\mathcal {A}}_2$ makes at most ${q_{{\mathsf {post}}}}(\lambda )$ key generation queries, and ${\mathcal {A}}_1$ outputs at most ${q_{{\mathsf {chal}}}}(\lambda )$ challenge messages. We can similarly define admissible adversaries where the number of challenge messages/post challenge key queries are unbounded.

On the other hand, a simulator ${\mathcal {S}}= ({\mathcal {S}}_1, {\mathcal {S}}_2, {\mathcal {S}}_3, {\mathcal {S}}_4)$ is admissible if whenever ${\mathcal {A}}_2$ makes a key query f, ${\mathcal {S}}_4$ queries $\mathsf {KeyIdeal}$ on f only.

Definition 7

(Simulation security). A functional encryption scheme ${\mathsf {FE}}= ({\mathsf {Setup}}, {\mathsf {KeyGen}}, {\mathsf {Encrypt}}, {\mathsf {Decrypt}})$ is $({q_{{\mathsf {pre}}}}(\lambda ), {q_{{\mathsf {chal}}}}(\lambda ), {q_{{\mathsf {post}}}}(\lambda ))$-${\mathsf {Sim}}$-secure for some polynomials ${q_{{\mathsf {pre}}}}$, ${q_{{\mathsf {chal}}}}$, and ${q_{{\mathsf {post}}}}$, if there exists an admissible ${\mathsf {PPT}}$ simulator ${\mathcal {S}}=({\mathcal {S}}_1, {\mathcal {S}}_2, {\mathcal {S}}_3, {\mathcal {S}}_4)$ such that for all $({q_{{\mathsf {pre}}}}(\lambda ), {q_{{\mathsf {chal}}}}(\lambda ), {q_{{\mathsf {post}}}}(\lambda ))$-admissible ${\mathsf {PPT}}$ adversaries ${\mathcal {A}}= ({\mathcal {A}}_1, {\mathcal {A}}_2)$,

$$\begin{aligned} \{{\mathsf {Real}}^{\mathsf {FE}}_{\mathcal {A}}(\lambda )\}_{\lambda \in {\mathbb {N}}} {\mathop {\approx }\limits ^{{\mathrm{c}}}}\{{\mathsf {Ideal}}^{\mathsf {FE}}_{{\mathcal {A}}, {\mathcal {S}}}(\lambda )\}_{\lambda \in {\mathbb {N}}}. \end{aligned}$$

We also consider adversaries that make an unbounded (but polynomial) number of pre-challenge key queries/challenge messages/post-challenge key queries.

Definition 8

(Simulation security, unbounded queries). A functional encryption scheme ${\mathsf {FE}}= ({\mathsf {Setup}}, {\mathsf {KeyGen}}, {\mathsf {Encrypt}}, {\mathsf {Decrypt}})$ is $({\mathsf {poly}}, {q_{{\mathsf {chal}}}}(\lambda ), {q_{{\mathsf {post}}}}(\lambda ))$-${\mathsf {Sim}}$-secure for some polynomials ${q_{{\mathsf {chal}}}}$, and ${q_{{\mathsf {post}}}}$, if there exists an admissible ${\mathsf {PPT}}$ simulator ${\mathcal {S}}=({\mathcal {S}}_1, {\mathcal {S}}_2, {\mathcal {S}}_3, {\mathcal {S}}_4)$ such that for all $({\mathsf {poly}}, {q_{{\mathsf {chal}}}}(\lambda ), {q_{{\mathsf {post}}}}(\lambda ))$-admissible ${\mathsf {PPT}}$ adversaries ${\mathcal {A}}= ({\mathcal {A}}_1, {\mathcal {A}}_2)$,

$$\begin{aligned} \{{\mathsf {Real}}^{\mathsf {FE}}_{\mathcal {A}}(\lambda )\}_{\lambda \in {\mathbb {N}}} {\mathop {\approx }\limits ^{{\mathrm{c}}}}\{{\mathsf {Ideal}}^{\mathsf {FE}}_{{\mathcal {A}}, {\mathcal {S}}}(\lambda )\}_{\lambda \in {\mathbb {N}}}. \end{aligned}$$

We can similarly define simulation security when ${q_{{\mathsf {chal}}}}$ and ${q_{{\mathsf {post}}}}$ are unbounded.

Note that in the real world an adversary has explicit access to the random oracle. In the ideal world, both the key generation and random oracles are simulated by ${\mathcal {S}}$ throughout the experiment.

Discussion on Previous Definitions of Sim-Secure FE. There are a number of definitions of simulation secure functional encryption [2, 5, 12, 30]. While these definitions are similar in spirit, there are minor differences. For instance, in the security game of [2, 12], the adversary makes pre-challenge key queries, followed by a challenge phase (where it queries for ciphertexts), followed by a post-challenge key query phase. The definition of [5] is more general as it allows arbitrary interleaving of encryption and key-generation queries. We use the AGVW definition [2] in this work, although we believe our impossibility result can also be extended to work for the definitions in [5].

4 Hardness of Approximate Compression

In this section, we will first define the notion of approximate compression, and then show that there are certain circuit families which are hard to approximately compress. This section closely follows the work of Agrawal et al. [2], who defined the notion of (exact) compressibility of circuit evaluations, and showed that there exist certain circuit families that are (exact) incompressible.

Definition 9

Let $\ell$, t be polynomials and $\epsilon$ a non-negligible function. A class of circuits ${\mathcal {C}}= \{{\mathcal {C}}_{\lambda }\}_{\lambda }$ with domain ${\mathcal {D}}= \{{\mathcal {D}}_{\lambda }\}_{\lambda }$ and range ${\mathcal {R}}= \{{\mathcal {R}}_{\lambda }\}_{\lambda }$ is said to be $(\ell , t, \epsilon )$-approximately compressible if there exists a family of compression circuits ${\mathsf {Cmp}}= \{{\mathsf {Cmp}}_{\lambda }\}_{\lambda }$, a family of decompression circuits ${\mathsf {DeCmp}}= \{{\mathsf {DeCmp}}_{\lambda }\}_{\lambda }$, a polynomial ${\mathsf {poly}}$, and a non-negligible function $\eta$, such that for all large enough $\lambda$ the following properties hold:

• The circuits ${\mathsf {Cmp}}_{\lambda }$ and ${\mathsf {DeCmp}}_{\lambda }$ have size bounded by ${\mathsf {poly}}(\lambda )$.

• (compression) For all input $s \in {\mathcal {D}}_{\lambda }$ and circuits $C_1, C_2, \ldots , C_{\ell (\lambda )} \in {\mathcal {C}}_{\lambda }$,

  $$\begin{aligned} \left| {\mathsf {Cmp}}_{\lambda }\left( \left\{ C_i, C_i(s)\right\} _{i \in [\ell (\lambda )]} \right) \right| \le t(\lambda ). \end{aligned}$$

• (approximate decompression) If s is chosen at random from ${\mathcal {D}}_{\lambda }$, $C_1, C_2, \ldots , C_{\ell (\lambda )}$ are chosen uniformly and independently from ${\mathcal {C}}_{\lambda }$, then

  $$\begin{aligned}&\Pr \bigg [{\mathsf {HD}}\left( {\mathsf {DeCmp}}_\lambda \left( \left\{ C_i\right\} _{i \in [\ell (\lambda )]}, {\mathsf {Cmp}}_\lambda \left( \left\{ C_i, C_i(s)\right\} _{i \in [\ell (\lambda )]} \right) \right) , \left( C_1(s), \ldots , C_{\ell (\lambda )}(s) \right) \right) \\&\qquad \qquad \qquad \qquad \qquad \qquad \qquad \quad \le \epsilon (\lambda ) \cdot t(\lambda ) \bigg ] \ge \eta (\lambda ) \end{aligned}$$

We will now show that weak PRFs can be used to construct a class of circuits that are not approximate compressible. We will then use the more general notion of approximate incompressibility, rather than the specific case of weak PRFs, in proving our impossibility results. For simplicity of presentation, in the lemma statement below, we use specific constants which will be sufficient for our main result. However, the lemma can be easily extended to work for general $\ell$, t and $\epsilon$. We assume that the weak PRF outputs a single bit.

Lemma 1

Let ${\mathsf {wPRF}}= \left\{ {\mathsf {wPRF}}_{\lambda }\right\} _{\lambda }$ be a family of weak pseudorandom functions (for many points), where ${\mathsf {wPRF}}_{\lambda }: \{0,1\}^{n(\lambda )} \times \{0,1\}^{m(\lambda )} \rightarrow \{0,1\}$. Consider the family of circuits ${\mathcal {C}}= \{{\mathcal {C}}_{\lambda }\}_{\lambda }$, where ${\mathcal {C}}_{\lambda }= \left\{ {\mathsf {wPRF}}_\lambda (\cdot , x)\right\} _{x \in \{0,1\}^{m(\lambda )}}$. Let $t = t(\lambda )$ be any polynomial such that $t(\lambda ) \ge \lambda$ for all $\lambda \in {\mathbb {N}}$. Then ${\mathcal {C}}$ is not (16t, t, 1/8) approximate compressible.

The proof of this lemma is given in the full version of our paper [1].

5 Impossibility of Simulation Secure FE

In this section we show that there does not exist a functional encryption scheme for the family of all polynomial-sized circuits that is $({\mathsf {poly}}, 1, 0)$-${\mathsf {Sim}}$ secure in the random oracle model. Specifically, we show that a simulation secure FE scheme cannot be constructed for any family of circuits that is not approximately compressible (Definition 9). We exhibit an adversary ${\mathcal {A}}= ({\mathcal {A}}_1, {\mathcal {A}}_2)$ such that for any efficient simulator ${\mathcal {S}}$, the output of the real experiment, ${\mathsf {Real}}^{\mathsf {FE}}_{\mathcal {A}}(1^\lambda )$, is distinguishable from the output of the ideal experiment, ${\mathsf {Ideal}}^{\mathsf {FE}}_{{\mathcal {A}}, {\mathcal {S}}}(1^\lambda )$ (Definition 8).

High Level Description of Adversary. Let ${\mathcal {C}}$ be an approximate incompressible circuit family. The adversary ${\mathcal {A}}_1$ first asks for secret keys for a large number of randomly chosen circuits from C, and receives $\left\{ {\mathsf {sk}}_1, \ldots , {\mathsf {sk}}_q\right\}$ in return. Next, it generates encryptions of many random messages. It then decrypts each of these ciphertexts using the q secret keys. The purpose of these encryptions followed by the decryptions is to capture the random oracle queries that would have occurred while computing the q secret keys, which may also be required when these keys are used again for decryption later. Let $S_{\mathrm {keys}}$ denote the set of random oracle queries that occur during these decryptions.

${\mathcal {A}}_1$ chooses a random message $x^*$, and outputs it as the challenge (along with a state that consists of its view so far). ${\mathcal {A}}_2$ then receives a ciphertext ${\mathsf {ct}}^*$. It decrypts ${\mathsf {ct}}^*$ using ${\mathsf {sk}}_1, \ldots , {\mathsf {sk}}_t$, for some small t. Let $S_{{\mathsf {ct}}^*}$ denote the set of random oracle queries during these t decryptions. The purpose of these t decryptions is to capture the random oracle queries that would have occurred during the encryption of $x^*$, which may also be required when ${\mathsf {ct}}^*$ is decrypted again in the next step.

Finally, ${\mathcal {A}}_2$ decrypts ${\mathsf {ct}}^*$ using the remaining $q-t$ secret keys. An important thing to note here is that ${\mathcal {A}}_2$ turns off the random oracle, and instead uses the queries that it has already recorded. If a new random oracle query is required, then it uses a randomly chosen string. It compares the decrypted values to the correct function evaluations, and outputs 1 if most decryptions are correct.

First, we show that in the real world, ${\mathcal {A}}_2$ outputs 1 with probability at least 3/4. Let us focus on one of the $q-t$ decryptions, using a secret key ${\mathsf {sk}}_j$. At a high level, this decryption can go wrong if a random oracle query is made on z, and $z \notin S_{\mathrm {keys}} \cup S_{{\mathsf {ct}}}$, but z was used during the computation of either ${\mathsf {sk}}_j$ or ${\mathsf {ct}}$. We show that this event happens with low probability.

To complete the argument, we show that in the ideal world, ${\mathcal {A}}_2$ outputs 1 with probability around 1/2. In this world, the simulator receives q circuit evaluations on $x^*$, and must compress most of this information in the short challenge ciphertext and the random oracle queries made during the t post-challenge decryption operations. By choosing parameters carefully and appealing to the (approximate) incompressibility of the circuit family, we show that this is not possible.

5.1 Formal Description of Adversary

Let ${\mathcal {C}}= \left\{ {\mathcal {C}}_{\lambda }\right\} _\lambda$ be a family of circuits such that each circuit in ${\mathcal {C}}_{\lambda }$ takes an $n(\lambda )$-bit input and is not (16t, t, 1/8) approximately compressible for all polynomials t such that $t(\lambda ) \ge \lambda$. Let ${\mathsf {FE}}$ be a functional encryption scheme for this family in the random oracle model. We now formally define the adversary ${\mathcal {A}}= ({\mathcal {A}}_1, {\mathcal {A}}_2)$.

Adversary ${\mathcal {A}}_1$. Let $n_{{{\mathsf {key}}}}$ and $n_{{\mathsf {enc}}}$ be polynomials in $\lambda$ whose values will be fixed later. Let $\varGamma$ be a list of (query, response) pairs that is empty at the beginning. ${\mathcal {A}}_1$ has four phases: setup, key query, random oracle query collection, and an output phase.

• 1. Setup. ${\mathcal {A}}_1$ receives the public key ${\mathsf {pk}}$.

• 2. Key query. For $i \in [n_{{{\mathsf {key}}}}]$, it picks a circuit $C_i$ at random from ${\mathcal {C}}_{\lambda }$, requests a secret key for $C_i$, and obtains ${\mathsf {sk}}_i$ in return.

• 3. RO query collection 1. ${\mathcal {A}}_1$ picks $n_{{\mathsf {enc}}}$ inputs $x_1, x_2, \ldots , x_{n_{{\mathsf {enc}}}} {\mathop {\leftarrow }\limits ^{{\mathrm{R}}}}\{0, 1\}^{n(\lambda )}$. For $j \in [n_{{\mathsf {enc}}}]$, it runs ${\mathsf {Encrypt}}^{\mathcal {O}}({\mathsf {pk}}, x_j)$ to obtain a ciphertext ${\mathsf {ct}}_j$. The RO queries made during the encryption process are forwarded to the random oracle.

  Now each of the ciphertexts ${\mathsf {ct}}_{1}, \ldots , {\mathsf {ct}}_{n_{{\mathsf {enc}}}}$ are decrypted with key ${\mathsf {sk}}_i$ for every $i \in [n_{{{\mathsf {key}}}}]$. If an oracle query $\beta$ is made by the ${\mathsf {Decrypt}}$ algorithm, ${\mathcal {A}}_1$ queries the random oracle with the same. The response, say $\gamma$, is given to the algorithm, and $(\beta , \gamma )$ is added to $\varGamma$ (if it is not already present).

• 4. Output. ${\mathcal {A}}_1$ picks an input $x^* {\mathop {\leftarrow }\limits ^{{\mathrm{R}}}}\{0, 1\}^{n(\lambda )}$. It sets the state ${\mathsf {st}}$ to consist of ${\mathsf {pk}}$, $C_1, \ldots , C_{n_{{{\mathsf {key}}}}}$, ${\mathsf {sk}}_1, \ldots , {\mathsf {sk}}_{n_{{{\mathsf {key}}}}}$, $x^*$, and $\varGamma$. Then it outputs $(x^*, {\mathsf {st}})$.

Adversary ${\mathcal {A}}_2$. Let $n_{{\mathsf {eval}}}$ and $n_{{\mathsf {test}}}$ be polynomials in $\lambda$ s.t. $n_{{\mathsf {eval}}}(\lambda ) + n_{{\mathsf {test}}}(\lambda ) = n_{{{\mathsf {key}}}}(\lambda )$ for all $\lambda$. (Their values will be fixed later.) ${\mathcal {A}}_2$ gets ${\mathsf {ct}}^*$ and ${\mathsf {st}}$ as input, and parses the latter to get ${\mathsf {pk}}$, $C_1, \ldots , C_{n_{{{\mathsf {key}}}}}$, ${\mathsf {sk}}_1, \ldots , {\mathsf {sk}}_{n_{{{\mathsf {key}}}}}$, $x^*$, and $\varGamma$. ${\mathcal {A}}_2$ has three phases: random oracle query collection, test, and an output phase.

• 1. RO query collection 2. For every $i \in [n_{{\mathsf {eval}}}]$, ${\mathsf {ct}}^*$ is decrypted with ${\mathsf {sk}}_i$. If an RO query $\beta$ is made by the ${\mathsf {Decrypt}}$ algorithm, ${\mathcal {A}}_2$ queries the random oracle with the same. The response, say $\gamma$, is given to the algorithm, and $(\beta , \gamma )$ is added to $\varGamma$ (if it is not already present).

• 2. Test. In this phase, ${\mathsf {ct}}^*$ is decrypted with rest of the keys but without invoking the random oracle. In order to do so, a new list $\varDelta$ is initialized first, then the following steps are executed for every $n_{{\mathsf {eval}}}+1 \le i \le n_{{\mathsf {eval}}}+n_{{\mathsf {test}}}$. The decryption algorithm is run with inputs ${\mathsf {pk}}$, ${\mathsf {sk}}_i$, and ${\mathsf {ct}}^*$. When it makes an RO query $\beta$, ${\mathcal {A}}_2$ checks whether there is an entry of the form $(\beta , \gamma )$ in $\varGamma$ or $\varDelta$ (in that order) or not. If yes, then $\gamma$ is given to ${\mathsf {Decrypt}}$ and it continues to run. Otherwise, a random bit-string $\gamma '$ of length $m(\lambda )$ (the output length of the random oracle) is generated, $(\beta , \gamma ')$ is added to $\varDelta$, and $\gamma '$ is given to ${\mathsf {Decrypt}}$. This process of providing responses to the RO queries of ${\mathsf {Decrypt}}$ continues till it terminates. Let $\mathsf{out}_i$ denote the output of ${\mathsf {Decrypt}}$, which could be $\perp$.

• 3. Output. For every $n_{{\mathsf {eval}}}+1 \le i \le n_{{\mathsf {eval}}}+n_{{\mathsf {test}}}$, check if $\mathsf{out}_i$ is equal to $C_i(x^*)$ (where $x^*$ and $C_i$ are part of the state transferred to ${\mathcal {A}}_2$). Let ${\mathsf {num}}$ be the number of keys for which this check succeeds. Output 1 if ${\mathsf {num}}/ n_{{\mathsf {test}}}\ge 7/8$, else output 0.

To complete the description of ${\mathcal {A}}$, we need to define the polynomials $n_{{\mathsf {enc}}}$, $n_{{\mathsf {eval}}}$ and $n_{{\mathsf {test}}}$ (recall that $n_{{{\mathsf {key}}}}= n_{{\mathsf {eval}}}+ n_{{\mathsf {test}}}$). Let $q_{{\mathsf {Setup}}}$, $q_{{\mathsf {Enc}}}$, $q_{{\mathsf {KeyGen}}}$ and $q_{{\mathsf {Dec}}}$ be upper-bounds on the number of RO queries made by ${\mathsf {Setup}}$, ${\mathsf {Encrypt}}$, ${\mathsf {KeyGen}}$ and ${\mathsf {Decrypt}}$, respectively, as a function of $\lambda$. Also, let $\ell _{\mathsf {ct}}$ be an upper-bound on the length of ciphertexts generated by ${\mathsf {Encrypt}}$. Then set

• $n_{{\mathsf {enc}}}= 4 \lambda \cdot n_{{{\mathsf {key}}}}\cdot q_{{\mathsf {KeyGen}}}$,

• $n_{{\mathsf {eval}}}= 32 \lambda \left( q_{{\mathsf {Setup}}}+ q_{{\mathsf {Enc}}} \right)$,

• $n_{{\mathsf {test}}}= 16 (\ell _{{\mathsf {ct}}} + n_{{\mathsf {eval}}}\cdot q_{{\mathsf {Dec}}}\cdot m)$.

5.2 Real World Analysis

First, we will show that the adversary ${\mathcal {A}}= ({\mathcal {A}}_1, {\mathcal {A}}_2)$ described above outputs 1 with probability at least 3/4 in the real world experiment, as long as the scheme ${\mathsf {FE}}$ is correct. To begin with, we classify the random oracle queries made during a run of ${\mathcal {A}}$ into different sets as follows:

• ${{\mathsf {S}}} \text {-}{\mathsf {RO}}_{C_i}$ for $i \in [n_{{{\mathsf {key}}}}]$: random oracle queries made by ${\mathsf {KeyGen}}$ while generating secret key for $C_i$.

• ${{\mathsf {S}}} \text {-}{\mathsf {RO}}_{\mathrm {keys}} = \bigcup _{i \in [n_{{{\mathsf {key}}}}]} {{\mathsf {S}}} \text {-}{\mathsf {RO}}_{C_i}$: all random oracle queries during the key query phase of ${\mathcal {A}}_1$.

• ${{\mathsf {S}}} \text {-}{\mathsf {RO}}_{x^*}$: random oracle queries made while encrypting $x^*$ using ${\mathsf {pk}}$.

• ${{\mathsf {S}}} \text {-}{\mathsf {RO}}_{\mathrm {Dec}\text {-}i}$ for $i \in [n_{{\mathsf {test}}}]$: random oracle queries made during the decryption of ${\mathsf {ct}}^*$ using ${\mathsf {sk}}_{n_{{\mathsf {eval}}}+i}$.

• ${{\mathsf {S}}} \text {-}{\mathsf {RO}}_{\varGamma \text {-}b}$: random oracle queries recorded during ‘RO Collection Phase b’ for $b\in \left\{ 1,2\right\}$. Let ${{\mathsf {S}}} \text {-}{\mathsf {RO}}_{\varGamma } = {{\mathsf {S}}} \text {-}{\mathsf {RO}}_{\varGamma \text {-}1} ~ \bigcup ~ {{\mathsf {S}}} \text {-}{\mathsf {RO}}_{\varGamma \text {-}2}$.

• ${{\mathsf {S}}} \text {-}{\mathsf {RO}}_{{\mathsf {Setup}}}$: random oracle queries made during setup phase.

Lemma 2

For any functional encryption scheme ${\mathsf {FE}}$ for the circuit family ${\mathcal {C}}= \left\{ {\mathcal {C}}_{\lambda }\right\} _\lambda$, the adversary ${\mathcal {A}}= ({\mathcal {A}}_1, {\mathcal {A}}_2)$ described in Sect. 5.1 outputs 1 in ${\mathsf {Real}}^{\mathsf {FE}}_{\mathcal {A}}(1^\lambda )$ with probability at least $3/4 - {\mathsf {negl}}(\lambda )$.

Proof

We will use the correctness property of ${\mathsf {FE}}$ to prove this claim. Recall that, for simplicity, we assume correctness to be perfect, i.e., for all random oracles ${\mathcal {O}}: \{0,1\}^{\ell (\lambda )} \rightarrow \{0,1\}^{m(\lambda )}$, $x \in \{0,1\}^{n(\lambda )}$, $C \in {\mathcal {C}}_\lambda$

$$\begin{aligned} \Pr \left[ {\mathsf {Decrypt}}^{{\mathcal {O}}}\left( {\mathsf {pk}}, {\mathsf {sk}}, {\mathsf {ct}} \right) = C(x): \begin{array}{l} ({\mathsf {pk}}, {\mathsf {msk}}) \leftarrow {\mathsf {Setup}}^{{\mathcal {O}}}(1^{\lambda }) \\ {\mathsf {sk}}\leftarrow {\mathsf {KeyGen}}^{{\mathcal {O}}}\left( {\mathsf {msk}},C \right) \\ {\mathsf {ct}}\leftarrow {\mathsf {Encrypt}}^{{\mathcal {O}}}\left( {\mathsf {pk}}, x \right) \\ \end{array} \right] \ge 1-{\mathsf {negl}}(\lambda ) \end{aligned}$$

In particular, we do not assume the decryption to be deterministic.

Let ${\mathsf {Bad}}$ denote the event that the adversary outputs 0 at the end of the real world experiment. This event happens if at least 1/8th fraction of the $n_{{\mathsf {test}}}$ decryptions fail in the test phase. If ${\mathsf {I}}\text {-}{\mathsf {Dec}}_i$ is an indicator variable that takes the value 1 in case the ith decryption fails, then ${\mathsf {Bad}}$ happens iff $\sum _{i \in [n_{{\mathsf {test}}}]} {\mathsf {I}}\text {-}{\mathsf {Dec}}_i > 1/8 \cdot n_{{\mathsf {test}}}$. To analyze the probability of this event, we need to consider the random oracle queries required for decryption in the test phase. In this phase, ${\mathcal {A}}_2$ does not query the random oracle, but instead uses the list $\varGamma$. If some query $\beta$ is not present in $\varGamma$, then ${\mathcal {A}}_2$ tries to find it in $\varDelta$. If $\beta$ is not found in $\varDelta$ either, then a random value is chosen and recorded in $\varDelta$ against $\beta$.

Now there are two ways in which the $i^{th}$ decryption can fail. The first is if there is some entry $(\beta , \gamma )$ in $\varDelta$ such that $\beta$ is also among the RO queries hidden from the adversary (and its response is not $\gamma$), i.e., the queries made during the setup phase, key query phase or challenge ciphertext generation. The second case is when the RO query responses are consistent, but the decryption is incorrect due to ‘bad’ decryption coins. The second failure happens with negligible probability (due to correctness of the FE scheme). In other words, the ith decryption succeeds with overwhelming probability if all the needed hidden RO responses are captured in either of the two RO collection phases. This is formalized in the following observation.

Observation 1

Let ${\mathsf {Bad}}\text {-}{\mathsf {Dec}}$ be the following event:

$$\begin{aligned} \begin{array}{c} \exists i \in [n_{{\mathsf {test}}}] \text { s.t. }\\ \left( {{\mathsf {S}}} \text {-}{\mathsf {RO}}_{\mathrm {Dec}\text {-}i} ~ \bigcap ~ \left( {{\mathsf {S}}} \text {-}{\mathsf {RO}}_{{\mathsf {Setup}}} \bigcup {{\mathsf {S}}} \text {-}{\mathsf {RO}}_{\mathrm {keys}} \bigcup {{\mathsf {S}}} \text {-}{\mathsf {RO}}_{x^*} \right) \subseteq {{\mathsf {S}}} \text {-}{\mathsf {RO}}_{\varGamma } \right) \\ \wedge \\ {\mathcal {A}}_2's \text { decryption of } {\mathsf {ct}}^* \text { using }{\mathsf {sk}}_{n_{{\mathsf {eval}}}+i} \text { does not output } C_{n_{{\mathsf {eval}}}+i}(x^*) \\ \end{array} \end{aligned}$$

There exists a negligible function ${\mathsf {negl}}(\cdot )$ s.t. $\Pr \left[ {\mathsf {Bad}}\text {-}{\mathsf {Dec}}\right] \le {\mathsf {negl}}(\lambda )$ where the probability is over the random coins used by setup, key generation, encryption, decryption and the adversary’s choice of inputs.

Proof

This observation follows from the statistical correctness of the scheme. Fix any index $i \in [n_{{\mathsf {eval}}}]$. Since $({{\mathsf {S}}} \text {-}{\mathsf {RO}}_{\mathrm {Dec}\text {-}i} ~ \bigcap ~ \left( {{\mathsf {S}}} \text {-}{\mathsf {RO}}_{{\mathsf {Setup}}} \bigcup {{\mathsf {S}}} \text {-}{\mathsf {RO}}_{\mathrm {keys}} \bigcup {{\mathsf {S}}} \text {-}{\mathsf {RO}}_{x^*} \right) \subseteq {{\mathsf {S}}} \text {-}{\mathsf {RO}}_{\varGamma })$, the oracle queries are consistent. Hence, we can use the correctness guarantee of the scheme to bound the probability of ${\mathsf {Bad}}\text {-}{\mathsf {Dec}}$.

Let ${\mathsf {I}}\text {-}{\mathsf {Dec}}\text {-}1_i$ and ${\mathsf {I}}\text {-}{\mathsf {Dec}}\text {-}2_i$ be indicator variables that are 1 iff ${{\mathsf {S}}} \text {-}{\mathsf {RO}}_{\mathrm {Dec}\text {-}i} ~ \bigcap ~ \left( {{\mathsf {S}}} \text {-}{\mathsf {RO}}_{x^*} \bigcup {{\mathsf {S}}} \text {-}{\mathsf {RO}}_{{\mathsf {Setup}}} \right) \not \subseteq {{\mathsf {S}}} \text {-}{\mathsf {RO}}_{\varGamma }$ and ${{\mathsf {S}}} \text {-}{\mathsf {RO}}_{\mathrm {Dec}\text {-}i} ~ \bigcap ~ {{\mathsf {S}}} \text {-}{\mathsf {RO}}_{\mathrm {keys}} \not \subseteq {{\mathsf {S}}} \text {-}{\mathsf {RO}}_{\varGamma }$, respectively. Then, ${\mathsf {I}}\text {-}{\mathsf {Dec}}_i = 1$ iff either ${\mathsf {I}}\text {-}{\mathsf {Dec}}\text {-}1_i = 1$ or ${\mathsf {I}}\text {-}{\mathsf {Dec}}\text {-}2_i = 1$ (or both). Let ${\mathsf {Bad}}\text {-}1$ and ${\mathsf {Bad}}\text {-}2$ be events that happen iff $\sum _{i \in [n_{{\mathsf {test}}}]} {\mathsf {I}}\text {-}{\mathsf {Dec}}\text {-}1_i > 1/16 \cdot n_{{\mathsf {test}}}$ and $\sum _{i \in [n_{{\mathsf {test}}}]} {\mathsf {I}}\text {-}{\mathsf {Dec}}\text {-}2_i > 1/16 \cdot n_{{\mathsf {test}}}$, respectively. It is easy to see that

$$\begin{aligned} \Pr \left[ {\mathsf {Bad}} \right] \le \Pr \left[ {\mathsf {Bad}}\text {-}1 \right] + \Pr \left[ {\mathsf {Bad}}\text {-}2 \right] {+ \Pr \left[ {\mathsf {Bad}}\text {-}{\mathsf {Dec}} \right] } \end{aligned}$$

Below we show that $\Pr \left[ {\mathsf {Bad}}\text {-}1 \right] \le {\mathsf {negl}}(\lambda )$ and $\Pr \left[ {\mathsf {Bad}}\text {-}2 \right] \le 1/4$. Thus the lemma follows.    

Claim 1

$\Pr \left[ {\mathsf {Bad}}\text {-}1 \right] \le {\mathsf {negl}}(\lambda )$.

Proof

Fix any random oracle ${\mathcal {O}}$, the randomness used in ${\mathsf {Setup}}^{{\mathcal {O}}}(1^{\lambda })$, challenge message $x^*$, and the randomness used in ${\mathsf {Encrypt}}^{{\mathcal {O}}}({\mathsf {pk}}, x^*)$. This also fixes the sets ${{\mathsf {S}}} \text {-}{\mathsf {RO}}_{{\mathsf {Setup}}}$ and ${{\mathsf {S}}} \text {-}{\mathsf {RO}}_{x^*}$. Suppose a circuit C is picked at random from ${\mathcal {C}}_\lambda$, and a key, ${\mathsf {sk}}$, is generated for it by running ${\mathsf {KeyGen}}^{{\mathcal {O}}}\left( {\mathsf {msk}}, C \right)$. For $z \in {{\mathsf {S}}} \text {-}{\mathsf {RO}}_{{\mathsf {Setup}}} \cup {{\mathsf {S}}} \text {-}{\mathsf {RO}}_{x^*}$, let $\rho _z$ be the probability that z is an RO query in the decryption of ${\mathsf {ct}}^*$ (the challenge ciphertext) with ${\mathsf {sk}}$, where the probability is over the choice of C, the randomness used in ${\mathsf {KeyGen}}$ and the random coins used in decryption.

Let $X_{i, z}$ be an indicator variable that is 1 if an RO query on z is made during the ith decryption in post-challenge phase (either in the RO collection 2 or test phase). Note that the keys ${\mathsf {sk}}_1, \ldots , {\mathsf {sk}}_{n_{{{\mathsf {key}}}}}$ are generated independently by choosing circuits $C_1, \ldots , C_{n_{{{\mathsf {key}}}}}$ uniformly at random, and the random coins used in each key generation and decryption are independently chosen. Thus for any z, the variables $X_{1, z}, \ldots , X_{n_{{{\mathsf {key}}}}, z}$ are independent of each other, and $\Pr \left[ X_{i, z} = 1 \right] = \rho _z$ for every i.

We are interested in the probability that $\sum _{i \in [n_{{\mathsf {test}}}]} {\mathsf {I}}\text {-}{\mathsf {Dec}}\text {-}1_i > n_{{\mathsf {test}}}/16$, i.e., in at least 1/16th fraction of the decryptions in the test phase, an RO query q is made s.t. q was also an RO query in either set-up or encryption of $x^*$, but it was not captured in either of the collection phases. Thus, there must exist a z s.t. $z \notin {{\mathsf {S}}} \text {-}{\mathsf {RO}}_{\varGamma }$ (in particular, $z \notin {{\mathsf {S}}} \text {-}{\mathsf {RO}}_{\varGamma \text {-}2}$) but an RO query on z is made in at least $n_{{\mathsf {test}}}/16|Q|$ of the decryptions, where $Q = {{\mathsf {S}}} \text {-}{\mathsf {RO}}_{{\mathsf {Setup}}} \cup {{\mathsf {S}}} \text {-}{\mathsf {RO}}_{x^*}$. (If $Q=\phi$ then ${\mathsf {Bad}}\text {-}1$ cannot happen, and we are done.) Therefore,

$$\begin{aligned} \Pr \left[ \sum _{i \in [n_{{\mathsf {test}}}]} {\mathsf {I}}\text {-}{\mathsf {Dec}}\text {-}1_i> \frac{n_{{\mathsf {test}}}}{16} \right] \quad \le \quad \sum _{z \in Q} \Pr \left[ z \notin {{\mathsf {S}}} \text {-}{\mathsf {RO}}_{\varGamma \text {-}2} \quad \wedge \quad \sum _{i \in [n_{{\mathsf {test}}}]} X_{i, z} > \frac{n_{{\mathsf {test}}}}{16|Q|} \right] \end{aligned}$$

Based on the value of $\rho _z$, we can divide the rest of the analysis into two parts. Intuitively, if $\rho _z$ is large, then the probability that z is not captured during RO collection phase is negligible. And when it is small, the probability that z causes too many decryptions to fail in the test phase is negligible. Since Q is polynomial in the security parameter, this will prove that the probability of ${\mathsf {Bad}}\text {-}1$ is negligible as well. So now,

• If $\rho _z \ge 1/32|Q|$ then

  $$\begin{aligned} \Pr \left[ z \notin {{\mathsf {S}}} \text {-}{\mathsf {RO}}_{\varGamma \text {-}2} \right]&= \Pr \left[ X_{1, z} = 0 \wedge \ldots \wedge X_{n_{{\mathsf {eval}}}, z} = 0 \right] \\&= \prod _{i \in [n_{{\mathsf {eval}}}]} \Pr \left[ X_{i, z} = 0 \right] \\&= (1 - \rho _z)^{n_{{\mathsf {eval}}}} \le e^{-n_{{\mathsf {eval}}}/32|Q|}, \end{aligned}$$

  where the second equality follows from the independence of $X_{i, z}$. Recall that we set $n_{{\mathsf {eval}}}$ to be $32\lambda (q_{{\mathsf {Setup}}}+ q_{{\mathsf {Enc}}})$, where $q_{{\mathsf {Setup}}}$ and $q_{{\mathsf {Enc}}}$ are upper-bounds on the number of RO queries made during ${\mathsf {Setup}}$ and ${\mathsf {Encrypt}}$, respectively. Thus, $e^{-n_{{\mathsf {eval}}}/32|Q|}$ is at most $e^{-\lambda }$.

• If $\rho _z < 1/32|Q|$ then expected value of $\sum _{i \in [n_{{\mathsf {test}}}]} X_{i, z}$ is at most $n_{{\mathsf {test}}}/32|Q|$. Using Chernoff bounds we can argue that,

  $$\begin{aligned} \Pr \left[ \sum _{i \in [n_{{\mathsf {test}}}]} X_{i, z} > \frac{n_{{\mathsf {test}}}}{16|Q|} \right] < e^{-\frac{1}{3} \cdot \frac{n_{{\mathsf {test}}}}{32|Q|}}. \end{aligned}$$

  We know that $n_{{\mathsf {test}}}\ge n_{{\mathsf {eval}}}$. Thus, $e^{-\frac{1}{3} \cdot \frac{n_{{\mathsf {test}}}}{32|Q|}}$ is at most $e^{-\lambda }$ as well.

Claim 2

$\Pr \left[ {\mathsf {Bad}}\text {-}2 \right] \le 1/4$.

Proof

Fix any random oracle ${\mathcal {O}}$, the randomness used in ${\mathsf {Setup}}^{{\mathcal {O}}}(1^{\lambda })$, the circuits $C_1, \ldots , C_{n_{{{\mathsf {key}}}}}$ chosen in the key query phase, and the randomness used in ${\mathsf {KeyGen}}^{{\mathcal {O}}}({\mathsf {msk}}, C_i)$ for $i \in [n_{{{\mathsf {key}}}}]$. This, in particular, fixes secret keys ${\mathsf {sk}}_1, \ldots , {\mathsf {sk}}_{n_{{{\mathsf {key}}}}}$ and the set ${{\mathsf {S}}} \text {-}{\mathsf {RO}}_{\mathrm {keys}}$. Consider the following experiment: $x {\mathop {\leftarrow }\limits ^{{\mathrm{R}}}}\{0,1\}^{n(\lambda )}$, ${\mathsf {ct}}\leftarrow {\mathsf {Encrypt}}^{\mathcal {O}}({\mathsf {pk}}, x)$, and decrypt ${\mathsf {ct}}$ using ${\mathsf {sk}}_i$ for $i\in [n_{{\mathsf {eval}}}+1, n_{{{\mathsf {key}}}}]$. Let ${\hat{\rho }}_z$ be the probability that at least $n_{{\mathsf {test}}}/16|{\hat{Q}}|$ of the decryptions make an RO query on z, where ${\hat{Q}} = {{\mathsf {S}}} \text {-}{\mathsf {RO}}_{\mathrm {keys}}$.

Let $Y_{j, z}$ be an indicator variable that is 1 iff an RO query on z is made in at least $n_{{\mathsf {test}}}/16|{\hat{Q}}|$ of the decryptions of ${\mathsf {ct}}_j$ with keys ${\mathsf {sk}}_{n_{{\mathsf {eval}}}+1}, \ldots , {\mathsf {sk}}_{n_{{{\mathsf {key}}}}}$ in the first phase of RO query collection. Note that the ciphertexts ${\mathsf {ct}}_1, \ldots , {\mathsf {ct}}_{n_{{\mathsf {enc}}}}$ are generated independently by choosing $x_1, \ldots , x_{n_{{{\mathsf {key}}}}}$ uniformly at random, and the decryption coins are also chosen independently for each decryption. Thus for any z, the variables $Y_{1, z}, \ldots , Y_{n_{{\mathsf {enc}}}, z}$ are independent of each other, and $\Pr \left[ Y_{j, z} = 1 \right] = {\hat{\rho }}_z$ for every j. In a similar way, we can also define a random variable $Y^*_z$ that indicates whether an RO query on z is made in at least $n_{{\mathsf {test}}}/16|{\hat{Q}}|$ of the decryptions of ${\mathsf {ct}}^*$ with keys ${\mathsf {sk}}_{n_{{\mathsf {eval}}}+1}, \ldots , {\mathsf {sk}}_{n_{{{\mathsf {key}}}}}$ in the test phase. $Y^*_z$ is independent of $Y_{1, z}, \ldots , Y_{n_{{\mathsf {enc}}}, z}$ and $\Pr \left[ Y^*_z = 1 \right] = {\hat{\rho }}_z$.

In a manner similar to the previous claim, we can argue that

$$\begin{aligned} \Pr \left[ \sum _{i \in [n_{{\mathsf {test}}}]} {\mathsf {I}}\text {-}{\mathsf {Dec}}\text {-}2_i > \frac{n_{{\mathsf {test}}}}{16} \right] \quad \le \quad \sum _{z \in {\hat{Q}}} \Pr \left[ z \notin {{\mathsf {S}}} \text {-}{\mathsf {RO}}_{\varGamma \text {-}1} \wedge Y^*_z = 1 \right] \end{aligned}$$

If $z \notin {{\mathsf {S}}} \text {-}{\mathsf {RO}}_{\varGamma \text {-}1}$, then none of the decryptions in the first phase of RO collection make a query on z. In particular, the variables $Y_{1, z}, \ldots , Y_{n_{{\mathsf {enc}}}, z}$ are all zero in such a case. Therefore,

$$\begin{aligned} \Pr \left[ z \notin {{\mathsf {S}}} \text {-}{\mathsf {RO}}_{\varGamma \text {-}1} \wedge Y^*_z = 1 \right]&\le \Pr \left[ Y_{1, z} = 0 \wedge \ldots \wedge Y_{n_{{\mathsf {enc}}}, z} = 0 \wedge Y^*_z = 1 \right] \\&= \Pr \left[ Y^*_z = 1 \right] \quad \cdot \prod _{j \in [n_{{\mathsf {enc}}}]} \Pr \left[ Y_{j, z} = 0 \right] \\&= {\hat{\rho }}_z (1 - {\hat{\rho }}_z)^{n_{{\mathsf {enc}}}} \end{aligned}$$

Once again we have two cases. If ${\hat{\rho }}_z \le 1/4|{\hat{Q}}|$, then ${\hat{\rho }}_z (1 - {\hat{\rho }}_z)^{n_{{\mathsf {enc}}}}$ is at most $1/4|{\hat{Q}}|$ as well. Otherwise, $(1 - {\hat{\rho }}_z)^{n_{{\mathsf {enc}}}} \le e^{-n_{{\mathsf {enc}}}/4|{\hat{Q}}|} \le e^{-\lambda }$ because, recall that, $n_{{\mathsf {enc}}}$ is set to be $4 \lambda \cdot n_{{{\mathsf {key}}}}\cdot q_{{\mathsf {KeyGen}}}$, where $q_{{\mathsf {KeyGen}}}$ is an upper-bound on the number of RO queries made during ${\mathsf {KeyGen}}$. As a result, $\sum _{z \in {\hat{Q}}} {\hat{\rho }}_z (1 - {\hat{\rho }}_z)^{n_{{\mathsf {enc}}}}$ is at most 1/4.

5.3 Ideal World Analysis

Next, we will show that any for ${\mathsf {PPT}}$ simulator, our adversary ${\mathcal {A}}= ({\mathcal {A}}_1, {\mathcal {A}}_2)$ outputs 1 in the ideal world with negligible probability. Let t be a polynomial in $\lambda$ such that $t = \ell _{{\mathsf {ct}}} + n_{{\mathsf {eval}}}\cdot q_{{\mathsf {Dec}}}\cdot m$ (so that $n_{{\mathsf {test}}}= 16t$) where, recall that, $\ell _{\mathsf {ct}}$ is the maximum length of any ciphertext generated by ${\mathsf {Encrypt}}$. Note that $q_{{\mathsf {Dec}}}\cdot m$ is the maximum number of bits obtained through the random oracle during any decryption, $n_{{\mathsf {eval}}}\cdot q_{{\mathsf {Dec}}}\cdot m$ is the maximum number of bits sent to the adversary during the second RO query collection phase, and $\ell _{{\mathsf {ct}}} + n_{{\mathsf {eval}}}\cdot q_{{\mathsf {Dec}}}\cdot m$ is the total number of bits the adversary receives after sending the challenge message.

Lemma 3

If ${\mathcal {C}}= \left\{ {\mathcal {C}}_{\lambda }\right\} _\lambda$ is an (16t, t, 1/8) approximately incompressible circuit family, then for any ${\mathsf {PPT}}$ simulator ${\mathcal {S}}$, the adversary ${\mathcal {A}}= ({\mathcal {A}}_1, {\mathcal {A}}_2)$ outputs 1 with probability at most ${\mathsf {negl}}(\lambda )$.

Proof

Suppose there exists a simulator ${\mathcal {S}}$ such that our adversary ${\mathcal {A}}$ outputs 1 with a non-negligible probability $\eta$. We will use ${\mathcal {S}}$ to show that ${\mathcal {C}}$ is (16t, t, 1/8) approximately compressible. In particular, we will use ${\mathcal {S}}$ and ${\mathcal {A}}= ({\mathcal {A}}_1, {\mathcal {A}}_2)$ to construct ${\mathsf {Cmp}}$ and ${\mathsf {DeCmp}}$ circuits satisfying the three properties of an approximately compressible circuit family.

Note that ${\mathcal {A}}_1$ picks $C_{n_{{\mathsf {eval}}}+1}, \ldots , C_{n_{{\mathsf {eval}}}+n_{{\mathsf {test}}}}$ and $x^*$ uniformly at random and independent of its other choices. Let $r_{\mathcal {S}}$ and $r_{\mathcal {A}}$ denote the randomness used by the simulator ${\mathcal {S}}$ and adversary ${\mathcal {A}}$ (in choosing circuits $C_1, \ldots , C_{n_{{\mathsf {eval}}}}$, and in RO query collection 1 and test phases), respectively. The compression circuit takes as input ($C_1$, $\ldots$, $C_{16t}$, $y_1$, $\ldots$, $y_{16t}$), has a randomly chosen string for $r_{\mathcal {S}}$ and $r_{\mathcal {A}}$ hardwired, and works as follows:

• Use ${\mathcal {S}}$ to generate a public key ${\mathsf {pk}}$. Give ${\mathsf {pk}}$ to ${\mathcal {A}}_1$.

• Use ${\mathcal {S}}$ to generate secrets keys ${\mathsf {sk}}_1$, $\ldots$, ${\mathsf {sk}}_{n_{{{\mathsf {key}}}}}$ for $C'_1$, $\ldots$, $C'_{n_{{\mathsf {eval}}}}$, $C_1$, $\ldots$, $C_{16t}$, where $C'_1$, $\ldots$, $C'_{n_{{\mathsf {eval}}}}$ are sampled using $r_{\mathcal {A}}$. Give the secret keys to ${\mathcal {A}}_1$.

• Run the first phase of RO query collection. When ${\mathcal {A}}_1$ makes an RO query in this phase, forward it to ${\mathcal {S}}$. Give ${\mathcal {S}}$’s response back to ${\mathcal {A}}_1$.

• Provide $y_1, \ldots , y_{16t}$ to ${\mathcal {S}}$. It generates a ciphertext ${\mathsf {ct}}^*$.

• Run the second phase of RO query collection. Respond to ${\mathcal {A}}_2$’s RO queries in the same way as before. Let $z_1, \ldots , z_v$ be the responses in order, where $z_i \in \{0,1\}^m$.

• Output ${\mathsf {ct}}^*$ and $z_1, \ldots , z_v$.

The decompression circuit takes $C_1, \ldots , C_{16t}$ and the compressed string ${\mathsf {str}}\text {-}{\mathsf {cmp}}$ as inputs, which can be parsed as ${\mathsf {str}}\text {-}{\mathsf {cmp}}= ({\mathsf {ct}}^*, \left\{ z_i\right\} )$. It also has the random value chosen before for $r_{\mathcal {S}}$ and $r_{\mathcal {A}}$ hardwired, and works as follows:

• Use ${\mathcal {S}}$ to generate ${\mathsf {pk}}$ and secret keys ${\mathsf {sk}}_1, \ldots , {\mathsf {sk}}_{n_{{{\mathsf {key}}}}}$ as before. Give both to ${\mathcal {A}}_1$.

• Run the first phase of RO query collection. Respond to ${\mathcal {A}}_1$’s RO queries in the same way as before. Let $\varGamma$ be the list of RO queries and responses recorded in this phase.

• Run the second phase of RO query collection, where ${\mathsf {sk}}_1, \ldots , {\mathsf {sk}}_{n_{{\mathsf {eval}}}}$ are used to decrypt ${\mathsf {ct}}^*$. The RO responses required in this step are available as part of the input ($z_1, \ldots , z_v$). They are also added to $\varGamma$.

• Run the test phase with the help of $\varGamma$. Let $y'_i$ denote the outcome of decrypting ${\mathsf {ct}}^*$ with ${\mathsf {sk}}_{n_{{\mathsf {eval}}}+i}$ for $i \in [n_{{\mathsf {test}}}]$.

• Output $y'_1, \ldots , y'_{16t}$.

First, note that the size of both compression and decompression circuit is bounded by a polynomial in $\lambda$. Next, the output length of the compression circuit is at most $\ell _{\mathsf {ct}}+ v \cdot m$, but v is no more than $n_{{\mathsf {eval}}}\cdot q_{{\mathsf {Dec}}}$. Thus the output length is bounded by t.

Finally, we need to show that the decompression property works with probability $\eta$. When $C_1, \ldots , C_{16t}$ are chosen uniformly at random and $y_1, \ldots , y_{16t}$ is the evaluation of these circuits on a randomly chosen point, then it is easy to see that the decompression circuit emulates the ideal world experiment perfectly. We know that ${\mathcal {A}}_2$ outputs 1 if and only if for at least 7/8th of the decryptions, $y'_i = y_i$. Hence, if 1 is output with probability $\eta$, then the hamming distance of ${\mathsf {DeCmp}}(\left\{ C_i\right\} , {\mathsf {Cmp}}(\left\{ C_i\right\} , \left\{ y_i\right\} ))$ and $\left\{ y_i\right\}$ is at most 1/8 with probability at least $\eta$.

6 Simulation Secure FE for Bounded Collusions

In this section, we will show an FE scheme that is $(q_1, {\mathsf {poly}}, q_2)$ simulation secure in the random oracle model, where $q_1, q_2$ are a-priori fixed polynomials. Since both the pre-challenge and post-challenge queries are bounded, we will simply refer to the total number of key queries. An FE scheme is q-key ${\mathsf {poly}}$-ciphertext secure if it is $(q_1, {\mathsf {poly}}, q_2)$ simulation secure as in Definition 8 for all non-negative integers $q_1, q_2$ s.t. $q_1 + q_2 = q$. We first show a scheme that can handle 1 key query in Sect. 6.1. Then, in Sect. 6.2 (and the full version of our paper [1]), we show how to transform a 1-key ${\mathsf {poly}}$-ciphertext scheme to one that is q-key ${\mathsf {poly}}$-ciphertext simulation secure for an a-priori fixed q, by first building a scheme for log-depth circuits and then for all poly-size circuits. This transformation is very similar to the one showed by Gorbunov et al. [21], except that they dealt with only one ciphertext.

6.1 Simulation Secure FE for One Key Query

We will now describe our 1-key ${\mathsf {poly}}$-ciphertext scheme. Recall that in the standard model, it is impossible to have simulation security even for IBE if the adversary is allowed to query for an unbounded number of ciphertexts, followed by one adaptive key query [5, 12]. Here, we show how the random oracle can be used to bypass this impossibility result. At a high-level, the construction is similar to the Sahai-Seyalioglu [31] construction of single-key secure FE from PKE.

Let ${\mathcal {C}}= \left\{ {\mathcal {C}}_{\lambda }\right\} _{\lambda }$ be a class of circuits, where each circuit $C \in {\mathcal {C}}_{\lambda }$ takes an $n(\lambda )$ bit input and produces an $m(\lambda )$ bit output, and can be represented using $t(\lambda )$ bits. For $x \in \{0, 1\}^{n(\lambda )}$, let $U^{(\lambda )}_x$ be a universal circuit that takes any $C \in {\mathcal {C}}_{\lambda }$ as input and outputs C(x). Let ${\mathcal {U}}= \left\{ {\mathcal {U}}_{\lambda }\right\} _{\lambda }$ be a circuit family such that ${\mathcal {U}}_\lambda = \{U^{(\lambda )}_x \, | \, x \in \{0, 1\}^{n(\lambda )}\}$. Our one-bounded FE scheme ${\mathsf {One}}\text {-}{\mathsf {FE}}= ({\mathsf {Setup}}, {\mathsf {Encrypt}}, {\mathsf {KeyGen}}, {\mathsf {Decrypt}})$ uses a decomposable randomized encoding scheme $({\mathsf {RE.Encode}}, {\mathsf {RE.Decode}})$ for ${\mathcal {U}}$ and a public key encryption scheme ${\mathsf {PKE}}= ({\mathsf {Setup}}_{\mathrm{PKE}}, {\mathsf {Enc}}_{\mathrm{PKE}}, {\mathsf {Dec}}_{\mathrm{PKE}})$ that can operate on messages of length $\lambda$. For simplicity of presentation, we will skip the dependence on $\lambda$.

• ${\mathsf {Setup}}(1^{\lambda }) \rightarrow ({{\mathsf {mpk}}}, {\mathsf {msk}})$: The setup algorithm chooses 2t ${\mathsf {PKE}}$ public key/secret key pairs $({\mathsf {pk}}_{i,b}, {\mathsf {sk}}_{i,b}) \leftarrow {\mathsf {Setup}}_{\mathrm{PKE}}(1^{\lambda })$ for $i \in [t], b \in \{0,1\}$. It sets ${{\mathsf {mpk}}}= \left\{ {\mathsf {pk}}_{i,b}\right\} _{i\in [t], b \in \{0,1\}}$ and ${\mathsf {msk}}= \left\{ {\mathsf {sk}}_{i,b}\right\} _{i\in [t], b \in \{0,1\}}$.

• ${\mathsf {Enc}}({{\mathsf {mpk}}}, x) \rightarrow {\mathsf {ct}}$: The encryption algorithm first chooses 2t random strings $r_{i,b}\leftarrow \{0,1\}^{\lambda }$ for all $i \in [t]$, $b \in \{0,1\}$. Next, it computes a randomized encoding for the universal circuit $U_x$, i.e., $\left\{ w_{i,b}\right\} _{i\in [t], b \in \{0,1\}} \leftarrow {\mathsf {RE.Encode}}(1^\lambda , U_x)$. Now, let ${\mathsf {ct}}_{i,b}= {\mathsf {Enc}}_{\mathrm{PKE}}({\mathsf {pk}}_{i,b}, r_{i,b})$ and ${\widetilde{{\mathsf {ct}}}}_{i,b}= w_{i,b}\oplus {\mathcal {O}}(r_{i,b})$ for all $i \in [t]$, $b \in \{0,1\}$. The algorithm outputs ${\mathsf {ct}}= \left\{ {\mathsf {ct}}_{i,b}, {\widetilde{{\mathsf {ct}}}}_{i,b}\right\} _{i \in [t], b \in \{0,1\}}$.

• ${\mathsf {KeyGen}}({\mathsf {msk}}, C) \rightarrow {\mathsf {sk}}_C$: Let $\left( \beta _1, \ldots , \beta _t \right)$ be the bit representation of circuit C. The key generation algorithm outputs $\left\{ {\mathsf {sk}}_{i, \beta _i}\right\} _{i \in [t]}$ as the secret key for C.

• ${\mathsf {Dec}}({{\mathsf {mpk}}}, {\mathsf {sk}}_C, {\mathsf {ct}})$: Let ${\mathsf {sk}}_C = \left\{ {\mathsf {sk}}_{i, \beta _i}\right\} _{i \in [t]}$ and ${\mathsf {ct}}= \left\{ {\mathsf {ct}}_{i,b}, {\widetilde{{\mathsf {ct}}}}_{i,b}\right\} _{i \in [t], b \in \{0,1\}}$. The decryption algorithm first decrypts the relevant randomized encoding components, i.e., for each $i\in [t]$, it computes $r_{i,\beta _i}= {\mathsf {Dec}}_{\mathrm{PKE}}({\mathsf {sk}}_{i, \beta _i}, {\mathsf {ct}}_{i, \beta _i})$ and $w_{i,\beta _i}= {\widetilde{{\mathsf {ct}}}}_{i,\beta _i}\oplus {\mathcal {O}}(r_{i,\beta _i})$. Finally, it outputs ${\mathsf {RE.Decode}}(\left\{ w_{i,\beta _i}\right\} _{i \in [t]})$.

The correctness of our scheme follows directly from the correctness of the randomized encoding scheme and the public key encryption scheme.

The simulator description and proof of security is given in the full version of our paper [1].

6.2 Simulation Secure FE with Bounded Key Queries for NC1

In this section, we will show how to transform a scheme that handles one key query to one that handles a bounded number of key queries for the class of log-depth circuits. This transformation is identical to the one in [21]. However, the proof is slightly different because we handle unbounded challenge ciphertext queries.

Formal Description. Let ${\mathcal {C}}= \left\{ {\mathcal {C}}_{\lambda }\right\} _{\lambda }$ be a class of circuits, where each circuit $C \in {\mathcal {C}}_{\lambda }$ takes $n(\lambda )$ bit inputs, outputs a single bit and can be represented using an $n(\lambda )$ variate polynomial of degree $D(\lambda )$ over a (large enough) field ${\mathbb {F}}$. Let q denote a bound on the number of secret key queries. Our FE scheme ${\mathsf {FE}}= ({\mathsf {Setup}}, {\mathsf {Enc}}, {\mathsf {KeyGen}}, {\mathsf {Dec}})$ uses a 1-key ${\mathsf {poly}}$-ciphertext simulation secure FE scheme $({\mathsf {Setup}}_{\mathrm {one}}$, ${\mathsf {Encrypt}}_{\mathrm {one}}$, ${\mathsf {KeyGen}}_{\mathrm {one}}$, ${\mathsf {Decrypt}}_{\mathrm {one}})$ as a building block. Our scheme is parameterized by four polynomials: N, S, v and t, whose values depend on D and q. As in GVW, we set $t(\lambda ) = \varTheta (q^2 \lambda )$, $N(\lambda ) = \varTheta (N^2 q^2 t)$ and $v(\lambda ) = \varTheta (\lambda )$ and $S(\lambda ) = \varTheta (v q^2)$. We will skip the dependence on $\lambda$ when it is clear from the context.

For any circuit $C \in {\mathcal {C}}_{\lambda }$ and set $\varDelta \subset [S]$, we define a circuit $G_{C, \varDelta }$ which takes $n+S$ bit inputs and works as follows:

$$\begin{aligned} G_{C, \varDelta }(x_1, \ldots , x_{n}, y_1, \ldots , y_S) = C(x_1, \ldots , x_n) + \sum _{h \in \varDelta } y_h \end{aligned}$$

Let ${\mathcal {O}}= {\mathcal {O}}_1 \times \ldots {\mathcal {O}}_N$ be a hash function, where each ${\mathcal {O}}_i : \{0,1\}^{\ell } \rightarrow \{0,1\}^{m}$. Each of these hash functions ${\mathcal {O}}_i$ will be modeled as a random oracle in our security proof.

• ${\mathsf {Setup}}^{{\mathcal {O}}}(1^{\lambda }) \rightarrow ({\mathsf {MPK}}, {\mathsf {MSK}})$: The setup algorithm runs the one-key FE scheme’s setup N times. Let $({{\mathsf {mpk}}}_i, {\mathsf {msk}}_i) \leftarrow {\mathsf {Setup}}_{\mathrm {one}}^{{\mathcal {O}}_i}(1^{\lambda })$. The master public key ${\mathsf {MPK}}$ is set to be $\left\{ {{\mathsf {mpk}}}_i\right\} _{i\in [N]}$, and the master secret key ${\mathsf {MSK}}$ is $\left\{ {\mathsf {msk}}_i\right\} _{i \in [N]}$.

• ${\mathsf {Enc}}^{{\mathcal {O}}}({\mathsf {MPK}}, x) \rightarrow {\mathsf {ct}}$: Let ${\mathsf {MPK}}= \left\{ {{\mathsf {mpk}}}_i\right\} _{i\in [N]}$ and $x = (x_1,\ldots , x_n)$. The encryption algorithm works as follows:

  • It chooses n uniformly random polynomials $\mu _1, \ldots , \mu _n$ of degree t over field ${\mathbb {F}}$ subject to the constraint that the constant term of $\mu _i$ is $x_i$.

  • It chooses S uniformly random polynomials $\zeta _1$, $\ldots$, $\zeta _S$ of degree Dt over field ${\mathbb {F}}$ and constant term 0.

  • It computes N ciphertexts using the ${\mathsf {Encrypt}}_{\mathrm {one}}$ algorithm. For $i\in [N]$, it computes ${\mathsf {ct}}_i \leftarrow {\mathsf {Encrypt}}_{\mathrm {one}}^{{\mathcal {O}}_i}({{\mathsf {mpk}}}_i, (\mu _1(i), \ldots , \mu _n(i), \zeta _1(i), \ldots , \zeta _S(i)))$.

  The encryption algorithm outputs $({\mathsf {ct}}_1, \ldots , {\mathsf {ct}}_N)$ as the final ciphertext.

• ${\mathsf {KeyGen}}^{{\mathcal {O}}}({\mathsf {MSK}}, C)$: Let ${\mathsf {MSK}}= \left\{ {\mathsf {msk}}_i\right\} _{i\in [N]}$. The key generation algorithm works as follows:

  • It chooses a uniformly random set $\varGamma \subset [N]$ of size $Dt+1$.

  • It chooses a uniformly random set $\varDelta \subset [S]$ of size v.

  • It uses the ${\mathsf {KeyGen}}_{\mathrm {one}}$ algorithm to generate $Dt+1$ secret keys for the function $G_{C, \varDelta }$. For $i \in \varGamma$, it computes ${\mathsf {sk}}_i \leftarrow {\mathsf {KeyGen}}_{\mathrm {one}}^{{\mathcal {O}}_i}({\mathsf {msk}}_i, G_{C,\varDelta })$.

  The key generation algorithm outputs $(\varGamma , \varDelta , \left\{ {\mathsf {sk}}_i\right\} _{i\in \varGamma })$ as the secret key for C.

• ${\mathsf {Dec}}^{{\mathcal {O}}}({\mathsf {sk}}, {\mathsf {ct}})$: Let ${\mathsf {sk}}= (\varGamma , \varDelta , \left\{ {\mathsf {sk}}_i\right\} _{i \in \varGamma })$ and ${\mathsf {ct}}= ({\mathsf {ct}}_1, \ldots , {\mathsf {ct}}_N)$. The decryption algorithm works as follows:

  • For each $i\in \varGamma$, let $\alpha _i = {\mathsf {Decrypt}}_{\mathrm {one}}^{{\mathcal {O}}_i}({\mathsf {sk}}_i, {\mathsf {ct}}_i)$.

  • It computes a polynomial $\eta$ of degree Dt over field ${\mathbb {F}}$ such that for all $i\in \varGamma$, $\eta (i) = \alpha _i$.

  The decryption algorithm outputs $\eta (0^{n+S})$ as the final decryption.

Correctness. The correctness proof is identical to the one in [21]. Let $\mu _1$, $\ldots$, $\mu _n$, $\zeta _1$, $\ldots$, $\zeta _S$ be the polynomials chosen during encryption, and let $\varGamma , \varDelta$ be the sets chosen during key generation. From the correctness of the one-key FE scheme, it follows that the decryption algorithm computes $\alpha _i = C(\mu _1(i), \ldots , \mu _n(i)) + \sum _{j \in \varDelta } \zeta _j(i)$ for all $i \in \varGamma$. Now, since the polynomial $\eta = C(\mu _1, \ldots , \mu _n) + \sum _{j \in \varGamma } \zeta _j$ has degree Dt and $|\varGamma | = Dt+1$, the decryption algorithm can compute the polynomial $\eta$ using the set $\left\{ \alpha _i\right\} _{i\in [N]}$. Finally, note that $\eta (0^{n+S}) = C(\mu _1(0), \ldots , \mu _n(0)) + \sum _j \zeta _j(0) = C(x_1, \ldots , x_n)$.

In the full version of our paper [1], we prove security of our scheme for NC1 and describe how this scheme can be bootstrapped to all poly-size circuits.