# Simulation Secure Multi-input Quadratic Functional Encryption

Ferran Alborch Escobar, Sébastien Canard, Fabien Laguillaumie

► To cite this version:

Ferran Alborch Escobar, Sébastien Canard, Fabien Laguillaumie. Simulation Secure Multi-input Quadratic Functional Encryption. SAC 2024 - 31st International Conference on Selected Areas in Cryptography, Aug 2024, Montréal, Canada. pp.26-53, 10.1007/978-3-031-82852-2_2. hal-04988251

HAL Id: hal-04988251

https://hal.science/hal-04988251v1

Submitted on 18 Mar 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
Simulation Secure Multi-Input Quadratic
Functional Encryption

Ferran Alborch Escobar$^{1,2,3*}$, Sébastien Canard$^2$, and Fabien Laguillaumie$^3\ddot{ }$

**Abstract.** Multi-input functional encryption is a primitive that allows for the evaluation of an $\ell$-ary function over multiple ciphertexts, without learning any information about the underlying plaintexts. This type of computation is useful in many cases where one has to compute over encrypted data, such as privacy-preserving cloud services, federated learning, or more generally delegation of computation from multiple clients. In this work we propose the first secret-key multi-input quadratic functional encryption scheme satisfying simulation security. On contrary, current constructions supporting quadratic functionalities, proposed by Agrawal et al. in CRYPTO '21 and TCC '22, only reach indistinguishability-based security. Our proposed construction is generic, and for a concrete instantiation, we propose a new function-hiding inner-product functional encryption scheme proven simulation secure against one challenge ciphertext in the standard model, which is of independent interest.

**Keywords:** Functional Encryption · Multi-input · Quadratic Functions

# 1 Introduction

Functional encryption is a generalization of public key encryption first formalized in [14,24], allowing for more control over the access on encrypted data. In general terms, this means that there is an authority capable to generate functional keys related to a function $f$. When combined with a ciphertext $c_x$ of a plaintext $x$ during the decryption process, $f(x)$ is recovered. The security guarantees that no other information about $x$ is leaked apart from $f_i(x)$ for all functions $f_i$ queried.

On the construction of functional encryption (FE) for some specific functionalities, [1] gave the first instantiation for inner product (IPFE) from standard assumptions. Soon a plethora of so called IPFE satisfying different security models or based on different assumptions appeared [8,12,15]. Another set of works, first introduced in [11], refer to quadratic functions (QFE), for which papers in [10,22,17] propose instantiations in the standard model. For higher degrees it is known that succinct degree-3 functional encryption implies indistinguishability obfuscation [23] as long as there exist pseudo-random generators of block-wise locality 3, but there are no known schemes based on polynomial assumptions.

<footnote n="1">¹ Applied Crypto Group, Orange Innovation, 14000 Caen, France</footnote>

<footnote n="2">² LTCI, Télécom Paris, Institut Polytechnique de Paris, 91120 Palaiseau, France</footnote>

<footnote n="3">³ LIRMM, Université de Montpellier, CNRS, 34095 Montpellier, France</footnote>
The security of functional encryption has been known to be delicate to define
from its initial formalization [14,24]. This is due to the difficulty to incorporate
the inherent leakage $f(x)$ into the security definition. There are two different ap-
proaches: *indistinguishability*-based security and *simulation*-based security. The
first one requires for the adversary to be unable to distinguish between two plain-
texts $x_0, x_1$ given a ciphertext of one of them and several functional keys $sk_{f_i}$.
However, for this definition to make sense, it is required that $f_i(x_0) = f_i(x_1)$ is
satisfied. This limits its applicability and makes it inadequate for some function-
alities [14]. The second one requires the scheme to be indistinguishable from a
simulator taking as inputs the inherent leakage from the scheme, in other words,
the information released to the adversary trough execution of the scheme like
the output. It is known that this definition is strictly stronger than indistin-
guishability based security, but also that there are some impossibility results
[14,24,5]. In either case, there are also two cases that could be treated. If the
adversary can only request functional keys after sending all the challenges, it is
called *selective*, while if the adversary has no restriction on when it can request
functional keys it is called *adaptive*. In this work we focus in selective simulation
security against one challenge ciphertext, and multiple functional keys, which
makes sense in many real-life applications, where several queries are asked to
one single database.

*Multi-input functional encryption.* Multi-input functional encryption (MIFE) is a generalization of functional encryption first proposed by Goldwasser et al. in [18]. The main objective is to divide the plaintext into several parts (calleds inputs) so that they can be encrypted in independent executions of the encryption algorithm. In this case, the output of the decryption is a function taking all inputs as variables. This models a situation where data to be encrypted may not arrive all at the same time, while still be needed all together to obtain the evaluation of the desired function. This primitive is useful in many real-life use cases related to privacy-preserving cloud services, federated learning, or more generally delegation of computation to a more powerful entity.

Multi-input functional encryption for general purpose is difficult to achieve
(as its single-input counterpart) and has strong implications, e.g., indistinguishability obfuscation [18]. However, for concrete families of functions some instantiations have been found. In the case of inner-product, the first proposal was by Abdalla et al. [4] with a secret-key multi-input scheme. It was followed by a transformation from single-input IPFE to the multi-input case [3] still in the secret-key setting that requires no other assumptions apart from the one of the single-input scheme. For quadratic functionalities, only two proposals exist by Agrawal et al. [6,7] in which they give specific instantiations of secret-key multi-input quadratic functional encryption schemes based on function-hiding functional encryption. Such constructions are proven secure in the indistinguishability setting and, as far as we know, it does not exist any construction for a multi-input quadratic functional encryption scheme satisfying simulation security. Our main purpose in this paper is to fill this gap.
The focus on secret key constructions comes from the fact that public key multi-input functional encryption is easily constructed from single-input func- tional encryption [4,6] (for both linear and quadratic functionalities). However, these instantiations cannot be trivially transformed into secret key by consider- ing the public key as part of the master secret key due to the inherent leakage of the functionalities. For a more detailed analysis of this issue, we refer to [4, Section 1.1] and [6, Section 1.2, Appendix A.2].

*Function-hiding functional encryption.* As in [4,6], our MIQFE is based on a function-hiding IPFE (FH-IPFE). Function-hiding is an additional security property for functional encryption, first proposed by Shen *et al.* in [25]. Analogously to the ciphertext protecting the plaintext *x*, the functional key is in this setting required to protect the function *f*. In other words, the adversary *only* learns *f(x)* and no other information about either *x* or *f*. Once again, given the power the adversary has in the public-key setting to encrypt any message, public-key function-hiding schemes are unfeasible. By giving the adversary the possibility of encrypting any plaintext, the function “hidden” in the functional key can be recovered.

In the case of IPFE, several function-hiding constructions exist, most of the time based on bilinear pairings and secure in the standard model [13,16,26,21] (especially because a recent result shows that Learning With Errors based constructions are impossible [27]). Security-wise, as explained above, we need simulation based security for our multi-input quadratic FE. Regarding the literature on the subject, it only remains the scheme by Kim *et al.* in [20] which achieves such security in the Generic Group Model.

## 1.1 Contributions

Our first contribution is the transformation from any function-hiding inner-product functional encryption to a multi-input quadratic functional encryption achieving selective simulation security for one ciphertext in the secret key setting, with a ciphertext size of $O(nl^2)$ where $l$ is the number of inputs and $n$ the size of these inputs. This is the first instantiation of multi-input quadratic functional encryption scheme satisfying simulation security. To achieve this we base ourselves on the single-input quadratic functional encryption scheme of [17, Section 3], using techniques from the multi-input inner-product functional encryption scheme from [3, Section 3].

This transformation is based on a simulation secure function-hiding inner-product functional encryption for which we give a new instantiation in the standard model, based on the DDH-based inner-product scheme in [1, Section 3] and inspired by the partially function-hiding inner-product scheme in [17, Section 4]. This is the first simulation secure function-hiding inner-product scheme in the standard model.
## 1.2 State of the Art

In quadratic functional encryption, the function is generally defined by a matrix $F \in \mathbb{Z}_p^{n \times n}$ with $F(x) = x^\top F x$. Based on that, it is trivial to construct a “naive” single-input quadratic functional encryption scheme from any single-input inner-product functional encryption scheme, in which the functions are defined by a vector $y \in \mathbb{Z}_p^n$ with $y(x) = x^\top y$. For such a generic construction, we first observe that $x^\top F x = (x \otimes x)^\top \text{vect}(F)$ where $\otimes$ denotes the Kronecker product and $\text{vect}(F)$ is the vectorization of $F$. From that, such naive QFE can be constructed as follows.

### Encryption Scheme 1 (Naive QFE)

- **QFE.Enc($x$)**: Compute $c_x \leftarrow \text{IPFE.Enc}(x \otimes x)$.

- **QFE.KeyGen($F$)**: Compute $sk_F \leftarrow \text{IPFE.KeyGen}(\text{vect}(F))$.

- **QFE.Dec($c_x, sk_F$)**: Compute $(x \otimes x)^\top \text{vect}(F) \leftarrow \text{IPFE.Dec}(c_x, sk_F)$.

But it is obvious that this leads to quadratic ciphertext sizes. Hence, constructions for single-input quadratic functional encryption are centered on achieving linear-size ciphertexts. However, such a naive approach does not work in the multi-input setting since we would need $\text{Enc}(x_i \otimes x_j)$ and $x_i, x_j$ to be encrypted independently.

There are only two proposals for multi-input quadratic functional encryption [6,7]. In both, they adapt the single-input quadratic scheme from Lin [22] to the multi-input setting. The high level idea is to use function-hiding inner-product functional encryption. More specifically, during the encryption, every input is used as an input of both encryption and key generation of the function-hiding inner-product scheme. They achieve selective indistinguishability security for many challenge plaintexts, based on the security of the underlying scheme. In [6] they make use of two extra functionalities, namely predicated inner-product functional encryption and mixed group inner-product functional encryption, while in [7] the instantiation is simplified, while achieving a stronger sense of security allowing corruption of inputs, still in the indistinguishability based setting.

Another work by Gay [17] gives a transformation from “partially” function-hiding inner-product functional encryption to public-key single-input quadratic functional encryption scheme. This way, it achieves semi-adaptive simulation security for one ciphertext. Abdalla et al. in [3] gave a transformation from standard inner-product functional encryption to secret-key multi-input inner-product functional encryption scheme, achieving selective simulation security for one ciphertext and adaptive indistinguishability security for many ciphertexts. We will use elements of both these transformations to construct ours.

Efficiency-wise, let us consider an input plaintext of size $n\ell$, either by $\ell$ inputs of size $n$ or a single input of size $n\ell$. The previous naive construction of a single-input quadratic functional encryption scheme achieves simulation-security with $O(n^2\ell^2)$-bit size ciphertexts. On the other hand, Gay [17] proposes a simulation secure single-input quadratic functional encryption with ciphertext of size $O(n\ell)$. The ciphertext size of the multi-input inner product functional encryption from
<table><caption>**Table 1.** Relevant functional encryption schemes, where $\ell$ refers to the number of inputs and $n$ to the size of each input. For a fair comparison we consider the single-input schemes as one input of size $n\ell$. PFH stands for partially function-hiding.</caption><thead><tr><th>Proposal</th><th>Starting building block</th><th>Functionality</th><th>Simulation security</th><th>Size of the ciphertext</th></tr></thead><tbody><tr><td>Naive (1)</td><td>IPFE</td><td>QFE</td><td>✓</td><td>O(n<sup>2</sup>ℓ<sup>2</sup>)</td></tr><tr><td>[17]</td><td>PFH-IPFE</td><td>QFE</td><td>✓</td><td>O(nℓ)</td></tr><tr><td>[3]</td><td>IPFE</td><td>MIPFE</td><td>✓</td><td>O(nℓ)</td></tr><tr><td>[7]</td><td>FH-IPFE</td><td>MIQFE</td><td>✗</td><td>O(nℓ)</td></tr><tr><td>Our work</td><td>FH-IPFE</td><td>MIQFE</td><td>✓</td><td>O(nℓ<sup>2</sup>)</td></tr></tbody></table>

[3] is also $O(n\ell)$. In this work, we show that upgrading a single-input quadratic functional encryption to multi-input in simulation based security can be done at a cost linear in $\ell$, leading to a ciphertext size of $O(n\ell^2)$. With indistinguishability based security, the scheme in [7] achieves a ciphertext of size $O(n\ell)$. For a summary, see Table 1.

Concerning simulation secure function-hiding inner-product FE, there only exists by Kim et al.'s protocol in [20], where they achieve adaptive simulation security against many challenge ciphertexts by constraining themselves to the generic group model (GGM). Since this is an oracle-based model, the impossibility results for adaptive simulation security [14,24,5] no longer hold. There is also [28] which claims a function-hiding inner-product functional encryption scheme simulation secure against many challenge ciphertexts in the standard model, which is known to be impossible even in the non function-hiding setting.

## 1.3 Technical Overview

**Multi-input Quadratic Functional Encryption Scheme.** Our objective is to construct a simulation sound multi-input quadratic functional encryption scheme. One approach could have been to prove that the schemes [6,7] are simulation sound. However, the way both these schemes are constructed from the single-input quadratic functional encryption scheme by Lin [22] makes it impossible. Indeed, during the encryption of input $x_i$ they run both the encryption and key generation algorithms of a function-hiding inner-product. Then during decryption, they multiply all the results of the decryptions of all the cross terms $i, j$ by the coefficients of the matrix $F_{i,j}$ to obtain the desired result. Because there are several inputs to be encrypted independently, using both the encryption and key generation algorithms, the selective simulation soundness for one challenge ciphertext in the multi-input scheme would require adaptive simulation soundness for several challenge ciphertexts. But adaptive simulation soundness is hard to achieve for non function-hiding functional encryption in the standard model [14], and even more in the case of function-hiding functional encryption.

Our idea is hence to start from the single-input quadratic functional encryption scheme in [17] based on partially function-hiding inner-product functional encryption. Function-hiding is said to be partial when decryption keys
partially hide their underlying function (see [17] for details). Such a construction is sketched below, in the secret key setting to simplify the reading.

### Encryption Scheme 2 (Simplified Figure 4, [17])

