Tightly Secure Inner Product Functional Encryption: Multi-input and Function-Hiding Constructions

Abstract

Tightly secure cryptographic schemes have been extensively studied in the fields of chosen-ciphertext secure public-key encryption, identity-based encryption, signatures and more. We extend tightly secure cryptography to inner product functional encryption (IPFE) and present the first tightly secure schemes related to IPFE.

We first construct a new IPFE scheme that is tightly secure in the multi-user and multi-challenge setting. In other words, the security of our scheme does not degrade even if an adversary obtains many ciphertexts generated by many users. Our scheme is constructible on a pairing-free group and secure under the matrix decisional Diffie-Hellman (MDDH) assumption, which is the generalization of the decisional Diffie-Hellman (DDH) assumption. Applying the known conversions by Lin (CRYPTO 2017) and Abdalla et al. (CRYPTO 2018) to our scheme, we can obtain the first tightly secure function-hiding IPFE scheme and multi-input IPFE (MIPFE) scheme respectively.

Our second main contribution is the proposal of a new generic conversion from function-hiding IPFE to function-hiding MIPFE, which was left as an open problem by Abdalla et al. (CRYPTO 2018). We obtain the first tightly secure function-hiding MIPFE scheme by applying our conversion to the tightly secure function-hiding IPFE scheme described above.

Finally, the security reductions of all our schemes are fully tight, which means that the security of our schemes is reduced to the MDDH assumption with a constant security loss.

1 Introduction

(Multi-input) Inner Product Functional Encryption. Functional encryption (FE) [13, 37] is a relatively novel cryptographic notion that has a crucially different feature from traditional encryption schemes. Specifically, FE schemes allow us to obtain computation results from encrypted data without revealing any other information about the underlying data. This is in contrast to traditional encryption schemes, in which only owners of legitimate keys can learn entire underlying data from ciphertexts while others can learn nothing. An FE scheme supports a certain function class $\mathcal {F}$ and in which an owner of a master secret can issue a secret key $\mathsf{sk}_{f}$ for any function $f \in \mathcal {F}$. Decryption of a ciphertext $\mathsf{ct}_{x}$ of message x with $\mathsf{sk}_{f}$ yields the computation result f(x) and nothing else.

Multi-input functional encryption (MIFE) [28] is a natural extension of FE, which can handle a function class that takes multiple inputs. Roughly speaking, an owner of $\mathsf{sk}_{f}$ can learn the computation result $f(x_{1}, \ldots ,x_{\mu })$ from ciphertexts $\mathsf{ct}_{x_{1}} , \ldots ,\mathsf{ct}_{x_{\mu }}$ of messages $x_{1} , \ldots ,x_{\mu }$ for some natural number $\mu \ge 2$.

Known (MI)FE schemes can be classified into two categories with respect to their function classes.

• General functionalities: This category consists of (MI)FE schemes for general circuits, e.g., [8, 23, 24, 28, 39]. Although they are powerful enough to handle all functions computable in polynomial time, known schemes are built on quite heavy cryptographic primitives such as indistinguishability obfuscation [23] or multi-linear maps [22]. Thus, they are captured as rather feasibility results.

• Specific functionalities: The second category covers (MI)FE schemes for specific functions such as inner product and quadratic function, e.g., [2, 4, 6, 9]. They are aimed at obtaining more practical features, namely, efficiency and concrete security, with sacrificing the generality. Therefore, they have simple constructions, and their security is based on standard assumptions.

Inner product functional encryption (IPFE) [2] and multi-input IPFE (MIPFE) [4], categorized into the latter, are FE and MIFE respectively, whose function classes are inner product. More precisely, in an (M)IPFE scheme, a secret key $\mathsf{sk}_{\mathbf{y}_{1} , \ldots ,\mathbf{y}_{\mu }}$ is associated with vectors $\mathbf{y}_{1} , \ldots ,\mathbf{y}_{\mu }$, and decrypting ciphertexts $\mathsf{ct}_{\mathbf{x}_{1}} , \ldots ,\mathsf{ct}_{\mathbf{x}_{\mu }}$ of vectors $\mathbf{x}_{1} , \ldots ,\mathbf{x}_{\mu }$ with $\mathsf{sk}_{\mathbf{y}_{1} , \ldots ,\mathbf{y}_{\mu }}$ reveals the summation of the inner products $\sum _{i \in [\mu ]}\langle \mathbf{x}_{i}, \mathbf{y}_{i} \rangle$. When $\mu =1$, the above description corresponds to an IPFE scheme. Inner product is a simple but powerful functionality, and many practical applications of IPFE have been suggested, e.g, biometric authentication, nearest-neighbor search and statistical analysis [2, 32].

Function Privacy. In (MI)FE, we can consider two types of privacy: message privacy and function privacy. Message privacy, which is essential for standard (MI)FE schemes, is the property that ciphertexts do not reveal any information about underlying data. On the other hand, function privacy is an additional but important property for (MI)FE schemes, which indicates that secret keys also hide the information of the corresponding function. Function privacy is essential for some applications such as delegation of sensitive computation [15]. We often refer to (MI)FE with function privacy as function-hiding (MI)FE. Function-hiding (MI)FE schemes have also been studied for both general functionalities [14, 15] and specific functionalities [12, 18, 32, 38].

Tight Security. When we try to prove the security of a cryptographic scheme, we often construct a reduction algorithm that solves a problem assumed to be hard by utilizing a PPT adversary that breaks the security of the scheme. Then, breaking the security of the scheme immediately implies solving the hard problem. It is both theoretically and practically important to evaluate how difficult breaking the scheme is compared with solving the problem. More formally, when the reduction algorithm equipped with an adversary that breaks the scheme with probability $\epsilon$ in time t solves the underlying problem with probability $\epsilon /L$ in roughly the same time t, it is important to evaluate the security loss L. This is because we need to set the parameter size of the scheme large enough to negate the effect of L for the security guarantee. Thus, the smaller the security loss L, the more desirable the security reduction. We say that the security reduction is tight if the security loss is constant, i.e., $L = O(1)$.

When we consider public-key primitives such as public-key encryption (PKE) or identity-based encryption (IBE), we usually prove their security in the single-challenge setting. This is because the security of public-key primitives in the single-challenge setting normally implies that in the multi-user and multi-challenge setting via hybrid argument, which is more realistic setting where an adversary can make polynomially many challenge queries against multiple users. However, such a hybrid argument increases the security loss by the factor of $\mu q$, where $\mu$ is the number of users and q is the maximum number of challenge queries for each users [11]. Since the numbers of users and ciphertexts are quite large in practice, we strongly desire cryptographic schemes whose security is guaranteed independently of those numbers.

Motivated by the above reason, (almost) tightly secure cryptographic schemes have been extensively studied in various fields, especially on chosen-ciphertext secure PKE (CCA-secure PKE), IBE, and signature, e.g, [7, 17, 25, 26, 29,30,31, 33]. In spite of such a great deal of effort, tightly secure schemes in the context of advanced encryption are known only for IBE except the very recent result on broadcast encryption by Gay et al. [27]. Hence, it is an important and interesting task to explore what kind of cryptographic schemes can achieve tight security.

Tight Security for IPFE. We would like to discuss the importance of tightly secure IPFE in more detail. We consider that the most significant situation where we need a tightly secure IPFE scheme is when a function-hiding scheme is needed. This is because the only way that we know to realize function-hiding IPFE schemes requires bilinear groups, which is relatively susceptible to security loss. One solution to compensate for security loss caused by loose reduction is to increase the parameter size of underlying primitives, e.g., bilinear groups, which will reinforce the difficulty of underlying problems, e.g., the matrix Diffie-Hellman problem. As observed by Abe et al. [5], however, this is not an easy task for bilinear groups because there are many factors that involve the security and efficiency of them such as the choice of curves, pairings, and various parameters like embedding degrees. Hence, we typically adopt one from existing well-studied settings, which are investigated only for standard parameters such as 128, 192, and 256-bit security. The main problem of this fact is that there is no intermediate instantiation among these parameters, and one have to hop to the next standard level if stronger security is necessary. A pairing computation is especially influenced by this hop; for instance, they state that a pairing in the 192-bit security takes 6 to 7 times more time than in the 128-bit security on ordinary personal computers [10, 20].

Additionally, it is not unrealistic that an adversary obtains a large amount of ciphertexts so that we need to consider the security loss of IPFE schemes. Let us consider the case to use a function-hiding IPFE scheme for DNA analysis. Suppose a national institution holds a database consisting of a certain part of the human’s DNA sequence. It is rational to assume that the part consists of $2^{13}$ bases and the number of the samples is $2^{20}$; actually, GenBank operated by the National Center for Biotechnology Information has more than $2^{27}$ sequences [1]. Each sample is encoded to a binary vector setting as A = (1, 0, 0, 0), T = (0, 1, 0, 0), and so on, and stored in a cloud server with an encrypted form. We can check the number of the same bases between encrypted sequences and a target sequence by decrypting with a secret key for the target sequence. Because DNA sequences have a correlation with phenotypes, the DNA similarity check will be useful for genetical research, medical diagnosis, etc. We need the function-hiding property because target sequences are also personal data and thus sensitive. In this situation, the possibly untrusted server has $q=2^{20}$ ciphertexts, large enough to consider the security loss of the scheme. Decryption of all known schemes involves the same number of pairings as the order of the vector length: $m=2^{15}$ per one sample in our case. Thus, the choice of the security level significantly affects the efficiency of the system, and we can conclude that tight security is a very important concept in the context of IPFE as well as other cryptosystems.

1.1 Our Contributions

We extend the realm of tightly secure cryptography to IPFE and present a series of the first tightly secure (M)IPFE schemes. Our first main contribution is to construct the first tightly secure public-key IPFE scheme in the multi-user and multi-challenge setting. Note that previous IPFE schemes are tightly reduced to underlying assumptions in the single-challenge setting [6], which means that their security is independent from the number of secret key queries. To our knowledge, however, there are no results on tight security of IPFE in the multi-user and multi-challenge setting. Our tightly secure IPFE scheme is constructible from a pairing-free group and its security is based on the matrix decisional Diffie-Hellman (MDDH) assumption, which is a generalization of the well-studied decisional Diffie-Hellman (DDH) assumption, with a small constant security loss.

Our result can be easily extended to the multi-input setting. Recently, Abdalla et al. proposed a generic conversion from an IPFE scheme into a MIPFE scheme [3, 4]. Their conversion employs parallel execution of $\mu$ instances of the underlying IPFE scheme that is secure in the multi-challenge setting. By this construction, their conversion incurs a security loss of $O(\mu q)$ if we apply it to an IPFE scheme that is secure in the single challenge setting, where $\mu$ is the number of slots of the converted scheme and q is the maximum number of ciphertext queries for each slot. Interestingly, this construction is precisely compatible with an IPFE scheme that is secure in the multi-user and multi-challenge setting. In other words, the security of the converted MIPFE scheme is tightly reduced to that of the underlying IPFE scheme if the underlying scheme is secure in the multi-user and multi-challenge setting. Thus, we can obtain the first tightly secure MIPFE scheme.

Another important issue is the realization of tightly secure function-hiding (M)IPFE schemes. All previous function-hiding schemes suffer from a security loss of $L = O(q_{\mathsf{ct}}+q_{\mathsf{sk}})$, where $q_{\mathsf{ct}}$ (resp. $q_{\mathsf{sk}}$) refers to the total number of ciphertext (resp. secret key) queries [12, 18, 34, 38]. To achieve tight security, we utilize Lin’s technique, who presented a simple paradigm to construct a function-hiding (private-key) IPFE scheme from a (public-key) IPFE scheme [34]. Applying her paradigm to our IPFE scheme, we can obtain the first tightly secure function-hiding IPFE scheme that is based on bilinear groups. However, the naive application of her paradigm to our scheme results in a redundant scheme. Thus, we optimize the scheme by reducing the unnecessary part.

The final target is to construct a tightly secure function-hiding MIPFE scheme. Unfortunately, there is no known generic technique to achieve a function-hiding MIPFE scheme. In fact, Abdalla et al. mention that a powerful conversion to achieve a function-hiding MIPFE scheme is a very interesting open problem [3]. Furthermore, the techniques used in the rather specific constructions of known function-hiding MIPFE schemes [3, 19] are not applicable to our case. This is because our scheme requires the selective setting in a certain step of the proof, if we naively try to prove the security similarly to [3, 19].

Our second main contribution is overcoming this problem by solving the open problem posed by Abdalla et al., that is, we introduce a new powerful and generic conversion. It converts a (weakly) function-hiding IPFE scheme into a (fully) function-hiding MIPFE scheme. Our conversion is as general as that for constructing non-function-hiding MIPFE by Abdalla et al. [3]: the requirements for an underlying scheme are essentially the same. Hence, if new function-hiding IPFE schemes are proposed in the future, e.g., based on lattices, we may utilize our conversion to obtain new function-hiding MIPFE schemes though some modification will be necessary. Additionally, we can obtain (non-tightly-secure) function-hiding MIPFE schemes in a more modular way than the previous ones [3, 19] by utilizing our conversion to function-hiding IPFE schemes, e.g., the scheme from AGRW17 [4] + Lin17 [34]. Applying our conversion to our tightly secure function-hiding IPFE scheme, we can finally achieve the first tightly secure function-hiding MIPFE scheme.

Similarly to all previous IPFE schemes based on a cyclic group or bilinear groups, the decryption algorithms of our schemes require to solve the discrete logarithm problem on a decryption value. As pointed out in [2, 32], however, this step is not so problematic in many cases. This is mainly because decryption values will not become exponentially large in real applications. Additionally, although there are some IPFE schemes that allow exponentially large outputs, they are either inefficient due to the large modulus [6] or based on a non-standard assumption [16].

We summarize the comparison of our schemes with previous ones in Tables 1, 2, 3 and 4. In these tables, we count the numbers of elements assuming that a matrix distribution $\mathcal {D}_{k}$ is a uniform one over $\mathbb {Z}_p^{(k+1)\times k}$. Some readers may be concerned about the increase of the key and ciphertext sizes, which may slow the efficiency of the system even after the compensation of security loss. However, we would like to emphasize that our contribution is the first step toward more efficient tightly secure schemes. Furthermore, our schemes may outperform previous ones in some situations. For example, when we instantiate our function-hiding IPFE scheme from the SXDH, it takes almost 5 times more pairings in decryption than the state-of-the-art scheme (Table 3). As discussed in the previous subsection, the difference of security level possibly affects pairings by the factor of 6 to 7 in practice, and thus there is a possibility that the decryption, the most important process of IPFE, of our scheme is faster than those of previous ones in the same security level. We leave constructing more compact tightly secure IPFE schemes as an interesting open problem.

Table 1. Comparison of adaptively secure IPFE schemes in the multi-user and multi-challenge setting. The columns $|\mathsf{pk}|$ and $|\mathsf{ct}|$ refer to the number of group elements. The columns $|\mathsf{msk}|$ and $|\mathsf{sk}|$ refer to the number of $\mathbb {Z}_p$ elements. The number m refers to the vector length. The number $q_{\mathsf{ct}}$ refers to the total number of ciphertext queries by an adversary. Note that we omit the group description from $|\mathsf{pk}|$.

Table 2. Comparison of MIPFE schemes based on a pairing-free group. The columns $|\mathsf{msk}|$ and $|\mathsf{sk}|$ refer to the number of $\mathbb {Z}_p$ elements. The column $|\mathsf{ct}|$ refers to the number of group elements. The number m refers to the vector length. The number $\mu$ refers to the number of slots. The number $q_{\mathsf{ct}}$ refers to the total number of ciphertext queries for all slots by an adversary.

