Dynamic Collusion Bounded Functional Encryption from Identity-Based Encryption

Abstract

Functional Encryption is a powerful notion of encryption in which each decryption key is associated with a function f such that decryption recovers the function evaluation f(m). Informally, security states that a user with access to function keys $\mathsf {sk}_{f_1}, \mathsf {sk}_{f_2}, \ldots$ (and so on) can only learn $f_1(m), f_2(m), \ldots$ (and so on) but nothing more about the message. The system is said to be q-bounded collusion resistant if the security holds as long as an adversary gets access to at most $q = q(\lambda )$ function keys. A major drawback of such statically bounded collusion systems is that the collusion bound q must be declared at setup time and is fixed for the entire lifetime of the system.

We initiate the study of dynamically bounded collusion resistant functional encryption systems which provide more flexibility in terms of selecting the collusion bound, while reaping the benefits of statically bounded collusion FE systems (such as quantum resistance, simulation security, and general assumptions). Briefly, the virtues of a dynamically bounded scheme can be summarized as:

• Fine-grained individualized selection. It lets each encryptor select the collusion bound by weighing the trade-off between performance overhead and the amount of collusion resilience.

• Evolving encryption strategies. Since the system is no longer tied to a single collusion bound, thus it allows to dynamically adjust the desired collusion resilience based on any number of evolving factors such as the age of the system, or a number of active users, etc.

• Ease and simplicity of updatability. None of the system parameters have to be updated when adjusting the collusion bound. That is, the same key $\mathsf {sk}_f$ can be used to decrypt ciphertexts for collusion bound $q = 2$ as well as $q = 2^\lambda$.

We construct such a dynamically bounded functional encryption scheme for the class of all polynomial-size circuits under the general assumption of Identity-Based Encryption.

R. Goyal—Research supported in part by NSF CNS Award #1718161, an IBM-MIT grant, and by the Defense Advanced Research Projects Agency (DARPA) under Contract No. HR00112020023. Any opinions, findings and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the United States Government or DARPA.

B. Waters—Supported by NSF CNS-1908611, CNS-1414082, Packard Foundation Fellowship, and Simons Investigator Award.

1 Introduction

Public-key encryption [18] is one of the most fundamental concepts in cryptography. Traditionally, public-key encryption was defined to provide an “all-or-nothing” type functionality and security, where given a decryption key $\mathsf {sk}$, a user can either recover the entire plaintext m from a ciphertext $\mathsf {ct}$ or nothing at all. In the recent years, an extremely powerful notion of encryption called Functional Encryption (FE) [11, 32] has emerged.

FE provides a fine-grained access control mechanism over encrypted data where a decryption key is now associated with a function f and the decryptor recovers the function evaluation f(m) from the ciphertext. Moreover, a user with access to function keys $\mathsf {sk}_{f_1}, \ldots , \mathsf {sk}_{f_n}$ can only learn $f_1(m), \ldots , f_n(m)$ but nothing more about the message. This security requirement is commonly captured in a game based indistinguishability definition, where the adversary submits two messages, $m_0$ and $m_1$, as a challenge and must be unable to distinguish between encryptions of $m_0$ and $m_1$ with non-negligible probability given that $f_i(m_0) = f_i(m_1)$ hold for all keys in adversary’s possession.

Over the last several years, FE has been studied extensively. Significant progress has been made towards building various expressive forms of FE under such indistinguishability-based definitions. Starting with initial works [12, 29] that built specific forms of predicate encryption over bilinear maps, the search for FE for general circuits under standard cryptographic assumptions culminated in the recent breakthrough work of Jain, Lin, and Sahai [28]. They proposed an FE scheme for general circuits from a combination of PRGs in $\mathbf{NC} ^0$, Symmetric eXternal Diffie-Hellman (SXDH), Learning with Errors (LWE), and Learning Parity with Noise (LPN) over large fields assumptions. While this is tremendous progress, an unfortunate limitation of this FE scheme is that it is susceptible to quantum attacks due to the post-quantum insecurity of the SXDH assumption. But even more broadly, pursuing the direction of indistinguishability-based security for FE suffers from the drawback that it is unclear how it captures the intuition that an attacker learns at most the function evaluation but nothing more.

For these reasons, FE has also been investigated in the bounded collusion model under simulation-based definitions. In the bounded collusion model, the FE system declares a bound q at the setup time, such that all the system parameters are allowed to grow polynomially with q (in addition to the security parameter $\lambda$). Additionally, the security requirement is captured via a simulation-based game, which says that as long as the attacker does not make more than q key queries, the adversary’s view - which includes the ciphertext $\mathsf {ct}_m$ and function keys $\mathsf {sk}_{f_1}, \ldots , \mathsf {sk}_{f_q}$ - can be “simulated” given only the function evaluations $f_1(m), \ldots , f_q(m)$ and nothing more about m. Although this more closely captures the intuition behind FE, if the attacker corrupts more than q keys, then no security is provided. Despite its limitations, the bounded collusion model for FE has been very useful in various contexts such as proving negative results in differential privacy [30], applications to tracing [15, 26], etc. In some cases, it is the only currently known pathway to certain applications in the post-quantum regime. A notable feature of the bounded collusion model is that under them, FE can be built from the minimal assumption of public-key encryption (and OWFs in case of private-key FE) as studied in a long line of works [1, 4, 7, 15, 24, 26, 31].

The Question. A major drawback of such bounded collusion FE systems is that the setup authority needs to declare the collusion bound q at the very beginning, and the bound q is fixed, once and for all, for the entire lifetime of the system. This puts the authority in a difficult situation, as it requires an incredible amount of foresight at the setup time. In particular, if the authority sets the bound q lower than the eventual number of compromised keys, then the system will be insecure; whereas overestimating the bound q would result in significant performance overhead. Now when the collusion bound is breached, the only option is to do a fresh setup and redistribute the keys which is at best inefficient, and possibly infeasible in certain scenarios. Switching to the state-of-the-art fully collusion resistant FE schemes would suffer from drawbacks discussed above.

With the aforementioned limitations of existing FE systems, we ask the following –

Can we build an FE system for general circuits that reaps the benefits of bounded collusion FE systems – post-quantum security, simulation security, and general assumptions – while at the same time provide more flexibility to the authority in terms of selecting the collusion bound? And, would such an FE system lead to results in the domain of full collusion resistance?

In this work, we study the above question. We answer the first part in affirmative by introducing a new flexible corruption model that we call the “dynamic collusion” model, and building a simulation secure FE system in the dynamic collusion model from the general assumption of Identity-Based Encryption (IBE) [10, 16, 34] (for which we have quantum-safe instantiations [2, 14, 22]). Since it is widely believed that the FE for general circuits is significantly more expressive than plain IBE, this seems to answer the latter part negatively. Concurrently¹, the authors of [3] noticed the same gaps and limitations in bounded-collusion FE security, and defined a similar dynamic collusion model. For a more detailed comparison of the concurrent work, refer to Sect. 1.3.

Defining Dynamically Bounded Collusion Resistance

In this work, we refer to the traditional notion of bounded collusion resistance for FE as statically bounded collusion resistance. Recall that, syntactically, a statically bounded FE is defined exactly as fully collusion resistant FE, that is using four polynomial time algorithms – $\mathsf {Setup}$, $\mathsf {KeyGen}$, $\mathsf {Enc}$, and $\mathsf {Dec}$ – except the $\mathsf {Setup}$ algorithm now additionally takes the target collusion bound q as an input. As mentioned previously, declaring the collusion bound q upfront lets the setup authority set up the system parameters with enough redundancy, and this typically leads to the running time and sizes of all system parameters (i.e., the keys and ciphertexts) to grow polynomially with q.

In the dynamic collusion model, the $\mathsf {Setup}$ algorithm no longer takes the collusion bound as input, but instead the $\mathsf {Enc}$ algorithm selects the collusion bound per ciphertext. That is, the setup and key generation algorithms no longer depend on the collusion bound q, but only the encryptor needs to specify the collusion bound.² Basically, this lets the encryptor dynamically decide the size of set of colluding users against which it wants to hide its message. As a consequence, in the dynamic collusion model, only the size of the ciphertexts potentially grows with the collusion bound q, but the running times of the $\mathsf {Setup}$ and $\mathsf {KeyGen}$ algorithms (therefore the public and secret keys) are independent of q. The security requirement is again captured via a simulation-based game but where the admissibility constraints on the attacker are lifted such that the number of key queries the attacker is permitted can be adaptively specified at the time of committing the challenge m instead of beginning of the game as in the static model.

Our dynamic collusion model and its comparison with the static model is discussed in detail in Sect. 3. Below we briefly highlight the virtues of the dynamic collusion model.

• Fine-grained individualized selection. A dynamically bounded collusion FE scheme allows each user to select the collusion bound by weighing the trade-off between the performance overhead and amount of collusion resilience at encryption time. For example, depending upon the factors such as available computing resources, or the bandwidth on the communication channel, or the sensitivity of data etc., an encryptor might want to increase/decrease the amount of collusion resilience to better fit the computing/communication/privacy constraints.

• Evolving encryption strategies. Since the system is no longer statically tied to a single collusion bound at setup time, thus it allows to dynamically adjust the desired collusion resilience based on any number of evolving factors such as the age of the system, or number of active users etc. Thus, the authority does not need to have any foresight about the attackers at setup time in contrast to statically bounded collusion FE systems. (Of course the ciphertexts in which the collusion bound was exceeded will not be secure, but future attacks can be prevented by adapting to a larger collusion bound.)

• Ease and simplicity of updatability. While the above features are already highly desirable, a noteworthy property of these systems is that none of the parameters have to be updated when adjusting the collusion bound. That is, the same function key $\mathsf {sk}_f$ can be used to decrypt ciphertexts for collusion bound $q = 2$ as well as $q = 2^\lambda$ without requiring any updates. Also, the storage space for the parameters is bounded by a fixed polynomial in $\lambda$.

Next, we provide an overview of our approach and describe the technical ideas. Later on, we discuss some related works and open questions.

1.1 Technical Overview

In this section, we provide a high level overview of our new collusion framework and the corresponding FE construction. The overview is split into five parts which roughly correspond to the proceeding sections of the paper. First, we informally introduce the notion of dynamically bounded collusion resistant FE. Second, we define an efficiency property that we refer to as weak optimality for statically bounded collusion FE systems, and show that any weakly optimal FE construction could be generically lifted to a dynamically bounded collusion FE scheme. Next, we build such a weakly optimal FE scheme via the framework of tagged functional encryption scheme, where a tagged FE scheme is same as a regular FE scheme except each ciphertext and secret key is additionally embedded with a tag such that only ciphertexts and keys with the same tag can be combined together. Finally, we build a tagged FE scheme for statically bounded collusions in two steps – first, reduce the problem of constructing tagged FE with static collusions to the simpler setting of at most one key corruption (also referred to as 1-bounded collusion); and second, design a tagged FE system in the simpler setting directly from IBE.

Dynamic vs. Static Bounded Collusion Model

Let us start by recalling the syntax of functional encryption in the static collusion model. An FE scheme in the static collusion model consists of four algorithms with the following semantics:

• $\mathsf {Setup}$ takes as input the and samples the master public-secret key pair $(\mathsf {mpk}, \mathsf {msk})$.

• $\mathsf {KeyGen}$ generates a function key $\mathsf {sk}_f$ given function f and master key $\mathsf {msk}$.

• $\mathsf {Enc}$ encrypts a message m to a ciphertext $\mathsf {ct}$.

• $\mathsf {Dec}$ recovers f(m) from the ciphertext and decryption key.

