Anis Bkakria
email: anis.bkakria@irt-systemx.fr

Robust, Revocable, Forward and Backward Adaptively Secure Attribute-Based Encryption with Outsourced Decryption ⋆

Keywords: Attribute-Based Encryption, Threshold Cryptography, Adaptive Security

Robust, revocable, forward and backward adaptively

secure attribute-based encryption with outsourced decryption

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 [START_REF] White | Top 5 cloud computing predictions for[END_REF], 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 cryptographybased system models and techniques have been proposed to enable efficient and secure cloud access control. Among the previous, ABE [START_REF] Sahai | Fuzzy identity-based encryption[END_REF]. The latter allows to ensure simultaneously confidentiality preservation and fine-grained access control. ABE has succeeded in attracting considerable research efforts [START_REF] Kumar | Attribute based encryption in cloud computing: A survey, gap analysis, and future directions[END_REF][START_REF] Ruqayah R Al-Dahhan | Survey on revocation in ciphertext-policy attribute-based encryption[END_REF][START_REF] Zhang | Attribute-based encryption for cloud computing access control: A survey[END_REF] 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 [START_REF] Bkakria | Robust and provably secure attribute-based encryption supporting access revocation and outsourced decryption[END_REF], 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 [START_REF] Bkakria | Robust and provably secure attribute-based encryption supporting access revocation and outsourced decryption[END_REF] 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 [START_REF] Bkakria | Robust and provably secure attribute-based encryption supporting access revocation and outsourced decryption[END_REF] 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.

Related Work

Revocable ABE. Several researchers have been devoted to build ABE constructions allowing access revocation. Liang et al. [START_REF] Liang | Attribute based proxy re-encryption with delegating capabilities[END_REF] introduce a provably selectively secure CP-ABE construction that enables access revocation through proxy re-encryption. Using the latter technique, Luo et al. [START_REF] Luo | Ciphertext policy attribute-based proxy re-encryption[END_REF] designed a selectively secure and small attribute universe based CP-ABE supporting policy updating. Always relying on proxy re-encryption, Yu et al. [START_REF] Yu | Attribute based data sharing with attribute revocation[END_REF] 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. [START_REF] Lewko | Revocation systems with very small private keys[END_REF] propose a selectively secure in the standard model ABE construction that enables attribute revocation. Hur and Noh [START_REF] Hur | Attribute-based access control with efficient revocation in data outsourcing systems[END_REF] 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. [START_REF] Yang | Attribute-based fine-grained access control with efficient revocation in cloud storage systems[END_REF] 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 [START_REF] Yang | Dac-macs: Effective data access control for multiauthority cloud storage systems[END_REF], 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. [START_REF] Cui | Server-aided revocable attribute-based encryption[END_REF] propose a CP-ABE scheme that enables attribute revocation where most of the related computations are delegated to an untrusted server. Similarly to [START_REF] Hur | Attribute-based access control with efficient revocation in data outsourcing systems[END_REF], the authors of [START_REF] Cui | Server-aided revocable attribute-based encryption[END_REF] claim that their construction is both backward and forward secure without providing any formal proofs. Liu et al. [START_REF] Liu | Practical attribute-based encryption: traitor tracing, revocation and large universe[END_REF] 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. [START_REF] Li | Secure, efficient and revocable multiauthority access control system in cloud storage[END_REF] 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. [START_REF] Qin | dual) server-aided revocable attribute-based encryption with decryption key exposure resistance[END_REF] 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. [START_REF] Xiong | Unbounded and efficient revocable attributebased encryption with adaptive security for cloud-assisted internet of things[END_REF] propose an adaptively secure CP-ABE scheme allowing attribute revocation. It uses monotonic span program [START_REF] Karchmer | On span programs[END_REF] 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. [START_REF] Yang | Dac-macs: Effective data access control for multiauthority cloud storage systems[END_REF] propose a construction that outsource most part of the computations to the cloud server. The same idea was later used in [START_REF] Cui | Server-aided revocable attribute-based encryption[END_REF][START_REF] Yeh | Cloud-based fine-grained health information access control framework for lightweightiot devices with dynamic auditing andattribute revocation[END_REF][START_REF] Qin | dual) server-aided revocable attribute-based encryption with decryption key exposure resistance[END_REF][START_REF] Xiong | Unbounded and efficient revocable attributebased encryption with adaptive security for cloud-assisted internet of things[END_REF]. 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. [START_REF] Li | Tmacs: A robust and verifiable threshold multi-authority access control system in public cloud storage[END_REF] 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.

Approaches

Robustness Revocation Security FS BS Outsourced Model Decryption [START_REF] Sahai | Fuzzy identity-based encryption[END_REF][START_REF] Ostrovsky | Attribute-based encryption with non-monotonic access structures[END_REF][START_REF] Goyal | Bounded ciphertext policy attribute based encryption[END_REF][START_REF] Nishide | Attribute-based encryption with partially hidden encryptorspecified access structures[END_REF][START_REF] Liang | Provably secure and efficient bounded ciphertext policy attribute based encryption[END_REF][START_REF] Emura | A ciphertext-policy attribute-based encryption scheme with constant ciphertext length[END_REF][START_REF] Waters | Ciphertext-policy attribute-based encryption: An expressive, efficient, and provably secure realization[END_REF][START_REF] Han | Privacy-preserving decentralized key-policy attribute-based encryption[END_REF][START_REF] Han | Ppdcp-abe: Privacy-preserving decentralized ciphertext-policy attribute-based encryption[END_REF] ✗ ✗ Selective ✗ ✗ ✗ [START_REF] Liang | Attribute based proxy re-encryption with delegating capabilities[END_REF][START_REF] Luo | Ciphertext policy attribute-based proxy re-encryption[END_REF][START_REF] Yu | Attribute based data sharing with attribute revocation[END_REF][START_REF] Lewko | Revocation systems with very small private keys[END_REF][START_REF] Hur | Attribute-based access control with efficient revocation in data outsourcing systems[END_REF][START_REF] Yang | Attribute-based fine-grained access control with efficient revocation in cloud storage systems[END_REF][START_REF] Li | User collusion avoidance cp-abe with efficient attribute revocation for cloud storage[END_REF]]