Table 3. Comparison of fully function-hiding IPFE schemes in the standard model. Lin17 [34] refers to the scheme obtained by applying her paradigm to the IPFE scheme AGRW17 [4]. The column $|\mathsf{msk}|$ refers to the number of $\mathbb {Z}_p$ elements. The columns $|\mathsf{ct}|$ and $|\mathsf{sk}|$ refer to the number of group elements in $G_{1}$ and $G_{2}$ respectively. The number m refers to the vector length. The numbers $q_{\mathsf{ct}}$ and $q_{\mathsf{sk}}$ refer to the total numbers of ciphertext queries and secret key queries by an adversary respectively.

Table 4. Comparison of fully function-hiding MIPFE schemes. The column $|\mathsf{msk}|$ refers to the number of $\mathbb {Z}_p$ elements. The columns $|\mathsf{ct}|$ and $|\mathsf{sk}|$ refer to the number of group elements in $G_{1}$ and $G_{2}$ respectively. The number m refers to the vector length. The number $\mu$ refers to the number of slots. The numbers $q_{\mathsf{ct}}$ and $q_{\mathsf{sk}}$ refer to the total numbers of ciphertext queries for all slots and secret key queries by an adversary respectively.

2 Technical Overview

2.1 Tightly Secure IPFE

Our scheme is secure in the multi-user and multi-challenge setting under the MDDH assumption, but here we describe our scheme based on the DDH assumption in the single-user and multi-challenge setting to ease the exposition. Our starting point is the adaptively secure IPFE scheme by Agrawal et al. [6]. We briefly describe their scheme below. Let m be a vector length in the scheme.

• $\mathsf{Setup}(1^{\lambda }, 1^{m})$: $a \xleftarrow {\mathsf{U}}\mathbb {Z}_p,\;\mathbf{W}\xleftarrow {\mathsf{U}}\mathbb {Z}_p^{m\times 2}, \; \mathbf{a} :=(a,1),\; \mathsf{pk}:=([\mathbf{a}], [\mathbf{W}\mathbf{a}]), \mathsf{msk}:=\mathbf{W}.$

• $\mathsf{Enc}(\mathsf{pk}, \mathbf{x})$: $s \xleftarrow {\mathsf{U}}\mathbb {Z}_p,\;\; \mathsf{ct}:=([s\mathbf{a}], [s\mathbf{W}\mathbf{a}+\mathbf{x}]).$

• $\mathsf{KeyGen}(\mathsf{pk}, \mathsf{msk}, \mathbf{y})$: $\mathsf{sk}:=(-\mathbf{W}^{\top }\mathbf{y}, \mathbf{y} ).$

• $\mathsf{Dec}(\mathsf{pk}, \mathsf{ct}, \mathsf{sk})$: $-\mathbf{y}^{\top }\mathbf{W}[s\mathbf{a}]+\mathbf{y}^{\top }[s\mathbf{W}\mathbf{a}+\mathbf{x}]=[\langle \mathbf{x}, \mathbf{y} \rangle ]$.

Next, we explain the security proof of this scheme by Abdalla et al. [4], which is somewhat different from the original proof by Agrawal et al. and roughly goes as follows. First, the form of the challenge ciphertext is changed from $\mathsf{ct}:=([s\mathbf{a}], [s\mathbf{W}\mathbf{a}+\mathbf{x}^{\beta }])$ to $\mathsf{ct}:=([s\mathbf{a}+s'\mathbf{b}], [\mathbf{W}(s\mathbf{a}+s'\mathbf{b})+\mathbf{x}^{\beta }])$, where $s' \xleftarrow {\mathsf{U}}\mathbb {Z}_p$, $\mathbf{b} :=(1,0)$, and $\beta \xleftarrow {\mathsf{U}}\{0,1\}$. This change is computationally indistinguishable under the DDH assumption. At this point, we redefine $\mathbf{W}$ as

$$\begin{aligned} \mathbf{W} :=\widetilde{\mathbf{W}} + u(\mathbf{x}^{1}-\mathbf{x}^{0})\mathbf{a}^{\bot ^{\top }}, \end{aligned}$$

(2.1)

where $u \xleftarrow {\mathsf{U}}\mathbb {Z}_p$, $\widetilde{\mathbf{W}} \xleftarrow {\mathsf{U}}\mathbb {Z}_p^{m \times 2}$, and $\mathbf{a}^{\bot } :=(1,-a)$, and note that $\mathbf{a}^{\bot ^{\top }}\mathbf{b} =1$. In fact, $\mathbf{x}^{0}$ and $\mathbf{x}^{1}$ may depend on $\widetilde{\mathbf{W}}$ because the information of $\widetilde{\mathbf{W}}$ is leaked to the adversary from the public key and queried secret keys. However, we can assume that $\mathbf{x}^{0}$ and $\mathbf{x}^{1}$ do not depend on $\widetilde{\mathbf{W}}$ (and formally we use complexity leveraging to argue that). Then, redefined $\mathbf{W}$ is also a random element in $\mathbb {Z}_p^{m \times 2}$ and we have

$$\begin{aligned}&\mathbf{W}\mathbf{a} = \widetilde{\mathbf{W}}\mathbf{a}, \end{aligned}$$

(2.2)

$$\begin{aligned}&\mathbf{W}^{\top }\mathbf{y_{\ell }} = \widetilde{\mathbf{W}}^{\top }\mathbf{y_{\ell }}\;\;\; (\ell \text { is an index for the query number)},\end{aligned}$$

(2.3)