In the dynamic collusion model, the collusion bound q is not fixed at the system setup, but instead the encryptor chooses the amount of collusion resilience it wants every time a fresh ciphertext is created. This is reflected with the following changes:

• $\mathsf {Setup}$ no longer takes the collusion bound q as an input.

• $\mathsf {Enc}$ takes for sampling the ciphertext.

Note that since the collusion bound q is not specified during setup or key generation at all, thus the efficiency condition for a dynamically bounded collusion FE scheme requires the running time of $\mathsf {Setup}$ and $\mathsf {KeyGen}$ to be fixed polynomials in $\lambda$, whereas in static setting they are allowed to grow polynomially with q.

Static to Dynamic via Weak Optimality

As we mentioned before, our first observation is that a dynamically bounded collusion FE scheme can be constructed from any statically bounded scheme if it satisfies a ‘weak optimality’ property. Intuitively, the weak optimality property says that the running time of the setup and key generation algorithms grows only poly-logarithmically in the collusion bound q.

Now looking closely at the notion of weakly-optimal statically bounded collusion FE, we observe that the major difference between this and a dynamic system is that the $\mathsf {Setup}$ algorithm requires q as an explicit input in the static setting, but not in the dynamic setting. Our idea to get around this is to exploit the efficiency property of the static scheme, where the dynamic collusion FE scheme essentially runs $\lambda$ independent instances of the static collusion FE scheme in parallel with geometrically increasing collusion bounds. That is, i-th subsystem (running a single instance of the static scheme) is set up with collusion bound $q_i = 2^i$. And, now the master public-secret key pair as well as each function key in the dynamic system contains $\lambda$ independently sampled keys where the i-th sub-key is sampled using the i-th static FE system. Since the encryption algorithm receives the target collusion bound q as input, thus the encryptor uniquely selects a static FE sub-system under which it encrypts the message. The target collusion bound to subsystem index mapping can simply be defined $i := \lceil \log q \rceil$ (i.e., nearest power of two). Note that setting up the system this way ensures the dynamic system achieves the desired efficiency. This is because the setup and key generation will be efficient (by weak optimality of the static FE scheme), and since $2^i = 2^{\lceil \log q \rceil } < 2 q$, thus the running time of encryption and decryption is a polynomial in q.

Since the above transformation is very natural, one would expect the simulation security of the resulting dynamic FE system to also follow directly from the simulation security of the underlying static FE schemes. However, this is not the case. To better understand the technical barrier, let us first consider the most natural simulation strategy described next. The simulator for the dynamic system simply runs the simulator for each of the underlying static systems in parallel, where the ciphertext simulator is only run for the static system corresponding to the adversarially selected challenge target collusion bound $q^{*}$. While this seems to compile, there are two subtle issues that need to be carefully handled.

First, the running time of each static FE simulator grows with the underlying collusion bound which grows as large as exponential in $\lambda$. For avoiding the problem of inefficient simulation, we additionally require the underlying static FE scheme to have weakly-optimal simulators as well which means that all but the ciphertext simulation phase of the static FE could be performed optimally (i.e., the simulator running time grows only poly-logarithmically in q). However, this is still not enough for proving simulation security. The reason is that typically the simulation security states that the distribution of secret keys and ciphertext are simulatable as long as the adversary does not make more key queries than what is specified by the static collusion bound. That is, if the adversary makes more key queries then no guarantee is provided. Now our dynamic FE simulator must invoke the underlying static FE simulator even for collusion bounds smaller than $q^{*}$, thus the standard simulation guarantee is insufficient. To get around this issue, we define a notion called strong simulation security for static-bounded-collusion FE schemes under which we require that the real and ideal worlds are also indistinguishable even when the adversary makes more key queries than that specified by the collusion bound as long as the adversary does not make any challenge message queries. More details are provided in Sect. 3.2.

From Tagged FE to Weak Optimality

Our next idea is to embed auxiliary tagging information inside each individual ciphertext and decryption key such that the auxiliary information is useful for achieving weak optimality generically by embedding information about the collusion bound inside the auxiliary information. Formally, in a tagged FE system, the semantics of encryption and key generation are changed as:

• $\mathsf {KeyGen}, \mathsf {Enc},$ both also take in a tag string $\mathsf {tg}$ as an input.

And, now the decryption algorithm recovers f(m) from the ciphertext and decryption key corresponding to tags $\mathsf {tg}_1, \mathsf {tg}_2$ (respectively) iff $\mathsf {tg}_1 = \mathsf {tg}_2$. Basically, the intuition behind a tagged FE scheme is to efficiently implement many parallel instances of a statically bounded collusion FE scheme such that the master public-secret keys do not grow with number of underlying (untagged) FE instances.

In other words, the idea behind tagged FE is to serve as an extension to regular (untagged) FE in the same way as IBE is to PKE, that is to capture the same master public-secret key compression properties. That is, a tagged FE enables compressing exponentially many parallel instances of untagged FE into a succinct system where all the system parameters are efficient, and the ciphertexts and decryption keys corresponding to each underlying untagged FE system can be efficiently computed given those parameters. In terms of simulation security for tagged FE, the property is a natural extension of statically bounded-collusion security model for FE to the tagged setting, where now the adversary is allowed to query keys and ciphertexts for an unbounded number of tags, and the simulation security must hold for all challenge ciphertexts (queried under separate tags) as long as the number of key queries does not exceed the collusion bound on any tag for which a challenge ciphertext is also requested.

Looking ahead, the benefit of a tagged FE scheme will be that we can distribute the final desired collusion bound over to the auxiliary tag space as well, and not just the collusion bound ingrained in the tagged FE system. And, since tagged FE can encode the tag space more efficiently than the collusion bound, thus this is useful for obtaining the desired weak optimality.

At a high level, to transform any tagged FE scheme into an FE scheme that satisfies the desired weak optimality property, we rely on the linearization trick by Ananth and Vaikuntanathan [7] where they suggested a generic compiler to improve efficiency of a statically bounded-collusion FE scheme from an arbitrary polynomial dependence on the collusion bound, q, to only a linear dependence. Our observation is that if we substitute all the underlying FE scheme in the linearization transformation from [7] with a single tagged FE scheme, then that would result in a statically bounded-collusion FE scheme with weak optimality.

Briefly, collusion bound linearization transformation simply consists of running q many parallel instances of the inefficient (untagged) FE scheme each, but with collusion bound set to be the security parameter ${\lambda }$. While for encrypting the message m, the ciphertext is computed as an encryption of m under each of the underlying FE schemes; the key generator only generated a decryption key for a random instance out of the q inefficient FE systems. By a standard balls and bins concentration argument, it was shown that, with all but negligible probability, the collusion bound of $\lambda$ was never crossed for any of the underlying FE system as long as only q many total key queries were made. We rely on the same idea for our weak optimality transformation wherein we simply replace the q many parallled untagged FE systems with a single tagged FE system, where now the i-th FE sub-scheme in the [7] transformation is set to be the sub-scheme corresponding to tag value i. The full transformation is provided later in Sect. 5.

Intuitively, we use the linearization trick to absorb the blow-up due to the collusion bound in the tag space of the FE scheme instead. This decouples the desired collusion bound, q, from the resulting FE scheme with the collusion bound fixed inside the underlying tagged FE system thereby allowing us to set the collusion bound for the tagged system to be simply $\lambda$. Thus, we can reason from the efficiency of the tagged FE scheme that the resulting scheme only has polylogarithmic dependence in the $\lambda$ for $\mathsf {Setup}$ and $\mathsf {KeyGen}$, making it weakly optimal.

Amplifying Collusion Bound in Tagged FE

The next component in our sequence of transformations is a generic collusion bound amplification procedure for tagged FE, in turn reducing the problem to constructing tagged FE for 1-bounded collusion instead. Our approach follows the general bootstrapping blueprint developed for upgrading collusion bound in untagged FE literature [7, 24] which runs a specific multiparty computation protocol in the head.

In such MPC protocols, there are $\mathsf {N}$ servers/parties and a single client with an input x with the computation proceeding in two phases – offline and online. In the offline phase, the client encodes its input x into $\mathsf {N}$ individual encodings – $\{\hat{x}^1, \ldots , \hat{x}^\mathsf {N}\}$ – one for each server. While in the online phase, a function f is encoded into $\mathsf {N}$ individual encodings – $\{\hat{f}^1, \ldots , \hat{f}^\mathsf {N}\}$ – such that i-th server learns the i-th function encoding, and any subset S of servers of size $\mathsf {p}$ can locally decode their individual encodings to obtain partial evaluations, $\hat{y}^i$ for $i \in S$, such that all these $\mathsf {p}$ partial evaluations can be publicly combined to compute the function evaluation f(x). And importantly, the security of the MPC protocol assures that, even if at most $\mathsf {t}$ servers get corrupted, no information other than actual value f(x) can be adversarially learned given the public partial evaluations. Now for applications to collusion bound amplification in FE, it is important to have MPC protocols in which the client can delegate the computation for multiple functions w.r.t. a single offline phase.

The high level idea is that each ciphertext encodes the message m into various different pieces where each piece corresponds to an individual offline encoding for a particular server, and now the key generator selects a random subset of servers for which it gives the appropriate function encodings for each selected server. In more detail, the bootstrapping procedure works as follows, where $\mathsf {1KeyFE}$ is any 1-bounded collusion untagged FE scheme:

• $\mathsf {Setup}$ samples $\mathsf {N}$ independent master public-secret key pair $(\mathsf {mpk}_i, \mathsf {msk}_i)$ for the $\mathsf {1KeyFE}$ scheme. These $\mathsf {N}$ key pairs are set as the master public-secret key pairs for this scheme respectively.

• $\mathsf {Enc}$ encodes the message m using the offline phase to compute encodings $\{\hat{x}^1,\ldots ,\hat{x}^\mathsf {N}\}$, and encrypts the i-th encoding under the i-th master public key, that is $\mathsf {ct}_i \leftarrow \mathsf {1KeyFE}.\mathsf {Enc}(\mathsf {mpk}_i, \hat{x}^i)$ for $i \in [\mathsf {N}]$, and outputs $(\mathsf {ct}_1, \ldots , \mathsf {ct}_\mathsf {N})$ as the full ciphertext.

• $\mathsf {KeyGen}$ selects a random subset $S \subseteq [\mathsf {N}]$ of size $\mathsf {p}$, and performs the online phase to compute $\{\hat{f}^1,\ldots ,\hat{f}^\mathsf {N}\}$. Now enable decryption, it creates a FE decryption key for each server $i \in S$ enabling the local circuit computation, that is $\mathsf {sk}_{f, i} \leftarrow \mathsf {1KeyFE}.\mathsf {KeyGen}(\mathsf {msk}_i, \mathsf {Local}(\hat{f}^i, \cdot ))$, and sets the final decryption key as these individual decryption keys $\mathsf {sk}_{f, i}$ for $i \in S$.

• $\mathsf {Dec}$ first recovers the partial evaluations $\hat{y}^i = \mathsf {Local}(\hat{f}^i,\hat{x}^i)$ for $i \in S$ by running the $\mathsf {1KeyFE}$ decryption, and then combines them to compute f(m).