✗ ✓ Selective ✓ ✗ ✗ [44,7,45] ✗ ✓ Selective ✓ ✗ ✓ [23] ✓ ✗ Selective ✗ ✗ ✗ [4,20,37] ✗ ✗ Fully ✗ ✗ ✗ [27,22] ✗ ✓ Fully ✓ ✗ ✗ [34,41] ✗ ✓ Fully ✓ ✗ ✓ [5] ✓ ✓ Fully ✓ ✗ ✓ This work ✓ ✓ Fully ✓ ✓ ✓
Table 1: Feature comparaison of (most) related CP-ABE constructions. We use FS and BS to denote respectively the forward and backward secrecy properties.

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 [START_REF] Pryds | A threshold cryptosystem without a trusted party[END_REF].

Bilinear Maps

Let G 1 , G 2 , and G T be three multiplicative cyclic groups of prime order p. Let e : G 1 × G 2 → G T be a bilinear map having the following properties:

-Symmetric bilinearity:

∀g 1 ∈ G 1 , ∀g 2 ∈ G 2 and ∀a, b ∈ Z p , we have e(g a 1 , g b 2 ) = e(g b 1 , g a 2 ) = e(g 1 , g 2 ) a•b . -Non-degeneracy: e(g 1 , g 2 ) ̸ = 1.
-The group operations in G 1 , G 2 and e(•, •) are efficiently computable.

The security of our construction holds as long as G 1 ̸ = 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(•, •)) as a bilinear environment.

We prove the security of the proposed construction under a non-interactibe Generalized Diffie-Hellman Exponent assumption (GDHE) which has been proved to be a hard problem in [START_REF] Boyen | The uber-assumption family[END_REF]. 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 (x1,,xc) (resp. g

f (x1,,xc) 2 ) from a random element of G 1 (resp. G 2 ).
Definition 1 (independence [START_REF] Boyen | The uber-assumption family[END_REF]). Let p be some large prime, r, s, t, and c be positive integers.

Let R = ⟨r 1 , • • • , r r ⟩ ∈ F p [X 1 , • • • , X c ] r , S = ⟨s 1 , • • • , s s ⟩ ∈ F p [X 1 , • • • , X c ] s , and T = ⟨t 1 , • • • , t t ⟩ ∈ F p [X 1 , • • • , X c ] t
be three tuples of multivariate polynomials over the field F p . We say that polynomial f

∈ F p [X 1 , • • • , X c ] is dependant on the triple ⟨R, S, T ⟩ if there exists r • s + t constants {ϑ (a) i,j } i=r,j=s i,j=1 , {ϑ (b) k } t k=1 such that f = i,j ϑ (a) i,j • r i • s j + k ϑ (b) k • t k
We say that f is independent of ⟨R, S, T ⟩ if f is not dependent on ⟨R, S, T ⟩.

Definition 2 (GDHE assumption [START_REF] Boyen | The uber-assumption family[END_REF]). Let (G 1 , G 2 , G T , p, e(•, •)) be a bilinear environment and r, s, t, and c be positive integers.

Let R = ⟨r 1 , • • • , r r ⟩ ∈ F p [X 1 , • • • , X c ] r , S = ⟨s 1 , • • • , s s ⟩ ∈ F p [X 1 , • • • , X c ] s , and T = ⟨t 1 , • • • , t r ⟩ ∈ F p [X 1 , • • • , X c
] t be three tuples of multivariate polynomials over the field F p . The GDHE assumption states that, given the vector ,xc) or U is random if f is independent of (R, S, T ).

H(x 1 , • • • , x c ) = (g R(x1,••• ,xc) 1 , g S(x1,••• ,xc) 2 , e(g 1 , g 2 ) T (x1,••• ,xc) ) ∈ G r 1 × G s 2 × G t T it is hard to decide whether U = e(g 1 , g 2 ) f (x1

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 [START_REF] Bertilsson | A construction of practical secret sharing schemes using linear block codes[END_REF][START_REF] Ito | Secret sharing scheme realizing general access structure[END_REF][START_REF] Pryds | A threshold cryptosystem without a trusted party[END_REF][START_REF] Shamir | How to share a secret[END_REF]. In this work, we use the trusted third party free threshold secret sharing construction proposed in [START_REF] Pryds | A threshold cryptosystem without a trusted party[END_REF], which we briefly describe as following.

Consider a system involving a set P = {P 1 , P 2 , • • • , P n } of n participants and a threshold t (t ≤ n). Let us suppose that to each participant P i ∈ P is associated a unique scalar z i ∈ Z p (∀P i , ∀P j ∈ P : P i ̸ = P j ⇔ z i ̸ = z j ) representing the public identifier of the participant in the system. First, each participant P i selects a random scalar s i ∈ 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 = n i=1 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 ̸ = 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 = n j=1 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:

t k=1   S ′ k • t j=1,j̸ =k -z j z k -z j   = t k=1   S ′ k • t j=1,j̸ =k z j z j -z k   = n i=1 S i = S

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. The system we consider to build our scheme 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., [START_REF] Shohel | Turning trust around: smart contract-assisted public key infrastructure[END_REF] 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.

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, Σ) → 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() → (SK, P K) is a probabilistic algorithm that returns a secret key share SK and a master public key share P K. -CAKeyGen({P K i }) → M P K is a probabilistic algorithm that takes as input the master public key shares {P K i } of the involved AAs and outputs a master public key M P K. -Encrypt(M, M, M P K) → χ is a probabilistic algorithm that takes a message M and an access structure M and outputs an encrypted data item bundle χ.

