# A Cheating Detectable Privacy-Preserving Data Sharing Scheme for Cloud Computing

Authors: Xin Wang; Bo Yang; Zhe Xia; Yanqi Zhao; Huifang Yu
Journal: Security and Communication Networks
 (2018)

---

## Abstract

Cloud computing provides a new, attractive paradigm for the effective sharing of storage and computing resources among global consumers. More and more enterprises have begun to enter the field of cloud computing and storing data in the cloud to facilitate the sharing data among users. However, in many cases, users may be concerned about data privacy, trust, and integrity. It is challenging to provide data sharing services without sacrificing these security requirements. In this paper, a data sharing scheme of reliable, secure, and privacy protection based on general access structure is introduced. The proposed scheme is not only effective and flexible, but also is capable of protecting privacy for the cloud owner, supporting data sharing under supervision, enabling accountability of users’ decryption keys, and identifying cheaters if some users behave dishonestly. Security analysis and efficiency analysis demonstrate that our proposed scheme has better performance in computational costs compared with most related works. The scheme is versatile to be used in various environments. For example, it is particularly suitable to be employed to protect personal health data and medical diagnostic data in information medical environment.


---

## Body

## 1. Introduction

At present, new technologies and new industries emerge in an endless stream based on big data and cloud computing. Data production, management, and emerging business models based on big data are springing up. In recent years, with the transformation of large number of businesses into digitalization and informatization, mass data is constantly being manufactured and consumed, which promotes the rapid development of big data technology in research, development, and application. In the context of this industry, the quantity and quality of data become extremely important. Cloud computing provides a new and appealing paradigm to share the resources of storage and computation efficiently among the global consumers. Compared with the traditional data storage methods, cloud users can more conveniently access the data without considering the arrangement of the hardware or infrastructure by data storing and sharing on cloud. However, the cloud presents the value attraction for its huge functionality and convenience, and it brings a lot of new challenge. One reason is that the data owner has lost the physical control on the data when he stored the data on the cloud, and meanwhile, the cloud server is faced to the public. Hence, the owner’s data may be subjected to various kinds of threats and malicious attacks. For instance, the data’s confidentiality requirement may be disobeyed by some clouds for financial purposes, or they may even sell their business competitors confidential information. Thus, although cloud computing is very attractive to enterprises and consumers by economically sharing massive data among the users, it may fail to guarantee data storage security and privacy to individual of the data owner. Furthermore, in some uses, after the data possessor has put out his encrypted data to the cloud, he may yet wish to keep the data’s some controls, for example, update the data or revoke the access rights for some other users [1]. In consequence, many recent works have devoted to guarantee security and privacy using remotely storing the shared data and in the meantime assuring the desirable security characteristics. In 2010, the first scheme achieving secure data access control with provable security in cloud storage has been proposed by Yu et al. [2], using key-policy attribute-based encryption and symmetric encryption (KP-ABE) [3]. The scheme can reach fine-grained data access by combing KP-ABE with proxy reencryption (PRE) and lazy reencryption. The scheme’s performance still needs to be improved, though a part of the private key update calculation can be put out to the cloud. Dong et al. subsequently give a scheme [4] employing symmetric encryption with ciphertext-policy attribute-based encryption [5, 6] (CP-ABE). To sum up, regarding the employed technologies, KP-ABE or CP-ABE has either been used by these above schemes under the symmetric encryption to design data security secure access control. Some other design methods are based on hierarchical identity-based encryption (HIBE) [7], but they have appealed to less attention. These schemes have simply considered how to supply data privacy against the cloud, but they do not have the preservation of private information of owner and the possible dishonest behaviors by some authorized users when storing the data in cloud. For instance, some authorized users may provide fake share deliberately to cause decryption failure. In the personal health medical information surroundings, some extra security demands are required. Since in certain special circumstances, such as medical accidents, abnormal deaths, and traffic accidents, medical disputes claim should be considered. In these situations, while medical evidence is needed, electronic medical records of the patient should be able to be right decrypted by the authorized users. Assuming someone has had an accident or been killed in serious incidents. In case supposing that there are disputes, historic records of the users will be the crucial evidences and they need to be recovered for expert testimony. These existing schemes, however, focus on the confidentiality and privacy of the data itself and the cost of performance mainly, but they are not suitable for medical records scenarios’ needs. To realize an effectual, scalable, and privacy-preserving data sharing service in the cloud, the following requirements should be consequently satisfied:(1) the data owner can authorize who can access the data, and the authorized users should be able to get to shared data in the cloud under the constraints that are defined by the data owner;(2) the cloud needs to be able to give support to dynamic requirements so that data owners can update the data file and add or revoke users;(3) when data owner stores his information on the cloud without suitable protection, the data are readable by anyone since the cloud is publicly accessible. The personal private information, for example, their medical information and users’ telephone number, consequently needs to be protected against the cloud, and it should not be made public;(4) the data decryption operation should be carried out under mutual supervision, and the dishonest users need to be identified if they submit false shares. How to settle the above important issues has not been considered in cloud that computes yet, although a number of schemes have been proposed in the literature.In this paper, we propose an effective, scalable and flexible privacy-preserving data sharing scheme to ensure semantic security and effective utilization of owner’s data. In order to preserve the privacy of owner’s sensitive information that may be unrelated to the data itself, Bloom filter hash function is used to hide data storage in cloud. The scheme employs secret sharing based on general access structure to preserve confidentiality of the owner’s data against the cloud. In addition, Reed-Solomon (RS) encoding technique has been adopted to identify the dishonest user who presents a false share. In the proposed scheme, all authorized users are divided into groups by their identity when they register themselves with the protocol. Each data file is described by a set of group secrets, and for every group, such asUk, has been assigned one master key αk so that the data file can be successfully decrypted when these group secrets are correctly recovered. In addition, each cloud user is assigned into a group and every group secret is shared among the group users by utilizing secret sharing of general access structure.To ensure correct sharing of the secret, this scheme defines a public-private key pair for each user. By combing secret sharing access structure and user’s public key, the share or secret key is sent to user in every group. Therefore, each user could get a different key and he can check this share key by his private keydIDi→j. The secret keys of group users are defined to reflect their group access privileges, so that all of the users should present their correctly shared keys without cheating. RS encoding technique is used to enable the identification of the cheater when he provided a fake share.In the proposed protocol, the secret is shared among multiple participants, and only a quorum of these participants work together can recover the secret. In an ideal secret sharing, the secret share held by each participant has exactly the same size as the secret, and the size of all secret shares together is proportional to the number of the participants. Therefore, when considering the protocol as a whole, more information needs to be dealt with, but each participant’s task remains the same. The benefit is that the secrecy and availability of the secret key are enhanced. Suppose the adversary wants to learn the secret key or destroy it. She needs to compromise multiple participants to achieve her objective instead of compromising a single one in the traditional protocols.Compared with the existing schemes, our analysis shows that the proposed scheme provides the following benefits regarding both security and efficiency:(1) The cloud server can assist search record by data file tag and it can learn nothing about owner’s data in plaintext and owner’s personal sensitive information.(2) The user who can access the data file is authorized by the data owner, and he can verify the secret key sent by the owner.(3) The dishonest cloud users who present fake decryption keys can be identified, so that the ciphertext can be safely and correctly decrypted under the supervision of these users.The rest of this paper is organized as follows. The preliminaries are briefly described in Section2. Section 3 discusses system models and security requirement. Our proposed scheme is introduced in Section 4, and its security is analyzed in Section 5. Efficiency analysis as well as its comparison with the related existing schemes is presented in Section 6. Finally, we present an example of the practical impact of our work and conclude this paper in Sections 7 and 8, respectively.


## 2. Preliminaries

### 2.1. Bilinear Maps

LetG1 and G2 be two multiplicative cyclic groups with prime order p and g be a generator of group G1. Moreover, let e:G1×G1→G2 be the bilinear map that satisfies the following properties:(1)
Bilinearity: for alla and b there must be ega,gb=eg,gab.(2)
Nondegeneracy: there must beeg,g≠1.


### 2.2. Secret Sharing Schemes

Secret sharing schemes (SSS) [8] are used to divide a secret among a number of parties. The value given to a party is called the share (of the secret) for that party. Every SSS realizes some access structure that defines the sets of parties who should be able to reconstruct the secret using their shares.


### 2.3. Access Structure and Monotone Span Programs

Definition 1 (access structure [9, 10]).
LetP1,P2,⋯,Pn be a set of parties. A collection A⊆2P1,P2,⋯,Pn is monotone for ∀B,C: if B∈A and B⊆C, then C∈A. An access structure (respectively, monotone access structure) is a collection (respectively, monotone collection) A of nonempty subsets of P1,P2,⋯,Pn; i.e., A⊆2P1,P2,⋯,Pn∖⌀. The sets in A are called the authorized sets; otherwise, they are called the unauthorized sets.In a linear secret sharing scheme [9], to realize an access structure A, the dealer who possesses the secret y can distribute these shares of y to a number of parties such that y can be reconstructed by a linear combination of these shares of any authorized set. However, an unauthorized set can obtain no information about the secret y.There is a close relationship between linear secret sharing scheme and a linear algebraic model called monotone span programs (MSP) [11]. It has been shown that the existence of a linear secret sharing scheme for some access structure is equivalent to the existence of a monotone span program for that access structure.Definition 2 (monotone span program).
LetK be a field and x1,⋯,xn be a set of variables. A monotone span program over K is a labeled matrix M^M,ρ where M is a matrix over K and ρ is a labeling of the rows of M by literals from x1,⋯,xn (every row is labeled by one literal).A monotone span program accepts or rejects an input by the following criteria. For every input setγ of literals, let Mγ be the submatrix composing of those rows whose labels are in γ. The monotone span program M^ accepts γ if and only if 1→∈spanMγ.