- **QFE.SetUp(1^κ)**: Sample $\mathbf{a} \in \mathbb{Z}_p^2$, $\mathbf{B} \in \mathbb{Z}_p^{3 \times 2}$, $\mathbf{U} \in \mathbb{Z}_p^{n \times 2}$ and $\mathbf{V} \in \mathbb{Z}_p^{m \times 3}$. Define

$$ \mathbf{M} := \left( \frac{\mathbf{a} \otimes (\mathrm{Id}_m | \mathbf{V}\mathbf{B})}{0} \mid \frac{0}{| \mathrm{Id}_n \otimes \mathbf{B} |} \right), $$

and run (IPFE.pk, IPFE.msk) ← IPFE.SetUp(1^κ, [M]_1). Output QFE.msk = (a, B, U, V, IPFE.pk, IPFE.msk)

- **QFE.Enc(\mathbf{x})**: Sample $r \stackrel{\$}{\leftarrow} \mathbb{Z}_p$ and $\mathbf{s} \stackrel{\$}{\leftarrow} \mathbb{Z}_p^2$ and compute

$$ [\mathbf{c}_x^1]_1 := [\mathbf{x} + \mathbf{U}\mathbf{a}\mathbf{r}]_1, \quad [\mathbf{c}_x^2]_2 := [\mathbf{x} + \mathbf{V}\mathbf{B}\mathbf{s}]_2, \\ \text{IPFE.c} \leftarrow \text{IPFE.Enc} \left( \text{IPFE.pk}, \left( \mathbf{r} \otimes \begin{pmatrix} \mathbf{x} \\ \mathbf{s} \end{pmatrix} \quad \mathbf{x} \otimes \mathbf{s} \right) \right). $$

Output $c_x = ([c_x^1]_1, [c_x^2]_2, \text{IPFE.c})$.

- **QFE.KeyGen(F)**: Compute

$$ \text{IPFE.sk} \leftarrow \text{IPFE.KeyGen} \left( \text{IPFE.msk}, \left( \text{vect}(\mathbf{U}^\top \mathbf{F}) \quad \text{vect}(\mathbf{F}\mathbf{V}) \right) \right). $$

Output $\text{sk}_F = (\mathbf{F}, \text{IPFE.sk})$.

- **QFE.Dec(c_x, sk_F)**: Compute

$$ [d]_T \leftarrow \text{IPFE.Dec}(\text{IPFE.c}, \text{IPFE.sk}), [v]_T := e([\mathbf{c}_x^1]_1, \mathbf{F}[\mathbf{c}_x^2]_2) - [d]_T $$

Output $\log([v]_T)$ if $v \in [0, n^2 \cdot B^3]$ and $\perp$ otherwise.

At a high level, there are two one-time pads $c_x^1, c_x^2$ which are combined as $c_x^1 \top \mathbf{F} c_x^2$ to give the desired value $\mathbf{x}^\top \mathbf{F} \mathbf{x}$ plus some extra terms. The inner-product functional encryption scheme is used to compute these extra terms so they can be subtracted in the end. Eventually, the partially function-hiding property is used to ensure that the functional key does not leak too much information about $\mathbf{U}$ and $\mathbf{V}$ (in concrete, $[c_x^i]_i$ remain indistinguishable from random).

The first idea that comes to mind to extend this scheme from single-input to multi-input would be to encrypt each input and substitute the (partially function-hiding) inner-product functional encryption scheme for a (partially function-hiding) multi-input one. However, the decryption phase necessitates to eliminate the extra terms coming from $e([c_x^1]_1, \mathbf{F}_{i,j}[c_x^2]_2)$:

$$ e([c_{x_i}^1]_1, \mathbf{F}_{i,j}[c_{x_j}^2]_2) = [\mathbf{x}_i^\top \mathbf{F}_{i,j} \mathbf{x}_j]_T + [\mathbf{x}_i^\top \mathbf{F}_{i,j} \mathbf{V} \mathbf{B} \mathbf{s}_i]_T \\ + [\mathbf{U} \mathbf{a} \mathbf{r}_i^\top \mathbf{F}_{i,j} \mathbf{j} \mathbf{x}_j]_T + [\mathbf{U} \mathbf{a} \mathbf{r}_i^\top \mathbf{F}_{i,j} \mathbf{V} \mathbf{B} \mathbf{s}_i]_T. $$
This elimination could be done using the IPFE encryption. In this case, we would need the ciphertext and functional key to be

$$ 
\begin{aligned}
\text{IPFE.}\tilde{c}_{i,j} &\leftarrow \text{IPFE.Enc}\left(\text{IPFE.pk}, \begin{pmatrix} r_i \otimes \begin{pmatrix} \mathbf{x}_j \\ \mathbf{s}_j \end{pmatrix} \\ \mathbf{x}_i \otimes \mathbf{s}_j \end{pmatrix}\right), \\
\text{IPFE.}\tilde{sk}_{i,j} &\leftarrow \text{IPFE.KeyGen}\left(\text{IPFE.msk}, \begin{pmatrix} \text{vect}(\mathbf{U}^\top \mathbf{F}_{i,j}) \\ \text{vect}(\mathbf{F}_{i,j} \mathbf{V}) \end{pmatrix}\right).
\end{aligned}
$$

However, $\mathbf{x}_i$ and $\mathbf{x}_j$ should be encrypted in different independent instances of the encryption algorithm and therefore such ciphertext cannot be created. To circumvent this issue we use two main properties of the multi-input scheme. Firstly, we use the fact that during decryption, all partial decryptions (for $i, j \in [\ell]$) will be added altogether, and in particular IPFE.c$_{i,j}$ and IPFE.c$_{j,i}$. This allows us to “interweave” the ciphertexts, where in input $i$ we compute half of what is needed for $e([ct_{\mathbf{x}_i}]_1, F_{i,j}[ct_{\mathbf{x}_j}]_2)$ and half of what is needed for $e([ct_{\mathbf{x}_j}]_1, F_{j,i}[ct_{\mathbf{x}_i}]_2)$, while the other two halves are computed on input $j$. Therefore, combining the decryptions of IPFE.c$_{i,j}$ and IPFE.c$_{j,i}$ we obtain all the extra terms resulting from $e([ct_{\mathbf{x}_i}]_1, F_{i,j}[ct_{\mathbf{x}_j}]_2)$ and $e([ct_{\mathbf{x}_j}]_1, F_{j,i}[ct_{\mathbf{x}_i}]_2)$. More specifically, by computing the following where the changes are squared

$$ 
\begin{aligned}
\text{IPFE.c}_{i,j} &\leftarrow \text{IPFE.Enc}\left(\text{IPFE.pk}, \begin{pmatrix} r_j \otimes \begin{pmatrix} \mathbf{x}_i \\ \mathbf{s}_i \end{pmatrix} \\ \mathbf{x}_i \otimes \mathbf{s}_j \end{pmatrix}\right), \\
\text{IPFE.sk}_{i,j} &\leftarrow \text{IPFE.KeyGen}\left(\text{IPFE.msk}, \begin{pmatrix} \text{vect}(\mathbf{U}^\top \mathbf{F}_{j,i}) \\ \text{vect}(\mathbf{F}_{i,j} \mathbf{V}) \end{pmatrix}\right),
\end{aligned}
$$

which given the linearity of inner product, during decryption we get for any $i, j \in [\ell]$,

$$ 
\begin{aligned}
\text{IPFE.Dec}(\text{IPFE.c}_{i,j}, \text{IPFE.sk}_{i,j}) + \text{IPFE.Dec}(\text{IPFE.c}_{j,i}, \text{IPFE.sk}_{j,i}) \\
= \\
\text{IPFE.Dec}(\text{IPFE.}\tilde{c}_{i,j}, \text{IPFE.}\tilde{sk}_{i,j}) + \text{IPFE.Dec}(\text{IPFE.}\tilde{c}_{j,i}, \text{IPFE.}\tilde{sk}_{j,i})
\end{aligned}
$$

which is what we need to eliminate the extra terms appearing in both crossed terms $i, j$ and $j, i$.

Secondly, we use the fact that we are in the secret-key setting. As such we can presample the random values we will use in the encryption algorithm during the set up. From the encryption of a specific input, this gives us access to the values of all the rest of the inputs.

Furthermore, this use of secret-key cryptography allows us to directly base ourselves in function-hiding inner-product functional encryption, without the need to use its “partial” version (the scheme from [17] cannot do so since public-key function-hiding functional encryption is impossible). We also simplify the scheme to require less security assumptions. Eventually, the security of our scheme depends solely on the security of the underlying function-hiding inner-product functional encryption scheme.
The final step of our transformation is to use the argument in [3] to make sure
that the correct result can only be obtained when all the inputs are taken into
account. More precisely, they encrypt a one-time pad $w + x$ and then compute
an extra $zk_y = w^\top y$ during key generation, which one is finally substracted
during decryption to obtain the real value. This holds as long as there are less
functional key queries than the size of the vector since $w$ will still have enough
entropy to make $zk_F$ indistinguishable from random.

**Function-hiding Inner-product Functional Encryption Scheme.** Similarly to the construction of partially function-hiding functional encryption from [17, Section 4], we construct our function-hiding inner product functional encryption scheme by layering two instances of a non function-hiding scheme (one in and one out) as follows: $Enc^{FH}(x) = Enc^{out}(KeyGen^{in}(x))$ and $KeyGen^{FH}(y) = KeyGen^{out}(Enc^{in}(y))$. Then, decryption is done through the use of a bilinear pairing. This allows us to protect both the plaintext in the ciphertext and the function in the functional key.

The instantiation in [17, Section 4] is based on the non function-hiding scheme
from [8, Section 3], since it intends to achieve simulation security in the public
key setting and as such it needs an extra slot to handle this. In our case, given
that we are in the secret key setting, basing ourselves in the scheme from [1,
Section 3] is enough. As such we use a different approach than [17] to simulate
the functional keys, where we use the Q-fold DDH assumption instead of the "1"-
fold DDH one. This allows us to have slightly smaller ciphertexts and functional
keys (one less slot) than the construction in [17].

This layering approach is very similar to the function-hiding inner prod-
uct functional encryption scheme given in [22, Section 6.3]. Indeed, the cru-
cial difference is the order in which the layers are set. In their case they have
$Enc^{FH}(x) = KeyGen^{out}(Enc^{in}(x))$ and $KeyGen^{FH}(y) = Enc^{out}(KeyGen^{in}(y))$. How-
ever, this set up does not work for proving simulation security. As evidence, let us
denote $key^{out}$, $key^{in}$ the keys for each layer of non function-hiding inner-product
functional encryption. When simulating the function-hiding ciphertext by simu-
lating the encryption in the inner layer, the simulated ciphertext will still depend
on (non-simulated) $key^{out}$. Then, when simulating the function-hiding functional
key by simulating the encryption in the outer layer, the key we need to simulate
is both in the ciphertext and functional key, which are in two different groups. As
such, trying to use the DDH assumption (in which [1] is based) to simulate this
functional key will not work since there will be one element in $G_1$ and another
in $G_2$: the bilinear pairing trivially breaks the scheme.

In our case, when simulating the function-hiding ciphertext by simulating
the encryption in the *outer* layer, the ciphertext no longer depends on $key^{in}$ and
as such we are free to use the DDH assumption to simulate the function-hiding
functional key, simulating the encryption in the *inner* layer.
## 2 Preliminaries

One-dimensional elements will be noted as lower-case letters $(x, y, \dots)$, while vectors will use bold lower-case letters $(\mathbf{x}, \mathbf{y}, \dots)$ and matrices will use bold upper-case letters $(M, U, V, \dots)$. Let $D$ be a probability distribution, $x \leftarrow D$ means the element $x$ is sampled from the distribution $D$, while for any set $\mathcal{Y}$, $y \stackrel{\$}{\leftarrow} \mathcal{Y}$ means that $y$ is sampled uniformly at random from $\mathcal{Y}$. Finally, a function $f$ is said to be negligible over $n$ ($f = \text{negl}(n)$) if for all $k \in \mathbb{N}_{>0}$, there exists $n_0 \in \mathbb{N}_{>0}$ such that for any $n > n_0$ then $|f(n)| < 1/n^k$.

### 2.1 Pairing Groups

This work makes use of asymmetric pairing groups, inherited from function-hiding functional encryption. Let $\mathbb{G}_1, \mathbb{G}_2, \mathbb{G}_T$ be three additive cyclic groups of order a prime $p$. Let $P_1, P_2$ be generators of $\mathbb{G}_1$ and $\mathbb{G}_2$ respectively and let $e : \mathbb{G}_1 \times \mathbb{G}_2 \to \mathbb{G}_T$ be an efficiently computable (non-degenerate) bilinear map. This means that $e(\alpha P_1, \beta P_2) = \alpha \cdot \beta P_T$ for any $\alpha, \beta \in \mathbb{Z}_p$ where we define $P_T := e(P_1, P_2)$.

For $s \in \{1, 2, T\}$ and a matrix $\mathbf{A} = (a_{ij}) \in \mathbb{Z}_p^{n \times m}$ for any $n, m \ge 1$ we define $[\mathbf{A}]_s$ as the representation of $\mathbf{A}$ in the group $\mathbb{G}_s$. In other words, $[\mathbf{A}]_s = (a_{ij}P_s) \in \mathbb{G}_s^{n \times m}$. For any two matrices $\mathbf{A}, \mathbf{B} \in \mathbb{Z}_p^{n \times m}$, $e([\mathbf{A}]_1, [\mathbf{B}]_2) := [\mathbf{A}\mathbf{B}]_T$ and for $s \in \{1, 2, T\}$ we have $[\mathbf{A}]_s + [\mathbf{B}]_s := [\mathbf{A} + \mathbf{B}]_s$.

Finally, we define the PPT algorithm PGGen that, on input a security parameter $\kappa$, outputs a set $(\mathbb{G}_1, \mathbb{G}_2, \mathbb{G}_T, p, P_1, P_2, e)$ where $p$ is a $2\kappa$-bit prime.

### 2.2 Functional Encryption

Functional encryption is a generalization of encryption first formalized by Boneh et al. [14] and O'Neill [24], in which the decryption algorithm no longer outputs necessarily the plaintext, but a function applied to this plaintext. This is achieved through the generation of functional keys related to the specific function wanted to be applied. Such schemes are defined as follows in the secret-key setting.

