Multi-authority ABE for Non-monotonic Access Structures

Abstract

Attribute-Based Encryption (ABE) is a cryptographic primitive which supports fine-grained access control on encrypted data, making it an appealing building block for many applications. Multi-Authority Attribute-Based Encryption (MA-ABE) is a generalization of ABE where the central authority is distributed across several independent parties.

We provide the first MA-ABE scheme from asymmetric prime-order pairings where no trusted setup is needed and where the attribute universe of each authority is unbounded. Moreover, it is the first to handle non-monotonic access structures. These features broaden the applicability and improve the efficiency of our scheme. Our construction makes a modular use of Functional Encryption schemes with fine-grained access control.

1 Introduction

Attribute-Based Encryption (ABE) [SW05, GPSW06] subsumes traditional public-key encryption by providing fine-grained access to the encrypted data. Namely, each ciphertext is associated with an access policy, and each user receives a so-called user secret key according to their credentials. If these credentials fulfill the policy, the user secret key can be used to successfully decrypt the ciphertext. Otherwise, the plaintext remains hidden, even if several non-authorized users collude.

Despite being a prominent topic in the research community, the notion of ABE suffers from several drawbacks. User secret keys are generated from a so-called master secret key, which can decrypt any ciphertext. Consequently, the generation of these keys must be performed by a trusted third party, who controls the master secret key and who must be online every time a key is requested (not only during the setup phase of the scheme). Such a third party is a single point of failure in the system and is likely to be a target for attacks. Copying the master secret and using redundant servers to alleviate this bottleneck only increases the chances of key exposure. Besides, the master secret key owner can impersonate any user of its choice, acting as an escrow (see [Rog15] for further details on this issue). To mitigate these shortcomings, a solution is to decentralize the key-generation so that no single party holds the master secret key in full. Furthermore, decentralization is encouraged given that in many scenarios the access policy used to generate a ciphertext includes attributes coming from different organizations.

The work of [Cha07] and later [MKE08] considered a variation of ABE where any party can become an authority by publishing some public key; these authorities, created on the fly, handle different attributes, and no coordination is required among them. In these systems, a user equipped with a global identifier can collect different credentials associated with different attributes from each authority. However, the user must then interact with a trusted central authority that will process such credentials and provide the actual ABE user secret keys. The advantage of their approach is that this central authority is agnostic to the meaning of the attributes and credentials of the user, and does not need to communicate with the other authorities. However, most of the aforementioned shortcomings remain. Afterward, [LCLS08] removed the need for a central authority, but the set of authorities in their construction is fixed and they must interact during the setup phase. Another limitation is that the security of their scheme is only proven for an a priori bounded number of collusions. [CC09] also presented a scheme with no central authority relying on distributed PRFs. However, their scheme is still limited in terms of expressiveness (it can only express a strict AND policy) and only handles a pre-determined set of attributes. In [LW11], the authors gave the first construction where there is no central authority, authorities can join the system on the fly without communicating with each other and the ciphertexts can be associated with a rich class of expressive access policies (including Boolean formulas). Despite these impressive features, their construction still suffers from some limitations: it requires a trusted setup; it uses inefficient composite-order pairings; each authority can only handle a small (poly-size) set of attributes as, in fact, the public key of each authority grows with the number of attributes owned by the authority. Later on, in [OT13, RW15], the authors built MA-ABE where there is no trusted setup beyond the mere agreement of which groups and which hash function to use, and where the attribute set of each authority is of exponential size or unbounded. Moreover, these schemes have the advantage of using prime-order pairings, which are more efficient than their composite-order counterparts. However, the scheme from [OT13] is not shown to achieve security in the presence of corrupted authorities, an important requirement in the standard security definition for MA-ABE. The scheme from [RW15] inherits from [LW11] prohibitively large ciphertexts. Indeed, in these schemes, each ciphertext contains a number of target group elements that grows with the size of its associated access policy, which are significantly larger than source group elements. Another reason all existing schemes lack practical efficiency is their use of symmetric pairings, which are less efficient than their asymmetric counterparts. This is in contrast with state-of-the-art single-authority ABE schemes, defined over asymmetric pairings and without target group elements in the ciphertext.

Finally, existing MA-ABE can only handle monotonic access structures. Namely, policies that can be expressed by a Boolean formula with positive literals only, e.g. of the form: $\textsf{Role}= Reviewer \wedge \textsf{Year}= 2022$. Suppose the document to be encrypted is an audit of the security department of some company for the year 2022. In order to avoid conflict of interests, employees from the security department should not be able to access the document. This corresponds to the non-monotonic formula: $(\textsf{Role} = Reviewer \wedge \textsf{Year} = 2022 ) \wedge \lnot (\textsf{Department} = Security )$. A naive way to implement negative literals would be to give user secret keys associated with both the credential owned by the user and all the negative literals not owned by the user, e.g. $\lnot (\textsf{HumanResources})$, $\lnot (\textsf{IT})$, $\lnot (\textsf{Marketing})$, $\lnot (\mathsf {R \& D})$, $\lnot (\textsf{Production})$, and so on, for all existing departments in the company where the user does not belong. This solution yields very large user secret keys, since they grow proportionally with the number of possible attributes. In fact, this becomes unfeasible for large attribute universe (where the number of attribute is super-polynomial), let alone unbounded universe (where there is no restriction on the number of possible attributes, i.e. any bit string can serve as an attribute). [OSW07] gave the first ABE for non-monotonic formulas, but their techniques do not seem to be directly applicable to the multi-authority setting. This prompts the question: Can we achieve MA-ABE with similar features and efficiency than single-authority ABE?

Our contribution. We provide the first MA-ABE scheme from asymmetric prime-order pairings, without trusted setup and where the attribute universe of each authority is of unbounded size. Furthermore, our scheme handles non-monotonic access structures. It makes a modular use of practical Functional Encryption (FE) schemes for simple functions, namely, inner-products (we refer to our technical overview for more details about the FE we use). We prove security from standard assumptions using pairings (namely, the SXDH assumption) in the random oracle model. Our construction achieves security against adversaries that can choose the access structure of the challenge ciphertext and the attributes of the user secret keys, but the access structure and the attributes chosen cannot depend on the cryptographic material received. That is, they must not depend on the challenge ciphertext or the user secret keys (although they can depend on the public key). We refer to this security notion as super-selective security—the selective security notion traditionally refers to the setting where the adversary is constrained to choose the access structure used in the challenge ciphertext before receiving any cryptographic material (either the public key or the user secret keys). We leave it as an open problem to obtain adaptive security. Table 1 compares our scheme with the state-of-the-art.

Table 1. Comparison among MA-ABE schemes. The attribute universe is said to be small when it is a-priori bounded by a polynomial in the security parameter. It is said to be large when it is of a-priori bounded exponential size in the security parameters, or not bounded at all. “Corrupted authorities” refers to whether or not the scheme is secure when the adversary can acquire the secret keys of some authorities of their choice, or even create authorities with a public key of their choice (this is the standard definition for MA-ABE). “q-type” refers to a family of parameterized computational assumptions in pairing groups. “s-selective” refers to the super-selective security notion (defined in Sect. 2.5).

Technical overview. We consider an MA-ABE where access policies are represented by monotone span programs (MSP) (as per Definition 1), which capture monotonic Boolean formulas. We explain how to handle non-monotonic formulas later in this overview. In a nutshell, an MSP allows users to produce shares $s_1,\ldots ,s_\ell$ of a secret s, where $\ell$ is the size of the MSP, and each share $s_j$ is associated with an attribute $\rho (j)$. Akin to standard secret sharing schemes, the secret s can be recovered if and only if sufficiently many shares $s_j$ are given. The ABE uses cyclic groups $\mathbb {G}_{\textsf{1}},\mathbb {G}_{\textsf{2}},\mathbb {G}_{\textsf{t}}$ of prime order p, equipped with a bilinear map $e: \mathbb {G}_{\textsf{1}}\times \mathbb {G}_{\textsf{2}}\rightarrow \mathbb {G}_{\textsf{t}}$. We use additive bracket notation for all three groups, that is, for $\textsf{s} \in \{1,2,\textsf{t}\}$, and all scalars $x \in \mathbb {Z}_p$, we write $\llbracket x \rrbracket _\textsf{s} = x P_\textsf{s}$ where $P_\textsf{s}$ is a generator of $\mathbb {G}_\textsf{s}$. Finally, we make use of Functional Encryption (FE) schemes, which are an advanced form of public-key encryption where the secret key can be used to derive functional secret keys $\textsf{sk}_f$ for certain functions f. Decryption can use $\textsf{sk}_f$ to extract from an encryption $\textsf{Enc}(\textsf{pk},m)$ of the message m the value f(m). Nothing else is revealed about the message m apart from the value f(m). Many functional secret keys can be derived for different functions from the secret key (which is referred to as master secret key, just like in the ABE setting). In short, FE enables selective computations on encrypted data. We rely on practical FE schemes that handle a particular class of functions of interest.

For encryption, an exponent s is uniformly sampled from $\mathbb {Z}_p$ and the encapsulation key is defined as $\llbracket s \rrbracket _\textsf{t}$ (we consider the KEM variant of ABE). The MSP is used to create shares $\{s_j\}_{j \in [\ell ]}$ of s and shares $\{u_j\}_{j \in [\ell ]}$ of 0. The MA-ABE ciphertext consists of one FE ciphertext of the vector $(s_j,u_j)$ per $j \in [\ell ]$. The public key of the FE used for each $j\in [\ell ]$ is published by the authority that owns the attribute $\rho (j)$. Note that in order to register into the system, each authority will run the FE setup algorithm to create its pair of keys $(\textsf{FE}.\textsf{pk},\textsf{FE}.\textsf{msk})$.

The FE we are using is for identity-based inner-products. That is, each ciphertext encrypts a vector $\boldsymbol{x}$ (of some fixed dimension, say d, which is then set to 2 for our modular construction), and an identity $\textsf{id}$. Each functional secret key is associated with a vector $\llbracket \boldsymbol{y} \rrbracket _\textsf{2} \in \mathbb {G}_{\textsf{2}}^d$ and an identity $\textsf{id}'$. The decryption of the ciphertext with the functional secret key succeeds if the identities match, in which case the inner-product $\llbracket \boldsymbol{x}^\top \boldsymbol{y} \rrbracket _\textsf{t}$ is recovered. Nothing else is revealed about the encrypted vector $\boldsymbol{x}$. However, we do not require that the identities $\textsf{id}$ and $\textsf{id}'$ or the vector $\llbracket \boldsymbol{y} \rrbracket _\textsf{2}$ remain hidden. These functional secret keys can be generated from the master secret key of the FE scheme.

As we explained, the MA-ABE ciphertext will contain the FE encryption of the vector $(s_j,u_j)$ for the identity $\rho (j)$, under the $\textsf{FE}.\textsf{pk}$ of the authority that owns attribute $\rho (j)$, for all $j \in [\ell ]$.

The secret key of a user identified by a global identifier $\textsf{gid}$, for an attribute $\textsf{att}$, will contain the FE functional secret key for the vector $\llbracket (1,z_\textsf{gid}) \rrbracket _\textsf{2}$ and the identity $\textsf{att}$, where $\llbracket z_\textsf{gid} \rrbracket _\textsf{2}$ is the output of the hash value $H(\textsf{gid})$. This FE functional secret key is computed using the FE master secret key of the authority that owns the attribute $\textsf{att}$.

The user $\textsf{gid}$ collects all the FE functional secret keys $\textsf{sk}_{\llbracket (1,z_\textsf{gid}) \rrbracket _\textsf{2},\textsf{att}}$, by making a request $(\textsf{att}, \textsf{gid})$ to the relevant authorities. Each FE key $\textsf{sk}_{\llbracket (1,z_\textsf{gid}) \rrbracket _\textsf{2},\textsf{att}}$ yields the value $\llbracket s_j+z_{\textsf{gid}}u_j \rrbracket _\textsf{t}$ if j is such that $\rho (j)=\textsf{att}$. If sufficiently many such values are revealed, then they can be combined to obtain $\llbracket s+z_{\textsf{gid}} \cdot 0 \rrbracket _\textsf{t} = \llbracket s \rrbracket _\textsf{t}$, the encapsulation key. Otherwise said, if the user $\textsf{gid}$ possesses enough attributes to satisfy the MSP in the ciphertext, it recovers the encapsulation key. Here we rely on the fact that the share reconstruction for an MSP is linear.

To argue security, we could simply rely on the simulation security of the underlying FE scheme, which states that only the value $\llbracket s_j+z_{\textsf{gid}}u_j \rrbracket _\textsf{t}$ is revealed by the ciphertext and the FE functional secret key for identity $\rho (j)$ and vector $\llbracket (1,z_\textsf{gid}) \rrbracket _\textsf{2}$ (together with the value $\llbracket z_\textsf{gid} \rrbracket _\textsf{2}$, which is public). Note that the term $\llbracket z_{\textsf{gid}} u_j \rrbracket _\textsf{t}$ prevent collusions across different $\textsf{gid}$. In fact it hides the share $s_j$, assuming the values $\llbracket z_\textsf{gid} \rrbracket _\textsf{2}$ generated by the hash function are pseudo-random (this holds in the random oracle model). So, if for any given $\textsf{gid}$ there are not enough attributes to satisfy the access structure associated to the ciphertext, then there are not enough values $\llbracket s_j+z_{\textsf{gid}}u_j \rrbracket _\textsf{t}$ to recover $\llbracket s \rrbracket _\textsf{t}$, which remains hidden.

This approach works, but it requires an FE scheme that is simulation-secure with many challenge ciphertexts. Unfortunately, such primitive cannot be built from standard assumptions (this can be proved by an incompressibility argument, similar to [BSW11], see Remark 1). We use an FE with indistiguishability-based security instead, which means that our MA-ABE requires a more sophisticated security proof relying on some prime-order variant of the dual vector pairing space methodology [OT09, Lew12]. Our modular construction can be instantiated with any FE with indistinguishability-based security for the appropriate functionality, such as the scheme from [ACGU20].

We now explain how to handle non-monotonic access structures, represented by span programs where each share is associated with either a normal or negated attribute (as per Definition 2). For negated attributes, we simply replace the identity-based FE for inner-products (which we call $\mathcal{F}\mathcal{E}_1$ here) in our modular construction with an FE with revocations (called $\mathcal{F}\mathcal{E}_2$). That is, the ciphertext of $\mathcal{F}\mathcal{E}_2$ encrypts a vector $\boldsymbol{x}$ together with an identity $\textsf{id}$, as before, but now each functional secret key is associated with a vector $\llbracket \boldsymbol{y} \rrbracket _\textsf{2}$ and a set of identities $\mathcal {S}$. If $\textsf{id}\notin \mathcal {S}$, then the decryption recovers $\llbracket \boldsymbol{x}^\top \boldsymbol{y} \rrbracket _\textsf{t}$. Else, no information is revealed about $\boldsymbol{x}$ (although the identity $\textsf{id}$, the vector $\llbracket \boldsymbol{y} \rrbracket _\textsf{2}$ and the set $\mathcal {S}$ are not hidden). We present a new construction for such an FE scheme whose selective security is proven under standard pairing assumptions (SXDH). Our modular MA-ABE for non-monotonic access structures uses $\mathcal{F}\mathcal{E}_1$ and $\mathcal{F}\mathcal{E}_2$ as follows. The encryption creates shares $\{s_j\}_{j \in [\ell ]}$ of a random value s and shares $\{u_j\}_{j \in [\ell ]}$ of 0 according to the span program that represents the access structure, as before. The novelty here is that each share $j \in [\ell ]$ is mapped to $\rho (j)$ which is either a normal attribute, in which case the encryption encrypts the vector $(s_j,u_j)$ with the identity $\rho (j)$ using $\mathcal{F}\mathcal{E}_1$; or it is mapped to $\rho (j)$ which is a negated attribute, in which case the encryption encrypts $(s_j,u_j)$ with the identity $\rho (j)$ but this time using $\mathcal{F}\mathcal{E}_2$. Let $\textsf{gid}$ be the global identifier of a user that possesses different sets of attributes $\mathcal {S}_\textsf{aut}=\{\textsf{att}^\textsf{aut}_1,\ldots ,\textsf{att}^\textsf{aut}_{n_\textsf{aut}}\}$ each owned by a different authority $\textsf{aut}$. For each authority $\textsf{aut}$, the user collects the $\mathcal{F}\mathcal{E}_2$ functional secret key for the vector $\llbracket (1,z_\textsf{gid}) \rrbracket _\textsf{2}$ and the set $\mathcal {S}_\textsf{aut}$, together with a set of $n_\textsf{aut}$ $\mathcal{F}\mathcal{E}_1$ functional secret keys for the vector $\llbracket (1,z_\textsf{gid}) \rrbracket _\textsf{2}$ and the identity $\textsf{att}^\textsf{aut}_i$ for $i=1,\ldots ,n_\textsf{aut}$. Thanks to these keys, a user can recover the values $\llbracket s_j + z_\textsf{gid}u_j \rrbracket _\textsf{t}$ for the shares j associated with $\rho (j)$ which is either a normal attribute owned by the user $\textsf{gid}$, or a negated attributed that is not part of the set of attributes owned by $\textsf{gid}$. As a result, decryption succeeds if and only if the attributes of the user $\textsf{gid}$ satisfy the non-monotonic access structure. The security of the MA-ABE boils down to the security of the underlying FE schemes.

