Multi-Input Quadratic Functional Encryption: Stronger Security, Broader Functionality

Abstract

Multi-input functional encryption, MIFE, is a powerful generalization of functional encryption that allows computation on encrypted data coming from multiple different data sources. In a recent work, Agrawal, Goyal, and Tomida (CRYPTO 2021) constructed MIFE for the class of quadratic functions. This was the first MIFE construction from bilinear maps that went beyond inner product computation. We advance the state-of-the-art in MIFE, and propose new constructions with stronger security and broader functionality.

• Stronger Security: In the typical formulation of MIFE security, an attacker is allowed to either corrupt all or none of the users who can encrypt the data. In this work, we study MIFE security in a stronger and more natural model where we allow an attacker to corrupt any subset of the users, instead of only permitting all-or-nothing corruption. We formalize the model by providing each user a unique encryption key, and letting the attacker corrupt all non-trivial subsets of the encryption keys, while still maintaining the MIFE security for ciphertexts generated using honest keys. We construct a secure MIFE system for quadratic functions in this fine-grained corruption model from bilinear maps. Our construction departs significantly from the existing MIFE schemes as we need to tackle a more general class of attackers.

• Broader Functionality: The notion of multi-client functional encryption, MCFE, is a useful extension of MIFE. In MCFE, each encryptor can additionally tag each ciphertext with appropriate metadata such that ciphertexts with only matching metadata can be decrypted together. In more detail, each ciphertext is now annotated with a unique label such that ciphertexts encrypted for different slots can now only be combined together during decryption as long as the associated labels are an exact match for all individual ciphertexts. In this work, we upgrade our MIFE scheme to also support ciphertext labelling. While the functionality of our scheme matches that of MCFE for quadratic functions, our security guarantee falls short of the general corruption model studied for MCFE. In our model, all encryptors share a secret key, therefore this yields a secret-key version of quadratic MCFE, which we denote by SK-MCFE. We leave the problem of proving security in the general corruption model as an important open problem.

1 Introduction

Functional encryption (FE) [18, 19, 31] is a generalization of public key encryption that enables fine grained control over access to encrypted data. In FE, the secret key is associated with a function f, the ciphertext is associated with an input $\textbf{x}$ from the domain of f, and decryption enables recovery of $f(\textbf{x})$ and nothing else. Importantly, no information about $\textbf{x}$ is revealed beyond what is revealed by $\{f_i(\textbf{x})\}_i$ for any set of secret decryption keys corresponding to functions $\{f_i\}_i$ in possession of the adversary. This collusion resistance property of FE makes it very suitable for computing on encrypted data – a ciphertext encrypting the genomic data of hundreds of individuals can now be decrypted using function keys corresponding to various statistical functionalities studying correlations between genomic sequences and disease, while guaranteeing privacy of individual genomic sequences. Motivated by several important applications, including the construction of the powerful notion of indistinguishability obfuscation (iO) [12, 16], FE has received an enormous amount of attention in the community, with scores of elegant constructions from diverse assumptions, achieving various useful functionalities and satisfying assorted notions of security [3, 6, 14, 15, 20, 24, 25, 34].

Multi-Input Functional Encryption. Functional encryption was first generalized to support aggregated computation over multiple input sources by the celebrated work of Goldwasser et al. [26]. The premise of multi-input FE, denoted by MIFE, is that in many natural applications of FE it is essential to support generalized functionalities where arity is greater than one. For instance, in the above example of genome wide association studies, the ciphertext must encrypt genomic data of multiple individuals for it to be useful for the statistical studies in question, but this suggests that this data must be encrypted all at once by a single entity, which is an unreasonable assumption in practice. Genomic data is highly sensitive information and it is much more meaningful to allow every individual to encrypt their own data locally and generalize the construction to support functions of large arity that can process several ciphertexts at a time. This constraint is organically captured by MIFE, where n independent encryptors may individually generate ciphertexts for vectors $\{\textbf{x}_i^j\}_{i \in [n], j \in [\textsf{poly}]}$ and a secret key for function f allows to compute $f(\textbf{x}_1^{j_1},\textbf{x}_2^{j_2},\ldots ,\textbf{x}_n^{j_n})$ for any $j_1,\ldots ,j_n \in [\textsf{poly}]$.

Since its inception, MIFE received substantial attention which quickly bifurcated into two parallel branches – (i) the first builds on top of powerful primitives such as iO or compact single-input FE for general models of computation, like circuits or Turing machines and uses these to construct MIFE for circuits or Turing machines [11, 12, 16], (ii) the second focuses on efficient direct constructions for restricted functionalities from simple assumptions such as pairings or learning with errors [1, 2, 4, 5, 9, 21, 23, 29, 32]. In this work, we continue development of the second branch by making advances to the recently proposed construction of MIFE for quadratic functions by Agrawal, Goyal, and Tomida [9].

Modelling Security. Given the tension between functionality and security, where functionality seeks to reveal partial information about the input, while security seeks to protect privacy of the input, the question of modelling security in functional encryption has turned out to be subtle, and has been examined in multiple works [7, 8, 18, 30]. For the setting of unbounded collusion, namely where the adversary can obtain any polynomial number of function keys, in the security game, the indistinguishability based definition of security has emerged as the gold standard (due to impossibilities that plague the alternative simulation-based security [7, 8, 18]). In the single-input setting, both symmetric and public key FE have been studied and are relevant for different applications. In the multi-input setting, it was observed by Goldwasser et al. [26] that the symmetric key setting, where the encryptor requires a secret key to compute a ciphertext, is much more relevant for applications. This is to prevent the primitive from becoming meaningless due to excessive leakage occurring by virtue of functionality. In more detail, let us consider a two input scheme where a given first slot ciphertext hides a challenge bit b. Now, in the public key setting, an adversary can compute an unbounded encryptions for slot 2 herself and match these with the challenge ciphertext of slot 1 to learn a potentially unbounded amount of information. This unrestricted information leakage can be prevented by requiring the encryption algorithm to require a secret key.

However, in the symmetric key multi-input setting, an additional subtlety emerges related to the uniqueness of each user’s encryption key. For instance, if we consider the application of encrypting genomic data discussed above, it quickly becomes apparent that having all users share the same encryption key is problematic – if the genomic data is encrypted and stored in a central repository, then any malicious insider, who has contributed data and is hence in possession of the master encryption key, can download and decrypt data belonging to any other user! As data is supposed to span hundreds of users, the master encryption key will become widely distributed and the privacy of honest user data can very quickly and easily get compromised. Hence, it is crucial for security that encryption keys be unique to users, and the adversary gaining control of a particular user’s key does not compromise the security of other users’ data.

Multi-Input FE for Quadratic Functions. Recently, Agrawal, Goyal, and Tomida (AGT) [9] provided the first construction of multi-input functional encryption for quadratic functions. In more detail, they construct an n-input MIFE scheme for the function class $\mathcal {F}_{m,n}$, which is defined as follows. Each function $f \in \mathcal {F}_{m,n}$ is represented by a vector $\textbf{c}\in \mathbb {Z}^{(mn)^{2}}$. For inputs $\textbf{x}_{1} , \ldots ,\textbf{x}_{n} \in \mathbb {Z}^{m}$, f is defined as $f(\textbf{x}_{1} , \ldots ,\textbf{x}_{n}) = \langle {\textbf{c}},{\textbf{x}\otimes \textbf{x}}\rangle$ where $\textbf{x}=(\textbf{x}_{1}|| \cdots ||\textbf{x}_{n})$ and $\otimes$ denotes the Kronecker product. In their quadratic MIFE scheme for $\mathcal {F}_{m,n}$, a user can encrypt $\textbf{x}_{i} \in \mathbb {Z}^{m}$ to $\textsf{CT}_{i}$ for slot $i \in [n]$, a key generator can compute a secret key ${\textsf{SK}}$ for $\textbf{c}\in \mathbb {Z}^{(mn)^{2}}$, and decryption of $\textsf{CT}_{1} , \ldots ,\textsf{CT}_{n}$ with ${\textsf{SK}}$ reveals only $\langle \textbf{c}, \textbf{x}\otimes \textbf{x} \rangle$ and nothing else.

However, while this result makes exciting progress in the domain of direct constructions for MIFE by providing the first candidate supporting quadratic functions, it suffers from the severe drawback that all the encryptors must share the same master key for encryption. As described above, this limits the applicability of the construction for many meaningful practical applications, e.g. when the system is susceptible to insider attacks. Moreover, having a single master key for all users creates a single point of failure which makes the system vulnerable to not only attack but also inadvertent leakage/misuse. Decentralizing trust is an overarching goal in cryptography, and this motivates to design a scheme where users have unique encryption keys and the adversarial model is strong enough to capture corruption of some subset of these.

Multi-Client Functional Encryption. A generalization of multi-input functional encryption is the notion of multi-client functional encryption (MCFE) where the ciphertext is additionally associated with a label. In more detail, encryptor i now encrypts not only the input $\textbf{x}_i$ but also a public label $\ell _i$ to obtain $\textsf{CT}(i,\textbf{x}_i, \ell _i)$. A functional key ${\textsf{SK}}_f$ for any n-ary function f can be used to decrypt $\{\textsf{CT}(i, \textbf{x}_i, \ell _i)\}_{i \in [n]}$ if and only if all the labels match, i.e. $\ell _i = \ell$ for all $i \in [n]$. Note that setting all labels to a single value (say “TRUE”) recovers the notion of MIFE, which allows unrestricted combinations of ciphertexts across slots. The more expressive MCFE provides additional control over allowable combinations of ciphertexts, which is very useful for several applications – for instance, in the example of computing on encrypted genomic data discussed above, being able to filter records based on some label such as ethnicity = African may help to substantially reduce the number of inputs that participate in the study, making the process more efficient.

We emphasize that regardless of the security model (all-or-nothing or fine-grained), the motivation of labelling functionality is to better control the decryption pattern to reduce the information that a decrypter can learn. In the plain n input MIFE setting, where Q ciphertexts per slot are available, the decrypter can potentially compute $Q^n$ function values, which reveal a large amount of information about the underlying plaintexts. However, using Q distinct labels to label every ciphertext in each slot, we can reduce the number of function values revealed to as little as Q. Thus, the labelling functionality is quite useful for controlling the amount of information that a decrypter learns.

It is worth noting that for an MIFE construction supporting general circuits, MCFE can easily be captured by adding an additional check in the function key to verify that all the labels are equal, but for restricted function classes like linear or quadratic functions, MCFE is more powerful than MIFE. In the arena of direct constructions from simple assumptions, the notion of MCFE has been studied for the case of linear functions [1, 2, 21, 26, 29] but not for quadratic functions, to the best of our knowledge.

Our Results. We advance the state-of-the-art in MIFE, and propose new constructions with stronger security and broader functionality.

• Stronger Security: Typically, in the MIFE security game, an attacker is allowed to either corrupt all or none¹ of the users who can encrypt the data. Here we study MIFE security in a “fine-grained” corruption model where an attacker can corrupt even non-trivial subset of the users, instead of only the trivial subsets.    We formalize such a fine-grained corruption model by providing each user a unique encryption key, and letting the attacker corrupt any subset of the encryption keys. We require that, even after corruption of any non-trivial subset of encryption keys, the scheme still satisfies the MIFE-style security for all ciphertexts generated using honest encryption keys. We give a construction for a MIFE system whose security can be proven in this fine-grained corruption model, instead of the standard all-or-nothing corruption model. Our construction departs significantly from the existing AGT quadratic MIFE scheme [9] as we need to tackle a more general class of attackers.    We observe that while several inner product MIFE schemes already have stronger security in the context of MCFE [1, 10, 22], achieving it in quadratic MIFE is much more difficult. Intuitively, a decrypter in a quadratic MIFE system is allowed to learn a function value on cross terms derived from different slots, and achieving this without heavy machinery such as obfuscation seems to require the encryption keys to be correlated with each other (this is also the case for the AGT scheme). Due to the correlation, the corruption of even a single encryption key affects the security of ciphertexts for all the other slots. This is in contrast to inner product MIFE, which is basically obtained by running independent single-input inner product FE instances in parallel.

• Broader Functionality: In MCFE, each encryptor can specify a special label, to tag each ciphertext with appropriate metadata, such that ciphertexts with only exactly matching metadata/labels can be decrypted together. Here we upgrade our MIFE scheme to additionally support ciphertext labelling. While the functionality of our upgraded MIFE scheme matches that of MCFE for quadratic functions, our security guarantee falls short of the general corruption model studied for MCFE. In our model, all encryptors share a secret key, therefore this yields a secret-key version of quadratic MCFE, which we denote by SK-MCFE. We leave the problem of proving security in the general corruption model as an important open problem.

1.1 Technical Overview

The starting point for both of our MIFE and SK-MCFE schemes for quadratic functions is the recent AGT scheme [9]. The AGT construction necessitates that all encryptors share the same master secret key, thus throughout the sequel we will refer to it as the “SK-MIFE ” scheme.

A Simplified Overview of the AGT SK-MIFE Scheme. The AGT scheme uses three building blocks – (i) SK-FE for inner product (IPFE), (ii) SK-FE for predicate inner product (pIPFE), and (iii) SK-MIFE for mixed-group inner product. The mixed-group property of (iii) is necessary for a technical reason in the security proof, but for now we can consider it as SK-MIFE for inner product (IP-MIFE). And, for security, all of the underlying schemes are required to satisfy the corresponding function-hiding security property. Concretely, the required MIFE schemes are summarized in Table 1.²

Table 1. Description of input and function classes for IPFE, pIPFE, IP-MIFE.