**Definition 1 (Functional Encryption Scheme).** Let $\kappa \in \mathbb{N}_{>0}$ be a security parameter and $\mathcal{F}$ be a family of functions. A function $f \in \mathcal{F}$ is defined as $f : \mathcal{X} \to \mathcal{S}$. We define a secret-key functional encryption scheme the following tuple of PPT algorithms:

- FE.SetUp$(1^\kappa, \mathcal{F}) : \text{given the security parameter } \kappa \text{ and the family of functions } \mathcal{F} \text{ as input, it outputs some public parameters FE.param and a master secret key FE.msk. We will assume the public parameters as inputs in all other algorithms.}$

- FE.Enc$(\text{FE.msk}, x) : \text{given the master secret key FE.msk and a plaintext } x \in \mathcal{X} \text{ as inputs, it outputs a ciphertext } c_x$.

- FE.KeyGen$(\text{FE.msk}, f) : \text{given the master secret key FE.msk and a function } f \in \mathcal{F} \text{ as inputs, it outputs a functional key sk}_f$.
- FE.Dec($c_x, sk_f$) : given a ciphertext $c_x$ and a functional key $sk_f$ as inputs, it outputs a value in $S$ or $\perp$ if it fails.

The correctness notion for such schemes is as follows.

**Definition 2 (Correctness of Functional Encryption).** Let $\kappa \in \mathbb{N}_{>0}$ be a security parameter and FE = (FEEstablish, FEEnc, FEKeyGen, FE.Dec) be a secret-key functional encryption scheme. We say it is correct if for any $x \in \mathcal{X}$ and $f \in \mathcal{F}$ we have

$$ \Pr[\mathrm{FE.Dec}(c_x, sk_f) \neq f(x)] = \mathrm{negl}(\kappa) $$

where the distribution is taken over FE.msk $\leftarrow$ FE.SetUp(1$^{\kappa}$, $\mathcal{F}$), $c_x \leftarrow$ FE.Enc(FE.msk, $x$) and $sk_f \leftarrow$ FE.KeyGen(FE.msk, $f$).

**Multi-input Functional Encryption** As mentioned in Section 1, multi-input functional encryption is a generalisation of functional encryption which divides the plaintext into $\ell$ inputs to be encrypted independently. The standard definitions for this are case as follows.

**Definition 3 (Multi-input Functional Encryption Scheme).** Let $\kappa \in \mathbb{N}_{>0}$ be a security parameter, $\ell \in \mathbb{N}_{>0}$ be the number of inputs and $\mathcal{F}$ be a family of $\ell$-ary functions. A function $f \in \mathcal{F}$ is defined as $f: \mathcal{X}_1 \times \dots \times \mathcal{X}_\ell \to S$. We define a secret-key multi-input quadratic functional encryption scheme as the following tuple of PPT algorithms:

- MIFE.SetUp(1$^{\kappa}$, $\mathcal{F}$): given the security parameter 1$^{\kappa}$ and a family of $\ell$-ary functions $\mathcal{F}$, it outputs some public parameters MIFE.param a master secret key MIFE.msk. We will assume the public parameters as inputs in all other algorithms.

- MIFE.Enc(MIFE.msk, $i, x_i$): given the master secret key MIFE.msk, an input number $i \in [\ell]$ and $x_i \in \mathcal{X}_i$, it outputs a ciphertext $c_{x_i}$.

- MIFE.KeyGen(MIFE.msk, $f$): given the master secret key MIFE.msk and a function $f \in \mathcal{F}$ as inputs, it outputs a functional decryption key $sk_f$.

- MIFE.Dec($c_{x_1}, \dots, c_{x_\ell}, sk_f$): a deterministic algorithm that given ciphertexts $c_{x_1}, \dots, c_{x_\ell}$ and a functional key $sk_f$ as inputs, it outputs a value in $S$, or $\perp$ if it fails.

The correctness notion for these schemes goes as follows.

**Definition 4 (Correctness of Multi-input Functional Encryption).** Let $\kappa \in \mathbb{N}_{>0}$ be a security parameter, $\ell \in \mathbb{N}_{>0}$ be the number of inputs and MIFE = (MIFEEstablish, MIFEEnc, MIFE.KeyGen, MIFE.Dec) be a secret-key multi-input functional encryption scheme. We say it is correct if for any $x_1 \in \mathcal{X}_1, \dots, x_\ell \in \mathcal{X}_\ell$ and $f \in \mathcal{F}$ we have

$$ \Pr[\mathrm{MIFE.Dec}(c_{x_1}, \dots, c_{x_\ell}, sk_f) \neq f(x_1, \dots, x_\ell)] = \mathrm{negl}(\kappa) $$

where the distribution is taken over MIFE.msk $\leftarrow$ MIFE.SetUp(1$^{\kappa}$, $\mathcal{F}$), $c_{x_i} \leftarrow$ MIFE.Enc(MIFE.msk, $i, x_i$) for all $i \in [\ell]$ and $sk_f \leftarrow$ MIFE.KeyGen(MIFE.msk, $f$).
<table><caption>**Table 2.** Real and ideal experiments in SEL-SIM security for MIQFE.</caption><thead><tr><th></th><th>Exp<sub>A</sub><sup>real</sup>(1<sup>κ</sup>):<br>1: MIFE.msk ← MIQFE.SetUp(1<sup>κ</sup>, F)<br>2: ({x<sub>i</sub>}<sub>i∈[ℓ]</sub>, st<sub>1</sub>) ← A<sub>1</sub>(1<sup>κ</sup>) where x<sub>i</sub> ∈ X<sub>i</sub><br>3: For all i ∈ [ℓ], c<sub>x<sub>i</sub></sub> ← MIFE.Enc(MIFE.msk, i, x<sub>i</sub>)<br>4: γ ← A<sub>2</sub><sup>O<sub>MIFE.KeyGen</sub>(msk, ·)</sup>({c<sub>x<sub>i</sub></sub>}<sub>i∈[ℓ]</sub>, st<sub>1</sub>)</th><th>Exp<sub>A,S</sub><sup>ideal</sup>(1<sup>κ</sup>):<br>1: MIFE.msk ← MIFE.SetUpSim(1<sup>κ</sup>, F)<br>2: ({x<sub>i</sub>}<sub>i∈[ℓ]</sub>, st<sub>1</sub>) ← A<sub>1</sub>(1<sup>κ</sup>) where x<sub>i</sub> ∈ X<sub>i</sub><br>3: For all i ∈ [ℓ], c̃<sub>x<sub>i</sub></sub> ← MIFE.EncSim(MIFE.msk, i)<br>4: γ ← A<sub>2</sub><sup>Q<sub>MIFE.KeyGen</sub>(MIFE.msk, {x<sub>i</sub>}<sub>i∈[ℓ]</sub>, ·)</sup>({c̃<sub>x<sub>i</sub></sub>}<sub>i∈[ℓ]</sub>, st<sub>1</sub>)</th></tr></thead></table>

As explained in Section 1, there are two main ways to classify security definitions for functional encryption: indistinguishability based or simulation based and selective or adaptive. In this work we are interested in selective simulation security for one challenge ciphertext, for which we give the definition below.

**Definition 5 (Simulation Security for Multi-input Functional Encryption).** Let $\kappa \in \mathbb{N}_{>0}$ be a security parameter, $\ell \in \mathbb{N}_{>0}$ be the number of inputs and MIFE = (MIFE.SetUp, MIFE.Enc, MIFE.KeyGen, MIFE.Dec) be a secret-key multi-input functional encryption scheme. For any PPT simulator $S := (\text{MIFE}\text{.}\text{SetUpSim}, \text{MIFE}\text{.}\text{EncSim}, \text{MIFE}\text{.}\text{KeyGenSim})$ and any PPT adversary $\mathcal{A}$ we define the experiments in Table 2 where the oracles are described as follows.

1. **Real Experiment:** $O_{\text{MIFE}\text{.}\text{KeyGen}}(\text{MIFE.msk}, \cdot)$ takes as input a function $f \in \mathcal{F}$ and outputs $sk_f \leftarrow \text{MIFE}\text{.}\text{KeyGen}(\text{MIFE.msk}, f)$.

2. **Ideal Experiment:** $\tilde{O}_{\text{MIFE}\text{.}\text{KeyGen}}(\text{MIFE.msk}, x_1, \dots, x_\ell, \cdot)$ takes as input a function $f \in \mathcal{F}$, computes $v = f(x_1, \dots, x_\ell)$ and outputs $sk_f \leftarrow \text{MIFE}\text{.}\text{KeyGenSim}(\text{MIFE.msk}, v, f)$.

We say MIFE is one selective multi-input simulation secure if there exists a PPT simulator $S := (\text{MIFE}\text{.}\text{SetUpSim}, \text{MIFE}\text{.}\text{EncSim}, \text{MIFE}\text{.}\text{KeyGenSim})$ such that for all PPT adversary $\mathcal{A}$ the following inequality holds.

$$ \mathrm{Adv}_{\mathrm{MIFE}}^{\mathrm{MI-SIM}}(\mathcal{A}) = |\mathrm{Pr}[1 \leftarrow \mathrm{Exp}_{\mathcal{A}}^{\mathrm{real}}(1^{\kappa})] - \mathrm{Pr}[1 \leftarrow \mathrm{Exp}_{\mathcal{A}}^{\mathrm{ideal}}(1^{\kappa})]| \leq \mathrm{negl}(\kappa) $$

**Function-hiding Functional Encryption** As mentioned in Section 1, function-hiding functional encryption is a restriction of functional encryption which guarantees privacy for the function from the functional key, as well as the standard privacy for the message from the ciphertext. The security definition in the simulation security setting is then as follows.

**Definition 6 (Simulation Security of Function-hiding Functional Encryption).** Let $\kappa \in \mathbb{N}_{>0}$ be a security parameter, $n \in \mathbb{N}_{>0}$ be the dimension, and FE = (FE.SetUp, FE.Enc, FE.KeyGen, FE.Dec) be a secret-key functional encryption scheme. For any PPT simulator $S := (\text{FE}\text{.}\text{SetUpSim}, \text{FE}\text{.}\text{EncSim}, \text{FE}\text{.}\text{KeyGenSim})$ and any PPT adversary $\mathcal{A}$ we define the experiments in Table 3 where the oracles are described as follows.
<table><caption>**Table 3.** Real and ideal experiments in function-hiding SEL-SIM security for FE.</caption><thead><tr><th></th><th>Exp<sub>A</sub><sup>real</sup>(1<sup>κ</sup>):<br>1: FE.msk &larr; FE.SetUp(1<sup>κ</sup>, 𝒦)<br>2: (x, st<sub>1</sub>) &larr; A<sub>1</sub>(1<sup>κ</sup>) where x &in; 𝒦<br>3: c<sub>x</sub> &larr; FE.Enc(FE.msk, x)<br>4: γ &larr; A<sub>2</sub><sup>O<sub>FE.KeyGen</sub>(FE.msk, ·)</sup>(c<sub>x</sub>, st<sub>1</sub>)</th><th>Exp<sub>A,S</sub><sup>ideal</sup>(1<sup>κ</sup>):<br>1: FE.msk &larr; FE.SetUpSim(1<sup>κ</sup>, 𝒦)<br>2: (x, st<sub>1</sub>) &larr; A<sub>1</sub>(1<sup>κ</sup>) where x &in; 𝒦<br>3: c&#771;<sub>x</sub> &larr; FE.EncSim(FE.msk)<br>4: γ &larr; A<sub>2</sub><sup>̄O<sub>FE.KeyGen</sub>(FE.msk, x, ·)</sup>(c&#771;<sub>x</sub>, st<sub>1</sub>)</th></tr></thead></table>

1. **Real Experiment:** $O_{FE.KeyGen}(FE.msk, \cdot)$ takes as input a function $f \in \mathcal{F}$ and outputs $sk_f \leftarrow FE.KeyGen(FE.msk, f)$.

2. **Ideal Experiment:** $\tilde{O}_{FE.KeyGen}(FE.msk, x, \cdot)$ takes as input a function $f \in \mathcal{F}$, computes $v = f(x)$ and outputs $\tilde{sk}_f \leftarrow FE.KeyGenSim(FE.msk, v)$.

We say FE is one selective function-hiding simulation secure if there exists a PPT simulator $S := (FE.SetUpSim, FE.EncSim, FE.KeyGenSim)$ such that for all PPT adversary $\mathcal{A}$ the following inequality holds.

$$ \mathrm{Adv}_{\mathrm{FE}}^{\mathrm{FH-SIM}}(\mathcal{A}) = |\mathrm{Pr}[1 \leftarrow \mathrm{Exp}_{\mathcal{A}}^{\mathrm{real}}(1^{\kappa})] - \mathrm{Pr}[1 \leftarrow \mathrm{Exp}_{\mathcal{A}}^{\mathrm{ideal}}(1^{\kappa})]| \leq \mathrm{negl}(\kappa) $$

The reason why this security definition captures function-hiding is the fact that FE.KeyGenSim takes as inputs only the simulated keys and the output of the function applied to the challenge. If this is satisfied, then the only information leaked from the ciphertext and functional key is the output of the function, since they both can be simulated only knowing this information.

## 3 Multi-input Quadratic Functional Encryption Scheme

In this section we describe our multi-input quadratic functional encryption scheme for bounded-norm quadratic functionalities. We first describe the family of functions we want to cover. Let $\mathcal{F}_{Q,B}^{n,\ell} : (\llbracket 0, B \rrbracket^n)^\ell \to \llbracket 0, (n\ell)^2 \cdot B^3 \rrbracket$ be the family of $\ell$-ary functions such that a function $\mathbf{F} \in \mathcal{F}_{Q,B}^{n,\ell}$ is defined by a matrix in $\llbracket 0, B \rrbracket^{n\ell \times n\ell}$ which we note as

$$ \mathbf{F} = \begin{pmatrix} \mathbf{F}_{1,1} & \cdots & \mathbf{F}_{1,\ell} \\ \vdots & \ddots & \vdots \\ \mathbf{F}_{\ell,1} & \cdots & \mathbf{F}_{\ell,\ell} \end{pmatrix} $$

