Decentralized Multi-Authority Attribute-Based Inner-Product FE: Large Universe and Unbounded

Abstract

This paper presents the first decentralized multi-authority attribute-based inner product functional encryption $(\textsf{MA}\text {-}\textsf{ABIPFE})$ schemes supporting vectors of a priori unbounded lengths. The notion of $\textsf{AB}\text {-}\textsf{IPFE}$, introduced by Abdalla et al. [ASIACRYPT 2020], combines the access control functionality of attribute-based encryption $(\textsf{ABE})$ with the possibility of evaluating linear functions on encrypted data. A decentralized $\textsf{MA}\text {-}\textsf{ABIPFE}$ defined by Agrawal et al. [TCC 2021] essentially enhances the $\textsf{ABE}$ component of $\textsf{AB}\text {-}\textsf{IPFE}$ to the decentralized multi-authority setting where several authorities can independently issue user keys involving attributes under their control. In $\textsf{MA}\text {-}\textsf{ABIPFE}$ for unbounded vectors $(\textsf{MA}\text {-}\textsf{ABUIPFE})$, encryptors can encrypt vectors of arbitrary length under access policies of their choice whereas authorities can issue secret keys to users involving attributes under their control and vectors of arbitrary lengths. Decryption works in the same way as for $\textsf{MA}\text {-}\textsf{ABIPFE}$ provided the lengths of the vectors within the ciphertext and secret keys match.

We present two $\textsf{MA}\text {-}\textsf{ABUIPFE}$ schemes supporting access policies realizable by linear secret sharing schemes $(\textsf{LSSS})$, in the significantly faster prime-order bilinear groups under decisional assumptions based on the target groups which are known to be weaker compared to their counterparts based in the source groups. The proposed schemes demonstrate different trade-offs between versatility and underlying assumptions. The first scheme allows each authority to control a bounded number of attributes and is proven secure under the well-studied decisional bilinear Diffie-Hellman $(\textsf{DBDH})$ assumption. On the other hand, the second scheme allows authorities to control exponentially many attributes and attributes are not required to be enumerated at the setup, that is, supports large attribute universe, and is proven secure under a non-interactive q-type variant of the $\textsf{DBDH}$ assumption called L-$\textsf{DBDH}$, similar to what was used in prior large-universe multi-authority $\textsf{ABE}$ $(\textsf{MA}\text {-}\textsf{ABE})$ construction.

When compared with the only known $\textsf{MA}\text {-}\textsf{ABIPFE}$ scheme due to Agrawal et al. [TCC 2021], our schemes offer significantly higher efficiency while offering greater flexibility and security under weaker assumptions at the same time. Moreover, unlike Agrawal et al., our schemes can support the appearance of the same attributes within an access policy arbitrarily many times. Since efficiency and practicality are the prime focus of this work, we prove the security of our constructions in the random oracle model against static adversaries similar to prior works on $\textsf{MA}\text {-}\textsf{ABE}$ with similar motivations and assumptions. On the technical side, we extend the unbounded $\textsf{IPFE}$ techniques of Dufour-Sans and Pointcheval [ACNS 2019] to the context of $\textsf{MA}\text {-}\textsf{ABUIPFE}$ by introducing a novel hash-decomposition technique.

1 Introduction

Functional encryption $(\textsf{FE})$, introduced by Boneh, Sahai and Waters [15] and O’Neill [34] is an advanced form of public key encryption $(\textsf{PKE})$ designed for computing on encrypted data while maintaining its confidentiality beyond the computed results. $\textsf{FE}$ delivers cryptographic solutions to a wide variety of privacy-enhancing technologies from enabling finer access control to outsourcing computations on sensitive data to the cloud. Starting with the work of Abdalla et al. [3], a long sequence of works [2, 4, 10, 18, 40] studied $\textsf{FE}$ schemes for the class of linear functions, also known as inner product $\textsf{FE}$ $(\textsf{IPFE})$. In $\textsf{IPFE}$, the ciphertexts and functional secret keys are associated with vectors $\boldsymbol{x}$ and $\boldsymbol{y}$ respectively while a decrypter only learns the inner product ${\boldsymbol{x}} \cdot {\boldsymbol{y}}$ and nothing else about $\boldsymbol{x}$. Although the functionality is simple, $\textsf{IPFE}$ has found a great amount of applications in both theory, for example, designing more expressive $\textsf{FE}$ schemes for quadratic [23, 27] and general functions [26, 28] and in practice, for example, performing statistical studies on encrypted data, evaluating polynomials, computing conjunctions and disjunctions [3], or calculating hamming weights in biometric authentications [29, 45], constructing trace and revoke schemes [6]. However, any $\textsf{IPFE}$ system suffers from an inherent leakage of data due to it’s linear functionality. In fact, releasing a set of secret keys for vectors forming a basis of the underlying vector space would result in a complete break of the system since it enables the recovery of the master secret key of the $\textsf{IPFE}$ system and hence uncover all the encrypted data in the system.

One natural way to control such leakage of data in $\textsf{IPFE}$ is to combine it with attribute-based encryption $(\textsf{ABE})$, that is, to additionally associate access policies/attributes within the ciphertexts/secret keys (or the other way around) in the same spirit as attribute-based encryption $(\textsf{ABE})$ such that the eligibility for computing on the encrypted data requires a prior validation of the attributes by the policy. Such access control mechanism in $\textsf{IPFE}$ was introduced by Abdalla et al. [5] where they termed this upgraded notion as attribute-based $\textsf{IPFE}$ $(\textsf{AB}\text {-}\textsf{IPFE})$. The notion of $\textsf{AB}\text {-}\textsf{IPFE}$ [5, 8, 35] has been mostly explored in the setting where a single authority is responsible for managing all the attributes in the system and issuing secret keys to users. This not only is a limitation from the point of view of trust, but also it is problematic for practical applications. In fact, in reality, different attributes are governed by different authorities, for example, academic degrees are handled by universities, medical attributes are managed by hospitals while driving licenses are controlled by transportation or automobile agencies.

Multi Authority $\boldsymbol{\textsf{AB}}{} {\textbf {-}}\boldsymbol{\textsf{IPFE}}$: Inspired by the notion of multi-authority $\textsf{ABE}$ $(\textsf{MA}\text {-}\textsf{ABE})$ [19,20,21, 30, 33, 36, 43] which deals with the decentralization of attribute management in the context of $\textsf{ABE}$, Agrawal et al. [9] initiated the study of multi-authority $\textsf{AB}\text {-}\textsf{IPFE}$ $(\textsf{MA}\text {-}\textsf{ABIPFE})$ which enhances the $\textsf{ABE}$ segment of $\textsf{AB}\text {-}\textsf{IPFE}$ to the multi-authority setting. That is, just like $\textsf{MA}\text {-}\textsf{ABE}$, in $\textsf{MA}\text {-}\textsf{ABIPFE}$ individual authorities are allowed to generate their own master key pairs and provide secret keys for attributes only under their control without interacting with the other authorities. A user learns ${\boldsymbol{x}} \cdot {\boldsymbol{y}}$ by decrypting a ciphertext generated with respect to a policy P and a vector $\boldsymbol{x}$ using various secret keys associated to a vector $\boldsymbol{y}$ and the different attributes it possesses that are obtained from the authorities controlling those attributes. Some potential practical application of $\textsf{MA}\text {-}\textsf{ABIPFE}$ could be computing average salary of employees in an organization possessing a driving license and holding a Ph.D, statistics determining mental health of students of different departments in a university, etc.

Despite its countless potential applications, so far the only candidate $\textsf{MA}\text {-}\textsf{ABIPFE}$ scheme, is due to Agrawal et al. [9] which supports access policies realizable by linear secret sharing schemes $(\textsf{LSSS})$ and is designed in a composite-order group and the security is based on variants of the subgroup decision assumptions which are source group assumptions, that is, assumptions made about the source groups of the underlying bilinear pairing. It is a well-known fact that composite-order bilinear groups are very expensive both in terms of computation and communication/storage. This is reflected in the $\textsf{MA}\text {-}\textsf{ABIPFE}$ of [9], especially the decryption takes an unacceptable time of around five days (as shown in Table 2) when run using reasonable parameters, which clearly makes the scheme impractical. In order to address this efficiency bottleneck, a possible way to avoid this heavy efficiency bottleneck is to look for a construction in the prime-order bilinear groups which are way better in terms of the above parameters compared to their composite-order counterparts [22, 25, 31].

Another significant drawback of the $\textsf{MA}\text {-}\textsf{ABIPFE}$ is that the vector lengths are fixed and the number of authorities or attributes are bounded in the setup. Consequently, the system must provision for a vector length bound that captures all possible plaintext vectors that would be encrypted during the lifetime of the system. Further, the size of ciphertexts and the encryption time, however small the length of the plaintext vector $\boldsymbol{x}$ is, scale with the worst-case vector length bound. Also, in the [9] construction, each authority can control at most a bounded number of attributes. This could be a bottleneck in certain applications, for instance, a university may introduce a new academic degree program over time which would require its potential to freely expand the attribute list under its control. Moreover, in the $\textsf{MA}\text {-}\textsf{ABIPFE}$ system of [9], new authorities/attributes could not join beyond the upper limit set in the setup. This is clearly a disadvantage for several applications from the point of view of sustainability since it is often impossible to visualize all possible attributes/authorities that can ever come into existence at the time of setting up the system. For instance, new universities may be included in the survey of analyzing mental health of their students, which amplifies the number of authorities/attributes as well as the length of data. Additionally, the $\textsf{MA}\text {-}\textsf{ABIPFE}$ scheme of [9] suffer from the so-called “one-use” restriction, that is, an attribute can appear within an access policy at most a bounded number of times, which clearly limits the class of access policies and negatively impacts efficiency. Lastly, in order to gain confidence in a new cryptographic primitive such as $\textsf{MA}\text {-}\textsf{ABIPFE}$, it is always important to have more and more candidates for that primitive under qualitatively weaker computational assumptions. We thus consider the following open problem:

Open Problem: Is it possible to construct efficient $\textsf{MA}\text {-}\textsf{ABIPFE}$ schemes for any expressive class of policies, e.g., $\textsf{LSSS}$, and avoiding the one-use restriction in prime-order bilinear groups under any (possibly qualitatively weaker) computational assumption such that an arbitrary number of authorities (possibly having an unbounded number of attributes under their control) can join at any point of time and an unbounded length data can be processed?

Our Results: In this paper, we answer the above open problem affirmatively. More precisely, we start by formulating the notion of (decentralized) multi-authority attribute-based unbounded $\textsf{IPFE}$ $(\textsf{MA}\text {-}\textsf{ABUIPFE})$ which has all the features discussed above, namely, (a) several independent authorities can control different attributes in the system, (b) authorities can join the system at any time and there is no upper bound on the number of authorities that can ever exist in the system, and (c) unbounded length message and key vectors can be processed, that is, each authority can generate their public and master secret keys without fixing the length of vectors that can be processed with their keys. Next, we construct $\textsf{MA}\text {-}\textsf{ABUIPFE}$ supporting $\textsf{LSSS}$ access structures in the significantly faster prime-order bilinear group setting under computational assumptions based in the target group which are known to be qualitatively weaker compared to those based in the source group [11, 21]. The efficiency improvements achieved by our scheme as compared to the only known $\textsf{MA}\text {-}\textsf{ABIPFE}$ scheme [9] is quite significant (see Tables 1 and 2 for a concrete comparison of the schemes). On a more positive note, we are able to overcome the “one-use restriction”, that is, support the appearance of attributes within access policies arbitrarily many times.

We present two $\textsf{MA}\text {-}\textsf{ABUIPFE}$ schemes with varying trade-offs between versatility and underlying assumptions.

• Small-Universe $\boldsymbol{\textsf{MA}}{} {\textbf {-}}\boldsymbol{\textsf{ABUIPFE}}$ Scheme: We construct an $\textsf{MA}\text {-}\textsf{ABUIPFE}$ scheme where an authority is allowed to control a single (or a bounded number of) attribute(s), but the number of authorities that could be added to the system is still arbitrary. The construction is proven secure under the decisional bilinear Diffie-Hellman $(\textsf{DBDH})$ assumption [13, 38] which is a very well-studied computational assumption based in the target groups. Note that the $\textsf{DBDH}$ assumption underlies the security of classical $\textsf{ABE}$ schemes [24, 37, 42] and has recently been shown to realize $\textsf{MA}\text {-}\textsf{ABE}$ [21]. Our $\textsf{MA}\text {-}\textsf{ABUIPFE}$ scheme demonstrates that it is possible to base the security of an even richer functionality on $\textsf{DBDH}$ as well.

• Large-Universe $\boldsymbol{\textsf{MA}}{} {\textbf {-}}\boldsymbol{\textsf{ABUIPFE}}$ Scheme: We further upgrade our small-universe $\textsf{MA}\text {-}\textsf{ABUIPFE}$ scheme to support large attribute universe, that is, where each authority can control exponentially many attributes and attributes need not be enumerated at the setup. We present the security of this construction under a parameterized version of the $\textsf{DBDH}$ assumption which we call the L-$\textsf{DBDH}$ assumption. We justify the validity of this new computational assumption in the generic bilinear group model [12, 39] as is done for nearly if not all bilinear group-based computational assumptions used today. Note that, so far, there is no known $\textsf{MA}\text {-}\textsf{ABE}$ scheme supporting large universe in the literature that is proven secure without parameterized assumption. The efficiency of the proposed large-universe scheme is well comparable to the small-universe one. Thus, our large-universe $\textsf{MA}\text {-}\textsf{ABUIPFE}$ $(\textsf{LMA}\text {-}\textsf{ABUIPFE})$ scheme addresses several efficiency and practicality issues towards deploying this primitive in practice.

Since our focus on this paper is on efficiency and practicality, we content with proving the security of our schemes in the static model where the adversary has to declare all its ciphertext, secret key, and authority corruption queries upfront following prior work on $\textsf{MA}\text {-}\textsf{ABE}$ with similar motivations [36]. However, we would like to mention that while we could not prove our schemes secure against selective adversaries under $\textsf{DBDH}$ or similar target-group-based assumptions, that is, adversaries who must send the challenge ciphertext and authority corruption queries upfront but are allowed to make user secret key queries adaptively afterwards, as considered in [9], we could not identify any vulnerability in our proposed schemes against such adversaries. Also, just like prior $\textsf{MA}\text {-}\textsf{ABE}$ schemes proven secure under standard computational assumptions, we make use of the random oracle model¹.

In order to design our small-universe $\textsf{MA}\text {-}\textsf{ABUIPFE}$, we build on the techniques used in the $\textsf{MA}\text {-}\textsf{ABE}$ construction from $\textsf{DBDH}$ by [21] and the unbounded $\textsf{IPFE}$ construction from $\textsf{DBDH}$ by [38]. However, as explained in Sect. 2 below, a straightforward combination of those techniques does not work. We devise a novel hash-decomposition technique to decompose the evaluation of the hash values, used as randomizers for tying together the different secret keys for the same user, between the encryption and key generation/decryption algorithms and also for handling satisfying and non-satisfying secret key queries of the adversary during the security proof differently. (Please see Sect. 2 for more details on the hash-decomposition technique.)

Along the way to our small universe $\textsf{MA}\text {-}\textsf{ABUIPFE}$ scheme, we also present a single authority $\textsf{AB}\textsf{U}\textsf{IPFE}$ for $\textsf{LSSS}$ access policies in prime-order bilinear groups under the $\textsf{DBDH}$ assumption. Prior to this work, there was no known $\textsf{AB}\text {-}\textsf{IPFE}$ scheme even for bounded length vectors that was proven secure under a target group assumption. Thus, the proposed $\textsf{AB}\textsf{U}\textsf{IPFE}$ expands the portfolio of computational assumptions on which this useful primitive can be based on and thereby increasing the confidence in the existence of this primitive in turn. Further, our construction also demonstrates that despite of being a more expressive functionality, $\textsf{MA}\text {-}\textsf{ABIPFE}$ is still possible under the same assumption as $\textsf{ABE}$ or $\textsf{MA}\text {-}\textsf{ABE}$. In fact, our $\textsf{AB}\text {-}\textsf{IPFE}$ is the first target-group assumption-based $\textsf{FE}$ scheme that goes beyond the “all-or-nothing” paradigm.

Table 1. Efficiency Comparison of [9] and Our Scheme with 128-bit Security

The notations from Table 1 are described below:

• $|\textsf{PK}_t|$/$|\textsf{PK}_\theta |$: size of the public key associated to the attribute t or authority $\theta$

• $|\textsf{SK}_{\textsf{GID}, t, \boldsymbol{u}}|$: size of the secret key associated to the tuple $(\textsf{GID}, t, \boldsymbol{u})$

• $|\textsf{CT}|$: size of the ciphertext

• n: length of vectors; $\ell , s_{\textsf{max}}$: number of rows and columns in $\textsf{LSSS}$ matrix respectively

• $\textsf{E}_{N, S}, \textsf{E}_{q, S}$: exponentiation time in composite and prime order source groups respectively

• $\textsf{E}_{N, T}, \textsf{E}_{q, T}$: exponentiation time in composite and prime order target groups respectively

• $\textsf{P}_{N}, \textsf{P}_{q}$: time to compute a pairing in composite and prime order groups respectively

Table 2. Concrete Efficiency Comparison for 128-bit Security, $n=200, \ell = 50, s_{\textsf{max}}= 20$.

Advantages of Our Schemes Over Agrawal et al. [9] Beyond Unboundedness: Our $\textsf{MA}\text {-}\textsf{ABUIPFE}$ schemes have notable advantages in terms of versatility and performance over the $\textsf{MA}\text {-}\textsf{ABIPFE}$ of [9], named as AGT-$\textsf{FE}$ hereafter beyond the unboundedness property that we achieve in this work. Firstly, the composite-order group-based AGT-$\textsf{FE}$ is significantly slower than our prime-order constructions [22, 25] because of the inherent efficiency gains offered by prime-order bilinear groups. Especially, the size of group elements of a composite-order group $\mathbb {G}_N$ is much larger than that of a prime-order group $\mathbb {G}_q$ for the same security level: 3072-bit length of $\mathbb {G}_N$ compared to 256-bit length of $\mathbb {G}_q$ for the 128-bit security level. Moreover, one pairing operation is more than 250 times slower in $\mathbb {G}_N$ compared to its prime-order counterpart. A concrete comparison of efficiency is depicted in Tables 1 and 2. As we can see, at 128-bit security level, while AGT-$\textsf{FE}$ takes nearly 5 days for a decryption, our scheme only takes several minutes. We also bring down the public key size (which is constant for any arbitrary length vector) by around 99% and at the same time the ciphertext size is comparable to that of AGT-$\textsf{FE}$. Thus our constructions mark a significant progress towards the practical deployment of this primitive. Secondly, the security of AGT-$\textsf{FE}$ is based on source-group-assumptions, precisely, various types of subgroup decision assumptions, which are known to be qualitatively stronger than the target-group-based assumptions [11] such as the $\textsf{DBDH}$ assumption considered in this work. The existing transformations from composite-order group-based systems to analogous prime-order group-based systems [16, 22, 31] that could be applied to AGT-$\textsf{FE}$, technically replaces the subgroup structures by some vector space structures. Consequently, it incurs additional overheads and potential loss in the efficiency to the resulting prime-order system. Further, the translated scheme would still depend on source group assumptions, e.g. the k-linear or its variants.

Thus, our $\textsf{MA}\text {-}\textsf{ABUIPFE}$ exhibits a substantial boost with respect to the performance and at the same time it is secure under a weaker assumption. Furthermore, we extend our $\textsf{MA}\text {-}\textsf{ABUIPFE}$ to the large universe setting which has the flexibility to include an unbounded number of attributes under different authorities to the system at any point of time.

Static Security: Our Motivation: The static security may not be the dream security model for $\textsf{MA}\text {-}\textsf{ABUIPFE}$. However, in this work, our main motivation is on performance and versatility. Moreover, as we already mentioned above, we could not find any vulnerability of our schemes against stronger adversaries, e.g., selective adversaries as considered in [9], even though we could not prove it based on the computational assumptions we considered in this paper. Schemes with greater performance and weaker provable security have often found to suit better in practical deployments. Further, weaker security notions have often been a major stepping stone to obtain more advanced security, e.g., adaptive security, for the same primitive. Please note that many primitives like $\textsf{ABE}$ [24, 37, 42], $\textsf{MA}\text {-}\textsf{ABE}$ [19, 21, 36, 43], $\textsf{IPFE}$ [3], and $\textsf{MC}$-$\textsf{IPFE}$ [1, 17], were first built only with selective/static security before being upgraded to adaptive security [10, 20, 32] based on the same assumptions. Moreover, from a sustainability point of view, it is always important to have a portfolio of candidates for a primitive under various computational assumptions so that if one of the assumptions gets broken, candidates under a different assumption can be deployed. Another motivation for designing a $\textsf{DBDH}$ or related assumption-based scheme is to innovate new techniques that could possibly be translated to the $\textsf{LWE}$ setting, as has previously been done for other $\textsf{FE}$ primitives, e.g., [7, 13, 19, 21].