Notation. We denote IPFE ciphertexts of $\textbf{v}$ by $\textsf{iCT}[\textbf{v}]$, pIPFE ciphertexts of $(\textbf{v}_{1},\textbf{v}_{2})$ by $\textsf{pCT}[(\textbf{v}_{1},\textbf{v}_{2})]$ and IP-MIFE ciphertexts of $\textbf{v}$ for slot i by $\textsf{miCT}_{i}[\textbf{v}]$ under some master secret keys $\textsf{iMSK}$, $\textsf{pMSK}$, $\textsf{miMSK}$, respectively. Similarly we denote IPFE secret keys of $\textbf{v}$ by $\textsf{iSK}[\textbf{v}]$, pIPFE secret keys of $(\textbf{v}_{1},\textbf{v}_{2})$ by $\textsf{pSK}[(\textbf{v}_{1},\textbf{v}_{2})]$ and IP-MIFE secret keys for $\textbf{v}$ by $\textsf{miSK}[\textbf{v}]$ under the same master secret keys $\textsf{iMSK}$, $\textsf{pMSK}$, $\textsf{miMSK}$, respectively.

AGT Scheme Description. Let us start by recalling the structure of ciphertexts and secret keys in the AGT SK-MIFE scheme. At a high level, an AGT ciphertext $\textsf{CT}_{i}$ of $\textbf{x}\in \mathbb {Z}^{m}$ and ${\textsf{SK}}$ for $\textbf{c}\in \mathbb {Z}_p^{(mn)^{2}}$ are of the following form:

$$\begin{aligned}&\textsf{CT}_{i} = \left( \left\{ \textsf{pCT}[(\textbf{h}, \textbf{b}_{j})], \;\textsf{pSK}[(\widetilde{\textbf{h}}, \widetilde{\textbf{b}}_{j})]\right\} _{j \in [m]},\; \textsf{iCT}[\textbf{d}], \;\textsf{iSK}[\widetilde{\textbf{d}}], \;\textsf{miCT}_{i}[\textbf{f}] \right) \end{aligned}$$

(1)

$$\begin{aligned}&{\textsf{SK}}= \left( \left\{ \sigma _{i,k}\right\} _{i,k \in [n]}, \textsf{miSK}[\widetilde{\textbf{f}}] \right) \end{aligned}$$

(2)

for some $\mathbb {Z}_p$ vectors $\textbf{b}_{j}, \widetilde{\textbf{b}}_{j}, \textbf{d}, \widetilde{\textbf{d}}, \textbf{f},\widetilde{\textbf{f}}, \textbf{h}, \widetilde{\textbf{h}}$ and $\mathbb {Z}_p$ elements $\sigma _{i,k}$.

Now a message vector $\textbf{x}$ is encoded in the vectors $\textbf{b}_{j}, \widetilde{\textbf{b}}_{j}$, and the remaining vectors in the ciphertext are only added to either tie together separate components of different AGT ciphertexts, or randomize a portion of a single AGT ciphertext. We refer the reader to [9] for a more detailed overview, but for our purposes, it is enough to understand how the decryption algorithm works.

Consider a sequence of n AGT ciphertexts $\textsf{CT}_{1} , \ldots ,\textsf{CT}_{n}$ and a corresponding secret key ${\textsf{SK}}$. The decryptor first runs the decryption algorithm for the pIPFE scheme for all possible input combinations. That is, for all $i, k \in [n]$ and $j, \ell \in [m]$, it computes

$$\begin{aligned} z_{i, j, k, \ell } = \textsf{pDec}(\textsf{pCT}[(\textbf{h}_{i}, \textbf{b}_{i,j})], \textsf{pSK}[(\widetilde{\textbf{h}}_{k},\widetilde{\textbf{b}}_{k,\ell })]). \end{aligned}$$

(3)

As it turns out, the underlying encoding procedure used in AGT ensures that each such term is of the form $z_{i, j, k, \ell } = \textbf{x}_{i}[j]\textbf{x}_{k}[\ell ] + u_{i,j,k,\ell }$, where $u_{i,j,k,\ell }$ is a pseudorandom masking term such that $\sum \textbf{c}[(i,j,k,\ell )] u_{i,j,k,\ell } = \langle \textbf{c}, {\textbf{u}} \rangle$ can be computed by combining the remaining portions of the ciphertexts and secret key. That is, the decryptor first computes

$$ \sum \textbf{c}[(i,j,k,\ell )] z_{i,j,k,\ell } = \sum \textbf{c}[(i,j,k,\ell )] \textbf{x}_{i}[j]\textbf{x}_{k}[\ell ] + \sum \textbf{c}[(i,j,k,\ell )] u_{i,j,k,\ell } $$

where $\sum \textbf{c}[(i,j,k,\ell )] \textbf{x}_{i}[j]\textbf{x}_{k}[\ell ]$ is the desired output, and then it computes $\sum \textbf{c}[(i,j,k,\ell )] u_{i,j,k,\ell } = \langle \textbf{c}, {\textbf{u}} \rangle$ by combining the $(\textsf{iCT}[\textbf{d}], \textsf{iSK}[\widetilde{\textbf{d}}], \textsf{miCT}_{i}[\textbf{f}])$ portion of each ciphertext amongst themselves and also with the secret key $(\left\{ \sigma _{i,k}\right\} _{i,k \in [n]}, \textsf{miSK}[\widetilde{\textbf{f}}])$.

Achieving Strong Fine-Grained Security. Recall that in the stronger fine-grained corruption model, each encryptor has a unique encryption key, and the adversary is allowed to corrupt any subset of encryption keys in the security game. Throughout the sequel, we refer to such a scheme as plain MIFE in contrast to SK-MIFE.

Before describing our main ideas, we highlight the reason as to why AGT is not already secure in this stronger corruption model. Observe that each component of the AGT ciphertext $\textsf{CT}_{i}$ is generated under the same master secret key of the corresponding scheme over all slots. In other words, it is essential that all encryption keys include the same IPFE, pIPFE, and IP-MIFE master secret keys. As it turns out, this is one of the main barriers to proving the SK-MIFE construction of AGT to be strongly secure. This is because the scheme ends up being completely insecure if encryption keys for any slot are revealed! Basically, revealing only the underlying pIPFE master secret key allows one to completely decrypt any ciphertexts of the AGT scheme.

While this seems like a major technical barrier at first, we observe that there is a very elegant way to get around this problem by relying on the underlying homomorphic properties satisfied by the SK-MIFE scheme. Although, the AGT SK-MIFE construction can not be used as is since the usage of the pIPFE scheme prevents any useful type of ciphertext homomorphism, we are able to simplify the underlying SK-MIFE construction that not only avoids the usage of pIPFE completely, but also leads to an interesting homomorphism property that we show is very useful in upgrading any weakly secure SK-MIFE into a strongly secure MIFE scheme.

The Special Property. Let us start by describing the special homomorphism property P that we crucially rely on. It states that there exists an explicit and efficient algorithm $\widetilde{\textsf{Enc}}$, and a sequence of public elementary messages $e_{i,1} , \ldots ,e_{i,d} \in \mathcal {X}_{i}$ ($\forall i \in [n]$) such that – for every slot $i \in [n]$ and message $x_i \in \mathcal {X}_i$, the following two distributions are statistically indistinguishable:

$$\begin{aligned}\begin{gathered} \left\{ \left( \textsf{PP}, \{\textsf{CT}_{i,j}\}_{j \in [d]}, \textsf{CT}_{i} \right) : \textsf{CT}_{i} \leftarrow \textsf{Enc}(\textsf{MSK}, i, x_i)\right\} , \\ \left\{ \left( \textsf{PP}, \{\textsf{CT}_{i,j}\}_{j \in [d]}, \textsf{CT}_{i} \right) : \textsf{CT}_{i} \leftarrow \widetilde{\textsf{Enc}}(\left\{ \textsf{CT}_{i,j}\right\} _{j}, x_i)\right\} \end{gathered}\end{aligned}$$

where $(\textsf{PP}, \textsf{MSK}) \leftarrow \textsf{Setup}(1^{\lambda })$ and $\textsf{CT}_{i, j} \leftarrow \textsf{Enc}(\textsf{MSK}, i, e_{i, j})$ for $j \in [d]$.

Property P to MIFE. Assuming there exists an SK-MIFE scheme satisfying property P, our main observation is that there exists a generic compiler to upgrade it to a MIFE for the same function class in which an attacker can corrupt any arbitrary set of encryption keys. That is, consider any SK-MIFE scheme $({\textsf {Setup}}', \textsf{Enc}', {\textsf {KeyGen}}', \textsf{Dec}')$ for some function class $\mathcal {F}$ satisfying property P, our compiler upgrades it to an MIFE scheme $({\textsf {Setup}}, \textsf{Enc}, {\textsf {KeyGen}}', \textsf{Dec}')$ for $\mathcal {F}$ as follows:

• $\textsf{Setup}(1^{\lambda }, 1^{n})$: It computes $\textsf{PP}, \textsf{MSK}\leftarrow {\textsf {Setup}}'(1^{\lambda })$ and $\textsf{CT}_{i,j} \leftarrow \textsf{Enc}'(\textsf{MSK}, i, e_{i,j})$ for all $i \in [n], j \in [d]$, and sets $\textsf{EK}_{i} = \{\textsf{CT}_{i,j}\}_{j}$ for all $i \in [n]$. Then, it outputs the parameters as $\textsf{PP}, \{\textsf{EK}_{i}\}_{i}, \textsf{MSK}$.

• $\textsf{Enc}(\textsf{EK}_{i}, x)$: It computes $\textsf{CT}_{i} \leftarrow \widetilde{\textsf{Enc}}(\left\{ \textsf{CT}_{i,j}\right\} _{j}, x)$ and outputs $\textsf{CT}_{i}$.

The correctness follows directly from the correctness of the underlying SK-MIFE scheme and the statistical closeness of the output distributions between $\textsf{Enc}$ and $\widetilde{\textsf{Enc}}$. And, the proof of security also follows via a hybrid argument. The main idea is to first switch how each challenge ciphertext is generated. That is, instead of computing it as $\widetilde{\textsf{Enc}}(\left\{ \textsf{CT}_{i,j}\right\} _{j}, x^{\beta })$, the challenger computes it directly as $\textsf{Enc}(\textsf{MSK}, i, x^{\beta })$ (where $\beta \in \{0,1\}$ and $x^{0}, x^{1}$ are the challenge messages). Note that this readily follows from the statistical closeness, and thus, by relying on the regular security of the underlying SK-MIFE scheme, we can prove the stronger security for our MIFE scheme. This is because the reduction algorithm can simulate a corrupted encryption key $\textsf{EK}_{i} = \{\textsf{CT}_{i,j}\}_{j \in [d]}$ by querying its own oracle on the elementary messages $e_{i,1} , \ldots ,e_{i,d}$. For more details, we refer the reader to the main body.

Building SK-MIFE with Property P . In order to obtain our final result, we need to instantiate the above generic compiler with an SK-MIFE scheme for quadratic functions with property P. As mentioned earlier, our core idea in this part is to rely on the homomorphic structure of the AGT SK-MIFE scheme. Recall that a ciphertext in the AGT scheme consists of bilinear source group elements. Thus, we can define a group operation over the AGT ciphertexts by element-wise multiplication of group elements (and we use addition for the group operation in what follows). Let $\textsf{CT}_{i}[\textbf{x}]$ be a slot-i encryption of $\textbf{x}$ in the AGT scheme. Our observation is that if for any $a_1, a_2 \in \mathbb {Z}_p$, we have

$$\begin{aligned} a_{1}\textsf{CT}_{i}[\textbf{x}_{1}] + a_{2}\textsf{CT}_{i}[\textbf{x}_{2}] = \textsf{CT}_{i}[a_{1}\textbf{x}_{1}+a_{2}\textbf{x}_{2}], \end{aligned}$$

(4)

then we can achieve P by simply setting the elementary messages to be $\textbf{e}_{1} , \ldots ,\textbf{e}_{n}$, where $\textbf{e}_{j}$ is the one-hot vector with the j-th element being one, and defining $\widetilde{\textsf{Enc}}$ using the appropriate group operations. Unfortunately, this is not the case!

Insufficiency of AGT. To better understand the reason for failure, we need to open up the encryption abstractions used in AGT to their underlying bilinear form. Informally, an AGT ciphertext $\textsf{CT}_{i}$ for $\textbf{x}\in \mathbb {Z}_p^{m}$ looks like $\textsf{CT}_{i} = ([\textbf{v}\textbf{M}_{i}]_{1}, [\textbf{w}\textbf{N}_{i}]_{2})$. Here $[\cdot ]_{1}, [\cdot ]_{2}$ denote element-wise group exponentiation in bilinear groups $G_{1}, G_{2}$, and $\textbf{M}_{i}, \textbf{N}_{i}$ are common matrices shared among all ciphertexts for slot i. Also, each element of $\textbf{v}, \textbf{w}$ depends on $\textbf{x}$ and the random tape used in encryption. Concretely, each element of $\textbf{v}, \textbf{w}$ is one of the following four types — (i) 1; (ii) $\textbf{x}[j]$ for some $j \in [m]$; (iii) a fresh random $\mathbb {Z}_p$ element; or (iv) an element of the tuple $(b, c, b \ell , c \ell )$ where $b, c, \ell$ are fresh random $\mathbb {Z}_p$ elements.

From the viewpoint of well-formedness of a homomorphically operated ciphertext, it is not hard to see that the elements (ii) and (iii) will stay consistent with the homomorphism Eq. (4), while the elements (i) and (iv) will no longer be well-formed after the group operations. This is because, after the homomorphic addition as Eq. (4), the element (i) becomes $a_{1}+a_{2}$, while the element (iv) become an elements of the tuple $(a_{1}b_{1}+a_{2}b_{2}, a_{1}c_{1}+a_{2}c_{2}, a_{1}b_{1}\ell _{1}+a_{2}b_{2}\ell _{2}, a_{1}c_{1}\ell _{1}+a_{2}c_{2}\ell _{2})$. While an element (i) can still be well-formed as long as $a_{1}+a_{2}=1$, an element (iv) will never be well-formed (unless $\ell _{1} = \ell _{2}$, which occurs with only negligible probability).

