where $t_i \stackrel{\$}{\leftarrow} \mathbb{Z}_q$ and $\sum_{i \in \mathcal{H}} t_i = R$. We note that the secret shares are the same for all repetitions $j$ at position $i$ under tag$^*$, or $j'$ under tag$_\ell$. We have $G_{0.1.0} = G_{0.1}$ and $G_{0.1.q_e+1} = G_{0.2}$.

We describe the transition from $G_{0.1.\ell-1}$ to $G_{0.1.\ell}$ for $\ell \in [q_e]$ (the case $\ell = q_e+1$ is similar), using a DDH instance ($[a]_1, [b]_1, [c]_1$) where $c-ab=0$ or a uniformly random value. Given a ppt adversary $\mathcal{A}$ that can distinguish $G_{0.1.\ell-1}$ from $G_{0.1.\ell}$ that differ at the $\ell$-th ciphertext query, we build a ppt adversary $\mathcal{B}$ that breaks the DDH:

- The adversary $\mathcal{B}$ uses $[a]_1$ to simulate $H_1(\text{tag}_\ell)$. This implicitly sets $\omega_\ell := a$.

- The adversary $\mathcal{B}$ samples $\tilde{t}_i \stackrel{\$}{\leftarrow} \mathbb{Z}_q$ for corrupted $i$, as well as other parameters to output the corrupted keys $(ek_i, sk_i)$ to $\mathcal{A}$. Then, $\mathcal{B}$ computes and defines $S_\ell := -\sum_{i \in \mathcal{C}} \tilde{t}_i$.

- Let us denote $H := |\mathcal{H}|$ the number of honest $i$. For $i$ among the first $H-1$ honest clients whose keys are never leaked, $\mathcal{B}$ uses the random-self reducibility to compute $[\omega_\ell \tilde{t}_i]_2$ for responding to the $\ell$-th ciphertext query $\mathbf{c}_{\ell,i}^{(j)}$.

- First, for $i$ among the first $H-1$ honest, $\mathcal{B}$ samples $\alpha_{\ell,i}, \beta_{\ell,i} \stackrel{\$}{\leftarrow} \mathbb{Z}_q$ and implicitly defines $b_{\ell,i} := \alpha_{\ell,i}b + \beta_{\ell,i}$, $c_{\ell,i} := \alpha_{\ell,i}c + \beta_{\ell,i}a$, and in the end $a_{\ell,i} := a$. We note that

$$ \begin{cases} [b_{\ell,i}]_1 = \alpha_{\ell,i}[b]_1 + [\beta_{\ell,i}]_1 \\ [c_{\ell,i}]_1 = \alpha_{\ell,i}[c]_1 + \beta_{\ell,i}[a]_1 \end{cases} $$

are efficiently computable from the DDH instance. Then, $\mathcal{B}$ uses $[c_{\ell,i}]_1$ in the simulation of $\mathbf{c}_{\ell,i}^{(j)}$.

- Second, for the last $H$-th honest client $i_H$, $\mathcal{B}$ computes and defines:

$$ [c_{\ell,i_H}]_1 := S_\ell \cdot [a]_1 - \sum_{i \in \mathcal{H} \setminus \{i_H\}} [c_{\ell,i}]_1 \Rightarrow \sum_{i \in \mathcal{H}} c_{\ell,i} = a \cdot S_\ell \quad (22) $$

where $S_\ell$ is known in clear from above and other honest $[c_{\ell,i}]_1$ can be computed as explained. The adversary $\mathcal{B}$ then uses $[c_{\ell,i_H}]_1$ to simulate $\mathbf{c}_{\ell,i_H}^{(j)}$. We emphasize that we make use of the static corruption in the simulation for honest $i$, since we never have to compute the $(c_{\ell,i})_{i \in \mathcal{H}}$ as a scalar and can embed the DDH instance so that on the exponents (of group elements) they sum to $S_\ell$.

It can be verified that if $c-ab=0$, then $\mathcal{B}$ simulates $\mathbf{c}_{\ell,i}^{(j')} [N+1] = \omega_\ell \tilde{t}_i := ab_{\ell,i}$ and we are in $G_{0.1.\ell-1}$. Else $\mathbf{c}_{\ell,i}^{(j')} [N+1] = t_{\ell,i} := c_{\ell,i}$ is a uniformly random value such that $\sum_{i \in \mathcal{H}} c_{\ell,i} + \omega_\ell \sum_{i \in \mathcal{C}} \tilde{t}_i \stackrel{(*)}{=} aS_\ell + \omega_\ell \sum_{i \in \mathcal{C}} \tilde{t}_i = 0$ thanks to (22). In the end we have $|\text{Pr}[G_{0.1.\ell-1} = 1] - \text{Pr}[G_{0.1.\ell} = 1]| \le \text{Adv}_{\mathbb{G}_1}^{\text{DDH}}(1^\lambda)$ and thus $|\text{Pr}[G_{0.2} = 1] - \text{Pr}[G_{0.1} = 1]| \le (q_e+1) \cdot \text{Adv}_{\mathbb{G}_1}^{\text{DDH}}(1^\lambda)$.

After arriving at $G_{0.2}$ the vectors are now of the following form:

$$ \mathbf{c}_{\ell,i}^{(j')} = (\mathbf{x}_{\ell,i}^{(j')}, [\tilde{t}_{\ell,i}], 0, \rho_{\ell,i}^{(j')}, 0^N, 0^{2N+2N \cdot \tilde{J}+1})_{\mathbf{B}_i} $$

$$ \mathbf{d}_{k,i}^{(j')} = (\mathbf{y}_{k,i}^{(j')}, \mu_k, \pi_{k,i}^{(j')}, 0, 0^N, 0^{2N+2N \cdot \tilde{J}+1})_{\mathbf{B}_i^*} $$

$$ \mathbf{c}_i^{(j)} = (\mathbf{x}_i^{(0,j)}, [\tilde{t}_i], 0, \rho_i^{(j)}, 0^N, 0^{2N+2N \cdot \tilde{J}+1})_{\mathbf{B}_i} $$

$$ \mathbf{d}_i^{(j)} = (\mathbf{y}_i^0, \mu, \pi_i^{(j)}, 0, 0^N, 0^{2N+2N \cdot \tilde{J}+1})_{\mathbf{B}_i^*} $$
as desired in $\mathbb{G}_1$. As a result, we have $\mathbb{G}_{0.2} = \mathbb{G}_1$ and the total difference in advantages is $|\Pr[\mathbb{G}_1 = 1] - \Pr[\mathbb{G}_0 = 1]| \le (q_e + 1) \cdot \mathbf{Adv}_{\mathbb{G}_1}^{\mathrm{DDH}}(1^{\lambda})$.

**Game G2:** We use DSDH in $\mathbb{G}_1$ to make $\mathbf{x}_{\ell,i}^{(j')}$ appear in coordinates $[N+4, 2N+3]$ of $\mathbf{c}_{\ell,i}^{(j')}$, as well as $\mathbf{x}_i^{(1,j)}$ in coordinates $[N+4, 2N+3]$ of $\mathbf{c}_i^{(j)}$. This is of type computational basis changes that is reviewed in appendix A.1, the calculation stays the same where we use DSDH to introduced fixed instead of random values.

We proceed by a sequence of $N+1$ hybrids, indexed by $m \in [0; N]$, such that the first hybrid of $m=0$ is identical to $\mathbb{G}_1$, and for $m \ge 1$ in the $m$-th hybrid the coordinates $[N+4, N+3+m]$ of $\mathbf{c}_{\ell,i}^{(j')}$, $\mathrm{vecx}_i^{(1,j)}$ are modified. For $m \in [N]$, the transition from the $(m-1)$-th hybrid to the $m$-th hybrid is described below. Given a DSDH instance $([a]_1, [b]_1, [c]_1)$ in $\mathbb{G}_2$ where $\delta := c - ab$ is either 0 or 1, the bases $(\mathbf{B}_i, \mathbf{B}_i^*)$ are changed following:

$$ \mathbf{B}_i = \begin{bmatrix} 1 & a \\ 0 & 1 \end{bmatrix}_{N+3,N+3+m} \cdot \mathbf{H}_i; \quad \mathbf{B}_i^* = \begin{bmatrix} 1 & 0 \\ -a & 1 \end{bmatrix}_{N+3,N+3+m} \cdot \mathbf{H}_i^* . $$

The bases $\mathbf{B}_i$ can be computed using $[[a]]_1$ and the ciphertext components can be written as follows:

$$ \begin{align*} \mathbf{c}_{\ell,i}^{(j')} &= (\mathbf{x}_{\ell,i}^{(j')}, t_{\ell,i}, 0, \rho_{\ell,i}^{(j')}, \underbrace{\mathbf{x}_{\ell,i}^{(j')}[1], \dots, \mathbf{x}_{\ell,i}^{(j')}[m-1], 0, \dots, 0}_{\text{last } (N-m+1)\text{-th coordinates are 0}} + (0^{N+2}, b\mathbf{x}_{\ell,i}^{(j')}[m], 0, \underbrace{0, \dots, 0, c\mathbf{x}_{\ell,i}^{(j')}[m], 0, \dots, 0}_{\text{m-th coordinate among } N} + 0^{2N \cdot \bar{J}+1})\mathbf{H}_i^* \\ &= (\mathbf{x}_{\ell,i}^{(j')}, t_{\ell,i}, 0, \rho_{\ell,i}^{(j')}, b\mathbf{x}_{\ell,i}^{(j')}[m], \underbrace{\mathbf{x}_{\ell,i}^{(j')}[1], \dots, \mathbf{x}_{\ell,i}^{(j')}[m-1], \delta\mathbf{x}_{\ell,i}^{(j')}[m], 0, \dots, 0}_{\text{last } (N-m)\text{-th coordinates are 0}} + 0^{2N \cdot \bar{J}+1})\mathbf{B}_i \end{align*} $$

$$ \begin{align*} \mathbf{c}_i^{(j)} &= (\mathbf{x}_i^{(b,j)}, t_i, 0, \rho_i^{(j)}, \underbrace{\mathbf{x}_i^{(1,j)}[1], \dots, \mathbf{x}_i^{(1,j)}[m-1], 0, \dots, 0}_{\text{last } (N-m+1)\text{-th coordinates are 0}} + (0^{N+2}, b\mathbf{x}_i^{(1,j)}[m], 0, \underbrace{0, \dots, 0, c\mathbf{x}_i^{(1,j)}[m], 0, \dots, 0}_{\text{m-th coordinates among } N} + 0^{2N \cdot \bar{J}+1})\mathbf{H}_i^* \\ &= (\mathbf{x}_i^{(b,j)}, t_i, 0, \rho_i^{(j)} + b\mathbf{x}_i^{(1,j)}[m], \underbrace{\mathbf{x}_i^{(1,j)}[1], \dots, \mathbf{x}_i^{(1,j)}[m-1], \delta\mathbf{x}_i^{(1,j)}[m], 0, \dots, 0}_{\text{last } (N-m)\text{-th coordinates are 0}} + 0^{2N \cdot \bar{J}+1})\mathbf{B}_i \end{align*} $$

We update $(\rho_{\ell,i}^{(j')}, \rho_i^{(j')})$ to $(\rho_{\ell,i}^{(j')} + b\mathbf{x}_{\ell,i}^{(j')}[m], \rho_i^{(j)} + b\mathbf{x}_i^{(1,j)}[m])$. Even though $\mathbf{b}_{i,N+3+m}$ cannot be computed due to the lack of $[[a]]_2$, the simulator can write the $\mathbf{d}$-vectors in $\mathbf{H}_i^*$ to observe how they are affected:

$$ \begin{align*} \mathbf{d}_{k,i}^{(j')} &= (\mathbf{y}_{k,i}^{(j')}, \mu_k, \pi_{k,i}^{(j')}, 0, 0^N, 0^{2N \cdot \bar{J}+1})\mathbf{H}_i^* \\ &= (\mathbf{y}_{k,i}^{(j')}, \mu_k, \pi_{k,i}^{(j')}, 0 + 0 \cdot a, 0^N, 0^{2N \cdot \bar{J}+1})\mathbf{B}_i^* \\ &= (\mathbf{y}_{k,i}^{(j')}, \mu_k, \pi_{k,i}^{(j')}, 0, 0^N, 0^{2N \cdot \bar{J}+1})\mathbf{B}_i^* \\ \mathbf{d}_i^{(j)} &= (\mathbf{y}_i^{(b,\bar{J})}, \mu, \pi_i^{(j)}, 0, 0^N, 0^{2N \cdot \bar{J}+1})\mathbf{B}_i^* . \end{align*} $$

If $\delta = 0$ we are in the $(m-1)$-th hybrid, else we are in the $m$-th hybrid. Totally, we proceed for all $i \in \mathcal{H}$ in parallel, after $N$ transitions we arrive at $\mathbb{G}_3$ and obtain $|\Pr[\mathbb{G}_2 = 1] - \Pr[\mathbb{G}_1 = 1]| \le 2N \cdot \mathbf{Adv}_{\mathbb{G}_1}^{\mathrm{DDH}}(1^{\lambda})$.
After $G_2$ the vectors are now:

$$ \mathbf{c}_{\ell, i}^{(j')} = (\mathbf{x}_{\ell, i}^{(j')}, t_{\ell, i}, 0, \rho_{\ell, i}^{(j')}, \boxed{\mathbf{x}_{\ell, i}^{(j')}} \cdot 0^{2N \cdot \tilde{J} + 1})_{\mathbf{B}_i} $$

$$ \mathbf{d}_{k, i}^{(j')} = (\mathbf{y}_{k, i}^{(j')}, \mu_k, \pi_{k, i}^{(j')}, 0, 0^N, 0^{2N \cdot \tilde{J} + 1})_{\mathbf{B}_i^*} $$

$$ \mathbf{c}_{i}^{(j)} = (\mathbf{x}_{i}^{(b,j)}, t_{i}, 0, \rho_{i}^{(j)}, \boxed{\mathbf{x}_{i}^{(1,j)}} \cdot 0^{2N \cdot \tilde{J} + 1})_{\mathbf{B}_{i}} $$

$$ \mathbf{d}_{i}^{(\tilde{j})} = (\mathbf{y}_{i}^{(b,\tilde{j})}, \mu, \pi_{i}^{(\tilde{j})}, 0, 0^{N}, 0^{2N \cdot \tilde{J} + 1})_{\mathbf{B}_{i}^{*}} $$

**Game G3:** We apply Lemma 1 to swap $\mathbf{y}_i^{(b,\tilde{j})}$, $\mathbf{y}_{k,i}^{(\tilde{j}'')}$ from coordinates $[1, N]$ to $\mathbf{y}_i^{(1,\tilde{j})}$, $\mathbf{y}_{k,i}^{(\tilde{j}'')}$ in coordinates $[N+4, 2N+3]$ of vectors $\mathbf{d}_i^{(\tilde{j})}$, $\mathbf{d}_{k,i}^{(\tilde{j}'')}$.
This can be done by a sequence of $q_k + 2$ hybrids over the $q_k$ distinct tags $\text{tag-f}_k$ to OKeyGen and the challenge tag $\text{tag-f}^*$ that is declared at the outset of the one-challenge security game. The first hybrid is the same as $G_2$. The transition between each hybrid is done by an application of Lemma 1. We first swap the challenge vector $\mathbf{d}_i^{(\tilde{j})}$, then swap the non-challenge $\mathbf{d}_{k,i}^{(\tilde{j}'')}$ one after another on an ordering over $\mu_k$, e.g. their order of appearances. We verify the constraints required by Lemma 1.

**Swapping the challenge vector $\mathbf{y}_i^{(b,\tilde{j})}$ to $\mathbf{y}_i^{(1,\tilde{j})}$:**

* Thanks to the admissibility condition that is concretely interpreted for inner products, we have for all $j \in [J], \tilde{j} \in [\tilde{J}]$ that

$$ \sum_{i \in \mathcal{H}} \langle \mathbf{y}_i^{(b, \tilde{j})}, \mathbf{x}_i^{(b, j)} \rangle - \langle \mathbf{y}_i^{(1, \tilde{j})}, \mathbf{x}_i^{(1, j)} \rangle \stackrel{(1)}{=} \sum_{i=1}^{n} \langle \mathbf{y}_i^{(b, \tilde{j})}, \mathbf{x}_i^{(b, j)} \rangle - \langle \mathbf{y}_i^{(1, \tilde{j})}, \mathbf{x}_i^{(1, j)} \rangle \stackrel{(2)}{=} 0, $$

where (1) is implied by Condition 1 in Definition 5 and (2) comes from Condition 2. This provides the conditions for the application of Lemma 1.

* The sets of vectors, listed in the order of the lemma's oracles, are $(\mathbf{d}_{k,i}^{(\tilde{j}'')})_{k \in [q_k], i \in \mathcal{H}}^{\tilde{j}' \in [J]}$, $(\mathbf{d}_i^{(\tilde{j})})_{i \in \mathcal{H}}^{\tilde{j} \in [J]}$, $(\mathbf{c}_i^{(j)})_{j \in [J]}^{j \in [J]}$ and $(\mathbf{c}_{\ell,i}^{(\tilde{j}'')})_{\ell \in [q_\ell], i \in \mathcal{H}}^{\tilde{j}' \in [J]}$. The $2N + 2N \cdot \tilde{J} + 4$ coordinates affected, in the order w.r.t the statement of Lemma 1 so that they form a subspace of dimension $2N + 2N \cdot \tilde{J} + 4$, are $([1, N], [N+4, 2N+3], N+1, N+3, N+2, [2N+4, 2N+2N \cdot \tilde{J} + 4])$.

* This swap incurs a security loss upper bounded by $(4n\tilde{J}N + 4) \cdot \mathbf{Adv}_{G_1, G_2}^{\text{SXDH}}(1^\lambda)$.

**Swapping the non-challenge vectors $\mathbf{y}_{k,i}^{(\tilde{j}'')}$ to $\mathbf{y}_{k,i}^{(\tilde{j}'')}$:** We remark that we do not change the vector $\mathbf{y}_{k,i}^{(\tilde{j}'')}$ while swapping.

* Thanks to the admissibility condition that is concretely interpreted for inner products, we have for all $j \in [J], \tilde{j} \in [\tilde{J}]$ that

$$ \sum_{i \in \mathcal{H}} \langle \mathbf{y}_{k,i}^{(\tilde{j}'')}, \mathbf{x}_i^{(b,j)} \rangle - \langle \mathbf{y}_{k,i}^{(\tilde{j}'')}, \mathbf{x}_i^{(1,j)} \rangle \stackrel{(1)}{=} \sum_{i=1}^{n} \langle \mathbf{y}_{k,i}^{(\tilde{j}'')}, \mathbf{x}_i^{(b,j)} \rangle - \langle \mathbf{y}_{k,i}^{(\tilde{j}'')}, \mathbf{x}_i^{(1,j)} \rangle \stackrel{(2)}{=} 0. $$

This provides the conditions for the application of Lemma 1.

* The sets of vectors, listed in the order of the lemma's oracles, are $(\mathbf{d}_i^{(\tilde{j})})_{i \in \mathcal{H}}^{\tilde{j} \in [J]}$ together with $(\mathbf{d}_{k',i}^{(\tilde{j}'')})_{k' \in [q_k] \setminus \{k\}, i \in \mathcal{H}}^{\tilde{j}' \in [J]}$, $(\mathbf{d}_{k,i}^{(\tilde{j}'')})_{i \in \mathcal{H}}^{\tilde{j}' \in [J]}$, $(\mathbf{c}_i^{(j)})_{i \in \mathcal{H}}^{j \in [J]}$ and $(\mathbf{c}_{\ell,i}^{(\tilde{j}'')})_{\ell \in [q_\ell], i \in \mathcal{H}}^{\tilde{j}' \in [J]}$. The $2N + 2N \cdot \tilde{J} + 4$ coordinates affected, in the order w.r.t the statement of Lemma 1 so that they form a subspace of dimension $2N + 2N \cdot \tilde{J} + 4$, are $([1, N], [N+4, 2N+3], N+1, N+3, N+2, [2N+4, 2N+2N \cdot \tilde{J} + 4])$.
• The security loss for each swap over the $q_k$ non-challenge tags to OKeyGen is upper bounded by: $(4n\tilde{J}N + 4) \cdot \mathbf{Adv}_{\mathbb{G}_1, \mathbb{G}_2}^{\text{SXDH}}(1^{\lambda})$.

In total, we have $|\text{Pr}[\mathbb{G}_3 = 1] - \text{Pr}[\mathbb{G}_2 = 1]| \le (q_k + 1) \cdot (4n\tilde{J}N + 4) \cdot \mathbf{Adv}_{\mathbb{G}_1, \mathbb{G}_2}^{\text{SXDH}}(1^{\lambda})$.

After $\mathbb{G}_3$ the vectors are now:

$$ \mathbf{c}_{\ell, i}^{(j')} = (\mathbf{x}_{\ell, i}^{(j')}, t_{\ell, i}, 0, \rho_{\ell, i}^{(j')}, \mathbf{x}_{\ell, i}^{(j')}, 0^{2N \cdot \tilde{J} + 1})_{\mathbf{B}_i} $$

$$ \mathbf{d}_{k, i}^{(j')} = (\underline{0}^N, \mu_k, \pi_{k, i}^{(j')}, 0, \underline{\mathbf{y}}_{k, i}^{(j')}, 0^{2N \cdot \tilde{J} + 1})_{\mathbf{B}_i^*} $$

$$ \mathbf{c}_{i}^{(j)} = (\mathbf{x}_{i}^{(b,j)}, t_{i}, 0, \rho_{i}^{(j)}, \mathbf{x}_{i}^{(1,j)}, 0^{2N \cdot \tilde{J} + 1})_{\mathbf{B}_i} $$

$$ \mathbf{d}_{i}^{(j)} = (\underline{0}^N, \mu, \pi_{i}^{(j)}, 0, \underline{\mathbf{y}}_{i}^{(1,j)}, 0^{2N \cdot \tilde{J} + 1})_{\mathbf{B}_i^*} $$

**Game G4:** In $\mathbb{G}_4$, we use DSDH in $\mathbb{G}_1$ to change $\mathbf{x}_i^{(b,j)}$ into $\mathbf{x}_i^{(1,j)}$ in coordinates $[1, N]$ of $\mathbf{c}_i^{(j)}$. This is of type computational basis changes that is reviewed in appendix A.1, the calculation stays the same where we use DSDH to introduced fixed instead of random values.

We exploit the randomness at coordinate $(N + 3)$ of the c-vectors and proceed by a sequence of $N + 1$ hybrids, indexed by $m \in [0; N]$, such that the first hybrid for $m = 0$ is identical to $\mathbb{G}_3$ while in the $m$-th hybrid the first coordinates $[1, m]$ of $\mathbf{c}_{\ell, i}^{(j')}, \mathbf{c}_i^{(j)}$ are modified, for $m \ge 1$. For $m \in [N]$, the transition from the $(m-1)$-th hybrid to the $m$-th hybrid can be done by a computational basis change using a DSDH instance $([a]_1, [b]_1, [c]_1)$ in $\mathbb{G}_1$ where $\delta := c - ab$ is either 0 or 1. The bases $(\mathbf{B}_i, \mathbf{B}_i^*)$ are changed following:

$$ \mathbf{B}_i = \begin{bmatrix} 1 & 0 \\ a & 1 \end{bmatrix}_{m,N+3} \cdot \mathbf{H}_i; \quad \mathbf{B}_i^* = \begin{bmatrix} 1 & -a \\ 0 & 1 \end{bmatrix}_{m,N+3} \cdot \mathbf{H}_i^* $$

The calculation can be adapted from that in the transitions from $\mathbb{G}_1$ to $\mathbb{G}_2$. The $\mathbf{B}_i$ can be computed using $[a]_1$. More specifically, the ciphertext components can be written as follows:

$$ \mathbf{c}_{\ell, i}^{(j')} = (\mathbf{x}_{\ell, i}^{(j')}, t_{\ell, i}, 0, \rho_{\ell, i}^{(j')}, \mathbf{x}_{\ell, i}^{(j')}, 0^{2N \cdot \tilde{J} + 1})_{\mathbf{B}_i} $$

$$ \mathbf{c}_i^{(j)} = \underbrace{(\mathbf{x}_i^{(1,j)}[1], \dots, \mathbf{x}_i^{(1,j)}[m-1], \mathbf{x}_i^{(b,j)}[m; N], t_i, 0, \rho_i^{(j)}, \mathbf{x}_i^{(1,j)}, 0^{2N \cdot \tilde{J} + 1})_{\mathbf{B}_i} \quad \text{last } (N-m+1)\text{-th coordinates from } \mathbf{x}_i^{(b,j)} $$

$$ + \underbrace{(0, \dots, 0, c \cdot \Delta \mathbf{x}_i^{(j)}[m], 0, \dots, 0, 0, 0, b \Delta \mathbf{x}_i^{(j)}[m], 0, \dots, 0^{2N \cdot \tilde{J} + 1})_{\mathbf{H}_i^*} \quad \text{m-th coordinate among } N $$

$$ = \underbrace{(\mathbf{x}_i^{(1,j)}[1], \dots, \mathbf{x}_i^{(1,j)}[m-1], \mathbf{x}_i^{(b,j)}[m] + \delta \cdot \Delta \mathbf{x}_i^{(j)}[m], \mathbf{x}_i^{(b,j)}[m+1; N], t_i, 0, \dots, 0^{2N \cdot \tilde{J} + 1})_{\mathbf{B}_i} \quad \text{last } (N-m)\text{-th coordinates from } \mathbf{x}_i^{(b,j)} $$

$$ \rho_i^{(j)} + b \Delta \mathbf{x}_i^{(j)}[m], \mathbf{x}_i^{(1,j)}, 0^{2N \cdot \tilde{J} + 1})_{\mathbf{B}_i} $$

where $\Delta \mathbf{x}_i^{(j)}[m] := (\mathbf{x}_i^{(1,j)} - \mathbf{x}_i^{(b,j)})[m]$. If $\delta = 0$ we are in the $(m-1)$-th hybrid, else we are in the $m$-th hybrid. Even though we cannot compute $\mathbf{b}_{i,m}^*$ due to the lack of $[a]_2$, the d-vectors can be written directly in $\mathbf{H}_i^*$ and stay invariant thanks to the fact that their coordinates $[1, N]$ are all 0 after $\mathbb{G}_3$. Totally, after $N$ transitions we arrive at $\mathbb{G}_4$ and obtain $|\text{Pr}[\mathbb{G}_4 = 1] - \text{Pr}[\mathbb{G}_3 = 1]| \le 2N \cdot \mathbf{Adv}_{\mathbb{G}_1}^{\text{DDH}}(1^{\lambda})$.
After $G_4$ the vectors are now:

$$c_{\ell, i}^{(j')} = (\mathbf{x}_{\ell, i}^{(j')}, t_{\ell, i}, 0, \rho_{\ell, i}^{(j')}, \mathbf{x}_{\ell, i}^{(j')}, 0^{2N \cdot \tilde{J} + 1})_{\mathbf{B}_i}$$

$$\mathbf{d}_{k, i}^{(j')} = (0^N, \mu_k, \pi_{k, i}^{(j')}, 0, \mathbf{y}_{k, i}^{(j')}, 0^{2N \cdot \tilde{J} + 1})_{\mathbf{B}_i^*}$$

$$\mathbf{c}_i^{(j)} = (\underline{\mathbf{x}}_i^{(1,j)}, t_i, 0, \rho_i^{(j)}, \mathbf{x}_i^{(1,j)}, 0^{2N \cdot \tilde{J} + 1})_{\mathbf{B}_i}$$

$$\mathbf{d}_i^{(j)} = (0^N, \mu, \pi_i^{(j)}, 0, \mathbf{y}_i^{(1,j)}, 0^{2N \cdot \tilde{J} + 1})_{\mathbf{B}_i^*},$$

and they do not depend on the challenge bit $b \leftarrow \{0, 1\}$ anymore, so $\Pr[G_4 = 1] = 1/2$.

The final security loss of the reduction is

$$\begin{aligned} \mathbf{Adv}_{\mathcal{E}, \mathcal{F}_{N_1, \dots, N_n}, \mathcal{A}}^{\text{1chal-pos-stat-wfh}}(1^{\lambda}) &= |\Pr[G_0 = 1] - \frac{1}{2}| \\ &= |\Pr[G_0 = 1] - \Pr[G_4 = 1]| \\ &\le \sum_{i=1}^4 |\Pr[G_i = 1] - \Pr[G_{i-1} = 1]| \\ &\le ((q_k + 1) \cdot (4n\tilde{J}N + 4) + 4N + q_e + 1) \cdot \mathbf{Adv}_{\mathcal{G}_1, \mathcal{G}_2}^{\text{SXDH}}(1^{\lambda}) \end{aligned}$$

and the proof is completed. □

# B Supporting Materials – Section 5

## B.1 From Complete to Incomplete Challenges – Proof of Lemma 2

**Lemma 2.** Assume there exist (1) a one-challenge (weakly function-hiding) DMCFE scheme $\mathcal{E}^{\text{pos}}$ for a function class $\mathcal{F}$ that is secure against complete queries, and (2) an AoNE scheme $\mathcal{E}^{\text{aone}}$ whose message space contains the ciphertext space of $\mathcal{E}^{\text{pos}}$. Then there exists a one-challenge (weakly function-hiding) DMCFE scheme $\mathcal{E}$ for $\mathcal{F}$ that is even secure against incomplete queries. More precisely, for any ppt adversary $\mathcal{A}$, there exist ppt algorithms $\mathcal{B}_1$ and $\mathcal{B}_2$ such that

$$\mathbf{Adv}_{\mathcal{E}, \mathcal{F}, \mathcal{A}}^{\text{1chal-xxx-wfh}}(1^{\lambda}) \le 12 \cdot \mathbf{Adv}_{\mathcal{E}^{\text{pos}}, \mathcal{F}, \mathcal{B}_1}^{\text{1chal-pos-xxx-wfh}}(1^{\lambda}) + 12 \cdot \mathbf{Adv}_{\mathcal{E}^{\text{aone}}, \mathcal{F}^{\text{aone}}, \mathcal{B}_2}^{\text{1chal-xxx-wfh}}(1^{\lambda}),$$

where $\text{xxx} \subseteq \{\text{stat}, \text{sel}\}$.

*Proof.* Let $\mathcal{E}^{\text{pos}} = (\text{pSetup}, \text{pDKeyGen}, \text{pEnc}, \text{pDec})$ be a one-challenge, weakly function-hiding DMCFE scheme for the function class $\mathcal{F}$ that is secure against complete queries. Let $\mathcal{E}^{\text{aone}} = (\text{aSetup}, \text{aEnc}, \text{aDec})$ be a DMCFE scheme for the AoNE functionality $\mathcal{F}^{\text{aone}}$. We construct a one-challenge, weakly function-hiding DMCFE scheme $\mathcal{E}$ for the function class $\mathcal{F}$ that is secure against incomplete queries. The details of $\mathcal{E} = (\text{Setup}, \text{DKeyGen}, \text{Enc}, \text{Dec})$ go as follows:

*Setup(1$^{\lambda}$, 1$^n$)*: On input the security parameter $1^{\lambda}$ and the support $1^n$, run

$$\text{pPP}, (\text{pSK}_i, \text{pEK}_i)_{i \in [n]} \leftarrow \text{pSetup}(1^{\lambda}, 1^n); \quad \text{aPP}, (\text{aEK}_i)_{i \in [n]} \leftarrow \text{aSetup}(1^{\lambda}, 1^n)$$

and return PP := (pPP, aPP), (SK$_i$ := (pSK$_i$, aEK$_i$), EK$_i$ := (pEK$_i$, aEK$_i$))$_{i \in [n]}$.

*DKeyGen SK$_i$, tag-f, y$_i$)*: On input a secret key SK$_i$, a tag tag-f, and y$_i$, compute

$$\text{pDK}_i \leftarrow \text{pDKeyGen}(\text{pSK}_i, \text{tag-f}, y_i); \quad \text{aDK}_i \leftarrow \text{aEnc}(\text{aEK}_i, \text{tag-f}, \text{pDK}_i)$$

and return DK$_i := aDK_i$.
Enc(EKᵢ, tag, xᵢ): On input an encryption key EKᵢ, a tag tag, and xᵢ, compute:

$$p\text{CT}_i \leftarrow p\text{Enc}(p\text{EK}_i, \text{tag}, x_i); \quad a\text{CT}_i \leftarrow a\text{Enc}(a\text{EK}_i, \text{tag}, p\text{CT}_i)$$

and return CTᵢ := aCTᵢ.

Dec((DKᵢ)ᵢ∈[n], (CTᵢ)ᵢ∈[n]): On input a set of functional keys (DKᵢ)ᵢ∈[n] and a set of ciphertexts (CTᵢ)ᵢ∈[n], compute

$$(p\text{DK}_i)_{i \in [n]} \leftarrow a\text{Dec}((a\text{DK}_i)_{i \in [n]}); \quad (p\text{CT}_i)_{i \in [n]} \leftarrow a\text{Dec}((a\text{CT}_i)_{i \in [n]}).$$

If one of these decryption processes returns ⊥, return ⊥. Otherwise, return

$$\text{out} \leftarrow p\text{Dec}((p\text{DK}_i)_{i \in [n]}, (p\text{CT}_i)_{i \in [n]}).$$

The correctness of E follows immediately from the correctness of E<sup>pos</sup> and E<sup>aone</sup>. Turning to its security, we introduce a sequence of hybrids G<sub>0</sub>, ..., G<sub>4</sub>. For i ∈ [0; 4], we denote **Adv**<sup>G<sub>i</sub></sup>(A) := |Pr[G<sub>i</sub> = 1] - 1/2|. To improve readability, we introduce the shorthands

$$(\text{Exp}_{B_1}^{\text{ip}}, \text{Adv}_{B_1}^{\text{ip}}) := (\text{Exp}_{\mathcal{E}^{\text{pos}}, \mathcal{F}, B_1}^{\text{chal-pos-xxx-wfh}}(1^{\lambda}), \text{Adv}_{\mathcal{E}^{\text{pos}}, \mathcal{F}, B_1}^{\text{chal-pos-xxx-wfh}}(1^{\lambda}))$$

$$(\text{Exp}_{B_2}^{\text{aone}}, \text{Adv}_{B_2}^{\text{aone}}) := (\text{Exp}_{\mathcal{E}^{\text{aone}}, f_{\text{aone}}, B_2}^{\text{chal-xxx-wfh}}(1^{\lambda}), \text{Adv}_{\mathcal{E}^{\text{aone}}, f_{\text{aone}}, B_2}^{\text{chal-xxx-wfh}}(1^{\lambda})).$$

The hybrid games are defined as follows.

**Game G<sub>0</sub>:** This game equals Exp<sup>chal-xxx-wfh</sup><sub>E, F, A</sub>(1<sup>λ</sup>), so we have Adv<sup>G<sub>0</sub></sup> = Adv<sup>chal-xxx-wfh</sup><sub>E, F, A</sub>(1<sup>λ</sup>).

Recall that one-challenge security states that the adversary must declare up front to Initialize additional public information for challenge messages and challenge keys tag*, tag-f* so that:

* if (i, tag, x<sub>i</sub><sup>(0)</sup>, x<sub>i</sub><sup>(1)</sup>) ∈ Q<sub>Enc</sub> and tag ≠ tag*, then x<sub>i</sub><sup>(0)</sup> = x<sub>i</sub><sup>(1)</sup>,

* if (i, tag-f, y<sub>i</sub><sup>(0)</sup>, y<sub>i</sub><sup>(1)</sup>) ∈ Q<sub>KG<sub>en</sub></sub> and tag-f ≠ tag-f*, then y<sub>i</sub><sup>(0)</sup> = y<sub>i</sub><sup>(1)</sup>.

We define events E<sub>0</sub> and E<sub>1</sub> as follows:

(E<sub>0</sub>) A has asked queries of the form OKeyGen(i, tag-f, y<sub>i</sub><sup>(0)</sup>, y<sub>i</sub><sup>(1)</sup>) for all or no i ∈ H ∩ [n].

(E<sub>1</sub>) A has asked queries of the form OKeyGen(i, tag-f, y<sub>i</sub><sup>(0)</sup>, y<sub>i</sub><sup>(1)</sup>) for some but not all i ∈ H ∩ [n], i.e. E<sub>1</sub> = ¬E<sub>0</sub>.

**Game G<sub>1</sub>:** This is the same as G<sub>0</sub> except that the simulator chooses a random bit d ↪→ {0, 1} during Initialize. Upon A calling Finalize, if (d = 0 and E<sub>1</sub> happens) or (d = 1 and E<sub>0</sub> happens), the simulator outputs 0. Intuitively the guess d indicates whether our simulator will break the one-challenge complete security of E<sup>pos</sup> (E<sub>0</sub> happens) or break the one-challenge security of E<sup>aone</sup> (E<sub>1</sub> happens), while simulating the corresponding game to A. Note that the simulator's behavior is independent of the bit d before Finalize is called. Therefore, we have Adv<sup>G<sub>1</sub></sup>(A) = 1/2 · Adv<sup>G<sub>0</sub></sup>(A).

**Game G<sub>2</sub>:** If d = 1, then the simulation works exactly as in the previous game. Otherwise, the simulator acts as an adversary B<sub>1</sub> in the game Exp<sup>ip</sup><sub>B<sub>1</sub></sub>. W.l.o.g., we assume that each i ∈ [n] is queried at most once to OCorrupt because all secret and encryption keys are fixed from setup time.
* Initialization: Upon $\mathcal{A}$ calling Initialize$(1^{\lambda}, \text{tag}^*, \text{tag-f}^*)$, $\mathcal{B}_1$ chooses a random bit $b \leftarrow \{0, 1\}$, and initializes empty sets $\mathcal{C}$ and $\mathcal{H}$, runs

$$ \mathit{aPP}, (\mathit{aEK}_i)_{i \in [n]} \leftarrow \mathit{aSetup}(1^{\lambda}, 1^n) $$

then call the Initialize oracle of $\mathcal{E}^{\text{pos}}$

$$ \mathit{pPP}, (\mathit{pSK}_i, \mathit{pEK}_i)_{i \in [n]} \leftarrow \mathit{pSetup}(1^{\lambda}, 1^n) $$

to obtain pPP. $\mathcal{B}_1$ returns PP := (pPP, aPP).

* Corruption Queries: Upon $\mathcal{A}$ querying $\mathcal{O}$Corrupt$(i)$ for some $i \in \mathcal{I}$, $\mathcal{B}_1$ first checks whether $\mathcal{O}$Corrupt has previously been called on the same input and returns the same value as before in this case. It then adds $i$ to $\mathcal{C}$, queries $(\mathit{pSK}_i, \mathit{pEK}_i) \leftarrow \mathbf{Exp}_{\mathcal{B}_1}^{\text{ip}}$. $\mathcal{O}$Corrupt$(i)$ and returns $\mathit{SK}_i := (\mathit{pSK}_i, \mathit{aEK}_i)$, $\mathit{EK}_i := (\mathit{pEK}_i, \mathit{aEK}_i)$.

* Encryption Queries: Upon $\mathcal{A}$ querying $\mathcal{O}$Enc$(i, \text{tag}, x^{(0)}, x^{(1)})$, $\mathcal{B}_1$ queries and computes

$$ \mathit{pCT}_i \leftarrow \mathbf{Exp}_{\mathcal{B}_1}^{\text{ip}}.\mathcal{OEnc}(i, \text{tag}, x^{(0)}, x^{(1)}); \quad \mathit{aCT}_i \leftarrow \mathcal{E}^{\text{aone}}.\mathit{Enc}(\mathit{aEK}_i, \text{tag}, \mathit{pCT}_i) $$

and returns $\mathit{CT}_i := \mathit{aCT}_i$.

* Key-Generation Queries: Upon $\mathcal{A}$ querying $\mathcal{O}$DKeyGen on input $(i, \text{tag-f}, y^{(0)}, y^{(1)})$, $\mathcal{B}_1$ does the following:

* If $\text{tag-f} = \text{tag-f}^*$, $\mathcal{B}_1$ queries

$$ \mathit{pDK}_i \leftarrow \mathbf{Exp}_{\mathcal{B}_1}^{\text{ip}}.\mathcal{OKeyGen}(i, \text{tag-f}^*, y^{(b)}, y^{(1)}); \quad \mathit{aDK}_i \leftarrow \mathcal{E}^{\text{aone}}.\mathit{Enc}(\mathit{aEK}_i, \text{tag-f}^*, \mathit{pDK}_i) $$

* If $\text{tag-f} \neq \text{tag-f}^*$, then $y^{(0)} = y^{(1)}$ and $\mathcal{B}_1$ queries

$$ \mathit{pDK}_i \leftarrow \mathbf{Exp}_{\mathcal{B}_1}^{\text{ip}}.\mathcal{OKeyGen}(i, \text{tag-f}, y^{(1)}, y^{(1)}); \quad \mathit{aDK}_i \leftarrow \mathcal{E}^{\text{aone}}.\mathit{Enc}(\mathit{aEK}_i, \text{tag-f}^*, \mathit{pDK}_i) $$

and returns $\mathit{DK}_i := \mathit{aDK}_i$.

* Finalize: Upon $\mathcal{A}$ calling Finalize$(b')$, $\mathcal{B}_1$ forwards the same bit to its own challenger by calling $\mathbf{Exp}_{\mathcal{B}_1}^{\text{ip}}$. Finalize$(b')$.

In the end, we have $|\mathbf{Adv}_{\mathcal{G}_2}(\mathcal{A}) - \mathbf{Adv}_{\mathcal{G}_1}(\mathcal{A})| \le 2 \cdot \mathbf{Adv}_{\mathcal{B}_1}^{\text{ip}}$.

**Game G3:** We do a similar modification in the simulation for the case $d = 1$. The indistinguishability between $G_3$ and $G_2$ reduces to the security of $\mathcal{E}^{\text{aone}}$. More specifically, we construct a reduction $\mathcal{B}_2$ that acts as an adversary in the experiment $\mathbf{Exp}_{\mathcal{B}_2}^{\text{aone}}$. The simulator $\mathcal{B}_2$ uses its AoNE oracles, while setting up by itself the $\mathcal{E}^{\text{pos}}$. In particular, upon $\mathcal{A}$ querying $\mathcal{O}$DKeyGen on input $(i, \text{tag-f}^*, y^{(0)}, y^{(1)})$, $\mathcal{B}_2$ does the following:

* If $\text{tag-f} = \text{tag-f}^*$, $\mathcal{B}_2$ computes

$$ \mathit{pDK}_i \leftarrow \mathcal{E}^{\text{pos}}.\text{KeyGen}(\mathit{pSK}_i, \text{tag-f}^*, y^{(b)}) $$

$$ \mathit{pDK}'_i \leftarrow \mathcal{E}^{\text{pos}}.\text{KeyGen}(\mathit{pSK}_i, \text{tag-f}^*, y^{(1)}) $$

then queries

$$ \mathit{aDK}_i \leftarrow \mathbf{Exp}_{\mathcal{B}_2}^{\text{aone}}.\mathcal{OLoR}(i, \text{tag-f}^*, \mathit{pDK}_i, \mathit{pDK}'_i) $$

* If $\text{tag-f} \neq \text{tag-f}^*$, then $y^{(0)} = y^{(1)}$ and $\mathcal{B}_2$ queries

$$ \mathit{pDK}_i \leftarrow \mathcal{E}^{\text{pos}}.\text{KeyGen}(\mathit{pSK}_i, \text{tag-f}, y^{(1)}) $$

$$ \mathit{aDK}_i \leftarrow \mathbf{Exp}_{\mathcal{B}_2}^{\text{aone}}.\mathcal{OLoR}(i, \text{tag-f}, \mathit{pDK}_i, \mathit{pDK}_i) $$

and returns $\mathit{DK}_i := \mathit{aDK}_i$. In the end, we have $|\mathbf{Adv}_{\mathcal{G}_3}(\mathcal{A}) - \mathbf{Adv}_{\mathcal{G}_2}(\mathcal{A})| \le 2 \cdot \mathbf{Adv}_{\mathcal{B}_2}^{\text{aone}}$.
**Game G<sub>4</sub>:** We answer queries of the form $\mathcal{OEnc}(i, \text{tag}^*, x^{(0)}, x^{(1)})$ by encryptions of $(x^{(1)}, \text{tag}^*)$ as opposed to $(x^{(b)}, \text{tag}^*)$ using a similar sequence of hybrids as $G_1$, $G_2$ and $G_3$, but with flipped roles of the oracles $\mathcal{OKeyGen}$ and $\mathcal{OEnc}$. Note that $G_4$ is independent of the bit $b$. In the end, we obtain $\mathbf{Adv}^{G_3}(\mathcal{A}) \le 2 \cdot (\mathbf{Adv}^{G_4}(\mathcal{A}) + 2 \cdot \mathbf{Adv}_{B_1}^{\text{ip}} + 2 \cdot \mathbf{Adv}_{B_2}^{\text{aone}})$.

To conclude, we compute

$$ 
\begin{aligned}
\mathbf{Adv}_{\mathcal{E}, \mathcal{F}, \mathcal{A}}^{\text{1chal-xxx-wfh}}(1^{\lambda}) &= \mathbf{Adv}^{G_0}(\mathcal{A}) \\
&= 2 \cdot \mathbf{Adv}^{G_1}(\mathcal{A}) \\
&\le 2 \cdot (\mathbf{Adv}^{G_2}(\mathcal{A}) + 2 \cdot \mathbf{Adv}_{B_1}^{\text{ip}}) \\
&\le 2 \cdot (\mathbf{Adv}^{G_3}(\mathcal{A}) + 2 \cdot \mathbf{Adv}_{B_1}^{\text{ip}} + 2 \cdot \mathbf{Adv}_{B_2}^{\text{aone}}) \\
&\le 4 \cdot \mathbf{Adv}^{G_4}(\mathcal{A}) + 12 \cdot \mathbf{Adv}_{B_1}^{\text{ip}} + 12 \cdot \mathbf{Adv}_{B_2}^{\text{aone}} \\
&= 12 \cdot \mathbf{Adv}_{B_1}^{\text{ip}} + 12 \cdot \mathbf{Adv}_{B_2}^{\text{aone}},
\end{aligned}
$$

where the last equality follows from the fact that $G_4$ is independent of $b$. $\square$

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

## B.2 From One-Challenge to Multi-Challenge – Proof of Lemma 3

**Lemma 3.** Let $\mathcal{E} = (\text{Setup}, \text{DKeyGen}, \text{Enc}, \text{Dec})$ be a DMCFE scheme for the function class $\mathcal{F}$. If $\mathcal{E}$ is one-challenge weakly function-hiding, then it is also weakly function-hiding. More specifically, for any ppt adversary $\mathcal{A}$, there exists a ppt algorithm $\mathcal{B}$ such that

$$ \mathbf{Adv}_{\mathcal{E}, \mathcal{F}, \mathcal{A}}^{\text{xxx-wfh}}(1^{\lambda}) \le (q_e + q_k) \cdot \mathbf{Adv}_{\mathcal{E}, \mathcal{F}, \mathcal{B}}^{\text{1chal-xxx-wfh}}(1^{\lambda}), $$

where $q_e$ and $q_k$ denote the maximum numbers of different tags tag and tag-f that $\mathcal{A}$ can query to $\mathcal{OEnc}$ and $\mathcal{ODKeyGen}$ respectively, and $\text{xxx} \subseteq \{\text{stat}, \text{sel}, \text{pos}\}$.

*Proof.* Let $\mathcal{A}$ be a ppt adversary in the experiment $\mathbf{Exp}_{\mathcal{E}, \mathcal{F}, \mathcal{A}}^{\text{xxx-wfh}}(1^{\lambda})$ and $b \leftarrow \{0, 1\}$ be the challenge bit. We denote the $q_e$ distinct tag that can occur in a query to $\mathcal{OEnc}$ by $\text{tag}_1, \dots, \text{tag}_{q_e}$. Similarly, we denote the $q_k$ distinct tag-f that can occur in queries to $\mathcal{OKeyGen}$ by $\text{tag-f}_1, \dots, \text{tag-f}_{q_k}$. We define a sequence of hybrid games:

**Game $G_{1,j}$ for $j \in [0; q_k]$:** This hybrid is the same as $\mathbf{Exp}_{\mathcal{E}, \mathcal{F}, \mathcal{A}}^{\text{xxx-wfh}}(1^{\lambda})$ except that a query $\mathcal{OKeyGen}(i, \text{tag-f}_\ell, (y_i^{(0)}, y_i^{(1)}))$ is answered by a decryption key for $(y_i^{(1)}, \text{tag-f}_\ell)$ if $\ell \le j$, and by a decryption key for $(y_i^{(0)}, \text{tag-f}_\ell)$ if $\ell > j$. Note that $G_{1,0} = \mathbf{Exp}_{\mathcal{E}, \mathcal{F}, \mathcal{A}}^{\text{xxx-wfh}}(1^{\lambda})$, conditioned on $b = 0$ as the challenge bit. The indistinguishability between $G_{1,j}$ and $G_{1,j-1}$ for $j \in [q_k]$ is proven in Lemma 5.

**Game $G_{2,j}$ for $j \in [0; q_e]$:** This hybrid is the same as $G_{1,q_k}$ except that a query $\mathcal{OEnc}(i, \text{tag}_\ell, (x_i^{(0)}, x_i^{(1)}))$ is answered by an encryption of $(x_i^{(1)}, \text{tag}_\ell)$ if $\ell \le j$ (as opposed to $(x_i^{(0)}, \text{tag}_\ell)$). Note that $G_{2,0} = G_{1,q_k}$ and $G_{2,q_e} = \mathbf{Exp}_{\mathcal{E}, \mathcal{F}, \mathcal{A}}^{\text{xxx-wfh}}(1^{\lambda})$, conditioned on $b = 1$ as the challenge bit. The indistinguishability between $G_{2,j}$ and $G_{2,j-1}$ for $j \in [q_e]$ is proven in Lemma 6.

For any hybrid $G_{t,j}$, with $t \in [2]$, $j \in [0, q_e] \cup [0, q_k]$, we define the event $G_{t,j} = 1$ to indicate
that $\mathcal{A}$ outputs 1 in $G_{t,j}$. We calculate the advantage as follows:

$$
\begin{align*}
\mathbf{Adv}_{\mathcal{E},f,\mathcal{A}}^{\text{xxx-wfh}} (1^{\lambda})
&= \frac{1}{2} \cdot \left| \Pr[\mathcal{A} \text{ outputs 1 in } \mathbf{Exp}_{\mathcal{E},f,\mathcal{A}}^{\text{xxx-wfh}}(1^{\lambda}) | b=1] \\
&\quad - \Pr[\mathcal{A} \text{ outputs 1 in } \mathbf{Exp}_{\mathcal{E},f,\mathcal{A}}^{\text{xxx-wfh}}(1^{\lambda}) | b=0] \right| \\
&= \frac{1}{2} \cdot \left| \Pr[G_{2,q_e} = 1] - \Pr[G_{1,0} = 1] \right| \\
&= \frac{1}{2} \cdot \left| \sum_{j=1}^{q_k} (\Pr[G_{1,j} = 1] - \Pr[G_{1,j-1} = 1]) + \sum_{j=1}^{q_e} (\Pr[G_{2,j} = 1] - \Pr[G_{2,j-1} = 1]) \right| \\
&\le \frac{1}{2} \cdot \left( \sum_{j=1}^{q_k} |\Pr[G_{1,j} = 1] - \Pr[G_{1,j-1} = 1]| + \sum_{j=1}^{q_e} |\Pr[G_{2,j} = 1] - \Pr[G_{2,j-1} = 1]| \right) \\
&\le (q_k + q_e) \cdot \mathbf{Adv}_{\mathcal{E},f,\mathcal{B}}^{\text{1chal-xxx-wfh}}(1^{\lambda}) ,
\end{align*}
$$

where the last inequality is a consequence of Lemmas 5 and 6.

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

**Lemma 5.** If $\mathcal{E}$ is weakly function-hiding, then we have for each $j \in [q_k]$ that

$$
|\Pr[G_{1,j} = 1] - \Pr[G_{1,j-1} = 1]| \le 2 \cdot \mathbf{Adv}_{\mathcal{E},f,\mathcal{B}}^{\text{1chal-xxx-wfh}}(1^{\lambda}) .
$$

*Proof.* Let $\mathcal{A}$ be an adversary trying to distinguish between $G_{1,j}$ and $G_{1,j-1}$. We construct a ppt adversary $\mathcal{B}$ playing against $\mathbf{Exp}_{\mathcal{E},f,\mathcal{B}}^{\text{1chal-xxx-wfh}}(1^{\lambda})$ that uses black-box access to $\mathcal{A}$. $\mathcal{B}$ simulates the view of $\mathcal{A}$ as follows:

* Initialization: Upon $\mathcal{A}$ calling Initialize($1^{\lambda}$, $1^n$), $\mathcal{B}$ runs the initialization procedure

$$
\text{Initialize}(1^{\lambda}, 1^n, \text{tag-f}^* := \text{tag-f}_j, \text{tag}^* := \text{tag}_j)
$$

of $\mathbf{Exp}_{\mathcal{E},f,\mathcal{B}}^{\text{1chal-xxx-wfh}}(1^{\lambda})$ and forwards the response to $\mathcal{A}$.

* Encryption Queries: Upon $\mathcal{A}$ querying $\mathcal{OEnc}(i, \text{tag}_\ell, (x_i^{(0)}, x_i^{(1)}))$, $\mathcal{B}$ queries the oracle $\mathcal{OEnc}$ of $\mathbf{Exp}_{\mathcal{E},f,\mathcal{B}}^{\text{1chal-xxx-wfh}}(1^\lambda)$ on input $(i, \text{tag}_\ell, (x_i^{(0)}, x_i^{(1)}))$ and forwards the response to $\mathcal{A}$ for all $\ell \in [q_e]$.

* Key-Generation Queries:

Upon $\mathcal{A}$ querying $\mathcal{OKeyGen}$ on input $(i, \text{tag-f}_\ell, (y_i^{(0)}, y_i^{(1)}))$, $\mathcal{B}$ does:

1. If $\ell < j$, $\mathcal{B}$ queries $(i, \text{tag-f}_\ell, (y_i^{(1)}, y_i^{(1)}))$ to the oracle $\mathcal{OKeyGen}$ of the experiment $\mathbf{Exp}_{\mathcal{E},f,\mathcal{B}}^{\text{1chal-xxx-wfh}}(1^\lambda)$ and forwards the response to $\mathcal{A}$.

2. If $\ell = j$, $\mathcal{B}$ queries $\mathcal{OKeyGen}(i, \text{tag-f}_j, (y_i^{(0)}, y_i^{(1)}))$ and forwards to $\mathcal{A}$ the response.

3. If $\ell > j$, $\mathcal{B}$ queries $\mathcal{OKeyGen}(i, \text{tag-f}_\ell, (y_i^{(0)}, y_i^{(1)}))$ and forwards to $\mathcal{A}$ the response.

* Corruption Queries: Upon $\mathcal{A}$ querying $\mathcal{OCorrupt}(i)$, $\mathcal{B}$ queries $\mathcal{OCorrupt}$ of the experiment $\mathbf{Exp}_{\mathcal{E},f,\mathcal{B}}^{\text{1chal-xxx-wfh}}(1^{\lambda})$ on the same input $i$ and forwards the response to $\mathcal{A}$.

* Finalize: Upon $\mathcal{A}$ calling Finalize($b'$), $\mathcal{B}$ passes the same bit $b'$ to its own Finalize procedure.
We note that $\mathcal{A}$ is an admissible adversary in $G_{1,j}$ and $G_{1,j-1}$ if and only if $\mathcal{B}$ is an admissible adversary against $\mathbf{Exp}_{\mathcal{E},f,\mathcal{B}}^{\text{1chal-xxx-wfh}}(1^{\lambda})$. Moreover, we observe that $\mathcal{B}$ simulates $G_{1,j-1}$ to $\mathcal{A}$ if $b=0$, and $G_{1,j}$ otherwise. Thus, we calculate

$$ \begin{aligned} \left| \Pr[G_{1,j} = 1] - \Pr[G_{1,j-1} = 1] \right| &= \left| \Pr[\mathcal{B} \text{ outputs 1 in } \mathbf{Exp}_{\mathcal{E},f,\mathcal{B}}^{\text{1chal-xxx-wfh}}(1^{\lambda}) \mid b=1] \right. \\ & \qquad \left. - \Pr[\mathcal{B} \text{ outputs 1 in } \mathbf{Exp}_{\mathcal{E},f,\mathcal{B}}^{\text{1chal-xxx-wfh}}(1^{\lambda}) \mid b=0] \right| \\ & \le 2 \cdot \mathbf{Adv}_{\mathcal{E},f,\mathcal{B}}^{\text{1chal-xxx-wfh}}(1^{\lambda}) \end{aligned} $$

and the lemma is concluded.

□

**Lemma 6.** If $\mathcal{E}$ is weakly function-hiding, then we have for each $j \in [q_k]$ that

$$ \left| \Pr[G_{2,j} = 1] - \Pr[G_{2,j-1} = 1] \right| \le 2 \cdot \mathbf{Adv}_{\mathcal{E},f,\mathcal{B}}^{\text{1chal-xxx-wfh}}(1^{\lambda}) . $$

*Proof.* Let $\mathcal{A}$ be an adversary trying to distinguish between $G_{2,j}$ and $G_{2,j-1}$. We construct a ppt adversary $\mathcal{B}$ playing against $\mathbf{Exp}_{\mathcal{E},f,\mathcal{B}}^{\text{1chal-xxx-wfh}}(1^{\lambda})$ that uses black-box access to $\mathcal{A}$. $\mathcal{B}$ simulates the view of $\mathcal{A}$ as follows:

* Initialization: Upon $\mathcal{A}$ calling $\text{Initialize}(1^{\lambda}, 1^n)$, $\mathcal{B}$ runs the initialization procedure

$$ \text{Initialize}(1^{\lambda}, 1^n, \text{tag-f}^* := \text{tag-f}_j, \text{tag}^* := \text{tag}_j) $$

of $\mathbf{Exp}_{\mathcal{E},f,\mathcal{B}}^{\text{1chal-xxx-wfh}}(1^{\lambda})$ and forwards the response to $\mathcal{A}$.

* Encryption Queries: Upon $\mathcal{A}$ querying $\mathcal{OEnc}(i, \text{tag}_\ell, (x_i^{(0)}, x_i^{(1)}))$, $\mathcal{B}$ behaves as follows:

1. If $\ell < j$, $\mathcal{B}$ queries $(i, \text{tag}_\ell, (x_i^{(1)}, x_i^{(1)}))$ to the oracle $\mathcal{OEnc}$ of $\mathbf{Exp}_{\mathcal{E},f,\mathcal{B}}^{\text{1chal-xxx-wfh}}(1^{\lambda})$ and forwards the response to $\mathcal{A}$.

2. If $\ell = j$, $\mathcal{B}$ queries $\mathcal{OEnc}(i, \text{tag}_j, (x_i^{(0)}, x_i^{(1)}))$ and forwards the response to $\mathcal{A}$.

3. If $\ell > j$, $\mathcal{B}$ queries $\mathcal{OEnc}(i, \text{tag}_\ell, (x_i^{(0)}, x_i^{(0)}))$ and forwards the response to $\mathcal{A}$.

* Key-generation Queries: Upon $\mathcal{A}$ querying $\mathcal{OKeyGen}(i, \text{tag-f}_\ell, (y_i^{(0)}, y_i^{(1)}))$, $\mathcal{B}$ queries $(i, \text{tag-f}_\ell, (y_i^{(1)}, y_i^{(1)}))$ the oracle $\mathcal{OEnc}$ of $\mathbf{Exp}_{\mathcal{E},f,\mathcal{B}}^{\text{1chal-xxx-wfh}}(1^{\lambda})$ and forwards the response to $\mathcal{A}$, for all $\ell \in [q_k]$.

* Corruption Queries: Upon $\mathcal{A}$ querying $\mathcal{OCorrupt}(i)$ for some $i \in [n]$, $\mathcal{B}$ queries the oracle $\mathcal{OCorrupt}$ of $\mathbf{Exp}_{\mathcal{E},f,\mathcal{B}}^{\text{1chal-xxx-wfh}}(1^{\lambda})$ on the same input $i$ and forwards the response $(\text{ek}_i, \text{sk}_i)$ to $\mathcal{A}$.

* Finalize: Upon $\mathcal{A}$ calling $\text{Finalize}(b')$, $\mathcal{B}$ passes the same bit $b'$ to its own Finalize procedure.

We note that $\mathcal{A}$ is an admissible adversary in $G_{2,j}$ and $G_{2,j-1}$ if and only if $\mathcal{B}$ is an admissible adversary against $\mathbf{Exp}_{\mathcal{E},f,\mathcal{B}}^{\text{1chal-xxx-wfh}}(1^{\lambda})$. Moreover, we observe that $\mathcal{B}$ simulates $G_{2,j-1}$ if $b=0$, and $G_{2,j}$ otherwise. Using the same calculation as in Lemma 5, we conclude that

$$ \left| \Pr[G_{2,j} = 1] - \Pr[G_{2,j-1} = 1] \right| \le 2 \cdot \mathbf{Adv}_{\mathcal{E},f,\mathcal{B}}^{\text{1chal-xxx-wfh}}(1^{\lambda}) $$

and the proof is completed.

□
## B.3 From Weak to Full Function-Hiding – Proof of Lemma 4

**Lemma 4.** If there exists a weakly function-hiding DMCFE scheme $\mathcal{E}$ for $\mathcal{F}^{\text{ip}}$, then there exists a (fully) function-hiding DMCFE scheme $\mathcal{E}'$ for $\mathcal{F}^{\text{ip}}$. More precisely, for any ppt adversary $\mathcal{A}$, there exists a ppt algorithm $\mathcal{B}$ such that

$$ \mathbf{Adv}_{\mathcal{E}', \mathcal{F}^{\text{fh}}, \mathcal{A}}^{\mathcal{E}^{\text{xxx-fh}}}(1^{\lambda}) \le 3 \cdot \mathbf{Adv}_{\mathcal{E}', \mathcal{F}^{\text{fh}}, \mathcal{B}}^{\mathcal{E}^{\text{xxx-wfh}}}(1^{\lambda}), $$

where $\mathcal{X} \subseteq \{\text{stat}, \text{sel}, \text{1chal}, \text{pos}\}$.

*Proof.* Given $\mathcal{E} = (\text{Setup}, \text{DKeyGen}, \text{Enc}, \text{Dec})$, we define the fully function-hiding scheme $\mathcal{E}' = (\text{Setup}', \text{DKeyGen}', \text{Enc}', \text{Dec}')$ for $\mathcal{F}^{\text{ip}}$ as follows:

*   **Setup:** $\text{Setup}'(1^{\lambda}, 1^{2n})$ runs

$$ (\{\text{sk}_i\}_{i \in [n]}, \{\text{ek}_i\}_{i \in [n]}, \text{pp}) \leftarrow \text{Setup}(1^{\lambda}, 1^n), $$

and outputs $\{\text{sk}'_i := \text{sk}_i\}_{i \in [n]}$, $\{\text{ek}'_i := \text{ek}_i\}_{i \in [n]}$ and $\text{pp}' := \text{pp}$.

*   **Key Generation:** $\text{DKeyGen}'(\text{sk}'_i, \text{tag-f}, \mathbf{y}_i)$ parses $\text{sk}'_i = \text{sk}_i$, runs

$$ \text{dk}_i \leftarrow \text{DKeyGen}(\text{sk}_i, \text{tag-f}, \mathbf{y}_i \parallel \mathbf{0}^N), $$

and outputs $\text{dk}'_i := \text{dk}_i$.

*   **Encryption:** $\text{Enc}'(\text{ek}'_i, \text{tag}, \mathbf{x}_i)$ parses $\text{ek}'_i = \text{ek}_i$, computes a ciphertext

$$ \text{ct}_i \leftarrow \text{Enc}(\text{ek}_i, \text{tag}, \mathbf{x}_i \parallel \mathbf{0}^N, \mathcal{U}_{M,i}, \text{tag}_i), $$

and outputs $\text{ct}'_i := \text{ct}_i$.

*   **Decryption:** $\text{Dec}((\text{dk}'_{\text{tag-f},i})_{i \in [n]}, (\text{ct}'_{\text{tag},i})_{i \in [n]})$ outputs

$$ d \leftarrow \text{Dec}((\text{dk}'_{\text{tag-f},i})_{i \in [n]}, (\text{ct}'_{\text{tag},i})_{i \in [n]}). $$

The correctness of $\mathcal{E}'$ follows immediately from that of $\mathcal{E}$ and the fact that

$$ \langle (\mathbf{x}_i \parallel \mathbf{0}^N)_{i \in [n]}, (\mathbf{y}_i \parallel \mathbf{0}^N)_{i \in [n]} \rangle = \langle (\mathbf{x}_i)_{i \in [n]}, (\mathbf{y}_i)_{i \in [n]} \rangle, $$

where we denote $(\mathbf{z}_i)_{i \in [n]} := (\mathbf{z}_1 \parallel \dots \parallel \mathbf{z}_n)$ for arbitrary vectors $\mathbf{z}_1, \dots, \mathbf{z}_n$. Furthermore, we show that $\mathcal{E}'$ enjoys the function-hiding property. Towards this, we consider a sequence of hybrid games $G_0, \dots, G_3$ where $G_0$ equals $\text{Exp}_{\mathcal{E}', \mathcal{F}^{\text{fh}}, \mathcal{A}}^{\mathcal{E}^{\text{xxx-fh}}}(1^{\lambda})$, where the challenge bit is 0, and $G_3$ equals $\text{Exp}_{\mathcal{E}', \mathcal{F}^{\text{fh}}, \mathcal{A}}^{\mathcal{E}^{\text{xxx-fh}}}(1^{\lambda})$, where the challenge bit is 1, and $\mathcal{A}$ is a ppt adversary. For $i \in [3]$, we denote the event $G_i = 1$ to signify that $\mathcal{A}$ outputs 1 in the hybrid $G_i$.

**Game $G_0$:** This is $\text{Exp}_{\mathcal{E}', \mathcal{F}^{\text{fh}}, \mathcal{A}}^{\mathcal{E}^{\text{xxx-fh}}}(1^{\lambda})$ conditioned on the challenge bit $b = 0$. We denote the $\ell$-th distinct tag that occurs in a query to $\mathcal{OEnc}$ by $\text{tag}_\ell$. Similarly, $\text{tag-f}_k$ refers to the $k$-th distinct tag in a query to $\mathcal{OKeyGen}$. Queries to $\mathcal{OEnc}$ and $\mathcal{OKeyGen}$ are answered as follows:

*   Upon $\mathcal{A}$ querying

$$ \mathcal{OEnc}(i, \text{tag}_\ell, \mathbf{x}_i^{(0)}, \mathbf{x}_i^{(1)}) $$

the simulator $\mathcal{B}$ queries to its weakly function-hiding oracle for

$$ \text{ct}_{\ell,i} \leftarrow \text{Enc}(i, \text{tag}_\ell, \mathbf{x}_i^{(0)} \parallel \mathbf{0}^N, \mathbf{x}_i^{(0)} \parallel \mathbf{0}^N) $$

and returns $\text{ct}'_{\ell,i} := \text{ct}_{\ell,i}$.
• Upon $\mathcal{A}$ querying $\mathcal{OKeyGen}(i, \text{tag-f}_k, \mathbf{y}_i^{(0)}, \mathbf{y}_i^{(1)})$, the simulator $\mathcal{B}$ queries to its weakly function-hiding oracle for

$$dk_{k,i} \leftarrow \text{KeyGen}(i, \text{tag-f}_k, \mathbf{y}_i^{(0)} \parallel 0^N, \mathbf{y}_i^{(0)} \parallel 0^N)$$

and returns $dk'_{k,i} := dk_{k,i}$.

We note that the vector's length $N$ is included in $\mathcal{P}\mathcal{P}$ which can be known to the simulator via the setup of Initialize($1^{\lambda}, 1^n$), upon requests from $\mathcal{A}$. In other words, the ciphertexts $(ct'_{\ell,i})_{i \in [n]}$ encrypt the vector $(\mathbf{x}_i^{(0)} \parallel 0^N)_{i \in [n]}$, and the partial decryption keys $(dk'_{k,i})_{i \in [n]}$ allow for the computation of the inner product with the vector $(\mathbf{y}_i^{(0)} \parallel 0^N)_{i \in [n]}$.

**Game G$_1$:** We modify the definition of $\mathcal{OEnc}$ and $\mathcal{OKeyGen}$ as follows:

• Upon $\mathcal{A}$ querying

$$\mathcal{OEnc}(i, \text{tag}_\ell, \mathbf{x}_i^{(0)}, \mathbf{x}_i^{(1)})$$

the challenger queries to its weakly function-hiding oracle for

$$ct_{\ell,i} \leftarrow \text{Enc}(i, \text{tag}_\ell, 0^N \parallel \mathbf{x}_i^{(1)}, 0^N \parallel \mathbf{x}_i^{(1)})$$

and returns $ct'_{\ell,i} := ct_{\ell,i}$.

• Upon $\mathcal{A}$ querying $\mathcal{OKeyGen}(i, \text{tag-f}_k, \mathbf{y}_i^{(0)}, \mathbf{y}_i^{(1)})$, the challenger queries to its weakly function-hiding oracle for

$$dk_{k,i} \leftarrow \text{KeyGen}(i, \text{tag-f}_k, \mathbf{y}_i^{(0)} \parallel \mathbf{y}_i^{(1)}, \mathbf{y}_i^{(0)} \parallel \mathbf{y}_i^{(1)})$$

and returns $dk'_{k,i} := dk_{k,i}$.

Thus, the ciphertexts $(ct'_{\ell,i})_{i \in [n]}$ encrypt the vector $(0^N \parallel \mathbf{x}_i^{(1)})_{i \in [n]}$ (as opposed to $(\mathbf{x}_i^{(0)} \parallel 0^N)_{i \in [n]}$ in $G_0$), and the partial decryption keys $(dk'_{k,i})_{i \in [n]}$ allow for the computation of the inner product with the vector $(\mathbf{y}_i^{(0)} \parallel \mathbf{y}_i^{(1)})_{i \in [n]}$ (as opposed to $(\mathbf{y}_i^{(0)} \parallel 0^N)_{i \in [n]}$ in $G_0$). The function-hiding admissibility of $\mathcal{A}$ states that $\langle (\mathbf{x}_i^{(0)}), (\mathbf{y}_i^{(0)}) \rangle_{i \in [n]} = \langle (\mathbf{x}_i^{(1)}), (\mathbf{y}_i^{(1)}) \rangle_{i \in [n]}$ which implies that

$$\langle (\mathbf{x}_i^{(0)} \parallel 0^N)_{i \in [n]}, (\mathbf{y}_i^{(0)} \parallel 0^N)_{i \in [n]} \rangle = \langle (\mathbf{x}_i^{(0)} \parallel 0^N)_{i \in [n]}, (\mathbf{y}_i^{(0)} \parallel \mathbf{y}_i^{(1)})_{i \in [n]} \rangle \\ = \langle (0^N \parallel \mathbf{x}_i^{(1)})_{i \in [n]}, (\mathbf{y}_i^{(0)} \parallel \mathbf{y}_i^{(1)})_{i \in [n]} \rangle$$

Thus our simulator's queries are admissible in the weakly function-hiding model. Then it follows by the weak function-hiding property of $\mathcal{E}'$ that there exists a $\mathcal{P}\mathcal{P}$ adversary $\mathcal{B}$ such that

$$|\text{Pr}[G_1 = 1] - \text{Pr}[G_0 = 1]| = \left| \begin{aligned} & \text{Pr}[\mathcal{B} \text{ outputs 1 in } \mathbf{Exp}_{\mathcal{E}, \mathcal{F}_{\mathcal{P}, \mathcal{B}}}^{\mathcal{X}\mathcal{X}\mathcal{X}\text{-wfh}}(1^{\lambda}) \mid b = 1] \\ & - \text{Pr}[\mathcal{B} \text{ outputs 1 in } \mathbf{Exp}_{\mathcal{E}, \mathcal{F}_{\mathcal{P}, \mathcal{B}}}^{\mathcal{X}\mathcal{X}\mathcal{X}\text{-wfh}}(1^{\lambda}) \mid b = 0] \\ & \le 2 \cdot \mathbf{Adv}_{\mathcal{E}, \mathcal{F}_{\mathcal{P}, \mathcal{B}}}^{\mathcal{X}\mathcal{X}\mathcal{X}\text{-wfh}}(1^{\lambda}) \end{aligned} \right|$$

The simulator's queries change only the function's contents while relaying tag-f$_k$ queried by $\mathcal{A}$. The same will hold for the following hybrids.

**Game G$_2$:** We modify the definition of $\mathcal{OEnc}$ and $\mathcal{OKeyGen}$ again.
• Upon $\mathcal{A}$ querying

$$ \mathcal{OEnc}(i, \text{tag}_\ell, \mathbf{x}_i^{(0)}, \mathbf{x}_i^{(1)}) $$

the challenger queries to its weakly function-hiding oracle for

$$ \text{ct}_{\ell,i} \leftarrow \text{Enc}(i, \text{tag}_\ell, \mathbf{x}_i^{(1)} \parallel 0^N, \mathbf{x}_i^{(1)} \parallel 0^N) $$

and returns $\text{ct}'_{\ell,i} := \text{ct}_{\ell,i}$.

• Upon $\mathcal{A}$ querying $\mathcal{OKeyGen}(i, \text{tag-f}_k, \mathbf{y}_i^{(0)}, \mathbf{y}_i^{(1)})$, the challenger queries to its weakly function-hiding oracle for

$$ \text{dk}_{k,i} \leftarrow \text{KeyGen}(i, \text{tag-f}_k, \mathbf{y}_i^{(1)} \parallel \mathbf{y}_i^{(1)}, \mathbf{y}_i^{(1)} \parallel \mathbf{y}_i^{(1)}) $$

and returns $\text{dk}'_{k,i} := \text{dk}_{k,i}$.

That is, the simulator $\mathcal{B}$ provides to $\mathcal{A}$ with ciphertexts of $(\mathbf{x}_i^{(1)} \parallel 0^N)_{i \in [n]}$ and functional keys for $(\mathbf{y}_i^{(1)} \parallel \mathbf{y}_i^{(1)})_{i \in [n]}$, as opposed to $(0^N \parallel \mathbf{x}_i^{(1)})_{i \in [n]}$ and $(\mathbf{y}_i^{(0)} \parallel \mathbf{y}_i^{(1)})_{i \in [n]}$ in $\mathcal{G}_1$. Notice that

$$ \langle (0^N \parallel \mathbf{x}_i^{(1)})_{i \in [n]}, (\mathbf{y}_i^{(0)} \parallel \mathbf{y}_i^{(1)})_{i \in [n]} \rangle = \langle (0^N \parallel \mathbf{x}_i^{(1)})_{i \in [n]}, (\mathbf{y}_i^{(1)} \parallel \mathbf{y}_i^{(1)})_{i \in [n]} \rangle \\ = \langle (\mathbf{x}_i^{(1)} \parallel 0^N)_{i \in [n]}, (\mathbf{y}_i^{(1)} \parallel \mathbf{y}_i^{(1)})_{i \in [n]} \rangle . $$

Thus our simulator's queries are admissible in the weakly function-hiding model. Then it follows by the weak function-hiding property of $\mathcal{E}'$ that there exists a ppt adversary $\mathcal{B}$ such that $|\text{Pr}[\mathcal{G}_2 = 1] - \text{Pr}[\mathcal{G}_1 = 1]| \le 2 \cdot \text{Adv}_{\mathcal{E}, \mathcal{F}^\text{fh}, \mathcal{B}}^{\text{xxx-wfh}}(1^\lambda)$.

**Game $\mathcal{G}_3$:** We modify the definition of $\mathcal{OKeyGen}$ as follows. (The definition of $\mathcal{OEnc}$ is as in $\mathcal{G}_2$.)

• Upon $\mathcal{A}$ querying $\mathcal{OKeyGen}(i, \text{tag-f}_k, \mathbf{y}_i^{(0)}, \mathbf{y}_i^{(1)})$, the challenger queries to its weakly function-hiding oracle for

$$ \text{dk}_{k,i} \leftarrow \text{KeyGen}(i, \text{tag-f}_k, \mathbf{y}_i^{(1)} \parallel 0^N, \mathbf{y}_i^{(1)} \parallel 0^N) $$

and returns $\text{dk}'_{k,i} := \text{dk}_{k,i}$.

Thus, the challenger provides functional keys for $(\mathbf{y}_i^{(1)} \parallel 0^N)_{i \in [n]}$, as opposed to $(\mathbf{y}_i^{(1)} \parallel \mathbf{y}_i^{(1)})_{i \in [n]}$ in $\mathcal{G}_2$. We have

$$ \langle (\mathbf{x}_i^{(1)} \parallel 0^N)_{i \in [n]}, (\mathbf{y}_i^{(1)} \parallel \mathbf{y}_i^{(1)})_{i \in [n]} \rangle = \langle (\mathbf{x}_i^{(1)} \parallel 0^N)_{i \in [n]}, (\mathbf{y}_i^{(1)} \parallel 0^N)_{i \in [n]} \rangle . $$

And our simulator's queries are admissible in the weakly function-hiding model. As above, it follows by the weak function-hiding property of $\mathcal{E}'$ that there exists a ppt adversary $\mathcal{B}$ such that $|\text{Pr}[\mathcal{G}_3 = 1] - \text{Pr}[\mathcal{G}_2 = 1]| \le 2 \cdot \text{Adv}_{\mathcal{E}, \mathcal{F}^\text{fh}, \mathcal{B}}^{\text{xxx-wfh}}(1^\lambda)$. Note that $\mathcal{G}_3$ equals the experiment $\text{Exp}_{\mathcal{E}', \mathcal{F}^\text{fh}, \mathcal{A}}^{\text{xxx-fh}}(1^\lambda)$ conditioned on $b=1$.

Using a hybrid argument, we conclude that:

$$ \begin{aligned} \text{Adv}_{\mathcal{E}', \mathcal{F}^\text{fh}, \mathcal{A}}^{\text{xxx-fh}}(1^\lambda) &= \frac{1}{2} |\text{Pr}[\mathcal{G}_3 = 1] - \text{Pr}[\mathcal{G}_0 = 1]| \le \frac{1}{2} \cdot \sum_{i=1}^3 |\text{Pr}[\mathcal{G}_i = 1] - \text{Pr}[\mathcal{G}_{i-1} = 1]| \\ &\le 3 \cdot \text{Adv}_{\mathcal{E}, \mathcal{F}^\text{fh}, \mathcal{B}}^{\text{xxx-wfh}}(1^\lambda) \end{aligned} $$

and the lemma is proved. □