-DecKeyGen(M P K, AAs) → K is a probabilistic algorithm that takes as input the master public key M P K and the set of registered attribute authorities AAs and outputs a secret decryption key K. -Revoke(u, {σ i }) → (M P K, 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 M P K and an updated secret key SK csp for the CSP. -PartialDecrypt(SK csp ,K, ind) → χ is a deterministic algorithm that takes as input the secret key SK csp of the CSP, a randomized decryption key K, and the index ind of the data item to decrypt χ and returns a partially decrypted data item χ. -Decrypt(K, χ)→ M is a deterministic algorithm that takes as input a DU's secret decryption key K and a partially decrypted data item χ and outputs a plaintext data item M .

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.

Security Requirements

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

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 C A .

1. Setup: C executes the algorithms GlobalSetup, AAKeyGen, and CAKeyGen. It then shares the public parameters env and the master public key M P K with A. 2. 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 ∀i ∈ [1, n], Σ i does not satisfy M * . Then it sends them to C. The latter chooses a random β ∈ {0, 1}, encrypts M β under M * to get the challenge ciphertext C * , and sends C * to A. 4. 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. 5. Guess: A outputs its guess β ′ of β.

We define A's advantage by Adv

Exp C A (λ) = |P r[β = β ′ ] -1/2|. Our construction is said to be collusion resistant if Adv Exp C A (λ) is negligible.
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 R A . We omit the first four steps of the game since they are the same as defined in Exp C A (Definition 3). 5. 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 ∈ [1, t -1]. 6. Guess: A outputs its guess β ′ of β.

We define A's advantage by Adv

Exp R A (λ) = |P r[β = β ′ ] -1/2|. Our construction is said to be (t,n)-Robust if Adv Exp R A (λ) is negligible.
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.

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 B-F

A

. The first step of this game is the same as defined in Exp C A (Definition 3) and so will be omitted. 2. Query -Pre revocation: this phase is carried out according to the following two steps. We define

Adv Exp B-F A,β 1 (λ) = |P r[β 1 = β ′ 1 ] -1/2| and Adv Exp B-F A,β 2 (λ) = |P r[β 2 = β ′ 2 ] -1/2|. Our construction is said to be forward secure if Adv Exp B-F A,β 1 (λ) and Adv Exp B-F A,β 2 (λ) are negligible.
Remark 1. 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 revokable ABE (e.g. [START_REF] Ge | Revocable attribute-based encryption with data integrity in clouds[END_REF][START_REF] Huiling Qian | Privacy-preserving personal health record using multiauthority attribute-based encryption with revocation[END_REF][START_REF] Yang | Expressive, efficient, and revocable data access control for multi-authority cloud storage[END_REF]).

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 B A . The first three steps of this game is the same as defined in Exp C A (Definition 3) and so will be omitted. 4. 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. 5. 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 * . 6. Guess: A outputs its guess β ′ of β.

We define A's advantage by Adv

Exp B A (λ) = |P r[β = β ′ ] -1/2|.
Our construction is said to be backward secure if Adv Exp B A (λ) is negligible.

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.

System Initialization

The initialization of the system is performed as described in the following. •)) be a bilinear environment, g 1 and g 2 be two random elements of G 1 and G 2 respectively. Let H : G T → {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 SM K and a verification key V M K and sends the pubic

GlobalSetup Let (G 1 , G 2 , G T , p, e(•,
parameters env = (G 1 , G 2 , G T , p, e(•, •), g 1 , g 2 , H, Ξ, V M K) to B for storage.

System Initialization

The system is initialized using the following steps.

-AA registration: Each attribute authority AA i uses Ξ to generate a private key SK AAi and a public key PK AAi and sends a registration request to DCA. If AA i is a legal authority, the DCA generates a random global identity aid ∈ Z p , issues a signed certificate Cert aid , and submits the couple (aid, Cert 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 ∈ 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 = ∅. 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 , • • • , 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 M P K = (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: 1. Select four random scalars a i , α i , α i , δ i ∈ Z p as a sub-secrets and generate four random polynomials

f i (x), h i (x), f i (x), and h i (x) of degree t -1 such that f i (0) = a i , h i (0) = α i , f i (0) = δ i , and h i (0) = α i . Then for all j ∈ {1, 2, • • • , n}\{i}, calculate s {a} i,j = f i (aid j ), s {α} i,j = h i (aid j ), s {δ} i,j = f i (aid j ),
sk {k} i = n j=1 s {k} j,i , k ∈ {a, α, δ, α} pka i = g sk {a} i 1 , pka i = g sk {a} i 2 , pke i = e(g 1 , g 2 ) sk {α} i , pkr i = g sk {α} i 2
, and pkt i,0 = g sk {δ} i 2 . Finally, each A i sends its master public key share P K i = {pka i , pka i , pke i , pkr i , pkt i,0 } to B for storage. The secret key share is set as

SK i = {sk {k} i } k∈{a,α,δ,α} . 3.
For each attribute σ ∈ Σ, and for each time slot π, choose a random scalar

θ σ,i,π ∈ Z p , compute Θ σ,i,π = g θσ,i,π 1 and Θ σ,i,π = g θσ,i,π 2
and send them to the B for storage. 4. For each attribute σ ∈ Σ, 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 {P K 1 , • • • , P K 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.

pka = i∈I (pka i ) j∈I,j̸ =i aid i aid j -aid i = g a 1 pka = i∈I (pka i ) j∈I,j̸ =i aid i aid j -aid i = g a 2 pke = i∈I (pke i ) j∈I,j̸ =i aid i aid j -aid i = e(g 1 , g 2 ) α pkr = i∈I (pkr i ) j∈I,j̸ =i
Θ σ,π = n i=1 Θ σ,i,π , Θ σ,π = n i=1 Θ σ,i,π
Finally, DCA sends the master public key M P K = {env, pka, pka, pke, pkr, pkt 0 , Θ σ,πp , Θ σ,πp , π p = 0} σ∈Σ 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, pka, and Θ σ,π 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 M SK = {a, α, α, δ} is implicitly shared among the different AAs. However, it does not need to be obtained by any entity in the system.

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 Σ * ⊆ Σ 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 ∈ Z p and uses the component pke of the master public key M P K to generate the symmetric key κ as:

κ = H(pke s ) = H (e(g 1 , g 2 ) α•s )
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 [START_REF] Liu | On efficiently transferring the linear secret-sharing scheme matrix in ciphertext-policy attribute-based encryption[END_REF] where M is an l × k LSSS matrix and ρ(x) maps each row of M to an attribute σ ∈ Σ. 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

⃗ v = {s, v 2 , • • • , v k } ∈ Z k p . For each row vector M i of M, λ i = M i • ⃗ v ⊤ is
calculated and a random scalar r i ∈ Z p is chosen. The ciphertext encrypting the symmetric encryption key κ is computed as following:

C = {C ′ = g s 2 , C i = pka λi • Θ -ri ρ(i),πc , D i = g ri 2 } i∈[1,l]
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 M P K.

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 Σ ui 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 recieved 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 Σ (j) ui = Σ ui \{σ|u i ∈ U r,σ } to u i where {σ|u i ∈ U r,σ } is the set of attributes that has been revoked from u i . Then, A j chooses a random scalar b j ∈ Z p and uses the M P K to generate a secret decryption key share for u i as following:

K ui,j = K j = g sk {α} j 1 • pka bj , L j = g bj 1 , K σ,j = Θ bj σ,πc , K π,j = g bj •sk {δ} j 1 σ∈Σ (j) u i
We note here that the queried attribute authorities may assign different attributes Σ (j)

ui to u i . If it is the case, the computed decryption key will involve only the set of attributes

Σ ui = ∩ t j=0 Σ (j)
ui 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.

K = t i=1 K t j=1,j̸ =i aid j aid j -aid i i = g α 1 • g a• t i=1 (bi• j=1,j̸ =i aid j aid j -aid i ) 1 L = t i=1 L t j=1,j̸ =i aid j aid j -aid i i = g t i=1 (bi• j=1,j̸ =i aid j aid j -aid i ) 1 K σ = t i=1 K t j=1,j̸ =i aid j aid j -aid i σ,i = Θ t i=1 (bi• j=1,j̸ =i aid j aid j -aid i ) σ,πc , σ ∈ Σ ui K π = t i=1 K π,j = g δ• t i=1 (bi• j=1,j̸ =i aid j aid j -aid i ) 1
For sake of simplicity, let us introduce the parameter d:

d = t i=1   b i • j=1,j̸ =i aid j aid j -aid i  
Therefore, the user's secret key can be simplified as following:

K u = K = g α 1 • g a•d 1 , L = g d 1 , K σ = Θ d σ,πc , K π = g δ•d 1 , π u = π p , π r = π p σ∈Σu i
where π u is used to denote the timestep on which K u is issued, and π r is used for decryption key updates.

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.

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 ∈ Σ to a specific set of data users U r . A i generates a random scalar t ∈ Z p and computes

R i = {R i = g t•sk {α} i 2 , R v = pkr t , R b = g t 2 , Σ r , U r }
Then, A i signs R i using Cert aidi , 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 ∈ [1, n]\{i} authenticates then processes the access revocation request. If it is legitimate, it computes the revocation request share as following

R j = {R j = R sk {α} j b , R v = pkr t , Σ r , U r }
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:

∀σ ∈ Σ r : U r,σ = U r,σ ∪ U r
Finally, the AAs collaboratively generate a new pkt π (π = π p + 1) using the protocol defined in the AA key generation (Section 5.1).

Revocation Enforcement Once more than t -1 shares for a revocation request are committed to B, the CSP computes

t i=1 R i t j=1,j̸ =i aid j aid j -aid i (1)
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 α. 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 ∈ Z p and updates the master public key M P K as

∀σ ∈ Σ r : Θ σ,πc+1 ← Θ z σ,πc , Θ σ,πc+1 ← Θ z σ,πc , and
π p ← π p + 1
and updates its secret key SK csp as

SK csp ← SK csp ∪ {µ πp = z}
Finally, CSP sends the updated MPK for updation in B.

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.

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.

Secret Decryption Key Randomization

The data user u starts by randomizing its secret decryption key as follows. It picks a random scalar x ∈ Z p and computes:

K u = {K ′ = K x , L ′ = L x , K ′ σ = K x σ , K ′ π = K x π , π u , π r }
Then, u sends K u and the index ind of the data item to be pre-decrypted to CSP.

Outsourced Pre-decryption After receiving (K u , ind), CSP starts by checking the correctness of the the timestep π u by verifying the following equality:

e(L ′ , pkt πu ) = e(K ′ π , g 2 ) (2)
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 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 K u , the master public key M P K, and the index ind of the data item to encrypt. It outputs a pre-decrypted symmetric key κ 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.

17 κ = e(K ′ ,C ′ ) i∈I (e(L ′ ,C i )•e(K ′ i ,D i )) w i ) 18 return (κ, Eκ(M ))
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, • • • , l}, and M i is used to denote the ith row of the matrix M. Finally, let {w i } i∈I be constants such that

i∈I w i • M i = (1, 0, • • • , 0).
User Decryption Once the user retrieves the pre-decrypted symmetric key κ and the ciphertext E κ (M ), he/she recovers the symmetric key κ by performing the following operations:

κ = H κ 1/x
which can be used to decrypt the data item.

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 ⊂ Σ 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 = ∅) and the master public key M P K = {env, pka, pka, pke, pkr, Θ σ , Θ σ , π p = 0} σ∈Σ . Let us denote by Θ σ,π (resp. Θ σ,π ) the value of Θ σ (resp. Θ σ ) 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 ∈ Σ u from u, i ∈ [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 ∈ Zp to SK csp and updates the M P K as Θ σ ← Θ . According to Section 5.3, at any timestep π * ∈ [0, m], an updated secret decryption key, i.e., a secret decryption key issued at π * will have the form

K u = K = g α 1 • g a•d 1 , L = g d 1 , K σ = Θ d• i∈Iσ µi σ,0 , π r = π * σ∈Σu i
Now, according to Algorithm 1 (lines 7 to 16), an updated encrypted data item is a data item where π c = π p and

C = {C ′ = g s 2 , C i = pka λi • Θ -ri• i∈I ρ(i) ,i>max(πu ,πc ) µi ρ(i),πc , D i = g ri 2 } i∈[1,l]
Now, according to the outsourced pre-decryption process of our construction, the randomized secret decryption key is

K u = {K ′ = K x , L ′ = L x , K ′ σ = K x σ , π u }
As we suppose that Σ u \Σ r satisfies the access structure M used to encrypt C, then, we have

∃I ⊆ {i|ρ(i) ∈ Σ u \Σ r }, ∃ w i : i∈I w i • M i = (1, 0, • • • , 0)
where M i denotes the ith row of the matrix M. Then, according to Algorithm 1 (line 17), we have

κ = e(K ′ , C ′ ) i∈I (e(L ′ , C i ) • e(K ′ i , D i )) wi ) = e(g α•x 1 • g a•d•x 1 , g s 2 ) i∈I e(g d•x 1 , g a•λi 2 • Θ -ri• j∈I ρ(j) ,j>max(πu ,πc ) µi ρ(i),πc ) • e(Θ d•x• j∈Iσ µi ρ(i),0 , g ri 2 )
wi Then, if π u ≤ π c , then we have:

κ = e(g 1 , g 2 ) α•s•x .
Then by applying the user decryption operation we get

H κ 1/x = H (e(g 1 , g 2 ) α•s ) = κ
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 C A (Definition 3). In the following, we show that the advantage of the adversary A to win Exp C

A is negligible under the GDHE assumption (Definition 2).

Let us denote by Ω G1 , Ω G2 , and Ω Gt the set of elements of G 1 , G 2 , and G t respectively that are to be known by A during Exp C

A . According to the latter, first the challenger performs GlobalSetup, AAKeyGen, and CAKeyGen and sends env = (G 1 , G 2 , G T , p, e(•, •), g 1 , g 2 , H, Ξ, CM K, V M K) and M P K = {env, pka, pka, pke, pkr, Θ σ,πp , Θ σ,πp , π p = 0} σ∈Σ to A. Hence, at the end of the setup phase, we have:

Ω G1 = {pka, Θ σ,πp } σ∈Σ Ω G2 = {pka, pkr, Θ σ,πp } σ∈Σ Ω Gt = {pke}
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 ski,j 1

•pka bi,j , g bi,j 1 , Θ bi,j σ,πp } σ∈Σj ,i∈Aj to Ω G1 and nothing to Ω G2 and Ω Gt , 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 s 2 , pka λi • Θ ri ρ(i),πp , g ri 2 } i∈ [1,l] to Ω G2 and nothing to Ω G1 and Ω Gt . Then, similarly to the first phase, the second phase of the query step adds {g ski,j 1

• pka bi,j , g bi,j 1 , Θ bi,j σ,πp } σ∈Σj to Ω G1 and nothing to Ω G2 and Ω Gt . 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

Ω G1 ={pka, Θ σ,πp , g ski,j 1 • pka bi,j , g bi,j 1 , Θ bi,j σ,πp , g bi,j •δ 1 } σ∈Σj ,j∈[1,m],i∈Ai Ω G2 ={pka, pkr, pkt 0 , Θ σ,πp , g s 2 , pka λi • Θ ri ρ(i),πp , g ri 2 } i∈[1,l] Ω Gt ={pke}
Hence, to prove the theorem we need to show that the advantage of A to decide whether the element U ∈ 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 = α • s is independent of (R, S, T ) where

R = {a, n i=1 θ σ,i,πp , sk i,j + b i,j , b i,j • n i=1 θ σ,i,πp } σ∈Σ,j∈[1,m],i∈Ai S = {a, α, n i=1 θ σ,i,πp , s, a • λ j + r j • n i=1 θ σ,i,πp , r j } i∈[1,n],j∈[1,l] T = {α}
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 ϑ k so that the following equation holds:

α • s = i,j ϑ (a) i,j • r i • s j + k ϑ (b) k • t k (3)
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 = ∅. Similarly we can exclude the elements a, α, n i=1 θ σ,i , and r j from S to get S = {s}. So, let ϑ (1) , ϑ (2) be constant such that:

α • s = ϑ (1) • s + ϑ (2) • α (4)
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) • 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) ̸ = 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 R A is negligible under the GDHE assumption. Similarly, we use Ω G1 , Ω G2 , and Ω Gt to denote the set of elements of G 1 , G 2 , and G t respectively that are to be known by A during Exp C

