# Decentralized Multi-Client Functional Encryption with Strong Security

Ky Nguyen, David Pointcheval, Robert Schädlich

► To cite this version:

Ky Nguyen, David Pointcheval, Robert Schädlich. Decentralized Multi-Client Functional Encryption with Strong Security. IACR Communications in Cryptology, 2024, 1 (2), 10.62056/andkp2fgx. hal-05029125

HAL Id: hal-05029125

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

Submitted on 10 Apr 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
# Decentralized Multi-Client Functional Encryption with Strong Security

Ky Nguyen ID, David Pointcheval ID and Robert Schädlich ID

DIENS, Ecole normale superieure, CNRS, Inria, PSL University, Paris, France

**Abstract.** Decentralized Multi-Client Functional Encryption (DMCFE) extends the basic functional encryption to multiple clients that do not trust each other. They can independently encrypt the multiple plaintext-inputs to be given for evaluation to the function embedded in the functional decryption key, defined by multiple parameter-inputs. And they keep control on these functions as they all have to contribute to the generation of the functional decryption keys. Tags can be used in the ciphertexts and the keys to specify which inputs can be combined together. As any encryption scheme, DMCFE provides privacy of the plaintexts. But the functions associated to the functional decryption keys might be sensitive too (e.g. a model in machine learning). The function-hiding property has thus been introduced to additionally protect the function evaluated during the decryption process.

In this paper, we provide new proof techniques to analyze a new concrete construction of function-hiding DMCFE for inner products, with strong security guarantees in the random oracle model: the adversary can adaptively query multiple challenge ciphertexts and multiple challenge keys, with unbounded repetitions of the same message tags in the ciphertext-queries and a fixed polynomially-large number of repetitions of the same key tags in the key-queries, allowing static corruption of the secret encryption keys. Previous constructions were proven secure in the selective setting only.

**Keywords:** Functional Encryption · Inner Product · Function-Hiding

## 1 Introduction

**Functional Encryption.** Public-Key Encryption (PKE) has become so indispensable that without this building block, secure communication over the Internet would be unfeasible nowadays. However, this concept of PKE limits the access to encrypted data in an *all-or-nothing* fashion: once the recipients have the secret key, they will be able to recover the original data; otherwise, no information is revealed. The concept of Functional Encryption (FE), originally introduced by Boneh, Sahai and Waters [SW05, BSW11], overcomes this limitation: a decryption key can be generated under some specific function *F*, namely a *functional decryption key*, and enable the evaluation *F(x)* from an encryption of a plaintext *x* in order to provide a finer control over the leakage of information about *x*.

Since its introduction, FE has provided a unified framework for prior advanced encryption notions, such as Identity-Based Encryption [Sha84, Coc01, BF01] or Attribute-Based Encryption [SW05, GPSW06, OSW07, ALdP11, OT12b], and has become a very active domain of research. Abdalla et al. [ABDP15] proposed the first FE scheme (in short-hand as ABDP from this point) that allows computing the inner product between a functional vector in the functional decryption key and a data vector in the ciphertext

<footnote>E-mail: ky.nguyen@ens.fr (Ky Nguyen), david.pointcheval@ens.fr (David Pointcheval), robert.schaedlich@ens.fr (Robert Schädlich)</footnote>
(IPFE). The interests in FE then increased, either in improving existing constructions for concrete function classes, e.g. inner products [ALS16, BBL17, CLT18] and quadratic functions [BCFG17, Gay20, AS17, Lin17], or in pushing the studies of new advanced notions [GVW15] as well as the relationship to other notions in cryptography [AJ15, BV15]. While FE with a single encryptor, i.e. single-client FE, is of great theoretical interest, there is also a motivation to investigate a multi-user setting, which might be applicable in practical applications when the data is an aggregation of information coming from multiple sources. Another important research question concentrates on the privacy of functions under which functional keys are generated. We discuss these two lines of work below.

**Extensions of FE in the Multi-User Setting.** Goldwasser et al. [GGG+14, GKL+13] initiated the study of Multi-Input Functional Encryption (MIFE) and Multi-Client Functional Encryption (MCFE). In MCFE particularly, the encrypted data is broken into a vector $(x_1, \dots, x_n)$ and a client $i$ among $n$ clients uses their encryption key $ek_i$ to encrypt $x_i$, under some (usually time-based) tag tag. Given a vector of ciphertexts $(ct_1 \leftarrow Enc(ek_1, tag, x_1), \dots, ct_n \leftarrow Enc(ek_n, tag, x_n))$, a decryptor holding a functional decryption key $dk_F$ can decrypt and obtain $F(x_1, \dots, x_n)$ as long as all $ct_1, \dots, ct_n$ are generated under the same tag. No information beyond $F(x_1, \dots, x_n)$ is leaked, especially concerning the individual secret components $x_i$, and combinations of ciphertexts under different message tags provide no further information either. Furthermore, in practice encrypting $x_i$ under different message tags tag' $\neq$ tag might bear a different meaning with respect to a client $i$ and thus controls the possibilities constituting ciphertext vectors<fnref n="1" />. This also necessitates the encryption keys $ek_i$ being private. The notion of MCFE can be seen as an extension of FE where multiple clients can contribute into the ciphertext vector independently and non-interactively, where encryption is done by private encryption keys. After their introduction, MIFE/MCFE motivated a plethora of works on the subject, notably for the concrete function class of inner products [DOT18, CDG+18a, CDG+18b, ACF+18, ABKW19, ABG19, LT19, CDSG+20, ACGU20, NPP22].

*Decentralized Multi-Client Functional Encryption.* The setup of MCFE requires some authority (a trusted third party) responsible for the setup and generation of functional decryption keys. The authority possesses a master secret key msk that can be used to handle the distribution of private encryption keys $ek_i$ and deriving functional decryption keys $dk_F$. When clients do not trust each other, this centralized setting of authority might be a disadvantage. The need for such a central authority is completely eliminated in the so-called *Decentralized Multi-Client Functional Encryption (DMCFE)* introduced by Chotard et al. [CDG+18a]. In DMCFE, only during the setup phase do we need interaction for generating parameters that will be needed by the clients later. The key generation is done independently by different senders, each has a secret key $sk_i$. Agreeing on a function $F$, each sender generates their functional key $dk_{F,i}$ using $sk_i$, the description of $F$, and a tag tag-f. Originally in [CDG+18a], the tag tag-f can contain the description of $F$ itself. Using DMCFE, the need of an authority for distributing functional keys is completely removed, with minimal interaction required during setup. The seminal work of [CDG+18a] constructed the first DMCFE for computing inner products (IP-DMCFE), where $n$ clients can independently contribute to the ciphertext vector $(ct_1 \leftarrow Enc(ek_1, tag, x_1), \dots, ct_n \leftarrow Enc(ek_n, tag, x_n))$ and $n$ senders can independently contribute to the functional keys $dk_{y,1} \leftarrow DKeyGen(sk_1, tag-f, y_1), \dots, dk_{y,n} \leftarrow DKeyGen(sk_n, tag-f, y_n)$ of some vector $y = (y_1, \dots, y_n)$. For the function class to compute inner products, many follow-up works improve upon the work of [CDG+18a] on both

<footnote n="1">¹In contrast, MIFE involves no message tags and thus a large amount of information can be obtained by arbitrarily combining ciphertexts to decrypt under some functional decryption key.</footnote>
aspects of efficiency as well as security, or by giving generic transformation to (D)MCFE from single-client FE [LT19, ABKW19, ABG19].

***Repetitions under One Tag.*** Involving tags at the time of encryption and key generation restricts that only ciphertexts and functional keys having the same tag can be combined in the notion of DMCFE. This raises a natural question: what security can we guarantee when one client uses the same tag on multiple data ? We call such multiple usages of the same tag in a DMCFE system *repetitions*. In the formal security model of (D)MCFE in [CDG+18a] and subsequent works [LT19], once the adversary makes a query for (i, tag), further queries for the same pair (i, tag) will be ignored. This means repetitions are not taken into account. The authors of [CDG+18a] argued that it is the responsibility of the users not to use the same tag twice. However, a security notion for DMCFE that captures a sense of protection even when repetitions mistakenly/maliciously happen will be preferable, e.g. this is indeed studied in some other works [ABKW19, ABG19]. In addition, when repetitions are allowed for ciphertexts, the security model of MCFE strictly encompasses MIFE by replacing tags with a constant value, as confirmed in recent works [ATY23].

***Function Privacy in FE.*** Standard security notions of FE ensure that adversaries do not learn anything about the content of ciphertexts beyond what is revealed by the functions for which they possess decryption keys. However, it is *not* required that functional decryption keys hide the function they decrypt. In practice, this can pose a serious problem because the function itself could contain confidential data. For example, the evaluated function may represent a neural network. Training such networks is often time-consuming and expensive, which is why companies offer their use as a paid service. However, to ensure that customers continue to pay for the use of the product, it is crucial that the concrete parameters of the network (i.e. the computed function) remain secret. This additional security requirement for functional encryption schemes is known as the *function-hiding property*. As another example, suppose one wants to perform statistical analysis (e.g. weighted averages) of private data from several companies to get a better understanding of the dynamics of a sector. This can be implemented using a DMCFE for inner products. Consulting firms conduct such analyses as a fee-based service. To ensure that clients continue to pay for updated results in the future, the consulting firm may wish to hide the concrete parameters of their calculations. This can be achieved by using a DMCFE with function-hiding security.

Besides practical applications, function-hiding FE schemes for restricted function classes (such as inner products) have also proven to be an important technical building block for the construction of FE schemes for broader function classes: Lin [Lin17] employed a function-hiding IPFE (FH-IPFE) to obtain an FE scheme for quadratic functions. A different technique was also introduced by Gay in [Gay20] equally aiming at constructing FE for quadratic functions. With several technical novelties, Agrawal et al. [AGT21a, AGT22] were able to generalize the aforementioned constructions to obtain MIFE for quadratic functions.

***Existing Function-Hiding FE Schemes in the Literature.*** Bishop et al. [BJK15] presented the first IPFE scheme that guaranteed a weak variant of the function-hiding property. This construction was lifted to fully function-hiding security by Datta et al. [DDM16, DDM17]. This was further improved in terms of efficiency and/or computational hardness assumptions by works of [TAO16, KKS19, KLM+18, Tom19, Tom20]. The constructions of [BJK15, DDM16, TAO16] all leverage the power of *dual pairing vector spaces* (DPVSes) developed by Okamoto and Takashima in [OT10, OT12a, OT12b]. Alternatively, Lin [Lin17] used a different approach to get simpler constructions of FH-IPFE from the ABDP IPFE. Using the same blueprint and exploiting the specific algebraic properties of the underlying inner-
product MIFE scheme carefully, Abdalla et al. [ACF+18] were able to construct function-
hiding MIFE for inner products (FH-IP-MIFE). In [AGT21b], Agrawal et al. came up with
the first construction of function-hiding MCFE for inner products (FH-IP-MCFE) that is
inspired by the FH-IP-MIFE by Datta et al. [DOT18]. Very recently, Shi and Vanjani [SV23]
presented a generic transformation from single-client to multi-client functional encryption,
preserving the function-hiding property and leading to the first FH-IP-MCFE with adaptive
security. Remarkably, their security proof does not rely on random oracles. We are not
aware of any construction of function-hiding DMCFE for inner products (FH-IP-DMCFE)
whose security does not rely on the random oracle model (ROM).

In [CDSG+20], Chotard et al. generalized DMCFE and defined the notion of *Dynamic Decentralized Functional Encryption (DDFE)* that allows users to join at various stages during the lifetime of a system, while maintaining all decentralized features of DMCFE. Notably, the setup of DDFE is non-interactive and decentralized, while that of DMCFE is a *priori* interactive. In the end, a DDFE scheme allows aggregating data from different sources by decrypting an independent list of ciphertexts using an independent list of functional keys, both of which are fabricated in a completely decentralized manner by users with their $sk_i$, while requiring no trusted third party. To these extents, DDFE is a primitive strictly stronger than DMCFE, given that the function class of the former contains functions that are well-defined relating to a given list of functional keys and those functions can be expressed by the function class of the latter<fnref n="2" />. In [AGT21b], the authors revisits DDFE for the class of inner products (IP-DDFE) and provide a transformation from FH-IP-MCFE to FH-IP-DDFE, following the approach of Chotard et al. [CDSG+20] who presented a similar transformation in the non-function-hiding setting. As a consequence, the FH-IP-DDFE scheme of [AGT21b] entails the only FH-IP-DMCFE so far in the literature.

It is worth noting that all known constructions that guarantee function-hiding security
rely on pairings. A recent work by Ünal [Üna20] shows that in the manner of most
lattice-based approaches, there is little hope to achieve function privacy in IPFE schemes,
in the setting of multi-user or not.

Our Contributions

To the best of our knowledge, the only candidate of FH-IP-DMCFE comes from [AGT21b], implicitly as a result of their function-hiding FH-IP-DDFE. The implied security of their FH-IP-DMCFE is *selectively indistinguishability-based* in the ROM under *static* corruption, where the adversary makes all encryption, key generation and corruption queries up front in one shot, with repetitions w.r.t encryption tags and *no repetitions* w.r.t key generation tags. This state-of-the-art leads us to the following question:

*How far can we raise the security level of pairing-based function-hiding IP-DMCFE in the ROM?*

In this paper, we strictly improve on various aspects of security compared with [AGT21b].
Below and in Table 1 are presented a summary of our contributions and a comparison
with existing works:

1. *Function-Hiding IP-DMCFE.* We construct the first FH-IP-DMCFE that tolerates *adaptive* encryption queries (with unbounded repetitions) and *adaptive* key generation queries with a *fixed polynomially large number* repetitions, under static corruption. The bounded number of repetitions on key generation queries can be polynomially large and is specified at setup time of the scheme. Our FH-DMCFE thus handles up to an *exponentially large* number of mix-and-match of key repetitions under the same tag *tag-f*, which is determined by the scheme's parameters. It uses pairings

<footnote n="2">²With an appropriate formalization, all function classes in this work, including inner products, satisfy this property.</footnote>
<table><caption>**Table 1:** We compare our constructions with existing works, in terms of the type of primitives with function-hiding security (**Type**), whether the encryption oracle (**OEnc**) and key generation oracle (**OKeyGen**) can be queried adaptively and with repetitions (**Oracle Queries**), which assumptions are used for the security proof (**Assumptions**), and whether the security is proven in the ROM (✓) or not (✗) (**ROM**). The shorthands (**sel**, **adap**) denote selective or adaptive oracle queries. The shorthands (**w-rep**, **bnd-rep**, **no-rep**) indicates whether the adversary can demand repetitive queries to the same slot and tag unboundedly, under a fixed bound, or not, in that order. All schemes are defined for the inner-product functionality of their respective type of primitive (see Def. 6) and consider only static corruption. Preferred properties are *underlined*.</caption><thead><tr><th rowspan="2">Scheme</th><th rowspan="2">Type</th><th colspan="2">Oracle Queries</th><th rowspan="2">Assumptions<sup>††</sup></th><th rowspan="2">ROM</th></tr><tr><th>OEnc</th><th>OKeyGen</th></tr></thead><tbody><tr><td>[AGT21b, Section 6.2]</td><td>FH-IP-MCFE</td><td>sel, w-rep</td><td>sel<sup>†</sup></td><td>SXDH</td><td>✓</td></tr><tr><td>[SV23, Section B.3]</td><td>FH-IP-MCFE</td><td>adap, w-rep</td><td>adap<sup>†</sup></td><td>D-Lin</td><td>x<sup>‡</sup></td></tr><tr><td>[AGT21b, Section 6.3]</td><td>FH-IP-DMCFE*</td><td>sel, w-rep</td><td>sel, no-rep</td><td>SXDH</td><td>✓</td></tr><tr><td>Corollary 1</td><td>FH-IP-DMCFE</td><td>adap, w-rep</td><td>adap, bnd-rep</td><td>SXDH</td><td>✓</td></tr></tbody></table>

† For MCFE, there is no notion of tags for key generation, hence no notion of repetitions.

‡ This is the only FH-MCFE that is provably secure without the ROM. To our knowledge, there is no FH-DMCFE nor FH-DDFE in the literature that does not use ROs.

†† All mentioned constructions use pairing groups.

* This FH-IP-DMCFE is implied by the FH-IP-DDFE of [AGT21b, Section 6.3].

and is provably secure in the ROM. Details about our construction are explained in Section 4.2.

2. Technical Contribution. Along the way, we push forward the study of DPVS techniques. We state a novel lemma that shows the indistinguishability of two distributions in a setting where not all input data is known up front. This lemma proves to be the key ingredient for the security proof of our FH-IP-DMCFE scheme in the *adaptive* setting. Due to its oracle-based general formulation, we believe that the lemma can find other applications in the future. The formal statement (Lemma 1) and a proof overview can be found in Section 4.1. Basic definitions for the DPVS framework are provided in Section 3.2.

## 2 High-Level Overview in the Selective Setting

In this section, we first describe a straightforward construction of a selective FH-DMCFE for inner products based on a blackbox FH-IPFE scheme in the spirit of existing FH-IP-MIFE and FH-IP-MCFE constructions such as [DOT18, AGT21b]. Subsequently, we discuss the main difficulties that need to be overcome towards adaptive security. Regarding the notations of the following overview, we let $\mathbb{Z}_q$ denote the ring of integers with addition and multiplication modulo $q \ge 2$. For a vector $\mathbf{x}$ of dimension $n$, the notation $\mathbf{x}[i]$ indicates the $i$-th coordinate of $\mathbf{x}$, for $i \in [n]$. We will follow the implicit notation in [EHK$^{+}$13] and use $\llbracket a \rrbracket$ to denote $g^a$ in a cyclic group $\mathbb{G}$ of prime order $q$ generated by $g$, given $a \in \mathbb{Z}_q$. This implicit notation extends to matrices and vectors having entries in $\mathbb{Z}_q$, e.g. $\llbracket (a, b) \rrbracket = (g^a, g^b) \in \mathbb{G}^2$.
**Recap: The Function-Hiding MCFE of [AGT21b].** An FH-IPFE scheme iFE = (iSetup, iKeyGen, iEnc, iDec) based on a pairing group $\mathbb{G} = (\mathbb{G}_1, \mathbb{G}_2, \mathbb{G}_t, g_1, g_2, g_t, \mathbf{e}, \mathbf{q})$ enables the sampling of a master secret key $\mathbf{imsk} \leftarrow iSetup(1^{\lambda})$ which can be used to generate functional decryption keys $\mathbf{idk} \leftarrow iKeyGen(\mathbf{imsk}, [[\mathbf{y}]_2])$ for vectors $\mathbf{y} \in \mathbb{Z}_q^N$ encoded in $\mathbb{G}_2$ and ciphertexts $\mathbf{ict} \leftarrow iEnc(\mathbf{imsk}, [[\mathbf{x}]_1])$ associated with vectors $\mathbf{x} \in \mathbb{Z}_q^N$ encoded in $\mathbb{G}_1$. The decryption iDec($\mathbf{idk}$, $\mathbf{ict}$) reveals only the inner product $\llbracket\langle\mathbf{x}, \mathbf{y}\rangle\rrbracket_t$ of $\mathbf{x}$ and $\mathbf{y}$ encoded in $\mathbb{G}_t$ and hides all other information about $\mathbf{x}$ and $\mathbf{y}$. When we use several IPFE instances with master secret keys $\mathbf{imsk}_1, \dots, \mathbf{imsk}_n$ in parallel, we use the shorthands $\mathbf{ict}_i(\llbracket\mathbf{x}\rrbracket_1)$ and $\mathbf{idk}_i(\llbracket\mathbf{y}\rrbracket_2)$ for iEnc($\mathbf{imsk}_i$, $\llbracket\mathbf{x}\rrbracket_1$) and iKeyGen($\mathbf{imsk}_i$, $\llbracket\mathbf{y}\rrbracket_2$).

Recall that MCFE is a special case of DMCFE where a trusted authority is responsible for the generation of the functional decryption keys as well as the encryption keys ($\mathbf{ek}_i$)$_{i \in [n]}$ for the $n$ clients. The key held by the authority is called the master secret key $\mathbf{msk}$. In the scheme of [AGT21b], the encryption key $\mathbf{ek}_i$ of a client $i \in [n]$ consists of a master secret key $\mathbf{imsk}_i$ of a FH-IPFE scheme. The key-generating authority holds $\mathbf{msk} = (\mathbf{imsk}_i)_{i \in [n]}$. Given a tuple $(i, \mathbf{tag}, \mathbf{x}_i)$, the encryption algorithm defines an extended vector of the form $\llbracket\hat{\mathbf{x}}_i\rrbracket_1 = \llbracket(\mathbf{x}_i, \omega, \mathbf{0})\rrbracket_1$, where $\omega = \mathbf{H}(\mathbf{tag})$ is a hash of the tag, and returns $\mathbf{ct}_i = \mathbf{ict}_i(\llbracket\hat{\mathbf{x}}_i\rrbracket_1)$. The notation $\mathbf{0}$ in the extended vector $\hat{\mathbf{x}}_i$ represents additional coordinates that are only used in the security proof and are $\mathbf{0}$ in the real scheme. A functional decryption key for a vector $\mathbf{y} = (\mathbf{y}_i)_{i \in [n]}$ is created by choosing $t_1, \dots, t_n \stackrel{\$}{\leftarrow} \mathbb{Z}_q$ conditioned on $\sum_{i \in [n]} t_i = 0$, defining $\llbracket\hat{\mathbf{y}}_i\rrbracket_2 = \llbracket(\mathbf{y}_i, t_i, \mathbf{0})\rrbracket_2$ and returning $\mathbf{dk} = \{\mathbf{idk}_i(\llbracket\hat{\mathbf{y}}_i\rrbracket_2)\}_{i \in [n]}$. Decrypting $\mathbf{ict}_i(\llbracket\hat{\mathbf{x}}_i\rrbracket_1)$ with $\mathbf{idk}_i(\llbracket\hat{\mathbf{y}}_i\rrbracket_2)$ gives $\langle\mathbf{x}_i, \mathbf{y}_i\rangle + \omega t_i$ encoded in $\mathbb{G}_t$. Since the value $t_i$ is secret, the term $\omega t_i$ serves as a mask that hides the partial inner product $\langle\mathbf{x}_i, \mathbf{y}_i\rangle$. On the other hand, if on has a ciphertext $\mathbf{ct}_i$ for each client and all ciphertexts are generated w.r.t the same tag, then the sum of the partial decryptions gives $\sum_{i \in [n]} \langle\mathbf{x}_i, \mathbf{y}_i\rangle + \omega t_i = \sum_{i \in [n]} \langle\mathbf{x}_i, \mathbf{y}_i\rangle + \omega \cdot \sum_{i \in [n]} t_i = \sum_{i \in [n]} \langle\mathbf{x}_i, \mathbf{y}_i\rangle$, as $\sum_{i \in [n]} t_i = 0$. The scheme is proven to be secure against selective adversaries that submit all oracle queries up front.

**Our Selectively Function-Hiding DMCFE.** In contrast to MCFE, decryption keys in the DMCFE model are generated non-interactively by $n$ different senders each holding a secret key $\mathbf{sk}_i$ for $i \in [n]$. Given a tuple $(\mathbf{tag-f}, \mathbf{y}_i)$, sender $i$ produces a partial decryption key $\mathbf{dk}_i$, and decryption is possible if all senders provide their partial key w.r.t the same tag $\mathbf{tag-f}$. Our selective FH-DMCFE is a straightforward extension of the FH-MCFE of [AGT21b]. Looking at their scheme, we note that decryption keys already consist of $n$ IPFE keys $\{\mathbf{idk}_i(\llbracket\hat{\mathbf{y}}_i\rrbracket_2)\}_{i \in [n]}$. Therefore, it seems natural to let each sender generate one IPFE decryption key. The vectors $\{\hat{\mathbf{y}}_i\}_{i \in [n]}$ encode a secret sharing $(t_i)_{i \in [n]}$ of $\mathbf{0}$ which must now be sampled in a decentralized manner. To do so, we fix a secret sharing $(\tilde{t}_i)_i \stackrel{\$}{\leftarrow} \mathbb{Z}_q^n$ of $\mathbf{0}$ during the (interactive) setup procedure and randomize it by setting $(t_i)_i = (\mu \tilde{t}_i)_i$, where $\mu = \mathbf{H}(\mathbf{tag-f})$. Roughly, under the DDH assumption in $\mathbb{G}_2$, such a multiple of $(\tilde{t}_i)_i$ cannot be distinguished from a fresh secret sharing of $\mathbf{0}$ if the adversary does not obtain several keys for the same sender-tag pair $(i, \mathbf{tag-f})$. Using this restriction, it is straightforward to generalize the security proof of [AGT21b] to the case of FH-DMCFE.

Note that both the syntax and security of FH-DMCFE for inner products are symmetric w.r.t key generation and encryption. Therefore, it is mostly irrelevant if the secret sharing $(\tilde{t}_i)_i$ is embedded into the decryption keys or the ciphertexts. For the sake of consistency with our adaptive scheme presented in Section 4.2, we prefer to place it in the ciphertexts. However, we emphasize that the proof of selective security works either way. We summarize our construction in Figure 1.

**Proof of Selective Security.** As for our adaptive scheme, we only consider static corruptions (see Item 1 of Definition 5). Additionally, we only discuss the proof of one-challenge security against complete queries (see Items 3 and 4). This is sufficient as in Section 5, we show how to remove both restrictions from the security model via a sequence
Setup(1$^{λ}$) : Sample $(\tilde{t}_i)_{i \in [n]} \stackrel{\$}{\leftarrow} \mathbb{Z}_q^n$ such that $\sum_i \tilde{t}_i = 0$; generate $n$ IPFE master secret keys $\{\text{imsk}_i\}_{i \in [n]}$; output $\text{sk}_i = \text{imsk}_i$ and $\text{ek}_i = (\tilde{t}_i, \text{imsk}_i)$ for $i \in [n]$.

DKeyGen($\text{sk}_i$, tag-f, $\mathbf{y}_i$) : Compute $[\mu]_2 = \text{H}_2(\text{tag-f})$; output $\text{dk}_i = \text{idk}_i([\hat{\mathbf{y}}_i]_2)$ for $\hat{\mathbf{y}}_i = (\mathbf{y}_i, \mu, \mathbf{0})$.

Enc($\text{ek}_i$, tag, $\mathbf{x}_i$) : Compute $[\omega]_1 = \text{H}_1(\text{tag})$; output $\text{ct}_i = \text{ict}_i([\hat{\mathbf{x}}_i]_1)$ for $\hat{\mathbf{x}}_i = (\mathbf{x}_i, \omega \tilde{t}_i, \mathbf{0})$.

Dec($\{ (\text{dk}_i, \text{ct}_i) \}_{i \in [n]}$) : Run IPFE decryption for all pairs $(\text{idk}_i([\hat{\mathbf{y}}_i]_2), \text{ict}_i([\hat{\mathbf{x}}_i]_1))$ to recover $[z_i]_t = [(\mathbf{x}_i, \mathbf{y}_i) + \mu \omega \tilde{t}_i]_t$ and find discrete log of $[z]_t = [\sum_{i \in [n]} z_i]_t$.

<caption>**Figure 1:** Our selectively function-hiding DMCFE scheme</caption>

of generic conversions.

Recall that the one-challenge restriction allows only one tag tag* to the encryption oracle $\mathcal{O}\text{Enc}(i, \text{tag}^*, \mathbf{x}_i^{(0)}, \mathbf{x}_i^{(1)})$ having $\mathbf{x}_i^{(0)} \neq \mathbf{x}_i^{(1)}$. Other tags tag$_{ℓ} \neq \text{tag}^*$ and their corresponding inputs $(\mathbf{x}_{\ell,i}^{(0)}, \mathbf{x}_{\ell,i}^{(1)})$ to $\mathcal{O}\text{Enc}$ are indexed by $\ell$ and it holds that $\mathbf{x}_{\ell,i}^{(0)} = \mathbf{x}_{\ell,i}^{(1)}$, so we can omit the superscript in this case. Furthermore, we add indices to denote repeated queries to the same client-tag pair. That is, the $j$-th query to $\mathcal{O}\text{Enc}$ for client $i$ and tag tag* (respectively tag$_{ℓ}$) is denoted by $(\mathbf{x}_i^{(0,j)}, \mathbf{x}_i^{(1,j)})$ (respectively $\mathbf{x}_{\ell,i}^{(j)}$). In the same manner, there exists only one tag-f* queried to the key-generation oracle $\mathcal{O}\text{DKeyGen}(i, \text{tag-f}^*, \mathbf{y}^{(0)}, \mathbf{y}^{(1)})$ having $\mathbf{y}^{(0)} \neq \mathbf{y}^{(1)}$, while for other tag-f$_k \neq \text{tag-f}^*$ it holds that $\mathbf{y}^{(0)} = \mathbf{y}^{(1)}$. We denote the $\tilde{j}$-th query to $\mathcal{O}\text{DKeyGen}$ for client $i$ and tag tag-f* (respectively tag-f$_k$) by $(\mathbf{y}_i^{(0,j)}, \mathbf{y}_i^{(1,j)})$ (respectively $\mathbf{y}_{\ell,i}^{(j)}$). To summarize, in the one-challenge security game with challenge bit $b \stackrel{\$}{\leftarrow} \{0,1\}$, the adversary obtains the following decryption keys and ciphertexts:

$$ 
\begin{aligned}
\mathbf{d}_i^{(j)} &= \text{idk}_i([\mathbf{y}_i^{(b,j)}, \mu, 0, \mathbf{0}, 0, \mathbf{0}]_2) \quad \mathbf{c}_i^{(j)} = \text{ict}_i([\mathbf{x}_i^{(b,j)}, t_i := \omega \cdot \tilde{t}_i, 0, \mathbf{0}, 0, \mathbf{0}]_1) \\
\mathbf{d}_{k,i}^{(j)} &= \text{idk}_i([\mathbf{y}_{k,i}^{(j)}, \mu_k, 0, \mathbf{0}, 0, \mathbf{0}]_2) \quad \mathbf{c}_{\ell,i}^{(j)} = \text{ict}_i([\mathbf{x}_{\ell,i}^{(j)}, t_{\ell,i} := \omega_{\ell} \cdot \tilde{t}_i, 0, \mathbf{0}, 0, \mathbf{0}]_1)
\end{aligned}
\quad (1) $$

During the entire security proof, we restrict all changes to honest slots $i \in \mathcal{H}$ because the admissibility condition (Item 1 of Definition 5) gives that encryption and key generation queries for corrupted slots $i \in \mathcal{C}$ are already independent of the challenge bit $b$, so there is nothing to show. In the first step, the simulator randomizes the values $t_i$ and $t_{\ell,i}$ for honest clients $i \in \mathcal{H}$ while relying on the DDH assumption in $\mathbb{G}_1$. Subsequently, the simulator introduces the vectors $\mathbf{x}_i^{(1)}$ and $\mathbf{x}_{\ell,i}$ in the additional 0-coordinates of the ciphertexts of honest clients $i \in \mathcal{H}$.

$$ 
\begin{aligned}
\mathbf{d}_i^{(j)} &= \text{idk}_i([\mathbf{y}_i^{(b,j)}, \mu, 0, \mathbf{0}, 0, \mathbf{0}]_2) \quad \mathbf{c}_i^{(j)} = \text{ict}_i([\mathbf{x}_i^{(b,j)}, t_i, 0, \boxed{\mathbf{x}_i^{(1,j)}}, 0, \mathbf{0}]_1) \\
\mathbf{d}_{k,i}^{(j)} &= \text{idk}_i([\mathbf{y}_{k,i}^{(j)}, \mu_k, 0, \mathbf{0}, 0, \mathbf{0}]_2) \quad \mathbf{c}_{\ell,i}^{(j)} = \text{ict}_i([\mathbf{x}_{\ell,i}^{(j)}, t_{\ell,i}, 0, \boxed{\mathbf{x}_{\ell,i}^{(j)}}, 0, \mathbf{0}]_1)
\end{aligned}
\quad (2) $$

This change cannot be noticed by the adversary assuming message-privacy of iFE. In the next step, the simulator embeds fresh secret sharings $(\tau_i)_{i \in \mathcal{H}}$ and $(\tau_{\ell,i})_{i \in \mathcal{H}}$ of 0 in the ciphertexts for $i \in \mathcal{H}$ as follows:

$$ 
\begin{aligned}
\mathbf{d}_i^{(j)} &= \text{idk}_i([\mathbf{y}_i^{(b,j)}, \mu, \boxed{\mathbf{1}}, \mathbf{0}, 0, \mathbf{0}]_2) \quad \mathbf{c}_i^{(j)} = \text{ict}_i([\mathbf{x}_i^{(b,j)}, t_i, \boxed{\tau_i}, \mathbf{x}_i^{(1,j)}, 0, \mathbf{0}]_1) \\
\mathbf{d}_{k,i}^{(j)} &= \text{idk}_i([\mathbf{y}_{k,i}^{(j)}, \mu_k, 0, \mathbf{0}, 0, \mathbf{0}]_2) \quad \mathbf{c}_{\ell,i}^{(j)} = \text{ict}_i([\mathbf{x}_{\ell,i}^{(j)}, t_{\ell,i}, \boxed{\tau_{\ell,i}}, \mathbf{x}_{\ell,i}^{(j)}, 0, \mathbf{0}]_1)
\end{aligned}
\quad (3) $$