Stripping Away pIPFE from AGT. Diving a bit further into the structure and semantics of the AGT SK-MIFE scheme, we find out that the elements (iv) are derived from the pIPFE scheme. So, a natural thought is if we can remove the pIPFE scheme from AGT, then we can eliminate the elements (iv) thereby solving the above problem. However, the usage of the pIPFE scheme in the AGT template was crucial as replacing it with a (non-predicate) IPFE scheme enabled a mix-and-match attack wherein an attacker can illegally combine portions of two different ciphertexts for the same slot. Concretely, for two ciphertexts $\textsf{CT}^{1}_{i}, \textsf{CT}^{2}_{i}$ in the same slot, pIPFE prevents decryptor from computing $\textsf{pDec}(\textsf{pCT}^{1}_{i,j}, \textsf{pCT}^{2}_{i,\ell })$ in the decryption process as in Eq. (3) (meaning that $\langle \textbf{h}^{1}, \widetilde{\textbf{h}}^{2} \rangle \ne 0$ if $\textbf{h}^{1}$ and $\widetilde{\textbf{h}}^{2}$ are vectors derived from two different ciphertexts for the same slot i).

Although this seems to be a major bottleneck at first, we make an important observation that if each encryptor computes and encrypts all possible quadratic terms between its own message vector at the time of encryption, then a decryptor does not need to generate the quadratic terms derived from the same slot via the pIPFE decryption. Therefore, the mix-and-match problem can be rather easily solved by replacing pIPFE with a plain (non-predicate) IPFE scheme. And, since this new encryption method only increases the length of the underlying encrypted vector from m to $m^2$, thus it is still efficient. We refer to Definition 2.6 and 2.7 for more details.

Final Rerandomization Trick. While it seems that we are done at this point, unfortunately this is still not sufficient. And, the reason is the fact that even after removing elements (iv), we cannot achieve the property P by using $\textbf{e}_{1} , \ldots ,\textbf{e}_{n}$ as the public elementary messages from two reasons. First, $\sum _{j} \textbf{x}[j]$ is not necessarily 1, and thus elements (i) may not be 1 after the homomorphic addition. Second, elements (iii) depend on $\textbf{x}$ and the random tape used to generate the ciphertexts of $\textbf{e}_{i}$, and thus not independently random after the homomorphic addition. The second reason can be visualized as the resulting ciphertext containing far less entropy than a freshly sampled ciphertext.

However, we solve these issues by the following rerandomization trick. Our idea is to additionally include a large sequence of ${\textbf{0}}$ vectors to the list of elementary messages, and sample a fresh sequence of random elements which will be used to homomorphically add each encryption of ${\textbf{0}}$ to the underlying homomorphically computed ciphertext such that the resulting ciphertext has sufficient entropy. That is, for a sufficiently large D, we define $\widetilde{\textsf{Enc}}$ as follows: $\widetilde{\textsf{Enc}}\left( (\{\textsf{CT}_{i}[\textbf{e}_{j}]\}_{j \in [m]}, \{\textsf{CT}_{i,j}[{\textbf{0}}]\}_{j \in [D]}),\textbf{x} \right)$ computes $\textsf{CT}_{i}[\textbf{x}]$ as

$$\begin{aligned} \textsf{CT}_{i}[\textbf{x}] = \textsf{CT}_{i,1}[{\textbf{0}}] + \sum _{j \in [m]} \textbf{x}_{i}[j] \big (\textsf{CT}_{i}[\textbf{e}_{j}] - \textsf{CT}_{i,1}[{\textbf{0}}]\big ) + \sum _{j \in [\frac{D- 1}{2}]} \gamma _{j}(\textsf{CT}_{i, 2j}[{\textbf{0}}] - \textsf{CT}_{i, 2j + 1}[{\textbf{0}}]), \end{aligned}$$

where $\gamma _{1} , \ldots ,\gamma _{(D- 1)/2} \leftarrow \mathbb {Z}_p$.

This solves the second problem as now the elements (iii) are distributed randomly if $D$ is sufficiently large due to the fresh entropy introduced by $\gamma _{1} , \ldots ,\gamma _{(D- 1)/2}$. And, since we have $\sum _{j \in [m]} (\textbf{x}_{i}[j] - \textbf{x}_{i}[j]) + \sum _{j \in [(D-1)/2]} (\gamma _{j} - \gamma _{j}) = 0$, thus element (i) is also equal to 1 in $\textsf{CT}_{i}[\textbf{x}]$. Hence, the above rerandomization trick combined with the pIPFE removal strategy gives us our SK-MIFE scheme for quadratic functions with property P, which in turn gives us our quadratic MIFE scheme secure in the stronger fine-grained corruption model.

Supporting the Ciphertext Labelling Functionality. Finally, we provide a rather simple yet incredibly useful mechanism to annotate labels with SK-MIFE ciphertexts. This adds the feature of multi-client style encryption to the quadratic SK-MIFE scheme. To this end, we look back at the existing techniques to achieve desired labelling for IP-MIFE schemes (that is, the ideas used to obtain IP-MCFE, or in other words, MCFE for inner product), but find that all techniques are rather specific to inner product. The prior works basically use the following blueprint [1, 10, 21, 22]. The MCFE schemes use a (single-input) IPFE scheme as a building block, and a ciphertext of the MCFE for the i-th slot message $\textbf{x}_{i}$ with a label $\textsf{lab}$ is simply a ciphertext of the IPFE scheme for some vector $\widetilde{\textbf{x}}_{i}$ related to $\textbf{x}_{i}$ and $\textsf{lab}$. A secret key of the MCFE scheme for $\textbf{c}=(\textbf{c}_{1}||\ldots ||\textbf{c}_{n})$ contains IPFE secret keys for some vector $\widetilde{\textbf{c}}_{i}$ related to $\textbf{c}$ for $i \in [n]$, and decryption for slot-i reveals

$$ \langle \widetilde{\textbf{x}}_{i}, \widetilde{\textbf{c}}_{i} \rangle = \langle \textbf{x}_{i}, \textbf{c}_{i} \rangle + u_{i} $$

where $u_{i}$ is a masking term such that $\sum _{i \in [n]}u_{i}$ is equal to 0 (or a computable value by the decryptor) only when $\widetilde{\textbf{x}}_{i}$ is associated with the same label for all i. Hence, the decryptor can learn only $\sum _{i} \langle \textbf{x}_{i}, \textbf{c}_{i} \rangle$ as desired. However, the structure of the only known MIFE scheme for quadratic functions by AGT, as observed, is quite different from this blueprint, and thus we need a new approach.

Our starting point is again the AGT MIFE scheme where recall the ciphertext has the form as described in Eq. (1). A natural first thought is to try to replace all the three underlying IPFE, pIPFE, and IP-MIFE schemes with their labelled counterparts. After a quick glance, it appears that this would be a viable strategy since if we could annotate each component in the AGT ciphertext with a label, then the entire AGT ciphertext will be labelled as well.

As we elaborated during the description of our MIFE construction, the application of pIPFE in the AGT template can be replaced with any IPFE scheme (ignoring the quadratic increase in the overall ciphertext size). Concretely, we showed that the ciphertext $\textsf{CT}$ of the modified AGT scheme can be written as

$$ \textsf{CT}_{i} = \left( \left\{ \textsf{iCT}^{(1)}[\textbf{b}_{j}], \textsf{iSK}^{(1)}[\widetilde{\textbf{b}}_{j}]\right\} _{j \in [m]},\; \textsf{iCT}^{(2)}[\textbf{d}], \;\textsf{iSK}^{(2)}[\widetilde{\textbf{d}}], \;\textsf{miCT}_{i}[\textbf{f}] \right) , $$

where $(\textsf{iCT}^{(1)}, \textsf{iSK}^{(1)})$ and $(\textsf{iCT}^{(2)}, \textsf{iSK}^{(2)})$ are generated by two separate master secret keys $\textsf{iMSK}^{(1)}$ and $\textsf{iMSK}^{(2)}$, respectively. Thus, it seems like if we can annotate both, the IPFE and the IP-MIFE, components of the modified AGT scheme with the same label, then the resulting quadratic MIFE scheme will also support ciphertext labelling functionality.

Now to annotate the IP-MIFE component of the ciphertext, we need a labelled version of the SK-MIFE scheme for mixed-group inner products with function-hiding security as a counterpart. Although such a scheme for inner product is not already known, we were able to construct a new scheme with the desired properties by combining ideas from the SK-MIFE scheme for mixed-group inner product in [9] and the MCFE scheme for inner product in [10]. We refer the reader to Sect. 3 for the exact details.

Finally, to get the desired result, we simply need a mechanism to annotate the IPFE component of the AGT ciphertexts with labels such that ciphertexts with different labels can no longer be combined. Our idea is to simply keep a PRF key K as part of the overall system master key, and use the PRF key K to sample a label-dependent IPFE key at the time of encryption. That is, the setup no longer samples the IPFE keys used during the encryption, but instead the encryptor first samples the IPFE keys using $\textsf{PRF}(K, \textsf{lab})$ as the randomness where $\textsf{lab}$ is the specified label, and then uses those keys to compute the appropriate ciphertext components. Clearly, ciphertexts encrypted w.r.t. different labels can no longer be combined since the underlying ciphertext components are now incompatible (as they are sampled using independent IPFE keys). And, basically by iterating the hybrid sequence of the SK-MIFE scheme for quadratic functions in [9] per queried label, we can also prove security in the secret-key MCFE setting.

Open Problems. We conclude the introduction by discussing some open problems. To the best of our knowledge, this is the first work proposing a technique to convert SK-MIFE to MIFE with stronger security. Since our technique is applicable to all SK-MIFE schemes with property $\textsf{P}$, exploring other classes of MIFE to which our technique is applicable is an interesting open problem. We observe that this conversion does seem applicable to group-based SK-MIFE schemes for inner product in [4, 5] since they enjoy a nice homomorphic property. However, MIFE schemes for inner product with the stronger security are already known so this does not yield a new result. Nevertheless it does give a new pathway to obtaining these results since known MCFE schemes for inner product are constructed without going through SK-MIFE.

The second open question is the construction of a (public-key) MCFE scheme for quadratic functions. Interestingly, while the above ideas are sufficient for SK-MCFE for quadratic functions, we were unable to prove security in the public-key setting. First, in the above abstraction, the usage of PRFs to annotate the IPFE portion of the modified AGT ciphertext requires the encryption key for each slot to contain the secret PRF key K. Thus, corruption of even one encryption key completely breaks down the scheme. An approach is to sample a separate PRF key for each pair of encryption slots, however, even that does not seem to suffice as corrupting even a single secret key for a particular encryption slot seems to provide an attacker a mechanism to maul the labels from honest ciphertexts, thereby breaking security. Other natural approaches run into similar roadblocks. We leave the question full fledged MCFE as an exciting open problem.

We remark that the approach of providing generic compilers to “upgrade” security notions of primitives can be very useful in enabling new constructions since it simplifies the minimum building block that must be instantiated. For the case of restricted functionalities like linear [1] or quadratic functions (this), such compilers have required the underlying scheme to satisfy “nice” algebraic properties. Can this requirement be removed? Given current techniques, it seems difficult to remove such requirements without relying on strong tools like obfuscation. However, exploring this question more fully is a promising line of research.

Finally, it is evidently a fascinating question whether we can “lift” the degree of the underlying function class beyond 2 without relying on strong tools like compact functional encryption or obfuscation. Currently, we have results from single assumptions in the arena of degree $\le 2$ [1, 2, 4, 5, 9, 21, 23, 29, 32] and results from combinations of assumptions for classes like $\textsf{NC}_1$ and beyond [27, 28] even in the single input setting. While compact functional encryption can be generalized to the multi-input setting [13, 17], can we have constructions of MIFE and MCFE for bigger classes of functions without relying on obfustopia primitives?

2 Preliminaries

Notation. We begin by defining the notation that we will use throughout the paper. We use bold letters to denote vectors and the notation [a, b] to denote the set of integers $\{k\in \mathbb {N}~|~a\le k\le b\}$. We use [n] to denote the set [1, n]. For vector $\textbf{v}$, $\textbf{v}[i]$ denotes the i-th element of $\textbf{v}$. For $(i_{n} , \ldots ,i_{1}) \in [N_{n}] \times \cdots \times [N_{1}] \subset \mathbb {N}^{n}$, we sometimes identify $(i_{n} , \ldots ,i_{1})$ as $\sum _{j \in [2,n]}\left( (i_{j}-1)\prod _{\ell \in [j-1]}N_{\ell }\right) +i_{1}$, which is an element in $[N_{1}N_{2}\cdots N_{n}]$. This identification is used to introduce an order in the elements in $[N_{1}] \times \cdots \times [N_{n}]$. For a matrix ${\textbf{A}} = (a_{j,\ell })_{j,\ell }$ over $\mathbb {Z}_p$, $[{\textbf{A}}]_{i}$ denotes a matrix over $G_{i}$ whose $(j, \ell )$-th entry is $g_{i}^{a_{j,\ell }}$, and we use this notation for vectors and scalars similarly. Throughout the paper, we use $\lambda$ to denote the security parameter.

We will use a pseudorandom function (PRF) and standard cryptographic bilinear groups where the matrix decisional Diffie-Hellman (MDDH) assumption holds.

2.1 Multi-Input Functional Encryption

Syntax. Let n be the number of encryption slots, and $\mathcal {F}= \{\mathcal {F}_n\}_{n \in \mathbb {N}}$ be a function family such that, for all $f \in \mathcal {F}_n$, $f: \mathcal{X}_{1} \times \cdots \times \mathcal{X}_{n} \rightarrow \mathcal{Y}$. Here $\mathcal{X}_i$ and $\mathcal{Y}$ be the input and output spaces (respectively). A multi-input functional encryption (MIFE)³ scheme for function family $\mathcal {F}$ consists of following algorithms.