$$\begin{aligned}&\begin{aligned} \mathbf{W}(s\mathbf{a}+s'\mathbf{b})+\mathbf{x}^{\beta }&= \widetilde{\mathbf{W}}(s\mathbf{a}+s'\mathbf{b})+us'(\mathbf{x}^{1}-\mathbf{x}^{0})+\mathbf{x}^{\beta } \\&= \widetilde{\mathbf{W}}(s\mathbf{a}+s'\mathbf{b})+(us'+\beta )(\mathbf{x}^{1}-\mathbf{x}^{0})+\mathbf{x}^{0}. \end{aligned} \end{aligned}$$

(2.4)

In the indistinguishability-based security game, we impose a query condition on the adversary to avoid a trivial attack. That is, for all secret key queries, we have $\mathbf{x}^{0}\mathbf{y}_{\ell } = \mathbf{x}^{1}\mathbf{y}_{\ell }$. Equation (2.3) follows from this condition. Finally, from Eq. (2.4), we can argue that the information of $\beta$ is hidden from the adversary by the term $us'$ unless $s' = 0$, because u is a fresh randomness from the viewpoint of the adversary. Thus, the scheme is secure under the DDH assumption. In the multi-challenge setting, however, this proof strategy needs a hybrid argument for each challenge and incurs the security loss of $O(q_{\mathsf{ct}})$, where $q_{\mathsf{ct}}$ is the number of the ciphertext challenges. Intuitively, this is because the matrix $\mathbf{W}$ is shared in all challenge ciphertexts and we cannot redefine $\mathbf{W}$ suitable for all challenge ciphertexts simultaneously in Eq. (2.1).

The first attempt to obtain a tight reduction is setting $\mathbf{W}$ in Eq. (2.1) as

$$\begin{aligned} u_{1}, \ldots ,u_{L} \xleftarrow {\mathsf{U}}\mathbb {Z}_p,\;\;\mathbf{W} :=\widetilde{\mathbf{W}} + \sum _{\iota \in [L]}u_{\iota }\mathbf{x}_{\iota }\mathbf{a}^{\bot ^{\top }}, \end{aligned}$$

where $L (\le m)$ is the dimension of the space V spanned by $\mathbf{x}^{1}_{j} - \mathbf{x}^{0}_{j} \in \mathbb {Z}_p^{m}$ for all $j \in [q_{\mathsf{ct}}]$, and $\{\mathbf{x}_{\iota }\}_{\iota \in [L]}$ are a basis of V. In this case, Eqs. (2.2) and (2.3) do not change and Eq. (2.4) becomes

$$\begin{aligned} \mathbf{W}(s_{j}\mathbf{a}+s'_{j}\mathbf{b})+\mathbf{x}_{j}^{\beta } = \widetilde{\mathbf{W}}(s_{j}\mathbf{a}+s'_{j}\mathbf{b})+s'_{j}\sum _{\iota \in [L]}u_{\iota }\mathbf{x}_{\iota }+\beta (\mathbf{x}^{1}_{j}-\mathbf{x}_{j}^{0} ) + \mathbf{x}_{j}^{0}, \end{aligned}$$

where j is the index of challenge queries. If we can say that $\{[s'_{j}u_{\iota }] \}_{j \in [q_{\mathsf{ct}}], \iota \in [L]}$ are indistinguishable from $\{[r_{j, \iota }] \}_{j \in [q_{\mathsf{ct}}], \iota \in [L]}$, which are $q_{\mathsf{ct}}L$ random elements in G, we can conclude that the term $s'_{j}\sum _{\iota \in [L]}u_{\iota }\mathbf{x}_{\iota }$ hides the information of $\beta$. This is because $\mathbf{x}^{1}_{j}-\mathbf{x}_{j}^{0} \in V$ for all $j \in [q_{\mathsf{ct}}]$, and each $\sum _{\iota \in [L]} r_{j,\iota }\mathbf{x}_{\iota }$ is a completely random element in V. Fortunately, it is well known that $\{s'_{j}u_{\iota } \}_{j \in [q_{\mathsf{ct}}], \iota \in [L]}$ on the exponent forms a synthesizer [36], and they are computationally indistinguishable from $q_{\mathsf{ct}}L$ random group elements with the security loss being either $q_{\mathsf{ct}}$ or L. Thus, we can prove the security of the scheme by Agrawal et al. with the security loss of O(m), which is independent from the adversaries’ behavior.

However, the above proof contains two deficiencies. The first is that the security reduction is still not tight. The second is that the above strategy is useful against only selective adversaries. This is because the reduction algorithm needs to know about V to simulate each challenge ciphertext, but V depends on all challenge queries that the adversary makes. Thus, we have to overcome these two problems.

Toward Tight Security. The solution for the first problem (and partly for the second problem as a result) is to increase the column of the part $\mathbf{a}$, which allows us to embed more randomness into ciphertexts. That is, we modify the scheme as

• $\mathsf{Setup}(1^{\lambda }, 1^{m})$:

  $$\begin{aligned}&a \xleftarrow {\mathsf{U}}\mathbb {Z}_p,\;\;\mathbf{W}\xleftarrow {\mathsf{U}}\mathbb {Z}_p^{m\times 2m}, \;\; \mathbf{a} :=(a,1),\\&\mathbf{A} :=\mathbf{I}_{m} \otimes \mathbf{a} = \overbrace{ \begin{pmatrix} \mathbf{a}&{}&{}&{} \\ &{}\mathbf{a}&{}&{}\\ &{}&{}\ddots &{}\\ &{}&{}&{}\mathbf{a} \end{pmatrix} }^{m \text { vectors}} \in \mathbb {Z}_p^{2m \times m}, \\&\mathsf{pk}:=([\mathbf{a}], [\mathbf{W}\mathbf{A}]),\;\;\mathsf{msk}:=\mathbf{W}. \end{aligned}$$

• $\mathsf{Enc}(\mathsf{pk}, \mathbf{x})$: $\mathbf{s} :=(s_{1}, \ldots ,s_{m}) \xleftarrow {\mathsf{U}}\mathbb {Z}_p^{m},\;\; \mathsf{ct}:=([\mathbf{A}\mathbf{s}], [\mathbf{W}\mathbf{A}\mathbf{s}+\mathbf{x}]).$

• $\mathsf{KeyGen}(\mathsf{pk}, \mathsf{msk}, \mathbf{y})$: $\mathsf{sk}:=(-\mathbf{W}^{\top }\mathbf{y}, \mathbf{y} ).$

• $\mathsf{Dec}(\mathsf{pk}, \mathsf{ct}, \mathsf{sk})$: $-\mathbf{y}^{\top }\mathbf{W}[\mathbf{A}\mathbf{s}]+\mathbf{y}^{\top }[\mathbf{W}\mathbf{A}\mathbf{s}+\mathbf{x}]=[\langle \mathbf{x}, \mathbf{y} \rangle ]$.

The security proof goes as follows. First, the form of all challenge ciphertexts is changed to

$$\begin{aligned}&\mathbf{B} :=\mathbf{I}_{m} \otimes (1,0) \in \mathbb {Z}_p^{2m\times m}, \;\; \mathbf{s}'_{j} :=(s'_{j,1} , \ldots ,s'_{j,m}) \xleftarrow {\mathsf{U}}\mathbb {Z}_p^{m}, \\&\mathsf{ct}:=([\mathbf{A}\mathbf{s}_{j}+\mathbf{B}\mathbf{s}'_{j}], [\mathbf{W}(\mathbf{A}\mathbf{s}_{j}+\mathbf{B}\mathbf{s}'_{j}) + \mathbf{x}^{\beta }_{j}]). \nonumber \end{aligned}$$

(2.5)

The DDH problem is tightly reduced to the problem of distinguishing this change by the random self-reducibility. Next, we redefine $\mathbf{W}$ as

$$\begin{aligned} u \xleftarrow {\mathsf{U}}\mathbb {Z}_p,\;\;\;\mathbf{W} :=\widetilde{\mathbf{W}} + u\sum _{\iota \in [L]}\mathbf{x}_{\iota }\mathbf{a}_{\iota }^{\bot ^{\top }}, \end{aligned}$$

(2.6)

where $\mathbf{a}_{\iota }^{\bot } \in \mathbb {Z}_p^{2m}$ is the $\iota$-th column of $\mathbf{A}^{\bot } :=\mathbf{I}_{m} \otimes \mathbf{a}^{\bot }$. Then, we have

$$\begin{aligned}&\mathbf{W}\mathbf{A} = \widetilde{\mathbf{W}}\mathbf{A}, \nonumber \\&\mathbf{W}^{\top }\mathbf{y_{\ell }} = \widetilde{\mathbf{W}}^{\top }\mathbf{y_{\ell }}, \nonumber \\&\mathbf{W}(\mathbf{A}\mathbf{s}_{j}+\mathbf{B}\mathbf{s}'_{j}) + \mathbf{x}^{\beta }_{j} = \widetilde{\mathbf{W}}(\mathbf{A}\mathbf{s}_{j}+\mathbf{B}\mathbf{s}'_{j}) + u\sum _{\iota \in [L]} s'_{j,\iota } \mathbf{x}_{\iota } +\beta (\mathbf{x}^{1}_{j}-\mathbf{x}_{j}^{0} ) + \mathbf{x}_{j}^{0}. \end{aligned}$$

(2.7)

In this case, we can see that $\{[us'_{j,\iota }] \}_{j \in [q_{\mathsf{ct}}], \iota \in [L]}$ are computationally indistinguishable from $\{[r_{j,\iota }] \}_{j \in [q_{\mathsf{ct}}], \iota \in [L]}$, which are $q_{\mathsf{ct}}L$ random elements in G, and this indistinguishability is tightly reduced to the DDH assumption by the random self-reducibility. Then, the information of $\beta$ is completely hidden by the same argument as before in the selective security model.

Toward Adaptive Security. In this paragraph, we refer to the computational change from $\mathbf{A}\mathbf{s}_{j}$ to $\mathbf{A}\mathbf{s}_{j}+\mathbf{B}\mathbf{s}'_{j}$ as the first step and that from $\{[us'_{j,\iota }] \}_{j \in [q_{\mathsf{ct}}], \iota \in [L]}$ to $\{[r_{j,\iota }] \}_{j \in [q_{\mathsf{ct}}], \iota \in [L]}$ as the second step. The main obstacle to achieve the adaptive security is that the reduction algorithm needs to know about the space V before seeing all challenge queries in the second step. Our observation is that we do not need a random element in V to hide the information of $\beta$ in each ciphertext. Let $V_{j}$ be a space spanned by $\mathbf{x}^{1}_{\iota } - \mathbf{x}^{0}_{\iota } \in \mathbb {Z}_p^{m}$ for all $\iota \in [j]$. Then, a random element in $V_{j}$ suffices to hide the information of $\beta$ in the j-th ciphertext. Fortunately, the reduction algorithm knows about $V_{j}$ when it simulates the j-th ciphertext because it already receives vectors that span $V_{j}$.

To do so, we modify the first step. In particular, we change the way of choosing $\mathbf{s}'_{j}$ in Eq. (2.5) as

$$s'_{j,1} , \ldots ,s'_{j,\phi (j)} \xleftarrow {\mathsf{U}}\mathbb {Z}_p, \;\; \mathbf{s}'_{j} :=(s'_{j,1} , \ldots ,s'_{j,\phi (j)}, 0^{m-\phi (j)}) \in \mathbb {Z}_p^{m},$$

where $\phi (j) :=\dim {V_{j}}$. Next, we modify the definition of $\mathbf{x}_{\iota }$ as $\mathbf{x}_{\iota } :=\mathbf{x}^{1}_{\rho (\iota )} - \mathbf{x}^{0}_{\rho (\iota )} \in \mathbb {Z}_p^{m}$ for all $\iota \in [L]$, where $\rho (\iota ) :=\min \phi ^{-1}(\iota )$. It is not difficult to confirm that $\{\mathbf{x}_{\iota } \}_{\iota \in [\phi (j)]}$ form a basis of $V_{j}$. Then, Eq. (2.7) is changed to

$$\mathbf{W}(\mathbf{A}\mathbf{s}_{j}+\mathbf{B}\mathbf{s}'_{j}) + \mathbf{x}^{\beta }_{j} = \widetilde{\mathbf{W}}(\mathbf{A}\mathbf{s}_{j}+\mathbf{B}\mathbf{s}'_{j}) + u\sum _{\iota \in [\phi (j)]} s'_{j,\iota } \mathbf{x}_{\iota } +\beta (\mathbf{x}^{1}_{j}-\mathbf{x}_{j}^{0} ) + \mathbf{x}_{j}^{0}. $$

Observe that the reduction algorithm can compute $\mathbf{x}_{\iota }$ for $\iota \in [\phi (j)]$ when it simulates the j-th ciphertext. As explained in the previous paragraph, $\{[us'_{j,\iota }] \}_{j \in [q_{\mathsf{ct}}], \iota \in [\phi (j)]}$ are computationally indistinguishable from $\{[r_{j,\iota }] \}_{j \in [q_{\mathsf{ct}}], \iota \in [\phi (j)]}$, and the term $\sum _{\iota \in [\phi (j)]} r_{j, \iota }\mathbf{x}_{\iota }$ hides the information of $\beta$ in the j-th ciphertext. Thus, we can achieve the adaptive security.

2.2 Conversion from Function-Hiding IPFE to Function-Hiding MIPFE

Similarly to previous MIPFE schemes, our conversion utilizes parallel execution of an underlying function-hiding IPFE scheme. The construction of our conversion can be seen as the combination of the non-function-hiding MIPFE scheme by Abdalla et al. [3] and the function-hiding MIPFE scheme by Datta et al. [19]. For simplicity, we consider the IPFE scheme over $\mathbb {Z}_{n}$ for some integer n, which means that the functionality of FE is inner product over $\mathbb {Z}_{n}$. Let m be a vector length and $\mu$ be a number of slots of the converted scheme, and $\mathsf {IPFE} :=(\mathsf{Setup}', \mathsf{Enc}', \mathsf{KeyGen}', \mathsf{Dec}')$ be an underlying weakly function-hiding IPFE scheme. Then, our conversion invokes $\mathsf{Setup}'$ with setting the vector length as $2m+1$ and generates $\mu$ master secret keys $\mathsf{msk}_{1}' , \ldots ,\mathsf{msk}_{\mu }'$ (we omit public parameters here). In addition, it chooses $\mu$ random vectors $\mathbf{u}_{1} , \ldots ,\mathbf{u}_{\mu } \xleftarrow {\mathsf{U}}\mathbb {Z}_{n}^{m}$ and sets a master secret key of the converted scheme as $\mathsf{msk}:=(\mathsf{msk}'_{1} , \ldots ,\mathsf{msk}'_{\mu }, \mathbf{u}_{1} , \ldots ,\mathbf{u}_{\mu })$. To encrypt a vector $\mathbf{x}_{i}$ for the index i, it encrypts $\tilde{\mathbf{x}}_{i} :=(\mathbf{x}_{i}+\mathbf{u}_{i}, 0^{m}, 1)$ as $\mathsf{ct}'_{i} \leftarrow \mathsf{Enc}'(\mathsf{msk}_{i}, \tilde{\mathbf{x}}_{i})$ and outputs $\mathsf{ct}'_{i}$. To generate a secret key for $\{ \mathbf{y}_{i} \}_{i \in [\mu ]}$, it first generates secret shares of $-\sum _{i \in [\mu ]} \langle \mathbf{y}_{i}, \mathbf{u}_{i} \rangle$ as $r_{1} , \ldots ,r_{\mu } \xleftarrow {\mathsf{U}}\mathbb {Z}_{n}$ such that $\sum _{i \in [\mu ]} r_{i} = -\sum _{i \in [\mu ]} \langle \mathbf{y}_{i}, \mathbf{u}_{i} \rangle \pmod {n}$. These shares prevent the leakage of partial inner product values. Then, our conversion generates a secret key for $\tilde{\mathbf{y}}_{i} :=(\mathbf{y}_{i}, 0^{m}, r_{i})$ as $\mathsf{sk}'_{i} \leftarrow \mathsf{KeyGen}'(\mathsf{msk}'_{i}, \tilde{\mathbf{y}}_{i})$ for all $i \in [\mu ]$ . Finally, it sets the secret key for converted scheme as $\mathsf{sk}:=(\mathsf{sk}'_{1} , \ldots ,\mathsf{sk}'_{\mu })$. The decryption algorithm simply computes $\sum _{i \in [\mu ]} \mathsf{Dec}'(\mathsf{ct}'_{i}, \mathsf{sk}'_{i}) \pmod {n}$. The correctness of the converted scheme is not difficult to confirm because $\sum _{i \in [\mu ]} \langle \tilde{\mathbf{x}}_{i}, \tilde{\mathbf{y}}_{i} \rangle = \sum _{i \in [\mu ]} \langle \mathbf{x}_{i}, \mathbf{y}_{i} \rangle$.

Although our conversion is as simple as that by Abdalla et al. [3], the security proof needs a more ingenious technique. To see this, we briefly recall the proof strategy of their conversion and show that the naive application of their strategy to our conversion does not work. Here, we assume that the converted MIPFE scheme is weakly function-hiding, meaning that an adversary against the converted scheme has the following condition on the queries in the security game. Let $q_{\mathsf{ct}, i}$ be the total number of ciphertext queries for index i and $q_{\mathsf{sk}}$ be the total number of secret key queries. Then, for all $(j_{1} , \ldots ,j_{\mu }) \in [q_{\mathsf{ct},1}] \times \cdots \times [q_{\mathsf{ct},\mu }]$, and $\ell \in [q_{\mathsf{sk}}]$, we have

$$\begin{aligned} \sum _{i \in [\mu ]} \langle \mathbf{x}^{0}_{i, j_{i}}, \mathbf{y}^{0}_{i, \ell } \rangle = \sum _{i \in [\mu ]} \langle \mathbf{x}^{0}_{i, j_{i}}, \mathbf{y}^{1}_{i, \ell } \rangle = \sum _{i \in [\mu ]} \langle \mathbf{x}^{1}_{i, j_{i}}, \mathbf{y}^{1}_{i, \ell } \rangle . \end{aligned}$$

(2.8)

The proof employs a series of games, and the goal is that the adversary does not obtain any information about a random bit $\beta$ in the final game. The first step is to redefine $\mathbf{u}_{i} :=\tilde{\mathbf{u}}_{i} + \mathbf{x}^{0}_{i,1}-\mathbf{x}^{\beta }_{i,1}$, where $\tilde{\mathbf{u}}_{i} \xleftarrow {\mathsf{U}}\mathbb {Z}_{n}$. This information-theoretic change does not affect secret keys because $\sum _{i \in [\mu ]} \langle \mathbf{x}^{0}_{i,1}-\mathbf{x}^{\beta }_{i,1}, \mathbf{y}^{\beta }_{i, \ell } \rangle =0$ from Eq. (2.8). The second step is to change $\tilde{\mathbf{x}}_{i,j_{i}}$ from $(\mathbf{x}^{\beta }_{i,j_{i}}+\tilde{\mathbf{u}}_{i}+ \mathbf{x}^{0}_{i,1}-\mathbf{x}^{\beta }_{i,1}, 0^{m}, 1)$ to $(\mathbf{x}^{0}_{i,j_{i}}+\tilde{\mathbf{u}}_{i}, 0^{m}, 1)$. This change is justified by the security of the underlying IPFE scheme because $\langle \mathbf{x}^{\beta }_{i,j_{i}}-\mathbf{x}^{\beta }_{i,1}, \mathbf{y}^{\beta }_{i,\ell } \rangle =\langle \mathbf{x}^{0}_{i,j_{i}}-\mathbf{x}^{0}_{i,1}, \mathbf{y}^{\beta }_{i,\ell } \rangle$ for all $i \in [\mu ]$, which can be derived from Eq. (2.8). Finally, we want to change $\tilde{\mathbf{y}}_{i,\ell }$ from $(\mathbf{y}^{\beta }_{i,\ell }, 0^{m}, r_{i,\ell })$ to $(\mathbf{y}^{0}_{i,\ell }, 0^{m}, r'_{i,\ell })$ to hide the information of $\beta$. However, we cannot make this change in the adaptive setting. The reason is that the reduction algorithm needs to set $r'_{i,\ell } :=r_{i,\ell }+\varDelta _{i,\ell }$, where $\varDelta _{i,\ell } :=\langle \mathbf{x}^{0}_{i,j_{i}}+\mathbf{u}_{i}, \mathbf{y}^{\beta }_{i,\ell }-\mathbf{y}^{0}_{i,\ell } \rangle = \langle \mathbf{x}^{0}_{i,1}+\mathbf{u}_{i}, \mathbf{y}^{\beta }_{i,\ell }-\mathbf{y}^{0}_{i,\ell } \rangle$ (the second equality follows from Eq. (2.8)), to keep the inner product value when it simulates the $\ell$-th secret key. If the adversary makes a secret key query before it makes the first ciphertext query for some index i, the reduction algorithm cannot simulate a secret key because it does not know the value $\langle \mathbf{x}^{0}_{i,1}, \mathbf{y}^{\beta }_{i,\ell }-\mathbf{y}^{0}_{i,\ell } \rangle$. Hence, this strategy does not work.

To circumvent this problem, we introduce another proof strategy. Recall that this problem occurs in the second step, where $\mathbf{y}^{\beta }_{i,\ell }$ is changed to $\mathbf{y}^{0}_{i,\ell }$, whereas the first step goes well, where $\mathbf{x}^{\beta }_{i,j_{i}}$ is changed to $\mathbf{x}^{0}_{i,j_{i}}$. Intuitively, our solution for this problem is to make both changes in one-shot in the same manner as the first step. That is, we do not take the intermediate step where the inner product values of queried vectors are $\sum _{i \in [\mu ]} \langle \mathbf{x}^{0}_{i, j_{i}}, \mathbf{y}^{\beta }_{i, \ell } \rangle$, and we change the replies such that the inner product values of queried vectors are directly changed from $\sum _{i \in [\mu ]} \langle \mathbf{x}^{\beta }_{i, j_{i}}, \mathbf{y}^{\beta }_{i, \ell } \rangle$ to $\sum _{i \in [\mu ]} \langle \mathbf{x}^{0}_{i, j_{i}}, \mathbf{y}^{0}_{i, \ell } \rangle$. This means that our conversion allows us to directly achieve a fully function-hiding MIPFE scheme. This is possible if we prepare $2n+1$ dimensions for the underlying scheme and use the similar technique to that by Tomida et al. [38]. To do so, we want to create a situation where $\tilde{\mathbf{x}}_{i,j_{i}} :=(\mathbf{x}^{\beta }_{i,j_{i}}+\tilde{\mathbf{u}}_{i}-\mathbf{x}^{\beta }_{i,1}, \mathbf{x}^{0}_{i,1}, 1)$ and $\tilde{\mathbf{y}}_{i,\ell } :=(\mathbf{y}^{\beta }_{i,\ell }, \mathbf{y}^{0}_{i,\ell }, r'_{i,\ell })$. This is because if we have the above situation, we can change $\tilde{\mathbf{x}}_{i,j_{i}}$ to $(\tilde{\mathbf{u}}_{i}, \mathbf{x}^{0}_{i,j_{i}}-\mathbf{x}^{0}_{i,1} + \mathbf{x}^{0}_{i,1}, 1) = (\tilde{\mathbf{u}}_{i}, \mathbf{x}^{0}_{i,j_{i}}, 1)$ by the security of the underlying scheme and the relation $\langle \mathbf{x}^{\beta }_{i,j_{i}}-\mathbf{x}^{\beta }_{i,1}, \mathbf{y}^{\beta }_{i,\ell } \rangle =\langle \mathbf{x}^{0}_{i,j_{i}}-\mathbf{x}^{0}_{i,1}, \mathbf{y}^{0}_{i,\ell } \rangle$, which also can be derived from Eq. (2.8).

To reach the situation starting from the real game, however, we need one more trick. This is because the reduction algorithm needs to compute the value $\varDelta _{i,\ell } :=\langle \mathbf{x}^{0}_{i,1}, \mathbf{y}^{0}_{i,\ell } \rangle$ to adjust inner products with the term $r'_{i,\ell }$ when it simulates the $\ell$-th secret key. Thus, the same problems as above occurs. To solve this problem, we take the intermediate step where $\tilde{\mathbf{x}}_{i,j_{i}} :=(\mathbf{x}^{\beta }_{i,j_{i}}+\mathbf{u}_{i}, \mathbf{v}_{i}, 1)$ and $\tilde{\mathbf{y}}_{i,\ell } :=(\mathbf{y}^{\beta }_{i,\ell }, \mathbf{y}^{0}_{i,\ell }, r_{i,\ell })$, where $\mathbf{v}_{i} \xleftarrow {\mathsf{U}}\mathbb {Z}_{n}^{m}$ is randomly chosen at the beginning of the game. This is possible because computing $\varDelta _{i,\ell } :=\langle \mathbf{v}_{i}, \mathbf{y}^{0}_{i,\ell } \rangle$ suffices for the reduction algorithm to reach the step. After the step, we redefine $\mathbf{u}_{i} :=\tilde{\mathbf{u}}_{i}-\mathbf{x}^{\beta }_{i,1}$ and $\mathbf{v}_{i} :=\tilde{\mathbf{v}}_{i} + \mathbf{x}^{0}_{i,1}$ where $\tilde{\mathbf{u}}_{i}, \tilde{\mathbf{v}}_{i} \xleftarrow {\mathsf{U}}\mathbb {Z}_{n}^{m}$. This change is information-theoretic and we do not need to care about when the adversary makes the first ciphertext query. By these steps, our proof strategy goes well since there are no steps where reduction algorithms need to compute values related to $\mathbf{x}^{0}_{i, 1}$ when it simulates secret keys.

The interesting points of our technique are to crucially utilize the blank space, namely the $n+1$ to 2n-th dimensions, and directly construct a fully function-hiding MIPFE scheme from a weakly function-hiding IPFE scheme. This is in contrast to the function-hiding scheme in [3], where they first construct a weakly function-hiding MIPFE scheme, setting a vector length of an underlying IPFE scheme as almost n. Then, they convert it into a fully function-hiding scheme by doubling the vector length of the scheme.

3 Preliminary

3.1 Notation

For a natural number $n \in \mathbb {N}$, $\mathbb {Z}_{n}$ denotes a ring $\mathbb {Z}/ n\mathbb {Z}$ and [n] denotes a set $\{ 1, \ldots ,n \}$. For a set S, $s \xleftarrow {\mathsf{U}}S$ denotes that s is uniformly chosen from S. We treat vectors as column vectors. For a vector $\mathbf{x}$, $||\mathbf{x}||_{\infty }$ denotes its infinity norm. For vectors $\mathbf{v}_{1}, \mathbf{v}_{2} , \ldots ,\mathbf{v}_{n}$, $(\mathbf{v}_{1}, \mathbf{v}_{2} , \ldots ,\mathbf{v}_{n})$ denotes a vector generated by the vertical concatenation of these vectors. For matrices (including vectors) with the same number of rows $\mathbf{A}_{1}, \mathbf{A}_{2} , \ldots ,\mathbf{A}_{n}$, $(\mathbf{A}_{1}||\mathbf{A}_{2}|| \cdots ||\mathbf{A}_{n})$ denotes a matrix generated by the horizontal concatenation of these matrices. For a generator $g_{i}$ of a cyclic group $G_{i}$ of order p and $a \in \mathbb {Z}_p$, $[a]_{i}$ denotes $g_{i}^{a}$. Furthermore, for a matrix $\mathbf{A} :=(a_{j,\ell })_{j,\ell }$ over $\mathbb {Z}_p$, $[\mathbf{A}]_{i}$ denotes a matrix over $G_{i}$ whose (i, j) entry is $g_{i}^{a_{j,\ell }}$. For vectors $\mathbf{x} :=(x_{1} , \ldots ,x_{n})$ and $\mathbf{y} :=(y_{1} , \ldots ,y_{n}) \in \mathbb {Z}_p^{n}$, let $e([\mathbf{x}]_{1}, [\mathbf{y}]_{2}) :=e(g_{1}, g_{2})^{\langle \mathbf{x}, \mathbf{y} \rangle }$ be a function that computes the inner product on the exponent by $\prod _{i \in [n]} e([x_{i}]_{1}, [y_{i}]_{2})$. A matrix $\mathbf{I}_n$ denotes the $n \times n$ identity matrix. A matrix $\mathbf{O}_{m \times n}$ denotes the $m \times n$ zero matrix. A function $f:\mathbb {N}\rightarrow \mathbb {R}$ is called negligible if $f(\lambda ) = \lambda ^{-\omega (1)}$ and denotes $f(\lambda ) \le \mathsf {negl}(\lambda )$. For families of distributions $X :=\{X_{\lambda }\}_{\lambda \in \mathbb {N}}$ and $Y :=\{Y_{\lambda }\}_{\lambda \in \mathbb {N}}$, $X \approx _{c} Y$ means that they are computationally indistinguishable.

3.2 Basic Tools and Assumption

Definition 3.1

(Cyclic Group). A description of a cyclic group $\mathbb {G}_{\mathsf {CG}} {:=} (p, G, g)$ consists of a prime p, a cyclic group G of order p, and a generator g. A cyclic group generator $\mathcal {G}_\mathsf{CG}(1^\lambda )$ takes a security parameter $1^{\lambda }$ and outputs a description of a cyclic group $\mathbb {G}_{\mathsf {CG}}$ with a $\lambda$-bit prime p.

Definition 3.2

(Bilinear Groups). A description of bilinear groups $\mathbb {G}_{\mathsf {BG}} {:=} (p, G_{1}, G_{2}, G_{T}, g_{1},g_{2},e)$ consist of a prime p, cyclic groups $G_{1},G_{2},G_{T}$ of order p, generators $g_{1}$ and $g_{2}$ of $G_{1}$ and $G_{2}$ respectively, and a bilinear map $e:G_{1} \times G_{2} \rightarrow G_{T}$, which has two properties.

• (Bilinearity): $\forall h_{1} \in G_{1}, h_{2} \in G_{2} ,a,b \in \mathbb {Z}_p, e(h^{a}_{1}, h^{b}_{2}) = e(h_{1},h_{2})^{ab}$.

• (Non-degeneracy): For generators $g_{1}$ and $g_{2}$, $g_{T} :=e(g_{1}, g_{2})$ is a generator of $G_{T}$.

A bilinear group generator $\mathcal {G}_\mathsf{BG}(1^\lambda )$ takes a security parameter $1^{\lambda }$ and outputs a description of bilinear groups $\mathbb {G}_{\mathsf {BG}}$ with a $\lambda$-bit prime p.

Definition 3.3

($\mathcal {D}_{k}$-MDDH Assumption [21]). Let $\mathcal {D}_{k}$ be a matrix distribution over full rank matrices in $\mathbb {Z}_p^{(k+1) \times k}$. We can assume that, wlog, the first k rows of a matrix $\mathbf{A}$ chosen from $\mathcal {D}_{k}$ forms an invertible matrix. We consider the following distribution:

$$\begin{aligned}&\mathbb {G}_{\mathsf {CG}} \leftarrow \mathcal {G}_\mathsf{CG}(1^\lambda ),\;\;\mathbb {G}_{\mathsf {BG}} \leftarrow \mathcal {G}_\mathsf{BG}(1^\lambda ),\\&\mathbf{A} \leftarrow \mathcal {D}_{k}, \;\; \mathbf{v} \xleftarrow {\mathsf{U}}\mathbb {Z}_p^{k},\;\; \mathbf{t}_{0} :=\mathbf{A}\mathbf{v},\;\; \mathbf{t}_{1} \xleftarrow {\mathsf{U}}\mathbb {Z}_p^{k+1}. \end{aligned}$$

We say that the $\mathcal {D}_{k}$-MDDH assumption holds with respect to $\mathcal {G}_{\mathsf {CG}}$ if the advantage of any PPT adversary $\mathcal {A}$ defined below is negligible,

$$\mathsf{Adv}_{\mathcal {A}, \mathsf {CG}}^{\mathsf {\mathcal {D}_{k}\text {-}MDDH}}(\lambda ) :=|\mathsf{Pr}[1 \leftarrow \mathcal {A}(\mathbb {G}_{\mathsf {CG}}, [\mathbf{A}], [\mathbf{t}_{0}])] - \mathsf{Pr}[1 \leftarrow \mathcal {A}(\mathbb {G}_{\mathsf {CG}}, [\mathbf{A}], [\mathbf{t}_{1}])]|,$$

and with respect to $\mathcal {G}_{\mathsf {BG}}$ if the advantage of any PPT adversary $\mathcal {A}$ for both $i \in \{1,2\}$ defined below is negligible,

$$\mathsf{Adv}_{\mathcal {A}, \mathsf {BG}, i}^{\mathsf {\mathcal {D}_{k}\text {-}MDDH}}(\lambda ) :=|\mathsf{Pr}[1 \leftarrow \mathcal {A}(\mathbb {G}_{\mathsf {BG}}, [\mathbf{A}]_{i}, [\mathbf{t}_{0}]_{i})] - \mathsf{Pr}[1 \leftarrow \mathcal {A}(\mathbb {G}_{\mathsf {BG}}, [\mathbf{A}]_{i}, [\mathbf{t}_{1}]_{i})]|.$$

Random Self-reducibility. By the random self-reducibility, we can obtain arbitrarily many instances of the $\mathcal {D}_{k}$-MDDH problem without additional security loss. For any $n \in \mathbb {N}$, we additionally define the following distribution:

$$\begin{aligned} \mathbf{V} \xleftarrow {\mathsf{U}}\mathbb {Z}_p^{k \times n},\;\; \mathbf{T}_{0} :=\mathbf{A}\mathbf{V},\;\; \mathbf{T}_{1} \xleftarrow {\mathsf{U}}\mathbb {Z}_p^{(k+1) \times n}. \end{aligned}$$

The advantages of $\mathcal {A}$ against n-fold $\mathcal {D}_{k}$-MDDH assumption with respect to $\mathcal {G}_{\mathsf {CG}}$ and $\mathcal {G}_{\mathsf {BG}}$ are defined as:

$$\begin{aligned}&\mathsf{Adv}_{\mathcal {A}, \mathsf {CG}}^{\mathsf {n \text {-} \mathcal {D}_{k}\text {-}MDDH}}(\lambda ) :=|\mathsf{Pr}[1 \leftarrow \mathcal {A}(\mathbb {G}_{\mathsf {CG}}, [\mathbf{A}], [\mathbf{T}_{0}])] - \mathsf{Pr}[1 \leftarrow \mathcal {A}(\mathbb {G}_{\mathsf {CG}}, [\mathbf{A}], [\mathbf{T}_{1}])]|,\\&\mathsf{Adv}_{\mathcal {A}, \mathsf {BG}, i}^{\mathsf {n\text {-}\mathcal {D}_{k}\text {-}MDDH}}(\lambda ) :=|\mathsf{Pr}[1 \leftarrow \mathcal {A}(\mathbb {G}_{\mathsf {BG}}, [\mathbf{A}]_{i}, [\mathbf{T}_{0}]_{i})] - \mathsf{Pr}[1 \leftarrow \mathcal {A}(\mathbb {G}_{\mathsf {BG}}, [\mathbf{A}]_{i}, [\mathbf{T}_{1}]_{i})]|. \end{aligned}$$

Then, for any PPT adversaries $\mathcal {A}_{1}, \mathcal {A}_{2}$ and both $i \in \{1,2\}$, there exist PPT adversaries $\mathcal {B}_{1}, \mathcal {B}_{2}$ and we have

$$\begin{aligned}&\mathsf{Adv}_{\mathcal {A}_{1}, \mathsf {CG}}^{\mathsf {n \text {-} \mathcal {D}_{k}\text {-}MDDH}}(\lambda ) \le \mathsf{Adv}_{\mathcal {B}_{1}, \mathsf {CG}}^{\mathsf {\mathcal {D}_{k}\text {-}MDDH}}(\lambda ) +2^{-\varOmega (\lambda )},\\&\mathsf{Adv}_{\mathcal {A}_{2}, \mathsf {BG}, i}^{\mathsf {n \text {-} \mathcal {D}_{k}\text {-}MDDH}}(\lambda ) \le \mathsf{Adv}_{\mathcal {B}_{2}, \mathsf {BG}, i}^{\mathsf {\mathcal {D}_{k}\text {-}MDDH}}(\lambda ) +2^{-\varOmega (\lambda )},\\&\mathsf {Time}(\mathcal {B}_{j}) \approx \mathsf {Time}(\mathcal {A}_{j}) + n \mathsf {poly}_{j}(\lambda ) \;\; \text {for both }j \in \{1,2\}, \end{aligned}$$

where $\mathsf {poly}_{j}(\lambda )$ is independent from $\mathsf {Time}(\mathcal {A}_{j})$.

3.3 Definitions of Inner Product Functional Encryption

In this paper, we treat both single-input inner product functional encryption (IPFE) and multi-input IPFE. In both cases, the inner product functionality is defined over $\mathbb {Z}$ and its domain is limited depending on the infinity norms of the input vectors. We formally define the functionality called bonded-norm inner product.

Definition 3.4

(Bounded-Norm Inner Product over $\mathbb {Z}$). This function family $\mathcal {F}$ consists of functions $f^{X,Y}_{\mathbf{y}_{1}, \ldots ,\mathbf{y}_{\mu }}: \mathbb {Z}^{m} \times \cdots \times \mathbb {Z}^{m} \rightarrow \mathbb {Z}$ where $m, \mu , X,Y \in \mathbb {N}$, $\mathbf{y}_{i} \in \mathbb {Z}^{m}$ s.t. $||\mathbf{y}_{i}||_{\infty } \le Y$. For all $(\mathbf{x}_{1} , \ldots ,\mathbf{x}_{\mu }) \in (\mathbb {Z}^{m})^{\mu }$ s.t. $\forall i \in [\mu ],||\mathbf{x}_{i}||_{\infty } \le X$, we define the function as

$$f^{X,Y}_{\mathbf{y}_{1}, \ldots ,\mathbf{y}_{\mu }}(\mathbf{x}_{1}, \ldots ,\mathbf{x}_{\mu }) :=\sum _{i \in [\mu ]} \langle \mathbf{x}_{i}, \mathbf{y}_{i} \rangle .$$

We call $\mu$ a number of slots. We refer to the function as single-input inner product when $\mu =1$, and multi-input inner product when $\mu >1$.

With respect to single-input IPFE, there are two types of IPFE: public-key IPFE and private-key IPFE. To achieve the function privacy, we need the private-key setting as defined below. Roughly speaking, this is because an adversary can learn the information of functions embedded in secret keys by decrypting ciphetexts generated by itself with the secret keys in the public-key setting.

Definition 3.5

(Public-Key Inner Product Functional Encryption). Let $\mathcal {X}:=\{X_{\lambda } \}_{\lambda \in \mathbb {N}}, \mathcal {Y}:=\{Y_{\lambda } \}_{\lambda \in \mathbb {N}}$ be ensembles of norm-bounds. Public-key inner product functional encryption (Pub-IPFE) consists of five algorithms.

• $\mathsf{Par}(1^{\lambda })$: It takes a security parameter $1^{\lambda }$ and outputs a public parameter $\mathsf{pp}$.

• $\mathsf{Setup}(1^{m}, \mathsf{pp})$: It takes a vector length $1^{m}$ and $\mathsf{pp}$ and outputs a public key $\mathsf{pk}$ and a master secret key $\mathsf{msk}$.

• $\mathsf{Enc}(\mathsf{pk}, \mathbf{x})$: It takes $\mathsf{pk}$ and a vector $\mathbf{x} :=(x_{1} , \ldots ,x_m) \in \mathbb {Z}^{m}$ and outputs a ciphertext $\mathsf{ct}$.

• $\mathsf{KeyGen}(\mathsf{pk}, \mathsf{msk}, \mathbf{y})$: It takes $\mathsf{pk}, \mathsf{msk}$, and a vector $\mathbf{y} :=(y_{1} , \ldots ,y_{m}) \in \mathbb {Z}^{m}$ and outputs a secret key $\mathsf{sk}$.

• $\mathsf{Dec}(\mathsf{pk}, \mathsf{ct}, \mathsf{sk})$: It takes $\mathsf{pk}, \mathsf{ct}$ and $\mathsf{sk}$ and outputs a decrypted value $d \in \mathbb {Z}$ or a symbol $\bot$.

Correctness. Pub-IPFE is correct if it satisfies the following condition. For any $\lambda , m \in \mathbb {N}$ and for any $\mathbf{x}, \mathbf{y} \in \mathbb {Z}^{m}$ s.t. $||\mathbf{x}||_{\infty } \le X_{\lambda }$ and $||\mathbf{y}||_{\infty } \le Y_{\lambda }$, we have

$$\begin{aligned} \mathsf{Pr}\left[ d = \langle \mathbf{x}, \mathbf{y} \rangle \; \begin{array}{|l} \;\mathsf{pp}\leftarrow \mathsf{Par}(1^{\lambda })\\ \;(\mathsf{pk},\mathsf{msk}) \leftarrow \mathsf{Setup}(1^{m}, \mathsf{pp})\\ \;\mathsf{ct}\leftarrow \mathsf{Enc}(\mathsf{pk}, \mathbf{x})\\ \;\mathsf{sk}\leftarrow \mathsf{KeyGen}(\mathsf{pk}, \mathsf{msk}, \mathbf{y})\\ \;d :=\mathsf{Dec}(\mathsf{pk}, \mathsf{ct}, \mathsf{sk}) \end{array} \right] = 1. \end{aligned}$$

Security. Let $\mu \in \mathbb {N}$ be a natural number that represents the number of users. Pub-IPFE is adaptively secure in the multi-user and multi-challenge setting if it satisfies the following condition. That is, the advantage of $\mathcal {A}$ against Pub-IPFE defined as follows is negligible in $\lambda$ for any constant $m, \mu \in \mathbb {N}$, and PPT adversary $\mathcal {A}$,

$$\begin{aligned} \mathsf{Adv}_{\mathcal {A}}^{\mathsf {Pub\text {-}IPFE}}(\lambda ) :=\left| 2\textsf {Pr} \left[ \beta =\beta '\; \begin{array}{|l} \beta \xleftarrow {\mathsf{U}}\{0,1\}, \;\;\mathsf{pp}\leftarrow \mathsf{Par}(1^{\lambda })\\ \{(\mathsf{pk}_{i}, \mathsf{msk}_{i})\}_{i \in [\mu ]} \leftarrow \mathsf{Setup}(1^{m}, \mathsf{pp})\\ \beta ' \leftarrow \mathcal {A}^{\mathcal {O}_{\mathsf{ct}}(\beta , \cdot ,\cdot ), \mathcal {O}_{\mathsf{sk}}(\cdot , \cdot )}(1^{\lambda }, \{\mathsf{pk}_{i}\}_{i \in [\mu ]})\\ \end{array} \right] -1 \right| . \end{aligned}$$

The description of the oracles $\mathcal {O}_{\mathsf{ct}}$ and $\mathcal {O}_{\mathsf{sk}}$ is presented in Fig. 1. We refer to queries to $\mathcal {O}_{\mathsf{ct}}$ and $\mathcal {O}_{\mathsf{sk}}$ as a ciphertext query and a secret key query respectively. To avoid a trivial attack of $\mathcal {A}$, we have the following condition on $\mathcal {A}$’s queries. Let $q_{\mathsf{ct}, i}$ and $q_{\mathsf{sk}, i}$ be the total number of ciphertext queries and secret key queries for index i respectively. Then, for all $i \in [\mu ]$, $j_{i} \in [q_{\mathsf{ct},i}]$, and $\ell _{i} \in [q_{\mathsf{sk},i}]$, we have

$$\begin{aligned} \langle \mathbf{x}^{0}_{i, j_{i}}, \mathbf{y}_{i, \ell _{i}} \rangle = \langle \mathbf{x}^{1}_{i, j_{i}}, \mathbf{y}_{i, \ell _{i}} \rangle . \end{aligned}$$

(3.1)

Fig. 1.

The description of oracles in the security game for Pub-IPFE.

Definition 3.6

(Private-Key Inner Product Functional Encryption). Let $\mathcal {X}:=\{X_{\lambda } \}_{\lambda \in \mathbb {N}}, \mathcal {Y}:=\{Y_{\lambda } \}_{\lambda \in \mathbb {N}}$ be ensembles of norm-bounds. Private-key inner product functional encryption (Priv-IPFE) consists of five algorithms.

• $\mathsf{Par}(1^{\lambda })$: It takes a security parameter $1^{\lambda }$ and outputs a public parameter $\mathsf{pp}$.

• $\mathsf{Setup}(1^{m}, \mathsf{pp})$: It takes a vector length $1^{m}$ and $\mathsf{pp}$ and outputs a master secret key $\mathsf{msk}$.

• $\mathsf{Enc}(\mathsf{pp}, \mathsf{msk}, \mathbf{x})$: It takes $\mathsf{pp}$, $\mathsf{msk}$, and a vector $\mathbf{x} :=(x_{1} , \ldots ,x_m) \in \mathbb {Z}^{m}$ and outputs a ciphertext $\mathsf{ct}$.

• $\mathsf{KeyGen}(\mathsf{pp}, \mathsf{msk}, \mathbf{y})$: It takes $\mathsf{pp}, \mathsf{msk}$, and a vector $\mathbf{y} :=(y_{1} , \ldots ,y_{m}) \in \mathbb {Z}^{m}$ and outputs a secret key $\mathsf{sk}$.

• $\mathsf{Dec}(\mathsf{pp}, \mathsf{ct}, \mathsf{sk})$: It takes $\mathsf{pp}, \mathsf{ct}$ and $\mathsf{sk}$ and outputs a decrypted value $d \in \mathbb {Z}$ or a symbol $\bot$.

Correctness. Priv-IPFE is correct if it satisfies the following condition. For any $\lambda , m \in \mathbb {N}$ and for any $\mathbf{x}, \mathbf{y} \in \mathbb {Z}^{m}$ s.t. $||\mathbf{x}||_{\infty } \le X_{\lambda }$ and $||\mathbf{y}||_{\infty } \le Y_{\lambda }$, we have

$$\begin{aligned} \mathsf{Pr}\left[ d = \langle \mathbf{x}, \mathbf{y} \rangle \; \begin{array}{|l} \;\mathsf{pp}\leftarrow \mathsf{Par}(1^{\lambda })\\ \;\mathsf{msk}\leftarrow \mathsf{Setup}(1^{m}, \mathsf{pp})\\ \;\mathsf{ct}\leftarrow \mathsf{Enc}(\mathsf{pp}, \mathsf{msk}, \mathbf{x})\\ \;\mathsf{sk}\leftarrow \mathsf{KeyGen}(\mathsf{pp}, \mathsf{msk}, \mathbf{y})\\ \;d :=\mathsf{Dec}(\mathsf{pp}, \mathsf{ct}, \mathsf{sk}) \end{array} \right] = 1. \end{aligned}$$

Security. Let $\mu \in \mathbb {N}$ be a natural number that represents the number of users. Priv-IPFE is fully function-hiding in the multi-user setting if it satisfies the following condition. That is, the advantage of $\mathcal {A}$ against Priv-IPFE defined as follows is negligible in $\lambda$ for any constant $m, \mu \in \mathbb {N}$ and any PPT adversary $\mathcal {A}$,

$$\begin{aligned} \mathsf{Adv}_{\mathcal {A}, \mathsf {f \text {-}fh}}^{\mathsf {Priv\text {-}IPFE}}(\lambda ) :=\left| \begin{array}{l} \textsf {Pr} \left[ \beta '=1\; \begin{array}{|l} \mathsf{pp}\leftarrow \mathsf{Par}(1^{\lambda })\\ \{\mathsf{msk}_{i}\}_{i \in [\mu ]} \leftarrow \mathsf{Setup}(1^{m}, \mathsf{pp})\\ \beta ' \leftarrow \mathcal {A}^{\mathcal {O}_{\mathsf{ct}}(0 \cdot ,\cdot ), \mathcal {O}_{\mathsf{sk}}(0,\cdot , \cdot )}(\mathsf{pp})\\ \end{array} \right] \\ - \textsf {Pr} \left[ \beta '=1\; \begin{array}{|l} \mathsf{pp}\leftarrow \mathsf{Par}(1^{\lambda })\\ \{\mathsf{msk}_{i}\}_{i \in [\mu ]} \leftarrow \mathsf{Setup}(1^{m}, \mathsf{pp})\\ \beta ' \leftarrow \mathcal {A}^{\mathcal {O}_{\mathsf{ct}}(1, \cdot ,\cdot ), \mathcal {O}_{\mathsf{sk}}(1,\cdot , \cdot )}(\mathsf{pp})\\ \end{array} \right] \end{array} \right| . \end{aligned}$$

It is convenient for our paper to define the advantage on Priv-IPFE as above rather than the form like $|2\mathsf{Pr}[\beta =\beta ']-1|$, and both formulations are equivalent. The description of the oracles $\mathcal {O}_{\mathsf{ct}}$ and $\mathcal {O}_{\mathsf{sk}}$ is presented in Fig. 2. We refer to queries to $\mathcal {O}_{\mathsf{ct}}$ and $\mathcal {O}_{\mathsf{sk}}$ as a ciphertext query and a secret key query respectively. To avoid a trivial attack of $\mathcal {A}$, we have the following condition on $\mathcal {A}$’s queries. Let $q_{\mathsf{ct}, i}$ and $q_{\mathsf{sk}, i}$ be the total numbers of ciphertext queries and secret key queries for index i respectively. Then, for all $i \in [\mu ]$, $j_{i} \in [q_{\mathsf{ct},i}]$, and $\ell _{i} \in [q_{\mathsf{sk},i}]$, we have

$$\begin{aligned} \langle \mathbf{x}^{0}_{i, j_{i}}, \mathbf{y}^{0}_{i, \ell _{i}} \rangle = \langle \mathbf{x}^{1}_{i, j_{i}}, \mathbf{y}^{1}_{i, \ell _{i}} \rangle . \end{aligned}$$

(3.2)

We say that Priv-IPFE is weakly function-hiding in the multi-user setting if it satisfies the above definition except that the query condition of $\mathcal {A}$ is more restricted as follows. That is, for all $i \in [\mu ]$, $j_{i} \in [q_{\mathsf{ct},i}]$, and $\ell _{i} \in [q_{\mathsf{sk},i}]$, we have

$$\begin{aligned} \langle \mathbf{x}^{0}_{i, j_{i}}, \mathbf{y}^{0}_{i, \ell _{i}} \rangle = \langle \mathbf{x}^{1}_{i, j_{i}}, \mathbf{y}^{0}_{i, \ell _{i}} \rangle = \langle \mathbf{x}^{1}_{i, j_{i}}, \mathbf{y}^{1}_{i, \ell _{i}} \rangle . \end{aligned}$$

(3.3)

We denote the advantage of $\mathcal {A}$ in weakly function-hiding game in the multi-user setting by $\mathsf{Adv}_{\mathcal {A},\mathsf {w \text {-}fh}}^{\mathsf {Priv\text {-}IPFE}}(\lambda )$.

Fig. 2.

The description of oracles in the security game for Priv-IPFE.

As pointed out by Abdalla et al. [4], public-key multi-input IPFE (MIPFE) is almost meaningless because it inherently leaks the same amount of information as parallel execution of single-input IPFE. Therefore, following them, we only consider private-key MIPFE in this paper.

Definition 3.7

(Multi-input Inner Product Functional Encryption). Let $\mathcal {X}:=\{X_{\lambda } \}_{\lambda \in \mathbb {N}}, \mathcal {Y}:=\{Y_{\lambda } \}_{\lambda \in \mathbb {N}}$ be ensembles of norm-bound. Multi-input inner product functional encryption (MIPFE) consists of four algorithms.

• $\mathsf{Setup}(1^{\lambda }, 1^{m}, 1^{\mu })$: It takes a security parameter $1^{\lambda }$, a vector length $1^{m}$, and a number of slots $1^{\mu }$. Then, it outputs a public parameter $\mathsf{pp}$ and a master secret key $\mathsf{msk}$.

• $\mathsf{Enc}(\mathsf{pp}, \mathsf{msk}, i, \mathbf{x})$: It takes $\mathsf{pp}$, $\mathsf{msk}$, an index $i \in [\mu ]$, and a vector $\mathbf{x} :=(x_{1} , \ldots ,x_m) \in \mathbb {Z}^{m}$ and outputs a ciphertext $\mathsf{ct}_{i}$.

• $\mathsf{KeyGen}(\mathsf{pp}, \mathsf{msk}, \{\mathbf{y}_{i} \}_{i \in [\mu ]})$: It takes $\mathsf{pp}, \mathsf{msk}$, and vectors $\{ \mathbf{y}_{i} :=(y_{i,1} , \ldots , y_{i,m}) \}_{i \in [\mu ]} \in (\mathbb {Z}^{m})^{\mu }$, and outputs a secret key $\mathsf{sk}$.

• $\mathsf{Dec}(\mathsf{pp}, \mathsf{ct}_{1} , \ldots ,\mathsf{ct}_{\mu }, \mathsf{sk})$: It takes $\mathsf{pp}, \mathsf{ct}_{1} , \ldots ,\mathsf{ct}_{\mu }$ and $\mathsf{sk}$ and outputs a decrypted value $d \in \mathbb {Z}$ or a symbol $\bot$.

Correctness. MIPFE is correct if it satisfies the following condition. For any $\lambda , m, \mu \in \mathbb {N}$ and for any $\{ \mathbf{x}_{i} \}_{i \in [\mu ]}, \{ \mathbf{y}_{i} \}_{i \in [\mu ]} \in (\mathbb {Z}^{m})^{\mu }$ s.t. $\forall i,||\mathbf{x}_{i}||_{\infty } \le X_{\lambda }$ and $||\mathbf{y}_{i}||_{\infty } \le Y_{\lambda }$, we have

$$\begin{aligned} \mathsf{Pr}\left[ d =\sum _{i \in [\mu ]} \langle \mathbf{x}_{i}, \mathbf{y}_{i} \rangle \; \begin{array}{|l} \;\mathsf{pp}, \mathsf{msk}\leftarrow \mathsf{Setup}(1^{\lambda }, 1^{m}, 1^{\mu })\\ \;\mathsf{ct}_{i} \leftarrow \mathsf{Enc}(\mathsf{pp}, \mathsf{msk}, i, \mathbf{x}_{i}) \;\;\;\text {for all }i \in [\mu ]\\ \;\mathsf{sk}\leftarrow \mathsf{KeyGen}(\mathsf{pp}, \mathsf{msk}, \{\mathbf{y}_{i} \}_{i \in [\mu ]})\\ \;d :=\mathsf{Dec}(\mathsf{pp}, \mathsf{ct}, \mathsf{sk}) \end{array} \right] = 1. \end{aligned}$$

Security. MIPFE is fully function-hiding if it satisfies the following condition. That is, the advantage of $\mathcal {A}$ against MIPFE defined as follows is negligible in $\lambda$ for any constant $m, \mu \in \mathbb {N}$ and any PPT adversary $\mathcal {A}$,

$$\begin{aligned} \mathsf{Adv}_{\mathcal {A}, \mathsf {f \text {-}fh}}^{\mathsf {MIPFE}}(\lambda ) :=\left| 2\textsf {Pr} \left[ \beta =\beta '\; \begin{array}{|l} \beta \xleftarrow {\mathsf{U}}\{0,1\}, \\ (\mathsf{pp}, \mathsf{msk}) \leftarrow \mathsf{Setup}(1^{\lambda }, 1^{m}, 1^{\mu })\\ \beta ' \leftarrow \mathcal {A}^{\mathcal {O}_{\mathsf{ct}}(\beta , \cdot ,\cdot ), \mathcal {O}_{\mathsf{sk}}(\beta , \cdot )}(\mathsf{pp})\\ \end{array} \right] -1 \right| . \end{aligned}$$

The description of the oracles $\mathcal {O}_{\mathsf{ct}}$ and $\mathcal {O}_{\mathsf{sk}}$ is presented in Fig. 3. We refer to queries to $\mathcal {O}_{\mathsf{ct}}$ and $\mathcal {O}_{\mathsf{sk}}$ as a ciphertext query and a secret key query respectively. To avoid a trivial attack of $\mathcal {A}$, we have the following condition on $\mathcal {A}$’s queries. Let $q_{\mathsf{ct}, i}$ be the total number of ciphertext queries for index i and $q_{\mathsf{sk}}$ be the total number of secret key queries. Then, for all $(j_{1} , \ldots ,j_{\mu }) \in [q_{\mathsf{ct},1}] \times \cdots \times [q_{\mathsf{ct},\mu }]$, and $\ell \in [q_{\mathsf{sk}}]$,

$$\begin{aligned} \sum _{i \in [\mu ]} \langle \mathbf{x}^{0}_{i, j_{i}}, \mathbf{y}^{0}_{i, \ell } \rangle = \sum _{i \in [\mu ]} \langle \mathbf{x}^{1}_{i, j_{i}}, \mathbf{y}^{1}_{i, \ell } \rangle . \end{aligned}$$

(3.4)

In this paper, we assume that $q_{\mathsf{ct},i} \ge 1$ for all $i \in [\mu ]$ and $q_{\mathsf{sk}} \ge 1$. Note that this condition can be easily removed by simply utilizing symmetric key encryption [4, 19].

We say that MIPFE is just adaptively secure if it satisfies the above definition except that $\mathcal {O}_{\mathsf{sk}}(\beta ,\cdot )$ is replaced to $\mathsf{KeyGen}(\mathsf{pp},\mathsf{msk},\cdot )$, and $\mathbf{y}^{0}_{i, \ell }$ and $\mathbf{y}^{1}_{i, \ell }$ are changed to $\mathbf{y}_{i, \ell }$ in Eq. (3.4). This security definition captures only the message privacy of MIPFE schemes, i.e., the scheme is non-function-hiding. We denote the advantage of $\mathcal {A}$ in the adaptive-security game by $\mathsf{Adv}_{\mathcal {A},\mathsf {ad}}^{\mathsf {MIPFE}}(\lambda )$. Note that we do not explicitly use the word “adaptive” in the definitions of function-hiding because it seems wordy, but we consider only the adaptive security for function-hiding schemes in this paper.

Fig. 3.

The description of oracles in the security game for MIPFE.

4 Tightly Secure (Multi-input) Inner Product Functional Encryption

In this section, we present our tightly secure Pub-IPFE scheme and non-function-hiding MIPFE scheme, the latter is obtained by applying the conversion by Abdalla et al. [3] to our IPFE scheme.

4.1 Construction

Let $\mathcal {D}_{k}$ be a matrix distribution over full rank matrices in $\mathbb {Z}_p^{(k+1) \times k}$ and norm bounds $X_{\lambda }$ and $Y_{\lambda }$ be polynomials in $\lambda$.

• $\mathsf{Par}(1^{\lambda })$: It takes a security parameter $1^\lambda$ and outputs $\mathsf{pp}$ as follows.

  $$\begin{aligned} \mathbb {G}_{\mathsf {CG}} \leftarrow \mathcal {G}_\mathsf{CG}(1^\lambda ),\;\; \tilde{\mathbf{A}} \leftarrow \mathcal {D}_{k}, \;\; \mathsf{pp}:=(\mathbb {G}_{\mathsf {CG}}, [\tilde{\mathbf{A}}]) \end{aligned}$$

• $\mathsf{Setup}(1^{m}, \mathsf{pp})$: It takes a vector length $1^{m}$ and a public parameter $\mathsf{pp}$. Then, it outputs a public key $\mathsf{pk}$ and a master secret key $\mathsf{msk}$ as follows.

  $$\begin{aligned}&\mathbf{W} \xleftarrow {\mathsf{U}}\mathbb {Z}_p^{m \times k(k+1)m},\;\; \mathbf{A} :=\overbrace{ \begin{pmatrix} \tilde{\mathbf{A}}&{}&{}&{} \\ &{}\tilde{\mathbf{A}}&{}&{}\\ &{}&{}\ddots &{}\\ &{}&{}&{}\tilde{\mathbf{A}} \end{pmatrix} }^{km\text { matrices}} \in \mathbb {Z}_p^{k(k+1)m \times k^{2}m}, \\&\mathsf{pk}:=(\mathbb {G}_{\mathsf {CG}}, [\tilde{\mathbf{A}}], [\mathbf{W}\mathbf{A}]), \;\; \mathsf{msk}:=\mathbf{W}. \nonumber \end{aligned}$$

  (4.1)

• $\mathsf{Enc}(\mathsf{pk}, \mathbf{x})$: It takes $\mathsf{pk}$ and $\mathbf{x} \in \mathbb {Z}^{m}$ and outputs a ciphertext $\mathsf{ct}$ as follows.

  $$\begin{aligned} \mathbf{s} \xleftarrow {\mathsf{U}}\mathbb {Z}_p^{k^{2}m},\;\; \mathbf{c}_{1} :=\mathbf{A}\mathbf{s} \in \mathbb {Z}_p^{k(k+1)m},\;\; \mathbf{c}_{2} :=\mathbf{W}\mathbf{A}\mathbf{s} + \mathbf{x} \in \mathbb {Z}_p^{m}, \;\; \mathsf{ct}:=([\mathbf{c}_{1}], [\mathbf{c}_{2}]). \end{aligned}$$

• $\mathsf{KeyGen}(\mathsf{pk}, \mathsf{msk}, \mathbf{y})$: It takes $\mathsf{pp}$, $\mathsf{msk}$, and $\mathbf{y} \in \mathbb {Z}^{m}$ and outputs a secret key $\mathsf{sk}$ as follows.

  $$\begin{aligned} \mathbf{k}_{1} :=-\mathbf{W}^{\top }\mathbf{y} \in \mathbb {Z}_p^{k(k+1)m}, \;\; \mathbf{k}_{2} :=\mathbf{y} \in \mathbb {Z}_p^{m},\;\; \mathsf{sk}:=(\mathbf{k}_{1}, \mathbf{k}_{2}). \end{aligned}$$

• $\mathsf{Dec}(\mathsf{pk}, \mathsf{ct}, \mathsf{sk})$: It takes $\mathsf{pk}$, $\mathsf{ct}$, and $\mathsf{sk}$. Then it computes $[d] :=[\mathbf{k}_{1}^{\top }\mathbf{c}_{1} + \mathbf{k}_{2}^{\top }\mathbf{c}_{2}]$ and searches for d exhaustively in the range of $-mX_{\lambda }Y_{\lambda }$ to $mX_{\lambda }Y_{\lambda }$. If such d is found, it outputs d. Otherwise, it outputs $\bot$.

Correctness. Observe that if $\mathsf{ct}$ is an encryption of $\mathbf{x}$ and $\mathsf{sk}$ is a secret key of $\mathbf{y}$,

$$d = -\mathbf{y}^{\top }\mathbf{W}\mathbf{A}\mathbf{s} + \mathbf{y}^{\top }\mathbf{W}\mathbf{A}\mathbf{s} + \mathbf{y}^{\top }\mathbf{x} = \langle \mathbf{x}, \mathbf{y} \rangle .$$

Therefore, if $||\mathbf{x}||_{\infty } \le X_{\lambda }$ and $||\mathbf{y}||_{\infty } \le Y_{\lambda }$, the output of the decryption algorithm is $d = \langle \mathbf{x}, \mathbf{y} \rangle$.

4.2 Security

Theorem 4.1

Assume that the $\mathcal {D}_{k}$-MDDH assumption holds with respect to $\mathcal {G}_{\mathsf {CG}}$, then our Pub-IPFE scheme is adaptively secure in the multi-user and multi-challenge setting. More formally, let $\mu$ be a number of users, $q_{\mathsf{ct}} :=\sum _{i \in [\mu ]} q_{\mathsf{ct},i}$ be the total number of the ciphertext queries by $\mathcal {A}$, $q_{\mathsf{sk}} :=\sum _{i \in [\mu ]} q_{\mathsf{sk},i}$ be the total number of the secret key queries by $\mathcal {A}$, and m be a vector length. Then, for any PPT adversary $\mathcal {A}$ and security parameter $\lambda$, there exist PPT adversaries $\mathcal {B}_{1}$ and $\mathcal {B}_{2}$ for the $\mathcal {D}_{k}$-MDDH and we have

$$\begin{aligned}&\mathsf{Adv}_{\mathcal {A}}^{\mathsf {Pub\text {-}IPFE}}(\lambda ) \le 2\mathsf{Adv}_{\mathcal {B}_{1},\mathsf {CG}}^{\mathsf {\mathcal {D}_{k}\text {-}MDDH}}(\lambda ) + 2\mathsf{Adv}_{\mathcal {B}_{2},\mathsf {CG}}^{\mathsf {\mathcal {D}_{k}\text {-}MDDH}}(\lambda ) + 2^{-\varOmega (\lambda )},\\&\max \{\mathsf {Time}(\mathcal {B}_{1}), \mathsf {Time}(\mathcal {B}_{2})\} \approx \mathsf {Time}(\mathcal {A}) + (\mu + q_{\mathsf{ct}} +q_{\mathsf{sk}})\mathsf {poly}(\lambda , m), \end{aligned}$$

where $\mathsf {poly}(\lambda , m)$ is independent from $\mathsf {Time}(\mathcal {A})$.

Proof

We employ a series of games and evaluate the advantage of the adversary in each game. In the overveiw, we used the variable i to denote the index of users and $j_{i}$ (resp. $\ell _{i}$) to denote the index of ciphertext (resp. secret key) queries for user i. For example, a vector $\mathbf{s}$ in $j_{i}$-th ciphertext for user i will be denoted by $\mathbf{s}_{i, j_{i}}$. In the security proof, however, we change the forms of ciphertexts and secret keys for every user in the same way simultaneously. Thus, we do not need to specify users when we consider adversary’s queries. For conciseness, we omit the index i from $(i, j_{i})$ and $(i, \ell _{i})$, and just use j and $\ell$ to denote the indices of queries (but j and $\ell$ are implicitly associated with i).

• Game 0: This game is the same as the real game. Then, for all $j \in [q_{\mathsf{ct}, i}]$, the j-th ciphertext that $\mathcal {A}$ obtains from the oracle corresponds to

  $$\begin{aligned} \mathbf{s}_{j} \xleftarrow {\mathsf{U}}\mathbb {Z}_p^{k^{2}m},\;\; \mathbf{c}_{j,1} :=\mathbf{A}\mathbf{s}_{j},\;\; \mathbf{c}_{j,2} :=\mathbf{W}_{i}\mathbf{A}\mathbf{s}_{j} + \mathbf{x}_{j}^{\beta }. \end{aligned}$$

• Game 1: The reply for ciphertext queries is changed as follows. For $j \in [q_{\mathsf{ct}, i}]$, we define $\mathbf{x}_{j} :=\mathbf{x}^{1}_{j} - \mathbf{x}^{0}_{j} \in \mathbb {Z}_p^{m}$. Let $\phi _{i}:[q_{\mathsf{ct},i}] \rightarrow [m]$ be a map such that $\phi _{i}(j):=\mathsf {rank}(\mathbf{x}_{1}|| \cdots ||\mathbf{x}_{j})$. Then, for all $j \in [q_{\mathsf{ct}, i}]$, the j-th ciphertext that $\mathcal {A}$ obtains from the oracle corresponds to

  $$\begin{aligned}&\mathbf{b} \xleftarrow {\mathsf{U}}\mathbb {Z}_p^{k+1}\backslash \mathsf {span}(\tilde{\mathbf{A}}), \;\; \mathbf{B} :=\overbrace{ \begin{pmatrix} \mathbf{b}&{}&{}&{} \\ &{}\mathbf{b}&{}&{}\\ &{}&{}\ddots &{}\\ &{}&{}&{}\mathbf{b} \end{pmatrix} }^{km\text { vectors}} \in \mathbb {Z}_p^{k(k+1)m \times km}, \\&\tilde{\mathbf{s}}_{j,1} , \ldots ,\tilde{\mathbf{s}}_{j, \phi _{i}(j)} \xleftarrow {\mathsf{U}}\mathbb {Z}_p^{k},\;\; \mathbf{s}'_{j} :=(\tilde{\mathbf{s}}_{j,1} , \ldots ,\tilde{\mathbf{s}}_{j,\phi _{i}(j)}, 0^{k(m-\phi _{i}(j))}) \in \mathbb {Z}_p^{km},\nonumber \\&\mathbf{c}_{j,1} :=\mathbf{A}\mathbf{s}_{j}+\boxed {\mathbf{B}\mathbf{s}'_{j}},\;\; \mathbf{c}_{j,2} :=\mathbf{W}_{i}(\mathbf{A}\mathbf{s}_{j}+\boxed {\mathbf{B}\mathbf{s}'_{j}}) + \mathbf{x}_{j}^{\beta }. \nonumber \end{aligned}$$

  (4.2)

• Game 2: The reply for ciphertext queries is changed as follows. Let $\rho _{i}: [\phi _{i}(q_{\mathsf{ct},i})] \rightarrow [q_{\mathsf{ct},i}]$ be a map such that $\rho _{i}(\iota ) :=\min \phi _{i}^{-1}(\iota )$. In other words, on an input $\iota$, $\rho _{i}$ returns the first query number j such that the rank of the matrix $(\mathbf{x}_{1}|| \cdots ||\mathbf{x}_{j})$ equals $\iota$. Then, for all $j \in [q_{\mathsf{ct}, i}]$, the j-th ciphertext that $\mathcal {A}$ obtains from the oracle corresponds to

  

  Note that $\tilde{\mathbf{s}}_{j,\iota }$ is defined in Game 1.

• Game 3: The reply for ciphertext queries is changed as follows. For all $j \in [q_{\mathsf{ct}, i}]$, the j-th ciphertext that $\mathcal {A}$ obtains from the oracle corresponds to

  

• Game 4: The reply for ciphertext queries is changed as follows. For all $j \in [q_{\mathsf{ct}, i}]$, the j-th ciphertext that $\mathcal {A}$ obtains from the oracle corresponds to

  $$\begin{aligned}&r_{j,1} , \ldots ,r_{j, \phi _{i}(j)} \xleftarrow {\mathsf{U}}\mathbb {Z}_p,\\&\mathbf{c}_{j,1} :=\mathbf{A}\mathbf{s}_{j}+\mathbf{B}\mathbf{s}'_{j},\;\; \mathbf{c}_{j,2} :=\mathbf{W}_{i}(\mathbf{A}\mathbf{s}_{j}+\mathbf{B}\mathbf{s}'_{j}) + \boxed {\mathbf{x}_{j}^{0}}+ \sum _{\iota \in [\phi _{i}(j)]}r_{j, \iota }\mathbf{x}_{\rho _{i}(\iota )}. \end{aligned}$$

We present proofs of the indistinguishability among these games in the full version of this paper.    $\square$

4.3 Application to Multi-input Inner Product Functional Encryption

We can obtain an adaptively secure MIPFE scheme whose security is tightly reduced to the $\mathcal {D}_{k}$ - MDDH assumption by applying the generic conversion by Abdalla et al. [3] to our scheme. Let Pub-IPFE be a Pub-IPFE scheme that is adaptively secure in the multi-user and multi-challenge setting. It is not difficult to see that the security of the MIPFE scheme obtained by applying the conversion to Pub-IPFE is reduced to that of Pub-IPFE with the security loss being 1. Thus, we obtain the following corollary.

Corollary 4.1

Let $\textsf {MIPFE}$ be the MIPFE scheme obtained by applying the conversion in [3] to our Pub-IPFE scheme. Then $\textsf {MIPFE}$ is adaptively secure. More formally, let $\mu$ be a number of slots, $q_{\mathsf{ct}} :=\sum _{i \in [\mu ]} q_{\mathsf{ct},i}$ be the total number of the ciphertext queries by $\mathcal {A}$, $q_{\mathsf{sk}}$ be the total number of the secret key queries by $\mathcal {A}$, and m be a vector length. Then, for any PPT adversary $\mathcal {A}$ and security parameter $\lambda$, there exist PPT adversaries $\mathcal {B}_{1}$ and $\mathcal {B}_{2}$ for the $\mathcal {D}_{k}$-MDDH and we have

$$\begin{aligned}&\mathsf{Adv}_{\mathcal {A}, \mathsf {ad}}^{\mathsf {MIPFE}}(\lambda ) \le 2\mathsf{Adv}_{\mathcal {B}_{1}}^{\mathsf {\mathcal {D}_{k}\text {-}MDDH}}(\lambda ) + 2\mathsf{Adv}_{\mathcal {B}_{2}}^{\mathsf {\mathcal {D}_{k}\text {-}MDDH}}(\lambda ) + 2^{-\varOmega (\lambda )},\\&\max \{\mathsf {Time}(\mathcal {B}_{1}), \mathsf {Time}(\mathcal {B}_{2})\} \approx \mathsf {Time}(\mathcal {A}) + ( \mu +q_{\mathsf{ct}} + \mu q_{\mathsf{sk}})\mathsf {poly}(\lambda , m), \end{aligned}$$

where $\mathsf {poly}(\lambda , m)$ is independent from $\mathsf {Time}(\mathcal {A})$.

5 Function-Hiding Inner Product Functional Encryption

Lin proposed a simple framework that allows us to construct a function-hiding IPFE scheme from a public key IPFE scheme [34]. We can apply her framework to our scheme and obtain a tightly function-hiding IPFE scheme in the multi-user setting. Informally, her framework is as follows.

First, we can see that a ciphertext and a secret key in our IPFE scheme consist of vectors, and decryption involves inner product of these vectors. That is, a ciphertext of a vector $\mathbf{x}$ corresponds to a vector $\mathbf{c}_{\mathsf {in}} :=(\mathbf{c}_{\mathsf {in}, 1}, \mathbf{c}_{\mathsf {in}, 2}) :=(\mathbf{A}\mathbf{s}, \mathbf{W}\mathbf{A}\mathbf{s} + \mathbf{x}) \in \mathbb {Z}_p^{(k^{2}+k+1)m}$ and a secret key of a vector $\mathbf{y}$ corresponds to a vector $\mathbf{k}_{\mathsf {in}} :=(\mathbf{k}_{\mathsf {in}, 1}, \mathbf{k}_{\mathsf {in}, 2}) :=(-\mathbf{W}^{\top }\mathbf{y}, \mathbf{y}) \in \mathbb {Z}_p^{(k^{2}+k+1)m}$. Decryption just computes $\langle \mathbf{c}_{\mathsf {in}}, \mathbf{k}_{\mathsf {in}} \rangle$. We call the scheme described above an inner scheme.

To ensure the confidentiality of secret keys, we “encrypt” secret keys in the same way as ciphertexts in our IPFE scheme. That is, a secret key of the function-hiding IPFE scheme is generated as $\mathsf{sk}:=(\mathbf{c}_{\mathsf {out},1}, \mathbf{c}_{\mathsf {out},2}) :=\left( \mathbf{D}\mathbf{r} \in \mathbb {Z}_p^{k(k+1)(k^{2}+k+1)m}, \mathbf{V}\mathbf{D}\mathbf{r}+\mathbf{k}_{\mathsf {in}} \in \mathbb {Z}_p^{(k^{2}+k+1)m}\right)$, where $\mathbf{V}$, $\mathbf{D}$, and $\mathbf{r}$ correspond to $\mathbf{W}$, $\mathbf{A}$, and $\mathbf{s}$ respectively in our scheme presented in Sect. 4.1. We call the scheme utilized to encrypt secret keys an outer scheme. We also need to transform ciphertexts to make them compatible with $\mathsf{sk}$, which can be done by “generating a secret key” of $\mathbf{c}_{\mathsf {in}}$ in the outer scheme. That is, we define a ciphertext of the function-hiding IPFE scheme as $\mathsf{ct}:=(\mathbf{k}_{\mathsf {out},1}, \mathbf{k}_{\mathsf {out},2}):=\left( -\mathbf{V}^{\top }\mathbf{c}_{\mathsf {in}}\in \mathbb {Z}_p^{k(k+1)(k^{2}+k+1)m}, \mathbf{c}_{\mathsf {in}}\in \mathbb {Z}_p^{(k^{2}+k+1)m}\right)$. Observe that $\langle \mathsf{ct}, \mathsf{sk} \rangle = \langle \mathbf{c}_{\mathsf {in}}, \mathbf{k}_{\mathsf {in}} \rangle = \langle \mathbf{x}, \mathbf{y} \rangle$.

To achieve the security, of course we need to encode both $\mathsf{ct}$ and $\mathsf{sk}$ on the exponent of group elements. We employ bilinear groups that allow us to compute inner product over the group elements, which is necessary for decryption. Then, the confidentiality of ciphertexts is assured by the inner scheme and that of secret keys is assured by the outer scheme.

5.1 Actual Scheme and Optimization

As described above, if we directly apply Lin’s framework to our scheme, the first components of a ciphertext and a secret key will consist of $k(k+1)(k^{2}+k+1)m$ group elements. Recall the reason we need $k(k+1)m$ group elements in the first components of a ciphertext and a secret key in the original scheme. That is, the maximum dimension of the space spanned by the vectors $\mathbf{x}_{j} = \mathbf{x}^{1}_{j} - \mathbf{x}^{0}_{j}$ is m, and this fact directly affects the number of group elements in the first components. Because the vector length handled in the outer scheme is $(k^{2}+k+1)m$, the first components seem to require $k(k+1)(k^{2}+k+1)m$ group elements. However, observe that the maximum dimension of the space spanned by the vectors $\mathbf{k}_{\mathsf {out}, \ell } :=\mathbf{k}^{1}_{\mathsf {out}, \ell } - \mathbf{k}^{0}_{\mathsf {out}, \ell } :=(-\mathbf{W}^{\top }\mathbf{y}_{\ell }^{1}, \mathbf{y}_{\ell }^{1}) -(-\mathbf{W}^{\top }\mathbf{y}_{\ell }^{0}, \mathbf{y}_{\ell }^{0})$ for all $\ell \in [q_{\mathsf{sk}}]$ is m, not $(k^{2}+k+1)m$. Hence, we can reduce the number of group elements in the first components to $k(k+1)m$, and the resulting scheme is given as follows.

Let $\mathcal {D}_{k}$ be a matrix distribution over full rank matrices in $\mathbb {Z}_p^{(k+1) \times k}$ and norm bounds $X_{\lambda }$ and $Y_{\lambda }$ be polynomials in $\lambda$.

• $\mathsf{Par}(1^{\lambda })$: It takes a security parameter $1^\lambda$ and outputs $\mathsf{pp}$ as follows.

  $$\begin{aligned} \mathbb {G}_{\mathsf {BG}} \leftarrow \mathcal {G}_\mathsf{BG}(1^\lambda ),\;\; \tilde{\mathbf{A}}, \tilde{\mathbf{D}} \leftarrow \mathcal {D}_{k}, \;\; \mathsf{pp}:=(\mathbb {G}_{\mathsf {BG}}, [\tilde{\mathbf{A}}]_{1}, [\tilde{\mathbf{D}}]_{2}). \end{aligned}$$

• $\mathsf{Setup}(1^{m}, \mathsf{pp})$: It takes a vector length $1^{m}$ and a public parameter $\mathsf{pp}$. Then, it outputs a master secret key $\mathsf{msk}$ as follows.

  $$\begin{aligned} \mathbf{W} \xleftarrow {\mathsf{U}}\mathbb {Z}_p^{m \times k(k+1)m},\;\; \mathbf{V} \xleftarrow {\mathsf{U}}\mathbb {Z}_p^{(k^{2}+k+1)m \times k(k+1)m},\;\;\mathsf{msk}:=(\mathbf{W}, \mathbf{V}). \end{aligned}$$

• $\mathsf{Enc}(\mathsf{pp}, \mathsf{msk}, \mathbf{x})$: It takes $\mathsf{pp}$, $\mathsf{msk}$, and $\mathbf{x} \in \mathbb {Z}^{m}$ and outputs a ciphertext $\mathsf{ct}$ as follows.

  $$\begin{aligned}&\mathbf{A} :=\overbrace{ \begin{pmatrix} \tilde{\mathbf{A}}&{}&{}&{} \\ &{}\tilde{\mathbf{A}}&{}&{}\\ &{}&{}\ddots &{}\\ &{}&{}&{}\tilde{\mathbf{A}} \end{pmatrix} }^{km\text { matrices}} \in \mathbb {Z}_p^{k(k+1)m \times k^{2}m},\\&\mathbf{s} \xleftarrow {\mathsf{U}}\mathbb {Z}_p^{k^{2}m},\;\; \mathbf{c}_{\mathsf {in}} :=(\mathbf{A}\mathbf{s}, \mathbf{W}\mathbf{A}\mathbf{s} + \mathbf{x}) \in \mathbb {Z}_p^{(k^{2}+k+1)m},\\&\mathbf{k}_{\mathsf {out},1}:=-\mathbf{V}^{\top }\mathbf{c}_{\mathsf {in}} \in \mathbb {Z}_p^{k(k+1)m},\;\;\mathbf{k}_{\mathsf {out},2} :=\mathbf{c}_{\mathsf {in}},\;\; \mathsf{ct}:=([\mathbf{k}_{\mathsf {out},1}]_{1}, [\mathbf{k}_{\mathsf {out},2}]_{1}). \end{aligned}$$

• $\mathsf{KeyGen}(\mathsf{pp}, \mathsf{msk}, \mathbf{y})$: It takes $\mathsf{pp}$, $\mathsf{msk}$, and $\mathbf{y} \in \mathbb {Z}^{m}$ and outputs a secret key $\mathsf{sk}$ as follows.

  $$\begin{aligned}&\mathbf{D} :=\overbrace{ \begin{pmatrix} \tilde{\mathbf{D}}&{}&{}&{} \\ &{}\tilde{\mathbf{D}}&{}&{}\\ &{}&{}\ddots &{}\\ &{}&{}&{}\tilde{\mathbf{D}} \end{pmatrix} }^{km\text { matrices}} \in \mathbb {Z}_p^{k(k+1)m \times k^{2}m},\\&\mathbf{r} \xleftarrow {\mathsf{U}}\mathbb {Z}_p^{k^{2}m},\;\; \mathbf{k}_{\mathsf {in}} :=(-\mathbf{W}^{\top }\mathbf{y}, \mathbf{y}) \in \mathbb {Z}_p^{(k^{2}+k+1)m},\\&\mathbf{c}_{\mathsf {out},1}:=\mathbf{D}\mathbf{r} \in \mathbb {Z}_p^{k(k+1)m}, \;\; \mathbf{c}_{\mathsf {out},2} :=\mathbf{V}\mathbf{D}\mathbf{r} + \mathbf{k}_{\mathsf {in}} \in \mathbb {Z}_p^{(k^{2}+k+1)m},\\&\mathsf{sk}:=([\mathbf{c}_{\mathsf {out}, 1}]_{2}, [\mathbf{c}_{\mathsf {out}, 2}]_{2}). \end{aligned}$$

• $\mathsf{Dec}(\mathsf{pp}, \mathsf{ct}, \mathsf{sk})$: It takes $\mathsf{pp}$, $\mathsf{ct}$, and $\mathsf{sk}$. Then it computes $[d]_{T} :=e([\mathbf{k}_{\mathsf {out}, 1}]_{1},[\mathbf{c}_{\mathsf {out}, 1}]_{2})e([\mathbf{k}_{\mathsf {out}, 2}]_{1},[\mathbf{c}_{\mathsf {out},2}]_{2})$ and searches for d exhaustively in the range of $-mX_{\lambda }Y_{\lambda }$ to $mX_{\lambda }Y_{\lambda }$. If such d is found, it outputs d. Otherwise, it outputs $\bot$.

Correctness. Observe that if $\mathsf{ct}$ is an encryption of $\mathbf{x}$ and $\mathsf{sk}$ is a secret key of $\mathbf{y}$,

$$d = -\mathbf{c}_{\mathsf {in}}^{\top }\mathbf{V}\mathbf{D}\mathbf{r} + \mathbf{c}_{\mathsf {in}}^{\top }\mathbf{V}\mathbf{D}\mathbf{r} + \mathbf{c}_{\mathsf {in}}^{\top }\mathbf{k}_{\mathsf {in}}= \langle \mathbf{c}_{\mathsf {in}}, \mathbf{k}_{\mathsf {in}} \rangle = \langle \mathbf{x}, \mathbf{y} \rangle .$$

Therefore, if $||\mathbf{x}||_{\infty } \le X_{\lambda }$ and $||\mathbf{y}||_{\infty } \le Y_{\lambda }$, the output of the decryption algorithm is $d = \langle \mathbf{x}, \mathbf{y} \rangle$.

5.2 Security

Theorem 5.1

Assume that the $\mathcal {D}_{k}$-MDDH assumption holds with respect to $\mathcal {G}_{\mathsf {BG}}$, then our Priv-IPFE scheme is weakly function-hiding in the multi-user setting. More formally, let $\mu$ be a number of users, $q_{\mathsf{ct}} :=\sum _{i \in [\mu ]} q_{\mathsf{ct},i}$ be the total number of the ciphertext queries by $\mathcal {A}$, $q_{\mathsf{sk}} :=\sum _{i \in [\mu ]} q_{\mathsf{sk},i}$ be the total number of the secret key queries by $\mathcal {A}$, and m be a vector length. Then, for any PPT adversary $\mathcal {A}$ and security parameter $\lambda$, there exist PPT adversaries $\mathcal {B}_{1} , \ldots ,\mathcal {B}_{4}$ for the $\mathcal {D}_{k}$-MDDH, and we have

$$\begin{aligned}&\mathsf{Adv}_{\mathcal {A}, \mathsf {w \text {-}fh}}^{\mathsf {Priv\text {-}IPFE}}(\lambda ) \le 2\sum _{\iota \in \{1,2\}}\mathsf{Adv}_{\mathcal {B}_{\iota },\mathsf {BG},1}^{\mathsf {\mathcal {D}_{k}\text {-}MDDH}}(\lambda ) +2\sum _{\iota \in \{3,4\}}\mathsf{Adv}_{\mathcal {B}_{\iota },\mathsf {BG},2}^{\mathsf {\mathcal {D}_{k}\text {-}MDDH}}(\lambda ) + 2^{-\varOmega (\lambda )},\\&\max _{\iota \in [4]} \{\mathsf {Time}(\mathcal {B}_{\iota })\} \approx \mathsf {Time}(\mathcal {A}) + (\mu + q_{\mathsf{ct}} +q_{\mathsf{sk}})\mathsf {poly}(\lambda , m), \end{aligned}$$

where $\mathsf {poly}(\lambda , m)$ is independent from $\mathsf {Time}(\mathcal {A})$.

Theorem 5.1 follows from Theorem 4.1 and Lin’s observation [34]. That is, the following relations hold:

$$\begin{aligned} \left\{ \{\mathsf{ct}^{0}_{j} \}_{ j \in [q_{\mathsf{ct}, i}]}, \{\mathsf{sk}^{0}_{\ell } \}_{\ell \in [q_{\mathsf{sk}, i}]} \right\} _{i \in [\mu ] }&\approx _{c} \left\{ \{\mathsf{ct}^{1}_{j} \}_{ j \in [q_{\mathsf{ct}, i}]}, \{\mathsf{sk}^{0}_{\ell } \}_{\ell \in [q_{\mathsf{sk}, i}]} \right\} _{i \in [\mu ] } \\&\approx _{c} \left\{ \{\mathsf{ct}^{1}_{j} \}_{ j \in [q_{\mathsf{ct}, i}]}, \{\mathsf{sk}^{1}_{\ell } \}_{\ell \in [q_{\mathsf{sk}, i}]} \right\} _{i \in [\mu ] }. \end{aligned}$$

The first indistinguishability follows from the security of the inner scheme and Eq. (3.3), and the second indistinguishability follows from the security of the outer scheme and Eq. (3.3). More precisely, we use the relations $\langle \mathbf{x}^{0}_{i, j_{i}}, \mathbf{y}^{0}_{i, \ell _{i}} \rangle = \langle \mathbf{x}^{1}_{i, j_{i}}, \mathbf{y}^{0}_{i, \ell _{i}} \rangle$ for the inner scheme and $\langle \mathbf{c}^{1}_{\mathsf {in}, i, j_{i}}, \mathbf{k}^{0}_{\mathsf {in}, i, \ell _{i}} \rangle = \langle \mathbf{c}^{1}_{\mathsf {in}, i, j_{i}}, \mathbf{k}^{1}_{\mathsf {in}, i, \ell _{i}} \rangle$ for the outer scheme. Both relations can be derived from Eq. (3.3). Note that because our scheme is adaptively secure, the above relations hold even if ciphertexts and secret keys are queried by an adversary adaptively.

Remark 5.1

Although the above scheme is weakly function-hiding in the multi-user setting, we can easily convert it into one that is fully function-hiding in the multi-user setting by the conversion proposed by Lin and Vaikuntanathan [35]. The conversion is very simple and works by only doubling vector lengths. When encrypting $\mathbf{x} \in \mathbb {Z}^{m}$, we just encrypt $(\mathbf{x}, 0^{m})$ in the original scheme. Key generation is also done in the same way. In addition, this conversion is tight. That is, for any PPT adversary $\mathcal {A}$ and security parameter $\lambda$, there exist PPT adversaries $\mathcal {B}_{1},\mathcal {B}_{2},\mathcal {B}_{3}$ and we have

$$\begin{aligned}&\mathsf{Adv}_{\mathcal {A}, \mathsf {f \text {-}fh}}^{\mathsf {Priv\text {-}IPFE}}(\lambda ) \le \sum _{\iota \in [3]}\mathsf{Adv}_{\mathcal {B}_{\iota }, \mathsf {w \text {-}fh}}^{\mathsf {Priv\text {-}IPFE}}(\lambda ),\\&\max _{\iota \in [3]} \{\mathsf {Time}(\mathcal {B}_{\iota })\} \approx \mathsf {Time}(\mathcal {A}) + (\mu + q_{\mathsf{ct}} +q_{\mathsf{sk}})\mathsf {poly}(\lambda , m), \end{aligned}$$

where $\mathsf {poly}(\lambda , m)$ is independent from $\mathsf {Time}(\mathcal {A})$.

6 From Single to Multi-input Function-Hiding Inner Product Functional Encryption

In this section, we present a generic conversion from weakly function-hiding single-input IPFE to fully function-hiding multi-input IPFE. Because all known function-hiding single-input IPFE schemes are based on bilinear groups, we design the conversion to be compatible with group based schemes. As in [3], however, we believe that our conversion is so generic that we can easily modify it to be suitable to schemes based on other primitives.

6.1 Conversion

Property. Let $\mathsf {Priv\text {-}IPFE} :=(\mathsf{Par}, \mathsf{Setup}, \mathsf{Enc}, \mathsf{KeyGen}, \mathsf{Dec})$ be a Priv-IPFE scheme (Definition 3.6). In our conversion, we require that an underlying scheme has the following properties.

• 1. $\mathsf {Priv\text {-}IPFE}$ is weakly function-hiding in the multi-user setting.

• 2. A public parameter $\mathsf{pp}$ defines an order n, a group G of order n with group law $\circ$, and an encoding function $E:\mathbb {Z}_{n}\rightarrow G$.

• 3. A decryption algorithm $\mathsf{Dec}$ can be divided into the two algorithms $\mathsf{Dec}_{1}$ and $\mathsf{Dec}_{2}$ with the following properties. For any $\lambda , m \in \mathbb {N}$, any $\mathbf{x}, \mathbf{y} \in \mathbb {Z}^{m}$, and any $z \in \mathbb {Z}_{n}$ such that $|z| \le mX_{\lambda }Y_{\lambda }$, we have

  $$\begin{aligned}&\mathsf{Pr}\left[ d = E(\langle \mathbf{x}, \mathbf{y} \rangle \!\!\!\mod n) \; \begin{array}{|l} \;\mathsf{pp}\leftarrow \mathsf{Par}(1^{\lambda })\\ \;\mathsf{msk}\leftarrow \mathsf{Setup}(1^{m}, \mathsf{pp})\\ \;\mathsf{ct}\leftarrow \mathsf{Enc}(\mathsf{pp}, \mathsf{msk}, \mathbf{x})\\ \;\mathsf{sk}\leftarrow \mathsf{KeyGen}(\mathsf{pp}, \mathsf{msk}, \mathbf{y})\\ \; d:=\mathsf{Dec}_{1}(\mathsf{pp}, \mathsf{ct}, \mathsf{sk}) \end{array} \right] =1, \\&\mathsf{Dec}_{2}(\mathsf{pp}, E(z)) = z. \end{aligned}$$

• 4. For any $a, b \in \mathbb {Z}_{n}$, we have $E(a)\circ E(b) = E(a+b)$.

Conversion. Let $\mathsf {Priv\text {-}IPFE}\! :=\!\left( \mathsf{Par}', \mathsf{Setup}',\mathsf{Enc}', \mathsf{KeyGen}',\mathsf{Dec}'\! :=\! (\mathsf{Dec}'_{1}, \mathsf{Dec}'_{2}) \right)$ be a Priv-IPFE scheme with the property defined above. Let $\mathsf {MIPFE} :=(\mathsf{Setup}, \mathsf{Enc}, \mathsf{KeyGen}, \mathsf{Dec})$ be a converted MIPFE scheme. Let $X_{\lambda } :=X'_{\lambda }/\mu$ be a norm bound of $\mathsf {MIPFE}$, where $X'_{\lambda }$ is a norm bound of $\mathsf {Priv\text {-}IPFE}$. Our conversion is performed as follows.

• $\mathsf{Setup}(1^{\lambda }, 1^{m}, 1^{\mu })$: It takes a security parameter $1^{\lambda }$, a vector length $1^{m}$, and a number of slots $1^{\mu }$. Then, it outputs a public parameter $\mathsf{pp}$ and a master secret key $\mathsf{msk}$ as follows.

  $$\begin{aligned}&\mathsf{pp}' \leftarrow \mathsf{Par}'(1^{\lambda }), \;\; \{ \mathsf{msk}'_{i} \}_{i \in [\mu ]} \leftarrow \mathsf{Setup}'(1^{2m+1}, \mathsf{pp}'),\;\; \{\mathbf{u}_{i} \}_{i \in [\mu ]} \xleftarrow {\mathsf{U}}\mathbb {Z}_{n}^{m}, \\&\mathsf{pp}:=\mathsf{pp}',\;\;\mathsf{msk}:=(\{ \mathsf{msk}'_{i} \}_{i \in [\mu ]}, \{\mathbf{u}_{i} \}_{i \in [\mu ]}). \end{aligned}$$

• $\mathsf{Enc}(\mathsf{pp}, \mathsf{msk}, i, \mathbf{x})$: It takes $\mathsf{pp}$, $\mathsf{msk}$, $i \in [\mu ]$ and $\mathbf{x} \in \mathbb {Z}^{m}$ and outputs a ciphertext $\mathsf{ct}_{i}$ as follows.

  $$\begin{aligned} \tilde{\mathbf{x}} :=(\mathbf{x}+\mathbf{u}_{i}, 0^{m}, 1 ) \in \mathbb {Z}_{n}^{2m+1}, \;\; \mathsf{ct}_{i}' \leftarrow \mathsf{Enc}'(\mathsf{pp}', \mathsf{msk}'_{i}, \tilde{\mathbf{x}}),\;\; \mathsf{ct}_{i} :=\mathsf{ct}'_{i}. \end{aligned}$$

• $\mathsf{KeyGen}(\mathsf{pp}, \mathsf{msk}, \{\mathbf{y}_{i} \}_{i \in [\mu ]})$: It takes $\mathsf{pp}$, $\mathsf{msk}$, and $\{\mathbf{y}_{i} \}_{i \in [\mu ]}\in \mathbb {Z}^{m}$ and outputs a secret key $\mathsf{sk}$ as follows.

  $$\begin{aligned}&\{r_{i} \}_{i \in [\mu -1]} \xleftarrow {\mathsf{U}}\mathbb {Z}_{n}, \;\; r_{\mu } :=- \left( \sum _{i \in [\mu -1]} r_{i} + \sum _{i \in [\mu ]} \langle \mathbf{y}_{i}, \mathbf{u}_{i} \rangle \right) \in \mathbb {Z}_{n}, \\&\tilde{\mathbf{y}}_{i} :=(\mathbf{y}_{i}, 0^{m}, r_{i}) \in \mathbb {Z}_{n}^{2m+1},\;\;\mathsf{sk}'_{i} \leftarrow \mathsf{KeyGen}'(\mathsf{pp}', \mathsf{msk}'_{i}, \tilde{\mathbf{y}}_{i})\;\;\text {for all }i \in [\mu ],\\&\mathsf{sk}:=\{\mathsf{sk}'_{i}\}_{i \in [\mu ]}. \end{aligned}$$

• $\mathsf{Dec}(\mathsf{pp}, \{\mathsf{ct}_{i}\}_{i \in [\mu ]}, \mathsf{sk})$: It takes $\mathsf{pp}$, $\{\mathsf{ct}_{i}\}_{i \in [\mu ]}$, and $\mathsf{sk}$. Then, it computes decryption value d as follows.

  $$\begin{aligned} d_{i} :=\mathsf{Dec}'_{1}(\mathsf{pp}', \mathsf{ct}'_{i}, \mathsf{sk}'_{i}) \in \mathbb {G}\;\;\text {for all }i \in [\mu ],\;\; d :=\mathsf{Dec}'_{2}(\mathsf{pp}', d_{1} \circ \cdots \circ d_{\mu }). \end{aligned}$$

Correctness. From property 3, we have

$$d_{i} = E(\langle \mathbf{x}_{i}+\mathbf{u}_{i}, \mathbf{y}_{i} \rangle + r_{i} \!\! \mod n).$$

From property 4, we have

$$d_{1} \circ \cdots \circ d_{\mu } = E\left( \sum _{i \in [\mu ]} (\langle \mathbf{x}_{i}+\mathbf{u}_{i}, \mathbf{y}_{i} \rangle + r_{i}) \!\! \mod n \right) = E\left( \sum _{i \in [\mu ]} \langle \mathbf{x}_{i}, \mathbf{y}_{i} \rangle \!\! \mod n \right) .$$

Then, from property 3 and the correctness of $\mathsf {Priv\text {-}IPFE}$, we have $d :=\mathsf{Dec}'_{2}(d_{1} \circ \cdots \circ d_{\mu }) = \sum _{i \in [\mu ]} \langle \mathbf{x}_{i}, \mathbf{y}_{i} \rangle$.

Remark 6.1

Typically, we define Priv-IPFE as consisting of four algorithms $(\mathsf{Setup}, \mathsf{Enc}, \mathsf{KeyGen}, \mathsf{Dec})$ and $\mathsf{Setup}$ outputs $\mathsf{pp}$ and $\mathsf{msk}$ when we consider Priv-IPFE in the single-user setting. To apply our conversion to such a Priv-IPFE scheme, just setting $\mathsf{pp}:=\mathsf{pp}'_{1} , \ldots ,\mathsf{pp}'_{\mu }$ suffices in the setup algorithm. In the security proof, however, we need a hybrid argument for each slot similarly to [3]. Thus, the security reduction will not become tight.

6.2 Security

Theorem 6.1

Let Priv-IPFE be a Priv-IPFE scheme that satisfies the properties described above. Then converted scheme, MIPFE, is a fully function-hiding MIPFE scheme. More formally, let $\mu$ be a number of slots, $q_{\mathsf{ct}} :=\sum _{i \in [\mu ]} q_{\mathsf{ct},i}$ be the total number of the ciphertext queries by $\mathcal {A}$, $q_{\mathsf{sk}}$ be the total number of the secret key queries by $\mathcal {A}$, and m be a vector length. Then, for any PPT adversary $\mathcal {A}$ and security parameter $\lambda$, there exist PPT adversaries $\mathcal {B}_{1} , \mathcal {B}_{2}$ for Priv-IPFE and we have

$$\begin{aligned}&\mathsf{Adv}_{\mathcal {A}, \mathsf {f \text {-}fh}}^{\mathsf {MIPFE}}(\lambda ) \le 2 \sum _{\iota \in [2]}\mathsf{Adv}_{\mathcal {B}_{\iota }, \mathsf {w \text {-}fh}}^{\mathsf {Priv\text {-}IPFE}}(\lambda ),\\&\max _{\iota \in [2]}\{\mathsf {Time}(\mathcal {B}_{\iota })\} \approx \mathsf {Time}(\mathcal {A}) + (\mu + q_{\mathsf{ct}} + \mu q_{\mathsf{sk}})\mathsf {poly}(\lambda , m), \end{aligned}$$

where $\mathsf {poly}(\lambda , m)$ is independent from $\mathsf {Time}(\mathcal {A})$.

Proof

We employ a series of games and evaluate the advantage of the adversary in each game. For ease of exposition, we first consider six games: Games 0 to 5, and show that the each transition of games is justified by the security of the underlying scheme (or an information-theoretical argument). Then, we explain that the transition from Game 0 to 2 and that from Game 3 to 5 can be done in one-shot. We summarize forms of ciphertexts and secret keys in each game in Table 5. Similarly to in Sect. 4.2, we omit index i from index $j_{i}$ and just denote it by j. We present formal proof in the full version of this paper.    $\square$

Table 5. Overview of the game change.

6.3 Application to Our Scheme

Applying the conversion to our scheme presented in Sect. 5.1, we can obtain a tightly secure fully function-hiding MIPFE scheme. First, we confirm that our scheme satisfies the property presented in Sect. 6.1.

• 1. Theorem 5.1 says that our scheme is weakly function-hiding.

• 2. We can define that $n :=p$, $G :=G_{T}$, and $E:a \in \mathbb {Z}_p\rightarrow [a]_{T} \in G_{T}$. The group law $\circ$ corresponds to the multiplication over $G_{T}$.

• 3. We can define that $\mathsf{Dec}_{1}$ computes $[d]_{T}$ and $\mathsf{Dec}_{2}$ searches for the discrete logarithm of $[d]_{T}$.

• 4. It is obvious that $g_{T}^{a} \cdot g^{b}_{T} = g_{T}^{a+b}$.

Then, from Theorems 5.1 and 6.1, we obtain the following corollary.

Corollary 6.1

Let $\textsf {MIPFE}$ be the MIPFE scheme obtained by applying the conversion in Sect. 6.1 to our weakly function-hiding Priv-IPFE scheme. Then $\textsf {MIPFE}$ is fully function-hiding. More formally, let $\mu$ be a number of slots, $q_{\mathsf{ct}} :=\sum _{i \in [\mu ]} q_{\mathsf{ct},i}$ be the total number of the ciphertext queries by $\mathcal {A}$, $q_{\mathsf{sk}}$ be the total number of the secret key queries by $\mathcal {A}$, and m be a vector length. Then, for any PPT adversary $\mathcal {A}$ and security parameter $\lambda$, there exist PPT adversaries $\mathcal {B}_{1}, \ldots ,\mathcal {B}_{4}$ for the $\mathcal {D}_{k}$-MDDH and we have

$$\begin{aligned}&\mathsf{Adv}_{\mathcal {A}, \mathsf {f\text {-}fh}}^{\mathsf {MIPFE}}(\lambda ) \le 8\sum _{\iota \in \{1,2\}}\mathsf{Adv}_{\mathcal {B}_{\iota },\mathsf {BG},1}^{\mathsf {\mathcal {D}_{k}\text {-}MDDH}}(\lambda ) +8\sum _{\iota \in \{3,4\}}\mathsf{Adv}_{\mathcal {B}_{\iota },\mathsf {BG},2}^{\mathsf {\mathcal {D}_{k}\text {-}MDDH}}(\lambda ) + 2^{-\varOmega (\lambda )},\\&\max _{\iota \in [4]}\{\mathsf {Time}(\mathcal {B}_{\iota })\} \approx \mathsf {Time}(\mathcal {A}) + ( \mu +q_{\mathsf{ct}} + \mu q_{\mathsf{sk}})\mathsf {poly}(\lambda , m), \end{aligned}$$

where $\mathsf {poly}(\lambda , m)$ is independent from $\mathsf {Time}(\mathcal {A})$.