Robust,revocable,forward and backward adaptively secure attribute-based encryption with outsourced decryption 1

Abstract

Attribute based encryption (ABE) is a cryptographic technique allowing fine-grained access control by enabling one-to-many encryption. Existing ABE constructions suffer from at least one of the following limitations. First, single point of failure on security meaning that, once an authority is compromised, an adversary can either easily break the confidentiality of the encrypted data or effortlessly prevent legitimate users from accessing data; second, the lack of user and/or attribute revocation mechanism achieving forward and backward secrecy; third, a heavy computation workload is placed on data user; last but not least, the lack of adaptive security in standard models.

In this paper, we propose the first single-point-of-failure free multi-authority ciphertext-policy ABE that simultaneously (1) ensures robustness for both decryption key issuing and access revocation while achieving both backward and forward secrecy; (2) enables outsourced decryption to reduce the decryption overhead for data users that have limited computational resources; and (3) achieves adaptive (full) security in standard models. The provided theoretical complexity comparison as well as the conducted experiments show that our construction introduces linear storage and computation overheads that occurs only once during its setup phase, which we believe to be a reasonable price to pay to achieve all previous features.

Keywords

Attribute-based encryption threshold cryptography adaptive security

1. Introduction

Cloud computing enables the on-demand provision of various resources, such as computing power and storage over the Internet, freeing companies from maintaining IT infrastructure and managing data centers so they can focus on their core business. In addition, cloud computing enables users to take advantage of a variety of powerful resources on a pay-as-you-go basis. Nevertheless, security and privacy issues have become the main obstacle to the wider adoption of cloud computing. According to Techfunnel’s top five cloud computing predictions for 2020 [40], security tops the list of the biggest cloud challenges. Hence, users/companies are reluctant to outsource their important data to non fully-trusted Cloud server.

In a non fully trusted cloud environment, preserving data confidentiality, making appropriate decisions about data access, and enforcing fine-grained access policies are major challenges. Hence, many cryptography-based system models and techniques have been proposed to enable efficient and secure cloud access control. Among the previous, ABE [35]. The latter allows to ensure simultaneously confidentiality preservation and fine-grained access control. ABE has succeeded in attracting considerable research efforts [2,18,48] which allows to define additional cryptographically functional features, such as access revocation, accountability, and robustness to the basic construction. Unfortunately, all the proposed ABE constructions suffer from at least one of the following limitations. First, the lack of robustness meaning that once the authority responsible of issuing decryption keys to data users is compromised, an adversary can either easily break the confidentiality of the encrypted data or effortlessly prevent legitimate users from accessing data. Second, the lack of access revocation making the concerned approaches inflexible. Third, most of the proposed ABE constructions require heavy computation workload to be performed by data user at access time. Last but not least, the lack of security in standard models. We provide a full comparison with related literature in Section 2.

In [5], we propose a new multi-authority ciphertext-policy ABE (CP-ABE) scheme with some interesting features. First, it ensures robustness for both decryption key issuing and access revocation processes. That is, an adversary needs to compromise several authorities to be able either to break the confidentiality of the outsourced data or to prevent authorized users from accessing outsourced data. Second, our construction enable attribute revocation while achieving forward secrecy. Third, it enables to outsource most part of the decryption process to the cloud server while ensuring that the latter learns nothing about the partially decrypted data. Fourth, our construction achieves adaptive security in standard models. The construction we propose in [5] is – to our knowledge – the first to provide all previously mentioned features. Finally, we conduct theoretical comparison with similar constructions to show that ours introduces linear storage and computation overheads that occur only once during its setup phase.

In this paper, we extend our construction proposed in [5] in three directions. First, we improve the propose construction to ensure backward secrecy. Second, we propose a framework implementing the different capability of our construction. Finally, we provide an extensive experimental analysis to evaluate the efficiency of our construction.

The paper is organized as follows. Section 2 reviews related work and provides a comprehensive comparison with our construction. Sections 3 and 4 present the assumptions and the adversary model we are considering to achieve provable security. Section 5 formalizes our primitive. Then, in Section 6, we provide the security results. In Section 7, we discuss the complexity of our construction. Section 8 details the implementation of our construction. Section 9 presents the obtained experimental results. Finally, Section 10 concludes.

2. Related work

Revocable ABE. Several researchers have been devoted to build ABE constructions allowing access revocation. Liang et al. [24] introduce a provably selectively secure CP-ABE construction that enables access revocation through proxy re-encryption. Using the latter technique, Luo et al. [28] designed a selectively secure and small attribute universe based CP-ABE supporting policy updating. Always relying on proxy re-encryption, Yu et al. [47] propose an AND-gate policy based ABE construction enabling attribute and user revocation. The proposed construction is proved to be selectively secure under the decisional bilinear Diffie–Hellman (DBDH) assumption. To allow the enforcement of non-monotonic access structures, Lewko et al. [19] propose a selectively secure in the standard model ABE construction that enables attribute revocation. Hur and Noh [14] rely on a stateless group key distribution method based on binary trees to define a CP-ABE solution enabling efficient attribute revocation. The authors claimed that the proposed scheme achieves backward secrecy and forward secrecy without providing formal security analysis. Yang et al. [44] propose a CP-ABE construction enabling attribute and user revocation based on a ciphertext re-encryption mechanism performed by a third-party honest-but-curious server. The proposed construction is proved to be selectively secure under the q-type assumption. In [45], Yang et al. propose a multi-authority CP-ABE supporting revocation process. The latter is performed mainly by attribute authorities which are responsible of computing an updated decryption key for each non-revoked user. Relying on binary trees, Cui et al. [7] propose a CP-ABE scheme that enables attribute revocation where most of the related computations are delegated to an untrusted server. Similarly to [14], the authors of [7] claim that their construction is both backward and forward secure without providing any formal proofs. Liu et al. [27] propose a large universe CP-ABE construction enabling both user revocation and accountability. The authors show that the proposed construction is selectively secure in standard models. Li et al. [22] propose a new multi-authority CP-ABE scheme enabling attribute revocation while being adaptively secure in the setting of bilinear groups with composite order. Relying on an untrusted server, Qin et al. [34] design an adaptively secure CP-ABE scheme enabling attribute revocation. In the proposed scheme, the untrusted server is used to help non-revoked users to decrypt ciphertexts. Very recently, Xiong et al. [41] propose an adaptively secure CP-ABE scheme allowing attribute revocation. It uses monotonic span program [17] as an access structure to reduce the number of pairing and exponentiation operations required during data encryption and decryption.

Outsourced decryption-based ABE. To mitigate the burden of decryption for data user, Yang et al. [45] propose a construction that outsource most part of the computations to the cloud server. The same idea was later used in [7,34,41,46]. A common weakness of the previously mentioned ABE constructions is that they all include a single point of failure on security. That is, as soon as an attribute authority is compromised by an adversary, the latter can easily break the confidentiality of the outsourced data by issuing valid secret decryption keys.

Robust ABE. To mitigate the single-point-of-failure weakness, Li et al. [23] propose a multi-authority CP-ABE called TMACS. In contrast to previously mentioned approaches, in TMACS, the set of attribute authorities are collaboratively managing the whole set of attributes and no one of them can have full control over any specific attribute. The construction relies on a $(t, n)$ threshold secret sharing protocol (Section 3.2) to require the collaboration of at least t attribute authorities to issue a valid decryption key, which allows to prove that the proposed construction is selectively secure even when $t - 1$ authorities are compromised. Unfortunately, neither the access revocation, nor the outsourced decryption has been addressed in this work.

Table 1 presents a comprehensive feature comparison of the (most) related CP-ABE schemes. According to it, the construction we propose in this paper is the only one that achieves simultaneously robustness, access revocation, outsourced decryption, and adaptive security.

Table 1
Feature comparaison of (most) related CP-ABE constructions. We use FS and BS to denote respectively the forward and backward secrecy properties

Approaches Robustness Revocation Security model FS BS Outsourced decryption

[9,11–13,25,30,31,35,38] ✗ ✗ Selective ✗ ✗ ✗

[14,19,21,24,28,44,47] ✗ ✓ Selective ✓ ✗ ✗

[7,45,46] ✗ ✓ Selective ✓ ✗ ✓

[23] ✓ ✗ Selective ✗ ✗ ✗

[4,20,37] ✗ ✗ Fully ✗ ✗ ✗

[22,27] ✗ ✓ Fully ✓ ✗ ✗

[34,41] ✗ ✓ Fully ✓ ✗ ✓

[5] ✓ ✓ Fully ✓ ✗ ✓

This work ✓ ✓ Fully ✓ ✓ ✓

Approaches	Robustness	Revocation	Security model	FS	BS	Outsourced decryption
[9,11–13,25,30,31,35,38]	✗	✗	Selective	✗	✗	✗
[14,19,21,24,28,44,47]	✗	✓	Selective	✓	✗	✗
[7,45,46]	✗	✓	Selective	✓	✗	✓
[23]	✓	✗	Selective	✗	✗	✗
[4,20,37]	✗	✗	Fully	✗	✗	✗
[22,27]	✗	✓	Fully	✓	✗	✗
[34,41]	✗	✓	Fully	✓	✗	✓
[5]	✓	✓	Fully	✓	✗	✓
This work	✓	✓	Fully	✓	✓	✓

3. Preliminaries

In this section, we give background information on bilinear maps and the security assumption we are considering. Then, we give a brief description of the trusted third party free secret sharing method proposed by Pedersen in [32].

3.1. Bilinear maps

Let $G_{1}$ , $G_{2}$ , and $G_{T}$ be three multiplicative cyclic groups of prime order p. Let $e : G_{1} \times G_{2} \to G_{T}$ be a bilinear map having the following properties:

Symmetric bilinearity: $\forall g_{1} \in G_{1}$ , $\forall g_{2} \in G_{2}$ and $\forall a, b \in Z_{p}$ , we have $e (g_{1}^{a}, g_{2}^{b}) = e (g_{1}^{b}, g_{2}^{a}) = e {(g_{1}, g_{2})}^{a \cdot b}$ .

Non-degeneracy: $e (g_{1}, g_{2}) \neq 1$ .

The group operations in $G_{1}$ , $G_{2}$ and $e (\cdot, \cdot)$ are efficiently computable.

The security of our construction holds as long as

G_{1} \neq G_{2}

and no efficiently computable homomorphism exists between

G_{1}

and

G_{2}

in either directions. In the sequel, we refer to the tuple

(G_{1}, G_{2}, G_{T}, p, e (\cdot, \cdot))

as a bilinear environment.

We prove the security of the proposed construction under a non-interactive Generalized Diffie–Hellman Exponent assumption (GDHE) which has been proved to be a hard problem in [6]. That is, according to Definitions 1 and 2, as long as the challenge polynomial f that denotes the secret information we want to protect is independent of $⟨ R, S, T ⟩$ , i.e., the information the adversary can get out of the known information, an adversary cannot distinguish $g^{f (x_{1}, \dots, x_{c})}$ (resp. $g_{2}^{f (x_{1}, \dots, x_{c})}$ ) from a random element of $G_{1}$ (resp. $G_{2}$ ).

Definition 1 (Independence [6]).

Let p be some large prime, r, s, t, and c be positive integers. Let $R = ⟨ r_{1}, \dots, r_{r} ⟩ \in F_{p} {[X_{1}, \dots, X_{c}]}^{r}$ , $S = ⟨ s_{1}, \dots, s_{s} ⟩ \in F_{p} {[X_{1}, \dots, X_{c}]}^{s}$ , and $T = ⟨ t_{1}, \dots, t_{t} ⟩ \in F_{p} {[X_{1}, \dots, X_{c}]}^{t}$ be three tuples of multivariate polynomials over the field $F_{p}$ . We say that polynomial $f \in F_{p} [X_{1}, \dots, X_{c}]$ is dependent on the triple $⟨ R, S, T ⟩$ if there exists $r \cdot s + t$ constants ${ϑ_{i, j}^{(a)}}_{i, j = 1}^{i = r, j = s}$ , ${ϑ_{k}^{(b)}}_{k = 1}^{t}$ such that $\begin{matrix} f = \sum_{i, j} ϑ_{i, j}^{(a)} \cdot r_{i} \cdot s_{j} + \sum_{k} ϑ_{k}^{(b)} \cdot t_{k} \end{matrix}$ We say that f is independent of $⟨ R, S, T ⟩$ if f is not dependent on $⟨ R, S, T ⟩$ .

Definition 2 (GDHE assumption [6]).

Let $(G_{1}, G_{2}, G_{T}, p, e (\cdot, \cdot))$ be a bilinear environment and r, s, t, and c be positive integers. Let $R = ⟨ r_{1}, \dots, r_{r} ⟩ \in F_{p} {[X_{1}, \dots, X_{c}]}^{r}$ , $S = ⟨ s_{1}, \dots, s_{s} ⟩ \in F_{p} {[X_{1}, \dots, X_{c}]}^{s}$ , and $T = ⟨ t_{1}, \dots, t_{r} ⟩ \in F_{p} {[X_{1}, \dots, X_{c}]}^{t}$ be three tuples of multivariate polynomials over the field $F_{p}$ . The GDHE assumption states that, given the vector $\begin{matrix} H (x_{1}, \dots, x_{c}) = (g_{1}^{R (x_{1}, \dots, x_{c})}, g_{2}^{S (x_{1}, \dots, x_{c})}, e {(g_{1}, g_{2})}^{T (x_{1}, \dots, x_{c})}) \in G_{1}^{r} \times G_{2}^{s} \times G_{T}^{t} \end{matrix}$ it is hard to decide whether $U = e {(g_{1}, g_{2})}^{f (x_{1}, \dots, x_{c})}$ or U is random if f is independent of $(R, S, T)$ .

3.2. Trusted third party free threshold secret sharing

In a secret sharing scheme, a secret is distributed among several participants organized in an access structure listing all groups that can access the secret. The objective is to provide information specific to each participant so that only a specific group of participants can reconstruct the secret. Several practical secret sharing schemes have been proposed [3,15,32,36]. In this work, we use the trusted third party free threshold secret sharing construction proposed in [32], which we briefly describe as following.