### 2.4. Bloom Filter

Bloom filter (BF) [12] is a simple and effective random data storage structure. It is constructed by a set of hash functions BFx=h1x,⋯,hkx and it has two operations: addx and queryx, where x indicates Tagowner in the proposed scheme. The addx operation handles an element with multiple hash functions h1·,⋯,hk·, so that the element is uniformly mapped to a number, for example, hix=yi∈1:m, and sets the yi-th bit in the array to be one (the array is initialized to zeroes). The queryx operation repeats the same hashing procedure and then checks if the appropriate bits are set as 1. In 2012, the partially hidden access structure in ABE was proposed [13, 14]. In addition, the Bloom filter was employed to hide the value of the attribute in partially hidden access structures in [15]. In this proposed scheme, we use the Bloom filter to protect the privacy of the data owner as Figure 1.Figure 1
Bloom filter of personal privacy information.In order to prevent the cloud server from learning information that may invade personal privacy, like name, mobile number, and home address, each attribute information is split into two parts: an attribute name and its value. The general attribute name is made public while the personal privacy information’s specific attribute values are kept secret, when the data file is stored in the cloud server. For example, let the data owner’s name be Alice, the phone number be 1-626-780-7552, and home address be11ndStreet,Brooklyn,NewYork. Then, let the general attribute name of personal information to be protected be AttNameowner=Name,Occupation,TelephoneNumber,Address, then the owner’s specific values is AttValueowner=AliceLawyer1-626-780-755211ndStreet,Brooklyn,NewYork. The data owner builds the data file label Tagowner=HAttValueowner and then constructs a Bloom filter BFdatafile=BFTagowner using Tagowner. In Figure 1, let x=HAttValueowner.To check whether a Tag is in setS that is stored in the cloud, we should firstly compute the values h1Tag,h2Tag,⋯,hkTag, and verify if each hiTag is 1, where i∈1~k. If the check fails, we can insure that Tag is not in S. Otherwise, we say that Tag is in S with a high probability, because the bloom filter has always a false positive rate. The false positive rate will be analyzed in detail in Section 6. The Bloom filter has an attractive feature of convenient query and concise space. When applying standard Bloom filter, there is a necessity to do k hash operations, where the time complexity to insert one element is Ok. When determining whether an element is in the set, the k hash calculation is also needed. In addition, it needs the time complexity Ok to finish an element query. For a set with n elements, it just needs a bit array with size m, so the space complexity is Om. It is then very concise to use only m/n bits to save each element. The storage space of the traditional tree query algorithm and hash query algorithm is directly associated with the size of the element itself and the size of the set, while the Bloom filter query algorithm is independent of the number of the elements and it is simply connected the number of the vector’s bits, where the mapping comes from the element to the vector.


### 2.5. Reed-Solomon Code

In coding theory, RS code could detect and correct a number of random information errors. McEliece and Sarwate [16] pointed out that Shamir’s Secret Sharing Scheme (SSS) is closely related to the RS error correction. They observed that a list of shares of Shamir’s k,n threshold SSS forms a codeword of RS code. Thus, if k+2t shares containing t invalid shares are provided in the reconstruction phase, the secret reconstruction algorithm can identify all t cheaters with certain probability. In addition, it is obvious, by using Lagrange interpolation, that a polynomial fx of degree k-1 is uniquely determined by f1,⋯,fn if and only if n≥k+2t, where t is the number of the cheaters. In 2011, using a single keyed message authentication code, Obana designed an efficient k,n threshold SSS with unconditional security, which is capable of identifying up to t cheaters under the condition k-1/3≥t [17, 18].


## 2.1. Bilinear Maps

LetG1 and G2 be two multiplicative cyclic groups with prime order p and g be a generator of group G1. Moreover, let e:G1×G1→G2 be the bilinear map that satisfies the following properties:(1)
Bilinearity: for alla and b there must be ega,gb=eg,gab.(2)
Nondegeneracy: there must beeg,g≠1.


## 2.2. Secret Sharing Schemes

Secret sharing schemes (SSS) [8] are used to divide a secret among a number of parties. The value given to a party is called the share (of the secret) for that party. Every SSS realizes some access structure that defines the sets of parties who should be able to reconstruct the secret using their shares.


## 2.3. Access Structure and Monotone Span Programs

Definition 1 (access structure [9, 10]).
LetP1,P2,⋯,Pn be a set of parties. A collection A⊆2P1,P2,⋯,Pn is monotone for ∀B,C: if B∈A and B⊆C, then C∈A. An access structure (respectively, monotone access structure) is a collection (respectively, monotone collection) A of nonempty subsets of P1,P2,⋯,Pn; i.e., A⊆2P1,P2,⋯,Pn∖⌀. The sets in A are called the authorized sets; otherwise, they are called the unauthorized sets.In a linear secret sharing scheme [9], to realize an access structure A, the dealer who possesses the secret y can distribute these shares of y to a number of parties such that y can be reconstructed by a linear combination of these shares of any authorized set. However, an unauthorized set can obtain no information about the secret y.There is a close relationship between linear secret sharing scheme and a linear algebraic model called monotone span programs (MSP) [11]. It has been shown that the existence of a linear secret sharing scheme for some access structure is equivalent to the existence of a monotone span program for that access structure.Definition 2 (monotone span program).
LetK be a field and x1,⋯,xn be a set of variables. A monotone span program over K is a labeled matrix M^M,ρ where M is a matrix over K and ρ is a labeling of the rows of M by literals from x1,⋯,xn (every row is labeled by one literal).A monotone span program accepts or rejects an input by the following criteria. For every input setγ of literals, let Mγ be the submatrix composing of those rows whose labels are in γ. The monotone span program M^ accepts γ if and only if 1→∈spanMγ.


## 2.4. Bloom Filter

Bloom filter (BF) [12] is a simple and effective random data storage structure. It is constructed by a set of hash functions BFx=h1x,⋯,hkx and it has two operations: addx and queryx, where x indicates Tagowner in the proposed scheme. The addx operation handles an element with multiple hash functions h1·,⋯,hk·, so that the element is uniformly mapped to a number, for example, hix=yi∈1:m, and sets the yi-th bit in the array to be one (the array is initialized to zeroes). The queryx operation repeats the same hashing procedure and then checks if the appropriate bits are set as 1. In 2012, the partially hidden access structure in ABE was proposed [13, 14]. In addition, the Bloom filter was employed to hide the value of the attribute in partially hidden access structures in [15]. In this proposed scheme, we use the Bloom filter to protect the privacy of the data owner as Figure 1.Figure 1
Bloom filter of personal privacy information.In order to prevent the cloud server from learning information that may invade personal privacy, like name, mobile number, and home address, each attribute information is split into two parts: an attribute name and its value. The general attribute name is made public while the personal privacy information’s specific attribute values are kept secret, when the data file is stored in the cloud server. For example, let the data owner’s name be Alice, the phone number be 1-626-780-7552, and home address be11ndStreet,Brooklyn,NewYork. Then, let the general attribute name of personal information to be protected be AttNameowner=Name,Occupation,TelephoneNumber,Address, then the owner’s specific values is AttValueowner=AliceLawyer1-626-780-755211ndStreet,Brooklyn,NewYork. The data owner builds the data file label Tagowner=HAttValueowner and then constructs a Bloom filter BFdatafile=BFTagowner using Tagowner. In Figure 1, let x=HAttValueowner.To check whether a Tag is in setS that is stored in the cloud, we should firstly compute the values h1Tag,h2Tag,⋯,hkTag, and verify if each hiTag is 1, where i∈1~k. If the check fails, we can insure that Tag is not in S. Otherwise, we say that Tag is in S with a high probability, because the bloom filter has always a false positive rate. The false positive rate will be analyzed in detail in Section 6. The Bloom filter has an attractive feature of convenient query and concise space. When applying standard Bloom filter, there is a necessity to do k hash operations, where the time complexity to insert one element is Ok. When determining whether an element is in the set, the k hash calculation is also needed. In addition, it needs the time complexity Ok to finish an element query. For a set with n elements, it just needs a bit array with size m, so the space complexity is Om. It is then very concise to use only m/n bits to save each element. The storage space of the traditional tree query algorithm and hash query algorithm is directly associated with the size of the element itself and the size of the set, while the Bloom filter query algorithm is independent of the number of the elements and it is simply connected the number of the vector’s bits, where the mapping comes from the element to the vector.


## 2.5. Reed-Solomon Code