with $\mathbf{F}_{i,j} \in \llbracket 0, B \rrbracket^{n \times n}$, and applied to $(\mathbf{x}_1, \dots, \mathbf{x}_\ell) \in (\llbracket 0, B \rrbracket^n)^\ell$ gives $\mathbf{F}(\mathbf{x}_1, \dots, \mathbf{x}_\ell) := \sum \mathbf{x}_i^\top \mathbf{F}_{i,j} \mathbf{x}_j$ for $i, j \in [\ell]$.

To construct our MIQFE scheme we use a function-hiding inner-product functional encryption whose family of functions is $\tilde{\mathcal{F}}_{\mathrm{IP}}^{2n} : \mathbb{Z}_p^{2n} \to \mathbb{G}_T$ (for some $\mathcal{P}G = (\mathbb{G}_1, \mathbb{G}_2, \mathbb{G}_T, p, P_1, P_2, e) \leftarrow \mathrm{PGGen}(1^\kappa)$). A function $\mathbf{y} \in \tilde{\mathcal{F}}_{\mathrm{IP}}^{2n}$ is defined by a vector in $\mathbb{Z}_p^{2n}$ and applied to $\mathbf{z}$ gives $\mathbf{y}(\mathbf{z}) := [\mathbf{z}^\top \mathbf{y}]_T$.
## 3.1 Description of the Scheme

Let IPFE = (IPFE.Setup, IPFE.Enc, IPFE.KeyGen, IPFE.Dec) be a function-hiding inner-product functional encryption scheme for the family of functions $\tilde{\mathcal{F}}_{\text{IP}}^{2n}$. Below is a description of our MIQFE scheme for the family of functions $\mathcal{F}_{Q,B}^{n,l}$.

### Encryption Scheme 3 (MIQFE Scheme)

- **MIQFE.Setup(1^k, \mathcal{F}_{Q,B}^{n,l})**: Sample $\mathcal{PG} = (\mathbb{G}_1, \mathbb{G}_2, \mathbb{G}_T, p, P_1, P_2, e) \leftarrow \text{PGGen}(1^k)$, $\mathbf{u}_i \stackrel{\$}{\leftarrow} \mathbb{Z}_p^n$ and $c_i \stackrel{\$}{\leftarrow} \mathbb{Z}_p$ for $i \in [l]$ and sample $\mathbf{w}_{i,j} \stackrel{\$}{\leftarrow} \mathbb{Z}_p^{2n}$ for $i, j \in [l]$. Run IPFE.msk$_{i,j} \leftarrow \text{IPFE.Setup}(1^k, \tilde{\mathcal{F}}_{\text{IP}}^{2n}, \mathcal{PG})$ for $i, j \in [l]$. Output

$$ \text{MIQFE.param} = \mathcal{PG} \text{ and} \\ \text{MIQFE.msk} = (\{\mathbf{u}_i, c_i\}_{i \in [l]}, \{\mathbf{w}_{i,j}, \text{IPFE.msk}_{i,j}\}_{i,j \in [l]}) $$

- **MIQFE.Enc(MIQFE.msk, $\mathbf{x}_i$)**: Compute

$$ \mathbf{ct}_{\mathbf{x}_i} := \mathbf{x}_i + c_i \mathbf{u}_i \in \mathbb{Z}_p^n, \\ \text{IPFE.c}_{i,j} \leftarrow \text{IPFE.Enc} \left( \text{IPFE.msk}_{i,j}, \mathbf{w}_{i,j} + c_j \begin{pmatrix} \mathbf{ct}_{\mathbf{x}_i} \\ \mathbf{x}_i \end{pmatrix} \right) \text{ for } j \in [l]. $$

$$ \text{Output MIQFE.c}_i = (\mathbf{ct}_{\mathbf{x}_i}, \{\text{IPFE.c}_{i,j}\}_{j \in [l]}). $$

- **MIQFE.KeyGen(MIQFE.msk, $\mathbf{F}$)**: Compute

$$ \text{IPFE.sk}_{i,j} \leftarrow \text{IPFE.KeyGen} \left( \text{IPFE.msk}_{i,j}, \begin{pmatrix} \mathbf{u}_j^\top \mathbf{F}_{j,i} \\ \tilde{\mathbf{F}}_{i,j} \mathbf{u}_j \end{pmatrix} \right) \text{ for } i, j \in [l], \\ \mathbf{zk}_{\mathbf{F}} \leftarrow \sum_{i,j \in [l]} \mathbf{w}_{i,j}^\top \begin{pmatrix} \mathbf{u}_j^\top \mathbf{F}_{j,i} \\ \tilde{\mathbf{F}}_{i,j} \mathbf{u}_j \end{pmatrix}. $$

$$ \text{Output MIQFE.sk}_{\mathbf{F}} = (\mathbf{F}, \{\text{IPFE.sk}_{i,j}\}_{i,j \in [l]}, \mathbf{zk}_{\mathbf{F}}). $$

- **MIQFE.Dec(MIQFE.c$_1$, ..., MIQFE.c$_l$, MIQFE.sk$_F$)**: Compute

$$ [d_{i,j}]_T \leftarrow \text{IPFE.Dec}(\text{IPFE.c}_{i,j}, \text{IPFE.sk}_{i,j}) \\ [v]_T := \left( \sum_{i,j \in [l]} [\mathbf{ct}_{\mathbf{x}_i}^\top \mathbf{F}_{i,j} \mathbf{ct}_{\mathbf{x}_j}]_T - [d_{i,j}]_T \right) + [\mathbf{zk}_F]_T $$

$$ \text{Output } \log([v]_T) \text{ if } v \in [0, (nl)^2 \cdot B^3] \text{ and } \perp \text{ otherwise.} $$

**Remark 1.** We define the output of the functions $\mathbf{y}$ to be in $\mathbb{G}_T$ to be compatible with existing function-hiding IPFE and only for that. Designing such a scheme without pairings is a hard open problem. This means that all schemes require bounded inputs to have a bounded output from which the discrete logarithm can be computed. Therefore, this requires us to perform the operations for the decryption algorithm in the exponent, since the input $\mathbf{w}_{i,j} + c_j \begin{pmatrix} \mathbf{ct}_{\mathbf{x}_i} \\ \mathbf{x}_i \end{pmatrix}$ is not bounded by definition thus making it unfeasible to compute $d_{i,j}$ in plain.
This means then that we add no extra pairing operations on top of those needed for the function-hiding scheme. As such, were there to be a scheme without pairings or allowing non-bounded inputs this property would immediately translate to our construction.

## 3.2 Correctness and Security

**Proposition 1.** The MIQFE scheme defined in Section 3.1 is a correct multi-input functional encryption scheme for $\mathcal{F}_{Q,B}^{n,\ell}$ as long as IPFE is a correct scheme for $\tilde{\mathcal{F}}_{IP}^{2n}$.

For the proof we refer to Appendix B.

**Theorem 1.** The MIQFE scheme described in 3 is one selective multi-input simulation secure, if the underlying inner-product functional encryption scheme is one selective function-hiding simulation secure. In other words, for any PPT adversary $\mathcal{A}$ there exist PPT adversaries $\mathcal{B}$ such that

$$ \mathrm{Adv}_{\mathrm{MIQFE}}^{\mathrm{MI-SIM}}(\mathcal{A}) \le \ell^2 \cdot \mathrm{Adv}_{\mathrm{IPFE}}^{\mathrm{FH-SIM}}(\mathcal{B}) + \frac{\ell}{p}. $$

*Proof.* Let $\mathcal{A}$ be a PPT adversary playing the 1-SEL-SIM security game for MIQFE, and let $\kappa \in \mathbb{N}$ be a security parameter. We will prove the result through a series of games Game $i$ for $i \in \{0, 1, 2, 3, 4\}$, defined in Figure 1 with changes in Game $i+1$ being over Game $i$. We show that $\mathrm{Exp}_{\mathcal{A}}^{\mathrm{real}}(1^{\kappa}) = \mathrm{Game} \ 0 \approx_s \mathrm{Game} \ 1 \approx_s \mathrm{Game} \ 2 \approx_s \mathrm{Game} \ 3 \approx_c \mathrm{Game} \ 4 = \mathrm{Exp}_{\mathcal{A},S}^{\mathrm{ideal}}(1^{\kappa})$. Let also IPFE.Sim = (IPFE.SetUpSim, IPFE.EncSim, IPFE.KeyGenSim) be the simulator for function-hiding 1-SEL-SIM for the IPFE scheme.

Let $\mathcal{C}'$ be a challenger that chooses $b \in \{0, 1\}$ uniformly at random. If $b = 0$ it interacts with a PPT adversary $\mathcal{A}'$ as in Game $i$, otherwise it interacts as in Game $i+1$. At the end of the interaction, $\mathcal{A}'$ will make its guess $\tilde{b} \in \{0, 1\}$. We define (for $i = 0, 1, 2, 3$) $\mathrm{Adv}_{i(i+1)}(\mathcal{A}') := |\mathrm{Pr}[\tilde{b} = 1 | b = 0] - \mathrm{Pr}[\tilde{b} = 1 | b = 1]|$.

**Game 0.** This is the real experiment for 1-SEL-SIM security for MIQFE.

**Game 1.** In this Game we are changing the ciphertext $ct_{x_i}$ to $c_i u_i$ which is random, and then change $u_i$ to $\tilde{u}_i := u_i - c_i^{-1} x_i$ in the rest of algorithms to maintain coherence. Also, since we need $c_i \neq 0$, we will abort `SetUp` whenever this is not satisfied. Then, distinguishing Games is distinguishing between $u_i$ and $\tilde{u}_i$.

First we show that coherence is kept. Indeed,
<figure><img src="image_2.png" /><figcaption>Fig. 1. Games for the security proof of the MIQFE scheme from Encryption Scheme 3.</figcaption></figure>

$$
\begin{align*}
[\tilde{v}]_T &= \left( \sum_{i,j \in [\ell]} [\tilde{c}t_{x_i} F_{i,j} \tilde{c}t_{x_j}]_T - [d_{i,j}]_T \right) + [zk_F]_T \\
&= \left( \sum_{i,j \in [\ell]} [c_i \tilde{u}_i^\top F_{i,j} c_j \tilde{u}_j]_T - \left[ (w_{i,j} + c_j (\tilde{c}t_{x_i} x_i))^\top \begin{pmatrix} \tilde{u}_j^\top F_{j,i} \\ F_{i,j} \tilde{u}_j \end{pmatrix} \right]_T \right) \\
&\quad + \left[ \sum_{i,j \in [\ell]} w_{i,j}^\top \begin{pmatrix} \tilde{u}_j^\top F_{j,i} \\ F_{i,j} \tilde{u}_j \end{pmatrix} \right]_T \\
&= \sum_{i,j \in [\ell]} [c_i \tilde{u}_i^\top F_{i,j} c_j \tilde{u}_j]_T - [c_j c_i \tilde{u}_i^\top (\tilde{u}_j - c_j^{-1} \tilde{x}_j)^\top F_{j,i}]_T \\
&\quad - [c_j \tilde{x}_i^\top F_{i,j} (\tilde{u}_j - c_j^{-1} \tilde{x}_j)]_T
\end{align*}
$$
$$
\begin{align*}
&= \sum_{i,j \in [\ell]} [c_i \mathbf{u}_i^\top \mathbf{F}_{i,j} c_j \mathbf{u}_j]_T - [c_j \mathbf{u}_j^\top \mathbf{F}_{j,i} c_i \mathbf{u}_i]_T + [\mathbf{x}_j^\top \mathbf{F}_{j,i} c_i \mathbf{u}_i]_T \\
&\quad - [\mathbf{x}_i^\top \mathbf{F}_{i,j} c_j \mathbf{u}_j]_T + [\mathbf{x}_i^\top \mathbf{F}_{i,j} \mathbf{x}_j]_T \\
&= \left[ \sum_{i,j \in [\ell]} \mathbf{x}_i^\top \mathbf{F}_{i,j} \mathbf{x}_j \right]_T .
\end{align*}
$$

Then, for the change in $c_i$, the probability to abort during SetUp is $1/p$ for all $i \in [\ell]$ independently. Then, as long as $\mathbf{u}_i$ and $\tilde{\mathbf{u}}_i$ are indistinguishable, so will be Game 0 and Game 1. Now, $\tilde{\mathbf{u}}_i$ will exist as long as $c_i$ has an inverse, which it will since $c_i \neq 0$, and given that $\mathbf{u}_i$ is sampled uniformly at random in $\mathbb{Z}_p^n$ and used only once (we are proving one selective security), then $\mathbf{u}_i$ and $\tilde{\mathbf{u}}_i$ are computationally indistinguishable. Therefore, for any PPT adversary $\mathcal{A}'$, $\text{Adv}_{01}(\mathcal{A}') \le \ell/p$.

### Game 2.
In this Game we are substituting the IPFE algorithms (IPFE.SetUp, IPFE.Enc, IPFE.KeyGen) used to compute $d_{i,j}$ which we do not modify, by their corresponding simulators (IPFE.SetUpSim, IPFE.EncSim, IPFE.KeyGenSim), so distinguishing between games would imply an adversary breaking 1-SEL-SIM security for IPFE.

More formally, we prove in Lemma 2 that for any PPT adversary $\mathcal{A}'$, there exists a PPT adversary $\mathcal{B}$ such that $\text{Adv}_{12}(\mathcal{A}') \le \ell^2 \cdot \text{Adv}_{\text{IPFE}}^{\text{FH-SIM}}(\mathcal{B})$. The intuition is that through the use of a Hybrid argument, we swap in the simulators for every $d_{i,j}$ with $i, j \in [\ell]$.

### Game 3.
In this Game we change the construction of $d_{i,j}$, more specifically we swap $\mathbf{w}_{i,j}^\top (\tilde{\mathbf{u}}_j^\top \mathbf{F}_{j,i}) / (\mathbf{F}_{i,j} \tilde{\mathbf{u}}_j)$ for a random value $\tilde{w}_{i,j}$, as long as $\mathbf{F}_{j,i} \neq \mathbf{0}$ or $\mathbf{F}_{i,j} \neq \mathbf{0}$. Otherwise we keep the value at 0. First we show that coherence is held. Indeed,