• $\textsf{Setup}(1^{\lambda }, 1^n) \rightarrow (\textsf{PP}, \{\textsf{EK}_i\}_i, \textsf{MSK}).$ It takes a security parameter $1^{\lambda }$, number of slots $1^n$, and outputs public parameters $\textsf{PP}$, n encryption keys $\{\textsf{EK}_{i}\}_{i \in [n]}$, a master secret key $\textsf{MSK}$. (The remaining algorithms implicitly take $\textsf{PP}$ as input.)

• $\textsf{Enc}( \textsf{EK}_{i}, x) \rightarrow \textsf{CT}_{i}.$ It takes the i-th encryption key $\textsf{EK}_i$ and an input $x \in \mathcal{X}_{i}$, and outputs a ciphertext $\textsf{CT}_{i}$.

• $\textsf{KeyGen}(\textsf{MSK}, f) \rightarrow {\textsf{SK}}.$ It takes the master key $\textsf{MSK}$ and a function $f \in \mathcal{F}$ as inputs, and outputs a decryption key ${\textsf{SK}}$.

• $\textsf{Dec}(\textsf{CT}_{1} , \ldots ,\textsf{CT}_{n}, {\textsf{SK}}) \rightarrow y.$ It takes n ciphertexts $\textsf{CT}_{1} , \ldots ,\textsf{CT}_{n}$ and decryption key ${\textsf{SK}}$, and outputs a decryption value $y \in \mathcal{Y}$ or a special abort symbol $\bot$.

Correctness. An MIFE scheme for function family $\mathcal {F}$ is correct if for all $\lambda , n \in \mathbb {N},\; (x_{1} , \ldots ,x_{n}) \in \mathcal{X}_{1} \times \cdots \times \mathcal{X}_{n},\; f \in \mathcal{F}_n$, we have

$$\begin{aligned} \Pr \left[ y = f(x_{1} , \ldots ,x_{n}) : \begin{array}{l} (\textsf{PP}, \{\textsf{EK}_{i}\}_i, \textsf{MSK}) \leftarrow \textsf{Setup}(1^{\lambda }, 1^n) \\ \{\textsf{CT}_{i} \leftarrow \textsf{Enc}(i, \textsf{EK}_{i}, x_{i})\}_{i} \\ {\textsf{SK}}\leftarrow \textsf{KeyGen}(\textsf{MSK}, f) \\ y = \textsf{Dec}(\textsf{CT}_{1} , \ldots ,\textsf{CT}_{n}, {\textsf{SK}}) \end{array} \right] = 1. \end{aligned}$$

Definition 2.1

For security, we define two indistinguishability-based security definitions: message-hiding security and function-hiding security. An MIFE scheme is sel-XX-YY-IND-secure ($\text {XX} \in \{\text {pos}, \text {any}\}, \text {YY} \in \{\text {mh}, \text {fh}\}$)⁴ if for any stateful admissible PPT adversary $\mathcal {A}$, there exists a negligible function such that for all $\lambda , n \in \mathbb {N}$, the following probability is negligibly close to 1/2 in $\lambda$:

$$ \Pr \left[ \mathcal {A}(\{\textsf{EK}_{i}\}_{i \in \mathcal {C}\mathcal {S}}, \{\textsf{CT}_{\mu }\}_\mu , \{{\textsf{SK}}_{\nu }\}_\nu ) = \beta : \begin{array}{l} \beta \leftarrow \{0,1\}\\ \textsf{PP}, \{\textsf{EK}_{i}\}_{i \in [n]} , \textsf{MSK}\leftarrow \textsf{Setup}(1^\lambda , 1^n) \\ (\mathcal {C}\mathcal {S}, \mathcal {M}\mathcal {S}, \mathcal {F}\mathcal {S}) \leftarrow \mathcal {A}(1^{\lambda }, \textsf{PP}) \;\;\text {s.t.} \\ \quad \mathcal {C}\mathcal {S}\subseteq [n]\\ \quad \mathcal {M}\mathcal {S}= \{i^{\mu }, x^{\mu , 0}, x^{\mu , 1}\}_{\mu \in [q_{c}]} \\ \quad \mathcal {F}\mathcal {S}= \{f^{\nu , 0}, f^{\nu , 1}\}_{\nu \in [q_{k}]} \\ \{\textsf{CT}_{\mu } \leftarrow \textsf{Enc}(i^{\mu }, \textsf{EK}_{i^{\mu }}, x^{\mu , \beta })\}_\mu \\ \{{\textsf{SK}}_{\nu } \leftarrow \textsf{KeyGen}(\textsf{MSK}, f^{\nu , \beta })\}_\nu \end{array} \right] $$

where the adversary $\mathcal {A}$ is said to be admissible if and only if:

• 1. $f^{0}(x^{0}_{1} , \ldots ,x^{0}_{n}) = f^{1}(x^{1}_{1} , \ldots ,x^{1}_{n})$ for all sequences $(x^{0}_{1} , \ldots ,x^{0}_{n}, x^{1}_{1} , \ldots ,x^{1}_{n}, f^{0}, f^{1})$ such that:

  • For all $i \in [n]$, $[(i, x^{0}_{i}, x^{1}_{i}) \in \mathcal {M}\mathcal {S}]$ or $[i \in \mathcal {C}\mathcal {S}$ and $x^{0}_{i} = x^{1}_{i}]$,

  • $(f^{0}, f^{1}) \in \mathcal {F}\mathcal {S}$.

• 2. When $\text {XX} = \text {pos}$, $q_{c}[i] > 0$ for all $i \in [n]$, where $q_{c}[i]$ denotes the number of elements of the form $(i, *, *)$ in $\mathcal {M}\mathcal {S}$.

• 3. When $\text {YY} = \text {mh}$, $f^{\nu , 0} = f^{\nu , 1}$ for all $\nu \in [q_{k}]$.

MIFE security in secret-key setting. We say an MIFE scheme is secret-key MIFE (SK-MIFE) scheme if all the n encryption keys $\textsf{EK}_i$ are basically the master secret key $\textsf{MSK}$. The security of an SK-MIFE scheme is defined the same way as an MIFE scheme except that the adversary has to set $\mathcal {C}\mathcal {S}=\emptyset$.

2.2 Multi-Client Functional Encryption

A multi-client functional encryption (MCFE) scheme is an extension of MIFE where each ciphertext is now annotated with a unique label such that ciphertexts encrypted for different slots can now only be combined together during decryption as long as the associated labels match for all individual ciphertext pieces. We first define its syntax where we highlight in terms of changes, how MCFE compares with MIFE.

Syntax. An MCFE system is associated with a label space $\mathcal{L}$, in addition to the number of encryption slots n and function class $\mathcal{F}$ as in MIFE. A multi-client functional encryption scheme for function family $\mathcal {F}$ consists of following algorithms.

• $\textsf{Setup}, \textsf{KeyGen}, \textsf{Dec}$ have the same syntax as in MIFE.

• $\textsf{Enc}(\textsf{EK}_{i}, \textsf{lab}, x) \rightarrow \textsf{CT}.$ The encryption algorithm takes the i-th encryption key $\textsf{EK}_i$, a label $\textsf{lab}$, and an input $x \in \mathcal{X}_{i}$, and outputs a ciphertext $\textsf{CT}_{i}$.

Correctness. An MCFE scheme for function family $\mathcal {F}$ is correct if for all $\lambda , n \in \mathbb {N},\; (x_{1} , \ldots ,x_{n}) \in \mathcal{X}_{1} \times \cdots \times \mathcal{X}_{n},\; f \in \mathcal{F}$, and label $\textsf{lab}\in \mathcal{L}$, we have

$$\begin{aligned} \Pr \left[ y = f(x_{1} , \ldots ,x_{n}) : \begin{array}{l} (\textsf{PP}, \{\textsf{EK}_{i}\}_i, \textsf{MSK}) \leftarrow \textsf{Setup}(1^{\lambda }, 1^n) \\ \{\textsf{CT}_{i} \leftarrow \textsf{Enc}(i, \textsf{EK}_{i}, \textsf{lab}, x_{i})\}_{i} \\ {\textsf{SK}}\leftarrow \textsf{KeyGen}(\textsf{MSK}, f) \\ y = \textsf{Dec}(\textsf{CT}_{1} , \ldots ,\textsf{CT}_{n}, {\textsf{SK}}) \end{array} \right] = 1. \end{aligned}$$

That is, if all the ciphertexts are encrypted for the same label, then the decryption works as in MIFE.

MCFE Security in Secret-key Setting. In this work we are mostly interested in the secret-key setting. The intuition behind security for secret-key MCFE is similar to that for secret-key MIFE, with the difference that the admissibility constraint for ciphertexts is defined for each label individually. Below we define it formally.

Definition 2.2

An SK-MCFE scheme is sel-XX-YY-IND-secure ($\text {XX} \in \{\text {pos}, \text {any}\}], \text {YY} \in \{\text {mh}, \text {fh}\}$) if for any stateful admissible PPT adversary $\mathcal {A}$, there exists a negligible function such that for all $\lambda , n \in \mathbb {N}$, the following probability is negligibly close to 1/2 in $\lambda$:

$$ \Pr \left[ \mathcal {A}(\{\textsf{CT}_{\mu }\}_\mu , \{{\textsf{SK}}_{\nu }\}_\nu ) = \beta : \begin{array}{l} (\textsf{PP}, \textsf{MSK}) \leftarrow \textsf{Setup}(1^\lambda , 1^n), \beta \leftarrow \{0,1\}\\ (\mathcal {M}\mathcal {S}, \mathcal {F}\mathcal {S}) \leftarrow \mathcal {A}(1^{\lambda }, \textsf{PP})\;\; \text {s.t.} \\ \quad \mathcal {M}\mathcal {S}= \{i^{\mu }, \textsf{lab}^{\mu }, x^{\mu , 0}, x^{\mu , 1}\}_{\mu \in [q_{c}]} \\ \quad \mathcal {F}\mathcal {S}= \{f^{\nu , 0}, f^{\nu , 1}\}_{\nu \in [q_{k}]} \\ \{\textsf{CT}_{\mu } \leftarrow \textsf{Enc}( \textsf{MSK},i^{\mu }, \textsf{lab}^{\mu }, x^{\mu , \beta })\}_\mu \\ \{{\textsf{SK}}_{\nu } \leftarrow \textsf{KeyGen}(\textsf{MSK}, f^{\nu , \beta })\}_\nu \end{array} \right] $$

where the adversary $\mathcal {A}$ is said to be admissible if and only if:

• 1. $f^{0}(x^{0}_{1} , \ldots ,x^{0}_{n}) = f^{1}(x^{1}_{1} , \ldots ,x^{1}_{n})$ for all sequences $(x^{0}_{1} , \ldots ,x^{0}_{n}, x^{1}_{1} , \ldots ,x^{1}_{n},f^{0}, f^{1}, \textsf{lab})$ such that:

  • For all $i \in [n]$, $(i, \textsf{lab}, x^{0}_{i}, x^{1}_{i}) \in \mathcal {M}\mathcal {S}$,

  • $(f^{0}, f^{1}) \in \mathcal {F}\mathcal {S}$.

• 2. When $\text {XX} = \text {pos}$, for any label $\textsf{lab}$ queried by the adversary, $q_{c}[i, \textsf{lab}] > 0$ for all $i \in [n]$, where $q_{c}[i, \textsf{lab}]$ denotes the number of elements of the form $(i, \textsf{lab}, *, *)$ in $\mathcal {M}\mathcal {S}$.

• 3. When $\text {YY} = \text {mh}$, $f^{\nu , 0} = f^{\nu , 1}$ for all $\nu \in [q_{k}]$.

Remark 2.3

In this paper, we only consider pos-security since a sel-pos-YY-secure MIFE/MCFE scheme can be generically transformed into a sel-any-YY-secure MIFE/MCFE scheme [1, 2, 5, 23].

2.3 Functionalities

In this section, we define basic function classes for MIFE/SK-MCFE that is used in this paper.

Definition 2.4

(Inner Product over Bilinear Groups). Let $\mathbb {G}= (p, G_{1}, G_{2}, G_{T}, g_{1}, g_{2},e)$ be bilinear groups. A function family $\mathcal {F}^{\textsf{IP}}_{m, n, \mathbb {G}}$ for inner products over bilinear groups consists of functions $f:(G_{1}^{m})^{n} \rightarrow G_{T}$. Each $f \in \mathcal {F}^{\textsf{IP}}_{m, n, \mathbb {G}}$ is specified by $[(\textbf{y}_{1} , \ldots ,\textbf{y}_{n})]_{2}$ where $\textbf{y}_{i} \in \mathbb {Z}_p^{m}$ and defined as $f([\textbf{x}_{1}]_{1} , \ldots ,[\textbf{x}_{n}]_{1}) = [\sum _{i \in [n]}\langle \textbf{x}_{i}, \textbf{y}_{i} \rangle ]_{T}.$ We call MIFE/SK-MCFE for $\mathcal {F}^{\textsf{IP}}_{m,n,\mathbb {G}}$ MIFE/SK-MCFE for inner product. Especially, we sometimes call FE for $\mathcal {F}^{\textsf{IP}}_{m,1,\mathbb {G}}$ inner product functional encryption (IPFE).

Note that constructions of IPFE and SK-MCFE for inner product with function-hiding (sel-any-fh) security are already known [10, 33].

Definition 2.5