This step is not complicated but requires some care. Roughly, we use a sequence of hybrids over the secret sharings $(t_i)_{i \in [n]}$ and $(t_{\ell,i})_{i \in [n]}$ for all $\ell$, where in each hybrid we first hardwire the
product $\mu \cdot t_i$ (respectively $\mu \cdot t_{\ell,i}$) in $\mathbf{d}_i^{(j)}$, then rely on the DDH in $\mathbb{G}_2$ to obtain random values $t'_i$ (respectively $t'_{\ell,i}$). These random values can in turn be split into the original product $\mu \cdot t_i$ (respectively $\mu \cdot t_{\ell,i}$) and a fresh random share $\tau_i$ (respectively $\tau_{\ell,i}$). To isolate the values of the current hybrid, we use the additional two coordinates at the end of the vectors<fnref n="3" />.

The admissibility conditions (Items 1 and 2 of Definition 5) state for all $j_i, \tilde{j}_i$ that

$$ \sum_{i \in [n]} \langle \mathbf{x}_i^{(0, \tilde{j}_i)}, \mathbf{y}_i^{(0, \tilde{j}_i)} \rangle = \sum_{i \in [n]} \langle \mathbf{x}_i^{(1, \tilde{j}_i)}, \mathbf{y}_i^{(1, \tilde{j}_i)} \rangle \quad \text{and} \quad \sum_{i \in [n]} \langle \mathbf{x}_{\ell, i}^{(\tilde{j}_i)}, \mathbf{y}_i^{(0, \tilde{j}_i)} \rangle = \sum_{i \in [n]} \langle \mathbf{x}_{\ell, i}^{(\tilde{j}_i)}, \mathbf{y}_i^{(1, \tilde{j}_i)} \rangle $$

as well as $\mathbf{x}_i^{(0, \tilde{j})} = \mathbf{x}_i^{(1, \tilde{j})}$ and $\mathbf{y}_i^{(0, \tilde{j})} = \mathbf{y}_i^{(1, \tilde{j})}$ if $i \in \mathcal{C}$. From this, it follows for $b \in \{0, 1\}^4$ that

$$ \Delta_i^{(b)} := \langle \mathbf{x}_i^{(b, \tilde{j})}, \mathbf{y}_i^{(b, \tilde{j})} \rangle - \langle \mathbf{x}_i^{(1, \tilde{j})}, \mathbf{y}_i^{(1, \tilde{j})} \rangle \quad \text{and} \quad \Delta_{\ell, i}^{(b)} := \langle \mathbf{x}_{\ell, i}^{(\tilde{j})}, \mathbf{y}_i^{(b, \tilde{j})} - \mathbf{y}_i^{(1, \tilde{j})} \rangle $$

are constant for all repetitions $j, \tilde{j}$, and $\Delta_i^{(b)} = \Delta_{\ell, i}^{(b)} = 0$ if $i \in \mathcal{C}$. Furthermore, we have that $\sum_{i \in \mathcal{H}} \Delta_i^{(b)} = \sum_{i \in \mathcal{H}} \Delta_{\ell, i}^{(b)} = 0$. Together, these conditions imply that the distributions

$$ D_0 = \left\{ (\tau_i)_{i \in \mathcal{H}} : (\tau_i)_{i \in \mathcal{H}} \stackrel{\$}{\leftarrow} \mathbb{Z}_q^{|\mathcal{H}|} \text{ s.t. } \sum_{i \in \mathcal{H}} \tau_i = 0 \right\} $$