$$
\begin{align*}
[zk_F]_T - \sum_{i,j \in [\ell]} [d_{i,j}]_T &= \\
&= \left[ \sum_{i,j \in [\ell]} \mathbf{w}_{i,j}^\top \left( \frac{\tilde{\mathbf{u}}_j^\top \mathbf{F}_{j,i}}{\mathbf{F}_{i,j} \tilde{\mathbf{u}}_j} \right) - \sum_{i,j \in [\ell]} \left( \mathbf{w}_{i,j} + c_j \left( c_i(\mathbf{u}_i - \tilde{\mathbf{u}}_i) \right) \right)^\top \left( \frac{\tilde{\mathbf{u}}_j^\top \mathbf{F}_{j,i}}{\mathbf{F}_{i,j} \tilde{\mathbf{u}}_j} \right) \right]_T \\
&= \left[ \sum_{i,j \in [\ell]} c_j \left( c_i(\mathbf{u}_i - \tilde{\mathbf{u}}_i) \right)^\top \left( \frac{\tilde{\mathbf{u}}_j^\top \mathbf{F}_{j,i}}{\mathbf{F}_{i,j} \tilde{\mathbf{u}}_j} \right) \right]_T ,
\end{align*}
$$

$$
\begin{align*}
[zk_F]_T - \sum_{i,j \in [\ell]} [\tilde{d}_{i,j}]_T &= \left[ \sum_{i,j \in [\ell]} \tilde{w}_{i,j} - \sum_{i,j \in [\ell]} \tilde{w}_{i,j} + c_j \left( c_i(\mathbf{u}_i - \tilde{\mathbf{u}}_i) \right)^\top \left( \frac{\tilde{\mathbf{u}}_j^\top \mathbf{F}_{j,i}}{\mathbf{F}_{i,j} \tilde{\mathbf{u}}_j} \right) \right]_T \\
&= \left[ \sum_{i,j \in [\ell]} c_j \left( c_i(\mathbf{u}_i - \tilde{\mathbf{u}}_i) \right)^\top \left( \frac{\tilde{\mathbf{u}}_j^\top \mathbf{F}_{j,i}}{\mathbf{F}_{i,j} \tilde{\mathbf{u}}_j} \right) \right]_T .
\end{align*}
$$
Then, since each $w_{i,j}$ is sampled uniformly at random in $\mathbb{Z}_p^{2n}$, as long as the adversary has access to less than $2n$ different samples of $w_{i,j}^\top \begin{pmatrix} \tilde{u}_j^\top F_{j,i} \\ F_{i,j} \tilde{u}_j \end{pmatrix}$, it is still indistinguishable from random due to the remaining entropy of $w_{i,j}$. This is an argument used in [2] to show that their multi-input inner-product scheme is simulation sound. Therefore, for any PPT adversary $\mathcal{A}'$, $\text{Adv}_{23}(\mathcal{A}') = 0$.

**Game 4.** In this Game we finish the simulation by changing one last time the construction of $d_{i,j}$. More specifically we change $d_{i,j}$ from $\tilde{w}_{i,j} + c_j \begin{pmatrix} \tilde{c}t_{x_i} \\ c_i(u_i - \tilde{u}_i) \end{pmatrix}^\top \begin{pmatrix} \tilde{u}_j^\top F_{j,i} \\ F_{i,j} \tilde{u}_j \end{pmatrix}$ to $\tilde{w}_{i,j} + \tilde{c}t_{x_j}^\top F_{j,i} \tilde{c}t_{x_i}$ and modify $zk_F$ from $\sum_{i,j \in [\ell]} \tilde{w}_{i,j}$ to $v + \sum_{i,j \in [\ell]} \tilde{w}_{i,j}$ to maintain coherence. Notably, it is in this step where the function-hiding property of the underlying IPFE scheme is relevant since we can run the key generation simulator only knowing the desired output, and no other information about the linear function. It is also in this change where the “interweaving” of the IPFE ciphertexts commented in the technical overview can be seen.

Firstly, we show that coherence is held. Indeed, in Game 3 we have

$$ \widetilde{zk_F}^{(3)} = \sum_{i,j \in [\ell]} \tilde{d}_{i,j}^{(3)} - c_j \begin{pmatrix} \tilde{c}t_{x_i} \\ x_i \end{pmatrix}^\top \begin{pmatrix} \tilde{u}_j^\top F_{j,i} \\ F_{i,j} \tilde{u}_j \end{pmatrix} $$

since $c_i(u_i - \tilde{u}_i) = x_i$ by definition of $\tilde{u}_i$. and in Game 4 we get

$$
\begin{align*}
\sum_{i,j \in [\ell]} \tilde{d}_{i,j}^{(4)} - c_j \begin{pmatrix} \tilde{c}t_{x_i} \\ x_i \end{pmatrix}^\top \begin{pmatrix} \tilde{u}_j^\top F_{j,i} \\ F_{i,j} \tilde{u}_j \end{pmatrix} &= \\
&= \sum_{i,j \in [\ell]} \tilde{d}_{i,j}^{(4)} - ((c_j c_i u_i)^\top (u_j - c_j^{-1} x_j)^\top F_{i,j} + c_j x_i F_{i,j} (u_j - c_j^{-1} x_j)) \\
&= \sum_{i,j \in [\ell]} \tilde{d}_{i,j}^{(4)} - (c_j u_j^\top F_{j,i} c_i u_i - x_j^\top F_{j,i} c_i u_i + x_i^\top F_{i,j} c_j u_j - x_i^\top F_{i,j} x_j) \\
&= \sum_{i,j \in [\ell]} \tilde{w}_{i,j} + \tilde{c}t_{x_j}^\top F_{j,i} \tilde{c}t_{x_i} - (\tilde{c}t_{x_j}^\top F_{j,i} \tilde{c}t_{x_i} - x_i^\top F_{i,j} x_j) \\
&= v + \sum_{i,j \in [\ell]} \tilde{w}_{i,j} \\
&= \widetilde{zk_F}^{(4)}.
\end{align*}
$$

It is in this equality that we see the “interweaving” at work, since $x_j^\top F_{j,i} c_i u_i$ and $x_i^\top F_{i,j} c_j u_j$ get canceled only because we are adding for all $i, j \in [\ell]$. Then, as long as $\tilde{d}_{i,j}^{(3)}$ and $\tilde{d}_{i,j}^{(4)}$ are indistinguishable, then $\widetilde{zk_F}^{(3)}$ and $\widetilde{zk_F}^{(4)}$ are also indistinguishable. To complete the argument, we note that since $\tilde{w}_{i,j}$ is sampled uniformly at random, then $\tilde{d}_{i,j}^{(3)}$ is indistinguishable from $\tilde{w}_{i,j}$ which in turn is indistinguishable from $\tilde{d}_{i,j}^{(4)}$. All in all, for any PPT adversary $\mathcal{A}'$, $\text{Adv}_{34}(\mathcal{A}') = 0$.
Finally, adding it all up, and considering that Game 0 is the real experiment and Game 4 is the ideal experiment, we get

$$ \begin{aligned} \mathrm{Adv}_{\mathrm{MIQFE}}^{\mathrm{MI-SIM}}(\mathcal{A}) &= \mathrm{Adv}_{01}(\mathcal{A}) + \mathrm{Adv}_{12}(\mathcal{A}) + \mathrm{Adv}_{23}(\mathcal{A}) + \mathrm{Adv}_{34}(\mathcal{A}) \\ &\le \ell^2 \cdot \mathrm{Adv}_{\mathrm{IPFE}}^{\mathrm{FH-SIM}}(\mathcal{B}) + \frac{\ell}{p}. \end{aligned} $$

# 4 Function-Hiding Inner-Product Functional Encryption Instantiation

In the previous section we give an instantiation of a one selective multi-input simulation secure MIQFE based on a one selective function-hiding simulation secure IPFE scheme. As said in Section 1.2, such a scheme does not exist in the standard model, so in this section we give a function-hiding inner-product functional encryption scheme for bounded-norm inner-product functionalities and prove it to be one selective function-hiding simulation secure. As explained in Section 1.3, we will construct the scheme by layering tow instances of the scheme [1, Section 3].

We will first describe the family of functions we want to cover. Let $\mathcal{F}_{\mathrm{IP}}^n : [0, B]^n \to [0, n \cdot B^2]$ be the family of functions such that a function $\mathbf{y} \in \mathcal{F}_{\mathrm{IP}}^n$ is defined by a vector in $[0, B]$ and applied to $\mathbf{z}$ gives $\mathbf{y}(\mathbf{z}) := \mathbf{z}^{\top}\mathbf{y}$.

## 4.1 Description of the Scheme

We define our scheme for the family of functions $\mathcal{F}_{\mathrm{IP}}^n$ as defined above as follows.

### Encryption Scheme 4 (Function-hiding IPFE Scheme)

- **IPFE. SetUp(1^\kappa, \mathcal{F}_{\mathrm{IP}}^n)**: Sample $\mathcal{PG} = (\mathbb{G}_1, \mathbb{G}_2, \mathbb{G}_T, p, P_1, P_2, e) \leftarrow \mathrm{PGGen}(1^\kappa)$, $\mathbf{u} \stackrel{\$}{\leftarrow} \mathbb{Z}_p^{n+1}$ and $\mathbf{v} \stackrel{\$}{\leftarrow} \mathbb{Z}_p^n$. Output IPFE.param = $\mathcal{PG}$ and IPFE.msk = $(\mathbf{u}, \mathbf{v})$.

- **IPFE. Enc(IPFE.msk, \mathbf{x})**: Sample $c \stackrel{\$}{\leftarrow} \mathbb{Z}_p$. Compute

$$ ct_1 := [c]_1 \in \mathbb{G}_1; ct_2 := \left[ \begin{pmatrix} -\mathbf{v}^{\top}\mathbf{x} \\ \mathbf{x} \end{pmatrix} + c \cdot \mathbf{u} \right]_1 \in \mathbb{G}_1^{n+1} $$

Output IPFE.c<sub>x</sub> := (ct<sub>1</sub>, ct<sub>2</sub>).

- **IPFE. KeyGen(IPFE.msk, \mathbf{y})**: Sample $t \stackrel{\$}{\leftarrow} \mathbb{Z}_p$. Compute

$$ sk_1 := \left[ -\mathbf{u}^{\top} \begin{pmatrix} t \\ \mathbf{y} + t \cdot \mathbf{v} \end{pmatrix} \right]_2 \in \mathbb{G}_2; sk_2 := \left[ \begin{pmatrix} t \\ \mathbf{y} + t \cdot \mathbf{v} \end{pmatrix} \right]_2 \in \mathbb{G}_2^{n+1} $$

Output IPFE.sk<sub>y</sub> := (sk<sub>1</sub>, sk<sub>2</sub>).

- **IPFE.Dec(IPFE.c<sub>x</sub>, IPFE.sk<sub>y</sub>)**: Compute $[v]_T := e(ct_1, sk_1) + e(ct_2, sk_2)$. Output $\log([v]_T)$ if $v \in [0, n \cdot B^2]$ and $\perp$ otherwise.

*Remark 2.* Note that this scheme is easily transformable into a scheme for the family of functions $\tilde{\mathcal{F}}_{\mathrm{IP}}^n$ by eliminating the discrete logarithm at the end of decryption and not bounding $\mathbf{x}$ and $\mathbf{y}$.
<figure><img src="image_3.png" /><figcaption>Fig. 2. Games for the security proof of the IPFE from Encryption Scheme 4.</figcaption></figure>

## 4.2 Correctness and Security

**Proposition 2.** The IPFE scheme defined in Encryption Scheme 4 is a correct functional encryption scheme for $\mathcal{F}_{\text{IP}}^n$.

For the proof we refer to Appendix B.

**Theorem 2.** The IPFE scheme described in 4 is one selective function-hiding simulation secure, if the DDH assumption holds in group $G_2$. In other words, for any PPT adversary $\mathcal{A}$ there exists a PPT adversary $\mathcal{B}$ such that

$$ \text{Adv}_{\text{IPFE}}^{\text{FH-SIM}}(\mathcal{A}) \le 2Q_{sk} \cdot \text{Adv}_{\mathbb{G}_2}^{\text{DDH}}(\mathcal{B}) + \frac{1}{p} + \frac{2Q_{sk}}{p-1}. $$

where $Q_{sk}$ denotes the number of queries performed to KeyGen.

*Proof.* Let $\mathcal{A}$ be a PPT adversary playing the function-hiding 1-SEL-SIM security game for IPFE, and let $\kappa \in \mathbb{N}$ be a security parameter. We will prove the result through a series of games $\text{Game } i$ for $i \in \{0, 1, 2\}$, defined in Figure 2 with changes in Game $i+1$ being over Game $i$. We show that $\text{Exp}_{\mathcal{A}}^{\text{real}}(1^{\kappa}) = \text{Game 0} \approx_s \text{Game 1} \approx_c \text{Game 2} = \text{Exp}_{\mathcal{A},S}^{\text{ideal}}(1^{\kappa})$.

Let $\mathcal{C}'$ be a challenger that chooses $b \in \{0, 1\}$ uniformly at random. If $b=0$ it interacts with a PPT adversary $\mathcal{A}'$ as in Game $i$, otherwise it interacts as in Game $i+1$. At the end of the interaction, $\mathcal{A}'$ will make its guess $\tilde{b} \in \{0, 1\}$. For $i=0, 1$, we define $\text{Adv}_{i(i+1)}(\mathcal{A}') := |\Pr[\tilde{b}=1|b=0] - \Pr[\tilde{b}=1|b=1]|$.

*Game 0.* This is the real experiment for FH 1-SEL-SIM security for IPFE.

*Game 1.* In this Game we change the construction of $ct_2$ from $\left[ \begin{pmatrix} -v^\top x \\ x \end{pmatrix} + c \cdot u \right]_1$ to $[c \cdot u]$ and to keep coherence we must change $sk_1$ from $sk_1$
$sk_1 = [-\mathbf{u}^\top \begin{pmatrix} \mathbf{t} \\ \mathbf{y} + \mathbf{V}t \end{pmatrix}]_2$ to $[-\mathbf{u}^\top \begin{pmatrix} \mathbf{t} \\ \mathbf{y} + \mathbf{V}t \end{pmatrix} + c^{-1} \cdot \mathbf{x}^\top \mathbf{y}]_2$. To be able to make this change we move the sampling of $c$ to the Setup and abort if $c = 0$.