Consider a system involving a set $P = {P_{1}, P_{2}, \dots, P_{n}}$ of n participants and a threshold t ( $t ⩽ n$ ). Let us suppose that to each participant $P_{i} \in P$ is associated a unique scalar $z_{i} \in Z_{p}$ ( $\forall P_{i}, \forall P_{j} \in P : P_{i} \neq P_{j} \Leftrightarrow z_{i} \neq z_{j}$ ) representing the public identifier of the participant in the system. First, each participant $P_{i}$ selects a random scalar $s_{i} \in Z_{p}$ that represents his/her sub-secret and generates a random polynomial $f_{i} (x)$ of degree $t - 1$ such that $f_{i} (0) = s_{i}$ . The sum of sub-secrets $S = \sum_{i = 1}^{n} s_{i}$ represents the master secret that is shared among the participants. Nevertheless, S is not known to any participant. Second, each participant $P_{i}$ computes the sub-shares $s_{i, j} = f_{i} (z_{j})$ , $1 ⩽ j ⩽ n$ , $j \neq i$ and securely sends $s_{i, j}$ to $P_{j}$ . Once a participant $P_{i}$ receives sub-shares from all other $n - 1$ participants, he/she/it computes $s_{i, i} = f_{i} (z_{i})$ and computes it own master share as $S_{i}^{'} = \sum_{j = 1}^{n} s_{j, i}$ . Once each participant $P_{i}$ has computed $S_{i}^{'}$ , the master secret key S can be constructed using the Lagrange interpolating formula by any t out of n participants. Let us denote by $S_{k}^{'}$ , $1 ⩽ k ⩽ t$ the set of master shares to be used, the master secret can be constructed as following: $\begin{array}{r} \sum_{k = 1}^{t} (S_{k}^{'} \cdot \prod_{j = 1, j \neq k}^{t} \frac{- z_{j}}{z_{k} - z_{j}}) = \sum_{k = 1}^{t} (S_{k}^{'} \cdot \prod_{j = 1, j \neq k}^{t} \frac{z_{j}}{z_{j} - z_{k}}) = \sum_{i = 1}^{n} S_{i} = S \end{array}$

4. System and security models

In this section, we introduce the system model we are considering. Then, we define the scheme we are proposing, the considered threat model, and the security requirements we aim to ensure.

Fig. 1.

System model.

4.1. System model

The system we consider to build our scheme is depicted in Fig. 1. It is composed of five entities: A decentralized certificate authority, multiple attribute authorities, data providers, data users, and a cloud server provider.

The decentralized certificate authority (DCA) is a consortium blockchain-based PKI management system e.g., [1,42] which is responsible of setting up of the system by choosing its parameters such as, the set of attributes as well as the bilinear environment to be used. It is also in charge of registering data users and attribute authorities. Finally, DCA is responsible of choosing the robustness level that should be satisfied, i.e., the number of attribute authorities that should be compromised to break the confidentiality of the shared data. We stress that the DCA is not involved in decryption key issuing and access revocation.

Attribute authorities (AAs) are a set of entities that collaboratively control the access to the shared data by cooperatively issuing decryption keys to data users, and revocation key to the cloud server provider.

Cloud storage provider (CSP) is responsible of providing data storage and computation capabilities such as outsourced decryption and ciphertext re-encryption.

The data provider (DP) is the entity that aims to share its data. It encrypts his/her data using a chosen access policy that specifies who can get access to his/her data.

The data user (DU) represents an entity that will access and use the shared data. A DU is labeled by a set of attributes. It is supposed to be able to download any encrypted (shared) data from the CSP. However, only DUs who are labeled with proper attributes can successfully decrypt the retrieved encrypted data.

4.2. Definition of our construction

Our construction consists of eight algorithms: GlobalSetup, CAKeyGen, AAKeyGen, Encrypt, Revoke, DecKeyGen, PartialDecrypt, and Decrypt. The algorithms GlobalSetup and CAKeyGen are performed by DCA. AAKeyGen is performed by AAs. DecKeyGen is performed collaboratively between a DU and AAs. Revoke is collaboratively performed by AAs and CSP. Encrypt is performed by DP. PartialDecrypt algorithm involves DU and CSP. Finally, Decrypt is performed by DU.

$GlobalSetup (λ, t, Σ) \to env$ is a probabilistic algorithm that takes as input the security parameter λ, a robustness level t, and a set of attributes Σ. It outputs the public parameters of the system $env$ . The latter will be implicitly used by all the other algorithms and so will be omitted.

$AAKeygen () \to (SK, PK)$ is a probabilistic algorithm that returns a secret key share $SK$ and a master public key share $PK$ .

$CAKeyGen ({{PK}_{i}}) \to MPK$ is a probabilistic algorithm that takes as input the master public key shares ${{PK}_{i}}$ of the involved AAs and outputs a master public key $MPK$ .

$Encrypt (M, M, MPK) \to χ$ is a probabilistic algorithm that takes a message M and an access structure $M$ and outputs an encrypted data item bundle χ.

$DecKeyGen (MPK, AAs) \to K$ is a probabilistic algorithm that takes as input the master public key $MPK$ and the set of registered attribute authorities $AAs$ and outputs a secret decryption key $K$ .

$Revoke (u, {σ_{i}}) \to (MPK, {SK}_{csp})$ is a probabilistic algorithm that takes as input a data user u and a set of attributes ${σ_{i}}$ and returns an updated master public key $MPK$ and an updated secret key ${SK}_{csp}$ for the CSP.

$PartialDecrypt ({SK}_{csp}, \overline{K}, ind) \to \overline{χ}$ is a deterministic algorithm that takes as input the secret key ${SK}_{csp}$ of the CSP, a randomized decryption key $\overline{K}$ , and the index $ind$ of the data item to decrypt χ and returns a partially decrypted data item $\overline{χ}$ .

$Decrypt (K, \overline{χ}) \to M$ is a deterministic algorithm that takes as input a DU’s secret decryption key $K$ and a partially decrypted data item $\overline{χ}$ and outputs a plaintext data item M.

4.3. Threat model

In our scheme, as the DCA capabilities are supposed to be provided by a blockchain-based PKI management system, then we fairly assume that the DCA is a trusted single point of failure-free entity. Hence, DCA is supposed to issue correct signed certificates to the different registered entities involved in the system.

Attribute authorities involved in the system are considered as honest-but-curious entities. They are honest in the sense that they are supposed to correctly perform the different operations of our construction, but we suppose that some of them can be corrupted by an adversary who aims to learn as much information as possible about the data. Similarly, we assume that the CSP is also honest-but-curious as it will correctly follow the proposed protocol, yet may try to lean information about the shared data.

Data consumers are considered to be malicious entities that can collude with each other and/or with compromised attribute authorities.

Finally, we suppose that the CSP will not collude with data users to infer more information about the shared data. We believe that this last assumption is fairly reasonable since, in a free market environment, an open dishonest behavior will result in considerable damages for the involved entities.

4.4. Security requirements

Four security requirements are considered in our construction. Collusion resistance, robustness, as well as forward and backward secrecy.

4.4.1. Collusion resistance

Since we suppose that multiple malicious data users may collude to gain access to an encrypted data that none of them can access alone, we require our construction to be secure against such collusion attack as formalized by the following definition.

Definition 3 (Collusion Resistance).

Let λ be the security parameter, $A$ be the adversary, $C$ be the challenger. We consider the following game that we denote ${Exp}_{A}^{C}$ .

Setup: $C$ executes the algorithms GlobalSetup, AAKeyGen, and CAKeyGen. It then shares the public parameters $env$ and the master public key $MPK$ with $A$ .

Query – Phase 1: $A$ can make a set of n adaptive secret decryption key queries by executing DecKeyGen. For each query $Q_{i}$ , $A$ is allowed to choose the set of attributes $Σ_{i}$ that should be involved in the decryption key. For each query $Q_{i}$ , $C$ executes DecKeyGen to generate a valid secret decryption key $K_{i}$ and sends it back to $A$ .

Challenge: $A$ chooses two equal-length messages $M_{0}$ , $M_{1}$ , and a challenge access structure $M^{*}$ such that $\forall i \in [1, n]$ , $Σ_{i}$ does not satisfy $M^{*}$ . Then it sends them to $C$ . The latter chooses a random $β \in {0, 1}$ , encrypts $M_{β}$ under $M^{*}$ to get the challenge ciphertext $C^{*}$ , and sends $C^{*}$ to $A$ .

Query – Phase 2: $A$ can make adaptive secret decryption key queries as in phase 1. At this level, the only restriction is that the set of attributes $Σ_{i}$ involved in each query does not satisfies the challenge access structure $M^{*}$ , otherwise, $A$ will trivially win the game by running the Decrypt algorithm.

Guess: $A$ outputs its guess $β^{'}$ of β.

We define

A

’s advantage by

{Adv}^{{Exp}_{A}^{C}} (λ) = | Pr [β = β^{'}] - 1 / 2 |

. Our construction is said to be collusion resistant if

{Adv}^{{Exp}_{A}^{C}} (λ)

is negligible.

4.4.2. Robustness

According to the threat model we are considering (Section 4.3), we suppose that a subset of attribute authorities can be compromised by an adversary. Hence, we require our construction to be robust. That is, any encrypted data item remains fully protected against unauthorized entities as far as no more than $t - 1$ attribute authorities are compromised. We formalize the robustness requirement using the following definition.

Definition 4 ( $(t, n)$ -Robustness).

Let λ be the security parameter, $A$ be the adversary, and $C$ be the challenger. We consider the following game that we denote ${Exp}_{A}^{R}$ . We omit the first four steps of the game since they are the same as defined in ${Exp}_{A}^{C}$ (Definition 3).

Compromise: In this step, $A$ adaptively chooses $t - 1 < n$ attribute authorities and compromises them to get their master secret key shares ${sk}_{i}$ , $i \in [1, t - 1]$ .

Guess: $A$ outputs its guess $β^{'}$ of β.

We define

A

’s advantage by

{Adv}^{{Exp}_{A}^{R}} (λ) = | Pr [β = β^{'}] - 1 / 2 |

. Our construction is said to be

(t, n)

-Robust if

{Adv}^{{Exp}_{A}^{R}} (λ)

is negligible.

4.4.3. Forward secrecy

Forward secrecy is a mandatory property for enabling secure revocation. In the context of attribute based encryption, forward secrecy requires that it should not be feasible for a data user to decrypt previous and subsequent ciphertexts, if a subset of his/her attributes required for decryption are revoked. This requirement is formalized using the following definition.

Algorithm 1:

Outsourced pre-decryption. $M_{u}$ is used to denote the sub-matrix of $M$ , where each row of $M_{u}$ corresponds to an attribute in $Σ_{u}$ , $I$ is a subset of ${1, 2, \dots, l}$ , and $M_{i}$ is used to denote the ith row of the matrix $M$ . Finally, let ${w_{i}}_{i \in I}$ be constants such that $\sum_{i \in I} w_{i} \cdot M_{i} = (1, 0, \dots, 0)$

Definition 5 (Forward Secrecy).

Let λ be the security parameter, $A$ be the adversary, and $C$ be the challenger. We consider the following game that we denote ${Exp}_{A}^{B - F}$ . The first step of this game is the same as defined in ${Exp}_{A}^{C}$ (Definition 3) and so will be omitted.

Query – Pre revocation: this phase is carried out according to the following two steps.

$A$ performs a secret decryption key query by executing DecKeyGen. For this query, $A$ is allowed to choose the set of attributes $Σ^{*}$ that should be involved in the secret decryption key. Once the query is received by $C$ , it executes DecKeyGen to generate a valid secret decryption key $K$ and sends it back to $A$ .

$A$ chooses two equal-length messages $M_{0}$ and $M_{1}$ , and an access structure $M_{1}^{*}$ such that $Σ^{*}$ satisfies $M_{1}^{*}$ , i.e., $A$ can use the secret decryption key $K$ requested in the step (2)(a) to decrypt the two data items $M_{0}$ and $M_{1}$ . $A$ sends $M_{0}$ , $M_{1}$ , and $M_{1}^{*}$ to $C$ who encrypts $M_{0}$ and $M_{1}$ to get the two ciphertexts $C_{0}$ and $C_{1}$ .

Revocation: $C$ revokes a subset $Σ^{'} \subseteq Σ^{*}$ of attributes from $A$ such that $Σ^{*} ∖ Σ^{'}$ no longer satisfies $M_{1}^{*}$ .

Query – Post revocation: $A$ chooses two equal-length messages $M_{0}^{'}$ and $M_{1}^{'}$ , and an access structure $M_{2}^{*}$ such that $Σ^{*} ∖ Σ^{'}$ does not satisfy $M_{2}^{*}$ . $A$ sends $M_{0}^{'}$ , $M_{1}^{'}$ , and $M_{2}^{*}$ to $C$ who encrypts $M_{0}^{'}$ and $M_{1}^{'}$ to get the two ciphertexts $C_{0}^{'}$ and $C_{1}^{'}$ .

Challenge: $C$ chooses randomly $β_{1}, β_{2} \in {0, 1}$ , re-encrypts $C_{β}$ and $C_{β}^{'}$ as described in Algorithm 1 (lines 9 to 18) and sends them to $A$ .

Guess: $A$ outputs its guesses $β_{1}^{'}$ and $β_{2}^{'}$ of $β_{1}$ and $β_{2}$ respectively.

We define

{Adv}^{{Exp}_{A, β_{1}}^{B - F}} (λ) = | Pr [β_{1} = β_{1}^{'}] - 1 / 2 |

and

{Adv}^{{Exp}_{A, β_{2}}^{B - F}} (λ) = | Pr [β_{2} = β_{2}^{'}] - 1 / 2 |

. Our construction is said to be forward secure if

{Adv}^{{Exp}_{A, β_{1}}^{B - F}} (λ)

and

{Adv}^{{Exp}_{A, β_{2}}^{B - F}} (λ)

are negligible.

Remark.
We want to emphasize that in the previous security game, the adversary $A$ is not given access to the ciphertext before the challenge step. If the adversary had such access, they could easily win the game by storing the symmetric keys used to encrypt the ciphertexts and using them during the Challenge phase. This assumption is quite reasonable because it doesn’t make sense to protect data items for entities that already know them. It has been also considered in most of the revocable ABE (e.g. [10,33,43]).
4.4.4. Backward secrecy

Backward secrecy property means that a new added data user should be unable to decrypt data items that are created prior to his/her/its introduction to the system. This property is formalized using the following definition.

Definition 6 (Backward Secrecy).

Let λ be the security parameter, $A$ be the adversary, and $C$ be the challenger. We consider the following game that we denote ${Exp}_{A}^{B}$ . The first three steps of this game is the same as defined in ${Exp}_{A}^{C}$ (Definition 3) and so will be omitted.

Time slot incrementation – Once the query phase is finished, the challenger $C$ increment the time slot in the public key by performing an access revocation.

Query – Phase 2: $A$ makes a secret decryption key query to request a decryption key involving the set of adaptively chosen attributes $Σ^{*}$ such that the latter satisfies $M^{*}$ .

Guess: $A$ outputs its guess $β^{'}$ of β.

We define

A

’s advantage by

{Adv}^{{Exp}_{A}^{B}} (λ) = | Pr [β = β^{'}] - 1 / 2 |

. Our construction is said to be backward secure if

{Adv}^{{Exp}_{A}^{B}} (λ)

is negligible.

5. Our proposed scheme

We now present the detailed construction. We emphasis that, since the DCA capabilities are provided by a consortium blockchain-based PKI management system, we use the same blockchain as a trusted shared storage to store the different public elements exchanged between the different parties that compose our system. Hence, the consortium blockchain is supposed to be accessible to all the entities involved in the system. In the sequel, we refer to the consortium blockchain as $B$ .

5.1. System initialization

The initialization of the system is performed as described in the following.

5.1.1. GlobalSetup

Let $(G_{1}, G_{2}, G_{T}, p, e (\cdot, \cdot))$ be a bilinear environment, $g_{1}$ and $g_{2}$ be two random elements of $G_{1}$ and $G_{2}$ respectively. Let $H : G_{T} \to {0, 1}^{m}$ be a cryptographic hash function for some m ( $⩾ 256$ ) and Ξ be an unforgeable under adaptive chosen message attacks signature system. The DCA generates a signature key $SMK$ and a verification key $VMK$ and sends the pubic parameters $env = (G_{1}, G_{2}, G_{T}, p, e (\cdot, \cdot), g_{1}, g_{2}, H, Ξ, VMK)$ to $B$ for storage.

5.1.2. System initialization

The system is initialized using the following steps.

AA registration: Each attribute authority ${AA}_{i}$ uses Ξ to generate a private key ${SK}_{{AA}_{i}}$ and a public key ${PK}_{{AA}_{i}}$ and sends a registration request to DCA. If ${AA}_{i}$ is a legal authority, the DCA generates a random global identity $aid \in Z_{p}$ , issues a signed certificate $C {ert}_{aid}$ , and submits the couple $(aid, C {ert}_{aid})$ for storage in $B$ .

CSP registration: This step is triggered when CSP sends a registration query to DCA. Then, the latter assigns a random identifier $cspid \in Z_{p}$ , issues a certificates ${Cert}_{cspid}$ , and submits the couple ( $cspid$ , ${Cert}_{cspid}$ ) for storage in $B$ . Finally, the CSP initializes its secret key as ${SK}_{csp} = \emptyset$ . The latter will be used to enforce access revocation by updating encrypted data items.

Robustness level selection: Let us suppose that n attribute authorities $AA = {A_{1}, \dots, A_{n}}$ are registered in the system. Using this process, DCA chooses the robustness level t ( $t < n$ ) that should be satisfied and sends the master public key $MPK = (env, n, t)$ for storage in $B$ .

AA key generation: This process is performed by each one of the n attribute authorities. It requires the cooperation of the attribute authorities with each other to call the trusted third party free threshold secret sharing (Section 3.2). Each $A_{i}$ performs the following steps:

Select four random scalars $a_{i}, α_{i}, {\overline{α}}_{i}, δ_{i} \in Z_{p}$ as a sub-secrets and generate four random polynomials $f_{i} (x)$ , $h_{i} (x)$ , ${\overline{f}}_{i} (x)$ , and ${\overline{h}}_{i} (x)$ of degree $t - 1$ such that $f_{i} (0) = a_{i}$ , $h_{i} (0) = α_{i}$ , ${\overline{f}}_{i} (0) = δ_{i}$ , and ${\overline{h}}_{i} (0) = {\overline{α}}_{i}$ . Then for all $j \in {1, 2, \dots, n} ∖ {i}$ , calculate $s_{i, j}^{{a}} = f_{i} ({aid}_{j})$ , $s_{i, j}^{{α}} = h_{i} ({aid}_{j})$ , $s_{i, j}^{{δ}} = {\overline{f}}_{i} ({aid}_{j})$ , and $s_{i, j}^{{\overline{α}}} = {\overline{h}}_{i} ({aid}_{j})$ , and send $s_{i, j}^{{a}}$ , $s_{i, j}^{{α}}$ , $s_{i, j}^{{δ}}$ , and $s_{i, j}^{{\overline{α}}}$ securely to $A_{j}$ .

After receiving $s_{j, i}^{{a}}$ , $s_{j, i}^{{α}}$ , $s_{j, i}^{{δ}}$ , and $s_{j, i}^{{\overline{α}}}$ from all other $n - 1$ AAs, each $A_{i}$ calculates $\begin{array}{r} {sk}_{i}^{{k}} = \sum_{j = 1}^{n} s_{j, i}^{{k}}, k \in {a, α, δ, \overline{α}} \end{array}$ ${pka}_{i} = g_{1}^{{sk}_{i}^{{a}}}$ , $\overline{{pka}_{i}} = g_{2}^{{sk}_{i}^{{a}}}$ , ${pke}_{i} = e {(g_{1}, g_{2})}^{{sk}_{i}^{{α}}}$ , ${pkr}_{i} = g_{2}^{{sk}_{i}^{{\overline{α}}}}$ , and ${pkt}_{i, 0} = g_{2}^{{sk}_{i}^{{δ}}}$ . Finally, each $A_{i}$ sends its master public key share ${PK}_{i} = {{pka}_{i}, \overline{{pka}_{i}}, {pke}_{i}, {pkr}_{i}, {pkt}_{i, 0}}$ to $B$ for storage. The secret key share is set as ${SK}_{i} = {{sk}_{i}^{{k}}}_{k \in {a, α, δ, \overline{α}}}$ .

For each attribute $σ \in Σ$ , and for each time slot π, choose a random scalar $θ_{σ, i, π} \in Z_{p}$ , compute $Θ_{σ, i, π} = g_{1}^{θ_{σ, i, π}}$ and ${\overline{Θ}}_{σ, i, π} = g_{2}^{θ_{σ, i, π}}$ and send them to the $B$ for storage.

For each attribute $σ \in Σ$ , store an initially empty list of users $U_{r, σ}$ denoting the users and the time slot during which the attribute σ is revoked from the user.

Master public key generation: This step is performed by DCA which randomly selects t out of the n AAs master public key shares ${{PK}_{1}, \dots, {PK}_{n}}$ . Let us denote by $I$ the set of indices of the t chosen master public key shares. The global public key of the system is then computed as follows. $\begin{array}{c} pka = \prod_{i \in I} {({pka}_{i})}^{\prod_{j \in I, j \neq i} \frac{{aid}_{i}}{{aid}_{j} - {aid}_{i}}} = g_{1}^{a} \\ \overline{pka} = \prod_{i \in I} {({\overline{pka}}_{i})}^{\prod_{j \in I, j \neq i} \frac{{aid}_{i}}{{aid}_{j} - {aid}_{i}}} = g_{2}^{a} \\ pke = \prod_{i \in I} {({pke}_{i})}^{\prod_{j \in I, j \neq i} \frac{{aid}_{i}}{{aid}_{j} - {aid}_{i}}} = e {(g_{1}, g_{2})}^{α} \\ pkr = \prod_{i \in I} {({pkr}_{i})}^{\prod_{j \in I, j \neq i} \frac{{aid}_{i}}{{aid}_{j} - {aid}_{i}}} = g_{2}^{\overline{α}} \\ {pkt}_{0} = \prod_{i \in I} {({pkt}_{i, 0})}^{\prod_{j \in I, j \neq i} \frac{{aid}_{i}}{{aid}_{j} - {aid}_{i}}} = g_{2}^{δ} \end{array}$ with $a = \sum_{i = 1}^{n} a_{i}$ , $α = \sum_{i = 1}^{n} α_{i}$ , $σ = \sum_{i = 1}^{n} σ_{i}$ ,and $\overline{α} = \sum_{i = 1}^{n} \overline{α_{i}}$ . Then, DCA computes $Θ_{σ, π}$ and ${\overline{Θ}}_{σ, π}$ , $\forall σ \in Σ$ as follows: $\begin{matrix} Θ_{σ, π} = \prod_{i = 1}^{n} Θ_{σ, i, π}, {\overline{Θ}}_{σ, π} = \prod_{i = 1}^{n} {\overline{Θ}}_{σ, i, π} \end{matrix}$ Finally, DCA sends the master public key $MPK = {env, pka, \overline{pka}, pke, pkr, {pkt}_{0}, Θ_{σ, π_{p}}, {\overline{Θ}}_{σ, π_{p}}, π_{p} = 0}_{σ \in Σ}$ to $B$ for storage. We note that the scalar $π_{p}$ represents the time slot on which the public key is created/updated.

It is worth motioning that $pke$ , $\overline{pka}$ , and ${\overline{Θ}}_{σ, π}$ are to be used by DP for data encryption (Section 5.2), $pka$ and $Θ_{σ, π}$ are to be used by AAs for decryption key generation (Section 5.3), $pkr$ is used by AAs for access revocation, and ${pkt}_{i}$ is used by CSP to ensure the backward secrecy property. We emphasis here that the master secret key $MSK = {a, α, \overline{α}, δ}$ is implicitly shared among the different AAs. However, it does not need to be obtained by any entity in the system.

5.2. Data sharing

The data encryption operation Encrypt is performed by the data provider independently. Before outsourcing the data item to CSP, similarly to most ABE schemes, the data to be shared M is firstly encrypted using a secure symmetric key algorithm (e.g., AES). The used symmetric key is generated and encrypted as we described in the following steps.

The data provider starts by defining a monotone boolean formula involving a subset of attributes $Σ^{*} \subseteq Σ$ as the access policy that should be enforced on the data to be outsourced/shared. Then he/she executes the Encrypt algorithm which picks a random scalar $s \in Z_{p}$ and uses the component $pke$ of the master public key $MPK$ to generate the symmetric key κ as: $\begin{matrix} κ = H ({pke}^{s}) = H (e {(g_{1}, g_{2})}^{α \cdot s}) \end{matrix}$ The symmetric key κ is then used to encrypt the data item to be shared M to get a ciphertext that we denote $E_{κ} (M)$ .

The data provider chooses the access policy to be enforced and transforms it into a Linear Secret Sharing Scheme (LSSS) access structure $(M, ρ)$ as described in [26] where $M$ is an $l \times k$ LSSS matrix and $ρ (x)$ maps each row of $M$ to an attribute $σ \in Σ$ . Next, to make sure that only the keys that satisfy $(M, ρ)$ will be able to compute κ, we hide the random element s used to generate κ by choosing a random vector $\vec{v} = {s, v_{2}, \dots, v_{k}} \in Z_{p}^{k}$ . For each row vector $M_{i}$ of $M$ , $λ_{i} = M_{i} \cdot {\vec{v}}^{⊤}$ is calculated and a random scalar $r_{i} \in Z_{p}$ is chosen. The ciphertext encrypting the symmetric encryption key κ is computed as following: $\begin{aligned} C & = {C^{'} = g_{2}^{s}, C_{i} = {\overline{pka}}^{λ_{i}} \cdot {\overline{Θ}}_{ρ (i), π_{c}}^{- r_{i}}, D_{i} = g_{2}^{r_{i}}}_{i \in [1, l]} \end{aligned}$ Finally, the data owner sends the encrypted data item bundle $χ = (E_{κ} (M), C, π_{c} = π_{p})$ to CSP. Similarly, $π_{c}$ is used to denote the timestep on which the data item has been encrypted. At encryption, the timestep $π_{c}$ is the same as the timestep associated to the master public key $MPK$ .

5.3. User registration and key generation

When a user $u_{i}$ joins the system, he/she sends a registration query to the DCA to get a unique $uid$ and a signed certificate ${Cert}_{uid}$ . Let us denote by $Σ_{u_{i}}$ the set of attributes that has to be assigned to $u_{i}$ according to the role he/she plays in the system. Thus, to generate a secret decryption key, $u_{i}$ performs the following two steps.

First, $u_{i}$ selects t out of the n registered attribute authorities according to his/her own preferences. Then, $u_{i}$ separately queries each of the selected t attribute authorities to request a secret decryption key share. We emphasis here that a data user will be able to generate a valid secret decryption key if and only if he/she gets t secret decryption key shares from t different attribute authorities. To request a secret decryption key share from an attribute authority $A_{j}$ , $u_{i}$ sends a secret decryption issuance query containing the identifier $uid$ of $u_{i}$ signed using ${Cert}_{uid}$ to $A_{j}$ . Once the query is received by $A_{j}$ , the latter starts by checking the signature of DCA on ${Cert}_{uid}$ then authenticates the request content by verifying the signature of $u_{i}$ on the request. If $u_{i}$ is authorized to access the shared data, then $A_{j}$ assigns the set of attributes $\begin{matrix} Σ_{u_{i}}^{(j)} = Σ_{u_{i}} ∖ {σ | u_{i} \in U_{r, σ}} \end{matrix}$ to $u_{i}$ where ${σ | u_{i} \in U_{r, σ}}$ is the set of attributes that has been revoked from $u_{i}$ . Then, $A_{j}$ chooses a random scalar $b_{j} \in Z_{p}$ and uses the $MPK$ to generate a secret decryption key share for $u_{i}$ as following: $\begin{matrix} K_{u_{i}, j} = {K_{j} = g_{1}^{{sk}_{j}^{{α}}} \cdot {pka}^{b_{j}}, L_{j} = g_{1}^{b_{j}}, K_{σ, j} = Θ_{σ, π_{c}}^{b_{j}}, K_{π, j} = g_{1}^{b_{j} \cdot {sk}_{j}^{{δ}}}}_{σ \in Σ_{u_{i}}^{(j)}} \end{matrix}$ We note here that the queried attribute authorities may assign different attributes $Σ_{u_{i}}^{(j)}$ to $u_{i}$ . If it is the case, the computed decryption key will involve only the set of attributes $Σ_{u_{i}} = ⋂_{j = 0}^{t} Σ_{u_{i}}^{(j)}$ that are assigned by all t attribute authorities.

Once $u_{i}$ gains t secret decryption key shares from t different attribute authorities, he/she computes his/her secret decryption key as following. $\begin{array}{c} K = \prod_{i = 1}^{t} K_{i}^{\prod_{j = 1, j \neq i}^{t} \frac{{aid}_{j}}{{aid}_{j} - {aid}_{i}}} = g_{1}^{α} \cdot g_{1}^{a \cdot \sum_{i = 1}^{t} (b_{i} \cdot \prod_{j = 1, j \neq i} \frac{{aid}_{j}}{{aid}_{j} - {aid}_{i}})} \\ L = \prod_{i = 1}^{t} L_{i}^{\prod_{j = 1, j \neq i}^{t} \frac{{aid}_{j}}{{aid}_{j} - {aid}_{i}}} = g_{1}^{\sum_{i = 1}^{t} (b_{i} \cdot \prod_{j = 1, j \neq i} \frac{{aid}_{j}}{{aid}_{j} - {aid}_{i}})} \\ K_{σ} = \prod_{i = 1}^{t} K_{σ, i}^{\prod_{j = 1, j \neq i}^{t} \frac{{aid}_{j}}{{aid}_{j} - {aid}_{i}}} = Θ_{σ, π_{c}}^{\sum_{i = 1}^{t} (b_{i} \cdot \prod_{j = 1, j \neq i} \frac{{aid}_{j}}{{aid}_{j} - {aid}_{i}})}, σ \in Σ_{u_{i}} \\ K_{π} = \prod_{i = 1}^{t} K_{π, j} = g_{1}^{δ \cdot \sum_{i = 1}^{t} (b_{i} \cdot \prod_{j = 1, j \neq i} \frac{{aid}_{j}}{{aid}_{j} - {aid}_{i}})} \end{array}$ For sake of simplicity, let us introduce the parameter d: $\begin{matrix} d = \sum_{i = 1}^{t} (b_{i} \cdot \prod_{j = 1, j \neq i} \frac{{aid}_{j}}{{aid}_{j} - {aid}_{i}}) \end{matrix}$ Therefore, the user’s secret key can be simplified as following: $\begin{matrix} K_{u} = {K = g_{1}^{α} \cdot g_{1}^{a \cdot d}, L = g_{1}^{d}, K_{σ} = Θ_{σ, π_{c}}^{d}, K_{π} = g_{1}^{δ \cdot d}, π_{u} = π_{p}, π_{r} = π_{p}}_{σ \in Σ_{u_{i}}} \end{matrix}$ where $π_{u}$ is used to denote the timestep on which $K_{u}$ is issued, and $π_{r}$ is used for decryption key updates.

5.4. Access revocation

Our construction aims to achieve robust fine-grained and on-demand access revocation. That is, to prevent a compromised AA from prohibiting authorized users from accessing the outsourced data by revoking them, our construction requires the collaboration of t out of the n ( $t > n / 2$ ) registered attribute authorities to perform an access revocation. The revocation process is performed according to the following three steps.

5.4.1. Collaborative revocation request

The access revocation process is triggered by an attribute authority $A_{i}$ that wants to revoke the access granted by specific set of attributes $Σ_{r} \in Σ$ to a specific set of data users $U_{r}$ . $A_{i}$ generates a random scalar $t \in Z_{p}$ and computes $\begin{matrix} R_{i} = {R_{i} = g_{2}^{t \cdot {sk}_{i}^{{\overline{α}}}}, R_{v} = {pkr}^{t}, R_{b} = g_{2}^{t}, Σ_{r}, U_{r}} \end{matrix}$ Then, $A_{i}$ signs $R_{i}$ using ${Cert}_{{aid}_{i}}$ , sends it to $B$ for storage, and broadcasts the revocation request to other registered attribute authorities. Once the revocation request is received by the attribute authorities, each $A_{j}$ , $j \in [1, n] ∖ {i}$ authenticates then processes the access revocation request. If it is legitimate, it computes the revocation request share as following $\begin{matrix} R_{j} = {R_{j} = R_{b}^{{sk}_{j}^{{\overline{α}}}}, R_{v} = {pkr}^{t}, Σ_{r}, U_{r}} \end{matrix}$ then, signs $R_{j}$ and sends it to $B$ for storage.

Afterwards, each of the attribute authorities that participates to the previous collaborative revocation request will update locally the list of revoked user for each attribute as following: $\begin{matrix} \forall σ \in Σ_{r} : U_{r, σ} = U_{r, σ} \cup U_{r} \end{matrix}$ Finally, the AAs collaboratively generate a new ${pkt}_{π}$ ( $π = π_{p} + 1$ ) using the protocol defined in the AA key generation (Section 5.1).

5.4.2. Revocation enforcement

Once more than $t - 1$ shares for a revocation request are committed to $B$ , the CSP computes $\begin{matrix} (1) & \prod_{i = 1}^{t} {R_{i}}^{\prod_{j = 1, j \neq i}^{t} \frac{{aid}_{j}}{{aid}_{j} - {aid}_{i}}} \end{matrix}$ and checks if the latter is equal to $R_{v}$ . Thanks to the usage of the trusted third party free threshold secret sharing, the collaboration of t attribute authorities are required to compute the shared secret scalar $\overline{α}$ . Hence, if Equation (1) is equal to $R_{v}$ , the CSP will be sure that the access revocation is requested by at least t out of the n registered attribute authorities.

Then, CSP generates a random scalar $z \in Z_{p}$ and updates the master public key $MPK$ as $\begin{matrix} \forall σ \in Σ_{r} : Θ_{σ, π_{c} + 1} \leftarrow Θ_{σ, π_{c}}^{z}, {\overline{Θ}}_{σ, π_{c} + 1} \leftarrow {\overline{Θ}}_{σ, π_{c}}^{z}, and π_{p} \leftarrow π_{p} + 1 \end{matrix}$ and updates its secret key ${SK}_{csp}$ as $\begin{matrix} {SK}_{csp} \leftarrow {SK}_{csp} \cup {μ_{π_{p}} = z} \end{matrix}$ Finally, CSP sends the updated MPK for updation in $B$ .

5.4.3. Secret decryption key updating

Once an access revocation request is performed, each data user needs to request a fresh secret decryption key as described in Section 5.3.

5.5. Outsourced pre-decryption and user decryption

Our construction enables a data user to outsource most part of the decryption computation to CSP. The main objective of this feature is to allow a data user to shift expensive computations, i.e., pairing operations to CSP without disclosing any information about the encrypted data to CSP. Outsourced pre-decryption is performed according to the following steps.

5.5.1. Secret decryption key randomization

The data user u starts by randomizing its secret decryption key as follows. It picks a random scalar $x \in Z_{p}$ and computes: $\begin{matrix} {\overline{K}}_{u} = {K^{'} = K^{x}, L^{'} = L^{x}, K_{σ}^{'} = K_{σ}^{x}, K_{π}^{'} = K_{π}^{x}, π_{u}, π_{r}} \end{matrix}$ Then, u sends ${\overline{K}}_{u}$ and the index $ind$ of the data item to be pre-decrypted to CSP.

5.5.2. Outsourced pre-decryption

After receiving ( ${\overline{K}}_{u}$ , $ind$ ), CSP starts by checking the correctness of the timestep $π_{u}$ by verifying the following equality: $\begin{matrix} (2) & e (L^{'}, {pkt}_{π_{u}}) = e (K_{π}^{'}, g_{2}) \end{matrix}$ If the latter holds, then the CSP can be sure that the decryption key was issued during the timestep $π_{u}$ . Otherwise, the CSP outputs ⊥. Then CSP performs the PartialDecrypt algorithm which we detail in Algorithm 1. To be useful for pre-decrypting the data item, the randomized secret decryption key $\overline{K_{u}}$ should include a set of attributes $Σ_{u}$ that satisfies the access structure $(M, ρ)$ used to encrypt the requested data item. As detailed in Algorithm 1, the PartialDecrypt algorithm takes as input the secret key ${SK}_{csp}$ of the CSP, a randomized secret decryption key $\overline{K_{u}}$ , the master public key $MPK$ , and the index $ind$ of the data item to encrypt. It outputs a pre-decrypted symmetric key $\overline{κ}$ and the data item ciphertext $E_{κ} (M)$ .

It is important to note that backward secrecy is maintained by the CSP (Cloud Service Provider), which updates the shared ciphertext only between the timestep when the secret decryption key is generated and the current system timestep. Therefore, if the ciphertext is shared during a timestep before the secret decryption key is generated for the user, the updated ciphertext cannot be decrypted correctly by the user.

5.5.3. User decryption

Once the user retrieves the pre-decrypted symmetric key $\overline{κ}$ and the ciphertext $E_{κ} (M)$ , he/she recovers the symmetric key κ by performing the following operations: $\begin{matrix} κ = H ({\overline{κ}}^{1 / x}) \end{matrix}$ which can be used to decrypt the data item.

6. Security results

This section presents the security results of our construction. First, in Theorem 1, we show that our construction provides a correct revocable fine-grained access control capabilities. Then, we prove the collusion resistance, the robustness, the forward and backward secrecy properties in Theorems 2, 3, 4, and 5 respectively.

Theorem 1 (Correctness).

Given a data user u to whom a set of attributes $Σ_{u}$ is assigned and a ciphertext $C$ encrypted using an access structure $M$ . Let us denote by $Σ_{r} \subset Σ_{u}$ the revoked attributes for u. As long as $Σ_{u} ∖ Σ_{r}$ satisfies $M$ and the secret decryption key of u is issued before the encryption of $C$ , i.e., $π_{u} ⩽ π_{c}$ , then the secret decryption key issued to u allows recovering the plaintext of $C$ .

Proof.
The proof is by contradiction. Suppose, contrary to the statement of the theorem, that there exists a timestep π of the system on which the user u cannot recover the plaintext of $C$ despite that $Σ_{u} ∖ Σ_{r}$ satisfies $M$ and that the $C$ is shared after the issuing of the secret decryption key of u, i.e., $π_{u} ⩽ π_{c}$ .

As described in Section 5.1, CSP’s secret key is initially empty ( ${SK}_{csp} = \emptyset$ ) and the master public key $MPK = {env, pka, \overline{pka}, pke, pkr, Θ_{σ}, {\overline{Θ}}_{σ}, π_{p} = 0}_{σ \in Σ}$ . Let us denote by $Θ_{σ, π}$ (resp. ${\overline{Θ}}_{σ, π}$ ) the value of $Θ_{σ}$ (resp. ${\overline{Θ}}_{σ}$ ) at timestep π of the system.

Let us now suppose that m access revocations are performed in the system, each revokes the set of attributes $Σ_{r, i} \in Σ_{u}$ from u, $i \in [1, m]$ . According to the access revocation process of our construction (Section 5.4), each access revocation enforced at the timestep π of the system adds a random scalar $μ_{π + 1} \in Z p$ to ${SK}_{csp}$ and updates the $MPK$ as $Θ_{σ} \leftarrow Θ_{σ}^{μ_{π + 1}}$ and ${\overline{Θ}}_{σ} \leftarrow {\overline{Θ}}_{σ}^{μ_{π + 1}}$ .

Let us denote by $I_{σ} = {i | σ \in Σ_{r, i}}$ the set of indices of access revocations in which the attribute σ is involved. At the timestep π, i.e., after performing π access revocations, we have ${SK}_{csp} = {μ_{i}}_{i = 1}^{π}$ , and $\forall σ \in Σ$ : $Θ_{σ, π} = Θ_{σ, 0}^{\prod_{i \in I_{σ}} μ_{i}}$ and ${\overline{Θ}}_{σ, π} = {\overline{Θ}}_{σ, 0}^{\prod_{i \in I_{σ}} μ_{i}}$ .

According to Section 5.3, at any timestep $π^{} \in [0, m]$ , an updated secret decryption key, i.e., a secret decryption key issued at $π^{}$ will have the form $\begin{matrix} K_{u} = {K = g_{1}^{α} \cdot g_{1}^{a \cdot d}, L = g_{1}^{d}, K_{σ} = Θ_{σ, 0}^{d \cdot \prod_{i \in I_{σ}} μ_{i}}, π_{r} = π^{*}}_{σ \in Σ_{u_{i}}} \end{matrix}$ Now, according to Algorithm 1 (lines 7 to 16), an updated encrypted data item is a data item where $π_{c} = π_{p}$ and $\begin{aligned} C & = {C^{'} = g_{2}^{s}, C_{i} = {\overline{pka}}^{λ_{i}} \cdot {\overline{Θ}}_{ρ (i), π_{c}}^{- r_{i} \cdot \prod_{i \in I_{ρ (i)}, i > max (π_{u}, π_{c})} μ_{i}}, D_{i} = g_{2}^{r_{i}}}_{i \in [1, l]} \end{aligned}$ Now, according to the outsourced pre-decryption process of our construction, the randomized secret decryption key is $\begin{matrix} {\overline{K}}_{u} = {K^{'} = K^{x}, L^{'} = L^{x}, K_{σ}^{'} = K_{σ}^{x}, π_{u}} \end{matrix}$ As we suppose that $Σ_{u} ∖ Σ_{r}$ satisfies the access structure $M$ used to encrypt $C$ , then, we have $\begin{matrix} \exists I \subseteq {i | ρ (i) \in Σ_{u} ∖ Σ_{r}}, \exists w_{i} : \sum_{i \in I} w_{i} \cdot M_{i} = (1, 0, \dots, 0) \end{matrix}$ where $M_{i}$ denotes the ith row of the matrix $M$ . Then, according to Algorithm 1 (line 17), we have $\begin{aligned} \overline{κ} & = \frac{e (K^{'}, C^{'})}{\prod_{i \in I} {(e (L^{'}, C_{i}) \cdot e (K_{i}^{'}, D_{i}))}^{w_{i}})} \\ = \frac{e (g_{1}^{α \cdot x} \cdot g_{1}^{a \cdot d \cdot x}, g_{2}^{s})}{\prod_{i \in I} {(e (g_{1}^{d \cdot x}, g_{2}^{a \cdot λ_{i}} \cdot {\overline{Θ}}_{ρ (i), π_{c}}^{- r_{i} \cdot \prod_{j \in I_{ρ (j)}, j > max (π_{u}, π_{c})} μ_{i}}) \cdot e (Θ_{ρ (i), 0}^{d \cdot x \cdot \prod_{j \in I_{σ}} μ_{i}}, g_{2}^{r_{i}}))}^{w_{i}}} \end{aligned}$ Then, if $π_{u} ⩽ π_{c}$ , then we have: $\begin{array}{r} \overline{κ} = e {(g_{1}, g_{2})}^{α \cdot s \cdot x} . \end{array}$ Then by applying the user decryption operation we get $\begin{matrix} H ({\overline{κ}}^{1 / x}) = H (e {(g_{1}, g_{2})}^{α \cdot s}) = κ \end{matrix}$ Finally, κ can be used to recover the plaintext of $C$ which contradicts our assumption and conclude the proof. □
Theorem 2 (Collusion Resistance).

Our construction is collusion resistant under the GDHE assumption.

Proof.
We prove the collusion resistance property using the security game ${Exp}_{A}^{C}$ (Definition 3). In the following, we show that the advantage of the adversary $A$ to win ${Exp}_{A}^{C}$ is negligible under the GDHE assumption (Definition 2).

Let us denote by $Ω_{G_{1}}$ , $Ω_{G_{2}}$ , and $Ω_{G_{t}}$ the set of elements of $G_{1}$ , $G_{2}$ , and $G_{t}$ respectively that are to be known by $A$ during ${Exp}_{A}^{C}$ . According to the latter, first the challenger performs GlobalSetup, AAKeyGen, and CAKeyGen and sends $env = (G_{1}, G_{2}, G_{T}, p, e (\cdot, \cdot), g_{1}, g_{2}, H, Ξ, CMK, VMK)$ and $MPK = {env, pka, \overline{pka}, pke, pkr, Θ_{σ, π_{p}}, {\overline{Θ}}_{σ, π_{p}}, π_{p} = 0}_{σ \in Σ}$ to $A$ . Hence, at the end of the setup phase, we have: $\begin{array}{c} Ω_{G_{1}} = {pka, Θ_{σ, π_{p}}}_{σ \in Σ} \\ Ω_{G_{2}} = {\overline{pka}, pkr, {\overline{Θ}}_{σ, π_{p}}}_{σ \in Σ} \\ Ω_{G_{t}} = {pke} \end{array}$

Afterwards, during the first phase of the query step, each secret decryption request query $Q_{j}$ issued by $A$ and answered by $C$ adds ${g_{1}^{{sk}_{i, j}} \cdot {pka}^{b_{i, j}}, g_{1}^{b_{i, j}}, Θ_{σ, π_{p}}^{b_{i, j}}}_{σ \in Σ_{j}, i \in A_{j}}$ to $Ω_{G_{1}}$ and nothing to $Ω_{G_{2}}$ and $Ω_{G_{t}}$ , where $A_{j}$ is used to denote the indices (in the set of all registered AA) of the attribute authorities used by $C$ to answer the query $Q_{j}$ . Then, in the challenge phase, the ciphertext $C^{*}$ returned to $A$ adds ${g_{2}^{s}, {\overline{pka}}^{λ_{i}} \cdot {\overline{Θ}}_{ρ (i), π_{p}}^{r_{i}}, g_{2}^{r_{i}}}_{i \in [1, l]}$ to $Ω_{G_{2}}$ and nothing to $Ω_{G_{1}}$ and $Ω_{G_{t}}$ . Then, similarly to the first phase, the second phase of the query step adds ${g_{1}^{{sk}_{i, j}} \cdot {pka}^{b_{i, j}}, g_{1}^{b_{i, j}}, Θ_{σ, π_{p}}^{b_{i, j}}}_{σ \in Σ_{j}}$ to $Ω_{G_{1}}$ and nothing to $Ω_{G_{2}}$ and $Ω_{G_{t}}$ . Hence, at the end of the second phase of the query step, supposing that $A$ performs m secret decryption queries during the query phase, he/she disposes of the following elements $\begin{array}{c} Ω_{G_{1}} = {pka, Θ_{σ, π_{p}}, g_{1}^{{sk}_{i, j}} \cdot {pka}^{b_{i, j}}, g_{1}^{b_{i, j}}, Θ_{σ, π_{p}}^{b_{i, j}}, g_{1}^{b_{i, j} \cdot δ}}_{σ \in Σ_{j}, j \in [1, m], i \in A_{i}} \\ Ω_{G_{2}} = {\overline{pka}, pkr, {pkt}_{0}, {\overline{Θ}}_{σ, π_{p}}, g_{2}^{s}, {\overline{pka}}^{λ_{i}} \cdot {\overline{Θ}}_{ρ (i), π_{p}}^{r_{i}}, g_{2}^{r_{i}}}_{i \in [1, l]} \\ Ω_{G_{t}} = {pke} \end{array}$

Hence, to prove the theorem we need to show that the advantage of $A$ to decide whether the element $U \in G_{t}$ used to generate the symmetric key κ is equal to ${pke}^{s}$ or a random element of $G_{t}$ is negligible. According to the GHDE assumption, the previous statement can be proved by showing that $f = α \cdot s$ is independent of $(R, S, T)$ where $\begin{array}{c} R = {a, \sum_{i = 1}^{n} θ_{σ, i, π_{p}}, {sk}_{i, j} + b_{i, j}, b_{i, j} \cdot \sum_{i = 1}^{n} θ_{σ, i, π_{p}}}_{σ \in Σ, j \in [1, m], i \in A_{i}} \\ S = {a, \overline{α}, \sum_{i = 1}^{n} θ_{σ, i, π_{p}}, s, a \cdot λ_{j} + r_{j} \cdot \sum_{i = 1}^{n} θ_{σ, i, π_{p}}, r_{j}}_{i \in [1, n], j \in [1, l]} \\ T = {α} \end{array}$ According to Definition 1, to prove that f is independent of $(R, S, T)$ , we need to prove that no combination of elements from $(R, S, T)$ could exists with non-negligible probability such that there exists constants $ϑ_{i, j}^{(a)}$ , $ϑ_{k}^{(b)}$ so that the following equation holds: $\begin{matrix} (3) & α \cdot s = \sum_{i, j} ϑ_{i, j}^{(a)} \cdot r_{i} \cdot s_{j} + \sum_{k} ϑ_{k}^{(b)} \cdot t_{k} \end{matrix}$ At this level, we emphasis that since a, $θ_{σ, i}$ , and $b_{i, j}$ are random variables in $Z_{p}$ , then the probability that a combination of these elements will give f is negligible. Then all elements of R involving a, $θ_{σ, i}$ , and $b_{i, j}$ cannot be part of Equation (3), which means that $R = \emptyset$ . Similarly we can exclude the elements a, $\overline{α}$ , $\sum_{i = 1}^{n} θ_{σ, i}$ , and $r_{j}$ from S to get $S = {s}$ . So, let $ϑ^{(1)}$ , $ϑ^{(2)}$ be constant such that: $\begin{matrix} (4) & α \cdot s = ϑ^{(1)} \cdot s + ϑ^{(2)} \cdot α \end{matrix}$ To conclude the proof, we need to show that no $ϑ^{(1)}$ and $ϑ^{(2)}$ could exist such that Equation (4) holds. So let us consider Equation (4) as a polynomial in α and regroup the monomials according to their degree in α to get $ϑ^{(1)} \cdot s = 0$ . Since s is a random variable in $Z_{p}$ , then $ϑ^{(1)} = 0$ (I). Finally, we do the same by considering Equation (4) as a polynomial in s, we get $α = ϑ^{(1)}$ . However, since α is generated randomly from $Z_{p}$ , then $ϑ^{(1)} \neq 0$ with overwhelming probability, which contradicts (I) and concludes the proof. □
Theorem 3 (Robustness).

Our construction is $(t, n)$ -robust under the GDHE assumption.

Proof.
According to Definition 4, to prove the robustness of our construction, we need to show that the advantage of the adversary $A$ for winning the game ${Exp}_{A}^{R}$ is negligible under the GDHE assumption.

Similarly, we use $Ω_{G_{1}}$ , $Ω_{G_{2}}$ , and $Ω_{G_{t}}$ to denote the set of elements of $G_{1}$ , $G_{2}$ , and $G_{t}$ respectively that are to be known by $A$ during ${Exp}_{A}^{C}$ . As the first four steps of the ${Exp}_{A}^{R}$ security game (Definition 4) are the same in the security game ${Exp}_{A}^{C}$ (Definition 3), then we follow the same strategy as in the proof of Theorem 2 to show that at the end of the fourth step of ${Exp}_{A}^{R}$ , we have $\begin{array}{c} Ω_{G_{1}} = {pka, Θ_{σ}, g_{1}^{{sk}_{i, j}} \cdot {pka}^{b_{i, j}}, g_{1}^{b_{i, j}}, Θ_{σ}^{b_{i, j}}, g_{1}^{b_{i, j} \cdot δ}}_{σ \in Σ_{j}, j \in [1, m], i \in A_{i}} \\ Ω_{G_{2}} = {\overline{pka}, pkr, {pkt}_{0}, {\overline{Θ}}_{σ}, g_{2}^{s}, {\overline{pka}}^{λ_{i}} \cdot {\overline{Θ}}_{ρ (i)}^{r_{i}}, g_{2}^{r_{i}}}_{i \in [1, l]} \\ Ω_{G_{t}} = {pke} \end{array}$ In the step 5 of ${Exp}_{A}^{R}$ , $A$ can adaptively choose $t - 1$ out the n registered attribute authorities and compromise them to get their secret key shares. Let us denote by ${AA}_{c}$ the set of compromised attribute authorities. Knowing the secret key shares ${SK}_{A}$ , $A \in {AA}_{c}$ , the adversary $A$ can compute $G_{i}^{{SK}_{A}^{z}}$ for all $z \in Z$ , all $G_{i} \in Ω_{G_{i}}$ , and all $A \in {AA}_{c}$ . Therefore, to prove the theorem, we need to show that the advantage of $A$ to decide whether the element $U \in G_{t}$ used to generate the symmetric key κ is equal to ${pke}^{s}$ or a random element of $G_{t}$ is negligible. Relying on the GDHE assumption, the previous statement can be proved if we can show that $f = α \cdot s$ is independent of $(R, S, T)$ where $\begin{array}{c} R = {a \cdot {SK}_{A}^{z}, {SK}_{A}^{z} \cdot \sum_{i = 1}^{n} θ_{σ, i}, ({sk}_{i, j} + b_{i, j}) \cdot {SK}_{A}^{z}, {SK}_{A}^{z} \cdot b_{i, j} \cdot \sum_{i = 1}^{n} θ_{σ, i}}_{σ \in Σ, j \in [1, m], i \in A_{i}, z \in Z, A \in {AA}_{c}} \\ \begin{aligned} S = & {a \cdot {SK}_{A}^{z}, \overline{α} \cdot {SK}_{A}^{z}, {SK}_{A}^{z} \cdot \sum_{i = 1}^{n} θ_{σ, i}, s \cdot, \\ {SK}_{A}^{z} \cdot (a \cdot λ_{j} + r_{j} \cdot \sum_{i = 1}^{n} θ_{σ, i}), {SK}_{A}^{z} \cdot r_{j}}_{i \in [1, n], j \in [1, l], z \in Z, A \in {AA}_{c}} \end{aligned} \\ T = {α \cdot {SK}_{A}^{z}}_{z \in Z, A \in {AA}_{c}} \end{array}$ Now based on the dependence definition (Definition 1), to prove the theorem we need to show that no combination of elements of $(R, S, T)$ could exists with non-negligible probability such that there exists constants $ϑ_{i, j}^{(a)}$ , $ϑ_{k}^{(b)}$ so that the following equation holds: $\begin{matrix} (5) & α \cdot s = \sum_{i, j} ϑ_{i, j}^{(a)} \cdot r_{i} \cdot s_{j} + \sum_{k} ϑ_{k}^{(b)} \cdot t_{k} \end{matrix}$ By, following the same reasoning as in the proof of Theorem 2, since the probability of getting f out of the randomly chosen values $\overline{α}$ , a, $θ_{σ, i}$ , δ, and $b_{i, j}$ is negligible, we can exclude all elements containing $\overline{α}$ , a, $θ_{σ, i}$ , δ, and $b_{i, j}$ from the sets R, S, and T. Then we get $\begin{array}{r} R = \emptyset, S = {s \cdot {SK}_{A}^{z}}_{z \in Z, A \in {AA}_{c}} and T = {α \cdot {SK}_{A}^{z}}_{z \in Z, A \in {AA}_{c}} \end{array}$ So, let $ϑ_{z, A}^{(1)}$ , $ϑ_{z, A}^{(2)}$ be constant such that: $\begin{matrix} (6) & α \cdot s = \sum_{z \in Z, A \in {AA}_{c}} ϑ_{z, A}^{(1)} \cdot s \cdot {SK}_{A}^{z} + \sum_{z \in Z, A \in {AA}_{c}} ϑ_{z, A}^{(2)} \cdot α \cdot {SK}_{A}^{z} \end{matrix}$ To prove that f is independent of $(R, S, T)$ , we need to show that no $ϑ_{z, A}^{(1)}$ and $ϑ_{z, A}^{(2)}$ for all $z \in Z$ and all $A \in {AA}_{c}$ can exist such that Equation (6) holds. Now let us consider the previous equation as a polynomial in s. We regroup the monomials according to their degree in s to get
$\sum_{z \in Z, A \in {AA}_{c}} ϑ_{z, A}^{(2)} \cdot α \cdot {SK}_{A}^{z} = 0$

$α \cdot s = \sum_{z \in Z, A \in {AA}_{c}} ϑ_{z, A}^{(1)} \cdot s \cdot {SK}_{A}^{z}$
First, let us focus on Equation (i). If the latter holds, then this means that one of the following condition also holds:
α is a root of non-zero polynomial of degree one

${SK}_{A}$ is a root of non-zero polynomial of degree z

$\forall z \in Z$ , $A \in {AA}_{c} : ϑ_{z, A}^{(2)} = 0$
Since α and ${SK}_{A}$ are chosen randomly from $Z_{p}$ , with p is a large prime, then the first two conditions hold with negligible probability of $1 / p$ and $z / p$ respectively. Therefore, we deduce (I) that condition (i.3) holds with overwhelming probability.

Now let us focus on Equation (ii) and consider it as a polynomial in s, then we get $\begin{matrix} (7) & \begin{aligned} α = \sum_{z \in Z, A \in {AA}_{c}} ϑ_{z, A}^{(1)} \cdot {SK}_{A}^{z} \\ \sum_{i = 1}^{n} f_{i} (0) = \sum_{z \in Z, A \in {AA}_{c}} ϑ_{z, A}^{(1)} \cdot {(\sum_{i = 1}^{n} f_{i} ({id}_{A}))}^{z} \end{aligned} \end{matrix}$ At this level, let us consider the previous equation (Equation (7)) as a polynomial in $f_{i}$ . We regroup the monomials according to their degree in $f_{i}$ to get the following:
$\forall z > 1$ , $\sum_{z \in Z, A \in {AA}_{c}} ϑ_{z, A}^{(1)} \cdot {(\sum_{i = 1}^{n} f_{i} ({id}_{A}))}^{z} = 0$

$\sum_{i = 1}^{n} f_{i} (0) = \sum_{A \in {AA}_{c}} ϑ_{z, A}^{(1)} \cdot \sum_{i = 1}^{n} f_{i} ({id}_{A})$
From equation (ii.1), since $f_{i}$ is randomly chosen from $Z_{p}^{t - 1}$ , then we can deduce (II) that, with overwhelming probability ( $≃ z / p^{t - 1}$ ), for all $z > 1$ , all $A \in {AA}_{c}$ , $ϑ_{z, A}^{(1)} = 0$ .

Now let us focus on Equation (ii.2). Since ${AA}_{c}$ is composed of $t - 1$ attribute authorities, let us denote by ${A_{1}^{(c)}, \dots, A_{t}^{(c)}}$ the set of attribute authorities in ${AA}_{c}$ . Then using the previous notation, we can rewrite Equation (ii.2) as $\begin{matrix} (8) & \sum_{i = 1}^{n} f_{i} (0) = \sum_{i = 1}^{n} \sum_{j = 1}^{t - 1} ϑ_{1, t}^{(1)} \cdot f_{i} ({id}_{A_{j}^{(c)}}) \end{matrix}$ As $\forall i \in [1, n]$ , $f_{i}$ is randomly chosen from $Z_{p}^{t - 1}$ , then we have $\begin{matrix} (9) & \forall i \in [1, n], f_{i} (0) = \sum_{j = 1}^{t - 1} ϑ_{1, t}^{(1)} \cdot f_{i} ({id}_{A_{j}^{(c)}}) \end{matrix}$ Now, by considering the fact that for all $i \in [1, n]$ , $f_{i}$ is a polynomial of degree $t - 1$ , then if Equation (9) holds, then one can use it to break the security of Shamir’s secret sharing scheme [36] which has been proven to be unconditionally secure. Consequently, no $ϑ_{1, t}^{(1)}$ can be found so that Equation (9) holds (III). Then, (I), (II), and (III) conclude the proof. □
Theorem 4.
Our construction is forward secure under the GDHE assumption.
Proof.
According to Definition 5, to prove that our scheme ensures forward secrecy, we need to show that ${Adv}^{{Exp}_{A, β_{1}}^{B - F}} (λ)$ and ${Adv}^{{Exp}_{A, β_{2}}^{B - F}} (λ)$ are negligible under the GDHE assumption.

Similarly to previous proofs, let us denote by $Ω_{G_{1}}$ , $Ω_{G_{2}}$ , and $Ω_{G_{t}}$ the set of elements of $G_{1}$ , $G_{2}$ , and $G_{t}$ respectively that are to be known by $A$ during ${Exp}_{A}^{B - F}$ . At the end of the step (2)(a), the secret decryption key issued by $C$ and sent to $A$ adds $\begin{matrix} {g_{1}^{α} \cdot g_{1}^{a \cdot d}, g_{1}^{d}, Θ_{σ, π_{p}}^{d}, g_{1}^{d \cdot δ}}_{σ \in Σ^{}} \end{matrix}$ to $Ω_{G_{1}}$ and nothing to $Ω_{G_{2}}$ and $Ω_{G_{t}}$ . The step (2)(b) of ${Exp}_{A}^{B - F}$ adds nothing to $Ω_{G_{1}}$ , $Ω_{G_{2}}$ and $Ω_{G_{t}}$ . Furthermore, during the step (3) of ${Exp}_{A}^{B - F}$ , the access revocation operation adds the random scalar $μ \in Z_{p}$ to the secret key ${SK}_{CSP}$ of the CSP and updates the master public key MPK by setting $Θ_{σ, π_{p} + 1} \leftarrow Θ_{σ, π_{p}}^{μ}$ and ${\overline{Θ}}_{σ, π_{p} + 1} \leftarrow {\overline{Θ}}_{σ, π_{p}}^{μ}$ for all $σ \in Σ^{'}$ . Hence, the revocation step adds $Θ_{σ, π_{p}}^{μ}$ to $G_{1}$ , ${\overline{Θ}}_{σ, π_{p}}^{μ}$ to $G_{2}$ and nothing to $G_{t}$ . Similarly to the step (2)(b), the step (4) adds nothing to $G_{1}$ , $G_{2}$ and $G_{t}$ . Finally, the challenge step (step (5)) adds $\begin{matrix} {g_{2}^{s}, {\overline{pka}}^{λ_{i}} \cdot {\overline{Θ}}_{ρ (i), π_{p}}^{μ \cdot r_{i}}, g_{2}^{r_{i}}, g_{2}^{s^{'}}, {\overline{pka}}^{λ_{i}^{'}} \cdot {\overline{Θ}}_{ρ^{'} (i), π_{p}}^{μ \cdot r_{i}^{'}}, g_{2}^{r_{i}^{'}}, {\overline{Θ}}_{σ, π_{p}}^{μ}, pkr, {pkt}_{j}}_{ρ (i) \in Σ^{}, ρ^{'} (i) \in Σ^{} ∖ Σ^{'}, σ \in Σ^{'}, j \in [0, π_{p}]} \end{matrix}$ to $Ω_{G_{2}}$ and nothing to $Ω_{G_{1}}$ and $Ω_{G_{t}}$ . Hence, at the end of step (5), we have $\begin{array}{c} Ω_{G_{1}} = {g_{1}^{α} \cdot g_{1}^{a \cdot d}, g_{1}^{d}, Θ_{σ, π_{p}}^{d}, Θ_{σ, π_{p}}^{μ}, g_{1}^{d \cdot δ}}_{σ^{} \in Σ^{}, σ \in Σ^{'}} \\ \begin{aligned} Ω_{G_{2}} = & {g_{2}^{s}, {\overline{pka}}^{λ_{i}} \cdot {\overline{Θ}}_{ρ (i), π_{p}}^{μ \cdot r_{i}}, g_{2}^{r_{i}}, g_{2}^{s^{'}}, {\overline{pka}}^{λ_{i}^{'}} \cdot {\overline{Θ}}_{ρ^{'} (i), π_{p}}^{μ \cdot r_{i}^{'}}, g_{2}^{r_{i}^{'}}, \\ {\overline{Θ}}_{σ, π_{p}}^{μ}, pkr, {pkt}_{j}}_{ρ (i) \in Σ^{}, ρ^{'} (i) \in Σ^{} ∖ Σ^{'}, σ \in Σ^{'}, j \in [0, π_{p}]} \end{aligned} \\ Ω_{G_{t}} = {pke} \end{array}$ Therefore, to prove forward secrecy, we need to show that the advantage of $A$ to decide whether $U = e {(g_{1}, g_{2})}^{α \cdot s}$ and $U^{'} = e {(g_{1}, g_{2})}^{α \cdot s^{'}}$ or are random elements of $G_{t}$ is negligible. Based on the GDHE assumption, the previous statement can be proved if we can show that $f = α \cdot s$ and $f^{'} = α \cdot s^{'}$ are independent of $(R, S, T)$ where $\begin{array}{c} R = {α + a \cdot d, d, d \cdot \sum_{i = 1}^{n} θ_{σ, i, π_{p}}, μ \cdot \sum_{i = 1}^{n} θ_{σ, i, π_{p}}, d \cdot δ}_{σ \in Σ^{}, j \in [1, m], i \in A_{i}} \\ S = {s, a \cdot λ_{i}, μ \cdot r_{i} \cdot \sum_{i = 1}^{n} θ_{σ, i, π_{p}}, r_{i}, s^{'}, a \cdot λ_{i}^{'}, μ \cdot r_{i}^{'} \cdot \sum_{i = 1}^{n} θ_{σ, i, π_{p}}, r_{i}^{'}}_{ρ (i) \in Σ^{}, ρ^{'} (i) \in Σ^{} ∖ Σ^{'}, σ \in Σ^{'}} \\ T = {α} \end{array}$ Then to show that f and $f^{'}$ are independent of $(R, S, T)$ , we must show that there exists no constants $ϑ_{i, j}^{(a)}$ , $ϑ_{k}^{(b)}$ , $ϑ_{i, j}^{' (a)}$ , $ϑ_{k}^{' (b)}$ such that $\begin{array}{c} (10) & α \cdot s = \sum_{i, j} ϑ_{i, j}^{(a)} \cdot r_{i} \cdot s_{j} + \sum_{k} ϑ_{k}^{(b)} \cdot t_{k} and \\ (11) & α \cdot s^{'} = \sum_{i, j} ϑ_{i, j}^{' (a)} \cdot r_{i} \cdot s_{j} + \sum_{k} ϑ_{k}^{' (b)} \cdot t_{k} \end{array}$ Let us start by Equation (10). Since a, d, $θ_{σ, i}$ , α, $s^{'}$ , $r_{i}$ , $r_{i}^{'}$ , μ and s are random variables in $Z_{p}$ and that a, d, $θ_{σ, i}$ , $s^{'}$ , $r_{i}$ , $r_{i}^{'}$ , and μ, are independent of α and s, then the probability that a combination of elements involving a, d, $θ_{σ, i}$ , $s^{'}$ , $r_{i}$ , $r_{i}^{'}$ , and μ will give f is negligible. So we can exclude all elements of R, S, and T involving a, d, $θ_{σ, i}$ , $s^{'}$ , $r_{i}$ , $r_{i}^{'}$ , and μ but not α, s, and $λ_{i}$ from Equation (10). Therefore, we have $\begin{matrix} (12) & α \cdot s = ϑ^{(1)} (α + a \cdot d) \cdot s + \sum_{ρ (i) \in Σ^{}} ϑ_{i}^{(2)} (α + a \cdot d) \cdot (a \cdot λ_{i}) + ϑ^{(3)} \cdot α \end{matrix}$ Let us consider Equation (12) as a polynomial in α and regroup the monomials according to their degree in α to get
$α \cdot s = ϑ^{(1)} \cdot α \cdot s + a \cdot α \sum_{ρ (i) \in Σ^{}} ϑ_{i}^{(2)} \cdot λ_{i} + ϑ^{(3)} \cdot α$

$ϑ^{(1)} \cdot a \cdot d \cdot s + a^{2} \cdot d \sum_{ρ (i) \in Σ^{}} ϑ_{i}^{(2)} \cdot λ_{i} = 0$
Let us now focus on Equation (i) by considering it as a polynomial on a. By regrouping the monomials according to their degree, we have:
$s = ϑ^{(1)} \cdot s + ϑ^{(3)}$

$\sum_{ρ (i) \in Σ^{}} ϑ_{i}^{(2)} \cdot λ_{i} = 0$
At this level, by considering Equation (i.1) as polynomial is s, we get $ϑ^{(1)} = 1$ . Let us now focus on Equation (ii) by considering it as polynomial in a. Then we have $ϑ^{(1)} \cdot d \cdot s = 0$ . As d and s are randomly chosen from $Z_{p}$ , then $ϑ^{(1)} = 0$ witch overwhelming probability, which contradicts $ϑ^{(1)} = 1$ and prove that Equation (10) does not hold. We can follow the same previous steps to prove that Equation (11) does not hold, which conclude the proof. □
Theorem 5.
Our construction is backward secure under the GDHE assumption.
Proof.
According to Definition 6, to prove that our scheme ensures backward secrecy, we need to show that ${Adv}^{{Exp}_{A}^{B}} (λ)$ are negligible under the GDHE assumption.

Similarly, we use $Ω_{G_{1}}$ , $Ω_{G_{2}}$ , and $Ω_{G_{t}}$ to denote the set of elements of $G_{1}$ , $G_{2}$ , and $G_{t}$ respectively that are to be known by $A$ during ${Exp}_{A}^{B}$ . Hence, after the third step of the game we have: $\begin{array}{c} Ω_{G_{1}} = {pka, Θ_{σ, 0}, g_{1}^{α} \cdot {pka}^{d_{j}}, g_{1}^{d_{j}}, Θ_{σ, 0}^{d_{j}}, g_{1}^{d_{j} \cdot δ}}_{σ \in Σ_{j}, j \in [1, m], i \in A_{i}} \\ Ω_{G_{2}} = {\overline{pka}, pkr, {pkt}_{0}, {\overline{Θ}}_{σ, 0}, g_{2}^{s}, {\overline{pka}}^{λ_{i}} \cdot {\overline{Θ}}_{ρ (i), 0}^{r_{i}}, g_{2}^{r_{i}}}_{i \in [1, l]} \\ Ω_{G_{t}} = {pke} \end{array}$ We emphasis here that the challenge phase is supposed to be performed during $π_{p} = 0$ .

In the step four of the security game, the challenger $C$ performs a access revocation to increment the timestep ( $π_{p} = 1$ ) of the system. The previous operation adds the items ${Θ_{σ, 1} = Θ_{σ, 0}^{μ}}_{σ \in Σ}$ and ${{\overline{Θ}}_{σ, 1} = {\overline{Θ}}_{σ, 0}^{μ}}_{σ \in Σ}$ to $Ω_{G_{1}}$ and $Ω_{G_{2}}$ respectively.

In step five of the considered security game, $A$ performs a secret key generation query. The latter adds ${Θ_{σ^{}, 1}^{d^{}}, g_{1}^{α} \cdot {pka}^{d^{}}, g_{1}^{d^{}}}$ to $Ω_{G_{1}}$ .

In order to establish the theorem, it is necessary to demonstrate that the advantage of $A$ in determining whether the element $U \in G_{t}$ , which is utilized to generate the symmetric key κ, is equal to ${pke}^{s}$ or a randomly chosen element from $G_{t}$ , is negligible. By relying on the GDHE (Generalized Decisional Diffie–Hellman Exponent) assumption, the aforementioned assertion can be proven if we can establish the independence of $f = α \cdot s$ from the variables $(R, S, T)$ , where $\begin{array}{c} \begin{aligned} R = & {α + a \cdot d_{j}, d_{j}, d_{j} \cdot \sum_{i = 1}^{n} θ_{σ, i, 0}, \sum_{i = 1}^{n} θ_{σ, i, 0}, d_{j} \cdot δ, d^{} \cdot \sum_{i = 1}^{n} θ_{σ^{}, i, 1}, \\ α + a \cdot d^{}, d^{}}_{σ \in Σ_{j}, σ^{} \in Σ_{j}^{}, j \in [1, m]} \end{aligned} \\ S = {s, a \cdot λ_{i} + r_{i} \cdot \sum_{i = 1}^{n} θ_{σ^{}, i, 0}, r_{i}, δ}_{σ^{} \in Σ^{}} \\ T = {α} \end{array}$ It is important to highlight that the inability to decrypt $C^{}$ arises from the secret decryption retrieved during the query step (Step 2). This is due to the fact that the set of attributes $Σ_{i}$ involved in the queries does not satisfy the access structure $M^{}$ used to encrypt $C^{}$ . Consequently, all elements in which $d_{j}$ and $σ \in Σ_{j}$ are present should be excluded from R, S, and T. In addition, since the probability of getting f out of the randomly chosen values a and δ, we can exclude all elements containing a and δ from the sets R, S, and T. Therefore, we get $\begin{matrix} (13) & R = {α + a \cdot d^{}, d^{} \cdot \sum_{i = 1}^{n} θ_{σ^{}, i, 1}}, S = {s, a \cdot λ_{i}, d^{} \cdot \sum_{i = 1}^{n} θ_{σ^{}, i, 0}}, and T = {α} \end{matrix}$

To establish the theorem, we must demonstrate that it is impossible for any combination of elements from sets R, S, and T to exist with a non-negligible probability, where certain constants $ϑ_{i, j}^{(a)}$ and $ϑ_{k}^{(b)}$ satisfy the following equation, according to the definition of dependence (Definition 1): $\begin{matrix} (14) & \begin{aligned} \begin{aligned} α \cdot s & = \sum_{i, j} ϑ_{i, j}^{(a)} \cdot r_{i} \cdot s_{j} + \sum_{k} ϑ_{k}^{(b)} \cdot t_{k} \\ = ϑ^{(1)} (α + a \cdot d^{}) s + ϑ^{(2)} (α + a \cdot d^{}) (a \cdot λ_{i}) + ϑ^{(3)} (α + a \cdot d^{}) (d^{} \cdot \sum_{i = 1}^{n} θ_{σ^{}, i, 0}) \end{aligned} \\ ϑ^{(4)} s \cdot d^{} \cdot μ \sum_{i = 1}^{n} θ_{σ^{}, i, 0} + ϑ^{(5)} a \cdot λ_{i} \cdot d^{} \cdot μ \sum_{i = 1}^{n} θ_{σ^{}, i, 0} + ϑ^{(6)} {(d^{})}^{2} \cdot μ {(\sum_{i = 1}^{n} θ_{σ^{}, i, 0})}^{2} \end{aligned} \end{matrix}$ Hence, to prove the theorem, we need to show that $ϑ^{(k)} = 0$ , $\forall k \in [1, 6]$ .

First, let us consider Equation (14) as a polynomial in μ. By regrouping the monomials according to their degree, we have: $\begin{matrix} (15) & ϑ^{(1)} (α + a \cdot d^{}) s + ϑ^{(2)} (α + a \cdot d^{}) (a \cdot λ_{i}) + ϑ^{(3)} (α + a \cdot d^{}) (d^{} \cdot \sum_{i = 1}^{n} θ_{σ^{}, i, 0}) = 0 \end{matrix}$ and $\begin{matrix} (16) & ϑ^{(4)} s \cdot d^{} \cdot μ \sum_{i = 1}^{n} θ_{σ^{}, i, 0} + ϑ^{(5)} a \cdot λ_{i} \cdot d^{} \cdot μ \sum_{i = 1}^{n} θ_{σ^{}, i, 0} + ϑ^{(6)} {(d^{})}^{2} \cdot μ {(\sum_{i = 1}^{n} θ_{σ^{}, i, 0})}^{2} = 0 \end{matrix}$ Let us focus on Equation (15) and consider it as a polynomial in $d^{}$ , then we have: $\begin{matrix} (17) & ϑ^{(3)} a \cdot {(d^{})}^{2} \cdot \sum_{i = 1}^{n} θ_{σ^{}, i, 0} = 0 \Leftrightarrow ϑ^{(3)} = 0 . \end{matrix}$ and $\begin{matrix} (18) & ϑ^{(1)} (α + a \cdot d^{}) s + ϑ^{(2)} (α + a \cdot d^{}) (a \cdot λ_{i}) = 0 \end{matrix}$ Now, if we consider the latte equation as a polynomial in a, the we get:
$ϑ^{(2)} a^{2} \cdot d^{} \cdot λ_{i} = 0 \Leftrightarrow ϑ^{(2)} = 0$

$ϑ^{(1)} a \cdot d^{} \cdot s = 0 \Leftrightarrow ϑ^{(1)} = 0$
At this level, we showed that $ϑ^{(1)} = ϑ^{(2)} = ϑ^{(3)} = 0$ . So, we have to show that $ϑ^{(4)} = ϑ^{(5)} = ϑ^{(6)} = 0$ . Let us focus on Equation (16) and consider it as a polynomial in a. Then we have: $\begin{matrix} (19) & ϑ^{(5)} a \cdot λ_{i} \cdot d^{} \cdot μ \sum_{i = 1}^{n} θ_{σ^{}, i, 0} = 0 \Leftrightarrow ϑ^{(5)} = 0 \end{matrix}$ and $\begin{matrix} (20) & ϑ^{(4)} s \cdot d^{} \cdot μ \sum_{i = 1}^{n} θ_{σ^{}, i, 0} + ϑ^{(6)} {(d^{})}^{2} \cdot μ {(\sum_{i = 1}^{n} θ_{σ^{}, i, 0})}^{2} = 0 \end{matrix}$ Finally, let us consider the latter Equation a polynomial in $d^{}$ , then we have:
$ϑ^{(4)} s \cdot d^{} \cdot μ \sum_{i = 1}^{n} θ_{σ^{}, i, 0} = 0 \Leftrightarrow ϑ^{(4)} = 0$

$ϑ^{(6)} {(d^{})}^{2} \cdot μ {(\sum_{i = 1}^{n} θ_{σ^{*}, i, 0})}^{2} = 0 \Leftrightarrow ϑ^{(6)} = 0$
which concludes the proof. □

7. The complexity

In this section, we analyze the practicability of our construction regarding several properties. We evaluate the storage and communication overheads, as well as the computation cost of the different operations used by our construction. We also evaluate compare the sizes of the different cryptographic keys to be used by the entities involved in our construction. For a better understanding of the evaluation results, we conduct a comparative analysis between our construction and TMACS [23]. Both schemes are achieving robustness while providing ABE-based fine-grained access control. The notations we used in the complexity evaluation are described in Table 2.

Table 2
Notations used in the conducted evaluation

Notation Description

n The number of AAs

t Robustness level ( $⩽ n$ )

$N_{Σ}$ The number of attributes in the system

$N_{u}$ The number of attributes held by a user

$N_{U}$ The number of users in the system

$N_{O}$ The number of data owners in the system

$N_{I}$ Average data item size

l The number of rows of the access matrix

$S_{G_{}}$ The size of an element in $G_{}$ , $* \in {0, 1, t}$

$S_{Z_{p}}$ The size of an element in $Z_{p}$

π Number of performed access revocations

$X$ Set of data encrypted items

$N_{U, R}$ Number of users concerned by a revocation request

$N_{Σ, R}$ Number of attributes concerned by a revocation request

$M$ A group exponentiation operation

$E$ A pairing operation

Notation	Description
n	The number of AAs
t	Robustness level ( $⩽ n$ )
$N_{Σ}$	The number of attributes in the system
$N_{u}$	The number of attributes held by a user
$N_{U}$	The number of users in the system
$N_{O}$	The number of data owners in the system
$N_{I}$	Average data item size
l	The number of rows of the access matrix
$S_{G_{*}}$	The size of an element in $G_{}$ , $ \in {0, 1, t}$
$S_{Z_{p}}$	The size of an element in $Z_{p}$
π	Number of performed access revocations
$X$	Set of data encrypted items
$N_{U, R}$	Number of users concerned by a revocation request
$N_{Σ, R}$	Number of attributes concerned by a revocation request
$M$	A group exponentiation operation
$E$	A pairing operation

7.1. Storage complexity

In Table 3, we compare the storage complexity of our construction and TMACS on the different entities. Specifically, we quantify the storage complexity in terms of the size of elements (e.g., group elements, certificates, etc.) that are to be stored by each entity. Compared to TMACS, our construction requires less information to be stored by DCA and AA. In addition the size of an encrypted data item in our scheme is smaller than the one of TMACS. On the DU side, no more information needs to be stored compared to TMACS. When comes to CSP, our construction requires the CSP to store a revocation key of size linear to the number of performed revocation operations. While the latter can be large in some use cases, we stress that the CSP is supposed to have unlimited storage space. Note that the TMACS scheme does not require the CSP to store any revocation key as it does not enable access revocation.

Table 3
Comparison of the storage complexity

Entity This work TMACS

DCA $(N_{U} + n) S_{Z_{p}}$ $(2 N_{Σ} + 10) S_{G_{1}} + (2 N_{U} + n) S_{Z_{p}}$

AA $(3 + 2 N_{Σ}) S_{Z_{p}}$ $(6 + 2 N_{Σ}) S_{Z_{p}}$

DP - -

DU $(2 + N_{u}) S_{G_{1}}$ $(2 + N_{u}) S_{G_{1}}$

CSP Keys ${max}_{C \in X} (π - π_{C}) S_{Z_{p}}$ -

Data $(1 + 2 l) S_{G_{2}}$ $(1 + 2 l) S_{G_{2}} + S_{G_{t}}$

Entity	This work	TMACS
DCA	$(N_{U} + n) S_{Z_{p}}$	$(2 N_{Σ} + 10) S_{G_{1}} + (2 N_{U} + n) S_{Z_{p}}$
AA	$(3 + 2 N_{Σ}) S_{Z_{p}}$	$(6 + 2 N_{Σ}) S_{Z_{p}}$
DP	-	-
DU	$(2 + N_{u}) S_{G_{1}}$	$(2 + N_{u}) S_{G_{1}}$
CSP	Keys	${max}_{C \in X} (π - π_{C}) S_{Z_{p}}$	-
Data	$(1 + 2 l) S_{G_{2}}$	$(1 + 2 l) S_{G_{2}} + S_{G_{t}}$

The sign (-) is used to indicate that no storage is required.

7.2. Communication complexity

In Table 4, we provide a comparison of the theoretical communication complexities incurred by the different processes involved in our construction and TMACS. Specifically, we quantify the amount of information (in terms of the sizes of used group elements) exchanged by each entity during the different processes.

Table 4
Comparison of the communication complexity

Process Entities This work TMACS

Setup DCA $(2 n + 2 N_{U} + 2) S_{Z_{p}}$ $4 N_{U} + 4 N_{O} + 2 n N_{Σ}$

AA $(5 n + 3) S_{Z_{p}} + (N_{Σ} + 1) S_{G_{1}} + (N_{Σ} + 2) S_{G_{2}} + S_{G_{t}}$ $(2 n + 1) S_{Z_{p}} + S_{G_{1}}$

DU $4 S_{Z_{p}}$ $4 S_{Z_{p}}$

DO $(2 N_{U} + 1) S_{G_{2}}$ $(2 N_{U} + 1) S_{G_{2}}$

Decryption key AA $(2 + N_{u}) S_{G_{1}}$ $(2 + N_{u}) S_{G_{1}}$

Generation DU $(2 + N_{u}) {tS}_{G_{1}}$ $(2 + N_{u}) {tS}_{G_{1}}$

Data DU $(2 + N_{u}) S_{G_{1}}$ -

Decryption CSP $S_{G_{t}} + N_{I}$ $(2 + N_{u}) S_{G_{2}} + N_{I}$

Revocation CSP $(t + 1) S_{G_{2}} + N_{Σ, R} (S_{G_{1}} + S_{G_{2}})$ N/A

AA $3 S_{G_{2}} + (2 + N_{u}) (N_{U} - N_{U, R}) S_{G_{1}}$ N/A

DU $(2 + N_{u}) {tS}_{G_{1}}$

Process	Entities	This work	TMACS
Setup	DCA	$(2 n + 2 N_{U} + 2) S_{Z_{p}}$	$4 N_{U} + 4 N_{O} + 2 n N_{Σ}$
AA	$(5 n + 3) S_{Z_{p}} + (N_{Σ} + 1) S_{G_{1}} + (N_{Σ} + 2) S_{G_{2}} + S_{G_{t}}$	$(2 n + 1) S_{Z_{p}} + S_{G_{1}}$
DU	$4 S_{Z_{p}}$	$4 S_{Z_{p}}$
DO	$(2 N_{U} + 1) S_{G_{2}}$	$(2 N_{U} + 1) S_{G_{2}}$
Decryption key	AA	$(2 + N_{u}) S_{G_{1}}$	$(2 + N_{u}) S_{G_{1}}$
Generation	DU	$(2 + N_{u}) {tS}_{G_{1}}$	$(2 + N_{u}) {tS}_{G_{1}}$
Data	DU	$(2 + N_{u}) S_{G_{1}}$	-
Decryption	CSP	$S_{G_{t}} + N_{I}$	$(2 + N_{u}) S_{G_{2}} + N_{I}$
Revocation	CSP	$(t + 1) S_{G_{2}} + N_{Σ, R} (S_{G_{1}} + S_{G_{2}})$	N/A
AA	$3 S_{G_{2}} + (2 + N_{u}) (N_{U} - N_{U, R}) S_{G_{1}}$	N/A
DU	$(2 + N_{u}) {tS}_{G_{1}}$

The items in bold represents the smallest communication complexity of two compared schemes, the sign (-) is used to indicate that no communication is required by an entity, and we used (N/A) to indicate that the process is not supported by a scheme.

As illustrate in the table, our construction does not include any communication overhead compared to TMACS, except for (i) AA during the setup process and (ii) DU during the data decryption process. However, we stress that both (linear) overheads can be tolerated since the first occurs only once during the setup phase, while the second permits the DU to considerably reduce the amount of computations required for data decryption (Table 5) by using the outsourced pre-decryption. Besides, our construction slightly reduces the communication complexity for DCA and CSP during the setup and the data decryption processes respectively.

7.3. Computation complexity

In this section, we give a comparative analysis of the computational complexity of our scheme and TMACS. Table 5 shows, for the two constructions, the computational complexities for the different entities of the system when performing the different processes. The processes complexities are expressed mainly in terms of the number of group exponentiations and pairings. We note here that we ignore computations related to certificate generation and signature as they are performed by most existing ABE schemes.

Table 5
Comparison of the computation complexity

Process Entities This work TMACS

Setup DCA $4 t E$ $t E$

AA $(4 + 2 N_{Σ}) E$ $E$

Decryption key AA $(2 + 2 N_{u}) M$ $(2 + 2 N_{u}) M$

Generation DU $(2 t + {tN}_{u}) M$ $(2 t + {tN}_{u}) M$

Encryption DO $E + (2 l + 1) M$ $E + (2 l + 1) M$

Decryption DU $M$ $(1 + 2 l) E$

CSP $(1 + 2 l) E + (π - π_{C}) M$ -

Revocation CSP $(t + 2 N_{Σ, R}) M$ N/A

AA $3 M N$ N/A

DU $(2 t + {tN}_{u}) M$ N/A

Process	Entities	This work	TMACS
Setup	DCA	$4 t E$	$t E$
AA	$(4 + 2 N_{Σ}) E$	$E$
Decryption key	AA	$(2 + 2 N_{u}) M$	$(2 + 2 N_{u}) M$
Generation	DU	$(2 t + {tN}_{u}) M$	$(2 t + {tN}_{u}) M$
Encryption	DO	$E + (2 l + 1) M$	$E + (2 l + 1) M$
Decryption	DU	$M$	$(1 + 2 l) E$
CSP	$(1 + 2 l) E + (π - π_{C}) M$	-
Revocation	CSP	$(t + 2 N_{Σ, R}) M$	N/A
AA	$3 M N$	N/A
DU	$(2 t + {tN}_{u}) M$	N/A

The items in bold represents the smallest communication complexity of two compared schemes, the sign (-) is used to indicate that no communication are required by an entity, and we used (N/A) to indicate that the process is not supported by a scheme.

The comparison shows that our construction does not include any computation overhead compared to TMACS for performing data encryption and decryption key generation processes. Thanks to the outsourcing pre-decryption, our construction drastically reduces the amount of computations required to be performed by DU for decrypting a data item. However, our construction requires linearly in the number of attributes more group exponentiations than TMACS to perform the setup process. Again, we stress that this latter computation overhead can be tolerated as it occurs only once during the setup phase.

8. The implementation framework

Figure 2 gives an overview of the framework implementing our construction. To implement the capabilities of the different components of our ABE construction and to allow them to communicate, we used a java-based framework called Spring Boot [39] (Spring Boot Framework). Each component exposes a Rest API in charge of processing over components’ queries and send returning responses. To ensure the confidentiality of the exchanged information between the different components, communications are performed over HTTPS. Moreover, to authenticate the data exchanged between the different components, we use the open, industry standard RFC 7519 JSON Web Tokens [16].

Fig. 2.

Overview of the implementation framework.

The functionalities provided by our decentralized ABE (e.g., encryption, decryption, etc.) requires mathematical operations underlying pairing-based cryptosystems such as, bilinear pairings, cyclic groups elements exponentiation and multi-exponentiation, etc. In our implementation, these mathematical operations are provided by the jPBC library [8]. As storage infrastructure, we use MinIO [29], a High-Performance Object Storage compatible with Amazon S3 cloud storage service.

9. Experimental evaluation

9.1. Experimental setup

The features of our construction are evaluated on a Linux server having 2ÕIntel(R) Xeon(R) CPU E5-2695 v3 @ 2.30 GHz, 2Õ14/14 cores; 28 threads. During the conducted evaluations, each entity is deployed in a virtual machine having 4 vCPUs,2

²
Our implementation is not multi-threaded, however, we stress that most operations (e.g., encryption, decryption, and revocation) are embarrassingly parallelizable.

8 GB of memory, and 50 GB storage. In addition, we examine the practicality of our method for data consumers utilizing restricted devices. In this case, we analyze the utilization of a Multos Smartcard equipped with SC23Z018 secure microcontrollers, which possess 4 kb of RAM and operate on the Multos OS.

9.2. Experimental results

In this section, we give the timing performance of four functions from our construction, namely: Setup function regarding the number of involved attribute authority; Encryption function regarding the number of attributes in the access policy; Decryption key generation time regarding the number of attributes associated to the data and the robustness level; and finally, decryption function regarding the number of attributes in the access policy (with and without ciphertext update).

Fig. 3.

System initialization time as a function of the number of involved attribute authorities.

Figure 3 illustrates the execution time of the system initialization function according to the number of involved attribute authorities. As described previously, this function is composed of two phases, the entity registration phase, which is shown in blue in the plot, and the public master key generation phase, shown in red. The x-axis represents the numbers of involved attribute authorities and the y-axis represents execution time in seconds, and we can clearly see that the time required for system initialization grows linearly according to the number of involved attribute authorities.

Fig. 4.

Time required for encryption as a function of the number of attributes in the access policy.

Figure 4 depicts the execution time of the encryption function according to the number of attributes in the access policy, this time the duration is represented in milliseconds on the x-axis and the y-axis represents the number of attributes of the access policy.

Figure 5 show the execution time of the decryption key generation according to two parameters, the first on is the number of attributes associated to the consumer data and the second one is the robustness level t (we remember that t is the minimum number of attribute authorities that must collaborate together to generate the secret decryption key). In this figure, we have used a colour codification to vary the parameter level of robustness t, and keep the same graduation for the parameter number of attributes, namely the execution time in milliseconds on the x-axis and number of attributes on the x-axis.

Fig. 5.

Secret decryption key generation time as the number of attributes associated to the data consumer and the robustness level t.

Fig. 6.

Decryption evaluation.

Figure 6 consists on the evaluation of the decryption function, it is composed of two graphs “a” and “b”. Graph a shows the execution time of the ciphertext updating according to the number of revoked attributes, and graph b represent the execution time of the decryption function according to the number of required attributes. In both graphs, the y-axis represents the execution time in milliseconds and the x-axis represents respectively the number of revoked attributes for “a” and then the number of required attributes for “b”.

Moreover, we assess the functionality of the outsourced decryption feature when executed by the aforementioned Multos Smartcard. The evaluation results are represented in the Table 6. The latter report the time required by the smart card to randomize the secret decryption key.

Table 6

Outsourced decryption latency on constrained device

Number of attributes	Key randomization	Partial decryption (CSP)	Final decryption	Total
2	301 ms	0.7 ms	60 ms	362 ms
4	417 ms	0.7 ms	60 ms	478 ms
8	637 ms	0.8 ms	60 ms	698 ms
16	1,02 s	0.9 ms	60 ms	1,08 s

Finally, we evaluated the quantity of information exchanged between the various entities during the different operations of our scheme. The results are presented in Table 7. During the system setup phase, we measured the quantity of data exchanged between the attribute authorities as they collaboratively generated the master public key, as a function of the number n of involved AAs. For access revocation, we quantified the information exchanged between the AAs and the CSP. For encryption and decryption, we measured the quantity of data exchanged as a function of the number of attributes in the enforced access policy (denoted by l) and in secret decryption key (denoted by $N_{u}$ ) respectively. It is important to note that only ABE elements are considered for encryption and decryption. The size of the exchanged AES encryption of the data item itself is not included.

Table 7

Data exchanged between entities during various operations of the scheme

Key generation			Data encryption			Data decryption			Access revocation

$n = 4$	$n = 8$	$n = 16$	$l = 4$	$l = 8$	$l = 16$	$N_{u} = 4$	$N_{u} = 8$	$N_{u} = 16$	$Σ_{r} = 4$	$Σ_{r} = 8$	$Σ_{r} = 16$
581 B	2, 04 KB	8, 1 KB	198 B	330 B	594 B	301 B	433 B	697 B	127 B	292 B	477 B

10. Conclusion

In this work, we propose the first CP-ABE fine-grained access control construction for outsourced data that enables the following features simultaneously. First, it ensures robustness for both decryption key issuing and access revocation while achieving both forward and backward secrecy. Second, it enables outsourced decryption to reduce the decryption overhead for data users that have limited computational resources. Third, it achieves adaptive security in standard models. In the future, it will be interesting to investigate whether we can extend the construction to ensure backward secrecy. In addition, we provide an overview of the framework implementing our ABE construction and conduct several experimentations to study the efficiency of our ABE construction.

References

A.S.

Ahmed and

Aura, Turning trust around: Smart contract-assisted public key infrastructure, in: 2018 17th IEEE International Conference on Trust, Security and Privacy in Computing and Communications/12th IEEE International Conference on Big Data Science and Engineering (TrustCom/BigDataSE), IEEE, 2018, pp. 104–111.

R.R.

Al-Dahhan,

Shi,

G.M.

Lee and

Kifayat, Survey on revocation in ciphertext-policy attribute-based encryption, Sensors19(7) (2019), 1695. doi:10.3390/s19071695.

Bertilsson and

Ingemarsson, A construction of practical secret sharing schemes using linear block codes, in: International Workshop on the Theory and Application of Cryptographic Techniques, Springer, 1992, pp. 67–79.

Bethencourt,

Sahai and

Waters, Ciphertext-policy attribute-based encryption, in: 2007 IEEE Symposium on Security and Privacy (SP’07), IEEE, 2007, pp. 321–334. doi:10.1109/SP.2007.11.

Bkakria, Robust and provably secure attribute-based encryption supporting access revocation and outsourced decryption, in: Data and Applications Security and Privacy XXXVI – 36th Annual IFIP WG 11.3 Conference, DBSec 2022, Proceedings, Newark, NJ, USA, July 18–20, 2022,

Sural and

Lu, eds, Lecture Notes in Computer Science, Vol. 13383, Springer, 2022, pp. 197–214. doi:10.1007/978-3-031-10684-2_12.

Boyen, The uber-assumption family, in: Pairing-Based Cryptography – Pairing 2008,

S.D.

Galbraith and

K.G.

Paterson, eds, Springer, Berlin, Heidelberg, 2008, pp. 39–56. ISBN 978-3-540-85538-5. doi:10.1007/978-3-540-85538-5_3.

Cui,

R.H.

Deng,

Li and

Qin, Server-aided revocable attribute-based encryption, in: European Symposium on Research in Computer Security, Springer, 2016, pp. 570–587.

De Caro and

Iovino, jPBC: Java pairing based cryptography, in: Proceedings of the 16th IEEE Symposium on Computers and Communications, ISCC 2011, June 28–July 1, 2011, Kerkyra, Corfu, Greece, IEEE, 2011, pp. 850–855, http://gas.dia.unisa.it/projects/jpbc/ .

Emura,

Miyaji,

Nomura,

Omote and

Soshi, A ciphertext-policy attribute-based encryption scheme with constant ciphertext length, in: International Conference on Information Security Practice and Experience, Springer, 2009, pp. 13–23. doi:10.1007/978-3-642-00843-6_2.

10.

Ge,

Susilo,

Baek,

Liu,

Xia and

Fang, Revocable attribute-based encryption with data integrity in clouds, IEEE Transactions on Dependable and Secure Computing19(5) (2021), 2864–2872. doi:10.1109/TDSC.2021.3065999.

11.

Goyal,

Jain,

Pandey and

Sahai, Bounded ciphertext policy attribute based encryption, in: International Colloquium on Automata, Languages, and Programming, Springer, 2008, pp. 579–591. doi:10.1007/978-3-540-70583-3_47.

12.

Han,

Susilo,

Mu and

Yan, Privacy-preserving decentralized key-policy attribute-based encryption, IEEE transactions on parallel and distributed systems23(11) (2012), 2150–2162. doi:10.1109/TPDS.2012.50.

13.

Han,

Susilo,

Mu,

Zhou and

M.H.

Au, PPDCP-ABE: Privacy-preserving decentralized ciphertext-policy attribute-based encryption, in: European Symposium on Research in Computer Security, Springer, 2014, pp. 73–90.

14.

Hur and

D.K.

Noh, Attribute-based access control with efficient revocation in data outsourcing systems, IEEE Transactions on Parallel and Distributed Systems22(7) (2011), 1214–1221. doi:10.1109/TPDS.2010.203.

15.

Ito,

Saito and

Nishizeki, Secret sharing scheme realizing general access structure, Electronics and Communications in Japan (Part III: Fundamental Electronic Science)72(9) (1989), 56–64.

16.

Jones,

Bradley and

Sakimura, JSON web token (JWT), RFC 7519, Internet Engineering Task Force, 2015.

17.

Karchmer and

Wigderson, On span programs, in: Proceedings of the Eighth Annual Structure in Complexity Theory Conference, IEEE, 1993, pp. 102–111. doi:10.1109/SCT.1993.336536.

18.

Kumar,

Alphonseet al., Attribute based encryption in cloud computing: A survey, gap analysis, and future directions, Journal of Network and Computer Applications108 (2018), 37–52. doi:10.1016/j.jnca.2018.02.009.

19.

Lewko,

Sahai and

Waters, Revocation systems with very small private keys, in: 2010 IEEE Symposium on Security and Privacy, IEEE, 2010, pp. 273–285. doi:10.1109/SP.2010.23.

20.

Lewko and

Waters, Decentralizing attribute-based encryption, in: Annual International Conference on the Theory and Applications of Cryptographic Techniques, Springer, 2011, pp. 568–588.

21.

Li,

Yao,

Han,

Zhang and

Shen, User collusion avoidance CP-ABE with efficient attribute revocation for cloud storage, IEEE Systems Journal12(2) (2017), 1767–1777. doi:10.1109/JSYST.2017.2667679.

22.

Li,

Ma,

Li,

Liu,

Xiong and

Chen, Secure, efficient and revocable multi-authority access control system in cloud storage, Computers & Security59 (2016), 45–59. doi:10.1016/j.cose.2016.02.002.

23.

Li,

Xue,

Xue and

Hong, TMACS: A robust and verifiable threshold multi-authority access control system in public cloud storage, IEEE Transactions on parallel and distributed systems27(5) (2015), 1484–1496. doi:10.1109/TPDS.2015.2448095.

24.

Liang,

Cao,

Lin and

Shao, Attribute based proxy re-encryption with delegating capabilities, in: Proceedings of the 4th International Symposium on Information, Computer, and Communications Security, 2009, pp. 276–286. doi:10.1145/1533057.1533094.

25.

Liang,

Cao,

Lin and

Xing, Provably secure and efficient bounded ciphertext policy attribute based encryption, in: Proceedings of the 4th International Symposium on Information, Computer, and Communications Security, 2009, pp. 343–352. doi:10.1145/1533057.1533102.

26.

Liu and

Cao, On efficiently transferring the linear secret-sharing scheme matrix in ciphertext-policy attribute-based encryption, IACR Cryptol. ePrint Arch. 2010, 2010:374.

27.

Liu and

D.S.

Wong, Practical attribute-based encryption: Traitor tracing, revocation and large universe, The Computer Journal59(7) (2016), 983–1004. doi:10.1093/comjnl/bxv101.

28.

Luo,

Hu and

Chen, Ciphertext policy attribute-based proxy re-encryption, in: International Conference on Information and Communications Security, Springer, 2010, pp. 401–415. doi:10.1007/978-3-642-17650-0_28.

29.

Minio, MinIO: High performance, kubernetes native object storage, 2022, [Online accessed: 2022-12-10], https://min.io.

30.

Nishide,

Yoneyama and

Ohta, Attribute-based encryption with partially hidden encryptor-specified access structures, in: International Conference on Applied Cryptography and Network Security, Springer, 2008, pp. 111–129. doi:10.1007/978-3-540-68914-0_7.

31.

Ostrovsky,

Sahai and

Waters, Attribute-based encryption with non-monotonic access structures, in: Proceedings of the 14th ACM Conference on Computer and Communications Security, 2007, pp. 195–203. doi:10.1145/1315245.1315270.

32.

T.P.

Pedersen, A threshold cryptosystem without a trusted party, in: Workshop on the Theory and Application of Cryptographic Techniques, Springer, 1991, pp. 522–526.

33.

Qian,

Li,

Zhang and

Han, Privacy-preserving personal health record using multi-authority attribute-based encryption with revocation, International Journal of Information Security14 (2015), 487–497. doi:10.1007/s10207-014-0270-9.

34.

Qin,

Zhao,

Zheng and

Cui, (Dual) server-aided revocable attribute-based encryption with decryption key exposure resistance, Information Sciences490 (2019), 74–92. doi:10.1016/j.ins.2019.03.053.

35.

Sahai and

Waters, Fuzzy identity-based encryption, in: Annual International Conference on the Theory and Applications of Cryptographic Techniques, Springer, 2005, pp. 457–473.

36.

Shamir, How to share a secret, Communications of the ACM22(11) (1979), 612–613. doi:10.1145/359168.359176.

37.

Tomida,

Kawahara and

Nishimaki, Fast, compact, and expressive attribute-based encryption, Designs, Codes and Cryptography89(11) (2021), 2577–2626. doi:10.1007/s10623-021-00939-8.

38.

Waters, Ciphertext-policy attribute-based encryption: An expressive, efficient, and provably secure realization, in: International Workshop on Public Key Cryptography, Springer, 2011, pp. 53–70.

39.

Webb,

Syer,

Long,

Nicoll,

Winch,

Wilkinson,

Overdijk,

Dupuis and

Deleuze, Spring boot reference guide, Part IV. Spring Boot features24 (2013).

40.

White, Top 5 cloud computing predictions for 2020, 2020, Accessed: 2022-04-11.

41.

Xiong,

Huang,

Yang,

Wang and

Yu, Unbounded and efficient revocable attribute-based encryption with adaptive security for cloud-assisted Internet of things, IEEE Internet of Things Journal (2021).

42.

Yakubov,

Shbair,

Wallbom,

Sandaet al., A blockchain-based PKI management framework, in: The First IEEE/IFIP International Workshop on Managing and Managed, by Blockchain (Man2Block) Colocated with IEEE/IFIP NOMS 2018, Tapei, Tawain, April 23–27, 2018, 2018.

43.

Yang and

Jia, Expressive, efficient, and revocable data access control for multi-authority cloud storage, IEEE transactions on parallel and distributed systems25(7) (2013), 1735–1744. doi:10.1109/TPDS.2013.253.

44.

Yang,

Jia and

Ren, Attribute-based fine-grained access control with efficient revocation in cloud storage systems, in: Proceedings of the 8th ACM SIGSAC Symposium on Information, Computer and Communications Security, 2013, pp. 523–528. doi:10.1145/2484313.2484383.

45.

Yang,

Jia,

Ren,

Zhang and

Xie, DAC-MACS: Effective data access control for multiauthority cloud storage systems, IEEE Transactions on Information Forensics and Security8(11) (2013), 1790–1801. doi:10.1109/TIFS.2013.2279531.

46.

L.-Y.

Yeh,

P.-Y.

Chiang,

Y.-L.

Tsai and

J.-L.

Huang, Cloud-based fine-grained health information access control framework for LightweightIoT devices with dynamic auditing and attribute revocation, IEEE Transactions on Cloud Computing6(2) (2018), 532–544. doi:10.1109/TCC.2015.2485199.

47.

Yu,

Wang,

Ren and

Lou, Attribute based data sharing with attribute revocation, in: Proceedings of the 5th ACM Symposium on Information, Computer and Communications Security, 2010, pp. 261–270. doi:10.1145/1755688.1755720.

48.

Zhang,

R.H.

Deng,

Xu,

Sun,

Li and

Zheng, Attribute-based encryption for cloud computing access control: A survey, ACM Computing Surveys (CSUR)53(4) (2020), 1–41. doi:10.1145/3362031.

Robust,revocable,forward and backward adaptively secure attribute-based encryption with outsourced decryption 1

Abstract

Keywords

1. Introduction

2. Related work

3.1. Bilinear maps

Definition 1 (Independence [6]).

Definition 2 (GDHE assumption [6]).

3.2. Trusted third party free threshold secret sharing

4. System and security models

4.2. Definition of our construction

4.3. Threat model

4.4. Security requirements

4.4.1. Collusion resistance

Definition 3 (Collusion Resistance).

4.4.2. Robustness

Definition 4 ( ( t , n ) -Robustness).

4.4.3. Forward secrecy

Definition 6 (Backward Secrecy).

5. Our proposed scheme

5.1. System initialization

5.1.1. GlobalSetup

5.1.2. System initialization

5.2. Data sharing

5.3. User registration and key generation

5.4. Access revocation

5.4.1. Collaborative revocation request

5.4.2. Revocation enforcement

5.4.3. Secret decryption key updating

5.5. Outsourced pre-decryption and user decryption

5.5.1. Secret decryption key randomization

5.5.2. Outsourced pre-decryption

5.5.3. User decryption

6. Security results

Theorem 1 (Correctness).

9.1. Experimental setup

2 Our implementation is not multi-threaded, however, we stress that most operations (e.g., encryption, decryption, and revocation) are embarrassingly parallelizable.

References

Definition 4 ( $(t, n)$ -Robustness).

²
Our implementation is not multi-threaded, however, we stress that most operations (e.g., encryption, decryption, and revocation) are embarrassingly parallelizable.