$$ D_1 = \left\{ (\tau_i)_{i \in \mathcal{H}} : (\tau'_i)_{i \in \mathcal{H}} \stackrel{\$}{\leftarrow} \mathbb{Z}_q^{|\mathcal{H}|} \text{ s.t. } \sum_{i \in \mathcal{H}} \tau_i = 0, \tau_i := \tau'_i - \Delta_i^{(b)} \right\} $$

are identical (and a similar result also holds for all $(\tau_{\ell,i})_{i \in \mathcal{H}}$). Thus, it is an information-theoretic change to provide the adversary with

$$ \begin{aligned} \mathbf{d}_i^{(\tilde{j})} &= \mathrm{idk}_i(\llbracket \mathbf{y}_i^{(b, \tilde{j})}, \mu, 1, 0, 0, 0 \rrbracket_2) & \mathbf{c}_i^{(\tilde{j})} &= \mathrm{ict}_i(\llbracket \mathbf{x}_i^{(b, \tilde{j})}, t_i, \tau_i - \Delta_i^{(b)}, \mathbf{x}_i^{(1, \tilde{j})}, 0, 0 \rrbracket_1) \\ \mathbf{d}_{k,i}^{(\tilde{j})} &= \mathrm{idk}_i(\llbracket \mathbf{y}_{k,i}^{(b, \tilde{j})}, \mu_k, 0, 0, 0, 0 \rrbracket_2) & \mathbf{c}_{\ell,i}^{(\tilde{j})} &= \mathrm{ict}_i(\llbracket \mathbf{x}_{\ell,i}^{(b, \tilde{j})}, t_{\ell,i}, \tau_{\ell,i} - \Delta_{\ell,i}^{(b)}, \mathbf{x}_{\ell,i}^{(1, \tilde{j})}, 0, 0 \rrbracket_1) \end{aligned} \quad (4) $$

Relying again on the function privacy of iFE, the simulator can change to:

$$ \begin{aligned} \mathbf{d}_i^{(\tilde{j})} &= \mathrm{idk}_i(\llbracket \mathbf{0}, \mu, 1, \mathbf{y}_i^{(1, \tilde{j})}, 0, 0 \rrbracket_2) & \mathbf{c}_i^{(\tilde{j})} &= \mathrm{ict}_i(\llbracket \mathbf{x}_i^{(b, \tilde{j})}, t_i, \tau_i, \mathbf{x}_i^{(1, \tilde{j})}, 0, 0 \rrbracket_1) \\ \mathbf{d}_{k,i}^{(\tilde{j})} &= \mathrm{idk}_i(\llbracket \mathbf{y}_{k,i}^{(b, \tilde{j})}, \mu_k, 0, 0, 0, 0 \rrbracket_2) & \mathbf{c}_{\ell,i}^{(\tilde{j})} &= \mathrm{ict}_i(\llbracket \mathbf{x}_{\ell,i}^{(b, \tilde{j})}, t_{\ell,i}, \tau_{\ell,i} - \Delta_{\ell,i}^{(b)}, \mathbf{x}_{\ell,i}^{(1, \tilde{j})}, 0, 0 \rrbracket_1) \end{aligned} \quad (5) $$

When applying similar arguments as in the steps from (3) to (5) in a hybrid over $\mathbf{d}_{k,i}^{(\tilde{j})}$ for all $k$, we finally arrive at:

$$ \begin{aligned} \mathbf{d}_i^{(\tilde{j})} &= \mathrm{idk}_i(\llbracket \mathbf{0}, \mu, 0, \mathbf{y}_i^{(1, \tilde{j})}, 0, 0 \rrbracket_2) & \mathbf{c}_i^{(\tilde{j})} &= \mathrm{ict}_i(\llbracket \mathbf{x}_i^{(b, \tilde{j})}, t_i, \tau_i, \mathbf{x}_i^{(1, \tilde{j})}, 0, 0 \rrbracket_1) \\ \mathbf{d}_{k,i}^{(\tilde{j})} &= \mathrm{idk}_i(\llbracket \mathbf{0}, \mu_k, 0, \mathbf{y}_{k,i}^{(b, \tilde{j})}, 0, 0 \rrbracket_2) & \mathbf{c}_{\ell,i}^{(\tilde{j})} &= \mathrm{ict}_i(\llbracket \mathbf{x}_{\ell,i}^{(b, \tilde{j})}, t_{\ell,i}, \tau_{\ell,i} - \Delta_{\ell,i}^{(b)}, \mathbf{x}_{\ell,i}^{(1, \tilde{j})}, 0, 0 \rrbracket_1) \end{aligned} \quad (6) $$

At this point, we can remove the vectors $\mathbf{x}_i^{(b, \tilde{j})}$ in $\mathbf{c}_i^{(\tilde{j})}$ which gives us a game that is independent of the bit $b$. So the adversary's advantage is 0 and the proof is finished.

$$ \begin{aligned} \mathbf{d}_i^{(\tilde{j})} &= \mathrm{idk}_i(\llbracket \mathbf{0}, \mu, 0, \mathbf{y}_i^{(1, \tilde{j})}, 0, 0 \rrbracket_2) & \mathbf{c}_i^{(\tilde{j})} &= \mathrm{ict}_i(\llbracket \mathbf{0}, t_i, \tau_i, \mathbf{x}_i^{(1, \tilde{j})}, 0, 0 \rrbracket_1) \\ \mathbf{d}_{k,i}^{(\tilde{j})} &= \mathrm{idk}_i(\llbracket \mathbf{0}, \mu_k, 0, \mathbf{y}_{k,i}^{(b, \tilde{j})}, 0, 0 \rrbracket_2) & \mathbf{c}_{\ell,i}^{(\tilde{j})} &= \mathrm{ict}_i(\llbracket \mathbf{x}_{\ell,i}^{(b, \tilde{j})}, t_{\ell,i}, \tau_{\ell,i}, \mathbf{x}_{\ell,i}^{(1, \tilde{j})}, 0, 0 \rrbracket_1) \end{aligned} \quad (7) $$

<footnote n="3">³Later in the proof for our FH-DMCFE based on DPVS, introducing the new random shares $\tau_i, \tau_{\ell,i}$ is taken care by Lemma 1, using particularly the DPVS basis changes and DDH. We thus do not write the random share introduction explicitly in the FH-DMCFE proof and refer to the transitions $G_0 \to G_1$ in the proof of Lemma 1 for more details.</footnote>

<footnote n="4">⁴More precisely, the case $b = 0$ follows from the admissibility condition while for $b = 1$, we always have $\Delta_i^{(b)} = \Delta_{\ell,i}^{(b)} = 0$</footnote>
**Problems for Adaptive Security.** In (4), the simulator embeds $\Delta_i^{(b)}$ and $\Delta_{\ell,i}^{(b)}$ into the ciphertexts. Note that these values do not only depend on the respective encryption query but also on key generation queries. In the selective setting where all queries are submitted up front, this does not pose a problem. In the adaptive setting, however, this can lead to the situation that the challenger needs to embed values into ciphertexts before they were even input to an oracle query.

To overcome this problem, we provide a concrete instantiation of the underlying FH-IPFE scheme based on DPVSes. If the simulator gets into a situation where it would have to use inputs that have not yet been queried by the adversary, we make it guess them. Even though this guess degrades the probability of a successful efficient simulation by an exponential factor, it does not help the adversary because we design the games to have perfectly identical views, thanks to *information-theoretic* properties of the DPVS setting. Jumping ahead, dealing with repeated queries for the same tag will be more tricky in this context. We therefore describe the main technical lemma in Section 4.1. It is worth noting what is involved in the lemma and how it is used in the proof. The statement of Lemma 1 considers the indistinguishability of an adversary’s views corresponding to their interactions with multiple oracles, *before* and *after* swapping the indexed contents of some oracle’s outputs and changing the contents’ indices from $b=1$ to $b=0$. The aforementioned oracles in Lemma 1 correspond to the execution of key-generation and ciphertext oracles of the FH-DMCFE security experiment (see Figure 2), for challenge and non-challenge queries. Lemma 1 allows the adversary to adaptively query the oracles to model the situation in the FH-DMCFE security proof, where key-generation and ciphertext oracles can be queried adaptively. Later on, the oracles in Lemma 1 are relevant whenever the lemma is applied in the FH-DMCFE security proof. Each time Lemma 1 is applied, e.g. the transition $G_2 \rightarrow G_3$ in Figure 5 and its details in the proof, we verify the hypothesis of the lemma and list the FH-DMCFE security oracles outputs in the order of the lemma’s oracles to affect the correct vectors. A discussion of our adaptively secure FH-DMCFE is given in Section 4.2.

# 3 Preliminaries

For integers $m$ and $n$ with $m < n$, we write $[m; n]$ to denote the set $\{z \in \mathbb{Z} : m \le z \le n\}$ and set $[n] := [1; n]$. For a finite set $S$, we let $2^S$ denote the power set of $S$, and $U(S)$ denote the uniform distribution over $S$. For any $q \ge 2$, we let $\mathbb{Z}_q$ denote the ring of integers with addition and multiplication modulo $q$. Given a prime $q$ and an integer $N$, we denote by $GL_N(\mathbb{Z}_q)$ the general linear group of degree $N$ over $\mathbb{Z}_q$, and use non-boldface capital letters $B, H, \dots$ for scalar matrices in $GL_N(\mathbb{Z}_q)$. We write vectors as row-vectors, unless stated otherwise. For a vector $\mathbf{x}$ of dimension $n$, the notation $\mathbf{x}[i]$ indicates the $i$-th coordinate of $\mathbf{x}$, for $i \in [n]$. We will follow the implicit notation in [EHK$^{+}$13] and use $\llbracket a \rrbracket$ to denote $g^a$ in a cyclic group $\mathbb{G}$ of prime order $q$ generated by $g$, given $a \in \mathbb{Z}_q$. This implicit notation extends to matrices and vectors having entries in $\mathbb{Z}_q$, e.g. $\llbracket (a, b) \rrbracket = (g^a, g^b) \in \mathbb{G}^2$. We use boldface letters $\mathbf{B}, \mathbf{b}, \dots$ for matrices and vectors of group elements, unless stated otherwise. We use the shorthand *ppt* for “probabilistic polynomial time”. In the security proofs, whenever we use an ordered sequence of games ($G_0, G_1, \dots, G_i, \dots, G_L$) indexed by $i \in [0; L]$, we refer to the predecessor of $G_j$ by $G_{j-1}$, for $j \in [L]$.

## 3.1 Hardness Assumptions

We state the assumptions needed for our constructions.

**Definition 1** (Decisional Diffie-Hellman). In a cyclic group $\mathbb{G}$ of prime order $q$, the
Decisional Diffie-Hellman (DDH) problem is to distinguish the distributions

$$D_0 = \{([1], [a], [b], [ab])\} \qquad D_1 = \{([1], [a], [b], [c])\}.$$

for $a, b, c \leftarrow \mathbb{Z}_q$. The DDH assumption in $\mathbb{G}$ assumes that no ppt adversary can solve the DDH problem with non-negligible probability.

**Definition 2** (Decisional Separation Diffie-Hellman). In a cyclic group $\mathbb{G}$ of prime order $q$, the Decisional Separation Diffie-Hellman (DSDH) problem is to distinguish the distributions

$$D_0 = \{(x, y, [1], [a], [b], [ab + x])\} \qquad D_1 = \{(x, y, [1], [a], [b], [ab + y])\}$$

for any $x, y \in \mathbb{Z}_q$, and $a, b \leftarrow \mathbb{Z}_q$. The DSDH assumption in $\mathbb{G}$ assumes that no ppt adversary can solve the DSDH problem with non-negligible probability.

It can be shown straightforwardly that $\mathbf{Adv}_{\mathbb{G}}^{\text{DSDH}}(1^{\lambda}) \le 2 \cdot \mathbf{Adv}_{\mathbb{G}}^{\text{DDH}}(1^{\lambda})$.

**Definition 3** (Symmetric External Diffie-Hellman). In the bilinear setting $\mathbb{G} = (G_1, G_2, G_t, g_1, g_2, g_t, e, q)$, the Symmetric External Diffie-Hellman (SXDH) assumption makes the DDH assumption in both $G_1$ and $G_2$.

## 3.2 Dual Pairing Vector Spaces

We need the Decisional Diffie-Hellman (DDH) assumption in a cyclic group $\mathbb{G}$ of prime order $q$, which assumes no ppt adversary can distinguish $\{([1], [a], [b], [ab])\}$ from $\{([1], [a], [b], [c])\}$ with non-negligible probability, where the probability is taken over the choices $a, b, c \leftarrow \mathbb{Z}_q$ and the adversary's coins. In the bilinear setting $\mathbb{G} = (G_1, G_2, G_t, g_1, g_2, g_t, e, q)$, the Symmetric External Diffie-Hellman (SXDH) assumption makes the DDH assumption in both $G_1$ and $G_2$. Formal definitions are given in appendix A.1. Our constructions rely on the Dual Pairing Vector Spaces (DPVS) framework in the prime-order bilinear group setting $(G_1, G_2, G_t, g_1, g_2, g_t, e, q)$, and $G_1, G_2, G_t$ are all written additively. The DPVS technique dates back to the seminal work by Okamoto-Takashima [OT10, OT12a, OT12b] aiming at adaptive security for ABE as well as IBE, together with the dual system methodology introduced by Waters [Wat09]. In [LW10], the setting for dual systems is composite-order bilinear groups. Continuing on this line of works, Chen et al. [CLL+13] used prime-order bilinear groups under the SXDH assumption.

**Formalization.** Let us fix $N \in \mathbb{N}$ and consider $G_1^N$ having $N$ copies of $G_1$. Viewing $\mathbb{Z}_q^N$ as a vector space of dimension $N$ over $\mathbb{Z}_q$ with the notions of bases, we can obtain naturally a similar notion of bases for $G_1^N$. More specifically, any invertible matrix $B \in GL_N(\mathbb{Z}_q)$ identifies a basis $\mathbf{B}$ of $G_1^N$, whose $i$-th row $\mathbf{b}_i$ is $[B_i]_1$, where $B_i$ is the $i$-th row of $B$. It is straightforward that we can write $\mathbf{B} = [B]_1$ for any basis $\mathbf{B}$ of $G_1^N$ corresponding to an invertible matrix $B \in GL_N(\mathbb{Z}_q)$. We write $\mathbf{x} = (m_1, \dots, m_N)_{\mathbf{B}}$ to indicate the representation of $\mathbf{x}$ in the basis $\mathbf{B}$, i.e. $\mathbf{x} = \sum_{i=1}^N m_i \cdot \mathbf{b}_i$. At some point when we focus on the indices in an ordered list $L$ of length $l$, we write $\mathbf{x} = (m_{L[1]}, \dots, m_{L[l]})_{\mathbf{B}[L]}$. Treating $G_2^N$ similarly, we can furthermore define a product of two vectors $\mathbf{x} = [(m_1, \dots, m_N)]_1 \in G_1^N$, $\mathbf{y} = [(k_1, \dots, k_N)]_2 \in G_2^N$ by $\mathbf{x} \times \mathbf{y} := \prod_{i=1}^N \mathbf{e}(\mathbf{x}[i], \mathbf{y}[i]) = [(m_1, \dots, m_N), (k_1, \dots, k_N)]_t$. Given a basis $\mathbf{B} = (\mathbf{b}_i)_{i \in [N]}$ of $G_1^N$, we define $\mathbf{B}^*$ to be a basis of $G_2^N$ by first defining $\mathbf{B}^* := (B^{-1})^\top$ and the $i$-th row $\mathbf{b}_i^*$ of $\mathbf{B}^*$ is $[B_i^*]_2$. It holds that $B \cdot (B^*)^\top = I_N$ the identity matrix and $\mathbf{b}_i \times \mathbf{b}_j^* = [\delta_{i,j}]_t$ for every $i, j \in [N]$, where $\delta_{i,j} = 1$ if and only if $i = j$. We call the pair $(\mathbf{B}, \mathbf{B}^*)$ a pair of dual orthogonal bases of $(G_1^N, G_2^N)$. If $\mathbf{B}$ is constructed by a random invertible matrix $B \leftarrow GL_N(\mathbb{Z}_q)$, we call the resulting $(\mathbf{B}, \mathbf{B}^*)$ a pair of random dual bases. A DPVS is a bilinear group setting $\mathbb{G} = (G_1, G_2, G_t, g_1, g_2, g_t, e, q)$ with dual orthogonal bases. We denote by DPVSGen the algorithm that takes as inputs $\mathbb{G}$,
a unary $1^N$, and some random coins $r \in \{0,1\}^*$, then outputs a pair of random matrices $(B, B^*)$ that specify dual bases $(\mathbf{B} = \llbracket B \rrbracket_1, \mathbf{B}^* = \llbracket B^* \rrbracket_2)$ of $(\mathbb{G}_1^N, \mathbb{G}_2^N)$. Further details on DPVS-related techniques can be found in appendix A.1.

## 3.3 Decentralized Multi-Client Functional Encryption

The notion of *Decentralized Multi-Client Functional Encryption (DMCFE)* is introduced in [CDG+18a] where (1) the number of users is fixed in advanced by a (possibly interactive) global setup and (2) the key of a user can be an *encryption key* to encrypt their private individual data (a “client” in the terminology of [CDG+18a]) or a *secret key* to generate a functional key component (a “sender” in the terminology of [CDG+18a]). Moreover, for efficiency, prior papers (such as [CDG+18a, CDG+18b, ABKW19, ABG19, LT19, CDSG+20]) considered an additional *key combination algorithm* that, given $n$ functional key components $(\mathbf{dk}_{\text{tag-f},i})_{i \in [n]}$ generated for the same tag **tag-f**, outputs a succinct functional key $\mathbf{dk}_{\text{tag-f}}$ which can be passed to decryption $\text{Dec}(\mathbf{dk}_{\text{tag-f}}, \mathbf{c})$. Without loss of generality, the DMCFE notion in this paper implicitly includes the key combination algorithm in the decryption algorithm and whenever we refer to other existing DMCFE schemes, they are syntactically understood as such. The formal definition of DMCFE that is used in this paper is given below.

Let $\{\text{Tag}_\lambda\}_{\lambda \in \mathbb{N}}$, $\{\mathcal{D}_\lambda\}_{\lambda \in \mathbb{N}}$, $\{\mathcal{R}_\lambda\}_{\lambda \in \mathbb{N}}$ and $\{\text{Param}_\lambda\}_{\lambda \in \mathbb{N}}$ be sequences of tag, domain, range and parameter spaces, respectively. We consider a function class $\mathcal{F} = \{\mathcal{F}_{n,\lambda}\}_{n,\lambda \in \mathbb{N}}$, where each $\mathcal{F}_{n,\lambda} = \{f_{n,\lambda,(y_1,\dots,y_n)}\}_{(y_1,\dots,y_n)}$ contains functions $f_{n,\lambda,(y_1,\dots,y_n)}: \mathcal{D}_\lambda^n \to \mathcal{R}_\lambda$ described by their parameters $(y_1, \dots, y_n) \in \text{Param}_\lambda^n$.<fnref n="5" />

**Definition 4** (Decentralized Multi-Client Functional Encryption). A DMCFE scheme $\mathcal{E}$ for $\mathcal{F}$ between $n$ senders $(S_i)_{i \in [n]}$ and a functional decrypter $\mathcal{FD}$ consists of the four algorithms defined below:

*   **Setup(1^λ, 1^n):** This is a protocol between the senders that eventually generate their own secret keys $\mathbf{sk}_i$ and encryption keys $\mathbf{ek}_i$, as well as some optional public parameters $\mathbf{pp}$. We will assume that all the secret and encryption keys implicitly contain $\mathbf{pp}$.

*   **DKeyGen(\mathbf{sk}_i, \text{tag-f}, y_i):** On input a secret key $\mathbf{sk}_i$, a tag **tag-f** $\in \text{Tag}$, and parameter $y_i \in \text{Param}_\lambda$, this algorithm outputs a partial decryption key $\mathbf{dk}_{\text{tag-f},i}$.

*   **Enc(ek_i, tag, x_i):** On input an encryption key $\mathbf{ek}_i$, a tag **tag** and a message $x_i \in \mathcal{D}_\lambda$, this algorithm outputs a ciphertext $\mathbf{ct}_{\text{tag},i}$.

*   **Dec(d, c):** On input a list of functional decryption keys $\mathbf{d} := (\mathbf{dk}_{\text{tag-f},i})_{i=1}^n$ and a list of ciphertexts $\mathbf{c} := (\mathbf{ct}_{\text{tag},i})_{i=1}^n$, this algorithm runs a key combination if necessary, then outputs an element $\mathbf{d} \in \mathcal{R}_\lambda$ or a symbol $\perp$.

**Correctness.** $\mathcal{E}$ is correct if for all $\lambda, n \in \mathbb{N}$, $(x_1, \dots, x_n) \in \mathcal{D}_\lambda^n$, $f_{n,\lambda,(y_1,\dots,y_n)} \in \mathcal{F}_{n,\lambda}$ having parameters $(y_1, \dots, y_n) \in \text{Param}_\lambda^n$, and for any **tag**, **tag-f** $\in \text{Tag}_\lambda$, we have

$$ \Pr \left[ d = f_{n,\lambda,(y_1,\dots,y_n)}(x_1, \dots, x_n) \left| \begin{array}{l} (\mathbf{pp}, (\mathbf{sk}_i)_{i \in [n]}, (\mathbf{ek}_i)_{i \in [n]}) \leftarrow \text{Setup}(1^\lambda, 1^n) \\ \forall i \in [n]: \mathbf{dk}_{\text{tag-f},i} \leftarrow \text{DKeyGen}(\mathbf{sk}_i, \text{tag-f}, y_i) \\ \forall i \in [n]: \mathbf{ct}_{\text{tag},i} \leftarrow \text{Enc}(\mathbf{ek}_i, \text{tag}, x_i) \\ d := \text{Dec}((\mathbf{dk}_{\text{tag-f},i})_{i \in [n]}, (\mathbf{ct}_{\text{tag},i})_{i \in [n]}) \end{array} \right. \right] = 1 $$

where the probability is taken over the random coins of the algorithms.

<footnote n="5">⁵Implicitly, we use a deterministic encoding $\mathbf{p}_\lambda : \mathcal{F}_\lambda \to \text{Param}_\lambda \times \dots \times \text{Param}_\lambda$ in order to associate each function to its parameters.</footnote>
**Security.** We define function-hiding and standard security for DMCFE. In the seminal work by Chotard et al. [CDG+18a] and its follow-up study [CDSG+20], the security notion does not cover the function-hiding requirement for DMCFE or its more general sibling DDFE. Until recently, the work by Agrawal et al. [AGT21b] abstracted out DMCFE into the notion of Multi-Party Functional Encryption (MPFE). The authors of [AGT21b] also used MPFE to spell out the function-hiding security for MCFE as well as for DDFE. The latter does capture DMCFE as a particular case but for convenience of the reader, we introduce the detailed function-hiding security for DMCFE, without going through all the abstraction of MPFE nor of DDFE. Our security definition follows the Game-Playing Framework in [BR06]: Figure 2 defines the experiment $\mathbf{Exp}_{\mathcal{E}, \mathcal{F}, \mathcal{A}}^{\mathbf{fh}}(1^{\lambda})$ with procedures Initialize, ODKeyGen, OEnc, OCorrupt and Finalize; the adversary $\mathcal{A}$ runs Initialize, can call the oracles in any order and any number of times, and finishes the run by calling Finalize on input the guess $b'$.

**Definition 5 (Function-Hiding Security).** Let $\lambda \in \mathbb{N}$ be a security parameter. For a DMCFE scheme $\mathcal{E}$, a function class $\mathcal{F} = \{\mathcal{F}_{n,\lambda}\}_{n,\lambda}$ and a ppt adversary $\mathcal{A}$ we define the experiment $\mathbf{Exp}_{\mathcal{E}, \mathcal{F}, \mathcal{A}}^{\mathbf{fh}}(1^{\lambda})$ as shown in Figure 2 and set $\mathcal{H} := [n] \setminus \mathcal{C}$. The oracles OEnc, ODKeyGen and OCorrupt can be called in any order and any number of times. The adversary $\mathcal{A}$ is NOT admissible with respect to $\mathcal{C}$, $Q_{\text{Enc}}$, $Q_{\text{KGen}}$, denoted by $\text{adm}(\mathcal{A}) = 0$, if either one of the following holds:

1. There exists a tuple $(i, \text{tag}, x_i^{(0)}, x_i^{(1)}) \in Q_{\text{Enc}}$ or $(i, \text{tag-f}, y_i^{(0)}, y_i^{(1)}) \in Q_{\text{KGen}}$ such that $i \in \mathcal{C}$ and $x_i^{(0)} \neq x_i^{(1)}$ or $y_i^{(0)} \neq y_i^{(1)}$.

2. There exist tag, tag-f in Tag, two vectors $(x_i^{(0)})_{i \in [n]}$, $(x_i^{(1)})_{i \in [n]} \in \mathcal{D}_1 \times \dots \times \mathcal{D}_n$ and functions $f_{n,\lambda,(y_1^{(0)},...,y_n^{(0)})}^{(0)}$, $f_{n,\lambda,(y_1^{(1)},...,y_n^{(1)})}^{(1)} \in \mathcal{F}$ having parameters $(y_i^{(0)}, y_i^{(1)})_{i \in [n]}$ such that

$\bullet$ $(i, \text{tag}, x_i^{(0)}, x_i^{(1)}) \in Q_{\text{Enc}}$ and $(i, \text{tag-f}, y_i^{(0)}, y_i^{(1)}) \in Q_{\text{KGen}}$ for all $i \in \mathcal{H}$,

$\bullet$ $x_i^{(0)} = x_i^{(1)}$ and $y_i^{(0)} = y_i^{(1)}$ for all $i \in \mathcal{C}$, and

$\bullet$ $f_{n,\lambda,y_1^{(0)},...,y_n^{(0)}}^{(0)}(x_1^{(0)},...,x_n^{(0)}) \neq f_{n,\lambda,y_1^{(1)},...,y_n^{(1)}}^{(1)}(x_1^{(1)},...,x_n^{(1)})$.

Otherwise, we say that $\mathcal{A}$ is admissible w.r.t $\mathcal{C}$, $Q_{\text{Enc}}$ and $Q_{\text{KGen}}$ and write $\text{adm}(\mathcal{A}) = 1$. We call $\mathcal{E}$ function-hiding if for all ppt adversaries $\mathcal{A}$,

$$ \mathbf{Adv}_{\mathcal{E}, \mathcal{F}, \mathcal{A}}^{\mathbf{fh}}(1^{\lambda}) := \left| \Pr \left[ \mathbf{Exp}_{\mathcal{E}, \mathcal{F}, \mathcal{A}}^{\mathbf{fh}}(1^{\lambda}) = 1 \right] - \frac{1}{2} \right| $$

is negligible in $\lambda$.

**Weaker Notions.** We define weaker variants of indistinguishability by restricting the access to the oracles and imposing stronger admissibility conditions. In this paper we first present our main technical scheme under some weaker notions, then our final scheme under stronger notions is obtained following some general lemmas (see Section 5).

1. Security against Static Corruption: The experiment $\mathbf{Exp}_{\mathcal{E}, \mathcal{F}, \mathcal{A}}^{\text{stat-fh}}(1^{\lambda})$ is the same as $\mathbf{Exp}_{\mathcal{E}, \mathcal{F}, \mathcal{A}}^{\mathbf{fh}}(1^{\lambda})$ except that all queries to the oracle OCorrupt must be submitted before Initialize is called.

<footnote n="6">⁶This admissibility condition on $x_i^{(0)} = x_i^{(1)}$ for all $i \in \mathcal{C}$ was introduced in [CDG+18a] then used in all other works on (D)MCFE [CDG+18a, LT19, ABKW19, ABG19] and later on DDFE [CDSG+20, AGT21b]. A recent work [NPP23] studies the relaxation that removes this condition for (D)MCFE, i.e. allowing $x_i^{(0)} \neq x_i^{(1)}$ for $i \in \mathcal{C}$ and more attacks are considered admissible, and gives a provably secure DMCFE candidate computing inner products. We are not aware of any DMCFE scheme in the literature which is proven secure under the stronger notion from [NPP23].</footnote>
Initialize(1$^{\lambda}$, 1$^{n}$):
$\overline{C}$, $\overline{Q}_{\text{Enc}}$, $\overline{Q}_{\text{KGen}} \leftarrow \emptyset$; $b \leftarrow \{0, 1\}$
(pp, $(\text{sk}_i)_{i \in [n]}$, $(\text{ek}_i)_{i \in [n]}$) $\leftarrow$ Setup(1$^{\lambda}$, 1$^{n}$)
Return pp

$\mathcal{O}\text{DKeyGen}(i, \text{tag-f}, y_i^{(0)}, y_i^{(1)})$:
$\mathcal{Q}_{\text{KGen}} \leftarrow \mathcal{Q}_{\text{KGen}} \cup \{(i, \text{tag-f}, y_i^{(0)}, y_i^{(1)})\}$
Return $\text{dk}_{f,i} \leftarrow \text{DKeyGen}(\text{sk}_i, \text{tag-f}, y_i^{(b)})$

$\mathcal{O}\text{Enc}(i, \text{tag}, x_i^{(0)}, x_i^{(1)})$:
$\overline{Q}_{\text{Enc}} \leftarrow \overline{Q}_{\text{Enc}} \cup \{(i, \text{tag}, x_i^{(0)}, x_i^{(1)})\}$
Return $ct \leftarrow \text{Enc}(\text{ek}_i, \text{tag}, x_i^{(b)})$

$\mathcal{O}\text{Corrupt}(i)$:
$\overline{C} \leftarrow \mathcal{C} \cup \{i\}$; return $(\text{sk}_i, \text{ek}_i)$

Finalize($b'$):
If $\text{adm}(\mathcal{A}) = 1$, return $\beta \leftarrow (b' \stackrel{?}{=} b)$
Else, return 0

<caption>**Figure 2:** Security game $\mathbf{Exp}_{\mathcal{E},\mathcal{F},\mathcal{A}}^{\mathcal{fh}}(1^{\lambda})$ for Definition 5</caption>

2. *Security against Selective Challenges:* The experiment $\mathbf{Exp}_{\mathcal{E},\mathcal{F},\mathcal{A}}^{\text{sel-fh}}(1^{\lambda})$ is the same as $\mathbf{Exp}_{\mathcal{E},\mathcal{F},\mathcal{A}}^{\mathcal{fh}}(1^{\lambda})$ except that all queries to the oracles $\mathcal{O}\text{KeyGen}$ and $\mathcal{O}\text{Enc}$ must be submitted before Initialize is called.

3. *One-time Security:* The experiment $\mathbf{Exp}_{\mathcal{E},\mathcal{F},\mathcal{A}}^{\text{1chal-fh}}(1^{\lambda})$ is the same as $\mathbf{Exp}_{\mathcal{E},\mathcal{F},\mathcal{A}}^{\mathcal{fh}}(1^{\lambda})$ except that the adversary must declare up front to Initialize two additional “challenge” tags $\text{tag}^*$, $\text{tag-f}^* \in \text{Tag}$ such that for all $\text{tag}, \text{tag-f} \in \text{Tag}$:

* if $(i, \text{tag}, x_i^{(0)}, x_i^{(1)}) \in \mathcal{Q}_{\text{Enc}}$ and $\text{tag} \neq \text{tag}^*$, then $x_i^{(0)} = x_i^{(1)}$,

* if $(i, \text{tag-f}, y_i^{(0)}, y_i^{(1)}) \in \mathcal{Q}_{\text{KGen}}$ and $\text{tag-f} \neq \text{tag-f}^*$, then $y_i^{(0)} = y_i^{(1)}$.

4. *Security against Complete Challenges:* The experiment $\mathbf{Exp}_{\mathcal{E},\mathcal{F},\mathcal{A}}^{\text{pos-fh}}(1^{\lambda})$ is the same as $\mathbf{Exp}_{\mathcal{E},\mathcal{F},\mathcal{A}}^{\mathcal{fh}}(1^{\lambda})$ except that we add the following condition 3 for $\text{adm}(\mathcal{A}) = 0$ that we call the *complete-query constraint*:

3. There exists $\text{tag} \in \text{Tag}$ so that a query $\mathcal{O}\text{Enc}(i, \text{tag}, x_i^{(0)}, x_i^{(1)})$ has been asked for some but not all $i \in \mathcal{H}$, or there exists $\text{tag-f} \in \text{Tag}$ such that a query $\mathcal{O}\text{KeyGen}(i, \text{tag-f}, y_i^{(0)}, y_i^{(1)})$ has been asked for some but not all $i \in \mathcal{H}$.

In other words, we require for an adversary $\mathcal{A}$ to be *admissible* that, for any tag, either $\mathcal{A}$ makes no encryption (resp. key) query or makes at least one encryption (resp. key) query for each slot $i \in \mathcal{H}$.

5. *Weak Function-Hiding:* We can weaken the function-hiding property by changing condition 2 for $\text{adm}(\mathcal{A}) = 0$. More specifically, we replace it by the following condition 2':

2. There exist $\text{tag}, \text{tag-f} \in \text{Tag}$, $(x_i^{(0)})_{i \in [n]}$ and $(x_i^{(1)})_{i \in [n]}$ in $\mathcal{D}_1 \times \dots \times \mathcal{D}_n$ and two functions $f_{n,\lambda,(y_1^{(0)},\dots,y_n^{(0)})}^{(0)}$, $f_{n,\lambda,(y_1^{(1)},\dots,y_n^{(1)})}^{(1)} \in \mathcal{F}$ having parameters $(y_i^{(0)}, y_i^{(1)})_{i=1}^n$ such that

* $(i, \text{tag}, x_i^{(0)}, x_i^{(1)}) \in \mathcal{Q}_{\text{Enc}}$ and $(i, \text{tag-f}, y_i^{(0)}, y_i^{(1)}) \in \mathcal{Q}_{\text{KGen}}$ for all $i \in \mathcal{H}$,

* $x_i^{(0)} = x_i^{(1)}$ and $y_i^{(0)} = y_i^{(1)}$ for all $i \in \mathcal{C}$, and

* $f_{n,\lambda,(y_1^{(0)},\dots,y_n^{(0)})}^{(0)}(x_1^{(0)}, \dots, x_n^{(0)}) \neq f_{n,\lambda,(y_1^{(1)},\dots,y_n^{(1)})}^{(1)}(x_1^{(1)}, \dots, x_n^{(1)})$ OR

* $f_{n,\lambda,(y_1^{(0)},\dots,y_n^{(0)})}^{(0)}(x_1^{(0)}, \dots, x_n^{(0)}) \neq f_{n,\lambda,(y_1^{(1)},\dots,y_n^{(1)})}^{(1)}(x_1^{(1)}, \dots, x_n^{(1)})$ OR

* $f_{n,\lambda,(y_1^{(1)},\dots,y_n^{(1)})}^{(1)}(x_1^{(0)}, \dots, x_n^{(0)}) \neq f_{n,\lambda,(y_1^{(1)},\dots,y_n^{(1)})}^{(1)}(x_1^{(1)}, \dots, x_n^{(1)})$.
The experiment in this weak function-hiding model is denoted by $\mathbf{Exp}_{\mathcal{E}, \mathcal{F}, \mathcal{A}}^{\text{wfh}}(1^{\lambda})$.

In this paper we focus on the concrete class of inner products. The function family $\mathcal{F}_n^{\text{ip}}$ of bounded-norm inner-product functionalities with $n$ inputs is defined as follows.

**Definition 6 (Inner Product Functionality).** For $n, \lambda \in \mathbb{N}$, let $\mathcal{D}_{\lambda} = \text{Param}_{\lambda} = [-B; B]^N$ and $\mathcal{R}_{\lambda} = [-nNB^2; nNB^2]$, where $B = B(\lambda)$ and $N = N(\lambda): \mathbb{N} \to \mathbb{N}$ are polynomials. We define the inner-product functionality $\mathcal{F}^{\text{ip}} = \{\mathcal{F}_{n,\lambda}^{\text{ip}}\}_{n,\lambda \in \mathbb{N}}$ for $\mathcal{F}_{n,\lambda}^{\text{ip}} = \{f_{n,\lambda,(y_1, \dots, y_n)}: \mathcal{D}_{\lambda}^n \to \mathcal{R}_{\lambda}\}_{(y_1, \dots, y_n) \in \text{Param}_{\lambda}^n}$ as the family of functions

$$f_{n,\lambda,(y_1, \dots, y_n)}(\mathbf{x}_1, \dots, \mathbf{x}_n) = \sum_{i=1}^{n} \langle \mathbf{x}_i, \mathbf{y}_i \rangle.$$

# 4 A FH-DMCFE for Inner Products

## 4.1 Swapping Lemma

In this section we state a technical lemma that will be the basis of the security analysis of our function-hiding IP-DMCFE. This lemma plays an important role in the proof of Theorem 1 and is revisited in Section 4.2. As a reminder, we refer to the paragraph **Problems for Adaptive Security** in the technical overview of Section 2 for a discussion on why the oracles in the following statement of Lemma 1 are relevant afterwards in the FH-DMCFE proof.

**Lemma 1 (Swapping).** Let $\lambda \in \mathbb{N}$ and $H = H(\lambda), K = K(\lambda), L = L(\lambda), J_i = J_i(\lambda), \tilde{J}_i = \tilde{J}_i(\lambda), N = N(\lambda) \in \mathbb{N}$ where $i \in [H]$ and $H, K, L, J_i, \tilde{J}_i, N: \mathbb{N} \to \mathbb{N}$ are polynomials. Let $\tilde{J} := \max_{i \in [H]} \{\tilde{J}_i\}$, where the maximum is over polynomial evaluations $\tilde{J}_i(\lambda) \in \mathbb{N}$. Let $(\mathbf{B}_i, \mathbf{B}_i^*)$, for each $i \in [H]$, be a pair of random dual bases of dimension $2N + 2N \cdot \tilde{J} + 4$ in $(\mathbb{G}_1, \mathbb{G}_2, \mathbb{G}_t, g_1, g_2, g_t, \mathbf{e}, \mathbf{q})$. All basis vectors are kept secret. Let $R, R_1, \dots, R_K \in \mathbb{Z}_q$ be some public scalars. For $i \in [H]$, $\ell \in [L]$ and $k \in [K]$, sample $\sigma_i, \sigma_{i,k}, r, r_{\ell} \stackrel{\$}{\leftarrow} \mathbb{Z}_q$ conditioned on $\sum_{i \in [H]} \sigma_i = R$ and $\sum_{i \in [H]} \sigma_{k,i} = R_k$. We consider the following oracles:

$\tilde{\mathcal{O}}_d$: On input $(\ell, i, \mathbf{y}_{\ell,i}^{(\text{rep})}, \mathbf{y}_{\ell,i}^{(\text{rep})}') \in [L] \times [H] \times \mathbb{Z}_q^N \times \mathbb{Z}_q^N$, where $\text{rep} \in [J_i]$ is a counter for the number of queries of the form $(\ell, i, \star, \star)$, sample $\rho_{\ell,i}^{(\text{rep})} \stackrel{\$}{\leftarrow} \mathbb{Z}_q$ and output

$$\mathbf{d}_{\ell,i}^{(\text{rep})} = (\mathbf{y}_{\ell,i}^{(\text{rep})}, \mathbf{y}_{\ell,i}^{(\text{rep})}', r_{\ell}, 0, \rho_{\ell,i}^{(\text{rep})}, 0^{2N \cdot \tilde{J}+1})_{\mathbf{B}_i}.$$

$\tilde{\mathcal{O}}_d^b$: For $b \in \{0, 1\}$, on input $(i, \mathbf{y}_i^{(1, \tilde{J}_i)}, \mathbf{y}_i^{(0, \tilde{J}_i)}) \in [H] \times \mathbb{Z}_q^N$, where $\tilde{J}_i \in [\tilde{J}_i]$ is a counter for the number of queries of the form $(i, \star, \star)$, sample $\rho_i^{(\tilde{J}_i)} \stackrel{\$}{\leftarrow} \mathbb{Z}_q$ and output

$$\text{If } \underline{b=0}: \quad \mathbf{d}_{i}^{(\tilde{J}_i)} = (\underline{\mathbf{y}_{i}^{(1, \tilde{J}_i)}}, \underline{0}^N], r, 0, \rho_{i}^{(\tilde{J}_i)}, 0^{2N \cdot \tilde{J}+1})_{\mathbf{B}_i}$$

$$\text{If } \underline{b=1}: \quad \mathbf{d}_{i}^{(\tilde{J}_i)} = (\underline{0}^N], \underline{\mathbf{y}_{i}^{(0, \tilde{J}_i)}}, r, 0, \rho_{i}^{(\tilde{J}_i)}, 0^{2N \cdot \tilde{J}+1})_{\mathbf{B}_i}.$$

$\tilde{\mathcal{O}}_c$: On input $(i, \mathbf{x}_i^{(1, \tilde{J}_i)}, \mathbf{x}_i^{(0, \tilde{J}_i)}) \in [H] \times \mathbb{Z}_q^N \times \mathbb{Z}_q^N$, where $\tilde{J}_i \in [J_i]$ is a counter for the number of queries of the form $(i, \star, \star)$, sample $\pi_i^{(\tilde{J}_i)} \stackrel{\$}{\leftarrow} \mathbb{Z}_q$ and output

$$\mathbf{c}_{i}^{(\tilde{J}_i)} = (\mathbf{x}_{i}^{(1, \tilde{J}_i)}, \mathbf{x}_{i}^{(0, \tilde{J}_i)}, \sigma_i, \pi_{i}^{(\tilde{J}_i)}, 0, 0^{2N \cdot \tilde{J}+1})_{\mathbf{B}_i^*}.$$

$\tilde{\mathcal{O}}_c$: On inputs $(k, i, \mathbf{x}_{k,i}^{(\text{rep})}) \in [K] \times [H] \times \mathbb{Z}_q$, where $\text{rep} \in [J_i]$ is a counter for the number of queries of the form $(k, i, \star)$, sample $\pi_{k,i}^{(\text{rep})} \stackrel{\$}{\leftarrow} \mathbb{Z}_q$ and output

$$\mathbf{c}_{k,i}^{(\text{rep})} = (\mathbf{x}_{k,i}^{(\text{rep})}, \mathbf{x}_{k,i}^{(\text{rep})}, \sigma_{k,i}, \pi_{k,i}^{(\text{rep})}, 0, 0^{2N \cdot \tilde{J}+1})_{\mathbf{B}_i^*}.$$
If $\sum_{i=1}^{H} \langle \mathbf{y}_i^{(1, \tilde{j}_i)}, \mathbf{x}_i^{(1, \tilde{j}_i)} \rangle - \langle \mathbf{y}_i^{(0, \tilde{j}_i)}, \mathbf{x}_i^{(0, \tilde{j}_i)} \rangle = 0$ and $\sum_{i=1}^{H} \langle \mathbf{y}_i^{(1, \tilde{j}_i)} - \mathbf{y}_i^{(0, \tilde{j}_i)}, \mathbf{x}_i^{(\text{rep})} \rangle = 0$ for all $\tilde{j}_i \in [\tilde{J}_i]$, rep, $j_i \in [J_i]$, then the following advantage is negligible under the SXDH assumption:

$$ \left| \Pr[\mathcal{A}_{\tilde{O}_c, \mathcal{O}_c}^{\tilde{O}_d, \mathcal{O}_d^0} (1^{\lambda}, N, H, K, L, (J_i, \tilde{J}_i)_{i \in [H]}, R, (R_k)_{k \in [K]}) \to 1] \\ - \Pr[\mathcal{A}_{\tilde{O}_c, \mathcal{O}_c}^{\tilde{O}_d, \mathcal{O}_d^1} (1^{\lambda}, N, H, K, L, (J_i, \tilde{J}_i)_{i \in [H]}, R, (R_k)_{k \in [K]}) \to 1] \right| \\ \le (4n\tilde{J}N + 4) \cdot \mathbf{Adv}_{\mathcal{G}_1, \mathcal{G}_2}^{\text{SXDH}}(1^{\lambda}) $$

where $\mathcal{A}$ can query the oracles $\tilde{O}_d$, $\mathcal{O}_d^b$, $\mathcal{O}_c$, $\tilde{O}_c$ adaptively, i.e. the queries can be made in any order and any number of times respecting the (polynomial) upper bounds $K, L, (J_i, \tilde{J}_i)_{i \in [H]}$.

We give an informal proof sketch of the main ideas. The full proof is presented in appendix A.2. The sequence of games is depicted in Figure 4.

**Outline of the Proof for Lemma 1.** We explain the main steps in our proof as follows, where details about formal and computational basis changes can be revised from the examples in Basis Changes of appendix A.1. The proof is done so that for all the repetitions $\tilde{j}_i \in [\tilde{J}_i]$, we perform the change from the repetition $\tilde{\mathbf{y}}_i^{(0, \tilde{j}_i)}$ into $\tilde{\mathbf{y}}_i^{(1, \tilde{j}_i)}$ by the $\tilde{j}_i$-th block of isolated coordinates in the vectors $\mathbf{d}_i^{(\tilde{j}_i)}$. It is crucial that the polynomially large bound $\tilde{J} \ge \max_{i \in [n], \text{tag-f} \in \text{Tag}} \tilde{J}_{i, \text{tag-f}}$ is known in advance, so as to well define the dimension of DPVS bases.

We start from the game where the sample given to the adversary $\mathcal{A}$ follows $D_0$ and the changes on vectors throughout the games are put in boxes. We use the notation $\mathbf{0} := \mathbf{0}^N$ and write $\mathbf{0}^{\tilde{J}} := \mathbf{0} \parallel \dots \parallel \mathbf{0}$, for $\tilde{J}$ times. Our first step is to exploit the fact that $r \stackrel{\$}{\leftarrow} \mathbb{Z}_q$ is a uniformly random value and for each $j_i \in [J_i]$ all the secret shares $\sigma_i$ in $\mathbf{c}_i^{(\tilde{j}_i)}$ sum to a known constant $R$. This helps us perform a computational basis change on $(\mathbf{B}_i, \mathbf{B}_i^*)$ and introduce a value $r' \stackrel{\$}{\leftarrow} \mathbb{Z}_q^*$ in $\mathbf{d}_i[2N + 2N \cdot \tilde{J} + 4]$ as well as random secret shareings of $0$, common for $j_i \in [J_i]$, namely $(\tau_i)_{i=1}^H$, $(\tau'_{k,i})_{i=1}^H$, in $(\mathbf{c}_i^{(\tilde{j}_i)}[2N + 2N \cdot \tilde{j}_i + 4])_{i=1}^H$, $(\mathbf{c}_{k,i}^{(\text{rep})}[2N + 2N \cdot \tilde{j}_i + 4])_{i=1}^H$. We use the hypothesis that all basis vectors are kept secret so that the computational basis change using DDH cannot be detected by the adversary. More details can be found in the transition $G_0 \to G_1$.

After $G_1$, we perform a formal duplication to go to $G_2$ in which we duplicate coordinates $[1, N]$, $[N+1, 2N]$ to the $\tilde{J}$ blocks $[2N \cdot \tilde{j} + 4, N + 2N \cdot \tilde{j} + 3]$, $[N + 2N \cdot \tilde{j} + 4, 2N + 2N \cdot \tilde{j} + 3]$, where $\tilde{j}$ runs in $[\tilde{J}]$, in vectors $\mathbf{c}_i^{(\tilde{j}_i)}$, $\mathbf{c}_{k,i}^{(\text{rep})}$ for all $i \in [H]$, $k \in [K]$, $j_i \in [J_i]$.

$$ \begin{aligned} \mathbf{d}_{\ell, i}^{(\text{rep})} &= ( \mathbf{y}_{\ell, i}^{(\text{rep})} | \mathbf{y}_{\ell, i}^{(\text{rep})'} | r_{\ell} | 0 | \rho_{\ell, i}^{(\text{rep})} | \begin{pmatrix} \mathbf{0} \\ \mathbf{0} \end{pmatrix}^{\tilde{J}} | \mathbf{0} )_{\mathbf{B}_i} & 0 & )_{\mathbf{B}_i} \\ \mathbf{d}_i^{(\tilde{j}_i)} &= ( \mathbf{y}_i^{(1, \tilde{j}_i)} | \mathbf{0} | r | 0 | \rho_i^{(\tilde{j}_i)} | \begin{pmatrix} \mathbf{0} \\ \mathbf{0} \end{pmatrix}^{\tilde{J}} | \mathbf{0} )_{\mathbf{B}_i} & r' & )_{\mathbf{B}_i} \\ \mathbf{c}_i^{(\tilde{j}_i)} &= ( \mathbf{x}_i^{(1, \tilde{j}_i)} | \mathbf{x}_i^{(0, \tilde{j}_i)} | \sigma_i | \pi_i^{(\tilde{j}_i)} | 0 | \begin{pmatrix} \mathbf{x}_i^{(1, \tilde{j}_i)} \\ \mathbf{x}_i^{(0, \tilde{j}_i)} \end{pmatrix}^{\tilde{J}} | \mathbf{0} )_{\mathbf{B}_i} & \tau_i & )_{\mathbf{B}_i^*} \\ \mathbf{c}_{k, i}^{(\text{rep})} &= ( \mathbf{x}_{k, i}^{(\text{rep})} | \mathbf{x}_{k, i}^{(\text{rep})} | \sigma_{k, i} | \pi_{k, i}^{(\text{rep})} | 0 | \begin{pmatrix} \mathbf{x}_{k, i}^{(\text{rep})} \\ \mathbf{x}_{k, i}^{(\text{rep})} \end{pmatrix}^{\tilde{J}} | \mathbf{0} )_{\mathbf{B}_i} & \tau'_{k, i} & )_{\mathbf{B}_i^*} \end{aligned} $$

The duplication is done for all vectors $\mathbf{c}_i^{(\tilde{j}_i)}$, $\mathbf{c}_{k,i}^{(\text{rep})}$ also across all repetitions $\text{rep} \in [J]$. On a more technical level, this formal basis change will affect all vectors $\mathbf{d}_{\ell, i}^{(\text{rep})}$, $\mathbf{d}_i$ as well, also across all repetitions $\tilde{j}_i$, $\text{rep} \in [\tilde{J}_i]$. Roughly speaking, by the duality of $(\mathbf{B}_i, \mathbf{B}_i^*)$, this basis change will incur “moving” coordinates $[2N \cdot \tilde{j}_i + 4, N + 2N \cdot \tilde{J} + 3]$, $[N + 2N \cdot \tilde{J} + 4, 2N + 2N \cdot \tilde{J} + 3]$, for each $\tilde{j}_i \in [\tilde{J}]$ to $[1, N]$, $[N+1, 2N]$ in the $\mathbf{d}$-vectors. In this simple $G_1 \to G_2$, the moved coordinates contain $0$, so they do not pose any problems.

After $G_2$, in all $\mathbf{c}$-vectors, each of the $\tilde{J}$ blocks $[2N \cdot \tilde{j} + 4, N + 2N \cdot \tilde{j} + 3]$, $[N + 2N \cdot \tilde{j} + 4, 2N + 2N \cdot \tilde{J} + 3]$ contains a copy of the coordinates $[1, N]$, $[N+1, 2N]$. This allows us
to perform a computational basis change under SXDH in order to swap between [1, N] and
$[2N \cdot \tilde{j}_i + 4, N + 2N \cdot \tilde{j}_i + 3]$ in $\mathbf{d}_i^{(\tilde{j}_i)}$, for each $\tilde{j}_i \in [\tilde{J}_i]$ and $\tilde{J}_i \le \tilde{J}$ by definition. We stress
that for different $\tilde{j}_i$, the swap will move contents of [1, N] to separated coordinates in
different $\mathbf{d}_i^{(\tilde{j}_i)}$. In other words, for every $\tilde{j}_i, \tilde{j}_i'$, the coordinates $[2N \cdot \tilde{j}_i' + 4, N + 2N \cdot \tilde{j}_i' + 3]$
is well defined for $\mathbf{d}_i^{(\tilde{j}_i)}$ because $\tilde{j}_i \le \tilde{J}_i \le \tilde{J}$ and we have

$$
\mathbf{d}_{i}^{(\tilde{j}_{i})}[2N \cdot \tilde{j}_{i} + 4, N + 2N \cdot \tilde{j}_{i} + 3] = \begin{cases} \mathbf{y}_{i}^{(1, \tilde{j}_{i}')} & \text{if } \tilde{j}_{i} = \tilde{j}_{i}' \\ \mathbf{0} & \text{if } \tilde{j}_{i} \neq \tilde{j}_{i}' \end{cases} . \quad (8)
$$

The randomness is taken from $\rho_i$ at coordinate $2N + 3$ in $\mathbf{d}_i^{(\tilde{j}_i)}$.

$$
\begin{align*}
\mathbf{d}_{\ell, i}^{(\text{rep})} &= \left( \begin{array}{c} \mathbf{y}_{\ell, i}^{(\text{rep})} \\ \mathbf{y}_{\ell, i}^{(\text{rep})'} \end{array} \right) &
\begin{array}{c}
r_{\ell} \\ 0
\end{array} &
\begin{array}{c}
0 \\ \rho_{\ell, i}^{(\text{rep})}
\end{array} &
\cdots &
\begin{array}{c}
0 \\ \mathbf{y}_{i}^{(1, \tilde{j}_{i})} \end{array} &
\begin{array}{c}
0 \\ \mathbf{0} \end{array} &
\cdots &
\begin{array}{c}
0 \\ r' \end{array} &
\mathbf{B}_{i} \\
\mathbf{d}_{i}^{(\tilde{j}_{i})} &= \left( \begin{array}{c} \mathbf{0} \\ \mathbf{0} \end{array} \right) &
\begin{array}{c}
r \\ 0
\end{array} &
\begin{array}{c}
0 \\ \rho_{i}^{(\tilde{j}_{i})} \end{array} &
\cdots &
\begin{array}{c}
0 \\ \mathbf{0} \end{array} &
\begin{array}{c}
r' \\ \tau_{i} \end{array} &
\cdots &
\begin{array}{c}
r' \\ \tau_{k,i} \end{array} &
\mathbf{B}_{i}^{*} \\
\mathbf{c}_{i}^{(\tilde{j}_{i})} &= \left( \begin{array}{c} \mathbf{x}_{i}^{(1, \tilde{j}_{i})} \\ \mathbf{x}_{i}^{(0, \tilde{j}_{i})} \end{array} \right) &
\begin{array}{c}
\sigma_{i} \\ \pi_{i}^{(\tilde{j}_{i})} \end{array} &
\begin{array}{c}
0 \\ 0 \end{array} &
\cdots &
\begin{array}{c}
0 \\ \mathbf{x}_{i}^{(1, \tilde{j}_{i})} \end{array} &
\begin{array}{c}
\mathbf{x}_{i}^{(0, \tilde{j}_{i})} \\ \pi_{k,i}^{(\text{rep})} \end{array} &
\cdots &
\begin{array}{c}
0 \\ \tau_{k,i} \end{array} &
\mathbf{B}_{i}^{*} \\
\mathbf{c}_{k,i}^{(\text{rep})} &= \left( \begin{array}{c} \mathbf{x}_{k,i}^{(\text{rep})} \\ \mathbf{x}_{k,i}^{(\text{rep})} \end{array} \right) &
\begin{array}{c}
\sigma_{k,i} \\ \pi_{k,i}^{(\text{rep})} \end{array} &
\begin{array}{c}
0 \\ 0 \end{array} &
\cdots &
\begin{array}{c}
0 \\ \mathbf{x}_{k,i}^{(\text{rep})} \end{array} &
\begin{array}{c}
\mathbf{x}_{k,i}^{(\text{rep})} \\ \tau'_{k,i} \end{array} &
\cdots &
\begin{array}{c}
0 \\ \tau'_{k,i} \end{array} &
\mathbf{B}_{i}^{*}
\end{align*}
$$

As a sanity check, we observe that this change preserves the products $\mathbf{d}_i^{(\tilde{j}_i)} \times \mathbf{c}_i^{(\tilde{j}_i)}$ and $\mathbf{d}_i^{(\tilde{j}_i)} \times \mathbf{c}_{k,i}^{(\text{rep})}$ for all $k \in [K], \tilde{j}_i \in [\tilde{J}_i]$. Moreover, the computational basis change allows us to target only the vectors $(\mathbf{d}_i^{(\tilde{j}_i)})_{i \in [H]}$ while letting $\mathbf{d}_{\ell,i}^{(\text{rep})}$ for $\ell \in [L], i \in [H]$ unchanged.

Upon reaching $\mathbb{G}_3$, we are ready to approach the centerpiece of our proof. A formal basis change maintains perfectly identical views for the adversary in two games, resulting in a 0 difference in winning advantages under efficient simulation. We combine such formal basis changes with a *complexity leveraging* argument. In general, these kinds of arguments degrade the probability of a successful simulation by an exponential factor. In our case, however, an exponential multiple of 0 is still 0. This implies that, as long as we restrict ourselves to formal bases changes that do not rely on any computational assumption, the simulator can initially guess all queries submitted by the adversary throughout the game, thus considering the selective game.

Formal basis changes highlight the information-theoretic properties of DPVS. However, they are often much harder to use than computational changes. The reason is that a formal basis change affects all vectors, including all repetitions, in the same manner. In contrast to computational changes, it is not possible to apply changes only to some vectors. Intuitively, this is why in $\mathbb{G}_2$ and $\mathbb{G}_3$ we had to move all repetitions $\mathbf{d}_i^{(\tilde{j}_i)}$ into separate coordinates to prepare for the formal basis changes.

We now explain the sequence of games on which the complexity leveraging is applied. We want to perform some sort of swapping between coordinates $[2N \cdot \tilde{j}_i + 4, N + 2N \cdot \tilde{j}_i + 3]$ and $[N + 2N \cdot \tilde{j}_i + 4, 2N + 2N \cdot \tilde{j}_i + 3]$ of $\mathbf{d}_i^{(\tilde{j}_i)}$ and reach $\mathbb{G}_6$ whose vectors are:

$$
\begin{align*}
\mathbf{d}_{\ell, i}^{(\text{rep})} &= \left( \begin{array}{c} \mathbf{y}_{\ell, i}^{(\text{rep})} \\ \mathbf{y}_{\ell, i}^{(\text{rep})'} \end{array} \right) &
\begin{array}{c}
r_{\ell} \\ 0
\end{array} &
\begin{array}{c}
0 \\ \rho_{\ell, i}^{(\text{rep})}
\end{array} &
\cdots &
\begin{array}{c}
0 \\ \mathbf{0} \end{array} &
\begin{array}{c}
0 \\ \mathbf{y}_{i}^{(0, \tilde{j}_{i})} \end{array} &
\cdots &
\begin{array}{c}
0 \\ r' \end{array} &
\mathbf{B}_{i} \\
\mathbf{d}_{i}^{(\tilde{j}_{i})} &= \left( \begin{array}{c} \mathbf{0} \\ \mathbf{0} \end{array} \right) &
\begin{array}{c}
r \\ 0
\end{array} &
\begin{array}{c}
0 \\ \rho_{i}^{(\tilde{j}_{i})} \end{array} &
\cdots &
\begin{array}{c}
0 \\ \mathbf{0} \end{array} &
\begin{array}{c}
r' \\ \tilde{\tau}_{i} \end{array} &
\cdots &
\begin{array}{c}
r' \\ \tilde{\tau}_{k,i} \end{array} &
\mathbf{B}_{i}^{*} \\
\mathbf{c}_{i}^{(\tilde{j}_{i})} &= \left( \begin{array}{c} \mathbf{x}_{i}^{(1, \tilde{j}_{i})} \\ \mathbf{x}_{i}^{(0, \tilde{j}_{i})} \end{array} \right) &
\begin{array}{c}
\sigma_{i} \\ \pi_{i}^{(\tilde{j}_{i})} \end{array} &
\begin{array}{c}
0 \\ 0 \end{array} &
\cdots &
\begin{array}{c}
0 \\ \mathbf{x}_{i}^{(1, \tilde{j}_{i})} \end{array} &
\begin{array}{c}
\mathbf{x}_{i}^{(0, \tilde{j}_{i})} \\ \pi_{k,i}^{(\text{rep})} \end{array} &
\cdots &
\begin{array}{c}
0 \\ \tilde{\tau}_{k,i} \end{array} &
\mathbf{B}_{i}^{*} \\
\mathbf{c}_{k,i}^{(\text{rep})} &= \left( \begin{array}{c} \mathbf{x}_{k,i}^{(\text{rep})} \\ \mathbf{x}_{k,i}^{(\text{rep})} \end{array} \right) &
\begin{array}{c}
\sigma_{k,i} \\ \pi_{k,i}^{(\text{rep})} \end{array} &
\begin{array}{c}
0 \\ 0 \end{array} &
\cdots &
\begin{array}{c}
0 \\ \mathbf{x}_{k,i}^{(\text{rep})} \end{array} &
\begin{array}{c}
\mathbf{x}_{k,i}^{(\text{rep})} \\ \tilde{\tau}'_{k,i} \end{array} &
\cdots &
\begin{array}{c}
0 \\ \tilde{\tau}'_{k,i} \end{array} &
\mathbf{B}_{i}^{*}
\end{align*}
$$

The complexity leveraging will be applied to the selective versions $\mathbb{G}_3^* \to \mathbb{G}_4^* \to \mathbb{G}_5^* \to \mathbb{G}_6^*$ and only formal basis changes will be used in between. In these selective versions the simulator guesses the values $(\mathbf{y}_i^{(1, \tilde{j}_i)}, \mathbf{y}_i^{(0, \tilde{j}_i)}, \mathbf{x}_i^{(1, \tilde{j}_i)}, \mathbf{x}_i^{(0, \tilde{j}_i)})_{\tilde{j}_i \in [\tilde{J}_i], \tilde{j}_i \in [\tilde{J}_i]}$ and the hybrids are conditioned on a “good” event that these guesses are correct. The “good” event happens with fixed probability. This leads to an identical adversary’s view:

$$
\Pr[\mathbb{G}_3^* = 1] = \Pr[\mathbb{G}_4^* = 1] = \Pr[\mathbb{G}_5^* = 1] = \Pr[\mathbb{G}_6^* = 1]. \quad (9)
$$

We briefly highlight the selective games’ ideas below:
• In $G_3^* \to G_4^*$ a formal basis change is applied to do a quotient by $\mathbf{y}_i^{(1, \tilde{j}_i)}[z]$ for $z \in [N]$ over all $\tilde{J}$ blocks $[2N \cdot \tilde{j}_i + 4, N + 2N \cdot \tilde{j}_i + 3], [N + 2N \cdot \tilde{j}_i + 4, 2N + 2N \cdot \tilde{j}_i + 3]$, where $\tilde{j}_i$ runs in $[\tilde{J}_i]$, of c-vectors. We refer to matrices (14) in the proof for more details. We note that thanks to (8), for $\tilde{j}_i \neq \tilde{j}_i' \in [\tilde{J}]$, this change makes $\mathbf{d}_i^{(\tilde{j}_i)}[2N \cdot \tilde{j}_i + 4, N + 2N \cdot \tilde{j}_i + 3] = \mathbf{1}$ while $\mathbf{d}_i^{(\tilde{j}_i)}[2N \cdot \tilde{j}_i' + 4, N + 2N \cdot \tilde{j}_i' + 3] = \mathbf{0}$ for $\tilde{j}_i \neq \tilde{j}_i'$.

• In $G_4^* \to G_5^*$, we define a formal basis change that uses the fixed randomness $r' \in \mathbb{Z}_q^*$ in $\mathbf{d}_i^{(\tilde{j}_i)}[2N + 2N \cdot \tilde{j}_i + 4]$ (introduced from $G_1$) to switch 1 to 0 at coordinates $[2N \cdot \tilde{j}_i + 4, N + 2N \cdot \tilde{j}_i + 4]$ while marking 1 at coordinates $[N + 2N \cdot \tilde{j}_i + 4, 2N + 2N \cdot \tilde{j}_i + 3]$ of $\mathbf{d}_i^{(\tilde{j}_i)}$, for all $\tilde{j}_i$. The specific matrix definition is given in equation (15). Thanks to the observation at the end of $G_3^*$, for each repetition $\mathbf{d}_i^{(\tilde{j}_i)}$ only the $\tilde{j}_i$-th blocks $[2N \cdot \tilde{j}_i + 4, N + 2N \cdot \tilde{j}_i + 3], [N + 2N \cdot \tilde{j}_i + 4, 2N + 2N \cdot \tilde{j}_i + 3]$ is affected, while other blocks stay 0. We note that unlike $\mathbf{d}_i^{(\tilde{j}_i)}$, the vectors $\mathbf{d}_{\ell, i}^{(\text{rep})}$ stay invariant because $\mathbf{d}_{\ell, i}^{(\text{rep})}[2N + 2N \cdot \tilde{J} + 4] = 0$.

Dually, because of the formal duplication in $G_2$ to all $\tilde{J} \ge \tilde{J}_i$ blocks, all c-vectors will be altered such that the accumulated differences

$$ \sum_{\substack{\tilde{j}_i \in [\tilde{J}_i] \\ z \in [N]}} \mathbf{c}_i^{(\tilde{j}_i)}[2N \cdot \tilde{j}_i + 3 + z] - \mathbf{c}_i^{(\tilde{j}_i)}[N + 2N \cdot \tilde{j}_i + 3 + z] = \frac{1}{r'} \sum_{\tilde{j}_i \in [\tilde{J}_i]} \langle \mathbf{y}_i^{(1, \tilde{j}_i)}, \mathbf{x}_i^{(1, \tilde{j}_i)} \rangle - \langle \mathbf{y}_i^{(0, \tilde{j}_i)}, \mathbf{x}_i^{(0, \tilde{j}_i)} \rangle $$

will be added to $\tau_i$ in $\mathbf{c}_i^{(\tilde{j}_i)}[2N + 2N \cdot \tilde{J} + 4]$ (see (20) in the proof). For $\mathbf{c}_{k, i}^{(\text{rep})}$, similarly, we have the accumulated differences added to $\tau'_{k, i}$ is

$$ \sum_{\substack{\tilde{j}_i \in [\tilde{J}_i] \\ z \in [N]}} \mathbf{c}_{k, i}^{(\text{rep})}[2N \cdot \tilde{j}_i + 3 + z] - \mathbf{c}_{k, i}^{(\text{rep})}[N + 2N \cdot \tilde{j}_i + 3 + z] = \frac{1}{r'} \sum_{\tilde{j}_i \in [\tilde{J}_i]} \langle \mathbf{y}_i^{(1, \tilde{j}_i)} - \mathbf{y}_i^{(0, \tilde{j}_i)}, \mathbf{x}_{k, i}^{(\text{rep})} \rangle . $$

To show that this compensation for the accumulated differences in the $\tau_i$ and $\tau'_{k, i}$ cannot be noticed by the adversary, we exploit the conditions on the oracle queries in the statement of the lemma. Specifically, the condition $\sum_{i=1}^H \langle \mathbf{y}_i^{(1, \tilde{j}_i)}, \mathbf{x}_i^{(1, \tilde{j}_i)} \rangle - \langle \mathbf{y}_i^{(0, \tilde{j}_i)}, \mathbf{x}_i^{(0, \tilde{j}_i)} \rangle = 0$ implies that $\frac{1}{r'}(\langle \mathbf{y}_i^{(1, \tilde{j}_i)}, \mathbf{x}_i^{(1, \tilde{j}_i)} \rangle - \langle \mathbf{y}_i^{(0, \tilde{j}_i)}, \mathbf{x}_i^{(0, \tilde{j}_i)} \rangle)$ is constant for all $\tilde{j}_i \in [\tilde{J}], j_i \in [J_i]$ (see (13) for a formal argument) and $\sum_{i \in [H]} \frac{1}{r'}(\langle \mathbf{y}_i^{(1, \tilde{j}_i)}, \mathbf{x}_i^{(1, \tilde{j}_i)} \rangle - \langle \mathbf{y}_i^{(0, \tilde{j}_i)}, \mathbf{x}_i^{(0, \tilde{j}_i)} \rangle) = 0$. From this observation, it follows that after adding the value $1/r' \cdot \langle \mathbf{y}_i^{(1, \tilde{j}_i)}, \mathbf{x}_i^{(1, \tilde{j}_i)} \rangle - \langle \mathbf{y}_i^{(0, \tilde{j}_i)}, \mathbf{x}_i^{(0, \tilde{j}_i)} \rangle$ to $\tau_i$ for all $i \in [H]$, $(\tau_i)_{i \in [H]}$ is still a secret sharing of 0. The same reasoning applies for $1/r' \cdot \langle \mathbf{y}_i^{(1, \tilde{j}_i)} - \mathbf{y}_i^{(0, \tilde{j}_i)}, \mathbf{x}_{k, i}^{(\text{rep})} \rangle$ which is added to the secret sharing $(\tau'_{k, i})_{i=1}^H$ in $(\mathbf{c}_{k, i}^{(\text{rep})}[2N + 2N \cdot \tilde{J} + 4])_{i=1}^H$.

• In $G_5^* \to G_6^*$ we redo the quotient, still being in the selective variants conditioned on the “good” event.

• Finally, we also emphasize that all above DPVS formal basis changes do not depend on the exponentially large number of combinations $(\mathbf{d}_i^{(\tilde{j}_i)})_{i \in [H]}$, up to repetitions $\tilde{j}_i \in [\tilde{J}_i]$. We use the fact that each $i \in [H]$ has its vectors written in an independent pair of bases $(\mathbf{B}_i, \mathbf{B}_i^*)$, along with the crucial property (8) that allows treating each $\tilde{j}_i$-th repetition in an isolated block of the $\mathbf{d}_i^{(\tilde{j}_i)}$ vector, all $(\mathbf{d}_i^{(\tilde{j}_i)})^{\tilde{j}_i \in [\tilde{J}_i]}$ at the same time. To summarize, the specific information theoretic property of DPVS formal basis changes makes sure that all vectors in $(\mathbf{B}_i, \mathbf{B}_i^*)$ will be modified according to the basis matrices. The matrices (14) and (15) change consistently the $\tilde{j}_i$-th block in all pairs $(\mathbf{d}_i^{(\tilde{j}_i)}, \mathbf{c}_i^{(\tilde{j}_i)})$. For different $\tilde{j}_i \neq \tilde{j}_i'$ property (8) makes sure those matrices' change are trivial, i.e. 0 stays 0, in $\tilde{j}_i$-th block of $\mathbf{d}_i^{(\tilde{j}_i)}$. Furthermore, even though
all $\tilde{J}_i \le \tilde{J}$ blocks of $c_i^{(j_i)}$ are changed consistently by the matrices, in terms of the contents of all $d_i^{(\tilde{j}_i)}$, different $c_i^{(j_i)}$ from different $i$ cannot be combined because they are in different bases. The only constraint is a fixed polynomially large upper bound $\tilde{J} \ge \max_{i \in [n], \text{tag-f} \in \text{Tag}} \tilde{J}_{i, \text{tag-f}}$ so that the dimensions are well defined.

The probability calculation (see footnote 9) of the complexity leveraging makes use of the fact that the “good” event happens with a fixed probability in conjunction with property (9), leading to $\Pr[G_3 = 1] = \Pr[G_4 = 1] = \Pr[G_5 = 1] = \Pr[G_6 = 1]$. Coming out of the complexity-leveraging argument, the very last step consists in swapping $\mathbf{x}_i$ from coordinates $[N + 2N \cdot \tilde{j}_i + 3, 2N + 2N \cdot \tilde{j}_i + 3]$ back to $[1, N]$ (see $G_6 \to G_7$) and some cleaning in order to make the vectors follow $D_1$ (see $G_7 \to G_8$).

## 4.2 Basic Construction

This section presents our basic adaptively secure FH-DMCFE construction $\mathcal{E} = (\text{Setup}, \text{DKeyGen}, \text{Enc}, \text{Dec})$ for the function class $\mathcal{F}^{\text{ip}}$, where each client encrypts a vector of length $N \in \mathbb{N}$. We obtain the adaptive scheme by giving a concrete instantiation for the FH-IPFE scheme iFE used in our selectively secure FH-DMCFE from Figure 1. As a reminder, we refer to the beginning of Section 3.3 for the notations, including those of implicit representation for group elements and the bilinear group setting. The notations of DPVS and the writing of their vectors with respect to the dual bases are recalled in Section 3.2.

Our FH-IPFE instantiation is extremely simple. The master secret key is a pair of random dual bases $(\mathbf{B}, \mathbf{B}^*)$. To generate a key for some vector $\mathbf{y} \in \mathbb{Z}_q^N$, we sample $\pi \leftarrow \mathcal{S} \mathbb{Z}_q$ and return $\mathbf{d} = (\mathbf{y}, \pi, 0, 0)_B^*$ as decryption key. Similarly, to encrypt a vector $\mathbf{x} \in \mathbb{Z}_q^N$, we sample $\rho \leftarrow \mathcal{S} \mathbb{Z}_q$ and output $\mathbf{c} = (\mathbf{x}, 0, \pi, 0)_B$ as ciphertext. Decryption computes $\llbracket \mathbf{z} \rrbracket_t = \mathbf{c} \times \mathbf{d}$, then finds and outputs the discrete log $z$. When plugging this FH-IPFE into Figure 1, we obtain our adaptively secure scheme whose details are given in Figure 3.

**Correctness.** The correctness property is demonstrated as follows:

$$ \llbracket \text{out} \rrbracket_t = \sum_{i=1}^{n} \mathbf{c}_i \times \mathbf{d}_i = \sum_{i=1}^{n} \llbracket \langle \mathbf{x}_i, \mathbf{y}_i \rangle + \mu\omega \cdot \tilde{t}_i \rrbracket_t \\ = \left[ \sum_{i=1}^{n} \langle \mathbf{x}_i, \mathbf{y}_i \rangle + \mu\omega \cdot \sum_{i=1}^{n} \tilde{t}_i \right]_t = \left[ \sum_{i=1}^{n} \langle \mathbf{x}_i, \mathbf{y}_i \rangle \right]_t, $$

and we are using the fact that $\sum_{i=1}^n \tilde{t}_i = 0$.

**Security.** Theorem 1 states that the scheme given in Fig. 3 is function-hiding, one-challenge secure against complete queries under static corruption. An unbounded number of ciphertext repetitions is allowed, while the number of key repetitions is fixed as a parameter of the scheme. In Section 5, we argue that most restrictions on the security model can be removed by applying a sequence of generic lemmas.

**Theorem 1.** The DMCFE scheme $\mathcal{E} = (\text{Setup}, \text{DKeyGen}, \text{Enc}, \text{Dec})$ in Fig. 3 for the function class $\mathcal{F}^{\text{ip}}$ is one-challenge, function-hiding secure against complete queries under static corruption in the ROM, if the SXDH assumption holds for $(\mathbb{G}_1, \mathbb{G}_2)$.

More specifically, we let $q_e$ and $q_k$ denote the maximum number of distinct tags queried to $\text{OEnc}$ and $\text{OKeyGen}$, respectively. Furthermore, for $i \in [n]$ and tag, tag-f $\in \text{Tag}$, we define $\tilde{J}_{i, \text{tag-f}}$ to be the numbers of queries of the form $\text{OKeyGen}(i, \text{tag-f}, \star, \star)$. We require that $\max_{i \in [n], \text{tag-f} \in \text{Tag}} \tilde{J}_{i, \text{tag-f}} \le \tilde{J}$, where $\tilde{J}$ is specified by the DMCFE scheme at Setup time. Then, for any ppt adversary $\mathcal{A}$ against $\mathcal{E}$, we have the following bound:

$$ \mathbf{Adv}_{\mathcal{E}, \mathcal{F}^{\text{ip}}, \mathcal{A}}^{\text{chal-pos-stat-fh}}(1^{\lambda}) \le ((q_k + 1) \cdot (4n\tilde{J}N + 4) + 4N + q_e + 1) \cdot \mathbf{Adv}_{\mathbb{G}_1, \mathbb{G}_2}^{\text{SXDH}}(1^{\lambda}) $$
**Setup(1^λ, 1^n)**: Sample matrices $(B_i, B_i^*) \leftarrow \text{DPVSGen}(\mathbb{G}, 1^{2N \cdot (\tilde{J}+1)+4})$, for $i \in [n]$, of dimensions $2N \cdot (\tilde{J} + 1) + 4$ that specify dual orthogonal bases $(\mathbf{B}_i, \mathbf{B}_i^*)^a$. Sample $(\tilde{t}_i)_i \stackrel{\$}{\leftarrow} \mathbb{Z}_q^n$ conditioned on $\sum_{i=1}^n \tilde{t}_i = 0$. Output the public parameters $\mathbf{p}\mathbf{p} := \mathbb{G}$, secret keys $\mathbf{s}\mathbf{k}_i$ and the encryption keys $\mathbf{e}\mathbf{k}_i$ for all $i \in [n]$ as follows:

$$ \mathbf{s}\mathbf{k}_i := (\mathbf{b}_{i,1}^*, \dots, \mathbf{b}_{i,N}^*, \mathbf{B}_{i,N+1}^*, \mathbf{b}_{i,N+2}^*), \quad \mathbf{e}\mathbf{k}_i := (\tilde{t}_i, (\mathbf{b}_{i,1}^*, \dots, \mathbf{b}_{i,N}^*, \mathbf{B}_{i,N+1}^*, \mathbf{b}_{i,N+3}^*)) $$

**DKeyGen(s\mathbf{k}_i, tag-f, y_i)**: Parse $\mathbf{s}\mathbf{k}_i = (\mathbf{b}_{i,1}^*, \dots, \mathbf{b}_{i,N}^*, \mathbf{B}_{i,N+1}^*, \mathbf{b}_{i,N+2}^*)$, compute $H_2(\text{tag-f}) \to [\mu]_2$ and sample $\pi_i \stackrel{\$}{\leftarrow} \mathbb{Z}_q$. Then output$^b$

$$ \mathbf{d}_i = \sum_{k=1}^{N} \mathbf{y}_i[k] \mathbf{b}_{i,k}^* + [\mu]_2 \cdot \mathbf{B}_{i,N+1}^* + \pi_i \mathbf{b}_{i,N+2}^* = (\mathbf{y}_i, \mu, \pi_i, 0, 0^{N+2N \cdot \tilde{J}+1})_{\mathbf{B}_i^*} $$

**Enc(e\mathbf{k}_i, tag, x_i)**: Parse $\mathbf{e}\mathbf{k}_i = (\tilde{t}_i, (\mathbf{b}_{i,1}^*, \dots, \mathbf{b}_{i,N}^*, \mathbf{B}_{i,N+1}^*, \mathbf{b}_{i,N+3}^*))$, compute $H_1(\text{tag}) \to [\omega]_1$ and sample a random scalar $\rho_i \stackrel{\$}{\leftarrow} \mathbb{Z}_q$. Then output$^c$

$$ \mathbf{c}_i = \sum_{k=1}^{N} \mathbf{x}_i[k] \mathbf{b}_{i,k} + \tilde{t}_i [\omega]_1 \cdot \mathbf{B}_{i,N+1} + \rho_i \mathbf{b}_{i,N+3} = (\mathbf{x}_i, \tilde{t}_i \omega, 0, \rho_i, 0^{N+2N \cdot \tilde{J}+1})_{\mathbf{B}_i} $$

**Dec(d, c)**: Parse $\mathbf{d} := (\mathbf{d}_i)_{i \in [n]}$ and $\mathbf{c} := (\mathbf{c}_i)_i$. Compute $[\text{out}]_t = \sum_{i=1}^n \mathbf{c}_i \times \mathbf{d}_i$, then find and output the discrete log out.

**Figure 3:** FH-DMCFE scheme $\mathcal{E} = (\text{Setup}, \text{DKeyGen}, \text{Enc}, \text{Dec})$ for inner products. We work in the prime-order bilinear group setting $\mathbb{G} = (\mathbb{G}_1, \mathbb{G}_2, \mathbb{G}_t, g_1, g_2, g_t, \mathbf{e}, \mathbf{q})$ and use two full-domain hash functions $H_1: \text{Tag} \to \mathbb{G}_1$ and $H_2: \text{Tag} \to \mathbb{G}_2$. Let $\tilde{J} = \text{poly}(\lambda)$.

The proof of Theorem 1 follows exactly the proof sketch of the selective scheme in Section 2. As explained in the paragraph **Problems for Adaptive Security**, the main difficulty towards adaptive security lies in enabling the steps (3) to (5) in a sequence of hybrids without knowing $\Delta_i^{(b)}$ and $\Delta_{\ell,i}^{(b)}$ in advance. In the DPVS setting, the transition from one hybrid to the next corresponds exactly to an application of Lemma 1. Even though $\tilde{J}$ is fixed, it can be polynomially large leading to an exponentially number of combinations of key repetitions, this is also handled by Lemma 1. We refer to the high level in section 4.1. The full proof of theorem 1 can be found in appendix A.3.

# 5 Upgrading Security

In this section, we give a sequence of generic lemmas that can be used to strengthen the security model of our basic FH-DMCFE construction from Section 4.2. Specifically, we show how to remove the *complete-query* constraint and the restriction to *one-challenge* security. In this way, we obtain an FH-DMCFE for inner products whose only restrictions on the security model are *static corruptions* and a *polynomially bounded number of repetitions for decryption keys*.

**Security against Incomplete Queries.** To remove the complete-queries constraint, previous works [CDSG$^+$20, AGT21b] make use of a technique called *all-or-nothing encap-**

<footnote>$^a$For each $i \in [n]$, we denote $j$-th row of $\mathbf{B}_i$ (resp. $\mathbf{B}_i^*$) by $\mathbf{b}_{i,j}$ (resp. $\mathbf{b}_{i,j}^*$). Similarly, $B_{i,k}$ (respectively $B_{i,k}^*$) denotes the $k$-th row of the basis changing matrix $\mathbf{B}_i$ (respectively $B_i^*$).</footnote>

<footnote>$^b$Throughout the computation of $\mathbf{d}_i$, only the hash value $[\mu]_2 \in \mathbb{G}_2$ is used, never $\mu$ in the clear.</footnote>

<footnote>$^c$Throughout the computation of $\mathbf{c}_i$, only the hash value $[\omega]_1 \in \mathbb{G}_1$ is used, never $\omega$ in the clear.</footnote>
sulation (AoNE). Roughly, AoNE allows all parties of a group to encapsulate individual messages, that can all be extracted by everyone if and only if all parties of the group have sent their contribution. Otherwise, no message is revealed. In the constructions of [CDSG+20, AGT21b], such an AoNE layer is added on top of both ciphertexts and keys. Intuitively, this approach allows the following reasoning: if an adversary makes encryption queries for all (honest) clients under some tag tag (i.e. the global query is “complete”), then the AoNE scheme allows to obtain all ciphertexts, and we can rely on the security of the DMCFE scheme that is secure against complete challenges. On the other hand, if the adversary queries only some but not all honest clients (i.e. the global query is “incomplete”), then the security of the AoNE scheme guarantees that the adversary does not learn anything about the encapsulated messages. While this construction is well known, previous constructions prove only selective security, even if the employed AoNE scheme is adaptively secure. Therefore, we think it is important to show that this AoNE layer indeed preserves adaptive security if the underlying scheme, which is only secure against complete queries, has this property.

More specifically, the notion of AoNE is a particular functionality of DDFE introduced by Chotard et al. [CDSG+20]. In [AGT21b], AoNE also serves as a building block for their FH-DDFE scheme, and it is pointed out that function-hiding and standard security are the same for AoNE, as there is no concept of keys. Since we are focusing on the less general notion DMCFE, we define AoNE in a less general context as a functionality for DMCFE.

**Definition 7 (All-or-Nothing Encapsulation).** For $n, \lambda \in \mathbb{N}$, let $\text{Tag}_\lambda = \mathcal{R}_\lambda = \{0, 1\}^{\text{poly}(\lambda)}$, $\mathcal{K}_\lambda = \emptyset$, $M_{n,\lambda,\text{pub}} = [n] \times \text{Tag}_\lambda$ and $M_{\lambda,\text{pri}} = \{0, 1\}^L$ for a polynomial $L = L(\lambda): \mathbb{N} \to \mathbb{N}$. The all-or-nothing encapsulation functionality $f^{\text{aone}} = \{f_{n,\lambda}^{\text{aone}}: \{[n]\} \times (\{[n]\} \times M_\lambda)^n \to \mathcal{R}_\lambda\}_{n,\lambda \in \mathbb{N}}$ is defined via

$$f_{n,\lambda}^{\text{aone}}([n], (i, m_i)_{i \in [n]}) = \begin{cases} (x_i)_{i \in [n]} & \text{if condition (*) holds} \\ \perp & \text{otherwise} \end{cases}$$

for all $n, \lambda \in \mathbb{N}$, where $\{[n]\}$ is a singleton consisting of $[n]$ as its only member, and condition (*) holds if there exists tag $\in \text{Tag}_\lambda$ such that for each $i \in [n]$, $m_i$ is of the form $(m_{i,\text{pri}} := x_i \in \{0, 1\}^L, m_{i,\text{pub}} := ([n], \text{tag}) \in M_{n,\lambda,\text{pub}})$.

This means in particular that DKeyGen is unnecessary and Dec works without taking secret keys as input. The DDFE constructions from [CDSG+20] yield two constructions of DMCFE for the function class AoNE as per Definition 7. A first generic construction [CDSG+20, Section 4] from identity-based encryption is secure in the standard model. Another concrete construction [CDSG+20, Section 5] from bilinear maps under the Decisional Bilinear Diffie-Hellman (DBDH) assumption is proven secure in the ROM.

We present our result in form of a generic conversion that turns any one-challenge DMCFE scheme secure against complete queries into one that is also secure against incomplete queries.

**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}}, f_{\mathcal{aone}}, \mathcal{B}_2}^{\text{1chal-xxx-wfh}}(1^{\lambda}),$$

where $\text{xxx} \subseteq \{\text{stat}, \text{sel}\}$.
Our conversion simply adds a layer of DMCFE for AoNE on top of both ciphertexts and keys. On an intuitive level, our simulator initially guesses whether or not the oracle queries for the challenge tag tag-f* (or tag*) will be complete. If the guess was “complete” and this guess turns out to be correct at the end of the game, then the simulator attacks the underlying DMCFE scheme that is assumed to be secure against complete queries. If the guess was “incomplete” and the guess is correct, then the simulator attacks the security of the AoNE scheme. If the guess was incorrect (which happens with probability 1/2), then the simulator aborts with a random bit. In this way, we can upper bound the advantage of a distinguisher between two successive hybrids in terms of the advantages that efficient adversaries can achieve against the underlying AoNE and DMCFE schemes. We point out that this argument crucially relies on the one-challenge setting. Due to the guess on the (in)completeness of the oracle queries, we lose a factor 1/2 in the security proof. Thus, a hybrid argument over a polynomial number of incomplete queries would incur an exponential security loss. Therefore, it is important to add security against incomplete queries in the one-challenge model.

Details about the conversion as well as the proof are given in appendix B.1. We mention that a concurrent work by Shi and Vanjani [SV23] presents a similar conversion in the MCFE setting.

**Security against Multiple Challenges.** It remains to discuss how a one-challenge FH-DMCFE scheme for inner products can be made resistant against multiple challenge queries. First, observe that the equivalence of one-challenge and multi-challenge security in the standard setting (without function privacy) is trivial. Indeed, the proof can be done by a sequence of hybrids over the different tags queried to the encryption oracle. This approach, however, does not directly generalize to the function-hiding setting. The problem is that now both encryption and key-generation queries depend on the challenge bit $b \in \{0, 1\}$. Since ciphertexts and keys can be arbitrarily combined in general, such a sequence of hybrids leads to a situation where an adversary is able to mix ciphertexts that encrypt the left message with keys generated for the right function or vice versa. However, the function-hiding admissibility does not provide any security guarantees in the case of such a mixed decryption. Therefore, we cannot change ciphertexts and keys one by one anymore. We solve this problem by first proving security against multiple challenges in the weakly function-hiding setting. This model provides us exactly with the necessary guarantee for mixed decryptions, which allows a hybrid argument over all function and message tags to subsequently swap keys and ciphertexts. Afterwards, we apply another standard transformation that turns weakly function-hiding DMCFE schemes for inner products back into full-fledged function-hiding DMCFE (see Lemma 4). Previous works [LV16, ACF$^{+18}$] presented that transformation for single-input and multi-input FE schemes.

We state the formal lemmas below. The proofs are standard and the latter is very similar to [LV16, ACF$^{+18}$], but we give them in appendix B.2 and B.3 for completeness.

**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{chal-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 xxx $\subseteq \{\text{stat}, \text{sel}, \text{pos}\}$.

**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 A, there exists a ppt algorithm B such that

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

where xxx ⊆ {stat, sel, 1chal, pos}.

**Concrete Instantiation.** Given Lemmas 2, 3, and 4, we now generically transform our FH-DMCFE from Section 4.2 to upgrade its security. Specifically, we first apply Lemma 2 and follow the generic IBE-based AoNE from [CDSG+20, Section 4]. We use any adaptively secure pairing-based IBE [CLL+13, JR17] under SXDH<fnref n="7" /> to obtain generically a DMCFE for AoNE, in order to allow *incomplete queries*. We then use Lemma 3 to allow *multiple challenges*, while downgrading from function-hiding to weak function-hiding. Finally, we apply Lemma 4 to re-establish full-fledged *function-hiding*. The final scheme is summarized in the below corollary, with newly accomplished properties being *underlined*.

**Corollary 1.** There exists an FH-DMCFE scheme for the function class $\mathcal{F}^{\text{ip}}$ that is *adaptively function-hiding* secure against static corruption, while allowing unbounded repetitions for ciphertext queries and a fixed polynomially large number of repetitions for key-generation queries, under the SXDH assumption in the ROM.

## Acknowledgements

This work was supported in part by the French ANR Project ANR-19-CE39-0011 PRESTO and the France 2030 ANR Project ANR-22-PECY-003 SecureCompute.

## References

[ABDP15] Michel Abdalla, Florian Bourse, Angelo De Caro, and David Pointcheval. Simple functional encryption schemes for inner products. In Jonathan Katz, editor, *PKC 2015*, volume 9020 of LNCS, pages 733–751. Springer, Heidelberg, March / April 2015. doi:10.1007/978-3-662-46447-2_33.

[ABG19] Michel Abdalla, Fabrice Benhamouda, and Romain Gay. From single-input to multi-client inner-product functional encryption. In Steven D. Galbraith and Shiho Moriai, editors, *ASIACRYPT 2019, Part III*, volume 11923 of LNCS, pages 552–582. Springer, Heidelberg, December 2019. doi:10.1007/978-3-030-34618-8_19.

[ABKW19] Michel Abdalla, Fabrice Benhamouda, Markulf Kohlweiss, and Hendrik Waldner. Decentralizing inner-product functional encryption. In Dongdai Lin and Kazue Sako, editors, *PKC 2019, Part II*, volume 11443 of LNCS, pages 128–157. Springer, Heidelberg, April 2019. doi:10.1007/978-3-030-17259-6_5.

[ACF+18] Michel Abdalla, Dario Catalano, Dario Fiore, Romain Gay, and Bogdan Ursu. Multi-input functional encryption for inner products: Function-hiding realizations and constructions without pairings. In Hovav Shacham and Alexandra Boldyreva, editors, *CRYPTO 2018, Part I*, volume 10991 of LNCS, pages 597–627. Springer, Heidelberg, August 2018. doi:10.1007/978-3-319-96884-1_20.

<footnote n="7">⁷The seminal adaptively secure group-based (H)IBE is [Wat09] but it relies on both DDH and D-Lin.</footnote>
[ACGU20] Michel Abdalla, Dario Catalano, Romain Gay, and Bogdan Ursu. Inner-product functional encryption with fine-grained access control. In Shiho Moriai and Huaxiong Wang, editors, ASIACRYPT 2020, Part III, volume 12493 of LNCS, pages 467–497. Springer, Heidelberg, December 2020. doi: 10.1007/978-3-030-64840-4_16.

[AGT21a] Shweta Agrawal, Rishab Goyal, and Junichi Tomida. Multi-input quadratic functional encryption from pairings. In Tal Malkin and Chris Peikert, editors, CRYPTO 2021, Part IV, volume 12828 of LNCS, pages 208–238, Virtual Event, August 2021. Springer, Heidelberg. doi:10.1007/978-3-030-84259-8_8.

[AGT21b] Shweta Agrawal, Rishab Goyal, and Junichi Tomida. Multi-party functional encryption. In Kobbi Nissim and Brent Waters, editors, TCC 2021, Part II, volume 13043 of LNCS, pages 224–255. Springer, Heidelberg, November 2021. doi:10.1007/978-3-030-90453-1_8.

[AGT22] Shweta Agrawal, Rishab Goyal, and Junichi Tomida. Multi-input quadratic functional encryption: Stronger security, broader functionality. In Eike Kiltz and Vinod Vaikuntanathan, editors, TCC 2022, Part I, volume 13747 of LNCS, pages 711–740. Springer, Heidelberg, November 2022. doi:10.1007/978-3-031-22318-1_25.

[AJ15] Prabhanjan Ananth and Abhishek Jain. Indistinguishability obfuscation from compact functional encryption. In Rosario Gennaro and Matthew J. B. Robshaw, editors, CRYPTO 2015, Part I, volume 9215 of LNCS, pages 308–326. Springer, Heidelberg, August 2015. doi:10.1007/978-3-662-47989-6_15.

[ALdP11] Nuttapong Attrapadung, Benoît Libert, and Elie de Panafieu. Expressive key-policy attribute-based encryption with constant-size ciphertexts. In Dario Catalano, Nelly Fazio, Rosario Gennaro, and Antonio Nicolosi, editors, PKC 2011, volume 6571 of LNCS, pages 90–108. Springer, Heidelberg, March 2011. doi:10.1007/978-3-642-19379-8_6.

[ALS16] Shweta Agrawal, Benoît Libert, and Damien Stehlé. Fully secure functional encryption for inner products, from standard assumptions. In Matthew Robshaw and Jonathan Katz, editors, CRYPTO 2016, Part III, volume 9816 of LNCS, pages 333–362. Springer, Heidelberg, August 2016. doi: 10.1007/978-3-662-53015-3_12.

[AS17] Prabhanjan Ananth and Amit Sahai. Projective arithmetic functional encryption and indistinguishability obfuscation from degree-5 multilinear maps. In Jean-Sébastien Coron and Jesper Buus Nielsen, editors, EURO-CRYPT 2017, Part I, volume 10210 of LNCS, pages 152–181. Springer, Heidelberg, April / May 2017. doi:10.1007/978-3-319-56620-7_6.

[ATY23] Shweta Agrawal, Junichi Tomida, and Anshu Yadav. Attribute-based multi-input FE (and more) for attribute-weighted sums. In Helena Handschuh and Anna Lysyanskaya, editors, CRYPTO 2023, Part IV, volume 14084 of LNCS, pages 464–497. Springer, Heidelberg, August 2023. doi:10.1007/978-3-031-38551-3_15.

[BBL17] Fabrice Benhamouda, Florian Bourse, and Helger Lipmaa. CCA-secure inner-product functional encryption from projective hash functions. In Serge Fehr, editor, PKC 2017, Part II, volume 10175 of LNCS, pages 36–66. Springer, Heidelberg, March 2017. doi:10.1007/978-3-662-54388-7_2.
[BCFG17] Carmen Elisabetta Zaira Baltico, Dario Catalano, Dario Fiore, and Romain Gay. Practical functional encryption for quadratic functions with applications to predicate encryption. In Jonathan Katz and Hovav Shacham, editors, *CRYPTO 2017, Part I*, volume 10401 of LNCS, pages 67–98. Springer, Heidelberg, August 2017. doi:10.1007/978-3-319-63688-7_3.

[BF01] Dan Boneh and Matthew K. Franklin. Identity-based encryption from the Weil pairing. In Joe Kilian, editor, *CRYPTO 2001*, volume 2139–229. Springer, Heidelberg, August 2001. doi:10.1007/3-540-44647-8_13.

[BJK15] Allison Bishop, Abhishek Jain, and Lucas Kowalczyk. Function-hiding inner product encryption. In Tetsu Iwata and Jung Hee Cheon, editors, *ASI-ACRYPT 2015, Part I*, volume 9452 of LNCS, pages 470–491. Springer, Heidelberg, November / December 2015. doi:10.1007/978-3-662-48797-6_20.

[BR06] Mihir Bellare and Phillip Rogaway. The security of triple encryption and a framework for code-based game-playing proofs. In Serge Vaudenay, editor, *EUROCRYPT 2006*, volume 4004 of LNCS, pages 409–426. Springer, Heidelberg, May / June 2006. doi:10.1007/11761679_25.

[BSW11] Dan Boneh, Amit Sahai, and Brent Waters. Functional encryption: Definitions and challenges. In Yuval Ishai, editor, *TCC 2011*, volume 6597 of LNCS, pages 253–273. Springer, Heidelberg, March 2011. doi:10.1007/978-3-642-19571-6_16.

[BV15] Nir Bitansky and Vinod Vaikuntanathan. Indistinguishability obfuscation from functional encryption. In Venkatesan Guruswami, editor, *56th FOCS*, pages 171–190. IEEE Computer Society Press, October 2015. doi:10.1109/FOCS.2015.20.

[CDG$^{+}$18a] Jérémy Chotard, Edouard Dufour Sans, Romain Gay, Duong Hieu Phan, and David Pointcheval. Decentralized multi-client functional encryption for inner product. In Thomas Peyrin and Steven Galbraith, editors, *ASIACRYPT 2018, Part II*, volume 11273 of LNCS, pages 703–732. Springer, Heidelberg, December 2018. doi:10.1007/978-3-030-03329-3_24.

[CDG$^{+}$18b] Jérémy Chotard, Edouard Dufour Sans, Romain Gay, Duong Hieu Phan, and David Pointcheval. Multi-client functional encryption with repetition for inner product. Cryptology ePrint Archive, Report 2018/1021, 2018. https://eprint.iacr.org/2018/1021.

[CDSG$^{+}$20] Jérémy Chotard, Edouard Dufour-Sans, Romain Gay, Duong Hieu Phan, and David Pointcheval. Dynamic decentralized functional encryption. In Daniele Micciancio and Thomas Ristenpart, editors, *CRYPTO 2020, Part I*, volume 12170 of LNCS, pages 747–775. Springer, Heidelberg, August 2020. doi:10.1007/978-3-030-56784-2_25.

[CLL$^{+}$13] Jie Chen, Hoon Wei Lim, San Ling, Huaxiong Wang, and Hoeteck Wee. Shorter IBE and signatures via asymmetric pairings. In Michel Abdalla and Tanja Lange, editors, *PAIRING 2012*, volume 7708 of LNCS, pages 122–140. Springer, Heidelberg, May 2013. doi:10.1007/978-3-642-36334-4_8.

[CLT18] Guilhem Castagnos, Fabien Laguillaumie, and Ida Tucker. Practical fully secure unrestricted inner product functional encryption modulo $p$. In Thomas Peyrin and Steven Galbraith, editors, *ASIACRYPT 2018, Part II*, volume 11273 of LNCS, pages 733–764. Springer, Heidelberg, December 2018. doi:10.1007/978-3-030-03329-3_25.
[Coc01] Clifford Cocks. An identity based encryption scheme based on quadratic residues. In Bahram Honary, editor, *8th IMA International Conference on Cryptography and Coding*, volume 2260 of LNCS, pages 360–363. Springer, Heidelberg, December 2001. doi:10.1007/3-540-45325-3_32.

[DDM16] Pratish Datta, Ratna Dutta, and Sourav Mukhopadhyay. Functional encryption for inner product with full function privacy. In Chen-Mou Cheng, Kai-Min Chung, Giuseppe Persiano, and Bo-Yin Yang, editors, *PKC 2016, Part I*, volume 9614 of LNCS, pages 164–195. Springer, Heidelberg, March 2016. doi:10.1007/978-3-662-49384-7_7.

[DDM17] Pratish Datta, Ratna Dutta, and Sourav Mukhopadhyay. Strongly full-hiding inner product encryption. *Theoretical Computer Science*, 2017. URL: https://www.sciencedirect.com/science/article/pii/S0304397516307526, doi:https://doi.org/10.1016/j.tcs.2016.12.024.

[DOT18] Pratish Datta, Tatsuaki Okamoto, and Junichi Tomida. Full-hiding (unbounded) multi-input inner product functional encryption from the $k$-Linear assumption. In Michel Abdalla and Ricardo Dahab, editors, *PKC 2018, Part II*, volume 10770 of LNCS, pages 245–277. Springer, Heidelberg, March 2018. doi:10.1007/978-3-319-76581-5_9.

[EHK$^{+13}$] Alex Escala, Gottfried Herold, Eike Kiltz, Carla Ràfols, and Jorge Villar. An algebraic framework for Diffie-Hellman assumptions. In Ran Canetti and Juan A. Garay, editors, *CRYPTO 2013, Part II*, volume 8043 of LNCS, pages 129–147. Springer, Heidelberg, August 2013. doi:10.1007/978-3-642-40084-1_8.

[Gay20] Romain Gay. A new paradigm for public-key functional encryption for degree-2 polynomials. In Aggelos Kiayias, Markulf Kohlweiss, Petros Wallden, and Vassilis Zikas, editors, *PKC 2020, Part I*, volume 12110 of LNCS, pages 95–120. Springer, Heidelberg, May 2020. doi:10.1007/978-3-030-45374-9_4.

[GGG$^{+14}$] Shafi Goldwasser, S. Dov Gordon, Vipul Goyal, Abhishek Jain, Jonathan Katz, Feng-Hao Liu, Amit Sahai, Elaine Shi, and Hong-Sheng Zhou. Multi-input functional encryption. In Phong Q. Nguyen and Elisabeth Oswald, editors, *EUROCRYPT 2014*, volume 8441 of LNCS, pages 578–602. Springer, Heidelberg, May 2014. doi:10.1007/978-3-642-55220-5_32.

[GKL$^{+13}$] S. Dov Gordon, Jonathan Katz, Feng-Hao Liu, Elaine Shi, and Hong-Sheng Zhou. Multi-input functional encryption. Cryptology ePrint Archive, Report 2013/774, 2013. https://eprint.iacr.org/2013/774.

[GPSW06] Vipul Goyal, Omkant Pandey, Amit Sahai, and Brent Waters. Attribute-based encryption for fine-grained access control of encrypted data. In Ari Juels, Rebecca N. Wright, and Sabrina De Capitani di Vimercati, editors, *ACM CCS 2006*, pages 89–98. ACM Press, October / November 2006. Available as Cryptology ePrint Archive Report 2006/309. doi:10.1145/1180405.1180418.

[GVW15] Sergey Gorbunov, Vinod Vaikuntanathan, and Hoeteck Wee. Predicate encryption for circuits from LWE. In Rosario Gennaro and Matthew J. B. Robshaw, editors, *CRYPTO 2015, Part II*, volume 9216 of LNCS, pages 503–523. Springer, Heidelberg, August 2015. doi:10.1007/978-3-662-48000-7_25.
[JR17] Charanjit S. Jutla and Arnab Roy. Shorter quasi-adaptive NIZK proofs for linear subspaces. *Journal of Cryptology*, 30(4):1116–1156, October 2017. doi:10.1007/s00145-016-9243-7.

[KKS19] Sungwook Kim, Jinsu Kim, and Jae Hong Seo. A new approach to practical function-private inner product encryption. *Theoretical Computer Science*, 783:22–40, 2019. doi:10.1016/J.TCS.2019.03.016.

[KLM$^{+}$18] Sam Kim, Kevin Lewi, Avradip Mandal, Hart Montgomery, Arnab Roy, and David J. Wu. Function-hiding inner product encryption is practical. In Dario Catalano and Roberto De Prisco, editors, *SCN 18*, volume 11035 of LNCS, pages 544–562. Springer, Heidelberg, September 2018. doi:10.1007/978-3-319-98113-0_29.

[Lin17] Huijia Lin. Indistinguishability obfuscation from SXDH on 5-linear maps and locality-5 PRGs. In Jonathan Katz and Hovav Shacham, editors, *CRYPTO 2017, Part I*, volume 10401 of LNCS, pages 599–629. Springer, Heidelberg, August 2017. doi:10.1007/978-3-319-63688-7_20.

[LT19] Benoît Libert and Radu Titiu. Multi-client functional encryption for linear functions in the standard model from LWE. In Steven D. Galbraith and Shiho Moriai, editors, *ASIACRYPT 2019, Part III*, volume 11923 of LNCS, pages 520–551. Springer, Heidelberg, December 2019. doi:10.1007/978-3-030-34618-8_18.

[LV16] Huijia Lin and Vinod Vaikuntanathan. Indistinguishability obfuscation from DDH-like assumptions on constant-degree graded encodings. In Irit Dinur, editor, *57th FOCS*, pages 11–20. IEEE Computer Society Press, October 2016. doi:10.1109/FOCS.2016.11.

[LW10] Allison B. Lewko and Brent Waters. New techniques for dual system encryption and fully secure HIBE with short ciphertexts. In Daniele Micciancio, editor, *TCC 2010*, volume 5978 of LNCS, pages 455–479. Springer, Heidelberg, February 2010. doi:10.1007/978-3-642-11799-2_27.

[NPP22] Ky Nguyen, Duong Hieu Phan, and David Pointcheval. Multi-client functional encryption with fine-grained access control. In Shweta Agrawal and Dongdai Lin, editors, *ASIACRYPT 2022, Part I*, volume 13791 of LNCS, pages 95–125. Springer, Heidelberg, December 2022. doi:10.1007/978-3-031-22963-3_4.

[NPP23] Ky Nguyen, Duong Hieu Phan, and David Pointcheval. Optimal security notion for decentralized multi-client functional encryption. In Mehdi Tibouchi and Xiaofeng Wang, editors, *ACNS 23, Part II*, volume 13906 of LNCS, pages 336–365. Springer, Heidelberg, June 2023. doi:10.1007/978-3-031-33491-7_13.

[OSW07] Rafail Ostrovsky, Amit Sahai, and Brent Waters. Attribute-based encryption with non-monotonic access structures. In Peng Ning, Sabrina De Capitani di Vimercati, and Paul F. Syverson, editors, *ACM CCS 2007*, pages 195–203. ACM Press, October 2007. doi:10.1145/1315245.1315270.

[OT10] Tatsuaki Okamoto and Katsuyuki Takashima. Fully secure functional encryption with general relations from the decisional linear assumption. In Tal Rabin, editor, *CRYPTO 2010*, volume 6223 of LNCS, pages 191–208. Springer, Heidelberg, August 2010. doi:10.1007/978-3-642-14623-7_11.
[OT12a] Tatsuaki Okamoto and Katsuyuki Takashima. Adaptively attribute-hiding (hierarchical) inner product encryption. In David Pointcheval and Thomas Johansson, editors, *EUROCRYPT 2012*, volume 7237 of LNCS, pages 591–608. Springer, Heidelberg, April 2012. doi:10.1007/978-3-642-29011-4_35.

[OT12b] Tatsuaki Okamoto and Katsuyuki Takashima. Fully secure unbounded inner-product and attribute-based encryption. In Xiaoyun Wang and Kazue Sako, editors, *ASIACRYPT 2012*, volume 7658 of LNCS, pages 349–366. Springer, Heidelberg, December 2012. doi:10.1007/978-3-642-34961-4_22.

[Sha84] Adi Shamir. Identity-based cryptosystems and signature schemes. In G. R. Blakley and David Chaum, editors, *CRYPTO '84*, volume 196 of LNCS, pages 47–53. Springer, Heidelberg, August 1984. doi:10.1007/3-540-39568-7_5.

[SV23] Elaine Shi and Nikhil Vanjani. Multi-client inner product encryption: Function-hiding instantiations without random oracles. In Alexandra Boldyreva and Vladimir Kolesnikov, editors, *PKC 2023, Part I*, volume 13940 of LNCS, pages 622–651. Springer, Heidelberg, May 2023. doi:10.1007/978-3-031-31368-4_22.

[SW05] Amit Sahai and Brent R. Waters. Fuzzy identity-based encryption. In Ronald Cramer, editor, *EUROCRYPT 2005*, volume 3494 of LNCS, pages 457–473. Springer, Heidelberg, May 2005. doi:10.1007/11426639_27.

[TAO16] Junichi Tomida, Masayuki Abe, and Tatsuaki Okamoto. Efficient functional encryption for inner-product values with full-hiding security. In Matt Bishop and Anderson C. A. Nascimento, editors, *ISC 2016*, volume 9866 of LNCS, pages 408–425. Springer, Heidelberg, September 2016. doi:10.1007/978-3-319-45871-7_24.

[Tom19] Junichi Tomida. Tightly secure inner product functional encryption: Multi-input and function-hiding constructions. In Steven D. Galbraith and Shiho Moriai, editors, *ASIACRYPT 2019, Part III*, volume 11923 of LNCS, pages 459–488. Springer, Heidelberg, December 2019. doi:10.1007/978-3-030-34618-8_16.

[Tom20] Junichi Tomida. Tightly secure inner product functional encryption: Multi-input and function-hiding constructions. *Theoretical Computer Science*, 833:56–86, 2020. doi:10.1016/J.TCS.2020.05.008.

[Üna20] Akin Ünal. Impossibility results for lattice-based functional encryption schemes. In Anne Canteaut and Yuval Ishai, editors, *EUROCRYPT 2020, Part I*, volume 12105 of LNCS, pages 169–199. Springer, Heidelberg, May 2020. doi:10.1007/978-3-030-45721-1_7.

[Wat09] Brent Waters. Dual system encryption: Realizing fully secure IBE and HIBE under simple assumptions. In Shai Halevi, editor, *CRYPTO 2009*, volume 5677 of LNCS, pages 619–636. Springer, Heidelberg, August 2009. doi:10.1007/978-3-642-03356-8_36.
# A Supporting Materials – Section 4

## A.1 Additional Techniques and Notations for DPVS

**Basis Changes.** In this work, we use extensively *basis changes* over dual orthogonal bases of a DPVS. We again use $\mathbb{G}_1^N$ as a running example. Let $(\mathbf{A}, \mathbf{A}^*)$ be the dual canonical bases of $(\mathbb{G}_1^N, \mathbb{G}_2^N)$. Let $(\mathbf{U} = (\mathbf{u}_i)_i, \mathbf{U}^* = (\mathbf{u}_i^*)_i)$ be a pair of dual bases of $(\mathbb{G}_1^N, \mathbb{G}_2^N)$, corresponding to an invertible matrix $U \in \mathbb{Z}_q^{N \times N}$. Given an invertible matrix $B \in \mathbb{Z}_q^{N \times N}$, the basis change from $\mathbf{U}$ w.r.t $B$ is defined to be $\mathbf{B} := B \cdot \mathbf{U}$, which means:

$$ (x_1, \dots, x_N)_{\mathbf{B}} = \sum_{i=1}^{N} x_i \mathbf{b}_i = (x_1, \dots, x_N) \cdot \mathbf{B} = (x_1, \dots, x_N) \cdot B \cdot \mathbf{U} \\ = (y_1, \dots, y_N)_{\mathbf{U}} \text{ where } (y_1, \dots, y_N) := (x_1, \dots, x_N) \cdot B. $$

Under a basis change $\mathbf{B} = B \cdot \mathbf{U}$, we have

$$ (x_1, \dots, x_N)_{\mathbf{B}} = ((x_1, \dots, x_N) \cdot B)_{\mathbf{U}}; \quad (y_1, \dots, y_N)_{\mathbf{U}} = ((y_1, \dots, y_N) \cdot B^{-1})_{\mathbf{B}}. \quad (10) $$

The computation is extended to the dual basis change $\mathbf{B}^* = B' \cdot \mathbf{U}^*$, where $B' = (B^{-1})^\top$:

$$ (x_1, \dots, x_N)_{\mathbf{B}^*} = ((x_1, \dots, x_N) \cdot B')_{\mathbf{U}^*}; \quad (y_1, \dots, y_N)_{\mathbf{U}^*} = ((y_1, \dots, y_N) \cdot B^\top)_{\mathbf{B}^*}. \quad (11) $$

It can be checked that $(\mathbf{B}, \mathbf{B}^*)$ remains a pair of dual orthogonal bases. When we consider a basis change $\mathbf{B} = B \cdot \mathbf{U}$, if $B = (b_{i,j})_{i,j}$ affects only a subset $J \subseteq [N]$ of indices in the representation w.r.t basis $\mathbf{U}$, we will write $B$ as the square block containing $(b_{i,j})_{i,j}$ for $i, j \in J$ and implicitly the entries of $B$ outside this block are taken from the identity matrix $I_N$.

The basis changes are particularly useful in our security proofs. Intuitively these changes constitute a transition from a hybrid $\mathbf{G}$ having vectors expressed in $(\mathbf{U}, \mathbf{U}^*)$ to the next hybrid $\mathbf{G}_{\text{next}}$ having vectors expressed in $(\mathbf{B}, \mathbf{B}^*)$. We focus on two types of basis changes, which are elaborated below. For simplicity, we consider dimension $N = 2$:

**Formal Basis Change:** We change $(\mathbf{U}, \mathbf{U}^*)$ into $(\mathbf{B}, \mathbf{B}^*)$ using

$$ B := \begin{bmatrix} 1 & 0 \\ 1 & 1 \end{bmatrix}_{1,2} \qquad B' := (B^{-1})^\top = \begin{bmatrix} 1 & -1 \\ 0 & 1 \end{bmatrix}_{1,2} \\ \mathbf{B} = B \cdot \mathbf{U} \qquad \mathbf{B}^* = B' \cdot \mathbf{U}^*. $$

We use this type in situations such as: in $\mathbf{G}$ we have vectors all of the form $(x_1, 0)_{\mathbf{U}}, (y_1, 0)_{\mathbf{U}^*}$, and we want to go to $\mathbf{G}_{\text{next}}$ having vectors all of the form $(x_1, 0)_{\mathbf{B}}, (y_1, [y_1])_{\mathbf{B}^*}$. The simulator writes all vectors $(x_1, 0)_{\mathbf{U}}, (y_1, 0)_{\mathbf{U}^*}$ in $(\mathbf{U}, \mathbf{U}^*)$ and under this basis change they are written into

$$ (x_1, 0)_{\mathbf{U}} = (x_1 - 0, 0)_{\mathbf{B}} = (x_1, 0)_{\mathbf{B}}; \quad (y_1, 0)_{\mathbf{U}^*} = (y_1, 0 + y_1)_{\mathbf{B}^*} = (y_1, y_1)_{\mathbf{B}^*} $$

following the calculations in (10) and (11). The products between two dual vectors are invariant, all vectors are formally written from $(\mathbf{U}, \mathbf{U}^*)$ (corresponding to $\mathbf{G}$) to $(\mathbf{B}, \mathbf{B}^*)$ (corresponding to $\mathbf{G}_{\text{next}}$), the adversary's view over the vectors is thus identical from $\mathbf{G}$ to $\mathbf{G}_{\text{next}}$. In particular, this is a kind of *information-theoretic property* of DPVS by basis changing that we exploit to have identical hybrids' hop in the security proof.
**Computational Basis Change:** Given an instance of a computational problem, e.g. $\llbracket (a, b, c) \rrbracket_1$ of DDH in $\mathbb{G}_1$ where $c - ab = 0$ or $\delta \stackrel{\$}{\leftarrow} \mathbb{Z}_q$, we change $(\mathbf{U}, \mathbf{U}^*)$ into $(\mathbf{B}, \mathbf{B}^*)$ using

$$B := \begin{bmatrix} 1 & 0 \\ a & 1 \end{bmatrix}_{1,2}$$

$$\mathbf{B} = B \cdot \mathbf{U}$$

$$B' := (B^{-1})^{\top} = \begin{bmatrix} 1 & -a \\ 0 & 1 \end{bmatrix}_{1,2}$$

$$\mathbf{B}^* = B' \cdot \mathbf{U}^*.$$

One situation where this type of basis change can be useful is: in $\mathbb{G}$ we have some target vectors of the form $(0, \text{rnd})_{\mathbb{U}}$, where $\text{rnd} \stackrel{\$}{\leftarrow} \mathbb{Z}_q$ is a random scalar, together with other $(z_1, z_2)_{\mathbb{U}}$, and all the dual is of the form $(0, y_2)_{\mathbb{U}^*}$. We want to go to $\mathbb{G}_{\text{next}}$ having $(\widetilde{\text{rnd}}, \text{rnd})_{\mathbb{B}}$ masked by some randomness $\widetilde{\text{rnd}} \stackrel{\$}{\leftarrow} \mathbb{Z}_q$, while keeping $(0, y_2)_{\mathbb{B}^*}$. Because $\llbracket a \rrbracket_1$ is given, the simulator can simulate vectors $(z_1, z_2)_{\mathbb{U}}$ directly in $\mathbb{B}$ using $\llbracket a \rrbracket_1$ as well as the known coordinates $z_1, z_2$. The basis change will be employed for the simulation of target vectors:

$$(c, b)_{\mathbb{U}} + (0, \text{rnd})_{\mathbb{B}} = (c - a \cdot b, \text{rnd} + b)_{\mathbb{B}};$$

$$(0, y_2)_{\mathbb{U}^*} = (0, y_2 + a \cdot 0)_{\mathbb{B}^*} = (0, y_2)_{\mathbb{B}^*}$$

where all vectors in $\mathbf{B}^*$ must be written first in $\mathbb{U}^*$, since we do not have $\llbracket a \rrbracket_2$, to see how the basis change affects them. Using the basis change we simulate those target vectors by $(c - a \cdot b, \text{rnd} + b)_{\mathbb{B}}$ with $\text{rnd}$ implicitly being updated to $\text{rnd} + b$, the uninterested $(z_1, z_2)_{\mathbb{B}}$ are simulated correctly in $\mathbb{B}$, meanwhile the dual vectors $(0, y_2)_{\mathbb{B}^*}$ stays the same. Depending on the DDH instance, if $c - ab = 0$ the target vectors are in fact $(0, \text{rnd})_{\mathbb{B}}$ and we are simulating $\mathbb{G}$, else $c - ab = \delta \stackrel{\$}{\leftarrow} \mathbb{Z}_q$ the target vectors are simulated for $\mathbb{G}_{\text{next}}$ and $\text{rnd} := \delta$. Hence, under the hardness of DDH in $\mathbb{G}_1$, a computationally bounded adversary cannot distinguish its views in the hybrids' hop from $\mathbb{G}$ to $\mathbb{G}_{\text{next}}$.

We remark that the basis changes will modify basis vectors and for the indistinguishability to hold, perfectly in *formal* change and computationally in *computational* changes, all impacted basis vectors must not be revealed to the adversary.

**Additional Notations.** Any $\mathbf{x} = \llbracket (m_1, \dots, m_N) \rrbracket_1 \in \mathbb{G}_1^N$ is identified as the vector $(m_1, \dots, m_N) \in \mathbb{Z}_q^N$. There is no ambiguity because $\mathbb{G}_1$ is a cyclic group of order $q$ prime. The $0$-vector is $\mathbf{0} = \llbracket (0, \dots, 0) \rrbracket_1$. The addition of two vectors in $\mathbb{G}_1^N$ is defined by coordinate-wise addition. The scalar multiplication of a vector is defined by $t \cdot \mathbf{x} := \llbracket t \cdot (m_1, \dots, m_N) \rrbracket_1$, where $t \in \mathbb{Z}_q$ and $\mathbf{x} = \llbracket (m_1, \dots, m_N) \rrbracket_1$. The additive inverse of $\mathbf{x} \in \mathbb{G}_1^N$ is defined to be $-\mathbf{x} := \llbracket (-m_1, \dots, -m_N) \rrbracket_1$.

The canonical basis $\mathbf{A}$ of $\mathbb{G}_1^N$ consists of $\mathbf{a}_1 := \llbracket (1, 0, \dots, 0) \rrbracket_1$, $\mathbf{a}_2 := \llbracket (0, 1, 0, \dots, 0) \rrbracket_1$, ..., $\mathbf{a}_N := \llbracket (0, \dots, 0, 1) \rrbracket_1$. By convention the writing $\mathbf{x} = (m_1, \dots, m_N)$ concerns the canonical basis $\mathbf{A}$.

## A.2 Swapping with Repetitions – Proof of Lemma 1

**Lemma 1 (Swapping).** Let $\lambda \in \mathbb{N}$ and $H = H(\lambda), K = K(\lambda), L = L(\lambda), J_i = J_i(\lambda), \tilde{J}_i = \tilde{J}_i(\lambda), N = N(\lambda) \in \mathbb{N}$ where $i \in [H]$ and $H, K, L, J_i, \tilde{J}_i, N: \mathbb{N} \to \mathbb{N}$ are polynomials. Let $\tilde{J} := \max_{i \in [H]} \{\tilde{J}_i\}$, where the maximum is over polynomial evaluations $\tilde{J}_i(\lambda) \in \mathbb{N}$. Let $(\mathbf{B}_i, \mathbf{B}_i^*)$, for each $i \in [H]$, be a pair of random dual bases of dimension $2N + 2N \cdot \tilde{J} + 4$ in $(\mathbb{G}_1, \mathbb{G}_2, \mathbb{G}_t, g_1, g_2, g_t, \mathbf{e}, \mathbf{q})$. All basis vectors are kept secret. Let $R, R_1, \dots, R_K \in \mathbb{Z}_q$ be some public scalars. For $i \in [H]$, $\ell \in [L]$ and $k \in [K]$, sample $\sigma_i, \sigma_{i,k}, r, r_\ell \stackrel{\$}{\leftarrow} \mathbb{Z}_q$ conditioned on $\sum_{i \in [H]} \sigma_i = R$ and $\sum_{i \in [H]} \sigma_{k,i} = R_k$.

We consider the following oracles:
O_d: On input $(\ell, i, \mathbf{y}_{\ell,i}^{(\text{rep})}, \mathbf{y}_{\ell,i}^{(\text{rep})'}) \in [L] \times [H] \times \mathbb{Z}_q^N \times \mathbb{Z}_q^N$, where rep $\in [J_i]$ is a counter for the number of queries of the form $(\ell, i, \star, \star)$, sample $\rho_{\ell,i}^{(\text{rep})} \stackrel{\$}{\leftarrow} \mathbb{Z}_q$ and output

$$ \mathbf{d}_{\ell,i}^{(\text{rep})} = (\mathbf{y}_{\ell,i}^{(\text{rep})}, \mathbf{y}_{\ell,i}^{(\text{rep})'}, r_{\ell}, 0, \rho_{\ell,i}^{(\text{rep})}, 0^{2N \cdot \tilde{J} + 1})_{\mathbf{B}_i} . $$

O_d^b: For $b \in \{0,1\}$, on input $(i, \mathbf{y}_i^{(1, \tilde{j}_i)}, \mathbf{y}_i^{(0, \tilde{j}_i)}) \in [H] \times \mathbb{Z}_q^N$, where $\tilde{j}_i \in [\tilde{J}_i]$ is a counter for the number of queries of the form $(i, \star, \star)$, sample $\rho_i^{(\tilde{j}_i)} \stackrel{\$}{\leftarrow} \mathbb{Z}_q$ and output

$$ \text{If } \boxed{b=0}: \quad \mathbf{d}_i^{(\tilde{j}_i)} = (\boxed{\mathbf{y}_i^{(1, \tilde{j}_i)}}, \boxed{0^N}), \quad r, 0, \rho_i^{(\tilde{j}_i)}, 0^{2N \cdot \tilde{J} + 1})_{\mathbf{B}_i} $$

$$ \text{If } \boxed{b=1}: \quad \mathbf{d}_i^{(\tilde{j}_i)} = (\boxed{0^N}), \quad \boxed{\mathbf{y}_i^{(0, \tilde{j}_i)}}, \quad r, 0, \rho_i^{(\tilde{j}_i)}, 0^{2N \cdot \tilde{J} + 1})_{\mathbf{B}_i} . $$

O_c: On input $(i, \mathbf{x}_i^{(1, \tilde{j}_i)}, \mathbf{x}_i^{(0, \tilde{j}_i)}) \in [H] \times \mathbb{Z}_q^N \times \mathbb{Z}_q^N$, where $j_i \in [J_i]$ is a counter for the number of queries of the form $(i, \star, \star)$, sample $\pi_i^{(j_i)} \stackrel{\$}{\leftarrow} \mathbb{Z}_q$ and output

$$ \mathbf{c}_i^{(\tilde{j}_i)} = (\mathbf{x}_i^{(1, \tilde{j}_i)}, \mathbf{x}_i^{(0, \tilde{j}_i)}, \sigma_i, \pi_i^{(\tilde{j}_i)}, 0, 0^{2N \cdot \tilde{J} + 1})_{\mathbf{B}_i^*} . $$

O_c^c: On inputs $(k, i, \mathbf{x}_{k,i}^{(\text{rep})}) \in [K] \times [H] \times \mathbb{Z}_q$, where rep $\in [J_i]$ is a counter for the number of queries of the form $(k, i, \star)$, sample $\pi_{k,i}^{(\text{rep})} \stackrel{\$}{\leftarrow} \mathbb{Z}_q$ and output

$$ \mathbf{c}_{k,i}^{(\text{rep})} = (\mathbf{x}_{k,i}^{(\text{rep})}, \mathbf{x}_{k,i}^{(\text{rep})}, \sigma_{k,i}, \pi_{k,i}^{(\text{rep})}, 0, 0^{2N \cdot \tilde{J} + 1})_{\mathbf{B}_i^*} . $$

If $\sum_{i=1}^H \langle \mathbf{y}_i^{(1, \tilde{j}_i)}, \mathbf{x}_i^{(1, \tilde{j}_i)} \rangle - \langle \mathbf{y}_i^{(0, \tilde{j}_i)}, \mathbf{x}_i^{(0, \tilde{j}_i)} \rangle = 0$ and $\sum_{i=1}^H \langle \mathbf{y}_i^{(1, \tilde{j}_i)} - \mathbf{y}_i^{(0, \tilde{j}_i)}, \mathbf{x}_i^{(\text{rep})} \rangle = 0$ for all $\tilde{j}_i \in [\tilde{J}_i]$, rep, $j_i \in [J_i]$, then the following advantage is negligible under the SXDH assumption:

$$ \left| \Pr[\mathcal{A}_{\tilde{O}_c, \mathcal{O}_c}^{\tilde{O}_d, \mathcal{O}_d^0} (1^{\lambda}, N, H, K, L, (J_i, \tilde{J}_i)_{i \in [H]}, R, (R_k)_{k \in [K]}) \to 1] \\ - \Pr[\mathcal{A}_{\tilde{O}_c, \mathcal{O}_c}^{\tilde{O}_d, \mathcal{O}_d^1} (1^{\lambda}, N, H, K, L, (J_i, \tilde{J}_i)_{i \in [H]}, R, (R_k)_{k \in [K]}) \to 1] \right| \\ \le (4n\tilde{J}N + 4) \cdot \mathbf{Adv}_{\tilde{G}_1, \tilde{G}_2}^{\text{SXDH}}(1^{\lambda}) $$

where $\mathcal{A}$ can query the oracles $\tilde{O}_d$, $\mathcal{O}_d^b$, $\mathcal{O}_c$, $\tilde{O}_c$ adaptively, i.e. the queries can be made in any order and any number of times respecting the (polynomial) upper bounds $K, L, (J_i, \tilde{J}_i)_{i \in [H]}$.

*Proof.* The proof is done via a sequence of hybrid games. The games are depicted in Figure 4.

Unless stated otherwise, for simpler notations in the following we omit the index $i$ from $j_i \in [J_i], \tilde{j}_i \in [\tilde{J}_i], \mathbf{d}^{(j_i)}, \mathbf{c}^{(j_i)}$ and write $j \in [J], \tilde{j} \in [\tilde{J}], \mathbf{d}^{(j)}, \mathbf{c}^{(j)}$. For each $i \in [H]$, the value $j$ denotes the maximum number of possible repetitions $(\mathbf{d}_{\ell,i}^{(\text{rep})})_{\text{rep}}$, $(\mathbf{c}_i^{(j)})_j$, and $(\mathbf{c}_{k,i}^{(\text{rep})})_{\text{rep}}$, indexed by rep and $j$ over all $\ell, k$. The bound $\tilde{J} \ge \max_{i \in [H]} \{\tilde{J}_i\}$ of repetitions queried by the adversary for d-vectors is fixed in advance. For the ease of notation, we define $J := \max_{i \in [H]} \{J_i\}$ as the number of repetitions queried by the adversary for c-vectors, not fixed in advance. We note that the dimensions of the DPVS bases depends on the $\tilde{J}$, i.e. the maximum number of repetitions we allow the adversary to make on $\mathbf{d}_i^{(j)}$. We use notation $0 := 0^N$ and write $0^{\tilde{J}} := 0 \parallel \dots \parallel 0$, for $\tilde{J}$ times.

We describe the sequence of hybrids below.

**Game G₀:** The vectors are computed according to the interaction:

$$ \mathcal{A}_{\tilde{O}_c, \mathcal{O}_c}^{\tilde{O}_d, \mathcal{O}_d^0} (1^{\lambda}, N, H, K, L, (J_i, \tilde{J}_i)_{i \in [H]}, R, (R_k)_{k \in [K]}) . $$
**Game G₀:** The vectors are sampled according to $D_0$. The poly-bound $\tilde{J} \ge \max_{i \in [H]} \{\tilde{J}_i\}$ is fixed. Indices are running $j_i \in [J_i]$, $\tilde{j}_i \in [\tilde{J}_i]$.

**Game G₁:** (Random 0-Secret Sharing) $\sum_{i=1}^{H} \tau_i = \sum_{i=1}^{H} \tau'_{k,i} = 0, 0 := 0^N$

$$
\begin{align*}
d_{\ell,i}^{(\text{rep})} &= ( \mathbf{y}_{\ell,i}^{(\text{rep})} \quad \mathbf{y}_{\ell,i}^{(\text{rep})'} \quad r_{\ell} \quad 0 \quad \rho_{\ell,i}^{(\text{rep})} \quad \mathbf{0}^{\tilde{J}} \quad \mathbf{0}^{\tilde{J}} \quad 0 \quad \mathbf{B}_i ) \\
d_i^{(\tilde{j}_i)} &= ( \mathbf{y}_i^{(1,\tilde{j}_i)} \quad \mathbf{0} \quad \boxed{\phantom{0}} \quad 0 \quad \rho_i^{(\tilde{j}_i)} \quad \mathbf{0}^{\tilde{J}} \quad \mathbf{0}^{\tilde{J}} \quad \boxed{\phantom{0}} \quad \mathbf{B}_i ) \\
c_i^{(\tilde{j}_i)} &= ( \mathbf{x}_i^{(1,\tilde{j}_i)} \quad \mathbf{x}_i^{(0,\tilde{j}_i)} \quad \boxed{\phantom{0}} \quad \sigma_i \quad \pi_i^{(\tilde{j}_i)} \quad 0 \quad \mathbf{0}^{\tilde{J}} \quad \mathbf{0}^{\tilde{J}} \quad \boxed{\phantom{0}} \quad \mathbf{B}_i^* ) \\
c_{k,i}^{(\text{rep})} &= ( \mathbf{x}_{k,i}^{(\text{rep})} \quad \mathbf{x}_{k,i}^{(\text{rep})'} \quad \sigma_{k,i} \quad \pi_{k,i}^{(\text{rep})} \quad 0 \quad \mathbf{0}^{\tilde{J}} \quad \mathbf{0}^{\tilde{J}} \quad \boxed{\phantom{0}} \quad \mathbf{B}_i^* )
\end{align*}
$$

**Game G₂:** (Formal Duplication from coordinates $[1, N]$, $[N + 1, 2N]$ in $B_i^*$, for $c_i^{(\tilde{j}_i)}$ the coordinates $[2N \cdot \tilde{j}_i + 4, 2N \cdot \tilde{j}_i + N + 3]$, $[3N \cdot \tilde{j}_i + 4, 4N \cdot \tilde{j}_i + N + 3]$ change)

$$
\begin{align*}
d_{\ell,i}^{(\text{rep})} &= ( \mathbf{y}_{\ell,i}^{(\text{rep})} \quad \mathbf{y}_{\ell,i}^{(\text{rep})'} \quad r_{\ell} \quad 0 \quad \rho_{\ell,i}^{(\text{rep})} \quad \dots \quad \mathbf{0} \quad \mathbf{0} \quad \dots \quad 0 \quad \mathbf{B}_i ) \\
d_i^{(\tilde{j}_i)} &= ( \mathbf{y}_i^{(1,\tilde{j}_i)} \quad \mathbf{0} \quad r \quad 0 \quad \rho_i^{(\tilde{j}_i)} \quad \dots \quad \mathbf{0} \quad \mathbf{0} \quad \dots \quad r' \quad \mathbf{B}_i ) \\
c_i^{(\tilde{j}_i)} &= ( \mathbf{x}_i^{(1,\tilde{j}_i)} \quad \mathbf{x}_i^{(0,\tilde{j}_i)} \quad \sigma_i \quad \pi_i^{(\tilde{j}_i)} \quad 0 \quad \dots \quad \boxed{\mathbf{x}_i^{(1,\tilde{j}_i)}} \quad \boxed{\mathbf{x}_i^{(0,\tilde{j}_i)}} \quad \dots \quad \tau_i \quad \mathbf{B}_i^* ) \\
c_{k,i}^{(\text{rep})} &= ( \mathbf{x}_{k,i}^{(\text{rep})} \quad \mathbf{x}_{k,i}^{(\text{rep})'} \quad \sigma_{k,i} \quad \pi_{k,i}^{(\text{rep})} \quad 0 \quad \dots \quad \boxed{\mathbf{x}_{k,i}^{(\text{rep})}} \quad \boxed{\mathbf{x}_{k,i}^{(\text{rep})}} \quad \dots \quad \tau'_{k,i} \quad \mathbf{B}_i^* )
\end{align*}
$$

**Game G₃:** (Computational Swapping between $[1, N]$ and $[2N \cdot \tilde{j}_i + 4, 3N \cdot \tilde{j}_i + N + 3]$ in $d_i^{(\tilde{j}_i)}$ using $(2N + 3)$-randomness in $B_i$, by $n \cdot \tilde{J} \cdot N$ DSDH instances)

$$
\begin{align*}
d_{\ell,i}^{(\text{rep})} &= ( \mathbf{y}_{\ell,i}^{(\text{rep})} \quad \mathbf{y}_{\ell,i}^{(\text{rep})'} \quad r_{\ell} \quad 0 \quad \rho_{\ell,i}^{(\text{rep})} \quad \dots \quad \mathbf{0} \quad \mathbf{0} \quad \dots \quad 0 \quad \mathbf{B}_i ) \\
d_i^{(\tilde{j}_i)} &= ( \boxed{0} \quad \mathbf{0} \quad r \quad 0 \quad \boxed{\rho_i^{(\tilde{j}_i)}} \quad \dots \quad \boxed{\mathbf{y}_i^{(1,\tilde{j}_i)}} \quad \mathbf{0} \quad \dots \quad r' \quad \mathbf{B}_i ) \\
c_i^{(\tilde{j}_i)} &= ( \dots \quad (\mathbf{y}_i^{(1,\tilde{j}_i)}[m]\mathbf{x}_i^{(1,\tilde{j}_i)}[m])_m \quad (\mathbf{y}_i^{(0,\tilde{j}_i)}[m]\mathbf{x}_i^{(0,\tilde{j}_i)}[m])_m \quad \dots \quad \tau_i \quad \mathbf{B}_i^* ) \\
c_{k,i}^{(\text{rep})} &= ( \dots \quad (\mathbf{y}_i^{(1,\tilde{j}_i)}[m]\mathbf{x}_{k,i}^{(\text{rep})}[m])_m \quad (\mathbf{y}_i^{(0,\tilde{j}_i)}[m]\mathbf{x}_{k,i}^{(\text{rep})}[m])_m \quad \dots \quad \tau'_{k,i} \quad \mathbf{B}_i^* )
\end{align*}
$$

Inside a *complexity leveraging* argument, at the same time for all repetitions $\tilde{j}_i \in [\tilde{J}_i]$ of $d_i^{(\tilde{j}_i)}$:

**Game G₄**: (Formal Quotient on coordinates $[2N \cdot \tilde{j}_i + 4, 2N \cdot \tilde{j}_i + 2N + 3]$ in $B_i$)

$$
\begin{align*}
d_{\ell,i}^{(\text{rep})} &= ( \dots \quad \boxed{0} \quad \boxed{0} \quad \dots \quad 0 ) \mathbf{B}_i \\
d_i^{(\tilde{j}_i)} &= ( \dots \quad 1^N \quad 0 \quad \dots \quad r' ) \mathbf{B}_i \\
c_i^{(\tilde{j}_i)} &= ( \dots \quad (\mathbf{y}_i^{(1,\tilde{j}_i)}[m]\mathbf{x}_i^{(1,\tilde{j}_i)}[m])_m \quad (\mathbf{y}_i^{(0,\tilde{j}_i)}[m]\mathbf{x}_i^{(0,\tilde{j}_i)}[m])_m \quad \dots \quad \tau_i ) \mathbf{B}_i^* \\
c_{k,i}^{(\text{rep})} &= ( \dots \quad (\mathbf{y}_i^{(1,\tilde{j}_i)}[m]\mathbf{x}_{k,i}^{(\text{rep})}[m])_m \quad (\mathbf{y}_i^{(0,\tilde{j}_i)}[m]\mathbf{x}_{k,i}^{(\text{rep})}[m])_m \quad \dots \quad \tau'_{k,i} ) \mathbf{B}_i^*
\end{align*}
$$

**Game G₅**: $\tilde{\tau}_i := \tau_i + \frac{1}{r'} \sum_{j \in [\tilde{J}]} (\langle \mathbf{y}^{(\tilde{j}_i)}, \mathbf{x}_i^{(1,\tilde{j}_i)} \rangle - \langle \bar{\mathbf{y}}^{(\tilde{j}_i)}, \mathbf{x}_i^{(0,\tilde{j}_i)} \rangle)$, $\tilde{\tau}'_{k,i} := \tau'_{k,i} + \frac{1}{r'} \sum_{j \in [\tilde{J}]} (\langle \mathbf{y}^{(\tilde{j}_i)}, \mathbf{x}_{k,i}^{(\text{rep})} \rangle - \langle \bar{\mathbf{y}}^{(\tilde{j}_i)}, \mathbf{x}_{k,i}^{(\text{rep})} \rangle)$ (Formal Swapping)

$$
\begin{align*}
d_{\ell,i}^{(\text{rep})} &= ( \dots \quad \boxed{0} \quad \boxed{0} \quad \dots \quad 0 ) \mathbf{B}_i \\
d_i^{(\tilde{j}_i)} &= ( \dots \quad \boxed{0} \quad \boxed{1^N} \quad \dots \quad r' ) \mathbf{B}_i \\
c_i^{(\tilde{j}_i)} &= ( \dots \quad (\mathbf{y}_i^{(1,\tilde{j}_i)}[m]\mathbf{x}_i^{(1,\tilde{j}_i)}[m])_m \quad (\mathbf{y}_i^{(0,\tilde{j}_i)}[m]\mathbf{x}_i^{(0,\tilde{j}_i)}[m])_m \quad \dots \quad \boxed{\tilde{\tau}_i} ) \mathbf{B}_i^* \\
c_{k,i}^{(\text{rep})} &= ( \dots \quad (\mathbf{y}_i^{(1,\tilde{j}_i)}[m]\mathbf{x}_{k,i}^{(\text{rep})}[m])_m \quad (\mathbf{y}_i^{(0,\tilde{j}_i)}[m]\mathbf{x}_{k,i}^{(\text{rep})}[m])_m \quad \dots \quad \boxed{\tilde{\tau}'_{k,i}} ) \mathbf{B}_i^*
\end{align*}
$$

**Game G₆**: (Formal Quotient on coordinates $[2N \cdot \tilde{j}_i + 4, 2N \cdot \tilde{j}_i + 2N + 3]$ in $B_i$)

$$
\begin{align*}
d_{\ell,i}^{(\text{rep})} &= ( \mathbf{y}_{\ell,i}^{(\text{rep})} \quad \mathbf{y}_{\ell,i}^{(\text{rep})'} \quad r_{\ell} \quad 0 \quad \rho_{\ell,i}^{(\text{rep})} \quad \dots \quad \mathbf{0} \quad \mathbf{0} \quad \dots \quad 0 ) \mathbf{B}_i \\
d_i^{(\tilde{j}_i)} &= ( \mathbf{0} \quad \mathbf{0} \quad r \quad 0 \quad \rho_i^{(\tilde{j}_i)} \quad \dots \quad \boxed{\mathbf{0}} \quad \boxed{\mathbf{y}_i^{(0,\tilde{j}_i)}} \quad \dots \quad r' ) \mathbf{B}_i \\
c_i^{(\tilde{j}_i)} &= ( \mathbf{x}_i^{(1,\tilde{j}_i)} \quad \mathbf{x}_i^{(0,\tilde{j}_i)} \quad \sigma_i \quad \pi_i^{(\tilde{j}_i)} \quad 0 \quad \dots \quad \boxed{\mathbf{x}_i^{(1,\tilde{j}_i)}} \quad \boxed{\mathbf{x}_i^{(0,\tilde{j}_i)}} \quad \dots \quad \tilde{\tau}_i ) \mathbf{B}_i^* \\
c_{k,i}^{(\text{rep})} &= ( \mathbf{x}_{k,i}^{(\text{rep})} \quad \mathbf{x}_{k,i}^{(\text{rep})'} \quad \sigma_{k,i} \quad \pi_{k,i}^{(\text{rep})} \quad 0 \quad \dots \quad \boxed{\mathbf{x}_{k,i}^{(\text{rep})}} \quad \boxed{\mathbf{x}_{k,i}^{(\text{rep})}} \quad \dots \quad \tilde{\tau}'_{k,i} ) \mathbf{B}_i^*
\end{align*}
$$

**Game G₇:** (Computational Swapping between $[1, N]$ and $[2N \cdot \tilde{j}_i + 4, 3N \cdot \tilde{j}_i + N + 3]$ in $d_i^{(\tilde{j}_i)}$ using $(2N + 3)$-randomness in $B_i$, by $n \cdot J \cdot N$ DSDH instances)

$$
\begin{align*}
d_{\ell,i}^{(\text{rep})} &= ( \mathbf{y}_{\ell,i}^{(\text{rep})} \quad \mathbf{y}_{\ell,i}^{(\text{rep})'} \quad r_{\ell} \quad 0 \quad \rho_{\ell,i}^{(\text{rep})} \quad \dots \quad \mathbf{0} \quad \mathbf{0} \quad \dots \quad 0 ) \mathbf{B}_i \\
d_i^{(\tilde{j}_i)} &= ( \mathbf{0} \quad \boxed{\mathbf{y}_i^{(0,\tilde{j}_i)}} \quad r \quad 0 \quad \rho_i^{(\tilde{j}_i)} \quad \dots \quad \boxed{0} \quad \boxed{\mathbf{y}_i^{(0,\tilde{j}_i)}} \quad \dots \quad r' ) \mathbf{B}_i \\
c_i^{(\tilde{j}_i)} &= ( \mathbf{x}_i^{(1,\tilde{j}_i)} \quad \mathbf{x}_i^{(0,\tilde{j}_i)} \quad \sigma_i \quad \pi_i^{(\tilde{j}_i)} \quad 0 \quad \dots \quad \mathbf{x}_i^{(1,\tilde{j}_i)} \quad \mathbf{x}_i^{(0,\tilde{j}_i)} \quad \dots \quad \tilde{\tau}_i ) \mathbf{B}_i^* \\
c_{k,i}^{(\text{rep})} &= ( \mathbf{x}_{k,i}^{(\text{rep})} \quad \mathbf{x}_{k,i}^{(\text{rep})'} \quad \sigma_{k,i} \quad \pi_{k,i}^{(\text{rep})} \quad 0 \quad \dots \quad \mathbf{x}_{k,i}^{(\text{rep})} \quad \mathbf{x}_{k,i}^{(\text{rep})'} \quad \dots \quad \tilde{\tau}'_{k,i} ) \mathbf{B}_i^*
\end{align*}
$$

**Game G₈:** Undo G₂, G₁ (Cleaning) – Vectors sampled according to $D_1$.

$$
\mathbf{y}_{\ell,i}^{(\text{rep})} = ( \mathbf{y}_{\ell,i}^{(\text{rep})'} \quad 0 \quad 0 \quad 0 \quad \mathbf{0}^{\tilde{J}} \quad \mathbf{0}^{\tilde{J}} \quad 0 ) \mathbf{B}_i
$$
**Game G₁:** The transition is completely computational and we can target solely all the $\tilde{j}$-th repetitions $\mathbf{d}_{i}^{(j)}$, while leaving all $\mathbf{d}_{\ell, i}^{(\text{rep})}$ unchanged:

$$
\begin{align*}
\mathbf{d}_{\ell, i}^{(\text{rep})} &= (\mathbf{y}_{\ell, i}^{(\text{rep})}, \mathbf{y}_{\ell, i}^{(\text{rep})}', r_{\ell}, 0, \rho_{\ell, i}^{(\text{rep})}, 0^{2N \cdot \tilde{J} + 1})_{\mathbf{B}_i} \\
(\mathbf{d}_{i}^{(j)}) &= (\mathbf{y}_{i}^{(1, \tilde{j})}, \mathbf{0}, r, 0, \rho_{i}^{(j)}, \mathbf{0}^{\tilde{J}}, \mathbf{0}^{\tilde{J}}, [\tau^{\prime}])_{\mathbf{B}_i} \quad i \in [H] \\
(\mathbf{c}_{i}^{(j)}) &= (\mathbf{x}_{i}^{(1, \tilde{j})}, \mathbf{x}_{i}^{(0, \tilde{j})}, \sigma_{i}, \pi_{i}^{(j)}, 0, \mathbf{0}^{\tilde{J}}, \mathbf{0}^{\tilde{J}}, [\tau_{i}])_{\mathbf{B}_{i}^{*}} \quad i \in [H]^{j} \\
(\mathbf{c}_{k, i}^{(\text{rep})}) &= (\mathbf{x}_{k, i}^{(\text{rep})}, \mathbf{x}_{k, i}^{(\text{rep})}, \sigma_{k, i}, \pi_{k, i}^{(\text{rep})}, 0, \mathbf{0}^{\tilde{J}}, \mathbf{0}^{\tilde{J}}, [\tau'_{k, i}])_{\mathbf{B}_{i}^{*}} \quad i \in [H], k \in [K].
\end{align*}
$$

where $r' \leftarrow \mathbb{Z}_q^*$ and for all $j \in [J]$, the secret shareings $(\tau_i)_i$ and $(\tau'_{k,i})_i$ in $\mathbf{c}_i$-vectors satisfies: $\sum_{i=1}^H \tau_i = \sum_{i=1}^H \tau'_{k,i} = 0$, for $k \in [K]$. We emphasize that the same share $\tau_i$ is used across all repetitions $\mathbf{c}_i^{(j)}$ for a given $i$. Moreover, for the $\mathbf{d}_{\ell,i}^{(\text{rep})}$-vectors we do not introduce additional randomness such as $r'$, which is enabled by the current computational change where we can compute vectors in $\mathbf{B}_i$ (i.e. $\mathbf{d}_{\ell,i}^{(\text{rep})}$-vectors versus $\mathbf{d}_{i}^{(j')}$ vectors) differently.

We proceed in two steps:

**Game G$_{0.1}$:** We first use the subspace-indistinguishability to introduce $r' \leftarrow \mathbb{Z}_q^*$ at coordinate $2N + 2N \cdot \tilde{J} + 4$ of $\mathbf{d}_i^{(j)}$, while keeping $\mathbf{c}_i^{(j)}[2N + 2N \cdot \tilde{J} + 4] = \mathbf{d}_{\ell,i}^{(\text{rep})}[2N + 2N \cdot \tilde{J} + 4] = \mathbf{c}_{k,i}^{(\text{rep})}[2N + 2N \cdot \tilde{J} + 4] = 0$. Given a DSDH instance ($\llbracket a \rrbracket_1, \llbracket b \rrbracket_1, \llbracket c \rrbracket_1$) in $\mathbb{G}_1$ where $\delta := c - ab$ is either 0 or 1, the basis changing matrices are:

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

All vectors changed under these bases are secret. We compute $\mathbf{B}_i$ using $\llbracket a \rrbracket_1$ and write the $\mathbf{d}$-vectors as follows:

$$
\begin{align*}
\mathbf{d}_{i}^{(j)} &= (\mathbf{y}_{i}^{(j)}, \mathbf{0}, r, 0, \rho_{i}, \mathbf{0}^{\tilde{J}}, \mathbf{0}^{\tilde{J}}, 0)_{\mathbf{B}_{i}} + (\mathbf{0}, \mathbf{0}, br', 0, 0, \mathbf{0}^{\tilde{J}}, \mathbf{0}^{\tilde{J}}, cr')_{\mathbf{H}_{i}} \\
&= (\mathbf{y}_{i}^{(j)}, \mathbf{0}, [r + br'], 0, \rho_{i}, \mathbf{0}^{\tilde{J}}, \mathbf{0}^{\tilde{J}}, [\delta r'])_{\mathbf{B}_{i}} \\
\mathbf{d}_{\ell, i}^{(\text{rep})} &= (\mathbf{y}_{\ell, i}^{(\text{rep})}, \mathbf{y}_{\ell, i}^{(\text{rep})}', r_{\ell}, 0, \rho_{\ell, i}, \mathbf{0}^{\tilde{J}}, \mathbf{0}^{\tilde{J}}, 0)_{\mathbf{B}_{i}}.
\end{align*}
$$

We cannot compute $\mathbf{b}_{i,2N+1}^*$ but can write the $\mathbf{c}$-vectors in $\mathbf{H}^*$ and observe that they stay invariant in $\mathbf{B}_i^*$ as the $(2N + 2N \cdot \tilde{J} + 4)$-th coordinate is 0:

$$
\begin{align*}
\mathbf{c}_i^{(j)} &= (\mathbf{x}_i^{(1,j)}, \mathbf{x}_i^{(0,j)}, \sigma_i, \pi_i^{(j)}, 0, \mathbf{0}^{\tilde{J}}, \mathbf{0}^{\tilde{J}}, 0)_{\mathbf{H}_i^*} \\
&= (\mathbf{x}_i^{(1,j)}, \mathbf{x}_i^{(0,j)}, \sigma_i, \pi_i^{(j)}, 0, \mathbf{0}^{\tilde{J}}, \mathbf{0}^{\tilde{J}}, 0)_{\mathbf{B}_i^*} \\
\mathbf{c}_{k,i}^{(\text{rep})} &= (\mathbf{x}_{k,i}^{(\text{rep})}, \mathbf{x}_{k,i}^{(\text{rep})}, \sigma_{k,i}, \pi_{k,i}, 0, \mathbf{0}^{\tilde{J}}, \mathbf{0}^{\tilde{J}}, 0)_{\mathbf{H}_i^*} \\
&= (\mathbf{x}_{k,i}^{(\text{rep})}, \mathbf{x}_{k,i}^{(\text{rep})}, \sigma_{k,i}, \pi_{k,i}, 0, \mathbf{0}^{\tilde{J}}, \mathbf{0}^{\tilde{J}}, 0)_{\mathbf{B}_i^*}.
\end{align*}
$$

If $\delta = 0$ we are in $G_0$ else we are in $G_{0.1}$, while updating $r$ to $r + br'^8$. The difference in advantages is $|\text{Pr}[G_{0.1} = 1] - \text{Pr}[G_0 = 1]| \le 2 \cdot \text{Adv}_{\mathbb{G}_1}^{\text{DDH}}(1^\lambda)$.

<footnote>$^8$It is thanks to the randomness of $r \leftarrow \mathbb{Z}_q$ that allows us to update $br'$ without changing the distribution. When applying this swapping lemma for our FH-DMCFE scheme, this random $r$ is provided by the RO while hashing the tags.</footnote>
**Game G<sub>0.2</sub>:** We use DSDH in $\mathbb{G}_2$ to introduce any chosen secret sharings $(\tau_i)_{i \in [H]}$ and $(\tau'_{k,i})_{i \in [H]}$ of 0, i.e. $\sum_{i=1}^H \tau_i = \sum_{i=1}^H \tau'_{k,i} = 0$, such that $\tau_i, \tau'_{k,i} \neq 0$ for all $i$, for every $k \in [K]$. The secret sharings do not depend on the repetitions. Given a DSDH instance ($\llbracket a \rrbracket_2$, $\llbracket b \rrbracket_2$, $\llbracket c \rrbracket_2$) 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 & 0 \\ -a & 1 \end{bmatrix}_{2N+1,2N+2N \cdot \tilde{J}+4} \cdot \mathbf{H}_i; \quad \mathbf{B}_i^* = \begin{bmatrix} 1 & a \\ 0 & 1 \end{bmatrix}_{2N+1,2N+2N \cdot \tilde{J}+4} \cdot \mathbf{H}_i^* $$

All vectors changed under these bases are secret. We compute $\mathbf{B}_i^*$ using $\llbracket a \rrbracket_2$ and write the c-vectors as follows:

$$
\begin{align*}
\mathbf{c}_i^{(j)} &= (\mathbf{x}_i^{(1,j)}, \mathbf{x}_i^{(0,j)}, \sigma_i, \pi_i^{(j)}, 0, \mathbf{0}^{\tilde{J}}, \mathbf{0}^{\tilde{J}}, 0)_{\mathbf{B}_i^*} \\
&\quad + (\mathbf{0}, \mathbf{0}, b\tau_i, 0, 0, \mathbf{0}^{\tilde{J}}, \mathbf{0}^{\tilde{J}}, c\tau_i)_{\mathbf{H}_i^*} \\
&= (\mathbf{x}_i^{(1,j)}, \mathbf{x}_i^{(0,j)}, [\sigma_i + b\tau_i], \pi_i^{(j)}, 0, \mathbf{0}^{\tilde{J}}, \mathbf{0}^{\tilde{J}}, [\delta\tau_i])_{\mathbf{B}_i^*} \\
\mathbf{c}_{k,i}^{(\text{rep})} &= (\mathbf{x}_{k,i}^{(\text{rep})}, \mathbf{x}_{k,i}^{(\text{rep})}, \sigma_{k,i}, \pi_{k,i}^{(\text{rep})}, 0, \mathbf{0}^{\tilde{J}}, \mathbf{0}^{\tilde{J}}, 0)_{\mathbf{B}_i^*} \\
&\quad + (\mathbf{0}, \mathbf{0}, b\tau'_{k,i}, 0, 0, \mathbf{0}^{\tilde{J}}, \mathbf{0}^{\tilde{J}}, c\tau'_{k,i})_{\mathbf{H}_i^*} \\
&= (\mathbf{x}_{k,i}^{(\text{rep})}, \mathbf{x}_{k,i}^{(\text{rep})}, [\sigma_{k,i} + b\tau'_{k,i}], \pi_{k,i}^{(\text{rep})}, 0, \mathbf{0}^{\tilde{J}}, \mathbf{0}^{\tilde{J}}, [\delta\tau'_{k,i}])_{\mathbf{B}_i^*} .
\end{align*}
$$

For each $j \in [J]$, the secret shares $(\sigma_i)_{i=1}^H$ are updated to $(\sigma_i + b\tau_i)_{i=1}^H$ and still satisfy:

$$ \sum_{i=1}^{H} (\sigma_i + b\tau_i) = \left(\sum_{i=1}^{H} \sigma_i\right) + b \left(\sum_{i=1}^{H} \tau_i\right) = R $$

because $(\tau_i)_{i=1}^H$ is a secret sharing of 0. Similarly, $(\sigma_{k,i})_{i=1}^H$ are updated to $(\sigma_{k,i} + b\tau'_{k,i})_{i=1}^H$ and stay shares of $R_k$. We cannot compute $\mathbf{b}_{i,2N+2N \cdot \tilde{J}+4}$ but can write the d-vectors in $\mathbf{H}_i$, for $r'', r_\ell \leftarrow \mathbb{Z}_q, r' \leftarrow \mathbb{Z}_q^*$:

$$
\begin{align*}
\mathbf{d}_i^{(\tilde{J})} &= (\mathbf{y}_i^{(1,\tilde{J})}, \mathbf{0}, r'', 0, \rho_i, \mathbf{0}^{\tilde{J}}, \mathbf{0}^{\tilde{J}}, r')_{\mathbf{H}_i} \\
&= (\mathbf{y}_i^{(1,\tilde{J})}, \mathbf{0}, r'' + ar', 0, \rho_i, \mathbf{0}^{\tilde{J}}, \mathbf{0}^{\tilde{J}}, r')_{\mathbf{B}_i} \\
\mathbf{d}_{\ell,i}^{(\text{rep})} &= (\mathbf{y}_{\ell,i}^{(\text{rep})}, \mathbf{y}_{\ell,i}^{(\text{rep})'}, r_\ell, 0, \rho_{\ell,i}, \mathbf{0}^{\tilde{J}}, \mathbf{0}^{\tilde{J}}, 0)_{\mathbf{H}_i} \\
&= (\mathbf{y}_{\ell,i}^{(\text{rep})}, \mathbf{y}_{\ell,i}^{(\text{rep})'}, r_\ell, 0, \rho_{\ell,i}, \mathbf{0}^{\tilde{J}}, \mathbf{0}^{\tilde{J}}, 0)_{\mathbf{B}_i},
\end{align*}
$$

while simulating $r := r'' + ar'$ perfectly uniformly at random in $\mathbb{Z}_q$. If $\delta = 0$ we are in $G_{0.1}$, else we are in $G_{0.2} = G_1$. The difference in advantages is $|\text{Pr}[G_{0.2} = 1] - \text{Pr}[G_{0.1} = 1]| \le 2 \cdot \text{Adv}_{\mathbb{G}_2}^{\text{DDH}}(1^\lambda)$.

After $G_{0.2} = G_1$, the vectors are now:

$$
\begin{align*}
\mathbf{d}_{\ell,i}^{(\text{rep})} &= (\mathbf{y}_{\ell,i}^{(\text{rep})}, \mathbf{x}_{\ell,i}^{(\text{rep})}, r_\ell, 0, \rho_{\ell,i}, \mathbf{0}^{\tilde{J}}, \mathbf{0}^{\tilde{J}}, 0)_{\mathbf{B}_i} \\
\mathbf{d}_i^{(\tilde{J})} &= (\mathbf{y}_i^{(1,\tilde{J})}, \mathbf{0}, [r], 0, \rho_i, \mathbf{0}^{\tilde{J}}, \mathbf{0}^{\tilde{J}}, r')_{\mathbf{B}_i} \\
\mathbf{c}_i^{(j)} &= (\mathbf{x}_i^{(1,j)}, \mathbf{x}_i^{(0,j)}, [\sigma_i], \pi_i^{(j)}, 0, 0^{2N \cdot \tilde{J}}, [\tau_i])_{\mathbf{B}_i^*} \\
\mathbf{c}_{k,i}^{(\text{rep})} &= (\mathbf{x}_{k,i}^{(\text{rep})}, \mathbf{x}_{k,i}^{(\text{rep})}, [\sigma_{k,i}], \pi_{k,i}, 0, 0^{2N \cdot \tilde{J}}, [\tau'_{k,i}])_{\mathbf{B}_i^*}
\end{align*}
$$

and in total $|\text{Pr}[G_1 = 1] - \text{Pr}[G_0 = 1]| \le 2 \cdot \text{Adv}_{\mathbb{G}_2}^{\text{DDH}}(1^\lambda) + 2 \cdot \text{Adv}_{\mathbb{G}_1}^{\text{DDH}}(1^\lambda)$.
**Game G₂:** We perform a formal duplication on all **c-vectors**:

$$ 
\begin{align*}
(\mathbf{c}_i^{(j)} &= (\mathbf{x}_i^{(1,j)}, \mathbf{x}_i^{(0,j)}, \sigma_i, \pi_i^{(j)}, 0, \left(\boxed{\mathbf{x}_i^{(1,j)}, \mathbf{x}_i^{(0,j)}}\right)^{\tilde{J}}, \tau_i)_{\mathbf{B}_i^*})_{i \in [H]}^{j \in [J]} \\
(\mathbf{c}_{k,i}^{(\text{rep})} &= (\mathbf{x}_{k,i}^{(\text{rep})}, \mathbf{x}_{k,i}^{(\text{rep})}, \sigma_{k,i}, \pi_{k,i}^{(\text{rep})}, 0, \left(\boxed{\mathbf{x}_{k,i}^{(\text{rep})}, \mathbf{x}_{k,i}^{(\text{rep})}}\right)^{\tilde{J}}, \tau'_{k,i})_{\mathbf{B}_i^*})_{i \in [H], k \in [K]}^{\text{rep} \in [J]}
\end{align*}
$$

For $\mathbf{c}_i^{(j)}$ the coordinates $[2N \cdot \tilde{j} + 4, 2N \cdot \tilde{j} + N + 3]$, $[2N \cdot \tilde{j} + N + 4, 2N \cdot \tilde{j} + 2N + 3]$ change. We perform a formal basis change to duplicate $(\mathbf{x}_i^{(1,j)}, \mathbf{x}_i^{(0,j)})$ (respectively $(\mathbf{x}_{k,i}^{(\text{rep})}, \mathbf{x}_{k,i}^{(\text{rep})})$) from coordinates $[1, N]$, $[N + 1, 2N]$ to $[2N \cdot \tilde{j} + 4, 2N \cdot \tilde{j} + N + 3]$, $[2N \cdot \tilde{j} + N + 4, 2N \cdot \tilde{j} + 2N + 3]$ of $\mathbf{c}_i^{(j)}$ (respectively of $\mathbf{c}_{k,i}^{(\text{rep})}$), for all $\tilde{j} \in [\tilde{J}]$. We emphasize that the pair $(\mathbf{x}_i^{(1,j)}, \mathbf{x}_i^{(0,j)})$ (respectively $(\mathbf{x}_{k,i}^{(\text{rep})}, \mathbf{x}_{k,i}^{(\text{rep})})$) are duplicated $\tilde{J}$ times into $\tilde{J}$ separated blocks $[2N \cdot \tilde{j} + 4, 2N \cdot \tilde{j} + N + 3]$, $[2N \cdot \tilde{j} + N + 4, 2N \cdot \tilde{j} + 2N + 3]$ in $\mathbf{c}_i^{(j)}$ (respectively in $\mathbf{c}_{k,i}^{(\text{rep})}$). The bases are changed following using the following matrices (we denote $B_i[\text{row}, \text{col}]$ the entry at row $\text{row}$ and column $\text{col}$ of $B_i$)

$$ B_i = \begin{cases} B_i[\text{row}, \text{col}] = 1 & \text{if } \text{row} = \text{col} \\ B_i[\text{row}, \text{col}] = 1 & \text{if } (\text{row}, \text{col}) \in \{(2N\tilde{j} + 4 + d, 1 + d) : d \in [0, N-1], j \in [\tilde{J}]\} \\ B_i[\text{row}, \text{col}] = 1 & \text{if } (\text{row}, \text{col}) \in \{(2N\tilde{j} + N + 4 + d, N + 1 + d) : d \in [0, N-1], j \in [\tilde{J}]\} \\ B_i[\text{row}, \text{col}] = 0 & \text{otherwise} \end{cases} $$

$$ B'_i := (B_i^{-1})^\top \qquad \mathbf{B}_i = B_i \cdot \mathbf{H}_i; \quad \mathbf{B}_i^* = B'_i \cdot \mathbf{H}_i^* . $$

We write the vectors as follows, observing that the **d-vectors** stay invariant because for all $\tilde{j}, \text{rep} \in [\tilde{J}]$, their coordinates $[2N \cdot \tilde{j} + 4, 2N \cdot \tilde{j} + N + 3]$, $[2N \cdot \tilde{j} + N + 4, 2N \cdot \tilde{j} + 2N + 3]$ are all 0 and the duplication is done correctly for the **c-vectors**:

$$ 
\begin{align*}
\mathbf{d}_{\ell,i}^{(\text{rep})} &= (\mathbf{y}_{\ell,i}^{(\text{rep})}, \mathbf{y}_{\ell,i}^{(\text{rep})'}, r_{\ell}, 0, \rho_{\ell,i}, \mathbf{0}^{\tilde{J}}, \mathbf{0}^{\tilde{J}}, 0)_{\mathbf{H}_i} \\
&= (\mathbf{y}_{\ell,i}^{(\text{rep})}, \mathbf{y}_{\ell,i}^{(\text{rep})'}, r_{\ell}, 0, \rho_{\ell,i}, \mathbf{0}^{\tilde{J}}, \mathbf{0}^{\tilde{J}}, 0)_{\mathbf{B}_i} \\
\mathbf{d}_i^{(\tilde{j})} &= (\mathbf{y}_i^{(1,\tilde{j})}, 0, r, 0, \rho_i, \mathbf{0}^{\tilde{J}}, \mathbf{0}^{\tilde{J}}, r')_{\mathbf{H}_i} \\
&= (\mathbf{y}_i^{(1,\tilde{j})}, 0, r, 0, \rho_i, \mathbf{0}^{\tilde{J}}, \mathbf{0}^{\tilde{J}}, r')_{\mathbf{B}_i} \\
\mathbf{c}_i^{(\tilde{j})} &= (\mathbf{x}_i^{(1,\tilde{j})}, \mathbf{x}_i^{(0,\tilde{j})}, \sigma_i, \pi_i^{(\tilde{j})}, 0, \mathbf{0}^{\tilde{J}}, \mathbf{0}^{\tilde{J}}, \tau_i)_{\mathbf{H}_i^*} \\
&= (\mathbf{x}_i^{(1,\tilde{j})}, \mathbf{x}_i^{(0,\tilde{j})}, \sigma_i, \pi_i^{(\tilde{j})}, 0, \dots, \boxed{\mathbf{x}_i^{(1,\tilde{j})}, \mathbf{x}_i^{(0,\tilde{j})}}, \dots, \tau_i)_{\mathbf{B}_i^*} \\
\mathbf{c}_{k,i}^{(\text{rep})} &= (\mathbf{x}_{k,i}^{(\text{rep})}, \mathbf{x}_{k,i}^{(\text{rep})}, \sigma_{k,i}, \pi_{k,i}, 0, \mathbf{0}^{\tilde{J}}, \mathbf{0}^{\tilde{J}}, \tau'_{k,i})_{\mathbf{H}_i^*} \\
&= (\mathbf{x}_{k,i}^{(\text{rep})}, \mathbf{x}_{k,i}^{(\text{rep})}, \sigma_{k,i}, \pi_{k,i}, 0, \dots, \boxed{\mathbf{x}_{k,i}^{(\text{rep})}, \mathbf{x}_{k,i}^{(\text{rep})}}, \dots, \tau'_{k,i})_{\mathbf{B}_i^*} .
\end{align*}
$$

We are in $\mathcal{G}_1$ in bases $(\mathbf{H}_i, \mathbf{H}_i^*)$ and in $\mathcal{G}_2$ in bases $(\mathbf{B}_i, \mathbf{B}_i^*)$. The change is formal and we have $\text{Pr}[\mathcal{G}_2 = 1] = \text{Pr}[\mathcal{G}_1 = 1]$. Dually, the destination coordinates in the **d-vectors** are all 0 hence they stay unchanged.

**Game G₃:** For each $\tilde{j} \in [\tilde{J}]$, we perform a computational swap between $[1, N]$ and $[2N \cdot \tilde{j} + 4, 2N \cdot \tilde{j} + N + 3]$ in $\mathbf{d}_i^{(\tilde{j})}$ using $(2N + 3)$-randomness. We need $n \cdot \tilde{J} \cdot N$ DSDH instances ($[\mathbf{a}_{i,z}^{(\tilde{j})}]_1, [\mathbf{b}_{i,z}^{(\tilde{j})}]_1, [\mathbf{c}_{i,z}^{(\tilde{j})}]_1$ in $\mathcal{G}_1$ where $\delta_{i,z}^{(\tilde{j})} := c_{i,z}^{(\tilde{j})} - a_{i,z}^{(\tilde{j})} b_{i,z}^{(\tilde{j})}$ is either 0 or $\mathbf{y}_i^{(1,\tilde{j})}[z]$, for $z \in [N], \tilde{j} \in [J], i \in [n]$. The basis changes for $(\mathbf{B}_i, \mathbf{B}_i^*)$ will use $([\mathbf{a}_{i,z}^{(\tilde{j})}]_1, [\mathbf{b}_{i,z}^{(\tilde{j})}]_1, [\mathbf{c}_{i,z}^{(\tilde{j})}]_1)$ for $z \in [N], \tilde{j} \in [J]$.

The computation on the **c-vectors** can be done thanks to the fact that we have $\tilde{J}$ separate $N \times N$ blocks in the matrix to incorporate the separate $\tilde{J} \cdot N$ DSDH instances. The swaps are possible thanks to the pairs $(\mathbf{x}_i^{(1,j)}, \mathbf{x}_i^{(0,j)})$ (respectively $(\mathbf{x}_{k,i}^{(\text{rep})}, \mathbf{x}_{k,i}^{(\text{rep})})$ in $\mathbf{c}_i^{(j)}$ (respectively in $\mathbf{c}_{k,i}^{(\text{rep})}$) that are resulted from previous game G₂.
It is important that the change is computational using DDH in $\mathbb{G}_1$, therefore we can write the vectors in appropriate bases using DSDH while targeting all the repetitions of $(\mathbf{d}_i^{(j)})_i$. For instance, for a given $\tilde{j}$, we compute $\mathbf{B}_i$ using $\llbracket a \rrbracket_1$ and write the $\mathbf{d}$-vectors as follows:

$$
\begin{align*}
\mathbf{d}_i^{(\tilde{j})} &= \underbrace{(0, \dots, 0, \mathbf{y}_i^{(1, \tilde{j})}[z], \dots, \mathbf{y}_i^{(1, \tilde{j})}[N], 0, r, 0, \rho_i, 0, \dots, 0, \mathbf{y}_i^{(1, \tilde{j})}[1], \dots, \mathbf{y}_i^{(1, \tilde{j})}[z-1], 0, \dots, 0}_{\text{first } (z-1)\text{-th coordinates are 0}} \underbrace{\text{last } (N-z+1)\text{-th coordinates are 0}}_{\text{z-th coordinates among } N} \\
&\quad + \underbrace{(0, \dots, 0, -c_{i,z}^{(\tilde{j})}, 0, \dots, 0, 0, 0, 0, b_{i,z}^{(\tilde{j})}, 0, \dots, 0}_{\text{z-th coordinates among } N} \underbrace{0, \dots, 0, c_{i,z}^{(\tilde{j})}, 0, \dots, 0, 0, \dots, 0}_{\text{z-th coordinates among } N} \mathbf{H}_i \\
&= \underbrace{(0, \dots, 0, \underbrace{\mathbf{y}_i^{(1, \tilde{j})}[z] - \delta_{i,z}^{(\tilde{j})}}_{\text{first } (z-1)\text{-th coordinates are 0}}, \dots, \mathbf{y}_i^{(1, \tilde{j})}[N],}_{\text{first } (z-1)\text{-th coordinates are 0}} \\
&\quad \underbrace{0, r, 0, \underbrace{\rho_i + b_{i,z}^{(\tilde{j})}}_{\text{last } (N-z)\text{-th coordinates are 0}}, 0, \dots, 0, \underbrace{\mathbf{y}_i^{(1, \tilde{j})}[1], \dots, \mathbf{y}_i^{(1, \tilde{j})}[z-1], \underbrace{\delta_{i,z}^{(\tilde{j})}}_{\text{last } (N-z)\text{-th coordinates are 0}}, \dots, 0, 0, \dots, 0, r')}_{\mathbf{B}_i}
\end{align*}
$$

$$
\mathbf{d}_{\ell, i}^{(\text{rep})} = (\mathbf{y}_{\ell, i}^{(\text{rep})}, \mathbf{y}_{\ell, i}^{(\text{rep})}', r_{\ell}, 0, \rho_{\ell, i}, \mathbf{0}^{\tilde{j}}, \mathbf{0}^{\tilde{j}}, 0)_{\mathbf{B}_i}
$$

where the coordinates $(0, \dots, 0)$ put in $\mathbf{H}_i$ will not be affected by the corresponding
blocks in the basis matrix.

For all other c-vectors their coordinates remain intact and are 0.

$$
\begin{align*}
\mathbf{c}_i^{(j)} &= (\mathbf{x}_i^{(1,j)}, \mathbf{x}_i^{(0,j)}, \sigma_i, \pi_i^{(j)}, 0, \dots, \mathbf{x}_i^{(1,j)}, \mathbf{x}_i^{(0,j)}, \dots, \tau_i)_{\mathbf{B}_i^*} \\
\mathbf{c}_{k,i}^{(\text{rep})} &= (\mathbf{x}_{k,i}^{(\text{rep})}, \mathbf{x}_{k,i}^{(\text{rep})}, \sigma_{k,i}, \pi_{k,i}^{(\text{rep})}, 0, \dots, \mathbf{x}_{k,i}^{(\text{rep})}, \mathbf{x}_{k,i}^{(\text{rep})}, \dots, \tau_{k,i}^{\prime})_{\mathbf{B}_i^*} .
\end{align*}
$$

$$
\text{The security loss is } 2 \cdot n \cdot \tilde{J} \cdot N \cdot \text{Adv}_{\mathbb{G}_1, \mathbb{G}_2}^{\text{SXDH}}(1^{\lambda}).
$$

The vectors, when we arrive at $\mathbb{G}_3$, are of the form:

$$
\begin{align*}
\mathbf{d}_{\ell,i}^{(\text{rep})} &= (\mathbf{y}_{\ell,i}^{(\text{rep})}, \mathbf{y}_{\ell,i}^{(\text{rep})}', r_{\ell}, 0, \rho_{\ell,i}^{(\text{rep})}, \dots, \mathbf{0}, \mathbf{0}, \dots, \mathbf{0})_{\mathbf{B}_i} \\
\mathbf{d}_i^{(\tilde{j})} &= (\mathbf{0}, \mathbf{0}, r, 0, [\rho_i], \dots, [\mathbf{y}_i^{(1,\tilde{j})}], \mathbf{0}, \dots, r')_{\mathbf{B}_i} \\
\mathbf{c}_i^{(\tilde{j})} &= (\mathbf{x}_i^{(1,\tilde{j})}, \mathbf{x}_i^{(0,\tilde{j})}, \sigma_i, \pi_i^{(\tilde{j})}, 0, \dots, \mathbf{x}_i^{(1,\tilde{j})}, \mathbf{x}_i^{(0,\tilde{j})}, \dots, \tau_i)_{\mathbf{B}_i^*} \\
\mathbf{c}_{k,i}^{(\text{rep})} &= (\mathbf{x}_{k,i}^{(\text{rep})}, \mathbf{x}_{k,i}^{(\text{rep})}, \sigma_{k,i}, \pi_{k,i}^{(\text{rep})}, 0, \dots, \mathbf{x}_{k,i}^{(\text{rep})}, \mathbf{x}_{k,i}^{(\text{rep})}, \dots, \tau_{k,i}^{\prime})_{\mathbf{B}_i^*},
\end{align*}
$$

where for each $j \in [J]$, $(\tau_i)_{i=1}^H, (\tau'_{k,i})_{i=1}^H$ are random secret sharings of 0, with $\tau_i, \tau'_{k,i} \neq 0$
for all $i$, and $r' \stackrel{\$}{\leftarrow} \mathbb{Z}_q^*$.
Our goal in the next three games $G_4, G_5, G_6$ is to swap $\mathbf{y}_i^{(1,\tilde{j})}$ from
coordinates $[2N \cdot \tilde{j} + 4, 2N \cdot \tilde{j} + N + 3]$ to $\mathbf{y}_i^{(0,\tilde{j})}$ coordinates $[2N \cdot \tilde{j} + N + 4, 2N \cdot \tilde{j} + 2N + 3]$
of $\mathbf{d}_i^{(\tilde{j})}$, for all $i \in [H]$. The main idea is to consider the selective version $\mathbf{G}_t^*$ for $t \in \{4, 5, 6\}$,
where the values $(\mathbf{y}_i^{(1,\tilde{j})}[k], \mathbf{y}_i^{(0,\tilde{j})}[k], \mathbf{x}_i^{(1,\tilde{j})}, \mathbf{x}_i^{(0,\tilde{j})})_{i \in [H], k \in [N]}$ are guessed in advance. We then
use formal argument for the transitions $\mathbf{G}_t^* \to \mathbf{G}_{t+1}^*$ for $j \in \{3, 4, 5\}$ to obtain

$$
\mathrm{Pr}[\mathbb{G}_3^* = 1] = \mathrm{Pr}[\mathbb{G}_4^* = 1] = \mathrm{Pr}[\mathbb{G}_5^* = 1] = \mathrm{Pr}[\mathbb{G}_6^* = 1]. \quad (12)
$$

In the end, we use a *complexity leveraging* argument to conclude that thanks to (12), we
have $\mathrm{Pr}[\mathbb{G}_3 = 1] = \mathrm{Pr}[\mathbb{G}_4 = 1] = \mathrm{Pr}[\mathbb{G}_5 = 1] = \mathrm{Pr}[\mathbb{G}_6 = 1]$.

Temporarily, the index $i$ is put back to emphasize that $j_i, \tilde{j}_i$ might differ among different $i$. For the sequence $\mathbb{G}_3 \to \mathbb{G}_6$, we make a guess for the values $(\mathbf{y}_i^{(1,\tilde{j}_i)}, \mathbf{y}_i^{(0,\tilde{j}_i)}, \mathbf{x}_i^{(1,j_i)}, \mathbf{x}_i^{(0,j_i)})$ with $j_i \in [J_i], \tilde{j}_i \in [\tilde{J}_i], i \in [H]$, choose $r' \stackrel{\$}{\leftarrow} \mathbb{Z}_q^*$, random secret sharings $(\tau_i, \tau'_{k,i}, \tilde{\tau}_i, \tilde{\tau}'_{k,i})_{i=1}^H$ of 0 for each $j_i \in [J_i]$, with $\tau_i, \tau'_{k,i} \neq 0$ for all $i$. We define the event $E$ that the guess is correct on $(\mathbf{y}_i^{(1,\tilde{j}_i)}, \mathbf{y}_i^{(0,\tilde{j}_i)}, \mathbf{x}_i^{(1,j_i)}, \mathbf{x}_i^{(0,j_i)})_{j_i \in [J_i], \tilde{j}_i \in [\tilde{J}_i]}$ and for any $j_i \in [J_i]$

$$
\begin{align*}
\tilde{\tau}_i - \tau_i &= \frac{1}{r'} \sum_{\tilde{j}_i \in [\tilde{J}_i]} \left( \langle \mathbf{y}_i^{(1, \tilde{j}_i)}, \mathbf{x}_i^{(1, j_i)} \rangle - \langle \mathbf{y}_i^{(0, \tilde{j}_i)}, \mathbf{x}_i^{(0, j_i)} \rangle \right) \\
\tilde{\tau}'_{k, i} - \tau'_{k, i} &= \frac{1}{r'} \sum_{\tilde{j}_i \in [\tilde{J}_i]} \left( \langle \mathbf{y}_i^{(1, \tilde{j}_i)}, \mathbf{x}_i^{(\text{rep})} \rangle - \langle \mathbf{y}_i^{(0, \tilde{j}_i)}, \mathbf{x}_i^{(\text{rep})} \rangle \right) .
\end{align*}
$$
Before elaborating the games, we start by showing an important property. The admissibility condition 2 in Definition 5 gives $\sum_{i=1}^{H} \langle \mathbf{y}_i^{(1,j_i)}, \mathbf{x}_i^{(1,j_i)} \rangle = \sum_{i=1}^{H} \langle \mathbf{y}_i^{(0,j_i)}, \mathbf{x}_i^{(0,j_i)} \rangle$ for any $\tilde{j}_i \in [\tilde{J}_i], j_i \in [J_i]$. Suppose that there exists $\emptyset \neq I' \subseteq [H]$ and $j'_i, j''_i \in [J]$ so that

$$ \sum_{i \in I'} \langle \mathbf{y}_i^{(1, \tilde{j}_i)}, \mathbf{x}_i^{(1, \tilde{j}'_i)} \rangle - \langle \mathbf{y}_i^{(0, \tilde{j}_i)}, \mathbf{x}_i^{(0, \tilde{j}'_i)} \rangle \neq \sum_{i \in I'} \langle \mathbf{y}_i^{(1, \tilde{j}_i)}, \mathbf{x}_i^{(1, \tilde{j}''_i)} \rangle - \langle \mathbf{y}_i^{(0, \tilde{j}_i)}, \mathbf{x}_i^{(0, \tilde{j}''_i)} \rangle, $$

while

$$ \sum_{i \in [H] \setminus I'} \langle \mathbf{y}_i^{(1, \tilde{j}_i)}, \mathbf{x}_i^{(1, \tilde{j}'_i)} \rangle - \langle \mathbf{y}_i^{(0, \tilde{j}_i)}, \mathbf{x}_i^{(0, \tilde{j}'_i)} \rangle = \sum_{i \in [H] \setminus I'} \langle \mathbf{y}_i^{(1, \tilde{j}_i)}, \mathbf{x}_i^{(1, \tilde{j}''_i)} \rangle - \langle \mathbf{y}_i^{(0, \tilde{j}_i)}, \mathbf{x}_i^{(0, \tilde{j}''_i)} \rangle. $$

Summing both sides give an inequality

$$ \sum_{i \in I'} \langle \mathbf{y}_i^{(1, \tilde{j}_i)}, \mathbf{x}_i^{(1, \tilde{j}'_i)} \rangle - \langle \mathbf{y}_i^{(0, \tilde{j}_i)}, \mathbf{x}_i^{(0, \tilde{j}'_i)} \rangle + \sum_{i \in [H] \setminus I'} \langle \mathbf{y}_i^{(1, \tilde{j}_i)}, \mathbf{x}_i^{(1, \tilde{j}'_i)} \rangle - \langle \mathbf{y}_i^{(0, \tilde{j}_i)}, \mathbf{x}_i^{(0, \tilde{j}'_i)} \rangle \\ \neq \sum_{i \in I'} \langle \mathbf{y}_i^{(1, \tilde{j}_i)}, \mathbf{x}_i^{(1, \tilde{j}''_i)} \rangle - \langle \mathbf{y}_i^{(0, \tilde{j}_i)}, \mathbf{x}_i^{(0, \tilde{j}''_i)} \rangle + \sum_{i \in [H] \setminus I'} \langle \mathbf{y}_i^{(1, \tilde{j}_i)}, \mathbf{x}_i^{(1, \tilde{j}''_i)} \rangle - \langle \mathbf{y}_i^{(0, \tilde{j}_i)}, \mathbf{x}_i^{(0, \tilde{j}''_i)} \rangle $$

that contradicts condition 2 in Definition 5. The same can be argued w.r.t $\mathbf{x}_i^{(\text{rep})}$. Therefore, for each $i \in [H]$, for all $\tilde{j}_i \in [\tilde{J}], j_i \in [J]$, the terms

$$ \left\{ \begin{array}{l} \langle \mathbf{y}_i^{(1, \tilde{j}_i)}, \mathbf{x}_i^{(1, \tilde{j}_i)} \rangle - \langle \mathbf{y}_i^{(0, \tilde{j}_i)}, \mathbf{x}_i^{(0, \tilde{j}_i)} \rangle \\ \langle \mathbf{y}_i^{(1, \tilde{j}_i)}, \mathbf{x}_i^{(\text{rep})} \rangle - \langle \mathbf{y}_i^{(0, \tilde{j}_i)}, \mathbf{x}_i^{(\text{rep})} \rangle \end{array} \right. \qquad (13) $$

are constants.

From this point, in order to ease the presentation, we omit the index $i$ from $j_i \in [J_i], \tilde{j}_i \in [\tilde{J}_i], \mathbf{d}^{(\tilde{j}_i)}, \mathbf{c}^{(\tilde{j}_i)}$ and write $j \in [J], \tilde{j} \in [\tilde{J}], \mathbf{d}^{(\tilde{j})}, \mathbf{c}^{(\tilde{j})}$. We describe the selective games below, starting from $\mathbf{G}_3^*$, where event E is assumed true:

**Game $\mathbf{G}_3^*$:** This is the selective version of $\mathbf{G}_3$, assuming event E is true. For the basis matrices, thanks to the large enough dimension we can define the entries based on all repetitions $(\mathbf{y}_i^{(1, \tilde{j})}[m], \mathbf{y}_i^{(0, \tilde{j})}[m])_m$ where $\tilde{j} \in [\tilde{J}]$. For different $\tilde{j}_1 \neq \tilde{j}_2 \in [\tilde{J}]$, the entries in the matrix that depend on $\mathbf{d}_i^{(\tilde{j}_1)}$ will affect only the 0-entries in $\mathbf{d}_i^{(\tilde{j}_2)}$, thus not creating errors, and vice versa.

**Game $\mathbf{G}_4^*$:** Knowing $(\mathbf{y}_i^{(1, \tilde{j})}, \mathbf{y}_i^{(0, \tilde{j})}, \mathbf{x}_i^{(1, \tilde{j})}, \mathbf{x}_i^{(0, \tilde{j})})_{j \in [J], \tilde{j} \in [\tilde{J}]}$, we do quotients by $B_i$ defined via

$$ B_i := (B_i[\text{row}, \text{col}]) \qquad (14) $$

where

$$ B_i[\text{row}, \text{col}] = \left\{ \begin{array}{ll} \frac{1}{\mathbf{y}_i^{(1, \tilde{j})}[z]} & \begin{array}{l} \text{if } \text{row} = \text{col} \le 2N + 3 \\ \text{if } \exists \tilde{j} \in [J], z \in [N] \text{ s.t.} \end{array} \\ \\ \frac{1}{\mathbf{y}_i^{(0, \tilde{j})}[z]} & \begin{array}{l} \text{row} = \text{col} = 2N \cdot \tilde{j} + 3 + z \text{ AND } \mathbf{y}_i^{(1, \tilde{j})}[z] \neq 0 \\ \text{if } \exists \tilde{j} \in [J], z \in [N] \text{ s.t.} \end{array} \\ \\ \frac{1}{\mathbf{y}_i^{(0, \tilde{j})}[z]} & \begin{array}{l} \text{row} = \text{col} = 2N \cdot \tilde{j} + 3 + z \text{ AND } \mathbf{y}_i^{(1, \tilde{j})}[z] = 0 \\ \text{if } \exists \tilde{j} \in [J], z \in [N] \text{ s.t.} \end{array} \\ \\ \frac{1}{\mathbf{y}_i^{(1, \tilde{j})}[z]} & \begin{array}{l} \text{row} = \text{col} = 2N \cdot \tilde{j} + N + 3 + z \text{ AND } \mathbf{y}_i^{(0, \tilde{j})}[z] \neq 0 \\ \text{if } \exists \tilde{j} \in [J], z \in [N] \text{ s.t.} \end{array} \\ \\ 0 & \text{otherwise} \end{array} \right. $$

$$ B'_i := (B_i^{-1})^{\top}; \quad \mathbf{B}_i = B_i \cdot \mathbf{H}_i; \quad \mathbf{B}_i^* = B'_i \cdot \mathbf{H}_i^* . $$

The entries of the matrix take into account several conditions:
• The entries $B_i[\text{row, col}] = 1$, if $\text{row} = \text{col} \le 2N + 3$, fix the vectors coordinates that we do not want to change in $\mathbf{d}_i^{(j)}$.

• For $\tilde{j} \in [J], z \in [N]$, the entries

$$B_i[\text{row, col}] = \begin{cases} B_i[\text{row, col}] = \frac{1}{\mathbf{y}_i^{(1,j)}[z]} & \text{if } \exists \tilde{j} \in [J], z \in [N] \text{ s.t.} \\ \text{row} = \text{col} = 2N \cdot \tilde{j} + 3 + z & \text{AND } \mathbf{y}_i^{(1,j)}[z] \neq 0 \end{cases} \\ B_i[\text{row, col}] = \begin{cases} B_i[\text{row, col}] = 1 & \text{if } \exists \tilde{j} \in [J], z \in [N] \text{ s.t.} \\ \text{row} = \text{col} = 2N \cdot \tilde{j} + 3 + z & \text{AND } \mathbf{y}_i^{(1,j)}[z] = 0 \end{cases}$$

will change the coordinate $\mathbf{d}_i^{(j)}[2N \cdot \tilde{j} + 3 + z]$ into 1 iff $\mathbf{y}_i^{(1,j)}[z] \neq 0$. Dually for all c-vectors their coordinate $2N \cdot \tilde{j} + 3 + z$ will be multiply by $\mathbf{y}_i^{(1,j)}[z] \neq 0$. An analogous computation is performed by

$$B_i[\text{row, col}] = \begin{cases} \frac{1}{\mathbf{y}_i^{(0,j)}[z]} & \text{if } \exists \tilde{j} \in [J], z \in [N] \text{ s.t.} \\ \text{row} = \text{col} = 2N \cdot \tilde{j} + N + 3 + z & \text{AND } \mathbf{y}_i^{(0,j)}[z] \neq 0 \end{cases} \\ 1 \qquad \begin{cases} \text{if } \exists \tilde{j} \in [J], z \in [N] \text{ s.t.} \\ \text{row} = \text{col} = 2N \cdot \tilde{j} + N + 3 + z & \text{AND } \mathbf{y}_i^{(0,j)}[z] = 0 \end{cases}$$

but with respect to $\mathbf{y}_i^{(0,j)}$ and for coordinates $2N \cdot \tilde{j} + N + 3 + z$, for $z \in [n]$.

**Game G**\*_5 : In this game we perform a formal basis change to move all the values 1 from coordinates $[2N \cdot \tilde{j} + 4, 2N \cdot \tilde{j} + N + 3]$ for all to coordinates $[2N \cdot \tilde{j} + N + 4, 2N \cdot \tilde{j} + 2N + 3]$ of $\mathbf{d}_i$. The basis changing matrices $B_i$ from $G_4^*$ to $G_5^*$ is defined below

$$B_i := (B_i[\text{row, col}]) \qquad (15)$$

where

$$B_i[\text{row, col}] = \begin{cases} 1 & \text{if } \text{row} = \text{col} \\ \frac{1}{r'} & \text{if } \exists \tilde{j} \in [J], z \in [N] \text{ s.t.} \\ (\text{row, col}) = (2N + 2N \cdot \tilde{j} + 4, 2N \cdot \tilde{j} + 3 + z) & \text{AND } \mathbf{y}_i^{(1,j)}[z] \neq 0 \end{cases} \\ 0 & \text{if } \exists \tilde{j} \in [J], z \in [N] \text{ s.t.} \\ (\text{row, col}) = (2N + 2N \cdot \tilde{j} + 4, 2N \cdot \tilde{j} + 3 + z) & \text{AND } \mathbf{y}_i^{(1,j)}[z] = 0 \end{cases} \\ \frac{-1}{r'} & \text{if } \exists \tilde{j} \in [J], z \in [N] \text{ s.t.} \\ (\text{row, col}) = (2N + 2N \cdot \tilde{j} + 4, 2N \cdot \tilde{j} + N + 3 + z) & \text{AND } \mathbf{y}_i^{(0,j)}[z] \neq 0 \end{cases} \\ 0 & \text{if } \exists \tilde{j} \in [J], z \in [N] \text{ s.t.} \\ (\text{row, col}) = (2N + 2N \cdot \tilde{j} + 4, 2N \cdot \tilde{j} + N + 3 + z) & \text{AND } \mathbf{y}_i^{(0,j)}[z] = 0 \end{cases} \\ 0 & \text{otherwise} \end{cases}$$

$$B'_i := (B_i^{-1})^\top; \quad \mathbf{B}_i = B_i \cdot \mathbf{H}_i; \quad \mathbf{B}_i^* = B'_i \cdot \mathbf{H}_i^*.$$

From the previous game it holds that, for $\tilde{j} \in [\tilde{J}], z \in [N]$,

$$\mathbf{d}_i^{(j)}[2N \cdot \tilde{j} + 3 + z] = 1 \quad \text{iff} \quad \mathbf{y}_i^{(1,j)}[z] \neq 0 \\ \mathbf{d}_i^{(j)}[2N \cdot \tilde{j} + N + 3 + z] = 0 \quad \forall z \qquad (16)$$

while for any $j \in [J]$

$$\mathbf{c}_i^{(j)}[2N \cdot \tilde{j} + 3 + z] = \mathbf{y}_i^{(1,j)}[z] \cdot \mathbf{x}_i^{(1,j)}[m] \quad \text{iff} \quad \mathbf{y}_i^{(1,j)}[z] \neq 0$$

$$\mathbf{c}_i^{(j)}[2N \cdot \tilde{j} + 3 + z] = \mathbf{x}_i^{(1,j)}[m] \quad \text{iff} \quad \mathbf{y}_i^{(1,j)}[z] = 0$$

$$\mathbf{c}_i^{(j)}[2N \cdot \tilde{j} + N + 3 + z] = \mathbf{y}_i^{(0,j)}[z] \cdot \mathbf{x}_i^{(0,j)}[m] \quad \text{iff} \quad \mathbf{y}_i^{(0,j)}[z] \neq 0$$

$$\mathbf{c}_i^{(j)}[2N \cdot \tilde{j} + N + 3 + z] = \mathbf{x}_i^{(0,j)}[m] \quad \text{iff} \quad \mathbf{y}_i^{(0,j)}[z] = 0.$$
We again recall that the pairs $(\mathbf{x}_i^{(1,j)}, \mathbf{x}_i^{(0,j)})$ (similarly $(\mathbf{x}_{k,i}^{(\text{rep})}, \mathbf{x}_{k,i}^{(\text{rep})})$ in $\mathbf{c}_{k,i}^{(\text{rep})}$ for the same argument) in $\mathbf{c}_i^{(j)}$ are already in position thanks to $\mathbf{G}_2$. The above formal basis change will modify these d-vectors such that: for $\tilde{j} \in [\tilde{J}], z \in [N]$

$$ \mathbf{d}_i^{(j)}[2N \cdot \tilde{j} + 3 + z] = 0 \quad \forall z \in [N] \qquad (17) $$

$$ \mathbf{d}_i^{(j)}[2N \cdot \tilde{j} + N + 3 + z] = 1 \quad \text{iff} \quad \mathbf{y}_i^{(0, \tilde{j})}[z] \neq 0 \qquad (18) $$

$$ \mathbf{d}_i^{(j)}[2N \cdot \tilde{j} + N + 3 + z] = 0 \quad \text{iff} \quad \mathbf{y}_i^{(0, \tilde{j})}[z] = 0 \qquad (19) $$

where (17) comes from

$$ B_i[\text{row, col}] = \begin{cases} \frac{1}{r'} & \text{if } \exists \tilde{j} \in [J], z \in [N] \text{ s.t.} \\ (\text{row, col}) = (2N + 2N \cdot \tilde{j} + 4, 2N \cdot \tilde{j} + 3 + z) \quad \text{AND} \quad \mathbf{y}_i^{(1, \tilde{j})}[z] \neq 0, \\ 0 & \text{if } \exists \tilde{j} \in [J], z \in [N] \text{ s.t.} \\ (\text{row, col}) = (2N + 2N \cdot \tilde{j} + 4, 2N \cdot \tilde{j} + 3 + z) \quad \text{AND} \quad \mathbf{y}_i^{(1, \tilde{j})}[z] = 0 \end{cases} $$

(18) comes from (16) and

$$ B_i[\text{row, col}] = \begin{cases} \frac{1}{r'} & \text{if } \exists \tilde{j} \in [J], z \in [N] \text{ s.t.} \\ (\text{row, col}) = (2N + 2N \cdot \tilde{j} + 4, 2N \cdot \tilde{j} + N + 3 + z) \quad \text{AND} \quad \mathbf{y}_i^{(0, \tilde{j})}[z] \neq 0, \end{cases} $$

and (19) comes again from (16) together with

$$ B_i[\text{row, col}] = \begin{cases} 0 & \text{if } \exists \tilde{j} \in [J], z \in [N] \text{ s.t.} \\ (\text{row, col}) = (2N + 2N \cdot \tilde{j} + 4, 2N \cdot \tilde{j} + N + 3 + z) \quad \text{AND} \quad \mathbf{y}_i^{(0, \tilde{j})}[z] = 0. \end{cases} $$

Temporarily until the end of this $\mathbf{G}_6$, the index $i$ is put back to emphasize that $j_i, \tilde{j}_i$ might differ among different $i$. Accordingly, the c-vectors are changed as follows, for $j \in [J]$,

$$ \begin{aligned} \mathbf{c}_i^{(j_i)}[2N \cdot \tilde{j}_i + 2N + 4] &= \tau_i + \frac{1}{r'} \sum_{\tilde{j}_i \in [\tilde{J}_i]} \left( \sum_{z \in [N]} \mathbf{y}_i^{(1, \tilde{j}_i)}[z] \cdot \mathbf{x}_i^{(1, j_i)}[z] - \mathbf{y}_i^{(0, \tilde{j}_i)}[z] \cdot \mathbf{x}_i^{(0, j_i)}[z] \right. \\ & \qquad \left. + \sum_{z \in [N]} \mathbf{y}_i^{(1, \tilde{j}_i)}[z] \cdot \mathbf{x}_i^{(1, j_i)}[z] - \sum_{z \in [N]} \mathbf{y}_i^{(0, \tilde{j}_i)}[z] \cdot \mathbf{x}_i^{(0, j_i)}[z] \right) \\ &= \tau_i + \frac{1}{r'} \sum_{\tilde{j}_i \in [\tilde{J}_i]} \left( \langle \mathbf{y}_i^{(1, \tilde{j}_i)}, \mathbf{x}_i^{(1, j_i)} \rangle - \langle \mathbf{y}_i^{(0, \tilde{j}_i)}, \mathbf{x}_i^{(0, j_i)} \rangle \right), \quad (20) \end{aligned} $$

where the conditions are

$$ (\text{E3}) \quad \mathbf{y}_i^{(1, \tilde{j}_i)}[z] \neq 0 \quad \text{AND} \quad \mathbf{y}_i^{(0, \tilde{j}_i)}[z] \neq 0, $$

$$ (\text{E2}) \quad \mathbf{y}_i^{(1, \tilde{j}_i)}[z] \neq 0 \quad \text{AND} \quad \mathbf{y}_i^{(0, \tilde{j}_i)}[z] = 0 \quad \text{and} $$

$$ (\text{E1}) \quad \mathbf{y}_i^{(1, \tilde{j}_i)}[z] = 0 \quad \text{AND} \quad \mathbf{y}_i^{(0, \tilde{j}_i)}[z] \neq 0. $$

This formal swapping will modify the secret sharings $\tau_i$, in a given $\mathbf{c}_i^{(j_i)}$, into another secret sharing of 0 for any fixed $\tilde{j}_i, j_i$ thanks to condition

$$ \sum_{i=1}^{H} \langle \mathbf{y}_{i}^{(1, \tilde{j}_{i})}, \mathbf{x}_{i}^{(1, j_{i})} \rangle = \sum_{i=1}^{H} \langle \mathbf{y}_{i}^{(0, \tilde{j}_{i})}, \mathbf{x}_{i}^{(0, j_{i})} \rangle . $$

Moreover the updated $\tau_i$ does not depend on $\tilde{j}_i, j_i$ because $\langle \mathbf{y}_i^{(1, \tilde{j}_i)}, \mathbf{x}_i^{(1, j_i)} \rangle - \langle \mathbf{y}_i^{(0, \tilde{j}_i)}, \mathbf{x}_i^{(0, j_i)} \rangle$ is constant for all $\tilde{j}_i \in [\tilde{J}_i], j_i \in [J_i]$, for any fixed $i \in [H]$, thanks to the observation (13). In the vectors $\mathbf{c}_{k,i}^{(\text{rep})}$ a similar argument can be done, because the difference
being added to $\tau'_{k,i}$ is $\frac{1}{r'} \sum_{\tilde{j}_i \in [\tilde{J}_i]} (\langle \mathbf{y}_i^{(1, \tilde{j}_i)}, \mathbf{x}_i^{(\text{rep})} \rangle - \langle \mathbf{y}_i^{(0, \tilde{j}_i)}, \mathbf{x}_i^{(\text{rep})} \rangle)$ together with the hypothesis

$$ \sum_{i=1}^{H} \langle \mathbf{y}_i^{(1, \tilde{j}_i)}, \mathbf{x}_i^{(\text{rep})} \rangle = \sum_{i=1}^{H} \langle \mathbf{y}_i^{(0, \tilde{j}_i)}, \mathbf{x}_i^{(\text{rep})} \rangle . $$

We will use again the observation (13) to conclude that the difference does not depend on repetitions.

**Game $G_6^*$:** The game hop from $G_5^*$ to $G_6^*$ to undo these quotients can be defined similarly as we have done from $G_3^* \to G_4^*$, in order to multiply back $\mathbf{y}_i^{(0, \tilde{j}_i)}$ into coordinates $[2N \cdot \tilde{j}_i + N + 4, 2N \cdot \tilde{j}_i + 2N + 3]$.

The above games demonstrate relation (12). We now employ the complexity leveraging argument. Let us fix $t \in \{3, 4, 5\}$. For $u \in \{t, t+1\}$ let $\mathbf{Adv}_u(\mathcal{A}) := |\text{Pr}[G_u(\mathcal{A}) = 1] - 1/2|$ denote the advantage of a ppt adversary $\mathcal{A}$ in game $G_u$. We build a ppt adversary $\mathcal{B}^*$ playing against $G_u^*$ such that its advantage $\mathbf{Adv}_u^*(\mathcal{B}^*) := |\text{Pr}[G_u^*(\mathcal{B}^*) = 1] - 1/2|$ equals $\gamma \cdot \mathbf{Adv}_u(\mathcal{A})$ for $u \in \{t, t+1\}$, for some constant $\gamma$.

The adversary $\mathcal{B}^*$ first guesses the values $(\mathbf{y}_i^{(1, \tilde{j}_i)}, \mathbf{y}_i^{(0, \tilde{j}_i)}, \mathbf{x}_i^{(1, \tilde{j}_i)}, \mathbf{x}_i^{(0, \tilde{j}_i)})$ with $j_i \in [J_i]$, $\tilde{j}_i \in [\tilde{J}_i]$, $i \in [H]$, choose $r' \stackrel{\leftarrow}{\approx} \mathbb{Z}_q^*$, random secret shareings $(\tau_i, \tau'_{k,i}, \tilde{\tau}_i, \tilde{\tau}'_{k,i})_{i=1}^H$ of 0 for each $j_i \in [J_i]$, with $\tau_i, \tau'_{k,i} \neq 0$ for all $i$. Then $\mathcal{B}^*$ defines the event $E$ that the guess is correct on $(\mathbf{y}_i^{(1, \tilde{j}_i)}, \mathbf{y}_i^{(0, \tilde{j}_i)}, \mathbf{x}_i^{(1, \tilde{j}_i)}, \mathbf{x}_i^{(0, \tilde{j}_i)})_{j_i \in [J_i], \tilde{j}_i \in [\tilde{J}_i]}$ and for any $j_i \in [J_i]$

$$ \tilde{\tau}_i - \tau_i = \frac{1}{r'} \sum_{\tilde{j}_i \in [\tilde{J}_i]} \left( \langle \mathbf{y}_i^{(1, \tilde{j}_i)}, \mathbf{x}_i^{(1, \tilde{j}_i)} \rangle - \langle \mathbf{y}_i^{(0, \tilde{j}_i)}, \mathbf{x}_i^{(0, \tilde{j}_i)} \rangle \right) $$

$$ \tilde{\tau}'_{k,i} - \tau'_{k,i} = \frac{1}{r'} \sum_{\tilde{j}_i \in [\tilde{J}_i]} \left( \langle \mathbf{y}_i^{(1, \tilde{j}_i)}, \mathbf{x}_i^{(\text{rep})} \rangle - \langle \mathbf{y}_i^{(0, \tilde{j}_i)}, \mathbf{x}_i^{(\text{rep})} \rangle \right) . $$

When $\mathcal{B}^*$ guesses successfully and $E$ happens, then the simulation of $\mathcal{A}$'s view in $G_t$ is perfect. Otherwise, $\mathcal{B}^*$ aborts the simulation and outputs a random bit $b'$. Since $E$ happens with some fixed probability $\gamma$ and is independent from the view of $\mathcal{A}$, we have<fnref n="9" />:

$$ \begin{aligned} \mathbf{Adv}_u^*(\mathcal{B}^*) &= \left| \text{Pr}[G_u^*(\mathcal{B}^*) = 1] - \frac{1}{2} \right| \\ &= \left| \text{Pr}[E] \cdot \text{Pr}[G_u^*(\mathcal{B}^*) = 1 | E] + \frac{\text{Pr}[\neg E]}{2} - \frac{1}{2} \right| \\ &= \left| \gamma \cdot \text{Pr}[G_u^*(\mathcal{B}^*) = 1 | E] + \frac{1 - \gamma - 1}{2} \right| \\ \stackrel{(*)}{=} \gamma \cdot \left| \text{Pr}[G_u(\mathcal{A}) = 1] - \frac{1}{2} \right| &= \gamma \cdot \mathbf{Adv}_u(\mathcal{A}) \end{aligned} \quad (21) $$

where (*) comes from the fact that conditioned on $E$, $\mathcal{B}$ simulates perfectly $G_u$ for $\mathcal{A}$, therefore $\text{Pr}[G_u(\mathcal{A}) = 1 | E] = \text{Pr}[G_u^*(\mathcal{B}^*) = 1 | E]$, then we apply the independence between $E$ and $G_u(\mathcal{A}) = 1$. Together with relation (12), this concludes that $\text{Pr}[G_t = 1] = \text{Pr}[G_{t+1} = 1]$ for any fixed $t \in \{3, 4, 5\}$, in particular $\text{Pr}[G_6 = 1] = \text{Pr}[G_3 = 1]$.

**Game $G_7$:** Similar to the transition $G_2$ to $G_3$, we use a computational swap between $[N+1, 2N]$ and $[2N \cdot \tilde{j} + N + 4, 2N \cdot \tilde{j} + 2N + 3]$ in $\mathbf{d}_i^{(j)}$ using $(2N+3)$-randomness. We need $n \cdot \tilde{J} \cdot N$ DSDH instances $([a_{i,z}^{(j)}]_1, [b_{i,z}^{(j)}]_1, [c_{i,z}^{(j)}]_1)$ in $\mathbb{G}_1$ where $\delta_{i,z}^{(j)} := c_{i,z}^{(j)} - a_{i,z}^{(j)}b_{i,z}^{(j)}$ is either 0 or $\mathbf{x}_i^{(j)}[z]$, for $z \in [N], \tilde{j} \in [\tilde{J}], i \in [n]$. The security loss is $2 \cdot n \cdot \tilde{J} \cdot N \cdot \mathbf{Adv}_{\mathbb{G}_1, \mathbb{G}_2}^{\text{SXDH}}(1^{\lambda})$.

<footnote n="9">⁹This calculation (21) to relate $\mathbf{Adv}_u^*(\mathcal{B}^*)$ to $\mathbf{Adv}_u(\mathcal{A})$ is the core of our complexity leveraging argument, being built upon the previous information-theoretic game transtions and the probability of event $E$.</footnote>
**Game $G_8$**: We redo the transitions from $G_1$ to $G_2$ to clean the vectors.

After arriving at $G_8$, the vectors are computed following the interaction

$$A_{\tilde{O}_u, \tilde{O}_v, \mathcal{O}_v}^{\tilde{O}_u, \mathcal{O}_u^1}(1^{\lambda}, N, H, K, L, (J_i, \tilde{J}_i)_{i \in [H]}, R, (R_k)_{k \in [K]}) ,$$

the transitions are indistinguishable under SXDH, and the proof is finished. □

## A.3 Security – Proof of Theorem 1

**Security** The security of our scheme in Fig. 3 is proven below.

**Theorem 1.** The DMCFE scheme $\mathcal{E} = (\text{Setup}, \text{DKeyGen}, \text{Enc}, \text{Dec})$ in Fig. 3 for the function class $\mathcal{F}^{\text{ip}}$ is one-challenge, function-hiding secure against complete queries under static corruption in the ROM, if the SXDH assumption holds for $(\mathbb{G}_1, \mathbb{G}_2)$.

More specifically, we let $q_e$ and $q_k$ denote the maximum number of distinct tags queried to $\mathcal{OEnc}$ and $\mathcal{OKeyGen}$, respectively. Furthermore, for $i \in [n]$ and tag, tag-f $\in \text{Tag}$, we define $\tilde{J}_{i, \text{tag-f}}$ to be the numbers of queries of the form $\mathcal{OKeyGen}(i, \text{tag-f}, \star, \star)$. We require that $\max_{i \in [n], \text{tag-f} \in \text{Tag}} \tilde{J}_{i, \text{tag-f}} \le \tilde{J}$, where $\tilde{J}$ is specified by the DMCFE scheme at Setup time. Then, for any ppt adversary $\mathcal{A}$ against $\mathcal{E}$, we have the following bound:

$$\mathbf{Adv}_{\mathcal{E}, \mathcal{F}^{\text{ip}}, \mathcal{A}}^{\text{1chal-pos-stat-fh}}(1^{\lambda}) \le ((q_k + 1) \cdot (4n\tilde{J}N + 4) + 4N + q_e + 1) \cdot \mathbf{Adv}_{\mathbb{G}_1, \mathbb{G}_2}^{\text{SXDH}}(1^{\lambda})$$

*Proof.* The proof is done via a sequence of hybrid games. The games are depicted in Figure 5.

**Game $G_0$**: This is the experiment $\text{Exp}_{\mathcal{E}, \mathcal{F}, \mathcal{A}}^{\text{1chal-pos-stat-fh}}(1^{\lambda})$ of a ppt adversary $\mathcal{A}$, where $b \leftarrow_s \{0, 1\}$ is the challenge bit. Because we are in the one-challenge setting with static corruption, the adversary will declare since Initialize the challenge ciphertext tag $\text{tag}^*$, the challenge function tag $\text{tag-f}^*$ as well as the set $\mathcal{C} \subset [n]$ of corrupted clients. We define $\mathcal{H} := [n] \setminus \mathcal{C}$. Without loss of generality, we order the honest clients in $\mathcal{H}$ by $[1; H]$ where $H := |\mathcal{H}|$. Knowing $\text{tag}^*, \text{tag-f}^*$, we index by $\ell \in [q_e]$ the $\ell$-th group of ciphertext components queried to $\mathcal{OEnc}$ for $\text{tag}_\ell \ne \text{tag-f}^*$. Similarly, we index by $k \in [q_k]$ the $k$-th group of key components queried to $\mathcal{OKeyGen}$ for $\text{tag-f}_k \ne \text{tag-f}^*$.

For the ciphertext and key queries, challenge or not, the adversary can issue repetitions and we index the repetition by $j'_i \in [J_i]$ (respectively $\tilde{j}'_i \in [\tilde{J}_i]$) for the non-challenge and by $j_i \in [J_i]$ (respectively $\tilde{j}_i \in [\tilde{J}_i]$) for the challenge ciphertext (respectively key) components, where $J_i, \tilde{J}_i$ are maximum numbers of repetitions at position $i \in [n]$, over all queried tags, in ciphertext and key components in that order. We recall that $\max_{i \in [n], \text{tag-f} \in \text{Tag}} \tilde{J}_{i, \text{tag-f}} \le \tilde{J}$, where $\tilde{J} = \text{poly}(\lambda)$ is specified by the DMCFE scheme at Setup time. Unless stated otherwise, for simpler notations in the following we omit the index $i$ from $j_i, j'_i \in [J_i], \tilde{j}_i, \tilde{j}'_i \in [\tilde{J}_i]$ and write $j, j' \in [J], \tilde{j}, \tilde{j}' \in [\tilde{J}]$ for the challenge ciphertext and key components.

There is a secret sharing $(\tilde{t}_i)_i$ of 0 that we generate from Initialize. For the tag $\text{tag-f}_k$ w.r.t non-challenge functional key queries, we denote $H_2(\text{tag-f}_k) \to [[\mu_k]]_2$. Similarly, for the only challenge functional key query to KeyGen corresponding to $\text{tag-f}^*$, we denote $H_2(\text{tag-f}^*) \to [[\mu]]_2$.

In the same manner, for the $\ell$-th non-challenge tag $\text{tag}_\ell$, we write $H_1(\text{tag}_\ell) \to [[\omega_\ell]]_1$ and $t_{\ell,i} := \omega_\ell \cdot \tilde{t}_i$. For the challenge tag $\text{tag}^*$, we denote $H_1(\text{tag}^*) \to [[\omega]]_1$ and $t_i := \omega \cdot \tilde{t}_i$. In the end, the challenger provides the key and ciphertext components as
**Game G₀:** $\sum_{i=1}^n \tilde{t}_i = 0$, $H_1(\text{tag}_\ell) \to [[\omega_\ell]]_1$, $H_1(\text{tag}^*) \to [[\omega]]_1$, $H_2(\text{tag-f}_k) \to [[\mu_k]]_2$, $H_2(\text{tag-f}^*) \to [[\mu]]_2$, $b \leftarrow \{0, 1\}$ is the challenge bit. The poly-bound $\tilde{J} \ge \max_{i \in [H]} \{\tilde{J}_i\}$ is fixed. Indices are running $j_i, j'_i \in [J_i], \tilde{j}_i, \tilde{j}'_i \in [\tilde{J}_i]$.

$$
\begin{align*}
\mathbf{c}_{\ell, i}^{(\tilde{j}'_i)} &= ( \mathbf{x}_{\ell, i}^{(\tilde{j}'_i)} \quad | \quad \tilde{t}_i \omega_\ell \quad | \quad 0 \quad | \quad \rho_{\ell, i}^{(\tilde{j}'_i)} \quad | \quad 0^N \quad | \quad 0^{2N \cdot \tilde{J} + 1} )_{\mathbf{B}_i \\
\mathbf{d}_{k, i}^{(\tilde{j}'_i)} &= ( \mathbf{y}_{k, i}^{(\tilde{j}'_i)} \quad | \quad \mu_k \quad | \quad \pi_{k, i}^{(\tilde{j}'_i)} \quad | \quad 0 \quad | \quad 0^N \quad | \quad 0^{2N \cdot \tilde{J} + 1} )_{\mathbf{B}_i^* \\
\mathbf{c}_i^{(\tilde{j}_i)} &= ( \mathbf{x}_i^{(\tilde{j}_i)} \quad | \quad \tilde{t}_i \omega \quad | \quad 0 \quad | \quad \rho_i^{(\tilde{j}_i)} \quad | \quad 0^N \quad | \quad 0^{2N \cdot \tilde{J} + 1} )_{\mathbf{B}_i \\
\mathbf{d}_i^{(\tilde{j}_i)} &= ( \mathbf{y}_i^{(\tilde{j}_i)} \quad | \quad \mu \quad | \quad \pi_i^{(\tilde{j}_i)} \quad | \quad 0 \quad | \quad 0^N \quad | \quad 0^{2N \cdot \tilde{J} + 1} )_{\mathbf{B}_i^*
\end{align*}
$$

**Game G₁:** $\sum_{i=1}^n t_{\ell,i} = \sum_{i=1}^n t_i = 0$ (Randomization)

$$
\begin{align*}
\mathbf{c}_{\ell, i}^{(\tilde{j}'_i)} &= ( \mathbf{x}_{\ell, i}^{(\tilde{j}'_i)} \quad | \quad \boxed{t_{\ell, i}} \quad | \quad 0 \quad | \quad \rho_{\ell, i}^{(\tilde{j}'_i)} \quad | \quad 0^N \quad | \quad 0^{2N \cdot \tilde{J} + 1} )_{\mathbf{B}_i \\
\mathbf{d}_{k, i}^{(\tilde{j}'_i)} &= ( \mathbf{y}_{k, i}^{(\tilde{j}'_i)} \quad | \quad \mu_k \quad | \quad \pi_{k, i}^{(\tilde{j}'_i)} \quad | \quad 0 \quad | \quad 0^N \quad | \quad 0^{2N \cdot \tilde{J} + 1} )_{\mathbf{B}_i^* \\
\mathbf{c}_i^{(\tilde{j}_i)} &= ( \mathbf{x}_i^{(\tilde{j}_i)} \quad | \quad \boxed{t_i} \quad | \quad 0 \quad | \quad \rho_i^{(\tilde{j}_i)} \quad | \quad 0^N \quad | \quad 0^{2N \cdot \tilde{J} + 1} )_{\mathbf{B}_i \\
\mathbf{d}_i^{(\tilde{j}_i)} &= ( \mathbf{y}_i^{(\tilde{j}_i)} \quad | \quad \mu \quad | \quad \pi_i^{(\tilde{j}_i)} \quad | \quad 0 \quad | \quad 0^N \quad | \quad 0^{2N \cdot \tilde{J} + 1} )_{\mathbf{B}_i^*
\end{align*}
$$

**Game G₂:** (Subspace Indistinguishability)

$$
\begin{align*}
\mathbf{c}_{\ell, i}^{(\tilde{j}'_i)} &= ( \mathbf{x}_{\ell, i}^{(\tilde{j}'_i)} \quad | \quad t_{\ell, i} \quad | \quad 0 \quad | \quad \rho_{\ell, i}^{(\tilde{j}'_i)} \quad | \quad \boxed{\mathbf{x}_{\ell, i}^{(\tilde{j}'_i)}} \quad | \quad 0^{2N \cdot \tilde{J} + 1} )_{\mathbf{B}_i \\
\mathbf{c}_i^{(\tilde{j}_i)} &= ( \mathbf{x}_i^{(\tilde{j}_i)} \quad | \quad t_i \quad | \quad 0 \quad | \quad \rho_i^{(\tilde{j}_i)} \quad | \quad \boxed{\mathbf{x}_i^{(\tilde{j}_i)}} \quad | \quad 0^{2N \cdot \tilde{J} + 1} )_{\mathbf{B}_i^*
\end{align*}
$$

**Game G₃:** (Application of Lemma 1 for all OKeyGen tags under a bounded number $\tilde{J}$ of repetitions $\tilde{j}_i, \tilde{j}'_i \in [\tilde{J}_i], \tilde{J}_i \le \tilde{J}$ for $\mathbf{d}_i^{(\tilde{j}_i)}$ and $\mathbf{d}_i^{(\tilde{j}'_i)}$)

$$
\begin{align*}
\mathbf{d}_{k, i}^{(\tilde{j}'_i)} &= ( \boxed{0^N} \quad | \quad \mu_k \quad | \quad \pi_{k, i}^{(\tilde{j}'_i)} \quad | \quad 0 \quad | \quad \boxed{\mathbf{y}_{k, i}^{(\tilde{j}'_i)}} \quad | \quad 0^{2N \cdot \tilde{J} + 1} )_{\mathbf{B}_i^* \\
\mathbf{d}_i^{(\tilde{j}_i)} &= ( \boxed{0^N} \quad | \quad \mu \quad | \quad \pi_i^{(\tilde{j}_i)} \quad | \quad 0 \quad | \quad \boxed{\mathbf{y}_i^{(1, \tilde{j}_i)}} \quad | \quad 0^{2N \cdot \tilde{J} + 1} )_{\mathbf{B}_i^*}
\end{align*}
$$

**Game G₄:** (Subspace Indistinguishability)

$$
\begin{align*}
\mathbf{c}_{\ell, i}^{(\tilde{j}'_i)} &= ( \mathbf{x}_{\ell, i}^{(\tilde{j}'_i)} \quad | \quad t_{\ell, i} \quad | \quad 0 \quad | \quad \rho_{\ell, i}^{(\tilde{j}'_i)} \quad | \quad \mathbf{x}_{\ell, i}^{(\tilde{j}'_i)} \quad | \quad 0^{2N \cdot \tilde{J} + 1} )_{\mathbf{B}_i \\
\mathbf{c}_i^{(\tilde{j}_i)} &= ( \boxed{\mathbf{x}_i^{(1, \tilde{j}_i)}} \quad | \quad t_i \quad | \quad 0 \quad | \quad \rho_i^{(\tilde{j}_i)} \quad | \quad \boxed{\mathbf{x}_i^{(1, \tilde{j}_i)}} \quad | \quad 0^{2N \cdot \tilde{J} + 1} )_{\mathbf{B}_i^*
\end{align*}
$$

<caption>**Figure 5:** Games for proving Theorem 1</caption>
follows: for the challenge bit b

$$ \mathbf{c}_{\ell,i}^{(j')} = (\mathbf{x}_{\ell,i}^{(j')}, \omega_{\ell} \tilde{t}_i, 0, \rho_{\ell,i}^{(j')}, 0^N, 0^{2N+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+1})_{\mathbf{B}_i^*} $$

$$ \mathbf{c}_{i}^{(j)} = (\mathbf{x}_{i}^{(b,j)}, \omega \tilde{t}_{i}, 0, \rho_{i}^{(j)}, 0^{N}, 0^{2N+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+1})_{\mathbf{B}_{i}^{*}} $$

We index by $(j, j')$ (respectively $(\tilde{j}, \tilde{j}')$) the repetitions of challenge and non-challenge ciphertext components (respectively key components). Note that the admissibility condition in Definition 5 requires that $\mathbf{x}_i^{(0,j)} = \mathbf{x}_i^{(1,j)}$ (respectively $\mathbf{y}_i^{(0,\tilde{j})} = \mathbf{y}_i^{(1,\tilde{j})}$) where $i \in \mathcal{C}$ for all queries to $\mathcal{OEnc}$ (respectively $\mathcal{ODKeyGen}$). All transitions, by means of basis changes in DPVS, in this proof apply only to pairs of bases $(\mathbf{B}_i, \mathbf{B}_i^*)$ where $i \in \mathcal{H}$. This means in particular that all basis vectors considered in the proof are hidden from the adversary.

In the following we define event $G_i = 1$ to signify that “The output $b'$ of $\mathcal{A}$ satisfies $b' = b$ in $G_i$”. We have $\mathbf{Adv}_{\mathcal{E}, \mathcal{F}_{N_1, \dots, N_n}, \mathcal{A}}^{\text{1chal-pos-stat-fh}}(1^{\lambda}) = |\text{Pr}[G_0 = 1] - \frac{1}{2}|$ and a probability calculation shows that for two successive games $G_{i-1}, G_i$, $|\text{Pr}[G_i = 1] - \text{Pr}[G_{i-1} = 1]|$ is the difference in probabilities that $\mathcal{A}$ outputs 1 in $G_i$ versus that $\mathcal{A}$ outputs 1 in $G_{i-1}$. We now start the description of games.

**Game G1:** In this game we replace the multiples of the secret shares of 0 in $c_i$, $c_{\ell,i}^{(j')}$, which are $t_i := \omega \cdot \tilde{t}_i$ and $t_{\ell,i} := \omega_{\ell} \cdot \tilde{t}_i$, for $H_1(\text{tag}) \to [[\omega]]_1$, $H_1(\text{tag}_{\ell}) \to [[\omega_{\ell}]]_1$ and $H_1$ is modelled as a random oracle. We proceed as follows:

**G$_{0.1}$:** We program $H_1$ at the points $\text{tag}, (\text{tag}_{\ell})_{\ell \in [q_e]}$ by sampling $\omega, \omega_{\ell} \stackrel{\$}{\leftarrow} \mathbb{Z}_q$ and setting $H_1(\text{tag}) := [[\omega]]_1, H_1(\text{tag-f}) := [[\omega_{\ell}]]_1$. This gives a perfect simulation and $\text{Pr}[G_{0.1}] = \text{Pr}[G_0]$.

**G$_{0.2}$:** We replace the multiples of the shares in $c_i$, $c_{\ell,i}^{(j')}$ by random secret shares, while preserving their sum. Our key observation is that: because we are in the *static* corruption model, all corrupted $i \in \mathcal{C}$ are known since the beginning. More specifically, the secret shares $(\tilde{t}_i)_{i=1}^n$ are generated at setup and $\sum_{i \in \mathcal{H}} \tilde{t}_i = - (\sum_{i \in \mathcal{C}} \tilde{t}_i)$ is fixed since the beginning. Therefore, upon receiving the challenge tag $\text{tag}^*$ (that is declared up front by the adversary in the current one-challenge setting) as well as all other non-challenge tags $\text{tag}_{\ell}$, thanks to the programmation of the random oracle from $G_{0.1}$, all the sums

$$ R := \omega \sum_{i \in \mathcal{H}} \tilde{t}_i \quad \text{and} \quad R_{\ell} := \omega_{\ell} \sum_{i \in \mathcal{H}} \tilde{t}_i $$

are fixed in advance. We use this observation and the *random-self reducibility* of DDH in $\mathbb{G}_2$ in a sequence of hybrids $G_{0.1,\ell}$ over $\ell \in [0, q_e + 1]$ for changing the non-challenge ciphertext query $c_{\ell,i}^{(j')}$ under $\text{tag}_{\ell}$ as well as changing the challenge key query $c_i^{(j)}$ under $\text{tag}^*$.

In the hybrid $G_{0.1,\ell}$ with $\ell \in [0; q_e]$, the first $\ell$ non-challenge key queries $c_{\ell,i}^{(j)}$ have random secret shares over $i \in \mathcal{H}$:

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

where $t_{\ell,i} \stackrel{\$}{\leftarrow} \mathbb{Z}_q$ and $\sum_{i \in \mathcal{H}} t_{\ell,i} = R_{\ell}$. In the hybrid $G_{0.1,q_e+1}$ we change the challenge key query $c_i^{(j)}$:

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