It turns out that the above compiler amplifies the collusion bound from 1 to q if a simple combinatorial property, regarding the random sets $(S_1, \ldots , S_q)$ sampled for each key, is satisfied. Here $S_j \subseteq [\mathsf {N}]$ be the set sampled while anwering the j-th key query. Observe that whenever two sets $S_j, S_{j'}$ intersect at an index i, we learn two keys for the underlying $\mathsf {1KeyFE}$ scheme thereby breaking its security, and an adversary can completely learn the underlying encoding $\hat{x}^i$. And, if the security is broken for enough $\mathsf {1KeyFE}$ systems (i.e., $> \mathsf {t}$), then our MPC guarantee fails. Thus, to prove security it is sufficient to show that the total number of pairwise intersections is not larger than $\mathsf {t}$. With this combinatorial guarantee, we can rely on the security of $\mathsf {1KeyFE}$ and the MPC protocol to ensure no information other than f(m) is revealed.

Our observation here is that the same blueprint can also be used for tagged FE schemes where for amplifying 1-bounded collusion to q-bounded collusion, we start with a slightly larger tag space for the underlying 1-bounded tagged FE scheme. Basically, to build a q-bounded collusion tagged FE scheme with tag space $\mathcal {T}$, we start with a 1-bounded scheme with tag space $[\mathsf {N}] \times \mathcal {T}$, and replace i-th instantiation of the $\mathsf {1KeyFE}$ scheme with 1-bounded tagged FE scheme and the tag is set as $(i, \mathsf {tg})$ where $\mathsf {tg}$ is the tag to be embedded (during encryption and key generation, respectively). Now the correctness and security of the resulting compiler closely follows the analysis for untagged FE schemes from [7], with some subtleties in the analysis that arise due to the fact that in tagged FE simulation security we need to be able to jointly simulate multiple ciphertexts (though for distinct tags) at that the same time. More details follow later in Sect. 6.

Adding Tags to 1-Bounded-Collusion FE via IBE

Lastly, to instantiate our above transformations to build a dynamically bounded collusion FE scheme, we need a tagged FE scheme that achieves 1-bounded collusion simulation security. To that end, we look back at the 1-bounded collusion untagged FE construction by Sahai and Seyalioglu [31] which works by combining garbled circuits with plain public-key encryption. In a few words, our idea is to imitate the same ideology for instantiating our tagged FE scheme, but replace the plain public-key encryption scheme with an identity-based encryption scheme to introduce additional space for efficiently embedding tags in the identity space of the IBE scheme.

Recall that in the well-known 1-bounded collusion untagged FE construction, an encryptor garbles the universal circuit U with message m hardwired such that, on an input a description of a circuit C, the hardwired circuit computes C(m). Now the encryptor hides the wire keys for the garbled circuit under the corresponding PKE public keys chosen during setup time, where two PKE key pairs are sampled per bit of the description length of the circuit C. And, the decryption key for a circuit C simply corresponds to half of the PKE secret keys selected on the basis of bit description of C, that C[i]-th PKE secret key for each i. Basically, a decryptor first uncovers the wire labels corresponding to circuit C using PKE decryption, and then simply evaluates the garbled circuit to learn the circuit evaluation C(m).

We observe that the same construction can be upgraded to a tagged FE scheme if we simply replace each PKE system in the above transformation with an IBE system³, where the identity space of the IBE system will be used to encode the “designated tag”. Thus, the encryptor simply sets the IBE identity corresponding to which encryption is performed to be the input tag $\mathsf {tg}$, and the decryption key consists of appropriate IBE keys where the identity for each underlying IBE system is the tag $\mathsf {tg}$ to be embedded. Clearly, this gives the desired efficiency if the underlying IBE scheme is efficient, and the security follows by a similar argument as to before where a more careful analysis is needed to argue simulation security in presence of multiple tags. While the above transformation is sufficient to prove security in the non-adaptive setting as the original [31] construction, we rely on the delayed/non-committing encryption strategies [13] as in [24, 27] to upgrade to adaptive security. Our tagged FE scheme with 1-bounded collusion security is described in Sect. 7.

1.2 Related Work and Future Directions

Prior Work on Bounded Collusion Resistance. The intial works on bounded collusion resistance for FE were for the specific class of IBE systems. Dodis et al. [19] and Goldwasser, Lewko, and Wilson [23] constructed bounded collusion secure IBE with varying parametere size from regular public-key encryption and special types of linearly key homomorphic public-key encryption, respectively. For more expressive classes of FE, Sahai and Seyalioglu [31] proposed general functional encryption schemes resilient against a single function-key query using garbled circuits [35]. Following [31], GVW [24] build a statically bounded collusion resistant FE scheme for $\mathbf{NC} ^1$ circuits from any public-key encryption scheme, and also provided a generic compiler to improve to the class of all polynomial time computable functions by additionally relying on PRFs computable in $\mathbf{NC} ^1$. Afterwards, a number of follow-up works [1, 4, 15, 26] improved the concrete efficiency of the statically bounded collusion resistant FE scheme wherein they improved the dependence of the FE scheme parameters on the collusion bound q by relying on more structured algebraic assumptions. Most recently, Ananth and Vaikuntanathan [7] achieved optimally efficient statically secure FE scheme from the minimal assumption of public-key encryption. The optimal efficiency states that the system parameters grow only linearly with the collusion bound q, since any further improvement would lead to a fully collusion resistant FE scheme via the bootstrapping theorems from [5, 6, 9, 21, 33].

Comparison with Bundling Functionalities and Encrypt Ahead FE. Goyal, Koppula, and Waters (GKW) [25] proposed the concept of bundling functionalities in FE systems, where bundling functionalities in an FE scheme meant having the property that a single set of public parameters can support the union of all message/function spaces supported by the underlying FE system. They provided a generic transformation that started with IBE (and other implied primitives) and was able to upgrade any FE scheme to its bundled counterpart. One might ask that whether applying the [25] transformation to the family of bounded collusion FE, where the the collusion bound q is treated as part of the functionality index that is bundled, already leads to a dynamically bounded collusion FE system. It turns out this is not the case because such a generic transformation suffers from the limitation that a function key for a given collusion bound is not reusable for other collusion bounds. In particular, this necessitates each user to make additional queries to the authority for obtaining function keys for desired collusion bound, and this only solves the problem of removing the problem of removing the collusion bound dependence for the setup algorithm. Additionally, GKW proposed a novel variant of FE called encrypt ahead FE. One could ask the same question about relationship between encrypt ahead FE and dynamically bounded collusion resistant FE, and the answer is the same as for the case of bundling functionalities which is they are insufficient.

Open Questions. Our work introduces a new interesting avenue for exploring dynamic collusion resilience in FE systems. An interesting research direction is studying similar concepts of dynamic “query” resilience in other cryptographic contexts. For example, one could ask the same question for the concept of CCA-secure encryption where we know that CPA-secure public-key encryption implies (statically-)bounded-query-CCA security for public-key encryption [17]. We believe answering the question of dynamically bounded-query-CCA security might provide more insight in resolving the longstanding open problem of constructing a (general) CCA-secure encryption scheme from a CPA-secure one.

1.3 Concurrent Work

In a concurrent and independent work, Agrawal et al. [3] also define the dynamic collusion model for bounded-collusion functional encryption, with a similar motivation of providing more flexibility in selecting the collusion bound. Their primary construction of dynamic-bounded FE is essentially the same as ours, with the main difference in their presentation. We define abstractions to simplify exposition, while their construction focuses on constructing a ciphertext-policy FE scheme (CPFE) rather than a key-policy FE scheme (KPFE). One can transform any CPFE scheme to a KPFE scheme and vice versa, by using a universal circuit.

Our main results are the same, but [3] extend their results to uniform computation models while relying on specific algebraic assumptions. Finally, they answer the question of the necessity of IBE in building dynamic-bounded collusion FE in the affirmative, which was left as an open problem in an earlier version of this paper.

2 Preliminaries

Notations. Let PPT denote probabilistic polynomial-time. For any integer $q \ge 2$, we let $\mathbb {Z}_q$ denote the ring of integers modulo q. We denote the set of all positive integers upto n as $[n] := \left\{ 1, \ldots , n\right\}$. For any finite set S, $x\leftarrow S$ denotes a uniformly random element x from the set S. Similarly, for any distribution $\mathcal {D}$, $x \leftarrow \mathcal {D}$ denotes an element x drawn from distribution $\mathcal {D}$. The distribution $\mathcal {D}^n$ is used to represent a distribution over vectors of n components, where each component is drawn independently from the distribution $\mathcal {D}$. Two distributions $\mathcal {D}_1$ and $\mathcal {D}_2$, parameterized by security parameter $\lambda$, are said to be computationally indistinguishable, represented by $\mathcal {D}_1 \approx _c\mathcal {D}_2$, if for all PPT adversaries $\mathcal {A}$, $|\Pr [\mathcal {A}(x) = 1 : x \leftarrow \mathcal {D}_1] - \Pr [\mathcal {A}(x) = 1 : x \leftarrow \mathcal {D}_2]| \le \mathsf {negl}(\lambda )$.

2.1 Garbled Circuits

Our definition of garbled circuits [35] is based upon the work of Bellare et al. [8]. Let $\{\mathcal {C}_n\}_n$ be a family of circuits where each circuit in $\mathcal {C}_n$ takes n bit inputs. A garbling scheme $\mathsf {GC}$ for circuit family $\{\mathcal {C}_n\}_{n}$ consists of polynomial-time algorithms $\mathsf {Garble}$ and $\mathsf {Eval}$ with the following syntax.

• $\mathsf {Garble}(1^{\lambda }, C\in \mathcal {C}_n)$: The garbling algorithm takes as input the security parameter $\lambda$ and a circuit $C\in \mathcal {C}_n$. It outputs a garbled circuit $\widetilde{C}$, together with 2n wire keys $\{w_{i,b}\}_{i\le n, b\in \{0,1\}}$.

• $\mathsf {Eval}(\widetilde{C}, \{w_i\}_{i \le n})$: The evaluation algorithm takes as input a garbled circuit $\widetilde{C}$ and n wire keys $\{w_i\}_{i \le n}$ and outputs $y\in \{0,1\}$.

Correctness. A garbling scheme $\mathsf {GC}$ for circuit family $\{\mathcal {C}_n\}_n$ is said to be correct if for all $\lambda$, n, $x\in \{0,1\}^n$ and $C\in \mathcal {C}_n$, $\mathsf {Eval}(\widetilde{C}, \{w_{i, x_i}\}_{i \le n}) = C(x)$, where $(\widetilde{C}, \{w_{i,b}\}_{i\le n, b\in \{0,1\}}) \leftarrow \mathsf {Garble}(1^{\lambda }, C)$.

Security. Informally, a garbling scheme is said to be secure if for every circuit C and input x, the garbled circuit $\widetilde{C}$ together with input wires $\{w_{i, x_i}\}_{i \le n}$ corresponding to some input x reveals only the output of the circuit C(x), and nothing else about the circuit C or input x.

Definition 1

A garbling scheme $\mathsf {GC}= (\mathsf {Garble}, \mathsf {Eval})$ for a class of circuits $\mathcal {C}= \{\mathcal {C}_n\}_n$ is said to be a secure garbling scheme if there exists a polynomial-time simulator $\mathsf {Sim}$ such that for all n, $C\in \mathcal {C}_n$ and $x\in \{0,1\}^n$, the following distributions are computationally indistinguishable:

$$ \left\{ \mathsf {Sim}\left( 1^\lambda , 1^n, 1^{|C|}, C(x) \right) \right\} _\lambda \approx _c \left\{ \left( \widetilde{C}, \{w_{i, x_i}\}_{i \le n} \right) \; : \; \left( \widetilde{C}, \{w_{i,b}\}_{i\le n, b\in \{0,1\}} \right) \leftarrow \mathsf {Garble}(1^{\lambda }, C)\right\} _\lambda . $$

While this definition is not as general as the definition in [8], it suffices for our construction.

2.2 Identity-Based Encryption

An Identity-Based Encryption (IBE) scheme $\mathsf {IBE}$ for set of identity spaces $\mathcal {I} = \{\mathcal {I}_{n}\}_{n \in \mathbb {N}}$ and message spaces $\mathcal {M}$ consists of four polynomial time algorithms $(\mathsf {Setup},\mathsf {KeyGen},\mathsf {Enc},\mathsf {Dec})$ with the following syntax:

• $\mathsf {Setup}(1^{\lambda }, 1^n) \rightarrow (\mathsf {mpk}, \mathsf {msk}).$ The setup algorithm takes as input the security parameter $\lambda$ and identity space index n. It outputs the public parameters $\mathsf {mpk}$ and the master secret key $\mathsf {msk}$.

• $\mathsf {KeyGen}(\mathsf {msk}, \mathsf {id}) \rightarrow \mathsf {sk}_{\mathsf {id}}.$ The key generation algorithm takes as input the master secret key $\mathsf {msk}$ and an identity $\mathsf {id}\in \mathcal {I}_{n}$. It outputs a secret key $\mathsf {sk}_{\mathsf {id}}$.

• $\mathsf {Enc}(\mathsf {mpk}, \mathsf {id}, m) \rightarrow \mathsf {ct}.$ The encryption algorithm takes as input the public parameters $\mathsf {mpk}$, a message $m \in \mathcal {M}$, and an identity $\mathsf {id}\in \mathcal {I}_{n}$. It outputs a ciphertext $\mathsf {ct}$.

• $\mathsf {Dec}(\mathsf {sk}_{\mathsf {id}}, \mathsf {ct}) \rightarrow m/\bot .$ The decryption algorithm takes as input a secret key $\mathsf {sk}_{\mathsf {id}}$ and a ciphertext $\mathsf {ct}$. It outputs either a message $m \in \mathcal {M}$ or a special symbol $\bot$.

Correctness. We say an IBE scheme $\mathsf {IBE}= (\mathsf {Setup},\mathsf {KeyGen},\mathsf {Enc},\mathsf {Dec})$ satisfies correctness if for all $\lambda , n \in \mathbb {N}$, $(\mathsf {mpk}, \mathsf {msk}) \leftarrow \mathsf {Setup}(1^{\lambda }, 1^n)$, $\mathsf {id}\in \mathcal {I}_{n}$, $m \in \mathcal {M}$, $\mathsf {sk}_{\mathsf {id}} \leftarrow \mathsf {KeyGen}(\mathsf {msk}, \mathsf {id})$, and $\mathsf {ct}\leftarrow \mathsf {Enc}(\mathsf {mpk}, \mathsf {id}, m)$, we have that $\mathsf {Dec}(\mathsf {sk}_{\mathsf {id}}, \mathsf {ct}) = m$.

Definition 2

We say an IBE scheme $\mathsf {IBE}= (\mathsf {Setup},\mathsf {KeyGen},\mathsf {Enc},\mathsf {Dec})$ is secure if for any stateful PPT adversary $\mathcal {A}$ there exists a negligible function $\mathsf {negl}(\cdot )$, such that for all $\lambda , n \in \mathbb {N}$, the probability

$$ \Pr \left[ \mathcal {A}_1^{\mathsf {KeyGen}(\mathsf {msk}, \cdot )}(\mathsf {st}, \mathsf {ct})\ = b : \ \begin{array}{cl} (\mathsf {mpk}, \mathsf {msk}) \leftarrow \mathsf {Setup}(1^{\lambda }, 1^n);\quad b \leftarrow \{0,1\}\\ (m_0, m_1, \mathsf {id}^{*}) \leftarrow \mathcal {A}^{\mathsf {KeyGen}(\mathsf {msk}, \cdot )}(1^{\lambda }, 1^n, \mathsf {mpk})\\ \mathsf {ct}\leftarrow \mathsf {Enc}(\mathsf {mpk}, \mathsf {id}^{*}, m_{b}) \end{array} \right] , $$

is $\le \dfrac{1}{2} + \mathsf {negl}(\lambda )$ where all identities $\mathsf {id}$ queried by $\mathcal {A}$ satisfy $\mathsf {id}\ne \mathsf {id}^{*}$.

3 Functional Encryption: Dynamic Bounded Collusion

In this section, we define the notion of functional encryption (FE) where we start by recalling the regime of (statically) bounded collusion secure FE systems as studied in prior works [24, 31]. We follow that by extending the notion to dynamic collusion bounded secure FE systems. And, along the way we also introduce a special compactness property for statically bounded collusion secure FE schemes. This will serve as an appropriate intermediate abstraction to build a fully dynamic collusion bounded FE schemes.

Syntax. Let $\mathcal {M}= \{\mathcal {M}_n\}_{n\in \mathbb {N}}$, $\mathcal {R}= \{\mathcal {R}_n\}_{n\in \mathbb {N}}$ be families of sets, and $\mathbb {F}= \{\mathcal {F}_n\}$ a family of functions, where for all $n\in \mathbb {N}$ and $f\in \mathcal {F}_n$, $f: \mathcal {M}_n \rightarrow \mathcal {R}_n$. We will also assume that for all $n\in \mathbb {N}$, the set $\mathcal {F}_n$ contains an empty function $\epsilon _n : \mathcal {M}_n \rightarrow \mathcal {R}_n$. As in [11], the empty function is used to capture information that intentionally leaks from the ciphertext.

A functional encryption scheme $\mathsf {FE}$ for a family of function classes $\{\mathcal {F}_n\}_{n\in \mathbb {N}}$ and message spaces $\{\mathcal {M}_n\}_{n \in \mathbb {N}}$ consists of four polynomial-time algorithms $(\mathsf {Setup}, \mathsf {Enc}, \mathsf {KeyGen}, \mathsf {Dec})$ with the following semantics.

• $\mathsf {Setup}(1^\lambda , 1^n) \rightarrow (\mathsf {mpk}, \mathsf {msk}).$ The setup algorithm takes as input the security parameter $\lambda$ and the functionality index n⁴ (in unary), and outputs the master public-secret key pair $(\mathsf {mpk}, \mathsf {msk})$.

• $\mathsf {Enc}(\mathsf {mpk}, m \in \mathcal {M}_n) \rightarrow \mathsf {ct}.$ The encryption algorithm takes as input the master public key $\mathsf {mpk}$ and a message $m \in \mathcal {M}_n$ and outputs a ciphertext $\mathsf {ct}$.

• $\mathsf {KeyGen}(\mathsf {msk}, f \in \mathcal {F}_n) \rightarrow \mathsf {sk}_f.$ The key generation algorithm takes as input the master secret key $\mathsf {msk}$ and a function $f \in \mathcal {F}_n$ and outputs a function key $\mathsf {sk}_f$.

• $\mathsf {Dec}(\mathsf {sk}_f, \mathsf {ct}) \rightarrow \mathcal {R}_n.$ The decryption algorithm takes as input a ciphertext $\mathsf {ct}$ and a secret key $\mathsf {sk}_f$ and outputs a value $y \in \mathcal {R}_n$.

Correctness and Efficiency. A functional encryption scheme $\mathsf {FE}= (\mathsf {Setup}, \mathsf {Enc}, \mathsf {KeyGen}, \mathsf {Dec})$ is said to be correct if for all $\lambda , n \in \mathbb {N}$, functions $f \in \mathcal {F}_n$, messages $m\in \mathcal {M}_n$ and $(\mathsf {mpk}, \mathsf {msk}) \leftarrow \mathsf {Setup}(1^\lambda , 1^n)$, we have that

$$ \Pr \left[ \mathsf {Dec}(\mathsf {KeyGen}(\mathsf {msk}, f), \mathsf {Enc}(\mathsf {mpk}, m)) = f(m) \right] = 1, $$

where the probability is taken over the coins of key generation and encryption algorithms. And, it is said to be efficient if the running time of the algorithms is a fixed polynomial in the parameters $\lambda$ and n.

3.1 Bounded Collusion FE: Static and Dynamic

Informally, a functional encryption scheme is said to be secure if an adversary having secret keys for functions $\{f_i\}_{i\le q}$ and a ciphertext $\mathsf {ct}$ for message m learns only $\{f_i(m)\}_{i \le q}$, $\epsilon (m)$ and nothing else about the underlying message m. Here $\epsilon$ is the empty function associated with the message space.

The Static Setting. Now in the “static” bounded collusion setting, the scheme is said to guarantee security so long as q is a polynomial in the security parameter $\lambda$ and fixed a-priori at the setup time. Thus, the syntax of the setup algorithm changes as follows:

• $\mathsf {Setup}(1^\lambda , 1^n, q) \rightarrow (\mathsf {mpk}, \mathsf {msk}).$ The setup algorithm takes as input the security parameter $\lambda$ and the functionality index n (in unary), and also takes as input the ‘collusion bound’ q (in binary).⁵ It outputs the master public-secret key pair $(\mathsf {mpk}, \mathsf {msk})$.

Efficiency. Although the collusion bound q is given in binary to the setup algorithm, the efficiency condition for a statically bounded collusion FE scheme only requires that the running time of the all the algorithms is a fixed polynomial in $\lambda$, n and q. That is, the running time of $\mathsf {Setup}$, $\mathsf {KeyGen}$, $\mathsf {Enc}$, and $\mathsf {Dec}$ is allowed to polynomially grow with the collusion bound q.

Static Bounded Collusion Security. This is formally captured via the following ‘simulation based’ security definition as follows. We first provide the adaptive definition, and later provide the non-adaptive definition.

Definition 3 (static-bounded-collusion simulation-security)

A functional encryption scheme $\mathsf {FE}= (\mathsf {Setup}, \mathsf {Enc}, \mathsf {KeyGen}, \mathsf {Dec})$ is said to be statically-bounded-collusion simulation-secure if there exists a stateful PPT simulator $\mathsf {Sim}= (\mathsf {S}_0, \mathsf {S}_1, \mathsf {S}_2, \mathsf {S}_3)$ such that for every stateful PPT adversary $\mathcal {A}$, the following distributions are computationally indistinguishable:

$$\begin{aligned}\begin{gathered} \left\{ \mathcal {A}^{\mathsf {KeyGen}(\mathsf {msk}, \cdot )}(\mathsf {ct}) : \begin{array}{cl} (1^n, 1^q) \leftarrow \mathcal {A}(1^{\lambda }) \\ (\mathsf {mpk}, \mathsf {msk}) \leftarrow \mathsf {Setup}(1^{\lambda }, 1^n, q) \\ m \leftarrow \mathcal {A}^{\mathsf {KeyGen}(\mathsf {msk}, \cdot )}(\mathsf {mpk}) \\ \mathsf {ct}\leftarrow \mathsf {Enc}(\mathsf {mpk}, m) \end{array} \right\} _{\lambda \in \mathbb {N}} \\ \approx _c \\ \left\{ \mathcal {A}^{\mathsf {S}_3^{U_m(\cdot )}(\mathsf {st}_2, \cdot )}(\mathsf {ct}) : \begin{array}{cl} (1^n, 1^q) \leftarrow \mathcal {A}(1^{\lambda }) \\ (\mathsf {mpk}, \mathsf {st}_0) \leftarrow \mathsf {S}_0(1^{\lambda }, 1^n, q) \\ m \leftarrow \mathcal {A}^{\mathsf {S}_1(\mathsf {st}_0, \cdot )}(\mathsf {mpk}) \\ (\mathsf {ct}, \mathsf {st}_2) \leftarrow \mathsf {S}_2(\mathsf {st}_1, \varPi ^m) \end{array} \right\} _{\lambda \in \mathbb {N}} \end{gathered}\end{aligned}$$

whenever the following admissibility constraints and properties are satisfied:

• $\mathsf {S}_1$ and $\mathsf {S}_3$ are stateful in that after each invocation, they updates their states $\mathsf {st}_1$ and $\mathsf {st}_3$ (respectively) which is carried over to its next invocation.

• $\varPi ^m$ contains a list of functions $f_i$ queried by $\mathcal {A}$ in the pre-challenge phase along with the their output on the challenge message m. That is, if $f_i$ is the i-th function queried by $\mathcal {A}$ to oracle $\mathsf {S}_1$ and $q_{\mathsf {pre}}$ be the number of queries $\mathcal {A}$ makes before outputting m, then $\varPi ^m = \left( (f_1, f_1(m)), \ldots , (f_{q_{\mathsf {pre}}}, f_{q_{\mathsf {pre}}}(m)) \right)$.⁶

• $\mathcal {A}$ makes at most q queries combined to the key generation oracles in the corresponding games.

• $\mathsf {S}_3$ for each queried function $f_i$, in the post-challenge phase, makes a single query to its message oracle $U_m$ on the same $f_i$ itself.

Remark 1 (unary vs binary)

Note that in the above security games, we require the adversary to specify the collusion bound q in unary at the beginning. This is in contrast to the setup algorithm which gets q in binary as an input. The reason for this distinction is that in the security game for bounded collusion security we do not want to allow the attacker to specify super-polynomial collusion bounds, whereas (as we point out later) allowing the setup algorithm to be run on super-polynomial values of the collusion bound is important for our dynamic collusion bounded FE schemes.

Weak Optimality. Additionally, we also introduce the notion of a “weakly optimal” statically-bounded-collusion secure FE scheme where this system provides better efficiency properties. That is, in a weakly optimal static bounded collusion system, the running time of the setup and key generation algorithms grows only poly-logarithmically in the collusion bound q. Concretely, we define it below.

Definition 4 (weakly optimal statically-bounded-collusion)

A functional encryption scheme $\mathsf {FE}= (\mathsf {Setup}, \mathsf {Enc}, \mathsf {KeyGen}, \mathsf {Dec})$ is said to be ‘weakly optimal’ statically-bounded-collusion FE scheme if the running time of the $\mathsf {Setup}$ and $\mathsf {KeyGen}$ algorithm is additionally upper bounded by a fixed polynomial in $\lambda$, n and $\log q$.

Strengthening the Simulation Guarantee. In this work, we consider a strengthening of the above simulation-secure properties (for the class of weakly optimal static-bounded-collusion FE schemes) which will be be crucial towards building a dynamic-bounded-collusion functional encryption scheme. Note that typically the simulation security states that the distribution of secret keys and ciphertext are simulatable as long as the adversary does not make more key queries than what is specified by the static collusion bound. That is, if the adversary makes more key queries then no guarantee is provided. However, we consider a stronger simulation guarantee below wherein the real world is still simulatable even when the adversary makes more key queries than that specified by the collusion bound as long as the adversary does not make any challenge message queries. That is, either the collusion bound is not crossed, or no challenge ciphertext is queried. In addition to this, we require the running time of the simulator algorithms $\mathsf {S}_0, \mathsf {S}_1$ and $\mathsf {S}_3$ (that is, all except the ciphertext simulator $\mathsf {S}_2$) grow only poly-logarithmically in the static collusion bound q. Formally, we define it below.

Definition 5 (strong simulation-security)

A functional encryption scheme $\mathsf {FE}= (\mathsf {Setup}, \mathsf {Enc}, \mathsf {KeyGen}, \mathsf {Dec})$ is said to be statically-bounded-collusion strong simulation-secure if, in the security game defined in Definition 3, the following additional conditions hold:

• 1. the number of key queries made by adversary is allowed to exceed the static collusion bound q as long as the adversary does not submit any challenge message, and

• 2. the running time of the simulator algorithms $\mathsf {S}_0, \mathsf {S}_1$ and $\mathsf {S}_3$ is upper bounded by a fixed polynomial in $\lambda$, n and $\log q$.

Lastly, we also define the non-adaptive variant of the simulation security.

Definition 6 (non-adaptive simulation-security)

A functional encryption scheme $\mathsf {FE}= (\mathsf {Setup}, \mathsf {Enc}, \mathsf {KeyGen}, \mathsf {Dec})$ is said to be statically-bounded-collusion non-adaptive (regular/strong) simulation-secure if the adversary is prohibited from making any key queries in the post-challenge phase (that is, after receiving the challenge ciphertext) in its respective security game.

The Dynamic Setting. Now in the “dynamic” bounded collusion setting, the scheme is no longer tied to a single collusion bound q fixed a-priori at the system setup, but instead the encryptor could choose the amount of collusion resilience it wants. Thus, this changes the syntax of the setup and encryption algorithm when compared to the static setting from above:

• $\mathsf {Setup}(1^\lambda , 1^n) \rightarrow (\mathsf {mpk}, \mathsf {msk}).$ The setup algorithm takes as input the security parameter $\lambda$ and the functionality index n (in unary). It outputs the master public-secret key pair $(\mathsf {mpk}, \mathsf {msk})$. (Note that thus syntactically the setup of a dynamic bounded collusion scheme is same as that of a fully collusion resistant scheme.)

• $\mathsf {Enc}(\mathsf {mpk}, m \in \mathcal {M}_n, 1^q) \rightarrow \mathsf {ct}.$ The encryption algorithm takes as input the master public key $\mathsf {mpk}$, a message $m \in \mathcal {M}_n$, and it takes the desired collusion bound q (in unary) as an input. It outputs a ciphertext $\mathsf {ct}$.

Efficiency. Since the collusion bound q is not specified during setup or key generation at all, thus the efficiency condition for a dynamically bounded collusion FE scheme requires the running time of $\mathsf {Setup}$ and $\mathsf {KeyGen}$ to be fixed polynomials in $\lambda$ and n. While since the encryptor takes q as input in unary, thus the running time of the $\mathsf {Enc}$ algorithm could grow polynomially with collusion bound q. Similarly, the running time of $\mathsf {Dec}$ is also allowed to grow polynomially with collusion bound q.

Dynamic Bounded Collusion Security. This is formally captured via a ‘simulation based’ security definition as in the static setting. The game is similar to that provided in Definition 3, except now the attacker specifies the collusion bound q while making the challenge ciphertext query and the simulator also only receives the collusion bound as input at that point. For completeness, we describe it formally below (both the adaptive and non-adaptive variants).

Definition 7 (dynamic-bounded-collusion simulation-security)

A functional encryption scheme $\mathsf {FE}= (\mathsf {Setup}, \mathsf {Enc}, \mathsf {KeyGen}, \mathsf {Dec})$ is said to be dynamically-bounded-collusion simulation-secure if there exists a stateful PPT simulator $\mathsf {Sim}= (\mathsf {S}_0, \mathsf {S}_1, \mathsf {S}_2, \mathsf {S}_3)$ such that for every stateful PPT adversary $\mathcal {A}$, the following distributions are computationally indistinguishable:

$$\begin{aligned}\begin{gathered} \left\{ \mathcal {A}^{\mathsf {KeyGen}(\mathsf {msk}, \cdot )}(\mathsf {ct}) : \begin{array}{cl} 1^n \leftarrow \mathcal {A}(1^{\lambda }) \\ (\mathsf {mpk}, \mathsf {msk}) \leftarrow \mathsf {Setup}(1^{\lambda }, 1^n) \\ (m, 1^q) \leftarrow \mathcal {A}^{\mathsf {KeyGen}(\mathsf {msk}, \cdot )}(\mathsf {mpk}) \\ \mathsf {ct}\leftarrow \mathsf {Enc}(\mathsf {mpk}, m, 1^q) \end{array} \right\} _{\lambda \in \mathbb {N}} \\ \approx _c \\ \left\{ \mathcal {A}^{\mathsf {S}_3^{U_m(\cdot )}(\cdot )}(\mathsf {ct}) : \begin{array}{cl} 1^n \leftarrow \mathcal {A}(1^{\lambda }) \\ \mathsf {mpk}\leftarrow \mathsf {S}_0(1^{\lambda }, 1^n) \\ (m, 1^q) \leftarrow \mathcal {A}^{\mathsf {S}_1(\cdot )}(\mathsf {mpk}) \\ \mathsf {ct}\leftarrow \mathsf {S}_2(\varPi ^m, 1^q) \end{array} \right\} _{\lambda \in \mathbb {N}} \end{gathered}\end{aligned}$$

whenever the admissibility constraints and properties, as defined in Definition 3, are satisfied.

Definition 8 (non-adaptive simulation-security)

A functional encryption scheme $\mathsf {FE}= (\mathsf {Setup}, \mathsf {Enc}, \mathsf {KeyGen}, \mathsf {Dec})$ is said to be dynamically-bounded-collusion non-adaptive simulation-secure if, in the security game defined in Definition 7, the adversary is prohibited from making any key queries in the post-challenge phase (that is, after receiving the challenge ciphertext).

3.2 Upgrading Static to Dynamic Bounded Collusion FE via Weak Optimal Efficiency

In this section, we provide a generic construction of a dynamic-bounded-collusion FE scheme from any static-bounded-collusion FE scheme that satisfies the strong simulation property (Definition 5) and the weak optimality property (Definition 4). Below we provide our construction followed by correctness and security proofs.

Construction. Let $\mathsf {Static}\hbox {-}\mathsf {FE}= (\mathsf {S}\hbox {-}\mathsf {FE}.\mathsf {Setup}, \mathsf {S}\hbox {-}\mathsf {FE}.\mathsf {Enc}, \mathsf {S}\hbox {-}\mathsf {FE}.\mathsf {KeyGen}, \mathsf {S}\hbox {-}\mathsf {FE}.\mathsf {Dec})$ be a weakly-optimal static-bounded-collusion FE scheme for a family of function classes $\{\mathcal {F}_n\}_{n\in \mathbb {N}}$ and message spaces $\{\mathcal {M}_n\}_{n \in \mathbb {N}}$. We use $\mathsf {Static}\hbox {-}\mathsf {FE}$ to build a dynamic-bounded-collusion FE scheme $\mathsf {FE}\,{=}\, (\mathsf {Setup}, \mathsf {Enc}, \mathsf {KeyGen}, \mathsf {Dec})$ as follows.

• $\mathsf {Setup}(1^{\lambda }, 1^n) \rightarrow (\mathsf {mpk}, \mathsf {msk}).$ The setup algorithm runs the $\mathsf {Static}\hbox {-}\mathsf {FE}$ setup algorithm $\lambda$ times with increasing values of the static collusion bound $q$ as follows:

  $$ \forall i \in [\lambda ], \quad (\mathsf {mpk}_i, \mathsf {msk}_i) \leftarrow \mathsf {S}\hbox {-}\mathsf {FE}.\mathsf {Setup}(1^{\lambda }, 1^n, q= 2^i). $$

  It then sets the master secret and public keys as an $\lambda$-tuple of all these keys, i.e. $\mathsf {msk}= \left( \mathsf {msk}_i \right) _{i \in [\lambda ]}$ and $\mathsf {mpk}= \left( \mathsf {mpk}_i \right) _{i \in [\lambda ]}$.

• $\mathsf {KeyGen}(\mathsf {msk}, f) \rightarrow \mathsf {sk}_f.$ Let $\mathsf {msk}= \left( \mathsf {msk}_i \right) _{i \in [\lambda ]}$. The key generation algorithm runs the $\mathsf {Static}\hbox {-}\mathsf {FE}$ key generation algorithm with all $\lambda$ keys independently as $\mathsf {sk}_{i, f} \leftarrow \mathsf {S}\hbox {-}\mathsf {FE}.\mathsf {KeyGen}(\mathsf {msk}_i, f)$ for $i \in [\lambda ]$. It outputs the secret key $\mathsf {sk}$ as $\mathsf {sk}= \left( \mathsf {sk}_{i, f} \right) _{i \in [\lambda ]}$.

• $\mathsf {Enc}(\mathsf {mpk}, m, 1^Q) \rightarrow \mathsf {ct}.$ Let $\mathsf {mpk}= \left( \mathsf {mpk}_i \right) _{i \in [\lambda ]}$. The encryption algorithm simply encrypts the message m under $\lceil \log Q \rceil$-th master public key as $\mathsf {ct}\leftarrow \mathsf {S}\hbox {-}\mathsf {FE}.\mathsf {Enc}(\mathsf {mpk}_{\lceil \log Q \rceil }, m)$. (It also includes Q as part of the ciphertext.)

• $\mathsf {Dec}(\mathsf {sk}_f, \mathsf {ct}) \rightarrow z.$ Let $\mathsf {sk}_f = \left( \mathsf {sk}_{i, f} \right) _{i \in [\lambda ]}$. The decryption algorithm runs the $\mathsf {Static}\hbox {-}\mathsf {FE}$ decryption using the $\lceil \log Q \rceil$-th function key as $z \leftarrow \mathsf {S}\hbox {-}\mathsf {FE}.\mathsf {Dec}(\mathsf {sk}_{\lceil \log Q \rceil , f}, \mathsf {ct})$.

Correctness, Efficiency, and Security. The correctness of the above scheme follows directly from the correctness of the underlying static-bounded-collusion FE system, while for the desired efficiency consider the following arguments. First, note that by weak optimality of $\mathsf {Static}\hbox {-}\mathsf {FE}$ we have that the running time of $\mathsf {S}\hbox {-}\mathsf {FE}.\mathsf {Setup}$ and $\mathsf {S}\hbox {-}\mathsf {FE}.\mathsf {KeyGen}$ grows as $\mathsf {poly}(\lambda , n, \log q)$. Since the $\mathsf {Setup}$ and $\mathsf {S}\hbox {-}\mathsf {FE}.\mathsf {KeyGen}$ algorithms run $\mathsf {S}\hbox {-}\mathsf {FE}.\mathsf {Setup}$ and $\mathsf {S}\hbox {-}\mathsf {FE}.\mathsf {KeyGen}$ (respectively) $\lambda$ many times for $\log q \in \left\{ 1, \ldots , \lambda \right\}$, thus we get that running time of $\mathsf {Setup}$ and $\mathsf {KeyGen}$ is $\mathsf {poly}(\lambda , n)$ as desired. Lastly, the encryption and decryption algorithm run in time at most $\mathsf {poly}(\lambda , n, 2^{\lceil \log Q \rceil }) = \mathsf {poly}(\lambda , n, Q)$ since the $\lceil \log Q \rceil$-th static-bounded-collusion FE system uses $2^{\lceil \log Q \rceil } \le 2 \cdot Q$ as the static collusion bound. Thus, the resulting $\mathsf {FE}$ scheme satisfies the required efficiency properties.

To conclude, we prove the following.

Theorem 1

If $\mathsf {Static}\hbox {-}\mathsf {FE}= (\mathsf {S}\hbox {-}\mathsf {FE}.\mathsf {Setup}, \mathsf {S}\hbox {-}\mathsf {FE}.\mathsf {Enc}, \mathsf {S}\hbox {-}\mathsf {FE}.\mathsf {KeyGen}, \mathsf {S}\hbox {-}\mathsf {FE}.\mathsf {Dec})$ is a weakly-optimal static-bounded-collusion simulation-secure FE scheme (as per Definition 5 and 4), then the above scheme $\mathsf {FE}= (\mathsf {Setup}, \mathsf {Enc}, \mathsf {KeyGen}, \mathsf {Dec})$ is a dynamic-bounded-collusion simulation-secure FE scheme (as per Definition 7).

The proof follows from a composition of the static-bounded-collusion simulation-security property of $\mathsf {Static}\hbox {-}\mathsf {FE}$. Recall that in the static setting, we require the scheme to provide a stronger form of real world vs. ideal world indistinguishability. Where typically the simulation security states that the distribution of secret keys and ciphertext are simulatable as long as the adversary does not make more key queries than what is specified by the static collusion bound. That is, if the adversary makes more key queries then no guarantee is provided. However, in our formalization of simulation security for static-bounded-collusion FE schemes, we require that the real and ideal worlds are also indistinguishable even when the adversary makes more key queries than that specified by the collusion bound as long as the adversary does not make any challenge message queries. That is, either the collusion bound is not crossed, or no challenge ciphertext is queried. Also, the running time of the simulator algorithms $\mathsf {S}_0, \mathsf {S}_1$ and $\mathsf {S}_3$ (all except the ciphertext simulator $\mathsf {S}_2$) grow only poly-logarithmically in the collusion bound.

Thus, the simulator for the dynamic-bounded-collusion FE scheme simply runs the $\mathsf {S}_0$ algorithms for all collusion bounds $q = 1, \ldots , 2^\lambda$ to simulate the individual master public keys. It then also runs the $\mathsf {S}_1$ algorithms for simulating the individual function keys for each of these static-bounded-collusion FE systems for answering each adversarial key query. Note that since the running time of $\mathsf {S}_0$ and $\mathsf {S}_1$ is also $\mathsf {poly}(\lambda , n, \log q)$ where $q = 1, \ldots , 2^\lambda$, thus this is efficient.

Now when the adversary makes the challenge query for message m, it also specifies the target collusion bound $Q^{*}$. The dynamic-bounded-collusion simulator then runs only the ciphertext simulator algorithm $\mathsf {S}_2$ for the static FE system corresponding to collusion bound $\log q = \lceil \log Q^{*} \rceil$. Note that the simulator does not run $\mathsf {S}_2$ for the underlying FE schemes with lower (and even higher) collusion bounds. This is important for two reasons: (1) we want to invoke the simulation security of the i-th static FE scheme for $i < \lceil \log Q^{*} \rceil$ but we can only do this if the ciphertext simulator $\mathsf {S}_2$ is not run for these static FE schemes, (2) the running time of $\mathsf {S}_2$ could grow polynomially with the collusion bound q, thus we should not invoke simulator algorithm $\mathsf {S}_2$ for $i > \lceil \log Q^{*} \rceil$ as well (since for say $i = \lambda$, the running time would be exponential in $\lambda$ which would make the dynamic simulator inefficient). Thus, even the ciphertext simulation is efficient and the dynamic simulator is an admissible adversary with respect to static FE challenger, therefore our dynamic FE simulator is both efficient and can rely on simulation security of the underlying static FE schemes. The last phase of simulation (i.e., post-challenge key generation phase) works the same as the second phase simulator (i.e., pre-challenge key generation phase) which is by running $\mathsf {S}_3$ for all collusion bounds.

This completes a high level sketch. A complete proof is provided in our full version [20].

Remark 2 (non-adaptive simulation-security)

If the underlying static-bounded-collusion FE scheme only provides security against non-adaptive attackers (as per Definition 6), then the resulting dynamic-bounded-collusion FE scheme is also secure only against non-adaptive attackers (as per Definition 8).

4 Tagged Functional Encryption

In this work, we introduce the concept of tagged functional encryption where the basic difference when compared to regular functional encryption systems is that ciphertexts and secret keys are embedded with a tag value such that only the ciphertexts and keys with the same tags can be combined during decryption.

Formally, a tagged FE scheme in the static collusion model for a set of tag spaces $\mathcal {I} = \{\mathcal {I}_{z}\}_{z \in \mathbb {N}}$ consists of the same four algorithms with following modification to the syntax:

• $\mathsf {Setup}(1^\lambda , 1^n, 1^z, 1^q) \rightarrow (\mathsf {mpk}, \mathsf {msk}).$ In addition to the normal inputs taken by a static-bounded FE scheme, the setup also takes in a tag space index z, which fixes a tag space $\mathcal {I}_z$.

• $\mathsf {Enc}(\mathsf {mpk}, \mathsf {tg}\in \mathcal {I}_z, m \in \mathcal {M}_n) \rightarrow \mathsf {ct}.$ The encryption also takes in a tag $\mathsf {tg}\in \mathcal {I}_z$ to bind to the ciphertext.

• $\mathsf {KeyGen}(\mathsf {msk}, \mathsf {tg}\in \mathcal {I}_z, f \in \mathcal {F}_n) \rightarrow \mathsf {sk}_{\mathsf {tg},f}.$ The key generation also binds the secret keys to a fixed tag $\mathsf {tg}\in \mathcal {I}_z$.

• $\mathsf {Dec}(\mathsf {sk}_{\mathsf {tg},f}, \mathsf {ct}) \rightarrow \mathcal {R}_n.$ The decryption algorithm has syntax identical to a non-tagged scheme.

Correctness and Efficiency. A tagged FE scheme $\mathsf {tgfe}$ is said to be correct if for all $\lambda , n, z, q \in \mathbb {N}$, every function $f \in \mathcal {F}_n$, message $m\in \mathcal {M}_n$, tag $\mathsf {tg}\in \mathcal {I}_z$, and $(\mathsf {mpk}, \mathsf {msk}) \leftarrow \mathsf {Setup}(1^\lambda , 1^n, 1^z, 1^q)$, we have that

$$ \Pr \left[ \mathsf {Dec}(\mathsf {KeyGen}(\mathsf {msk}, \mathsf {tg}, f), \mathsf {Enc}(\mathsf {mpk}, \mathsf {tg}, m)) = f(m) \right] = 1, $$

where the probability is taken over the coins of key generation and encryption algorithms. And, it is said to be efficient if the running time of the algorithms is a fixed polynomial in the parameters $\lambda , n, q$ and z.

Security. The security definition is modelled in a similar fashion to the ordinary static bounded collusion FE game with the difference that the adversary plays it on multiple $\mathsf {tg}$ simultaneously and the simulator must simulate the ciphertexts for every tag. In addition, the adversary is also allowed to make arbitrary many secret key queries for all other tags. The formal definition follows.

Definition 9 (tagged-static-bounded-collusion simulation-security)

For any choice of parameters $\lambda , n, q, z \in \mathbb {N}$, consider the following list of stateful oracles $\mathsf {S}_0, \mathsf {S}_1, \mathsf {S}_2$ where these oracles simulate the FE setup, key generation, and encryption algorithms respectively, and all three algorithms share and update the same global state of the simulator. Here the attacker interacts with the execution environment $\mathcal {E}$, and the environment makes queries to the simulator oracles. Formally, the simulator oracles and the environment are defined below:

• $\mathsf {S}_0(1^\lambda , 1^n, 1^z, 1^q)$ generates the simulated master public key $\mathsf {mpk}$ of the system, and initializes the global state $\mathsf {st}$ of the simulator which is used by the next two oracles.

• $\mathsf {S}_1(\cdot , \cdot , \cdot ),$ upon a call to generate secret key on a function-tag-value tuple $(f_i, \mathsf {tg}_i, \mu _i)$, where the function value is either $\mu _i = \bot$ (signalling that the adversary has not yet made any encryption query on tag $\mathsf {tg}_i$), or $(m^{\mathsf {tg}_i}, \mathsf {tg}_i)$ has already been queried for encryption (for some message $m^{\mathsf {tg}_i}$), and $\mu _i = f_i(m^{\mathsf {tg}_i})$, the oracle outputs a simulated key $\mathsf {sk}_{f_i, \mathsf {tg}_i}$.

• $\mathsf {S}_2(\cdot , \cdot ),$ upon a call to generate ciphertext on a tag-list tuple $(\mathsf {tg}_i, \varPi ^{m^{\mathsf {tg}_i}})$, where the list $\varPi ^{m^{\mathsf {tg}_i}}$ is a possibly empty list of the form $\varPi ^{m^{\mathsf {tg}_i}} = \big ((f_1^{\mathsf {tg}_i}, f_1^{\mathsf {tg}_i}({m^{\mathsf {tg}_i}})), \ldots , (f_{q_{\mathsf {pre}}}^{\mathsf {tg}_i}, f_{q_{\mathsf {pre}}}^{\mathsf {tg}_i}({m^{\mathsf {tg}_i}}))\big )$ (that is, contains the list of function-value pairs for which the adversary has already received a secret key for), the oracle outputs a simulated ciphertext $\mathsf {ct}_{\mathsf {tg}_i}$.

• $\mathcal {E}^{\mathsf {S}_1, \mathsf {S}_2}(\cdot , \cdot ),$ receives two types of queries – secret key query and encryption query. Upon a secret key query on a function-tag pair $(f_i, \mathsf {tg}_i)$, if $(m^{\mathsf {tg}_i}, \mathsf {tg}_i)$ has already been queried for encryption (for some message $m^{\mathsf {tg}_i}$) then $\mathcal {E}$ queries key oracle $\mathsf {S}_1$ on tuple $(f_i, \mathsf {tg}_i, \mu _i = f_i(m^{\mathsf {tg}_i}))$, otherwise it adds $(f_i, \mathsf {tg}_i)$ to the its local state, and queries $\mathsf {S}_1$ on tuple $(f_i, \mathsf {tg}_i, \mu _i = \bot )$. And, it simply forwards oracle’s simulated key $\mathsf {sk}_{f_i, \mathsf {tg}_i}$ to the adversary. Upon a ciphertext query on a message-tag pair $(m_i, \mathsf {tg}_i)$, if the adversary made an encryption query on the same tag $\mathsf {tg}_i$ previously, then the query is disallowed (that is, at most one message query per every unique tag is permitted). Otherwise, it computes a (possibly empty) list of function-value pairs of the form $\varPi ^{m_i} = \left( (f_1^{\mathsf {tg}_i}, f_1^{\mathsf {tg}_i}({m^{\mathsf {tg}_i}})), \ldots , (f_{q_{\mathsf {pre}}}^{\mathsf {tg}_i}, f_{q_{\mathsf {pre}}}^{\mathsf {tg}_i}({m^{\mathsf {tg}_i}})) \right)$ where $(f_j^{\mathsf {tg}_i}, \mathsf {tg}_i)$ are stored in $\mathcal {E}$’s local state, and removes all such pairs $(f_j^{\mathsf {tg}_i}, \mathsf {tg}_i)$ from its local state. $\mathcal {E}$ then queries ciphertext oracle $\mathsf {S}_2$ on tuple $(\mathsf {tg}_i, \varPi ^{m_i})$, and simply forwards oracle’s simulated ciphertext $\mathsf {ct}_{\mathsf {tg}_i}$ to the adversary.

A tagged functional encryption scheme $\mathsf {FE}= (\mathsf {Setup}, \mathsf {Enc}, \mathsf {KeyGen}, \mathsf {Dec})$ is said to be tagged-statically-bounded-collusion simulation-secure if there exists a stateful PPT simulator $\mathsf {Sim}= (\mathsf {S}_0, \mathsf {S}_1, \mathsf {S}_2)$ such that for every stateful admissible PPT adversary $\mathcal {A}$, the following distributions are computationally indistinguishable:

$$\begin{aligned}\begin{gathered} \left\{ \mathcal {A}^{\mathsf {KeyGen}(\mathsf {msk}, \cdot , \cdot ), \mathsf {Enc}(\mathsf {mpk}, \cdot , \cdot )}(\mathsf {mpk}) : \begin{array}{cl} (1^n, 1^q, 1^z) \leftarrow \mathcal {A}(1^{\lambda }) \\ (\mathsf {mpk}, \mathsf {msk}) \leftarrow \mathsf {Setup}(1^{\lambda }, 1^n, 1^z, 1^q) \\ \end{array} \right\} _{\lambda \in \mathbb {N}} \\ \approx _c \\ \left\{ \mathcal {A}^{\mathcal {E}^{\mathsf {S}_1, \mathsf {S}_2}(\cdot , \cdot )}(\mathsf {mpk}) : \begin{array}{cl} (1^n, 1^q, 1^z) \leftarrow \mathcal {A}(1^{\lambda }) \\ \mathsf {mpk}\leftarrow \mathsf {S}_0(1^{\lambda }, 1^n, 1^z, 1^q) \end{array} \right\} _{\lambda \in \mathbb {N}} \end{gathered}\end{aligned}$$

where $\mathcal {A}$ is an admissible adversary if:

• – $\mathcal {A}$ makes at most one encryption query per unique tag (that is, if the adversary made an encryption query on some tag $\mathsf {tg}_i$ previously, then making another encryption query for the same tag is disallowed)

• – $\mathcal {A}$ makes at most q queries combined to the key generation oracles in the above experiments for all tags $\mathsf {tg}_i$ such that it also submitted an encryption query for tag $\mathsf {tg}_i$.

Definition 10

(tagged-static-bounded-collusion non-adaptive simulation-security). A tagged functional encryption scheme $\mathsf {FE}= (\mathsf {Setup}, \mathsf {Enc}, \mathsf {KeyGen}, \mathsf {Dec})$ is said to be tagged-statically-bounded-collusion non-adaptive simulation-secure if, in the security game defined in Definition 9, the adversary is prohibited from making any key queries on any particular tag in the post-challenge phase (that is, if the adversary makes an encryption query w.r.t. tag $\mathsf {tg}$, then it must not make any more key queries on the same tag $\mathsf {tg}$ but can make key queries for other tags).

5 Tagged to Weakly Optimal Static Collusion FE

In this section we show how to convert the our construction of Q-bounded tagged FE to a weakly optimal statically secure functional encryption scheme with collusion bound Q. The transformation is very similar to the transformation in [7] that achieves linear complexity for any bounded-key FE scheme.

Let Q be the desired collusion bound for the static scheme. The transformation in [7] starts with Q instances of q-bounded statically secure FE, where q is set to some polynomial in the security parameter. The setup parameters are thus linearly bounded in Q. Encryption simply calls the base encrypt algorithm (for the q-bounded collusion scheme) on each instance. Since the base encryption scheme is for collusion bound $q=\mathsf {poly}(\lambda )$, one instance of encrypt takes time polynomial in the security parameter and thus encrypt is linearly bounded in Q. Key generation for a circuit C simply selects one of the instances at random and outputs the key generated by the base scheme on this instance. Correctness holds as the encrytor has encrypted for all possible instances. Security fails only if, after giving out Q secret keys, the load on a particular instance exceeds $q=\mathsf {poly}(\lambda )$ (which happens with only negligible probability via a simple Chernoff argument).

The transformation has the drawback that the setup outputs Q instances and thus all the algorithms depend linearly on Q. Our observation is thar if we start with a tagged FE scheme instead, then we can compress the public and secret parameters using the tag space by setting it proportional to the desired collusion bound Q. Similarly the key generation algorithm takes in a single master public key and master secret key and outputs one instance of the secret key. This helps us satisfy the weakly optimal property. More formal details follow below.

5.1 Construction

Let $\mathsf {tgfe}= (\mathsf {TgFE}.\mathsf {Setup}, \mathsf {TgFE}.\mathsf {Enc}, \mathsf {TgFE}.\mathsf {KeyGen}, \mathsf {TgFE}.\mathsf {Dec})$ be a bounded-collusion tagged FE scheme for a family of circuit classes $\{\mathcal {F}_n\}_{n\in \mathbb {N}}$, message spaces $\{\mathcal {M}_n\}_{n \in \mathbb {N}}$, and tag space $\{\mathcal {I}_z = \{0, 1\}^{z}\}_{z \in \mathbb {N}}$. We use $\mathsf {TgFE}$ to build $\mathsf {Static}\hbox {-}\mathsf {FE}$ a weakly-optimal static-bounded-collusion FE scheme for the same function classes and message spaces.

• $\mathsf {Setup}(1^{\lambda }, 1^n, Q) \rightarrow (\mathsf {mpk}, \mathsf {msk}).$ The setup algorithm runs the $\mathsf {TgFE}$ setup algorithm with the tag space of $\mathcal {I}_z = [2^{\lceil \log Q \rceil }]$ and collusion bound $q = \lambda$ and sets the master public-secret keys as

  $$\begin{aligned} (\mathsf {mpk},\mathsf {msk}) \leftarrow \mathsf {TgFE}.\mathsf {Setup}(1^{\lambda },1^n, 1^z = 1^{\lceil \log Q \rceil }, 1^q = 1^\lambda ). \end{aligned}$$

• Notation. Here and throughout the paper, we represent $\lceil \log Q \rceil$-bit tags as elements over a larger alphabet $[2^{\lceil \log Q \rceil }]$, and when we write $u \leftarrow [Q]$ then that denotes sampling u as a random integer between 1 and Q which can be uniquely encoded as an $\lceil \log Q \rceil$-bit tag.

• $\mathsf {KeyGen}(\mathsf {msk}, C) \rightarrow \mathsf {sk}_C.$ It samples a tag $u \leftarrow [Q]$, key $\mathsf {sk}_{C,u}\leftarrow \mathsf {TgFE}.\mathsf {KeyGen}(\mathsf {msk},u,C)$, and outputs $\mathsf {sk}_C = (\mathsf {sk}_{C,u}, u)$.

• $\mathsf {Enc}(\mathsf {mpk}, m, 1^Q) \rightarrow \mathsf {ct}.$ It encrypts the message m for all possible tags, and outputs the ciphertext $\mathsf {ct}= (\mathsf {ct}_1, \ldots , \mathsf {ct}_Q)$ where each sub-ciphertext is computed as:

  $$\begin{aligned} \forall u\in [Q], \quad \mathsf {ct}_u\leftarrow \mathsf {TgFE}.\mathsf {Enc}(\mathsf {mpk},u,m). \end{aligned}$$

• $\mathsf {Dec}(\mathsf {sk}_C, \mathsf {ct}) \rightarrow y.$ Let $\mathsf {sk}_C=(\mathsf {sk}_{C,u},u)$ and $\mathsf {ct}=(\mathsf {ct}_1,\ldots ,\mathsf {ct}_Q)$. The algorithm outputs $y\leftarrow \mathsf {TgFE}.\mathsf {Dec}(\mathsf {sk}_{C,u},\mathsf {ct}_u)$.

5.2 Correctness, Efficiency, and Security

The correctness of the above scheme follows directly from the correctness of the underlying $\mathsf {TgFE}$ scheme. For the efficiency, recall the requirements (Definition 4) which state that the $\mathsf {Setup}$ and $\mathsf {KeyGen}$ algorithms should be bound by a polynomial in $\lambda , n$ and $\log Q$. Both $\mathsf {Setup}$ and $\mathsf {KeyGen}$ run $\mathsf {TgFE}.\mathsf {Setup}$ and $\mathsf {TgFE}.\mathsf {KeyGen}$ once respectively. From the efficiency of these algorithms, we know that the running time is $\mathsf {poly}(\lambda ,n,\lceil \log Q\rceil )$.

Our full security proof is described in the full version [20].

6 Upgrading Collusion Bound for Tagged FE

Now we show that a bounded-collusion tagged FE scheme where the collusion bound can be any arbitrary polynomial can be generically built from a tagged FE scheme that allows corrupting at most one key per unique tag (i.e., 1-bounded collusion secure) by relying on the client server framework from [7]. The ideas behind this transformation are based on the 1-bounded non-tagged FE to Q-bounded non-tagged FE transformation from [7].

The client server framework is formally defined later in our full version [20] for completeness. Intuitively, in the client server framework, there is a single client and $\mathsf {N}$ servers. The computation proceeds in two phases, an offline phase, where the client encrypts an input x of the protocol for $\mathsf {N}$ servers where u-th server gets $\hat{x}^u$. This is followed by an online phase which runs in Q sessions for computation on circuits $C_1,\ldots ,C_Q$. In each session $j\in [Q]$, client delegates the computation of $C_j$ by computing $\hat{C}^u_j$ for $u\in [\mathsf {N}]$ and sending $\hat{C}_j^u$ to u-th server. Now $S\subseteq [\mathsf {N}]$ where $|S|=\mathsf {p}$ servers come online and for $u\in S$, u-th server computes $\hat{y}_j^u\leftarrow \mathsf {Local}(\hat{C}_j^u,\hat{x}^u)$. Finally the S server send information back to client who computes $y\leftarrow \mathsf {Decode}(\{\hat{y}^u_j\}_{u\in S},S)$ for each $j\in [Q]$, to compute $C_j(x)$.

The transformation in [7] invokes $\mathsf {N}$ (polynomial in $Q, \lambda$) many instantiations of the one bounded FE scheme. These $\mathsf {N}$ instances act like a separate server in the client server framework. Encryption simply computes the encryption of each one bounded instance on the offline computation on the inputs, i.e. encrypt under $\hat{x}^u$ for $u\in [\mathsf {N}]$ under the one bounded FE algorithm. Key generation computes the online encryption of the circuits, $\hat{C}^u$ for $u\in [\mathsf {N}]$ and picks a random subset S of size $\mathsf {p}$ and generates the secret keys on the 1 bounded instance for circuit $\mathsf {Local}(\hat{C}^u,\cdot )$ for $u\in S$. In our transformation, instead of having $\mathsf {N}$ independent instances, we instead blowup the tag space for the one tagged FE scheme and perform the key generation and encryption procedures very similarly. The analysis of the correctness and security are very similar to [7], except that in the $\mathsf {1TgFE}$ security game (Definition 9), we allow the adversary to request for multiple challenge ciphertexts (each on a different tag) and thus the security proof is tweaked adequately.

The full construction and proof is described in our full version [20].

7 Building 1-Bounded Collusion Tagged FE from IBE

Here we construct a tagged FE scheme that achieves security in the 1-bounded collusion model and, as we discussed in the previous section, this is sufficient to build a general bounded-collusion tagged FE scheme. Our construction is itself split into two components where first we have a simple construction using garbled circuits and IBE while only achieving non-adaptive security, and later show how to generically upgrade it to full adaptive security by relying on non-committing encryption techiques. We quickly sketch our formal constructions here. Please see the full version of our paper, [20], for the complete proofs.

7.1 Non-Adaptive 1-Bounded Tagged FE from Garbled Circuits and IBE

The non-adaptive construction is a close adaptation of the traditional construction of 1-bounded FE from public key encryption and garbled circuits found in [24, 31]. The idea is to simply encrypt all the wire labels of a garbling of a universal circuit using IBE and only give out select IBE secret keys of the wires corresponding to the circuit.

For simplicity, we assume that the functionality class $\mathcal {F}_n$ includes all circuits of size n (the circuit description is n bits long).

• $\mathsf {Setup}(1^\lambda , 1^n, 1^z) \rightarrow (\mathsf {mpk}, \mathsf {msk}).$ Sample an IBE master key pair as $(\mathsf {ibe}.\mathsf {pk}, \mathsf {ibe}.\mathsf {msk}) \leftarrow \mathsf {IBE}.\mathsf {Setup}(1^\lambda , 1^{z + \lceil \log n \rceil + 1})$, and output $\mathsf {mpk}= \mathsf {ibe}.\mathsf {pk}, \mathsf {msk}= \mathsf {ibe}.\mathsf {msk}$.

  Notation. Here and throughout the paper, we use $(b, i, \mathsf {tg})$ to denote the $(z + \lceil \log n \rceil + 1)$-bit identity, where b is a single bit, i encodes $\lceil \log n \rceil )$-bits, and $\mathsf {tg}$ is encoded in the remaining z bits. Basically, each bit-index-tag tuple is uniquely and efficiently mapped into the identity space.