This change can also be seen as swapping $\mathbf{u}$ for $\tilde{\mathbf{u}} := \mathbf{u} - c^{-1} \cdot \begin{pmatrix} -\mathbf{v}^\top \mathbf{x} \\ \mathbf{x} \end{pmatrix}$, since

$$ \left[ \begin{pmatrix} -\mathbf{v}^\top \mathbf{x} \\ \mathbf{x} \end{pmatrix} + c \cdot \tilde{\mathbf{u}} \right]_1 = \left[ \begin{pmatrix} -\mathbf{v}^\top \mathbf{x} \\ \mathbf{x} \end{pmatrix} + c \cdot \left( \mathbf{u} - c^{-1} \cdot \begin{pmatrix} -\mathbf{v}^\top \mathbf{x} \\ \mathbf{x} \end{pmatrix} \right) \right]_1 = [c \cdot \mathbf{u}]_1, $$

$$ \begin{aligned} \left[-\tilde{\mathbf{u}}^\top \begin{pmatrix} \mathbf{t} \\ \mathbf{y} + t \cdot \mathbf{v} \end{pmatrix}\right]_2 &= \left[-\left(\mathbf{u} - c^{-1} \cdot \begin{pmatrix} -\mathbf{v}^\top \mathbf{x} \\ \mathbf{x} \end{pmatrix}\right)^\top \begin{pmatrix} \mathbf{t} \\ \mathbf{y} + t \cdot \mathbf{v} \end{pmatrix}\right]_2 \\ &= \left[ -\mathbf{u}^\top \begin{pmatrix} \mathbf{t} \\ \mathbf{y} + t \cdot \mathbf{v} \end{pmatrix} - t \cdot c^{-1} \cdot (\mathbf{v}^\top \mathbf{x}) + c^{-1} \cdot \mathbf{x}^\top \mathbf{y} \right. \\ & \qquad \left. + t \cdot c^{-1} \cdot \mathbf{x}^\top \mathbf{v} \right]_2 \\ &= \left[-\mathbf{u}^\top \begin{pmatrix} \mathbf{t} \\ \mathbf{y} + t \cdot \mathbf{v} \end{pmatrix} + c^{-1} \cdot \mathbf{x}^\top \mathbf{y} \right]_2, \end{aligned} $$

and coherence is indeed held given that

$$ e(\tilde{c}t_1, sk_1) = \left[ -c \cdot \mathbf{u}^\top \begin{pmatrix} \mathbf{t} \\ \mathbf{y} + t \cdot \mathbf{v} \end{pmatrix} + \mathbf{x}^\top \mathbf{y} \right]_T, $$

$$ e(\tilde{c}t_2, sk_2) = \left[ c \cdot \mathbf{u}^\top \begin{pmatrix} \mathbf{t} \\ \mathbf{y} + t \cdot \mathbf{v} \end{pmatrix} \right]_T $$

which gives $[v]_T = [\mathbf{x}^\top \mathbf{y}]_T$ during decryption.

First, for the change in $c$, since we are proving one selective simulation its sampling can be moved to Setup, and the protocol will abort with probability $1/p$. Then, as long as $\mathbf{u}$ and $\tilde{\mathbf{u}}$ are indistinguishable, so will be Game 0 and Game 1. Now, $\tilde{\mathbf{u}}$ will exist as long as $c$ has an inverse, which it will since $c \neq 0$, and given that $\mathbf{u}$ is sampled uniformly at random in $\mathbb{Z}_p^{n+1}$ and used only once (we are proving one selective security), then $\mathbf{u}$ and $\tilde{\mathbf{u}}$ are indistinguishable. Therefore, for any PPT adversary $\mathcal{A}'$, $\text{Adv}_{01}(\mathcal{A}') \le 1/p$.

**Game 2.** In this Game we finish the simulation by changing in both $sk_1$ and $sk_2$ the vector $\begin{pmatrix} t \\ \mathbf{y} + t \cdot \mathbf{v} \end{pmatrix}$ to $\begin{pmatrix} t \\ t \cdot \mathbf{v} \end{pmatrix}$. This means that the encryption simulation can be performed without knowledge of $\mathbf{x}$ and the key generation simulation can be performed only knowing the output $\mathbf{x}^\top \mathbf{y}$.

More formally, we prove in Lemma 3 that for any PPT adversary $\mathcal{A}'$ there exists a PPT adversary $\mathcal{B}$ such that $\text{Adv}_{12}(\mathcal{A}') \le 2Q_{sk} \cdot \text{Adv}_{\mathbb{G}_2}^{\text{DDH}} + 2Q_{sk}/p - 1$. The intuition is that using a Hybrid argument through the queries asked we use the $n$-fold DDH assumption (see Appendix A) to swap $t \cdot \mathbf{v}$ for a value sampled uniformly at random so we can remove $\mathbf{y}$.
<table><caption>**Table 4.** Efficiency estimates for our MIQFE and IPFE constructions.</caption><thead><tr><th></th><th>Secret key</th><th>Ciphertext</th><th>Functional key</th></tr></thead><tbody><tr><td>Generic MIQFE</td><td>ℓ² · IPFE<sub>msk</sub><sup>2n</sup> + ℓ(1 + n)|p| + ℓ²2n|p|</td><td>ℓ · IPFE<sub>c<sub>x</sub></sub><sup>2n</sup> + n|p|</td><td>ℓ² · IPFE<sub>sk<sub>y</sub></sub><sup>2n</sup> + |p|</td></tr><tr><td>IPFE</td><td>(2n + 1)|p|</td><td>(n + 2)|G<sub>1</sub>|</td><td>(n + 2)|G<sub>2</sub>|</td></tr><tr><td>Concrete MIQFE</td><td>ℓ²(4n + 1)|p| + ℓ(1 + n)|p| + ℓ²2n|p|</td><td>ℓ(2n + 2)|G<sub>1</sub>| + n|p|</td><td>ℓ² · (2n + 2)|G<sub>2</sub>| + |p|</td></tr></tbody></table>

Finally, adding it all up, and considering that Game 0 is the real experiment and Game 2 is the ideal experiment, we get

$$ \mathrm{Adv}_{\mathrm{IPFE}}^{\mathrm{FH-SIM}}(\mathcal{A}) = \mathrm{Adv}_{01}(\mathcal{A}) + \mathrm{Adv}_{12}(\mathcal{A}) \le 2Q_{sk} \cdot \mathrm{Adv}_{\mathbb{G}_2}^{\mathrm{DDH}}(\mathcal{B}) + \frac{1}{p} + \frac{2Q_{sk}}{p-1}. $$

## 5 Efficiency Considerations

For any generic function-hiding simulation secure IPFE, our MIQFE scheme supporting $ℓ$ inputs of $n$ coefficient each, needs for $ℓ^2$ instances of IPFE, $ℓ$ for each input to handle the noise generated with combining with each of the other inputs. A part from that, the master secret key needs for $\{u_i\}_{i \in [\ell]} \in \mathbb{Z}_p^n$, $\{c_i\}_{i \in [\ell]} \in \mathbb{Z}_p$ and $\{w_{i,j} \in [\ell]\} \in \mathbb{Z}_p^{2n}$; the ciphertexts need for $ct_i \in \mathbb{Z}_p^n$; and the functional keys need for $zk_F \in \mathbb{Z}_p$.

Our function-hiding IPFE scheme supporting $n$ coefficients, needs in the master secret key for $u \in \mathbb{Z}_p^{n+1}$ and $v \in \mathbb{Z}_p^n$; the ciphertext for $ct_1 \in G_1$ and $ct_2 \in G_1^{n+1}$; and the functional keys need for $sk_1 \in G_2$ and $sk_2 \in G_2^{n+1}$, which also gives us concrete efficiency estimates of a concrete instantiation of our MIQFE scheme. All this is shown in Table 4, where $IPFE_s^k$ denotes the size of the element referred by $s$ of the base IPFE scheme for $k$ coefficients.

## 6 Conclusion

These results may inspire further work in the subject. An interesting direction to follow would be to improve the ciphertext efficiency of the scheme, to see if $O(nℓ)$ is possible while satisfying simulation security. Another noteworthy direction to explore is to look for a transformation directly from single input QFE to MIQFE, so as to try to avoid pairing based schemes, which seem inevitable when using function-hiding IPFE.

Finally, our results can be of use for applications where a simulation secure MIQFE is needed. As an example, recently a simulation secure MIPFE was used to instantiate an efficient randomized functional encryption scheme able to respond differentially private linear queries [9]. As such, a randomized functional encryption scheme able to respond differentially private quadratic queries is a potential future application.
**Acknowledgements** We thank Hieu Phan for the useful and helpful discussions concerning this work. This work was funded by the French ANR Project ANR-23-CE39-0009-06 TRUST, the France 2030 ANR Project ANR-22-PECY-003 SecureCompute and the French ANR Project ANR-21-CE39-0006 SANGRIA.

## References

1. Abdalla, M., Bourse, F., Caro, A.D., Pointcheval, D.: Simple functional encryption schemes for inner products. In: Katz, J. (ed.) Public-Key Cryptography – PKC 2015. pp. 733–751. Springer, Berlin, Heidelberg (2015). https://doi.org/10.1007/978-3-662-46447-2_33

2. Abdalla, M., Catalano, D., Fiore, D., Gay, R., Ursu, B.: Multi-input functional encryption for inner products: Function-hiding realizations and constructions without pairings. Cryptology ePrint Archive, Paper 2017/972 (2017). https://doi.org/10.1007/978-3-319-96884-1_20, https://eprint.iacr.org/2017/972

3. Abdalla, M., Catalano, D., Fiore, D., Gay, R., Ursu, B.: Multi-input functional encryption for inner products: Function-hiding realizations and constructions without pairings. In: Shacham, H., Boldyreva, A. (eds.) Advances in Cryptology – CRYPTO 2018. pp. 597–627. Springer International Publishing, Cham (2018). https://doi.org/10.1007/978-3-319-96884-1_20

4. Abdalla, M., Gay, R., Raykova, M., Wee, H.: Multi-input inner-product functional encryption from pairings. In: Coron, J.S., Nielsen, J.B. (eds.) Advances in Cryptology – EUROCRYPT 2017. pp. 601–626. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-56620-7_21

5. Agrawal, S., Gorbunov, S., Vaikuntanathan, V., Wee, H.: Functional encryption: New perspectives and lower bounds. In: Canetti, R., Garay, J.A. (eds.) Advances in Cryptology – CRYPTO 2013. pp. 500–518. Springer Berlin Heidelberg, Berlin, Heidelberg (2013). https://doi.org/10.1007/978-3-642-40084-1_28

6. Agrawal, S., Goyal, R., Tomida, J.: Multi-input quadratic functional encryption from pairings. In: Malkin, T., Peikert, C. (eds.) Advances in Cryptology – CRYPTO 2021. pp. 208–238. Springer International Publishing, Cham (2021). https://doi.org/10.1007/978-3-030-84259-8_8

7. Agrawal, S., Goyal, R., Tomida, J.: Multi-input quadratic functional encryption: Stronger security, broader functionality. In: Kiltz, E., Vaikuntanathan, V. (eds.) Theory of Cryptography. pp. 711–740. Springer Nature Switzerland, Cham (2022). https://doi.org/10.1007/978-3-031-22318-1_25

8. Agrawal, S., Libert, B., Stehlé, D.: Fully secure functional encryption for inner products, from standard assumptions. In: Robshaw, M., Katz, J. (eds.) Advances in Cryptology – CRYPTO 2016. pp. 333–362. Springer, Berlin, Heidelberg (2016). https://doi.org/10.1007/978-3-662-53015-3_12

9. Alborch Escobar, F., Canard, S., Laguillaumie, F., Phan, D.H.: Computational differential privacy for encrypted databases supporting linear queries. Proceedings on Privacy Enhancing Technologies 2024(4), 583–604 (2024). https://doi.org/10.56553/popets-2024-0131

10. Ananth, P., Sahai, A.: Projective arithmetic functional encryption and indistinguishability obfuscation from degree-5 multilinear maps. In: Coron, J.S., Nielsen, J.B. (eds.) Advances in Cryptology – EUROCRYPT 2017. pp. 152–181. Springer International Publishing, Cham (2017). https://doi.org/10.1007/978-3-319-56620-7_6
11. Baltico, C.E.Z., Catalano, D., Fiore, D., Gay, R.: Practical functional encryption for quadratic functions with applications to predicate encryption. In: Katz, J., Shacham, H. (eds.) Advances in Cryptology – CRYPTO 2017. pp. 67–98. Springer International Publishing, Cham (2017). https://doi.org/10.1007/978-3-319-63688-7_3

12. Benhamouda, F., Bourse, F., Lipmaa, H.: Cca-secure inner-product functional encryption from projective hash functions. In: Fehr, S. (ed.) Public-Key Cryptography – PKC 2017. pp. 36–66. Springer, Berlin, Heidelberg (2017). https://doi.org/10.1007/978-3-662-54388-7_2

13. Bishop, A., Jain, A., Kowalczyk, L.: Function-hiding inner product encryption. In: Iwata, T., Cheon, J.H. (eds.) Advances in Cryptology – ASIACRYPT 2015. pp. 470–491. Springer, Berlin, Heidelberg (2015). https://doi.org/10.1007/978-3-662-48797-6_20

14. Boneh, D., Sahai, A., Waters, B.: Functional encryption: Definitions and challenges. In: Ishai, Y. (ed.) Theory of Cryptography. pp. 253–273. Springer, Berlin, Heidelberg (2011). https://doi.org/10.1007/978-3-642-19571-6_16

15. Castagnos, G., Laguillaumie, F., Tucker, I.: Practical fully secure unrestricted inner product functional encryption modulo p. In: Peyrin, T., Galbraith, S. (eds.) Advances in Cryptology – ASIACRYPT 2018. pp. 733–764. Springer, Cham (2018). https://doi.org/10.1007/978-3-030-03329-3_25

16. Datta, P., Dutta, R., Mukhopadhyay, S.: Functional encryption for inner product with full function privacy. In: Cheng, C.M., Chung, K.M., Persiano, G., Yang, B.Y. (eds.) Public-Key Cryptography–PKC 2016. pp. 164–195. Springer, Berlin, Heidelberg (2016). https://doi.org/10.1007/978-3-662-49384-7_7