(Mixed-Group Inner Products). Let $\mathbb {G}= (p, G_{1}, G_{2}, G_{T}, g_{1}, g_{2},e)$ be bilinear groups. A function family $\mathcal {F}^{\textsf{MG}}_{m_{1}, m_{2}, n,\mathbb {G}}$ for mixed-group inner products consists of functions $f:(G_{1}^{m_{1}}\times G_{2}^{m_{2}})^{n} \rightarrow G_{T}$. Each $f \in \mathcal {F}^{\textsf{MG}}_{m_{1},m_{2}, n, \mathbb {G}}$ is specified by $([\textbf{y}_{1,1}]_{2}, [\textbf{y}_{1,2}]_{1} , \ldots ,[\textbf{y}_{n,1}]_{2}, [\textbf{y}_{n,2}]_{1})$ where $\textbf{y}_{i,1} \in \mathbb {Z}_p^{m_{1}}$ and $\textbf{y}_{i,2} \in \mathbb {Z}_p^{m_{2}}$ and defined as $f(([\textbf{x}_{1,1}]_{1},[\textbf{x}_{1,2}]_{2} ), \ldots ,([\textbf{x}_{n,1}]_{1},[\textbf{x}_{n,2}]_{2} )) = [\langle \textbf{x}, \textbf{y} \rangle ]_{T}$ where $\textbf{x}= (\textbf{x}_{1,1},\textbf{x}_{1,2}, \ldots ,\textbf{x}_{n,1},\textbf{x}_{n,2})$ and $\textbf{y}= (\textbf{y}_{1,1},\textbf{y}_{1,2}, \ldots ,\textbf{y}_{n,1},\textbf{y}_{n,2})$. We call MIFE/SK-MCFE for $\mathcal {F}^{\textsf{MG}}_{m_{1},m_{2}, n,\mathbb {G}}$ MIFE/SK-MCFE for mixed-group inner product.

Definition 2.6

(Bounded-Norm Quadratic functions over $\mathbb {Z}$). A function family $\mathcal {F}^{\textsf{QF}}_{m,n,X,C}$ for bounded-norm multi-input quadratic functions consist of functions $f: (\mathcal {X}^{m})^{n} \rightarrow \mathbb {Z}$ where $\mathcal {X}=\{ i \in \mathbb {Z}\mid |i| \le X\}$. Each $f \in \mathcal {F}^{\textsf{QF}}_{m,n,X,C}$ is specified by $\textbf{c}\in \mathbb {Z}^{(mn)^{2}}$ s.t. $||\textbf{c}||_{\infty } \le C$ and $\textbf{c}[(i,j,k,\ell )] = 0$ if $i \ge k$. Then, f specified by $\textbf{c}$ is defined as $f({\textbf{x}}_{1}, \ldots ,{\textbf{x}}_{n}) = \sum _{\begin{array}{c} i,k\in [n], j,\ell \in [m] \end{array}}\textbf{c}[(i,j,k,\ell )]\textbf{x}_{i}[j]\textbf{x}_{k}[\ell ].$ We call MIFE/SK-MCFE for $\mathcal {F}^{\textsf{QF}}_{m,n,X,C}$ MIFE/SK-MCFE for quadratic functions.

Remark 2.7

The original definition of quadratic functions in [9] provides that $\textbf{c}$ is a vector s.t. $\textbf{c}[(i,j,k,\ell )] = 0$ if $(i,j) > (k,\ell )$ instead of $i \ge k$. Actually, the functionality in Definition 2.6 implies the original functionality by defining $g(\textbf{x}_{1} , \ldots ,\textbf{x}_{n}) = f(\textbf{x}'_{1} , \ldots ,\textbf{x}'_{n})$ where $\textbf{x}'_{i} = (\textbf{x}_{i} \otimes \textbf{x}_{i}, \textbf{x}_{i},1)$ and $f \in \mathcal {F}^{\textsf{QF}}_{m,n,X,C}$.

Formally, our contribution in this paper is the constructions of MIFE and SK-MCFE for quadratic functions from pairings. Note that only an SK-MIFE scheme for quadratic functions based on pairings [9] is know prior to our work.

3 SK-MCFE for Mixed-Group Inner Product

In this section, we provide our construction for function-hiding SK-MCFE for mixed-group inner-product (Definition 2.5), which is used as a building block of our MIFE and SK-MCFE schemes for quadratic functions. The construction is similar to the function-hiding SK-MIFE for mixed-group inner-product in [9] by Agrawal, Goyal, and Tomida (AGT). Recall that the AGT SK-MIFE for mixed-group inner-product is obtained by combining a function-hiding SK-MIFE for inner-product and a function-hiding SK-FE for inner product. Our SK-MCFE for mixed-group inner-product is obtained by replacing a function-hiding SK-MIFE for inner-product in the AGT scheme with a function-hiding SK-MCFE for inner-product. Note that a function-hiding SK-MCFE for inner product can be obtained from a function-hiding MCFE scheme for inner product in [10] since SK-MCFE is the special case of MCFE. Additionally, while the MCFE scheme in [10] uses a hash function modeled as a random oracle in encryption, we can replace it with a PRF in the secret-key setting. The function-hiding SK-MCFE scheme for inner product without a random oracle is presented in Fig. 2.

Formally, we construct a function-hiding SK-MCFE scheme for $\mathcal {F}^{\textsf{MG}}_{m_{1},m_{2},n,\mathbb {G}}$ with label space $\mathcal {L}$ from a function-hiding SK-MCFE scheme for $\mathcal {F}^{\textsf{IP}}_{m, n, \mathbb {G}}$ with the same label space $\mathcal {L}$ and a function-hiding FE scheme for $\mathcal {F}^{\textsf{IP}}_{m,1,\mathbb {G}}$ in a generic way. Let $\textsf{icFE}=(\textsf{icSetup}, \textsf{icEnc}, \textsf{icKeyGen}, \textsf{icDec})$ be a function-hiding SK-MCFE for $\mathcal {F}^{\textsf{IP}}_{m, n, \mathbb {G}}$, and $\textsf{iFE}=(\textsf{iSetup}, \textsf{iEnc}, \textsf{iKeyGen}, \textsf{iDec})$ be a function-hiding IPFE scheme (SK-FE for $\mathcal {F}^{\textsf{IP}}_{m, 1, \mathbb {G}}$). Then, our function-hiding SK-MCFE for mixed-group inner product $\mathcal {F}^{\textsf{MG}}_{m_{1},m_{2},n,\mathbb {G}}$ is constructed as shown in Fig. 1.

Fig. 1.

Our mixed-group IP-MIFE scheme.

Due to the limit of the space, we present the correctness and the security proof in the full version.

4 SK-MCFE for Quadratic Functions

As explained in the technical overview, i) our MIFE scheme for quadratic functions can be generically obtained from the modified AGT SK-MIFE scheme for quadratic functions, which does not use a SK-FE scheme for predicate inner product; ii) the modified SK-MIFE scheme can be seen as the special case of our SK-MCFE scheme, where the label space consists of one element. Considering the above two facts, we first present our SK-MCFE scheme for quadratic functions to save the effort of presenting the security proof of the modified SK-MIFE scheme in the construction of our MIFE scheme.

4.1 Construction

Let $\textsf{mgFE}=(\textsf{mgSetup}, \textsf{mgEnc}, \textsf{mgKeyGen}, \textsf{mgDec})$ be an SK-MCFE scheme for mixed-group inner product (Sect. 3) with label space $\mathcal {L}$, and $\textsf{iFE}=(\textsf{iSetup}, \textsf{iEnc}, \textsf{iKeyGen}, \textsf{iDec})$ be a function-hiding IPFE scheme. Also, let $\textsf{PRF}= \left\{ \textsf{PRF}_{\lambda }\right\} _{\lambda \in \mathbb {N}}$ be a PRF family where $\textsf{PRF}_\lambda : \{0, 1\}^{\lambda } \times \mathcal {L}\rightarrow \{0, 1\}^{\lambda }$ and $\mathbb {G}$ be bilinear groups. Below we provide an SK-MCFE scheme for function class $\mathcal {F}^{\textsf{QF}}_{m, n,X,C}$ with the same label space $\mathcal {L}$. Similarly to [9], we can construct our SK-MCFE scheme from MDDH$_{k}$, while it makes the construction and security proof far more complicated as we can see in [9]. Thus, we present the construction based on MDDH$_{1}$ for better readability in this paper.

• $\textsf{Setup}(1^{\lambda }, 1^n)$ samples a random PRF key $K \leftarrow \{0, 1\}^{\lambda }$ and the master keys for the underlying IPFE and SK-MCFE scheme as $(\textsf{iPP}^{(2)},\textsf{iMSK}^{(2)})\leftarrow \textsf{iSetup}(1^{\lambda }),\; (\textsf{mgPP}, \textsf{mgMSK}) \leftarrow \textsf{mgSetup}(1^{\lambda }, 1^n)$ where the vector length of $\textsf{iFE}$ is set as 2, and the vector length of $\textsf{mgFE}$ is set as $m^{2}n+2$ and 1. Note that $\textsf{iPP}^{(2)}=\textsf{mgPP}=\mathbb {G}$. It also samples a sequence of randomization terms as:

  $$\begin{aligned}&\forall ~ i,k \in [n], j,\ell \in [m], \qquad w_{(i,j,k,\ell )} \leftarrow \mathbb {Z}_p\\&\forall ~ i \in [n], j \in [m], \qquad u_{i,j}, \widetilde{u}_{i,j}, v_{i,j}, \widetilde{v}_{i,j} \leftarrow \mathbb {Z}_p\end{aligned}$$

  It outputs the public parameters and master key as

  $$\begin{aligned}&\textsf{PP}=\mathbb {G},\;\; \textsf{MSK}= \left( K, \textsf{iMSK}^{(2)}, \textsf{mgMSK}, \{w_{(i,j,k,\ell )}\}_{i,j,k,\ell }, \{ u_{i,j}, \widetilde{u}_{i,j}, v_{i,j}, \widetilde{v}_{i,j} \}_{i,j} \right) . \end{aligned}$$

• $\textsf{Enc}(\textsf{MSK},i, \textsf{lab}, {\textbf{x}})$ parses $\textsf{MSK}$ as above, and using the PRF key K, it samples a IPFE master key of vector length $mn+3m+4$ as $(\textsf{iPP}^{(1)}, \textsf{iMSK}^{(1)}) \leftarrow \textsf{iSetup}(1^{\lambda }; \textsf{PRF}(K, \textsf{lab}))$. Here we assume (w.l.o.g.) that the MIFE setup algorithm takes $\lambda$ bits as random coins. It then samples random elements $s, \widetilde{s}, r, t \leftarrow \mathbb {Z}_p$. And, it sets vectors ${\textbf{b}}_{j}, \widetilde{\textbf{b}}_{j}$ for $j \in [m]$ as follows:

  $$ {\textbf{b}}_{j} =(\textbf{x}[j],0, s\textbf{e}_{(i,j)}, ru_{i,j}, v_{i,j}, {\textbf{0}}_{3m}), \quad \widetilde{\textbf{b}}_{j} = (\textbf{x}[j],0, \widetilde{s}\textbf{w}_{(*,*,i,j)}, \widetilde{u}_{i,j}, t\widetilde{v}_{i,j}, {\textbf{0}}_{3m}). $$

  where $\textbf{e}_{(i,j)}$ is the mn-dimensional one-hot vector with the (i, j)-th element being 1, and vector $\textbf{w}_{(*,*,i,j)} \in \mathbb {Z}_p^{mn}$ is defined as follows:

  $$ \forall ~ j \in [m], \quad \textbf{w}_{(*,*,i,j)} = (w_{(1,1,i,j)}, w_{(1,2,i,j)} , \ldots ,w_{(n,m, i,j)}) $$

  The encryptor encodes the vectors ${\textbf{b}}_{j}, \widetilde{\textbf{b}}_{j}$ under MIFE as follows:

  $$\begin{aligned}&\forall ~j \in [m], \;\; \textsf{iCT}_{j} \leftarrow \textsf{iEnc}(\textsf{iMSK}^{(1)}, [{\textbf{b}}_{j}]_{1}),\;\; \textsf{iSK}_j \leftarrow \textsf{iKeyGen}(\textsf{iMSK}^{(1)}, [\widetilde{\textbf{b}}_{j}]_{2}). \end{aligned}$$

  It also encodes the random elements $s, \widetilde{s}$ as follows:

  $$\begin{aligned}&\textsf{iCT}\leftarrow \textsf{iEnc}(\textsf{iMSK}^{(2)}, [(s, 0)]_{1}), \;\;\textsf{iSK}\leftarrow \textsf{iKeyGen}(\textsf{iMSK}^{(2)}, [(\widetilde{s}, 0)]_{2}). \end{aligned}$$

  Lastly, it sets $\textbf{f}=(r, t, {\textbf{0}}_{m^{2}n}),\; h=0$, and encrypts elements $\textbf{f},h$ as

  $$ \textsf{mgCT}\leftarrow \textsf{mgEnc}(\textsf{mgMSK},i, \textsf{lab}, ([\textbf{f}]_{1},[h]_{2})). $$

  And the resulting ciphertext is set as below:

  $$ \textsf{CT}= \left( \{\textsf{iCT}_{j}\}_{j}, \{\textsf{iSK}_{j}\}_{j}, \textsf{iCT}, \textsf{iSK}, \textsf{mgCT} \right) . $$