A . As the first four steps of the Exp R A security game (Definition 4) are the same in the security game Exp C A (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 R A , we have

Ω G1 ={pka, Θ σ , g ski,j 1
• pka bi,j , g bi,j

1 , Θ bi,j σ , g bi,j •δ 1 } σ∈Σj ,j∈[1,m],i∈Ai Ω G2 ={pka, pkr, pkt 0 , Θ σ , g s 2 , pka λi • Θ ri ρ(i) , g ri 2 } i∈[1,l] Ω Gt ={pke}
In the step 5 of Exp R A , 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 ∈ AA c , the adversary A can compute G SK z A i
for all z ∈ Z, all G i ∈ Ω Gi , and all A ∈ AA c . Therefore, to prove the theorem, we need to show that the advantage of A to decide whether the element U ∈ 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 = α • s is independent of (R, S, T ) where

R = {a • SK z A , SK z A • n i=1 θ σ,i , (sk i,j + b i,j ) • SK z A , SK z A • b i,j • n i=1 θ σ,i } σ∈Σ,j∈[1,m],i∈Ai,z∈Z,A∈AAc S = {a • SK z A , α • SK z A , SK z A • n i=1 θ σ,i , s•, SK z A • (a • λ j + r j • n i=1 θ σ,i ), SK z A • r j } i∈[1,n],j∈[1,l],z∈Z,A∈AAc T = {α • SK z A } z∈Z,A∈AAc
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 ϑ k so that the following equation holds:

α • s = i,j ϑ (a) i,j • r i • s j + k ϑ (b) k • t k (5)
By, following the same reasoning as in the proof of Theorem 2, since the probability of getting f out of the randomly chosen values α, a, θ σ,i , δ, and b i,j is negligible, we can exclude all elements containing α, a, θ σ,i , δ, and b i,j from the sets R, S, and T . Then we get

R = ∅, S = {s • SK z A } z∈Z,A∈AAc and T = {α • SK z A } z∈Z,A∈AAc So, let ϑ (1)
z,A , ϑ

z,A be constant such that:

α • s = z∈Z,A∈AAc ϑ (1)
z,A • s • SK z A + z∈Z,A∈AAc ϑ (2)
z,A • α • SK z A (6)
To prove that f is independent of (R, S, T ), we need to show that no ϑ

z,A and ϑ

z,A for all z ∈ Z and all A ∈ 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

(i) z∈Z,A∈AAc ϑ (2)
z,A • α • SK z A = 0 (ii) α • s = z∈Z,A∈AAc ϑ (1) z,A • s • SK z A
First, let us focus on Equation (i). If the latter holds, then this means that one of the following condition also holds:

(i.1) α is a root of non-zero polynomial of degree one (i.2) SK A is a root of non-zero polynomial of degree z (i.3) ∀z ∈ Z, A ∈ AA c : ϑ (2)
z,A = 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

α = z∈Z,A∈AAc ϑ (1)
z,A • SK z A n i=1 f i (0) = z∈Z,A∈AAc ϑ (1)
z,A • n i=1 f i (id A ) z (7)
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:

(ii.1) ∀z > 1, z∈Z,A∈AAc ϑ (1) z,A • ( n i=1 f i (id A )) z = 0 (ii.2) n i=1 f i (0) = A∈AAc ϑ (1) z,A • n i=1 f i (id A )
From equation (ii.1), since f i is randomly chosen from Z t-1 p , then we can deduce (II) that, with overwhelming probability (≃ z/p t-1 ), for all z > 1, all A ∈ AA c , ϑ

z,A = 0. Now let us focus on Equation (ii.2). Since AA c is composed of t -1 attribute authorities, let us denote by {A

(c) 1 , • • • , A (c)
t } the set of attribute authorities in AA c . Then using the previous notation, we can rewrite Equation (ii.2) as

n i=1 f i (0) = n i=1 t-1 j=1 ϑ (1) 1,t • f i (id A (c) j ) (8)
As ∀i ∈ [1, n], f i is randomly chosen from Z t-1 p , then we have

∀i ∈ [1, n], f i (0) = t-1 j=1 ϑ (1) 1,t • f i (id A (c) j ) (9)
Now, by considering the fact that for all i ∈ [1, n], f i is a polynomial of degree t -1, then if Equation 9holds, then one can use it to break the security of Shamir's secret sharing scheme [START_REF] Shamir | How to share a secret[END_REF] which has been proven to be unconditionally secure. Consequently, no ϑ

1,t 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 B-F A,β 1 (λ) and Adv Exp B-F A,β 2 (λ) are negligible under the GDHE assumption. Similarly to previous proofs, let us denote by Ω G1 , Ω G2 , and Ω Gt the set of elements of G 1 , G 2 , and G t respectively that are to be known by A during Exp B-F A . At the end of the step (2)(a), the secret decryption key issued by C and sent to A adds

{g α 1 • g a•d 1 , g d 1 , Θ d σ,πp , g d•δ 1 } σ∈Σ *
to Ω G1 and nothing to Ω G2 and Ω Gt . The step (2)(b) of Exp B-F A adds nothing to Ω G1 , Ω G2 and Ω Gt . Furthermore, during the step (3) of Exp B-F A , the access revocation operation adds the random scalar µ ∈ Z p to the secret key SK CSP of the CSP and updates the master public key MPK by setting Θ σ,πp+1 ← Θ µ σ,πp and Θ σ,πp+1 ← Θ µ σ,πp for all σ ∈ Σ ′ . Hence, the revocation step adds Θ µ σ,πp to G 1 , Θ µ σ,π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

{g s 2 , pka λi • Θ µ•ri ρ(i),πp , g ri 2 , g s ′ 2 , pka λ ′ i • Θ µ•r ′ i ρ ′ (i),πp , g r ′ i 2 , Θ µ σ,πp , pkr, pkt j } ρ(i)∈Σ * ,ρ ′ (i)∈Σ * \Σ ′ ,σ∈Σ ′ ,j∈[0,πp]
to Ω G2 and nothing to Ω G1 and Ω Gt . Hence, at the end of step (5), we have

Ω G1 = {g α 1 • g a•d 1 , g d 1 , Θ d σ,πp , Θ µ σ,πp , g d•δ 1 } σ * ∈Σ * ,σ∈Σ ′ Ω G2 = {g s 2 , pka λi • Θ µ•ri ρ(i),πp , g ri 2 , g s ′ 2 , pka λ ′ i • Θ µ•r ′ i ρ ′ (i),πp , g r ′ i 2 , Θ µ σ,πp , pkr, pkt j } ρ(i)∈Σ * ,ρ ′ (i)∈Σ * \Σ ′ ,σ∈Σ ′ ,j∈[0,πp] Ω Gt = {pke}
Therefore, to prove forward secrecy, we need to show that the advantage of A to decide whether U = e(g 1 , g 2 ) α•s and U ′ = e(g 1 , g 2 ) α•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 = α • s and f ′ = α • s ′ are independent of (R,S,T) where

R = α + a • d, d, d • n i=1 θ σ,i,πp , µ • n i=1 θ σ,i,πp , d • δ σ∈Σ * ,j∈[1,m],i∈Ai S = s, a • λ i , µ • r i • n i=1 θ σ,i,πp , r i , s ′ , a • λ ′ i , µ • r ′ i • n i=1 θ σ,i,πp , r ′ i ρ(i)∈Σ * ,ρ ′ (i)∈Σ * \Σ ′ ,σ∈Σ ′ T = {α}
Then to show that f and f ′ are independent of (R,S,T), we must show that there exists no constants ϑ

(a) i,j , ϑ (b) k , ϑ ′(a) i,j , ϑ ′(b) k such that α • s = i,j ϑ (a) i,j • r i • s j + k ϑ (b) k • t k and (10)
α • s ′ = i,j ϑ ′(a) i,j • r i • s j + k ϑ ′(b) k • t k (11)
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 α

• s = ϑ (1) (α + a • d) • s + ρ(i)∈Σ * ϑ (2) i (α + a • d) • (a • λ i ) + ϑ (3) • α (12)
Let us consider Equation 12 as a polynomial in α and regroup the monomials according to their degree in α to get

(i) α • s = ϑ (1) • α • s + a • α ρ(i)∈Σ * ϑ (2)
i • λ i + ϑ (3) • α (ii) ϑ (1) • a • d • s + a 2 • d ρ(i)∈Σ * ϑ (2) i • λ 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:

(i.1) s = ϑ (1) • s + ϑ (3) (i.2) ρ(i)∈Σ * ϑ (2)
i • λ 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) • d • 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 10does not hold. We can follow the same previous steps to prove that Equation 11does 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 B A (λ) are negligible under the GDHE assumption. Similarly, we use Ω G1 , Ω G2 , and Ω Gt to denote the set of elements of G 1 , G 2 , and G t respectively that are to be known by A during Exp B A . Hence, after the third step of the game we have:

Ω G1 ={pka, Θ σ,0 , g α 1 • pka dj , g dj 1 , Θ dj σ,0 , g dj •δ 1 } σ∈Σj ,j∈[1,m],i∈Ai Ω G2 ={pka, pkr, pkt 0 , Θ σ,0 , g s 2 , pka λi • Θ ri ρ(i),0 , g ri 2 } i∈[1,l] Ω Gt ={pke}
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 } σ∈Σ and {Θ σ,1 = Θ µ σ,0 } σ∈Σ to Ω G1 and Ω G2 respectively.

In step five of the considered security game, A performs a secret key generation query. The latter adds

{Θ d * σ * ,1 , g α 1 • pka d * , g d * 1
} to Ω G1 . In order to establish the theorem, it is necessary to demonstrate that the advantage of A in determining whether the element U ∈ 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 = α • s from the variables (R, S, T ), where

R = α + a • d j , d j , d j • n i=1 θ σ,i,0 , n i=1 θ σ,i,0 , d j • δ, d * • n i=1 θ σ * ,i,1 , α + a • d * , d * σ∈Σj ,σ * ∈Σ * j ,j∈[1,m] S = s, a • λ i + r i • n i=1 θ σ * ,i,0 , r i , δ σ * ∈Σ * T = {α}
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 σ ∈ Σ 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