• $\mathsf {Enc}(\mathsf {mpk}, \mathsf {tg}, m \in \mathcal {M}_n) \rightarrow \mathsf {ct}.$ Let $\mathcal {U}$ be the universal circuit for the family of size n circuits on inputs in $\mathcal {M}_n$ (i.e., $\mathcal {U}(C, m) = C(m)$). Now in the following garble $\mathcal {U}(\cdot , m)$ as $(\hat{\mathcal {U}}, \{w_{i,b}\}_{i \le n, b \in \{0,1\}}) \leftarrow \mathsf {GC}.\mathsf {Garble}(1^\lambda , \mathcal {U})$, and encrypt the labels as

  $$ \forall i \in n, b \in \{0,1\}, \quad \mathsf {ct}_{i,b} \leftarrow \mathsf {IBE}.\mathsf {Enc}(\mathsf {ibe}.\mathsf {pk}, (b, i, \mathsf {tg}), w_{i,b}) $$

  It finally outputs $\mathsf {ct}= (\hat{\mathcal {U}}, \{\mathsf {ct}_{i,b}\}_{i \le n, b \in \{0,1\}})$.

• $\mathsf {KeyGen}(\mathsf {msk}, \mathsf {tg}, C \in \{0,1\}^n) \rightarrow \mathsf {sk}_{\mathsf {tg},C}.$ Let $C[1], C[2], \ldots C[n]$ denote the bit representation of circuit C. It samples n IBE secret keys as $\mathsf {sk}_i = \mathsf {IBE}.\mathsf {KeyGen}(\mathsf {msk},(C[i], i, \mathsf {tg}))$ for $i \in [n]$, and outputs $\mathsf {sk}_{\mathsf {tg},C} = \{\mathsf {sk}_i\}_{i \in [n]}$.

