# Multi-client Attribute-Based and Predicate Encryption from Standard Assumptions

David Pointcheval, Robert Schädlich

► To cite this version:

David Pointcheval, Robert Schädlich. Multi-client Attribute-Based and Predicate Encryption from Standard Assumptions. TCC 2024 - 22nd Theory of Cryptography Conference, Dec 2024, Milan, Italy. pp.31-64, 10.1007/978-3-031-78020-2_2. hal-05029340

HAL Id: hal-05029340

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

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
# Multi-Client Attribute-Based and Predicate Encryption from Standard Assumptions

David Pointcheval<sup>1,2</sup> and Robert Schädlich<sup>2</sup>

¹ Cosmian, Paris, France

² DIENS, École normale supérieure, CNRS, Inria, PSL University, Paris, France

**Abstract.** Multi-input Attribute-Based Encryption (ABE) is a generalization of key-policy ABE where attributes can be independently encrypted across several ciphertexts, and a joint decryption of these ciphertexts is possible if and only if the combination of attributes satisfies the policy of the decryption key. We extend this model by introducing a new primitive that we call Multi-Client ABE (MC-ABE), which provides the usual enhancements of multi-client functional encryption over multi-input functional encryption. Specifically, we separate the secret keys that are used by the different encryptors and consider the case that some of them may be corrupted by the adversary. Furthermore, we tie each ciphertext to a label and enable a joint decryption of ciphertexts only if all ciphertexts share the same label. We provide constructions of MC-ABE for various policy classes based on SXDH. Notably, we can deal with policies that are not a conjunction of local policies, which has been a limitation of previous constructions from standard assumptions.

Subsequently, we introduce the notion of Multi-Client Predicate Encryption (MC-PE) which, in contrast to MC-ABE, does not only guarantee message-hiding but also attribute-hiding. We present a new compiler that turns any constant-arity MC-ABE into an MC-PE for the same arity and policy class. Security is proven under the LWE assumption.

<footnote>This is the full version of [PS25], DOI 10.1007/978-3-031-78020-2_2, published by Springer in the
proceedings of TCC 2024.</footnote>
# 1 Introduction

**Attribute-Based Encryption.** Attribute-based encryption (ABE) [SW05, GPSW06] is a powerful generalization of classical public-key encryption that enables fine-grained access control on encrypted data. In (key-policy) ABE, a ciphertext $CT_x$ encrypting a message $\mu$ is generated with respect to a public attribute $x$ while a secret decryption key $DK_f$ is generated with respect to a policy $f$. The decryption key $DK_f$ is authorized to decrypt the ciphertext $CT_x$ if and only if the attribute $x$ satisfies the policy $f$, i.e. $f(x) = 1$. Security requires indistinguishability in the presence of collusion attacks. That is, for any attribute $x$ and any pair of messages $(\mu^0, \mu^1)$, ciphertexts corresponding to $(x, \mu^0)$ and to $(x, \mu^1)$ are indistinguishable, even for adversaries possessing a set of decryption keys $\{DK_{f_i}\}_{i}$ unless one of the keys $DK_{f_i}$ is individually authorized to decrypt. A strengthening of this notion, traditionally referred to as Predicate Encryption (PE) [BW07, SBC$^+$07], requires ciphertexts to not only hide messages but also their associated attributes.

**Decentralized Encryption.** Until recently, ABE and PE were solely studied in the centralized setting, i.e. the considered policies $f$ have arity one. The notions of Multi-Input ABE (MI-ABE) [BJK$^+$18, AYY22] and Multi-Input PE (MI-PE) [FFMV23] overcome this limitation by considering $n$ encryptors who each encrypt their inputs $(x_1, \mu_1), \dots, (x_n, \mu_n)$ independently using uncorrelated random coins. The key generator provides decryption keys for any $n$ functions $f$, and a joint decryption recovers $(\mu_1, \dots, \mu_n)$ if and only if $f(x_1, \dots, x_n) = 1$. As in the single-input case, the security model of MI-ABE only guarantees to hide the message encoded in a ciphertext while MI-PE hides in addition the associated attribute.

In practice, the multi-input versions of ABE and PE often seem more realistic as they allow data to be encrypted in different locations or at different points in time. As an example, consider a company that stores its client data in encrypted form on a server. Each employee has their own decryption key which they can use to decrypt parts of the data depending on the employee's role. At one point, the company decides to expand and opens several new branches across the country. Clients should be able to be served from each branch. This requires that data can be independently encrypted and uploaded to the central server while still being subject to the global access control for employees. To implement these requirements, we could use an MI-ABE or MI-PE.

Let us extend the above scenario as follows. First, suppose that one of the company's branches falls victim to a hacker attack. Since MI-ABE and MI-PE use the same master secret key across all encryption slots, an attack on a single branch threatens to compromise the security of the entire system. Instead, it would be better if a restricted form of security could be preserved even if a few branches are corrupted. Second, the company's data might be time-sensitive in a sense that, say, data from different years should not be authorized for a joint decryption. To prevent unintended decryptions and the resulting data leakage, we may wish to equip ciphertexts with timestamps and allow a joint decryption if and only if all involved ciphertexts share the same timestamp.

To deal with this extended scenario, we introduce two natural generalizations of MI-ABE and MI-PE which we dub *Multi-Client ABE* (MC-ABE) and *Multi-Client PE* (MC-PE). In contrast to MI-ABE and MI-PE, our new notions implement two additional features. First, they separate the secret keys of the slots and guarantee security even if some of them are known to the adversary. Second, encryption proceeds with respect to a label that can be used to realize a timestamp.

## 1.1 Related Work

The notion of MI-ABE had been studied first by Brakerski et al. [BJK$^+$18] as a new pathway for achieving witness encryption. However, they did not consider strong security notions
nor did they provide any constructions. In [AYY22], Agrawal et al. provided the first constructions for 2-input ABE for $NC^1$ from LWE and a nonstandard assumption on pairings. They also gave heuristic constructions for 2-input ABE for $\mathbf{P}$ and 3-input ABE for $NC^1$. Additionally, they gave a compiler that lifts a constant-input ABE scheme to a PE scheme for the same arity and policy class, using a sophisticated nesting technique of lockable obfuscation which can be based on LWE. In an independent work, Francati et al. [FFMV23] built MI-PE for conjunctions of (bounded) polynomial-depth circuits from $LWE^1$. Notably, they can support a polynomial number of inputs. Furthermore, when restricting to constant arity, they provide a construction that remains secure under user corruptions. On the negative side, neither of their MI-PE constructions can be proven secure under collusions. Very recently, Agrawal et al. [ARYY23] presented a constant-arity MI-ABE for $NC^1$ whose security is based on evasive LWE which is a strong knowledge type assumption. When additionally assuming tensor LWE, they can upgrade their scheme to support arbitrary policies in $\mathbf{P}$.

MI-ABE and MI-PE can both be viewed as a special case of the more general primitive Multi-Input Functional Encryption (MIFE) [GGG$^{+14}$]. The notion of MIFE has been the subject of extensive studies resulting in large body of works with various trade-offs between expressiveness, security, underlying assumptions and efficiency, e.g. [GGG$^{+14}$, AJ15, AGRW17, DOT18, ACF$^{+18}$, CDG$^{+18}$, Tom19, ABKW19, ABG19, LT19, AGT21, AGT22]. As MIFE for $NC^1$ is known to imply indistinguishability Obfuscation (iO) [BGI$^{+01}$, GGH$^{+13}$] it remains an important area of research to build MIFE schemes for simpler function classes from assumptions not known to imply iO. Some of these function classes are still powerful enough to imply MI-ABE. Specifically, Nguyen et al. [NPP22] built the first attribute-based Multi-Client Functional Encryption (MCFE) for inner products, where policies are conjunctions of Linear Secret Sharings (LSS). As they consider MCFE instead of MIFE, their construction supports corruption of users and encryption with respect to labels. They make use of pairings and proof security under the SXDH assumption. However, their security model does not allow repetitions$^2$. In [ATY23], Agrawal et al. presented the first attribute-based MIFE for attribute-weighted sums. The supported policies are conjunctions of $NC^1$ for a polynomial number of slots. Their construction uses pairings and is proven secure under the matrix DDH assumption. By plugging the scheme into the compiler from [AYY22], it can be lifted to MI-PE for constant arity and without corruptions.

## 1.2 Our Results

In this work, we introduce the notions of MC-ABE and MC-PE as a generalization of their multi-input siblings. We discuss our constructions for the two primitives below. For a comparison with known results, please see Table 1.

**MC-ABE for Non-Conjunctions.** Prior to our work, all known constructions of MI-ABE and MI-PE fall into one of two categories: they are either based on standard assumptions but their supported policies are only conjunctions of local policies [NPP22, FFMV23, ATY23], or they can handle more complex policy classes such as $NC^1$ or $\mathbf{P}$ but their security proof relies on nonstandard assumptions [AYY22, ARYY23]. We therefore raise the following question:

<footnote>$^1$A policy $f$ is said to be a conjunction of a policy class $\mathcal{F}$ if there exist policies $f_1, \dots, f_n \in \mathcal{F}$ such that $f(x_1, \dots, x_n) = f_1(x_1) \wedge \dots \wedge f_n(x_n)$.

$^2$Unless stated otherwise, we use the term MCFE as a generalization of MIFE, so it allows multiple uses of labels. In contrast, a weaker notion of MCFE has been considered in the literature [CDG$^{+18}$] where each label can be used only once, thus it does not imply MIFE. We refer to this weaker version as MCFE without repetitions.</footnote>
Is it possible to build MI-ABE or MC-ABE from standard assumptions for policies that are not a conjunction of local policies?

It is well known that MI-ABE for LSS can be generically upgraded to MI-ABE for $NC^1$ via a doubling of the attribute space, and that (polynomial-arity) MI-ABE for $NC^1$ implies Witness Encryption (WE) for languages that can be verified in $NC^1$ [BJK$^+$18]. Considering the fact that the construction of WE with $NC^1$ verification from standard assumptions is still an open problem, it is not surprising that MI-ABE for policies that are not a conjunction has also remained elusive so far, even for relatively simple policy classes such as LSS. As previous works [FFMV23, ATY23], we are not able to build MI-ABE or MC-ABE for a policy class that is powerful enough to trigger the entire chain of implications up to WE. Nonetheless, we identify various special cases that circumvent the known implications to WE, thereby giving an affirmative answer to the above question. Specifically, we present constructions of MC-ABE for the following situations:

1. *Small Parameters*. If the arity $n$ and the attribute space $\{0, 1\}^k$ are small (more precisely, they satisfy $kn = O(\log \lambda)$), then we can build an MC-ABE for all $NC^1$ policies.

2. *Simple Policies*. If $k = n = \text{poly}(\lambda)$, then we can build MC-ABEs for $NC^0$ policies and threshold policies with constant threshold, i.e. policies that accept any combination of at least $\tau$ out of the total of $kn$ attributes, where $\tau = O(1)$ or $\tau = kn - O(1)$. Note that $NC^0$ policies can only depend on a constant number of inputs whereas threshold policies depend on all inputs; so they cannot be implemented in $NC^0$.

3. *Weaker Security*. In the weaker MCFE model without repetitions, we can choose $k = n = \text{poly}(\lambda)$ and build MC-ABE for the policy class $NC^1$ and no user corruptions, or for the policy class LSS with user corruptions.

We discuss the relation between our constructions and the (non-)implications to WE in more detail below.

**From MC-ABE to MC-PE.** In [AYY22], the authors present two generic compilers that lift an MI-ABE scheme to MI-PE for the same policy class. The first one can deal with any constant arity but works only in a weak security model where the adversary must not obtain valid decryption keys for any ciphertext, even if the ciphertext corresponds to a “non-challenge” encryption query $(x, \mu^0, \mu^1)$ where $\mu^0 = \mu^1$. Note that the ability to decrypt such non-challenge ciphertexts does not render the security game trivial and admitting this kind of queries yields a stronger security model. Indeed, their second compiler allows the decryption of non-challenge ciphertexts, but works only for arity 2.

In this work, we present a new generic compiler that works for a constant number of inputs and achieves the stronger security model. Moreover, it can deal with labels and corruption of users, thus turning MC-ABE into MC-PE. Similar to [AYY22], our construction relies on lockable obfuscation whose security can be based on LWE.

## 1.3 Relation to Witness Encryption

A *witness encryption* (WE) scheme for an NP relation $\mathcal{R}$ defined over a language $\mathcal{L}$ allows a sender to efficiently encrypt a message $\mu$ with respect to a problem instance $x$. A receiver holding a witness $w$ can recover the message $\mu$ if $(x, w) \in \mathcal{R}$. Security requires that ciphertexts for messages $\mu^0$ and $\mu^1$ are computationally indistinguishable if $x \notin \mathcal{L}$. The authors of [BJK$^+$18] define a relaxation of classical WE that they call *non-trivially eXponentially efficient WE* (XWE), where the runtime of the encryption algorithm for witnesses of length $n$ is $\tilde{O}(2^{\gamma n})$ for some constant $\gamma < 1$ called the *compression factor*.
<table><caption>Table 1: Comparison with existing works in MI-ABE and MI-PE</caption><thead><tr><th>Work</th><th>Arity</th><th>Attribute<sup>1</sup></th><th>Collusion</th><th>Corruption</th><th>Labels</th><th>Policy Class</th><th>Assumptions</th></tr></thead><tbody><tr><td>[AYY22]</td><td>2</td><td>private</td><td>✓</td><td>✗</td><td>✗</td><td>NC<sup>1</sup></td><td>KOALA<sup>2</sup>, LWE</td></tr><tr><td rowspan="2">[ARYY23]</td><td rowspan="2">const</td><td rowspan="2">private</td><td rowspan="2">✓</td><td rowspan="2">✗</td><td rowspan="2">✗</td><td>NC<sup>1</sup></td><td>Evasive LWE<sup>3</sup></td></tr><tr><td>P</td><td>Evasive and Tensor LWE</td></tr><tr><td>[NPP22]</td><td>poly</td><td>public</td><td>✓</td><td>✓</td><td>OT<sup>4</sup></td><td>Conjunctions of LSS</td><td>SXDH</td></tr><tr><td rowspan="2">[FFMV23]</td><td>poly</td><td>private</td><td>✗</td><td>✗</td><td>✗</td><td>Conjunctions of P</td><td>LWE</td></tr><tr><td>const</td><td></td><td></td><td>✓</td><td></td><td></td><td></td></tr><tr><td>[ATY23]</td><td>poly</td><td>public</td><td>✓</td><td>✓</td><td>✗</td><td>Conjunctions of NC<sup>1</sup></td><td>Matrix DDH</td></tr><tr><td>[ATY23] + [AYY22]</td><td>const</td><td>private</td><td>✓</td><td>✗</td><td>✗</td><td>Conjunctions of NC<sup>1</sup></td><td>Matrix DDH, LWE</td></tr><tr><td rowspan="2">Sec. 5.1</td><td rowspan="2">poly</td><td rowspan="2">public</td><td rowspan="2">✓</td><td>✓</td><td rowspan="2">OT</td><td>LSS</td><td rowspan="2">SXDH</td></tr><tr><td>✗</td><td>NC<sup>1</sup></td></tr><tr><td rowspan="2">Sec. 5.2</td><td>log<sup>5</sup></td><td>public</td><td>✓</td><td>✓</td><td>✓</td><td>NC<sup>1</sup></td><td rowspan="2">SXDH</td></tr><tr><td>poly</td><td></td><td></td><td></td><td></td><td>NC<sup>0</sup> or const threshold</td></tr><tr><td>Sec. 5.2 + Sec. 6</td><td>const<sup>6</sup></td><td>private</td><td>✓</td><td>✓</td><td>✓</td><td>NC<sup>1</sup></td><td>SXDH, LWE</td></tr><tr><td>[ATY23] + Sec. 6</td><td>const</td><td>private</td><td>✓</td><td>✓</td><td>✗</td><td>Conjunctions of NC<sup>1</sup></td><td>Matrix DDH, LWE</td></tr></tbody></table>

In [BJK$^{+}$18], the authors show that $n$-input ABE for a policy class $\mathcal{F}$ implies WE for relations with length $n$ witnesses whose verification algorithm is in $\mathcal{F}$. If $n = \text{poly}(\lambda)$ and $\mathcal{F} = \text{P}$, we obtain WE for all NP relations. But even for smaller arity or simpler policy classes there are nontrivial implications. Since there are NP relations that can be verified in $NC^1$ (e.g. 3-SAT), MI-ABE for $NC^1$ policies already implies WE for certain NP relations. Furthermore, it is shown that $n$-input ABE for $n < \text{poly}(\lambda)$ implies XWE with a compression factor of $\gamma = 1/(n+1)$. Plugging the two-input ABE from [AYY22] or the $O(1)$-input ABE from [ARYY23] into the conversion to XWE, one obtains compression

<footnote n="1">¹ Public attributes correspond to ABE and private attributes to PE.</footnote>

<footnote n="2">² KOALA is a nonstandard knowledge type assumption on pairings.</footnote>

<footnote n="3">³ Evasive LWE is a nonstandard knowledge type assumption on lattices.</footnote>

<footnote n="4">⁴ OT refers to *one-time* labels, i.e. the weaker MCFE model without repetitions.</footnote>

<footnote n="5">⁵ More precisely, the scheme's arity $n$ and attribute space $\{0, 1\}^k$ are subject to the condition $kn = O(\log \lambda)$.</footnote>

<footnote n="6">⁶ The limitation from 5 is still in place and translates into $k = O(\log \lambda)$. Therefore, it does not include the next row which allows only conjunctions but $k = \text{poly}(\lambda)$.</footnote>
factors of $\gamma = 1/3$ and $\gamma = 1/O(1)$, respectively; although the latter result may be less interesting as their hardness assumption, evasive LWE, is already known to imply WE [Tsa22, VWW22]. When relying on standard assumptions, the best known compression factor is still $\gamma = 1/2$ which corresponds to a classical single-input ABE scheme, and any improvement would be highly interesting. Unfortunately, all our constructions fail to improve the compression factor due to the following reasons. (1) We either need $n = \text{poly}(\lambda)$ and $k = 1$ in which case we immediately get (polynomially efficient) WE, or $n < \text{poly}(\lambda)$ and $k = \text{poly}(\lambda)$ in which case we obtain XWE with compression factor $1/(n+1)$. If both $k, n < \text{poly}(\lambda)$, it is unclear how the compression factor could be improved. (2) $\text{NC}^0$ or constant-threshold policies are not powerful enough to verify an NP language. (3) The weaker MC-ABE model without repetitions does not imply MI-ABE, thus fails to imply (X)WE.

The work [FFMV23] presents an interesting alternative pathway towards WE. If the MI-ABE is secure under corruptions, then a two-input scheme for conjunctions of some policy class $\mathcal{F}$ implies WE for any relation whose verification algorithm lies in $\mathcal{F}$. Importantly, for the conversion of [FFMV23] to work, the first slot must have a wildcard while the second slot must not. This property is achieved by all our constructions. However, even in this case our construction for $\text{NC}^1$ fails to imply WE because for $n = 2$, the constraint $kn = O(\log \lambda)$ translates into $k = O(\log \lambda)$ which is not enough as witnesses must be of polynomial length.

## 2 Technical Overview

We first introduce our new primitives MC-ABE and MC-PE. Our syntax closely follows [ARYY23]. Specifically, the 0-th client (the “encryptor”) runs an algorithm Enc which takes as input a label $\text{lab}_0$, an attribute $x_0$ and a message $\mu$ to create a ciphertext $\text{CT}_{\text{lab}_0, x_0}$. The other clients $1, \dots, n-1$ (the “attribute key generators”) run an algorithm AKeyGen which takes only a label $\text{lab}_i$ and an attribute $x_i$ to generate a decryption key $\text{DK}_{\text{lab}_i, x_i}$. Policy decryption keys $\text{DK}_f$ for a policy $f$ are generated by a central authority which runs an algorithm PKeyGen. $\text{CT}_{\text{lab}_0, x_0}$ can be decrypted using $\{\text{DK}_{\text{lab}_i, x_i}\}_i$ and $\text{DK}_f$ if $\text{lab}_0 = \dots = \text{lab}_{n-1}$ and $f(x_0, \dots, x_{n-1}) = 1$. For MC-ABE security, we require the usual ciphertext indistinguishability against collusion attacks under corruptions. MC-PE security additionally considers left-or-right queries for attributes in both slot 0 ciphertexts and slot $i$ attribute decryption keys for all $i \in [n-1]$. This leads to a subtle yet important difference in the security models. In MC-ABE, the encryption oracle of client 0 is the only left-or-right (“challenge”) oracle. In this case, public-key security is stronger than secret-key security which is why we provide client 0 with a master public key MPK and all other clients $i \in [n-1]$ with a secret key $\text{SK}_i$. In MC-PE on the other hand, the oracles of all clients take left-or-right queries. Now considering a public encryption algorithm would actually make the primitive weaker due to inevitable leakage. This is a well-known phenomenon in the context of MIFE and MCFE in general. For this reason, we consider MC-PE in the secret-key setting where the encryptor takes a secret key $\text{SK}_0$ instead of a public key MPK. We summarize the syntax as follows:

$$ \begin{align*} \text{Client 0 :} \quad & \text{Enc}(\text{MPK}/\text{SK}_0, \text{lab}, x_0, \mu) \rightarrow \text{CT}_{x_0} \\ \text{Client } i \in [n-1] : \quad & \text{AKeyGen}(\text{SK}_i, \text{lab}, x_i) \rightarrow \text{DK}_{x_i} \\ \text{Authority :} \quad & \text{PKeyGen}(\text{MSK}, f) \rightarrow \text{DK}_f \end{align*} $$

For completeness, we mention that MC-ABE and MC-PE can also be considered in an $n$-message setting where not only the 0-th but all slots encrypt a message. In [AYY22], it was shown that a single-message MI-ABE scheme can be generically lifted to an $n$-message scheme. The conversion is extremely simple and basically runs $n$ single-message schemes in parallel with rotated slots. The same technique generalizes to MC-ABE and MC-PE.
## 2.1 Construction of MC-ABE

**Ingredients to our Constructions.** Let $\mathcal{G} = (\mathcal{G}_1, \mathcal{G}_2, \mathcal{G}_t, g_1, g_2, g_t, e, p)$ be a pairing group. For $i \in \{1, 2, t\}$ and $a \in \mathbb{Z}_p$, we write $[a]_i = g_i^a$ and use additive notations for the group operations.

An inner-product functional encryption (IPFE) scheme based on $\mathcal{G}$ enables the generation of ciphertexts $\text{iCT}([\mathbf{x}]_1)$ associated with vectors $\mathbf{x} \in \mathbb{Z}_p^N$ encoded in $\mathcal{G}_1$ and decryption keys $\text{iDK}([\mathbf{y}]_2)$ for vectors $\mathbf{y} \in \mathbb{Z}_p^N$ encoded in $\mathcal{G}_2$ such that the decryption of $\text{iCT}([\mathbf{x}]_1)$ with $\text{iDK}([\mathbf{y}]_2)$ reveals only the inner product $[\mathbf{x}^\top\mathbf{y}]_t$ of $\mathbf{x}$ and $\mathbf{y}$ encoded in $\mathcal{G}_t$ and hides all other information about $\mathbf{x}$ whereas $[\mathbf{y}]_2$ is usually public. When we use several IPFE schemes in parallel, we add an index to indicate the respective instance, e.g. for the $i$-th IPFE instance, we write $\text{iCT}_i([\mathbf{x}]_1)$ and $\text{iDK}_i([\mathbf{y}]_2)$.