17. Gay, R.: A new paradigm for public-key functional encryption for degree-2 polynomials. In: Kiayias, A., Kohlweiss, M., Wallden, P., Zikas, V. (eds.) Public-Key Cryptography – PKC 2020. pp. 95–120. Springer International Publishing, Cham (2020). https://doi.org/10.1007/978-3-030-45374-9_4

18. Goldwasser, S., Gordon, S.D., Goyal, V., Jain, A., Katz, J., Liu, F.H., Sahai, A., Shi, E., Zhou, H.S.: Multi-input functional encryption. In: Nguyen, P.Q., Oswald, E. (eds.) Advances in Cryptology – EUROCRYPT 2014. pp. 578–602. Springer Berlin Heidelberg, Berlin, Heidelberg (2014). https://doi.org/10.1007/978-3-642-55220-5_32

19. Herold, G., Kiltz, E., Ràfols, C., Villar, J.: An algebraic framework for diffie-hellman assumptions. Journal of Cryptology **30**(1), 242–288 (2017). https://doi.org/10.1007/s00145-015-9220-6

20. Kim, S., Lewi, K., Mandal, A., Montgomery, H., Roy, A., Wu, D.J.: Function-hiding inner product encryption is practical. In: Catalano, D., De Prisco, R. (eds.) Security and Cryptography for Networks. pp. 544–562. Springer International Publishing, Cham (2018). https://doi.org/10.1007/978-3-319-98113-0_29

21. Kim, S., Kim, J., Seo, J.H.: A new approach to practical function-private inner product encryption. Theoretical Computer Science **783**, 22–40 (2019). https://doi.org/https://doi.org/10.1016/j.tcs.2019.03.016

22. Lin, H.: Indistinguishability obfuscation from sxdh on 5-linear maps and locality-5 prgs. In: Katz, J., Shacham, H. (eds.) Advances in Cryptology – CRYPTO 2017. pp. 599–629. Springer International Publishing, Cham (2017). https://doi.org/10.1007/978-3-319-63688-7_20

23. Lin, H., Tessaro, S.: Indistinguishability obfuscation from trilinear maps and block-wise local prgs. In: Katz, J., Shacham, H. (eds.) Advances in Cryptology – CRYPTO 2017. pp. 630–660. Springer International Publishing, Cham (2017). https://doi.org/10.1007/978-3-319-63688-7_21
24. O'Neill, A.: Definitional issues in functional encryption. Cryptology ePrint Archive, Paper 2010/556 (2010), https://eprint.iacr.org/2010/556

25. Shen, E., Shi, E., Waters, B.: Predicate privacy in encryption systems. In: Reingold, O. (ed.) Theory of Cryptography. pp. 457–473. Springer Berlin Heidelberg, Berlin, Heidelberg (2009). https://doi.org/10.1007/978-3-642-00457-5_27

26. Tomida, J., Abe, M., Okamoto, T.: Efficient functional encryption for inner-product values with full-hiding security. In: Bishop, M., Nascimento, A.C.A. (eds.) Information Security. pp. 408–425. Springer International Publishing, Cham (2016). https://doi.org/10.1007/978-3-319-45871-7_24

27. Ünal, A.: Impossibility results for lattice-based functional encryption schemes. In: Canteaut, A., Ishai, Y. (eds.) Advances in Cryptology – EUROCRYPT 2020. pp. 169–199. Springer International Publishing, Cham (2020). https://doi.org/10.1007/978-3-030-45721-1_7

28. Zhao, Q., Zeng, Q., Liu, X., Xu, H.: Simulation-based security of function-hiding inner product encryption. Science China. Information Sciences 61(4), 048102 (2018)

## A The DDH Assumption

Let $p$ be a prime number, we define the following distribution, using the framework from [19]. The DDH distribution over $\mathbb{Z}_p^2$ samples $t \stackrel{\$}{\leftarrow} \mathbb{Z}_p$ and outputs $t := (1, t)^\top$.

**Definition 7.** Let $\kappa \in \mathbb{N}_{>0}$ be a security parameter and $s \in \{1, 2, T\}$. For any PPT adversary $\mathcal{A}$ we define the following advantage

$$ \mathrm{Adv}_{\mathbb{G}_s}^{\mathrm{DDH}}(\mathcal{A}) := |\mathrm{Pr}[1 \leftarrow \mathcal{A}(1^\kappa, \mathcal{PG}, [t]_s, [tr]_s)] - \mathrm{Pr}[1 \leftarrow \mathcal{A}(1^\kappa, \mathcal{PG}, [t]_s, [w]_s)]|, $$

where the probability is taken over $\mathcal{PG} \leftarrow \mathrm{PGGen}(1^\kappa)$, $t \leftarrow \mathrm{DDH}$, $r \stackrel{\$}{\leftarrow} \mathbb{Z}_p$ and $w \stackrel{\$}{\leftarrow} \mathbb{Z}_p^2$. We say that the Decisional Diffie-Hellman (DDH) assumption holds if for all PPT adversaries $\mathcal{A} \mathrm{Adv}_{\mathbb{G}_s}^{\mathrm{DDH}}(\mathcal{A}) \le \mathrm{neq}(\kappa)$.

We are also interested in the case where $Q$ independent queries are asked, with same $t$ but different $r_i$, and its relationship to the base DDH.

**Definition 8.** Let $\kappa \in \mathbb{N}_{>0}$ be a security parameter and $s \in \{1, 2, T\}$. For any PPT adversary $\mathcal{A}$ we define the following advantage

$$ \mathrm{Adv}_{\mathbb{G}_s}^{Q-\mathrm{DDH}}(\mathcal{A}) := |\mathrm{Pr}[1 \leftarrow \mathcal{A}(1^\kappa, \mathcal{PG}, [t]_s, [tr^\top]_s)] - \mathrm{Pr}[1 \leftarrow \mathcal{A}(1^\kappa, \mathcal{PG}, [t]_s, [W]_s)]|, $$

where the probability is taken over $\mathcal{PG} \leftarrow \mathrm{PGGen}(1^\kappa)$, $t \leftarrow \mathrm{DDH}$, $r \stackrel{\$}{\leftarrow} \mathbb{Z}_p^Q$ and $W \stackrel{\$}{\leftarrow} \mathbb{Z}_p^{2 \times Q}$. We say that the $Q$-fold Decisional Diffie-Hellman ($Q$-DDH) assumption holds if for all PPT adversaries $\mathcal{A} \mathrm{Adv}_{\mathbb{G}_s}^{Q-\mathrm{DDH}}(\mathcal{A}) \le \mathrm{neq}(\kappa)$.

More concretely we will use the random self-reducibility of the $Q$-fold DDH assumption.
**Lemma 1 (Lemma 1,[19]).** Let $Q > 1$, and $s \in \{1, 2, T\}$. Then, for any PPT adversary $\mathcal{A}$ there exists a PPT adversary $\mathcal{B}$ such that

$$ \mathrm{Adv}_{\mathrm{G}_s}^{Q-\mathrm{DDH}}(\mathcal{A}) \le \mathrm{Adv}_{\mathrm{G}_s}^{\mathrm{DDH}}(\mathcal{B}) + \frac{1}{p-1}, $$

where the probability is taken over $\mathcal{PG} \leftarrow \mathrm{PGGen}(1^\kappa)$, $t \leftarrow \mathrm{DDH}$, $r \stackrel{\$}{\leftarrow} \mathbb{Z}_p^Q$ and $\mathbf{W} \stackrel{\$}{\leftarrow} \mathbb{Z}_p^{2 \times Q}$.

# B Proofs of Correctness

## B.1 MIQFE scheme

**Proposition 3.** The MIQFE scheme defined in Section 3.1 is a correct multi-input functional encryption scheme for $\mathcal{F}_{Q,B}^{n,\ell}$ as long as IPFE is a correct scheme for $\tilde{\mathcal{F}}_{\mathrm{IP}}^{2n}$.

*Proof.* For ease of notation and reading we will leave out the $[\cdot]_T$. First we have

$$ \mathbf{ct}_{\mathbf{x}_i}^{\top} \mathbf{F}_{i,j} \mathbf{ct}_{\mathbf{x}_j} = \mathbf{x}_i^{\top} \mathbf{F}_{i,j} \mathbf{x}_j + c_i \mathbf{u}_i^{\top} \mathbf{F}_{i,j} \mathbf{x}_j + \mathbf{x}_i^{\top} \mathbf{F}_{i,j} c_j \mathbf{u}_j + c_i \mathbf{u}_i^{\top} \mathbf{F}_{i,j} c_j \mathbf{u}_j $$

from which we want to cancel out everything but $\mathbf{x}_i^{\top} \mathbf{F}_{i,j} \mathbf{x}_j$.

Let us take a look at $d_{i,j}$. Given that IPFE is a correct scheme for $\mathcal{F}_{\mathrm{IP}}^n$ we have that

$$ \begin{aligned} d_{i,j} &= \left( \mathbf{w}_{i,j} + \begin{pmatrix} c_j \mathbf{ct}_{\mathbf{x}_i} \\ c_j \mathbf{x}_i \end{pmatrix} \right)^{\top} \begin{pmatrix} \mathbf{u}_j^{\top} \mathbf{F}_{j,i} \\ \mathbf{F}_{i,j} \mathbf{u}_j \end{pmatrix} \\ &= \mathbf{w}_{i,j}^{\top} \begin{pmatrix} \mathbf{u}_j^{\top} \mathbf{F}_{j,i} \\ \mathbf{F}_{i,j} \mathbf{u}_j \end{pmatrix} + c_j \mathbf{x}_i^{\top} (\mathbf{u}_j^{\top} \mathbf{F}_{j,i}) + c_j c_i \mathbf{u}_i^{\top} (\mathbf{u}_j^{\top} \mathbf{F}_{j,i}) + c_j \mathbf{x}_i^{\top} \mathbf{F}_{i,j} \mathbf{u}_j \\ &= \mathbf{w}_{i,j}^{\top} \begin{pmatrix} \mathbf{u}_j^{\top} \mathbf{F}_{j,i} \\ \mathbf{F}_{i,j} \mathbf{u}_j \end{pmatrix} + c_j \mathbf{u}_j^{\top} \mathbf{F}_{j,i} \mathbf{x}_i + c_j \mathbf{u}_j^{\top} \mathbf{F}_{j,i} c_i \mathbf{u}_i + \mathbf{x}_i^{\top} \mathbf{F}_{i,j} c_j \mathbf{u}_j. \end{aligned} $$

Note that only the third term of $\mathbf{ct}_{\mathbf{x}_i} \mathbf{F}_{i,j} \mathbf{ct}_{\mathbf{x}_j}$ will cancel out, but at the same time the second and fourth terms of $\mathbf{ct}_{\mathbf{x}_j} \mathbf{F}_{j,i} \mathbf{ct}_{\mathbf{x}_i}$ appear. This means that by adding over all $i, j \in [\ell]$ all cancels out and we get

$$ \sum_{i,j \in [\ell]} \mathbf{ct}_{\mathbf{x}_i}^{\top} \mathbf{F}_{i,j} \mathbf{ct}_{\mathbf{x}_j} - d_{i,j} = \sum_{i,j \in [\ell]} \mathbf{x}_i^{\top} \mathbf{F}_{i,j} \mathbf{x}_j + \sum_{i,j \in [\ell]} \mathbf{w}_{i,j}^{\top} \begin{pmatrix} \mathbf{u}_j^{\top} \mathbf{F}_{j,i} \\ \mathbf{F}_{i,j} \mathbf{u}_j \end{pmatrix} $$

which by construction of $zk_F$ means that

$$ v = \sum_{i,j \in [\ell]} \mathbf{x}_i^{\top} \mathbf{F}_{i,j} \mathbf{x}_j. $$
## B.2 IPFE scheme

**Proposition 4.** The IPFE scheme defined in Encryption Scheme 4 is a correct functional encryption scheme for $\mathcal{F}_{\text{IP}}^n$.

*Proof.* The first pairing operation gives us

$$e(ct_1, sk_1) = \left[ c \cdot (-\mathbf{u})^{\top} \begin{pmatrix} t \\ \mathbf{y} + t \cdot \mathbf{v} \end{pmatrix} \right]_T,$$

and the second pairing operation gives us

$$ \begin{aligned} e(ct_2, sk_2) &= \left[ \left( \begin{pmatrix} -\mathbf{v}^{\top}\mathbf{x} \\ \mathbf{x} \end{pmatrix} + c \cdot \mathbf{u} \right)^{\top} \begin{pmatrix} t \\ \mathbf{y} + t \cdot \mathbf{v} \end{pmatrix} \right]_T \\ &= \left[ -t \cdot \mathbf{v}^{\top}\mathbf{x} + \mathbf{x}^{\top}\mathbf{y} + t \cdot \mathbf{x}^{\top}\mathbf{v} + c \cdot \mathbf{u}^{\top} \begin{pmatrix} t \\ \mathbf{y} + t \cdot \mathbf{v} \end{pmatrix} \right]_T \\ &= \left[ \mathbf{x}^{\top}\mathbf{y} + c \cdot \mathbf{u}^{\top} \begin{pmatrix} t \\ \mathbf{y} + t \cdot \mathbf{v} \end{pmatrix} \right]_T. \end{aligned} $$

This in turn gives us $[v]_T = [\mathbf{x}^{\top}\mathbf{y}]_T$.

# C Proofs of Auxiliary Lemma

## C.1 Proof of Lemma in Section 3

**Lemma 2.** For any PPT adversary $\mathcal{A}'$, there exists a PPT adversary $\mathcal{B}$ such that