• $\mathsf {Dec}(\mathsf {sk}_{\mathsf {tg},C}, \mathsf {ct}) \rightarrow y.$ It parses the secret key and ciphertext as above. It first decrypts the wire keys as $w_{i, C[i]} \leftarrow \mathsf {IBE}.\mathsf {Dec}(\mathsf {sk}_i, \mathsf {ct}_{i, C[i]})$ for $i \in [n]$, and then outputs $y = \mathsf {GC}.\mathsf {Eval}(\hat{\mathcal {U}}, \{w_{i,C[i]}\}_{i \in [n]})$.

7.2 Upgrading to Adaptive Security

We can transform any non-adaptive 1-bounded tagged FE scheme to an adaptive one using IBE. This is an analogue of the traditional method of using weak non-committing encryption (which is constructable from plain public key encryption) to make 1-bounded FE adaptive. Here, the encryption has two modes—a ‘normal mode’, where the scheme functions like a normal public key/IBE scheme, and a non-committing mode, where the encryptor can produce secret keys which equivocate to any value. This enables us to delay simulating the ciphertext of a adaptive key queries until the secret key is requested.

• $\mathsf {Setup}(1^\lambda , 1^n, 1^z) \rightarrow (\mathsf {mpk}, \mathsf {msk}).$ The setup algorithm runs the underlying tagged FE and IBE setup algorithms as $(\mathsf {natgfe}.\mathsf {pk}, \mathsf {natgfe}.\mathsf {msk}) \leftarrow \mathsf {NATgFE}.\mathsf {Setup}(1^\lambda , 1^n, 1^z)$, and $(\mathsf {ibe}.\mathsf {pk}, \mathsf {ibe}.\mathsf {msk}) \leftarrow \mathsf {IBE}.\mathsf {Setup}(1^\lambda , 1^{z + \lceil \log n' \rceil + 1})$ where $n'$ denotes the length of $\mathsf {natgfe}$ ciphertexts with the above parameters. It outputs the master keys as $(\mathsf {mpk}, \mathsf {msk}) = ((\mathsf {natgfe}.\mathsf {pk}, \mathsf {ibe}.\mathsf {pk}), (\mathsf {natgfe}.\mathsf {msk}, \mathsf {ibe}.\mathsf {msk}))$. Notation. Here and throughout the paper, we use $(b, i, \mathsf {tg})$ to denote the $(z + \lceil \log n' \rceil + 1)$-bit identity, where b is a single bit, i encodes $\lceil \log n' \rceil )$-bits, and $\mathsf {tg}$ is encoded in the remaining z bits. Basically, each bit-index-tag tuple is uniquely and efficiently mapped into the identity space.

• $\mathsf {Enc}(\mathsf {mpk}, \mathsf {tg}, m) \rightarrow \mathsf {ct}.$ Let $\mathsf {mpk}= (\mathsf {natgfe}.\mathsf {pk}, \mathsf {ibe}.\mathsf {pk})$. It encrypts m using tagged FE as $\mathsf {ct}' \leftarrow \mathsf {NATgFE}.\mathsf {Enc}(\mathsf {natgfe}.\mathsf {pk}, \mathsf {tg}, m)$, and it encrypts $\mathsf {ct}'$ bit-by-bit under IBE as $c_{b,j} = \mathsf {IBE}.\mathsf {Enc}(\mathsf {ibe}.\mathsf {pk}, (b, j, \mathsf {tg}), \mathsf {ct}'[j])$ for $b \in \{0,1\}, j \in [n']$. It then outputs $\mathsf {ct}= \{c_{b,j}\}_{b \in \{0,1\}, j \in [n']}$.

• $\mathsf {KeyGen}(\mathsf {msk}, \mathsf {tg}, C \in \{0,1\}^n) \rightarrow \mathsf {sk}_{\mathsf {tg},C}.$ Let $\mathsf {msk}= (\mathsf {natgfe}.\mathsf {msk}, \mathsf {ibe}.\mathsf {msk})$. It samples $n'$ random bits $b_1, b_2, \ldots , b_{n'} \leftarrow \{0,1\}$, and computes secret keys for the underlying systems as:

  $$\begin{aligned}&\mathsf {natgfe}.\mathsf {sk}_{\mathsf {tg},C} \leftarrow \mathsf {NATgFE}.\mathsf {KeyGen}(\mathsf {natgfe}.\mathsf {msk}, \mathsf {tg}, C), \\ \forall j \in [n'], \quad&\mathsf {ibe}.\mathsf {sk}_{b_j,j} \leftarrow \mathsf {IBE}.\mathsf {KeyGen}(\mathsf {ibe}.\mathsf {msk}, (b_j, j, \mathsf {tg})). \end{aligned}$$

  And it outputs $\mathsf {sk}_{\mathsf {tg},C} = (\mathsf {natgfe}.\mathsf {sk}_{\mathsf {tg},C}, \{(b_j, \mathsf {ibe}.\mathsf {sk}_{j,b_j})\}_{j \in [n']})$.

• $\mathsf {Dec}(\mathsf {sk}_{\mathsf {tg},C}, \mathsf {ct}) \rightarrow y$. It parses the secret key and ciphertext as above. It first decrypts the IBE ciphertexts as $\mathsf {ct}'[j]$ as $\mathsf {IBE}.\mathsf {Dec}(\mathsf {ibe}.\mathsf {sk}_{b_j,j}, \mathsf {ct}_{b,j})$ for $j \in [n']$, and then computes $y = \mathsf {NATgFE}.\mathsf {Dec}(\mathsf {natgfe}.\mathsf {sk}_{\mathsf {tg},C}, \mathsf {ct}')$ where $\mathsf {ct}'[i]$ is the i-th bit of $\mathsf {ct}'$.