In the same vein, identity-based encryption (IBE) allows creating ciphertexts $\text{idCT}(i, \mu)$ associated with an identity $i$ for a message $\mu$, and decryption keys $\text{idDK}(i')$ associated with an identity $i'$. Decryption is possible if $i = i'$.

Given a vector $\mathbf{x} \in \{0, 1\}^k$, we write $\Pi_{\mathbf{x}} = \{j \in [k] : \mathbf{x}[j] = 1\}$. A linear secret sharing (LSS) scheme allows to decompose a secret scalar $s \in \mathbb{Z}_p$ into a vector of shares $\text{Share}(s, f) \to \mathbf{s} \in \mathbb{Z}_p^k$ with respect to some policy $f: \{0, 1\}^k \to \{0, 1\}$ such that $s$ can be reconstructed from a subset of the shares $\{\mathbf{s}[j]\}_{j \in \Pi_{\mathbf{x}}}$ for $\mathbf{x} \in \{0, 1\}^k$ if and only if $f(\mathbf{x}) = 1$. For this reconstruction, there exists an efficient algorithm $\text{FindCoef}(\Pi_{\mathbf{x}}, f)$ that outputs coefficients $\omega_1, \dots, \omega_k$ such that $\omega_j = 0$ for all $j \notin \Pi_{\mathbf{x}}$ and $\sum_{j \in [k]} \omega_j \mathbf{s}[j] = s$.

**Key-Policy ABE for LSS Policies.** Our starting point is a technique that combines IPFE with secret sharing schemes. The same approach has recently been used to build ciphertext-policy ABEs with interesting new features [AWY20, AG21, LLL22, AG23]. Very roughly, these works view a secret sharing as a weak form of one-time, non-collusion resistant ABE, which is then lifted to full ABE using IPFE. To encrypt a message $\mu$ from a polynomial-size space<fnref n="3" /> under a policy $f$, they generate secret shares $\text{Share}(\mu, f) \to \mathbf{s} \in \mathbb{Z}_p^k$ and encode them in the ciphertexts of $k$ independent IPFE instances. To generate a key for an attribute vector $\mathbf{x} \in \{0, 1\}^k$, one picks a uniformly random scalar $r$ and generates IPFE secret keys of $r$ for those IPFE instances that correspond to indices in $\Pi_{\mathbf{x}}$:

$$ \begin{array}{l} \text{CP-ABE.CT}_f: \quad \{\text{iCT}_j([\mathbf{s}[j]]_2)\}_{j \in [k]} \\ \text{CP-ABE.DK}_x: \quad [r]_t, \{\text{iDK}_j([r]_1)\}_{j \in \Pi_x} \end{array} \quad [r]_t, \{[r \cdot \mathbf{s}[j]]_t\}_{j \in \Pi_x} $$

IPFE decryption yields target group encodings of $r\mathbf{s}[j]$ for all $j \in \Pi_x$. If $f(\mathbf{x}) = 1$, one can run $\text{FindCoef}(\Pi_x, f) \to \{\omega_j\}_j$ and recover the product $r \cdot \mu$ encoded in $\mathcal{G}_t$:

$$ \sum_{j \in \Pi_x} \omega_j [r \cdot \mathbf{s}[j]]_t = [r \cdot \sum_{j \in \Pi_x} \omega_j \cdot \mathbf{s}[j]]_t = [r \cdot \mu]_t $$

Then one can find $\mu$ by solving the discrete logarithm of $[r \cdot \mu]_t$ in basis $[r]_t$. Under an appropriate hardness assumption, the presence of $r$ prevents adversaries from meaningfully "combining" information obtained from decryptions with different ABE decryption keys.

To turn this into a key-policy scheme, the obvious idea is to flip ciphertexts and decryption keys. However, there is one subtlety: when generating a secret sharing for a policy $f$ during the key generation, the message $\mu$ is not known. So one cannot generate secret shares of $\mu$. Therefore, we generate the secret sharing for a random scalar $s$ which is used to mask $\mu$. Then one uses another IPFE instance to enable decryption:

$$ \begin{array}{l} \text{KP-ABE.CT}_x: \quad \text{iCT}_0([r, \mu]_1), \{\text{iCT}_j([r]_1)\}_{j \in \Pi_x} \\ \text{KP-ABE.DK}_f: \quad \text{iDK}_0([s, 1]_2), \{\text{iDK}_j([\mathbf{s}[j]]_2)\}_{j \in [k]} \end{array} \quad [r \cdot s + \mu]_t, \\ \{[r \cdot \mathbf{s}[j]]_t\}_{j \in \Pi_x} $$

<footnote n="3">³The restriction to a polynomial-size message space is only for notational convenience throughout the technical overview. For superpolynomial size, one can simply view the construction as a KEM with messages in $\mathcal{G}_t$ that can be used as a one-time pad.</footnote>
Similar to above, if $f(\mathbf{x}) = 1$, one can run FindCoef($\Pi_{\mathbf{x}}$, $f$) → $\{\omega_j\}_j$ and recover the message $\mu$ encoded in $\mathbb{G}_t$:

$$[r \cdot s + \mu]_t - \sum_{j \in \Pi_{\mathbf{x}}} \omega_j [r \cdot s[j]]_t = [r \cdot s + \mu]_t - \left[ r \cdot \sum_{j \in \Pi_{\mathbf{x}}} \omega_j s[j] \right]_t = [\mu]_t$$

**MC-ABE for LSS Without Repetitions.** We next discuss how the generation of the ciphertext $CT_{\mathbf{x}}$ can be distributed so as to turn the above key-policy ABE into an MC-ABE. A natural approach is to follow [CDG+18, NPP22] who construct (Decentralized) MCFE for inner products. Even though not explicitly stated as such, they essentially use an independent IPFE instance for each client, and the common randomness $r$ in the ciphertexts facing a secret sharing $(s[j])_j$ in the decryption keys is provided by a random oracle. Translating this idea into our context, each client $i \in [0; n-1]$ holds the master secret keys of $k$ independent IPFE instances, where $k$ is the dimension of the attribute vectors$^4$. The 0-th client additionally holds $iMSK_0$ as it takes the message input. To obtain the common random scalar $[r]_1$ encoded in $\mathbb{G}_1$, we use a hash function $H: \{0, 1\}^* \to \mathbb{G}_1$. To generate a decryption key for an attribute vector $\mathbf{x}_i \in \{0, 1\}^k$ with respect to a label lab, the corresponding client $i \in [n-1]$ computes $[r]_1 \leftarrow H(\text{lab})$ and issues $\{\text{iCT}_{i,j}([r]_1)\}_{j \in \Pi_{\mathbf{x}_i}}$. Similarly, to encrypt a message $\mu$ with respect to $\mathbf{x}_0 \in \{0, 1\}^k$, the 0-th client computes $\{\text{iCT}_{0,j}([r]_1)\}_{j \in \Pi_{\mathbf{x}_0}}$ and additionally provides $\text{iCT}_0([r, \mu]_1)$. Decryption keys $\text{DK}_f$ for policies $f$ are still generated by a central authority, so the policy key generation algorithm does not need to be modified. This leads us to the following MC-ABE for LSS:

$$\begin{array}{l} \text{MC-ABE.CT}_{\mathbf{x}_0}: \text{iCT}_0([r, \mu]_1), \{\text{iCT}_{0,j}([r]_1)\}_{j \in \Pi_{\mathbf{x}_0}} \\ \text{MC-ABE.DK}_{\mathbf{x}_i}: \{\text{iCT}_{i,j}([r]_1)\}_{j \in \Pi_{\mathbf{x}_i}} \\ \text{MC-ABE.DK}_f: \text{iDK}_0([s, 1]_2), \{\text{iDK}_{i,j}([s[i, j]]_2)\}_{\substack{j \in [k] \\ i \in [0; n-1]}} \end{array} \quad \left\{ \begin{array}{l} [r s + \mu]_t, \\ \{[r s[i, j]]_t\}_{\substack{j \in \Pi_{\mathbf{x}_i} \\ i \in [0; n-1]}} \end{array} \right.$$

where $[r]_1 \leftarrow H(\text{lab})$ and $s[i, j]$ denotes the entry of the share vector corresponding to the $j$-th coordinate of $\mathbf{x}_i$ for $i \in [0; n-1]$ and $j \in [k]$. The security notion that we can achieve for this scheme suffers from the same limitations as [CDG+18, NPP22]; most importantly, we cannot prove security under repetitions. Moreover, not being able to prove security under repetitions implies that the encryption algorithm must take a secret key, as otherwise the adversary could create multiple ciphertexts under the same label by herself. The reason for these restrictions is the fact that our only source of randomness is the random oracle whose only input is the label. Hence, to achieve security in a stronger model, our first step is to remove the random oracle from the construction.

**Removing the Random Oracle and Enabling Public Encryption.** In our first attempt above, the random oracle provides common randomness across independently generated ciphertexts and keys. Clearly, this is not possible anymore without a random oracle. Therefore, it seems inevitable to have one client (say, the 0-th) generate all the IPFE ciphertexts $\{\text{iCT}_{i,j}([r]_1)\}_{i,j}$. However, when generating $CT_{\mathbf{x}_0}$, the vectors $\mathbf{x}_1, \dots, \mathbf{x}_{n-1}$ are unknown, so it is unclear which $\text{iCT}_{i,j}([r]_1)$ for $i > 0$ should be included in $CT_{\mathbf{x}_0}$.

As a solution, we let client 0 generate all ciphertexts $\{\text{iCT}_{i,j}([r]_1)\}_{i \in [n-1]}^{j \in [k]}$, but instead of providing them “in the clear”, we hide them with an additional layer of identity-based encryption. Specifically, the 0-th client encrypts each $\text{iCT}_{i,j}([r]_1)$ with respect to the identity $(\text{lab}, j)$ using the public key of client $i$. Correspondingly, client $i \in [n-1]$ provides the identity-based decryption keys $\text{idDK}_i(\text{lab}, j)$ for each $j \in \Pi_{\mathbf{x}_i}$ needed to recover the

<footnote>$^4$Ciphertexts and decryption keys corresponding to the $j$-th IPFE scheme of client $i$ are denoted by $\text{iCT}_{i,j}$ and $\text{idDK}_{i,j}$.</footnote>
IPFE ciphertexts generated by client 0. This idea yields the following MC-ABE for LSS in the standard model:

$$
\begin{equation}
\left[
\begin{array}{@{}l@{}}
\text{CT}_{\mathbf{x}_0}: \quad \left[ \begin{array}{@{}l@{}}
\text{iCT}_0(\llbracket r, \mu \rrbracket_1), \{\text{iCT}_{0,j}(\llbracket r \rrbracket_1)\}_{j \in \Pi_{\mathbf{x}_0}} \\
\phantom{\text{iCT}_0(\llbracket r, \mu \rrbracket_1), \{\text{iCT}_{0,j}(\llbracket r \rrbracket_1)\}_{j \in \Pi_{\mathbf{x}_0}} \\
\{\text{idCT}_i((\text{lab}, j), \text{iCT}_{i,j}(\llbracket r \rrbracket_1))\}_{i \in [n-1]}^{j \in [k]}
\end{array} \right] \\
\\
\text{DK}_{\mathbf{x}_i}: \quad \{\text{idDK}_i(\text{lab}, j)\}_{j \in \Pi_{\mathbf{x}_i}} \\
\\
\text{DK}_f: \quad \text{iDK}_0(\llbracket s, 1 \rrbracket_2), \{\text{iDK}_{i,j}(\llbracket \mathbf{s}[i, j] \rrbracket_2)\}_{i \in [0; n-1]}^{j \in [k]}
\end{array}
\right]
\quad \left\{
\begin{array}{@{}l@{}}
\llbracket r \cdot s + \mu \rrbracket_t, \\
\\
\{\llbracket r \cdot \mathbf{s}[i, j] \rrbracket_t\}_{i \in [0; n]}^{j \in \Pi_{\mathbf{x}_i}}
\end{array}
\right.
\tag{1}
\end{equation}
$$

Here, $r \stackrel{\$}{\leftarrow} \mathbb{Z}_p$ is a fresh random scalar for each ciphertext. Due to this fact, the scheme remains secure even under several encryption queries for the same label and, in particular, enables a public encryption algorithm. Indeed, if each encryption samples a fresh $r \stackrel{\$}{\leftarrow} \mathbb{Z}_p$, then each message $\llbracket \mu \rrbracket_t$ is hidden by a fresh looking mask $\llbracket r \cdot s \rrbracket_t$. So the ability to create ciphertexts by herself does not help the adversary to recover information from a challenge ciphertext anymore.

On the negative side, the scheme in (1) is still not secure under repetitions for slots $i \in [n-1]$. For example, consider an adversary that submits queries for decryption keys $DK_{x_i}$ and $DK_{x'_i}$ for two attribute vectors $\mathbf{x}_i, \mathbf{x}'_i \in \{0, 1\}^k$. Then $DK_{y_i} := DK_{x_i} \cup DK_{x'_i}$ is a decryption key for the vector $\mathbf{y}_i \in \{0, 1\}^k$ having a 1 in all coordinates $j \in [k]$ where $1 \in \{\mathbf{x}[j], \mathbf{x}'[j]\}$. Thus, $DK_{y_i}$ may be used to decrypt ciphertexts that cannot be decrypted by neither $DK_{x_i}$ nor $DK_{x'_i}$.

**MC-ABE for LSS With Repetitions.** To achieve security under repetitions for slots $i \in [n-1]$, we must make sure that multiple decryption keys for the same label-slot pair $(\text{lab}, i)$ cannot be combined in a meaningful way as it is possible for the scheme in (1). In other words, all components of a decryption key $DK_{x_i}$ should “depend on” the entire vector $\mathbf{x}_i$ instead of only a single coordinate $\mathbf{x}_i[j]$. To this end, we now let $DK_{x'_i} = \text{idDK}_i(\text{lab}, \mathbf{x}_i)$ as opposed to $\{\text{idDK}_i(\text{lab}, j)\}_{j \in \Pi_{x'_i}}$. Then security of the MC-ABE under repetitions directly corresponds to the collusion resistance of the employed IBE.

On the other hand, correctness is no longer straightforward. This is because a successful decryption using the new keys requires the 0-th client to provide encryptions of the IPFE ciphertexts $\{\text{iCT}_{i,j}(\llbracket r \rrbracket_1)\}_{i,j}$ with respect to identities that depend on attribute vectors $\mathbf{x}_1, \dots, \mathbf{x}_{n-1}$. These vectors are not given as input and, thus, are unknown at encryption time. Moreover, decryption with a key $DK_f$ is supposed to work with any combination of $\mathbf{x}_1, \dots, \mathbf{x}_{n-1}$ satisfying $f(\mathbf{x}_0, \dots, \mathbf{x}_{n-1}) = 1$. Therefore, the problem is not only that these attribute vectors are unknown, but in general there can be many possible choices that should allow decrypting. In particular, when $f$ is the constant function that always outputs 1, then decryption must succeed for any choice of $\mathbf{x}_1, \dots, \mathbf{x}_{n-1}$. This observation ultimately forces the encryptor to provide encryptions of the IPFE ciphertexts $\{\text{iCT}_{i,j}(\llbracket r \rrbracket_1)\}_{j}$ with respect to every identity $(\text{lab}, \mathbf{x}_i)$ such that $\mathbf{x}_i \in \{0, 1\}^k$, for $i \in [n-1]$. More precisely, a ciphertext $\text{CT}_{\mathbf{x}_0}$ for a message $\mu$ consists of the following components:

$$
\text{CT}_{\mathbf{x}_0} : \left\{ \begin{array}{@{}l@{}}
\text{iCT}_0(\llbracket r_{\mathbf{x}}, \mu \rrbracket_1), \{\text{iCT}_{0,j}(\llbracket r_{\mathbf{x}} \rrbracket_1)\}_{j \in \Pi_{\mathbf{x}_0}}, \\
\\
\{\text{idCT}_i((\text{lab}, \mathbf{x}_i), \text{iCT}_{i,j}(\llbracket r_{\mathbf{x}} \rrbracket_1))\}_{i \in [n-1]}^{j \in \Pi_{\mathbf{x}_i}}
\end{array} \right\}_{\mathbf{x}=(\mathbf{x}_1, \dots, \mathbf{x}_{n-1}) \in \{0, 1\}^{(n-1)k}} \tag{2}
$$

where $r_{\mathbf{x}} \stackrel{\$}{\leftarrow} \mathbb{Z}_p$ for each $\mathbf{x} \in \{0, 1\}^{(n-1)k}$. It is clear that these ciphertexts have exponential size if $k$ or $n$ are chosen too large. However, it remains polynomial if one chooses e.g. $k \cdot n = O(\log \lambda)$ which gives $|\{0, 1\}^{(n-1)k}| = \text{poly}(\lambda)$.
be guaranteed that the choices of $L$ in the 0-th client remain compatible with the IBE keys provided by the other clients. For details, please see Section 5.2.

**Security.** To get a grasp of the security proof, it is instructive to first consider the case where the IPFE is simulation secure. This means the only values that the adversary learns are

* encodings $\llbracket s \rrbracket_2$ of random scalars $s \stackrel{\mathcal{S}}{\leftarrow} \mathbb{Z}_p$ sampled during the key generation and their corresponding share vectors $\llbracket s \rrbracket_2$, and

* target group encodings of the form $\llbracket r \cdot s + \mu \rrbracket_t$ (IPFE instance 0) and $\llbracket r \cdot s[i, j] \rrbracket_t$ (IPFE instance $(i, j)$) for random scalars $r \stackrel{\mathcal{S}}{\leftarrow} \mathbb{Z}_p$ sampled during the encryption of the challenge message.

Importantly, nothing about $r$ is leaked in $\mathbb{G}_1$. So we can rely on the DDH to obtain a fresh looking mask $\llbracket r \cdot s \rrbracket_t$ with a fresh share vector $\llbracket r \cdot s \rrbracket_2$ for each combination of $r$ and $s$. Then we can exploit the one-time security provided by the LSS scheme to replace the individual secret sharings with random values: by the admissibility of the adversary, there does not exist any pair $(r, s)$ such that the adversary has sufficient information about a subset of shares that allows her to recover the mask $\llbracket r \cdot s \rrbracket_t$. Instead, they look uniformly random and, thus, perfectly hide the challenge message.

Unfortunately, simulation security for many ciphertexts is known to be impossible in the standard model [BSW11]. Therefore, we can only rely on an IPFE with indistinguishability-based security. This makes the proof slightly more complex since we cannot directly conclude anymore that the adversary learns the scalars $r$ only as part of the inner products encoded in $\mathbb{G}_t$. To circumvent this problem, we use a primitive called slotted IPFE [LL20a] which is a mix between public-key and private-key IPFE that provides standard security on the public part and additionally hides the function vectors in the private part. Using this primitive, we can move the scalar $r$ from the message vectors encoded in $\mathbb{G}_1$ into a hidden coordinate of the function vectors in $\mathbb{G}_2$. Subsequently, we can rely on the DDH in $\mathbb{G}_2$ and proceed with the proof as in the case of simulation security.

Finally, we want to mention an important detail that occurs during the security proof. The adversary's admissibility condition only covers the case when she obtains at least one key for each slot (via either corruption or attribute key generation queries). Therefore, we must protect against so-called incomplete queries, where the adversary does not submit a query for every slot, but still has sufficient information to decrypt. In the context of IPFE (without access control) this can be done using a primitive called all-or-nothing encoding $[CDSG^{+20}]$. In the context of attribute-based MIFE for attribute-weighted sums, [ATY23] uses a ciphertext-policy ABE for arithmetic branching programs which was recently proposed by Lin and Luo [LL20b]. In our case, we can avoid the usage of a complex primitive like ABE because we can model the completeness condition as part of our policies. This is feasible since our construction can check a global condition before releasing any information. Previous works considered only conjunctions of local checks in each slot which is not powerful enough to verify completeness.

## 2.2 MC-PE from MC-ABE and Lockable Obfuscation

**Lockable Obfuscation.** We employ a primitive called *lockable obfuscation* (LO) [GKW17, WZ17]. Roughly speaking, LO allows to obfuscate a circuit $C$ with respect to a message $\mu$ and a lock value $\sigma$. Correctness asks that an evaluation of the obfuscated circuit on some input $x$ yields $\mu$ if $C(x) = \sigma$ and $\perp$ otherwise. Simulation security requires that if $\sigma$ looks random to the adversary, then the obfuscated circuit is computationally indistinguishable from a garbage program that does not carry any information about $\mu$ or $C$.
**The Compilers of [AYY22].** The authors of [AYY22] present two compilers from MI-ABE to MI-PE which nest several obfuscated circuits in a sophisticated manner. Very roughly, the obfuscated circuit $\tilde{C}_0$ for the zeroth slot takes as input another obfuscated circuit $\tilde{C}_1$ for the first slot, which in turn takes an obfuscated circuit $\tilde{C}_2$ for the second slot and so on until one arrives at the last slot $n-1$. $\tilde{C}_0$ is generated with respect to an attribute $x_0$ and a message $\mu$ whereas the other $\tilde{C}_i$'s only depend on an attribute $x_i$. The crucial part of the construction is to establish "communication" between consecutive circuits without violating attribute privacy. The idea is to build a recursive evaluation chain where the innermost circuit checks the condition $f(x_0, \dots, x_{n-1}) = 1$ using the MI-ABE; and a successful evaluation of an obfuscated circuit $\tilde{C}_i$, for $i \in [n-1]$, unlocks the lock and reveals a secret which is needed for a successful evaluation of $\tilde{C}_{i-1}$.

In their first compiler, these secret values are *global* secrets. This leads to a straightforward construction as all clients know these common secrets when they obfuscate their circuits. However, the supported security model is weak. This is because once the adversary submits any combination of oracle queries that enables a valid decryption process, these global secrets are revealed and security collapses even if all involved oracle queries have the same left and right input. To achieve security in a stronger model, their second compiler avoids these global secrets. However, this makes the construction more complex, and they are able to deal with only two slots. Our new construction can be viewed as a generalization of this arity-2 compiler to any constant arity. We therefore recall the arity-2 construction as a warm-up.

**Construction in the Two-Input Setting.** We start from an MI-ABE (aSetup, aEnc, aKeyGen, aKeyGen, aDec). For notational convenience, we use the shorthand notations $\text{aCT}_\ell(x_0, \mu)$, $\text{aDK}_\ell(i, x_i)$ and $\text{aDK}_\ell(f)$ to denote executions of $\text{aEnc}_\ell(\text{aMPK}_\ell, x_0, \mu)$, $\text{aKeyGen}(\text{aSK}_\ell, x_i)$ and $\text{aKeyGen}(\text{aMSK}_\ell, f)$, for two independently generated aFE instances $(\text{aMPK}_\ell, \text{aMSK}_\ell, \{\text{aSK}_\ell, i\}_i) \leftarrow \text{aSetup}(1^\lambda)$ indexed by $\ell \in \{0, 1\}$. The MI-PE encryptor (client 0) possesses $(\text{aMPK}_0, \text{aSK}_1)$ and the attribute key generator (client 1) possesses $(\text{aMPK}_1, \text{aSK}_0)$. The master secret key contains the ABE master secret keys $(\text{aMSK}_0, \text{aMSK}_1)$. To encrypt a message $\mu$ with respect to an attribute $x_0$, client 0 samples a random lock value $\sigma_0$ and computes $\text{aCT}_0(x_0, \sigma_0)$ and $\text{aDK}_1(1, x_0)$. The final ciphertext is an obfuscation $\tilde{C}_0$ of a circuit $C_0[\text{aCT}_0(x_0, \sigma_0), \text{aDK}_1(1, x_0)]$ with respect to the message $\mu$ and lock value $\sigma_0$. The notation $C[\alpha]$ indicates that the value $\alpha$ is hardwired in the description of the circuit $C$. Similarly, to produce a decryption key with respect to an attribute $x_1$, client 1 samples a lock value $\sigma_1$, generates $\text{aCT}_1(x_1, \sigma_1)$ and $\text{aDK}_0(1, x_1)$ and outputs an obfuscation $\tilde{C}_1$ of a circuit $C_1[\text{aCT}_1(x_1, \sigma_1)]$ with respect to the message $\text{aDK}_0(1, x_1)$ and lock value $\sigma_1$. An MI-PE decryption key consists of a set of MI-ABE decryption keys $\{\text{aDK}_0(f), \text{aDK}_1(f)\}$.

The pivotal point that makes the whole scheme work is the definition of the circuits. Specifically, decryption evaluates the obfuscated outer circuit $\tilde{C}_0$ on input the obfuscated inner circuit $\tilde{C}_1$ and the MI-ABE keys $\{\text{aDK}_0(f), \text{aDK}_1(f)\}$. Suppose that $f(x_0, x_1) = 1$. For a successful decryption, we must unlock $\tilde{C}_0$. The lock value $\sigma_0$ is already hardwired in the circuit $C_0[\text{aCT}_0(x_0, \sigma_0), \text{aDK}_1(1, x_0)]$, however it is hidden in the ciphertext $\text{aCT}_0(x_0, \sigma_0)$. To decrypt this ciphertext, we need the decryption key $\text{aDK}_0(1, x_1)$ embedded in $\tilde{C}_1$. For this reason $C_0[\text{aCT}_0(x_0, \sigma_0), \text{aDK}_1(1, x_0)]$ starts by evaluating $\tilde{C}_1$ on input $(\text{aDK}_1(1, x_0), \text{aDK}_1(f))$. From its inputs, the inner circuit $C_1[\text{aCT}_1(x_1, \sigma_1)]$ obtains everything it needs to decrypt its hardwired ciphertext $\text{aCT}_1(x_a, \sigma_1)$ and to recover the correct lock value $\sigma_1$ which unlocks $\tilde{C}_1$ and reveals $\text{aDK}_0(1, x_1)$. At this point, $C_0[\text{aCT}_0(x_0, \sigma_0), \text{aDK}_1(1, x_0)]$ can perform a similar computation by decrypting the ciphertext $\text{aCT}_0(x_0, \sigma_0)$ and recovering $\sigma_0$. This eventually unlocks $\tilde{C}_0$ and outputs $\mu$. Importantly, this construction does not use global secrets, hence its security is not compromised after one successful decryption.
**Generalization to Constant-Arity MC-ABE.** Our new compiler generalizes this framework to more than two slots and the more general MC-PE model. We will use independent MC-ABE instances for each slot to check if decryption is permitted, and each MC-PE client holds the key of one slot from each MC-ABE instance. Specifically, we let client $i \in [0; n - 1]$ control

* the $i$-th slot of the MC-ABE instances $\ell \in [0; i - 1]$,

* the 0-th slot of the MC-ABE instance $\ell = i$, and

* the $(i+1)$-th slot of the MC-ABE instances $\ell \in [i+1; n - 1]$.

In particular, we note that each MC-PE client is the encryptor in exactly one of the MC-ABE schemes.

To encrypt a message $\mu$ with respect to a label lab and an attribute $x_0$, client 0 samples a random lock value $\sigma_0$ and creates $\text{aCT}_0(\text{lab}, x_0, \sigma_0)$ and $\text{aDK}_\ell(\text{lab}, 1, x_0)$ for all $\ell \in [n-1]$. Then, it issues an obfuscation of a circuit $C_0[\text{aCT}_0(\text{lab}, x_0, \sigma_0), \{\text{aDK}_\ell(\text{lab}, 1, x_0)\}_{\ell \in [n-1]}]$ generated with respect to the message $\mu$ and the lock value $\sigma_0$. Similarly, to generate a key for a label lab and an attribute $x_i$, client $i \in [n-1]$ samples a lock value $\sigma_i$ and creates $\text{aCT}_i(\text{lab}, x_i, \sigma_i)$, $\text{aDK}_\ell(\text{lab}, i, x_i)$ for $\ell \in [0; i - 1]$, and $\text{aDK}_\ell(\text{lab}, i + 1, x_i)$ for $i \in [i + 1; n - 1]$. Then it outputs an obfuscation of a circuit $C_i[\text{aCT}_i, \{\text{aDK}_\ell(\text{lab}, i + 1, x_i)\}_{\ell \in [i+1; n-1]}]$ generated with respect to the message $\{\text{aDK}_\ell(\text{lab}, i, x_i)\}_{\ell \in [0; i-1]}$ and lock value $\sigma_i$. Decryption keys for a policy $f$ are a set of MC-ABE keys $\{\text{aDK}_\ell(f)\}_{\ell \in [0; n-1]}$.

As in the two-input case, the crucial point is to establish communication between the obfuscated circuits in a secure way. However, the nested evaluations become more complex now. We first observe the following properties satisfied by all obfuscated circuits $\tilde{C}_i$ for $i \in [0; n - 1]$:

1. Decryption keys $\text{aDK}_\ell(\text{lab}, i + 1, x_i)$ for $\ell > i$ are hardwired in the description of the circuit. This means they can be accessed during the evaluation of $\tilde{C}_i$ and passed as input to the evaluation of $\tilde{C}_j$ for $j > i$.

2. Decryption keys $\text{aDK}_\ell(\text{lab}, i, x_i)$ for $\ell < i$ are stored as the message of $\tilde{C}_i$ which is revealed in case of a successful evaluation. This means they can be recovered and used during the evaluation of $\tilde{C}_j$ for $j < i$.

Suppose that $f(x_0, \dots, x_{n-1}) = 1$. Decryption evaluates $\tilde{C}_0$ on input the obfuscated circuits $\{\tilde{C}_i\}_{i \in [n-1]}$ and the MC-ABE keys $\{\text{aDK}_\ell(f)\}_{\ell \in [0; n-1]}$. The lock value of $\tilde{C}_0$ is hidden in its hardwired ciphertext $\text{aCT}_0(\text{lab}, x_0, \sigma_0)$. To decrypt this ciphertext, we need the keys $\{\text{aDK}_0(\text{lab}, i, x_i)\}_{i \in [n-1]}$ stored in the messages of $\{\tilde{C}_i\}_{i \in [n-1]}$, so we need to evaluate them first. Specifically, via a chain of recursive calls where each $\tilde{C}_i$ invokes the evaluation of $\tilde{C}_{i+1}$, we arrive at the evaluation of $\tilde{C}_{n-1}$. From property 1, it follows that $\tilde{C}_{n-1}$ receives as input all the keys $\{\text{aDK}_{n-1}(\text{lab}, i, x_i)\}_{i \in [n-1]}$ to decrypt its hardwired ciphertext $\text{aCT}_{n-1}(\text{lab}, x_{n-1}, \sigma_{n-1})$ and to recover the lock value $\sigma_{n-1}$. In this way, $\tilde{C}_{n-1}$ can be unlocked and its message revealed. In the next step, it follows from property 2 that now the evaluation of $\tilde{C}_{n-2}$ has everything it needs to perform a similar computation to recover $\sigma_{n-2}$ and unlock $\tilde{C}_{n-2}$, and so on.

While at first glance it may seem that this decryption procedure is efficient for any (polynomial) number of slots, there is a subtle problem: each obfuscation increases the size of the circuit by a polynomial factor. As we nest the evaluation of the circuits, this leads to an exponential blow-up in the number of slots. Therefore, the decryption algorithm is only efficient for $n = O(1)$, i.e. constant arity.
**Security.** The security proof is a simple sequence of hybrids over all slots from $n-1$ to 0. In each hybrid, if $f(x_0, \dots, x_{n-1}) = 0$, then we can rely on the security of the $i$-th MC-ABE instance to replace the ciphertext $\mathsf{CT}_i(x_i, \sigma_i)$ hardwired in $\tilde{C}_i$ with a ciphertext of the zero string $\mathsf{CT}_i(x_i, 0)$. Then the lock value $\sigma_i$ appears random to the adversary and the obfuscated circuit $\tilde{C}_i$ can be replaced with a simulated obfuscation that carries no information about $x_i$. In the last step, we replace $\tilde{C}_0$ with a simulation that erases all information about $x_0$ and $\mu$. We stress the importance of the fact that the global authorization is checked in each obfuscated circuit independently. Clearly, if a client $i \in [0; n-1]$ is compromised, then the adversary can pick arbitrary attributes $x_i$ and generate MC-ABE decryption keys $\mathsf{DK}_\ell(\mathsf{lab}, i+1, x_i)$ for $\ell > i$ and $\mathsf{DK}_\ell(\mathsf{lab}, i, x_i)$ for $\ell < i$. But this does not help as long as the other clients $j \in [0; n-1] \setminus \{i\}$ do not provide obfuscated circuits $\tilde{C}_j$ for attributes $x_j$ such that $f(x_0, \dots, x_{n-1}) = 1$ for at least one attribute $x_i$. This is because the condition $f(x_0, \dots, x_{n-1}) = 1$ is checked in each obfuscated circuit $\tilde{C}_j$ using its own independent MC-ABE instance.

**Comparison with [FFMV23].** The authors of [FFMV23] build single-key MI-ABE for conjunctions of P. Their nesting technique bears similarities with ours which, in particular, leads to the same limitation that $n = O(1)$. The key difference between the constructions is that they start from a *single-input PE* whereas we start from a *multi-client ABE*. This has a significant impact on the supported policy classes as well as the achieved security level.

For the former, we recall that single-input PE exists for powerful policy classes [GVW15], which is why their construction can evaluate arbitrary local predicates in each slot, but globally they are restricted to conjunctions. On the other hand, MC-ABE from standard assumptions is only known for simple policy classes (also constructed in this work). Nonetheless, these policies are not a conjunction, so the schemes' supported policy classes are incomparable.

To see the impact on security, we recall from the above sketch of the security proof that it is crucial to check the *global* authorization in each obfuscated circuit. Clearly, this is impossible with a single-input PE scheme. (Otherwise, we already had a multi-input PE scheme and there was no need for a compiler). For this reason, the security argument in [FFMV23] relies on the fact that there must exist a (fixed) non-corrupted slot $i$ such that the local predicate is not satisfied for any attribute $x_i$ that is input to a slot-$i$ oracle query. In this case, the chain of nested evaluations breaks at slot $i$ and the message embedded in $\tilde{C}_0$ remains hidden. For two decryption keys $\mathsf{DK}_f$ and $\mathsf{DK}'_f$, the evaluation chains could break at different slots $i \neq i'$. So while these keys might not be individually authorized for decryption, together they could be used to establish a complete decryption chain, which is the reason that the scheme in [FFMV23] is not secure under collusions. On the other hand, our MC-ABE scheme allows to check the global predicate in each step of the nested evaluation. Hence, mixing two keys does not help if neither of them is individually authorized, and we obtain security even under collusions.

# 3 Preliminaries

## 3.1 Notational Conventions

Let $\lambda \in \mathbb{N}$ be the security parameter. Except in the definitions, we will suppress $\lambda$ in subscripts for brevity. A nonnegative function $\varepsilon: \mathbb{N} \to \mathbb{R}$ is negligible if $\varepsilon(\lambda) = O(\lambda^{-n})$ for all $n \in \mathbb{N}$. An algorithm is said to be *efficient* if it runs in probabilistic polynomial time (PPT) in the security parameter.

To avoid confusion, we always write vectors **v** and matrices **A** in boldface and use uppercase letters for the latter. Scalars **s** are written in italics. Unless otherwise stated, all
vectors $\mathbf{v}$ are viewed as column vectors. The corresponding row vector is denoted by $\mathbf{v}^\top$.

**Security Experiments and Distributions.** Let $\mathbf{Exp}$ be an interactive experiment that interacts with an algorithm $\mathcal{A}$ (called the adversary), depends on the security parameter $\lambda$ and has binary outcome. We also refer to such objects as games or hybrids. We let $\mathbf{Exp}_A(1^\lambda) \to 1$" denote the event that the outcome of running $\mathbf{Exp}$ with $\mathcal{A}$ on security parameter $\lambda$ is 1. For two experiments $\mathbf{Exp}^0$ and $\mathbf{Exp}^1$, we define the distinguishing advantage of $\mathcal{A}$ against the tuple $(\mathbf{Exp}^0, \mathbf{Exp}^1)$ as

$$ \mathbf{Adv}_{\mathbf{Exp}^0, \mathbf{Exp}^1, \mathcal{A}}(\lambda) := |\Pr[\mathbf{Exp}_A^1(1^\lambda) \to 1] - \Pr[\mathbf{Exp}_A^0(1^\lambda) \to 1]| . $$

We write $\mathbf{Exp}^0 \approx_c \mathbf{Exp}^1$ if the experiments are computationally indistinguishable, i.e. their distinguishing advantage is negligible for all efficient adversaries $\mathcal{A}$. We write $\mathbf{Exp}^0 \approx_s \mathbf{Exp}^1$ if the experiments are statistically indistinguishable, i.e. their distinguishing advantage is negligible for all (even unbounded) adversaries. We write $\mathbf{Exp}^0 \equiv \mathbf{Exp}^1$ if the experiments are identically distributed, i.e. their distinguishing advantage is 0 for all (even unbounded) adversaries. By default, the term indistinguishable refers to computational indistinguishability.

More general, the same notations can be used for sequences of distributions. Let $D^0 = \{D_\lambda^0\}_{\lambda \in \mathbb{N}}$ and $D^1 = \{D_\lambda^1\}_{\lambda \in \mathbb{N}}$ be two sequences of distributions. For $b \in \{0, 1\}$, we define $\mathbf{Exp}_A^b(1^\lambda)$ as follows: sample $x \stackrel{s}{\leftarrow} D_\lambda^b$, run $\mathcal{A}(1^\lambda, x)$ and use the output of $\mathcal{A}$ as the outcome of the experiment. Then we write $D^0 \approx_c D^1$ (resp. $D^0 \approx_s D^1$, $D^0 \equiv D^1$) if $\mathbf{Exp}_A^0 \approx_c \mathbf{Exp}_A^1$ (resp. $\mathbf{Exp}_A^0 \approx_s \mathbf{Exp}_A^1$, $\mathbf{Exp}_A^0 \equiv \mathbf{Exp}_A^1$).

**Sets and Indexing.** We denote by $\mathbb{Z}$ and $\mathbb{N}$ the sets of integers and natural numbers (positive integers). For integers $m$ and $n$, we write $[m; n]$ to denote the set $\{z \in \mathbb{Z} : m \le z \le n\}$ and let $[n] := [1; n]$. For a prime number $p$, $\mathbb{Z}_p$ denotes the finite field of integers modulo $p$. For a finite set $S$, we let $2^S$ denote the power set of $S$.

To index a vector or the columns of a matrix, we write $\mathbf{v}[i]$ and $\mathbf{A}[j]$. In contrast, objects of some collection that is not regarded as a vector or matrix are indexed using subscripts (or superscripts in some cases). For instance, $\mathbf{v}_i$ represents a vector, not a component of some vector. If $i$ runs through some index set $[n]$, it means that there are $n$ vectors $\mathbf{v}_1, \dots, \mathbf{v}_n$. If the $n$ objects are scalars (or not explicitly vectors), we will write $v_1, \dots, v_n$ instead.

For convenience, objects might be indexed by arbitrary sets, not just integers. For finite sets $\mathbf{s}$, $\mathcal{A}$, we write $A^s := \{(\mathbf{v}[i])_{i \in \mathbf{s}} : \mathbf{v}[i] \in \mathcal{A}\}$ for the set of vectors whose entries are in $\mathcal{A}$ and indexed by $\mathbf{s}$, e.g. $\mathbb{Z}_p^{[n]}$ is just $\mathbb{Z}_p^n$. Suppose $\mathbf{s}_1, \mathbf{s}_2$ are two index sets with $\mathbf{s}_1 \subseteq \mathbf{s}_2$. For a vector $\mathbf{v} \in \mathbb{Z}_p^{\mathbf{s}_2}$, we denote by $\mathbf{u} = \mathbf{v}|_{\mathbf{s}_1}$ its canonical projection onto $\mathbb{Z}_p^{\mathbf{s}_1}$, i.e. $\mathbf{u} \in \mathbb{Z}_p^{\mathbf{s}_1}$ and $\mathbf{u}[i] = \mathbf{v}[i]$ for all $i \in \mathbf{s}_1$. Conversely, for any vector $\mathbf{u} \in \mathbb{Z}_p^{\mathbf{s}_1}$, we write $\mathbf{v} = \mathbf{u}|^{\mathbf{s}_2}$ for its zero-extension into $\mathbb{Z}_p^{\mathbf{s}_2}$, i.e. $\mathbf{v} \in \mathbb{Z}_p^{\mathbf{s}_2}$ and $\mathbf{v}[i] = \mathbf{u}[i]$ if $i \in \mathbf{s}_1$, and $\mathbf{v}[i] = 0$ if $i \in \mathbf{s}_2 \setminus \mathbf{s}_1$.

## 3.2 Pairing Groups and Hardness Assumptions

**Pairing Groups.** Our constructions use a sequence of pairing groups

$$ \mathcal{G} = \{\mathcal{G}_{\lambda} = (\mathcal{G}_{\lambda,1}, \mathcal{G}_{\lambda,2}, \mathcal{G}_{\lambda,t}, g_{\lambda,1}, g_{\lambda,2}, g_{\lambda,t}, e_{\lambda}, p_{\lambda})\}_{\lambda \in \mathbb{N}}, $$

where $\mathcal{G}_{\lambda,1}$ (resp. $\mathcal{G}_{\lambda,2}$, $\mathcal{G}_{\lambda,t}$) is a cyclic group of order $p_\lambda$ generated by $g_{\lambda,1}$ (resp. $g_{\lambda,2}$, $g_{\lambda,t}$), and $e_\lambda : \mathcal{G}_{\lambda,1} \times \mathcal{G}_{\lambda,2} \to \mathcal{G}_{\lambda,t}$ is the pairing operation satisfying $e_\lambda(g_{\lambda,1}^a, g_{\lambda,2}^b) = g_{\lambda,t}^{ab}$ for all integers $a, b$. The group operations and the pairing map are required to be efficiently computable.

Following the implicit notation in [EHK+13], we write $[a]_i$ to denote $g_{\lambda,i}^a$ for $i \in \{1, 2, \dots, t\}$. This notation extends component-wise to matrices and vectors having entries in $\mathbb{Z}_p$.
Equipped with these notations, group operations are written additively and the pairing operation multiplicatively, e.g. $\llbracket A \rrbracket_1 - B \llbracket C \rrbracket_1 D = \llbracket A - BCD \rrbracket_1$ and $\llbracket A \rrbracket_1 \llbracket B \rrbracket_2 = \llbracket AB \rrbracket_t$.

**Computational Assumptions.** We state the assumptions needed for our constructions. Let $\{G_\lambda = (G_{\lambda,1}, G_{\lambda,2}, G_{\lambda,t}, g_{\lambda,1}, g_{\lambda,2}, g_{\lambda,t}, e_\lambda, p_\lambda)\}_{\lambda \in \mathbb{N}}$ be a sequence of pairing groups.

**Definition 1** (Decisional Diffie-Hellman Assumption (DDH)). Let $i \in \{1, 2, t\}$. The DDH assumption holds in $\{G_{\lambda,i}\}_{\lambda \in \mathbb{N}}$ if $\llbracket a, b, ab \rrbracket_i \in \mathbb{N} \approx_c \llbracket a, b, ab + c \rrbracket_i \in \mathbb{N}$ for $a, b, c \stackrel{\mathbb{S}}{\leftarrow} Z_{p_\lambda}$.

**Definition 2** (Symmetric eXternal Diffie-Hellman Assumption (SXDH)). The SXDH assumption holds in $\{G_\lambda\}_{\lambda \in \mathbb{N}}$ if the DDH assumption holds in both $\{G_{\lambda,1}\}_{\lambda \in \mathbb{N}}$ and $\{G_{\lambda,2}\}_{\lambda \in \mathbb{N}}$.

## 3.3 Monotone Access Structures and Linear Secret Sharing Schemes

Let $\mathcal{X} = \{0, 1\}^5$ be the attribute universe with index set $\mathfrak{s}$. An access structure on $\mathcal{X}$ is a collection $\mathcal{S} \subseteq 2^5 \setminus \emptyset$ of nonempty subsets of $\mathfrak{s}$. We call the sets in $\mathcal{S}$ authorized, and those in $2^5 \setminus \mathcal{S}$ unauthorized. Each access structure $\mathcal{S}$ corresponds to an access policy $f: \mathcal{X} \to \{0, 1\}$ defined via

$$f(\mathbf{x}) = \begin{cases} 1 & \text{if } \{i \in \mathfrak{s} : \mathbf{x}[i] = 1\} \in \mathcal{S} \\ 0 & \text{if } \{i \in \mathfrak{s} : \mathbf{x}[i] = 1\} \notin \mathcal{S} . \end{cases}$$

An access structure $\mathcal{S} \subseteq 2^5$ is said to be monotone if the following condition is satisfied for all $S_1, S_2 \subseteq \mathfrak{s}$: if $S_1 \in \mathcal{S}$ and $S_1 \subseteq S_2$, then $S_2 \in \mathcal{S}$. A policy is said to be monotone if its corresponding access structure is monotone.

We next recall the definition of a linear secret sharing scheme.

**Definition 3** (Linear Secret Sharing (LSS) Scheme [BL90, Bei96]). Let $\ell, n \in \mathbb{N}$ and $p$ be a prime number. We denote $\mathbf{e}_1 = (1, 0, \dots, 0)^\top \in \mathbb{Z}_p^n$ the first unit-vector in $\mathbb{Z}_p^n$. A linear secret sharing (LSS) scheme over $\mathbb{Z}_p$ for an access structure $\mathcal{S} \subseteq 2^5$ on an attribute universe $\mathcal{X} = \{0, 1\}^5$ is specified by a share generating matrix $\mathbf{M} \in \mathbb{Z}_p^{n \times \ell}$ and a function $\rho: [\ell] \to \mathfrak{s}$ mapping the columns of $\mathbf{M}$ to indices in $\mathfrak{s}$, which satisfy the following condition:

$$S \in \mathcal{S} \iff \mathbf{e}_1 \in \operatorname{span}\{\mathbf{M}[j] : j \in [\ell], \rho(j) \in S\}. \quad (3)$$

For convenience, we often do not distinguish between an access structure $\mathcal{S}$, its corresponding policy $f$ and a pair $(\mathbf{M}, \rho)$ satisfying (3). In particular, we may write $f = (\mathbf{M}, \rho)$. In order to share a value $s \in \mathbb{Z}_p$ using an LSS scheme over $\mathbb{Z}_p$, one samples $\mathbf{u} \stackrel{\mathbb{S}}{\leftarrow} \mathbb{Z}_p^{n-1}$ and computes the share vector

$$\mathbf{s} = (s, \mathbf{u}[1], \dots, \mathbf{u}[n-1]) \cdot \mathbf{M} \in \mathbb{Z}_p^\ell .$$

Then a set $\{\mathbf{s}[j]\}_{j \in J}$ for some $J \subseteq [\ell]$ can be used to reconstruct $s$ if and only if $\{\rho(j)\}_{j \in J}$ is authorized with respect to the access structure corresponding to $f = (\mathbf{M}, \rho)$. Indeed, in this case there exist coefficients $\omega_1, \dots, \omega_\ell \in \mathbb{Z}_p$ such that $\omega_j = 0$ for all $j \in [\ell] \setminus J$ and $\sum_{j \in [\ell]} \omega_j \mathbf{M}[j] = \mathbf{e}_1$. These coefficients can be used to compute

$$\sum_{j \in J} \omega_j \mathbf{s}[j] = \sum_{j \in [\ell]} \omega_j \mathbf{s}[j] = (s, \mathbf{u}[1], \dots, \mathbf{u}[n-1]) \cdot \sum_{j \in [\ell]} \omega_j \mathbf{M}[j] = s .$$

Lewko and Waters [LW11] presented an LSS scheme for all monotone access structures.
## 3.4 Function-Hiding Slotted Inner-Product Functional Encryption

We recall the definition of slotted IPFE from [LL20a]. Similar to [LL20a, AWY20, LLL22], this primitive will allow us to employ techniques akin to dual system encryption [Wat09, LW10]. To adhere to the formalism used in this work, we present the syntax in a pairing-based setting.

**Definition 4 (Slotted IPFE).** Let $\mathcal{G} = \{\mathcal{G}_\lambda = (\mathcal{G}_{\lambda,1}, \mathcal{G}_{\lambda,2}, \mathcal{G}_{\lambda,t}, g_{\lambda,1}, g_{\lambda,2}, g_{\lambda,t}, e_\lambda, p_\lambda)\}_{\lambda \in \mathbb{N}}$ be a sequence of pairing groups. A slotted IPFE scheme based on $\mathcal{G}$ consists of five efficient algorithms:

*   **Setup(1$^{\lambda}$, $\mathfrak{s}_{pub}, \mathfrak{s}_{pri}) \to (MPK, MSK):** On input the security parameter and two disjoint index sets, the public slot $\mathfrak{s}_{pub}$ and the private slot $\mathfrak{s}_{pri}$, this algorithm outputs a pair of a master public and a master secret key (MPK, MSK). We denote the whole index set by $\mathfrak{s} := \mathfrak{s}_{pub} \cup \mathfrak{s}_{pri}$.

*   **Enc(MSK, $[[x]]_1$) $\to$ CT:** On input a master secret key MSK and an encoding of a vector $x \in \mathbb{Z}_{p_\lambda}^s$ in $\mathcal{G}_{\lambda,1}$, this algorithm outputs a ciphertext CT for $x$.

*   **KeyGen(MSK, $[[y]]_2$) $\to$ SK:** On input a master secret key MSK and an encoding of a vector $y \in \mathbb{Z}_{p_\lambda}^s$ in $\mathcal{G}_{\lambda,2}$, this algorithm outputs a decryption key DK for $y$.

*   **Dec(DK, CT) $\to$ $[[d]]_t$:** On input a decryption key DK and a ciphertext CT, this algorithm outputs an element $[[d]]_t \in \mathcal{G}_{\lambda,t}$.

*   **SlotEnc(MPK, $[[x_{pub}]]_1$) $\to$ CT:** On input a master public key MPK and an encoding of a message vector $x_{pub} \in \mathbb{Z}_{p_\lambda}^s$ in $\mathcal{G}_{\lambda,1}$, this algorithm outputs a ciphertext for the vector $x = x_{pub}|^s \in \mathbb{Z}_{p_\lambda}^s$.

**Correctness.** A slotted IPFE scheme satisfies decryption correctness if for all $\lambda \in \mathbb{N}$, all disjoint index sets $\mathfrak{s}_{pub}, \mathfrak{s}_{pri}$ and all vectors $x, y \in \mathbb{Z}_{p_\lambda}^s$, it holds that

$$ \Pr \left[ \text{Dec}(\text{DK}, \text{CT}) = [[\langle x, y \rangle]]_t \left| \begin{array}{l} (\text{MPK}, \text{MSK}) \leftarrow \text{Setup}(1^{\lambda}, \mathfrak{s}_{\text{pub}}, \mathfrak{s}_{\text{pri}}) \\ \text{CT} \leftarrow \text{Enc}(\text{MSK}, [[x]]_1) \\ \text{DK} \leftarrow \text{KeyGen}(\text{MSK}, [[y]]_2) \end{array} \right. \right. = 1 . $$

Furthermore, we say that a slotted IPFE scheme satisfies slot-mode correctness if for all $\lambda \in \mathbb{N}$, all disjoint index sets $\mathfrak{s}_{pub}, \mathfrak{s}_{pri}$ and $x_{pub} \in \mathbb{Z}_{p_\lambda}^s$, the following distributions $D_0, D_1$ are identical:

$$ \begin{aligned} D_0 &= \left\{ (\text{MPK}, \text{MSK}, \text{CT}) \left| \begin{array}{l} (\text{MPK}, \text{MSK}) \leftarrow \text{Setup}(1^{\lambda}, \mathfrak{s}_{\text{pub}}, \mathfrak{s}_{\text{pri}}) \\ \text{CT} \leftarrow \text{Enc}(\text{MSK}, [[x_{\text{pub}}]^s]]_1) \end{array} \right. \right\}, \\ D_1 &= \left\{ (\text{MPK}, \text{MSK}, \text{CT}) \left| \begin{array}{l} (\text{MPK}, \text{MSK}) \leftarrow \text{Setup}(1^{\lambda}, \mathfrak{s}_{\text{pub}}, \mathfrak{s}_{\text{pri}}) \\ \text{CT} \leftarrow \text{SlotEnc}(\text{MPK}, [[x_{\text{pub}}]]_1) \end{array} \right. \right\}, \end{aligned} $$

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

**Security.** We define adaptive function-hiding IND-CPA security.

**Definition 5 (Function-Hiding Security).** For a slotted IPFE scheme iFE and a PPT adversary $\mathcal{A}$, we define the security experiment $\text{Exp}_{\text{iFE},\mathcal{A}}^{\text{sl-ipfe-}b}(1^{\lambda})$ as shown in Figure 1. The oracles $\text{OKeyGen}$ and $\text{OEnc}$ can be called in any order and any (polynomial) number of times. The adversary $\mathcal{A}$ is admissible with respect to $\mathcal{Q}_{\text{enc}}$ and $\mathcal{Q}_{\text{key}}$, denoted by $\text{adm}(\mathcal{A}) = 1$, if all $([[x_0]]_1, [[x_1]]_1) \in \mathcal{Q}_{\text{enc}}$ and $([y_0]]_2, [[y_1]]_2) \in \mathcal{Q}_{\text{key}}$ satisfy $\langle x_0, y_0 \rangle = \langle x_1, y_1 \rangle$ and $y_0|_{\mathfrak{s}_{pub}} = y_1|_{\mathfrak{s}_{pub}}$. Otherwise, we say that $\mathcal{A}$ is not admissible and write $\text{adm}(\mathcal{A}) = 0$. We call iFE function-hiding if $\text{Exp}_{\text{iFE},\mathcal{A}}^{\text{sl-ipfe-}0}(1^{\lambda}) \approx_c \text{Exp}_{\text{iFE},\mathcal{A}}^{\text{sl-ipfe-}1}(1^{\lambda})$.
<figure><img src="image_2.png" /><figcaption>Figure 1: Security game $\mathbf{Exp}_{\text{IFE},\mathcal{A}}^{\text{sl-ipfe-b}}(1^{\lambda})$ for Definition 5</figcaption></figure>

There exists a slotted IPFE scheme based on $\mathcal{G}$ which can be proven (adaptively) function-hiding under the SXDH$^6$ assumption in $\mathcal{G}$. The construction is based on a sequence of works [ALS16, Wee17, LV16, Lin17] and has been described explicitly in [LL20a].

## 3.5 Identity-Based Encryption

We recall the definition of identity-based encryption (IBE).

**Definition 6 (Identity-Based Encryption).** Let $\mathcal{M} = \{\mathcal{M}_{\lambda}\}_{\lambda \in \mathbb{N}}$ and $\mathcal{I} = \{\mathcal{I}_{\lambda}\}_{\lambda \in \mathbb{N}}$ be sequences of message and identity spaces, respectively. An *identity-based encryption scheme* for $\mathcal{M}$ and $\mathcal{I}$ consists of four efficient algorithms:

*   **Setup(1$^{\lambda}$) → (MPK, MSK):** On input the security parameter, this algorithm outputs a pair of a master public key MPK and a master secret key MSK.

*   **Enc(MPK, i, µ) → CT:** On input a master public key MSK, an identity $i \in \mathcal{I}_{\lambda}$ and a message $\mu \in \mathcal{M}_{\lambda}$, this algorithm outputs a ciphertext CT for $\mu$ created with respect to $i$.

*   **KeyGen(MSK, i') → DK:** On input a master secret key MSK and an identity $i' \in \mathcal{I}_{\lambda}$, this algorithm outputs a decryption key DK for $i'$.

*   **Dec(DK, CT) → $\mu' \lor \bot$:** On input a decryption key DK and a ciphertext CT, this algorithm outputs an element $\mu' \in \mathcal{M}_{\lambda}$ or $\bot$.

**Correctness.** An IBE scheme is said to be *correct* if for all $\lambda \in \mathbb{N}$, all identities $i \in \mathcal{I}_{\lambda}$ and all messages $\mu \in \mathcal{M}_{\lambda}$, it holds that

$$ \Pr \left[ \text{Dec}(\text{DK}, \text{CT}) = \mu \mid \begin{array}{l} (\text{MPK}, \text{MSK}) \leftarrow \text{Setup}(1^{\lambda}) \\ \text{CT} \leftarrow \text{Enc}(\text{MPK}, i, \mu) \\ \text{DK} \leftarrow \text{KeyGen}(\text{MSK}, i) \end{array} \right] = 1, $$

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

**Security.** We define adaptive IND-CPA security.

**Definition 7 (Security).** For an IBE scheme IBE and a PPT adversary $\mathcal{A}$, we define the security experiment $\mathbf{Exp}_{\text{IBE},\mathcal{A}}^{\text{ibe-b}}(1^{\lambda})$ as shown in Figure 2. The oracle $\mathcal{O}\text{KeyGen}$ can be called any (polynomial) number of times whereas the oracle $\mathcal{O}\text{Enc}$ can be called only once. We call IBE *secure* if $\mathbf{Exp}_{\text{IBE},\mathcal{A}}^{\text{ibe-0}}(1^{\lambda}) \approx_c \mathbf{Exp}_{\text{IBE},\mathcal{A}}^{\text{ibe-1}}(1^{\lambda})$.

There exist various IBE schemes in the group-based setting, e.g. [Wat09, CLL$^+$13, JR17].

<footnote>$^6$More precisely, the security proof only relies on MDDH$_k$, for any $k > 1$, in both $\mathbb{G}_1$ and $\mathbb{G}_2$. This assumption is implied by SXDH on $\mathcal{G}$.</footnote>
<figure><img src="image_3.png" /><figcaption>Figure 2: Security game $\mathbf{Exp}_{\text{IBE},\mathcal{A}}^{\text{ibe-b}}(1^{\lambda})$ for Definition 7</figcaption></figure>

## 3.6 Lockable Obfuscation

We recall the definition of a lockable obfuscator [GKW17, WZ17]. Given polynomials $n = n(\lambda)$, $m = m(\lambda)$ and $d = d(\lambda)$, we denote by $C_{n,m,d}(\lambda)$ the class of depth $d(\lambda)$ circuits with $n(\lambda)$ bits input and $m(\lambda)$ bits output.

**Definition 8 (Lockable Obfuscation).** Let $\mathcal{M} = \{\mathcal{M}_{\lambda}\}_{\lambda \in \mathbb{N}}$ be a sequence of message spaces and $\{C_{n,m,d}(\lambda)\}_{\lambda \in \mathbb{N}}$ a sequence of circuit classes. A lockable obfuscator for $\mathcal{M}$ and $\mathcal{C}$ is a tuple of two efficient algorithms:

*   **Obf(1$^{\lambda}$, C, $\mu$, $\sigma$) → ($\tilde{C}$):** On input 1$^{\lambda}$, a circuit $C \in C_{n,m,d}(\lambda)$, a message $\mu \in \mathcal{M}_{\lambda}$ and a “lock value” $\sigma \in \{0, 1\}^{m(\lambda)}$, this algorithm outputs an obfuscated circuit $\tilde{C}$.

*   **Eval($\tilde{C}$, $x$) → $\mu' \lor \perp$:** On input an obfuscated circuit $\tilde{C}$ and an input $x \in \{0, 1\}^{n(\lambda)}$, this algorithm outputs a value $\mu' \in \mathcal{M}_{\lambda}$ or $\perp$.

**Correctness.** A lockable obfuscator satisfies (perfect) correctness if for all $\lambda \in \mathbb{N}$, all circuits $C \in C_{n,m,d}(\lambda)$, all messages $\mu \in \mathcal{M}_{\lambda}$ and all inputs $x \in \{0, 1\}^{n(\lambda)}$, the following two implications are satisfied:

1. if $C(x) = \sigma$, then $\text{Eval}(\text{Obf}(1^{\lambda}, C, \mu, \sigma), x) = \mu$

2. if $C(x) \neq \sigma$, then $\text{Eval}(\text{Obf}(1^{\lambda}, C, \mu, \sigma), x) = \perp$

**Security.** We define security against multiple challenges. In [AYY22], this definition was observed to be equivalent to the original single-challenge version from [GKW17].

**Definition 9 (Security against Multiple Queries).** For a lockable obfuscation scheme $\text{LObf} =$ ($\text{Obf}$, $\text{Eval}$) and an efficient algorithm $\text{Sim}$, we define the following oracles:

*   $\mathcal{O}\text{Obf}^0(C, \mu)$: sample $\sigma \leftarrow \{0, 1\}^{m(\lambda)}$ and return $\tilde{C} \leftarrow \text{Obf}(1^{\lambda}, C, \mu, \sigma)$

*   $\mathcal{O}\text{Obf}^1(C, \mu)$: return $\text{Sim}(1^{\lambda}, 1^{|C|}, 1^{|\mu|})$

We call $\text{LObf}$ secure if there exists a PPT simulator $\text{Sim}$ such that for all PPT adversaries $\mathcal{A}$, there exists a negligible function $\text{negl}(\cdot)$ such that

$$ \mathbf{Adv}_{\text{LObf},\mathcal{A}}^{\text{lock}}(\lambda) := \left| \Pr[\mathcal{A}^{\mathcal{O}\text{Obf}^1} \to 1] - \Pr[\mathcal{A}^{\mathcal{O}\text{Obf}^0} \to 1] \right| \le \text{negl}(\lambda) . $$

Perfectly correct lockable obfuscators for general circuits are known to exist under the LWE assumption [GKW17, GKVW20].
# 4 Multi-Client Attribute-Based and Predicate Encryption

We define multi-client attribute-based encryption (MC-ABE) and multi-client predicate encryption (MC-PE). Since the only difference between these notions lies in the security game, we unify the syntax of the algorithms.

**Definition 10 (Public-Key Syntax).** Let $n = n(\lambda)$ be a polynomial. Furthermore, let $\mathcal{M} = \{\mathcal{M}_\lambda\}_{\lambda \in \mathbb{N}}$ be a sequence of message spaces, $\mathcal{X} = \{\mathcal{X}_\lambda\}_{\lambda \in \mathbb{N}}$ a sequence of attribute universes, $\mathcal{L} = \{\mathcal{L}_\lambda\}_{\lambda \in \mathbb{N}}$ a sequence of label spaces and $\mathcal{F} = \{\mathcal{F}_\lambda\}_{\lambda \in \mathbb{N}}$ a sequence of policy classes, where each policy $f_\lambda \in \mathcal{F}_\lambda$ maps from $\mathcal{X}_\lambda^n$ to $\{0, 1\}$. An MC-ABE (resp. MC-PE) scheme for $\mathcal{M}$, $\mathcal{X}$, $\mathcal{F}$ and $\mathcal{L}$ consists of five efficient algorithms:

*   **Setup(1^\lambda) → (MPK, MSK, \{SK_i\}_{i \in [n-1]}):** On input the security parameter $1^\lambda$, this algorithm outputs a pair of master public key MPK and master secret key MSK as well as a set of secret keys $\{SK_i\}_{i \in [n-1]}$.

*   **Enc(MPK, lab, $x_0$, $\mu$) → CT\textsubscript{lab}:** On input the master public key MPK, a label lab $\in \mathcal{L}_\lambda$, an attribute $x_0 \in \mathcal{X}_\lambda$ and a message $\mu \in \mathcal{M}_\lambda$, this algorithm outputs a ciphertext CT\textsubscript{lab}.

    In case of an MC-ABE scheme, we assume that CT\textsubscript{lab} implicitly includes $x_0$.

*   **AKeyGen SK\textsubscript{i}, lab, $x_i$) → DK\textsubscript{lab,i}:** On input a secret key SK\textsubscript{i} for some $i \in [n-1]$, a label lab $\in \mathcal{L}_\lambda$ and an attribute $x_i \in \mathcal{X}_\lambda$, this algorithm outputs a decryption key DK\textsubscript{lab,i}.

    In case of an MC-ABE scheme, we assume that DK\textsubscript{lab,i} implicitly includes $x_i$.

*   **PKeyGen(MSK, $f$) → DK\textsubscript{$f$}:** On input the master secret key MSK and a policy $f \in \mathcal{F}_\lambda$, this algorithm outputs a decryption key DK\textsubscript{$f$}.

    We assume that DK\textsubscript{$f$} implicitly includes a description of $f$.

*   **Dec(DK\textsubscript{$f$}, \{DK\textsubscript{lab,i}\}_{i \in [n-1]}, CT\textsubscript{lab}) → $\mu' \lor \bot$:** On input a decryption key DK\textsubscript{$f$} for a policy $f \in \mathcal{F}_\lambda$, a set of attribute decryption keys $\{DK\textsubscript{lab,i}\}_{i \in [n-1]}$ generated with respect to some label lab $\in \mathcal{L}_\lambda$ and a ciphertext CT\textsubscript{lab} created with respect to the same label lab, this algorithm outputs an element $\mu' \in \mathcal{M}_\lambda$ or $\bot$.

Below, we discuss security in the public-key and secret-key setting. In the secret-key setting, we slightly change the syntax, as we find it more intuitive to let the encryption algorithm take a secret key $SK_0$ instead of a master public key MPK if this key is not given to the adversary.

**Remark 1 (Comparison With the Syntax of [AYY22, FFMV23, ARYY23]).** Recent papers [AYY22, FFMV23, ARYY23] consider a varying syntax for MI-ABE and MI-PE. Our definition follows [ARYY23] as their syntax is the most natural one for our MC-ABE constructions. In fact, when removing the MCFE-related labels from our definition and replacing all keys with a unique master secret key, we almost obtain their definition except for one minor modification: their scheme defines $n-1$ potentially different algorithms $\{\text{KeyGen}_i\}_{i \in [n-1]}$ for the attribute key generation whereas we consider only one algorithm AKeyGen. In our constructions, the attribute key generation works in exactly the same way for all clients. Therefore, this modification does not have any impact on the semantics.

**Correctness.** An MC-ABE (resp. MC-PE) is *correct* if for every $\lambda, n \in \mathbb{N}$, label lab $\in \mathcal{L}_\lambda$, message $\mu \in \mathcal{M}_\lambda$, policy $f \in \mathcal{F}_\lambda$ and attributes $x_0, \dots, x_{n-1} \in \mathcal{X}_\lambda$ such that
<figure><img src="image_4.png" /><figcaption>Figure 3: Security game $\mathbf{Exp}_{\text{aFE},\mathcal{A}}^{\text{mc-abe-b}}(1^{\lambda})$ for Definition 11</figcaption></figure>

$f(x_0, \dots, x_{n-1}) = 1$, it holds that

$$ \Pr \left[ \mu' = \mu \left| \begin{array}{l} (\text{MPK}, \text{MSK}, \{\text{SK}_i\}_{i \in [n-1]}) \leftarrow \text{Setup}(1^{\lambda}) \\ \text{CT}_{\text{lab}} \leftarrow \text{Enc}(\text{MPK}, \text{lab}, x_0, \mu) \\ \forall i \in [n-1]: \text{DK}_{\text{lab},i} \leftarrow \text{AKeyGen}(\text{SK}_i, \text{lab}, x_i) \\ \text{DK}_f \leftarrow \text{PKeyGen}(\text{MSK}, f) \\ \mu' := \text{Dec}(\text{DK}_f, \{\text{DK}_{\text{lab},i}\}_{i \in [n-1]}, \text{CT}_{\text{lab}}) \end{array} \right. \right] = 1 $$

**Security.** We define security for MC-ABE in the public-key setting as well as security for MC-PE in the secret-key setting.

**Definition 11** (Public-Key Security for MC-ABE). Let $xxx \in \{\text{sel}, \text{adap}\}$ and $yyy \in \{\text{norep}, \text{rep}\}$. For an MC-ABE scheme aFE and a PPT adversary $\mathcal{A}$, we define the experiment $\mathbf{Exp}_{\text{aFE},\mathcal{A}}^{\text{mc-abe-b}}(1^{\lambda})$ as shown in Figure 3. The oracles $\mathcal{O}\text{Corrupt}$, $\mathcal{O}\text{Enc}$, $\mathcal{O}\text{AKeyGen}$ and $\mathcal{O}\text{PKeyGen}$ can be called in any order and any polynomial number of times, except for $\mathcal{O}\text{Enc}$ which can be called only once. Let $(\text{lab}, x_0, \mu^0, \mu^1)$ denote the single query to $\mathcal{O}\text{Enc}$. The adversary $\mathcal{A}$ is admissible, denoted by $\text{adm}(\mathcal{A}) = 1$, if it satisfies the following conditions:

1. For all $f \in \mathcal{Q}_{\text{pkey}}$ and $x_1, \dots, x_{n-1} \in \mathcal{X}_{\lambda}$ such that $(i, \text{lab}, x_i) \in \mathcal{Q}_{\text{akey}}$ for all $i \in [n-1] \setminus \mathcal{C}$, it holds $f(x_0, \dots, x_{n-1}) = 0$.

2. If $xxx = \text{sel}$, then the adversary submits the queries to $\mathcal{O}\text{Corrupt}$, $\mathcal{O}\text{Enc}$ and $\mathcal{O}\text{AKeyGen}$ upfront in one shot.

3. If $yyy = \text{norep}$, then for each $i \in [n-1]$ and $\text{lab} \in \mathcal{L}$ the adversary submits at most one query of the form $\mathcal{O}\text{AKeyGen}(i, \text{lab}, \star)$, i.e. we have $|\{x_i \in \{0, 1\}^k : (i, \text{lab}, x_i) \in \mathcal{Q}_{\text{akey}}\}| \le 1$.

Otherwise, we say that $\mathcal{A}$ is not admissible and write $\text{adm}(\mathcal{A}) = 0$. We call aFE $xxx-yyy$-secure if $\mathbf{Exp}_{\text{aFE},\mathcal{A}}^{\text{mc-abe-0}}(1^{\lambda}) \approx_c \mathbf{Exp}_{\text{aFE},\mathcal{A}}^{\text{mc-abe-1}}(1^{\lambda})$.

**Definition 12** (Secret-Key Security for MC-PE). Let $xxx \in \{\text{sel}, \text{adap}\}$ and $yyy \in \{\text{norep}, \text{rep}\}$. For an MC-PE scheme pFE and a PPT adversary $\mathcal{A}$, we define the experiment $\mathbf{Exp}_{\text{pFE},\mathcal{A}}^{\text{mc-pe-b}}(1^{\lambda})$ as shown in Figure 4. The oracles $\mathcal{O}\text{Corrupt}$, $\mathcal{O}\text{Enc}$, $\mathcal{O}\text{AKeyGen}$ and $\mathcal{O}\text{PKeyGen}$ can be called in any order and any polynomial number of times. Let $\text{lab} \in \mathcal{L}$.
Initialize(1^λ):
$\overline{C}, \mathcal{Q}_{\text{enc}}, \mathcal{Q}_{\text{akey}}, \mathcal{Q}_{\text{pkey}} \leftarrow \emptyset$
($\{\text{SK}_i\}_{i \in [0; n-1]}, \text{MSK}) \leftarrow \text{Setup}(1^\lambda)$

$\mathcal{O}\text{Corrupt}(i)$ for $i \in [0; n-1]$:
$\overline{C} \leftarrow \mathcal{C} \cup \{i\}; \text{return } \text{SK}_i$

$\mathcal{O}\text{Enc}(\text{lab}, x_0^0, x_0^1, \mu^0, \mu^1)$:
$\overline{\mathcal{Q}_{\text{enc}} \leftarrow \mathcal{Q}_{\text{enc}} \cup \{(\text{lab}, x_0^0, x_0^1, \mu^0, \mu^1)\}}$
Return $\text{CT} \leftarrow \text{Enc}(\text{SK}_1, \text{lab}, x_0^b, \mu^b)$

$\mathcal{O}\text{AKeyGen}(i, \text{lab}, x_i^0, x_i^1)$:
$\overline{\mathcal{Q}_{\text{akey}} \leftarrow \mathcal{Q}_{\text{akey}} \cup \{(i, \text{lab}, x_i^0, x_i^1)\}}$
Return $\text{DK}_i \leftarrow \text{AKeyGen}(\text{SK}_i, \text{lab}, x_i^b)$

$\mathcal{O}\text{PKeyGen}(f)$:
$\overline{\mathcal{Q}_{\text{pkey}} \leftarrow \mathcal{Q}_{\text{pkey}} \cup \{f\}}$
Return $\text{DK}_f \leftarrow \text{PKeyGen}(\text{MSK}, f)$

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

<caption>Figure 4: Security game $\mathbf{Exp}_{\text{pFE},\mathcal{A}}^{\text{mc-pe-}b}(1^{\lambda})$ for Definition 12</caption>

We define $\mathcal{Q}'_{0,\text{lab}} = \{(x_0^0, x_0^1, \mu^0, \mu^1) : (\text{lab}, x_0^0, x_0^1, \mu^0, \mu^1) \in \mathcal{Q}_{\text{enc}}\}$ and $\mathcal{Q}'_{i,\text{lab}} = \{(x_i^0, x_i^1) : (i, \text{lab}, x_i^0, x_i^1) \in \mathcal{Q}_{\text{akey}}\}$ as well as

$$
\begin{align*}
\mathcal{Q}_{0,\text{lab}} &= \begin{cases} \mathcal{Q}'_{0,\text{lab}} & \text{if } 0 \in [0; n-1] \setminus \mathcal{C} \\ \mathcal{Q}'_{0,\text{lab}} \cup \{(x_0, x_0, \mu, \mu) : x_0 \in \mathcal{X}, \mu \in \mathcal{M}\} & \text{if } 0 \in \mathcal{C} \end{cases} \\
\mathcal{Q}_{i,\text{lab}} &= \begin{cases} \mathcal{Q}'_{i,\text{lab}} & \text{if } i \in [0; n-1] \setminus \mathcal{C} \\ \mathcal{Q}'_{i,\text{lab}} \cup \{(x_i, x_i) : x_i \in \mathcal{X}\} & \text{if } i \in \mathcal{C} \end{cases}
\end{align*}
$$

for all $i \in [n-1]$. The adversary $\mathcal{A}$ is *admissible*, denoted by $\text{adm}(\mathcal{A}) = 1$, if it satisfies
the following conditions:

1. For all lab $\in \mathcal{L}$, $(x_0^0, x_0^1, \mu^0, \mu^1) \in \mathcal{Q}_{0,\text{lab}}$, $(x_1^0, x_1^1) \in \mathcal{Q}_{1,\text{lab}}$, $(x_2^0, x_2^1) \in \mathcal{Q}_{2,\text{lab}}$, ..., $(x_{n-1}^0, x_{n-1}^1) \in \mathcal{Q}_{n-1,\text{lab}}$ and policies $f \in \mathcal{Q}_{\text{pkey}}$, it holds

$$
f(x_0^0, \dots, x_{n-1}^0) = f(x_0^1, \dots, x_{n-1}^1) = 0 \quad \text{or} \quad (x_0^0, \dots, x_{n-1}^0, \mu^0) = (x_0^1, \dots, x_{n-1}^1, \mu^1).
$$

2. If xxx = sel, then the adversary cannot call $\mathcal{O}\text{Corrupt}$, $\mathcal{O}\text{Enc}$ and $\mathcal{O}\text{AKeyGen}$ anymore after submitting the first query to $\mathcal{O}\text{PKeyGen}$.

3. If yyy = norep, then for each $i \in [n-1]$ and lab $\in \mathcal{L}$ the adversary submits at most one query of the form $\mathcal{O}\text{AKeyGen}(i, \text{lab}, \star, \star)$, i.e. we have $|\{x_i \in \{0, 1\}^k : (i, \text{lab}, x_i) \in \mathcal{Q}_{\text{akey}}\}| \le 1$.

Otherwise, we say that $\mathcal{A}$ is not admissible and write $\text{adm}(\mathcal{A}) = 0$. We call pFE xxx-yyy-
secure if $\text{Exp}_{\text{pFE},\mathcal{A}}^{\text{mc-pe-0}}(1^{\lambda}) \approx_c \text{Exp}_{\text{pFE},\mathcal{A}}^{\text{mc-pe-1}}(1^{\lambda})$.

5 Construction of MC-ABE

In this section, we present our constructions for MC-ABE. For this, we need the following
two definitions.

**Complete Policies.** Let $k, n \in \mathbb{N}$. We define the function $c: \{0, 1\}^{[n-1]\times\{0\}} \to \{0, 1\}$ by
$c((x_{i,0})_{i \in [n-1]}) = \bigwedge_{i \in [n-1]} x_{i,0}$. Given a policy $f: \{0, 1\}^{[0;n-1]\times[k]} \to \{0, 1\}$, we write $(c \wedge f)$
for the complete policy

$$
(c \wedge f) : \{0, 1\}^{[0; n-1] \times [0; k]} \to \{0, 1\} \\
(x_{i,j})_{i,j} \mapsto c((x_{i,0})_{i \in [n-1]}) \wedge f((x_{i,j})_{(i,j) \in [0; n-1] \times [k]}).
$$
We note that $c$ is monotone (so having certificates of $\{\neg x_{i,0}\}_{i \in [n-1]}$ is never relevant) and that $(c \wedge f)$ does not depend on the attribute $x_{0,0}$ at all. Taking these facts into account would allow for a slight improvement in the efficiency of Constructions 2 and 5 below, as some of the generated iFE instances are never used. We disregard this fact for the sake of a clearer write-up.

**Transformation to Monotone Policies.** For $(x_{i,j})_{i,j} \in \{0,1\}^{[0;n-1]\times[0;k]}$, we define $(\bar{x}_{i,j}^{\beta})_{i,j} \in \{0,1\}^{[0;n-1]\times[0;k]\times\{0,1\}}$ by $\bar{x}_{i,j}^1 = x_{i,j}$ and $\bar{x}_{i,j}^0 = 1 - x_{i,j}$. Given a policy $f: \{0,1\}^{[0;n-1]\times[0;k]} \to \{0,1\}$ computable by an NC$^1$ circuit, we construct the corresponding monotone policy $\bar{f}: \{0,1\}^{[0;n-1]\times[0;k]\times\{0,1\}} \to \{0,1\}$ as follows: first, we view $f$ as a Boolean formula consisting of (fan-in 1) $\neg$ gates and (fan-in 2) $\wedge$ and $\vee$ gates. Then, using De Morgan laws, we push the $\neg$ gates to the leaves such that all internal nodes consist only of $\wedge$ and $\vee$ gates, while leaves are labeled by either attributes or their negations. Finally, for each $(i,j) \in [0;n-1] \times [0;k]$ we identify the attribute $x_{i,j} \in \{0,1\}$ with the attribute $\bar{x}_{i,j}^1$ and the negation of $x_{i,j}$ with $\bar{x}_{i,j}^0$. The resulting formula $\bar{f}$ is monotone and equivalent to $f$ in the sense that it satisfies $\bar{f}((\bar{x}_{i,j}^{\beta})_{i,j}^{\beta}) = f((x_{i,j})_{i,j})$ for all inputs $(x_{i,j})_{i,j} \in \{0,1\}^{[0;n-1]\times[0;k]}$.

We combine the transformation to monotone policies with complete policies. Given an NC$^1$ policy $f: \{0,1\}^{[0;n-1]\times[k]} \to \{0,1\}$, we denote by $(c \wedge f): \{0,1\}^{[0;n-1]\times[k]} \times \{0,1\} \to \{0,1\}$ the monotone policy obtained by applying the above transformation to the complete policy $(c \wedge f): \{0,1\}^{[0;n-1]\times[k]} \to \{0,1\}$.

## 5.1 MC-ABE Without Repetitions

We start with the description of our MC-ABE for LSS without repetitions. As explained in Section 2, this construction can be lifted to MC-ABE for NC$^1$ policies when not considering corruptions.

**Construction 2 (MC-ABE for LSS Without Repetitions).** Let $k, n = \text{poly}(\lambda)$. For a vector $\mathbf{x} \in \{0,1\}^k$, we denote $\Pi_{\mathbf{x}} = \{j \in [k] : \mathbf{x}[j] = 1\}$. Our construction uses the following ingredients:

* A slotted IPFE scheme iFE = (iSetup, iEnc, iKeyGen, iDec) based on a pairing group $\mathbb{G} = (\mathbb{G}_1, \mathbb{G}_2, \mathbb{G}_t, g_1, g_2, g_t, e, p)$.

* An identity-based encryption scheme idFE = (idSetup, idEnc, idKeyGen, idDec) with identity space $\mathcal{I} = \mathcal{L} \times [0; k]$ for $\mathcal{L} = \{0,1\}^{\text{poly}(\lambda)}$ and message space being the ciphertext space of iFE.

The MC-ABE scheme aFE for $n$ clients and LSS policies with label space $\mathcal{L}$, message space $\mathcal{M} = \mathbb{G}_t$ and attribute universe $\mathcal{X} = \{0,1\}^k$ works as follows:

Setup($1^{\lambda}$) takes as input the security parameter $1^{\lambda}$ and generates

$$ \begin{align*} (\text{iMPK}_0, \text{iMSK}_0) &\leftarrow \text{iSetup}(1^{\lambda}, \{1, 2\}, \{3\}) \\ \{(\text{iMPK}_{i,j}, \text{iMSK}_{i,j})\} &\leftarrow \text{iSetup}(1^{\lambda}, \{1\}, \{2\}) \}_{(i,j) \in ([0;n-1]\times[0;k])} \\ \{(\text{idMPK}_i, \text{idMSK}_i)\} &\leftarrow \text{idSetup}(1^{\lambda}) \}_{i \in [n-1]} . \end{align*} $$

Then it outputs $(\text{MPK}, \text{MSK}, \{\text{SK}_i\}_{i \in [n-1]})$ as follows:

$$ \begin{align*} \text{MPK} &= (\text{iMPK}_0, \{\text{iMPK}_{i,j}\}_{(i,j) \in ([0;n-1] \times [0;k])}, \{\text{idMPK}_i\}_{i \in [n-1]}) \\ \text{MSK} &= (\text{iMSK}_0, \{\text{iMSK}_{i,j}\}_{(i,j) \in ([0;n-1] \times [0;k])}, \\ \{\text{SK}_i = \text{idMSK}_i\}_{i \in [n-1]} & . \end{align*} $$

We implicitly parse these keys in the algorithms below.
Enc(MPK, lab, $\mathbf{x}_0$, $\llbracket \mu \rrbracket_t$) takes as input MPK, a label lab $\in \mathcal{L}$, an attribute $\mathbf{x}_0 \in \{0, 1\}^k$ and a message $\llbracket \mu \rrbracket_t \in \mathbb{G}_t$. The algorithm samples random elements $\llbracket r \rrbracket_1, \llbracket \sigma \rrbracket_1 \stackrel{\$}{\leftarrow} \mathbb{G}_1$, computes $\llbracket d \rrbracket_t = \llbracket \sigma + \mu \rrbracket_t$ and generates

$$
\begin{align*}
\text{iCT}_0 &\leftarrow \text{iSlotEnc}(\text{iMPK}_0, \llbracket (r, \sigma) \rrbracket_1) \\
\{\text{iCT}_{i,j} &\leftarrow \text{iSlotEnc}(\text{iMPK}_{i,j}, \llbracket r \rrbracket_1) \}_{(i,j) \in \{0\} \times \Pi_{\mathbf{x}_0} \cup [n-1] \times [0;k]} \\
\{\text{idCT}_{i,j} &\leftarrow \text{idEnc}(\text{idMPK}_i, (\text{lab}, j), \text{iCT}_{i,j}) \}_{(i,j) \in [n-1] \times [0;k]} .
\end{align*}
$$

Then it outputs $\text{CT}_{\text{lab}} = (\llbracket d \rrbracket_t, \text{iCT}_0, \{\text{iCT}_{0,j}\}_{j \in \Pi_{\mathbf{x}_0}}, \{\text{idCT}_{i,j}\}_{(i,j) \in [n-1] \times [0;k]}).$

AKeyGen SK, lab, x_i takes as input SK_i for some i \in [n-1], a label lab \in L and an attribute x_i \in \{0, 1\}^k. Then the algorithm outputs the decryption key DK_{lab,i} = \{idDK_{i,j}\}_{j \in \{0\} \cup \Pi_{x_i}} computed as follows:

$$
\{\mathrm{idDK}_{i,j} \leftarrow \mathrm{idKeyGen}(\mathrm{idMSK}_i, (\mathrm{lab}, j))\}_{j \in \{0\} \cup \Pi_{x_i}} .
$$

PKeyGen(MSK, f) takes as input MSK and a monotone policy f. Let (c ∧ f) = (M ∈ Z_{p}^{m×l}, ρ: [l] → ([0; n − 1] × [0; k])) . The algorithm samples s ← Z_{p} and u ← Z_{p}^{m−1}, computes s = (s, u^{T}) · M and generates

$$
\begin{align*}
\text{iDK}_0 &\leftarrow \text{iKeyGen}(\text{iMSK}_0, \llbracket (s, 1, 0) \rrbracket_2) \\
\{\text{iDK}_j &\leftarrow \text{iKeyGen}(\text{iMSK}_{\rho(j)}, \llbracket (\mathbf{s}[j], 0) \rrbracket_2) \}_{j \in [l]} .
\end{align*}
$$

Finally, it outputs $DK_f = \{iDK_j\}_{j \in [0; l]}$.

Dec(DK$_f$, {DK$_{lab,i}$}$_{i \in [n-1]}$, CT$_{lab}$) takes as input a decryption key DK$_f$ for a policy f, a set of decryption keys {DK$_{lab,i}$}$_{i \in [n-1]}$ generated with respect to attributes $\mathbf{x}_1, \dots, \mathbf{x}_{n-1} \in \{0, 1\}^k$ and a label lab $\in \mathcal{L}$, and a ciphertext CT$_{lab}$ created with respect to an attribute $\mathbf{x}_0 \in \{0, 1\}^k$ and the same label lab. We parse DK$_f$, {DK$_{lab,i}$}$_{i \in [n-1]}$ and CT$_{lab}$ as in the algorithms above. Let (c ∧ f) = (M ∈ Z_{p}^{m×l}, ρ: [l] → ([0; n − 1] × [0; k])) . If X = ⋃_{i∈[0;n-1]} ({i} × ({0} ∪ Π_{x_i}) ∩ ρ([l]) does not satisfy the policy (c ∧ f), then the algorithm outputs ⊥. Otherwise, it decrypts

$$
\{\text{iCT}_{i,j} \leftarrow \text{idDec}(\text{idDK}_{i,j}, \text{idCT}_{i,j})\}_{(i,j) \in X \cap ([n-1] \times [0;k])},
$$

and finds coefficients $\omega_1, \dots, \omega_l \in \mathbb{Z}_p$ such that $\sum_{j \in [l]} \omega_j \mathbf{M}[j] = \mathbf{e}_1$ and $\omega_j = 0$ for all $j \notin \rho^{-1}(X)$. Finally, the algorithm computes

$$
\llbracket d_0 \rrbracket_t \leftarrow \text{iDec}(\text{iDK}_0, \text{iCT}_0) \\
\{ \llbracket d_j \rrbracket_t \leftarrow \text{iDec}(\text{iDK}_j, \text{iCT}_{\rho(j)}) \}_{j \in \rho^{-1}(X)},
$$

and outputs $\llbracket \mu' \rrbracket_t = \llbracket d \rrbracket_t - \llbracket d_0 \rrbracket_t + \sum_{j \in \rho^{-1}(X)} \omega_j \llbracket d_j \rrbracket_t$.

**Correctness.** By the correctness of idFE and iFE, we have $d_0 = rs + \sigma$ and, for all $j \in \rho^{-1}(X)$, $d_j = rs[j]$. Note that $\cup_{i \in [n-1]} \{(i, 0)\} \subseteq X$, so $X$ always satisfies c. If additionally $f(\mathbf{x}_0, \dots, \mathbf{x}_{n-1}) = 1$, then $X$ is authorized with respect to $c \wedge f$. In this case, we conclude from the correctness of the LSS scheme that

$$
\mu' = d - d_0 + \sum_{j \in \rho^{-1}(X)} \omega_j d_j = (\sigma + \mu) - (rs + \sigma) + r \cdot \underbrace{\sum_{j \in \rho^{-1}(X)} \omega_j s[j]}_{= s} = \mu
$$
**Security.** We prove selective security without repetitions.

**Proposition 3.** If the DDH assumption holds in $\mathbb{G}_2$, iFE is slot-mode correct and function-hiding and idFE is secure, then Construction 2 is **sel-norep-secure**.

When instantiating iFE with the slotted ABE from [LL20a] and idFE with the IBE from [CLL+13, JR17]$^7$, we obtain the following theorem.

**Theorem 4.** Assuming SXDH on pairings, there exist

* a **sel-norep-secure** MC-ABE for LSS, and

* a **sel-norep-secure** MC-ABE for NC$^1$ without corruptions.

*Proof* (Proposition 3). We consider a sequence $G_0^0, \dots, G_6^0, G_6^1, \dots, G_0^1$ of hybrid games, where $G_0^b = \text{Exp}_{\text{aFE},A}^{\text{mc-abe-b}}(1^\lambda)$. We argue $G_0^0 \equiv G_6^1$ and $G_{\nu-1}^b \approx_c G_\nu^b$ for $\nu \in [6]$ and $b \in \{0, 1\}$. Then the claim follows via a hybrid argument. Modifications between consecutive games are highlighted using **boxes**.

**Game $G_0^b$:** This is $\text{Exp}_{\text{aFE},A}^{\text{mc-abe-b}}(1^\lambda)$. In particular, for the reply to the (single) encryption query $\mathcal{O}\text{Enc}(\text{lab}, \mathbf{x}_0, [[\mu^0]]_t, [[\mu^1]]_t)$, the challenger samples random elements $[[r]]_1, [[\sigma]]_1 \stackrel{\$}{\leftarrow} \mathbb{G}_1$, computes $[[d]]_t := [[\sigma + \mu^b]]_t$, generates

$$ 
\begin{aligned}
\text{iCT}_0 &\leftarrow \text{iSlotEnc}(\text{iMPK}_0, [[(r, \sigma)]_1) \\
\{\text{iCT}_{i,j} &\leftarrow \text{iSlotEnc}(\text{iMPK}_{i,j}, [[r]]_1)\}_{(i,j) \in \{0\} \times \Pi_{\mathbf{x}_0} \cup [n-1] \times [0;k]} \\
\{\text{idCT}_{i,j} &\leftarrow \text{idEnc}(\text{idMPK}_i, (\text{lab}, j), \text{iCT}_{i,j})\}_{(i,j) \in [n-1] \times [0;k]},
\end{aligned}
$$

and sends $\text{CT}_{\text{lab}} = ([[d]]_t, \text{iCT}_0, \{\text{iCT}_{0,j}\}_{j \in \Pi_{\mathbf{x}_0}}, \{\text{idCT}_{i,j}\}_{(i,j) \in [n-1] \times [0;k]})$ to $\mathcal{A}$.

**Game $G_1^b$:** This game is the same as $G_0^b$, except that the challenger computes

$$ 
\begin{aligned}
\text{iCT}_0 &\leftarrow \text{iEnc}(\text{iMSK}_0, [[(r, \sigma, 0)]_1) \\
\{\text{iCT}_{i,j} &\leftarrow \text{iEnc}(\text{iMSK}_{i,j}, [[(r, 0)]_1])\}_{(i,j) \in \{0\} \times \Pi_{\mathbf{x}_0} \cup [n-1] \times [0;k]}.
\end{aligned}
$$

We have $G_0^b \equiv G_1^b$ which follows from the slot-mode correctness of iFE.

**Game $G_2^b$:** We define the set $J^{\ge 1}$ containing the indices of all ciphertexts $\text{idCT}_{i,j}$ that the adversary is able to decrypt:

$$ J^{\ge 1} = (C \times [0; k]) \cup \{(i, j) : \exists (i, \text{lab}, \mathbf{x}_i) \in \mathcal{Q}_{\text{akey}} \text{ s.t. } (\mathbf{x}_i[j] = 1 \lor j = 0)\}. $$

This game is the same as $G_1^b$, except that the challenger now computes

$$ \text{iCT}_{i,j} \leftarrow \begin{cases} \text{iEnc}(\text{iMSK}_{i,j}, [[(r, 0)]_1) & \text{if } (i, j) \in J^{\ge 1} \\ \text{iEnc}(\text{iMSK}_{i,j}, [[(0, 0)]_1) & \text{if } (i, j) \notin J^{\ge 1}. \end{cases} $$

We have $G_1^b \approx_c G_2^b$ from the security of idFE.

**Game $G_3^b$:** This game is the same as $G_2^b$, except that we hardwire the encryption query into the decryption keys. Initially, the challenger samples $r, \sigma \stackrel{\$}{\leftarrow} \mathbb{Z}_p$ and answers to the

<footnote>$^7$The seminal adaptively secure group-based (H)IBE is [Wat09] but it relies on both DDH and D-Lin.</footnote>
selective encryption query by sending $CT_{lab} = (\llbracket d \rrbracket_t = \llbracket \sigma + \mu^b \rrbracket_t, iCT_0, \{iCT_{0,j}\}_{j \in \Pi_{x_0}}, \{idCT_{i,j}\}_{(i,j) \in [n-1] \times [0;k]})$ computed as follows:

$$
\begin{align*}
iCT_0 &\leftarrow \text{iEnc}(\text{iMSK}_0, \llbracket (0, 0, 1) \rrbracket_1) \\
iCT_{i,j} &\leftarrow \begin{cases} \text{iEnc}(\text{iMSK}_{i,j}, \llbracket (0, 1) \rrbracket_1) & \text{if } (i, j) \in J \\ \text{iEnc}(\text{iMSK}_{i,j}, \llbracket (0, 0) \rrbracket_1) & \text{if } (i, j) \notin J \end{cases} \\
idCT_{i,j} &\leftarrow \text{idEnc}(\text{idMPK}_i, (\text{lab}, j), iCT_{i,j}),
\end{align*}
$$

where $J = J^{\ge 1} \cup \{(0, j) : \mathbf{x}_0[j] = 1\}$. Upon receiving a query $\mathcal{OPKeyGen}(f)$ with $(c \land f) = (\mathbf{M} \in \mathbb{Z}_p^{m \times l}, \rho: [l] \to ([0; n-1] \times [0; k]))$, it samples $s \leftarrow \mathbb{Z}_p$, $\mathbf{u} \leftarrow \mathbb{Z}_p^{m-1}$ and computes $\mathbf{s} = (s, \mathbf{u}^{\top}) \cdot \mathbf{M}$. Then it sends $\text{DK}_f = \{\text{iDK}_{\kappa}\}_{\kappa \in [0; l]}$ to $\mathcal{A}$ generated as follows:

$$
\begin{align*}
iDK_0 &\leftarrow \text{iKeyGen}(\text{iMSK}_0, \llbracket (s, 1, \underline{r \cdot s + \sigma}) \rrbracket_2) \\
iDK_{\kappa} &\leftarrow \begin{cases}
\text{iKeyGen}(\text{iMSK}_{\rho(\kappa)}, \llbracket (\mathbf{s}[\kappa], \underline{r \cdot s[\kappa]}) \rrbracket_2) & \text{if } \rho(\kappa) \in J \\
\text{iKeyGen}(\text{iMSK}_{\rho(\kappa)}, \llbracket (\mathbf{s}[\kappa], 0) \rrbracket_2) & \text{if } \rho(\kappa) \notin J.
\end{cases}
\end{align*}
$$

As the public parts of the iFE keys and the inner products between vectors embedded
in the iFE keys and ciphertexts do not change, it follows $G_2^b \approx_c G_3^b$ from the function-
hiding security of iFE.

**Game** $G_4^b$: This game is the same as $G_3^b$ except that the challenger embeds a fresh secret sharing in each decryption key. Specifically, upon receiving a query $\mathcal{OPKeyGen}(f)$ with $(c \land f) = (\mathbf{M}, \rho)$, the challenger samples $s, t \stackrel{\$}{\leftarrow} \mathbb{Z}_p$ and $\mathbf{u}, \mathbf{v} \stackrel{\$}{\leftarrow} \mathbb{Z}_p^{m-1}$, computes $\mathbf{s} = (s, \mathbf{u}^{\top}) \cdot \mathbf{M}$ and $\mathbf{t} = (t, \mathbf{v}^{\top}) \cdot \mathbf{M}$ and sends $\text{DK}_f = \{\text{iDK}_{\kappa}\}_{\kappa \in [0;\ell]}$ to $\mathcal{A}$ generated as follows:

$$
\begin{align*}
iDK_0 &\leftarrow \text{iKeyGen}(\text{iMSK}_0, \llbracket (s, 1, \mathbf{t} + \sigma) \rrbracket_2) \\
iDK_{\kappa} &\leftarrow \begin{cases}
\text{iKeyGen}(\text{iMSK}_{\rho(\kappa)}, \llbracket (\mathbf{s}[\kappa], \mathbf{t}[\kappa]) \rrbracket_2) & \text{if } \rho(\kappa) \in J \\
\text{iKeyGen}(\text{iMSK}_{\rho(\kappa)}, \llbracket (\mathbf{s}[\kappa], 0) \rrbracket_2) & \text{if } \rho(\kappa) \notin J.
\end{cases}
\end{align*}
$$

It is not hard to see that $G_3^b \approx_c G_4^b$ under the DDH assumption in $\mathbb{G}_2$. (Note that we
can exploit the random self-reducibility of the DDH problem here, so a single DDH
instance suffices).

Let $f \in \mathcal{Q}_{\text{pkey}}$ and $(c \land f) = (\mathbf{M} \in \mathbb{Z}_p^{m \times l}, \rho: [l] \to ([0; n-1] \times [0; k]))$. We let $M_f = \text{span}\{\mathbf{M}[\kappa] : \kappa \in [l], \rho(\kappa) \in J\}$ be the vector space spanned by the columns of $\mathbf{M}$ associated with attributes in $J$. Furthermore, let $M_f^{\perp}$ denote the orthogonal complement of $M_f$ and $A_f^{\perp}$ the affine space of $M_f^{\perp}$ containing all vectors whose first coordinate is 1. We argue that $A_f^{\perp}$ is nonempty. To do so, we distinguish two cases.

1. If there exists $i \in [n-1]$ such that $i \notin \mathcal{C}$ and $\mathcal{Q}_{\text{akey}}$ does not contain a tuple of the form $(i, \text{lab}, \star)$, then $J \cap ([n-1] \times \{0\})$ does not satisfy $c$ (and thus $(c \land f)$). Hence, we have $\mathbf{e}_1 \notin M_f$ which implies that $A_f^{\perp}$ is nonempty.

2. If there exists a tuple $(i, \mathbf{lab}, \mathbf{x}_i) \in \mathcal{Q}_{akey}$ for all $i \in [n-1] \setminus \mathcal{C}$, then it follows from the admissibility of $\mathcal{A}$ that $J \cap ([n-1] \times k)$ cannot satisfy $f$ (and thus $(c \land f)$), which implies that $\mathbf{e}_1 \notin M_f$ and $A_f^{\perp}$ is nonempty.

**Game** $G_5^b$: This game is the same as $G_4^b$, except that we modify how the challenger generates the share vector **t** for the reply to a query $\mathcal{OPKeyGen}(f)$. Let $(c \land f) =$
($\mathbf{M}, \rho$). In $G_4^b$, the challenger samples $t \stackrel{\$}{\leftarrow} \mathbb{Z}_p$, $\mathbf{v} \stackrel{\$}{\leftarrow} \mathbb{Z}_p^{m-1}$ and computes $\mathbf{t} = (t, \mathbf{v}^\top) \cdot \mathbf{M}$. In the current game, the challenger picks an additional vector $(1, \bar{\mathbf{v}})^\top \in A_f^\perp$ and sets

$$ \mathbf{t} = (t, \mathbf{v}^\top) \cdot \mathbf{M} + (0, t\bar{\mathbf{v}}^\top) \cdot \mathbf{M} . $$

The distributions $\{\mathbf{v} : \mathbf{v} \stackrel{\$}{\leftarrow} \mathbb{Z}_p^{m-1}\}$ and $\{\mathbf{v} + t\bar{\mathbf{v}} : \mathbf{v} \stackrel{\$}{\leftarrow} \mathbb{Z}_p^{m-1}\}$ are identical for any $\bar{\mathbf{v}} \in \mathbb{Z}_p^{m-1}$. The first distribution corresponds to $G_4^b$ and the second one to $G_5^b$ (followed by the same post-processing), so we have $G_4^b \equiv G_5^b$.

**Game $G_6^b$:** This game is the same as $G_5^b$ except that we change the behavior of the key generation oracle upon receiving a query $\text{OPKeyGen}(f)$. Let $(c \wedge f) = (\mathbf{M}, \rho)$. As in the previous hybrid, the challenger samples $s, t \stackrel{\$}{\leftarrow} \mathbb{Z}_p$ and $\mathbf{u}, \mathbf{v} \stackrel{\$}{\leftarrow} \mathbb{Z}_p^{m-1}$ and computes $\mathbf{s} = (s, \mathbf{u}^\top) \cdot \mathbf{M}$. In the current hybrid, it then generates $\text{DK}_f = \{\text{iDK}_\kappa\}_{\kappa \in [0; \ell]}$ as follows:

$$ \begin{aligned} \text{iDK}_0 &\leftarrow \text{iKeyGen}(\text{iMSK}_0, \llbracket (s, 1, t + \sigma) \rrbracket_2) \\ \text{iDK}_\kappa &\leftarrow \begin{cases} \text{iKeyGen}(\text{iMSK}_{\rho(\kappa)}, \llbracket (\mathbf{s}[\kappa], (0, \mathbf{v}^\top) \cdot \mathbf{M}[\kappa]) \rrbracket_2) & \text{if } \rho(\kappa) \in J \\ \text{iKeyGen}(\text{iMSK}_{\rho(\kappa)}, \llbracket (\mathbf{s}[\kappa], 0) \rrbracket_2) & \text{if } \rho(\kappa) \notin J, \end{cases} \end{aligned} $$

whereas in $G_5^b$, the challenger additionally picks $(1, \bar{\mathbf{v}})^\top \in A_f^\perp$ and computes

$$ \text{iDK}_\kappa \leftarrow \text{iKeyGen}(\text{iMSK}_{\rho(\kappa)}, \llbracket (\mathbf{s}[\kappa], (t, (\mathbf{v} + t\bar{\mathbf{v}})^\top) \cdot \mathbf{M}[\kappa]) \rrbracket_2) $$

for all $\kappa \in [\ell]$ such that $\rho(\kappa) \in J$. We can observe that

$$ (t, (\mathbf{v} + t\bar{\mathbf{v}})^\top) \cdot \mathbf{M}[\kappa] = (0, \mathbf{v}^\top) \cdot \mathbf{M}[\kappa] + t(1, \bar{\mathbf{v}}^\top) \cdot \mathbf{M}[\kappa] = (0, \mathbf{v}^\top) \cdot \mathbf{M}[\kappa] , $$

where the last equality follows from the fact that $(1, \bar{\mathbf{v}}^\top) \in M_f^\perp$ and $\mathbf{M}[\kappa] \in M_f$. Thus, we have $G_5^b \equiv G_6^b$. We notice that in $G_6^b$ the random element $\llbracket t \rrbracket_2 \stackrel{\$}{\leftarrow} \mathbb{G}_2$ appears only in $\text{iDK}_0$, so it perfectly masks $\llbracket \sigma \rrbracket_2$. From this, it follows in turn that $\llbracket \sigma \rrbracket_t$ serves as a perfect mask for the challenge message $\llbracket \mu^b \rrbracket_t$ in $\llbracket d \rrbracket_t = \llbracket \sigma + \mu^b \rrbracket_t$, and we conclude that $G_6^0 \equiv G_6^1$.

□

## 5.2 MC-ABE With Repetitions

In this section, we present our construction of MC-ABE in the stronger security model with repetitions.

**Our Policy Classes.** We consider various policy classes $\mathcal{F}$ containing policies of the form $f: \{0, 1\}^{[0;n-1]\times[k]} \to \{0, 1\}$.

* **Small Parameters.** Let $k, n$ such that $kn = O(\log \lambda)$, i.e. the total length of the input is logarithmic in $\lambda$. We let $\mathcal{F}^{\text{log-att}}$ denote the class of all policies with input $\{0, 1\}^{[0;n-1]\times[k]}$ computable by an NC¹ circuit and, for $\mathbf{x}_0, \dots, \mathbf{x}_n \in \{0, 1\}^k$, we define the sets

$$ \Pi_{\mathbf{x}_0}^{\text{log-att}'} = \{ (\mathbf{y}'_0, \dots, \mathbf{y}'_{n-1}) : \mathbf{y}'_0 = \mathbf{x}_0 \wedge \mathbf{y}'_1, \dots, \mathbf{y}'_{n-1} \in \{0, 1\}^k \} , $$

and $\Omega_{\mathbf{x}_i}^{\text{log-att}'} = \{\mathbf{x}_i\}$ for $i \in [n-1]$.
• **NC⁰ Policies.** Let $k, n = \text{poly}(\lambda)$ and $d = O(1)$ be some fixed upper bound on the depth of the considered circuits. Then each policy depends on at most $\tau = 2^d = O(1)$ out of the $kn$ input bits. We denote by $\mathcal{F}^{\text{const-dep}}$ the set of all NC⁰ policies with depth $d$ and input $\{0, 1\}^{[0:n-1]\times[k]}$. For $\mathbf{x}_0, \dots, \mathbf{x}_n \in \{0, 1\}^k$, we define the sets

$$ \Pi_{\mathbf{x}_0}^{\text{const-dep}'} = \left\{ (\mathbf{y}'_0, \dots, \mathbf{y}'_{n-1}) : \begin{array}{l} \mathbf{y}'_0 = \mathbf{x}_0 \wedge \mathbf{y}'_1, \dots, \mathbf{y}'_{n-1} \in \{0, 1, \perp\}^k \\ \text{s.t.} \quad \sum_{i \in [0; n-1]} \delta(\mathbf{y}'_i) = \tau \end{array} \right\} \\ \\ \Omega_{\mathbf{x}_i}^{\text{const-dep}'} = \left\{ \mathbf{z}'_i \in \{0, 1, \perp\}^k : (\forall j \in [k], \mathbf{z}'_i[j] \in \{\mathbf{x}_i[j], \perp\}) \wedge (\delta(\mathbf{z}'_i) \le \tau) \right\}, $$

where $\delta(\mathbf{y}) = |\{j \in [k] : \mathbf{y}[j] \in \{0, 1\}\}|$ denotes the number of coordinates being not equal to $\perp$.

• **Threshold Policies.** Let $k, n = \text{poly}(\lambda)$. Instead of a constant input locality, we may also consider policies, where every authorized set has a constant-size subset that is also authorized. This property is satisfied by e.g. threshold policies with a constant threshold $\tau = O(1)$. We denote by $f^{\text{t-thr}}$ the threshold policy which allows the reconstruction of the secret from arbitrary $t$ (out of the total of $kn$) shares. Then we define the policy class $\mathcal{F}^{\leq \text{const-thr}} = \{f^{\text{t-thr}} : t \in [\tau]\}$ and, for $\mathbf{x}_0, \dots, \mathbf{x}_n \in \{0, 1\}^k$, we set

$$ \Pi_{\mathbf{x}_0}^{\leq \text{const-thr}'} = \left\{ (\mathbf{y}'_0, \dots, \mathbf{y}'_{n-1}) : \begin{array}{l} \mathbf{y}'_0 = \mathbf{x}_0 \wedge \mathbf{y}'_1, \dots, \mathbf{y}'_{n-1} \in \{1, \perp\}^k \\ \text{s.t.} \quad \sum_{i \in [0; n-1]} \delta(\mathbf{y}'_i) = \tau \end{array} \right\} \\ \\ \Omega_{\mathbf{x}_i}^{\leq \text{const-thr}'} = \left\{ \mathbf{z}'_i \in \{1, \perp\}^k : (\forall j \in [k], \mathbf{z}'_i[j] \in S_{\mathbf{x}_i[j]} ) \wedge (\delta(\mathbf{z}'_i) \le \tau) \right\}, $$

where $S_0 = \{\perp\}$ and $S_1 = \{1, \perp\}$. Note that threshold policies are in particular monotone policies, which is why we can pick $\mathbf{y}'_i, \mathbf{z}'_i \in \{1, \perp\}^k$ as opposed to $\mathbf{y}'_i, \mathbf{z}'_i \in \{0, 1, \perp\}^k$. This will improve the efficiency of the scheme as it reduces the size of the sets $\Pi_{\mathbf{x}_0}^{\leq \text{const-thr}'}$ and $\Omega_{\mathbf{x}_i}^{\leq \text{const-thr}'}$.

Conversely, we define the policy class $\mathcal{F}^{\geq \text{const-thr}} = \{f^{\text{t-thr}} : t \in [kn - \tau; kn]\}$ and the sets

$$ \Pi_{\mathbf{x}_0}^{\geq \text{const-thr}'} = \left\{ (\mathbf{y}'_0, \dots, \mathbf{y}'_{n-1}) : \begin{array}{l} \mathbf{y}'_0 = \mathbf{x}_0 \wedge \mathbf{y}'_1, \dots, \mathbf{y}'_{n-1} \in \{1, \perp\}^k \\ \text{s.t.} \quad \sum_{i \in [0; n-1]} \delta(\mathbf{y}'_i) \geq kn - \tau \end{array} \right\} $$

and $\Omega_{\mathbf{x}_i}^{\geq \text{const-thr}'} = \{\mathbf{z}'_i\}$ where $\mathbf{z}'_i \in \{1, \perp\}^k$ is defined coordinate-wise as $\mathbf{z}'_i[j] = s_{\mathbf{x}_i[j]}$ for all $j \in [k]$ where $s_0 = \perp$ and $s_1 = 1$.

As in Construction 2, we must protect against incomplete queries by considering the complete policy ($c \wedge f$) instead of $f$. For this, we define

$$ \Pi_{\mathbf{x}_0}^{\text{type}} = \left\{ (\mathbf{y}_0, \dots, \mathbf{y}_{n-1}) : \begin{array}{l} \mathbf{y}_0 = (\perp, \mathbf{y}'_0) \wedge \mathbf{y}_1 = (1, \mathbf{y}'_1) \wedge \dots \wedge \mathbf{y}_{n-1} = (1, \mathbf{y}'_{n-1}) \\ \text{s.t.} \quad (\mathbf{y}'_0, \dots, \mathbf{y}'_{n-1}) \in \Pi_{\mathbf{x}_0}^{\text{type}'} \end{array} \right\} \\ \\ \Omega_{\mathbf{x}_i}^{\text{type}} = \{\mathbf{z}_i = (1, \mathbf{z}'_i) : \mathbf{z}'_i \in \Omega_{\mathbf{x}_i}^{\text{type}}\}, $$

where $\text{type} \in \{\text{log-att}, \text{const-dep}, \leq \text{const-thr}, \geq \text{const-thr}\}$ and $i \in [n-1]$.

**Construction 5 (MC-ABE with Repetitions).** Let type $\in \{\text{log-att}, \text{const-loc}, \leq \text{const-thr}, \geq \text{const-thr}\}$. If type = log-att, pick $k$ and $n$ such that $kn = O(\log \lambda)$. Otherwise, let $k = n = \text{poly}(\lambda)$. Our construction uses the following ingredients:

• A slotted IPFE scheme iFE = (iSetup, iEnc, iKeyGen, iDec) based on a pairing group $\mathbb{G} = (\mathbb{G}_1, \mathbb{G}_2, \mathbb{G}_t, g_1, g_2, g_t, e, p)$.
* An identity-based encryption scheme idFE = (idSetup, idEnc, idKeyGen, idDec) with identity space $\mathcal{I} = \mathcal{L} \times \{0, 1\}^{[0;k]}$ for $\mathcal{L} = \{0, 1\}^{\text{poly}(\lambda)}$ and message space being the ciphertext space of iFE

The MC-ABE scheme aFE for $n$ clients and the policy class $\mathcal{F}^{\text{type}}$ with message space $\mathcal{M} = \mathbb{G}_t$, label space $\mathcal{L}$ and attribute universe $\mathcal{X} = \{0, 1\}^k$ works as follows:

Setup($1^{\lambda}$) takes as input the security parameter $1^{\lambda}$ and generates

$$ 
\begin{aligned}
& (\text{iMPK}_0, \text{iMSK}_0) \leftarrow \text{iSetup}(1^{\lambda}, \{1, 2\}, \{3\}) \\
& \{ (\text{iMPK}_{i,j}^{\beta}, \text{iMSK}_{i,j}^{\beta}) \leftarrow \text{iSetup}(1^{\lambda}, \{1\}, \{2\}) \}_{(i,j) \in [0; n-1] \times [0;k]}^{\beta \in \{0,1\}} \\
& \{ (\text{idMPK}_i, \text{idMSK}_i) \leftarrow \text{idSetup}(1^{\lambda}) \}_{i \in [n-1]} .
\end{aligned}
$$

Then it outputs $(\text{MPK}, \text{MSK}, \{\text{SK}_i\}_{i \in [n-1]})$ as follows:

$$ 
\begin{aligned}
\text{MPK} &= (\text{iMPK}_0, \{\text{iMPK}_{i,j}^{\beta}\}_{(i,j) \in [0; n-1] \times [0;k]}, \{\text{idMPK}_i\}_{i \in [n-1]}) \\
\text{MSK} &= (\text{iMSK}_0, \{\text{iMSK}_{i,j}^{\beta}\}_{(i,j) \in [0; n-1] \times [0;k]}, \\
& \qquad \{\text{SK}_i = \text{idMSK}_i\}_{i \in [n-1]} .
\end{aligned}
$$

We implicitly parse these keys in the algorithms below.

Enc(MPK, lab, $\mathbf{x}_0$, $\llbracket \mu \rrbracket_t$) takes MPK, a label lab $\in \mathcal{L}$, an attribute $\mathbf{x}_0 \in \{0, 1\}^k$ and a message $\llbracket \mu \rrbracket_t \in \mathbb{G}_t$ as input. We define $q_0 := |\Pi_{\mathbf{x}_0}^{\text{type}}|$ and parse $\Pi_{\mathbf{x}_0}^{\text{type}} = \{\mathbf{y}^{\nu}\}_{\nu \in [q_0]}$ where $\mathbf{y}^{\nu} = (\mathbf{y}_1^{\nu}, \dots, \mathbf{y}_n^{\nu})$. For $i \in [0; n-1]$, let $Y_i^{\nu} = \{i\} \times \{j \in [0; k] : \mathbf{y}_i^{\nu}[j] \neq \perp\}$. For convenience, we also set $Y^{\nu} = \bigcup_{i \in [0; n-1]} Y_i^{\nu}$ and $Y_{\ge 1}^{\nu} = Y^{\nu} \setminus Y_0^{\nu}$. The algorithm samples random elements $\llbracket r^1 \rrbracket_1, \dots, \llbracket r^{q_0} \rrbracket_1$, $\llbracket \sigma \rrbracket_1 \stackrel{\$}{\leftarrow} \mathbb{G}_1$, computes $\llbracket d \rrbracket_t = \llbracket \sigma + \mu \rrbracket_t$ and generates

$$ 
\begin{aligned}
& \{\text{iCT}_0^{\nu} \leftarrow \text{iSlotEnc}(\text{iMPK}_0, \llbracket (r^{\nu}, \sigma) \rrbracket_1)\}_{\nu \in [q_0]} \\
& \{\text{iCT}_{i,j}^{\nu} \leftarrow \text{iSlotEnc}(\text{iMPK}_{i,j}^{\nu}[j], \llbracket r^{\nu} \rrbracket_1)\}_{(i,j) \in Y^{\nu}} \\
& \{\text{idCT}_{i,j}^{\nu} \leftarrow \text{idEnc}(\text{idMPK}_i, (\text{lab}, \mathbf{y}_i^{\nu}), \text{iCT}_{i,j}^{\nu})\}_{(i,j) \in Y_{\ge 1}^{\nu}} .
\end{aligned}
$$

Finally, it outputs the ciphertext

$$ \text{CT}_{\text{lab}} = (\llbracket d \rrbracket_t, \{\text{iCT}_0^{\nu}\}_{\nu \in [q_0]}, \{\text{iCT}_{0,j}^{\nu}\}_{(0,j) \in Y_0^{\nu}}, \{\text{idCT}_{i,j}^{\nu}\}_{(i,j) \in Y_{\ge 1}^{\nu}}) . $$

AKeyGen SK$_i$, lab, $\mathbf{x}_i$) takes as input SK$_i$ for some $i \in [n-1]$, a label lab $\in \mathcal{L}$ and an attribute $\mathbf{x}_i \in \{0, 1\}^k$. We define $q_i := |\Omega_{\mathbf{x}_i}^{\text{type}}|$ and parse $\Omega_{\mathbf{x}_i}^{\text{type}} = \{\mathbf{z}_i^{\nu}\}_{\nu \in [q_i]}$. The algorithm outputs DK$_{\text{lab},i} = \{\text{idDK}_i^{\nu}\}_{\nu \in [q_i]}$ computed as follows:

$$ \text{idDK}_i^{\nu} \leftarrow \text{idKeyGen}(\text{idMSK}_i, (\text{lab}, \mathbf{z}_i^{\nu})) . $$

PKeyGen(MSK, f) takes as input MSK and a policy $f \in \mathcal{F}^{\text{type}}$. Let $(c \land f) = (\mathbf{M} \in \mathbb{Z}_p^{m \times l}, \rho = (\rho_1, \rho_2, \rho_3): [l] \to [0; n-1] \times [0; k] \times \{0, 1\})$. The algorithm samples $s \stackrel{\$}{\leftarrow} \mathbb{Z}_p$ and $\mathbf{u} \stackrel{\$}{\leftarrow} \mathbb{Z}_p^{m-1}$, computes $\mathbf{s} = (s, \mathbf{u}^{\top}) \cdot \mathbf{M}$ and generates

$$ 
\begin{aligned}
& \text{iDK}_0 \leftarrow \text{iKeyGen}(\text{iMSK}_0, \llbracket (s, 1, 0) \rrbracket_2) \\
& \{\text{iDK}_{\kappa} \leftarrow \text{iKeyGen}(\text{iMSK}_{\rho_1(\kappa)}, \rho_2(\kappa), \llbracket (\mathbf{s}[\kappa], 0) \rrbracket_2)\}_{\kappa \in [l]} .
\end{aligned}
$$

Finally, it outputs DK$_f = \{\text{iDK}_{\kappa}\}_{\kappa \in [0; l]}$.
Dec(DK<sub>f</sub>, {DK<sub>lab,i</sub>}<sub>i∈[n-1]</sub>, CT<sub>lab</sub>) takes as input a decryption key DK<sub>f</sub> for a policy f ∈ F<sup>type</sup>, a set of decryption keys {DK<sub>lab,i</sub>}<sub>i∈[n-1]</sub> created with respect to attributes x<sub>1</sub>, ..., x<sub>n-1</sub> ∈ {0, 1}<sup>k</sup> and a label lab ∈ L, and a ciphertext CT<sub>lab</sub> created with respect to an attribute x<sub>0</sub> ∈ {0, 1}<sup>k</sup> and the same label lab. Parse DK<sub>f</sub>, {DK<sub>lab,i</sub>}<sub>i∈[n-1]</sub>, CT<sub>lab</sub>, Π<sup>type</sup><sub>x<sub>0</sub></sub>, {Ω<sup>type</sup><sub>x<sub>i</sub></sub>}<sub>i∈[n-1]</sub> and {Y<sup>ν</sup>}<sub>ν∈[q<sub>0</sub>]</sub> as in the algorithms above. Let (c ∧ f) = (M ∈ Z<sub>p</sub><sup>m×l</sup>, ρ: [l] → [0; n-1] × [0; k] × {0, 1}) The algorithm picks indices v<sub>0</sub> ∈ [q<sub>0</sub>], v<sub>1</sub> ∈ [q<sub>1</sub>], ..., v<sub>n-1</sub> ∈ [q<sub>n-1</sub>] such that

1. $\mathbf{y}_i^{v_0} = \mathbf{z}_i^{v_i}$ for all $i \in [n-1]$, and

2. $X = \{(i, j, \mathbf{y}_i^{v_0}[j]) : (i, j) \in Y^{v_0}\} \cap \rho([l])$ satisfies the policy $\overline{(c \wedge f)}$.

If no such indices exist, then the algorithm outputs $\perp$. Otherwise, it decrypts

$$ \{iCT_{i,j} \leftarrow \text{idDec}(\text{idDK}_{i}^{v_i}, \text{idCT}_{i,j}^{v_0})\}_{(i,j) \in Y_{\ge 1}^{v_0}}, $$

and finds coefficients $\omega_1, \dots, \omega_l \in \mathbb{Z}_p$ such that $\sum_{\kappa \in [l]} \omega_\kappa M[\kappa] = e_1$ and $\omega_\kappa = 0$ for all $\kappa \notin \rho^{-1}(X)$. Finally, the algorithm computes

$$ \{[d_0]_t \leftarrow \text{iDec}(iDK_0, iCT_0) \\ \{[d_\kappa]_t \leftarrow \text{iDec}(iDK_\kappa, iCT_{\rho_1(\kappa), \rho_2(\kappa)})\}_{\kappa \in \rho^{-1}(X)}, $$

and outputs $[[\mu']]_t = [[d]_t - [d_0]]_t + \sum_{\kappa \in \rho^{-1}(X)} \omega_\kappa [[d_\kappa]]_t$.

**Correctness.** Let type ∈ {log-att, const-dep, ≤const-thr, ≥const-thr}. We consider attributes x<sub>0</sub>, ..., x<sub>n-1</sub> ∈ {0, 1}<sup>k</sup> and f ∈ F<sup>type</sup> such that f(x<sub>0</sub>, ..., x<sub>n-1</sub>) = 1. Let lab ∈ L and DK<sub>f</sub>, {DK<sub>lab,i</sub>}<sub>i∈[n-1]</sub> and CT<sub>lab</sub> be computed as in Construction 5. We first argue that there always exists a possible choice of indices v<sub>0</sub>, ..., v<sub>n-1</sub> which satisfies conditions 1 and 2. For convenience, we parse Π<sup>type</sup><sub>x<sub>0</sub></sub> and {Ω<sup>type</sup><sub>x<sub>i</sub></sub>}<sub>i∈[n-1]</sub> as in Construction 5.

* type = log-att. In this case, we have v<sub>i</sub> = 1 for all i ∈ [n-1] since q<sub>i</sub> = 1, and thus z<sub>i</sub><sup>v<sub>i</sub></sup> = x<sub>i</sub>. For condition 1, we furthermore observe that there exists an index v<sub>0</sub> ∈ [q<sub>0</sub>] such that y<sub>i</sub><sup>v<sub>0</sub></sup> = x<sub>i</sub> for all i ∈ [n-1]. This is because by definition, Π<sup>log-att'</sup><sub>x<sub>0</sub></sub> contains the tuple (x<sub>0</sub>, ..., x<sub>n-1</sub>) for all possible choices of x<sub>1</sub>, ..., x<sub>n-1</sub>. For condition 2, we first note that the choice of v<sub>0</sub> is unique, so X is uniquely determined. Then it is not hard to see that this set X satisfies the policy (c ∧ f) since c only checks that there is one decryption key DK<sub>lab,i</sub> for each i and f(x<sub>0</sub>, ..., x<sub>n-1</sub>) = 1 by assumption.

* type = const-dep. We first observe that a circuit f of depth d = O(1) depends on at most $\tau = 2^d = O(1)$ inputs. For this reason, there exists a subset L ⊆ [n] × [k] of size $\tau$ such that the output of f only depends on inputs in L. (If the locality of f is smaller than $\tau$, then the choice of L is not unique). For condition 1, let i ∈ [n-1]. By construction of Ω<sup>const-dep</sup><sub>x<sub>i</sub></sub>, there exists an index v<sub>i</sub> such that z<sub>i</sub><sup>v<sub>i</sub></sup>[j] = $\perp$ for (i, j) ∈ ({i} × [k]) \ L and z<sub>i</sub><sup>v<sub>i</sub></sup>[j] = x<sub>i</sub>[j] for (i, j) ∈ L. Furthermore, for each choice of L and x<sub>1</sub>, ..., x<sub>n-1</sub>, there exists an index v<sub>0</sub> ∈ [q<sub>0</sub>] such that for all (i, j) ∈ [n-1] × [k], it holds y<sub>i</sub><sup>v<sub>0</sub></sup>[j] = x<sub>i</sub>[j] if (i, j) ∈ L and y<sub>i</sub><sup>v<sub>0</sub></sup>[j] = $\perp$ otherwise. For condition 2, the argument is similar to the previous case. Once we have found an assignment for v<sub>0</sub>, ..., v<sub>n-1</sub> that satisfies the first condition, the second follows since f(x<sub>0</sub>, ..., x<sub>n-1</sub>) = 1.

* type = ≤const-thr. The argument is the same as in the case type = const-dep except that now all tuples (y<sub>0</sub><sup>v<sub>0</sub></sup>, ..., y<sub>n-1</sub><sup>v<sub>0</sub></sup>) ∈ Π<sup>const-thr</sup><sub>x<sub>0</sub></sub> and vectors z<sub>i</sub><sup>v<sub>i</sub></sup> ∈ Ω<sup>const-thr</sup><sub>x<sub>i</sub></sub>, for i ∈ [n-1], have coordinates in {1, $\perp$} instead of {0, 1, $\perp$}. For condition 1, this
is irrelevant as we replace the 0 coordinates with $⊥$ in both the $\mathbf{y}_i^{\nu_0}$ and the $\mathbf{z}_i^{\nu_i}$ vectors. So their equality is preserved. For condition 2, we exploit the fact that all policies in $\mathcal{F} \leq \text{const-thr}$ are monotone. Therefore, if a coordinate of $\mathbf{y}_i^{\nu_0}$ or $\mathbf{z}_i^{\nu_i}$ is 0 or $⊥$ is irrelevant for the fact whether $X$ satisfies $(c \land f)$ or not.

* type = $\geq \text{const-thr}$. The argument is similar to the case type = log-att. For $i \in [n-1]$, we have $\nu_i = 1$ and for all $j \in [k]$, $\mathbf{z}_i^1[j] = 1$ if $\mathbf{x}_i = 1$ and $\mathbf{z}_i^1[j] = \perp$ otherwise. If $\sum_{i \in [0; n-1]} \delta(\mathbf{x}_i) \geq kn - \tau$, then there also exists $\nu_0 \in [q_0]$ such that $\mathbf{y}_i^{\nu_0} = \mathbf{z}_i^1$ for all $i \in [n-1]$. In contrast, such a $\nu_0$ does not exist if $\sum_{i \in [0; n-1]} \delta(\mathbf{x}_i) < kn - \tau$. But this is irrelevant since $f(\mathbf{x}_0, \dots, \mathbf{x}_{n-1}) = 0$ in this case, i.e. such a combination of attributes is never authorized regardless of the policy $f$.

Once the algorithm has chosen indices $\nu_0, \dots, \nu_{n-1}$ that satisfy conditions 1 and 2, we can argue as in Construction 2. By the correctness of idFE and iFE, we have $d_0 = r^{\nu_0} \cdot s + \sigma$ and, for all $\kappa \in \rho^{-1}(X)$, $d_\kappa = r^{\nu_0} \cdot s[\kappa]$. Then we conclude from the correctness of the LSS scheme that

$$ \mu' = d - d_0 + \sum_{\kappa \in \rho^{-1}(X)} \omega_\kappa d_\kappa = (\sigma + \mu) - (r^{\nu_0} s + \sigma) + r^{\nu_0} \cdot \underbrace{\sum_{\kappa \in \rho^{-1}(X)} \omega_\kappa s[\kappa]}_{= s} = \mu $$

**Efficiency.** For efficiency, we need to ensure that $\Pi_{\mathbf{x}_0}^{\text{type}}$ and $\Omega_{\mathbf{x}_i}^{\text{type}}$ have polynomial size for all $i \in [n-1]$ and type $\in \{\text{log-att}, \text{const-dep}, \leq \text{const-thr}, \geq \text{const-thr}\}$.

* type = log-att. By construction, we have $|\Omega_{\mathbf{x}_i}^{\text{log-att}}| = 1$ and

$$ |\Pi_{\mathbf{x}_0}^{\text{log-att}}| = 2^{k(n-1)} = 2^{O(\log \lambda)} = \text{poly}(\lambda), $$

since $kn = O(\log \lambda)$.

* type = const-dep. Since $\tau = 2^d = O(1)$, we have

$$ |\Pi_{\mathbf{x}_0}^{\text{const-dep}}| \leq \binom{kn}{\tau} \cdot 2^\tau = \text{poly}(\lambda) $$

$$ |\Omega_{\mathbf{x}_i}^{\text{const-dep}}| \leq \sum_{\ell \in [0; \tau]} \binom{k}{\ell} \cdot 2^\ell = \text{poly}(\lambda). $$

* type = $\leq \text{const-thr}$. Similar to the case type = const-dep, as $\tau = O(1)$, we have

$$ |\Pi_{\mathbf{x}_0}^{\leq \text{const-thr}}| \leq \binom{kn}{\tau} = \text{poly}(\lambda) $$

$$ |\Omega_{\mathbf{x}_i}^{\leq \text{const-thr}}| \leq \sum_{\ell \in [0; \tau]} \binom{k}{\ell} = \text{poly}(\lambda). $$

* type = $\geq \text{const-thr}$. Since $\tau = O(1)$, we have $|\Omega_{\mathbf{x}_i}^{\geq \text{const-thr}}| = 1$ and

$$ |\Pi_{\mathbf{x}_0}^{\geq \text{const-thr}}| \leq \sum_{\ell \in [0; \tau]} \binom{kn}{\ell} = \text{poly}(\lambda). $$
**Security.** We prove selective security with repetitions.

**Proposition 6.** Let type ∈ {log-att, const-dep, ≤const-thr, ≥const-thr}. If the DDH assumption holds in $\mathbb{G}_2$, iFE is slot-mode correct and function-hiding and idFE is secure, then Construction 5 is sel-rep-secure.

When instantiating iFE with the slotted ABE from [LL20a] and idFE with the IBE from [CLL$^{+}$13], we obtain the following theorem.

**Theorem 7.** Assuming SXDH on pairings, there exist

* a sel-rep-secure MC-ABE for the policy class $NC^1$ where the parameters satisfy $kn = O(\log \lambda)$, and

* a sel-rep-secure MC-ABE for the policy classes $\mathcal{F}^{\text{const-dep}}$, $\mathcal{F}^{\leq \text{const-thr}}$ and $\mathcal{F}^{\geq \text{const-thr}}$ with $k = n = \text{poly}(\lambda)$.

*Proof* (Proposition 6). Let $\mathcal{OEnc}(\text{lab}, \mathbf{x}_0, [[\mu^0]]_t, [[\mu^1]]_t)$ be the (single) encryption query. We define $q_0 := |\Pi_{\mathbf{x}_0}^{\text{type}}|$ and parse $\Pi_{\mathbf{x}_0}^{\text{type}} = \{\mathbf{y}^\nu\}_{\nu \in [q_0]}$ where $\mathbf{y}^\nu = (\mathbf{y}_1^\nu, \dots, \mathbf{y}_n^\nu)$. For $i \in [0; n-1]$, let $Y_i^\nu = \{i\} \times \{j \in [0; k] : \mathbf{y}_i^\nu[j] \neq \perp\}$, $Y^\nu = \bigcup_{i \in [0; n-1]} Y_i^\nu$ and $Y_{\ge 1}^\nu = Y^\nu \setminus Y_0^\nu$. For the reply to the encryption query, the challenger samples random elements $[[r^1]]_1, \dots, [[r^{q_0}]_1, [[\sigma]]_1] \stackrel{\mathcal{S}}{\leftarrow} \mathbb{G}_1$, computes $[[d]]_t = [[\sigma + \mu]]_t$ and generates

$$ \begin{aligned} \{\text{iCT}_0^\nu \leftarrow \text{iSlotEnc}(\text{iMPK}_0, [[(r^\nu, \sigma)]_1]) \}^{\nu \in [q_0]} \\ \{\text{iCT}_{i,j}^\nu \leftarrow \text{iSlotEnc}(\text{iMPK}_{i,j}^{\mathbf{y}_i^\nu[j]}, [[r^\nu]]_1) \}^{\nu \in [q_0]}_{(i,j) \in Y^\nu} \\ \{\text{idCT}_{i,j}^\nu \leftarrow \text{idEnc}(\text{idMPK}_i, (\text{lab}, \mathbf{y}_i^\nu), \text{iCT}_{i,j}^\nu) \}^{\nu \in [q_0]}_{(i,j) \in Y_{\ge 1}^\nu} . \end{aligned} $$

Then it sends the following challenge ciphertext CT to $\mathcal{A}$:

$$ \text{CT}_{\text{lab}} = ([[d]]_t, \{\text{iCT}_0^\nu\}^{\nu \in [q_0]}, \{\text{iCT}_{0,j}^\nu\}^{\nu \in [q_0]}_{(0,j) \in Y_0^\nu}, \{\text{idCT}_{i,j}^\nu\}^{\nu \in [q_0]}_{(i,j) \in Y_{\ge 1}^\nu}) . $$

We consider a sequence of hybrid games $G_\nu^b$, for $\nu \in [0; q_0]$ and $b \in \{0, 1\}$, where $G_\nu^b$ is the same as $\text{Exp}_{\text{aFE},\mathcal{A}}^{\text{mc-abe-b}}(1^\lambda)$ except that, for each $\nu' \in [q_0]$, the challenger computes

$$ \text{iCT}_0^{\nu'} \leftarrow \begin{cases} \text{iSlotEnc}(\text{iMPK}_0, [[(r^{\nu'}, \mathbf{0})]]_1) & \text{if } \nu' \le \nu \\ \text{iSlotEnc}(\text{iMPK}_0, [[(r^{\nu'}, \sigma)]_1) & \text{if } \nu' > \nu \end{cases} $$

We note that $G_0^b = \text{Exp}_{\text{aFE},\mathcal{A}}^{\text{mc-abe-b}}(1^\lambda)$ and $G_{q_0}^0 \equiv G_{q_0}^1$. For the latter, we observe that in the hybrids $G_{q_0}^0$ and $G_{q_0}^1$ the random mask $[[\sigma]]_t \stackrel{\mathcal{S}}{\leftarrow} \mathbb{G}_t$ appears only in the terms $[[d]]_t := [[\sigma + \mu^b]]_t$, which implies that the distributions $[[\sigma + \mu^0]]_t$ and $[[\sigma + \mu^1]]_t$ are identical. Below we prove the following claim for all $\nu \in [q_0]$ and $b \in \{0, 1\}$.

**Claim 8.** We have $G_{\nu-1}^b \approx_c G_\nu^b$ under the slot-mode correctness and function-hiding security of iFE, the security of idFE and the DDH assumption in $\mathbb{G}_2$.

This concludes the proof of the proposition.

□

We next prove the claim.

*Proof* (Claim 8). We consider a sequence of hybrids $\hat{G}_0^0, \dots, \hat{G}_0^1, \hat{G}_0^1, \dots, \hat{G}_0^1$, where $\hat{G}_0^0 = G_{\nu-1}^b$ and $\hat{G}_0^1 = G_\nu^b$. We argue $\hat{G}_{\alpha-1}^\beta \approx_c \hat{G}_\alpha^\beta$, for $\alpha \in [6]$ and $\beta \in \{0, 1\}$, as well as $G_0^0 \equiv G_0^1$. Then the claim follows via a hybrid argument. Modifications between consecutive games are highlighted using boxes.
**Game $\hat{G}_0^\beta$**: This is $G_{\nu-1+\beta}$.

**Game $\hat{G}_1^\beta$**: This game is the same as $\hat{G}_0^\beta$, except that the challenger computes

$$ \begin{cases} \text{iCT}_0^\nu \leftarrow \text{iEnc}(\text{iMSK}_0, \llbracket (r^\nu, \rho^\beta, 0) \rrbracket_1) \\ \text{iCT}_{i,j}^\nu \leftarrow \text{iEnc}(\text{iMSK}_{i,j}^{y_i^\nu[j]}, \llbracket (r^\nu, 0) \rrbracket_1) \end{cases} \quad (i,j) \in Y^\nu, $$

where $\rho^0 = \sigma$ and $\rho^1 = 0$. We have $\hat{G}_0^\beta \equiv \hat{G}_1^\beta$ which follows from the slot-mode correctness of iFE.

**Game $\hat{G}_2^\beta$**: We define the set $J \subseteq [0; n-1] \times [0; k]$ containing the indices of all ciphertexts $\text{iCT}_{i,j}^\nu$ known to the adversary:

$$ J = \{ (i, j) \in Y^\nu : [i \in \mathcal{C} \cup \{0\}] \lor [\exists (i, \text{lab}, \mathbf{x}_i) \in \mathcal{Q}_{\text{akey}} \text{ s.t. } \mathbf{y}_i^\nu \in \Omega_{\mathbf{x}_i}^{\text{type}}] \}. $$

This game is the same as $\hat{G}_1^\beta$, except that the challenger now computes

$$ \text{iCT}_{i,j}^\nu \leftarrow \begin{cases} \text{iEnc}(\text{iMSK}_{i,j}^{y_i^\nu[j]}, \llbracket (r^\nu, 0) \rrbracket_1) & \text{if } (i, j) \in J \\ \text{iEnc}(\text{iMSK}_{i,j}^{y_i^\nu[j]}, \llbracket (0, 0) \rrbracket_1) & \text{if } (i, j) \notin J. \end{cases} $$

We have $\hat{G}_1^\beta \approx_c \hat{G}_2^\beta$ from the security of idFE.

**Game $\hat{G}_3^\beta$**: Next we deal with the ciphertexts $\text{iCT}_{i,j}^\nu$ such that $(i, j) \in J$. Initially, the challenger needs to respond to the selective encryption query. In contrast to the previous game, it now computes

$$ \begin{aligned} \text{iCT}_0 &\leftarrow \text{iEnc}(\text{iMSK}_0, \llbracket (0, 0, 1) \rrbracket_1) \\ \text{iCT}_{i,j} &\leftarrow \begin{cases} \text{iEnc}(\text{iMSK}_{i,j}^{y_i^\nu[j]}, \llbracket (0, 1) \rrbracket_1) & \text{if } (i, j) \in J \\ \text{iEnc}(\text{iMSK}_{i,j}^{y_i^\nu[j]}, \llbracket (0, 0) \rrbracket_1) & \text{if } (i, j) \notin J. \end{cases} \end{aligned} $$

Upon receiving a query $\text{OPKeyGen}(f)$ with $\overline{(c \land f)} = (M \in \mathbb{Z}_p^{m \times \ell}, \rho: [\ell] \to [0; n-1] \times [0; k] \times \{0, 1\})$, the challenger samples $s \leftarrow \mathbb{Z}_p$, $\mathbf{u} \leftarrow \mathbb{Z}_p^{m-1}$ and computes $\mathbf{s} = (s, \mathbf{u}^\top) \cdot M$. Then it sends $\text{DK}_f = \{\text{iDK}_\kappa\}_{\kappa \in [0; \ell]}$ to $\mathcal{A}$ generated as follows:

$$ \begin{aligned} \text{iDK}_0 &\leftarrow \text{iKeyGen}(\text{iMSK}_0, \llbracket (s, 1, r^\nu \cdot s + \rho^\beta) \rrbracket_2) \\ \text{iDK}_\kappa &\leftarrow \begin{cases} \text{iKeyGen}(\text{iMSK}_{\rho(\kappa)}, \llbracket (\mathbf{s}[\kappa], r^\nu \cdot \mathbf{s}[\kappa]) \rrbracket_2) & \text{if } \rho(\kappa) \in J \\ \text{iKeyGen}(\text{iMSK}_{\rho(\kappa)}, \llbracket (\mathbf{s}[\kappa], 0) \rrbracket_2) & \text{if } \rho(\kappa) \notin J, \end{cases} \end{aligned} $$

where the scalar $r^\nu \leftarrow \mathbb{Z}_p$ is sampled during the creation of the challenge ciphertext (but not used). As the public parts of the iFE keys and the inner products between vectors embedded in the iFE keys and ciphertexts do not change, it follows $\hat{G}_2^\beta \approx_c \hat{G}_3^\beta$ from the function-hiding security of iFE.

**Game $\hat{G}_4^\beta$**: This game is the same as $\hat{G}_3^\beta$ except that the challenger embeds a fresh secret sharing in each secret key. Specifically, upon receiving a query $\text{OPKeyGen}(f)$ with $\overline{(c \land f)} = (M \in \mathbb{Z}_p^{m \times \ell}, \rho: [\ell] \to [0; n-1] \times [0; k] \times \{0, 1\})$, the challenger samples $s, t \leftarrow \mathbb{Z}_p$ and $\mathbf{u}, \mathbf{v} \leftarrow \mathbb{Z}_p^{m-1}$, computes $\mathbf{s} = (s, \mathbf{u}^\top) \cdot M$ and $\mathbf{t} = (t, \mathbf{v}^\top) \cdot M$ and sends $\text{DK}_f = \{\text{iDK}_\kappa\}_{\kappa \in [0; \ell]}$ to $\mathcal{A}$ generated as follows:

$$ \begin{aligned} \text{iDK}_0 &\leftarrow \text{iKeyGen}(\text{iMSK}_0, \llbracket (s, 1, t + \rho^\beta) \rrbracket_2) \\ \text{iDK}_\kappa &\leftarrow \begin{cases} \text{iKeyGen}(\text{iMSK}_{\rho(\kappa)}, \llbracket (\mathbf{s}[\kappa], \mathbf{t}[\kappa]) \rrbracket_2) & \text{if } \rho(\kappa) \in J \\ \text{iKeyGen}(\text{iMSK}_{\rho(\kappa)}, \llbracket (\mathbf{s}[\kappa], 0) \rrbracket_2) & \text{if } \rho(\kappa) \notin J. \end{cases} \end{aligned} $$
It is not hard to see that $\hat{\mathbb{G}}_3^\beta \approx_c \hat{\mathbb{G}}_4^\beta$ under the DDH assumption in $\mathbb{G}_2$. (Note that we can exploit the random self-reducibility of the DDH problem here, so a single DDH instance suffices).

Let $f \in \mathbb{Q}_{\text{key}}$ and $\overline{(c \wedge f)} = (\mathbf{M} \in \mathbb{Z}_p^{m \times l}, \rho: [\ell] \to ([0; n-1] \times [0; k] \times \{0, 1\}))$. We recall that the adversary can learn the iFE ciphertexts corresponding to the attributes with indices in $J' := \{(i, j, \mathbf{y}_i^{\prime}[j])\}_{(i,j) \in J}$. Let $M_f = \text{span}\{\mathbf{M}[\kappa] : \kappa \in [\ell] \wedge \rho(\kappa) \in J'\}$ be the vector space spanned by the columns of $\mathbf{M}$ associated with attributes in $J'$. Furthermore, let $M_f^{\perp}$ denote the orthogonal complement of $M_f$ and $A_f^{\perp}$ the affine space of $M_f^{\perp}$ containing all vectors whose first coordinate is 1. To argue that $A_f^{\perp}$ is nonempty, we distinguish two cases:

1. If there exists $i \in [n-1] \setminus \mathcal{C}$ such that $\mathbf{y}_i^{\prime} \notin \Omega_{\mathbf{x}_i}^{\text{type}}$ for all attributes $\mathbf{x}_i$ with $(i, \text{lab}, \mathbf{x}_i) \in \mathbb{Q}_{\text{key}}$, then $J'$ does not satisfy $c$ (and thus $\overline{(c \wedge f)}$). Hence, we have $\mathbf{e}_1 \notin M_f$ which implies that $A_f^{\perp}$ is nonempty.

2. Otherwise, consider any sequence of attributes $\mathbf{x}_1, \dots, \mathbf{x}_{n-1} \in \{0, 1\}^k$ such that for all $i \in [n-1]$, we have

$$[i \in \mathcal{C} \lor (i, \text{lab}, \mathbf{x}_i) \in \mathbb{Q}_{\text{key}}] \land [\mathbf{y}_i^{\prime} \in \Omega_{\mathbf{x}_i}^{\text{type}}].$$

For the sake of a contradiction, assume that $J'$ satisfies $\overline{(c \wedge f)}$. Then it follows that $J'' := \{(i, 0, 1)\}_{i \in [n-1]} \cup \{(i, j, \mathbf{x}_i[j])\}_{(i,j) \in [0; n-1] \times [k]}$ also satisfies $\overline{(c \wedge f)}$ since $J' \subseteq J''$ and $\overline{(c \wedge f)}$ is a monotone policy. In this case, the equivalence between $\overline{(c \wedge f)}$ and $(c \wedge f)$ gives that

$$(c \wedge f)((1, \mathbf{x}_0), \dots, (1, \mathbf{x}_{n-1})) = 1,$$

which implies in particular that $f(\mathbf{x}_0, \dots, \mathbf{x}_{n-1}) = 1$. This contradicts the admissibility of the adversary $\mathcal{A}$. Therefore, $J'$ cannot satisfy $\overline{(c \wedge f)}$, and we conclude that $\mathbf{e}_1 \notin M_f$ and $A_f^{\perp}$ is nonempty.

**Game $\hat{\mathbb{G}}_5^\beta$**: This game is the same as $\hat{\mathbb{G}}_4^\beta$, except that we modify how the challenger generates the share vector $\mathbf{t}$ for the reply to a query $\text{OPKeyGen}(f)$. Let $\overline{(c \wedge f)} = (\mathbf{M} \in \mathbb{Z}_p^{m \times l}, \rho: [\ell] \to [0; n-1] \times [0; k] \times \{0, 1\})$. In $\hat{\mathbb{G}}_4^\beta$, the challenger samples $t \stackrel{\$}{\leftarrow} \mathbb{Z}_p$, $\mathbf{v} \stackrel{\$}{\leftarrow} \mathbb{Z}_p^{m-1}$ and computes $\mathbf{t} = (t, \mathbf{v}^\top) \cdot \mathbf{M}$. In the current game, the challenger picks an additional vector $(1, \bar{\mathbf{v}})^\top \in A_f^{\perp}$ and sets

$$\mathbf{t} = (t, \mathbf{v}^{\top}) \cdot \mathbf{M} + (0, t\bar{\mathbf{v}}^{\top}) \cdot \mathbf{M}.$$

The distributions $\{\mathbf{v} : \mathbf{v} \stackrel{\$}{\leftarrow} \mathbb{Z}_p^{m-1}\}$ and $\{\mathbf{v} + t\bar{\mathbf{v}} : \mathbf{v} \stackrel{\$}{\leftarrow} \mathbb{Z}_p^{m-1}\}$ are identical for any $\bar{\mathbf{v}} \in \mathbb{Z}_p^{m-1}$. The first distribution corresponds to $\hat{\mathbb{G}}_4^\beta$ and the second one to $\hat{\mathbb{G}}_5^\beta$ (followed by the same post-processing), so we have $\hat{\mathbb{G}}_4^\beta \equiv \hat{\mathbb{G}}_5^\beta$.

**Game $\hat{\mathbb{G}}_6^\beta$**: This game is the same as $\hat{\mathbb{G}}_5^\beta$ except that we again change the behavior of the key generation oracle when receiving a query $\text{OPKeyGen}(f)$. Let $\overline{(c \wedge f)} = (\mathbf{M} \in \mathbb{Z}_p^{m \times l}, \rho: [\ell] \to [0; n-1] \times [0; k] \times \{0, 1\})$. As in the previous hybrid, the challenger samples $s, t \stackrel{\$}{\leftarrow} \mathbb{Z}_p$ and $\mathbf{u}, \mathbf{v} \stackrel{\$}{\leftarrow} \mathbb{Z}_p^{m-1}$ and computes $\mathbf{s} = (s, \mathbf{u}^\top) \cdot \mathbf{M}$. In the current hybrid, it then generates $\text{DK}_f = \{\text{DK}_\kappa\}_{\kappa \in [0; \ell]}$ as follows:

$$\begin{array}{l}
\text{iDK}_0 \leftarrow \text{iKeyGen}(\text{iMSK}_0, \llbracket (s, 1, t + \rho^\beta) \rrbracket_2) \\
\text{iDK}_\kappa \leftarrow \begin{cases}
\text{iKeyGen}(\text{iMSK}_{\rho(\kappa)}, \llbracket (\mathbf{s}[\kappa], (0, \mathbf{v}^\top) \cdot \mathbf{M}[\kappa]) \rrbracket_2) & \text{if } \rho(\kappa) \in J' \\
\text{iKeyGen}(\text{iMSK}_{\rho(\kappa)}, \llbracket (\mathbf{s}[\kappa], 0) \rrbracket_2) & \text{if } \rho(\kappa) \notin J',
\end{cases}
\end{array}$$
whereas in $\hat{G}_5^\beta$, the challenger additionally picks $(1, \bar{v})^\top \in A_f^\perp$ and computes

$$iDK_\kappa \leftarrow iKeyGen(iMSK_{\rho(\kappa)}), \llbracket (s[\kappa], (t, (v + t\bar{v})^\top) \cdot M[\kappa]) \rrbracket_2$$

for all $\kappa \in [\ell]$ such that $\rho(\kappa) \in J'$. We can observe that

$$\begin{aligned} (t, (v + t\bar{v})^\top) \cdot M[\kappa] &= (0, v^\top) \cdot M[\kappa] + t(1, \bar{v}^\top) \cdot M[\kappa] \\ &= (0, v^\top) \cdot M[\kappa], \end{aligned}$$

where the last equality follows from the fact that $(1, \bar{v}^\top) \in M_f^\perp$ and $M[\kappa] \in M_f$. The first distribution corresponds to $\hat{G}_5^\beta$ and the second one to $\hat{G}_6^\beta$ (followed by the same post-processing), thus we have $\hat{G}_5^\beta \equiv \hat{G}_6^\beta$. We further notice that in $\hat{G}_5^\beta$ the random element $\llbracket t \rrbracket_2 \leftarrow \mathbb{S} \otimes G_2$ appears only in $iDK_0$, so it perfectly masks $\llbracket \rho^\beta \rrbracket_2$ and we conclude that $\hat{G}_6^0 \equiv \hat{G}_6^1$.

□

# 6 Construction of MC-PE

In this section, we present our new compiler that turns any $O(1)$-client ABE into an $O(1)$-client PE scheme for the same policy class.

For each $\ell \in [0; n - 1]$, we define a permutation $\pi_\ell$ of the set $[0; n - 1]$ via

$$\pi_{\ell}(i) = \begin{cases} i + 1 & \text{if } i \in [0; \ell - 1] \\ 0 & \text{if } i = \ell \\ i & \text{if } i \in [\ell + 1; n - 1]. \end{cases}$$

Correspondingly, for a policy $f \in \mathcal{F}$ and $\ell \in [0; n - 1]$, we define $\pi_\ell(f)$ as a variant of $f$ with permuted inputs:

$$(\pi_{\ell}(f))(\mathbf{x}_0, \dots, \mathbf{x}_{n-1}) = f(\mathbf{x}_{\pi_{\ell}(0)}, \dots, \mathbf{x}_{\pi_{\ell}(n-1)}).$$

**Construction 9 (Multi-Client Predicate Encryption).** The construction uses the following ingredients:

* An MC-ABE scheme $aFE = (aSetup, aEnc, aKeyGen, aPKeyGen, aDec)$ for a message space $M = \{0, 1\}^m$ for some $m = \text{poly}(\lambda)$, a label space $\mathcal{L}$, an attribute universe $\mathcal{X}$ and a policy class $\mathcal{F}$.

* A lockable obfuscation scheme $LObf = (Obf, Eval)$ with lock space $M$ and message space $M'$. We write $C[x](y)$ to indicate that a circuit $C$ has the value $x$ hardwired in its description and takes $y$ as input.

The MC-PE scheme $pFE$ for message space $M'$, label space $\mathcal{L}$, attribute universe $\mathcal{X}$ and policy class $\mathcal{F}$ works as follows:

Setup($1^\lambda$) takes as input the security parameter $1^\lambda$ and generates $n$ $aFE$ instances

$$\{(aMPK_{\ell}, aMSK_{\ell}, \{aSK_{\ell,i}\}_{i \in [n-1]}) \leftarrow aSetup(1^{\lambda})\}_{\ell \in [0; n-1]}.$$

Then the algorithm outputs $(\{SK_i\}_{i \in [0; n-1]}, \text{MSK})$ as follows:

$$\{SK_i := (aMPK_i, \{aSK_{\ell,j}\}_{(\ell,j) \in J_i})\}_{i \in [0; n-1]}, \quad \text{MSK} := \{aMSK_{\ell}\}_{\ell \in [0; n-1]},$$

where $J_i = \{(\ell, \pi_\ell(i))\}_{\ell \in [0; n-1]} \setminus \{i\}$. We implicitly parse these keys in the algorithms below.
**hardwired values :**

* an aFE ciphertext aCT<sub>i</sub>

* a set of aFE attribute decryption keys {$\text{aDK}_{\ell,i+1}$}$_{\ell \in [i+1;n-1]}$

**input :**

* a set of obfuscated circuits {$\tilde{C}_{\ell}$}$_{\ell \in [i+1;n-1]}$

* a set of aFE attribute decryption keys {$\text{aDK}_{\ell,j}$}$_{\ell \in [i;n-1]}^{j \in [i]}$

* a set of aFE policy decryption keys {$\text{aDK}_{\ell,f}$}$_{\ell \in [i;n-1]}$

**output :** an element of the lock space $\sigma_i \in \mathcal{M}$ or $\perp$

initialize {$\text{aDK}_{\ell,j} \leftarrow \perp$}$_{\ell \in [0; j-1]}^{j \in [i+1; n-1]}$

for $k \leftarrow i+1$ to $n-1$ do

$c_k \leftarrow \text{Eval}(\tilde{C}_k, (\{\tilde{C}_{\ell}\}_{\ell \in [k+1;n-1]}, \{\text{aDK}_{\ell,j}\}_{\ell \in [k;n-1]}^{j \in [k]}, \{\text{aDK}_{\ell,f}\}_{\ell \in [k;n-1]}))$

if $c_k = \perp$ then return $\perp$

else parse {$\text{aDK}_{\ell,k}$}$_{\ell \in [0;k-1]} \leftarrow c_k$

end

return $\sigma_i \leftarrow \text{aDec}(\text{aDK}_{i,f}, \{\text{aDK}_{i,j}\}_{j \in [n-1]}, \text{aCT}_i)$

Figure 5: Definition of the circuit $C_i[\text{aCT}_i, \{\text{aDK}_{\ell,i+1}\}_{\ell \in [i+1;n-1]}]$ on input $(\{\tilde{C}_{\ell}\}_{\ell \in [i+1;n-1]}, \{\text{aDK}_{\ell,j}\}_{\ell \in [i;n-1]}^{j \in [i]}, \{\text{aDK}_{\ell,f}\}_{\ell \in [i;n-1]})$

Enc($\text{SK}_0$, lab, $x_0$, $\mu$) takes as input $\text{SK}_0$, a label lab $\in \mathcal{L}$, an attribute $x_0 \in \mathcal{X}$ and a message $\mu \in \mathcal{M}'$. The algorithm samples $\sigma_0 \stackrel{\$}{\leftarrow} \mathcal{M}$, runs

$$
\begin{align*}
\text{aCT}_0 &\leftarrow \text{aEnc}(\text{aMPK}_0, \text{lab}, x_0, \sigma_0) \\
\{\text{aDK}_{\ell,1} &\leftarrow \text{aKeyGen}(\text{aSK}_{\ell,1}, \text{lab}, x_0)\}_{\ell \in [n-1]} \\
\tilde{C}_0 &\leftarrow \text{Obf}(1^{\lambda}, C_0[\text{aCT}_0, \{\text{aDK}_{\ell,1}\}_{\ell \in [n-1]}], \mu, \sigma_0)
\end{align*}
$$

and outputs $\text{CT}_{\text{lab}} := \tilde{C}_0$. The circuit $C_0$ is described in Fig. 5.

AKeyGen($\text{SK}_i$, lab, $x_i$) takes as input $\text{SK}_i$ for some $i \in [n-1]$, a label lab $\in \mathcal{L}$ and an attribute $x_i \in \mathcal{X}$. The algorithm samples $\sigma_i \stackrel{\$}{\leftarrow} \mathcal{M}$, runs

$$
\begin{align*}
\text{aCT}_i &\leftarrow \text{aEnc}(\text{aMPK}_i, \text{lab}, x_i, \sigma_i) \\
\{\text{aDK}_{\ell,j} &\leftarrow \text{aKeyGen}(\text{aSK}_{\ell,j}, \text{lab}, x_i)\}_{(\ell,j) \in J_i} \\
\tilde{C}_i &\leftarrow \text{Obf}(1^{\lambda}, C_i[\text{aCT}_i, \{\text{aDK}_{\ell,i+1}\}_{\ell \in [i+1;n-1]}, \{\text{aDK}_{\ell,i}\}_{\ell \in [0;i-1]}, \sigma_i)
\end{align*}
$$

and outputs $\text{DK}_{\text{lab},i} := \tilde{C}_i$ with $C_i$ being described in Fig. 5.

PKeyGen(MSK, f) takes as input MSK and a policy $f \in \mathcal{F}$, runs

$$
\{\text{aDK}_{\ell,f} \leftarrow \text{aPKeyGen}(\text{aMSK}_{\ell}, \pi_{\ell}(f))\}_{\ell \in [0; n-1]},
$$

and outputs $\text{DK}_f := \{\text{aDK}_{\ell,f}\}_{\ell \in [n]}$.

Dec($\text{DK}_f$, $\{\text{DK}_{\text{lab},i}\}_{i \in [n-1]}$, $\text{CT}_{\text{lab}}$) takes a policy decryption key $\text{DK}_f = \{\text{aDK}_{\ell,f}\}_{\ell \in [0;n-1]}$, a set of attribute decryption keys $\{\text{DK}_{\text{lab},i} = \tilde{C}_i\}_{i \in [n-1]}$ and a ciphertext $\text{CT}_{\text{lab}} = \tilde{C}_0$ as input. The algorithm outputs $\mu'$ computed as follows:

$$
\mu' \leftarrow \text{Eval}(\tilde{C}_0, (\{\tilde{C}_i\}_{i \in [n-1]}, \emptyset, \{\text{aDK}_{\ell,f}\}_{\ell \in [0;n-1]})).
$$
**Correctness.** Let $\lambda, n \in \mathbb{N}$, $\mathit{lab} \in \mathcal{L}$, $\mu \in \mathcal{M}$, $f \in \mathcal{F}$ and $x_0, \dots, x_{n-1} \in \mathcal{X}$ such that $f(x_0, \dots, x_{n-1}) = 1$. Furthermore, let $\mathit{DK}_f = \{\mathit{aDK}_{\ell,f}\}_{\ell \in [0; n-1]}$, $\{\mathit{DK}_{\mathit{lab},i} = \tilde{C}_i\}_{i \in [n-1]}$ and $\mathit{CT}_{\mathit{lab}} = \tilde{C}_0$ be created as in Construction 9. To establish correctness, we prove the following statement.

**Lemma 10.** For $x_0, \dots, x_{n-1}$ such that $f(x_0, \dots, x_{n-1}) = 1$ and $i \in [0; n-1]$, we have

$$ \mathrm{Eval}(\tilde{C}_i, (\{\tilde{C}_\ell\}_{\ell \in [i+1; n-1]}, \{\mathit{aDK}_{\ell,j}\}_{\ell \in [i; n-1]}^{j \in [i]}, \{\mathit{aDK}_{\ell,f}\}_{\ell \in [i; n-1]})) = \mu_i, $$

where $\mu_0 = \mu$ and $\mu_i = \{\mathit{aDK}_{\ell,i}\}_{\ell \in [0; i-1]}$ for $i \in [n-1]$. In particular, correctness corresponds to the case $i=0$.

Furthermore, due to the nested evaluations, the scheme is efficient for constant arity, i.e. $n = O(1)$.

*Proof* (Lemma 10). We prove the lemma by induction over $i$ from $n-1$ to 0.

**Base Case.** Let $i = n-1$. By construction, we have

$$ \tilde{C}_{n-1} \leftarrow \mathrm{Obf}(1^{\lambda}, C_{n-1}[\mathit{aCT}_{n-1}, \emptyset], \{\mathit{aDK}_{\ell,n-1}\}_{\ell \in [0; n-2]}, \sigma_{n-1}), $$

where $\sigma_{n-1} \stackrel{\$}{\leftarrow} \mathcal{M}$ is the lock value of the obfuscated circuit. By definition, the circuit $C_{n-1}[\mathit{aCT}_{n-1}, \emptyset]$ takes as input $(\emptyset, \{\mathit{aDK}_{n-1,j}\}_{j \in [n-1]}, \{\mathit{aDK}_{n-1,f}\})$ and outputs the result of the decryption

$$ \sigma'_{n-1} \leftarrow \mathrm{aDec}(\mathit{aDK}_{n-1,f}, \{\mathit{aDK}_{n-1,j}\}_{j \in [n-1]}, \mathit{aCT}_{n-1}). $$

By the correctness of $\mathit{aFE}$, we have $\sigma_n = \sigma'_n$ and, by the correctness of $\mathit{LObf}$, the evaluation of $\tilde{C}_{n-1}$ outputs $\mu_{n-1} = \{\mathit{aDK}_{\ell,n-1}\}_{\ell \in [0; n-2]}$.

**Induction Step.** Let $i \in [0; n-2]$. We show that, if

$$ \mathrm{Eval}(\tilde{C}_k, (\{\tilde{C}_\ell\}_{\ell \in [k+1; n-1]}, \{\mathit{aDK}_{\ell,j}\}_{\ell \in [k; n-1]}^{j \in [k]}, \{\mathit{aDK}_{\ell,f}\}_{\ell \in [k; n-1]})) = \mu_k $$

for all $k \in [i+1; n-1]$, then

$$ \mathrm{Eval}(\tilde{C}_i, (\{\tilde{C}_\ell\}_{\ell \in [i+1; n-1]}, \{\mathit{aCT}_{\ell,j}\}_{\ell \in [i; n-1]}^{j \in [i]}, \{\mathit{aDK}_{\ell,f}\}_{\ell \in [i; n-1]})) = \mu_i. $$

By construction, $\tilde{C}_i$ is an obfuscation of $C_i[\mathit{aCT}_i, \{\mathit{aDK}_{\ell,i+1}\}_{\ell \in [i+1; n-1]}]$ under the lock value $\sigma_i$ for the message $\mu_i$. From the induction hypothesis, we obtain that the for loop in the definition of $C_i[\mathit{aCT}_i, \{\mathit{aDK}_{\ell,i+1}\}_{\ell \in [i+1; n-1]}]$ correctly recovers $\{\mathit{aDK}_{i,j}\}_{j \in [i+1; n-1]}$. Given in addition $\mathit{aCT}_i$ hardwired in the description of the circuit and $\{\mathit{aDK}_{i,j}\}_{j \in [i]}$ from the input, the circuit returns the decryption result

$$ \sigma'_i \leftarrow \mathrm{aDec}(\mathit{aDK}_{i,f}, \{\mathit{aDK}_{i,j}\}_{j \in [n-1]}, \mathit{aCT}_i). $$

The correctness of $\mathit{aFE}$ implies $\sigma_i = \sigma'_i$, and we can conclude from the correctness of $\mathit{LObf}$ that the evaluation of the obfuscated circuit indeed yields $\mu_i$ as desired.

□
**Security.** We show that the compiler preserves the security level of the underlying MC-ABE.

**Proposition 11.** Let $\mathbf{xxx} \in \{\text{sel, adap}\}$ and $\mathbf{yyy} \in \{\text{rep, norep}\}$. If aFE is $\mathbf{xxx-yyy-secure}$ and LObf is secure, then the MC-PE scheme pFE in Construction 9 is also $\mathbf{xxx-yyy-secure}$.

*Proof.* The proof proceeds via a sequence of hybrid games $G_{0,1}^b, G_{1,0}^b, G_{1,1}^b, G_{2,0}^b, G_{2,1}^b, \dots, G_{n,0}^b, G_{n,1}^b$ with $G_{0,1}^b = \text{Exp}_{\text{pFE},\mathcal{A}}^{\text{mc-pe-b}}(1^{\lambda})$ for $b \in \{0,1\}$ and $G_{n,0}^b \equiv G_{n,1}^1$. We argue that $G_{\kappa-1,1}^b \approx_c G_{\kappa,0}^b$ and $G_{\kappa,0}^b \approx_c G_{\kappa-1,1}^b$ for all $\kappa \in [n]$ and $b \in \{0,1\}$. Then the proposition follows via a hybrid argument. Modifications between consecutive games are highlighted using *boxes*.

**Game $G_{0,1}^b$ for $b \in \{0,1\}$:** This game is the same as $\text{Exp}_{\text{pFE},\mathcal{A}}^{\text{mc-pe-b}}(1^{\lambda})$.

**Game $G_{\kappa,0}^b$ for $\kappa \in [n-1]$ and $b \in \{0,1\}$:** Let $i = n - \kappa$. This game is the same as $G_{\kappa-1,1}^b$ except that in replies to queries of the form $\text{OAKeyGen}(i, \text{lab}, x_i^0, x_i^1)$ with $x_i^0 \neq x_i^1$, the challenger computes

$$ \text{aCT}_i \leftarrow \text{aEnc}(\text{aMPK}_i, \text{lab}, x_i^b, \mathbf{0}^m), $$

as opposed to $\text{aCT}_i \leftarrow \text{aEnc}(\text{aMPK}_i, \text{lab}, x_i^b, \sigma_i)$ for $\sigma_i \stackrel{\mathcal{S}}{\rightleftharpoons} \mathcal{M}$.

*Claim 12.* If aFE is secure, then $G_{\kappa-1,1}^b \approx_c G_{\kappa,0}^b$.

**Game $G_{\kappa,0}^b$ for $\kappa \in [n-1]$ and $b \in \{0,1\}$:** Let $i = n - \kappa$. The security of LObf guarantees the existence of an efficient simulator Sim. This game is the same as $G_{\kappa,0}^b$ except that in replies to queries of the form $\text{OAKeyGen}(i, \text{lab}, x_i^0, x_i^1)$ with $x_i^0 \neq x_i^1$, the challenger computes

$$ \tilde{C}_i \leftarrow \text{Sim}(1^{\lambda}, 1^{|C_i[aCT_i, \{\text{aDK}_{\ell,i+1}\}_{\ell \in [i+1:n-1]}|}, 1^{|\{\text{aDK}_{\ell,i}\}_{\ell \in [0:i-1]}|}), $$

instead of $\tilde{C}_i \leftarrow \text{Obf}(1^{\lambda}, C_i[aCT_i, \{\text{aDK}_{\ell,i+1}\}_{\ell \in [i+1:n-1]}], \{\text{aDK}_{\ell,i}\}_{\ell \in [0:i-1]}, \sigma_i)$.

*Claim 13.* If LObf is secure, then $G_{\kappa,0}^b \approx_c G_{\kappa,1}^b$.

**Game $G_{n,0}^b$ for $b \in \{0,1\}$:** This game is the same as $G_{n-1,1}^b$ except that in replies to queries of the form $\text{OEnc}(\text{lab}, x_0^0, x_0^1, \mu^0, \mu^1)$ with $x_0^0 \neq x_0^1$, the challenger computes

$$ \text{aCT}_0 \leftarrow \text{aEnc}(\text{aMPK}_0, \text{lab}, x_0^b, \mathbf{0}^m), $$

as opposed to $\text{aCT}_0 \leftarrow \text{aEnc}(\text{aMPK}_0, \text{lab}, x_0^b, \sigma_0)$.

*Claim 14.* If aFE is secure, then $G_{n-1,1}^b \approx_c G_{n,0}^b$.

The proof of Claim 14 is similar to that of Claim 12.

**Game $G_{n,1}^b$ for $b \in \{0,1\}$:** This game is the same as $G_{n,0}^b$ except that in replies to queries of the form $\text{OEnc}(\text{lab}, x_0^0, x_0^1, \mu^0, \mu^1)$ with $x_0^0 \neq x_0^1$ or $\mu^0 \neq \mu^1$, the challenger computes

$$ \tilde{C}_0 \leftarrow \text{Obf}(1^{\lambda}, 1^{|C_0[aCT_0, \{\text{aDK}_{\ell,1}\}_{\ell \in [n-1]}|}, 1^{|\mu^b|}), $$

as opposed to $\tilde{C}_0 \leftarrow \text{Obf}(1^{\lambda}, C_0[aCT_0, \{\text{aDK}_{\ell,1}\}_{\ell \in [n-1]}], \mu^b, \sigma_0)$.

*Claim 15.* If LObf is secure, then $G_{n,0}^b \approx_c G_{n,1}^b$.

The proof of Claim 15 is similar to that of Claim 13. It is not hard to see that $G_{n,0}^0 \equiv G_{n,1}^1$ as $|\mu^0| = |\mu^1|$ for all encryption queries $\text{OEnc}(\text{lab}, x_0^0, x_0^1, \mu^0, \mu^1)$ and, thus, all responses of the challenger are independent of the challenge bit $b$. This concludes the proof of Proposition 11. □
We now turn to the claims.

*Proof (Claim 12).* Let $i = n - \kappa$ as above. We show that if a PPT adversary $\mathcal{A}$ distinguishes between $G_{\kappa-1,1}^b$ and $G_{\kappa,0}^b$ with non-negligible probability, then there exists a PPT adversary $\mathcal{B}$ that can break the security of the $i$-th aFE instance using $\mathcal{A}$. The reduction is as follows:

* Initialization. Upon $\mathcal{A}$ calling Initialize$(1^{\lambda})$, $\mathcal{B}$ calls the initialization procedure $\mathbf{aMPK}_i \leftarrow \text{Initialize}(1^{\lambda})$ of its own game $\mathbf{Exp}_{\text{aFE},\mathcal{B}}^{\text{mc-abe-}\beta}(1^{\lambda})$ and generates keys for $n-1$ aFE instances by running

$$ \{(\mathbf{aMPK}_{\ell}, \mathbf{aMSK}_{\ell}, \{\mathbf{aSK}_{\ell,i}\}_{i \in [n-1]}) \leftarrow \mathbf{aSetup}(1^{\lambda})\}_{\ell \in [0; n-1] \setminus \{i\}} . $$

* Corruption Queries. Upon $\mathcal{A}$ calling $\mathcal{O}Corrupt(k)$ for $k \in [0; n-1]$, $\mathcal{B}$ first checks if $k \neq i$, in which case it submits a query $\mathbf{aSK}_{i,\rho_i(k)} \leftarrow \mathcal{O}Corrupt(\rho_i(k))$ to its own challenger. Then it sends $\mathbf{SK}_k = (\mathbf{aMPK}_k, \{\mathbf{aSK}_{\ell,j}\}_{(\ell,j) \in J_k})$ to $\mathcal{A}$.

* Encryption Queries. Upon $\mathcal{A}$ calling $\mathcal{O}Enc(\mathbf{lab}, x_0^0, x_0^1, \mu^0, \mu^1)$, $\mathcal{B}$ samples $\sigma_0 \stackrel{\$}{\leftarrow} \mathcal{M}$, submits a query $\mathbf{aDK}_{i,1} \leftarrow \mathcal{O}AKeyGen(1, \mathbf{lab}, x_0^b)$ to its own game $\mathbf{Exp}_{\text{aFE},\mathcal{B}}^{\text{mc-abe-}\beta}(1^{\lambda})$ and returns $\text{CT}_{\text{lab}} = \tilde{C}_0$ computed as follows

$$ \begin{aligned} & \mathbf{aCT}_0 \leftarrow \mathbf{aEnc}(\mathbf{aMPK}_0, \mathbf{lab}, x_0^b, \sigma_0) \\ & \{\mathbf{aDK}_{\ell,1} \leftarrow \mathbf{aAKeyGen}(\mathbf{aSK}_{\ell,1}, \mathbf{lab}, x_0^b)\}_{\ell \in [n-1] \setminus \{i\}} \\ & \tilde{C}_0 \leftarrow \mathbf{Obf}(1^{\lambda}, C_0[\mathbf{aCT}_0, \{\mathbf{aDK}_{\ell,1}\}_{\ell \in [n-1]}], \mu^b, \sigma_0) . \end{aligned} $$

* Attribute Key Generation Queries. Upon $\mathcal{A}$ calling $\mathcal{O}AKeyGen(k, \mathbf{lab}, x_k^0, x_k^1)$ for $k \in [n-1]$, $\mathcal{B}$ behaves according to the following case distinction:

* If $k \in [i-1]$, then $\mathcal{B}$ samples $\sigma_k \stackrel{\$}{\leftarrow} \mathcal{M}$, submits a query $\mathbf{aDK}_{i,k+1} \leftarrow \mathcal{O}AKeyGen(k+1, \mathbf{lab}, x_k^b)$ to its own game $\mathbf{Exp}_{\text{aFE},\mathcal{B}}^{\text{mc-abe-}\beta}(1^{\lambda})$ and returns $\mathbf{DK}_{\text{lab},k} = \tilde{C}_k$ computed as follows

$$ \begin{aligned} & \mathbf{aCT}_k \leftarrow \mathbf{aEnc}(\mathbf{aMPK}_k, \mathbf{lab}, x_k^b, \sigma_k) \\ & \{\mathbf{aDK}_{\ell,j} \leftarrow \mathbf{aAKeyGen}(\mathbf{aSK}_{\ell,j}, \mathbf{lab}, x_k^b)\}_{(\ell,j) \in J_k \setminus \{(i,k+1)\}} \\ & \tilde{C}_k \leftarrow \mathbf{Obf}(1^{\lambda}, C_k[\mathbf{aCT}_k, \{\mathbf{aDK}_{\ell,k+1}\}_{\ell \in [k+1;n-1]}], \{\mathbf{aDK}_{\ell,k}\}_{\ell \in [0;k-1]}, \sigma_k). \end{aligned} $$

* If $k = i$, then $\mathcal{B}$ samples $\sigma_i \stackrel{\$}{\leftarrow} \mathcal{M}$, sets

$$ (\mathbf{v}_0, \mathbf{v}_1) = \begin{cases} (\sigma_i, 0^m) & \text{if } x_i^0 \neq x_i^1 \\ (\sigma_i, \sigma_i) & \text{if } x_i^0 = x_i^1 \end{cases}, $$

submits a query $\mathbf{aCT}_i \leftarrow \mathcal{O}Enc(\mathbf{lab}, x_i^b, \mathbf{v}_0, \mathbf{v}_1)$ to its own challenger $\mathbf{Exp}_{\text{aFE},\mathcal{B}}^{\text{mc-abe-}\beta}(1^{\lambda})$ and returns $\mathbf{DK}_{\text{lab},i} = \tilde{C}_i$ computed as follows

$$ \begin{aligned} & \{\mathbf{aDK}_{\ell,j} \leftarrow \mathbf{aAKeyGen}(\mathbf{aSK}_{\ell,j}, \mathbf{lab}, x_i^b)\}_{(\ell,j) \in J_i} \\ & \tilde{C}_i \leftarrow \mathbf{Obf}(1^{\lambda}, C_i[\mathbf{aCT}_i, \{\mathbf{aDK}_{\ell,i+1}\}_{\ell \in [i+1;n-1]}], \{\mathbf{aDK}_{\ell,i}\}_{\ell \in [0;i-1]}, \sigma_i). \end{aligned} $$

* If $k \in [i+1; n-1]$, then $\mathcal{B}$ submits a query $\mathbf{aDK}_{i,k} \leftarrow \mathcal{O}AKeyGen(k, \mathbf{lab}, x_k^b)$ to its own game $\mathbf{Exp}_{\text{aFE},\mathcal{B}}^{\text{mc-abe-}\beta}(1^{\lambda})$ and generates decryption keys $\mathbf{aDK}_{\ell,j} \leftarrow \mathbf{aAKeyGen}(\mathbf{aSK}_{\ell,j}, \mathbf{lab}, x_k^b)$ for all $(\ell, j) \in J_k \setminus \{(i, k)\}$ by itself. If $x_k^0 \neq x_k^1$, it computes

$$ \begin{aligned} & \mathbf{aCT}_k \leftarrow \mathbf{aEnc}(\mathbf{aMPK}_k, \mathbf{lab}, x_k^b, 0^m) \\ & \tilde{C}_k \leftarrow \text{Sim}(1^{\lambda}, 1^{|C_k[\mathbf{aCT}_k, \{\mathbf{aDK}_{\ell,k+1}\}_{\ell \in [k+1;n-1]}|}, 1^{|\{\mathbf{aDK}_{\ell,k}\}_{\ell \in [0;k-1]}|}) . \end{aligned} $$
Otherwise, $\mathcal{B}$ samples $\sigma_k \stackrel{\$}{\leftarrow} \mathcal{M}$ and computes

$$ \begin{aligned} \text{aCT}_k &\leftarrow \text{aEnc}(\text{aMPK}_k, \text{lab}, x_k^b, \sigma_k) \\ \tilde{C}_k &\leftarrow \text{Obf}(1^{\lambda}, C_k[\text{aCT}_k, \{\text{aDK}_{\ell,k+1}\}_{\ell \in [k+1:n-1]}], \{\text{aDK}_{\ell,k}\}_{\ell \in [0:k-1]}, \sigma_k). \end{aligned} $$

Finally, $\mathcal{B}$ sends $\text{DK}_{\text{lab},k} = \tilde{C}_k$ to $\mathcal{A}$.

*   **Policy Key Generation Queries.** Upon $\mathcal{A}$ calling $\text{PKeyGen}(f)$, $\mathcal{B}$ submits a query $\text{aDK}_{i,f} \leftarrow \text{OPKeyGen}(\pi_i(f))$ to its own game $\text{Exp}_{\text{aFE},\mathcal{B}}^{\text{mc-abe-}\beta}(1^{\lambda})$, runs

$$ \{\text{aDK}_{\ell,f} \leftarrow \text{aPKeyGen}(\text{aMSK}_{\ell}, \pi_{\ell}(f))\}_{\ell \in [0; n-1] \setminus \{i\}}, $$

and sends $\text{DK}_f = \{\text{aDK}_{\ell,f}\}_{\ell \in [0; n-1]}$ to $\mathcal{A}$.

*   **Finalization.** Upon $\mathcal{A}$ calling $\text{Finalize}(b')$, $\mathcal{B}$ calls the finalization procedure $\text{Finalize}(b')$ of its own game $\text{Exp}_{\text{aFE},\mathcal{B}}^{\text{mc-abe-}\beta}(1^{\lambda})$.

We observe that if $\mathcal{A}$ is an admissible adversary in $\text{Exp}_{\text{pFE},\mathcal{A}}^{\text{mc-pe-b}}(1^{\lambda})$, then $\mathcal{B}$ is admissible in $\text{Exp}_{\text{aFE},\mathcal{B}}^{\text{mc-abe-}\beta}(1^{\lambda})$. We further observe that if $\mathcal{B}$'s challenger returns an encryption of $\mathbf{v}_0$ (i.e. $\beta = 0$), then $\mathcal{B}$ simulates $G_{\kappa-1,1}^b$; and if the challenger returns an encryption of $\mathbf{v}_1$ (i.e. $\beta = 1$), then $\mathcal{B}$ simulates $G_{\kappa,0}^b$.

□

*Proof* (Claim 13). Let $i = n - \kappa$ as above. We show that if a PPT adversary $\mathcal{A}$ distinguishes between $G_{\kappa,0}$ and $G_{\kappa,1}$ with non-negligible probability, then there exists a PPT adversary $\mathcal{B}$ that can break the strong security of $\text{LObf}$ using $\mathcal{A}$. The reduction is as follows:

*   **Initialization.** Upon $\mathcal{A}$ calling $\text{Initialize}(1^{\lambda})$, $\mathcal{B}$ generates $n$ aFE instances

$$ \{(\text{aMPK}_{\ell}, \text{aMSK}_{\ell}, \{\text{aSK}_{\ell,i}\}_{i \in [n-1]} \leftarrow \text{aSetup}(1^{\lambda})\}_{\ell \in [0; n-1]} . $$

*   **Corruption Queries.** Upon $\mathcal{A}$ calling $\text{Corrupt}(k)$ for $k \in [0; n-1]$, $\mathcal{B}$ sends $\text{SK}_i = (\text{aMPK}_i, \{\text{aSK}_{\ell,j}\}_{(\ell,j) \in J_i})$ to $\mathcal{A}$.

*   **Encryption Queries.** Upon $\mathcal{A}$ calling $\text{OEnc}(\text{lab}, x_0^0, x_0^1, \mu^0, \mu^1)$, $\mathcal{B}$ samples $\sigma_0 \stackrel{\$}{\leftarrow} \mathcal{M}$ and returns $\text{CT}_{\text{lab}} = \tilde{C}_0$ computed as follows:

$$ \begin{aligned} \text{aCT}_0 &\leftarrow \text{aEnc}(\text{aMPK}_0, \text{lab}, x_0^b, \sigma_0) \\ \{\text{aDK}_{\ell,1} &\leftarrow \text{aAKeyGen}(\text{aSK}_{\ell,1}, \text{lab}, x_0^b)\}_{\ell \in [n-1]} \\ \tilde{C}_0 &\leftarrow \text{Obf}(1^{\lambda}, C_0[\text{aCT}_0, \{\text{aDK}_{\ell,1}\}_{\ell \in [n-1]}], \mu, \sigma_0) . \end{aligned} $$

*   **Attribute Key Generation Queries.** Upon $\mathcal{A}$ calling $\text{OKeyGen}(k, \text{lab}, x_k^0, x_k^1)$ for $k \in [n-1]$, $\mathcal{B}$ behaves according to the following case distinction:

*   If $k \in [i-1]$, then $\mathcal{B}$ samples $\sigma_k \stackrel{\$}{\leftarrow} \mathcal{M}$ and returns $\text{CT}_k = \tilde{C}_k$ computed as follows:

$$ \begin{aligned} \text{aCT}_k &\leftarrow \text{aEnc}(\text{aMPK}_k, \text{lab}, x_k^b, \sigma_k) \\ \{\text{aDK}_{\ell,j} &\leftarrow \text{aAKeyGen}(\text{aSK}_{\ell,j}, \text{lab}, x_k^b)\}_{(\ell,j) \in J_k} \\ \tilde{C}_k &\leftarrow \text{Obf}(1^{\lambda}, C_k[\text{aCT}_k, \{\text{aDK}_{\ell,k+1}\}_{\ell \in [k+1:n-1]}], \{\text{aDK}_{\ell,k}\}_{\ell \in [0:k-1]}, \sigma_k). \end{aligned} $$
◦ If $k = i$ and $x_k^0 \neq x_k^1$, then $\mathcal{B}$ runs

$$ \begin{aligned} & \text{aCT}_i \leftarrow \text{aEnc}(\text{aMPK}_i, \text{lab}, x_i^b, 0^m) \\ & \{\text{aDK}_{\ell,j} \leftarrow \text{aKeyGen}(\text{aSK}_{\ell,j}, \text{lab}, x_i^b)\}_{(\ell,j) \in J_i}, \end{aligned} $$

and returns $\tilde{C}_i$ obtained from its own $\text{LObf}$ challenger

$$ \tilde{C}_i \leftarrow \text{LObf.Obf}^{\beta}(C_i[\text{aCT}_i, \{\text{aDK}_{\ell,i+1}\}_{\ell \in [i+1;n-1]}], \{\text{aDK}_{\ell,i}\}_{\ell \in [0;i-1]}). $$

Otherwise, if $k = i$ and $x_k^0 = x_k^1$, then $\mathcal{B}$ samples $\sigma_i \stackrel{\$}{\leftarrow} \mathcal{M}$ and returns $\text{aCT}_i = \tilde{C}_i$ computed as follows:

$$ \begin{aligned} & \text{aCT}_i \leftarrow \text{aEnc}(\text{aMPK}_i, \text{lab}, x_i^b, \sigma_i) \\ & \{\text{aDK}_{\ell,j} \leftarrow \text{aKeyGen}(\text{aSK}_{\ell,j}, \text{lab}, x_i^b)\}_{(\ell,j) \in J_i} \\ & \tilde{C}_i \leftarrow \text{Obf}(1^{\lambda}, C_i[\text{aCT}_i, \{\text{aDK}_{\ell,i+1}\}_{\ell \in [i+1;n-1]}], \{\text{aDK}_{\ell,i}\}_{\ell \in [0;i-1]}, \sigma_i). \end{aligned} $$

◦ If $k \in [i+1; n]$ and $x_k^0 \neq x_k^1$, then $\mathcal{B}$ sends $\text{aCT}_k = \tilde{C}_k$ to $\mathcal{A}$ computed as follows:

$$ \begin{aligned} & \text{aCT}_k \leftarrow \text{aEnc}(\text{aMPK}_k, \text{lab}, x_k^b, 0^m) \\ & \{\text{aDK}_{\ell,j} \leftarrow \text{aKeyGen}(\text{aSK}_{\ell,j}, \text{lab}, x_k^b)\}_{(\ell,j) \in J_k} \\ & \tilde{C}_k \leftarrow \text{Sim}(1^{\lambda}, 1^{|C_k[\text{aCT}_k, \{\text{aDK}_{\ell,k+1}\}_{\ell \in [k+1;n-1]}]|}, 1^{|\{\text{aDK}_{\ell,k}\}_{\ell \in [0;k-1]}|}). \end{aligned} $$

Otherwise, if $k \in [i+1; n]$ and $x_k^0 = x_k^1$, it samples $\sigma_k \stackrel{\$}{\leftarrow} \mathcal{M}$ and returns $\text{aCT}_k = \tilde{C}_k$ computed as follows:

$$ \begin{aligned} & \text{aCT}_k \leftarrow \text{aEnc}(\text{aMPK}_k, \text{lab}, x_k^b, \sigma_k) \\ & \{\text{aDK}_{\ell,j} \leftarrow \text{aKeyGen}(\text{aSK}_{\ell,j}, \text{lab}, x_k^b)\}_{(\ell,j) \in J_k} \\ & \tilde{C}_k \leftarrow \text{Obf}(1^{\lambda}, C_k[\text{aCT}_k, \{\text{aDK}_{\ell,k+1}\}_{\ell \in [k+1;n-1]}], \{\text{aDK}_{\ell,k}\}_{\ell \in [0;k-1]}, \sigma_k). \end{aligned} $$

• Policy Key Generation Queries. Upon $\mathcal{A}$ calling $\text{OPKeyGen}(f)$, $\mathcal{B}$ runs

$$ \{\text{aDK}_{\ell,f} \leftarrow \text{aKeyGen}(\text{aMSK}_{\ell}, f)\}_{\ell \in [0; n-1]}, $$

and sends $\text{DK}_f = \{\text{aDK}_{\ell,\pi_{\ell}(f)}\}_{\ell \in [0; n-1]}$ to $\mathcal{A}$.

• Finalization. Upon $\mathcal{A}$ calling $\text{Finalize}(b')$, $\mathcal{B}$ sends $b'$ to the $\text{LObf}$ challenger.

We observe that if the challenge bit $\beta$ of the $\text{LObf}$ challenger is 0, i.e. the $\text{LObf}$ challenger returns a real obfuscation of $C_i[\{\text{aCT}_{\ell,i}\}_{\ell \in [i; n]}]$, then $\mathcal{B}$ simulates $\text{G}_{\kappa,0}$. Conversely, if $\beta = 1$, then the $\text{LObf}$ challenger returns a simulated obfuscation and $\mathcal{B}$ simulates $\text{G}_{\kappa,1}$. $\square$

Acknowledgments

This work was supported in part by the France 2030 ANR Project ANR-22-PECY-003 SecureCompute.
References

[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.

[AG21] Miguel Ambrona and Romain Gay. Multi-authority ABE, revisited. Cryptology ePrint Archive, Report 2021/1381, 2021. https://eprint.iacr.org/2021/1381.

[AG23] Miguel Ambrona and Romain Gay. Multi-authority ABE for non-monotonic access structures. In Alexandra Boldyreva and Vladimir Kolesnikov, editors, *PKC 2023, Part II*, volume 13941 of LNCS, pages 306-335. Springer, Heidelberg, May 2023. doi:10.1007/978-3-031-31371-4_11.

[AGRW17] Michel Abdalla, Romain Gay, Mariana Raykova, and Hoeteck Wee. Multi-input inner-product functional encryption from pairings. In Jean-Sébastien Coron and Jesper Buus Nielsen, editors, *EUROCRYPT 2017, Part I*, volume 10210 of LNCS, pages 601-626. Springer, Heidelberg, April / May 2017. doi:10.1007/978-3-319-56620-7_21.

[AGT21] 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.

[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.

[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.
[ARYY23] Shweta Agrawal, Mélissa Rossi, Anshu Yadav, and Shota Yamada. Constant input attribute based (and predicate) encryption from evasive and tensor LWE. In Helena Handschuh and Anna Lysyanskaya, editors, *CRYPTO 2023, Part IV*, volume 14084 of LNCS, pages 532–564. Springer, Heidelberg, August 2023. doi:10.1007/978-3-031-38551-3_17.

[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.

[AWY20] Shweta Agrawal, Daniel Wichs, and Shota Yamada. Optimal broadcast encryption from LWE and pairings in the standard model. In Rafael Pass and Krzysztof Pietrzak, editors, *TCC 2020, Part I*, volume 12550 of LNCS, pages 149–178. Springer, Heidelberg, November 2020. doi:10.1007/978-3-030-64375-1_6.

[AYY22] Shweta Agrawal, Anshu Yadav, and Shota Yamada. Multi-input attribute based encryption and predicate encryption. In Yevgeniy Dodis and Thomas Shrimpton, editors, *CRYPTO 2022, Part I*, volume 13507 of LNCS, pages 590–621. Springer, Heidelberg, August 2022. doi:10.1007/978-3-031-15802-5_21.

[Bei96] Amos Beimel. *Secure Schemes for Secret Sharing and Key Distribution*. PhD thesis, Technion - Israel Institute of Technology, Haifa, Israel, 1996. https://www.cs.bgu.ac.il/~beimel/Papers/thesis.pdf.

[BGI+01] Boaz Barak, Oded Goldreich, Russell Impagliazzo, Steven Rudich, Amit Sahai, Salil P. Vadhan, and Ke Yang. On the (im)possibility of obfuscating programs. In Joe Kilian, editor, *CRYPTO 2001*, volume 2139 of LNCS, pages 1–18. Springer, Heidelberg, August 2001. doi:10.1007/3-540-44647-8_1.

[BJK+18] Zvika Brakerski, Aayush Jain, Ilan Komargodski, Alain Passelègue, and Daniel Wichs. Non-trivial witness encryption and null-iO from standard assumptions. In Dario Catalano and Roberto De Prisco, editors, *SCN 18*, volume 11035 of LNCS, pages 425–441. Springer, Heidelberg, September 2018. doi:10.1007/978-3-319-98113-0_23.

[BL90] Josh Cohen Benaloh and Jerry Leichter. Generalized secret sharing and monotone functions. In Shafi Goldwasser, editor, *CRYPTO'88*, volume 403 of LNCS, pages 27–35. Springer, Heidelberg, August 1990. doi:10.1007/0-387-34799-2_3.

[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.

[BW07] Dan Boneh and Brent Waters. Conjunctive, subset, and range queries on encrypted data. In Salil P. Vadhan, editor, *TCC 2007*, volume 4392 of LNCS, pages 535–554. Springer, Heidelberg, February 2007. doi:10.1007/978-3-540-70936-7_29.

[CDG+18] 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.

[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.

[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.

[FFMV23] Danilo Francati, Daniele Friolo, Giulio Malavolta, and Daniele Venturi. Multi-key and multi-input predicate encryption from learning with errors. In Carmit Hazay and Martijn Stam, editors, *EUROCRYPT 2023, Part III*, volume 14006 of LNCS, pages 573–604. Springer, Heidelberg, April 2023. doi:10.1007/978-3-031-30620-4_19.

[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.

[GGH$^{+13}$] Sanjam Garg, Craig Gentry, Shai Halevi, Mariana Raykova, Amit Sahai, and Brent Waters. Candidate indistinguishability obfuscation and functional encryption for all circuits. In *54th FOCS*, pages 40–49. IEEE Computer Society Press, October 2013. doi:10.1109/FOCS.2013.13.

[GKVW20] Rishab Goyal, Venkata Koppula, Satyanarayana Vusirikala, and Brent Waters. On perfect correctness in (lockable) obfuscation. In Rafael Pass and Krzysztof Pietrzak, editors, *TCC 2020, Part I*, volume 12550 of LNCS, pages 229–259. Springer, Heidelberg, November 2020. doi:10.1007/978-3-030-64375-1_9.

[GKW17] Rishab Goyal, Venkata Koppula, and Brent Waters. Lockable obfuscation. In Chris Umans, editor, *58th FOCS*, pages 612–621. IEEE Computer Society Press, October 2017. doi:10.1109/FOCS.2017.62.

[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.

[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.

[LL20a] Huijia Lin and Ji Luo. Compact adaptively secure ABE from $k$-Lin: Beyond NC¹ and towards NL. In Anne Canteaut and Yuval Ishai, editors, *EURO-CRYPT 2020, Part III*, volume 12107 of LNCS, pages 247–277. Springer, Heidelberg, May 2020. doi:10.1007/978-3-030-45727-3_9.

[LL20b] Huijia Lin and Ji Luo. Succinct and adaptively secure ABE for ABP from $k$-Lin. In Shiho Moriai and Huaxiong Wang, editors, *ASIACRYPT 2020, Part III*, volume 12493 of LNCS, pages 437–466. Springer, Heidelberg, December 2020. doi:10.1007/978-3-030-64840-4_15.

[LLL22] Hanjun Li, Huijia Lin, and Ji Luo. ABE for circuits with constant-size secret keys and adaptive security. In Eike Kiltz and Vinod Vaikuntanathan, editors, *TCC 2022, Part I*, volume 13747 of LNCS, pages 680–710. Springer, Heidelberg, November 2022. doi:10.1007/978-3-031-22318-1_24.

[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.

[LW11] Allison B. Lewko and Brent Waters. Decentralizing attribute-based encryption. In Kenneth G. Paterson, editor, *EUROCRYPT 2011*, volume 6632 of LNCS, pages 568–588. Springer, Heidelberg, May 2011. doi:10.1007/978-3-642-20465-4_31.
[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.

[PS25] David Pointcheval and Robert Schädlich. Multi-client attribute-based and predicate encryption from standard assumptions. In Elette Boyle and Mohammad Mahmoody, editors, Theory of Cryptography, pages 31-64, Cham, 2025. Springer Nature Switzerland. doi:10.1007/978-3-031-78020-2_2.

[SBC+07] Elaine Shi, John Bethencourt, Hubert T.-H. Chan, Dawn Xiaodong Song, and Adrian Perrig. Multi-dimensional range query over encrypted data. In 2007 IEEE Symposium on Security and Privacy, pages 350-364. IEEE Computer Society Press, May 2007. doi:10.1109/SP.2007.29.

[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.

[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.

[Tsa22] Rotem Tsabary. Candidate witness encryption from lattice techniques. In Yevgeniy Dodis and Thomas Shrimpton, editors, CRYPTO 2022, Part I, volume 13507 of LNCS, pages 535-559. Springer, Heidelberg, August 2022. doi:10.1007/978-3-031-15802-5_19.

[VWW22] Vinod Vaikuntanathan, Hoeteck Wee, and Daniel Wichs. Witness encryption and null-IO from evasive LWE. In Shweta Agrawal and Dongdai Lin, editors, ASIACRYPT 2022, Part I, volume 13791 of LNCS, pages 195-221. Springer, Heidelberg, December 2022. doi:10.1007/978-3-031-22963-3_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.

[Wee17] Hoeteck Wee. Attribute-hiding predicate encryption in bilinear groups, revisited. In Yael Kalai and Leonid Reyzin, editors, TCC 2017, Part I, volume 10677 of LNCS, pages 206-233. Springer, Heidelberg, November 2017. doi:10.1007/978-3-319-70500-2_8.

[WZ17] Daniel Wichs and Giorgos Zirdelis. Obfuscating compute-and-compare programs under LWE. In Chris Umans, editor, 58th FOCS, pages 600-611. IEEE Computer Society Press, October 2017. doi:10.1109/FOCS.2017.61.