# Multi-Authority Criteria-Based Encryption Scheme for IoT

Authors: Jianguo Sun; Yang Yang; Zechao Liu; Yuqing Qiao
Journal: Security and Communication Networks
 (2021)

---

## Abstract

Currently, the Internet of Things (IoT) provides individuals with real-time data processing and efficient data transmission services, relying on extensive edge infrastructures. However, those infrastructures may disclose sensitive information of consumers without authorization, which makes data access control to be widely researched. Ciphertext-policy attribute-based encryption (CP-ABE) is regarded as an effective cryptography tool for providing users with a fine-grained access policy. In prior ABE schemes, the attribute universe is only managed by a single trusted central authority (CA), which leads to a reduction in security and efficiency. In addition, all attributes are considered equally important in the access policy. Consequently, the access policy cannot be expressed flexibly. In this paper, we propose two schemes with a new form of encryption named multi-authority criteria-based encryption (CE) scheme. In this context, the schemes express each criterion as a polynomial and have a weight on it. Unlike ABE schemes, the decryption will succeed if and only if a user satisfies the access policy and the weight exceeds the threshold. The proposed schemes are proved to be secure under the decisional bilinear Diffie–Hellman exponent assumption (q-BDHE) in the standard model. Finally, we provide an implementation of our works, and the simulation results indicate that our schemes are highly efficient.


---

## Body

## 1. Introduction

As an emerging concept, the Internet of Things (IoT) offers great convenience to our daily lives since it provides individuals with ultra-fast data transmission and quality storing services by edge infrastructure. Many well-known IT enterprises such as Google, Microsoft, and Amazon have deployed edge computing platforms to integrate edge infrastructure and various devices, so that individuals can benefit in many fields [1]. Unfortunately, due to the complexity of architecture, there are inevitably some security risks in IoT, especially that some unsupervised edge infrastructures may quietly capture users’ sensitive information or be compromised by malicious users, which poses a severe threat to individuals [2, 3]. For example, edge devices may reveal sensitive data such as health records and personal finances to the public. Therefore, data security in IoT has become a significant concern for many enterprises or individuals.To alleviate this situation, Yeh et al. [4] proposed an access control framework for IoT with the property of attribute revocation. Qiu et al. [5] constructed an authentication and key agreement (AKA) protocol for lightweight devices in IoT. The protocol was proved to be secure in the random oracle model and enjoyed desirable computing efficiency. Wang et al. [6] conducted a detailed analysis of the vulnerability for IoT devices and offered targeted countermeasures depending on the types of attacks. However, traditional public-key techniques only support one-to-one encryption, i.e., messages encrypted by public keys can only be decrypted by their corresponding private keys. This means that there needs to be sufficient storage space to store the ciphertext in practical applications, whereas edge devices generally have limited storage capacity.Attribute-based encryption (ABE) is an effective encryption tool that provides fine-grained and one-to-many access control for outsourcing data in IoT [7]. According to different encryption mechanisms, ABE can be divided into ciphertext-policy ABE (CP-ABE) and key-policy ABE (KP-ABE). In CP-ABE, the data owner can construct an access policy and embed it into the ciphertext, and the user’s attribute set is embedded in the secret key. On the contrary, the private keys in KP-ABE are associated with the access policy, and the ciphertext is labeled with attributes. A user can successfully recover messages if and only if his/her attributes satisfy the access policy. Many excellent ABE schemes for access control in IoT have been proposed [8–11]. However, most of them have two problems. On the one hand, only a single attribute authority (AA) manages the whole attribute set and generates the secret keys. If a large number of users request private keys, the server will be at risk of crashing. Furthermore, once the attribute authority is compromised, any user with unauthorized attributes will be able to decrypt the ciphertext. Therefore, ABE schemes supporting multiple authorities should be considered, i.e., the attribute universe should be managed by multiple attribute authorities. In this way, even if an authority compromises or collapses, a user can still obtain the secret key from other authorities. On the other hand, all attributes in the access policy of the previous schemes are regarded at the same level, which ignores the scenario that some attributes may be more important than the others. More precisely, in an IoT-based medical system, it is desirable to grant doctors higher weights than the nurses.In order to distinguish the importance among attributes, some weighted ABE schemes [12–14] have been proposed. Liu et al. [12] proposed a weighted CP-ABE scheme. However, in the scheme, the attribute universe is managed by a single central authority. Wang et al. [13] constructed a multi-authority weighted ABE scheme in cloud computing. In the scheme, CA is still required in the key generation phase, which reduces the security of the scheme. Yan et al. [14] introduced a weighted attribute-based encryption scheme. However, the weight corresponding to each attribute is specified by a central authority, while in the actual scenario of encryption, the data owner should be allowed to decide the weight of each attribute in the access policy. To address the above problems, Phuong et al. [15] first proposed criteria-based encryption (CE) scheme, which supports the weighting of each criterion in the access policy. To be precise, each criterion is expressed as a polynomial, each root of which corresponds to a case satisfying the polynomial-associated criterion. The access policy consists of a series of weighted criteria containing at least one case. For this, the main difference between ABE and CE is that each criterion contains multiple satisfying cases and has a reasonable weight specified by the encryptor. An instance of intuition is provided as follows. Suppose that in a smart medical system, the government needs to monitor the health of community members. Since medical data involve sensitive information of individuals and are not available to others, the receivers need to meet certain restrictions to make access possible ((the receiver must be an authorized chief physician, weighted 5, and marked as a criterion P1) AND (the receiver has more than 5 years of work experience, weighted 2, and marked as a criterion P2) OR (the receiver is a community manager employed by the government, weighted 1, and marked as a criterion P3) OR (the receiver is a community member holding a legal device, weighted 6, and marked as a criterion P4)). And in order to access the data, the cumulative weight of the receiver must be more than 5. Bob is a community manager hired by the government and has 6 years of work experience related to medical treatment. He cannot obtain approval for not reaching the cumulative weight threshold as required. Alice is a chief physician who has served the community for seven years. She satisfies both the access policy and the threshold, so she can be authorized. As shown in Figure 1, the criterion P3 corresponds to two cases (roots): the receiver is a community manager and appointed by the government. But unfortunately, the issue of generating keys by only a single authority is still unsolved in their scheme.Figure 1
The example of access policy.In this paper, we propose two types of multi-authority criteria-based encryption schemes, named MA-CE-Verify Root and MA-CE-Root Equality, respectively, which aim to solve the problems we mentioned above. Specifically, we denote each criterion as a polynomial. One can assign a weight for each criterion freely according to demands. In addition, the corresponding cases of satisfying the criteria are represented as the roots of polynomials. In the first scheme, at least a case (or root) of each criterion specified in the access policy should be held by the decryptor, and the cumulative weight needs to exceed the threshold as well for successful decryption, while in the second scheme, only if the decryptor satisfies all the cases (or all roots) for each criterion and the cumulative weight exceeds the threshold, he/she can decrypt correctly. Moreover, in our schemes, multiple authorities manage the global criterion universe and perform key generation, which solves the bottleneck of performance and improves the security of the system.


### 1.1. Our Contributions

In this work, our main contributions can be summarized as follows:(1)
We propose two types of multi-authority criteria-based encryption schemes, which support the weighting of each criterion. In our schemes, multiple AAs jointly manage the criterion universe using thet,n-threshold sharing technology. Furthermore, data owners can freely set the weight of each criterion as required. Thus, flexible access control is provided by our schemes.(2)
The security proof shows that our schemes achieve indistinguishability under chosen-plaintext attack (IND-CPA) under the decisional bilinear Diffie–Hellman exponent assumption (q-BDHE).(3)
We implement the proposed schemes and provide theoretical analysis. The results show that our constructions have desirable performance in practical situations.


### 1.2. Related Work

Goyal et al. [16] proposed attribute-based encryption (ABE) that provides one-to-many encryption. In their works, ABE is divided into two forms: ciphertext-policy ABE (CP-ABE) and key-policy ABE (KP-ABE). Sahai et al. [17] realized a revocable ABE (RABE) scheme, in which the outsourcing server updates the encrypted data to revoke the user’s decryption permission. On the downside, the complexity of bilinear-pairing operations makes it difficult to directly apply this scheme to IoT. Agrawal et al. [18] proposed two versatile ABE architectures with short ciphertext and key. One limitation is that the scheme does not consider that different attributes in the access policy are at different levels of importance, i.e., the attributes do not carry reasonable weights. Waters [19] and Agrawal et al. [20] proposed ABE schemes that support arbitrary length input and provide a general ABE structure. In these schemes, the management of attribute universe and key generation are only implemented by a single attribute authority. Once the authority is corrupted, the adversary can directly generate the key of any user with legal status to decrypt the message [21]. ABE schemes with multiple authorities have been proposed to solve this issue. Lewko et al. [22] constructed an ABE scheme in which any party can become an attribute authority. Moreover, the scheme can resist collision attacks. However, the construction based on composite order group seriously affects the execution efficiency of the scheme. In [23–26], the schemes are provided for different practical application scenarios. Unfortunately, these schemes are limited by some security issues or computational complexity. In this context, there are obstacles to directly applying them in IoT scenarios. Sandor et al. [27] presented an efficient decentralized multi-authority ABE scheme that can significantly solve the key escrow problem for mobile devices. Generally, decentralizing ABE solves the problem of accessing encrypted data when the attributes of users come from multiple authorities, in which each authority is only in charge of issuing attributes and keys in its domain. However, in the schemes, an adversary can still compromise the server of AA to obtain some information that he should not have. The issue can be solved by using t,n-threshold sharing in our works. The adversary cannot get any information related to the key unless the number of corrupted authorities is greater than t.


### 1.3. Organization

InSection 2, we present the notation and preliminaries. In Section 3, we provide three components. The system model and some requirements of the schemes are described in Section 3.1. We define the framework of the schemes in Section 3.2, while the security model is given in Section 3.3. In Section 4, we illustrate how to construct our two schemes. We give the security proof of our schemes in Section 5. The performance analysis of proposed schemes is represented in Section 6. At the end of our work, the conclusions and extensions are put forward in Section 7.


## 1.1. Our Contributions

In this work, our main contributions can be summarized as follows:(1)
We propose two types of multi-authority criteria-based encryption schemes, which support the weighting of each criterion. In our schemes, multiple AAs jointly manage the criterion universe using thet,n-threshold sharing technology. Furthermore, data owners can freely set the weight of each criterion as required. Thus, flexible access control is provided by our schemes.(2)
The security proof shows that our schemes achieve indistinguishability under chosen-plaintext attack (IND-CPA) under the decisional bilinear Diffie–Hellman exponent assumption (q-BDHE).(3)
We implement the proposed schemes and provide theoretical analysis. The results show that our constructions have desirable performance in practical situations.