• $\textsf{KeyGen}(\textsf{MSK}, {\textbf{c}})$ parses $\textsf{MSK}$ as above, and the key vector ${\textbf{c}}$ lies in the space $\mathbb {Z}^{(m n)^{2}}$. Let the vector $\widetilde{\textbf{f}}_{i} \in \mathbb {Z}_p^{(2 + m^{2}n)}$ be the following vector: for all $i \in [n]$,

  $$ \widetilde{\textbf{f}}_{i}[1] =\sum _{j,\ell \in [m], k \in [n]}\textbf{c}[(i,j,k,\ell )]u_{i,j}\widetilde{u}_{k,\ell }, \; \widetilde{\textbf{f}}_{i}[2] = \sum _{j,\ell \in [m], k \in [n]}\textbf{c}[(k,\ell ,i,j)]v_{k,\ell }\widetilde{v}_{i,j} $$

  and $\widetilde{\textbf{f}}_{i}$ is zeros at all other places. It also sets $\widetilde{h}_{i}=0$ for all $i \in [n]$. The key generator samples a SK-MCFE secret key corresponding to vectors $\{\widetilde{\textbf{f}}_{i},\widetilde{h}_{i}\}_{i}$ as $\textsf{mgSK}\leftarrow \textsf{mgKeyGen}(\textsf{mgMSK}, \{[\widetilde{\textbf{f}}_{i}]_{2}, [\widetilde{h}_{i}]_{1} \}_{i \in [n]})$, and partial derandomization terms:

  $$ \forall ~i,k \in [n], \quad \sigma _{i,k} = \sum _{j,\ell \in [m]}\textbf{c}[(i,j,k,\ell )]w_{(i,j,k,\ell )} $$

  And, it outputs the secret key as

  $$ {\textsf{SK}}= \left( {\textbf{c}}, \textsf{mgSK}, \{\sigma _{i,k}\}_{i,k} \right) . $$

• $\textsf{Dec}(\textsf{CT}_{1} , \ldots ,\textsf{CT}_{n}, {\textsf{SK}})$ parses the ciphertexts and secret key as:

  $$\begin{aligned}\begin{gathered} \textsf{CT}_i = \left( \{\textsf{iCT}_{i,j}\}_{i,j}, \{\textsf{iSK}_{i,j}\}_{i,j}, \textsf{iCT}_{i}, \textsf{iSK}_{i}, \textsf{mgCT}_{i} \right) ,\;\;{\textsf{SK}}= \left( {\textbf{c}}, \textsf{mgSK}, \{\sigma _{i,k}\}_{i,k} \right) . \end{gathered}\end{aligned}$$

  It runs the MIFE decryption algorithm as:

  $$\begin{aligned}{}[z_{1}]_{T} = \prod _{\begin{array}{c} \begin{array}{c} i,k \in [n]\\ j,\ell \in [m] \end{array} \end{array}} \textsf{iDec}(\textsf{iCT}_{i,j},\textsf{iSK}_{k,\ell })^{\textbf{c}[(i,j,k,\ell )]},\; [z_{2}]_{T} = \prod _{i,k\in [n]}\textsf{iDec}(\textsf{iCT}_{i}, \textsf{iSK}_{k})^{ \sigma _{i, k}} \end{aligned}$$

  It also runs the SK-MCFE decryption algorithm as:

  $$\begin{aligned}{}[z_{3}]_{T} = \textsf{mgDec}(\textsf{mgCT}_{1}, \ldots ,\textsf{mgCT}_{n}, \textsf{mgSK}) \end{aligned}$$

  Finally it outputs z where $[z]_{T} = [z_{1}- z_{2}-z_{3}]_{T}$ by searching for z within the range of $z \le |m^{2}n^{2}CX^{2}|$.

Correctness. Let $s_{i}, \widetilde{s}_{i}, r_{i}, t_{i}$ for $i \in [n]$ be random elements used to generate $\textsf{CT}_{i}$. Due to the correctness of $\textsf{iFE}, \textsf{mgFE}$, in decryption, we have

$$\begin{aligned}&z_{1} = \sum _{\begin{array}{c} i,k \in [n], j,\ell \in [m] \end{array}} \textbf{c}[(i,j,k,\ell )] (\textbf{x}_{i}[j]\textbf{x}_{k}[\ell ]+s_{i}\widetilde{s}_{k}w_{(i,j,k,\ell )}+r_{i}u_{i,j}\widetilde{u}_{k,\ell }+t_{k}v_{i,j}\widetilde{v}_{k,\ell })\\&z_{2} = \sum _{\begin{array}{c} i,k \in [n], j,\ell \in [m] \end{array}} \textbf{c}[(i,j,k,\ell )] s_{i}\widetilde{s}_{k}w_{(i,j,k,\ell )}\\&z_{3} = \sum _{i,k \in [n], j,\ell \in [m]} \textbf{c}[(i,j,k,\ell )](r_{i}u_{i,j}\widetilde{u}_{k,\ell }+t_{k}v_{i,j}\widetilde{v}_{k,\ell }). \end{aligned}$$

Therefore, we have $z = \sum _{\begin{array}{c} i,k \in [n], j,\ell \in [m] \end{array}} \textbf{c}[(i,j,k,\ell )] \textbf{x}_{i}[j]\textbf{x}_{k}[\ell ]$.

4.2 Security

For security, we have the following theorem.

Theorem 4.1

If $\textsf{iFE}$ and $\textsf{mgFE}$ are sel-pos-fh-IND-secure, and the MDDH$_{1}$ assumption holds in $\mathbb {G}$, then the proposed SK-MCFE for quadratic functions is sel-pos-mh-IND-secure.

Due to the limit of the space, we present the security proof in the full version.

5 MIFE for Quadratic Functions

In this section, we provide our construction for MIFE for quadratic functions.

5.1 Homomorphism in Underlying Schemes

For the construction of our MIFE for quadratic functions, we use the same building blocks as SK-MCFE for quadratic functions Sect. 4, namely, a function-hiding SK-MCFE scheme $\textsf{mgFE}$ for mixed-group inner product and a function-hiding IPFE scheme $\textsf{iFE}$. Additionally, we require them to have homomorphism for the construction of MIFE for quadratic functions. Precisely $\textsf{iFE}$ needs to have homomorphism for both encryption and key generation while $\textsf{mgFE}$ needs to have homomorphism for only encryption.

Homomorphism of $\textsf{iFE}$. We use function-hiding IPFE in [33] for $\textsf{iFE}$ with homomorphism. In their construction from MDDH$_{1}$, the setup algorithm chooses a bilinear group $\mathbb {G}$ and a random matrix $\textbf{B}$ in $\mathbb {Z}_p^{(m+3) \times (m+3)}$, and sets $\textsf{PP}=\mathbb {G}, \textsf{MSK}= (\textbf{B}, \textbf{B}^{*})$ where $\textbf{B}^{*}=(\textbf{B}^{-1})^{\top }$. Encryption of $[\textbf{x}]_{1} \in G_{1}^{m}$ chooses $r \leftarrow \mathbb {Z}_p$ and outputs $\textsf{iCT}=[(\textbf{x},r,0,0)\textbf{B}]_{1}$. Similarly, key generation of $[\textbf{y}]_{2} \in G_{2}^{m}$ chooses $s \leftarrow \mathbb {Z}_p$ and outputs $\textsf{iSK}=[(\textbf{y},0,s,0)\textbf{B}^{*} ]_{2}$. Thus, the random-tape space of $\textsf{iEnc}$ and $\textsf{iKeyGen}$ can be seen as $\mathbb {Z}_p$ and, for all $\textbf{x}_{1},\textbf{x}_{2},\textbf{y}_{1}, \textbf{y}_{2} \in \mathbb {Z}_p^{m}, a_{1},a_{2},r_{1}, r_{2},s_{1},s_{2} \in \mathbb {Z}_p$ we have the following homomorphism of $\mathbb {Z}_p$-module with respect to encryption and key generation:

$$\begin{aligned} a_{1}\textsf{iEnc}(\textsf{iMSK}, [\textbf{x}_{1}]_{1};r_{1}) + a_{2}\textsf{iEnc}(\textsf{iMSK}, [\textbf{x}_{2}]_{1};r_{2})\\ = \textsf{iEnc}(\textsf{iMSK}, [a_{1}\textbf{x}_{1}+a_{2}\textbf{x}_{2}]_{1} ;a_{1}r_{1}+a_{2}r_{2})\\ a_{1}\textsf{iKeyGen}(\textsf{iMSK}, [\textbf{y}_{1}]_{2};s_{1}) + a_{2}\textsf{iKeyGen}(\textsf{iMSK}, [\textbf{y}_{2}]_{2};s_{2}) \\= \textsf{iKeyGen}(\textsf{iMSK}, [a_{1}\textbf{y}_{1}+a_{2}\textbf{y}_{2}]_{2} ;a_{1}s_{1}+a_{2}s_{2}) \end{aligned}$$

We can confirm this as follows:

$$\begin{aligned}&a_{1}[(\textbf{x}_{1},r_{1},0,0)\textbf{B}]_{1} + a_{2}[(\textbf{x}_{2},r_{2},0,0)\textbf{B}]_{1} = [(a_{1}\textbf{x}_{1}+a_{2}\textbf{x}_{2}, a_{1}r_{1}+a_{2}r_{2},0,0)\textbf{B}]_{1}\\&a_{1}[(\textbf{y}_{1},0,s_{1},0)\textbf{B}^{*} ]_{2} + a_{2}[(\textbf{y}_{2},0,s_{2},0)\textbf{B}^{*} ]_{2} = [(a_{1}\textbf{y}_{1}+a_{2}\textbf{y}_{2},0,a_{1}s_{1}+a_{2}s_{2},0)\textbf{B}^{*} ]_{2}. \end{aligned}$$

Homomorphism of $\textsf{mgFE}$. As shown in Sect. 3, our SK-MCFE scheme $\textsf{mgFE}$ for mixed-group inner product uses a function-hiding SK-MCFE scheme $\textsf{icFE}$ for inner product and function-hiding FE scheme $\textsf{iFE}$ for inner product as a building block. For a function-hiding SK-MCFE scheme for inner product, we use a slightly modified function-hiding MCFE scheme for inner product proposed in [10], which is described in Fig. 2. The modification lies in the way of generating t in encryption, which is generated via a random oracle in the MCFE scheme in [10], but PRF suffices in the secret-key setting. Since an $\textsf{icFE}$ ciphertext consists of a $\textsf{iFE}$ ciphertext, a $\textsf{mgFE}$ ciphertext of $([\textbf{x}_{1}]_{1}, [\textbf{x}_{2}]_{2}) \in G^{m_{1}}_{1} \times G^{m_{2}}_{2}$ can be generated as

for some master secret keys $\textsf{iMSK}^{(1)}, \textsf{iMSK}^{(2)}$ and PRF key K. Thus, the random-tape space of $\textsf{mgEnc}$ can be set as $\mathbb {Z}_p^{k+2}$, and by using the homomorphism of $\textsf{iFE}$, we can obtain the following homomorphism of ciphertexts in $\textsf{mgFE}$. For all $N \in \mathbb {N},\; i \in [n], \; \textsf{lab}\in \mathcal {L},\; a_{1} , \ldots ,a_{N} \in \mathbb {Z}_p\; \text {s.t.}\; \sum _{j \in [N]}a_{j}=1,\; \textbf{x}_{1,1} , \ldots ,\textbf{x}_{N,1} \in \mathbb {Z}_p^{m_{1}}, \; \textbf{x}_{1,2} , \ldots ,\textbf{x}_{N,2} \in \mathbb {Z}_p^{m_{2}}, \;\textbf{r}_{1} , \ldots ,\textbf{r}_{N} \in \mathbb {Z}_p^{k+2}$, we have

$$\begin{aligned} \sum _{j \in [N]} a_{j}\textsf{mgEnc}(\textsf{mgMSK},i,\textsf{lab}, ([\textbf{x}_{j,1}]_{1}, [\textbf{x}_{j,2}]_{2}); \textbf{r}_{j})\\ =\textsf{mgEnc}(\textsf{mgMSK},i,\textsf{lab}, ([\sum _{j \in [N]}a_{j}\textbf{x}_{j,1} ]_{1}, [\sum _{j \in [N]} a_{j}\textbf{x}_{j,2} ]_{2}); \sum _{j \in [N]}a_{j}\textbf{r}_{j}) \end{aligned}$$

Fig. 2.

Function-Hiding SK-MCFE for inner product

5.2 Construction

Let $\textsf{mgFE}=(\textsf{mgSetup}, \textsf{mgEnc}, \textsf{mgKeyGen}, \textsf{mgDec})$ be an SK-MCFE scheme for mixed-group inner product (Sect. 3) with label space $\mathcal {L}$, and $\textsf{iFE}=(\textsf{iSetup}, \textsf{iEnc}, \textsf{iKeyGen}, \textsf{iDec})$ be a function-hiding IPFE scheme. Also, let $\textsf{PRF}= \left\{ \textsf{PRF}_{\lambda }\right\} _{\lambda \in \mathbb {N}}$ be a PRF family where $\textsf{PRF}_\lambda : \{0, 1\}^{\lambda } \times \mathcal {L}\rightarrow \{0, 1\}^{\lambda }$. Let $\textsf{lab}_{0}$ be a fixed label in $\mathcal {L}$ and $D=4m+2k+17$ where k is the parameter for the bilateral MDDH assumption used for $\textsf{mgFE}$. Below we provide an MIFE scheme for function class $\mathcal {F}^{\textsf{QF}}_{m, n,X,C}$. Note that $\textsf{MstEnc}$ is a subroutine algorithm used in $\textsf{Setup}$, which corresponds to $\widetilde{\textsf{Enc}}$ of property $\textsf{P}$ in the technical overview.