R = {α + a • d * , d * • n i=1 θ σ * ,i,1 }, S = {s, a • λ i , d * • n i=1 θ σ * ,i,0 }, and T = {α} (13)
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 ϑ

α • s = i,j ϑ (a) i,j • r i • s j + k ϑ (b) k • t k = ϑ (1) (α + a • d * )s + ϑ (2) (α + a • d * )(a • λ i ) + ϑ (3) (α + a • d * )(d * • n i=1 θ σ * ,i,0 ) ϑ (4) s • d * • µ n i=1 θ σ * ,i,0 + ϑ (5) a • λ i • d * • µ n i=1 θ σ * ,i,0 + ϑ (6) (d * ) 2 • µ( n i=1 θ σ * ,i,0 ) 2 (14)
Hence, to prove the theorem, we need to show that ϑ (k) = 0, ∀k ∈ [START_REF] Shohel | Turning trust around: smart contract-assisted public key infrastructure[END_REF][START_REF] Boyen | The uber-assumption family[END_REF].

First, let us consider Equation 14 as a polynomial in µ. By regrouping the monomials according to their degree, we have:

ϑ (1) (α + a • d * )s + ϑ (2) (α + a • d * )(a • λ i ) + ϑ (3) (α + a • d * )(d * • n i=1 θ σ * ,i,0 ) = 0 (15)
and