Paper Organization: The paper is organized as follows. We provide technical overview of our small and large universe $\textsf {MA-ABUIPFE}$ schemes in Sect. 2. Important notations and computational assumptions are given in Sect. 3. The other prerequisites such as definitions of bilinear groups, access structures, LSSS and justification of our newly introduced L-$\textsf{DBDH}$ assumption are given in the full version. We formalize the notion of small and large universe MA-ABUIPFEs for LSSS in Sect. 4. In Sect. 5, we present the construction of small universe MA-ABUIPFE and formally discuss its correctness and security analysis. Next, our LMA-ABUIPFE scheme is described in Sect. 6 whereas its correctness and the security analysis are shifted to the full version. The small universe single authority ABUIPFE scheme along with its correctness and security analysis are provided in the full version.

2 Technical Overview

In this technical overview, we focus on discussing the high level technical details of constructing small universe $\textsf{MA}\text {-}\textsf{ABUIPFE}$ since this is where most of our technical ideas lie. For extending it to large universe setting, we depend on the technique of Rouselakis and Waters [36] which we discuss later in this section. Since our goal is to construct the schemes under target-group-based assumptions, we start with the only existing $\textsf{UIPFE}$ scheme of [38] whose security relies on the $\textsf{DBDH}$ assumption. In fact, their $\textsf{UIPFE}$ is designed from the selectively secure (bounded) $\textsf{IPFE}$ of Abdalla et al. [3] using a hash and pairing mechanism.

2.1 Constructing the Small Universe $\textsf{MA}\text {-}\textsf{ABUIPFE}$

In this overview, we denote by q a prime number and by $[\![x]\!]_i$ an element in a group $\mathbb {G}_i$ for $i \in \{1,2,T\}$. At a high level, given a public key $[\![\alpha ]\!]_1$, the encryption algorithm of [38] amplifies entropy by pairing the public key with the outputs of a hash function applied on the indices of the message vectors. More precisely, the ciphertext and secret keys in the [38] $\textsf{UIPFE}$ (DP-$\textsf{UIPFE}$) takes the following forms.

$$\begin{array}{l c c c c} \textsf {CT}_{\boldsymbol{v}}: &{} &{} C_0 = [\![r]\!]_1,~~~ \{C_i = [\![v_i]\!]_T \cdot e([\![\alpha ]\!]_1, r[\![\textsf {H}(i)]\!]_2)\}_{i \in \mathcal {I}_{\boldsymbol{v}}}; &{} &{}~~ r \leftarrow \mathbb {Z}_q\\ \textsf {SK}_{\boldsymbol{u}}: &{} &{} - \alpha \mathop {\prod }\nolimits _{j \in \mathcal {I}_{\boldsymbol{u}}} \textsf {H}(j)^{u_j} \end{array}$$

where $\mathcal {I}_{\boldsymbol{u}}, \mathcal {I}_{\boldsymbol{v}} \subset \mathbb {N}$ are the index sets of $\boldsymbol{u}, \boldsymbol{v}$ respectively, the hash function $\textsf {H}$ maps the indices to elements in $\mathbb {G}_2$ and $(q, \mathbb {G}_1, \mathbb {G}_2, \mathbb {G}_T, e)$ is a prime-order bilinear group. If the index sets are equal, i.e. $\mathcal {I}_{\boldsymbol{u}} = \mathcal {I}_{\boldsymbol{v}} = \mathcal {I}$ then one can use the key vector $\boldsymbol{u}$ to extract $[\![{\boldsymbol{u}} \cdot {\boldsymbol{v}}]\!]_T$ from the product $\prod _{j \in \mathcal {I}} C_j^{u_j}$ and a single pairing $e(C_0, \textsf {SK}_{\boldsymbol{u}})$. As a natural first step, we seek to utilize the DP-$\textsf{UIPFE}$ to upgrade an existing $\textsf{MA}\text {-}\textsf{ABE}$ to a small universe $\textsf{MA}\text {-}\textsf{ABUIPFE}$ scheme.

As the aim is to rely on the target-group-based assumption, we consider the $\textsf{DBDH}$-based $\textsf{MA}\text {-}\textsf{ABE}$ of Datta, Komargodski and Waters ($\text {DKW-}\textsf{MA}\text {-}\textsf{ABE}$) [21] for this upgrade. As a simpler first step, we investigate the primitive in the bounded and small universe setting, that is, the number of authorities and vector lengths are bounded and each authority controls a single attribute.

2.1.1 The First Step: A Bounded $\textsf{MA}\text {-}\textsf{ABIPFE}$ Scheme

Let us start by adding the functionality of $\textsf{IPFE}$ on top of $\text {DKW-}\textsf{MA}\text {-}\textsf{ABE}$. For each authority t, the public key and master secret key in the $\text {DKW-}\textsf{MA}\text {-}\textsf{ABE}$ construction are given by $\textsf{PK}_t = ([\![\alpha _t]\!]_T, [\![y_{t, 2}]\!]_1, \dots , [\![y_{t, s_{\textsf{max}}}]\!]_1 )$ and $\textsf{MSK}_t = (\alpha _t, y_{t, 2}, \dots , y_{t, s_{\textsf{max}}})$ where $s_{\textsf{max}}$ is a bound on the maximum number of columns in the $\textsf{LSSS}$ access structure and $\alpha _t, y_{t, 2}, \ldots , y_{t, s_{\textsf{max}}} \leftarrow \mathbb {Z}_q$. In order to construct an $\textsf{MA}\text {-}\textsf{ABIPFE}$ scheme from the $\text {DKW-}\textsf{MA}\text {-}\textsf{ABE}$, we convert the components of $\textsf{MSK}_t$ from scalars to vectors whose lengths are fixed according to the vector length bound of the system. All the other components are similarly upgraded to either vectors or matrices of fixed dimensions. In particular, the resulting $\textsf{MA}\text {-}\textsf{ABIPFE}$ derived from $\text {DKW-}\textsf{MA}\text {-}\textsf{ABE}$ can be described in the following way where $P = (\boldsymbol{\textrm{M}} = (M_{i, j})_{\ell \times s_{\textsf{max}}}, \rho : [\ell ] \rightarrow \mathcal{A}\mathcal{U})$ is the $\textsf{LSSS}$ access policy associated with the ciphertexts, $\mathcal{A}\mathcal{U}$ is the set of all authorities, and $\boldsymbol{M}_i$ denotes the i-th row of $\boldsymbol{\textrm{M}}$.

$$\begin{aligned} \textsf{PK}_t:&~~~~ ([\![\boldsymbol{\alpha }_t]\!]_T, [\![\boldsymbol{y}_{t, 2}]\!]_1, \dots , [\![\boldsymbol{y}_{t, s_{\textsf{max}}}]\!]_1 ) \\ \textsf{MSK}_t:&~~~~ (\boldsymbol{\alpha }_t, \boldsymbol{y}_{t, 2}, \dots , \boldsymbol{y}_{t, s_{\textsf{max}}}) \\ \textsf{CT}_{\boldsymbol{v}, P}:&~~~~ \begin{array}{r l r l} C_0 =&{} [\![\boldsymbol{v} + \boldsymbol{z}]\!]_T, &{} C_{1, i} = &{} [\![\boldsymbol{M}_i \boldsymbol{\textrm{B}} + r_i \boldsymbol{\alpha }_{\rho (i)}]\!]_T,\\ C_{2, i} =&{} [\![r_i]\!]_1, &{} C_{3, i, j} = &{} [\![M_{i, j} \boldsymbol{x}_j + r_i \boldsymbol{y}_{\rho (i), j}]\!]_1 ~~ \forall i \in [\ell ], j \in [2, s_{\textsf{max}}] \end{array} \\ \textsf{SK}_{\textsf{GID}, t, \boldsymbol{u}}:&~~~~ [\![{\boldsymbol{\alpha }_{t}} \cdot {\boldsymbol{u}}]\!]_2 \cdot \prod _{j=2}^{s_{\textsf{max}}} \textsf{H}(\textsf{GID}~ \Vert ~\boldsymbol{u} ~ \Vert ~j)^{{\boldsymbol{y}_{t, j}} \cdot {\boldsymbol{u}}}\\ \end{aligned}$$

where $\boldsymbol{z} \leftarrow \mathbb {Z}_q^n, r_i \leftarrow \mathbb {Z}_q$ and n represents the length of $\boldsymbol{u}, \boldsymbol{v}$. Further, $\boldsymbol{\textrm{B}} \in \mathbb {Z}_q^{s_{\textsf{max}}\times n}$ and $\{\boldsymbol{x}_j \leftarrow \mathbb {Z}_q^n\}_{j \in [2, s_{\textsf{max}}]}$ are the secret shares of $\boldsymbol{z}$ and $\boldsymbol{0}$ respectively. Recall that the decryption algorithm of $\textsf{MA}\text {-}\textsf{ABIPFE}$ requires a set of secret keys $\{\textsf{SK}_{\textsf{GID}, t, \boldsymbol{u}}\}_{t \in S}$ for the same user identifier $\textsf{GID}$ and an authorized subset S of attributes featuring in the $\textsf{LSSS}$ access policy associated with the ciphertext in order to decrypt it. Given such a collection of keys , the decryption algorithm gets rid of the masking term from $C_0\cdot \boldsymbol{u}$ by computing

$$\begin{aligned}{}[\![{\boldsymbol{u}} \cdot {\boldsymbol{z}}]\!]_T = \displaystyle \prod _{i \in I} \left[ \frac{ {C_{1, i}} \cdot {\boldsymbol{u}} \cdot \prod _{j = 2}^{s_{\textsf{max}}} e\left( \textsf{H}(\textsf{GID}~ \Vert ~\boldsymbol{u} ~ \Vert ~j), {C_{3, i, j}} \cdot {\boldsymbol{u}}\right) }{ e\left( \textsf{SK}_{\textsf{GID}, \rho (i), \boldsymbol{u}}, C_{2, i} \right) } \right] ^{w_i} \end{aligned}$$

(2.1)

where I represents the rows of $\boldsymbol{\textrm{M}}$ associated to S. Note that the Eq. (2.1) holds as the decryption algorithm can efficiently find a coefficients $\{w_i \in \mathbb {Z}_q\}_{i \in I}$ satisfying $(1, 0, \dots , 0) = \sum _{i \in I} w_i \boldsymbol{M}_i$ whenever the attributes linked to the rows in I satisfies the policy $(\boldsymbol{\textrm{M}}, \rho )$.

The role of the public hash function $\textsf {H}$ is to tie together a set of independently generated secret keys under the same user identifier $\textsf{GID}$ while decrypting. In the security proof, $\textsf {H}$ is treated as a random oracle to ensure that a fresh randomness is produced for each user identity $\textsf{GID}$ that links together the different secret keys generated for it and it is infeasible for an adversary to mix and match secret keys generated with respect to different global identifiers even if the attributes associated with those secret keys satisfy the access policy associated with the ciphertext.

In fact, the above bounded $\textsf{MA}\text {-}\textsf{ABIPFE}$ scheme can be proven secure in the static model under the $\textsf{DBDH}$ assumption. Let us now proceed to transform the bounded scheme into an unbounded one using the idea of DP-$\textsf{UIPFE}$ sketched above. Unfortunately, a straightforward approach does not work. In particular, we face a few difficulties while incorporating the hash and pairing mechanism of [38] with the $\text {DKW-}\textsf{MA}\text {-}\textsf{ABE}$ as we describe below.

2.1.2 Challenges in Expanding Authority Keys on the Fly and Our Approach

The foremost problem arises in vectorizing the components of the authority master secret keys $\textsf{MSK}_t$. This is because there being no upper bound on the length of vectors, we cannot simply use random vectors of predetermined sizes in the vectorization process. Rather, we must provision for generating the components of the vectors on the fly as needed during encryption/key generation. Similar to the idea of [38], we use hash functions modeled as random oracles in order to resolve this issue. More precisely,we proceed as follows: An authority t generates the public/master secret keys as $(\textsf{PK}_t = ([\![\alpha _t]\!]_T, [\![y_{t, 2}]\!]_1, \dots , [\![y_{t, s_{\textsf{max}}}]\!]_1 ), \textsf{MSK}_t = (\alpha _t, y_{t,2}, \ldots , y_{t, s_{\textsf{max}}}))$ without knowing the vector lengths where $\alpha , y_{t,2}, \ldots , y_{t,smx}$ are still scalars. To maintain the simplicity of this overview, we assume that the vectors $\boldsymbol{u} = (u_k)_{k \in \mathcal {I}_{\boldsymbol{u}}}$ and $\boldsymbol{v} = (v_k)_{k \in \mathcal {I}_{\boldsymbol{v}}}$ are both associated with the index set $\mathcal {I}_{\boldsymbol{u}} = \mathcal {I}_{\boldsymbol{v}} = \mathcal {I} = [n]$ which is unknown to the authority setup. Then the scalar $\alpha _t$ could be vectorized using a hash function $\textsf {H}_1$ as follows.

$$\begin{aligned} \text {during encryption}:&~~~~ C_{1, i} = [\![\boldsymbol{M}_i \boldsymbol{\textrm{B}} + \boldsymbol{\vartheta }_i]\!]_T\\&~~~~~~ \text {where } [\![\vartheta _{i, k}]\!]_T = e( r_i[\![\alpha _{\rho (i)}]\!]_1, \textsf {H}_1(\rho (i)~ \Vert ~k ~ \Vert ~\mathcal {I}))\\ \text {during key generation}:&~~~~ {\boldsymbol{\alpha }_{t}} \cdot {\boldsymbol{u}} = \prod _{k=1}^n \textsf {H}_1(t ~ \Vert ~k ~ \Vert ~\mathcal {I})^{\alpha _t \cdot u_k}\\ \end{aligned}$$

The next step is to vectorize the authority master secret key components $y_{t, j}$ according to the vector lengths. One may hope to apply [38] idea to extend $y_{t, j}$ to the same length of the vectors on the fly in a similar way. To see whether it works, let us assume that the hash function $\textsf {H}$ used in the key generation in the above bounded $\textsf{MA}\text {-}\textsf{ABIPFE}$ additionally takes an index position and an index set as inputs. That is, let us do the following modification for the key generation of the bounded $\textsf{MA}\text {-}\textsf{ABIPFE}$ scheme

Thus, using this idea, it is possible to expand $y_{t, j}$ to a vector $\boldsymbol{y}_{t, j}$ of the same length as the key vector $\boldsymbol{u}$ and eventually enabling an authority to compute the term while generating keys for an unbounded length vector. Note that, the hash value has $\textsf{GID}$ and $\boldsymbol{u}$ as inputs. Therefore, this would call for the following modification in the ciphertext computation.

However, such a vector $[\![\boldsymbol{y}_{t, j}]\!]_1$ is not known or rather the k-th element can not be computed during encryption. The main reason is that the global identity $\textsf{GID}$ and the vector $\boldsymbol{u}$ are available when an authority generates a secret key, but the encryption algorithm is oblivious of which $\textsf{GID}$ or $\boldsymbol{u}$ will be used to decrypt the ciphertext. In fact, it is natural that the same ciphertext would be decrypted by several users with different $\textsf{GID}$ and $\boldsymbol{u}$ vectors. Hence, a simple hash and pairing technique similar to DP-$\textsf{UIPFE}$ is not sufficient for a data owner to encrypt unbounded length vectors.

At this point, we devise a correlated “hash-decomposition” mechanism which enables us to compute the value of a hash function by combining the outputs of several hash functions applied on different segments of the input to the original hash function. More precisely, our idea is to define the hash value by grouping two independently generated hash values as

(2.2)

where $\textsf {H}_2$ and $\textsf {H}_3$ are two new public hash functions generated during global setup. Now, we observe that the first hash value in the product can be computed without knowing $\textsf{GID}$, which in turn enable the encryptor to expand an authority public key component $[\![y_{t, j}]\!]_1$ into a vector $[\![\boldsymbol{y}_{t, j}^{(2)}]\!]_T$ as . Similarly, an authority expands the master secret key component $y_{t, j}$ into vectors $[\![\boldsymbol{y}_{t, j}^{(2)}]\!]_2$ and $[\![\boldsymbol{y}_{t, j}^{(3)}]\!]_2$ as and respectively while generating a secret key for a vector $\boldsymbol{u}$. However, at this point, it is not immediate how would the vector $[\![\boldsymbol{y}_{t, j}^{(2)}]\!]_T$ be useful for the encryption algorithm.

Next, we carefully look into the decryption equation of the bounded $\textsf{MA}\text {-}\textsf{ABIPFE}$ scheme described above (Eq. (2.1)) and try to adapt it for the $\textsf{MA}\text {-}\textsf{ABUIPFE}$ setting with the modifications we did so far. We note that the pairing operation in the numerator can be rearranged with the hash function $\textsf {H}$ replaced by $\textsf {H}_2$ as

Since $\boldsymbol{u}$ is not available during encryption, we only compute the above term without multiplying by $\boldsymbol{u}$ and represent it as a single element

Therefore, the hash-decomposition mechanism allows the encryptor to simulate the first part of the hash value from Eq. (2.2) using the hash function $\textsf {H}_2$. The second part of the hash value still remains to be handled. For this, we generate an additional layer of secret share of zero by sampling $f_2, \dots , f_{s_{\textsf{max}}} \in \mathbb {Z}_q$ and introduce the encodings for all $i \in [\ell ], j \in [2, s_{\textsf{max}}]$ within the ciphertext. At the time of decryption, will be paired with the term . Thus, combining and via the hash-decomposition mechanism we are able to distribute the execution of the pairing operation from (Eq. (2.1)) among the encryption and decryption algorithms as follows:

Equipped with these concepts, we state our final $\textsf{MA}\text {-}\textsf{ABUIPFE}$ scheme below by assuming $\mathcal {I}_{\boldsymbol{u}} = \mathcal {I}_{\boldsymbol{v}} = \mathcal {I} = [n]$.

$$\begin{aligned} \textsf{PK}_t:&~~ ([\![\alpha _t]\!]_T, [\![y_{t, 2}]\!]_1, \dots , [\![y_{t, s_{\textsf{max}}}]\!]_1 ) \\ \textsf{MSK}_t:&~~ (\alpha _t, y_{t, 2}, \dots , y_{t, s_{\textsf{max}}}) \\ \textsf{CT}_{\boldsymbol{v}, P}:&~~ \begin{array}{r l } C_0 =&{} [\![\boldsymbol{v} + \boldsymbol{z}]\!]_T,~~~~ C_{1, i} = [\![\boldsymbol{M}_i \boldsymbol{\textrm{B}} + \boldsymbol{\vartheta }_{i}]\!]_T, ~~~~ C_{2, i} = [\![r_i]\!]_1,\\ C_{3, i, j, k} = &{} e([\![M_{i,j} x_{j, k}]\!]_1, \textsf {H}_2( j ~ \Vert ~k ~ \Vert ~\mathcal {I})) \cdot [\![r_i y_{\rho (i), j, k}^{(2)}]\!]_T , \\ C_{4, i, j} = &{} [\![M_{i, j}f_j + r_i y_{\rho (i), j}]\!]_1, ~~~~ \forall i \in [\ell ],~ j \in [2, s_{\textsf{max}}],~ k \in [n] \end{array} \\ \textsf{SK}_{\textsf{GID}, t, \boldsymbol{u}}:&~~~~ \prod _{k=1}^n \textsf {H}_1(t ~ \Vert ~k ~ \Vert ~\mathcal {I})^{\alpha _t \cdot u_k} \cdot \prod _{j=2}^{s_{\textsf{max}}} \prod _{k=1}^n ([\![y_{t, j, k}^{(2)}]\!]_2 \cdot [\![y_{t, j, k}^{(3)}]\!]_2)^{u_k} \\ \end{aligned}$$

The components $\boldsymbol{\vartheta }_{i}, y_{t, j, k}^{(2)}, y_{t, j, k}^{(3)}$ are defined as above. The decryption follows by canceling the masking term from $C_0 \cdot \boldsymbol{u}$ using a similar computation like in Eq. (2.1) executed as

$$\begin{aligned}{}[\![{\boldsymbol{u}} \cdot {\boldsymbol{z}}]\!]_T = \displaystyle \prod _{i \in I} \left[ \frac{ {C_{1, i}} \cdot {\boldsymbol{u}} \cdot \prod _{j = 2}^{s_{\textsf{max}}} C_{i, j}^{(3, 4)}(\boldsymbol{u})}{ e\left( \textsf{SK}_{\textsf{GID}, \rho (i), \boldsymbol{u}}, C_{2, i} \right) } \right] ^{w_i} \end{aligned}$$

(2.3)

We next look into the security of the proposed construction. Here again, we face several challenges while adapting the security proof of [21, 38] into our setting.

2.1.3 Challenges in the Security Analysis and Our Approach