To build the FE for inner-products with revocations, we start with a one-time statistically secure scheme where the encryption of a vector $\boldsymbol{x}\in \mathbb {Z}_p^n$ for an identity $\textsf{id}^\star \!\in \mathbb {Z}_p$ is of the form $\textsf{ct}=\big (\boldsymbol{x}+ \boldsymbol{v},P(\textsf{id}^\star )\big )$ where $\boldsymbol{v}\in \mathbb {Z}_p^n$ is a random vector and P is a random polynomial evaluated on $\textsf{id}^\star \!\in \mathbb {Z}_p$. The functional secret key for a vector $\boldsymbol{y}\in \mathbb {Z}_p^n$ and a set of identities $\mathcal {S}\subset \mathbb {Z}_p$ is of the form $\textsf{sk}_{\boldsymbol{y},\mathcal {S}} = \left( \boldsymbol{y}^\top \boldsymbol{v}+ P(0), \{P(\textsf{id})\}_{\textsf{id}\in \mathcal {S}}\right)$. We assume the identity space is $\mathbb {Z}^*_p$, excluding 0 as a valid identity. Polynomial P is of degree d, and we assume the set $\mathcal {S}$ associated with each functional secret key is of size exactly d. We explain later how to remove this restriction. If $\textsf{id}^\star \!\notin \mathcal {S}$, we have the evaluation of the polynomial P on $d+1$ distinct points, so we can recover P(0) using Lagrange interpolation and get $\boldsymbol{y}^\top \boldsymbol{v}$, thanks to which we can obtain $\boldsymbol{x}^\top \boldsymbol{y}$. On the other hand, if $\textsf{id}^\star \!\in \mathcal {S}$, we only have the evaluation of P on d distinct points, which reveals no information about P(0), which completely masks $\boldsymbol{v}^\top \boldsymbol{y}$. Therefore, $\boldsymbol{v}$ masks $\boldsymbol{x}$ perfectly. To obtain an FE scheme with public-key encryption and security for many functional secret keys, we use standard techniques from pairing groups:

• instead of using the vector $\boldsymbol{v}$ and the polynomial P, the encryption uses $\llbracket \boldsymbol{v} \rrbracket _\textsf{1}$ and the coefficients of P in $\mathbb {G}_{\textsf{1}}$ that are part of $\textsf{pk}$ to compute:

  $$\textsf{ct}=(\llbracket \boldsymbol{x}+ \boldsymbol{v}r \rrbracket _\textsf{1}, \llbracket r P(\textsf{id}^\star ) \rrbracket _\textsf{1}) , \text { for } r \leftarrow _R\mathbb {Z}_p . $$

• to obtain security against collusions, we randomize the functional secret keys:

  $$\textsf{sk}_{\boldsymbol{y},\mathcal {S}} = (\llbracket \boldsymbol{y}^\top \boldsymbol{v}+ s P(0) \rrbracket _\textsf{2}, \{\llbracket s P(\textsf{id}) \rrbracket _\textsf{2}\}_{ \textsf{id}\in \mathcal {S}}) , \text { for }s \leftarrow _R\mathbb {Z}_p . $$

The scheme describe here would be secure in the generic group model. To accommodate for a security proof using the SXDH assumption (i.e. the assumption that DDH holds both in $\mathbb {G}_{\textsf{1}}$ and $\mathbb {G}_{\textsf{2}}$), we modify slightly the scheme using techniques reminiscent from the hash proof system from [CS02], similarly to [ALS16] in the context of functional encryption for inner-products.

Remark 1

(Impossibility of simulation secure FE). We consider an adversary playing against the many-ciphertexts simulation security of an identity-based FE scheme for inner-products, which makes $q_1$ functional secret key queries for random vectors $\llbracket \boldsymbol{y}_1 \rrbracket _\textsf{2},\ldots ,\llbracket \boldsymbol{y}_{q_1} \rrbracket _\textsf{2}$ and identities $\textsf{id}_1,\ldots ,\textsf{id}_{q_1}$. The adversary also chooses random vectors $\boldsymbol{x}_1,\ldots ,\boldsymbol{x}_{q_2}$ and identities $\textsf{id}^\star _1,\ldots ,\textsf{id}^\star _{q_2}$ for the challenge ciphertexts. The adversary chooses $\textsf{id}_1=\textsf{id}_2=\cdots = \textsf{id}_{q_1} = \textsf{id}^\star _1 = \cdots = \textsf{id}^\star _{q_2}$. The simulator must produce the challenge ciphertexts and the functional secret keys using only the values $\llbracket \boldsymbol{x}_i^\top \boldsymbol{y}_j \rrbracket _\textsf{t}$ and $\llbracket \boldsymbol{y}_j \rrbracket _\textsf{2}$ for $i=1,\ldots ,q_2$ and $j=1,\ldots ,q_1$, plus the identities. By the SXDH assumption (which we require for our MA-ABE), the $q_1 \cdot q_2$ values $\llbracket \boldsymbol{x}_i^\top \boldsymbol{y}_j \rrbracket _\textsf{t}$ are pseudo-random. The ciphertexts and functional secret keys, which are of total size $(q_1+q_2) \cdot \textsf{poly}(\lambda )$ must encode these values of total size $q_1 \cdot q_2 \cdot \textsf{poly}'(\lambda )$ where $\textsf{poly},\textsf{poly}'$ are polynomials, which is a contradiction. It is not clear how to bypass this impossibility result even in the random oracle model. In fact [AKW18] presents similar impossibility results for FE even in the random oracle model.

Related Works. [Kim19] builds a multi-authority ABE for all circuits from LWE for a slightly different notion that the GID model presented here (it can be seen as a relaxation of the GID model). In a recent work, [DKW21a] builds an MA-ABE for DNF formula from LWE, followed by [WWW22] that removed the use of random oracles. In [MJ18], the authors present a decentralized ABE, which is similar to an MA-ABE except the number of authorities of the system is fixed ahead of time, and each authority requires the public keys of the other authorities to generate its share of the user secret key. They realized this notion for the orthogonality-testing predicate (a.k.a. inner-product), which captures $NC_0$ circuits. Later on, [AYY22] extended their construction to partially hide the predicate in the user secret keys. In the same paper, they also presented a distributed ciphertext-policy ABE for $NC_1$, based on the LWE assumption and the bilinear generic group model. A distributed ABE is like an MA-ABE except the number of authorities is fixed ahead of time, and the adversary cannot create corrupted authorities with arbitrary public keys, but is instead restricted to (statically) recover the secret keys of honestly generated authorities. In [OT13], the authors build decentralized attribute-based signatures, which generalize the notion of ring signatures, by allowing a user whose attributes satisfy a predicate to sign a message with respect to the predicate. The validity of the signature implies that the signer has valid credentials, but the identity of the signer (or its attributes) remain hidden. As a side result, they also build a multi-authority ABE whose adaptive security is proven under the DLIN assumption in prime-order symmetric pairing groups in the random oracle model. Their scheme supports non-monotone access structures combined with inner-products. However, the security they prove does not handle corruptions of authorities. That is, in the security game, the adversary cannot get the secret key of a set of selected authorities, as is the case for others multi-authority ABE. In a paper concurrent to our work [DKW21b], the authors give the first MA-ABE for monotone span programs from the search variant of the Bilinear Diffie Hellman assumption. In their scheme, the size of the MSP, the number of attribute re-use and the size of the attribute universe of each authorities are all a-priori bounded. Their construction also inherits some of the practical deficiencies from prior schemes, namely, it uses symmetric pairings and the ciphertexts contain many target group elements. In [WFL19], the authors build an MA-ABE for bounded collusions (that is, where the number of possible user secret keys that can be corrupted is a priori bounded). Their construction also relies on inner-product FE but which are not identity-based nor handle revocation. They can be built from DDH (without pairing). The main different with our work lies in the unbounded-collusion security feature we achieve, which requires different techniques.

2 Preliminaries

2.1 Notations

We say a function $f: \mathbb {N}\rightarrow \mathbb {R}$ is negligible if f is asymptotically dominated by the inverse of any polynomial, i.e. for every polynomial $p \in \mathbb {R}[X]$, there exists $\lambda _p \in \mathbb {N}$ such that $|f(\lambda )|\le |1/p(\lambda )|$ for all $\lambda \ge \lambda _p$. We denote by $|\boldsymbol{v}|$ the length or dimension of vector $\boldsymbol{v}$ and by $v_i$ its i-th component. For any $n \in \mathbb {N}$, we denote $\{1,\ldots ,n\}$ by [n]. For any column vector $\boldsymbol{u}\in \mathbb {Z}^n$ and $\boldsymbol{v}\in \mathbb {Z}^m$, we denote by $(\boldsymbol{v},\boldsymbol{u}) \in \mathbb {Z}^{n+m}$ the column vector obtained by concatenating them. Given two matrices (or vectors) $\boldsymbol{A}\in \mathbb {Z}^{m_1 \times n_1}$ and $\boldsymbol{B}\in \mathbb {Z}^{m_2 \times n_2}$, we denote by $\boldsymbol{A}\otimes \boldsymbol{B}\in \mathbb {Z}^{m_1 m_2 \times n_1 n_2}$ their Kronecker product, aka. tensor product defined as follows. For all $i \in [m_1 m_2]$ and $j \in [n_1 n_2]$ which we can write $i= m_1 i_1 + i_2$ with $i_1 \in [m_2]$, $i_2 \in [m_2]$, $j= n_1 j_1 + j_2$ with $j_1 \in [n_2]$, $j_2 \in [n_2]$, the (i, j)’th coordinate of $\boldsymbol{A}\otimes \boldsymbol{B}$ is $a_{i_1,j_1} \cdot b_{i_2,j_2}$.

2.2 Lagrange Interpolation

Let p be a prime and $\mathbb {Z}_p[X]$ denotes the mono-variate polynomials over $\mathbb {Z}_p$. There exists an efficient deterministic algorithm $\textsf{Lagr}$ such that for all $P \in \mathbb {Z}_p[X]$ of degree d, given as input $d+1$ distinct values $x_1,\ldots ,x_{d+1} \in \mathbb {Z}_p\setminus \{0\}$, outputs $(\alpha _1,\ldots ,\alpha _{d+1}) = \textsf{Lagr}(x_1,\ldots ,\ldots ,x_{d+1})$ such that $\alpha _i \in \mathbb {Z}_p$ for all $i \in [d+1]$ and $P(0)=\sum _{i=1}^{d+1} \alpha _i P(x_i)$. The following fact states that when the evaluations of a polynomial P of degree d at only d or less distinct points (different from 0) are given, it is impossible to recover the value P(0), because it is statistically independent from the values at the other points. Fact 1. Let $d \in \mathbb {N}$, p be a prime, $x_1,\ldots ,x_d \in \mathbb {Z}_p\setminus \{0\}$ be d distinct values and P be a uniformly random polynomial over $\mathbb {Z}_p[X]$ of degree d. The value P(0) is statistically independent from $\{P(x_1),\ldots ,P(x_d)\}$.

2.3 Access Structure

We recall the definition of monotonic access structures using the language of monotonic span programs [KW93], which capture Boolean formulas. The set of all possible attributes used by an access structure is referred to as the attribute universe. Most of the prior works consider attribute universes of polynomial size (aka small universe) or at least attribute universe of finite size (aka large universe). Here we focus on unbounded attribute universe, where any bit string can serve as an attribute. This is the most advantageous setting in term of flexibility.We denote the set of all possible bit strings by $\{0,1\}^*$.

Definition 1

(Monotonic access structure [Bei96, KW93]). A monotonic access structure is a pair $(\boldsymbol{M},\rho )$ where $\boldsymbol{M}\in \mathbb {Z}_p^{n \times \ell }$ and $\rho : [\ell ] \rightarrow \{0,1\}^*$. The matrix $\boldsymbol{M}$ is used to generate shares as described in Fig. 1, and $\rho$ maps each share to its associated attribute. Given a set of attributes $\mathcal {S}\subseteq \{0,1\}^*$, we say that

$$\mathcal {S}\,satisfies\,(\boldsymbol{M},\rho )\,iff\,\boldsymbol{1} \in \textsf{Span}(\boldsymbol{M}_{\mathcal {S}}),$$

where $\boldsymbol{1} := (1,0,\ldots ,0) \in \mathbb {Z}^{n}$; $\boldsymbol{M}_{S}$ denotes the collection of vectors $\{ \boldsymbol{M}_j : \rho (j) \in \mathcal {S}\}$ where $\boldsymbol{M}_j$ denotes the j’th column of $\boldsymbol{M}$; and $\textsf{Span}$ refers to linear span of collection of vectors over $\mathbb {Z}_p$.

That is, $\mathcal {S}$ satisfies $(\boldsymbol{M},\rho )$ iff there exists constants $\omega _1,\ldots ,\omega _\ell \in \mathbb {Z}_p$ such that

$$\begin{aligned} \textstyle \sum _{ \rho (j) \in S } \omega _j \boldsymbol{M}_j = \boldsymbol{1} \end{aligned}$$

(1)

Observe that the constants $\{\omega _i\}$ can be computed in time polynomial in the size of the matrix $\boldsymbol{M}$ via Gaussian elimination.

Fig. 1.

Share generation algorithm. Here, $\boldsymbol{M}_j$ denotes the j-th column of $\boldsymbol{M}$. For each $j \in [\ell ]$, $\boldsymbol{a}_j$ is a share of the secret $\boldsymbol{a}\in \mathbb {Z}_p^d$.

Now we consider non-monotonic access structures, where $\rho$ maps each share to either an attribute or a negated attribute. A set of attribute $\mathcal {S}$ satisfies the non-monotonic access structure $(\boldsymbol{M},\rho )$ if given all the shares that correspond to an attribute in $\mathcal {S}$ or a negated attribute of the form $\lnot \textsf{att}$ where $\textsf{att}$ is not in $\mathcal {S}$, it is possible to recover the secret. For any set $\mathcal {S}\subseteq \{0,1\}^*$, we denote by $\{\lnot \} \cdot \mathcal {S}$ the set defined as $\{\lnot \textsf{att}\}_{\textsf{att}\in \mathcal {S}}$. The formal definition of a non-monotonic access structure is given below.

Definition 2

(Non-monotonic access structure [OSW07]). A non-monotonic access structure is a pair $(\boldsymbol{M},\rho )$ where $\boldsymbol{M}\in \mathbb {Z}_p^{n \times \ell }$ and $\rho : [\ell ] \rightarrow \{0,1\}^* \cup \left( \{\lnot \} \cdot \{0,1\}^*\right)$. The matrix $\boldsymbol{M}$ is used to generate shares as described in Fig. 1, and $\rho$ maps each share to its associated attribute in $\{0,1\}^*$ or negated attribute in $\{\lnot \} \cdot \{0,1\}^*$. Given a set of attributes $\mathcal {S}\subseteq \{0,1\}^*$, we say that

$$\mathcal {S}\,satisfies\,(\boldsymbol{M},\rho )\,iff\,\boldsymbol{1} \in \textsf{Span}(\boldsymbol{M}_{\mathcal {S}}),$$

where $\boldsymbol{1} := (1,0,\ldots ,0) \in \mathbb {Z}^{n}$; $\boldsymbol{M}_{S}$ denotes the collection of vectors $\{ \boldsymbol{M}_j : \rho (j) \in \mathcal {S}\ \text{ or } \ \rho (j)=\lnot \textsf{att}\ \text{ with } \ \textsf{att}\in \{0,1\}^* \setminus \mathcal {S}\}$, $\boldsymbol{M}_j$ denotes the j’th column of $\boldsymbol{M}$, and $\textsf{Span}$ refers to the linear span of a collection of (column) vectors over $\mathbb {Z}_p$.

For any set of attributes $\mathcal {S}_\textsf{corr}\subset \{0,1\}^*$, we say