ϑ (4) s • d * • µ n i=1 θ σ * ,i,0 + ϑ (5) a • λ i • d * • µ n i=1 θ σ * ,i,0 + ϑ (6) (d * ) 2 • µ( n i=1 θ σ * ,i,0 ) 2 = 0 (16)
Let us focus on Equation 15and consider it as a polynomial in d * , then we have:

ϑ (3) a • (d * ) 2 • n i=1 θ σ * ,i,0 = 0 ⇔ ϑ (3) = 0. ( 17
)
and ϑ (1)

(α + a • d * )s + ϑ (2) (α + a • d * )(a • λ i ) = 0 (18)
Now, if we consider the latte equation as a polynomial in a, the we get:

-ϑ (2) a 2 • d * • λ i = 0 ⇔ ϑ (2) = 0 -ϑ (1) a • d * • s = 0 ⇔ ϑ (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 16and consider it as a polynomial in a. Then we have:

ϑ (5) a • λ i • d * • µ n i=1 θ σ * ,i,0 = 0 ⇔ ϑ (5) = 0 (19)
and

ϑ (4) s • d * • µ n i=1 θ σ * ,i,0 + ϑ (6) (d * ) 2 • µ( n i=1 θ σ * ,i,0 ) 2 = 0 (20)
Finally, let us consider the latter Equation a polynomial in d * , then we have: (6) = 0 which concludes the proof.

-ϑ (4) s • d * • µ n i=1 θ σ * ,i,0 = 0 ⇔ ϑ (4) = 0 -ϑ (6) (d * ) 2 • µ( n i=1 θ σ * ,i,0 ) 2 = 0 ⇔ ϑ

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 [START_REF] Li | Tmacs: A robust and verifiable threshold multi-authority access control system in public cloud storage[END_REF]. 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.

(2 + Nu)S G 1 CSP Keys maxC∈X (π -πC)S Zp - Data (1 + 2l)S G 2 (1 + 2l)S G 2 + S G t
The sign (-) is used to indicate that no storage is required.

Table 3: Comparison of the storage complexity

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.

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.

)S G 1 + (NΣ + 2)S G 2 + S G t (2n + 1)S Zp + S G 1 (2n + 1)S Zp + S G 1 (2n + 1)S Zp + S G 1 DU 4S Zp 4S Zp DO (2N U + 1)S G 2 (2N U + 1)S G 2 Decryption Key AA (2 + Nu)S G 1 (2 + Nu)S G 1 Generation DU (2 + Nu)tS G 1 (2 + Nu)tS G 1 Data DU (2 + Nu)S G 1 - Decryption CSP S G t + NI S G t + NI S G t + NI (2 + Nu)S G 2 + NI Revocation CSP (t + 1)S G 2 + NΣ,R(S G 1 + S G 2 ) N/A AA 3S G 2 +(2+Nu)(NU - NU,R)S G 1 N/A DU (2 + Nu)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.