• $\textsf{Setup}(1^{\lambda }, 1^n)$ samples a random PRF key $K \leftarrow \{0, 1\}^{\lambda }$ and the master keys for the underlying IPFE and SK-MCFE scheme as $(\textsf{iPP}^{(2)},\textsf{iMSK}^{(2)})\leftarrow \textsf{iSetup}(1^{\lambda }),\; (\textsf{mgPP}, \textsf{mgMSK}) \leftarrow \textsf{mgSetup}(1^{\lambda }, 1^n)$ where the vector length of $\textsf{iFE}$ is set as 2, and the vector length of $\textsf{mgFE}$ is set as $m^{2}n+2$ and 1. Note that $\textsf{iPP}^{(2)}=\textsf{mgPP}=\mathbb {G}$. It also samples a sequence of randomization terms as:

  $$\begin{aligned}&\forall ~ i,k \in [n], j,\ell \in [m], \qquad w_{(i,j,k,\ell )} \leftarrow \mathbb {Z}_p\\&\forall ~ i \in [n], j \in [m], \qquad u_{i,j}, \widetilde{u}_{i,j}, v_{i,j}, \widetilde{v}_{i,j} \leftarrow \mathbb {Z}_p\end{aligned}$$

  It sets the public parameters and master key as

  $$\begin{aligned}&\textsf{PP}= \mathbb {G},\;\;\textsf{MSK}= \left( K, \textsf{iMSK}^{(2)}, \textsf{mgMSK}, \{w_{(i,j,k,\ell )}\}_{i,j,k,\ell }, \{ u_{i,j}, \widetilde{u}_{i,j}, v_{i,j}, \widetilde{v}_{i,j} \}_{i,j} \right) . \end{aligned}$$

  It runs $\textsf{MstEnc}$ described below to generate master ciphertexts, which forms encryption keys, as

  $$\begin{aligned}&\forall ~ i \in [n], j \in [m], \quad \textsf{MCT}_{1,i,j} \leftarrow \textsf{MstEnc}(\textsf{MSK},i, \textbf{e}_{j})\\&\forall ~ i \in [n], j \in [D], \quad \textsf{MCT}_{0,i,j} \leftarrow \textsf{MstEnc}(\textsf{MSK},i, {\textbf{0}}_{m}). \end{aligned}$$

  Finally it output encryption keys together with the public key and master secret key as

  $$ \forall ~ i \in [n], \quad \textsf{EK}_{i} = (\{\textsf{MCT}_{1,i,j}\}_{j \in [n]}, \{\textsf{MCT}_{0,i,j}\}_{j \in [D]}). $$

• $\textsf{MstEnc}(\textsf{MSK},i, {\textbf{x}})$ parses $\textsf{MSK}$ as above, and using the PRF key K, it samples a IPFE master key of vector length $mn+3m+4$ as:

  $$\begin{aligned}&(\textsf{iPP}^{(1)}, \textsf{iMSK}^{(1)}) \leftarrow \textsf{iSetup}(1^{\lambda }; \textsf{PRF}(K, \textsf{lab}_{0})) \end{aligned}$$

  It then samples random elements $s, \widetilde{s}, r, t \leftarrow \mathbb {Z}_p$. And, it sets vectors ${\textbf{b}}_{j}, \widetilde{\textbf{b}}_{j}$ for $j \in [m]$ as follows:

  $$ {\textbf{b}}_{j} =(\textbf{x}[j],0, s\textbf{e}_{(i,j)}, ru_{i,j}, v_{i,j}, {\textbf{0}}_{3m}), \quad \widetilde{\textbf{b}}_{j} = (\textbf{x}[j],0, \widetilde{s}\textbf{w}_{(*,*,i,j)}, \widetilde{u}_{i,j}, t\widetilde{v}_{i,j}, {\textbf{0}}_{3m}). $$

  where where $\textbf{e}_{(i,j)}$ is the mn-dimensional one-hot vector with the (i, j)-th element being 1, and vector $\textbf{w}_{(*,*,i,j)} \in \mathbb {Z}_p^{mn}$ is defined as follows:

  $$ \forall ~ j \in [m], \quad \textbf{w}_{(*,*,i,j)} = (w_{(1,1,i,j)}, w_{(1,2,i,j)} , \ldots ,w_{(n,m, i,j)}) $$

  The encryptor encodes the vectors ${\textbf{b}}_{j}, \widetilde{\textbf{b}}_{j}$ under MIFE as follows:

  $$\begin{aligned}&\forall ~j \in [m], \quad \textsf{iCT}_{j} \leftarrow \textsf{iEnc}(\textsf{iMSK}^{(1)}, [{\textbf{b}}_{j}]_{1}), \;\; \textsf{iSK}_j \leftarrow \textsf{iKeyGen}(\textsf{iMSK}^{(1)}, [\widetilde{\textbf{b}}_{j}]_{2}). \end{aligned}$$

  It also encodes the random elements $s, \widetilde{s}$ as follows:

  $$\begin{aligned}&\textsf{iCT}\leftarrow \textsf{iEnc}(\textsf{iMSK}^{(2)}, [(s, 0)]_{1}), \;\;\textsf{iSK}\leftarrow \textsf{iKeyGen}(\textsf{iMSK}^{(2)}, [(\widetilde{s}, 0)]_{2}). \end{aligned}$$

  Lastly, it sets $\textbf{f}=(r, t, {\textbf{0}}_{m^{2}n}),\; h=0$, and encrypts elements $\textbf{f},h$ with respect to label $\textsf{lab}_{0}$ as

  $$ \textsf{mgCT}\leftarrow \textsf{mgEnc}(\textsf{mgMSK},i, \textsf{lab}_{0}, ([\textbf{f}]_{1},[h]_{2})). $$

  The resulting ciphertext is set as $\textsf{MCT}= \left( \{\textsf{iCT}_{j}\}_{j}, \{\textsf{iSK}_{j}\}_{j}, \textsf{iCT}, \textsf{iSK}, \textsf{mgCT} \right) .$

• $\textsf{Enc}(\textsf{EK}_{i} ,{\textbf{x}})$ parses $\textsf{EK}_{i}$ as above. It then samples random elements $\gamma _{1} , \ldots ,\gamma _{(D-1)/2} \leftarrow \mathbb {Z}_p$. And, it encrypts $\textbf{x}$ to $\textsf{CT}$ by homomorphic addition of master ciphertexts as follows:

  $$\begin{aligned} \textsf{CT}= \sum _{j \in [m]} \textbf{x}[j]\textsf{MCT}_{1,i,j} - \left( \sum _{j \in [m]} \textbf{x}[j] -1 \right) \textsf{MCT}_{0,i,1}\\ + \sum _{j \in [(D-1)/2]}\gamma _{j}(\textsf{MCT}_{0,i,2j}-\textsf{MCT}_{0,i,2j+1} ) \end{aligned}$$

  where the above is the component-wise homomorphic addition with respect to ciphertexts of $\textsf{iFE}$ and $\textsf{mgFE}$. Then, it outputs $\textsf{CT}$.

• $\textsf{KeyGen}(\textsf{MSK}, {\textbf{c}})$ parses $\textsf{MSK}$ as above, and the key vector ${\textbf{c}}$ lies in the space $\mathbb {Z}_p^{(m n)^{2}}$. Let the vector $\widetilde{\textbf{f}}_{i} \in \mathbb {Z}_p^{(2 + m^{2}n)}$ be the following vector: for all $i \in [n]$

  $$ \widetilde{\textbf{f}}_{i}[1] =\sum _{j,\ell \in [m], k \in [n]}\textbf{c}[(i,j,k,\ell )]u_{i,j}\widetilde{u}_{k,\ell }, \; \widetilde{\textbf{f}}_{i}[2] = \sum _{j,\ell \in [m], k \in [n]}\textbf{c}[(k,\ell ,i,j)]v_{k,\ell }\widetilde{v}_{i,j} $$

  and $\widetilde{\textbf{f}}_{i}$ is zeros at all other places. It also sets $\widetilde{h}_{i}=0$ for all $i \in [n]$. The key generator samples a SK-MCFE secret key corresponding to vectors $\{\widetilde{\textbf{f}}_{i},\widetilde{h}_{i}\}_{i}$ as $\textsf{mgSK}\leftarrow \textsf{mgKeyGen}(\textsf{mgMSK}, \{[\widetilde{\textbf{f}}_{i}]_{2}, [\widetilde{h}_{i}]_{1} \}_{i \in [n]})$, and partial derandomization terms:

  $$ \forall ~i,k \in [n], \quad \sigma _{i,k} = \sum _{j,\ell \in [m]}\textbf{c}[(i,j,k,\ell )]w_{(i,j,k,\ell )} $$

  And, it outputs the secret key as ${\textsf{SK}}= \left( {\textbf{c}}, \textsf{mgSK}, \{\sigma _{i,k}\}_{i,k} \right) .$

• $\textsf{Dec}(\textsf{CT}_{1} , \ldots ,\textsf{CT}_{n}, {\textsf{SK}})$ parses the ciphertexts and secret key as:

  $$\begin{aligned}\begin{gathered} \textsf{CT}_i = \left( \{\textsf{iCT}_{i,j}\}_{i,j}, \{\textsf{iSK}_{i,j}\}_{i,j}, \textsf{iCT}_{i}, \textsf{iSK}_{i}, \textsf{mgCT}_{i} \right) , \\ {\textsf{SK}}= \left( {\textbf{c}}, \textsf{mgSK}, \{\sigma _{i,k}\}_{i,k} \right) . \end{gathered}\end{aligned}$$

  It runs the MIFE decryption algorithm as:

  $$\begin{aligned}{}[z_{1}]_{T} = \prod _{\begin{array}{c} i,k \in [n],\\ j,\ell \in [m] \end{array}} \textsf{iDec}(\textsf{iCT}_{i,j},\textsf{iSK}_{k,\ell })^{\textbf{c}[(i,j,k,\ell )]},\; [z_{2}]_{T} = \prod _{i,k\in [n]}\textsf{iDec}(\textsf{iCT}_{i}, \textsf{iSK}_{k})^{ \sigma _{i, k}} \end{aligned}$$

  It also runs the SK-MCFE decryption algorithm as:

  $$ [z_{3}]_{T} = \textsf{mgDec}(\textsf{mgCT}_{1}, \ldots ,\textsf{mgCT}_{n}, \textsf{mgSK}) $$

  Finally it outputs z where $[z]_{T} = [z_{1}- z_{2}-z_{3}]_{T}$ by searching for z within the range of $z \le |m^{2}n^{2}CX^{2}|$.

Correctness. Let $s_{b,i,j}, \widetilde{s}_{b,i,j}, r_{b,i,j}, t_{b,i,j}$ for $b \in \{0,1\}, i \in [n], j \in [D]$ be random elements used to generate $\textsf{MCT}_{b,i,j}$ in $\textsf{EK}_{i}$. Thanks to the homomorphism of $\textsf{iFE}$ and $\textsf{mgFE}$, $\textsf{Enc}(\textsf{EK}_{i} ,{\textbf{x}})$ outputs $\textsf{CT}_{i}= \left( \{\textsf{iCT}_{i,j}\}_{j}, \{\textsf{iSK}_{i,j}\}_{j}, \textsf{iCT}_{i}, \textsf{iSK}_{i}, \textsf{mgCT}_{i} \right)$, which are encryption of

$$\begin{aligned} \begin{aligned}{}&[\textbf{b}]_{1}=[(\textbf{x}_{i}[j],0, s_{i}\textbf{e}_{(i,j)}, r_{i}u_{i,j}, v_{i,j}, {\textbf{0}}_{3m})]_{1}\\&[\widetilde{\textbf{b}}]_{2} = [(\textbf{x}_{i}[j],0, \widetilde{s}_{i} \textbf{w}_{(*,*,i,j)}, \widetilde{u}_{i,j}, t_{i}\widetilde{v}_{i,j}, {\textbf{0}}_{3m})]_{2}\\&[(s_{i},0)]_{1}, \quad [(\widetilde{s}_{i},0)]_{2}, \quad ([\textbf{f}]_{1}, [h]_{2}) = ([(r_{i},t_{i}, {\textbf{0}}_{m^{2}n})]_{1}, [0]_{2})\;\;\text {for label }\textsf{lab}_{0} \end{aligned} \end{aligned}$$

(5)

respectively, where

$$\begin{aligned} \begin{aligned}{}&s_{i} = \sum _{j \in [m]}\textbf{x}_{i}[j]s_{1,i,j} - \left( \sum _{j \in [m]} \textbf{x}_{i}[j] -1 \right) s_{0,i,1}+\sum _{j \in [(D-1)/2]} \gamma _{j}(s_{0,i,2j}- s_{0,i,2j+1})\\&\widetilde{s}_{i} = \sum _{j \in [m]}\textbf{x}_{i}[j]\widetilde{s}_{1,i,j} - \left( \sum _{j \in [m]} \textbf{x}_{i}[j] -1 \right) \widetilde{s}_{0,i,1}+\sum _{j \in [(D-1)/2]} \gamma _{j}(\widetilde{s}_{0,i,2j}- \widetilde{s}_{0,i,2j+1})\\&r_{i} = \sum _{j \in [m]}\textbf{x}_{i}[j]r_{1,i,j} - \left( \sum _{j \in [m]} \textbf{x}_{i}[j] -1 \right) r_{0,i,1}+\sum _{j \in [(D-1)/2]} \gamma _{j}(r_{0,i,2j}- r_{0,i,2j+1})\\&t_{i} = \sum _{j \in [m]}\textbf{x}_{i}[j]t_{1,i,j} - \left( \sum _{j \in [m]} \textbf{x}_{i}[j] -1 \right) t_{0,i,1}+\sum _{j \in [(D-1)/2]} \gamma _{j}(t_{0,i,2j}- t_{0,i,2j+1}). \end{aligned} \end{aligned}$$

(6)

Hence, similarly to the correctness of our SK-MCFE for quadratic functions (Sect. 4), in decryption, we have

$$\begin{aligned}&z_{1} = \sum _{\begin{array}{c} i,k \in [n], j,\ell \in [m] \end{array}} \textbf{c}[(i,j,k,\ell )] (\textbf{x}_{i}[j]\textbf{x}_{k}[\ell ]+s_{i}\widetilde{s}_{k}w_{(i,j,k,\ell )}+r_{i}u_{i,j}\widetilde{u}_{k,\ell }+t_{k}v_{i,j}\widetilde{v}_{k,\ell })\\&z_{2} = \sum _{\begin{array}{c} i,k \in [n], j,\ell \in [m] \end{array}} \textbf{c}[(i,j,k,\ell )] s_{i}\widetilde{s}_{k}w_{(i,j,k,\ell )}\\&z_{3} = \sum _{i,k \in [n], j,\ell \in [m]} \textbf{c}[(i,j,k,\ell )](r_{i}u_{i,j}\widetilde{u}_{k,\ell }+t_{k}v_{i,j}\widetilde{v}_{k,\ell }). \end{aligned}$$