$$\mathcal {S}\,satisfies\,(\boldsymbol{M},\rho )\,with\,corruptions\,\mathcal {S}_\textsf{corr}\,iff\,\boldsymbol{1} \in \textsf{Span}(\boldsymbol{M}_{\mathcal {S},\mathcal {S}_\textsf{corr}}),$$

where $\boldsymbol{1} := (1,0,\ldots ,0) \in \mathbb {Z}^{n}$; $\boldsymbol{M}_{S}$ denotes the collection of vectors $\{ \boldsymbol{M}_j : \rho (j) \in \mathcal {S}\cup \mathcal {S}_\textsf{corr}\ \text{ or } \ \rho (j)=\lnot \textsf{att}\ \text{ with } \ \textsf{att}\in \{0,1\}^* \setminus \mathcal {S}\}$, $\boldsymbol{M}_j$ denotes the j’th column of $\boldsymbol{M}$, and $\textsf{Span}$ refers to the linear span of a collection of (column) vectors over $\mathbb {Z}_p$.

That is, $\mathcal {S}$ satisfies $(\boldsymbol{M},\rho )$ iff there exists constants $\omega _1,\ldots ,\omega _\ell ,\omega '_1,\ldots ,\omega '_\ell \in \mathbb {Z}_p$ such that

$$\begin{aligned} \textstyle \sum _{ \rho (j) \in \mathcal {S}\cup \mathcal {S}_\textsf{corr}} \omega _j \boldsymbol{M}_j + \sum _{\rho (j)=\lnot \textsf{att}, \textsf{att}\notin \mathcal {S}} \omega '_j \boldsymbol{M}_j = \boldsymbol{1} \end{aligned}$$

(2)