Table 4: Comparison of the communication complexity

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.

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.

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. 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 [START_REF] De | jpbc: Java pairing based cryptography[END_REF]. As storage infrastructure, we use MinIO [START_REF] Minio | MinIO -High Performance, Kubernetes Native Object Storage[END_REF] , a High-Performance Object Storage compatible with Amazon S3 cloud storage service.

Experimental Evaluation

Experimental Setup

The features of our construction are evaluated on a Linux server having 2×Intel(R) Xeon(R) CPU E5-2695 v3 @ 2.30GHz, 2×14/14 cores; 28 threads. During the conducted evaluations, each entity is deployed in a virtual machine having 4 vCPUs1 , 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 4kb of RAM and operate on the Multos OS.

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

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.

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.

Fig. 1 :

 1 Fig. 1: System Model

  (a) 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. (b) 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 . 3. Revocation: C revokes a subset Σ ′ ⊆ Σ * of attributes from A such that Σ * \Σ ′ no longer satisfies M * 1 . 4. 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 . 5. Challenge: C chooses randomly β 1 , β 2 ∈ {0, 1}, re-encrypts C β and C ′ β as described in Algorithm 1 (lines 9 to 18) and sends them to A. 6. Guess: A outputs its guesses β ′ 1 and β ′ 2 of β 1 and β 2 respectively.

  aid i aid j -aid i = g α 2 pkt 0 = i∈I (pkt i,0 ) j∈I,j̸ =i aid i aid j -aid i = g δ 2 with a = n i=1 a i , α = n i=1 α i , σ = n i=1 σ i ,and α = n i=1 α i . Then, DCA computes Θ σ,π and Θ σ,π , ∀σ ∈ Σ as follows:

Input: 8 z = 1 9/ 11 z = z * µi 12 end 13 foreach i ∈ [ 1 ,

 811112131 SKcsp, Ku, M P K, ind Output: κ, Eκ(M ) 1 (Eκ(M ), C, πc) = get item(ind) 2 I = {i : ρ(i) ∈ Σu} 3 if πr ̸ = πp then 4 return exception("Unsynchronized secret decryption key") 5 end 6 {C ′ , Ci, Di} i∈[1,l] = C 7 if πu < πp then * enforcing backward secrecy */ 10 for i ∈]max(πu, πc), πp] do

  by I σ = {i|σ ∈ Σ 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 ∀σ ∈ Σ : Θ σ,π = Θ i∈Iσ µi σ,0 and Θ σ,π = Θ i∈Iσ µi σ,0

  following equation, according to the definition of dependence (Definition 1):

Figure 2

 2 Figure2gives 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 javabased framework called Spring Boot[START_REF] Webb | Spring boot reference Part IV[END_REF] (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[START_REF] Jones | Json web token (jwt)[END_REF].

Fig. 2 :

 2 Fig. 2: Overview of the implementation framework

Fig. 3 :

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

Fig. 4 :

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

Fig. 5 :

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

Fig. 6 :

 6 Fig. 6: Decryption Evaluation

  n = 4 n = 8 n = 16 l = 4 l = 8 l = 16 Nu = 4 Nu = 8 Nu = 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

Table 2 :

 2 Notations used in the conducted evaluation

	Entity	This work	TMACS
	DCA	(NU + n)S Zp	(2NΣ + 10)S G 1 + (2NU + n)S Zp
	AA	(3 + 2NΣ)S Zp	(6 + 2NΣ)S Zp
	DP	-	-
	DU	(2 + Nu)S G 1

Table 5 :

 5 Comparison of the computation complexity

	8 The Implementation Framework

Table 7 :

 7 Data Exchanged Between Entities During Various Operations of the Scheme

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

⋆ This research is funded by the German-French joint collaboration program on "Cybersecurity" funded by the MESRI (via ANR) and BMBF (via VDI/VDE IT) (ANR-20-CYAL-0008), within the frame of AUTOPSY project.

In addition, we thank the anonymous reviewers for their valuable comments.