The main difference between the $\textsf{MA}\text {-}\textsf{ABE}$ and $\textsf{MA}\text {-}\textsf{ABUIPFE}$ security model is in the secret key queries made by the adversary. This is because $\textsf{MA}\text {-}\textsf{ABUIPFE}$ is more like an $\textsf{FE}$ scheme and the adversary is entitled to ask for secret keys that would decrypt the challenge ciphertext which is in contrast to any $\textsf{MA}\text {-}\textsf{ABE}$ scheme where only non-authorized keys are released. On the other hand, proving security of $\textsf{MA}\text {-}\textsf{ABUIPFE}$ is more technically challenging compared to the (bounded) $\textsf{MA}\text {-}\textsf{ABIPFE}$ (like AGT-$\textsf{FE}$ [9]) as an authorized key which always leads to a successful decryption in case of $\textsf{MA}\text {-}\textsf{ABIPFE}$, may not be eligible for decrypting a ciphertext of $\textsf{MA}\text {-}\textsf{ABUIPFE}$. The index set associated with the authorized key must match to the index set of the encrypted vector for successful decryption in $\textsf{MA}\text {-}\textsf{ABUIPFE}$. In other words, the adversary should be restricted to infer any information about the encrypted message vector from the authorized keys whose index sets are not equal to the index set of the message vector. Moreover, AGT-$\textsf{FE}$ is proven secure under subgroup decision assumptions which are source group assumptions while our target is to prove security under $\textsf{DBDH}$ which is a target group assumption, thus the dual system encryption technique [41] used for the security proof of AGT-$\textsf{FE}$ does not work in our case. Hence, we design a different proof strategy that works coherently with the hash-decomposition mechanism and for target group assumptions in the prime-order bilinear group.

We prove the security of our $\textsf{MA}\text {-}\textsf{ABUIPFE}$ in the static model similar to the $\text {DKW-}\textsf{MA}\text {-}\textsf{ABE}$. The adversary is asked to submit all it’s queries including the challenge message vectors $\boldsymbol{v}_0, \boldsymbol{v}_1$ with a common index set $\mathcal {I}^*$ and an associated challenge access structure $(\boldsymbol{\textrm{M}}, \rho )$. Recall that the adversary can also corrupt or even maliciously generate some of the authorities indicated by a set $\mathcal {C}$ of corrupted authorities or attributes. Let us consider a $\textsf{DBDH}$ instance $([\![a]\!]_1, [\![b]\!]_2, [\![c]\!]_1, [\![\tau ]\!]_T)$ where $\tau$ is either abc or random. In the first step, we use the information-theoretic partitioning lemma, the so-called “zero-out” lemma [36, Lemma 1], to isolate and ignore the set of rows of $\boldsymbol{\textrm{M}}$ that correspond to the corrupted authorities throughout the analysis. In particular, the lemma allows us to replace the $\textsf{LSSS}$ matrix $\boldsymbol{\textrm{M}}$ with an updated simpler matrix $\boldsymbol{\textrm{M}}'$ such that a subset of columns, say $C_{\boldsymbol{\textrm{M}}'}$, of $\boldsymbol{\textrm{M}}'$ can be set to zero that are related to the corrupted authorities. Next, we follow the proof techniques of [3, 38] and sample a basis $\widetilde{S} = \{(\boldsymbol{v}_0 - \boldsymbol{v}_1), \boldsymbol{b}_2, \dots , \boldsymbol{b}_n \}$ of $\mathbb {Z}_q^n$ where n denotes the size of $\mathcal {I}^*$ to represent key vectors $\boldsymbol{u}$ whose lengths are equal to n. However, answering the hash and secret key queries require a careful treatment while embedding the $\textsf{DBDH}$ challenge instance. The role of the hash function of $\text {DKW-}\textsf{MA}\text {-}\textsf{ABE}$ was limited to simulating the non-authorized keys of a fixed length. However, in our case, we need to deal with both authorized and unauthorized keys and here again, our hash-decomposition mechanism plays a crucial role. Moreover, a key can be non-authorized with respect to the index set or the associated policy, or both.

Let S be the set of attributes queried under a user identifier $\textsf{GID}$ as a part of secret key queries such that S contains at least an attribute involved in the challenge policy. The main idea of simulating secret keys of $\text {DKW-}\textsf{MA}\text {-}\textsf{ABE}$ was to sample a special vector $\boldsymbol{d} \in \mathbb {Z}_q^{s_{\textsf{max}}}$ such that the inner product of $\boldsymbol{d}$ with $\boldsymbol{M}'_i$ is zero for all $i \in \rho ^{-1}(S \cup \mathcal {C})$ and to set the hash values as