In coding theory, RS code could detect and correct a number of random information errors. McEliece and Sarwate [16] pointed out that Shamir’s Secret Sharing Scheme (SSS) is closely related to the RS error correction. They observed that a list of shares of Shamir’s k,n threshold SSS forms a codeword of RS code. Thus, if k+2t shares containing t invalid shares are provided in the reconstruction phase, the secret reconstruction algorithm can identify all t cheaters with certain probability. In addition, it is obvious, by using Lagrange interpolation, that a polynomial fx of degree k-1 is uniquely determined by f1,⋯,fn if and only if n≥k+2t, where t is the number of the cheaters. In 2011, using a single keyed message authentication code, Obana designed an efficient k,n threshold SSS with unconditional security, which is capable of identifying up to t cheaters under the condition k-1/3≥t [17, 18].


## 3. System Model and Security Goals

### 3.1. System Model

In our system model, there are four participants: data owner, data consumers, cloud server, and public key generator (PKG). The data owner, e.g., the patient, stores his medical data in the cloud. In this way, he can outsource the data maintenance to the cloud. The data consumers download the data file shared by the data owner and decrypt it using their decryption keys. For the sake of simplicity, the data consumers are referred to as users in this paper. When decrypting data file, these users are collaborating with each other. The cloud server offers a high-quality service utilizing a large number of servers. It has considerable storage space and computation power. The data owner can interact with the cloud server dynamically to update or delete his data files. The public key generator maintains the public key infrastructure. It is a trusted third party with responsibility to deliver the decryption key safely from the data owner to the users. This framework for privacy-preserving data sharing in the cloud is shown as in Figure2.Figure 2
The framework for privacy-preserving data sharing service in the cloud.Note that, the communication channels between users and cloud server are secured under existing protocols in the system model.


### 3.2. Adversary Model

The adversary model defines malicious behaviors based on whether they intimidate the confidentiality of the cloud data. In contrast, the cloud server in our model is semitrusted (also known as honest-but-curious or passive. In other words, it will follow the protocol most of the time). The cloud server is assumed not to collude with the cloud user. Note that although the semitrusted adversary model is weaker than the malicious model, it is a realistic model that is widely used in similar protocols.We have made it clear that the cloud server is semitrusted in our adversary model. This implies that the cloud server will not violate from the protocol but may try to learn more information that she is not authorized to access. Phishing attack is an important issue that needs to be considered in practice, but we will not address this issue since it is an actively attack. We will further consider this issue in our future works.Hence, the following three types of attackers are considered: (1) data exposure: data owner’s personal sensitive information might be leaked; (2) inner threats: some authorized users might present fake decryption key, causing failure when decrypting the data file; (3) outer threats: the channel that used to transmit the secret keys might be insecure.Different from publicly verifiability [19], the user could verify by himself about the decryption key delivered by the owner, and this property is called secret verifiability.


### 3.3. Design Goals

With the purpose of secure data sharing and data access control in the cloud, our main goal is to minimize the leakage of the data owner’s privacy information and prevent the malicious users from accessing the cloud data, including the deceptive users and collusive users. Then, the main design goals of our system can be summarized as follows.(1  ) Personal Privacy Protection. We use bloom filter to design a secure mechanism so that the data owner and the cloud server can share data through the cloud. The operation only involves some hash operations, so the computational cost is very low.(2  ) Data Access Control and Confidentiality. The proposed scheme employs secret sharing method to share data. The data owner has the authority to specify policy how these cloud users can access the data, and those unauthorized users cannot obtain the information of the data file.(3  ) Secret Verifiability of the Decryption Key. In order to ensure secure communications over insecure channels, the decryption key can be verified by the user himself that it has been correctly delivered by the owner. This property is called secret verifiability, while in publicly verifiability, the key can be verified by anyone who is interesting to.(4  ) Recognition of the Dishonest User. If some cloud users misbehave, they could be efficiently identified using the RS encoding method.


## 3.1. System Model

In our system model, there are four participants: data owner, data consumers, cloud server, and public key generator (PKG). The data owner, e.g., the patient, stores his medical data in the cloud. In this way, he can outsource the data maintenance to the cloud. The data consumers download the data file shared by the data owner and decrypt it using their decryption keys. For the sake of simplicity, the data consumers are referred to as users in this paper. When decrypting data file, these users are collaborating with each other. The cloud server offers a high-quality service utilizing a large number of servers. It has considerable storage space and computation power. The data owner can interact with the cloud server dynamically to update or delete his data files. The public key generator maintains the public key infrastructure. It is a trusted third party with responsibility to deliver the decryption key safely from the data owner to the users. This framework for privacy-preserving data sharing in the cloud is shown as in Figure2.Figure 2
The framework for privacy-preserving data sharing service in the cloud.Note that, the communication channels between users and cloud server are secured under existing protocols in the system model.


## 3.2. Adversary Model

The adversary model defines malicious behaviors based on whether they intimidate the confidentiality of the cloud data. In contrast, the cloud server in our model is semitrusted (also known as honest-but-curious or passive. In other words, it will follow the protocol most of the time). The cloud server is assumed not to collude with the cloud user. Note that although the semitrusted adversary model is weaker than the malicious model, it is a realistic model that is widely used in similar protocols.We have made it clear that the cloud server is semitrusted in our adversary model. This implies that the cloud server will not violate from the protocol but may try to learn more information that she is not authorized to access. Phishing attack is an important issue that needs to be considered in practice, but we will not address this issue since it is an actively attack. We will further consider this issue in our future works.Hence, the following three types of attackers are considered: (1) data exposure: data owner’s personal sensitive information might be leaked; (2) inner threats: some authorized users might present fake decryption key, causing failure when decrypting the data file; (3) outer threats: the channel that used to transmit the secret keys might be insecure.Different from publicly verifiability [19], the user could verify by himself about the decryption key delivered by the owner, and this property is called secret verifiability.


## 3.3. Design Goals

With the purpose of secure data sharing and data access control in the cloud, our main goal is to minimize the leakage of the data owner’s privacy information and prevent the malicious users from accessing the cloud data, including the deceptive users and collusive users. Then, the main design goals of our system can be summarized as follows.(1  ) Personal Privacy Protection. We use bloom filter to design a secure mechanism so that the data owner and the cloud server can share data through the cloud. The operation only involves some hash operations, so the computational cost is very low.(2  ) Data Access Control and Confidentiality. The proposed scheme employs secret sharing method to share data. The data owner has the authority to specify policy how these cloud users can access the data, and those unauthorized users cannot obtain the information of the data file.(3  ) Secret Verifiability of the Decryption Key. In order to ensure secure communications over insecure channels, the decryption key can be verified by the user himself that it has been correctly delivered by the owner. This property is called secret verifiability, while in publicly verifiability, the key can be verified by anyone who is interesting to.(4  ) Recognition of the Dishonest User. If some cloud users misbehave, they could be efficiently identified using the RS encoding method.


## 4. The Proposed Scheme

### 4.1. System Initialization

The public key generator chooses two groupsG1 and G2 of prime order p, two independent generators g,g^, a bilinear map e:G1×G1→G2, and an injective function μ:GFp×1,⋯,n→GFq (for example, μx,y=y-1p+x [18]) and a collision-resistant hash function H·.(1)
User registration: the user registers to the public key generator. He first randomly choosesdID∈Zp∗ as the private key and then computes hID=gdID as the public key.(2)
Here,U denotes the set of users who want to share an owner’s data file. Firstly, the public key generator takes a grouping function φ· and divides these users U into N different groups, such as doctors and nurses, relatives and friends, legal officers, and so on by user’s identity, which are denoted as U1,⋯,UN that satisfy U=U1∪⋯∪UN. Suppose the user ID is partitioned into UφID, where φ· is defined as φID:ID↦1,⋯,N. If φID=k, where k∈1,⋯,N, then the user group UφID is also denoted as Uk for short, namely, the group ID.(3)
PKG takes random exponentsak,αk∈Zp for group Uk(4)
The system public key is published as(1)PK=g,q,μ,H·,eg,gα1,⋯,eg,gαN,ga1,⋯,gaN.MSK=α1,⋯,αN is denoted as the system master key.


### 4.2. Data File Generation (Data File Sharing)

(1)
U k is a partitioned group and the number of the users in the group Uk is lk. The data owner chooses a linear secret sharing access structure and an exponent for every group. For group Uk, the data owner chooses a random secret sharing access structure Mk,ρk, where ρk associates rows of the matrix Mk and ρk,j corresponding to the jth row of Mk. Then it takes random exponents sk∣k∈1,⋯,N. M is the data to be encrypted; the data file is published as(2)C=C0=M·eg,g∑kαk·sk,C1=gs1,⋯,CN=gsN. (2)
In order to protect the private information of the data owner, the data owner computes the data file tagTagowner=HAttValueowner, and then constructs a Bloom filter BFdatafile=BFTagowner by using Tagowner. (3)
The data owner selects a unique ID for this data file and uploads the anonymous data fileBFdatafile,Mk,ρk,C0,Ckk=1~N to the cloud server.Finally, each data file is stored on the cloud in the format as shown in Table1.Table 1
Data file format on the cloud server.
Document number B F d a t a f i l e C 0 = M ⋅ e g , g ∑ k α k ⋅ s k , C 1 = g s 1 , ⋯ , C N = g s N


### 4.3. Key Generation