## 1.2. Related Work

Goyal et al. [16] proposed attribute-based encryption (ABE) that provides one-to-many encryption. In their works, ABE is divided into two forms: ciphertext-policy ABE (CP-ABE) and key-policy ABE (KP-ABE). Sahai et al. [17] realized a revocable ABE (RABE) scheme, in which the outsourcing server updates the encrypted data to revoke the user’s decryption permission. On the downside, the complexity of bilinear-pairing operations makes it difficult to directly apply this scheme to IoT. Agrawal et al. [18] proposed two versatile ABE architectures with short ciphertext and key. One limitation is that the scheme does not consider that different attributes in the access policy are at different levels of importance, i.e., the attributes do not carry reasonable weights. Waters [19] and Agrawal et al. [20] proposed ABE schemes that support arbitrary length input and provide a general ABE structure. In these schemes, the management of attribute universe and key generation are only implemented by a single attribute authority. Once the authority is corrupted, the adversary can directly generate the key of any user with legal status to decrypt the message [21]. ABE schemes with multiple authorities have been proposed to solve this issue. Lewko et al. [22] constructed an ABE scheme in which any party can become an attribute authority. Moreover, the scheme can resist collision attacks. However, the construction based on composite order group seriously affects the execution efficiency of the scheme. In [23–26], the schemes are provided for different practical application scenarios. Unfortunately, these schemes are limited by some security issues or computational complexity. In this context, there are obstacles to directly applying them in IoT scenarios. Sandor et al. [27] presented an efficient decentralized multi-authority ABE scheme that can significantly solve the key escrow problem for mobile devices. Generally, decentralizing ABE solves the problem of accessing encrypted data when the attributes of users come from multiple authorities, in which each authority is only in charge of issuing attributes and keys in its domain. However, in the schemes, an adversary can still compromise the server of AA to obtain some information that he should not have. The issue can be solved by using t,n-threshold sharing in our works. The adversary cannot get any information related to the key unless the number of corrupted authorities is greater than t.


## 1.3. Organization

InSection 2, we present the notation and preliminaries. In Section 3, we provide three components. The system model and some requirements of the schemes are described in Section 3.1. We define the framework of the schemes in Section 3.2, while the security model is given in Section 3.3. In Section 4, we illustrate how to construct our two schemes. We give the security proof of our schemes in Section 5. The performance analysis of proposed schemes is represented in Section 6. At the end of our work, the conclusions and extensions are put forward in Section 7.


## 2. Preliminaries

We now introduce some notations and preliminaries.


### 2.1. Notation

For a positive integern, 1,n=1,2,…,n. For vector u⟶ and v⟶, let u⟶,v⟶ be the inner product of two vectors. We use a∈RS to denote a random element a drawn from set S uniformly. For a matrix M, its i-th row is denoted by Mi, and its i,j-element is Mi,j. We use the symbol C⊨A to denote the criterion set C satisfies the access structure A. Note that the (monotonic) access structure used in this work is similar to that in literature [8], so the concrete concept is not repeated here. For any set S, lenS denotes the number of its elements.


### 2.2. Bilinear Maps

LetG and GT be two multiplicative cyclic groups of order p, where p is a large prime number and G is generated by g. Let e:G×G⟶GT be an admissible bilinear map, if it satisfies the following properties:(1)
Bilinearity: for anyg,h∈G and a,b∈Zp, ega,hb=eg,hab.(2)
Nondegeneracy: for anyg∈G, eg,g≠1.(3)
Computability: for anyg,h∈G, there is an efficient algorithm to calculate eg,h.


### 2.3.t,n-Threshold Secret Sharing

Suppose that several participants intend to share a secret with each other, while they do not hope that any one of them can obtain the secret independently, due to the privacy requirement of the secret. Secret sharing is a technique proposed to be used in the scenario above. In the secret-sharing scheme, each party can obtain a share of the secret, which is actually a part of information about the secret, and the whole secret can be reconstructed only by the cooperation of participants, which means that any party cannot know what the secret is individually. There have been many various secret-sharing schemes suitable for different situations proposed, and thet,n-threshold sharing is one of the most widely applicable and basic schemes among them. It was first proposed by Shamir [28] and then improved into many practical schemes, such as [21, 29]. In this work, we adopt the definition in [21].We take the setP=P1,P2,…,Pn as n members of the system. The identity of each member xii∈1,n is taken from the finite field GFp. Let the positive integer tt≤n denote a threshold. Additionally, let Si represent the subsecret of each member, such that S=∑i=1nSi. The t,n-threshold secret sharing can be described as follows.Share. Each member constructs the polynomial qix of degree t−1, such that Si=qi0. For j=1 to n, each member calculates subshare ηij=qixj and assigns xj,ηij to member Pj.Reconstruction. Suppose that there is a function Qx, such that Qx=∑j=1nqjx. Each member calculates the share ηi=∑j=1nηji=∑j=1nQxi. The shares of any t members are sufficient to reconstruct the function Qx according to the Lagrange interpolating formula. The master secret S can be constructed by S=Q0.


### 2.4. Linear Secret-Sharing Schemes

We make use of Linear Secret-Sharing Schemes (LSSSs) in [22]. A secret-sharing scheme Π defined on a set of parties P is linear over Zp if(1)
The shares for each party constitute a vector overZp.(2)
The matrixM with ℓ rows and n columns is called the share-generating matrix. And the function ρ maps Mi to a party ρi, where i∈1,n. When it comes to the column vector v⟶=s,r2,r3,…,rn∈Zpn, where s∈Zp is the secret to be shared and r2,r3,…,rn∈RZp are randomly chosen, then Mv⟶ is the vector composed of ℓ shares of the secret in accordance with Π. The share Mv⟶i belongs to party ρi.Linear reconstruction is defined as follows: suppose thatΠ is an LSSS of the access structure A. Let S∈A be any authorized set, and define I⊂1,2,…,ℓ as I=i:ρi∈S. Then, there exists a set of constants ωi∈Zpi∈I that satisfy the proposition; if λi are valid shares of any secret s according to Π, then s=∑i∈Iωiλi.Definition 1.
(Decisional Bilinear Diffie–Hellman Exponent Assumption (q-BDHE)). LetG be a group of prime order p and gi be short for gai. Given a,s∈Zp and h=gs, the decision q-BDHE problem [30] can be defined as follows: the adversary is given a vector(1)y⟶=g,gs,g1,…,gq,gq+2,…,g2q,and it is hard to distinguish egq+1,h∈GT from a random element in GT. There is an algorithm ℬ that outputs b∈0,1 with advantage ε in solving decisional q-BDHE in G if(2)|Prℬy⟶,T=eg,gaq+1s−Prℬy⟶,T=R=0|≥ε.
The decisional q-BDHE assumption holds if there is no polynomial-time algorithm that can solve the (decision) q-BDHE problem with non-negligible advantage.
Mathematically, the Vieta’s theorem is used to express the relationship between the root of a polynomial and its coefficients. In our schemes, it is a building block for computing the elements of the ciphertext/secret key.Definition 2 (Vieta’s theorem) (see [15]).
LetPi=anxn+an−1xn−1+…+a1x+a0 represent a polynomial of degree n, and its coefficients are expressed as the vector(3)u⟶=an,an−1,…,a1,a0.
For anyx⟶, we represent as follows:(4)x⟶=x⋅x…x︸n,x…x︸n−1,…,x,1,where element x is a root of Pi, if the inner product u⟶,x⇀=0. Suppose xii∈1,n are the roots of Pi; then, we have(5)x1+x2+⋯+xn=−an−1an,x1x2+x1x3+⋯+xnxn−1=an−2an,x1x2⋯xn=−1na0an.


## 2.1. Notation

For a positive integern, 1,n=1,2,…,n. For vector u⟶ and v⟶, let u⟶,v⟶ be the inner product of two vectors. We use a∈RS to denote a random element a drawn from set S uniformly. For a matrix M, its i-th row is denoted by Mi, and its i,j-element is Mi,j. We use the symbol C⊨A to denote the criterion set C satisfies the access structure A. Note that the (monotonic) access structure used in this work is similar to that in literature [8], so the concrete concept is not repeated here. For any set S, lenS denotes the number of its elements.


## 2.2. Bilinear Maps

LetG and GT be two multiplicative cyclic groups of order p, where p is a large prime number and G is generated by g. Let e:G×G⟶GT be an admissible bilinear map, if it satisfies the following properties:(1)
Bilinearity: for anyg,h∈G and a,b∈Zp, ega,hb=eg,hab.(2)
Nondegeneracy: for anyg∈G, eg,g≠1.(3)
Computability: for anyg,h∈G, there is an efficient algorithm to calculate eg,h.


## 2.3.t,n-Threshold Secret Sharing

Suppose that several participants intend to share a secret with each other, while they do not hope that any one of them can obtain the secret independently, due to the privacy requirement of the secret. Secret sharing is a technique proposed to be used in the scenario above. In the secret-sharing scheme, each party can obtain a share of the secret, which is actually a part of information about the secret, and the whole secret can be reconstructed only by the cooperation of participants, which means that any party cannot know what the secret is individually. There have been many various secret-sharing schemes suitable for different situations proposed, and thet,n-threshold sharing is one of the most widely applicable and basic schemes among them. It was first proposed by Shamir [28] and then improved into many practical schemes, such as [21, 29]. In this work, we adopt the definition in [21].We take the setP=P1,P2,…,Pn as n members of the system. The identity of each member xii∈1,n is taken from the finite field GFp. Let the positive integer tt≤n denote a threshold. Additionally, let Si represent the subsecret of each member, such that S=∑i=1nSi. The t,n-threshold secret sharing can be described as follows.Share. Each member constructs the polynomial qix of degree t−1, such that Si=qi0. For j=1 to n, each member calculates subshare ηij=qixj and assigns xj,ηij to member Pj.Reconstruction. Suppose that there is a function Qx, such that Qx=∑j=1nqjx. Each member calculates the share ηi=∑j=1nηji=∑j=1nQxi. The shares of any t members are sufficient to reconstruct the function Qx according to the Lagrange interpolating formula. The master secret S can be constructed by S=Q0.


## 2.4. Linear Secret-Sharing Schemes