Observe that the constants $\{\omega _i,\omega '_i\}$ can be computed in time polynomial in the size of the matrix $\boldsymbol{M}$ via Gaussian elimination. Now we recall a useful fact about access structures represented by span programs.

Lemma 1

([KW93]). Let $(\boldsymbol{M},\rho )$ be a non-monotonic access structure where $\boldsymbol{M}\in \mathbb {Z}_p^{n \times \ell }$. For all sets $\mathcal {S},\mathcal {S}_\textsf{corr}\subseteq \{0,1\}^*$ such that $\mathcal {S}$ does do not satisfy $(\boldsymbol{M},\rho )$ with corruptions $\mathcal {S}_\textsf{corr}$, there exists a vector $\boldsymbol{w}_{\mathcal {S}} \in \mathbb {Z}_p^{\ell -1}$ such that $(1,\boldsymbol{w})^\top \boldsymbol{M}_j=0$ for all $j \in [\ell ]$ such that $\rho (j) \in \mathcal {S}\cup \mathcal {S}_\textsf{corr}$ or $\rho (j) = \lnot \textsf{att}$ with $\textsf{att}\in \{0,1\}^* \setminus \mathcal {S}$.

2.4 Pairing Groups

Let $\textsf{GGen}$ be a PPT algorithm that on input the security parameter $1^\lambda$, outputs a description $\mathcal{P}\mathcal{G}=(p, \mathbb {G}_{\textsf{1}}, \mathbb {G}_{\textsf{2}}, P_{\textsf{1}}, P_{\textsf{2}}, \mathbb {G}_{\textsf{t}}, e)$ of pairing groups where $\mathbb {G}_{\textsf{1}}, \mathbb {G}_{\textsf{2}}$ and $\mathbb {G}_{\textsf{t}}$ are cyclic groups of order p for a $2\lambda$-bit prime p; $P_{\textsf{1}}$ and $P_{\textsf{2}}$ are generators of $\mathbb {G}_{\textsf{1}}$ and $\mathbb {G}_{\textsf{2}}$ respectively and $e : \mathbb {G}_{\textsf{1}}\times \mathbb {G}_{\textsf{2}}\rightarrow \mathbb {G}_{\textsf{t}}$ is an efficiently computable (non-degenerate) bilinear map, thus $P_{\texttt {t}} {:}{=}e(P_{\textsf{1}},P_{\textsf{2}})$ generates $\mathbb {G}_{\textsf{t}}$.

We use implicit representation of group elements. For $s \in \{\textsf{1},\textsf{2},\textsf{t}\}$ and $a \in \mathbb {Z}_p$, define $\llbracket a \rrbracket _s = a \cdot P_s \in \mathbb {G}_s$ as the implicit representation of a in $\mathbb {G}_s$. More generally, for a matrix $\boldsymbol{A}= (a_{ij}) \in \mathbb {Z}_p^{n\times m}$ we define $\llbracket \boldsymbol{A}\rrbracket _s$ as the implicit representation of $\boldsymbol{A}$ in $\mathbb {G}_s$:

$$\begin{aligned} \llbracket \boldsymbol{A}\rrbracket _s := \begin{pmatrix} a_{11} \cdot P_s &{} ... &{} a_{1m}\cdot P_s\\ &{} &{} \\ a_{n1}\cdot P_s&{} ... &{} a_{nm} \cdot P_s \end{pmatrix} \in \mathbb {G}_s^{n \times m}. \end{aligned}$$

Given $\llbracket a \rrbracket _\textsf{1}$ and $\llbracket b \rrbracket _\textsf{2}$, one can efficiently compute $\llbracket a \cdot b \rrbracket _\textsf{t}$ using the pairing e. For matrices $\boldsymbol{A}$ and $\boldsymbol{B}$ of matching dimensions, define $e(\llbracket \boldsymbol{A} \rrbracket _\textsf{1}, \llbracket \boldsymbol{B} \rrbracket _\textsf{2}) := \llbracket \boldsymbol{A}\boldsymbol{B} \rrbracket _\textsf{t}$. For any matrix $\boldsymbol{A}, \boldsymbol{B}\in \mathbb {Z}_p^{n \times m}$, any group $s \in \{\textsf{1},\textsf{2},\textsf{t}\}$, we denote by $\llbracket \boldsymbol{A}\rrbracket _s + \llbracket \boldsymbol{B}\rrbracket _s = \llbracket \boldsymbol{A}+\boldsymbol{B}\rrbracket _s$.

Definition 3

(DDH assumption). For any adversary $\mathcal {A}$, any group $s \in \{\textsf{1},\textsf{2},\textsf{t}\}$ and any security parameter $\lambda$, let

$$\begin{aligned} \textsf{Adv}^{\textsf{DDH}}_{\mathbb {G}_s,\mathcal {A}}(\lambda ) := |\Pr [1 \leftarrow \mathcal {A}(\mathcal{P}\mathcal{G},\llbracket \boldsymbol{a}\rrbracket _s,\llbracket \boldsymbol{a}r\rrbracket _s)] - \Pr [1 \leftarrow \mathcal {A}(\mathcal{P}\mathcal{G},\llbracket \boldsymbol{a}\rrbracket _s,\llbracket \boldsymbol{u}\rrbracket _s)]|, \end{aligned}$$

where the probabilities are taken over $\mathcal{P}\mathcal{G}\leftarrow _R\textsf{GGen}(1^\lambda ,d)$, $\boldsymbol{a} \leftarrow _R\mathbb {Z}_p^2$, $r \leftarrow _R\mathbb {Z}_p$, $\boldsymbol{u}\leftarrow _R\mathbb {Z}_p^2$, and the random coins of $\mathcal {A}$. We say DDH holds in $\mathbb {G}_s$ if for all PPT adversaries $\mathcal {A}$, $\textsf{Adv}^{\textsf{DDH}}_{\mathbb {G}_s,\mathcal {A}}(\lambda )$ is a negligible function of $\lambda$.

Definition 4

(SXDH assumption). For any security parameter $\lambda$ and any pairing group $\mathcal{P}\mathcal{G}=(\mathbb {G}_1,\mathbb {G}_2,\mathbb {G}_T,p,P_1,P_2,e) \leftarrow _R\textsf{GGen}(1^\lambda )$, we say SXDH holds in $\mathcal{P}\mathcal{G}$ if DDH holds in $\mathbb {G}_1$ and $\mathbb {G}_2$.

It is well known that the DDH and SXDH assumptions are equivalent when the dimensions of the vectors are larger than 2 (for any polynomially large dimensions).

2.5 Functional Encryption

We recall the notion of functional encryption originally given in [BSW11]. Let $\mathcal {F}= \{\mathcal {F}_\lambda \}_{\lambda \in \mathbb {N}}$ be a family of sets, where for each $\lambda \in \mathbb {N}$, $\mathcal {F}_\lambda$ is a set of functions from the message space $\mathcal {X}_\lambda$ to the output space $\mathcal {Y}_\lambda$. A functional encryption scheme for $\mathcal {F}$ consists of the following PPT algorithms.

• $\textsf{Setup}(1^\lambda )\rightarrow (\textsf{msk}, \textsf{pk})$. On input the global parameters $\textsf{gp}$, it outputs a master secret key $\textsf{msk}$ and a public key $\textsf{pk}$. The public key is (sometimes implicitly) input to all other algorithms.

• $\textsf{Enc}(\textsf{pk},m) \rightarrow \textsf{ct}$. On input the public key $\textsf{pk}$ and a message $m \in \mathcal {X}_\lambda$, it outputs a ciphertext $\textsf{ct}$.

• $\textsf{KeyGen}(\textsf{msk},f) \rightarrow \textsf{sk}_f$. On input the master secret key $\textsf{msk}$ and a function $f \in \mathcal {F}_\lambda$, it outputs a functional secret key $\textsf{sk}_f$, which includes the description of the function f.

• $\textsf{Dec}(\textsf{pk},\textsf{ct},\textsf{sk}_f) \rightarrow m$. On input the public key $\textsf{pk}$, a ciphertext $\textsf{ct}$ and a functional secret key $\textsf{sk}_f$, the decryption algorithm deterministically outputs a value $\mu \in \mathcal {Y}_\lambda$ (or a special rejection symbol if it fails to decrypt).

Correctness. For all $\lambda \in \mathbb {N}$, all $(\textsf{pk},\textsf{msk})$ in the support of $\textsf{Setup}(1^\lambda )$, all messages $m \in \mathcal {X}_\lambda$ and all functions $f \in \mathcal {F}_\lambda$, we have

$$\begin{aligned} \Pr [\textsf{Dec}(\textsf{pk},\textsf{Enc}(\textsf{pk},m),\textsf{KeyGen}(\textsf{msk},f))=f(m)]=1, \end{aligned}$$

where the probability is taken over the random coins of $\textsf{Enc}$ and $\textsf{KeyGen}$.

We now describe the indistinguishability-based security notion for FE.

Adaptive Security. Given an FE scheme denoted by $\textsf{FE}$ for $\mathcal {F}$, for any adversary $\mathcal {A}$ and security parameter $\lambda$, we define the advantage function:

$$ \textsf{Adv}^{\textsf{FE}}_{\mathcal {A}}(\lambda )\,{:}{=}\, \left| \Pr \left[ \begin{array}{rl} (\textsf{pk},\textsf{msk}) &{} \leftarrow \textsf{Setup}(1^\lambda )\\ (m_0,m_1,\textsf{st}) &{} \leftarrow \mathcal {A}^{\mathcal {O}_{\textsf{KeyGen}}(\cdot )}(\textsf{pk}) \\ \beta &{} \leftarrow _R\{0,1\}\\ \textsf{ct}^\star &{} \leftarrow \textsf{Enc}(\textsf{pk},m_\beta )\\ \beta ' &{} \leftarrow \mathcal {A}^{\mathcal {O}_{\textsf{KeyGen}}(\cdot )}(\textsf{ct}^\star ,\textsf{st}) \end{array} \!\!\! : \, \beta ' = \beta \right] - \frac{1}{2} \right| , $$

where the oracle $\mathcal {O}_{\textsf{KeyGen}}$, when given as input a function $f \in \mathcal {F}_\lambda$, returns $\textsf{KeyGen}(\textsf{msk},f)$ and $\textsf{st}$ denotes the state of the adversary $\mathcal {A}$. We say the adversary $\mathcal {A}$ is admissible if for all functions $f \in \mathcal {F}_\lambda$ queried to $\mathcal {O}_\textsf{KeyGen}$, it holds that $f(m_0)=f(m_1)$. An FE scheme $\textsf{FE}$ is said to be IND-secure if for all PPT admissible adversaries $\mathcal {A}$, $\textsf{Adv}_{\mathcal {A}}^{\textsf{FE}}$ is negligible.

Selective, Super-Selective Security. In the security game above, we say an adversary is selective if it chooses a pair of messages $(m_0,m_1)$ before querying any functional secret key to $\mathcal {O}_\textsf{KeyGen}$. An adversary is said to be super-selective if it is selective and it chooses the queries to $\mathcal {O}_\textsf{KeyGen}$ independently of the challenge ciphertext $\textsf{ct}^\star$. That is, an FE scheme $\textsf{FE}$ is said to be super-selective if for all admissible PPT adversaries $\mathcal {A}$, the function $\textsf{Adv}^{\textsf{ssel}\text{- }\textsf{FE}}_{\mathcal {A}}$ is negligible, where $\textsf{Adv}^{\textsf{ssel}\text{- }\textsf{FE}}_{\mathcal {A}}$ is defined for all $\lambda \in \mathbb {N}$ as follows:

$$ \textsf{Adv}^{\textsf{ssel}\text{- }\textsf{FE}}_{\mathcal {A}}(\lambda )\,{:}{=}\, \left| \Pr \left[ \begin{array}{rl} (\textsf{pk},\textsf{msk}) &{} \leftarrow \textsf{Setup}(1^\lambda )\\ (m_0,m_1,\textsf{st}) &{} \leftarrow \mathcal {A}(\textsf{pk}) \\ \textsf{st}' &{} \leftarrow \mathcal {A}(\textsf{st})^{\mathcal {O}_{\textsf{KeyGen}}(\cdot )} \\ \beta &{} \leftarrow _R\{0,1\}\\ \textsf{ct}^\star &{} \leftarrow \textsf{Enc}(\textsf{pk},m_\beta )\\ \beta ' &{} \leftarrow \mathcal {A}(\textsf{ct}^\star ,\textsf{st}') \end{array} \!\!\! : \, \beta ' = \beta \right] - \frac{1}{2} \right| , $$

where the oracle $\mathcal {O}_{\textsf{KeyGen}}$, when given as input a function $f \in \mathcal {F}_\lambda$, returns $\textsf{KeyGen}(\textsf{msk},f)$ and $\textsf{st}$, $\textsf{st}'$s denote the states of the adversary $\mathcal {A}$. As for the IND-security above, we say the adversary $\mathcal {A}$ is admissible if for all functions $f \in \mathcal {F}_\lambda$ queried to $\mathcal {O}_\textsf{KeyGen}$, it holds that $f(m_0)=f(m_1)$.

2.6 Definition of Multi-authority ABE

We recall the definition of multi-authority ABE from [LW11]. We assume every authority is identified by a public key. For every authority $\textsf{pk}$, we denote by $\mathcal {U}_\textsf{pk}$ the associated attribute universe. Without loss of generality, we assume that attribute universes are disjoint for different authorities.

We consider access structures $(\boldsymbol{M},\rho )$ where $\boldsymbol{M}\in \mathbb {Z}_p^{n \times \ell }$, and $\rho$ maps each row $j \in [\ell ]$ to an attribute in $\mathcal {U}_{\theta (j)}$, where $\theta$ maps a row $j \in [\ell ]$ to the authority who owns the attribute $\rho (j)$. To keep notations simple, we assume the map $\theta$ is implicitly part of the description of the access structure.

Definition. A MA-ABE scheme consists of the following PPT algorithms:

• $\textsf{GlobalSetup}(1^\lambda )\,{\rightarrow }\,\textsf{gp}$. On input the security parameter, it outputs global parameters, which are input to all other algorithms (usually implicitly).

• $\textsf{AuthSetup}(\textsf{gp}) \,{\rightarrow }\,(\textsf{pk},\textsf{sk})$. Each authority runs a setup procedure to generate its own pair of keys. The public key serves as a univocal identifier for the authority, which is associated with an attribute universe denoted by $\mathcal {U}_\textsf{pk}$.

• $\textsf{Enc}(\boldsymbol{M},\rho ,\varPi ) \,{\rightarrow }\,(\textsf{ct},\kappa )$. On input an access structure $\boldsymbol{M}\in \mathbb {Z}_p^{n \times \ell }$, $\rho : [\ell ] \rightarrow \{0,1\}^*$ and a set of authorities $\varPi$ such that for all columns $j\in [\ell ]$, we have $\theta (j) \in \varPi$, the encryption algorithm outputs a ciphertext $\textsf{ct}$ and a symmetric encryption key $\kappa \in \mathcal {K}$. The ciphertext implicitly contains a description of the access structure $(\boldsymbol{M},\rho )$.

• $\textsf{KeyGen}(\textsf{pk},\textsf{sk},\textsf{gid},\mathcal {S})\,{\rightarrow }\,\textsf{sk}_{\textsf{gid},\mathcal {S}}$. On input an authority’s public key $\textsf{pk}$ and the corresponding secret key $\textsf{sk}$, a global identifier $\textsf{gid}$ and a set of attribute $\mathcal {S}\subset \mathcal {U}_\textsf{pk}$, the key generation algorithm outputs a user secret key $\textsf{sk}_{\textsf{gid},\mathcal {S}}$, which implicitly contains a description of $\textsf{gid}$ and $\mathcal {S}$.

• $\textsf{Dec}(\textsf{ct},\{\textsf{sk}_{\textsf{gid},\mathcal {S}_i}\}_i) \,{\rightarrow }\,\kappa /\bot$. On input a ciphertext $\textsf{ct}$ and a set of user secret keys $\{\textsf{sk}_{\textsf{gid},\mathcal {S}_i}\}_i$ created for the same global identifier, the decryption algorithm deterministically outputs a symmetric key $\kappa$ or $\bot$.

Correctness. For all $\lambda \in \mathbb {N}$, all $\textsf{gp}$ in the support of $\textsf{GlobalSetup}(1^\lambda )$, all $\nu \in \mathbb {N}$, all $(\textsf{pk}_1,\textsf{sk}_1),\cdots ,(\textsf{pk}_\nu ,\textsf{sk}_\nu )$ in the support of $\textsf{Setup}(\textsf{gp})$, all access structures $(\boldsymbol{M},\rho )$ associated with the set of authorities $\varPi =\{\textsf{pk}_1,\ldots ,\textsf{pk}_\nu \}$, all pairs $(\textsf{ct},\kappa )$ in the support of $\textsf{Enc}(\boldsymbol{M},\rho ,\varPi )$, all sets of attributes $\mathcal {S}_i \subset \mathcal {U}_{\textsf{pk}_i}$ for all $i \in [\nu ]$ such that $\mathcal {S}=\cup _{i \in [\nu ]} \mathcal {S}_i$ satisfies $(\boldsymbol{M},\rho )$ and all global identifiers $\textsf{gid}\in \{0,1\}^*$:

$$ \Pr \left[ \textsf{Dec}(\textsf{ct},\{\textsf{sk}_{\textsf{gid},\mathcal {S}_i}\}_{i \in [\nu ]}) = \kappa \right] = 1 , $$

where the probability is taken over $\textsf{sk}_{\textsf{gid},\mathcal {S}_i} \leftarrow \textsf{KeyGen}(\textsf{pk}_i,\textsf{sk}_i,\textsf{gid},\mathcal {S}_i)$ for all $i \in [\nu ]$.

Adaptive Security. Given a multi-authority ABE denoted by $\textsf{ABE}$, for any stateful adversary $\mathcal {A}$ and security parameter $\lambda$, we define the advantage function:

$$\begin{aligned}&\textsf{Adv}^{\textsf{ABE}}_{\mathcal {A}}(\lambda )\,{:}{=}\\&\qquad \left| \Pr \left[ \begin{array}{rl} \textsf{gp}&{} \leftarrow \textsf{GlobalSetup}(1^\lambda )\\ (\boldsymbol{M},\rho ,\varPi _\textsf{hon},\varPi _\textsf{corr}) &{} \leftarrow \mathcal {A}^{\mathcal {O}_{\textsf{create}},\mathcal {O}_{\textsf{corr}}(\cdot ),\mathcal {O}_{\textsf{KeyGen}}(\cdot ,\cdot ,\cdot )}(\textsf{gp}) \\ (\textsf{ct}^\star ,\kappa ) &{} \leftarrow \textsf{Enc}(\boldsymbol{M},\rho ,\varPi )\\ \beta &{} \leftarrow _R\{0,1\};\, K_0\,{:}{=}\,\kappa ;\, K_1 \leftarrow _R\mathcal {K}\\ \beta ' &{} \leftarrow \mathcal {A}^{\mathcal {O}_{\textsf{corr}}(\cdot ),\mathcal {O}_{\textsf{KeyGen}}(\cdot ,\cdot ,\cdot )}(\textsf{ct}^\star ,K_\beta ) \end{array} \!\!\! : \, \beta ' = \beta \right] - \frac{1}{2} \right| . \end{aligned}$$

The oracles are defined as follows:

• $\mathcal {O}_{\textsf{create}}$: runs $(\textsf{pk}, \textsf{sk}) \leftarrow \textsf{AuthSetup}(\textsf{gp})$, adds $\textsf{pk}$ to the sets of honest authorities denoted by $\mathcal {S}_{\textsf{hon}}$ (initially empty) and returns $\textsf{pk}$.

• $\mathcal {O}_{\textsf{corr}}(\textsf{pk})$: if $\textsf{pk}\in \mathcal {S}_{\textsf{hon}}$, it returns the associated secret key $\textsf{sk}$ and removes $\textsf{pk}$ from $\mathcal {S}_{\textsf{hon}}$.

• $\mathcal {O}_{\textsf{KeyGen}}(\textsf{pk},\textsf{gid},\mathcal {S})$: if $\textsf{pk}\in \mathcal {S}_{\textsf{hon}}$ and $\mathcal {S}\subset \mathcal {U}_\textsf{pk}$, it returns $\textsf{KeyGen}(\textsf{pk},\textsf{sk},\textsf{gid},\mathcal {S})$ where $\textsf{sk}$ is the secret key associated with $\textsf{pk}$; otherwise, it returns $\bot$. This oracle can be queried at most once per $(\textsf{pk},\textsf{gid})$ pair. That is, there cannot be two queries of the form $(\textsf{pk},\textsf{gid},\mathcal {S})$ and $(\textsf{pk},\textsf{gid},\mathcal {S}')$ for different $\mathcal {S}\ne \mathcal {S}'$ to $\mathcal {O}_{\textsf{KeyGen}}$. This restriction is necessary for non-monotonic access structure (see Remark 2).

The adversary $\mathcal {A}$ outputs an access structure $(\boldsymbol{M},\rho )$ with respect to the authorities $\varPi = \varPi _\textsf{hon}\cup \varPi _\textsf{corr}$, where $\varPi _\textsf{hon}$ denotes the set of honest authorities, that is, which have been created via $\mathcal {O}_{\textsf{create}}$, and which have not been queried to $\mathcal {O}_{\textsf{corr}}$ (they can still be queried to $\mathcal {O}_{\textsf{corr}}$ later on), whereas $\varPi _\textsf{corr}$ denotes the set of corrupted authorities, that is, authorities created via $\mathcal {O}_{\textsf{create}}$ that have been subsequently queried to $\mathcal {O}_{\textsf{corr}}$, or authorities whose public keys were maliciously created by the adversary $\mathcal {A}$ himself. We require that $\varPi _\textsf{corr}$ contains not only the public keys of the corrupted authorities, but also their associated secret keys¹.

We denote by $\mathcal {Q}_{\textsf{KeyGen}}$ the set of queries to $\mathcal {O}_{\textsf{KeyGen}}$, $\mathcal {S}_\textsf{hon}\subseteq \varPi _\textsf{hon}$ the set of authorities in $\varPi _\textsf{hon}$ that are still honest at the end of the experiment, $\mathcal {S}_{\textsf{corr}} = \varPi _\textsf{corr}\cup \varPi _\textsf{hon}\setminus \mathcal {S}_{\textsf{hon}}$, $\varSigma _\textsf{corr}= \cup _{\textsf{pk}\in \mathcal {S}_{\textsf{corr}}} \mathcal {U}_\textsf{pk}$, and for every global identifier $\textsf{gid}\in \{0,1\}^*$, $\mathcal {S}_{\textsf{gid}} = \cup _{\textsf{pk}\in \mathcal {S}_{\textsf{hon}}, (\textsf{pk},\textsf{gid},\mathcal {S}) \in \mathcal {Q}_{\textsf{KeyGen}}} \mathcal {S}$. We say the adversary $\mathcal {A}$ is admissible if for all $\textsf{gid}\in \{0,1\}^*$, $\mathcal {S}_{\textsf{gid}}$ does not satisfy $(\boldsymbol{M},\rho )$ with corruptions $\varSigma _\textsf{corr}$ (as per Definition 1). We say $\textsf{ABE}$ is adaptively secure if for all PPT admissible adversaries $\mathcal {A}$, there exists a negligible function $\nu$ such that for all $\lambda \in \mathbb {N}$, $\textsf{Adv}^{\textsf{ABE}}_{\mathcal {A}}(\lambda ) \le \nu (\lambda )$.

Static Corruptions. We say an ABE is secure with static corruptions if the adversary does not have access to the oracle $\mathcal {O}_{\textsf{corr}}$. He can still create authorities maliciously as part of $\varPi _\textsf{corr}$, but all authorities created by $\mathcal {O}_{\textsf{create}}$ remain honest throughout the experiment.

Selective, Super-Selective Security. In the security game above, we say an adversary is selective if it chooses the tuple $(\boldsymbol{M},\rho ,\varPi _\textsf{corr},\varPi _\textsf{hon})$ before querying any user secret key to $\mathcal {O}_\textsf{KeyGen}$. An adversary is said to be super-selective if it is selective and it chooses the queries to $\mathcal {O}_\textsf{KeyGen}$ independently of the challenge ciphertext $\textsf{ct}^\star$. That is, an MA-ABE scheme $\textsf{ABE}$ is said to be super-selective if for all admissible PPT adversaries $\mathcal {A}$, the function $\textsf{Adv}^{\textsf{ssel}\text{- }\textsf{ABE}}_{\mathcal {A}}$ is negligible, where $\textsf{Adv}^{\textsf{ssel}\text{- }\textsf{ABE}}_{\mathcal {A}}$ is defined for all $\lambda \in \mathbb {N}$ as follows:

$$\begin{aligned}&\textsf{Adv}^{\textsf{ABE}}_{\mathcal {A}}(\lambda )\,{:}{=}\\&\qquad \left| \Pr \left[ \begin{array}{rl} \textsf{gp}&{} \leftarrow \textsf{GlobalSetup}(1^\lambda )\\ (\boldsymbol{M},\rho ,\varPi _\textsf{hon},\varPi _\textsf{corr},\textsf{st}) &{} \leftarrow \mathcal {A}^{\mathcal {O}_{\textsf{create}},\mathcal {O}_{\textsf{corr}}(\cdot )}(\textsf{gp}) \\ \textsf{st}' &{} \leftarrow \mathcal {A}^{\mathcal {O}_{\textsf{corr}}(\cdot ),\mathcal {O}_{\textsf{KeyGen}}(\cdot ,\cdot ,\cdot )}(\textsf{st})\\ (\textsf{ct}^\star ,\kappa ) &{} \leftarrow \textsf{Enc}(\boldsymbol{M},\rho ,\varPi )\\ \beta &{} \leftarrow _R\{0,1\};\, K_0\,{:}{=}\,\kappa ;\, K_1 \leftarrow _R\mathcal {K}\\ \beta ' &{} \leftarrow \mathcal {A}^{\mathcal {O}_{\textsf{corr}}(\cdot )}(\textsf{ct}^\star ,K_\beta ,\textsf{st}') \end{array} \!\!\! : \, \beta ' = \beta \right] - \frac{1}{2} \right| . \end{aligned}$$

where the oracles are defined as above, and $\textsf{st}$, $\textsf{st}'$ denote the states of the adversary $\mathcal {A}$.

Remark 2

(At most one user secret key query per $\textsf{gid}$). In the definitions above, we restrict the adversary to query the oracle $\mathcal {O}_{\textsf{KeyGen}}$ at most once per $(\textsf{pk},\textsf{gid})$ pair . This restriction is necessary when considering non-monotone access structure. In fact, security relies on the fact that users only obtain user secret keys associated to the set of all attributes they possess. Giving the adversary access to at most one query to $\mathcal {O}_{\textsf{KeyGen}}$ per $(\textsf{pk},\textsf{gid})$ is one way to ensure this is the case.

For instance, suppose a user Alice possesses the attributes $\textsf{att}_1$ and $\textsf{att}_2$ that are owned by an authority. Alice should not be able to obtain user secret keys associated to strict subsets of $\{\textsf{att}_1,\textsf{att}_2\}$. If for example she obtains a user secret key for $\{\textsf{att}_1\}$, she would be able to decrypt a ciphertext associated with an access structure excluding users possessing $\textsf{att}_2$.

Remark 3

(Stronger security via ZK-AoK). In the security definition above, we require the adversary to provide not only the public keys, but also the secret keys of all the authorities in $\varPi _\textsf{corr}$. It is possible to lift this restriction, and thereby strengthen the security definition, using standard techniques involving Zero-Knowledge Argument of Knowledge (ZK-AoK). Any authority must publish not only a public key, but also an argument of knowledge of the associated secret key. The zero-knowledge property ensures that nothing is revealed about the secret key, and the argument of knowledge property forces the issuer to know the associated secret key. This way, the adversary must know the secret key associated to any authority it creates maliciously, since it has to provide an argument of knowledge. Note that in our ABE constructions we use a ZK-AoK for a very simple language that admits an efficient sigma protocol, that can be made non-interactive with the Fiat-Shamir heuristic. Consequently, strengthening the security comes at a modest efficiency cost. In the rest of this paper, we focus on the weaker security definition, which is easier to prove.

3 Inner-Product FE

3.1 Identity-Based Inner-product FE

We recall the definition of Identity-Based Inner-Product Functional Encryption (ID-IPFE) which is a particular case of Functional Encryption where the family $\mathcal {F}=\{\mathcal {F}_\lambda \}_{\lambda \in \mathbb {N}}$ is as follows. Let d be a polynomial and $\textsf{GGen}$ a pairing group generator. For every $\lambda \in \mathbb {N}$, the set of functions $\mathcal {F}_\lambda$ is associated with a pairing group $(p, \mathbb {G}_{\textsf{1}}, \mathbb {G}_{\textsf{2}}, P_{\textsf{1}}, P_{\textsf{2}}, \mathbb {G}_{\textsf{t}}, e) = \textsf{GGen}(1^\lambda )$, where p is a prime which denotes the order of the groups $\mathbb {G}_{\textsf{1}}, \mathbb {G}_{\textsf{2}}$, and $\mathbb {G}_{\textsf{t}}$. We assume the pairing group $\mathcal{P}\mathcal{G}$ is given as input of the setup algorithm. The message space $\mathcal {X}_\lambda = \mathbb {Z}_p^{d(\lambda )} \times \mathbb {Z}_p$. That is, every message is of the form $(\boldsymbol{x},\textsf{id})$, where $\boldsymbol{x}\in \mathbb {Z}_p^{d(\lambda )}$ is referred to as the message vector, and $\textsf{id}\in \mathbb {Z}_p$ is referred to as the identity. The function space $\mathcal {F}_\lambda = \mathbb {G}_{\textsf{2}}^{d(\lambda )} \times \mathbb {Z}_p$. Every function is of the form $(\llbracket \boldsymbol{y} \rrbracket _\textsf{2},\textsf{id}')$ where $\llbracket \boldsymbol{y} \rrbracket _\textsf{2} \in \mathbb {G}_{\textsf{2}}^{d(\lambda )}$ and $\textsf{id}' \in \mathbb {Z}_p$. Decryption recovers the inner product $\llbracket \boldsymbol{x}^\top \boldsymbol{y} \rrbracket _\textsf{t} \in \mathbb {G}_{\textsf{t}}$ when $\textsf{id}=\textsf{id}'$. When $\textsf{id}'\ne \textsf{id}$, the vector $\boldsymbol{x}$ remains hidden. In both cases, the vector $\llbracket \boldsymbol{y} \rrbracket _\textsf{2}$ and the identities $\textsf{id}$ and $\textsf{id}'$ are revealed.

In [DP19, TT18], the authors give an unbounded variant of the related family where functions are of the form $(\boldsymbol{y},\textsf{id}) \in \mathbb {Z}_p^{d(\lambda )} \times \mathbb {Z}_p$, that is, the vector $\boldsymbol{y}$ needs to be known in $\mathbb {Z}_p^{d(\lambda )}$ instead of $\mathbb {G}_{\textsf{2}}^{d(\lambda )}$. In our MA-ABE that uses the ID-IPFE as a building block, the party generating the functional secret keys only know the value $\llbracket \boldsymbol{y} \rrbracket _\textsf{2} \in \mathbb {G}_{\textsf{2}}^{d(\lambda )}$, which prevents us from using their scheme. In [ACGU20], the authors present an ID-IPFE for the functions described above (where $\mathcal {F}_\lambda = \mathbb {G}_{\textsf{2}}^{d(\lambda )} \times \mathbb {Z}_p$) which is selectively secure under the SXDH assumption. They also present an adaptively secure construction but only for the messages $(\boldsymbol{x},\textsf{id})$ and functions $(\llbracket \boldsymbol{y} \rrbracket _\textsf{2},\textsf{id}')$ such that $\boldsymbol{x}^\top \boldsymbol{y}$ is small (i.e. lies in a set of polynomial size), which is not the case for our application. Indeed the value of the inner product $\llbracket \boldsymbol{x}^\top \boldsymbol{y} \rrbracket _\textsf{t}$ in our case will be well-spread in the full group $\mathbb {G}_{\textsf{t}}$. This prevents from using the adaptively secure scheme from [ACGU20]. It is an open problem to build an adaptively secure ID-IPFE for large values.

3.2 Inner-Product FE with Revocations

Here we consider a Functional Encryption scheme for the family $\mathcal {F}=\{\mathcal {F}_\lambda \}_{\lambda \in \mathbb {N}}$ where for all $\lambda \in \mathbb {N}$, $\mathcal {X}_\lambda = \mathbb {Z}_p^{d(\lambda )} \times \mathbb {Z}_p$, $\mathcal {F}_\lambda =\mathbb {G}_{\textsf{2}}^{d(\lambda )} \times \mathcal {S}_t$, $\mathcal {S}_t$ denotes all the sets of size t included in $\mathbb {Z}_p$, and p is a prime which denotes the order of a pairing group $\mathcal{P}\mathcal{G}=(p, \mathbb {G}_{\textsf{1}}, \mathbb {G}_{\textsf{2}}, P_{\textsf{1}}, P_{\textsf{2}}, \mathbb {G}_{\textsf{t}}, e)$. We assume the pairing group $\mathcal{P}\mathcal{G}$ is given as input of the setup algorithm. For every message of the form $(\boldsymbol{x},\textsf{id})$ where $\boldsymbol{x}\in \mathbb {Z}_p^{d(\lambda )}$ and $\textsf{id}\in \mathbb {Z}_p$, and every function of the form $(\llbracket \boldsymbol{y} \rrbracket _\textsf{2},\mathcal {S})$ where $\mathcal {S}\subset \mathbb {Z}_p$ is of size t, decryption recovers $\llbracket \boldsymbol{x}^\top \boldsymbol{y} \rrbracket _\textsf{t}$ when $\textsf{id}\notin \mathcal {S}$. When $\textsf{id}\in \mathcal {S}$, then the vector $\boldsymbol{x}$ remains hidden. In both cases, the identity $\textsf{id}$, the set $\mathcal {S}$ and the vector $\llbracket \boldsymbol{y} \rrbracket _\textsf{2}$ are revealed. Note that the set $\mathcal {S}$ associated to each functional secret key is required to be of size exactly t. We argue in Sect. 3.3 how to remove this restriction and have sets of size at most t. We now give the first construction of such an FE scheme, whose selective security we prove under SXDH. It is described in Fig. 2. It makes use of Lagrange interpolation, described in Sect. 2.2.

Fig. 2.

Inner-product FE with revocations for d-dimensional vectors and sets of size t. Its selective security is proven under SXDH. The algorithm $\textsf{Lagr}$ is described in Sect. 2.2.

Correctness. Since $\textsf{id}\notin \mathcal {S}$, we can use the correctness of the algorithm $\textsf{Lagr}$, which states that: $\prod _{j\in [t+1]}\llbracket \gamma _j \rrbracket _\textsf{t}^{\alpha _j} = \llbracket s \boldsymbol{b}^\top \boldsymbol{P}(0) \boldsymbol{a}r \rrbracket _\textsf{t}$. Thus, the decryption computes:

$$\begin{aligned}&e(\llbracket \boldsymbol{c}_2^\top \rrbracket _\textsf{1},\llbracket \boldsymbol{y} \rrbracket _\textsf{2})\cdot \prod _{j \in [t+1]} \llbracket \gamma _j \rrbracket _\textsf{t}^{\alpha _j} \,/\, e(\llbracket c_1 \rrbracket _\textsf{1},\llbracket k_2 \rrbracket _\textsf{2}) \\ =&\llbracket (\boldsymbol{x}+ \boldsymbol{V}\boldsymbol{a}r)^\top \boldsymbol{y}+ s \boldsymbol{b}^\top \boldsymbol{P}(0) \boldsymbol{a}r - r \boldsymbol{a}^\top (\boldsymbol{V}^\top \boldsymbol{y}+ \boldsymbol{P}(0)^\top \boldsymbol{b}s) \rrbracket _\textsf{t} \\ =&\llbracket \boldsymbol{x}^\top \boldsymbol{y} \rrbracket _\textsf{t}. \end{aligned}$$

Theorem 1

(Selective security). The scheme presented in Fig. 2 is selectively secure under the SXDH assumption.

Proof

We proceed via a series of hybrid games described bellow (the differences from one game to the next are highlighted in red).

$\underline{\textsf{Game}_0:}$ is the game from the selective security definition in Sect. 2.5. Recall that the adversary $\mathcal {A}$ first receives $\textsf{pk}=\Big (\llbracket \boldsymbol{a} \rrbracket _\textsf{1},\left( \llbracket \boldsymbol{U}_i \boldsymbol{a} \rrbracket _\textsf{1}\right) _{i \in \{0,\ldots ,t\}},\llbracket \boldsymbol{V}\boldsymbol{a} \rrbracket _\textsf{1}\Big )$. Then, it chooses a pair of messages $((\boldsymbol{x}_0,\textsf{id}_0),(\boldsymbol{x}_1,\textsf{id}_1))$, upon which it receives $\textsf{ct}^\star = (\llbracket \boldsymbol{a}r \rrbracket _\textsf{1}, \llbracket \boldsymbol{x}_\beta + \boldsymbol{V}\boldsymbol{a}r \rrbracket _\textsf{1}, \llbracket \boldsymbol{P}(\textsf{id}_\beta ) \boldsymbol{a}r \rrbracket _\textsf{1})$, where $\beta \leftarrow _R\{0,1\}$. Afterwards, it can query its oracle $\mathcal {O}_{\textsf{KeyGen}}$ on inputs of the form $(\llbracket \boldsymbol{y} \rrbracket _\textsf{2},\mathcal {S})$, upon which it gets $\textsf{sk}= (\llbracket \boldsymbol{b}s \rrbracket _\textsf{2},\llbracket \boldsymbol{V}^\top \boldsymbol{y}+ \boldsymbol{P}(0)^\top \boldsymbol{b}s \rrbracket _\textsf{2},(\llbracket \boldsymbol{P}(\textsf{id}_j)^\top \boldsymbol{b}s \rrbracket _\textsf{2})_{\textsf{id}_j \in \mathcal {S}})$. The adversary $\mathcal {A}$ is admissible, which means that $\textsf{id}_0=\textsf{id}_1$, which we denote by $\textsf{id}^\star =\textsf{id}_0=\textsf{id}_1$, and that for all queries $(\llbracket \boldsymbol{y} \rrbracket _\textsf{2},\mathcal {S})$ to $\mathcal {O}_{\textsf{KeyGen}}$, we have $\textsf{id}^\star \in \mathcal {S}$ or ($\textsf{id}^\star \notin \mathcal {S}$ and $\boldsymbol{x}_0^\top \boldsymbol{y}= \boldsymbol{x}_1^\top \boldsymbol{y}$). At the end, the adversary $\mathcal {A}$ outputs a guess $\beta '$.

$\underline{\textsf{Game}_1:}$ we change the way the challenge ciphertext is computed. Namely, we have now

where . We prove that $\textsf{Game}_0 \approx _c \textsf{Game}_1$ by the DDH assumption in $\mathbb {G}_{\textsf{1}}$. Namely, we have $(\llbracket \boldsymbol{a} \rrbracket _\textsf{1},\llbracket \boldsymbol{a}r \rrbracket _\textsf{1}) \approx _c (\llbracket \boldsymbol{a} \rrbracket _\textsf{1},\llbracket \boldsymbol{z} \rrbracket _\textsf{1})$ where the leftmost distribution corresponds to $\textsf{Game}_0$, whereas the rightmost distribution corresponds to $\textsf{Game}_1$.

$\underline{\textsf{Game}_2:}$ we change the way the challenge ciphertext is computed. Namely, we have now

where . Here $\textsf{Span}(\boldsymbol{a})$ denotes the set of vectors proportional to $\boldsymbol{a}$. The cardinal of $\textsf{Span}(\boldsymbol{a})$ is p, thus, the statistical distance between the uniform distribution over $\mathbb {Z}_p^2 \setminus \textsf{Span}(\boldsymbol{a})$ and uniform over $\mathbb {Z}_p^2$ is 1/p, and $\textsf{Game}_1 \approx _s \textsf{Game}_2$.

$\underline{\textsf{Game}_3:}$ we change the way the functional keys and the challenge ciphertext are computed. Namely, the ciphertext is now of the form:

$$ \textsf{ct}^\star =\big (\llbracket \boldsymbol{z} \rrbracket _\textsf{1}, \llbracket \boldsymbol{V}\boldsymbol{z} \rrbracket _\textsf{1},\llbracket \boldsymbol{P}(\textsf{id}^\star )\boldsymbol{z} \rrbracket _\textsf{1}\big ) . $$

Note that the ciphertext does not depend on the message $\boldsymbol{x}_\beta$ anymore. Each query $(\llbracket \boldsymbol{y} \rrbracket _\textsf{2},\mathcal {S})$ to $\mathcal {O}_{\textsf{KeyGen}}$ is now answered with

where $\boldsymbol{a}^\bot \in \mathbb {Z}_p^2$ is the vector such that $\boldsymbol{a}^\top \boldsymbol{a}^\bot =0$ and $\boldsymbol{z}^\top \boldsymbol{a}^\bot =1$. $\textsf{Game}_2$ and $\textsf{Game}_3$ are identically distributed, since for all $\boldsymbol{x}_\beta \in \mathbb {Z}_p^d$, all $\boldsymbol{a}^\bot \in \mathbb {Z}_p^2$, the following are identically distributed: $\{\boldsymbol{V}\leftarrow _R\mathbb {Z}_p^{d \times 2}: \boldsymbol{V}\}$ and $\{\boldsymbol{V}\leftarrow _R\mathbb {Z}_p^{d \times 2}: \boldsymbol{V}- \boldsymbol{x}_\beta (\boldsymbol{a}^\bot )^\top \}$. The former distribution corresponds to $\textsf{Game}_2$ with some pre and post-processing, whereas the latter corresponds to $\textsf{Game}_3$ with the same pre and post-processing. Note that $\textsf{Game}_3$ crucially relies on the fact that the adversary is selective, since the vector $\boldsymbol{x}_\beta$ needs to be known to generate all functional secret keys.

$\underline{\textsf{Game}_4:}$ we change the way the functional keys are computed. Namely, each query $(\llbracket \boldsymbol{y} \rrbracket _\textsf{2},\mathcal {S})$ to $\mathcal {O}_{\textsf{KeyGen}}$ is now answered with

That is, now we only have the term $\boldsymbol{a}^\bot \boldsymbol{x}_\beta ^\top \boldsymbol{y}$ for functional key queries $(\boldsymbol{y},\mathcal {S})$ where $\textsf{id}^\star \notin \mathcal {S}$ . To transition from $\textsf{Game}_3$ to $\textsf{Game}_4$, we use the following hybrid games.

$\underline{\textsf{Game}_{3.i}:}$ for all $i\in \{0,\ldots ,Q\}$, where Q denotes the number of functional key queries, $\textsf{Game}_{3.i}$ is defined as $\textsf{Game}_4$ for the first i’th key queries and as $\textsf{Game}_3$ for the last $Q-i$ queries. By definition we have $\textsf{Game}_3=\textsf{Game}_{3.0}$ and $\textsf{Game}_4=\textsf{Game}_{3.Q}$. It suffices to show that for all $i\in [Q]$, $\textsf{Game}_{3.i-1} \approx _c \textsf{Game}_{3.i}$. To do so, we introduce new intermediate games, defined as follows.

$\underline{\textsf{Game}_{3.i-1.1}:}$ is defined as $\textsf{Game}_{3.i-1}$, except the i’th query to $\mathcal {O}_{\textsf{KeyGen}}$, denoted by $(\llbracket \boldsymbol{y}_i \rrbracket _\textsf{2},\mathcal {S}_i)$, is now answered with

where . We have $\textsf{Game}_{3.i-1} \approx _c \textsf{Game}_{3.i-1.1}$ by the DDH assumption in $\mathbb {G}_{\textsf{2}}$, which states that $(\llbracket \boldsymbol{b} \rrbracket _\textsf{2},\llbracket \boldsymbol{b}s_i \rrbracket _\textsf{2})\approx _c (\llbracket \boldsymbol{b} \rrbracket _\textsf{2},\llbracket \boldsymbol{d} \rrbracket _\textsf{2})$ where $\boldsymbol{b},\boldsymbol{d}\leftarrow _R\mathbb {Z}_p^2,s_i \leftarrow _R\mathbb {Z}_p$. The former distribution corresponds to $\textsf{Game}_{3.i-1}$ with some efficient post-processing, whereas the latter corresponds to $\textsf{Game}_{3.i-1.1}$ with the same post-processing.

$\underline{\textsf{Game}_{3.i-1.2}:}$ is defined as $\textsf{Game}_{3.i-1.1}$, except the vector $\boldsymbol{d}$ used to compute the i’th queried functional secret key is sampled as $\boldsymbol{d}\leftarrow _R\mathbb {Z}_p^2 \setminus \textsf{Span}(\boldsymbol{b})$, instead of uniformly random over $\mathbb {Z}_p^2$. Since the cardinal of $\textsf{Span}(\boldsymbol{b})$ is at most p, the uniform distribution over $\mathbb {Z}_p^2 \setminus \textsf{Span}(\boldsymbol{b})$ has statistical distance at most 1/p with the uniform distribution over $\mathbb {Z}_p^2$. Thus, $\textsf{Game}_{3.i-1.1} \approx _s \textsf{Game}_{3.i-1.2}$.

$\underline{\textsf{Game}_{3.i-1.3}:}$ is defined as $\textsf{Game}_{3.i-1.2}$, except the i’th query to $\mathcal {O}_{\textsf{KeyGen}}$ is now answered with

where $\boldsymbol{d}\leftarrow _R\mathbb {Z}_p^2 \setminus \textsf{Span}(\boldsymbol{b})$. Note that if $\textsf{id}^\star \notin \mathcal {S}_i$, then the two games $\textsf{Game}_{3.i-1.2}$ and $\textsf{Game}_{3.i-1.3}$ are identical. Thus we focus on the case $\textsf{id}^\star \in \mathcal {S}_i$. In that case we show that $\textsf{Game}_{3.i-1.3}$ is also identically distributed to $\textsf{Game}_{3.i-1.2}$ using a statistical argument, which relies on the fact that vectors $\boldsymbol{P}(\textsf{id}_j)^\top \boldsymbol{b}$ and $\boldsymbol{P}(\textsf{id}_j)^\top \boldsymbol{d}$ are statistically independent since $\boldsymbol{b}$ and $\boldsymbol{d}$ are linearly independent. The same holds with respect to the matrix $\boldsymbol{P}(0)$. Moreover, since $\textsf{id}^\star \in \mathcal {S}_i$, the set of values $\{(\boldsymbol{P}(\textsf{id}_j) )_{\textsf{id}_j \in \mathcal {S}_i}, \boldsymbol{P}(\textsf{id}^\star )\}$ are statistically independent from the value $\boldsymbol{P}(0)$—recall that the polynomial P is of degree t; we are using Fact 1 from Sect. 2.2. Combining these two facts, we know that the vector $\boldsymbol{P}(0)^\top \boldsymbol{d}$ is uniformly random, independent from everything else (challenge ciphertext, public key and other functional secret keys). Thus, it can act as a one-time pad on the value $\boldsymbol{a}^\bot \boldsymbol{x}_\beta ^\top \boldsymbol{y}$ that we wish to remove.

$\underline{\textsf{Game}_{3.i-1.4}:}$ is defined as $\textsf{Game}_{3.i-1.3}$, except the vector $\boldsymbol{d}$ used to compute the i’th queried functional secret key is sampled $\boldsymbol{d}\leftarrow _R\mathbb {Z}_p^2$, instead of uniformly random over $\mathbb {Z}_p^2\setminus \textsf{Span}(\boldsymbol{b})$. This is the reverse to the transition from $\textsf{Game}_{3.i-1.1}$ to $\textsf{Game}_{3.i-1.2}$. By the same statistical argument, we obtain $\textsf{Game}_{3.i-1.3} \approx _s \textsf{Game}_{3.i-1.4}$.

Finally, note that $\textsf{Game}_{3.i-1.4}$ is the same as $\textsf{Game}_{3.i}$ except the i’th queried key is computed using $\llbracket \boldsymbol{d} \rrbracket _\textsf{2} \leftarrow _R\mathbb {G}_{\textsf{2}}^2$ in the former, and $\llbracket \boldsymbol{b}s_i \rrbracket _\textsf{2} \in \mathbb {G}_{\textsf{2}}^2$ with $s_i \leftarrow _R\mathbb {Z}_p$ in the latter. Therefore, we have $\textsf{Game}_{3.i-1.4} \approx _c \textsf{Game}_{3.i}$ by the DDH assumption, which states that $(\llbracket \boldsymbol{b} \rrbracket _\textsf{2},\llbracket \boldsymbol{d} \rrbracket _\textsf{2})\approx _c (\llbracket \boldsymbol{b} \rrbracket _\textsf{2},\llbracket \boldsymbol{b}s_i \rrbracket _\textsf{2})$ where $\boldsymbol{b},\boldsymbol{d}\leftarrow _R\mathbb {Z}_p^2,s_i \leftarrow _R\mathbb {Z}_p$. The former distribution corresponds to $\textsf{Game}_{3.i-1.4}$, whereas the latter distribution corresponds to $\textsf{Game}_{3.i}$. Note that this transition is exactly reverse to the transition from $\textsf{Game}_{3.i-1}$ to $\textsf{Game}_{3.i-1.1}$. This concludes the proof that $\textsf{Game}_{3.i-1} \approx _c \textsf{Game}_{3.i}$ and consequently, that $\textsf{Game}_3 \approx _c \textsf{Game}_4$.

Note that in $\textsf{Game}_4$, the only values that possibly reveal some information about the bit $\beta$ is the set $\{\boldsymbol{x}_\beta ^\top \boldsymbol{y}_i\}$ for all queries $(\llbracket \boldsymbol{y}_i \rrbracket _\textsf{2},\mathcal {S}_i)$ such that $\textsf{id}^\star \notin \mathcal {S}_i$. Since the adversary $\mathcal {A}$ is admissible, we know that for all such values, $\boldsymbol{x}_\beta ^\top \boldsymbol{y}_i=\boldsymbol{x}_0^\top \boldsymbol{y}_i=\boldsymbol{x}_1^\top \boldsymbol{y}_i$. In other words, these values do not depend on $\beta$ and the advantage of $\mathcal {A}$ is 0.   $\square$

3.3 Revocations with Arbitrary-Size Identity Sets

Our previous construction requires that the size of any identities set $\mathcal {S}$ be exactly t (a pre-established system parameter).

A possible way to relax this limitation is to introduce dummy identities and use them as “fillers”, to extend an identity set until it reaches size t. Furthermore, in order to make the secret-key size proportional to the identity set $\mathcal {S}$, we could run different instances of the IPFE for different set-size bounds $t_1, \dots , t_n$. A secret-key for set $\mathcal {S}$ would then be issued only with respect to the i-th IPFE instance, where $t_i$ is the smallest such that $|\mathcal {S}| \le t_i$. (Ciphertexts would need to be provided with respect to all IPFE instances). A natural and effective choice for the values of $t_i$ is the set of powers of 2. That way, the ciphertext-size would be increased by a factor of $\log _2$ of the global maximum identity set size. Note that such factor is logairthmic in the security parameter. This technique has already been used in the literature and in particular in the context of ABE, e.g. by Ostrovsky et al. [OSW07, Section 3.3].

4 Generic Construction of MA-ABE from IPFE

We present a modular construction of MA-ABE for non-monotone access structures based on inner-product FE schemes. We show that the resulting MA-ABE is super selectively secure for static corruptions, provided the underlying FE are super selectively secure. The security is proven in the random oracle model.

Fig. 3.

Construction of Multi-Authority ABE from an ID-IPFE scheme $\varGamma$ and an IPFE with revocations $\varSigma$ (for vectors of dimension 4). Recall that $\theta$ maps a row $j \in [\ell ]$ to the authority that owns the attribute associated to that row.

Correctness. Let $\llbracket \boldsymbol{z}_{\textsf{gid}} \rrbracket _\textsf{2}\,{:}{=}\,H(\textsf{gid})$. Observe that, by the correctness of $\varGamma$ and $\varSigma$, we have:

$$\begin{aligned}&\sum _{\rho (j) \in S}{\omega _j} \varGamma .\textsf{Dec}(\textsf{pk}_{\theta (j)}, \textsf{ct}_{j}, \textsf{sk}_{\textsf{gid},\mathcal {S}_{\theta (j)}}, \llbracket 1, \boldsymbol{z}_\textsf{gid} \rrbracket _\textsf{2}) \\ +&\sum _{\rho (j)=\lnot \textsf{att}, \textsf{att}\notin \mathcal {S}} \omega '_j \varSigma .\textsf{Dec}(\textsf{pk}_{\theta (j)}, \textsf{ct}_{j}, \textsf{sk}_{\textsf{gid},\mathcal {S}_{\theta (j)}}, \llbracket 1, \boldsymbol{z}_\textsf{gid} \rrbracket _\textsf{2}) \\ =&\sum _{\rho (j) \in S}{\omega _j} \llbracket s_j + \boldsymbol{a}^\top \boldsymbol{z}_\textsf{gid}u_j \rrbracket _\textsf{t} + \sum _{\rho (j)=\lnot \textsf{att}, \textsf{att}\notin \mathcal {S}} \omega '_j \llbracket s_j + \boldsymbol{a}^\top \boldsymbol{z}_\textsf{gid}u_j \rrbracket _\textsf{t} \\ =&\llbracket s + \boldsymbol{a}^\top \boldsymbol{z}_{\textsf{gid}} \cdot 0 \rrbracket _\textsf{t} = \kappa . \end{aligned}$$

Theorem 2

(Super-selective security). The scheme from Fig. 3, is a super-selectively secure MA-ABE with static corruption in the random oracle model, assuming the schemes $\varGamma$ and $\varSigma$ are super-selectively secure and the DDH assumption holds in $\mathbb {G}_{\textsf{2}}$.

Combining with the existence of an ID-IPFE selectively secure under SXDH (from [ACGU20]) and Theorem 1 (the existence of selectively secure IPFE with revocations from SXDH) and noting that selective security implies super-selective security, we obtain the following corollary.

Corollary 1

There exists a super-selectively secure MA-ABE with static corruptions from SXDH.

We now proceed to prove the theorem.

Proof

We prove security via a sequence of hybrid games. We highlight in red the changes from one hybrid to the next when relevant.

$\underline{\textsf{Game}_0:}$ The first game corresponds to the super-selective security game for MA-ABE with static corruptions, defined in Sect. 2.6. We recall it here for completeness. We call $\mathcal {A}$ the admissible adversary. First, $\mathcal {A}$ receives the global parameters $\textsf{gp}=(\varGamma .\textsf{gp},H)$. Then, it can query its oracle $\mathcal {O}_{\textsf{create}}$ that creates a new (honest) authority with an associated $(\textsf{pk},\textsf{sk})$ pair when invoked, adds $\textsf{pk}$ to the set of honest authorities denoted by $\mathcal {S}_\textsf{hon}$ and returns $\textsf{pk}$ to $\mathcal {A}$. Then, $\mathcal {A}$ sends $(\boldsymbol{M},\rho ,\varPi _\textsf{hon},\varPi _\textsf{corr})$ to its challenger, where $\boldsymbol{M}\in \mathbb {Z}_p^{n \times \ell }$, $\rho : [\ell ] \rightarrow \mathbb {Z}_p$ is an access structure with attributes owned by the authorities in the set $\varPi =\varPi _\textsf{hon}\cup \varPi _\textsf{corr}$. Here, $\varPi _\textsf{hon}$ is a set of honest authorities’ public keys, that is, $\varPi _\textsf{hon}\subseteq \mathcal {S}_\textsf{hon}$, and $\varPi _\textsf{corr}$ is a set of authorities’ public key created by $\mathcal {A}$ itself (and not via $\mathcal {O}_{\textsf{create}}$). Because $\mathcal {A}$ is free to create these public keys however it wants (potentially maliciously), these are referred to as corrupted authorities. Note that $\mathcal {A}$ cannot query its oracle $\mathcal {O}_{\textsf{corr}}$, since we assume only static corruptions here. We write $\varPi = \{\textsf{pk}_1,\ldots ,\textsf{pk}_\nu \}$, and we define $\theta : [\ell ] \rightarrow [\nu ]$, which maps each column $j \in [\ell ]$ to the authority that owns the attribute associated with that column.

Afterwards, the adversary can query its oracle $\mathcal {O}_{\textsf{KeyGen}}$ on inputs $\textsf{pk}\in \mathcal {S}_\textsf{hon}$ associated with the secret key $\textsf{sk}= (\textsf{msk}_\varSigma ,\textsf{msk}_\varGamma )$ and $\mathcal {S}\subset \mathcal {U}_\textsf{pk}$, which computes $\textsf{sk}_\varSigma \leftarrow \varSigma .\textsf{KeyGen}(\textsf{msk}_\varSigma , \llbracket 1,\boldsymbol{z}_\textsf{gid} \rrbracket _\textsf{2},\mathcal {S})$ and for all attributes $\textsf{att}_j \in \mathcal {S}$, it computes $\textsf{sk}_{\varGamma ,j} \leftarrow \varGamma .\textsf{KeyGen}(\textsf{msk}_\varGamma , \llbracket 1,\boldsymbol{z}_\textsf{gid} \rrbracket _\textsf{2},\textsf{att}_j)$, where $\llbracket \boldsymbol{z}_\textsf{gid} \rrbracket _\textsf{2}=H(\textsf{gid})$. It returns $\textsf{sk}_{\textsf{gid},\mathcal {S}}=(\textsf{sk}_\varSigma ,(\textsf{sk}_{\varGamma ,j})_{\textsf{att}_j \in \mathcal {S}})$ to the adversary $\mathcal {A}$.

At this point, the challenger samples $s\leftarrow _R\mathbb {Z}_p$ and computes $(s_1,\ldots ,s_\ell ) \leftarrow \textsf{Share}(\boldsymbol{M},s)$, $(u_1,\ldots ,u_\ell ) \leftarrow \textsf{Share}(\boldsymbol{M},0)$², $\boldsymbol{a}\leftarrow _R\mathbb {Z}_p^3$, $\kappa _0=\llbracket s \rrbracket _\textsf{t}$, $\kappa _1 \leftarrow _R\mathbb {G}_{\textsf{t}}$, $\beta \leftarrow _R\{0,1\}$, for all $j \in [\ell ]$, $\boldsymbol{x}_j = (s_j,u_j \cdot \boldsymbol{a}) \in \mathbb {Z}_p^4$, and

• if $\rho (j)= \textsf{att}_j$ where $\textsf{att}_j \in \{0,1\}^*$, then $\textsf{ct}_j \leftarrow \varGamma .\textsf{Enc}(\textsf{pk}_{\varGamma ,\theta (j)},\boldsymbol{x}_i,\rho (j))$,

• if $\rho (j) =\lnot \textsf{att}_j$ where $\textsf{att}_j \in \{0,1\}^*$, then $\textsf{ct}_j \leftarrow \varSigma .\textsf{Enc}(\textsf{pk}_{\varSigma ,\theta (j)},\boldsymbol{x}_i,\rho (j))$.

It sets $\textsf{ct}^\star = \{\textsf{ct}_j\}_{j \in [\ell ]}$ and returns $(\textsf{ct}^\star ,\kappa _\beta )$ to $\mathcal {A}$. Finally, $\mathcal {A}$ outputs a guess $\beta ' \in \{0,1\}$. Recall that $\mathcal {A}$ is admissible, which means it cannot compute $\kappa _0$ from $\textsf{ct}^\star$ simply by correctness of the scheme with the user secret keys it queried and the secret key of the corrupted authorities (see Sect. 2.6 for more details). The experiment outputs 1 if $\beta =\beta '$, 0 otherwise.

In the following hybrids, we use the following dual basis: first, we choose a random basis $(\boldsymbol{a}_1 | \boldsymbol{a}_2 | \boldsymbol{a}_3 ) \in \mathbb {Z}_p^{3 \times 3}$ of $\mathbb {Z}_p^3$ such that $\boldsymbol{a}= r_1 \boldsymbol{a}_1$ for $r_1 \leftarrow _R\mathbb {Z}^*_p$ (recall that the vector $\boldsymbol{a}$ is sampled to produce the challenge ciphertext). Strictly speaking, such a basis exists only when $\boldsymbol{a}\ne \textbf{0}$. Since $\boldsymbol{a}$ is sampled uniformly at random over $\mathbb {Z}_p^3$, it is different from $\textbf{0}$ with overwhelming probability. Thus, we implicitly assume $\boldsymbol{a}$ is sampled uniformly over $\mathbb {Z}_p^3 \setminus \{\textbf{0}\}$ in the proof (this only changes the distribution by a negligible statistical distance). Then, we denote by $(\boldsymbol{a}_1^* | \boldsymbol{a}_2^* | \boldsymbol{a}_3^*) \in \mathbb {Z}_p^{3 \times 3}$ its dual basis, that is, such that for all $i,j \in \{1,2,3\}$, $\boldsymbol{a}_i^\top \boldsymbol{a}_j^* =0$ if $i \ne j$ and $\boldsymbol{a}_i^\top \boldsymbol{a}_j^* =1$ if $i=j$. We make use of the following assumptions relative to the pairing groups $(\mathbb {G}_1,\mathbb {G}_2,\mathbb {G}_T)$ and the random dual basis $(\boldsymbol{a}_1|\boldsymbol{a}_2| \boldsymbol{a}_3)$ and $(\boldsymbol{a}_1^*|\boldsymbol{a}_2^* |\boldsymbol{a}_3^*)$.

Assumption 1. $\{\boldsymbol{v}\leftarrow _R\mathbb {Z}_p^3: (\llbracket \boldsymbol{a}_1 \rrbracket _\textsf{1},\llbracket \boldsymbol{v} \rrbracket _\textsf{2})\} \approx _c \{\boldsymbol{v}\leftarrow _R\textsf{Span}(\boldsymbol{a}_1^*): (\llbracket \boldsymbol{a}_1 \rrbracket _\textsf{1},\llbracket \boldsymbol{v} \rrbracket _\textsf{2})\}$.

This assumption is known to be implied by the DDH assumption in $\mathbb {G}_{\textsf{2}}$ (see for instance [Lew12]).

$\underline{\textsf{Game}_1:}$ is the same as $\textsf{Game}_0$ except that the outputs of the hash function are computed as follows: for all $\textsf{gid}$, $H(\textsf{gid}) = \llbracket \boldsymbol{z}_\textsf{gid} \rrbracket _\textsf{2}$ where $\boldsymbol{z}_\textsf{gid}\leftarrow _R\textsf{Span}(\boldsymbol{a}_1^*)$. We have $\textsf{Game}_0 \approx _c \textsf{Game}_1$ by Assumption 1. Technically, we need to use this assumption for each query of $\mathcal {A}$ to the hash function H (modeled as a random oracle) using a hybrid argument.

$\underline{\textsf{Game}_2:}$ is the same as $\textsf{Game}_1$, except that the challenge ciphertext uses the vectors , for all $j \in [\ell ]$ such that $\theta (j) \in \mathcal {S}_\textsf{hon}$, where $v_j = (\gamma , \boldsymbol{v})^\top \boldsymbol{M}_j$, $\boldsymbol{v}\leftarrow _R\mathbb {Z}_p^{n-1}$, and $\gamma \leftarrow _R\mathbb {Z}_p$. That is, the $v_j$ are shares of a random value $\gamma$. Recall that $\boldsymbol{a}_1,\boldsymbol{a}_3 \in \mathbb {Z}_p^3$ are vectors part of the basis $(\boldsymbol{a}_1 | \boldsymbol{a}_2 | \boldsymbol{a}_3)$ and $\boldsymbol{a}= r_1 \boldsymbol{a}_1$ where $r_1 \leftarrow _R\mathbb {Z}_p^*$. The shares $s_j$ and $u_j$ are computed as before. For all $j \in [\ell ]$ such that $\theta (j) \in \varPi _\textsf{corr}$, the vector $\boldsymbol{x}_j$ are as before. The challenge ciphertext is set to be $(\{\textsf{ct}_j\}_{j \in [\ell ]},\kappa _\beta )$, where $\kappa _\beta$ is computed as before. We argue that $\textsf{Game}_1 \approx _c \textsf{Game}_2$ using the super-selective security of $\varGamma$ and $\varSigma$, since the extra red vector is orthogonal to the vectors $\llbracket 1,\boldsymbol{z}_\textsf{gid} \rrbracket _\textsf{2}$ from the user secret keys. This is because for all queried $\textsf{gid}$, $\boldsymbol{z}_\textsf{gid}\in \textsf{Span}(\boldsymbol{a}_1^*)$ and $\boldsymbol{a}_3^\top \boldsymbol{a}_1^*=0$.

$\underline{\textsf{Game}_3:}$ is the same as $\textsf{Game}_2$, except that the outputs of the hash function are computed as follows: for all $\textsf{gid}$, $H(\textsf{gid}) = \llbracket \boldsymbol{a}_1^* r_\textsf{gid}+ \boldsymbol{a}_3^* \rrbracket _\textsf{2}$, where $r_\textsf{gid}\leftarrow _R\mathbb {Z}_p$. We prove that $\textsf{Game}_2 \approx _c \textsf{Game}_3$ in Lemma 2.

$\underline{\textsf{Game}_4:}$ is the same as $\textsf{Game}_3$, except that the challenge ciphertext uses the vectors for all $j \in [\ell ]$ such that $\theta (j) \in \mathcal {S}_\textsf{hon}$, where $s'_j = (s+\gamma ,\boldsymbol{w})^\top \boldsymbol{M}_j$ and $v'_j = (0,\boldsymbol{v})^\top \boldsymbol{M}_j$. That is, the $s'_j$ are now shares of $s+\gamma$ instead of s and the $v'_j$ are now shares of 0 instead of $\gamma$. The shares $u_j$ are computed as before. We argue that $\textsf{Game}_3 \approx _c \textsf{Game}_4$ thanks to the super-selective security of $\varGamma$ and $\varSigma$. Indeed, for all $j \in [\ell ]$ and all queried $\textsf{gid}$, we have $(s'_j,u_j r_1 \boldsymbol{a}_1 + v'_j \boldsymbol{a}_3)^\top (1,\boldsymbol{a}^*_1 r_\textsf{gid}+ \boldsymbol{a}_3^*) = (s+\gamma ,\boldsymbol{w})^\top \boldsymbol{M}_j + r_1 r_\textsf{gid}(0,\boldsymbol{u})^\top \boldsymbol{M}_j + (0,\boldsymbol{v})^\top \boldsymbol{M}_j = (s,\boldsymbol{w})^\top \boldsymbol{M}_j + r_1 r_\textsf{gid}(0,\boldsymbol{u})^\top \boldsymbol{M}_j + (\gamma ,\boldsymbol{v})^\top \boldsymbol{M}_j = s_j + r_1 r_\textsf{gid}u_j + v_j = (s_j,u_j r_1 \boldsymbol{a}_1 + v_j \boldsymbol{a}_3)^\top (1,\boldsymbol{a}_1^* r_\textsf{gid}+ \boldsymbol{a}_3^*)$, just as in $\textsf{Game}_3$. That is, the change of the vectors encrypted under $\varGamma$ from $\textsf{Game}_3$ to $\textsf{Game}_4$ preserves the value of the inner product.

Finally, to conclude the proof, we show that in $\textsf{Game}_4$, the advantage of $\mathcal {A}$ is 0. This comes from the fact that the value $\kappa _0 = \llbracket s \rrbracket _\textsf{t}$ is uniformly random, independent of the rest of the adversary’s view. Indeed, the only place where the value s appears is in the challenge ciphertext, in the vectors $\boldsymbol{x}_j$ encrypted under $\varGamma$ or $\varSigma$. For all $j \in [\ell ]$ such that $\theta (j) \in \mathcal {S}_\textsf{hon}$, the vector $\boldsymbol{x}_j$ is of the form $\boldsymbol{x}_j= (s'_j,u_j r_1 \boldsymbol{a}_1+v'_j\boldsymbol{a}_3))$ where $s'_j$ is of the form $s_j'=(s+\gamma ,\boldsymbol{w})^\top \boldsymbol{M}_j$ for all $j \in [\ell ]$. That is, the values $s'_j$ are shares of the secret $s+\gamma$. But the value $\gamma \leftarrow _R\mathbb {Z}_p$ is independent of the rest of the adversary’s view, thus it acts as a one-time pad on s. Consequently, $\boldsymbol{x}_j$ is independent of the value s. For all $j \in [\ell ]$ such that $\theta (j) \in \varPi _\textsf{corr}$, we have $\boldsymbol{x}_j =(s_j,u_j r_1 \boldsymbol{a}_1+v_j\boldsymbol{a}_3))$, where the values $s_j$ are shares of the secret s. But because the adversary $\mathcal {A}$ is admissible, we know that the shares $\{s_j\}_{j \in [\ell ], \theta (j) \in \varPi _\textsf{corr}}$ are independent of s, by security of the MSP. Thus, both $\kappa _0$ and $\kappa _1$ are uniformly random independent of everything else, the view of the adversary does not depend on the bit $\beta$; its advantage is 0.   $\square$

Now we state and prove the lemma used in the proof above. Its proof relies on the assumptions below, which are known to be implied by DDH in $\mathbb {G}_{\textsf{2}}$ (see for instance [Lew12]).

Lemma 2

We have $\textsf{Game}_2 \approx _c \textsf{Game}_3$ assuming the super-selective security of $\varGamma$ and $\varSigma$, and the SXDH assumption.

To prove the lemma, we rely on the following assumptions, which are known to be implied by DDH in $\mathbb {G}_{\textsf{2}}$ (see for instance [Lew12]).

Assumption 2.

$$\begin{aligned}&\,\{\boldsymbol{v}\leftarrow _R\textsf{Span}(\boldsymbol{a}_1^*), r_1, r_2 \leftarrow _R\mathbb {Z}^*_p: (\llbracket r_1 \boldsymbol{a}_1+r_2 \boldsymbol{a}_2 \rrbracket _\textsf{1},\llbracket \boldsymbol{a}_1 \rrbracket _\textsf{1},\llbracket \boldsymbol{a}_3 \rrbracket _\textsf{1},\llbracket \boldsymbol{a}_1^* \rrbracket _\textsf{2}, \llbracket \boldsymbol{a}_3^* \rrbracket _\textsf{2}, \llbracket \boldsymbol{v} \rrbracket _\textsf{2})\} \\ \approx _c&\, \{\boldsymbol{v}\leftarrow _R\textsf{Span}(\boldsymbol{a}_1^*, \boldsymbol{a}_2^*), r_1, r_2 \leftarrow _R\mathbb {Z}^*_p: (\llbracket r_1 \boldsymbol{a}_1+r_2 \boldsymbol{a}_2 \rrbracket _\textsf{1},\llbracket \boldsymbol{a}_1 \rrbracket _\textsf{1},\llbracket \boldsymbol{a}_3 \rrbracket _\textsf{1},\llbracket \boldsymbol{a}_1^* \rrbracket _\textsf{2}, \llbracket \boldsymbol{a}_3^* \rrbracket _\textsf{2},\llbracket \boldsymbol{v} \rrbracket _\textsf{2})\} \, . \end{aligned}$$

Assumption 3.

$$\begin{aligned}&\, \{\boldsymbol{v}\leftarrow _R\textsf{Span}(\boldsymbol{a}_1^*,\boldsymbol{a}_2^*), r \leftarrow _R\mathbb {Z}_p: (\llbracket \boldsymbol{a}_1 \rrbracket _\textsf{1},\llbracket r\boldsymbol{a}_2+\boldsymbol{a}_3 \rrbracket _\textsf{1},\llbracket \boldsymbol{a}_1^* \rrbracket _\textsf{2}, \llbracket \boldsymbol{a}_3^* \rrbracket _\textsf{2},\llbracket \boldsymbol{v} \rrbracket _\textsf{2})\} \\ \approx _c&\,\{\boldsymbol{v}\leftarrow _R\textsf{Span}(\boldsymbol{a}_1^*, \boldsymbol{a}_2^*,\boldsymbol{a}_3^*), r \leftarrow _R\mathbb {Z}_p: (\llbracket \boldsymbol{a}_1 \rrbracket _\textsf{1},\llbracket r\boldsymbol{a}_2+\boldsymbol{a}_3 \rrbracket _\textsf{1},\llbracket \boldsymbol{a}_1^* \rrbracket _\textsf{2}, \llbracket \boldsymbol{a}_3^* \rrbracket _\textsf{2},\llbracket \boldsymbol{v} \rrbracket _\textsf{2})\} \, . \end{aligned}$$

Proof

To prove the lemma, we introduce the following hybrid games for all $i \in \{0,\ldots ,q\}$ where $q \in \mathbb {N}$ denotes the number of distinct $\textsf{gid}$ queried via $\mathcal {O}_\textsf{KeyGen}$: $\textsf{Game}_{2.i}$ is like $\textsf{Game}_2$, except that for the first i’th $\textsf{gid}$, $\mathcal {O}_\textsf{KeyGen}$ behaves like in $\textsf{Game}_3$. Namely, for the first i’th $\textsf{gid}$ queried to $\mathcal {O}_\textsf{KeyGen}$, the oracle uses $H(\textsf{gid}) = \llbracket \boldsymbol{a}_1^* r_\textsf{gid}+ \boldsymbol{a}_3^* \rrbracket _\textsf{2}$, whereas it uses $H(\textsf{gid})=\llbracket \boldsymbol{a}_1^* r_\textsf{gid} \rrbracket _\textsf{2}$ for the last $q-i$ queries. It is clear by definition of the games that $\textsf{Game}_{2.0}=\textsf{Game}_2$ and $\textsf{Game}_{2.q}=\textsf{Game}_3$. We prove that for all $i \in [q]$, $\textsf{Game}_{2.i-1} \approx _c \textsf{Game}_{2.i}$. To do so, we use the following hybrid games.

$\underline{\textsf{Game}_{2.i-1.1}:}$ is the same as $\textsf{Game}_{2.i-1}$, except that the challenge ciphertext uses the vectors for all $j \in [\ell ]$ such that $\theta (j) \in \mathcal {S}_\textsf{hon}$, where $r_2 \leftarrow _R\mathbb {Z}_p^*$. We argue that $\textsf{Game}_{2.i-1} \approx _c \textsf{Game}_{2.i-1.1}$ thanks to the super-selective security of $\varGamma$ and $\varSigma$. Indeed, for all $j \in [\ell ]$ and all queried $\textsf{gid}$, we have $\boldsymbol{z}_{\textsf{gid}} \in \textsf{Span}(\boldsymbol{a}_1^*, \boldsymbol{a}_3^*)$, thus , just as in game $\textsf{Game}_{2.i-1}$, since $\boldsymbol{a}_2^\top \boldsymbol{a}_1^*=\boldsymbol{a}_2^\top \boldsymbol{a}_3^*=0$.

$\underline{\textsf{Game}_{2.i-1.2}:}$ is the same as $\textsf{Game}_{2.i-1.1}$ except that the output of the hash function on the i’th queried global identifier, which we denote by $\textsf{gid}_i$, is computed as follows: $H(\textsf{gid}_i) = \llbracket \boldsymbol{z}_{\textsf{gid}_i} \rrbracket _\textsf{2}$ where $\boldsymbol{z}_{\textsf{gid}_i} \leftarrow _R\textsf{Span}(\boldsymbol{a}_1^*,\boldsymbol{a}_2^*)$, as opposed to uniformly random over $\textsf{Span}(\boldsymbol{a}_1^*)$ in $\textsf{Game}_{2.i-1.1}$. We have $\textsf{Game}_{2.i-1.1} \approx _c \textsf{Game}_{2.i-1.2}$ by Assumption 2.

$\underline{\textsf{Game}_{2.i-1.3}:}$ is the same as $\textsf{Game}_{2.i-1.2}$ except that the challenge ciphertext uses the vectors for all $j \in [\ell ]$ such that $\theta (j) \in \mathcal {S}_\textsf{hon}$, where $r_j = (0,\boldsymbol{r})^\top \boldsymbol{M}_j$, and $\boldsymbol{r}\leftarrow _R\mathbb {Z}_p^{n-1}$. We have that $\textsf{Game}_{2.i-1.2} \approx _c \textsf{Game}_{2.i-1.3}$ from the DDH assumption in $\mathbb {G}_{\textsf{1}}$, which implies that $\{r_2 \leftarrow _R\mathbb {Z}^*_p, \boldsymbol{u}\leftarrow _R\mathbb {Z}_p^{n-1}: (\llbracket \boldsymbol{u} \rrbracket _\textsf{1},\llbracket r_2 \boldsymbol{u} \rrbracket _\textsf{1})\} \approx _c \{\boldsymbol{u},\boldsymbol{r}\leftarrow _R\mathbb {Z}_p^{n-1}: (\llbracket \boldsymbol{u} \rrbracket _\textsf{1}, \llbracket \boldsymbol{r} \rrbracket _\textsf{1})\}$³

$\underline{\textsf{Game}_{2.i-1.4}:}$ is the same as $\textsf{Game}_{2.i-1.3}$ except that the challenge ciphertext uses the vectors for all $j \in [\ell ]$ such that $\theta (j) \in \mathcal {S}_\textsf{hon}$, where the value $\eta _j$ is defined as $\eta (1,\boldsymbol{w}_{\textsf{gid}_i})^\top \boldsymbol{M}_j$, where $\eta \leftarrow _R\mathbb {Z}_p$ and $\boldsymbol{w}_{\textsf{gid}_i}$ is a vector such that $(1,\boldsymbol{w}_{\textsf{gid}_i})^\top \boldsymbol{M}_j = 0$ for all $j \in [\ell ]$ such that $\rho (j) \in \mathcal {S}_{\textsf{gid}_i}$ or ($\rho (j) = \lnot \textsf{att}_j$ and $\textsf{att}_j \in \{0,1\}^* \setminus \mathcal {S}_{\textsf{gid}_i}$). The set $\mathcal {S}_{\textsf{gid}_i}$ is defined as $\mathcal {S}_{\textsf{gid}_i} = \cup _{\textsf{pk}\in \mathcal {S}_\textsf{hon}, (\textsf{pk},\textsf{gid}_i,\mathcal {S}) \in \mathcal {Q}_\textsf{KeyGen}} \mathcal {S}$. We know that $\mathcal {S}_{\textsf{gid}_i}$ does not satisfy the access structure $(\boldsymbol{M},\rho )$ of the challenge ciphertext, because the adversary is admissible. Thus, by security of the access structure (Lemma 1), we know that such a vector $\boldsymbol{w}_{\textsf{gid}_i} \in \mathbb {Z}_p^{n-1}$ exists. Note that we crucially rely on the selectivity here, since the vector $\boldsymbol{w}_{\textsf{gid}_i}$ used in the challenge ciphertext depends on attributes queried to $\mathcal {O}_{\textsf{KeyGen}}$. The fact that $\textsf{Game}_{2.i-1.4}\approx _c \textsf{Game}_{2.i-1.3}$ follows from the super-selective security of $\varGamma$ and $\varSigma$. Indeed, the extra red component encrypted under $\varGamma$ or $\varSigma$ never interacts with the vectors used to produce user secret keys. Namely, for all $\textsf{gid}\ne \textsf{gid}_i$, we have $H(\textsf{gid})=\llbracket \boldsymbol{z}_\textsf{gid} \rrbracket _\textsf{2}$ with $\boldsymbol{z}_\textsf{gid}\in \textsf{Span}(\boldsymbol{a}_1^*,\boldsymbol{a}_3^*)$ so . For $\textsf{gid}=\textsf{gid}_i$, we argue that for all $j \in [\ell ]$ such that $\theta (j) \in \mathcal {S}_\textsf{hon}$, either $\eta _j = 0$, or the extra can be added thanks to the super-selective security of $\varGamma$ and $\varSigma$. When $\rho (j) \in \mathcal {S}_{\textsf{gid}_i}$ or $\rho (j)=\lnot \textsf{att}$ with $\textsf{att}\in \{0,1\}^* \setminus \mathcal {S}_{\textsf{gid}_i}$, we know that $\eta _j=0$. When $\rho (j)$ is not of this form, then we know that none of the functional secret keys generated by $\mathcal {O}_\textsf{KeyGen}$ on $\textsf{gid}_i$ decrypt the ciphertext $\textsf{ct}_j$. Thus, we can conclude using the super-selective security of $\varSigma$ and $\varGamma$.

$\underline{\textsf{Game}_{2.i-1.5}:}$ is the same as $\textsf{Game}_{2.i-1.4}$ except that the challenge ciphertext uses the vectors where $\eta '_j=(\eta ,\boldsymbol{r})^\top \boldsymbol{M}_j$, for all $j \in [\ell ]$ such that $\theta (j) \in \mathcal {S}_\textsf{hon}$. The fact that $\textsf{Game}_{2.i-1.5}=\textsf{Game}_{2.i-1.4}$ follows from the fact a uniformly random vector $\boldsymbol{r}\leftarrow _R\mathbb {Z}_p^{n-1}$ is distributed identically to an offset $\boldsymbol{x}\in \mathbb {Z}_p^{n-1}$ plus a uniformly random vector $\boldsymbol{r}\leftarrow _R\mathbb {Z}_p^{n-1}$. This is true no matter the value of $\boldsymbol{x}$, as long as $\boldsymbol{r}$ is sampled independently of $\boldsymbol{x}$. So, the following distributions are equals: $\{r_j + \eta _j\}_{j \in [\ell ]} = \{(0,\boldsymbol{r})^\top \boldsymbol{M}_j + \eta (1,\boldsymbol{w}_{\textsf{gid}_i})^\top \boldsymbol{M}_j\}_{j \in [\ell ]} = \{(\eta ,\boldsymbol{r}+\eta \boldsymbol{w}_{\textsf{gid}_i})^\top \boldsymbol{M}_j\}_{j \in [\ell ]} \equiv \{(\eta ,\boldsymbol{r})^\top \boldsymbol{M}_j\}_{j \in [\ell ]} = \{\eta '_j\}_{j \in [\ell ]}$. This first distribution corresponds to $\textsf{Game}_{2.i-1.4}$, whereas the last distribution corresponds to $\textsf{Game}_{2.i-1.5}$.

$\underline{\textsf{Game}_{2.i-1.6}:}$ is the same as $\textsf{Game}_{2.i-1.5}$ except that the challenge ciphertext uses the vectors or all $j \in [\ell ]$ such that $\theta (j) \in \mathcal {S}_\textsf{hon}$, where $r'_j = r(\gamma ,\boldsymbol{v})^\top \boldsymbol{M}_j$, $r\leftarrow _R\mathbb {Z}_p$. Recall that $\gamma \in \mathbb {Z}_p$ and $\boldsymbol{v}\in \mathbb {Z}_p^{n-1}$ are used to compute the shares $v_j$, namely $v_j = (\gamma ,\boldsymbol{v})^\top \boldsymbol{M}_j$. We argue that $\textsf{Game}_{2.i-1.5} \approx _c \textsf{Game}_{2.i-1.6}$ using the DDH assumption in $\mathbb {G}_{\textsf{1}}$, which implies that $\{\boldsymbol{r}, \boldsymbol{v}\leftarrow _R\mathbb {Z}_p^{n-1}, \eta , \gamma \leftarrow _R\mathbb {Z}_p: (\llbracket \eta \rrbracket _\textsf{1},\llbracket \boldsymbol{r} \rrbracket _\textsf{1}, \llbracket \gamma \rrbracket _\textsf{1},\llbracket \boldsymbol{v} \rrbracket _\textsf{1})\} \approx _c \{\boldsymbol{v}\leftarrow _R\mathbb {Z}_p^{n-1}, r,\gamma \leftarrow _R\mathbb {Z}_p: (\llbracket r \gamma \rrbracket _\textsf{1}, \llbracket r \boldsymbol{v} \rrbracket _\textsf{1}, \llbracket \gamma \rrbracket _\textsf{1}, \llbracket \boldsymbol{v} \rrbracket _\textsf{1})\}$.

$\underline{\textsf{Game}_{2.i-1.7}:}$ is the same as $\textsf{Game}_{2.i-1.6}$ except that the output of the hash function on the i’th queried global identifier, which we denote by $\textsf{gid}_i$, is computed as follows: where $\boldsymbol{z}_{\textsf{gid}_i} \leftarrow _R\textsf{Span}(\boldsymbol{a}_1^*,\boldsymbol{a}_2^*)$. We have $\textsf{Game}_{2.i-1.6} \approx _c \textsf{Game}_{2.i-1.7}$ by Assumption 3. Indeed, we have $\{ \boldsymbol{z}_{\textsf{gid}_i} \leftarrow _R\textsf{Span}(\boldsymbol{a}_1^*,\boldsymbol{a}_2^*): \llbracket \boldsymbol{z}_{\textsf{gid}_i} \rrbracket _\textsf{2}\} \approx _c \{ \boldsymbol{z}_{\textsf{gid}_i} \leftarrow _R\textsf{Span}(\boldsymbol{a}_1^*,\boldsymbol{a}_2^*,\boldsymbol{a}_3^*): \llbracket \boldsymbol{z}_{\textsf{gid}_i} \rrbracket _\textsf{2}\} \equiv \{ \boldsymbol{z}_{\textsf{gid}_i} \leftarrow _R\textsf{Span}(\boldsymbol{a}_1^*,\boldsymbol{a}_2^*,\boldsymbol{a}_3^*): \llbracket \boldsymbol{z}_{\textsf{gid}_i} + \boldsymbol{a}_3^* \rrbracket _\textsf{2}\} \approx _c \{ \boldsymbol{z}_{\textsf{gid}_i} \leftarrow _R\textsf{Span}(\boldsymbol{a}_1^*,\boldsymbol{a}_2^*): \llbracket \boldsymbol{z}_{\textsf{gid}_i} + \boldsymbol{a}_3^* \rrbracket _\textsf{2}\}$, where the $\approx _c$ follows from Assumption 3. The first distribution corresponds to $\textsf{Game}_{2.i-1.6}$, whereas the last distribution corresponds to $\textsf{Game}_{2.i-1.7}$. Note that for readability we omit the other values $(\llbracket \boldsymbol{a}_1 \rrbracket _\textsf{1}, \llbracket r \boldsymbol{a}_2 + \boldsymbol{a}_3 \rrbracket _\textsf{1}, \llbracket \boldsymbol{a}_1^* \rrbracket _\textsf{2}, \llbracket \boldsymbol{a}_3^* \rrbracket _\textsf{2})$ present in the output of all distributions. These values are sufficient to generate the entire adversary’s view.

$\underline{\textsf{Game}_{2.i-1.8}:}$ is the same as $\textsf{Game}_{2.i-1.7}$ except that the challenge ciphertext uses the vectors for all $j \in [\ell ]$ such that $\theta (j) \in \mathcal {S}_\textsf{hon}$, where $\eta '_j = (\eta ,\boldsymbol{r})^\top \boldsymbol{M}_j$, $\eta \leftarrow _R\mathbb {Z}_p$, $\boldsymbol{r}\leftarrow _R\mathbb {Z}_p^{n-1}$. This is the reverse of the transition from $\textsf{Game}_{2.i-1.5}$ and $\textsf{Game}_{2.i-1.6}$. We have $\textsf{Game}_{2.i-1.7} \approx _c \textsf{Game}_{2.i-1.8}$ using the DDH assumption in $\mathbb {G}_{\textsf{1}}$, which implies that $\{r,\gamma \leftarrow _R\mathbb {Z}_p, \boldsymbol{v}\leftarrow _R\mathbb {Z}_p^{n-1}: (\llbracket r \gamma \rrbracket _\textsf{1},\llbracket r \boldsymbol{v} \rrbracket _\textsf{1}, \llbracket \gamma \rrbracket _\textsf{1},\llbracket \boldsymbol{v} \rrbracket _\textsf{1})\} \approx _c \{\eta ,\gamma \leftarrow _R\mathbb {Z}_p, \boldsymbol{r}, \boldsymbol{v}\leftarrow _R\mathbb {Z}_p^{n-1}: (\llbracket \eta \rrbracket _\textsf{1},\llbracket \boldsymbol{r} \rrbracket _\textsf{1},\llbracket \gamma \rrbracket _\textsf{1},\llbracket \boldsymbol{v} \rrbracket _\textsf{1})\}$.

$\underline{\textsf{Game}_{2.i-1.9}:}$ is the same as $\textsf{Game}_{2.i-1.8}$ except that the challenge ciphertext uses the vectors for all $j \in [\ell ]$ such that $\theta (j) \in \mathcal {S}_\textsf{hon}$, where $r_j = (0,\boldsymbol{r})^\top \boldsymbol{M}_j$, $\eta _j = \eta (1,\boldsymbol{w}_{\textsf{gid}_i})^\top \boldsymbol{M}_j$, $\eta \leftarrow _R\mathbb {Z}_p$ and $\boldsymbol{w}_{\textsf{gid}_i}$ is defined as before. This is the reverse of the transition from $\textsf{Game}_{2.i-1.4}$ and $\textsf{Game}_{2.i-1.5}$. The fact that $\textsf{Game}_{2.i-1.8}=\textsf{Game}_{2.i-1.9}$ follows from the fact a uniformly random vector $\boldsymbol{r}\leftarrow _R\mathbb {Z}_p^{n-1}$ is distributed identically to an offset $\boldsymbol{x}\in \mathbb {Z}_p^{n-1}$ plus a uniformly random vector $\boldsymbol{r}\leftarrow _R\mathbb {Z}_p^{n-1}$, as long as $\boldsymbol{r}$ is sampled independently of $\boldsymbol{x}$. So, the following distributions are equals: $\{\eta '_j\}_{j \in [\ell ]} = \{(\eta ,\boldsymbol{r})^\top \boldsymbol{M}_j\}_{j \in [\ell ]} \equiv \{(\eta ,\boldsymbol{r}+\eta \boldsymbol{w}_{\textsf{gid}_i})^\top \boldsymbol{M}_j\}_{j \in [\ell ]} = \{(0,\boldsymbol{r})^\top \boldsymbol{M}_j + \eta (1,\boldsymbol{w}_{\textsf{gid}_i})^\top \boldsymbol{M}_j\}_{j \in [\ell ]} = \{r_j+\eta _j\}_{j \in [\ell ]}$. This first distribution corresponds to $\textsf{Game}_{2.i-1.8}$, whereas the last distribution corresponds to $\textsf{Game}_{2.i-1.9}$.

$\underline{\textsf{Game}_{2.i-1.10}:}$ is the same as $\textsf{Game}_{2.i-1.9}$ except that the challenge ciphertext uses the vectors for all $j \in [\ell ]$ such that $\theta (j) \in \mathcal {S}_\textsf{hon}$, where $r_j = (0,\boldsymbol{r})^\top \boldsymbol{M}_j$, $\boldsymbol{r}\leftarrow _R\mathbb {Z}_p^{n-1}$. This is the reverse of the transition from $\textsf{Game}_{2.i-1.3}$ and $\textsf{Game}_{2.i-1.4}$. The fact that $\textsf{Game}_{2.i-1.9}\approx _c \textsf{Game}_{2.i-1.10}$ follows from the super-selective security of $\varGamma$ and $\varSigma$. Indeed, the component $\eta _j \boldsymbol{a}_2$ encrypted under $\varGamma$ and $\varSigma$ in $\textsf{Game}_{2.i-1.9}$ never interacts with the vectors used to produce user secret keys. Namely, for all $\textsf{gid}\ne \textsf{gid}_i$, we have $H(\textsf{gid})=\llbracket \boldsymbol{z}_\textsf{gid} \rrbracket _\textsf{2}$ with $\boldsymbol{z}_\textsf{gid}\in \textsf{Span}(\boldsymbol{a}_1^*,\boldsymbol{a}_3^*)$ so $(0,\eta _j \boldsymbol{a}_2)^\top (1,\boldsymbol{z}_\textsf{gid})=0$. For $\textsf{gid}=\textsf{gid}_i$, we know that all queries $(\textsf{pk},\textsf{gid}_i,\mathcal {S})$ to $\mathcal {O}_\textsf{KeyGen}$ are such that $\mathcal {S}\in \mathcal {S}_{\textsf{gid}_i}$ (by definition of the set $\mathcal {S}_{\textsf{gid}_i}$), and, as argued before, we know that for all $j \in [\ell ]$ such that $\theta (j) \in \mathcal {S}_\textsf{hon}$, either $\eta _j = 0$ or $\textsf{ct}_j$ cannot be decrypted by the functional secret keys generated by $\mathcal {O}_{\textsf{KeyGen}}$ on $\textsf{gid}_i$.

$\underline{\textsf{Game}_{2.i-1.11}:}$ is the same as $\textsf{Game}_{2.i-1.10}$ except that the challenge ciphertext uses the vectors for all $j \in [\ell ]$ such that $\theta (j) \in \mathcal {S}_\textsf{hon}$, where $r_2 \leftarrow _R\mathbb {Z}^*_p$. This is the reverse of the transition from $\textsf{Game}_{2.i-1.2}$ and $\textsf{Game}_{2.i-1.3}$. We have that $\textsf{Game}_{2.i-1.10} \approx _c \textsf{Game}_{2.i-1.11}$ from the DDH assumption in $\mathbb {G}_{\textsf{1}}$, which implies that $\{\boldsymbol{u},\boldsymbol{r}\leftarrow _R\mathbb {Z}_p^{n-1}: (\llbracket \boldsymbol{u} \rrbracket _\textsf{1}, \llbracket \boldsymbol{r} \rrbracket _\textsf{1})\} \approx _c \{r_2 \leftarrow _R\mathbb {Z}^*_p, \boldsymbol{u}\leftarrow _R\mathbb {Z}_p^{n-1}: (\llbracket \boldsymbol{u} \rrbracket _\textsf{1},\llbracket r_2 \cdot \boldsymbol{u} \rrbracket _\textsf{1})\}$⁴. This first distribution corresponds to $\textsf{Game}_{2.i-1.10}$, whereas the last distribution corresponds to $\textsf{Game}_{2.i-1.11}$.

$\underline{\textsf{Game}_{2.i-1.12}:}$ is the same as $\textsf{Game}_{2.i-1.11}$ except that the output of the hash function on the i’th queried global identifier, which we denote by $\textsf{gid}_i$, is computed as follows: $H(\textsf{gid}_i) = \llbracket \boldsymbol{z}_{\textsf{gid}_i} + \boldsymbol{a}_3^* \rrbracket _\textsf{2}$ where $\boldsymbol{z}_{\textsf{gid}_i} \leftarrow _R\textsf{Span}(\boldsymbol{a}_1^*)$, as opposed to uniformly random over $\textsf{Span}(\boldsymbol{a}_1^*,\boldsymbol{a}_2^*)$ in $\textsf{Game}_{2.i-1.11}$. This is the reverse of the transition from $\textsf{Game}_{2.i-1.1}$ and $\textsf{Game}_{2.i-1.2}$. We have $\textsf{Game}_{2.i-1.1} \approx _c \textsf{Game}_{2.i-1.2}$ by Assumption 2.

$\underline{\textsf{Game}_{2.i}:}$ is the same as $\textsf{Game}_{2.i-1.12}$, except that the challenge ciphertext uses the vectors $\boldsymbol{x}_j=(s_j,u_j r_1 \boldsymbol{a}_1 + v_j \boldsymbol{a}_3 )$ for all $j \in [\ell ]$ such that $\theta (j) \in \mathcal {S}_\textsf{hon}$. That is, we remove the component $u_j r_2 \boldsymbol{a}_2$. We argue that $\textsf{Game}_{2.i-1.12} \approx _c \textsf{Game}_{2.i}$ thanks to the super-selective security of $\varGamma$ and $\varSigma$. Indeed, for all $j \in [\ell ]$ such that $\theta (j) \in \mathcal {S}_\textsf{hon}$ and all queried $\textsf{gid}$, we have $\boldsymbol{z}_{\textsf{gid}} \in \textsf{Span}(\boldsymbol{a}_1^*, \boldsymbol{a}_3^*)$, thus $(s_j,u_j r_1 \boldsymbol{a}_1 + u_j r_2 \boldsymbol{a}_2 + v_j \cdot \boldsymbol{a}_3)^\top (1,\boldsymbol{z}_\textsf{gid}) = (s_j,u_j r_1 \boldsymbol{a}_1 + v_j \cdot \boldsymbol{a}_3)^\top (1,\boldsymbol{z}_\textsf{gid})$, just as in game $\textsf{Game}_{2.i}$, since $\boldsymbol{a}_2^\top \boldsymbol{a}_1^*=\boldsymbol{a}_2^\top \boldsymbol{a}_3^*=0$.   $\square$