UserIDi is a user of the universal user set, which is partitioned into group Uk by grouping function φ·. To sign the user IDi in group Uk, if user IDi is the jth in group Uk, then it is denoted as IDi→jUk, for short IDi→j.(1)
As mentioned earlier, the userIDi takes random dIDi∈Zp∗ as private key and computes hIDi=gdIDi as his public key.(2)
The data owner distributes the shared key to userIDi in group Uk.
(a)
Mk,ρk is the secret sharing access structure for group Uk, where Mk=mkijnk×lk. Then the data owner chooses a random vector vk→=sk,y2,⋯,ylk∈Zpn as secret vector, where sk is the encryption exponent to share in the group Uk. Then the share vector is computed as λk1,⋯λkj⋯,λklkT=Mkρk,i→·vφi→T, where Mkρk,i→ is the i-th row vector of the matrix Mk.(b)
The data owner chooses randomtk∈Zp∗ and computes the share key ShIDi→j=hIDiak·λkj,Kk′=gαk·gak·tk,Kk′′=gtk and the share verification ΩIDi→j=σIDi→j1=g^ak·y1,⋯,σIDi→jlk=g^ak·ylk of the key for user IDi→j, where y1=sk.(c)
The data owner takes a random degreet polynomial Rkx∈GFqx and computes RkμShIDi→j,IDi→j, denoted as vRjUk, in short vRIDi→j, with the injective function μ:GFp×1,⋯,n→GFq.(d)
SKi→j=ShIDi→j,Kk′,Kk′′,ΩIDi→j,vRIDi→j is encrypted by the user’s public key, so that only the user can decrypt it by his private key. In other words, the data owner sends the share key SKi→j safely to the user IDi→j by the public key infrastructure.(3)
The user receives theSKi→j and computes the decryption key by his private key dIDi as follows.
(a)
The user first verifiese∏j=1lkσIDi→jjmkij,g=eg^,ShIDi→jdIDi→j-1 with share verification information ΩIDi→j, share key ShIDi→j, and the user’s private key dIDi. The effective of this verification can be proved in Claim 2.(b)
The user then recoversKIDi→j=ShIDi→jdIDi-1=hIDiak·λkj·dIDi-1=gak·λkj from SKi→j by his private key dIDi.(c)
Finally the user computes the decryption keyDKi→j=KIDi→j=gak·λkj,Kk′=gαk·gak·tk,Kk′′=gtk,ΩIDi→j,vRIDi→j.


### 4.4. Decryption of Data File

A k is an authority set of the group Uk and Ak∣Ak⊆Uk,k∈1,⋯,N are the union of the N authority sets for N groups.(1)
These authorized users of theN sets Ak compute the tag Tagowner=HAttValueowner of data file that they want to decrypt and then send it to cloud server.(2)
The cloud server receives the tagTagowner.The cloud server verifies(3)BFh1Tagowner=BFh2Tagowner=⋯=BFhoTagowner=1,using Tagowner provided by these users. If it is satisfied, two decryption approaches can be adopted to get the plaintext: (a) decrypting by these authorized users and (b) outsourcing the decryption to the cloud. We describe them as follows:(a) Decrypting by these authorized users.After the authorized usersAk receive the corresponding data file BFdatafile,Mk,ρk,C0,Ckk=1~N sent by the cloud server, one has the following:(1) All the authority users from those authority setsAk use their decryption keys ShIDi→1,vRIDi→1,⋯,ShIDi→lk,vRIDi→lk to verify the correctness of these decryption keys.Firstly, it is recoveredR^kx from vRIDi→1,⋯,vRIDi→lk using Berlekamp algorithm. Then, the users of the group Uk verify R^kμShIDi→j,IDi→j=vRi→j for every decryption key DKi→j. If it is unequal then ShIDi→j is a fake share key. The user IDi→j is added to the list of cheaters Lk. Moreover, every group can identify the cheaters of the group in this way.(2) If there are no cheaters in all of the authority users, then these authority users recover the blind factor of dataM as follows.Firstly, for every authority set, there exists constantβk∈Zpn satisfying ∑j=1lkλkj·βk=sk, where k=1⋯N. Then, the blind factor of data M is computed as(4)∏k=1NeCk,Kk′∏k=1N∏j=1IDi→j∈AklkeShIDi→j,Kk′′βk=∏k=1Negsk,gαkgak·tk∏k=1N∏j=1IDi→j∈Aklkegak·λkj,gtkβk=∏k=1Negsk,gαk·egsk,gak·tkeg,g∑j=1IDi→j∈Aklkak·λkj·βk·tk=eg,g∑k=1Nαk·skFinally, M=C0/eg,g∑k=1Nαk·sk.(b) Outsourcing the decryption to the cloud.In this situation, these authorized users first generate the transformation keyTKCloudk in groups for the cloud before they are outsourcing the decryption and then obtaining group decryption GKk, where k∈1,⋯,N. To generate TKCloudk and GKk, the authorized user group Ak chooses a random value zk∈Zp and computes the transformation key TKCloudk as TKCloudk=ShIDi→11/zk,⋯,ShIDi→lk1/zk,K′1/zk2,K′′1/zk and outputs the group decryption key GKk=zk, for k∈1,⋯,N. We allow these authorized users themselves to generate the transformation key in group, which is more flexible. Then they send transformation key TKCloudkk=1⋯N to the cloud server for outsourced decryption.The cloud computes the following equation usingTKCloudkk=1~N: (5)C~0=eCk,Kk′1/zk2∏j=1IDi→j∈AklkeShIDi→j1/zk,Kk′′1/zkβk=egsk,gαkgak·tk1/zk2∏j=1IDi→j∈Aklkegak·λkj,gtkβk·1/zk2=egsk,gαk1/zk2·egsk,gak·tk1/zk2eg,g∑j=1IDi→j∈Aklkak·λkj·βk·tk·1/zk2=eg,gαk·sk·1/zk2and then it sends C~0 to the user groups Ak, for k∈1,⋯,N. After receiving C~0, all the user groups Ak compute message M as C0/∏k=1nC~0zk2=C0/∏k=1neg,gαk·sk·1/zk2zk2=M.


## 4.1. System Initialization

The public key generator chooses two groupsG1 and G2 of prime order p, two independent generators g,g^, a bilinear map e:G1×G1→G2, and an injective function μ:GFp×1,⋯,n→GFq (for example, μx,y=y-1p+x [18]) and a collision-resistant hash function H·.(1)
User registration: the user registers to the public key generator. He first randomly choosesdID∈Zp∗ as the private key and then computes hID=gdID as the public key.(2)
Here,U denotes the set of users who want to share an owner’s data file. Firstly, the public key generator takes a grouping function φ· and divides these users U into N different groups, such as doctors and nurses, relatives and friends, legal officers, and so on by user’s identity, which are denoted as U1,⋯,UN that satisfy U=U1∪⋯∪UN. Suppose the user ID is partitioned into UφID, where φ· is defined as φID:ID↦1,⋯,N. If φID=k, where k∈1,⋯,N, then the user group UφID is also denoted as Uk for short, namely, the group ID.(3)
PKG takes random exponentsak,αk∈Zp for group Uk(4)
The system public key is published as(1)PK=g,q,μ,H·,eg,gα1,⋯,eg,gαN,ga1,⋯,gaN.MSK=α1,⋯,αN is denoted as the system master key.


## 4.2. Data File Generation (Data File Sharing)

(1)
U k is a partitioned group and the number of the users in the group Uk is lk. The data owner chooses a linear secret sharing access structure and an exponent for every group. For group Uk, the data owner chooses a random secret sharing access structure Mk,ρk, where ρk associates rows of the matrix Mk and ρk,j corresponding to the jth row of Mk. Then it takes random exponents sk∣k∈1,⋯,N. M is the data to be encrypted; the data file is published as(2)C=C0=M·eg,g∑kαk·sk,C1=gs1,⋯,CN=gsN. (2)
In order to protect the private information of the data owner, the data owner computes the data file tagTagowner=HAttValueowner, and then constructs a Bloom filter BFdatafile=BFTagowner by using Tagowner. (3)
The data owner selects a unique ID for this data file and uploads the anonymous data fileBFdatafile,Mk,ρk,C0,Ckk=1~N to the cloud server.Finally, each data file is stored on the cloud in the format as shown in Table1.Table 1
Data file format on the cloud server.
Document number B F d a t a f i l e C 0 = M ⋅ e g , g ∑ k α k ⋅ s k , C 1 = g s 1 , ⋯ , C N = g s N


## 4.3. Key Generation