We make use of Linear Secret-Sharing Schemes (LSSSs) in [22]. A secret-sharing scheme Π defined on a set of parties P is linear over Zp if(1)
The shares for each party constitute a vector overZp.(2)
The matrixM with ℓ rows and n columns is called the share-generating matrix. And the function ρ maps Mi to a party ρi, where i∈1,n. When it comes to the column vector v⟶=s,r2,r3,…,rn∈Zpn, where s∈Zp is the secret to be shared and r2,r3,…,rn∈RZp are randomly chosen, then Mv⟶ is the vector composed of ℓ shares of the secret in accordance with Π. The share Mv⟶i belongs to party ρi.Linear reconstruction is defined as follows: suppose thatΠ is an LSSS of the access structure A. Let S∈A be any authorized set, and define I⊂1,2,…,ℓ as I=i:ρi∈S. Then, there exists a set of constants ωi∈Zpi∈I that satisfy the proposition; if λi are valid shares of any secret s according to Π, then s=∑i∈Iωiλi.Definition 1.
(Decisional Bilinear Diffie–Hellman Exponent Assumption (q-BDHE)). LetG be a group of prime order p and gi be short for gai. Given a,s∈Zp and h=gs, the decision q-BDHE problem [30] can be defined as follows: the adversary is given a vector(1)y⟶=g,gs,g1,…,gq,gq+2,…,g2q,and it is hard to distinguish egq+1,h∈GT from a random element in GT. There is an algorithm ℬ that outputs b∈0,1 with advantage ε in solving decisional q-BDHE in G if(2)|Prℬy⟶,T=eg,gaq+1s−Prℬy⟶,T=R=0|≥ε.
The decisional q-BDHE assumption holds if there is no polynomial-time algorithm that can solve the (decision) q-BDHE problem with non-negligible advantage.
Mathematically, the Vieta’s theorem is used to express the relationship between the root of a polynomial and its coefficients. In our schemes, it is a building block for computing the elements of the ciphertext/secret key.Definition 2 (Vieta’s theorem) (see [15]).
LetPi=anxn+an−1xn−1+…+a1x+a0 represent a polynomial of degree n, and its coefficients are expressed as the vector(3)u⟶=an,an−1,…,a1,a0.
For anyx⟶, we represent as follows:(4)x⟶=x⋅x…x︸n,x…x︸n−1,…,x,1,where element x is a root of Pi, if the inner product u⟶,x⇀=0. Suppose xii∈1,n are the roots of Pi; then, we have(5)x1+x2+⋯+xn=−an−1an,x1x2+x1x3+⋯+xnxn−1=an−2an,x1x2⋯xn=−1na0an.


## 3. Multi-Authority Criteria-Based Encryption

### 3.1. System Model and Requirements

In this section, we define the notion of the system model and illustrate some requirements in our multi-authority criteria-based encryption schemes. As shown in Figure2 [31], the system consists of a global central authority (CA), multiple criterion authorities (AAs), the edge infrastructures, data owners (DO), and data consumers (user). Here, we give the formal definition of them as follows.(1)
The central authority (CA) in the whole system is considered to be completely trusted and in charge of system establishment and initialization, including the generation of system parameters and the master public key. When a user (or AA) requests registration, CA verifies the legitimacy of his identity and assigns a uniquegid for the user and an aid for the AA, respectively. Besides, CA determines the threshold t in threshold sharing among attribute authorities, which is necessary for the process of secret key generation. In contrast, we note that CA is not responsible for any other issues in the system except for what has been described above. In other words, CA does not participate in the threshold sharing among AAs and key generation, which is the core of decentralization.(2)
A criterion authority (AA) mainly generates the component of the user secret key associated with the criteria in its domain and plays a role in system establishment as well. What’s worthy of mention is that, compared with common multi-authority CP-ABE, in our proposed system, all AAs manage the entire criterion universe together. We use the technique of threshold sharing among AAs so that each AA shares a piece of secret key calling its private key, which can ensure that a malicious user cannot get any information unless the number of corrupted authorities exceedst. After that, CA accepts public keys from all AAs to generate the system public key. Finally, when a user requests for his/her user’s secret key, each AA only distributes its corresponding share of user secret key. Namely, there is no need for an AA to communicate with any other AA during the period of encryption and key generation.(3)
A data owner (DO) encrypts the data. He/she specifies the access policy over criteria, the weight of each criterion, and the cumulative weight threshold that a user needs to satisfy. Concretely, DO runs the encryption algorithm and generates a ciphertext associated with all these requirements above and then uploads the ciphertext to edge infrastructure.(4)
The user obtains a global identitygid issued by CA and AAs. Besides, any user in the system can download the encrypted data but can get access to the plaintext only when he/she satisfies both the access policy and weight requirement that the data owner specifies.(5)
Each edge infrastructure is an entity that provides storage and computing services for DO. It accepts encrypted data sent by DO. Then, the data can be obtained by any registered user in the system.Figure 2
The framework of system model.For precision and unambiguity, some default definitions and requirements in our proposed schemes are provided here. In the system model, we suppose that CA is unconditionally credible and cannot be compromised. On the other hand, a user can download whichever encrypted data he wants but can recover the corresponding plaintext if and only if he/she satisfies both the access policy and the cumulative weight threshold. Moreover, since the weights reflect the difference in importance among criteria when formulating an access policy, the ideal situation is that the user criteria that satisfy the policy contain more relatively significant (higher weight) criteria rather than a simple patchwork of low-weight criteria. Therefore, we consider that data owners are all sufficiently rigorous to design access policies, endue weight on each criterion, and set the thresholds over criteria. Furthermore, there are at least two authorities in the system.


### 3.2. Syntax of Scheme

The syntax of the multi-authority criteria-based encryption scheme consists of the following PPT algorithms:(1)
GlobalSetup1λ⟶pp: the algorithm is performed by CA. It takes as input security parameter λ. It consists of three steps. CA first performs the group generation algorithm G1λ to obtain GP=G,GT,e,g,p and defines criterion universe U with size n. Then, it chooses φi∈RZp to label each polynomial Pi. Eventually, CA receives registration requests from users and AAs and records the number of AAs as nθ. It outputs public parameter pp=GP,n,t,φii∈1,n,nθ.(2)
AASetuppp⟶pkθ,skθ: the algorithm is performed by CA. For each authority AAθ, it first chooses αθ at random, such that α=∑θ=1nθαθ. Note that the value of α is secret to any AAθ. Then, all the authorities run t,n-threshold secret sharing according to αθ. Each authority AAθ outputs pkθ and keeps skθ as secret.(3)
CASetuppp,pkθθ∈1,nθ,d⟶PK,MSK: the algorithm is performed by CA and AA. It receives public parameter pp, public keys pkθθ∈1,nθ from all the AAs, and degree d of polynomials. It outputs public key PK and implicitly keeps values α,a for secret.(4)
EncryptPK,m,A,ρ,w⟶,τ⟶CT: the algorithm is performed by DO. It takes in public parameter pp, the public key PK, a message m, an access structure A,ρ, a weight vector w⟶, and weight threshold τ. It outputs a ciphertext CT.(5)
KeyGenpp,PK,gid,Cgid⟶SKgid: the algorithm is performed by the user with identity gid. It takes in pp, public key PK, the global identity gid of a user, and the set of cases Cgid belonging to the user. It outputs a SKgid.(6)
Decryptpp,SKgid,CT⟶m/⊥: it takes in the public parameter pp, the secret key SKgid, and the ciphertext CT. The algorithm outputs either a message m or the distinctive symbol ⊥.For the correctness of our schemes, we require that for theCT←EncryptPK,m,A,ρ,w⟶,τ and the SKgid←KeyGenpp,PK,gid,Cgid, one can execute Decryptpp,SKgid,CT algorithm to obtain the correct message m with overwhelming probability.


### 3.3. Security Model

Here, the IND-CPA security [16] for proposed scheme is defined in the following game which has a challenger C and an adversary A.Init. C performs the algorithm GlobalSetup, AA Setup, and CA Setup and then sends the pp and PK to A.Phase 1. A repeatedly performs private key associated with sets of case ℂ.Challenge. A specifies two messages m0,m1∈GT, a challenge access structure A∗, a vector w⟶∗, and a weight threshold τ∗ to C. The default condition is that ℂ cannot satisfy the access structure A∗. Then, C randomly picks an element b∈0,1 and executes Encrypt algorithm to generate mb∈GT under A∗. Finally, A obtains the ciphertext CT∗ from C.Phase 2. A can repeatedly make the same queries as Phase 1, except that ℂ cannot satisfy A∗.Guess. The adversary outputs a guess b′ of b.The advantage of the adversaryA in this game is defined as Prb′=b−1/2.Definition 3.
The proposed multi-authority criteria-based encryption scheme is secure if all polynomial-time adversaries have at most a negligible advantage in the above game.


## 3.1. System Model and Requirements

In this section, we define the notion of the system model and illustrate some requirements in our multi-authority criteria-based encryption schemes. As shown in Figure2 [31], the system consists of a global central authority (CA), multiple criterion authorities (AAs), the edge infrastructures, data owners (DO), and data consumers (user). Here, we give the formal definition of them as follows.(1)
The central authority (CA) in the whole system is considered to be completely trusted and in charge of system establishment and initialization, including the generation of system parameters and the master public key. When a user (or AA) requests registration, CA verifies the legitimacy of his identity and assigns a uniquegid for the user and an aid for the AA, respectively. Besides, CA determines the threshold t in threshold sharing among attribute authorities, which is necessary for the process of secret key generation. In contrast, we note that CA is not responsible for any other issues in the system except for what has been described above. In other words, CA does not participate in the threshold sharing among AAs and key generation, which is the core of decentralization.(2)
A criterion authority (AA) mainly generates the component of the user secret key associated with the criteria in its domain and plays a role in system establishment as well. What’s worthy of mention is that, compared with common multi-authority CP-ABE, in our proposed system, all AAs manage the entire criterion universe together. We use the technique of threshold sharing among AAs so that each AA shares a piece of secret key calling its private key, which can ensure that a malicious user cannot get any information unless the number of corrupted authorities exceedst. After that, CA accepts public keys from all AAs to generate the system public key. Finally, when a user requests for his/her user’s secret key, each AA only distributes its corresponding share of user secret key. Namely, there is no need for an AA to communicate with any other AA during the period of encryption and key generation.(3)
A data owner (DO) encrypts the data. He/she specifies the access policy over criteria, the weight of each criterion, and the cumulative weight threshold that a user needs to satisfy. Concretely, DO runs the encryption algorithm and generates a ciphertext associated with all these requirements above and then uploads the ciphertext to edge infrastructure.(4)
The user obtains a global identitygid issued by CA and AAs. Besides, any user in the system can download the encrypted data but can get access to the plaintext only when he/she satisfies both the access policy and weight requirement that the data owner specifies.(5)
Each edge infrastructure is an entity that provides storage and computing services for DO. It accepts encrypted data sent by DO. Then, the data can be obtained by any registered user in the system.Figure 2
The framework of system model.For precision and unambiguity, some default definitions and requirements in our proposed schemes are provided here. In the system model, we suppose that CA is unconditionally credible and cannot be compromised. On the other hand, a user can download whichever encrypted data he wants but can recover the corresponding plaintext if and only if he/she satisfies both the access policy and the cumulative weight threshold. Moreover, since the weights reflect the difference in importance among criteria when formulating an access policy, the ideal situation is that the user criteria that satisfy the policy contain more relatively significant (higher weight) criteria rather than a simple patchwork of low-weight criteria. Therefore, we consider that data owners are all sufficiently rigorous to design access policies, endue weight on each criterion, and set the thresholds over criteria. Furthermore, there are at least two authorities in the system.