$$\begin{aligned} \textsf {H}(\textsf{GID}~ \Vert ~j) = (g_2^b)^{d_j}\cdot g_2^{h_j}, ~\forall j \in C_{\boldsymbol{\textrm{M}}'}, \text { and uniform otherwise.} \end{aligned}$$

(2.4)

This, in fact, enables in simulating the secret keys using the properties of $\boldsymbol{d}$ and by embedding the matrix $\boldsymbol{\textrm{M}}'$ into the public keys of authorities linked to the challenge policy. Unfortunately, we observe that such encoding of hash values is not compatible with our hash-decomposition mechanism. Firstly, the hash function $\textsf {H}_2$ does not take a $\textsf{GID}$ as input and hence it is not possible to encode the hash values depending on a vector like $\boldsymbol{d}$ which is sampled according to an unauthorized set of attributes $(S \cup \mathcal {C})$ under a given global identity. In our case, $\textsf {H}_2$ should generate a good amount of entropy for indices of key vectors irrespective of any global identity. This would restrict an adversary to gain any illegitimate information about the encrypted message from any secret key where the associated index set does not match with $\mathcal {I}^*$ even though the attributes associated to the key satisfy the challenge policy. Secondly, $\textsf {H}_3$ takes a $\textsf{GID}$ as it’s input along with a key vector, a column number and an index set. The role of $\textsf {H}_3$ is to make a secret key generated under a given $\textsf{GID}$ useless to the adversary whenever the associated attributes does not satisfy the challenge policy.

In the static security model the simulator knows all the secret key queries in advance. We exploit this fact to prepare encodings for the hash values keeping in mind their roles in the security experiment. Our idea is to sample all possible $\{\boldsymbol{d}_{\phi }\}_{\phi }$ vectors corresponding to the sets $\{S_{\phi } \cup \mathcal {C}\}_{\phi }$ such that $S_{\phi } \cup \mathcal {C}$ constitutes an unauthorized subset of row of $\boldsymbol{\textrm{M}}$ and use the information of $\{\boldsymbol{d}_{\phi }\}_{\phi }$ in the encodings of the hash functions. More precisely, we use an add and subtract technique to set the hash values as follows

$$\begin{aligned} \textsf {H}_2(j ~ \Vert ~k ~ \Vert ~\mathcal {I}^*) = (g_2^b)^{\sum _{\phi } d_{\phi , j}}\cdot g_2^{h_{2, j}}, ~\forall j \in C_{\boldsymbol{\textrm{M}}'}, \text { and uniform otherwise.} \\ \textsf {H}_3(\textsf{GID}~ \Vert ~\boldsymbol{u}_{\phi '} ~ \Vert ~j ~ \Vert ~k) = (g_2^b)^{\sum _{\phi \ne \phi '} - d_{\phi ,j}} \cdot g_2^{h_{3, j}}, ~\forall j \in C_{\boldsymbol{\textrm{M}}'}, \text { and uniform otherwise.} \end{aligned}$$

Now, we multiply the above hash encodings while simulating non-authorized secret key queries and obtain a hash encoding similar to Eq. (2.4).

$$\begin{aligned} \textsf {H}_2(j ~ \Vert ~k ~ \Vert ~\mathcal {I}^*) \cdot \textsf {H}_3(\textsf{GID}~ \Vert ~\boldsymbol{u}_{\phi '} ~ \Vert ~j ~ \Vert ~k) = (g_2^b)^{d_{\phi ', j}}\cdot g_2^{h_{2, j}+h_{3, j}}~\forall j \in C_{\boldsymbol{\textrm{M}}'}. \end{aligned}$$

For simplicity of this section, we have ignored a few additional elements in the above encodings that connect the hash values with the $\textsf {H}_1$ encodings which actually facilitates in using the fact that ${\boldsymbol{d}_{\phi }} \cdot {\boldsymbol{M}_i'} = 0$ for all $i \in \rho ^{-1}(S_{\phi } \cup \mathcal {C})$ for non-authorized keys such that $\mathcal {I}_{\boldsymbol{u}_{\phi }} = \mathcal {I}^*$. Lastly, when simulating authorized secret keys we use the basis $\widetilde{S}$ to obtain a vector $\boldsymbol{\eta }$ satisfying ${\boldsymbol{\eta }} \cdot {\boldsymbol{u}_{\phi }} = 0$ with the help of the admissibility condition ${\boldsymbol{u}_{\phi }} \cdot {(\boldsymbol{v}_0-\boldsymbol{v}_1)} = 0$ for all keys leading to a successful decryption of the challenge ciphertext. The full security analysis can be found in Sect. 5.3.

2.2 Constructing the Large Universe $\textsf{MA}\text {-}\textsf{ABUIPFE}$

We recall that in the large universe setting each authority is allowed to control exponentially many attributes. We upgrade our small universe scheme to a large universe $\textsf{MA}\text {-}\textsf{ABUIPFE}$ $(\textsf{LMA}\text {-}\textsf{ABUIPFE})$ by extending the techniques presented in [36] from encrypting a fixed length message to encrypting an unbounded length vector in the context of $\textsf{MA}\text {-}\textsf{ABUIPFE}$. To support exponentially many attributes, we use an additional hash function $\textsf{R}$ which maps arbitrary attributes to elements of $\mathbb {G}_2$. We replace the map $\rho$ of the $\textsf{LSSS}$ access structure $(\boldsymbol{\textrm{M}}, \rho )$ by decomposition of two mappings $\textsf {T}$ and $\delta$, that is $\rho (i) = \textsf {T}(\delta (i)) = \theta$ where $\delta$ labels row numbers i of the $\textsf{LSSS}$ access matrix to some attributes $\delta (i)$ and $\textsf {T}$ assigns the attributes $\delta (i)$ to its respective authorities denoted by $\theta$. Our $\textsf{LMA}\text {-}\textsf{ABUIPFE}$ is described as follows.

$$\begin{aligned} \textsf{PK}_{\theta }:&~~ ([\![\alpha _{\theta }]\!]_T, [\![y_{\theta , 2}]\!]_1, \dots , [\![y_{\theta , s_{\textsf{max}}}]\!]_1 ) \\ \textsf{MSK}_{\theta }:&~~ (\alpha _{\theta }, y_{\theta , 2}, \dots , y_{\theta , s_{\textsf{max}}}) \\ \textsf{CT}_{\boldsymbol{v}, P}:&~~ \begin{array}{r l } C_0 =&{} [\![\boldsymbol{v} + \boldsymbol{z}]\!]_T,~~~~ C_{1, i} = [\![\boldsymbol{M}_i \boldsymbol{\textrm{B}} + \boldsymbol{\vartheta }_{i}]\!]_T, ~~~~ C_{2, i} = [\![r_i]\!],\\ C_{3, i, j, k} = &{} e([\![M_{i,j} x_{j, k}]\!]_1, \textsf {H}_2( j ~ \Vert ~k ~ \Vert ~\mathcal {I})) \cdot [\![r_i y_{\rho (i), j, k}^{(2)}]\!]_T , \\ C_{4, i, j} = &{} [\![M_{i, j}f_j + r_i y_{\rho (i), j}]\!]_1, ~~ C_{5, i, j} = \textsf {R}(\delta (i)~ \Vert ~j ~ \Vert ~\mathcal {I})\\ {} &{} ~~~~ \forall i \in [\ell ],~ j \in [2, s_{\textsf{max}}],~ k \in [n] \end{array} \\ \textsf{SK}_{\textsf{GID}, t, \boldsymbol{u}}:&~~ \begin{array}{l} \displaystyle \prod _{k=1}^n \textsf {H}_1(t ~ \Vert ~k ~ \Vert ~\mathcal {I})^{\alpha _{\theta } \cdot u_k} \cdot \prod _{j=2}^{s_{\textsf{max}}} \prod _{k=1}^n ([\![y_{\theta , j, k}^{(2)}]\!]_2 \cdot [\![y_{\theta , j, k}^{(3)}]\!]_2)^{u_k} \cdot \prod _{j=1}^{s_{\textsf{max}}} \textsf {R}(t~ \Vert ~j ~ \Vert ~\mathcal {I})^{\tau _j},\\ \textsf {Z}_{t, j} = [\![\tau _j]\!]_1,~~\forall j \in [s_{\textsf{max}}] \end{array} \\ \end{aligned}$$

The components $\boldsymbol{\vartheta }_i, \boldsymbol{y}_{\theta , j}^{(2)}, \boldsymbol{y}_{\theta , j}^{(3)}$ are defined similarly as in our $\textsf{MA}\text {-}\textsf{ABUIPFE}$ scheme.

$$\begin{aligned}{}[\![\vartheta _{i, k}]\!]_T&= e( r_i[\![\alpha _{\rho (i)}]\!]_1, \textsf {H}_1(\rho (i)~ \Vert ~k ~ \Vert ~\mathcal {I}_{\boldsymbol{v}})),\\ [\![y_{\theta , j, k}^{(2)}]\!]_T&=e( [\![y_{\theta , j}]\!]_1, \textsf {H}_2(j ~ \Vert ~k~ \Vert ~\mathcal {I})) ,~~[\![y_{\theta , j, k}^{(2)}]\!]_2 = \textsf {H}_2(j ~ \Vert ~k~ \Vert ~\mathcal {I})^{y_{\theta , j}},\\ [\![y_{\theta , j, k}^{(3)}]\!]_2&= \textsf {H}_3(\textsf{GID}~ \Vert ~\boldsymbol{u} ~ \Vert ~j ~ \Vert ~k)^{y_{\theta , j}},~~\forall k \in [n]. \end{aligned}$$

The decryption procedure is similar to our $\textsf{MA}\text {-}\textsf{ABUIPFE}$ scheme. We consider static security of $\textsf{LMA}\text {-}\textsf{ABUIPFE}$ and model the hash functions as random oracles. However, it may not be possible to base security on the plain $\textsf{DBDH}$ assumption. Following the same notations that we used to sketch the proof technique of our $\textsf{MA}$-$\textsf{AB}\textsf{U}\textsf{IPFE}$, we discuss the main reason which prevent using the $\textsf{DBDH}$ assumption as before. The $\textsf{R}$-values related to the authorities in the challenge policy in our proposed $\textsf{LMA}\text {-}\textsf{ABUIPFE}$ scheme described above are roughly set as $\textsf{R}(t ~ \Vert ~j ~ \Vert ~\mathcal {I}^*) = g_2^{\zeta _{t, j}} g_2^{a M_{i, j}'}$, where $\zeta _{t, j}$ is a random $\mathbb {Z}_q$-element and $M_{i, j}'$ is the (i, j)-th entry of the updated $\textsf{LSSS}$ matrix $\boldsymbol{\textrm{M}}'$ in the challenge policy. On the other hand, the randomness $r_i$ used in the encryption² are set as $r_i = c$. Hence, the reduction requires the group element $g_2^{ac}$ in order to simulate the components $C_{5, i, j}$ of the challenge ciphertext. However, the $\textsf{DBDH}$ assumption does not make it possible to make $g^{ac}$ available to an adversary.

Thus, for basing the security, we look into the parameterized versions of the $\textsf{DBDH}$ assumptions. Unlike [36] where they consider a much more complex parameterized assumption, a primary motivation of our security reduction is to depend on a simpler parameterized assumption that is as close as possible to the plain $\textsf{DBDH}$ assumption. More specifically, [36] consider an exponent type assumption where each instance consists of at least $O(L_{\textsf{max}}^3)$ group elements and $L_{\textsf{max}} \ge \text {max}\{\ell , s_{\textsf{max}}\}$, where $\ell ,s_{\textsf{max}}$ is the number of rows and columns of the challenge $\textsf{LSSS}$ access matrix respectively. Consequently, the reduction becomes more involved and complex. In contrast, we prove the security of $\textsf{LMA}\text {-}\textsf{ABUIPFE}$ based on the newly introduced $L\text {-}\textsf{DBDH}$ assumption where each instance has $O(L^2)$ group elements with $L \ge \ell$. We show that the $L\text {-}\textsf{DBDH}$ assumption is generically secure using the techniques of [12, 36]. Although incomparable with the assumption used in [36], it seems that our $L\text {-}\textsf{DBDH}$ assumption is weaker as it contains fewer elements. Therefore, our $\textsf{LMA}\text {-}\textsf{ABUIPFE}$ improves upon the previous results of [36] even without considering the enhanced functionality of $\textsf{UIPFE}$.

There are some other technical hurdles in the security reduction that does not directly allow using the program and cancel technique similar to [36] while simulating secret key queries. This is due to the fact that we are handling unbounded length messages and using a hash-decomposition mechanism on top of large universe paradigm. In contrast to the small universe scheme, an authority in a queried secret key of $\textsf{LMA}\text {-}\textsf{ABUIPFE}$ may be present in the challenge policy but none of their attributes are linked to it. We use our add and subtract technique which enables the reduction to combine the decomposed hash values into a single hash value that eventually produces an adequate amount of randomness preventing the leakage of unwanted information about the underlying message vector from such secret keys.

On the other hand, if the authorities as well as some of their controlled attributes are present in the challenge policy but the associated secret key is unauthorized then we observe that the program and cancel technique of [36] is not sufficient to handle an adversary of $\textsf{LMA}\text {-}\textsf{ABUIPFE}$ given the fact that it can query for secret keys corresponding to vectors of arbitrary lengths. In order to make these secret keys useless for an adversary irrespective of the associated lengths of vectors, we delicately program the hash queries that enables the reduction to procreate additional entropy via an interplay between the program and cancel technique of [36] and add and subtract mechanism of ours at the time of simulating such unauthorized secret keys. Although the high-level proof technique is inspired from [36], the technical obstacles mentioned above prevent applying their approach straightforwardly into our setting. As a whole, we carefully embed the L-$\textsf{DBDH}$ instance into the adversary’s queries by extending the [36] technique in the context of amplifying entropy for supporting computation over unbounded length vectors and at the same time making it compatible for hash-decomposition mechanism used in our scheme. We present a detailed security analysis in the full version.

3 Preliminaries

In this section, we present the notations used in this paper and the new L-$\textsf{DBDH}$ assumption we introduce.

3.1 Notations

We will denote the underlying security parameter by $\lambda$ throughout the paper. A function $\textsf{negl}: \mathbb {N} \rightarrow \mathbb {R}$ is said to be a negligible function of $\lambda$, if for every $c \in \mathbb {N}$, there exists a $\lambda _c \in \mathbb {N}$ such that $\forall \lambda > \lambda _c$, $\textsf{negl}(\lambda )< \lambda ^{-c}$. We denote the set of positive integers $\{1, \ldots , n\}$ as [n]. We denote $\emptyset$ as the empty set. We use the abbreviation $\textsf{PPT}$ for probabilistic polynomial-time. For a set X, we write $x\leftarrow X$ to denote that x is sampled according to the uniform distribution over the elements of X. Also for any set X, we denote by $|{X}|$ and $2^X$ the cardinality and the power set of the set X respectively. We use bold lower case letters, such as $\boldsymbol{v}$, to denote vectors and upper-case, such as $\boldsymbol{\textrm{M}}$, for matrices. We assume all vectors, by default, are row vectors. The $i^{\text {th}}$ row of a matrix is denoted by $\boldsymbol{M}_i$ and analogously for a set of row indices I, we denote $\boldsymbol{\textrm{M}}_I$ for the sub-matrix of $\boldsymbol{\textrm{M}}$ that consists of the rows $\boldsymbol{\textrm{M}}_i, \forall i\in I$. By $\textsf{rowspan}(\boldsymbol{\textrm{M}})$, we denote the linear span of the rows of a matrix $\boldsymbol{\textrm{M}}$.

For an integer $q\ge 2$, we let $\mathbb {Z}_q$ denote the ring of integers modulo q. We represent $\mathbb {Z}_q$ as integers in the range $(-q/2,q/2]$. The set of matrices of size $m \times n$ with elements in $\mathbb {Z}_q$ is denoted by $\mathbb {Z}_q^{m\times n}$. The operation $(\cdot )^\top$ denotes the transpose of vectors/matrices. Let $\boldsymbol{u} = (u_i)_{i \in \mathcal {I}_{\boldsymbol{u}}} \in \mathbb {Z}_q^{|\mathcal {I}_{\boldsymbol{u}}|} , \boldsymbol{v} = (v_i)_{i \in \mathcal {I}_{\boldsymbol{v}}} \in \mathbb {Z}_q^{|\mathcal {I}_{\boldsymbol{v}}|}$ where $\mathcal {I}_{\boldsymbol{u}}$ and $\mathcal {I}_{\boldsymbol{v}}$ are the associated index sets, then the inner product between the vectors is denoted as ${\boldsymbol{v}} \cdot {\boldsymbol{u}} = \boldsymbol{u}^{\top } \boldsymbol{u} = \sum _{i \in \mathcal {I}} u_i v_i \in \mathbb {Z}_q$ whenever $\mathcal {I}_{\boldsymbol{u}} = \mathcal {I}_{\boldsymbol{v}} = \mathcal {I}$.

3.2 Complexity Assumptions

We use bilinear groups of prime order to build our $\textsf{MA}\text {-}\textsf{ABUIPFE}$ schemes.

Here, we formally define the $\textsf{DBDH}$ assumption and a parameterized version of it, we call L-$\textsf{DBDH}$ which would underlie of security of our small and large universe $\textsf{MA}\text {-}\textsf{ABUIPFE}$ schemes respectively.

Assumption 3.1

(Decisional Bilinear Diffie-Hellman ($\boldsymbol{\textsf{DBDH}}$ ). [14, 38]) For a security parameter $\lambda \in \mathbb {N}$, let $\textsf{G} = (q, \mathbb {G}_1, \mathbb {G}_2, \mathbb {G}_T, g, e) \leftarrow \mathcal {G}(1^{\lambda })$ be a bilinear group and let $a, b, c \leftarrow \mathbb {Z}_q$. The $\textsf{DBDH}$ assumption states that for any $\textsf{PPT}$ adversary $\mathcal {A}$, there exists a negligible function $\textsf{negl}$ such that for any security parameter $\lambda \in \mathbb {N}$, given the distribution $\left( \textsf{G}, [\![a]\!]_1, [\![c]\!]_1, [\![a]\!]_2, [\![b]\!]_2, [\![\tau ]\!]_T\right)$, $\mathcal {A}$ has advantage

$$\textsf{Adv}_{\mathcal {A}}^{\textsf{DBDH}}(\lambda ) = \left| \Pr \left[ 1 \leftarrow \mathcal {A}\left( 1^{\lambda }, \mathcal {D}, [\![abc]\!]_T\right) \right] - \Pr \left[ 1\leftarrow \mathcal {A}\left( 1^{\lambda }, \mathcal {D}, [\![\tau ]\!]_T\right) \right] \right| \le \textsf{negl}(\lambda ),$$

Assumption 3.2

($\boldsymbol{L}$-Decisional Bilinear Diffie-Hellman ($\boldsymbol{L}$-$\boldsymbol{\textsf{DBDH}}$)). Let $\textsf{G} = (q, \mathbb {G}_1, \mathbb {G}_2, \mathbb {G}_T, g, e) \leftarrow \mathcal {G}(1^{\lambda })$ be a bilinear group and let $a, b, c, \mu _1,\ldots , \mu _L\leftarrow \mathbb {Z}_q$. The L-$\textsf{DBDH}$ assumption states that for any $\textsf{PPT}$ adversary $\mathcal {A}$, there exists a negligible function $\textsf{negl}$ such that for any security parameter $\lambda \in \mathbb {N}$, given the distribution

$$\left( \textsf{G}, \begin{pmatrix} [\![b]\!]_1, [\![c]\!]_1, \\ [\![a]\!]_2, [\![b]\!]_2\end{pmatrix}, \left\{ \begin{matrix} [\![a\mu _i]\!]_1, [\![c/\mu _i]\!]_1, \\ [\![a\mu _i]\!]_2 \end{matrix}\right\} _{i \in [L]}, \left\{ \begin{matrix}[\![c\mu _{\iota }/\mu _i]\!]_1, [\![ ac \mu _{\iota }/\mu _i]\!]_1, \\ [\![ ac \mu _{\iota }/\mu _i]\!]_2\end{matrix}\right\} _{\begin{array}{c} i, \iota \in [L], \\ i \ne \iota \end{array}}, [\![\tau ]\!]_T\right) $$

$\mathcal {A}$ has advantage

$$\textsf{Adv}_{\mathcal {A}}^{L\text {-}\textsf{DBDH}}(\lambda ) = \left| \Pr \left[ 1 \leftarrow \mathcal {A}\left( 1^{\lambda }, \mathcal {D}, [\![abc]\!]_T\right) \right] - \Pr \left[ 1\leftarrow \mathcal {A}\left( 1^{\lambda }, \mathcal {D}, [\![\tau ]\!]_T\right) \right] \right| \le \textsf{negl}(\lambda ),$$

4 Decentralized (Large Universe) $\textsf{MA}\text {-}\textsf{ABUIPFE}$ for $\textsf{LSSS}$

A large universe decentralized multi-authority attribute-based inner-product functional encryption ($\textsf{LMA}\text {-}\textsf{ABUIPFE}$) scheme $\textsf{LMA}\text {-}\textsf{ABUIPFE}= (\textsf{GlobalSetup}, \textsf{LocalSetup}, \textsf{KeyGen}, \textsf{Encrypt}, \textsf{Decrypt})$ for access structures captured by linear secret sharing schemes ($\textsf{LSSS}$) over some finite field $\mathbb {Z}_q$ with $q=q(\lambda )$ and inner product value space $\mathcal {U}$ consists of five algorithms with the following syntax. We denote by $\mathcal{A}\mathcal{U}$ the authority universe and by $\mathcal {GID}$ the universe of users’ global identifiers in the system. The attribute universe is denoted as $\textsf{U}_\textsf{att}$ which may be arbitrary. Further, an authority $\theta \in \mathcal{A}\mathcal{U}$ may have any arbitrary number of attributes from $\textsf{U}_\textsf{att}$ under its control. Following [36], we assume a publicly computable function $\textsf{T}: \textsf{U}_\textsf{att}\rightarrow \mathcal{A}\mathcal{U}$ that maps each attribute $t\in \textsf{U}_\textsf{att}$ to a unique authority $\theta = T(t)$. The algorithms proceed as follows:

$\boldsymbol{\textsf{GlobalSetup}(1^{\lambda }, s_{\textsf{max}})}$: It is the global setup algorithm which on input the security parameter $\lambda$ and a maximum width $s_{\textsf{max}}$ of the $\textsf{LSSS}$ matrix, and outputs the global public parameters $\textsf{GP}$. We assume that $\textsf{GP}$ includes the descriptions of $\mathcal{A}\mathcal{U}$ and $\mathcal {GID}$.

$\boldsymbol{\textsf{LocalSetup}(\textsf{GP}, \theta )}$: The authority $\theta \in \mathcal{A}\mathcal{U}$ runs the local setup algorithm during its initialization with the global parameters $\textsf{GP}$ and generates its public parameters and a master secret key pair $(\textsf{PK}_\theta , \textsf{MSK}_\theta )$.

$\boldsymbol{\textsf{KeyGen}(\textsf{GP}, \textsf{GID}, \textsf{MSK}_\theta , t, \boldsymbol{u}, \mathcal {I}_{\boldsymbol{u}})}$: The key generation algorithm takes input the global parameter $\textsf{GP}$, a user’s global identifier $\textsf{GID}\in \mathcal {GID}$, a master secret key $\textsf{MSK}_\theta$ for authority $\theta$ controlling an attribute $t\in \textsf{U}_\textsf{att}$, and a vector $\boldsymbol{u} \in \mathbb {Z}_q^{|\mathcal {I}_{\boldsymbol{u}}|}$ with an associated index set $\mathcal {I}_{\boldsymbol{u}}$. It outputs a secret key $\textsf{SK}_{\textsf{GID}, t, \boldsymbol{u}}$ which contains $(\boldsymbol{u}, \mathcal {I}_{\boldsymbol{u}})$.

$\boldsymbol{\textsf{Encrypt}(\textsf{GP}, (\boldsymbol{\textrm{M}}, \delta ), \{\textsf{PK}_\theta \}_\theta , \boldsymbol{v}, \mathcal {I}_{\boldsymbol{v}})}$: The encryption algorithm takes input the global parameter $\textsf{GP}$, an $\textsf{LSSS}$ access structure $(\boldsymbol{\textrm{M}}, \delta )$ where $\boldsymbol{\textrm{M}}$ is a matrix over $\mathbb {Z}_q$ and $\delta$ is a row-labeling function that assigns to each row of $\boldsymbol{\textrm{M}}$ an attribute in $\textsf{U}_\textsf{att}$. We define the function $\rho : [\ell ] \rightarrow \mathcal{A}\mathcal{U}$ as $\rho (\cdot ) := \textsf{T}(\delta (\cdot ))$ which maps row indices of $\boldsymbol{\textrm{M}}$ to authorities $\theta \in \mathcal{A}\mathcal{U}$. Accordingly, the encryption algorithm further takes a set $\{\textsf{PK}_\theta \}_\theta$ of public keys for all the authorities in the range of $\rho$, and a message vector $\boldsymbol{v} \in \mathbb {Z}_q^{|\mathcal {I}_{\boldsymbol{v}}|}$ with an associated index set $\mathcal {I}_{\boldsymbol{v}}$. It outputs a ciphertext $\textsf{CT}$. We assume that $\textsf{CT}$ implicitly contains the description of $(\boldsymbol{\textrm{M}}, \delta )$ and $\mathcal {I}_{\boldsymbol{v}}$.

$\boldsymbol{\textsf{Decrypt}(\textsf{GP}, \textsf{GID}, \textsf{CT}, \{\textsf{SK}_{\textsf{GID}, t, \boldsymbol{u}}\}_t)}$: The decryption algorithm takes in the global parameters $\textsf{GP}$, a ciphertext $\textsf{CT}$ generated with respect to some $\textsf{LSSS}$ access policy $(\boldsymbol{\textrm{M}},\delta )$ and an index set $\mathcal {I}$ associated to the message, and a collection of keys $\{\textsf{SK}_{\textsf{GID},t,\boldsymbol{u}}\}_t$ corresponding to user ID-attribute pairs $(\textsf{GID}, S \subseteq \textsf{U}_\textsf{att})$ and a key vector $(\boldsymbol{u}, \mathcal {I}_{\boldsymbol{u}})$ possessed by a user with global identifier $\textsf{GID}$. It outputs a message $\zeta$ when the collection of attributes associated with the secret keys $\{\textsf{SK}_{\textsf{GID},t, \boldsymbol{u}}\}_t$ satisfies the $\textsf{LSSS}$ access policy $(\boldsymbol{\textrm{M}},\delta )$, i.e., when the vector $(1,0,\ldots ,0)$ belongs to the linear span of those rows of $\boldsymbol{\textrm{M}}$ which are mapped by $\delta$ to the set of attributes in S that corresponds to the secret keys $\{\textsf{SK}_{\textsf{GID},t, \boldsymbol{u}}\}_{t \in S}$ possessed by the user with global identifier $\textsf{GID}$. Otherwise, decryption returns $\perp$.

Correctness: An $\textsf{LMA}\text {-}\textsf{ABUIPFE}$ scheme for $\textsf{LSSS}$-realizable access structures and inner product message space $\mathcal {U}$ is said to be correct if for every $\lambda \in \mathbb {N}$, every message vector $\boldsymbol{v} \in \mathbb {Z}_q^{|\mathcal {I}_{\boldsymbol{v}}|}$, key vector $\boldsymbol{u} \in \mathbb {Z}_q^{|\mathcal {I}_{\boldsymbol{u}}|}$ such that $\mathcal {I} = \mathcal {I}_{\boldsymbol{v}} = \mathcal {I}_{\boldsymbol{u}}$, and $\textsf{GID}\in \mathcal {GID}$, every $\textsf{LSSS}$ access policy $(\boldsymbol{\textrm{M}},\delta )$, and every subset of authorities $S \subseteq \textsf{U}_\textsf{att}$ controlling attributes which satisfy the access structure it holds that

$$\Pr \left[ \varGamma = {\boldsymbol{v}} \cdot {\boldsymbol{u}} \; \left| \; \begin{array}{c} \textstyle \textsf{GP}\leftarrow \textsf{GlobalSetup}(1^{\lambda },1^n), \\ \textstyle (\textsf{PK}_\theta ,\textsf{MSK}_\theta ) \leftarrow \textsf{LocalSetup}(\textsf{GP},\theta ), \\ \textstyle \textsf{SK}_{\textsf{GID},t, \boldsymbol{u}} \leftarrow \textsf{KeyGen}(\textsf{GP},\textsf{GID},\textsf{MSK}_{\theta }, t, \boldsymbol{u}), \\ \textstyle \textsf{CT}\leftarrow \textsf{Encrypt}(\textsf{GP}, (\boldsymbol{\textrm{M}},\delta ), \{\textsf{PK}_\theta \}_\theta ,\boldsymbol{v}),\\ \textstyle \varGamma = \textsf{Decrypt}(\textsf{GP},\textsf{CT}, \{\textsf{SK}_{\textsf{GID},t, \boldsymbol{u}}\}_{t\in S}) \end{array} \right. \right] = 1.$$

Static Security: In this paper, we consider static security for $\textsf{LMA}\text {-}\textsf{ABUIPFE}$ formalized by the following game between a challenger and an adversary. The static security model is adapted from [36], defined for $\textsf{MA}\text {-}\textsf{ABE}$, to the context of $\textsf{LMA}\text {-}\textsf{ABUIPFE}$. We emphasize that unlike $\textsf{MA}\text {-}\textsf{ABE}$, our static security model allows the adversary to ask for secret keys which are capable of decrypting the challenge ciphertext.

• Global Setup: The challenger runs $\textsf{GlobalSetup}(1^{\lambda },s_{\textsf{max}})$ to get and send the global public parameters $\textsf{GP}$ to the attacker.

• Adversary’s Queries: The adversary sends the following queries:

  • 1. A list $\mathcal {C} \subset \mathcal{A}\mathcal{U}$ of corrupt authorities and their respective public parameters $\{\textsf{PK}_\theta \}_{\theta \in \mathcal {C}}$, which it might have created in a malicious way.

  • 2. A set $\mathcal {N} \subset \mathcal{A}\mathcal{U}$ of non-corrupt authorities, i.e., $\mathcal {C} \cap \mathcal {N} = \emptyset$, for which the adversary requests the public keys.

  • 3. A set $\mathcal {Q} = \{(\textsf{GID}, S, \boldsymbol{u}, \mathcal {I}_{\boldsymbol{u}})\}$ of secret key queries with $\textsf{GID}\in \mathcal {GID}, S\subseteq \textsf{U}_\textsf{att}$ such that $\textsf{T}(S)\cap \mathcal {C} = \emptyset$, $\boldsymbol{u} \in \mathbb {Z}^{|\mathcal {I}_{\boldsymbol{u}}|}$ and $\mathcal {I}_{\boldsymbol{u}} \subset \mathbb {Z}$ where $\textsf{GID}$s are distinct in each of these tuples.

  • 4. Two message vectors $\boldsymbol{v}_0, \boldsymbol{v}_1 \in \mathbb {Z}_q^{|\mathcal {I}^*|}$ having the same index set $\mathcal {I}^*$, and a challenge $\textsf{LSSS}$ access policy $(\boldsymbol{\textrm{M}}, \delta )$ with $\boldsymbol{\textrm{M}} = (M_{i, j})_{\ell \times s_{\textsf{max}}} = (\boldsymbol{M}_1, \dots , \boldsymbol{M}_{\ell })^{\top } \in \mathbb {Z}_q^{\ell \times s_{\textsf{max}}}$, $\delta : [\ell ] \rightarrow \textsf{U}_\textsf{att}$ and satisfying the constraint that for each $(\textsf{GID}, S,\boldsymbol{u}, \mathcal {I}_{\boldsymbol{u}}) \in \mathcal {Q}$, either $S \cup \bigcup _{\theta \in \mathcal {C}} \textsf{T}^{-1}(\theta ) \subseteq [\ell ]$ constitutes an unauthorized subset of rows of the access matrix $\boldsymbol{\textrm{M}}$ or the secret key vector $\boldsymbol{u}$ satisfies the relation ${(\boldsymbol{v}_0 - \boldsymbol{v}_1)} \cdot {\boldsymbol{u}} = 0$ whenever $\mathcal {I}_{\boldsymbol{u}} = \mathcal {I}^*$. Note that the set $\bigcup _{\theta \in \mathcal {C}} \textsf{T}^{-1}(\theta )$ contains the attributes belonging to the corrupt authorities.

• Challenger’s Replies: The challenger flips a random coin $\beta \leftarrow \{0,1\}$ and replies with the following:

  • 1. The public keys $\textsf{PK}_\theta \leftarrow \textsf{LocalSetup}(\textsf{GP}, \theta )$ for all $\theta \in \mathcal {N}$.

  • 2. The secret keys $\textsf{SK}_{\textsf{GID}, t, \boldsymbol{u}} \leftarrow \textsf{KeyGen}(\textsf{GP},\textsf{GID},\textsf{MSK}_\theta , t, \boldsymbol{u})$ for all $(\textsf{GID}, S, \boldsymbol{u})\in \mathcal {Q}, t \in S$.

  • 3. The challenge ciphertext $\textsf{CT}\leftarrow \textsf{Encrypt}(\textsf{GP}, (\boldsymbol{\textrm{M}},\delta ), \{\textsf{PK}_\theta \}_{\theta \in \mathcal {C}\cup \mathcal {N}}, \boldsymbol{v}_{\beta })$.

• Guess: The adversary outputs a guess $\beta '$ for $\beta$.

The advantage of the adversary $\mathcal {A}$ is $\textsf{Adv}_{\mathcal {A},\textsf {SS-CPA}}^{\textsf{LMA}\text {-}\textsf{ABUIPFE}}(\lambda ) \triangleq |\Pr [\beta =\beta '] -1/2|.$

Definition 4.1

(Static Security for $\boldsymbol{\textsf{LMA}}{} {\textbf {-}}\boldsymbol{\textsf{ABUIPFE}}$ for $\boldsymbol{\textsf{LSSS}}$) An $\textsf{LMA}$-$\textsf{ABUIPFE}$ scheme for $\textsf{LSSS}$-realizable access structures satisfies static security if for any PPT adversary $\mathcal {A}$ there exists $\textsf{negl}(\cdot )$ such that for all $\lambda \in \mathbb {N}$, we have $\textsf{Adv}_{\mathcal {A},\textsf{SS}\text {-}\textsf{CPA}}^{\textsf{LMA}\text {-}\textsf{ABUIPFE}}(\lambda )$ $\le \textsf{negl}(\lambda ).$

Remark 4.1

(Static Security in the Random Oracle Model.) Similar to [19, 21, 36], we additionally consider the aforementioned notion of selective security with static corruption in the ROM. In this context, we assume a global hash function $\textsf{H}$ published as part of the global public parameters and accessible by all the parties in the system. In the security proof, we will model $\textsf{H}$ as a random oracle programmed by the challenger. In the security game, therefore, we let the adversary $\mathcal {A}$ submit a collection of $\textsf{H}$-oracle queries to the challenger immediately after seeing the global public parameters, along with all the other queries it makes in the static security game as described above.

Remark 4.2

(Small Universe $\boldsymbol{\textsf{MA}}{} {\textbf {-}}\boldsymbol{\textsf{ABUIPFE}}$.) The above definition of $\textsf{LMA}$-$\textsf{ABUIPFE}$ captures the large universe scenario where one authority can control multiple attributes. We can similarly define a small universe $\textsf{MA}\text {-}\textsf{ABUIPFE}$ or simply $\textsf{MA}\text {-}\textsf{ABUIPFE}$ by restricting each authority to control only a single attribute [36]. Hence, we would use the words “authority" and “attribute" interchangeably in the case of $\textsf{MA}\text {-}\textsf{ABUIPFE}$. There are a few syntactic and semantic changes in the above definition when adapted for the small universe setting:

• 1. There is a bijection between the attribute universe $\textsf{U}_\textsf{att}$ and the authority universe $\mathcal{A}\mathcal{U}$.

• 2. $\textsf{LocalSetup}(\textsf{GP}, t)$ outputs $(\textsf{PK}_t,\textsf{MSK}_t)$ for an authority/attribute $t\in \mathcal{A}\mathcal{U}$.

• 3. $\textsf{KeyGen}(\textsf{GP},\textsf{GID},\textsf{MSK}_t, \boldsymbol{u}, \mathcal {I}_{\boldsymbol{u}})$ outputs $\textsf{SK}_{\textsf{GID},t, \boldsymbol{u}}$.

• 4. For an $\textsf{LSSS}$ access structure $(M, \delta )$, we have $\rho (\cdot ) = \delta (\cdot )$ is an injective map.

• 5. The changes in the security definition follow accordingly. Due to space constraints, we state them directly in the proof of our small universe scheme in Sect. 5.3.

5 The Proposed Small Universe $\textsf {MA}\text {-}\textsf {ABUIPFE}$ from $\textsf{DBDH}$

In this section, we describe the formal construction and proof for our $\textsf{MA}\text {-}\textsf{ABUIPFE}$ scheme. The construction is in prime-order groups and uses a hash functions that will be modeled as a random oracle in the security proof.

5.1 The Construction

$\boldsymbol{\textsf{GlobalSetup}(1^{\lambda }, s_{\textsf{max}})}$: The global setup algorithm takes input the security parameter $\lambda$, the maximum width of an $\textsf{LSSS}$ matrix supported by the scheme $s_{\textsf{max}}= s_{\textsf{max}}(\lambda )$ and the vector length n in unary. It generates $\textsf{G} = (q, \mathbb {G}_1, \mathbb {G}_2, \mathbb {G}_T, g, e)$. Consider the hash functions $\textsf {H}_1 : \textsf{U}_\textsf{att}\times \mathbb {Z} \times \mathbb {Z}^* \rightarrow \mathbb {G}_2$, $\textsf {H}_2 : [s_{\textsf{max}}] \times \mathbb {Z} \times \mathbb {Z}^* \rightarrow \mathbb {G}_2$, $\textsf{H}_3 : \mathcal {GID} \times \mathbb {Z}^* \times [s_{\textsf{max}}] \rightarrow \mathbb {G}_2$. It outputs a global parameter $\textsf{GP}= (\textsf{G}, \textsf{H}_1, \textsf {H}_2, \textsf {H}_3)$.

$\boldsymbol{\textsf{LocalSetup}(\textsf{GP}, t)}$: The authority setup algorithm takes as input $\textsf{GP}$ and an authority index/attribute $t \in \mathcal{A}\mathcal{U}$. It samples vectors $\alpha _t, y_{t, 2}, \dots , y_{t, s_{\textsf{max}}} \leftarrow \mathbb {Z}_q$ and outputs

$$\begin{aligned} \textsf{PK}= \left( \{[\![\alpha _t]\!]_1, \{[\![y_{t,j}]\!]_1\}_{j\in \{2,\ldots , s_{\textsf{max}}\}}\}_{t\in \textsf{U}_\textsf{att}}\right) ,~~~ \textsf{MSK}= \{ \{\alpha _t, \{y_{t,j}\}_{j\in \{2,\ldots , s_{\textsf{max}}\}}\}_{t\in \textsf{U}_\textsf{att}} \} \end{aligned}$$

$\boldsymbol{\textsf{KeyGen}(\textsf{GP}, \textsf{GID}, \textsf{MSK}_t, \boldsymbol{u}, \mathcal {I}_{\boldsymbol{u}})}$: The key generation algorithm takes input $\textsf{GP}$, the user’s global identifier $\textsf{GID}$, the authority’s secret key $\textsf{MSK}_t$ and a vector $\boldsymbol{u} \in \mathbb {Z}_q^{|\mathcal {I}_{\boldsymbol{u}}|}$. It proceeds as follows

• 1. Parse $\mathcal {I}_{\boldsymbol{u}} = \{\iota _1, \dots , \iota _n\}$ and $\boldsymbol{u} = (u_{\iota _1}, \dots , u_{\iota _n})$.

• 2. Compute

  $${\displaystyle \textsf{SK}_{t, \boldsymbol{u}} = \prod _{k =1}^n \textsf {H}_1(t~ \Vert ~\iota _k ~ \Vert ~\mathcal {I}_{\boldsymbol{u}})^{\alpha _t u_{\iota _k}}\cdot \prod _{j=2}^{s_{\textsf{max}}} \prod _{k =1}^n (\textsf {H}_2( j ~ \Vert ~\iota _k~ \Vert ~\mathcal {I}_{\boldsymbol{u}}) \cdot \textsf {H}_3(\textsf{GID}~ \Vert ~\boldsymbol{u} ~ \Vert ~j~ \Vert ~\iota _k))^{y_{t, j}u_{\iota _k} }}.$$

• 3. Output $\textsf{SK}_{\textsf{GID}, t,\boldsymbol{u}} = \left( \textsf{GID}, \boldsymbol{u},\textsf{SK}_{t,\boldsymbol{u}}, \mathcal {I}_{\boldsymbol{u}}\right)$ as the secret key.

$\boldsymbol{\textsf{Encrypt}(\textsf{GP}, (\boldsymbol{\textrm{M}}, \rho ), \{\textsf{PK}_t\}, \boldsymbol{v}, \mathcal {I}_{\boldsymbol{v}})}$: The encryption algorithm takes input the global parameter $\textsf{GP}$, an $\textsf{LSSS}$ access structure $(\boldsymbol{\textrm{M}}, \rho )$ where $\boldsymbol{\textrm{M}} = (\boldsymbol{M}_1, \dots , \boldsymbol{M}_{\ell })^{\top } \in \mathbb {Z}_q^{\ell \times s_{\textsf{max}}}$ and $\rho : [\ell ] \rightarrow \mathcal{A}\mathcal{U}$, a set $\{\textsf{PK}_t\}$ of public keys for all the authorities in the range of $\rho$, and a message vector $\boldsymbol{v} \in \mathbb {Z}_q^m$. The function maps the row indices of $\boldsymbol{\textrm{M}}$ to authorities or attributes. We assume $\rho$ is an injective function, that is, an authority/attribute is associated with at most one row of $\boldsymbol{\textrm{M}}$. The algorithm proceeds as follows:

• 1. Parse $\mathcal {I}_{\boldsymbol{v}} = \{\iota _1, \dots , \iota _m\}$ and $\boldsymbol{v} = (v_{\iota _1}, \dots , v_{\iota _m})$.

• 2. Sample $\{r_i\leftarrow \mathbb {Z}_q\}_{i\in [\ell ]}$ and $\boldsymbol{f} = (f_2, \dots , f_{s_{\textsf{max}}}) \leftarrow \mathbb {Z}_q^{s_{\textsf{max}}-1}$.

• 3. Sample $\boldsymbol{z}, \boldsymbol{b}_2,\dots ,\boldsymbol{b}_{s_{\textsf{max}}}, \boldsymbol{x}_2, \dots , \boldsymbol{x}_{s_{\textsf{max}}}\leftarrow \mathbb {Z}_q^m$.

• 4. Set the matrix $\boldsymbol{\textrm{B}} = \begin{bmatrix} \boldsymbol{z}, \boldsymbol{b}_{2}, \ldots , \boldsymbol{b}_{s_{\textsf{max}}} \end{bmatrix}^{\top }_{s_{\textsf{max}}\times m}$.

• 5. Compute $\vartheta _{i, k} = e( r_i[\![\alpha _{\rho (i)}]\!]_1, \textsf {H}_1(\rho (i)~ \Vert ~\iota _k ~ \Vert ~\mathcal {I}_{\boldsymbol{v}}))$ and set $\boldsymbol{\vartheta }_i {:}{=}(\vartheta _{i, 1}, \dots , \vartheta _{i, m}).$

• 6. Compute the following terms:

  $$\begin{array}{c } C_0 = [\![\boldsymbol{v} + \boldsymbol{z}]\!]_T, ~~~~ C_{1, i} = [\![\boldsymbol{M}_i \boldsymbol{\textrm{B}} + \boldsymbol{\vartheta }_i]\!]_T,~~~~ C_{2, i} = [\![r_i]\!]_1,\\ C_{3, i, j, k} = e([\![M_{i,j} x_{j, k}]\!]_1, \textsf {H}_2( j ~ \Vert ~\iota _k ~ \Vert ~\mathcal {I}_{\boldsymbol{v}})) \cdot e(r_i [\![y_{\rho (i), j}]\!]_1, \textsf {H}_2( j ~ \Vert ~\iota _k~ \Vert ~\mathcal {I}_{\boldsymbol{v}})),\\ C_{4, i, j} = [\![M_{i, j} f_j + y_{\rho (i), j}r_i]\!]_1 \end{array}$$

  for all $i \in [\ell ], j \in \{2,\ldots , s_{\textsf{max}}\}, k \in [m]$.

• 7. Output the ciphertext

  $$\textsf{CT}= \left( \left( \boldsymbol{\textrm{M}}, \rho \right) , C_0, \{C_{1, i}, C_{2,i,}, C_{3,i,j,k}, C_{4, i, j}\}_{i \in [\ell ],j\in \{2,\ldots , s_{\textsf{max}}\}, k \in [m]}, \mathcal {I}_{\boldsymbol{v}}\right) .$$

$\boldsymbol{\textsf{Decrypt}(\textsf{GP}, \textsf{GID}, \textsf{CT}, \{\textsf{SK}_{\textsf{GID}, t, \boldsymbol{u}}\})}$: The decryption algorithm takes input the public key $\textsf{PK}$, a secret key $\textsf{SK}_{S, \boldsymbol{u}}$ for an attribute set $S\subseteq \textsf{U}_\textsf{att}$ and a vector $\boldsymbol{u}\in \mathbb {Z}^n_q$ and a ciphertext $\textsf{CT}$ for an access structure $(\boldsymbol{\textrm{M}}, \rho )$ with $\boldsymbol{\textrm{M}} \in \mathbb {Z}_q^{\ell \times s_{\textsf{max}}}$ and an injective map $\rho : [\ell ] \rightarrow \textsf{U}_\textsf{att}$.

Parse $\textsf{SK}_{\textsf{GID}, S,\boldsymbol{u}}= \left( \textsf{GID}, \boldsymbol{u},\{\textsf{SK}_{\rho (i),\boldsymbol{u}}\}_{\rho (i)\in S}, \mathcal {I}_{\boldsymbol{u}}\right)$, where $i\in [\ell ]$ and $\textsf{CT}= (\left( \boldsymbol{\textrm{M}}, \rho \right) , C_0, \{C_{1, i}, C_{2,i,}, C_{3,i,j,k}, C_{4, i, j}\}_{i \in [\ell ],j\in \{2,\ldots , s_{\textsf{max}}\}, k \in [m]}, \mathcal {I}_{\boldsymbol{v}})$. Denote $I = \{i | \rho (i)\in S\} \subseteq [\ell ]$. If $(1, 0, \dots , 0)$ is not in the span of $\boldsymbol{\textrm{M}}_I$ (i.e., $\boldsymbol{\textrm{M}}$ restricted to the set of rows from I) or $\mathcal {I}_{\boldsymbol{u}} \ne \mathcal {I}_{\boldsymbol{v}}$ decryption returns $\bot$. Else, when S satisfies $(\boldsymbol{\textrm{M}},\rho )$, the algorithm finds $\{w_i \in \mathbb {Z}_q\}_{i\in I}$ such that $(1, 0, \dots , 0) = \sum _{i \in I} w_i \boldsymbol{\textrm{M}}_i$. It then computes $[\![\varGamma ]\!]_T= {C_0} \cdot {\boldsymbol{u}}\cdot [\![\mu ]\!]_T$ where $[\![\mu ]\!]_T$ is given by

$$\begin{aligned} \displaystyle \left( \prod _{i \in I} \left[ \frac{ {C_{1,i}} \cdot {\boldsymbol{u}} \cdot \displaystyle \prod _{j=2}^{s_{\textsf{max}}} \prod _{k=1}^n u_{\iota _k} \cdot C_{3,i,j, k} \cdot e(C_{4, i, j}, \textsf {H}_3(\textsf{GID}~ \Vert ~\boldsymbol{u} ~ \Vert ~j~ \Vert ~\iota _k)^{u_{\iota _k}})}{ e\left( \textsf{SK}_{\rho (i), \boldsymbol{u}}, C_{2,i} \right) } \right] ^{w_i} \right) ^{-1} \end{aligned}$$

and outputs $\log _{g_T}([\![\varGamma ]\!]_T)$.

5.2 Correctness

Consider a secret key $\textsf{SK}_{\textsf{GID}, S,\boldsymbol{u}} = \left( \textsf{GID}, \boldsymbol{u},\{\textsf{SK}_{t,\boldsymbol{u}}\}_{t\in S}, \mathcal {I}_{\boldsymbol{u}}\right)$ consisting of a set of attributes satisfying the $\textsf{LSSS}$ access structure $(\boldsymbol{\textrm{M}}, \rho )$ associated with a ciphertext $\textsf{CT}= \left( \left( \boldsymbol{\textrm{M}}, \rho \right) , C_0, \{C_{1, i}, C_{2,i,}, C_{3,i,j,k}, C_{4, i, j}\}_{i \in [\ell ], j\in \{2,\ldots , s_{\textsf{max}}\}, k \in [m]}, \mathcal {I}_{\boldsymbol{v}}\right)$ such that $\mathcal {I}_{\boldsymbol{u}} = \mathcal {I}_{\boldsymbol{v}} = \mathcal {I}$. In particular, the vector $(1, 0, \dots , 0)\in \textsf{rowspan}(\boldsymbol{\textrm{M}}_I)$ corresponding to the set of indices $I = \{i \in I | \rho (i) = t \in S \}$.

For each $i \in I$, we have the following:

$$\begin{aligned} e(\textsf{SK}_{\rho (i), \boldsymbol{u}}, C_{2, i}) =&\prod _{k=1}^{n}e( g_1, \textsf {H}_1(\rho (i) ~ \Vert ~\iota _k~ \Vert ~\mathcal {I}))^{r_i\alpha _{\rho (i)}u_{\iota _k}} \cdot&\\&\prod _{j=2}^{s_{\textsf{max}}}\prod _{k=1}^n (e(g_1, \textsf {H}_2(j ~ \Vert ~\iota _k ~ \Vert ~\mathcal {I})) \cdot e(g_1, \textsf {H}_3(\textsf{GID}~ \Vert ~\boldsymbol{u} ~ \Vert ~j ~ \Vert ~\iota _k)))^{r_iy_{\rho (i), j}u_{\iota _k}}&\\ \end{aligned}$$

For $i \in I, j \in \{2, \dots , s_{\textsf{max}}\}, k \in [n]$,

$$\begin{aligned} u_{\iota _k}C_{3, i, j, k}&= e( [\![M_{i, j}x_{j, k}]\!]_1, \textsf {H}_2(j ~ \Vert ~\iota _k~ \Vert ~\mathcal {I}))^{u_{\iota _k}} \cdot e(g_1, \textsf {H}_2(j ~ \Vert ~\iota _k~ \Vert ~\mathcal {I}))^{r_iy_{\rho (i), j}u_{\iota _k}} \\ \end{aligned}$$

For $i \in I, j \in \{2, \dots , s_{\textsf{max}}\}, k \in [n]$,

$$\begin{aligned}&e(C_{4, i, j}, \textsf {H}_3(\textsf{GID}~ \Vert ~\boldsymbol{u}~ \Vert ~j ~ \Vert ~\iota _k)^{u_{\iota _k}})&\\&= e( [\![M_{i, j}f_{j}]\!]_1, \textsf {H}_3(\textsf{GID}~ \Vert ~\boldsymbol{u}~ \Vert ~j ~ \Vert ~\iota _k))^{u_{\iota _k}} \cdot e(g_1,\textsf {H}_3(\textsf{GID}~ \Vert ~\boldsymbol{u}~ \Vert ~j ~ \Vert ~\iota _k))^{r_iy_{\rho (i), j}u_{\iota _k}}&\\ \end{aligned}$$

Finally, for each $i \in I$, we have $C_{1, i} = [\![\boldsymbol{M}_i \boldsymbol{\textrm{B}} + \boldsymbol{\vartheta }_i]\!]_T$ and so

$$\begin{aligned}&\frac{ {C_{1,i}} \cdot {\boldsymbol{u}} \cdot \displaystyle \prod _{j=2}^{s_{\textsf{max}}} \prod _{k=1}^n (u_{\iota _k} \cdot C_{3,i,j, k} \cdot e(C_{4, i, j}, \textsf {H}_3(\textsf{GID}~ \Vert ~\boldsymbol{u}~ \Vert ~j ~ \Vert ~\iota _k)^{u_{\iota _k}}))}{ e\left( \textsf{SK}_{\rho (i), \boldsymbol{u}}, C_{2,i} \right) }{} & {} \\&= [\![{\boldsymbol{M}_i \boldsymbol{\textrm{B}} } \cdot {\boldsymbol{u}}]\!]_T \prod _{k=1}^n e(g_1, \textsf {H}_1(\rho (i)~ \Vert ~\iota _k~ \Vert ~\mathcal {I}))^{r_i\alpha _{\rho (i)}u_{\iota _k}} \cdot{} & {} \\&\quad \frac{ \displaystyle \prod _{j=2}^{s_{\textsf{max}}} \prod _{k=1}^n (u_{\iota _k} \cdot C_{3,i,j, k} \cdot e(C_{4, i, j}, \textsf {H}_3(\textsf{GID}~ \Vert ~\boldsymbol{u}~ \Vert ~j ~ \Vert ~\iota _k)^{u_{\iota _k}}))}{ e\left( \textsf{SK}_{\rho (i), \boldsymbol{u}}, C_{2,i} \right) }{} & {} \\&=[\![{\boldsymbol{M}_i \boldsymbol{\textrm{B}} } \cdot {\boldsymbol{u}}]\!]_T \cdot \prod _{j=2}^{s_{\textsf{max}}} \prod _{k=1}^n e( [\![M_{i, j}x_{j, k}]\!]_1, \textsf {H}_2(j ~ \Vert ~\iota _k~ \Vert ~\mathcal {I}))^{u_{\iota _k}} \cdot{} & {} \\&\qquad \qquad \qquad \qquad \qquad \qquad \quad \prod _{j=2}^{s_{\textsf{max}}} \prod _{k=1}^n e( [\![M_{i, j}f_{j}]\!]_1, \textsf {H}_3(\textsf{GID}~ \Vert ~\boldsymbol{u}~ \Vert ~j ~ \Vert ~\iota _k))^{u_{\iota _k}}{} & {} \end{aligned}$$

Since $\textsf{SK}_{S, \boldsymbol{u}}$ corresponds to a set of qualified authorities, $\exists \{w_i\in \mathbb {Z}_q\}_{i\in I}$ such that $\sum _{i \in I} w_i {\boldsymbol{M}_i \boldsymbol{\textrm{B}}} \cdot {\boldsymbol{u}} = (1, 0, \dots , 0)\boldsymbol{\textrm{B}} \cdot \boldsymbol{u} = {\boldsymbol{z}} \cdot {\boldsymbol{u}}$ and it holds that $\sum _{i \in I} w_i M_{i, j} = 0, \forall j \in \{2,\ldots , s_{\textsf{max}}\}$. Hence, we have

$$\begin{aligned}&\quad \,\, \prod _{i \in I} \left[ \frac{ {C_{1,i}} \cdot {\boldsymbol{u}} \cdot \displaystyle \prod _{j=2}^{s_{\textsf{max}}} \prod _{k=1}^n (u_{\iota _k} \cdot C_{3,i,j, k} \cdot e(C_{4, i, j}, \textsf {H}_3(\textsf{GID}~ \Vert ~\boldsymbol{u}~ \Vert ~j ~ \Vert ~\iota _k)^{u_{\iota _k}}))}{ e\left( \textsf{SK}_{\rho (i), \boldsymbol{u}}, C_{2,i} \right) } \right] ^{w_i}&\\& = [\![\sum _{i \in I}w_i{\boldsymbol{M}_i \boldsymbol{\textrm{B}} } \cdot {\boldsymbol{u}}]\!]_T = [\![{\boldsymbol{z}} \cdot {\boldsymbol{u}}]\!]_T&\end{aligned}$$

Finally, the message is recovered as $\log _{g_T}([\![\varGamma ]\!]_T)$ where

$$\begin{aligned}{}[\![\varGamma ]\!]_T = ({C_0} \cdot {\boldsymbol{u}}) / [\![{\boldsymbol{z}} \cdot {\boldsymbol{u}}]\!]_T = [\![{\boldsymbol{v}} \cdot {\boldsymbol{u}} + {\boldsymbol{z}} \cdot {\boldsymbol{u}}]\!]_T / [\![{\boldsymbol{z}} \cdot {\boldsymbol{u}}]\!]_T = [\![{\boldsymbol{v}} \cdot {\boldsymbol{u}}]\!]_T \end{aligned}$$

5.3 Security Analysis

Theorem 5.1

If the $\textsf{DBDH}$ assumption holds, then all $\textsf{PPT}$ adversaries have a negligible advantage in breaking the static security of the proposed small universe $\textsf{MA}\text {-}\textsf{ABUIPFE}$ scheme in the random oracle model.

Proof

We prove this theorem by showing that if there is any $\textsf{PPT}$ adversary $\mathcal {A}$ who breaks the static security of $\textsf{MA}\text {-}\textsf{ABUIPFE}$ then there is a $\textsf{PPT}$ adversary $\mathcal {B}$ who solves the $\textsf{DBDH}$ problem with a non-negligible advantage. Suppose, $\mathcal {B}$ gets an instance $(\textsf{G}, [\![a]\!]_1, [\![c]\!]_1, [\![a]\!]_2, [\![b]\!]_2, [\![\tau ]\!]_T)$ of the $\textsf{DBDH}$ problem where $\textsf{G} = (q, \mathbb {G}_1, \mathbb {G}_2, \mathbb {G}_T, g, e) \leftarrow \mathcal {G}(1^{\lambda })$ is a group description, the elements $a, b, c \leftarrow \mathbb {Z}_q$ are random integers, and the element $\tau \in \mathbb {Z}_q$ is either abc or a random element of $\mathbb {Z}_q$. The algorithm $\mathcal {B}$ works as follows:

On input $\lambda$, $\mathcal {A}$ outputs $s_{\textsf{max}}, \textsf{U}_\textsf{att}$ and queries the following.

Attacker’s Queries: Upon initialization, the adversary $\mathcal {A}$ sends the following to $\mathcal {B}$:

• (a) A list $\mathcal {C} \subset \mathcal{A}\mathcal{U}$ of corrupt authorities and their respective public keys

  $$\begin{aligned} \{\textsf{PK}_t = (\textrm{Y}_{t, 1}, \textrm{Y}_{t, 2}, \dots , \textrm{Y}_{t, s_{\textsf{max}}}) \}_{t \in \mathcal {C}}, \end{aligned}$$

  where $\textrm{Y}_{t, 1} , \textrm{Y}_{t, 2}, \dots , \textrm{Y}_{t, s_{\textsf{max}}} \in \mathbb {G}_1$ for all $t \in \mathcal {C}$.

• (b) A set $\mathcal {N} \subset \mathcal{A}\mathcal{U}$ of non-corrupt authorities, i.e., $\mathcal {C} \cap \mathcal {N} = \emptyset$, for which $\mathcal {A}$ requests the public keys.

• (c) A collection of hash queries $\mathcal {H}_1 = \{(t, \iota _k, \mathcal {I}) : t \in \textsf{U}_\textsf{att}, \iota _k \in \mathbb {Z}, \mathcal {I} \subset \mathbb {N}\}$, $\mathcal {H}_2 = \{(j, \iota _k, \mathcal {I}): j \in \{2, \dots , s_{\textsf{max}}\}, \iota _k \in \mathbb {Z}, \mathcal {I} \subset \mathbb {N}\}$ and $\mathcal {H}_3 = \{(\textsf{GID}, \boldsymbol{u}, j, \iota _k): \textsf{GID}\in \mathcal {GID}, \boldsymbol{u} \in \mathbb {Z}^*, j \in \{2, \dots , s_{\textsf{max}}\}, \iota _k \in \mathbb {Z} \}$.

• (d) A set $\mathcal {Q} = \{(\textsf{GID}, S, \boldsymbol{u}, \mathcal {I}_{\boldsymbol{u}})\}$ of secret key queries with $\textsf{GID}\in \mathcal {GID}, S\subseteq \textsf{U}_\textsf{att}$, $\boldsymbol{u} \in \mathbb {Z}^{|\mathcal {I}_{\boldsymbol{u}}|}$ and $\mathcal {I}_{\boldsymbol{u}} \subset \mathbb {Z}$.

• (e) Two message vectors $\boldsymbol{v}_0, \boldsymbol{v}_1 \in \mathbb {Z}_q^n$ having the same index set $\mathcal {I}^*$, and a challenge $\textsf{LSSS}$ access policy $(\boldsymbol{\textrm{M}}, \rho )$ with $\boldsymbol{\textrm{M}} = (M_{i, j})_{\ell \times s_{\textsf{max}}} = (\boldsymbol{M}_1, \dots , \boldsymbol{M}_{\ell })^{\top } \in \mathbb {Z}_q^{\ell \times s_{\textsf{max}}}$ and $\rho : [\ell ] \rightarrow \mathcal {C} \cup \mathcal {N}$ injective and satisfying the constraint that for each $(S,\boldsymbol{u}, \mathcal {I}_{\boldsymbol{u}}) \in \mathcal {Q}_{\boldsymbol{u}}$, either $\rho ^{-1}(\mathcal {C}\cup S)\subseteq [\ell ]$ constitutes an unauthorized subset of rows of the access matrix $\boldsymbol{\textrm{M}}$ or the secret key vector $\boldsymbol{u}$ satisfies the relation ${(\boldsymbol{v}_0 - \boldsymbol{v}_1)} \cdot {\boldsymbol{u}} = 0$ whenever $\mathcal {I}_{\boldsymbol{u}} = \mathcal {I}^*$.

Before answering $\mathcal {A}$’s queries, the adversary $\mathcal {B}$ substitute the secret sharing matrix $\boldsymbol{\textrm{M}}$ with the matrix $\boldsymbol{\textrm{M}}^{\prime }$ from Lemma 3.1 of [36] computed using $\rho ^{-1}(\mathcal {C})$ as the unauthorized subset of rows. Lemma 3.1 of [36] guarantees the fact that if $\mathcal {B}$ uses $\boldsymbol{\textrm{M}}^{\prime }$ instead of $\boldsymbol{\textrm{M}}$ in the simulation, the view of $\mathcal {A}$ in the simulated game is information theoretically the same as if $\mathcal {B}$ would have used the original matrix $\boldsymbol{\textrm{M}}$. Furthermore, Lemma 3.1 of [36] implies that if we assume the subspace spanned by $\boldsymbol{\textrm{M}}_{\rho ^{-1}(\mathcal {C})}$ has dimension $\widetilde{c}$, then so is the dimension of the subspace spanned by $\boldsymbol{\textrm{M}}^{\prime }_{\rho ^{-1}(\mathcal {C})}$ and $M^{\prime }_{i, j} = 0$ for all $(i, j) \in \rho ^{-1}(\mathcal {C}) \times [s_{\textsf{max}}- \widetilde{c}]$. $\mathcal {B}$ now proceeds to answer the queries of $\mathcal {A}$. Denote $\widehat{s_{\textsf{max}}} = s_{\textsf{max}}- \widetilde{c}$, where $\widetilde{c}$ is the dimension of the sequence spanned by the rows of $\boldsymbol{\textrm{M}}_{\rho ^{-1}(\mathcal {C})}$, the latter being the rows of $\boldsymbol{\textrm{M}}$ controlled by corrupted authorities, $\mathcal {C}$.

Note that $\mathcal {I}^*$ can be any subset of $\mathbb {Z}$ and w.l.o.g one can consider $\mathcal {I}^* = [n]$³ for some $n \in \mathbb {N}$. Inspired by the proof techniques of prior works [3, 38], the reduction first compute a basis of $(\boldsymbol{v}_0 - \boldsymbol{v}_1)^{\bot }$ as $\{\widetilde{\boldsymbol{b}}_1, \dots , \widetilde{\boldsymbol{b}}_{n-1}\}$. Then the set $\widetilde{\mathcal {S}} = \{\boldsymbol{v}_0 - \boldsymbol{v}_1, \widetilde{\boldsymbol{b}}_1, \dots , \widetilde{\boldsymbol{b}}_{n-1} \}$ form a basis of $\mathbb {Z}_q^n$. For any vector $\boldsymbol{u} \in \mathbb {Z}_q^n$, if we represent it as the linear combination of the vectors in $\widetilde{\mathcal {S}}$ as

$$\begin{aligned} \boldsymbol{u} = \zeta \cdot (\boldsymbol{v}_0 - \boldsymbol{v}_1) + \sum _{k=1}^{n-1} \zeta _k \widetilde{\boldsymbol{b}}_k,~~~~\text {for some }\zeta , \zeta _k \in \mathbb {Z}_q \end{aligned}$$

then $\zeta = 0$ whenever it holds that $(\boldsymbol{v}_0 - \boldsymbol{v}_1)\cdot \boldsymbol{u} = 0$. Let $\boldsymbol{e}_k$ be the k-th vector in the standard basis of $\mathbb {Z}_q^n$. We write $\boldsymbol{e}_i$ for each $i \in [n]$ as

$$\begin{aligned} \boldsymbol{e}_i = \eta _i \cdot (\boldsymbol{v}_0 - \boldsymbol{v}_1) + \sum _{k=1}^{n-1} \lambda _{i, k} \widetilde{\boldsymbol{b}}_k~~~~\text {for some }\eta , \lambda _{i, k} \in \mathbb {Z}_q. \end{aligned}$$

Generating Public Key: There are two cases to consider:

• 1. Case 1 —$~t \in \mathcal {N}\setminus \rho ([\ell ])$ (i.e., attribute t is absent in the challenge policy $(\boldsymbol{\textrm{M}},\rho )$ but it belongs to a non-corrupt authority) —  In this case, $\mathcal {B}$ executes the $\textsf{Setup}$ algorithm according to the real experiment. It samples $\alpha _t, y_{t, 2}, \dots , y_{t, s_{\textsf{max}}} \leftarrow \mathbb {Z}_q$ by itself, and computes the public key component corresponding to attribute t as $( [\![\alpha _t]\!]_1, [\![y_{t, 2}]\!]_1, \dots , [\![y_{t, s_{\textsf{max}}}]\!]_1)$.

• 2. Case 2—$t\in \rho ([\ell ])\setminus \mathcal {C}$ (i.e., attribute t appears in the challenge policy $(\boldsymbol{\textrm{M}},\rho )$ and it does not belong to a corrupt authority) — In this case, $\mathcal {B}$ samples $\alpha _t^{\prime }, y_{t, 2}^{\prime }, \dots , y_{t, s_{\textsf{max}}}^{\prime } \leftarrow \mathbb {Z}_q$ and implicitly sets $\alpha _{t} = \alpha _t^{\prime } + a \cdot M_{\rho ^{-1}(t), 1}'$ and $y_{t, j} = y_{t, j}^{\prime } + a M_{\rho ^{-1}(t), j}'$ for $j \in \{2,\ldots , \widehat{s_{\textsf{max}}}\}$ and $y_{t, j} = y_{t, j}'$ for $j \in \{\widehat{s_{\textsf{max}}}+1, \dots , s_{\textsf{max}}\}$(these are well-defined as $\rho$ is injective), and sets the public key elements w.r.t. attribute t as $( [\![\alpha _t]\!]_1, [\![y_{t, 2}]\!]_1, \dots , [\![y_{t, s_{\textsf{max}}}]\!]_1)$ where the elements $[\![\alpha _t]\!]_1$ and $[\![y_{t, j}]\!]_1$ for $j \in \{2,\ldots , \widehat{s_{\textsf{max}}}\}$ are computed as follows:

  $$\begin{aligned}{}[\![\alpha _t]\!]_1 = [\![\alpha _t^{\prime }]\!]_1 \cdot M_{\rho ^{-1}(t), 1}' [\![a]\!]_1, \,\,\, [\![y_{t, j}]\!]_1 = [\![y_{t, j}^{\prime }]\!]_1 \cdot M_{\rho ^{-1}(t), j}' [\![a]\!]_1 \end{aligned}$$

  (5.1)

  for all $j \in [2, \widehat{s_{\textsf{max}}}]$. Note that, $\alpha _t$ and $\{y_{t, j}\}_{j \in \{2,\ldots , s_{\textsf{max}}\}}$ are distributed uniformly over $\mathbb {Z}_q$ and hence each of these elements of the public key is properly distributed.

Answering Hash Queries:

• 1. $\boldsymbol{\textsf {H}_1}$ queries. If $(\iota _k \in \mathcal {I}^* \wedge \mathcal {I} = \mathcal {I}^*)$, then sample uniformly random elements $h_{1,\widehat{k}}, h_{1, t, \iota _k}$ from $\mathbb {Z}_q$ and set

  $$\begin{aligned} \textsf {H}_1(t~ \Vert ~\iota _k ~ \Vert ~\mathcal {I}) = (g_2^b)^{\eta _k}\cdot \prod _{\widehat{k}=1}^{n-1} g_2^{h_{1, \widehat{k}}\lambda _{k, \widehat{k}}}\cdot g_2^{h_{1, t, \iota _k}}. \end{aligned}$$

  (5.2)

  Otherwise, if $(\iota _k \not \in \mathcal {I}^* \vee \mathcal {I} \ne \mathcal {I}^*)$, then output a random $\mathbb {G}_2$ element, i.e., sample uniformly random element $h_{1, t, \iota _k}'$ from $\mathbb {Z}_q$ and set $\textsf {H}_1(t~ \Vert ~\iota _k~ \Vert ~\mathcal {I}) = g_2^{h_{1, t, \iota _k}'}$. The reduction stores the hash queries for future use.

• 2. $\boldsymbol{\textsf {H}_2}$ queries. If $(\iota _k \in \mathcal {I}^* \wedge \mathcal {I} = \mathcal {I}^*)$, then sample uniformly random elements $h_{2,\widehat{k}}, h_{2, j, \iota _k}$ for $j \in \{2, \dots , \widehat{s_{\textsf{max}}}\}$ (in Eq. 5.3) and elements $h_{2, j, \iota _k}'$ for $j \in \{\widehat{s_{\textsf{max}}}+1, \dots , s_{\textsf{max}}\}$ from $\mathbb {Z}_q$ (in Eq. 5.4) and set

  $$\begin{aligned} \textsf {H}_2(j~ \Vert ~\iota _k ~ \Vert ~\mathcal {I})&= (g_2^b)^{\eta _k\sum _{\phi =1}^Q d_{\phi , j}} \cdot \prod _{\widehat{k}=1}^{n-1} g_2^{h_{2, \widehat{k}}\lambda _{k, \widehat{k}}}\cdot g_2^{h_{2, j, \iota _k}}\end{aligned}$$

  (5.3)
  $$\begin{aligned} \textsf {H}_2(j~ \Vert ~\iota _k ~ \Vert ~\mathcal {I})&= g_2^{h_{2, j, \iota _k}'} \end{aligned}$$

  (5.4)

  where Q denotes the total number of non-accepting key queries $\{ (S_{\phi }, \boldsymbol{u}_{\phi }, \mathcal {I}_{\boldsymbol{u}_{\phi }}) \}_{\phi \in [Q]}$ made by the adversary in the case where $\mathcal {I}_{\boldsymbol{u}_{\phi }} = \mathcal {I}^*$ but the attributes in $S_{\phi }$ does not satisfy the challenge policy $(\boldsymbol{\textrm{M}}, \rho )$. Note that, for such secret key queries, there exists a vector $\boldsymbol{d}_{\phi } = (d_{\phi , 1}, \dots , d_{\phi , s_{\textsf{max}}}) \in \mathbb {Z}_q^{s_{\textsf{max}}}$ such that $d_{\phi , 1} = 1$ and the inner product ${\boldsymbol{M}_i'} \cdot {\boldsymbol{d}_{\phi }} = 0$ for all $i \in \rho ^{-1}(\mathcal {C} \cup S_{\phi })$, where $\boldsymbol{M}_i'$ denotes the i-th row of $\boldsymbol{\textrm{M}}'$. Additionally, the set of rows $\mathcal {R} = \{\boldsymbol{M}_i^{\prime } \in \mathbb {Z}_q^{s_{\textsf{max}}}: i \in \rho ^{-1}(\mathcal {C}) \}$ has dimension c and $M_{i, j}^{\prime } = 0$ for all $(i, j) \in \rho ^{-1}(\mathcal {C}) \times [\widehat{s_{\textsf{max}}}]$. Therefore, $\mathcal {R}$ spans the entire subspace $\mathbb {V} = \bigg \{ (\overset{\widehat{s_{\textsf{max}}}}{\overbrace{0, \dots , 0}}, \boldsymbol{\nu }) : \boldsymbol{\nu } \in \mathbb {Z}_q^c \bigg \}$. Thus, it follows that $\boldsymbol{d}_{\phi }$ is orthogonal to any of the vectors

  $$\begin{aligned} \bigg \{ (\overset{\widehat{s_{\textsf{max}}}}{\overbrace{0, \dots , 0}}, \overset{j-1}{\overbrace{0, \dots , 0}}, 1, \overset{c- j}{\overbrace{0, \dots , 0}} ) \bigg \}_{j \in \{\widehat{s_{\textsf{max}}}+1, \dots , s_{\textsf{max}}\}}. \end{aligned}$$

  In other words, $d_{\phi , j} = 0$ for all $j \in \{\widehat{s_{\textsf{max}}}+1, \dots , s_{\textsf{max}}\}$. Combining the above two facts, we have $(\boldsymbol{M}_i^{\prime }|_{[\widehat{s_{\textsf{max}}}]})\cdot (\boldsymbol{d}_{\phi }|_{[\widehat{s_{\textsf{max}}}]}) = 0$ for all $i \in \rho ^{-1}(S_{\phi })$, where for a vector $\boldsymbol{x}$, $\boldsymbol{x}|_{X}$ denotes a vector formed by taking the entries of $\boldsymbol{x}$ having indices in the set $X \in \mathbb {N}$. For simplicity of notation, let us denote $\boldsymbol{M}_i^{\prime } \star \boldsymbol{d}_{\phi } = (\boldsymbol{M}_i^{\prime }|_{[\widehat{s_{\textsf{max}}}]})\cdot (\boldsymbol{d}_{\phi }|_{[\widehat{s_{\textsf{max}}}]})$ for $i \in \rho ^{-1}(S_{\phi })$.

  Otherwise, if $(\iota _k \not \in \mathcal {I}^* \vee \mathcal {I} \ne \mathcal {I}^*)$, then output a random $\mathbb {G}_2$ element, i.e., sample uniformly random element $h_{2, t, \iota _k}''$ from $\mathbb {Z}_q$ and set $\textsf {H}_2(j~ \Vert ~\iota _k~ \Vert ~\mathcal {I}) = g_2^{h_{2, t, \iota _k}''}$. The reduction stores the hash queries for future use.

• 3. $\boldsymbol{\textsf {H}_3}$ queries. If $(\textsf{GID}, S_{\phi }, \boldsymbol{u}_{\phi }, \mathcal {I}_{\boldsymbol{u}_{\phi }}) \in \mathcal {Q}$ and $S_{\phi } \cap \rho ([\ell ]) \ne \emptyset$ and $\rho ^{-1}(S_{\phi } \cup \mathcal {C})$ constitutes an unauthorized subset of the rows of $\boldsymbol{\textrm{M}}$ then sample $h_{3, j, \iota _k}$ for $j \in \{2, \dots , \widehat{s_{\textsf{max}}}\}$ (in Eq. 5.5) and elements $h_{3, j, \iota _k}'$ for $j \in \{\widehat{s_{\textsf{max}}}+1, \dots , s_{\textsf{max}}\}$ from $\mathbb {Z}_q$ (in Eq. 5.6) and set

  $$\begin{aligned} \textsf {H}_3(\textsf{GID}~ \Vert ~\boldsymbol{u}_{\phi } ~ \Vert ~j ~ \Vert ~\iota _k)&= (g_2^b)^{\eta _k \sum _{\phi '\in [Q]\setminus \{\phi \}} - d_{\phi ', j}}\cdot g_2^{h_{3, j, \iota _k}}\end{aligned}$$

  (5.5)
  $$\begin{aligned} \textsf {H}_3(\textsf{GID}~ \Vert ~\boldsymbol{u}_{\phi } ~ \Vert ~j ~ \Vert ~\iota _k)&= g_2^{h_{3, j, \iota _k}'} \end{aligned}$$

  (5.6)

  for all $\iota _k \in \mathcal {I}_{\boldsymbol{u}_{\phi }}$ such that $\mathcal {I}_{\boldsymbol{u}_{\phi }} = \mathcal {I}^*$ and $\boldsymbol{d}_\phi$ is as defined above. If $(\textsf{GID}, S_{\phi }, \boldsymbol{u}_{\phi }, \mathcal {I}_{\boldsymbol{u}_{\phi }}) \in \mathcal {Q}$ and $S_{\phi } \cap \rho ([\ell ]) \ne \emptyset$ and $\mathcal {I}_{\boldsymbol{u}_{\phi }} \ne \mathcal {I}^*$ then sample $h_{3, j, \iota _k}''$ uniformly at random from $\mathbb {Z}_q$ and set $\textsf {H}_3(\textsf{GID}~ \Vert ~\boldsymbol{u}_{\phi } ~ \Vert ~j ~ \Vert ~\iota _k) = g_2^{h_{3, j, \iota _k}''}$.

  On the other hand, if $(\textsf{GID}, S_{\phi }, \boldsymbol{u}_{\phi }, \mathcal {I}_{\boldsymbol{u}_{\phi }}) \in \mathcal {Q}$ and $S_{\phi } \cap \rho ([\ell ]) \ne \emptyset$ and $\rho ^{-1}(S_{\phi } \cup \mathcal {C})$ constitutes an authorized subset of the rows of $\boldsymbol{\textrm{M}}$ then sample $h_{3, j, \iota _k}''' \leftarrow \mathbb {Z}_q$ and set $\textsf {H}_3(\textsf{GID}~ \Vert ~\boldsymbol{u}_{\phi } ~ \Vert ~j ~ \Vert ~\iota _k) = g_2^{h_{3, j, \iota _k}'''}$. The reduction stores the hash queries for future use. For all other cases, the reduction simple outputs a uniformly random element from $\mathbb {G}_2$ to answer the hash query $\textsf {H}_3(\textsf{GID}~ \Vert ~\boldsymbol{u}_{\phi } ~ \Vert ~j ~ \Vert ~\iota _k)$.

Generating Secret Keys: For any $(\textsf{GID}, S_{\phi },\boldsymbol{u}_{\phi }, \mathcal {I}_{\boldsymbol{u}_\phi }) \in \mathcal {Q}$, $\mathcal {B}$ returns a secret key $\textsf{SK}_{\textsf{GID}, S_{\phi }, \boldsymbol{u}_{\phi }} =\left( \textsf{GID}, \boldsymbol{u}_{\phi },\{\textsf{SK}_{t,\boldsymbol{u}_{\phi }}\}_{t\in S_{\phi }}, \mathcal {I}_{\boldsymbol{u}_{\phi }}\right)$, where it computes each of its components as follows. We denote

$$\begin{aligned} \textsf {H}_{2\cdot 3}(\textsf{GID}, \boldsymbol{u}_{\phi }, j, k) = \textsf {H}_2( j ~ \Vert ~\iota _k~ \Vert ~\mathcal {I}_{\boldsymbol{u}_{\phi }}) \cdot \textsf {H}_3(\textsf{GID}~ \Vert ~\boldsymbol{u}_{\phi } ~ \Vert ~j ~ \Vert ~\iota _k) \end{aligned}$$

for simplifying the representation of equations. For each $t \in S_{\phi }$ and $\mathcal {I}_{\boldsymbol{u}_{\phi }}$, it has four different cases to consider:

• 1. Case 1—($t \in S_{\phi } \setminus \rho ([\ell ])$) (i.e., the attribute is absent in the challenge policy $(M,\rho )$)—In this case, $\mathcal {B}$ simulates the secret keys according to the real experiment. It knows $\alpha _t, y_{t, j}$ for all $j \in \{2,\ldots , s_{\textsf{max}}\}$ in clear and hence can compute

  $$\displaystyle \textsf{SK}_{\phi , t, \boldsymbol{u}_{\phi }} = (\prod _{k =1}^n \textsf {H}_1(t~ \Vert ~\iota _k~ \Vert ~\mathcal {I}_{\boldsymbol{u}_{\phi }})^{\alpha _t u_{\iota _k}})\cdot \prod _{j=2}^{s_{\textsf{max}}} \prod _{k =1}^n \textsf {H}_{2\cdot 3}(\textsf{GID}, \boldsymbol{u}_{\phi }, j, k)^{y_{t, j}u_{\iota _k} } $$

  where $\textsf {H}_3(\textsf{GID}~ \Vert ~\boldsymbol{u}_{\phi } ~ \Vert ~j ~ \Vert ~\iota _k)$ were sampled uniformly.

• 2. Case 2—$(t \in S_{\phi } \cap \rho ([\ell ]) \wedge \mathcal {I}_{\boldsymbol{u}_{\phi }} \ne \mathcal {I}^*)$ (i.e., the attribute is present in the challenge policy, but the associated index set does not match with the challenge index set) In this case, $\mathcal {B}$ extracts the corresponding exponents of the hash values from the list of hash queries and computes

  $$\begin{aligned}\textsf{SK}_{\phi , t, \boldsymbol{u}_{\phi }} = (\prod _{k =1}^n \textsf {H}_1(t~ \Vert ~\iota _k ~ \Vert ~\mathcal {I}_{\boldsymbol{u}_{\phi }})^{\alpha _t u_{\iota _k}})\cdot \prod _{j=2}^{s_{\textsf{max}}} \prod _{k =1}^n \textsf {H}_{2\cdot 3}(\textsf{GID}, \boldsymbol{u}_{\phi }, j, k)^{y_{t, j}u_{\iota _k} } \end{aligned}$$

  where $\textsf {H}_3(\textsf{GID}~ \Vert ~\boldsymbol{u}_{\phi } ~ \Vert ~j ~ \Vert ~\iota _k) = g_2^{h_{3, j, \iota _k}''}$ were sampled uniformly from $\mathbb {Z}_q$.

• 3. Case 3—$(t \in S_{\phi } \cap \rho ([\ell ]) \wedge \mathcal {I}_{\boldsymbol{u}_{\phi }} = \mathcal {I}^*) \text { and } \rho ^{-1}(\mathcal {C} \cup S_{\phi })$ constitutes an unauthorized subset of the rows of $\boldsymbol{\textrm{M}}$ (i.e., $S_{\phi }$ does not satisfy the challenge policy $(\boldsymbol{\textrm{M}},\rho )$). Note that the inner product value ${(\boldsymbol{v}_0 -\boldsymbol{v}_1)} \cdot {\boldsymbol{u}_{\phi }}$ can be either zero or non-zero in this case. Since $S_{\phi }$ does not satisfy the challenge policy $(\boldsymbol{\textrm{M}},\rho )$, there exists a vector $\boldsymbol{d}_{\phi } = (d_{\phi , 1}, \dots , d_{\phi , s_{\textsf{max}}}) \in \mathbb {Z}_q^{s_{\textsf{max}}}$ such that $d_{\phi , 1} = 1$ and the inner product $\boldsymbol{M}_i' \star \boldsymbol{d}_{\phi } = 0$ for all $i \in \rho ^{-1}(S_{\phi })$, where $\boldsymbol{M}_i'$ denotes the i-th row of $\boldsymbol{\textrm{M}}'$. $\mathcal {B}$ computes the secret key $\textsf{SK}_{t, \boldsymbol{u}}$ as follows.

  $$\begin{aligned} \textsf{SK}_{\phi , t, \boldsymbol{u}_{\phi }}&= (\prod _{k =1}^n \textsf {H}_1(t~ \Vert ~\iota _k~ \Vert ~\mathcal {I}_{\boldsymbol{u}_{\phi }})^{\alpha _t u_{\iota _k}})\cdot \prod _{j=2}^{s_{\textsf{max}}} \prod _{k =1}^n \textsf {H}_{2\cdot 3}(\textsf{GID}, \boldsymbol{u}_{\phi }, j, k)^{y_{t, j}u_{\iota _k} }\\&= (\prod _{k=1}^n (g_2^{ab})^{\eta _kM_{\rho ^{-1}(t), 1}'u_{\iota _k}} ) \cdot \prod _{j=2}^{\widehat{s_{\textsf{max}}}} \prod _{k =1}^n (g_2^{ab})^{\eta _k d_{\phi , j}M_{\rho ^{-1}(t), j}'u_{\iota _k}} \cdot g_2^{L_{\phi }(a, b)}\\&= \prod _{j=1}^{\widehat{s_{\textsf{max}}}} \prod _{k =1}^n (g_2^{ab})^{\eta _k d_{\phi , j}M_{\rho ^{-1}(t), j}'u_{\iota _k}} \cdot g_2^{L_{\phi }(a, b)}\\&= \prod _{k=1}^n (g_2^{ab})^{\eta _ku_{\iota _k}(\boldsymbol{M}_{\rho ^{-1}(t)}' \star \boldsymbol{d}_{\phi } )} \cdot g_2^{L_{\phi }(a, b)} = g_2^{L_{\phi }(a, b)} \end{aligned}$$

  where $L_{\phi }(a, b)$ represents a linear function in a, b and hence $g_2^{L_{\phi }(a, b)}$ can be efficiently computable by $\mathcal {B}$. The first equality follows from the definition of $\alpha _t, y_{t, j}$ (Eq. (5.1)) and the hash functions $\textsf {H}_1$ (Eq. (5.2)), $\textsf {H}_2$ (Eqs. (5.3) and (5.4)) and $\textsf {H}_3$ (Eqs. (5.5) and (5.6)). The last equality holds since $\boldsymbol{M}_{\rho ^{-1}(t)}' \star \boldsymbol{d}_{\phi } = 0$ and the second last equality holds since $d_{\phi , 1} = 1$.

• 4. Case 4—$(t \in S_{\phi } \cap \rho ([\ell ]) \wedge \mathcal {I}_{\boldsymbol{u}_{\phi }} = \mathcal {I}^*) \text { and } \rho ^{-1}(S_{\phi })$ constitutes an authorized subset of rows of $\boldsymbol{\textrm{M}}$ (i.e., $S_{\phi }$ satisfies the challenge policy $(\boldsymbol{\textrm{M}},\rho )$) – In this case, $\mathcal {B}$ computes the secret key $\textsf{SK}_{\phi , t,\boldsymbol{u}_{\phi }}$ as follows.

  $$\begin{aligned} \textsf{SK}_{\phi , t, \boldsymbol{u}_{\phi }}&= (\prod _{k =1}^n \textsf {H}_1(t~ \Vert ~\iota _k~ \Vert ~\mathcal {I}_{\boldsymbol{u}_{\phi }})^{\alpha _t u_{\iota _k}})\cdot \prod _{j=2}^{s_{\textsf{max}}} \prod _{k =1}^n \textsf {H}_{2\cdot 3}(\textsf{GID}, \boldsymbol{u}_{\phi }, j, k)^{y_{t, j}u_{\iota _k} }\\&= (\prod _{k=1}^n (g_2^{ab})^{\eta _kM_{\rho ^{-1}(t), 1}'u_{\iota _k}} ) \cdot \prod _{j=2}^{\widehat{s_{\textsf{max}}}} \prod _{k =1}^n ( (g_2^{ab})^{\eta _k\sum _{\phi = 1}^Q d_{\phi , j}})^{M_{\rho ^{-1}(t), j}'u_{\iota _k}} \cdot g_2^{L_{\phi }(a, b)}\\&= \left[ (g_2^{ab})^{\eta _kM_{\rho ^{-1}(t), 1}'} \cdot \prod _{j=2}^{\widehat{s_{\textsf{max}}}} (g_2^{ab})^{\eta _k\sum _{\phi = 1}^Q d_{\phi , j} M_{\rho ^{-1}(t), j}'} \right] ^{\boldsymbol{\eta }\cdot \boldsymbol{u}_{\phi }} \cdot g_2^{L_{\phi }(a, b)} = g_2^{L_{\phi }(a, b)} \end{aligned}$$

  where the last equality follows from the fact that ${\boldsymbol{\eta }} \cdot {\boldsymbol{u}_{\phi }} = 0$ if the secret key query satisfies the condition ${(\boldsymbol{v}_0-\boldsymbol{v}_1)} \cdot {\boldsymbol{u}_{\phi }} = 0$ as $S_{\phi }$ is authorized. Hence, in this case, $\mathcal {B}$ can efficiently simulates the secret key as $L_{\phi }(a, b)$ is linear in a, b.

Generating the Challenge Ciphertext: $\mathcal {B}$ implicitly sets the vectors

$$\begin{aligned} \begin{aligned} \boldsymbol{z}&= - abc\cdot \boldsymbol{\eta } = -abc (\eta _1, \dots , \eta _n) \in \mathbb {Z}_q^n,\\ \boldsymbol{x}_j&= - (ac, \dots , ac) \in \mathbb {Z}_q^n, f_j = -ac \in \mathbb {Z}_q,~~~~\forall j \in \{2,\ldots , \widehat{s_{\textsf{max}}}\},\\ \boldsymbol{x}_j&= \boldsymbol{0} \in \mathbb {Z}_q^n,~~ f_j = 0 \in \mathbb {Z}_q, ~~~~\forall j \in \{\widehat{s_{\textsf{max}}}+1,\ldots , s_{\textsf{max}}\} \end{aligned}\end{aligned}$$

There are two cases to consider according to the authority whether it is corrupted or non-corrupted.

• 1. Case 1—$\rho (i) \in \mathcal {C}$ (meaning that the authority associated with this row is corrupted)—In this case, it holds that $\boldsymbol{M}_i^{\prime }\boldsymbol{\textrm{B}} = \boldsymbol{0}$ and $M_{i, j}^{\prime } \boldsymbol{x}_j = 0$ for all $(i, j) \in \rho ^{-1}(\mathcal {C}) \times [\widehat{s_{\textsf{max}}}]$ since $\boldsymbol{M}_i^{\prime }|_{[\widehat{s_{\textsf{max}}}]} = \bigg \{ \overset{\widehat{s_{\textsf{max}}}}{\overbrace{0, \dots , 0}} \bigg \}$ and due to the above implicit setting of $\boldsymbol{\textrm{B}}, \boldsymbol{x}_j$. Thus, for each such row, $\mathcal {B}$ picks $r_i \leftarrow \mathbb {Z}_q$, and using the authority public key $\textsf{PK}_{\rho (i)} = (\textrm{Y}_{\rho (i), 1}, \textrm{Y}_{\rho (i), 2}, \dots , \textrm{Y}_{\rho (i), s_{\textsf{max}}})$ obtained from $\mathcal {A}$, it computes

  $$ \begin{aligned} C_0&= [\![ \boldsymbol{v}_{\beta } + z]\!]_T, ~~ C_{1, i} = [\![\boldsymbol{M}_i^{\prime }\boldsymbol{\textrm{B}} + \boldsymbol{\vartheta }_i]\!]_T = [\![\boldsymbol{\vartheta }_i]\!]_T, ~~ C_{2, i} = [\![r_i]\!]_1,\\ C_{3, i, j, k}&= e([\![M_{i, j}'x_{j, k}]\!]_1, \textsf {H}_2(j~ \Vert ~\iota _k~ \Vert ~\mathcal {I}^*))\cdot e(r_i[\![\textrm{Y}_{\rho (i), j}]\!]_1, \textsf {H}_2(j~ \Vert ~\iota _k~ \Vert ~\mathcal {I}^*))\\&= e(r_i[\![\textrm{Y}_{\rho (i), j}]\!]_1, \textsf {H}_2(j~ \Vert ~\iota _k~ \Vert ~\mathcal {I}^*)) \\ C_{4, i, j}&= [\![M_{i, j}'f_j + \textrm{Y}_{\rho (i), j}r_i]\!]_1 = [\![\textrm{Y}_{\rho (i), j}r_i]\!]_1 \end{aligned}$$

  for all $i \in [\ell ], j \in \{2, \ldots , s_{\textsf{max}}\}$ and $k \in [n]$, where $\boldsymbol{\vartheta }_i = (\vartheta _{i, 1}, \dots , \vartheta _{i, m})$ and

  $$\begin{aligned} \vartheta _{i, k}&= e( r_i[\![\textrm{Y}_{\rho (i)}]\!]_1, \textsf {H}_1(\rho (i)~ \Vert ~\iota _k~ \Vert ~\mathcal {I}^*)). \end{aligned}$$

• 2. Case 2—$\rho (i) \in \mathcal {N}$ (meaning that the authority associated with this row is uncorrupted)—Firstly, $\mathcal {B}$ sets $C_0 = [\![\boldsymbol{v}_{\beta } + \boldsymbol{z}]\!]_T$ where $\beta$ is the challenge bit for $\mathcal {A}$. It also implicitly sets $r_i = c$ and the matrix $\boldsymbol{\textrm{B}} = (\boldsymbol{z}, \boldsymbol{0}, \cdots , \boldsymbol{0})^{\top } \in \mathbb {Z}_q^{s_{\textsf{max}}\times n}$. This implies $\boldsymbol{M}_i'\boldsymbol{\textrm{B}} = M_{i, 1}' \boldsymbol{z} = -M_{i, 1}'\cdot abc\cdot \boldsymbol{\eta }$ and the k-th element of the vector is $(\boldsymbol{M}_i'\boldsymbol{\textrm{B}})_k = - M_{i, 1}'abc\eta _k$. Recall that, for each $i \in [\ell ]$, we have $\alpha _{\rho (i)} = \alpha _{\rho (i)}^{\prime } + a \cdot M_{i, 1}'$ and $y_{\rho (i), j} = y_{\rho (i), j}^{\prime } + a M_{i, j}^{\prime }$. Now, $\mathcal {B}$ implicitly computes the vector $\boldsymbol{\vartheta }_i {:}{=}(\vartheta _{i, 1}, \dots , \vartheta _{i, m})$ as

  $$\begin{aligned} \vartheta _{i, k}&= e( r_i[\![\alpha _{\rho (i)}]\!]_1, \textsf {H}_1(\rho (i)~ \Vert ~\iota _k~ \Vert ~\mathcal {I}^*)) \\&= e( [\![c\alpha _{\rho (i)}^{\prime } + ac \cdot M_{i, 1}']\!]_1, [\![b\eta _k + \sum _{\widehat{k}=1}^{n-1} h_{1, \widehat{k}}\lambda _{k, \widehat{k}} + h_{1, \rho (i), \iota _k}]\!]_2) \\&= [\![ bc\alpha _{\rho (i)}^{\prime } \eta _k + M_{i, 1}'abc \eta _k + (c\alpha _{\rho (i)}^{\prime } + ac \cdot M_{i, 1}') \mathfrak {h}_{1, i, k}]\!]_T \end{aligned}$$

  where $\mathfrak {h}_{1, i, k} = \sum _{\widehat{k}=1}^{n-1} h_{1, \widehat{k}}\lambda _{k, \widehat{k}} + h_{1, \rho (i), \iota _k}$. We write $\boldsymbol{\mathfrak {h}}_{1, i} = (h_{1, \rho (i), \iota _k})_{k=1}^n$. Thus, for each $i\in [\ell ]$, $\mathcal {B}$ sets $C_{2, i} = [\![c]\!]_1$ and computes

  $$ \begin{aligned} C_{1, i}&= [\![\boldsymbol{M}_i\boldsymbol{\textrm{B}} + \boldsymbol{\vartheta }_i]\!]_T = [\![bc\alpha _{\rho (i)}^{\prime }\boldsymbol{\eta } + (c\alpha _{\rho (i)}^{\prime } + ac \cdot M_{i, 1}') \boldsymbol{\mathfrak {h}}_{1, i} ]\!]_T&\\&= e(g_1^c, g_2^b)^{\alpha _{\rho (i)}^{\prime }\boldsymbol{\eta }}\cdot e(g_1^c, g_2)^{\alpha _{\rho (i)}^{\prime }\boldsymbol{\mathfrak {h}}_i }\cdot e(g_1^c, g_2^a)^{M_{i, 1}'\boldsymbol{\mathfrak {h}}_{1, i}}&\end{aligned}$$

  Next, $\mathcal {B}$ computes $C_{3, i, j, k}$ as follows. Recall that $C_{3, i, j, k}$ is a product of two pairing operations. Note that, $M_{i, j}'x_{j, k} = 0$ if $j \in \{\widehat{s_{\textsf{max}}}+1, \ldots , s_{\textsf{max}}\}$. Thus, for $j \in \{2, \ldots , \widehat{s_{\textsf{max}}}\}$, the first pairing is computed as

  $$\begin{aligned}&e([\![M_{i, j}'x_{j, k}]\!]_1, \textsf {H}_2(j~ \Vert ~\iota _k~ \Vert ~\mathcal {I}^*))&\\&= e([\![M_{i, j}'x_{j, k}]\!]_1, (g_2^b)^{\eta _k\sum _{\phi =1}^Q d_{\phi , j}} \cdot \prod _{\widehat{k}=1}^{n-1} g_2^{h_{2, \widehat{k}}\lambda _{k, \widehat{k}}}\cdot g_2^{h_{2, \rho (i), \iota _k}})&\\&=[\![ M_{i, j}'x_{j, k}b\eta _k d_{j}^{+} + M_{i, j}' x_{j, k} \mathfrak {h}_{2, i, k} ]\!]_T&\\ \end{aligned}$$

  where $d_{j}^{+} = \sum _{\phi =1}^{Q} d_{\phi , j}$ and $\mathfrak {h}_{2, i, k} = \sum _{\widehat{k}=1}^{n-1} h_{2, \widehat{k}}\lambda _{k, \widehat{k}} + h_{2, \rho (i), \iota _k}$. If $j \in \{2, \ldots , \widehat{s_{\textsf{max}}}\}$, the second pairing is computed as

  $$ \begin{aligned}&e(r_i[\![y_{\rho (i), j}]\!]_1, \textsf {H}_2(j~ \Vert ~\iota _k~ \Vert ~\mathcal {I}^*))&\\&= e([\![cy_{\rho (i), j}^{\prime } + ac M_{i, j}^{\prime }]\!]_1, (g_2^b)^{\eta _k\sum _{\phi =1}^Q d_{\phi , j}} \cdot \prod _{\widehat{k}=1}^{n-1} g_2^{h_{2, \widehat{k}}\lambda _{k, \widehat{k}}}\cdot g_2^{h_{2, \rho (i), \iota _k}})&\\&=[\![ bc(y_{\rho (i), j}^{\prime } + a M_{i, j}')\eta _k d_{j}^{+} + c(y_{\rho (i), j}^{\prime } + a M_{i, j}') \mathfrak {h}_{2, i, k} ]\!]_T&\\ \end{aligned}$$

  Finally, for each $i \in [\ell ], j\in \{2, \dots , \widehat{s_{\textsf{max}}}\}, k \in [n]$, the ciphertext component $C_{3, i, j, k}$ is obtained as

  $$\begin{aligned} C_{3, i, j, k}&= e([\![M_{i, j}'x_{j, k}]\!]_1, \textsf {H}_2(j~ \Vert ~\iota _k~ \Vert ~\mathcal {I}^*))\cdot e(r_i[\![y_{\rho (i), j}]\!]_1, \textsf {H}_2(j~ \Vert ~\iota _k~ \Vert ~\mathcal {I}^*))\\&= [\![bcy_{\rho (i), j}^{\prime } \eta _k d_{j}^{+} + c y_{\rho (i), j}^{\prime } \mathfrak {h}_{2, i, k}]\!]_T \\&= e(g_1^c, g_2^b)^{y_{\rho (i), j}^{\prime } \eta _k d_{j}^{+}} \cdot e(g_1^c, g_2)^{y_{\rho (i), j}^{\prime } \mathfrak {h}_{2, i, k}} \end{aligned}$$

  which $\mathcal {B}$ can compute as a part of the challenge ciphertext. Now, if $j \in \{\widehat{s_{\textsf{max}}}+1, \ldots , s_{\textsf{max}}\}$, recall that $y_{\rho (i), j}$ are known is clear and hence $\mathcal {B}$ computes $C_{3, i, j, k}$ as

  $$ \begin{aligned} C_{3, i, j, k}&= e([\![M_{i, j}'x_{j, k}]\!]_1, \textsf {H}_2(j~ \Vert ~\iota _k~ \Vert ~\mathcal {I}^*))\cdot e(r_i[\![y_{\rho (i), j}]\!]_1, \textsf {H}_2(j~ \Vert ~\iota _k~ \Vert ~\mathcal {I}^*))\\&= e(r_i[\![y_{\rho (i), j}]\!]_1, [\![h_{2, j, \iota _k}']\!]_2) = e(g_1^c, g_2)^{y_{\rho (i), j} h_{2, j, \iota _k}'} \end{aligned}$$

  for all $i \in [\ell ], k \in [n]$. The last remaining part $C_{4, i, j}$ is given by

  $$\begin{aligned} C_{4, i, j}&= [\![M_{i, j}'f_j + y_{\rho (i), j}r_i]\!]_1 = [\![-ac M_{i, j}' + cy_{\rho (i), j}^{\prime } + ac M_{i, j}^{\prime } ]\!]_1 = (g_1^c)^{y_{\rho (i), j}^{\prime }} \end{aligned}$$

  if $i \in [\ell ], j \in \{2, \ldots , \widehat{s_{\textsf{max}}}\}$. Note that, $M_{i, j}'f_j = 0$ and $y_{\rho (i), j}$ are known in clear for $j \in \{\widehat{s_{\textsf{max}}}+1, \ldots , s_{\textsf{max}}\}$. Hence, $\mathcal {B}$ computes $C_{4, i, j}$ as

  $$\begin{aligned} C_{4, i, j}&= [\![M_{i, j}'f_j + y_{\rho (i), j}r_i]\!]_1 = [\![cy_{\rho (i), j}]\!]_1 = (g_1^c)^{y_{\rho (i), j}} \end{aligned}$$

  for each $i \in [\ell ], j \in \{2, \dots , s_{\textsf{max}}\}$. Observe that, the elements $\boldsymbol{\textrm{B}}, \boldsymbol{x}_j, f_j$ and $r_i$ are not properly distributed. Thus, $\mathcal {B}$ re-randomizes the ciphertext components using the algorithm $\textsf{CTRand}$ described below before it sends to $\mathcal {A}$.

Ciphertext Re-randomization Algorithm: The algorithm described below provides properly distributed ciphertexts even if the randomness used within the ciphertexts inputted into the algorithm are not uniform. The algorithm uses only publicly available information to perform the re-randomization and hence rectify the distribution of the challenge ciphertext in the reduction.

$\boldsymbol{\textsf{CTRand}((\boldsymbol{\textrm{M}}, \rho ), \textsf{CT}, \textsf{PK})}$: The algorithm takes input an $\textsf{LSSS}$ access policy $(\boldsymbol{\textrm{M}}, \rho )$, where $\boldsymbol{\textrm{M}} = (M_{i, j})_{\ell \times s_{\textsf{max}}} = (\boldsymbol{M}_1, \dots , \boldsymbol{M}_{\ell })^{\top } \in \mathbb {Z}_q^{\ell \times s_{\textsf{max}}}$ and $\rho : [\ell ] \rightarrow \textsf{U}_\textsf{att}$, a ciphertext $\textsf{CT}= \left( \left( \boldsymbol{\textrm{M}}, \rho \right) , C_0, \{C_{1, i}, C_{2,i,}, C_{3,i,j,k}, C_{4, i, j}\}_{i \in [\ell ], j\in \{2,\ldots , s_{\textsf{max}}\}, k \in [m]}, \mathcal {I}_{\boldsymbol{v}}\right)$, and the public key components $\textsf{PK}$ such that $\rho ([\ell ]) \subseteq \textsf{U}_\textsf{att}$.

• 1. Sample

  • (a) $r_1^{\prime }, \dots , r_{\ell }^{\prime } \leftarrow \mathbb {Z}_q; \boldsymbol{x}_2^{\prime }, \dots , \boldsymbol{x}_{s_{\textsf{max}}}^{\prime } \in \mathbb {Z}_q^{n}; f_2^{\prime }, \dots , f_{s_{\textsf{max}}}^{\prime } \in \mathbb {Z}_q$,

  • (b) $\boldsymbol{\textrm{B}}^{\prime } = (\boldsymbol{z}^{\prime }, \boldsymbol{b}_2^{\prime }, \dots , \boldsymbol{b}_{s_{\textsf{max}}}^{\prime })^{\top } \in \mathbb {Z}_q^{s_{\textsf{max}}\times n}$,

• 2. Compute $C_0^{\prime } = C_0 \cdot [\![\boldsymbol{z}^{\prime }]\!]_T$.

• 3. For all $i \in [\ell ]$, $j \in \{2,\ldots , s_{\textsf{max}}\}$ and $k \in [n]$, compute

  $$\begin{aligned} C_{1, i}^{\prime }&= C_{1, i} \cdot [\![\boldsymbol{M}_i \boldsymbol{\textrm{B}}^{\prime } + \boldsymbol{\vartheta }_i']\!]_T , ~~C_{2, i}^{\prime } = C_{2, i}\cdot [\![r_i^{\prime }]\!]_1,{} & {} {} & {} \\ C_{3, i, j, k}^{\prime }&= C_{3, i, j, k} \cdot e([\![M_{i, j}x_{j, k}']\!]_1, \textsf {H}_2(j~ \Vert ~\iota _k~ \Vert ~\mathcal {I}^*))\cdot e(r_i'[\![y_{\rho (i), j}]\!]_1, \textsf {H}_2(j~ \Vert ~\iota _k~ \Vert ~\mathcal {I}^*)){} & {} {} & {} \\ C_{4, i, j}'&= C_{4,i, j}\cdot [\![M_{i, j}f_j' + y_{\rho (i), j}r_i']\!]_1{} & {} {} & {} \end{aligned}$$

  where $\boldsymbol{\vartheta }_i' = (\vartheta _{i, 1}', \dots , \vartheta _{i, n}')$ and $\vartheta _{i, k}' = e( r_i'[\![\alpha _{\rho (i)}]\!]_1, \textsf {H}_1(\rho (i)~ \Vert ~\iota _k~ \Vert ~\mathcal {I}^*))$.

• 4. Output the ciphertext $\textsf{CT}= \left( \left( \boldsymbol{\textrm{M}}, \rho \right) , C_0', \{C_{1, i}', C_{2,i,}', C_{3,i,j,k}', C_{4, i, j}'\}_{i \in [\ell ], j\in \{2,\ldots , s_{\textsf{max}}\}, k \in [m]}, \mathcal {I}_{\boldsymbol{v}}\right)$.

Guess: If $\mathcal {A}$ guesses the challenge bit $\beta \in \{0, 1\}$ correctly, $\mathcal {B}$ returns 1; Otherwise $\mathcal {B}$ outputs 0. Now, observe that $\boldsymbol{z} = -\tau \cdot \boldsymbol{\eta }$ where $[\![\tau ]\!]_T$ is the $\textsf{DBDH}$ challenge element. If $\tau = abc$, then all the secret keys and the challenge ciphertext are distributed properly, in particular, the challenge ciphertext is an encryption of the message vector $\boldsymbol{v}_{\beta }$ for $\beta \leftarrow \{0, 1\}$. Therefore, in this case, $\mathcal {A}$ outputs $\beta ^{\prime } = \beta$ with probability $1/2 + \epsilon (\lambda )$ where $\epsilon (\lambda )$ is the advantage of $\mathcal {A}$ in the static security game of the $\textsf{MA}\text {-}\textsf{ABUIPFE}$ scheme. On the other hand, if $\tau$ is a random element of $\mathbb {Z}_q$ then the ciphertext element $C_0$ is uniformly random in $\mathbb {G}_T$, and hence from $\mathcal {A}$’s point of view there is no information of the challenge bit $\beta$ in the challenge ciphertext. So, the probability of $\mathcal {A}$ outputting $\beta ^{\prime } = \beta$ is exactly 1/2. Hence, by the guarantee of $\textsf{DBDH}$ assumption, $\mathcal {A}$ has a non-negligible advantage against the proposed $\textsf{MA}\text {-}\textsf{ABUIPFE}$ scheme in the static security game. This completes the proof.    $\square$

6 The Proposed Large Universe $\textsf{MA}\text {-}\textsf{ABUIPFE}$ from L-$\textsf{DBDH}$

In this section, we describe the construction of our $\textsf{LMA}\text {-}\textsf{ABUIPFE}$ scheme. The construction is in prime-order groups and additionally uses hash functions that are modelled as random oracles in the security proof just like our small universe construction.

$\boldsymbol{\textsf{GlobalSetup}(1^{\lambda }, s_{\textsf{max}})}$: The global setup algorithm takes input the security parameter $\lambda$ and a vector length n both in unary, and the maximum width of an $\textsf{LSSS}$ matrix supported by the scheme $s_{\textsf{max}}= s_{\textsf{max}}(\lambda )$. It generates $\textsf{G} = (q, \mathbb {G}_1, \mathbb {G}_2, \mathbb {G}_T, g, e)$ and specify hash functions $\textsf {H}_1 : \textsf{U}_\textsf{att}\times \mathbb {Z} \times \mathbb {Z}^* \rightarrow \mathbb {G}_2$, $\textsf {H}_2: [s_{\textsf{max}}] \times \mathbb {Z} \times \mathbb {Z}^* \rightarrow \mathbb {G}_2$, $\textsf {H}_3 : \mathcal {GID} \times \mathbb {Z}^* \times [s_{\textsf{max}}] \times \mathbb {Z} \rightarrow \mathbb {G}_2$ and $\mathsf {R:} \textsf{U}_\textsf{att}\times [s_{\textsf{max}}] \times \mathbb {Z}^* \rightarrow \mathbb {G}_2$ mapping strings $(t, j) \in \textsf{U}_\textsf{att}\times [s_{\textsf{max}}]$ to elements in $\mathbb {G}_2$. It outputs a global parameter $\textsf{GP}= (\textsf{G}, \textsf {H}_1, \textsf {H}_2, \textsf {H}_3, \textsf{R})$.

$\boldsymbol{\textsf{LocalSetup}(\textsf{GP}, \theta )}$: The authority setup algorithm takes input the global parameter $\textsf{GP}$ and an authority index $\theta \in \mathcal{A}\mathcal{U}$. It samples $\alpha _{\theta }, y_{\theta , 2}, \dots , y_{\theta , s_{\textsf{max}}} \leftarrow \mathbb {Z}_q$ and outputs $\textsf{PK}_{\theta } = ([\![\alpha _{\theta }]\!]_1, [\![y_{\theta , 2}]\!]_1, \dots , [\![y_{\theta , s_{\textsf{max}}}]\!]_1) \text { and } \textsf{MSK}_{\theta } = (\alpha _{\theta }, y_{\theta , 2}, \dots , y_{\theta , s_{\textsf{max}}}).$

$\boldsymbol{\textsf{KeyGen}(\textsf{GP}, \textsf{GID}, \textsf{MSK}_{\theta }, t, \boldsymbol{u}, \mathcal {I}_{\boldsymbol{u}})}$: The key generation algorithm takes input $\textsf{GP}$, the user’s global identifier $\textsf{GID}$, the authority’s secret key $\textsf{MSK}_{\theta }$, an attribute t controlled by the authority and a vector $\boldsymbol{u} \in \mathbb {Z}_q^{|\mathcal {I}_{\boldsymbol{u}}|}$. It samples $\tau _j \leftarrow \mathbb {Z}_p$ for $j \in [s_{\textsf{max}}]$ and proceeds as follows:

• 1. Parse $\mathcal {I}_{\boldsymbol{u}} = \{\iota _1, \dots , \iota _n\}$ and $\boldsymbol{u} = (u_{\iota _1}, \dots , u_{\iota _n})$.

• 2. Compute

  $$\textsf{K}_{t, \boldsymbol{u}} = (\prod _{k =1}^n \textsf {H}_1(t~ \Vert ~\iota _k~ \Vert ~\mathcal {I}_{\boldsymbol{u}})^{\alpha _{\theta } u_{\iota _k}})\cdot \prod _{j=2}^{s_{\textsf{max}}} \prod _{k =1}^n (\textsf {H}_2( j ~ \Vert ~\iota _k~ \Vert ~\mathcal {I}_{\boldsymbol{u}}) \cdot \textsf {H}_3(\textsf{GID}~ \Vert ~\boldsymbol{u} ~ \Vert ~j~ \Vert ~\iota _k))^{y_{\theta , j}u_{\iota _k} }.$$

• 3. Compute $\textsf{SK}_{t, \boldsymbol{u}} = \textsf{K}_{t, \boldsymbol{u}} \cdot \prod _{j=1}^{s_{\textsf{max}}} \textsf{R}(t ~ \Vert ~j ~ \Vert ~\mathcal {I}_{\boldsymbol{u}})^{\tau _j}$ and $\textsf{Z}_{t}^{(j)} = [\![\tau _j]\!]_1 ~\forall ~ j \in [s_{\textsf{max}}]$.

Output $\textsf{SK}_{\textsf{GID}, t, \boldsymbol{u}} = (\textsf{GID}, \boldsymbol{u}, \textsf{SK}_{t, \boldsymbol{u}}, \textsf{Z}_t^{(j)}, \mathcal {I}_{\boldsymbol{u}})$.

$\boldsymbol{\textsf{Encrypt}(\textsf{GP}, (\boldsymbol{\textrm{M}}, \delta ), \{\textsf{PK}_{\theta }\}, \boldsymbol{v}, \mathcal {I}_{\boldsymbol{v}})}$: The encryption algorithm takes input the global parameter $\textsf{GP}$, an $\textsf{LSSS}$ access structure $(\boldsymbol{\textrm{M}}, \delta )$ where $\boldsymbol{\textrm{M}} = (\boldsymbol{M}_1, \dots , \boldsymbol{M}_{\ell })^{\top } \in \mathbb {Z}_q^{\ell \times s_{\textsf{max}}}$ and $\delta : [\ell ] \rightarrow \textsf{U}_\textsf{att}$, a set $\{\textsf{PK}_{\theta }\}$ of public keys for all the relevant authorities, and a message vector $\boldsymbol{v} \in \mathbb {Z}_q^m$. The function $\delta$ maps the row indices of $\boldsymbol{\textrm{M}}$ to attributes. We define the function $\rho : [\ell ] \rightarrow \mathcal{A}\mathcal{U}$ as $\rho (\cdot ) = \textsf{T}(\delta (\cdot ))$ which maps row indices of $\boldsymbol{\textrm{M}}$ to authorities. The algorithm proceeds as follows:

• 1. Parse $\mathcal {I}_{\boldsymbol{v}} = \{\iota _1, \dots , \iota _m\}$ and $\boldsymbol{v} = (v_{\iota _1}, \dots , v_{\iota _m})$.

• 2. Sample $\{r_i\leftarrow \mathbb {Z}_q\}_{i\in [\ell ]}$ and $\boldsymbol{f} = (f_2, \dots , f_{s_{\textsf{max}}}) \leftarrow \mathbb {Z}_q^{s_{\textsf{max}}-1}$.

• 3. Sample $\boldsymbol{z}, \boldsymbol{b}_2,\dots ,\boldsymbol{b}_{s_{\textsf{max}}}, \boldsymbol{x}_2, \dots , \boldsymbol{x}_{s_{\textsf{max}}}\leftarrow \mathbb {Z}_q^m$.

• 4. Set the matrix $\boldsymbol{\textrm{B}} = \begin{bmatrix} \boldsymbol{z}, \boldsymbol{b}_{2}, \ldots , \boldsymbol{b}_{s_{\textsf{max}}} \end{bmatrix}^{\top }_{s_{\textsf{max}}\times m}$.

• 5. Compute $\vartheta _{i, k} = e( r_i[\![\alpha _{\rho (i)}]\!]_1, \textsf {H}_1(\rho (i)~ \Vert ~\iota _k ~ \Vert ~\mathcal {I}_{\boldsymbol{v}}))$ and set $\boldsymbol{\vartheta }_i {:}{=}(\vartheta _{i, 1}, \dots , \vartheta _{i, m}).$

• 6. Compute the following terms:

  $$ \begin{array}{c } C_0 = [\![\boldsymbol{v} + \boldsymbol{z}]\!]_T, ~~~~ C_{1, i} = [\![\boldsymbol{M}_i \boldsymbol{\textrm{B}} + \boldsymbol{\vartheta }_i]\!]_T,~~~~ C_{2, i} = [\![r_i]\!]_1,\\ C_{3, i, j, k} = e([\![M_{i,j} x_{j, k}]\!]_1, \textsf {H}_2( j ~ \Vert ~\iota _k~ \Vert ~\mathcal {I}_{\boldsymbol{v}})) \cdot e(r_i [\![y_{\rho (i), j}]\!]_1, \textsf {H}_2( j ~ \Vert ~\iota _k~ \Vert ~\mathcal {I}_{\boldsymbol{v}})),\\ C_{4, i, j} = [\![M_{i, j} f_j + y_{\rho (i), j}r_i]\!]_1, \end{array} $$

  for all $i \in [\ell ], j \in \{2,\ldots , s_{\textsf{max}}\}, k \in [m]$.

• 7. Compute $C_{5, i, j} = \textsf{R}(\delta (i) ~ \Vert ~j ~ \Vert ~\mathcal {I}_{\boldsymbol{v}})^{r_i}$ for all $i \in [\ell ], j \in [s_{\textsf{max}}]$.

• 8. Output the ciphertext $\textsf{CT}= \left( \left( \boldsymbol{\textrm{M}}, \delta \right) , C_0, \{C_{1, i}, C_{2,i,}, C_{3,i,j,k}, C_{4, i, j}, C_{5,i,1}, C_{5,i,j}\}_{\begin{array}{c} j\in \{2,\ldots , s_{\textsf{max}}\},\\ i \in [\ell ],k \in [m] \end{array}}, \mathcal {I}_{\boldsymbol{v}}\right)$.

$\boldsymbol{\textsf{Decrypt}(\textsf{GP}, \textsf{GID}, \textsf{CT}, \{\textsf{SK}_{\textsf{GID}, t, \boldsymbol{u}}\})}$: It takes input the public key $\textsf{PK}$, a secret key $\textsf{SK}_{S, \boldsymbol{u}}$ for an attribute set $S\subseteq \textsf{U}_\textsf{att}$ and a vector $\boldsymbol{u}\in \mathbb {Z}^n_q$ and a ciphertext $\textsf{CT}$ for an access structure $(\boldsymbol{\textrm{M}}, \delta )$ with $\boldsymbol{\textrm{M}} \in \mathbb {Z}_q^{\ell \times s_{\textsf{max}}}$ and a map $\delta : [\ell ] \rightarrow \textsf{U}_\textsf{att}$.

Parse $\textsf{SK}_{\textsf{GID}, t, \boldsymbol{u}} = (\textsf{GID}, \boldsymbol{u}, \textsf{SK}_{t, \boldsymbol{u}}, \textsf{Z}_t^{(j)}, \mathcal {I}_{\boldsymbol{u}})$, where $i\in [\ell ]$ and $\textsf{CT}= ((\boldsymbol{\textrm{M}}, \delta ), C_0, \{C_{1, i}, C_{2,i,}, C_{3,i,j,k}, C_{4, i, j}, C_{5, i, 1}, C_{5,i,j}\}_{i \in [\ell ],j\in \{2,\ldots , s_{\textsf{max}}\}, k \in [m]}, \mathcal {I}_{\boldsymbol{v}})$. Denote a set $I = \{i | \delta (i)\in S\} \subseteq [\ell ]$. If $(1, 0, \dots , 0)$ is not in the span of $\boldsymbol{\textrm{M}}_I$ (i.e., $\boldsymbol{\textrm{M}}$ restricted to the set of rows from I) or $\mathcal {I}_{\boldsymbol{u}} \ne \mathcal {I}_{\boldsymbol{v}}$ decryption returns $\bot$. Else, when S satisfies $(\boldsymbol{\textrm{M}},\rho )$, the algorithm finds $\{w_i \in \mathbb {Z}_q\}_{i\in I}$ such that $(1, 0, \dots , 0) = \sum _{i \in I} w_i \boldsymbol{\textrm{M}}_i$. It first computes

$$ [\![\mathrm {\Lambda }_i]\!]_T = \displaystyle \prod _{j=2}^{s_{\textsf{max}}} \prod _{k=1}^n u_{\iota _k} \cdot C_{3,i,j, k} \cdot e(C_{4, i, j}, \textsf {H}_3(\textsf{GID}~ \Vert ~\boldsymbol{u} ~ \Vert ~j~ \Vert ~\iota _k)^{u_{\iota _k}}) $$

and outputs $\log _{g_T}([\![\varGamma ]\!]_T)$ where $[\![\varGamma ]\!]_T= {C_0} \cdot {\boldsymbol{u}}\cdot [\![\mu ]\!]_T$ and

$$\begin{aligned}{}[\![\mu ]\!]_T = \displaystyle \left( \prod _{i \in I} \left[ \frac{ {C_{1,i}} \cdot {\boldsymbol{u}} \cdot [\![\mathrm {\Lambda }_i]\!]_T \cdot \displaystyle \prod _{j = 1}^{s_{\textsf{max}}} e(\textsf{Z}_{\delta (i)}^{(j)}, C_{5, i, j})}{ e\left( \textsf{SK}_{\rho (i), \boldsymbol{u}}, C_{2,i} \right) } \right] ^{w_i} \right) ^{-1}. \end{aligned}$$

Theorem 6.1

If the $L\text {-}\textsf{DBDH}$ assumption holds, then all $\textsf{PPT}$ adversaries have a negligible advantage in breaking the static security of the proposed $\textsf{LMA}\text {-}\textsf{ABUIPFE}$ scheme in the random oracle model.