$$ \mathrm{Adv}_{12}(\mathcal{A}') \le \ell^2 \cdot \mathrm{Adv}_{\text{IPFE}}^{\text{FH-SIM}}(\mathcal{B}). $$

*Proof.* We will prove the result through a series of Hybrid Games $H_{\eta}^{\iota}$ for $\iota \in [\ell]$ and $\eta \in [\ell]$, defined in Figure 3. For ease of notation we define the lexicographical order ($\mathbb{N}^2, <_L$) where $(a, b) <_L (c, d)$ if and only if $a < c$ or $a = c$ and $b < d$, analogously, $(a, b) >_L (c, d)$ if and only if $a > c$ or $a = c$ and $b > d$. We show that Game 1 $\approx_c H_1^1 \approx_c \dots \approx_c H_1^\ell \approx_c H_2^1 \approx_c \dots \approx_c H_\ell^\ell = \text{Game 2}$.

Let $\mathcal{C}'$ be a challenger that chooses $b \in \{0, 1\}$ uniformly at random. If $b = 0$ it interacts with a PPT adversary $\mathcal{A}'$ as in Hybrid $H_{\eta}^{\iota-1}$, otherwise it interacts as in Hybrid $H_{\eta}^{\iota}$. At the end of the interaction, $\mathcal{A}'$ will make its guess $\tilde{b} \in \{0, 1\}$. We define $\mathrm{Adv}_{(\iota-1)\iota}^{\mathrm{H}}(\mathcal{A}') := |\mathrm{Pr}[\tilde{b} = 1|b = 0] - \mathrm{Pr}[\tilde{b} = 1|b = 1]|$ for $\iota \in [\ell]$. We define analogously $\mathrm{Adv}_{(i-1)i}^{\mathrm{P}}(\mathcal{A}')$ for distinguishing between Hybrid $H_{i-1}^2$ and Hybrid $H_i^0$.

Formally speaking, going from hybrid $H_{\eta}^{\iota-1}$ to hybrid $H_{\eta}^{\iota}$ we are swapping the IPFE algorithms by their respective simulators. First, we note that coherence is held since the output of the decryption algorithm $d_{i,j}$ is the same in both hybrids given that $c_{\eta}(\mathbf{u}_{\eta} - \tilde{\mathbf{u}}_{\eta}) = \mathbf{x}_{\eta}$ by definition of $\tilde{\mathbf{u}}_{\eta}$. Furthermore, the plaintext
Hybrid $H_{\eta}^{\ell}$

MIQFE.SetUp<sup>i</sup>(1<sup>κ</sup>, F<sub>B,ℓ</sub><sup>n</sup>) :

PG ← PGGen(1<sup>κ</sup>), u<sub>i</sub> ← $\mathbb{Z}_{p}^{n}$ for i ∈ [ℓ], w<sub>i,j</sub> ← $\mathbb{Z}_{p}^{2n}$ for i, j ∈ [ℓ] c<sub>i</sub> ← $\mathbb{Z}_{p}$ for i ∈ [ℓ]. If any c<sub>i</sub> = 0 abort.

-if (i, j) <L (η, ℓ) : IPFE.msk<sub>i,j</sub><sup>L</sup> ← IPFE.SetUpSim(1<sup>κ</sup>, F<sub>IP</sub><sup>2n</sup>, PG),

-if (i, j) = (η, ℓ) : IPFE.msk<sub>i,j</sub><sup>L</sup> ← IPFE.SetUpSim(1<sup>κ</sup>, F<sub>IP</sub><sup>2n</sup>, PG),

-if (i, j) >L (η, ℓ) : IPFE.msk<sub>i,j</sub><sup>L</sup> ← IPFE.SetUp(1<sup>κ</sup>, F<sub>IP</sub><sup>2n</sup>, PG),

MIQFE.msk = ({u<sub>i</sub>, c<sub>i</sub>}<sub>i∈[ℓ]</sub>, {w<sub>i,j</sub>, IPFE.msk<sub>i,j</sub>'}<sub>i,j∈[ℓ]</sub>)

MIQFE.Enc<sup>i</sup>(MIQFE.msk, i, x<sub>i</sub>) :

$\tilde{u}_{i} = u_{i} - c_{i}^{-1}x_{i}, \tilde{c}t_{x_{i}} = c_{i}u_{i}, st_{i} = \tilde{u}_{i}$

-if (i, j) <L (η, ℓ) : IPFE.c<sub>i,j</sub>' ← IPFE.EncSim(IPFE.msk<sub>i,j</sub>)

-if (i, j) = (η, ℓ) : IPFE.c<sub>i,j</sub>' ← IPFE.EncSim(IPFE.msk<sub>i,j</sub>)

-if (i, j) >L (η, ℓ) : IPFE.c<sub>i,j</sub>' ← IPFE.Enc(IPFE.msk<sub>i,j</sub>, w<sub>i,j</sub>) + (c<sub>j</sub>\tilde{c}t<sub>x<sub>i</sub></sub>) / (c<sub>j</sub>x<sub>i</sub>)

MIQFE.c<sub>i</sub> = (\tilde{c}t<sub>x<sub>i</sub></sub>, {IPFE.c<sub>i,j</sub>'}j∈[ℓ])

MIQFE.KeyGen<sup>i</sup>(MIQFE.msk, {st<sub>i</sub>}i∈[ℓ], v, F) : For i, j ∈ [ℓ]

$d_{i,j} = (w_{i,j} + (c_j \tilde{c}t_{x_i}) / (\tilde{u}_j^\top F_{j,i}), (\tilde{u}_j^\top F_{j,i}), zk_F) = \sum_{i,j \in [\ell]} w_{i,j}^\top (\tilde{u}_j^\top F_{j,i}) / (\tilde{u}_j^\top F_{j,i} \tilde{u}_j)$

-if (i, j) <L (η, ℓ) : IPFE.sk<sub>i,j</sub>' ← IPFE.KeyGenSim(IPFE.msk<sub>i,j</sub>, d<sub>i,j</sub>)

-if (i, j) = (η, ℓ) : IPFE.sk<sub>i,j</sub>' ← IPFE.KeyGenSim(IPFE.msk<sub>i,j</sub>, d<sub>i,j</sub>)

-if (i, j) >L (η, ℓ) : IPFE.sk<sub>i,j</sub>' ← IPFE.KeyGen(IPFE.msk<sub>i,j</sub>, (\tilde{u}_j^\top F_{j,i}) / (\tilde{u}_j^\top F_{j,i} \tilde{u}_j))

MIQFE.sk<sub>F</sub> = (F, {IPFE.sk<sub>i,j</sub>'}i,j∈[ℓ], zk<sub>F</sub>)

<caption>Fig. 3. Games for the hybrid argument in Lemma 2. Changes are squared.</caption>

$w_{i,j} + (c_j \tilde{c}t_{x_i}) / (c_j x_i)$ is indistinguishable from random since $w_{i,j}$ is sampled uniformly at random and used only once (we are proving one selective security).

Then, distinguishing the simulators in the context of the MIQFE or by their
own has the same advantage, so for any PPT adversary $\mathcal{A}'$ trying to distinguish
$H_{\eta}^{\ell-1}$ and $H_{\eta}^{\ell}$ we can construct a PPT adversary $\mathcal{B}$ which distinguishes the real
experiment from the ideal experiment in the function-hiding simulation security
game for IPFE. Therefore, we get that for any PPT adversary $\mathcal{A}'$ there exists a
PPT adversary $\mathcal{B}$ such that $\mathrm{Adv}_{(\ell-1)\ell}^{\mathcal{H}}(\mathcal{A}') \le \mathrm{Adv}_{\mathrm{IPFE}}^{\mathrm{FH-SIM}}(\mathcal{B})$.

To finalize the proof we note that going from hybrid $H_{\eta-1}^{\ell}$ to hybrid $H_{\eta}^{1}$ and going from Game 1 to hybrid $H_{1}^{1}$ are analogous to going from hybrid $H_{\eta}^{\ell-1}$ to $H_{\eta}^{\ell}$ as well as the fact that Game 2 is exactly the same as hybrid $H_{\ell}^{\ell}$. Since there are $\ell^2$ relevant changes we get

$$
\begin{align*}
\mathrm{Adv}_{12}(\mathcal{A}) &= \ell^2 \cdot \mathrm{Adv}_{(\ell-1)\ell}^{\mathcal{H}}(\mathcal{A}) \\
&\le \ell^2 \cdot \mathrm{Adv}_{\mathrm{IPFE}}^{\mathrm{FH-SIM}}(\mathcal{B}).
\end{align*}
$$

C.2 Proof of Lemma in Section 4

Lemma 3. For any PPT adversary $\mathcal{A}'$ there exists a PPT adversary $\mathcal{B}$ such that

$$
\mathrm{Adv}_{12}(\mathcal{A}') \le 2Q_{sk} \cdot \mathrm{Adv}_{\mathbb{G}_2}^{\mathrm{DDH}} + \frac{2Q_{sk}}{p-1}.
$$
<figure><img src="image_4.png" /><figcaption>**Fig. 4.** Games for the hybrid argument in Lemma 3. Changes only occur on the KeyGen algorithm so the others are omitted and assumed the same as in Game 1 in Figure 2.</figcaption></figure>

where $Q_{sk}$ denotes the number of queries performed to KeyGen.

*Proof.* We will prove this through a series of Hybrid Games $H_{\rho}^{\alpha}$ for $\rho \in [Q_{sk}]$ and $\alpha \in \{0, 1, 2\}$, defined in Figure 4. We show that Game 1 = $H_1^0 \approx_c H_1^1 \approx_s H_1^2 \approx_c H_2^0 \approx_c \dots \approx_c H_{Q_{sk}}^2 \approx_c= H_{Q_{sk+1}}^0$ Game 2.

Let $\mathcal{C}'$ be a challenger that chooses $b \in \{0, 1\}$ uniformly at random. If $b = 0$ it interacts with a PPT adversary $\mathcal{A}'$ as in Hybrid $H_{\rho}^{i-1}$, otherwise it interacts as in Hybrid $H_{\rho}^i$. At the end of the interaction, $\mathcal{A}'$ will make its guess $\tilde{b} \in \{0, 1\}$. We define $\text{Adv}_{(i-1)i}(\mathcal{A}') := |\text{Pr}[\tilde{b} = 1|b = 0] - \text{Pr}[\tilde{b} = 1|b = 1]|$ for $i = 1, 2$. We define analogously $\text{Adv}_{(i-1)i}(\mathcal{A}')$ for distinguishing between Hybrid $H_{i-1}^2$ and Hybrid $H_i^0$.

Hybrid $H_{\rho}^1$. In this change we have swapped $\tilde{v}$ from $t \cdot v$ to uniformly at random. We show that for any PPT adversary $\mathcal{A}'$ trying to distinguish these two Hybrids we can construct a PPT adversary $\mathcal{B}$ against the $n$-fold DDH assumption in $\mathbb{G}_2$.

When, $\mathcal{B}$ receives the $n$-fold DDH challenge $[t]_2 = [(t, 1)^{\top}]_2$, $[\mathbf{W}]_2 := [(\mathbf{w}_1, \mathbf{w}_2)^{\top}]_2$ for some $\mathbf{w}_1, \mathbf{w}_2 \in \mathbb{Z}_p^n$, it runs IPFE.SetUp$_{\rho,1}^H$ and IPFE.Enc$_{\rho,1}^H$ and in IPFE.msk it substitutes $v$ for $[\mathbf{w}_2]_2$. Note that only having the element in $\mathbb{G}_2$ is not an issue since after Game 1 $v$ is only used during KeyGen and as such only the values in $\mathbb{G}_2$ are needed. It is in this step where using our order in layering the schemes from [1, Section 3] instead of the order in [22, Section 6.3] comes into play.

Then for query $i \in [Q_{sk}]$, if $i \neq \rho$ it runs KeyGen$_{\rho,1}^H$ normally, but if $i = \rho$ it sets $[t]_2$ as the first part of the $n$-fold DDH challenge and $\tilde{v} = [\mathbf{w}_1]_2$. Once again, only having the elements in $\mathbb{G}_2$ is not an issue since the operations can be performed in the group. Finally, it outputs the same bit as adversary $\mathcal{A}'$. It is clear to see that if the DDH challenge $[\tilde{\mathbf{W}}]_2$ is of the form $[\mathbf{t}\mathbf{r}^{\top}]_2 = [(\mathbf{t}\mathbf{r}, \mathbf{r})^{\top}]_2$ for some $\mathbf{r} \stackrel{\$}{\leftarrow} \mathbb{Z}_p^n$ then it is the same distribution as in Hybrid $H_{\rho}^0$ while if $[\mathbf{W}]_2$ is uniformly at random it is the same distribution as in Hybrid $H_{\rho}^1$. As such we
get

$$
\begin{aligned}
\mathrm{Adv}_{01}^{\alpha}(\mathcal{A}') &\le \mathrm{Adv}_{\mathbb{G}_2}^{\mathcal{Q}-\mathrm{DDH}}(\mathcal{B}) \\
&\le \mathrm{Adv}_{\mathbb{G}_2}^{\mathrm{DDH}}(\mathcal{B}) + \frac{1}{p-1},
\end{aligned}
$$

where we have applied the random self-reducibility of DDH, Lemma 1.

Hybrid $H_{\rho}^2$. In this change we have swapped $\mathbf{y}$ from $\mathbf{y}$ to 0. Distinguishing between these Hybrids is distinguishing between $\mathbf{y} + \tilde{\mathbf{v}}$ and $\tilde{\mathbf{v}}$, and since $\tilde{\mathbf{v}}$ is sampled uniformly at random and only used once they are indistinguishable. Therefore, for any PPT adversary $\mathcal{A}'$, $\mathrm{Adv}_{12}^{\alpha}(\mathcal{A}') = 0$.

Hybrid $H_{\rho+1}^0$. In this change we have swapped back $\tilde{v}$ from sampled uniformly at random to $t \cdot v$. As such this transition is analogous to the change from $H_{\rho}^0$ to $H_{\rho}^1$, so for any PPT adversary $\mathcal{A}'$ there exists a PPT adversary $\mathcal{B}$ such that

$$
\mathrm{Adv}_{i(i+1)}^{\rho}(\mathcal{A}') \le \mathrm{Adv}_{\mathbb{G}_2}^{\mathrm{DDH}}(\mathcal{B}) + \frac{1}{p-1}.
$$

Finally, adding all the transitions together and noting that $H_1^0$ is identically distributed to Game 1, while $H_{Q_{sk}+1}^0$ is identically distributed to Game 2, we get

$$
\mathrm{Adv}_{12}(\mathcal{A}') \le 2Q_{sk} \cdot \mathrm{Adv}_{\mathbb{G}_2}^{\mathrm{DDH}} + \frac{2Q_{sk}}{p-1}.
$$

where $Q_{sk}$ denotes the number of queries performed to KeyGen.