## 3.2. Syntax of Scheme

The syntax of the multi-authority criteria-based encryption scheme consists of the following PPT algorithms:(1)
GlobalSetup1λ⟶pp: the algorithm is performed by CA. It takes as input security parameter λ. It consists of three steps. CA first performs the group generation algorithm G1λ to obtain GP=G,GT,e,g,p and defines criterion universe U with size n. Then, it chooses φi∈RZp to label each polynomial Pi. Eventually, CA receives registration requests from users and AAs and records the number of AAs as nθ. It outputs public parameter pp=GP,n,t,φii∈1,n,nθ.(2)
AASetuppp⟶pkθ,skθ: the algorithm is performed by CA. For each authority AAθ, it first chooses αθ at random, such that α=∑θ=1nθαθ. Note that the value of α is secret to any AAθ. Then, all the authorities run t,n-threshold secret sharing according to αθ. Each authority AAθ outputs pkθ and keeps skθ as secret.(3)
CASetuppp,pkθθ∈1,nθ,d⟶PK,MSK: the algorithm is performed by CA and AA. It receives public parameter pp, public keys pkθθ∈1,nθ from all the AAs, and degree d of polynomials. It outputs public key PK and implicitly keeps values α,a for secret.(4)
EncryptPK,m,A,ρ,w⟶,τ⟶CT: the algorithm is performed by DO. It takes in public parameter pp, the public key PK, a message m, an access structure A,ρ, a weight vector w⟶, and weight threshold τ. It outputs a ciphertext CT.(5)
KeyGenpp,PK,gid,Cgid⟶SKgid: the algorithm is performed by the user with identity gid. It takes in pp, public key PK, the global identity gid of a user, and the set of cases Cgid belonging to the user. It outputs a SKgid.(6)
Decryptpp,SKgid,CT⟶m/⊥: it takes in the public parameter pp, the secret key SKgid, and the ciphertext CT. The algorithm outputs either a message m or the distinctive symbol ⊥.For the correctness of our schemes, we require that for theCT←EncryptPK,m,A,ρ,w⟶,τ and the SKgid←KeyGenpp,PK,gid,Cgid, one can execute Decryptpp,SKgid,CT algorithm to obtain the correct message m with overwhelming probability.


## 3.3. Security Model

Here, the IND-CPA security [16] for proposed scheme is defined in the following game which has a challenger C and an adversary A.Init. C performs the algorithm GlobalSetup, AA Setup, and CA Setup and then sends the pp and PK to A.Phase 1. A repeatedly performs private key associated with sets of case ℂ.Challenge. A specifies two messages m0,m1∈GT, a challenge access structure A∗, a vector w⟶∗, and a weight threshold τ∗ to C. The default condition is that ℂ cannot satisfy the access structure A∗. Then, C randomly picks an element b∈0,1 and executes Encrypt algorithm to generate mb∈GT under A∗. Finally, A obtains the ciphertext CT∗ from C.Phase 2. A can repeatedly make the same queries as Phase 1, except that ℂ cannot satisfy A∗.Guess. The adversary outputs a guess b′ of b.The advantage of the adversaryA in this game is defined as Prb′=b−1/2.Definition 3.
The proposed multi-authority criteria-based encryption scheme is secure if all polynomial-time adversaries have at most a negligible advantage in the above game.


## 4. Construction

In this section, we first provide an overview of the proposed schemes and then give the detailed constructions of the two schemes.


### 4.1. Overview