UserIDi is a user of the universal user set, which is partitioned into group Uk by grouping function φ·. To sign the user IDi in group Uk, if user IDi is the jth in group Uk, then it is denoted as IDi→jUk, for short IDi→j.(1)
As mentioned earlier, the userIDi takes random dIDi∈Zp∗ as private key and computes hIDi=gdIDi as his public key.(2)
The data owner distributes the shared key to userIDi in group Uk.
(a)
Mk,ρk is the secret sharing access structure for group Uk, where Mk=mkijnk×lk. Then the data owner chooses a random vector vk→=sk,y2,⋯,ylk∈Zpn as secret vector, where sk is the encryption exponent to share in the group Uk. Then the share vector is computed as λk1,⋯λkj⋯,λklkT=Mkρk,i→·vφi→T, where Mkρk,i→ is the i-th row vector of the matrix Mk.(b)
The data owner chooses randomtk∈Zp∗ and computes the share key ShIDi→j=hIDiak·λkj,Kk′=gαk·gak·tk,Kk′′=gtk and the share verification ΩIDi→j=σIDi→j1=g^ak·y1,⋯,σIDi→jlk=g^ak·ylk of the key for user IDi→j, where y1=sk.(c)
The data owner takes a random degreet polynomial Rkx∈GFqx and computes RkμShIDi→j,IDi→j, denoted as vRjUk, in short vRIDi→j, with the injective function μ:GFp×1,⋯,n→GFq.(d)
SKi→j=ShIDi→j,Kk′,Kk′′,ΩIDi→j,vRIDi→j is encrypted by the user’s public key, so that only the user can decrypt it by his private key. In other words, the data owner sends the share key SKi→j safely to the user IDi→j by the public key infrastructure.(3)
The user receives theSKi→j and computes the decryption key by his private key dIDi as follows.
(a)
The user first verifiese∏j=1lkσIDi→jjmkij,g=eg^,ShIDi→jdIDi→j-1 with share verification information ΩIDi→j, share key ShIDi→j, and the user’s private key dIDi. The effective of this verification can be proved in Claim 2.(b)
The user then recoversKIDi→j=ShIDi→jdIDi-1=hIDiak·λkj·dIDi-1=gak·λkj from SKi→j by his private key dIDi.(c)
Finally the user computes the decryption keyDKi→j=KIDi→j=gak·λkj,Kk′=gαk·gak·tk,Kk′′=gtk,ΩIDi→j,vRIDi→j.


## 4.4. Decryption of Data File

A k is an authority set of the group Uk and Ak∣Ak⊆Uk,k∈1,⋯,N are the union of the N authority sets for N groups.(1)
These authorized users of theN sets Ak compute the tag Tagowner=HAttValueowner of data file that they want to decrypt and then send it to cloud server.(2)
The cloud server receives the tagTagowner.The cloud server verifies(3)BFh1Tagowner=BFh2Tagowner=⋯=BFhoTagowner=1,using Tagowner provided by these users. If it is satisfied, two decryption approaches can be adopted to get the plaintext: (a) decrypting by these authorized users and (b) outsourcing the decryption to the cloud. We describe them as follows:(a) Decrypting by these authorized users.After the authorized usersAk receive the corresponding data file BFdatafile,Mk,ρk,C0,Ckk=1~N sent by the cloud server, one has the following:(1) All the authority users from those authority setsAk use their decryption keys ShIDi→1,vRIDi→1,⋯,ShIDi→lk,vRIDi→lk to verify the correctness of these decryption keys.Firstly, it is recoveredR^kx from vRIDi→1,⋯,vRIDi→lk using Berlekamp algorithm. Then, the users of the group Uk verify R^kμShIDi→j,IDi→j=vRi→j for every decryption key DKi→j. If it is unequal then ShIDi→j is a fake share key. The user IDi→j is added to the list of cheaters Lk. Moreover, every group can identify the cheaters of the group in this way.(2) If there are no cheaters in all of the authority users, then these authority users recover the blind factor of dataM as follows.Firstly, for every authority set, there exists constantβk∈Zpn satisfying ∑j=1lkλkj·βk=sk, where k=1⋯N. Then, the blind factor of data M is computed as(4)∏k=1NeCk,Kk′∏k=1N∏j=1IDi→j∈AklkeShIDi→j,Kk′′βk=∏k=1Negsk,gαkgak·tk∏k=1N∏j=1IDi→j∈Aklkegak·λkj,gtkβk=∏k=1Negsk,gαk·egsk,gak·tkeg,g∑j=1IDi→j∈Aklkak·λkj·βk·tk=eg,g∑k=1Nαk·skFinally, M=C0/eg,g∑k=1Nαk·sk.(b) Outsourcing the decryption to the cloud.In this situation, these authorized users first generate the transformation keyTKCloudk in groups for the cloud before they are outsourcing the decryption and then obtaining group decryption GKk, where k∈1,⋯,N. To generate TKCloudk and GKk, the authorized user group Ak chooses a random value zk∈Zp and computes the transformation key TKCloudk as TKCloudk=ShIDi→11/zk,⋯,ShIDi→lk1/zk,K′1/zk2,K′′1/zk and outputs the group decryption key GKk=zk, for k∈1,⋯,N. We allow these authorized users themselves to generate the transformation key in group, which is more flexible. Then they send transformation key TKCloudkk=1⋯N to the cloud server for outsourced decryption.The cloud computes the following equation usingTKCloudkk=1~N: (5)C~0=eCk,Kk′1/zk2∏j=1IDi→j∈AklkeShIDi→j1/zk,Kk′′1/zkβk=egsk,gαkgak·tk1/zk2∏j=1IDi→j∈Aklkegak·λkj,gtkβk·1/zk2=egsk,gαk1/zk2·egsk,gak·tk1/zk2eg,g∑j=1IDi→j∈Aklkak·λkj·βk·tk·1/zk2=eg,gαk·sk·1/zk2and then it sends C~0 to the user groups Ak, for k∈1,⋯,N. After receiving C~0, all the user groups Ak compute message M as C0/∏k=1nC~0zk2=C0/∏k=1neg,gαk·sk·1/zk2zk2=M.


## 5. Security Analysis

### 5.1. Provable Security

In the proposed scheme, we utilize a symmetric encryption to hide the message data and use secret sharing based on general access structure to share the session key with users in every group. Since the security of secret sharing based on general access structure does not rely on any computational complexity assumption, it is unconditionally secure. Therefore, the modification does not disclose any information, and the proposed scheme is chosen plaintext secure.


### 5.2. Privacy of the Data Owner’s Personal Information

In order to protect privacy of the data owner, the data owner first computes the tag of the data fileTagowner=HAttValueowner with public hash function H and constructs the bloom filter BFdatafile=BFTagowner of the tag Tagowner. Then the bloom filter BFdatafile with the ciphertext is constructed as data file and uploaded to cloud server. To decrypt the ciphertext they want to access, the cloud users firstly compute the Tagowner of the data file with public hash function H. Then they present the Tagowner to the cloud server; the cloud finds the item of the data file by verifying the bloom filter BFdatafile. If it passes the verification, the ciphertext of the data file BFdatafile,Mk,ρk,C0,Ckk=1~N is sent to users. Then the users decrypt the ciphertext to recover the plaintext with their decryption key. It is easy to see that the personal privacy of the owner can be protected from the cloud.Claim 1.
The correctness of the search result can be ensured if the rate of false search result is acceptable.
A false positive probabilityPosiPro exists when determining whether an element x belongs to a set because of the possible collisions in the hash functions. We can compute PosiPro as follows [15]:(6)PosiPro=1-1-1mkn·k≈1-e-kn/mk,where n is the number of elements in set S and m is the size of the bit array. Obviously, when k=log⁡2m/n, the false positive probability PosiPro can be minimized to a negligible value, i.e., 1/2k.


### 5.3. Verifiability of the Share Key Distribution

In the following, we prove that the user can verify the correctness of share key distributed by the data owner.Claim 2.
Suppose a user isIDi; if he accepts the share verification ΩIDi→j from the owner, then there exists a unique value ShIDi→j such that e∏j=1lkσIDi→jjmkij,g=eg^,ShIDi→jdIDi→j-1.Suppose the owner distributes a share verificationΩIDi→j′=g^ak·z1,⋯,g^ak·zlk to the user IDi; if the user accepts the value ΩIDi→j′, then e∏j=1lkg^ak·z1⋯g^ak·zlk,g=eg^,ShIDi→jdIDi→j-1, e∏j=1lkg^ak·z1⋯g^ak·zlk,g=eg^ak·∑j=1lkzj·mkij,g=eg^,g∑j=1lkak·zj·mkij=eg^,ShIDi→jdIDi→j-1, which leads to ShIDi→j=hIDi→j∑j=1lkak·zj·mkij=hIDi→jak·λkj; that is to say λkj=zj·mkij.Therefore, the share key can be verified by the user.


### 5.4. Identification of the Cheater

The RS code is employed here to prevent the cheaters from changing the polynomialRx, which is used to test the validity of the shares, due to the fact that RS code has the ability to perform error correction. In other words, a polynomial Rx of t degree is uniquely determined by Ri1,⋯,Rik if and only if k≥3t+1, even if there are some fake shares Rij they cannot prevent the correct reconstruction of Rx. Thus, we have the following conclusion.Claim 3.
Ift≤k-1/3 in every group Uφi, then the proposed scheme is a t,ε cheater identifiable data sharing scheme that no cheater can succeed in cheating without being identified with probability better than 1/q, where t is the number of the cheaters and k is the threshold for every group.


### 5.5. Mutual Supervision between Groups

Claim 4.
The proposed scheme is collision-resistant and mutual supervision between different groups.The proposed scheme not only identifies the cheater in group but also can achieve mutual supervision between groups, because the secret is distributed to each group, if and only if all of theN groups present the correct secret share, then the plaintext is recovered correctly. If some users present a fake share in any authorized user set, it would cause the group share error, which leads the decryption process to failure.