Since $\textbf{c}[(i,j,k,\ell )]=0$ for $i \ge k$, we have $z = \sum _{\begin{array}{c} i,k \in [n], j,\ell \in [m] \end{array}} \textbf{c}[(i,j,k,\ell )] \textbf{x}_{i}[j]\textbf{x}_{k}[\ell ]$.

5.3 Security

For security, we have the following theorem. Let $\textsf{qcFE}$ be SK-MCFE scheme for quadratic functions in Sect. 4.

Theorem 5.1

If $\textsf{qcFE}$ are sel-pos-mh-IND-secure, then the proposed MIFE for quadratic functions is sel-pos-mh-IND-secure.

Proof

Wlog, in the pos setting, we can denote challenge messages by $\{i, \textbf{x}^{\mu ,0}_{i}, \textbf{x}^{\mu ,1}_{i}\}_{i \in [n], \mu \in [q_{c}]}$ for some $q_{c}$ instead of $\{i^{\mu }, \textbf{x}^{\mu ,0}_{i^{\mu }}, \textbf{x}^{\mu ,1}_{i^{\mu }}\}_{\mu \in [q'_{c}]}$. For notational convenience, we use the former notation in this proof. We prove Theorem 5.1 via a series of hybrids $\textsf{H}^{\beta }_{1}, \textsf{H}^{\beta }_{\textsf{f}}$. We show that $\textsf{H}^{\beta }_{0} \approx _{c}\textsf{H}^{\beta }_{1} \approx _{c}\textsf{H}^{\beta }_{\textsf{f}}$, where $\textsf{H}^{\beta }_{0}$ is the original security game for MIFE defined in Definition 2.1. Each hybrid is defined as described in Fig. 3, where the reply for the ciphertext query is computed by $\textsf{MstEnc}$ instead of $\textsf{Enc}$. We denote the probability that $\mathcal {A}$ outputs $\beta$ in hybrid $\textsf{H}^{\beta }$ by $\textsf{P}(\mathcal {A}, \textsf{H}^{\beta })$ in what follows.

Fig. 3.

Description of hybrids

Theorem 5.1 directly follows from Lemma 5.2 and Lemma 5.3 since $\mathcal {A}$ does not obtain the information on $\beta$ in $\textsf{H}^{\beta }_{\textsf{f}}$.    $\square$

Lemma 5.2

For all PPT adversaries $\mathcal {A}$, we have $|\textsf{P}(\mathcal {A}, \textsf{H}^{\beta }_{0})-\textsf{P}(\mathcal {A}, \textsf{H}^{\beta }_{1})| \le 2^{-\Omega (\lambda )}$.

Proof

The difference between $\textsf{H}^{\beta }_{0}$ and $\textsf{H}^{\beta }_{1}$ lies in the way of generating challenge ciphertexts. That is, the challenge ciphertexts are generated by $\textsf{Enc}$ in $\textsf{H}^{\beta }_{0}$ while they are generated by $\textsf{MstEnc}$ in $\textsf{H}^{\beta }_{1}$. Recall that the random elements used in $\textsf{MstEnc}$ are $s, \widetilde{s}, r,t \in \mathbb {Z}_p$ and the random tapes used to generate $\left( \{\textsf{iCT}_{\ell }\}_{\ell \in [m]}, \{\textsf{iSK}_{\ell \in [m]}\}_{\ell }, \textsf{iCT}, \textsf{iSK}, \textsf{mgCT} \right)$. Since $\textsf{iEnc}, \textsf{iKeyGen}$ can use a random element in $\mathbb {Z}_p$, and $\textsf{mgEnc}$ can use a random element in $\mathbb {Z}_p^{k+2}$ as a random tape, we can use a random element in $\mathbb {Z}_p^{2m+k+8}$ as a random tape of $\textsf{MstEnc}$. Due to the homomorphism of $\textsf{iFE}$ and $\textsf{mgFE}$, for all $N \in \mathbb {N},\; i \in [n], \; a_{1} , \ldots ,a_{N} \in \mathbb {Z}_p\; \text {s.t.}\; \sum _{j \in [N]}a_{j}=1,\; \textbf{x}_{1} , \ldots ,\textbf{x}_{N} \in \mathbb {Z}_p^{m}, \;\textbf{r}_{1} , \ldots ,\textbf{r}_{N} \in \mathbb {Z}_p^{2m+k+8}$, we have the following homomorphism of $\textsf{MstEnc}$:

$$\begin{aligned} \sum _{j \in [N]} a_{j}\textsf{MstEnc}(\textsf{MSK},i, \textbf{x}; \textbf{r}_{j}) =\textsf{MstEnc}(\textsf{MSK},i, \sum _{j \in [N]}a_{j}\textbf{x}_{j}; \sum _{j \in [N]}a_{j}\textbf{r}_{j}). \end{aligned}$$

Parse $\textsf{EK}_{i}=(\{\textsf{MCT}_{1,i,j}\}_{i \in [n], j\in [m]}, \{\textsf{MCT}_{0,i,j}\}_{i \in [n], j \in [D]})$ and let $\textbf{r}_{b,i,j} \in \mathbb {Z}_p^{2m+k+8}$ be the random tape used to generate $\textsf{MCT}_{b,i,j}$ for $b \in \{0,1\}, \; i \in [n], \; j \in [D]$. In other words,

$$ \textsf{MCT}_{b,i,j} = {\left\{ \begin{array}{ll} \textsf{MstEnc}(\textsf{MSK}, i, \textbf{e}_{j}) ;\textbf{r}_{b,i,j}) &{} b=1 \\ \textsf{MstEnc}(\textsf{MSK}, i, {\textbf{0}}_{m}) ;\textbf{r}_{b,i,j}) &{} b=0 \end{array}\right. } $$

From the homomorphism of $\textsf{MstEnc}$ and the fact that $\textsf{Enc}$ can use ${\mathbf {\gamma }}=(\gamma _{1} , \ldots ,\gamma _{(D-1)/2}) \in \mathbb {Z}_p^{(D-1)/2}$ for a random tape, we have

$$\begin{aligned} \textsf{Enc}(\textsf{EK}_{i}, \textbf{x}: {\mathbf {\gamma }}) = \textsf{MstEnc}(\textsf{MSK},i, \sum _{j \in [m]}\textbf{x}[j]\textbf{e}_{j}; \textbf{r}) \end{aligned}$$

where

$$\begin{aligned} \textbf{r}= \sum _{j \in [m]}\textbf{x}_{i}[j]\textbf{r}_{1,i,j} - \left( \sum _{j \in [m]} \textbf{x}_{i}[j] -1 \right) \textbf{r}_{0,i,1}+\sum _{j \in [(D-1)/2]} \gamma _{j}(\textbf{r}_{0,i,2j}- \textbf{r}_{0,i,2j+1}). \end{aligned}$$

(7)

Here, we use the equality: $\sum _{j \in [m]}\textbf{x}_{i}[j] - \left( \sum _{j \in [m]} \textbf{x}_{i}[j] -1 \right) +\sum _{j \in [(D-1)/2]} (\gamma _{j} - \gamma _{j} )=1.$ Hence, to prove the lemma, it suffices to show that the following distributions are statistically close for all $i \in [n]$:

$$\begin{aligned}\begin{gathered} \left\{ (\textbf{r}, \{\textbf{r}_{1,i,j}\}_{j \in [m]}, \{\textbf{r}_{0,i,j}\}_{j \in [D]}) : \begin{array}{l} \forall (b,i,j), \textbf{r}_{b,i,j} \leftarrow \mathbb {Z}_p^{2m+k+8}, \; {\mathbf {\gamma }} \leftarrow \mathbb {Z}_p^{(D-1)/2} \\ \textbf{r}\text { is defined as Eq. (7)} \end{array} \right\} \\ \text {and}\\ \left\{ (\textbf{r}, \{\textbf{r}_{1,i,j}\}_{j \in [m]}, \{\textbf{r}_{0,i,j}\}_{j \in [D]}) : \forall (b,i,j), \textbf{r}_{b,i,j} \leftarrow \mathbb {Z}_p, \; \textbf{r}\leftarrow \mathbb {Z}_p^{2m+k+8} \right\} \end{gathered}\end{aligned}$$

This can be shown as follows. For all $j \in [(D-1)/2]$, $\widetilde{\textbf{r}}_{j}=\textbf{r}_{0,i,2j}- \textbf{r}_{0,i,2j+1}$ is uniformly distributed in $\mathbb {Z}_p^{2m+k+8}$, and thus $\widetilde{\textbf{r}}_{1} , \ldots ,\widetilde{\textbf{r}}_{(D-1)/2}$ span $\mathbb {Z}_p^{2m+k+8}$ with overwhelming probability if $(D-1)/2 \ge 2m+k+8$. Hence, $\sum _{j \in [(D-1)/2]} \gamma _{j}(\textbf{r}_{0,i,2j}- \textbf{r}_{0,i,2j+1}) = \sum _{j \in [(D-1)/2]} \gamma _{j}\widetilde{\textbf{r}}_{j}$ is randomly distributed even given $(\{\textbf{r}_{1,i,j}\}_{j \in [m]}, \{\textbf{r}_{0,i,j}\}_{j \in [D]})$. This concludes the proof.

Lemma 5.3

For all PPT adversaries $\mathcal {A}$, there exists a PPT adversary $\mathcal {B}$ against $\textsf{qcFE}$ in Sect. 4 such that $|\textsf{P}(\mathcal {A}, \textsf{H}^{\beta }_{1})-\textsf{P}(\mathcal {A}, \textsf{H}^{\beta }_{\textsf{f}})| \le \textsf{Adv}^{\textsf{qcFE}}_{\mathcal {B}}(\lambda )$.

Proof

The difference of these hybrids is whether $\textsf{CT}^{\mu }_{i}$ is encryption of $\textbf{x}^{\mu ,\beta }_{i}$ or $\textbf{x}^{\mu ,0}_{i}$. We can construct $\mathcal {B}$ as follows.

• 1. $\mathcal {B}$ is given $\textsf{qcPP}$ and gives it to $\mathcal {A}$.

• 2. $\mathcal {A}$ outputs $(\mathcal {C}\mathcal {S}, \{i, \textbf{x}^{\mu ,0}_{i}, \textbf{x}^{\mu ,1}_{i}\}_{i \in [n], \mu \in [q_{c}]}, \mathcal {F}\mathcal {S}=\{\textbf{c}^{\nu }\}_{\nu \in [q_{k}]})$, and $\mathcal {B}$ chooses $\beta \leftarrow \{0,1\}$ and queries its own oracle on $\mathcal {M}\mathcal {S}, \mathcal {F}\mathcal {S}$ where

  $$\mathcal {M}\mathcal {S}= \left( \begin{aligned}{}&\{i, \textsf{lab}_{0}, \textbf{e}_{j}, \textbf{e}_{j}\}_{i \in \mathcal {C}\mathcal {S}, j \in [m]}, \{(i, \textsf{lab}_{0}, {\textbf{0}}_{m}, {\textbf{0}}_{m}) \times D\}_{i \in \mathcal {C}\mathcal {S}}\\ {}&\{i, \textsf{lab}_{0}, \textbf{x}^{\mu , \beta }_{i}, \textbf{x}^{\mu ,0}_{i}\}_{i \in [n], \mu \in [q_{c}]} \end{aligned} \right) . $$

• 3. $\mathcal {B}$ is given

  $$ \left( \{\textsf{cCT}_{1,i,j}\}_{i \in \mathcal {C}\mathcal {S}, j \in [m]}, \{\textsf{cCT}_{0,i,j}\}_{i \in \mathcal {C}\mathcal {S}, j \in [D]}, \{\textsf{cCT}^{\mu }_{i}\}_{i \in [n], \mu \in [q_{c}]} , \{\textsf{cSK}^{\nu }\}_{\nu \in [q_{k}]} \right) $$

  where $\textsf{cCT}_{1,i,j}, \textsf{cCT}_{0,i,j}, \textsf{cCT}^{\mu }_{i}$ are ciphertexts of $\textsf{qcFE}$ for $(i, \textsf{lab}_{0}, \textbf{e}_{j}), (i, \textsf{lab}_{0}, {\textbf{0}}_{m}), (i, \textsf{lab}_{0}, \textbf{x}^{\mu ,\beta /0}_{i})$, respectively, and gives it to $\mathcal {A}$ by setting $\textsf{EK}_{i} = (\{\textsf{cCT}_{1,i,j}\}_{ j \in [m]}, \{\textsf{cCT}_{0,i,j}\}_{j \in [D]})$.

• 4. $\mathcal {A}$ outputs $\beta '$, and $\mathcal {B}$ outputs $\beta '$ as it is.

We can confirm the above simulation of $\mathcal {B}$ is valid from the three observations. First, $\mathcal {B}$’s query satisfies the game condition (recall that the adversary can query any pair of the same messages for corrupted slot). Second, $\textsf{qcPP}=\textsf{iPP}^{(1)}=\mathbb {G}$ where $\textsf{qcPP}$ is the public parameter of $\textsf{qcFE}$. Third, $\textsf{MstEnc}(\textsf{MSK},\cdot ,\cdot )$ and $\textsf{qcEnc}(\textsf{cMSK},\cdot , \textsf{lab}_{0}, \cdot )$ (the encryption algorithm of $\textsf{qcFE}$) are the exactly the same.