What we first consider is how to find a form to express the criteria. In our schemes, the criterion is related to a polynomial, and each root of the polynomial corresponds to a case that satisfies the criteria. The first scheme requires that the user satisfies at least one case of the criterion, while in the second, there is a stricter restriction that the user must satisfy all cases of the criteria. In this context, our scheme improves the flexibility of access policy in practical application. Specifically, recall the access policy described in Figure1. DO specifies an access policy A=P1ANDP2ORP3ORP4, and the cumulative weight threshold is set to τ=6. The observation is that the criterion set with cumulative weight exceeding τ can be expressed as T=4,1,2,1,3,1,4,2,4,3,4,1,2,3,1,2,4,1,3,4,2,3,4,1,2,3,4. Clearly, Alice is a chief physician who has served the community for seven years. The case set and criterion set can be described as CAlice=1,2;SAlice=1,2,1,2. She can successfully decrypt the data due to the fact that set CAlice⊨A (i.e., SCAlice=1,2 and WAlice=T∩SCAlice=1,2. Bob is a community manager hired by the government and has 6 years of work experience related to medical treatment. He cannot decrypt the message successfully, since WBob=T∩SCBob=∅.From the practical perspective, the first scheme is suitable for edge computing platforms, while the second is suitable for users’ private edge devices because those devices are more vulnerable to attacks by adversaries. Moreover, we introduce the multi-authority mechanism to solve the security problem caused by all attributes being managed by one authority. In this work, the criterion universe is jointly managed bynθ AAs. The restriction is that there is no collusion between AAs. Specifically, CA cannot interact with users except for generating global unique identities for them. The user can reconstruct the secret key, which has the term of eg,gα, after interacting with t different AAs. This way, we make it impossible for each AA to generate a valid key individually. Meanwhile, data owners can assign a reasonable weight for each criterion and the cumulative weight according to their requirements, which makes the scheme suitable for real application scenarios.


### 4.2. MA-CE-Verify Root Scheme

Here, we provide our first multi-authority criteria-based encryption scheme that requires the user to have at least one root of a polynomial (or criterion).(1)
GlobalSetup1λ⟶pp: CA first runs G1λ to obtain GP=G,GT,e,g,p, where g is a generator of G and G and GT are two multiplicative cyclic groups with the same order p, such that G×G⟶GT. Then, CA defines the criterion universe U with size n and chooses φi∈RZp to label each polynomial Pi. Moreover, CA receives registration requests from AAs and users, records the number of AAs as nθ, and generates the global unique identity aid, gid∈Zp for AA and user, respectively. At last, CA defines threshold t according to the value nθ. It outputs public parameter pp=GP,n,t,φii∈1,n,nθ.(2)
AA Setuppp⟶pkθ,skθ: firstly, each authority AAθθ∈1,nθ chooses the secret αθ∈RZp, such that master secret α=∑θ=1nθαθ. Then, AAθ randomly sets a polynomial qθx of degree t−1 which satisfies αθ=qθ0. Other AAξξ=1,2,…,θ−1,θ+1,…,nθ obtains the value sθξ=qθaidξ calculated by AAθ. Meanwhile, AAθ calculates sθθ=qθaidθ for itself. Finally, AAθ calculates its secret key skθ=∑ξ=1nθsξθ and public key pkθ=eg,gskθ.(3)
CA Setuppp,pkθθ∈1,nθ,d⟶PK,MSK: CA randomly picks t of nθ AAs’ public keys. Additionally, it picks h1,…,hn∈RG and calculates as(6)eg,gα=∏θ=1tpkθ∏ξ=1,ξ≠θtaidξ/aidξ−aidθ=eg,g∑θ=1tskθ∏ξ=1,ξ≠θtaidξ/aidξ−aidθ.Then, CA selectsa∈RZp and calculates ga. For criterion universe U, it picks a set of d-degree polynomials Pii∈1,n with coefficients ai,d,ai,d−1,…,ai,0 and labels Pi with φi. In this case, the set of polynomials can be described as(7)P⟶1=a1,d,a1,d−1,…,a1,0,1φ1,P⟶1′=a1,d,a1,d−1,…,a1,0,1,⋯,P⟶n=an,d,an,d−1,…,an,0,1φn,P⟶n′=an,d,an,d−1,…,an,0,1.Fori=1 to n, CA computes gφiP⟶i and gP⟶i′. It outputs(8)PK=g,ga,eg,gα,gφiP⟶i,gP⟶i′,hii∈1,n,and keeps the valuesα,a for secret.(4)
EncryptPK,m,A,ρ,w⟶,τ⟶CT: in this phase, the encryption algorithm sets the access policy A,ρ, where the size of the matrix A is ℓ×n, and the function ρ maps Ai to a criterion. Then, it specifies the weight vector w⟶=w1,…,wn, where the element wi represents the weight of each criterion. Also, it takes y2,y3,…,yn∈RZp to construct vector v⟶=s,y2,y3,…,yn∈Zpn, where the first element s∈RZp is the secret value to be shared. For i=1 to ℓ, it computes λi=v⟶⋅Mi. After completing the above processes, it computes the set T=k1i,k2i,…,kμii according to weight threshold τ, where μi indicates the length of i-th subset and kji∈1,2,…,n denotes index in U. Finally, the algorithm calculates(9)C0=m⋅eg,gαs,C0′=gs,Ci=gaλi⋅g−φρiP⟶ρis,Ci′=gaλi⋅g−P⟶ρi′⋅si∈1,ℓ,C^i=∏j=1μihkjisi∈1,lenT.It outputs ciphertext asCT=C0,C0′,Ci,Ci′i∈1,ℓ,C^ii∈1,lenT,T.(5)
KeyGenpp,PK,gid,Cgid⟶SKgid: the key generation algorithm is implemented by the user interacting with t AAs according to the requirements. The restriction is that AAθ cannot communicate with each other.Letzφx be a root of the polynomial at x. For each root zφx that belongs to user, AA creates the vector z⟶φx=zφxd,zφxd−1,…,zφx,1. We use Cgid⊆Cxx∈1,n to denote a set of cases, which belong to the user with gid. Let P=P1,P2,…,PlenCgid denote the set of criteria requested by the user and S=P1,P2,…PlenCgid,P1,P2,…,P1,P2,…,PlenCgid=k1l,…,kvll be all combinations of entities in set P, where vl denotes the length of subset and kjl∈1,n denotes index in U. AAθ picks δθ∈RZp and calculates as(10)Lθ=gδθ,∀Cθ,x∈CgidKθ,x=gφxZ⟶φx⋅δθ,Kθ,x′=gP⟶x′⋅δθ,K^θ,i=gskθgaδθ∏j=1vlhkjlδθl∈1,lenS.After interacting witht AAs, the user constructs the secret key as(11)L=∏θ=1tLθ∏ξ=1,ξ≠θtaidξ/aidξ−aidθ=g∑θ=1tδθ⋅∏ξ=1,ξ≠θtaidξ/aidξ−aidθ.For allCθ,x∈Cgid, we have(12)Kx=∏θ=1tKθ,xZ⟶φx⋅δθ∏ξ=1,ξ≠θtaidξ/aidξ−aidθ=gφxZ⟶φx∑θ=1tδθ∏ξ=1,ξ≠θtaidξ/aidξ−aidθ,Kx′=∏θ=1tgP⟶x′⋅δθ∏ξ=1,ξ≠θtaidξ/aidξ−aidθ=gP⟶x′⋅∑θ=1tδθ∏ξ=1,ξ≠θtaidξ/aidξ−aidθ,K^l=∏θ=1tK^θ,l∏ξ=1,ξ≠θtaidξ/aidξ−aidθ=∏θ=1tgskθgaδθ∏j=1vlhkjlδθ∏ξ=1,ξ≠θtaidξ/aidξ−aidθ.For simplicity, we makeu=∑θ=1tδθ⋅∏ξ=1,ξ≠θtaidξ/aidξ−aidθ. For this, the secret key of the user can be represented as(13)S,L=gu,∀Cx∈CgidKx=gφx⋅Z⟶φxu,Kx′=gP⟶x′⋅u,K^l=gα⋅gau⋅∏j=1vlhkjlul∈1,lenS.(6)
Decryptpp,SKgid,CT⟶m/⊥: the decryption algorithm can successfully be invoked by the user with a valid identity. Namely, the user can download encrypted data from the edge infrastructures, and they can decrypt data successfully if their case set Cgid satisfies access policy and the requirement of cumulative weight.Suppose that the ciphertextCT is encrypted under the access policy A,ρ. We recall the definition of LSSS. Let I⊂1,2,…,ℓ represent a case such that ρi∈Cgid. To decrypt the ciphertext, the user with SKgid computes ωi∈Zpi∈I; if λi is valid share corresponding access policy A,ρ, then the secret s=∑i∈Iωiλi can be calculated. To summarize, the decryption process is as follows:(14)∏i∈IeCi′,L⋅eCi,Kρi⋅eC0′,Kρi′eCi′,Kρiωi=∏i∈Iegaλi⋅g−P⟶ρi′⋅s,gu⋅egaλi⋅g−φρiP⟶ρis,gφρi⋅Z⟶ρiu⋅egs,gP⟶ρi′⋅uegaλi⋅g−P⟶ρi′⋅s,gφρi⋅Z⟶φρiuωi=∏i∈Iegaλi,gu⋅g−φρiP⟶ρis,gφρi⋅Z⟶ρiueg−P⟶ρi'⋅s,gφρi⋅Z⟶φρiuωi=eg,gasu.Define setW=T∩SC⊨A. For each w∈W, let wT and wS denote the index w in set T and S, respectively. Then, compute(15)J=∏w∈WeC0′,K^wSeC^wT,L1/W=∏w∈Wegs,gα⋅gau∏j=1lenwhwjue∏j=1lenwhwjs,gu1/W=∏w∈Wegs,gα⋅gau1/W=eg,gαs⋅eg,gasu.The user can recover the plaintextm from the following equation:(16)m=C0⋅eg,gasuJ.


### 4.3. MA-CE-Root Equality Scheme

Here, we provide our second scheme, which needs all the roots (or cases) of each polynomial (or criterion) to be held by the user.(1)
Global Setup1λ⟶pp: this algorithm is similar to scheme MA-CE-Verify Root. CA runs G1λ to obtain GP=G,GT,e,g,p and defines the criterion universe U with size n. CA also generates unique identity for AAs and users, respectively. Then, it chooses a threshold t and picks φii∈1,n∈RZp. Note that φi is not used to label the polynomial Pi. It outputs public parameter pp=GP,n,t,φii∈1,n,nθ.(2)
AA Setuppp⟶pkθ,skθ: the algorithm is similar to the AA Setup in the first scheme. For each authority AAθ, it inputs the public parameter pp and returns a pair of keys pkθ,skθ, where skθ is kept secret for other AAs.(3)
CA Setuppp,pkθθ∈1,nθ,d⟶PK,MSK: CA randomly chooses t public keys from nθ AAs. In addition, it picks h1,…,hn∈RG and calculates(17)eg,gα=∏θ=1tpkθ∏ξ=1,ξ≠θtaidξ/aidξ−aidθ.Then, CA randomly picksa∈Zp and computes ga. For i=1 to n, it picks a set of d-degree polynomials Pii∈1,n, which can be described as(18)P⟶1=1,a1,d−1a1,d,…,a1,0a1,d,P⟶2=1,a2,d−1a2,d,…,a2,0a2,d,P⟶n=1,an,d−1an,d,…,an,0an,d.It outputsPK=g,ga,eg,gα,gφiP⟶i,hii∈1,n and keeps the values α,a for secret.(4)
EncryptPK,m,A,ρ,w⟶,τ⟶CT: the encryption algorithm sets the access policy A,ρ, the size of the matrix is ℓ×n, and the function ρ maps Ai to a criterion. Then, it specifies the weight vector w⟶=w1,…,wn, where the element wi represents the weight of each criterion. Moreover, it constructs the vector v⟶=s,r2,r3,…,rn∈Zpn. For i=1 to ℓ, it computes λi=v⟶⋅Mi and set T=k1i,k2i,…,kμii according to the weight threshold τ, where μi indicates the length of i-th subset and kji∈1,2,…,n denotes index in U. Finally, the algorithm computes as(19)C0=m⋅eg,gαs,C0′=gsCi=gaλi⋅g−φρiP⟶ρisi∈1,ℓ,C^i=∏j=1μihkjisi∈1,lenT.It outputs ciphertext asCT=C0,C0′,Cii∈1,ℓ,C^ii∈1,lenT,T.(5)
Key Genpp,PK,gid,Cgid⟶SKgid: the user with gid interacts with any t AAs to obtain the key according to requirements. It takes the set Rootsx=x1,x2,…,xd to represent all the roots of the polynomial at x. According to Vieta’s theorem, AA uses Rootsx to construct the following vector:(20)z⟶φx=1,zxd−1,zxd−2,…,zx0.LetCgid⊆Cxx∈1,n represent the cases belonging to the user with identity gid, set P=P1,P2,…,PlenCgid denote the set of criteria requested by the user, and set S=P1,P2,…,PlenCgid,P1,P2,…,P1,P2,…,PlenCgid=k1l,…,kvll be all combinations of entities in set P, where vl denotes the length of l-th subset and kjl∈1,n denotes index in U. AAθ picks δθ∈RZp and calculates as(21)Lθ=gδθ,∀Cθ,x∈CgidKθ,x=gφxZ⟶φx⋅δθK^θ,l=gskθgaδθ∏j=1vlhkjlδθl∈1,lenS.After interacting witht AAs, the user constructs the secret key SKgid as follows:(22)L=gu,∀Cx∈CgidKx=gφxZ⟶φx⋅uK^l=gαgau∏j=1vlhkjlul∈1,lenS.(6)
Decryptpp,SKgid,CT⟶m/⊥: to recover the encrypted data under access policy A,ρ, the user first calculates constants ωi∈Zpi∈I and then computes(23)∏i∈IeCi,L⋅eC0′,Kρiωi=∏i∈Iegaλi⋅g−φρiP⟶ρis,gu⋅egs,gφxZ⟶φx⋅uωi=∏i∈Iegaλi,guωi=eg,gasu.Forw∈W=T∩SC⊨A, the symbols wT and wS denote the index w in set T and S, respectively; then, compute(24)J=∏w∈WeC0′,K^wSeC^wT,L1/W|=egs,gα⋅gauW/W=eg,gαs⋅eg,gasu.The user can recover the plaintextm=C0⋅eg,gasu/J.


## 4.1. Overview

What we first consider is how to find a form to express the criteria. In our schemes, the criterion is related to a polynomial, and each root of the polynomial corresponds to a case that satisfies the criteria. The first scheme requires that the user satisfies at least one case of the criterion, while in the second, there is a stricter restriction that the user must satisfy all cases of the criteria. In this context, our scheme improves the flexibility of access policy in practical application. Specifically, recall the access policy described in Figure1. DO specifies an access policy A=P1ANDP2ORP3ORP4, and the cumulative weight threshold is set to τ=6. The observation is that the criterion set with cumulative weight exceeding τ can be expressed as T=4,1,2,1,3,1,4,2,4,3,4,1,2,3,1,2,4,1,3,4,2,3,4,1,2,3,4. Clearly, Alice is a chief physician who has served the community for seven years. The case set and criterion set can be described as CAlice=1,2;SAlice=1,2,1,2. She can successfully decrypt the data due to the fact that set CAlice⊨A (i.e., SCAlice=1,2 and WAlice=T∩SCAlice=1,2. Bob is a community manager hired by the government and has 6 years of work experience related to medical treatment. He cannot decrypt the message successfully, since WBob=T∩SCBob=∅.From the practical perspective, the first scheme is suitable for edge computing platforms, while the second is suitable for users’ private edge devices because those devices are more vulnerable to attacks by adversaries. Moreover, we introduce the multi-authority mechanism to solve the security problem caused by all attributes being managed by one authority. In this work, the criterion universe is jointly managed bynθ AAs. The restriction is that there is no collusion between AAs. Specifically, CA cannot interact with users except for generating global unique identities for them. The user can reconstruct the secret key, which has the term of eg,gα, after interacting with t different AAs. This way, we make it impossible for each AA to generate a valid key individually. Meanwhile, data owners can assign a reasonable weight for each criterion and the cumulative weight according to their requirements, which makes the scheme suitable for real application scenarios.


## 4.2. MA-CE-Verify Root Scheme

Here, we provide our first multi-authority criteria-based encryption scheme that requires the user to have at least one root of a polynomial (or criterion).(1)
GlobalSetup1λ⟶pp: CA first runs G1λ to obtain GP=G,GT,e,g,p, where g is a generator of G and G and GT are two multiplicative cyclic groups with the same order p, such that G×G⟶GT. Then, CA defines the criterion universe U with size n and chooses φi∈RZp to label each polynomial Pi. Moreover, CA receives registration requests from AAs and users, records the number of AAs as nθ, and generates the global unique identity aid, gid∈Zp for AA and user, respectively. At last, CA defines threshold t according to the value nθ. It outputs public parameter pp=GP,n,t,φii∈1,n,nθ.(2)
AA Setuppp⟶pkθ,skθ: firstly, each authority AAθθ∈1,nθ chooses the secret αθ∈RZp, such that master secret α=∑θ=1nθαθ. Then, AAθ randomly sets a polynomial qθx of degree t−1 which satisfies αθ=qθ0. Other AAξξ=1,2,…,θ−1,θ+1,…,nθ obtains the value sθξ=qθaidξ calculated by AAθ. Meanwhile, AAθ calculates sθθ=qθaidθ for itself. Finally, AAθ calculates its secret key skθ=∑ξ=1nθsξθ and public key pkθ=eg,gskθ.(3)
CA Setuppp,pkθθ∈1,nθ,d⟶PK,MSK: CA randomly picks t of nθ AAs’ public keys. Additionally, it picks h1,…,hn∈RG and calculates as(6)eg,gα=∏θ=1tpkθ∏ξ=1,ξ≠θtaidξ/aidξ−aidθ=eg,g∑θ=1tskθ∏ξ=1,ξ≠θtaidξ/aidξ−aidθ.Then, CA selectsa∈RZp and calculates ga. For criterion universe U, it picks a set of d-degree polynomials Pii∈1,n with coefficients ai,d,ai,d−1,…,ai,0 and labels Pi with φi. In this case, the set of polynomials can be described as(7)P⟶1=a1,d,a1,d−1,…,a1,0,1φ1,P⟶1′=a1,d,a1,d−1,…,a1,0,1,⋯,P⟶n=an,d,an,d−1,…,an,0,1φn,P⟶n′=an,d,an,d−1,…,an,0,1.Fori=1 to n, CA computes gφiP⟶i and gP⟶i′. It outputs(8)PK=g,ga,eg,gα,gφiP⟶i,gP⟶i′,hii∈1,n,and keeps the valuesα,a for secret.(4)
EncryptPK,m,A,ρ,w⟶,τ⟶CT: in this phase, the encryption algorithm sets the access policy A,ρ, where the size of the matrix A is ℓ×n, and the function ρ maps Ai to a criterion. Then, it specifies the weight vector w⟶=w1,…,wn, where the element wi represents the weight of each criterion. Also, it takes y2,y3,…,yn∈RZp to construct vector v⟶=s,y2,y3,…,yn∈Zpn, where the first element s∈RZp is the secret value to be shared. For i=1 to ℓ, it computes λi=v⟶⋅Mi. After completing the above processes, it computes the set T=k1i,k2i,…,kμii according to weight threshold τ, where μi indicates the length of i-th subset and kji∈1,2,…,n denotes index in U. Finally, the algorithm calculates(9)C0=m⋅eg,gαs,C0′=gs,Ci=gaλi⋅g−φρiP⟶ρis,Ci′=gaλi⋅g−P⟶ρi′⋅si∈1,ℓ,C^i=∏j=1μihkjisi∈1,lenT.It outputs ciphertext asCT=C0,C0′,Ci,Ci′i∈1,ℓ,C^ii∈1,lenT,T.(5)
KeyGenpp,PK,gid,Cgid⟶SKgid: the key generation algorithm is implemented by the user interacting with t AAs according to the requirements. The restriction is that AAθ cannot communicate with each other.Letzφx be a root of the polynomial at x. For each root zφx that belongs to user, AA creates the vector z⟶φx=zφxd,zφxd−1,…,zφx,1. We use Cgid⊆Cxx∈1,n to denote a set of cases, which belong to the user with gid. Let P=P1,P2,…,PlenCgid denote the set of criteria requested by the user and S=P1,P2,…PlenCgid,P1,P2,…,P1,P2,…,PlenCgid=k1l,…,kvll be all combinations of entities in set P, where vl denotes the length of subset and kjl∈1,n denotes index in U. AAθ picks δθ∈RZp and calculates as(10)Lθ=gδθ,∀Cθ,x∈CgidKθ,x=gφxZ⟶φx⋅δθ,Kθ,x′=gP⟶x′⋅δθ,K^θ,i=gskθgaδθ∏j=1vlhkjlδθl∈1,lenS.After interacting witht AAs, the user constructs the secret key as(11)L=∏θ=1tLθ∏ξ=1,ξ≠θtaidξ/aidξ−aidθ=g∑θ=1tδθ⋅∏ξ=1,ξ≠θtaidξ/aidξ−aidθ.For allCθ,x∈Cgid, we have(12)Kx=∏θ=1tKθ,xZ⟶φx⋅δθ∏ξ=1,ξ≠θtaidξ/aidξ−aidθ=gφxZ⟶φx∑θ=1tδθ∏ξ=1,ξ≠θtaidξ/aidξ−aidθ,Kx′=∏θ=1tgP⟶x′⋅δθ∏ξ=1,ξ≠θtaidξ/aidξ−aidθ=gP⟶x′⋅∑θ=1tδθ∏ξ=1,ξ≠θtaidξ/aidξ−aidθ,K^l=∏θ=1tK^θ,l∏ξ=1,ξ≠θtaidξ/aidξ−aidθ=∏θ=1tgskθgaδθ∏j=1vlhkjlδθ∏ξ=1,ξ≠θtaidξ/aidξ−aidθ.For simplicity, we makeu=∑θ=1tδθ⋅∏ξ=1,ξ≠θtaidξ/aidξ−aidθ. For this, the secret key of the user can be represented as(13)S,L=gu,∀Cx∈CgidKx=gφx⋅Z⟶φxu,Kx′=gP⟶x′⋅u,K^l=gα⋅gau⋅∏j=1vlhkjlul∈1,lenS.(6)
Decryptpp,SKgid,CT⟶m/⊥: the decryption algorithm can successfully be invoked by the user with a valid identity. Namely, the user can download encrypted data from the edge infrastructures, and they can decrypt data successfully if their case set Cgid satisfies access policy and the requirement of cumulative weight.Suppose that the ciphertextCT is encrypted under the access policy A,ρ. We recall the definition of LSSS. Let I⊂1,2,…,ℓ represent a case such that ρi∈Cgid. To decrypt the ciphertext, the user with SKgid computes ωi∈Zpi∈I; if λi is valid share corresponding access policy A,ρ, then the secret s=∑i∈Iωiλi can be calculated. To summarize, the decryption process is as follows:(14)∏i∈IeCi′,L⋅eCi,Kρi⋅eC0′,Kρi′eCi′,Kρiωi=∏i∈Iegaλi⋅g−P⟶ρi′⋅s,gu⋅egaλi⋅g−φρiP⟶ρis,gφρi⋅Z⟶ρiu⋅egs,gP⟶ρi′⋅uegaλi⋅g−P⟶ρi′⋅s,gφρi⋅Z⟶φρiuωi=∏i∈Iegaλi,gu⋅g−φρiP⟶ρis,gφρi⋅Z⟶ρiueg−P⟶ρi'⋅s,gφρi⋅Z⟶φρiuωi=eg,gasu.Define setW=T∩SC⊨A. For each w∈W, let wT and wS denote the index w in set T and S, respectively. Then, compute(15)J=∏w∈WeC0′,K^wSeC^wT,L1/W=∏w∈Wegs,gα⋅gau∏j=1lenwhwjue∏j=1lenwhwjs,gu1/W=∏w∈Wegs,gα⋅gau1/W=eg,gαs⋅eg,gasu.The user can recover the plaintextm from the following equation:(16)m=C0⋅eg,gasuJ.


## 4.3. MA-CE-Root Equality Scheme

Here, we provide our second scheme, which needs all the roots (or cases) of each polynomial (or criterion) to be held by the user.(1)
Global Setup1λ⟶pp: this algorithm is similar to scheme MA-CE-Verify Root. CA runs G1λ to obtain GP=G,GT,e,g,p and defines the criterion universe U with size n. CA also generates unique identity for AAs and users, respectively. Then, it chooses a threshold t and picks φii∈1,n∈RZp. Note that φi is not used to label the polynomial Pi. It outputs public parameter pp=GP,n,t,φii∈1,n,nθ.(2)
AA Setuppp⟶pkθ,skθ: the algorithm is similar to the AA Setup in the first scheme. For each authority AAθ, it inputs the public parameter pp and returns a pair of keys pkθ,skθ, where skθ is kept secret for other AAs.(3)
CA Setuppp,pkθθ∈1,nθ,d⟶PK,MSK: CA randomly chooses t public keys from nθ AAs. In addition, it picks h1,…,hn∈RG and calculates(17)eg,gα=∏θ=1tpkθ∏ξ=1,ξ≠θtaidξ/aidξ−aidθ.Then, CA randomly picksa∈Zp and computes ga. For i=1 to n, it picks a set of d-degree polynomials Pii∈1,n, which can be described as(18)P⟶1=1,a1,d−1a1,d,…,a1,0a1,d,P⟶2=1,a2,d−1a2,d,…,a2,0a2,d,P⟶n=1,an,d−1an,d,…,an,0an,d.It outputsPK=g,ga,eg,gα,gφiP⟶i,hii∈1,n and keeps the values α,a for secret.(4)
EncryptPK,m,A,ρ,w⟶,τ⟶CT: the encryption algorithm sets the access policy A,ρ, the size of the matrix is ℓ×n, and the function ρ maps Ai to a criterion. Then, it specifies the weight vector w⟶=w1,…,wn, where the element wi represents the weight of each criterion. Moreover, it constructs the vector v⟶=s,r2,r3,…,rn∈Zpn. For i=1 to ℓ, it computes λi=v⟶⋅Mi and set T=k1i,k2i,…,kμii according to the weight threshold τ, where μi indicates the length of i-th subset and kji∈1,2,…,n denotes index in U. Finally, the algorithm computes as(19)C0=m⋅eg,gαs,C0′=gsCi=gaλi⋅g−φρiP⟶ρisi∈1,ℓ,C^i=∏j=1μihkjisi∈1,lenT.It outputs ciphertext asCT=C0,C0′,Cii∈1,ℓ,C^ii∈1,lenT,T.(5)
Key Genpp,PK,gid,Cgid⟶SKgid: the user with gid interacts with any t AAs to obtain the key according to requirements. It takes the set Rootsx=x1,x2,…,xd to represent all the roots of the polynomial at x. According to Vieta’s theorem, AA uses Rootsx to construct the following vector:(20)z⟶φx=1,zxd−1,zxd−2,…,zx0.LetCgid⊆Cxx∈1,n represent the cases belonging to the user with identity gid, set P=P1,P2,…,PlenCgid denote the set of criteria requested by the user, and set S=P1,P2,…,PlenCgid,P1,P2,…,P1,P2,…,PlenCgid=k1l,…,kvll be all combinations of entities in set P, where vl denotes the length of l-th subset and kjl∈1,n denotes index in U. AAθ picks δθ∈RZp and calculates as(21)Lθ=gδθ,∀Cθ,x∈CgidKθ,x=gφxZ⟶φx⋅δθK^θ,l=gskθgaδθ∏j=1vlhkjlδθl∈1,lenS.After interacting witht AAs, the user constructs the secret key SKgid as follows:(22)L=gu,∀Cx∈CgidKx=gφxZ⟶φx⋅uK^l=gαgau∏j=1vlhkjlul∈1,lenS.(6)
Decryptpp,SKgid,CT⟶m/⊥: to recover the encrypted data under access policy A,ρ, the user first calculates constants ωi∈Zpi∈I and then computes(23)∏i∈IeCi,L⋅eC0′,Kρiωi=∏i∈Iegaλi⋅g−φρiP⟶ρis,gu⋅egs,gφxZ⟶φx⋅uωi=∏i∈Iegaλi,guωi=eg,gasu.Forw∈W=T∩SC⊨A, the symbols wT and wS denote the index w in set T and S, respectively; then, compute(24)J=∏w∈WeC0′,K^wSeC^wT,L1/W|=egs,gα⋅gauW/W=eg,gαs⋅eg,gasu.The user can recover the plaintextm=C0⋅eg,gasu/J.


## 5. Security Proof

To prove the security of our constructions, the theorem in [8] is introduced as shown below.Theorem 1.
If the decisional q-BDHE assumption holds, then any polynomial-time adversary cannot selectively break the MA-CE-Verify Root scheme with a challenge matrix of sizeℓ∗×n∗, where n∗≤q.Here, we briefly overview the proof technique under the decisional q-BDHE assumption. Suppose that there exists an adversaryA with a nonnegligible advantage ε can selectively break the proposed scheme. A is allowed to select a matrix with the size of at most q×q. Here, the restriction is that the key queried from the challenger cannot decrypt the message. Then, we construct a PPT simulator B, which solves the q-BDHE assumption.Init. ℬ first receipts the q-BDHE challenge y⟶=g,gs,g1,…,gq,gq+2,…,g2q and T˜. Then, A sends the challenge structure A∗,ρ∗, a weight vector w⟶∗=w1,w2,…,wmm∈1,n, and a weight threshold τ∗ to ℬ.Setup. In this phase, ℬ picks α′∈RZp and implicitly takes α=α′+aq+1 by making eg,gα=ega,gaq⋅eg,gα′. Then, ℬ randomly generates φx for polynomial Px. The symbol Φ represents the collection of indexes i, such that ρ∗i=Px. Next, ℬ takes(25)ψx=gφxP⟶x∏i∈ΦgaAi,1∗⋅ga2Ai,2∗⋯gan∗⋅Ai,n∗∗,βx=gP⟶x′∏i∈ΦgaAi,1∗⋅ga2Ai,2∗⋯gan∗⋅Ai,n∗∗,γx=gφx∏i∈ΦgaAi,1∗⋅ga2Ai,2∗⋯gan∗⋅Ai,n∗∗.We note thatψx=gφxP⟶x, βx=gP⟶x′ and γx=gφx if Φ=∅. Finally, ℬ chooses η1,η2,…,ηn∈RZp and computes(26)hj=gηj/σ,ifPxhas  combination≤τ∗,gηj,otherwise,which implicitly takes σ=w1+w2+⋯+wm.Phase 1. ℬ replies private key queries for C=zφx, where C cannot satisfy A∗,ρ∗. For each zφx, ℬ first creates vector z⟶φx=zφxd,zφxd−1,…,zφx,1 and chooses r∈RZp. Then, according to the definition of LSSS, ℬ calculates a vector ω⟶=ω1,ω2,…,ωn∗∈Zpn∗ such that ω1=−1. For all i such that ρ∗i∈S, we have that the inner product ω⟶,Ai∗=0. Finally, ℬ implicitly defines u as(27)u=r+ω1aq+ω2aq−1+⋯+ωn∗aq−n∗+1.Therefore, the valueL can be denoted as(28)L=gr∏i=1n∗ga−i+1ωi=gu.We now considerzφx∈S for the case that there is no i such that ρ∗i has a root equal to zφx. ℬ can simply take Kx=Lφxz⟶φx. Otherwise, it calculates as(29)Kx=gφx∏i∈ΦgaAi,1∗⋅ga2Ai,2∗⋯gan∗Ai,n∗∗z⟶φxu.Note that by definingu, Kx has the form of Ai,j∗ajwjaq−j+1 in the exponent for some j. However, we have that w⟶,Ai∗=0, and the term of gaq+1 can be cancelled. Consequently, Kx can be expressed as(30)Kx=gφx∏i∈ΦgaAi,1∗⋅ga2Ai,2∗⋯gan∗Ai,n∗∗z⟶φxu=Lφxz⟶φx∏i∈Φ∏j=1n∗gaj⋅r⋅∏k=1,k≠jn∗gaq+j−k+1Ai,j∗.We now consider simulating the value ofK^l. Let P=P1,P2,…,PlenCgid be the set of criteria corresponding to the criterion universe U and S=k1l,…,kvlll∈1,2lenCgid be all combinations of entities in set P. For l=1 to 2lenCgid, we have(31)K^l=gαgau∏j=1vlgηkju=gα′⋅gau⋅gar⋅gaq+1w1⋅gaqw2⋯gaq−n∗+2wn∗⋅L∑j=1vlηkj=gα′⋅gar⋅gaqw2⋯gaq−n∗+2wn∗⋅L∑j=1vlηkj=gα′⋅gar∏l=2n∗gaq−l+2wl⋅L∑j=1vlηkj.Otherwise, we have(32)K^l=gαgau∏j=1vlgηkjt/σ=gα′⋅gaq+1⋅gar⋅gaq+1w1⋅gaqw2⋯gaq−n∗+2wn∗L∑j=1vlηkj/σ=gα′⋅gar⋅∏l=2n∗gaq−l+2wlL∑j=1vlηkj/σ.Challenge. We show how to build challenge ciphertext. A submits two messages m0 and m1 to ℬ. The simulator ℬ selects b∈0,1 at random and constructs C0=mb⋅T˜⋅egα′,h, C0′=h. Then, it picks y2′,y3′,…,yn∗′∈RZp and secret s using the vector(33)v⟶=s,sa+y2′,sa2+y3′,…,san−1+yn∗′∈Zpn∗.Finally,ℬ chooses threshold value τ∗ and performs Encrypt algorithm to construct Ci, Ci′, and C^i as follows:(34)Ci=gav⟶Ai∗⋅g−φiP⟶is=gsaAi,1∗⋅gsa2+ay2′Ai,2∗⋯gsan∗+ay2′Ai,n∗∗⋅gs−φiP⟶i⋅gaAi,1∗⋅ga2Ai,2∗⋯gan∗−s=gs−φiP⟶i∏j=1n∗gaAi,j∗yj′,Ci′=gav⟶Ai∗⋅g−P⟶i′s=gsaAi,1∗⋅gsa2+ay2′Ai,2∗⋯gsan∗+ay2′Ai,n∗∗⋅gs−P⟶i′⋅gaAi,1∗⋅ga2Ai,2∗⋯gan∗−s=gs−P⟶i′∏j=1n∗gaAi,j∗yj′,C^i=∏j=1μiℬkjisi∈1,lenT.Phase 2. A can adaptively make queries the same as Phase 1 with the restriction that none of those cases satisfy the access structure corresponding to the Challenge phase.Guess. The adversary A eventually outputs a guess bit b′∈0,1 of b. If A correctly guesses b′=b, then ℬ returns 0 to guess that T˜=eg,gaq+1s; otherwise, it outputs 1 to demonstrate that it considers T˜ is a random element obtained from group GT. When T˜ is a tuple, the simulator ℬ performs a perfect simulation. In this case, we have that(35)Prℬy⟶,T˜=eg,gaq+1s=0=12+AdvA.WhenT˜ is a random element in GT, ℬ simulates a completely random challenge ciphertext for adversary A, and we have(36)Prℬy⟶,T˜=R=0=12.Consequently,ℬ can play the decisional q-BDHE game with non-negligible advantage.Theorem 2.
If the decisional q-BDHE assumption holds, then no polynomial-time adversary can selectively break our MA-CE-Root Equality scheme with a challenge matrix of sizeℓ∗×n∗, where n∗≤q.The proof of this theorem is similar to Theorem1 (here we omit the proof process).


## 6. Performance Analysis

We now provide theoretical analysis and implementation evaluation of the two schemes in this section.


### 6.1. Theoretical Analysis

There is the comparison of the four schemes, including [12–14] and our two schemes, in terms of storage overhead and computation cost. Let ℙ indicate a pairing operation. E and ET denote an exponential operation of group G and GT, respectively. g and gT represent the size of elements in group G and GT, respectively. In our schemes, N represents the size of the criterion universe, while it represents attribute universe in [12–14]. nℓ and nu denote the number of criteria (or attributes) in the access matrix and the number of criteria that are satisfied by the user, respectively. Let na denote the number of attributes managed by attribute authority. l is the number of all criterion sets with cumulative weight greater than τ. lw is the size of the criterion set that satisfies the access policy and cumulative weight.We first compare the storage overhead of the four schemes, as shown in Table1. In terms of ciphertext size, our schemes are better than [12–14], since they require storing a large amount of leaf nodes information of the access tree. It can be observed that [13] is superior to our schemes in terms of key size and public key size. The reason is that the public key in our schemes needs to contain information corresponding to the criterion. All weights are specified by the trusted authority TA in [13]. Different from [13], the Key Gen phase of our schemes requires enumerating the criterion set that exceeds the weight. The performance of our schemes in terms of key size is comparable to that of [14]. However, the scheme in [14] cannot support multiple authorities, and the weight of each attribute is specified by TA. This inevitably limits the ability of the scheme in practical scenarios.Table 1
Comparison of storage overhead.
SchemesPK sizeCiphertext sizeKey sizeLMX13 [12]2N+2g+gT4nℓ+4g+gT7nugWZZ14 [13]N+2g+gTnℓna+1g+gTnu+1gYYZ20 [14]N+2g+gT3nℓ+2g+gT2nu+4Our scheme-13N+2g+gT2nℓ+lg+gT2nu+l+1gOur scheme-22N+2g+gTnℓ+lg+gTnu+l+1gTable2 shows the computation cost of these schemes in Key Gen, Encrypt, and Decrypt phases. In the Key Gen phase, the scheme in [13] performs better than other schemes, because the calculation of all the criterion sets takes up the main computation cost in our schemes and the scheme of [12]. In Encrypt and Decrypt phases, our schemes cost less time than [13] in practical application, since the computation cost of the latter is occupied by a large number of exponential and pairing operations. Moreover, it can be seen that the performance of [14] is similar to our first scheme and slightly inferior to the second scheme. The advantage of our schemes is that users can flexibly choose the weights in the access policy according to different application scenarios.Table 2
Comparison of computation cost.
SchemesKeyGenEncryptDecryptLMX13 [12]7nuEET+4nℓ+4E+ℙ5nu+1ℙWZZ14 [13]nu+1EET+nℓna+1E+ℙnulw+1ℙYYZ [14]2nu+4EET+3nℓ+2E+ℙ3nu+1ℙOur scheme-12nu+l+1EET+4nℓ+l+1E+ℙ4nu+2lwℙOur scheme-2nu+l+1EET+2nℓ+l+1E+ℙ2nu+2lwℙ


### 6.2. Implementation and Evaluation

We implement the proposed schemes in Charm [32] using Python 3.6.5. The programs adopt the Pairing-Based Cryptography (PBC) library version-0.5.14. We pick the symmetric curve with a 512 bit base field, and it provides 160 bit group order. All our programs were executed on VMware @ Workstation Pro 15.5.5 with a dual core Intel (R) Core (TM) i7-7700HQ CPU @2.8 GHz and 2.0 GB RAM running Ubuntu 18.04. All experimental results are taken from the average value of the program executed 20 times.Figure3 shows the value of key generation time with threshold tt=1,2,…,10. We set the number of AAs to 10 in the system. As known from the figure, with the increase of threshold t, the time consumed for key generation is fixed basically, due to the fact that the user requests keys from t AAs in the meantime, while the time consumption of each AA for calculating subshare of a key is almost the same. Moreover, the value of t is generally within 10 in actual application scenarios. In summary, it can be considered that the time consumption is hardly affected by the threshold t in the KeyGen phase.Figure 3
The value of key generation time with thresholdt.Figure4 shows the time consumption of Key Gen, Encrypt, and Decrypt algorithms as the number of user attributes increases in the proposed schemes. We take the number nθ of AAs as 10 and the threshold τ as 6. The performance of scheme-2 is slightly better than scheme-1 because the former has shorter ciphertext and key, which reduces exponential and pairing operations. We observe that the time consumption of each stage shows a nonlinear increasing trend. What mainly affects computational efficiency are summarized as follows. The first aspect is that the encryption algorithm needs to calculate all cases T that exceed the cumulative threshold τ. Another reason is that calculating the criteria set S that belong to the user dominates the execution time of the key generation algorithm (see Section 4 (Key Gen)). In addition, it takes a relatively long time to evaluate the intersection of set T and S in the decryption phase. Nevertheless, our schemes enjoy tolerable computational efficiency for the following reasons. Clearly, the time consumption does not exceed 130 ms in all phases. To be precise, when a user owns 30 attributes, the time consumption of the first scheme is 123 ms, while that of the second scheme is 120 ms. Therefore, the efficiency of our proposed schemes is acceptable in practical scenarios. Furthermore, we remark that in the IoT scenario, the relatively intensive computation can be offloaded to some outsourced equipment, and the rest of the operations remain on the receiver.Figure 4
Time cost of the two proposed schemes.
(a)(b)


## 6.1. Theoretical Analysis

There is the comparison of the four schemes, including [12–14] and our two schemes, in terms of storage overhead and computation cost. Let ℙ indicate a pairing operation. E and ET denote an exponential operation of group G and GT, respectively. g and gT represent the size of elements in group G and GT, respectively. In our schemes, N represents the size of the criterion universe, while it represents attribute universe in [12–14]. nℓ and nu denote the number of criteria (or attributes) in the access matrix and the number of criteria that are satisfied by the user, respectively. Let na denote the number of attributes managed by attribute authority. l is the number of all criterion sets with cumulative weight greater than τ. lw is the size of the criterion set that satisfies the access policy and cumulative weight.We first compare the storage overhead of the four schemes, as shown in Table1. In terms of ciphertext size, our schemes are better than [12–14], since they require storing a large amount of leaf nodes information of the access tree. It can be observed that [13] is superior to our schemes in terms of key size and public key size. The reason is that the public key in our schemes needs to contain information corresponding to the criterion. All weights are specified by the trusted authority TA in [13]. Different from [13], the Key Gen phase of our schemes requires enumerating the criterion set that exceeds the weight. The performance of our schemes in terms of key size is comparable to that of [14]. However, the scheme in [14] cannot support multiple authorities, and the weight of each attribute is specified by TA. This inevitably limits the ability of the scheme in practical scenarios.Table 1
Comparison of storage overhead.
SchemesPK sizeCiphertext sizeKey sizeLMX13 [12]2N+2g+gT4nℓ+4g+gT7nugWZZ14 [13]N+2g+gTnℓna+1g+gTnu+1gYYZ20 [14]N+2g+gT3nℓ+2g+gT2nu+4Our scheme-13N+2g+gT2nℓ+lg+gT2nu+l+1gOur scheme-22N+2g+gTnℓ+lg+gTnu+l+1gTable2 shows the computation cost of these schemes in Key Gen, Encrypt, and Decrypt phases. In the Key Gen phase, the scheme in [13] performs better than other schemes, because the calculation of all the criterion sets takes up the main computation cost in our schemes and the scheme of [12]. In Encrypt and Decrypt phases, our schemes cost less time than [13] in practical application, since the computation cost of the latter is occupied by a large number of exponential and pairing operations. Moreover, it can be seen that the performance of [14] is similar to our first scheme and slightly inferior to the second scheme. The advantage of our schemes is that users can flexibly choose the weights in the access policy according to different application scenarios.Table 2
Comparison of computation cost.
SchemesKeyGenEncryptDecryptLMX13 [12]7nuEET+4nℓ+4E+ℙ5nu+1ℙWZZ14 [13]nu+1EET+nℓna+1E+ℙnulw+1ℙYYZ [14]2nu+4EET+3nℓ+2E+ℙ3nu+1ℙOur scheme-12nu+l+1EET+4nℓ+l+1E+ℙ4nu+2lwℙOur scheme-2nu+l+1EET+2nℓ+l+1E+ℙ2nu+2lwℙ


## 6.2. Implementation and Evaluation

We implement the proposed schemes in Charm [32] using Python 3.6.5. The programs adopt the Pairing-Based Cryptography (PBC) library version-0.5.14. We pick the symmetric curve with a 512 bit base field, and it provides 160 bit group order. All our programs were executed on VMware @ Workstation Pro 15.5.5 with a dual core Intel (R) Core (TM) i7-7700HQ CPU @2.8 GHz and 2.0 GB RAM running Ubuntu 18.04. All experimental results are taken from the average value of the program executed 20 times.Figure3 shows the value of key generation time with threshold tt=1,2,…,10. We set the number of AAs to 10 in the system. As known from the figure, with the increase of threshold t, the time consumed for key generation is fixed basically, due to the fact that the user requests keys from t AAs in the meantime, while the time consumption of each AA for calculating subshare of a key is almost the same. Moreover, the value of t is generally within 10 in actual application scenarios. In summary, it can be considered that the time consumption is hardly affected by the threshold t in the KeyGen phase.Figure 3
The value of key generation time with thresholdt.Figure4 shows the time consumption of Key Gen, Encrypt, and Decrypt algorithms as the number of user attributes increases in the proposed schemes. We take the number nθ of AAs as 10 and the threshold τ as 6. The performance of scheme-2 is slightly better than scheme-1 because the former has shorter ciphertext and key, which reduces exponential and pairing operations. We observe that the time consumption of each stage shows a nonlinear increasing trend. What mainly affects computational efficiency are summarized as follows. The first aspect is that the encryption algorithm needs to calculate all cases T that exceed the cumulative threshold τ. Another reason is that calculating the criteria set S that belong to the user dominates the execution time of the key generation algorithm (see Section 4 (Key Gen)). In addition, it takes a relatively long time to evaluate the intersection of set T and S in the decryption phase. Nevertheless, our schemes enjoy tolerable computational efficiency for the following reasons. Clearly, the time consumption does not exceed 130 ms in all phases. To be precise, when a user owns 30 attributes, the time consumption of the first scheme is 123 ms, while that of the second scheme is 120 ms. Therefore, the efficiency of our proposed schemes is acceptable in practical scenarios. Furthermore, we remark that in the IoT scenario, the relatively intensive computation can be offloaded to some outsourced equipment, and the rest of the operations remain on the receiver.Figure 4
Time cost of the two proposed schemes.
(a)(b)


## 7. Conclusion

In this paper, we propose two multi-authority criteria-based encryption schemes that support data access control in IoT and are proved to be secure in the standard model. Specifically, they solve the problem of security bottleneck and server overload caused by involving only a single authority in the phase of key generation. Moreover, each criterion carries a weight specified by the encryptor, which allows the access policy to be expressed more flexibly. The theoretical analysis and simulation evaluation demonstrate that our schemes can conform to the actual application scenarios. The remaining problem is that the time consumption of each phase in the schemes increases nonlinearly, which limits the size of the criterion universe. In future work, we are committed to constructing more lightweight frameworks.



---

*Source: 9174630-2021-07-17.xml*