## 5.1. Provable Security

In the proposed scheme, we utilize a symmetric encryption to hide the message data and use secret sharing based on general access structure to share the session key with users in every group. Since the security of secret sharing based on general access structure does not rely on any computational complexity assumption, it is unconditionally secure. Therefore, the modification does not disclose any information, and the proposed scheme is chosen plaintext secure.


## 5.2. Privacy of the Data Owner’s Personal Information

In order to protect privacy of the data owner, the data owner first computes the tag of the data fileTagowner=HAttValueowner with public hash function H and constructs the bloom filter BFdatafile=BFTagowner of the tag Tagowner. Then the bloom filter BFdatafile with the ciphertext is constructed as data file and uploaded to cloud server. To decrypt the ciphertext they want to access, the cloud users firstly compute the Tagowner of the data file with public hash function H. Then they present the Tagowner to the cloud server; the cloud finds the item of the data file by verifying the bloom filter BFdatafile. If it passes the verification, the ciphertext of the data file BFdatafile,Mk,ρk,C0,Ckk=1~N is sent to users. Then the users decrypt the ciphertext to recover the plaintext with their decryption key. It is easy to see that the personal privacy of the owner can be protected from the cloud.Claim 1.
The correctness of the search result can be ensured if the rate of false search result is acceptable.
A false positive probabilityPosiPro exists when determining whether an element x belongs to a set because of the possible collisions in the hash functions. We can compute PosiPro as follows [15]:(6)PosiPro=1-1-1mkn·k≈1-e-kn/mk,where n is the number of elements in set S and m is the size of the bit array. Obviously, when k=log⁡2m/n, the false positive probability PosiPro can be minimized to a negligible value, i.e., 1/2k.


## 5.3. Verifiability of the Share Key Distribution

In the following, we prove that the user can verify the correctness of share key distributed by the data owner.Claim 2.
Suppose a user isIDi; if he accepts the share verification ΩIDi→j from the owner, then there exists a unique value ShIDi→j such that e∏j=1lkσIDi→jjmkij,g=eg^,ShIDi→jdIDi→j-1.Suppose the owner distributes a share verificationΩIDi→j′=g^ak·z1,⋯,g^ak·zlk to the user IDi; if the user accepts the value ΩIDi→j′, then e∏j=1lkg^ak·z1⋯g^ak·zlk,g=eg^,ShIDi→jdIDi→j-1, e∏j=1lkg^ak·z1⋯g^ak·zlk,g=eg^ak·∑j=1lkzj·mkij,g=eg^,g∑j=1lkak·zj·mkij=eg^,ShIDi→jdIDi→j-1, which leads to ShIDi→j=hIDi→j∑j=1lkak·zj·mkij=hIDi→jak·λkj; that is to say λkj=zj·mkij.Therefore, the share key can be verified by the user.


## 5.4. Identification of the Cheater

The RS code is employed here to prevent the cheaters from changing the polynomialRx, which is used to test the validity of the shares, due to the fact that RS code has the ability to perform error correction. In other words, a polynomial Rx of t degree is uniquely determined by Ri1,⋯,Rik if and only if k≥3t+1, even if there are some fake shares Rij they cannot prevent the correct reconstruction of Rx. Thus, we have the following conclusion.Claim 3.
Ift≤k-1/3 in every group Uφi, then the proposed scheme is a t,ε cheater identifiable data sharing scheme that no cheater can succeed in cheating without being identified with probability better than 1/q, where t is the number of the cheaters and k is the threshold for every group.


## 5.5. Mutual Supervision between Groups

Claim 4.
The proposed scheme is collision-resistant and mutual supervision between different groups.The proposed scheme not only identifies the cheater in group but also can achieve mutual supervision between groups, because the secret is distributed to each group, if and only if all of theN groups present the correct secret share, then the plaintext is recovered correctly. If some users present a fake share in any authorized user set, it would cause the group share error, which leads the decryption process to failure.


## 6. Performance Analyses

In this section, we briefly compare our scheme with some other classical data sharing schemes, like Yu scheme [2] and Dong scheme [4]. Yu scheme is relaying on KP-ABE, while Dong scheme is based on CP-ABE. In our scheme, tk can also be seen as the attribute that involved in the group Uk. These schemes have applications in healthcare or library scenarios to share data. Besides, our scheme is more suitable for medical supervision scenario, especially when evidence is needed like EMR in medical disputes or accident. Data confidentiality is achieved in all these schemes since the data owner stores the ciphertext of data file into cloud server, and the cloud servers are not able to learn the plaintext of any data file. The data decryption keys are not known by the cloud server in any one of these schemes [2, 4] as well as in our scheme, although the proxy reencryption key is given to the cloud server in [2]. The comparison of our scheme with the schemes in [2, 4], regarding the security properties, is summarized in Table 2.Table 2
Comparison of security properties.
Scheme Collusion-resistant Anonymous storage Having verification property Identifiable cheater [2] YES NO YES NO [4] YES NO NO NO Ours YES YES YES YESIn order to make the comparison fair and meaningful, when comparing the computational cost in the decryption phase, we consider the general situation that all users have participated. In case when the decryption is partially outsourced to the cloud, this will further reduce the computational cost for the users obviously.


### 6.1. Dynamic Operation

The dynamic operations such as user addition/revocation and file creation/deletion are processed in a similar way as in all these schemes, then the operation are introduced briefly.(1) File Operation. There are three operations for file operation: file creation, file deletion, and file updating. In these operations, the data owner has the right to delete the new file in [2, 4] and ours. He makes a unique tag and defines the access policy or attributes set for file creation. For file updating, the data owner ought to rearrange the access policy in our scheme and in [4], while updating the file’s attribute i in ciphertext and the proxy reencryption key in scheme [2].(  2) User Operation. There are two operations for user operations: new user grant and user revocation. Similarly, the data owner assigns the corresponding secret key to the new user according the type of the scheme, KP-ABE or CP-ABE. The data owner may revoke the access privileges from some users. It has been a great challenge to achieve an effective user revocation.In most existing schemes, it can take a direct manner in which the data owner reupdates the access policy, reencrypts the relevant files, and distributes the renewed keys to the nonrevoked users via the cloud server. This method is applicable in [2, 4] and our scheme. Based on the above reasons, the data owner needs to guarantee that all the operations are processed faithfully by the cloud servers.


### 6.2. Computation Complexity

In this section, we analyze and compare the computation overhead of the proposed scheme with [2, 4], considering the encryption and decryption operation. In the proposed scheme, the main computational cost involved in encryption and decryption algorithms are pairing eg,g and scalar multiplication. The ciphertext of the proposed scheme is C=C0=eg,g∑kαk·sk,C1=gs1,⋯,CN=gsN. Pairing is the most expensive operation. For each different file, data owner only needs to calculate eg,g once at the beginning. Thus, we do not consider the overhead of pairing operation in the computational complexity when comparing the proposed scheme with those in [2, 4]. In the computational complexity analysis, we only take into account scalar multiplication operation. During encrypting, all encryption operations are at the data owner’s side. The data owner needs to do N scalar multiplication for C0 and N scalar multiplications for Ck; thus, the owner should take 2N scalar multiplication in total for encryption. Then the computation complexity of encryption is ON.In the decryption stage, to recover ciphertext, the user needs at most2N+U scalar multiplications to calculate(7)∏k=1Negsk,gαk·egsk,gak·tkeg,g∑j=1IDi→j∈Aklkak·λkj·βk·tk.Thus, the computation complexity of decryption is at most about OU.In the key generation stage, it needs one scalar multiplication to calculateShIDi→j=hIDiak·λkj for each user IDi and two scalar multiplications to calculate Kk′=gαk·gak·tk and Kk′′=gtk for each group Uk. Therefore, the computational complexity of key generation is at most O1.For the cloud server, the main computational overhead is caused by the execution of tag testing algorithm by Bloom filter hash function. So the computation complexity for cloud server isO1.In [4], the data owner needs to do two scalar multiplications to calculate C1,x=eg1,g1λxeg1,g1αρxrx, one scalar multiplication for C2,x=g1rx, and two for C3,x=g1βρxrxg1ωx. Therefore, the data owner needs at most 5IM scalar multiplications. Thus, the computation complexity of encryption is OIM. To recover the ciphertext, the user needs another 2IM scalar multiplications at most to calculate ∏xeg1,g1λxeHID,g1ωx, so the time complexity is also at most OIM. The time complexity for key generation is OIu.While in [2], the data owner needs to do one scalar multiplications to calculate E~=M·eg,gys and one scalar multiplication for Ei=gti·s. Therefore the computation complexity of the data owner for encryption is OIu. To recover the ciphertext one has to compute eEi,ski=eg,gpi0s for each leaf node firstly. Then, it aggregates these pairing results in the bottom-up manner using the polynomial interpolation technique. Finally, it recovers the blind factor Ys=eg,gys and outputs the message M if only if attributes I satisfy access tree T. So the time complexity for decryption is about Omax⁡IM,Iu. And the time complexity for generation of the key SK=ski∣ski=gpi0/tii∈IM is OIM.The computational complexity of our scheme, as well as [2, 4], is given in Table 3, where Iu denotes the attributes of the user, IM denotes the attributes of access structure, set U represents the universal users, and N is the number of the partitioned groups in our scheme.Table 3
Comparison of computation complexity.
Scheme Encryption Decryption Key Generation (Data owner) (User) [2] O I u O max ⁡ I M , I u O I M [4] O I M O I M O I u Ours O N O U O 1


### 6.3. Experiment Results

The evaluation is conducted through experiment evaluating the time cost of the proposed scheme on a computer with Windows7 Intel i5-4590S -3.00GHz CPU, and 4-GB RAM. All results presented here are the average value in 100 different trials.


#### 6.3.1. The Overhead of Encryption Algorithm

In our scheme, the encryption is to calculateC1,⋯,CN. In [2], the calculation of ciphertext C is based on E~ and Eii∈I. And the calculation of ciphertext C in scheme [4] is based on C1,x,C2,x,C3,x. Let the number of attributes Iu equals the number of users N, and then the encryption speed of our scheme and other schemes with the number of the attribute is to 10 and to 50 is given, respectively, in Figures 3 and 4.Figure 3
Comparison of encryption performance with 10 attributes.Figure 4
Comparison of encryption performance with 50 attributes.From Figures3 and 4, we can see that the encryption cost increases linearly with the attributes in the three schemes, and our scheme has almost the same cost as [2] and it is much lower than [4].


#### 6.3.2. The Overhead of Decryption Algorithm

In our scheme, the decryption is to compute∏k=1NeCk,Kk′/∏k=1N∏j=1IDi→j∈AklkeShIDi→j,Kk′′βk. As we see the cost of decryption depends on the number of groups and the user number in each group. The decryption overload about 10 groups and 10 users in every group of our scheme is showed in Figure 5.Figure 5
The decryption performance of our scheme.The decryption overload of [2] is to compute the pairing operation which is not only due to the number of the attributes but also due to intermediate node, the size of the concrete tree structure. If the structure of the tree is a large number, then the overload will be very large. Here, we only give the comparison of decryption overload between our scheme and [4], where the number of users in our scheme is the same as the number of attributes in [4]. Every star in Figure 6 is denoted as a number of the groups in brackets under the same number of the attributes in our scheme. From Figure 6, we can see that the more groups, the greater the consumption.Figure 6
Decryption performance of the proposed scheme and [4].When all users are in one group in our scheme, the overhead of decryption are showed in Figures7 and 8, where attributes of access structure are up to 10 and 50, respectively. Then it can be seen that our scheme overhead is less than [4].Figure 7
Comparison of decryption performance with 10 attributes.Figure 8
Comparison of decryption performance with 50 attributes.


#### 6.3.3. The Overhead of Key Generation Algorithm

The key generation algorithm is to compute the power exponent in all of three schemes. In order to simplify the comparison, we take all users in one group, then key generation overloads of three schemes are showed in Figure9. From the Figure 9, it can be seen that the overload in our scheme is much less than [4] and a little more than [2].Figure 9
Comparison of key generation performance with 10 attributes.


### 6.4. Communication Cost

In our scheme, the communication cost is mainly attributed to the encrypted data and key distribution transmission. The encrypted data is sent by the data owner to the cloud: the value ofC0=eg,g∑kαk·sk and C1=gs1,⋯CN=gsN requires log⁡G2+N·log⁡G1 bits. The share keys are sent by the data owner to the users: the value ShIDi→j,Kk′,Kk′′ for every i requires 3N·log⁡G2, ΩIDi→j at most requires N2·log⁡G2 and vRIDi→j requires log⁡q bits. Thus the communication cost of the share key from owner to users is given by 3N·log⁡G2+N2·log⁡G2+log⁡q. The private key is usually a few hundred bits, and in general, it does not need to be compressed. We need to assume that before the cloud environment is established, the private key is initialized in advance, and each participant can securely store and use the private key. Thus the whole communication cost of the protocol is given by log⁡G2+N·log⁡G1+3N·log⁡G2+N2·log⁡G2+log⁡q+data. The communication expenses comparison between our scheme, KP-ABE-based schemes, and CP-ABE-based schemes is shown as Table 4. We can see that the communication cost of our scheme is nearly the same as CP-ABE-based schemes and our scheme and [4] is slightly more than KP-ABE-based schemes. However, in practice, the file is described by just a limited attributes or shared with limited users. In addition, even though the order of cyclic group G is large, log⁡G bits is far less than the file size (data). In other words, the extra communication cost can be ignored.Table 4
Comparison of communication costs.
Scheme Communication costs [2] I + 2 log ⁡ I + I + 1 log ⁡ G 1 + log ⁡ G 2 + d a t a [4] I 2 + log ⁡ I + 2 I + 1 log ⁡ G 1 + I + 1 log ⁡ G 2 + d a t a Ours log ⁡ G 2 + N ⋅ log ⁡ G 1 + 3 N ⋅ log ⁡ G 2 + N 2 ⋅ log ⁡ G 2 + log ⁡ q + d a t a


## 6.1. Dynamic Operation

The dynamic operations such as user addition/revocation and file creation/deletion are processed in a similar way as in all these schemes, then the operation are introduced briefly.(1) File Operation. There are three operations for file operation: file creation, file deletion, and file updating. In these operations, the data owner has the right to delete the new file in [2, 4] and ours. He makes a unique tag and defines the access policy or attributes set for file creation. For file updating, the data owner ought to rearrange the access policy in our scheme and in [4], while updating the file’s attribute i in ciphertext and the proxy reencryption key in scheme [2].(  2) User Operation. There are two operations for user operations: new user grant and user revocation. Similarly, the data owner assigns the corresponding secret key to the new user according the type of the scheme, KP-ABE or CP-ABE. The data owner may revoke the access privileges from some users. It has been a great challenge to achieve an effective user revocation.In most existing schemes, it can take a direct manner in which the data owner reupdates the access policy, reencrypts the relevant files, and distributes the renewed keys to the nonrevoked users via the cloud server. This method is applicable in [2, 4] and our scheme. Based on the above reasons, the data owner needs to guarantee that all the operations are processed faithfully by the cloud servers.


## 6.2. Computation Complexity

In this section, we analyze and compare the computation overhead of the proposed scheme with [2, 4], considering the encryption and decryption operation. In the proposed scheme, the main computational cost involved in encryption and decryption algorithms are pairing eg,g and scalar multiplication. The ciphertext of the proposed scheme is C=C0=eg,g∑kαk·sk,C1=gs1,⋯,CN=gsN. Pairing is the most expensive operation. For each different file, data owner only needs to calculate eg,g once at the beginning. Thus, we do not consider the overhead of pairing operation in the computational complexity when comparing the proposed scheme with those in [2, 4]. In the computational complexity analysis, we only take into account scalar multiplication operation. During encrypting, all encryption operations are at the data owner’s side. The data owner needs to do N scalar multiplication for C0 and N scalar multiplications for Ck; thus, the owner should take 2N scalar multiplication in total for encryption. Then the computation complexity of encryption is ON.In the decryption stage, to recover ciphertext, the user needs at most2N+U scalar multiplications to calculate(7)∏k=1Negsk,gαk·egsk,gak·tkeg,g∑j=1IDi→j∈Aklkak·λkj·βk·tk.Thus, the computation complexity of decryption is at most about OU.In the key generation stage, it needs one scalar multiplication to calculateShIDi→j=hIDiak·λkj for each user IDi and two scalar multiplications to calculate Kk′=gαk·gak·tk and Kk′′=gtk for each group Uk. Therefore, the computational complexity of key generation is at most O1.For the cloud server, the main computational overhead is caused by the execution of tag testing algorithm by Bloom filter hash function. So the computation complexity for cloud server isO1.In [4], the data owner needs to do two scalar multiplications to calculate C1,x=eg1,g1λxeg1,g1αρxrx, one scalar multiplication for C2,x=g1rx, and two for C3,x=g1βρxrxg1ωx. Therefore, the data owner needs at most 5IM scalar multiplications. Thus, the computation complexity of encryption is OIM. To recover the ciphertext, the user needs another 2IM scalar multiplications at most to calculate ∏xeg1,g1λxeHID,g1ωx, so the time complexity is also at most OIM. The time complexity for key generation is OIu.While in [2], the data owner needs to do one scalar multiplications to calculate E~=M·eg,gys and one scalar multiplication for Ei=gti·s. Therefore the computation complexity of the data owner for encryption is OIu. To recover the ciphertext one has to compute eEi,ski=eg,gpi0s for each leaf node firstly. Then, it aggregates these pairing results in the bottom-up manner using the polynomial interpolation technique. Finally, it recovers the blind factor Ys=eg,gys and outputs the message M if only if attributes I satisfy access tree T. So the time complexity for decryption is about Omax⁡IM,Iu. And the time complexity for generation of the key SK=ski∣ski=gpi0/tii∈IM is OIM.The computational complexity of our scheme, as well as [2, 4], is given in Table 3, where Iu denotes the attributes of the user, IM denotes the attributes of access structure, set U represents the universal users, and N is the number of the partitioned groups in our scheme.Table 3
Comparison of computation complexity.
Scheme Encryption Decryption Key Generation (Data owner) (User) [2] O I u O max ⁡ I M , I u O I M [4] O I M O I M O I u Ours O N O U O 1


## 6.3. Experiment Results

The evaluation is conducted through experiment evaluating the time cost of the proposed scheme on a computer with Windows7 Intel i5-4590S -3.00GHz CPU, and 4-GB RAM. All results presented here are the average value in 100 different trials.


### 6.3.1. The Overhead of Encryption Algorithm

In our scheme, the encryption is to calculateC1,⋯,CN. In [2], the calculation of ciphertext C is based on E~ and Eii∈I. And the calculation of ciphertext C in scheme [4] is based on C1,x,C2,x,C3,x. Let the number of attributes Iu equals the number of users N, and then the encryption speed of our scheme and other schemes with the number of the attribute is to 10 and to 50 is given, respectively, in Figures 3 and 4.Figure 3
Comparison of encryption performance with 10 attributes.Figure 4
Comparison of encryption performance with 50 attributes.From Figures3 and 4, we can see that the encryption cost increases linearly with the attributes in the three schemes, and our scheme has almost the same cost as [2] and it is much lower than [4].


### 6.3.2. The Overhead of Decryption Algorithm

In our scheme, the decryption is to compute∏k=1NeCk,Kk′/∏k=1N∏j=1IDi→j∈AklkeShIDi→j,Kk′′βk. As we see the cost of decryption depends on the number of groups and the user number in each group. The decryption overload about 10 groups and 10 users in every group of our scheme is showed in Figure 5.Figure 5
The decryption performance of our scheme.The decryption overload of [2] is to compute the pairing operation which is not only due to the number of the attributes but also due to intermediate node, the size of the concrete tree structure. If the structure of the tree is a large number, then the overload will be very large. Here, we only give the comparison of decryption overload between our scheme and [4], where the number of users in our scheme is the same as the number of attributes in [4]. Every star in Figure 6 is denoted as a number of the groups in brackets under the same number of the attributes in our scheme. From Figure 6, we can see that the more groups, the greater the consumption.Figure 6
Decryption performance of the proposed scheme and [4].When all users are in one group in our scheme, the overhead of decryption are showed in Figures7 and 8, where attributes of access structure are up to 10 and 50, respectively. Then it can be seen that our scheme overhead is less than [4].Figure 7
Comparison of decryption performance with 10 attributes.Figure 8
Comparison of decryption performance with 50 attributes.


### 6.3.3. The Overhead of Key Generation Algorithm

The key generation algorithm is to compute the power exponent in all of three schemes. In order to simplify the comparison, we take all users in one group, then key generation overloads of three schemes are showed in Figure9. From the Figure 9, it can be seen that the overload in our scheme is much less than [4] and a little more than [2].Figure 9
Comparison of key generation performance with 10 attributes.


## 6.3.1. The Overhead of Encryption Algorithm

In our scheme, the encryption is to calculateC1,⋯,CN. In [2], the calculation of ciphertext C is based on E~ and Eii∈I. And the calculation of ciphertext C in scheme [4] is based on C1,x,C2,x,C3,x. Let the number of attributes Iu equals the number of users N, and then the encryption speed of our scheme and other schemes with the number of the attribute is to 10 and to 50 is given, respectively, in Figures 3 and 4.Figure 3
Comparison of encryption performance with 10 attributes.Figure 4
Comparison of encryption performance with 50 attributes.From Figures3 and 4, we can see that the encryption cost increases linearly with the attributes in the three schemes, and our scheme has almost the same cost as [2] and it is much lower than [4].


## 6.3.2. The Overhead of Decryption Algorithm

In our scheme, the decryption is to compute∏k=1NeCk,Kk′/∏k=1N∏j=1IDi→j∈AklkeShIDi→j,Kk′′βk. As we see the cost of decryption depends on the number of groups and the user number in each group. The decryption overload about 10 groups and 10 users in every group of our scheme is showed in Figure 5.Figure 5
The decryption performance of our scheme.The decryption overload of [2] is to compute the pairing operation which is not only due to the number of the attributes but also due to intermediate node, the size of the concrete tree structure. If the structure of the tree is a large number, then the overload will be very large. Here, we only give the comparison of decryption overload between our scheme and [4], where the number of users in our scheme is the same as the number of attributes in [4]. Every star in Figure 6 is denoted as a number of the groups in brackets under the same number of the attributes in our scheme. From Figure 6, we can see that the more groups, the greater the consumption.Figure 6
Decryption performance of the proposed scheme and [4].When all users are in one group in our scheme, the overhead of decryption are showed in Figures7 and 8, where attributes of access structure are up to 10 and 50, respectively. Then it can be seen that our scheme overhead is less than [4].Figure 7
Comparison of decryption performance with 10 attributes.Figure 8
Comparison of decryption performance with 50 attributes.


## 6.3.3. The Overhead of Key Generation Algorithm

The key generation algorithm is to compute the power exponent in all of three schemes. In order to simplify the comparison, we take all users in one group, then key generation overloads of three schemes are showed in Figure9. From the Figure 9, it can be seen that the overload in our scheme is much less than [4] and a little more than [2].Figure 9
Comparison of key generation performance with 10 attributes.


## 6.4. Communication Cost

In our scheme, the communication cost is mainly attributed to the encrypted data and key distribution transmission. The encrypted data is sent by the data owner to the cloud: the value ofC0=eg,g∑kαk·sk and C1=gs1,⋯CN=gsN requires log⁡G2+N·log⁡G1 bits. The share keys are sent by the data owner to the users: the value ShIDi→j,Kk′,Kk′′ for every i requires 3N·log⁡G2, ΩIDi→j at most requires N2·log⁡G2 and vRIDi→j requires log⁡q bits. Thus the communication cost of the share key from owner to users is given by 3N·log⁡G2+N2·log⁡G2+log⁡q. The private key is usually a few hundred bits, and in general, it does not need to be compressed. We need to assume that before the cloud environment is established, the private key is initialized in advance, and each participant can securely store and use the private key. Thus the whole communication cost of the protocol is given by log⁡G2+N·log⁡G1+3N·log⁡G2+N2·log⁡G2+log⁡q+data. The communication expenses comparison between our scheme, KP-ABE-based schemes, and CP-ABE-based schemes is shown as Table 4. We can see that the communication cost of our scheme is nearly the same as CP-ABE-based schemes and our scheme and [4] is slightly more than KP-ABE-based schemes. However, in practice, the file is described by just a limited attributes or shared with limited users. In addition, even though the order of cyclic group G is large, log⁡G bits is far less than the file size (data). In other words, the extra communication cost can be ignored.Table 4
Comparison of communication costs.
Scheme Communication costs [2] I + 2 log ⁡ I + I + 1 log ⁡ G 1 + log ⁡ G 2 + d a t a [4] I 2 + log ⁡ I + 2 I + 1 log ⁡ G 1 + I + 1 log ⁡ G 2 + d a t a Ours log ⁡ G 2 + N ⋅ log ⁡ G 1 + 3 N ⋅ log ⁡ G 2 + N 2 ⋅ log ⁡ G 2 + log ⁡ q + d a t a


## 7. Application to Secure Medical Information Sharing Scene

In personal health medical information environment, like personal medical information, medical record information of a person is cumulated consistently during his life; he will have a lot of contact with nurses and doctors over his life. From perspective of the patient, he is the data owner. When his health medical record is stored in the cloud server, he also wishes to control his medical data and he needs to specify who can to access his information; those users are called authorized users. As shown in Figure10, these authorized users might be some friends, specialists, nurses, and public security investigators. To ensure impartiality and fairness, to prevent tampering, forgery, and other illegal acts, the access of medical record data of the owner should be carried out under the above different groups’ supervision. And scheme should have the properties of data confidentiality and privacy protection and cheater identification. To achieve this goal, a privacy protection approach is taken to use bloom filter, to hide some personal information that is not closely related to health conditions of the patient, such as name, gender, telephone number, ID card number, family address, and property, when medical record of owner is stored on cloud. Moreover, since each group has a group secret, data’s access is carried out under an effective supervision mechanism according to the portioned groups. Besides, it can be made sure that the participants conspiring or deceive can be found and identified applying an error correction function of RS encoding technique. In summary, the proposed scheme is helpful for patient to achieve flexible and supervised control on his case file stored on cloud server.Figure 10
The system model for personal medical information privacy protection system.


## 8. Conclusion

In this paper, a personal medical information privacy protection scheme in the cloud was proposed, which can be used to set the electronic medical records system up for patients efficiently. The proposed scheme has flexible data access control through combing the techniques of the secret sharing methods and symmetric encryption. The performance analysis shows that the proposed scheme has low overhead and high efficiency. In this proposed scheme, we use RS encoding method to identify the dishonest user. It means there are not too much misbehave users in every group. As indicate in Section2.5, this scheme has the capability of identifying up to t cheaters under the condition k-1/3≥t. Hence, in the future works, we will investigate how to remove this condition and to achieve more efficiency of recognition of the dishonest user. Moreover, we will investigate how to achieve efficient data file updated flexibly and how to process multifile convergence in batches.



---

*Source: 6174830-2018-10-16.xml*