# CP-ABE-Based Secure and Verifiable Data Deletion in Cloud

Authors: Jun Ma; Minshen Wang; Jinbo Xiong; Yongjin Hu
Journal: Security and Communication Networks
 (2021)

---

## Abstract

Cloud data, the ownership of which is separated from their administration, usually contain users’ private information, especially in the fifth-generation mobile communication (5G) environment, because of collecting data from various smart mobile devices inevitably containing personal information. If it is not securely deleted in time or the result of data deletion cannot be verified after their expiration, this will lead to serious issues, such as unauthorized access and data privacy disclosure. Therefore, this affects the security of cloud data and hinders the development of cloud computing services seriously. In this paper, we propose a novel secure data deletion and verification (SDVC) scheme based on CP-ABE to achieve fine-grained secure data deletion and deletion verification for cloud data. Based on the idea of access policy in CP-ABE, we construct an attribute association tree to implement fast revoking attribute and reencrypting key to achieve fine-grained control of secure key deletion. Furthermore, we build a rule transposition algorithm to generate random data blocks and combine the overwriting technology with the Merkle hash tree to implement secure ciphertext deletion and generate a validator, which is then used to verify the result of data deletion. We prove the security of the SDVC scheme under the standard model and verify the correctness and effectiveness of the SDVC scheme through theoretical analysis and ample simulation experiment results.


---

## Body

## 1. Introduction

The rapid developments of big data, Internet of Things (IoT), and the fifth-generation mobile communication (5G) technologies promote an explosion growth in data volumes generated by users’ mobile devices, which also result in the widespread popularity and further upgrading of 5G cloud storage services in cloud service provider (CSP) [1–3]. CSP provides users with massive data storage services without requiring the users to store data in local devices [4], which not only saves users’ a large amount of money for building their own storage, but also can search and retrieve the required data more quickly and share the data with other users more expediently, such as Dropbox, Baidu Cloud, and Alibaba Cloud [5–7]. Meanwhile, 5G technologies enable all kinds of intelligent devices to realize fast cloud connection, making it convenient for these devices to upload data to the CSP and providing convenient services for users [8].As we know, once users upload their personal data to the CSP, the ownership of the data is separated from the administration of them, resulting in the users completely losing control over their uploaded data from various mobile devices, such as body sensor equipment, smart rings, and smart phones [9, 10]. However, the personal data inevitably contain users’ private information; if it is not securely deleted from the CSP in time after their expiration, this will lead to serious problems, such as unauthorized access, resource abuse, side channel attack, data privacy disclosure, and other disastrous consequences [11–13]. Moreover, when users want to delete the cloud data, they need to completely trust CSP. After the users send request for deleting the expired data to the CSP, which generally returns “success” or “failure” as a response, the users cannot confirm the reliability of deletion results for their cloud data. Furthermore, driven by the interests, the “honest and curious” CSP does not delete or transfer users’ data in time, but returns the “success” message to deceive the users [14]. Therefore, this phenomenon leads to various types of users’ privacy disclosure occurring frequently; for example, Facebook emails suggest that it considered selling users’ data to third parties, and some cloud platforms have authorized their partners to get access to the sensitive information of users’ data [15, 16].Secure data deletion is a crucial part of protecting users’ data security and privacy within their whole lifecycle [9, 17], and data deletion verification provides protection and assuring for secure data deletion [18]. Related researchers have studied secure data deletion and obtained certain research findings. Xiong et al. [19] introduced and analyzed related methods of secure data deletion based on cryptography [20]. These methods can be mainly divided into data assured deletion schemes based on trusted execution environment, key management, and access control policies. However, all of these methods lack verification technique of deletion results for cloud data. As a result, exploring how to implement secure data deletion and deletion verification for cloud data is of great significance to healthy development of the cloud computing. There are four main solutions for secure data deletion and verification in the cloud, such as overwrite-based, provable data possession (PDP)-based, blockchain-based, and attribute-based encryption (ABE)-based schemes. Among these methods, ABE has a flexible access policy that enables fine-grained access control for cloud data [21, 22]. In particular, ciphertext-policy ABE (CP-ABE) [23, 24] can help us achieve fine-grained policy management and flexible access control for constructing flexible scheme for fine-grained secure data deletion and verification in the cloud.Therefore, this paper proposes a novel secure data deletion and verification (SDVC) scheme based on CP-ABE for cloud data in cloud, which includes a secure data deletion method and a data deletion verification method. The SDVC scheme constructs an attribute association tree (AAT) and a rule transposition algorithm (RTA) to realize attribute revocation [24] and reencrypting keys to quickly delete the cloud data and verify the data deletion results. The SDVC achieves rapid data deletion and results verification, and the main contributions of the SDVC scheme are as follows:(i)
A secure data deletion method based on CP-ABE algorithm implements fine-grained deletion control of cloud data, which constructs an AAT to achieve fast attribute revocation. Through updating node attribute within the AAT, we can reconstruct new access policies and reencrypt the data; thus, the ciphertext cannot be recovered and, finally, secure data deletion is implemented in a timely manner. Meanwhile, constructing the AAT actually reduces the attribute query overhead.(ii)
A data deletion verification method is built based on RTA and overwriting algorithm, which generates random data blocks to overwrite the expired cloud data blocks. When it overwrites data, the verification values of each data block are generated and the value of root node can be generated by MHT as a data deletion validator. This method not only makes the expired data unrecoverable, but also saves communication overhead compared to the methods uploading random data directly.(iii)
The security proof demonstrates that the SDVC scheme realizes secure deletion and verification for cloud data. The theory analysis and ample simulation results indicate that the SDVC scheme is effective and efficient in implementing secure data deletion and verification compared with the related methods.The rest of the paper is organized as follows: Section2 describes the related work; Section 3 gives preliminaries; and Section 4 describes the problem description, including system model, scheme overview, security model, and implementation goals. In Section 5, we construct the SDVC scheme. Section 6 and Section 7 give the security analysis, theoretical analysis, and performance evaluation. Section 8 concludes the whole paper.


## 2. Related Work

Various cloud services bring a lot of convenience to people who are increasingly inclined to store a large amount of data into CSP [25–27]. Once users upload their individual data to the cloud, the ownership of the data are separated from the administration of them, resulting in users losing complete control over their data. Therefore, in the process of secure data deletion and verification, there are problems such as unauthorized access, privacy leakage, and unverifiable deletion results [28]. Relevant scholars have obtained certain research findings; Xiong et al. [19] summarized three main types of secure data deletion methods for cloud data: trusted execution environment, key management, and access control policies. However, these methods do not consider how to verify the deletion results [29]. The existing research on cloud data deletion and verification can be mainly divided into the following four solutions, as described in Table 1.Table 1
Comparative analysis of related data deletion and verification solutions.
ClassificationsSolutionsTechniquesAdvantagesLimitationsOverwrite-based[30]Random data overwritingSimple data deletion and verificationHuge commu. overhead[31]CP-ABE, random data overwritingFlexible policy and easy verificationComput., commu. overhead[32]TPM, signature verificationTransparent, public verificationSmall storage capacityPDP-based[33]Dynamic PDP, skip-list structureControllability, confidentialityComplexity, key managementBlockchain-based[34]MHT, timestamp, blockchainSimple verificationNot dynamic and fine-grained[18]Smart contract, blockchainSimple verification in cloudNot dynamic and fine-grainedABE-based[35]KP-ABE, reencryptingFlexible, fine-grainedHuge commu. overheadSDVCCP-ABE, AAT, RTA, MHTFlexible, fine-grained, effectivenessDecryption overhead


### 2.1. Overwrite-Based Deletion and Verification

Regarding the overwrite-based deletion verification method, Paul and Saxena [30] proposed a provable, overwrite-based data deletion verification scheme, where the users first generate the same size of random data as the expired data and upload it to the CSP to overlay the expired data. After performing the overwriting operation, CSP will generate a data validator. If the returned validator is the same as the locally generated validator, the expired data is considered to be securely deleted. On the contrary, CSP may not delete data in time. Du et al. [31] proposed a deletion verification scheme for cloud data based on overwriting verification, which uses CP-ABE algorithm [36] to encrypt plaintext. When the cloud data expires, the ciphertext associated access policy is changed and used to reencrypt the expired ciphertext to achieve secure deletion. Furthermore, a searchable path of hash binary tree is generated according to the number of expired data blocks. Starting from the root node of the binary tree, this solution hierarchically traverses the binary tree, generates random binary data of the same size as the expired data, obtains the shortest path between the root node and each leaf node, then records all the node sequence numbers of the shortest path, converts them into binary expired data, and performs an XOR bit by bit to generate new data, which is used to overwrite the expired data. Finally, the algorithm calculates the value of each leaf node data as a validator by hash operation and verifies the data deletion results with the validator. Hao et al. [32] proposed a data deletion verification scheme based on trusted platform module (TPM). The basic idea of this scheme is to store the key through additional TPM hardware module configured by the CSP and perform data encryption and decryption operations [37]. When the expired data needs to be cleared, the TPM module performs the key deletion operation. Besides, the TPM module verifies the signature of the key deletion operation and uses the signature verification as a basis to prove whether the CSP has not performed the key deletion operation or tamper with the information of storage key in TPM. The TPM makes the deletion process more transparent and deletion results supporting public authentication, but is limited by the small storage capacity of its module. Miao et al. [38] proposed a solution where the data owners first calculate the metainformation of the expired data and send it to the CSP; after the CSP deletes the expired data, the metainformation of the new data is returned to the users, and the users verify data metainformation through verified equation; if the validation passes, the data has already been deleted. In this solution, as the amount of updating and deleting data increases, this leads to linear growth of computation, communication, and storage overhead of the CSP.


### 2.2. PDP-Based Deletion and Verification

Liu et al. [33] proposed an improved data transfer and data deletion verification scheme, which uses the dynamic provable data possession (PDP) mechanism [39] to update the original data of the cloud with the purpose of data deletion. Furthermore, it makes the original data unrecoverable and finally verifies whether the cloud holds the expired data through the data proofing function of the dynamic PDP mechanism and the skip-list authentication structure. The program considers the requirements for controllability and data confidentiality in the deletion process. The data owner introduces custom destruction mode to realize the controllability of the data deletion process, while the data confidentiality is realized by encrypting the plaintext data and using the key control to partitioned storage.


### 2.3. Blockchain-Based Deletion and Verification

Yang et al. [34] proposed a data deletion public verification scheme based on blockchain technology [40]. The scenario assumes that the CSP is semitrusted [24]. Firstly, the user encrypts the data and uploads it to the CSP. When data deletion is required, the user constructs a hash chain by combining the Merkle hash tree (MHT) [41], the timestamp server, and the blockchain technique. The hash chain verifies whether the CSP has actually deleted the expired data by the value in the hash chain. Liu et al. [18] proposed a cloud data deletion verification protocol based on blockchain. Firstly, the personal identity is authenticated by the smart contract algorithm, and the deletion operation record is created at the same time. The CSP then deletes the expired data specified by the data owner and generates a hash value to join the blockchain by hashing operation. Finally, the user verifies the data deletion result through the blockchain.


### 2.4. ABE-Based Deletion and Verification

Xue et al. [35] proposed a secure deletion solution based on KP-ABE. The user encrypts data with the KP-ABE algorithm. When the expired data needs to be deleted, the users cannot decrypt and access the data by revoking the attribute corresponding to the expired data and reencrypting the data [42]. Before the cloud data storage, the data is encrypted, and a digital signature is generated for each data block in the ciphertext by a hash operation. This digital signature corresponds to the ciphertext attribute, and the validator is generated by the MHT and feeds it back to the user to verify the deletion result.The deletion operation in the process of deleting data based on the overwriting-based deletion verification scheme is coarse-grained; the encryption algorithm is used to encrypt the data to ensure the security of the data, but the key is not handled securely; thus, there is a key leakage issue [43, 44]. The PDP-based deletion verification scheme does not delete the ciphertext stored in the CSP. When an unauthorized user gets access to ciphertext and cracks the cloud ciphertext through the ciphertext analysis and brute force cracking, privacy information is faced with threat of leakage [45–47]. Aiming at the issues of unauthorized access, large computational cost in the process of data deletion, and inability to implement fine-grained deletion and verification data, this work focuses on a secure and effective cloud data deletion and verification solution to achieve fine-grained data security deletion and verification through flexible and effective key management.


## 2.1. Overwrite-Based Deletion and Verification

Regarding the overwrite-based deletion verification method, Paul and Saxena [30] proposed a provable, overwrite-based data deletion verification scheme, where the users first generate the same size of random data as the expired data and upload it to the CSP to overlay the expired data. After performing the overwriting operation, CSP will generate a data validator. If the returned validator is the same as the locally generated validator, the expired data is considered to be securely deleted. On the contrary, CSP may not delete data in time. Du et al. [31] proposed a deletion verification scheme for cloud data based on overwriting verification, which uses CP-ABE algorithm [36] to encrypt plaintext. When the cloud data expires, the ciphertext associated access policy is changed and used to reencrypt the expired ciphertext to achieve secure deletion. Furthermore, a searchable path of hash binary tree is generated according to the number of expired data blocks. Starting from the root node of the binary tree, this solution hierarchically traverses the binary tree, generates random binary data of the same size as the expired data, obtains the shortest path between the root node and each leaf node, then records all the node sequence numbers of the shortest path, converts them into binary expired data, and performs an XOR bit by bit to generate new data, which is used to overwrite the expired data. Finally, the algorithm calculates the value of each leaf node data as a validator by hash operation and verifies the data deletion results with the validator. Hao et al. [32] proposed a data deletion verification scheme based on trusted platform module (TPM). The basic idea of this scheme is to store the key through additional TPM hardware module configured by the CSP and perform data encryption and decryption operations [37]. When the expired data needs to be cleared, the TPM module performs the key deletion operation. Besides, the TPM module verifies the signature of the key deletion operation and uses the signature verification as a basis to prove whether the CSP has not performed the key deletion operation or tamper with the information of storage key in TPM. The TPM makes the deletion process more transparent and deletion results supporting public authentication, but is limited by the small storage capacity of its module. Miao et al. [38] proposed a solution where the data owners first calculate the metainformation of the expired data and send it to the CSP; after the CSP deletes the expired data, the metainformation of the new data is returned to the users, and the users verify data metainformation through verified equation; if the validation passes, the data has already been deleted. In this solution, as the amount of updating and deleting data increases, this leads to linear growth of computation, communication, and storage overhead of the CSP.


## 2.2. PDP-Based Deletion and Verification

Liu et al. [33] proposed an improved data transfer and data deletion verification scheme, which uses the dynamic provable data possession (PDP) mechanism [39] to update the original data of the cloud with the purpose of data deletion. Furthermore, it makes the original data unrecoverable and finally verifies whether the cloud holds the expired data through the data proofing function of the dynamic PDP mechanism and the skip-list authentication structure. The program considers the requirements for controllability and data confidentiality in the deletion process. The data owner introduces custom destruction mode to realize the controllability of the data deletion process, while the data confidentiality is realized by encrypting the plaintext data and using the key control to partitioned storage.


## 2.3. Blockchain-Based Deletion and Verification

Yang et al. [34] proposed a data deletion public verification scheme based on blockchain technology [40]. The scenario assumes that the CSP is semitrusted [24]. Firstly, the user encrypts the data and uploads it to the CSP. When data deletion is required, the user constructs a hash chain by combining the Merkle hash tree (MHT) [41], the timestamp server, and the blockchain technique. The hash chain verifies whether the CSP has actually deleted the expired data by the value in the hash chain. Liu et al. [18] proposed a cloud data deletion verification protocol based on blockchain. Firstly, the personal identity is authenticated by the smart contract algorithm, and the deletion operation record is created at the same time. The CSP then deletes the expired data specified by the data owner and generates a hash value to join the blockchain by hashing operation. Finally, the user verifies the data deletion result through the blockchain.


## 2.4. ABE-Based Deletion and Verification

Xue et al. [35] proposed a secure deletion solution based on KP-ABE. The user encrypts data with the KP-ABE algorithm. When the expired data needs to be deleted, the users cannot decrypt and access the data by revoking the attribute corresponding to the expired data and reencrypting the data [42]. Before the cloud data storage, the data is encrypted, and a digital signature is generated for each data block in the ciphertext by a hash operation. This digital signature corresponds to the ciphertext attribute, and the validator is generated by the MHT and feeds it back to the user to verify the deletion result.The deletion operation in the process of deleting data based on the overwriting-based deletion verification scheme is coarse-grained; the encryption algorithm is used to encrypt the data to ensure the security of the data, but the key is not handled securely; thus, there is a key leakage issue [43, 44]. The PDP-based deletion verification scheme does not delete the ciphertext stored in the CSP. When an unauthorized user gets access to ciphertext and cracks the cloud ciphertext through the ciphertext analysis and brute force cracking, privacy information is faced with threat of leakage [45–47]. Aiming at the issues of unauthorized access, large computational cost in the process of data deletion, and inability to implement fine-grained deletion and verification data, this work focuses on a secure and effective cloud data deletion and verification solution to achieve fine-grained data security deletion and verification through flexible and effective key management.


## 3. Preliminaries

In this section, we give two preliminaries, Merkle hash tree and CP-ABE.


### 3.1. Merkle Hash Tree

MHT [41] is a full binary tree authentication data structure that can be used to verify the correctness of data storage [48]. Usually, the value on each node of the MHT is a hash value of stored data, and the value of a parent node is obtained by hashing the value of its child nodes; thus, the root node can be sequentially derived out by the leaf node. Suppose that there is a data set d1,d2,d3,d4; h4,h5,h6,h7 are the hash values of data set d1,d2,d3,d4, respectively. The hash value of the parent node is calculated from the child node until the hash value of the root node is obtained: h2=Hh4‖h5, h3=Hh6‖h7, h1=Hh2‖h3. In order to verify completeness and correctness of data d1,d2,d3,d4, the verifier can implement the goals by constructing MHT and calculating the root node.


### 3.2. CP-ABE

Sahai and Waters first proposed the idea of attribute-based encryption (ABE) [49]. As a typical ABE, the ciphertext-based attribute encryption algorithm (CP-ABE) is widely used in cloud data access control [50–52]. The main principle of CP-ABE is to set the attribute set A, private key SK, ciphertext CT, and access policy A. A is associated with CT, SK can be obtained through attribute set A, and access policy A is derived from attribute set A by the threshold function operation. The ciphertext can only be accessed if the value of threshold is met after the logical intersect operation between the user’s A and A associated with CT [53]. The CP-ABE algorithm is mainly composed of the following four algorithms:(i)
Initialization, performed by a trusted authority: it takes as input a security parameter and attribute descriptions, generates a public keyPK and a master key MK, and protects the confidentiality of MK.(ii)
Encryption, performed by the users: it takes as input a plaintextf, a system public key PK, and the access policy A and outputs a ciphertext CT. A=Λ,ρ through linear secret sharing scheme (LSSS), where Λ is a l×n matrix and function ρ is the line attribute tag function of Λ. A is implicitly included in the corresponding CT.(iii)
Key generation, performed by a trusted authority: it takes as input the master keyMK and an attribute set A used to describe the key and then outputs the private key SK.(iv)
Decryption, executed by the user: it takes as input the ciphertextCT and the private key SK. Ciphertext CT can only be decrypted if the attribute set satisfies the access policy A.


## 3.1. Merkle Hash Tree

MHT [41] is a full binary tree authentication data structure that can be used to verify the correctness of data storage [48]. Usually, the value on each node of the MHT is a hash value of stored data, and the value of a parent node is obtained by hashing the value of its child nodes; thus, the root node can be sequentially derived out by the leaf node. Suppose that there is a data set d1,d2,d3,d4; h4,h5,h6,h7 are the hash values of data set d1,d2,d3,d4, respectively. The hash value of the parent node is calculated from the child node until the hash value of the root node is obtained: h2=Hh4‖h5, h3=Hh6‖h7, h1=Hh2‖h3. In order to verify completeness and correctness of data d1,d2,d3,d4, the verifier can implement the goals by constructing MHT and calculating the root node.


## 3.2. CP-ABE

Sahai and Waters first proposed the idea of attribute-based encryption (ABE) [49]. As a typical ABE, the ciphertext-based attribute encryption algorithm (CP-ABE) is widely used in cloud data access control [50–52]. The main principle of CP-ABE is to set the attribute set A, private key SK, ciphertext CT, and access policy A. A is associated with CT, SK can be obtained through attribute set A, and access policy A is derived from attribute set A by the threshold function operation. The ciphertext can only be accessed if the value of threshold is met after the logical intersect operation between the user’s A and A associated with CT [53]. The CP-ABE algorithm is mainly composed of the following four algorithms:(i)
Initialization, performed by a trusted authority: it takes as input a security parameter and attribute descriptions, generates a public keyPK and a master key MK, and protects the confidentiality of MK.(ii)
Encryption, performed by the users: it takes as input a plaintextf, a system public key PK, and the access policy A and outputs a ciphertext CT. A=Λ,ρ through linear secret sharing scheme (LSSS), where Λ is a l×n matrix and function ρ is the line attribute tag function of Λ. A is implicitly included in the corresponding CT.(iii)
Key generation, performed by a trusted authority: it takes as input the master keyMK and an attribute set A used to describe the key and then outputs the private key SK.(iv)
Decryption, executed by the user: it takes as input the ciphertextCT and the private key SK. Ciphertext CT can only be decrypted if the attribute set satisfies the access policy A.


## 4. Problem Description

This section mainly describes the system model, scheme overview, security model, and implementation goals of the SDVC scheme. The main symbols and descriptions in the SDVC scheme are shown in Table2.Table 2
Symbols and descriptions.
SymbolDescriptionF, fData and subdata blocksCT, MFile ciphertext and key ciphertextdkSymmetric keyA, aAttribute and attribute valuesruleTransposition ruleσ, sigIndex and digital signatureMK, SK, PKMaster key, private key, and public keyH, hHash function and hash valueAAccess policyλ, γSecurity parameterruleTransposition rulevValidatorAttAttacker


### 4.1. System Model

The system model of SDVC scheme is shown in Figure1. It consists of four entities: cloud service provider, trusted authority, data owner, and data user.(i)
Cloud service provider (CSP): it has powerful computing power and storage resources and provides various services such as data storage and data distribution for users. CSP has the property of being “honest and curious” and may retain expired data driven by interest.(ii)
Trusted authority (TA): it starts the system initiating process, generates master key and public parameter, and securely protects users’ keys.(iii)
Data owner (DO): the use of various cloud applications in daily life makes the amount of data increasingly large. However, our smart devices have limited storage and computing resources, so the DO should lease CSP rich storage resources and computing resources for data storage and distribution.(iv)
Data user (DU): it requests the private key from the TA through the owned attribute set, and then DU retrieves data from the CSP. After the used data is expired, the plaintext, ciphertext, and key will be deleted in a timely manner.Figure 1
System model.Firstly, DO divides the original dataF into a number of data blocks f with 64 MB; after that, f is encrypted by using an AES-256 algorithm, and then the DO uploads the ciphertext to CSP. The TA generates the public key of the CP-ABE algorithm and publishes it to the DO, who encrypts the symmetric key dk by the CP-ABE algorithm through the public key and sends it to the TA. If the attribute set owned by the DU satisfies the access policy, then TA allocates a private key for the DU, who decrypts and obtains the dk by the private key of CP-ABE, and then decrypts the ciphertext to get the original data. When part of the data expires, the DO sends a deleting request to TA to delete the ciphertext of dk. The DO updates the attribute through the AAT, reencrypts the data-associated dk, and sends it to the TA using the new access policy. At the same time, the DO sends a random data block and deletion parameters to the CSP. The deletion parameter triggers the rule transposition algorithm to generate random data of the same size as the expired data, overwrites the expired data, and generates a validation value every time during the overwriting process for generation of verifier by the MHT. After the CSP overwrites the expired data, it returns the validator to the DO within a reasonable time range, and the DO compares it with the local validator to complete the verification.


### 4.2. Scheme Overview

The SDVC scheme is mainly composed of eleven algorithms: DO initializationDODeup, TA initialization TASetup, f encryption FileEnc, dk encryption DKEnc, private key generation SKGen, dk decryption DKDec, f decryption FileDec, attribute revocation ARev, rule transpose algorithm Transpose, overwriting algorithm OverWri, and verification algorithm Verify.DOSetup (1λ) is executed by DO. It takes a security parameter λ as input, generates a symmetric key dk, and constructs access policy A through attribute set A.TASetup (1γ) is completed by TA. It takes a security parameter γ as input, generates the public key PK of CP-ABE algorithm and master key MK, and then distributes PK to DO and maintains MK confidentiality.FileEnc (f,dk) is completed by DO. It takes plaintext data and symmetric key dk as input, generates ciphertext data CT by using AES-256 algorithm, and uploads CT to the CSP.DKEnc (dk,PK,A) is executed by DO. It uses public key PK and access strategy A to encrypt dk into ciphertext Mdk associated with A by CP-ABE algorithm and uploads Mdk to TA for secure storage.SKGen (MK,ψ) is completed by TA. It takes the master key MK and the corresponding attribute set ψ as input and outputs the private key SK of the CP-ABE algorithm.KeyDec (Mdk,SK) is completed by TA. It takes SK as input, and if the attribute set of DU satisfies the access policy A, TA decrypts Mdk and returns dk to DU.FileDec (CT,dk) is completed by DU. It takes dk and the ciphertext CT as input and outputs the plaintext F by AES-256 algorithm.AttRev (A) is completed by DO. DO revokes the attributes, rebuilds the access structure A′, and then uses PK and A′ to reencrypt dk to get Mdk′. After that, DO requests TA to update Mdk to Mdk′.Transpose (fR,rule) is completed by CSP. It takes as input a random data block fR and a transposition rule, rule, uploaded by DO. It outputs a random data block with the same size as the expired data by the RTA, and a hash value of each random data block by a hash function.OverWri (fR) is completed by CSP. It takes the generated random data block fR as input, overwrites the expired data block multiple times using a random overwriting algorithm, and generates a verification value at the same time.Verify (vRoot,vRoot′) is performed by DO. It generates the validator from verification value through MHT algorithm. DO compares the validator vRoot′ fed back from CSP with the locally generated validator vRoot, and the result will verify whether the expired data is successfully overwritten or deleted.


### 4.3. Security Model

The security model of the SDVC scheme mainly considers the confidentiality of the ciphertext when it is attacked by an attackerAtt after the data is deleted. It is well known that AES-256 cannot be compromised in probabilistic polynomial time (PPT), so this SDVC considers that Att will attack the key to decrypt data by allowing Att to query the private key of any access policy from TA except the target policy. The security model is formalized under indistinguishable encryption against chosen plaintext attack (IND-CPA) to the selected attribute set [51, 52].(i)
Initialization stage: the attackerAtt sets a series of attribute cracking keys and sends the attribute set to the challenger. Firstly, the challenger generates public key PK and master key MK, sends the PK to the attacker, and protects the confidentiality of the MK. Then, Att requests the private key SK from the challenger:Att sends a randomly constructed attribute set to the challenger, and the challenger executes the algorithm SKGen to generate Att’s private keys which are attribute-associated with Att except for satisfying the access structure A.(ii)
Challenge stage:Att selects two equal lengths of plaintext, respectively, M0, M1, and sends them to the challenger to request encryption; the challenger randomly chooses b∈0,1 and then returns ciphertext CTb to Att. At this stage, Att initiates a series of encryption requests and gets the feedback from the challenger.(iii)
Guess stage:Att outputs guess b′∈0,1; if b′=b, then Att wins in the challenge and regards Att as IND-CPA attacker. The advantage of attacking the SDVC scheme is(1)AdvAtt=Prb′−b−12.In all games, if the advantage of being successful, that is, the attacker achieves as many queries as possible, is negligible within the PPT under the decisional bilinear Diffie–Hellman (DBDH) problem, this indicates that the SDVC scheme is security.


#### 4.3.1. DBDH Definition

Consider that there are two multiplicative cyclic groupsG1 and G2 with big prime order p, g represents the generator of G1, and e:G1×G1⟶G2 represents a bilinear map. Given g,ga,gb,gc and h∈G2, we need to decide if h=eg,gabc is true.


#### 4.3.2. DBDH Hypothesis [54]

No PPT attackerAtt can distinguish quintuple β,β1,β2,β3,eβ,βz and β,β1′,β2′,β3′,eβ,βz′ with a probability greater than negligible, where z and z′ are random values from ℤP. The advantage of Att is(2)prβ,β1,β2,β3,eβ,βz=0−prβ,β1′,β2′,β3′,eβ,βz′=0,where the probability is taken over the selection of β∈G1.


### 4.4. Implementation Goals

The SDVC scheme mainly considers the following goals:(1)
Service availability: secure data deletion operations do not affect the use of other users’ data and any other services of the CSP.(2)
Unrecoverability: the expired data cannot be accessed by anyone after it is securely deleted in order to prevent unauthorized visitors from obtaining private information and attempt to recover deleted data.(3)
Fine-grained deletion: CSP deletes the specified data according to the user’s requirement, while other data cannot be affected.(4)
Timeliness of deletion: the data deletion operation needs to be timely and rapid. When the data is deleted, no one can access the deleted data.(5)
Deletion verification: the CSP deletes the data and returns the deletion certificate to the user to prove that the data has been securely deleted. Therefore, users do not have to worry about the risk of privacy leakage after deleting the expired data.


## 4.1. System Model

The system model of SDVC scheme is shown in Figure1. It consists of four entities: cloud service provider, trusted authority, data owner, and data user.(i)
Cloud service provider (CSP): it has powerful computing power and storage resources and provides various services such as data storage and data distribution for users. CSP has the property of being “honest and curious” and may retain expired data driven by interest.(ii)
Trusted authority (TA): it starts the system initiating process, generates master key and public parameter, and securely protects users’ keys.(iii)
Data owner (DO): the use of various cloud applications in daily life makes the amount of data increasingly large. However, our smart devices have limited storage and computing resources, so the DO should lease CSP rich storage resources and computing resources for data storage and distribution.(iv)
Data user (DU): it requests the private key from the TA through the owned attribute set, and then DU retrieves data from the CSP. After the used data is expired, the plaintext, ciphertext, and key will be deleted in a timely manner.Figure 1
System model.Firstly, DO divides the original dataF into a number of data blocks f with 64 MB; after that, f is encrypted by using an AES-256 algorithm, and then the DO uploads the ciphertext to CSP. The TA generates the public key of the CP-ABE algorithm and publishes it to the DO, who encrypts the symmetric key dk by the CP-ABE algorithm through the public key and sends it to the TA. If the attribute set owned by the DU satisfies the access policy, then TA allocates a private key for the DU, who decrypts and obtains the dk by the private key of CP-ABE, and then decrypts the ciphertext to get the original data. When part of the data expires, the DO sends a deleting request to TA to delete the ciphertext of dk. The DO updates the attribute through the AAT, reencrypts the data-associated dk, and sends it to the TA using the new access policy. At the same time, the DO sends a random data block and deletion parameters to the CSP. The deletion parameter triggers the rule transposition algorithm to generate random data of the same size as the expired data, overwrites the expired data, and generates a validation value every time during the overwriting process for generation of verifier by the MHT. After the CSP overwrites the expired data, it returns the validator to the DO within a reasonable time range, and the DO compares it with the local validator to complete the verification.


## 4.2. Scheme Overview

The SDVC scheme is mainly composed of eleven algorithms: DO initializationDODeup, TA initialization TASetup, f encryption FileEnc, dk encryption DKEnc, private key generation SKGen, dk decryption DKDec, f decryption FileDec, attribute revocation ARev, rule transpose algorithm Transpose, overwriting algorithm OverWri, and verification algorithm Verify.DOSetup (1λ) is executed by DO. It takes a security parameter λ as input, generates a symmetric key dk, and constructs access policy A through attribute set A.TASetup (1γ) is completed by TA. It takes a security parameter γ as input, generates the public key PK of CP-ABE algorithm and master key MK, and then distributes PK to DO and maintains MK confidentiality.FileEnc (f,dk) is completed by DO. It takes plaintext data and symmetric key dk as input, generates ciphertext data CT by using AES-256 algorithm, and uploads CT to the CSP.DKEnc (dk,PK,A) is executed by DO. It uses public key PK and access strategy A to encrypt dk into ciphertext Mdk associated with A by CP-ABE algorithm and uploads Mdk to TA for secure storage.SKGen (MK,ψ) is completed by TA. It takes the master key MK and the corresponding attribute set ψ as input and outputs the private key SK of the CP-ABE algorithm.KeyDec (Mdk,SK) is completed by TA. It takes SK as input, and if the attribute set of DU satisfies the access policy A, TA decrypts Mdk and returns dk to DU.FileDec (CT,dk) is completed by DU. It takes dk and the ciphertext CT as input and outputs the plaintext F by AES-256 algorithm.AttRev (A) is completed by DO. DO revokes the attributes, rebuilds the access structure A′, and then uses PK and A′ to reencrypt dk to get Mdk′. After that, DO requests TA to update Mdk to Mdk′.Transpose (fR,rule) is completed by CSP. It takes as input a random data block fR and a transposition rule, rule, uploaded by DO. It outputs a random data block with the same size as the expired data by the RTA, and a hash value of each random data block by a hash function.OverWri (fR) is completed by CSP. It takes the generated random data block fR as input, overwrites the expired data block multiple times using a random overwriting algorithm, and generates a verification value at the same time.Verify (vRoot,vRoot′) is performed by DO. It generates the validator from verification value through MHT algorithm. DO compares the validator vRoot′ fed back from CSP with the locally generated validator vRoot, and the result will verify whether the expired data is successfully overwritten or deleted.


## 4.3. Security Model

The security model of the SDVC scheme mainly considers the confidentiality of the ciphertext when it is attacked by an attackerAtt after the data is deleted. It is well known that AES-256 cannot be compromised in probabilistic polynomial time (PPT), so this SDVC considers that Att will attack the key to decrypt data by allowing Att to query the private key of any access policy from TA except the target policy. The security model is formalized under indistinguishable encryption against chosen plaintext attack (IND-CPA) to the selected attribute set [51, 52].(i)
Initialization stage: the attackerAtt sets a series of attribute cracking keys and sends the attribute set to the challenger. Firstly, the challenger generates public key PK and master key MK, sends the PK to the attacker, and protects the confidentiality of the MK. Then, Att requests the private key SK from the challenger:Att sends a randomly constructed attribute set to the challenger, and the challenger executes the algorithm SKGen to generate Att’s private keys which are attribute-associated with Att except for satisfying the access structure A.(ii)
Challenge stage:Att selects two equal lengths of plaintext, respectively, M0, M1, and sends them to the challenger to request encryption; the challenger randomly chooses b∈0,1 and then returns ciphertext CTb to Att. At this stage, Att initiates a series of encryption requests and gets the feedback from the challenger.(iii)
Guess stage:Att outputs guess b′∈0,1; if b′=b, then Att wins in the challenge and regards Att as IND-CPA attacker. The advantage of attacking the SDVC scheme is(1)AdvAtt=Prb′−b−12.In all games, if the advantage of being successful, that is, the attacker achieves as many queries as possible, is negligible within the PPT under the decisional bilinear Diffie–Hellman (DBDH) problem, this indicates that the SDVC scheme is security.


### 4.3.1. DBDH Definition

Consider that there are two multiplicative cyclic groupsG1 and G2 with big prime order p, g represents the generator of G1, and e:G1×G1⟶G2 represents a bilinear map. Given g,ga,gb,gc and h∈G2, we need to decide if h=eg,gabc is true.


### 4.3.2. DBDH Hypothesis [54]

No PPT attackerAtt can distinguish quintuple β,β1,β2,β3,eβ,βz and β,β1′,β2′,β3′,eβ,βz′ with a probability greater than negligible, where z and z′ are random values from ℤP. The advantage of Att is(2)prβ,β1,β2,β3,eβ,βz=0−prβ,β1′,β2′,β3′,eβ,βz′=0,where the probability is taken over the selection of β∈G1.


## 4.3.1. DBDH Definition

Consider that there are two multiplicative cyclic groupsG1 and G2 with big prime order p, g represents the generator of G1, and e:G1×G1⟶G2 represents a bilinear map. Given g,ga,gb,gc and h∈G2, we need to decide if h=eg,gabc is true.


## 4.3.2. DBDH Hypothesis [54]

No PPT attackerAtt can distinguish quintuple β,β1,β2,β3,eβ,βz and β,β1′,β2′,β3′,eβ,βz′ with a probability greater than negligible, where z and z′ are random values from ℤP. The advantage of Att is(2)prβ,β1,β2,β3,eβ,βz=0−prβ,β1′,β2′,β3′,eβ,βz′=0,where the probability is taken over the selection of β∈G1.


## 4.4. Implementation Goals

The SDVC scheme mainly considers the following goals:(1)
Service availability: secure data deletion operations do not affect the use of other users’ data and any other services of the CSP.(2)
Unrecoverability: the expired data cannot be accessed by anyone after it is securely deleted in order to prevent unauthorized visitors from obtaining private information and attempt to recover deleted data.(3)
Fine-grained deletion: CSP deletes the specified data according to the user’s requirement, while other data cannot be affected.(4)
Timeliness of deletion: the data deletion operation needs to be timely and rapid. When the data is deleted, no one can access the deleted data.(5)
Deletion verification: the CSP deletes the data and returns the deletion certificate to the user to prove that the data has been securely deleted. Therefore, users do not have to worry about the risk of privacy leakage after deleting the expired data.


## 5. Construction of the SDVC Scheme

The SDVC scheme mainly consists of data encryption and decryption phase, secure data deletion phase, and data deletion verification phase.


### 5.1. Data Encryption and Decryption Stage

#### 5.1.1. Data Encryption

Firstly, fileF is divided into n subfile data blocks f1,f2,…,fn, and the hash value of each subfile is calculated as the index value σ1,σ2,…,σn, with each index value pointing to a subfile. To achieve fine-grained deletion of files, file encryption operations are performed in units of data blocks. In order to get block of ciphertext cti, DO generates a symmetric key dki through security parameters λ and separately encrypts fi by AES-256 algorithm. After encryption, DU saves σ1,σ2,…,σn and other metadata, and DO generates all possible attribute sets A1,A2,…,An and sets the attribute weight value. Attributes have different values Ai=ai,1,ai,2,…,ai,n; according to different sensitivity levels, the data blocks are arranged in different attribute sets. Attribute value set a1,a2,…,am is mapped to hash set h1,h2,…,hm satisfying finite field by using anticollision hash function H:0,1∗←ℤP. Then, the access policy is constructed by the hash set and DO requests public key of CP-ABE from TA. TA selects two multiplicative cyclic groups G1 and G2 with big prime order p, for which there exists a bilinear map e:G1×G1⟶G2, and the generator of G1 is g. Indexes α, β (αβ∈ℤP, and ℤP is a finite field with prime order p) are selected randomly and gα,gβ, and eg,gα are calculated. Then, TA calculates the public key PK = e,g,gβ,eg,gα and the master key MK. After that, TA securely stores MK and sends PK to DO.


#### 5.1.2. Key Encryption

When encrypting symmetric keydk, the attribute set h1,h2,…,hm is used to build access policies A=Λ,ρ. To get ciphertext CTdk, dk is encrypted by using public key PK and A=Λ,ρ through CP-ABE algorithm. The equations for the encryption process of dk are as follows:(3)υ⟶=s,y1,y2,…,yn∈ℤp,λi=υ⟶⋅Λii=1,…,l,r1,…,rl∈ℤp,CTdk=ct=dk⋅eg,gαs,c′=gs,c1=gαλ1hρ1−r1,θ1=gr1,…,cn=gαλlhρl−rl,θl=grl.In fact, theυ⟶=s,y1,y2,…,yn is used to split the encryption index s and then distribute a random index s∈ℤP according to Λ, λi=υ⟶⋅Λii=1,…,l is the i-th share of the splits, and cii=1,2,…,l associates λi with the ρi property value. Symmetric keys dk1,dk2,…,dkn are encrypted into ciphertext CTdk1,CTdk2,…,CTdkn by the above encryption process and generate the corresponding digital signature SIG=sig1,sig2,…,sign. DO encapsulates the file ciphertext, index value, and digital signature CT1,σ1,sig1,CT2,σ2,sig2,…,CTn,σn,sign and uploads them to CSP for storage. Meanwhile, the ciphertext of the symmetric key CTdk1,CTdk2,…,CTdkn is uploaded to TA.


#### 5.1.3. Data Decryption

DU sends its own attribute set to the TA to request the private key of CP-AES. TA takes as input the master keyMK, public key PK, and attribute set ψ; selects index φ∈ℤP randomly; calculates δ=gαgβφ, L=gφ, δx=hxφ (∀x∈ψ); and then generates a private key SK=δ,L,δxx∈ψ. If the attribute set of DU is satisfied with the access policy corresponding to the CTdk, the ciphertext CTdk can be decrypted by the SK. Define I=i:ρi∈ψ⊂1,2,…,l; let ωi∈Zq|i∈I; if λi is the effective share in the matrix Λ corresponding to random indexes, then ∑i∈Iωiλi=s. If the attribute set ψ of DU does not meet the access policy, you cannot get the real dk. The decryption process is represented as follows:(4)DesCTdk=ct⋅∏i∈Ieci,γ⋅eθi,δρiωiec′,δ,(5)∏i∈Ieci,γ⋅eθi,δρiωiec′,δ=∏i∈Ieg,gφβλiωieg,gαs⋅eg,gβsφ=1eg,gαs.


#### 5.1.4. The Decryption of File Ciphertext

The DU is authorized to request the file ciphertext within the range of permission from CSP. After downloading the ciphertext, DU uses the symmetric keydk to get the file f obtained by decrypting the ciphertext through AES-256 algorithm, and finally gets the original file F.


### 5.2. Secure Data Deletion Phase

The secure data deletion phase is completed by the attribute revocation of the CP-ABE algorithm and random overwriting algorithm.Attribute revocation implements the fine-grained, timely, and logical secure deletion for the expired data in CSP. SDVC scheme constructs an AAT and assumes thatn DUs uid1,uid2,…,uidn have different attribute sets ψ1,ψ2,…,ψn, and each attribute set has multiple attribute values ψi=h1,h2,…,hl. The amount of data in CSP is relatively large, and, usually, different file data blocks will be accessed by different DUs. To achieve efficient attribute revocation, the association form of each attribute value of DU is formally described as an AAT based on multibranch tree in the data structure. The highest level of attribute value in the attribute set is selected as a root node of the AAT. The main attributes usually have a high level; for example, H (“Group 1”) or H (“Group 2”)… is the root node; H (“Subsidiary 1”) or H (“Subsidiary 2”)…, H (“Department 1”) or H (“Department 2”)…, and H (“Group 1”) or H (“Group 2”)… are child nodes. The AAT is established through the relationship among the attributes, assuming that the data block is d1,d2,…,d9, as shown in Figure 2. The attribute revocation is divided into two cases: the leaf nodes of the attribute set share the same parent node; the leaf nodes of the attribute set are associated with different parent nodes, respectively.(1)
The leaf nodes of AAT share the same attribute of parent node, and there exists the expired datad1,d2,d3. The attribute set of the access policy related to data block d1 is h1,h2,h5, and the attribute set corresponding to d2 is h1,h2,h6, while the attribute set of d3 is h1,h2,h7. Because the leaf nodes of the attributes of d1,d2,d3 share the same parent node, we update the attribute of parent node h2 to implement the attribute revocation of the expired data d1,d2,d3.(2)
The leaf nodes of AAT do not share the same attribute of parent node, and there exists the expired datad1,d4,d7. The attribute set of the access policy related to data block d1 is h1,h2,h5, the attribute set of d4 is h1,h3,h8, and the attribute set of d7 is h1,h4,h11. Because the leaf nodes of the attributes of d1,d4,d7 are associated with different parent node, respectively, the attribute values of the three leaf nodes need to be updated separately to implement the attribute revocation of the expired data d1,d4,d7.Figure 2
Attribute association tree (AAT).DO reencrypts the symmetric keydk to obtain the ciphertext CTdk′ and the digital signature sig′ using new access policy constructed by the updated attribute, uploads CTdk′ to TA, and deletes CTdk. Therefore, the original attributes of the DU cannot be satisfied with the access structure of CTdk′, so DU is unable to decrypt CTdk′ and cannot decrypt the file ciphertext.Random overwriting implements assured deletion for the expired data in CSP. In order to completely delete cloud data and prevent the privacy leakage caused by key leakage or brute force attack [55], the expired data is randomly overwritten by random data of the same size as the expired data, thereby achieving complete data deletion. In order to reduce the computational cost of the DO to generate random data blocks and the communication overhead of uploading them, a rule transposition algorithm (RTA) is designed based on transposition algorithm [56, 57]. The implementation process of RTA is described as follows. Firstly, the DO generates a random data block fR and a transposing rule which is called “rule.” Rule contains parameters l1,S,l2,m, among which, l1 represents a subblock with l1-bit sizes divided from fR, S indicates the initial value of the interval between subblocks transposed, l2 represents a fixed length value, and m is the number of overwriting data blocks. σ1,σ2,…,σm is the index value of the expired data block. Let fR and l1,S,l2,m be the input of the RTA, and let data blocks fr1,fr2,…,frm equaling to expired data and generated by fR in sequence be the output.The process of generation of data blockfr1 is described as follows. fR is divided into n subblocks dr1,dr2,…,drn with the equal size of l1 bits. The n subblocks dr1,dr2,…,drn are transposed successively to construct a data block fr1 according to the value interval S+l2. For example, when S0=0 and l2=1, let S1=S0+l2; we exchange di,di+S1 in terms of subblocks to get d2,d1,d4,d3,…,dn,dn−1 and reconstitute the data block fr1. When we transpose fr2, let S2=S1+l2, and transpose the subblocks of fR to generate fr2 according to the value interval S2. In a similar way, data block fri is generated from the subblocks dr1,dr2,…,drn according to the value interval Si=Si−1+l2. Therefore, we get TransposefR,rule⟶fr1,fr2,…,frm. The RTA generates the same amount of data blocks with the equal size to the expired ciphertext and obtains an index σ1′,σ2′,…,σm′ of the data block by hash algorithm.DO uploadsfRσ1,σ2,…,σm and rule to CSP to request deleting expired data and save the fR and rule. After receiving the request, CSP generates a series of random data blocks using RTA triggered by fR and rule. The expired data blocks with an index of σ1,σ2,…,σm are randomly overwritten multiple times by means of bitstream overwriting using new random data blocks with σ1′,σ2′,…,σm′, thereby implementing the secure deletion of the expired ciphertext. The brief workflow is shown in Algorithm 1.Algorithm 1: Rule transposition process.
input:random data blockfRtranspose ruleoutput:a series of random data blocks(1)
Begin;(2)
forj←0 to mdo(3)
DivideFilefR,l1⟶dr1,dr2,…,drn;(4)
fori←1 to ⌈n/2⌉do(5)
Si=Si−1+l2;(6)
di=di⊕di+Si;(7)
di+S1=di+Si⊕di;(8)
di=di⊕di+Si;(9)
end for(10)
Mergerd1+Si,d2+Si,…,dn−Si⟶frj;(11)
σj′=Hashfrj;(12)
end for


### 5.3. Data Deletion Verification Phase

The data deletion verification method is used to verify whether the “honest but curious” CSP actually deleted the expired ciphertext. When CSP overwrites the expired ciphertext, there is a risk of forging an index or not generating corresponding random data according to a givenrule due to the fact that the index σ1′,σ2′,…,σm′ is generated by CSP. After the expired ciphertext CT1,CT2,…,CTm is overwritten by fr1,fr2,…,frm successively, DO promptly gets the random data from CSP based on σ1′,σ2′,…,σm′; for example, σ2′,σ5′ corresponds to fr2,fr5; then, DO locally generates the random data blocks fr2′,fr5′ by fR and rule via RTA and uses the hash algorithm to calculate the hash value Hfr2′,Hfr5′ of fr2′,fr5′, respectively. If CSP does not generate data according to the specified transposition rule, σ2′=Hfr2′, σ5′=Hfr5′, fr2=fr2′, and fr5=fr5′ cannot be satisfied at the same time. Otherwise, the random data blocks and indexes σ1′,σ2′,…,σm′ generated by CSP are real.Furthermore, for the next step of verification, CSP successively concatenates the indexσi of the expired ciphertext block, index σi′ of fri, and digital signature sigi′ of CTdki to generate deletion verification value vi, vi=σiσi′sigi′, which is used to generate the root node value vR as a validator by MHT, as shown in Figure 3. Assuming that the expired ciphertext is CT1,CT2,…,CT8 and the generated verification value is v1,v2,…,v8, CSP makes hash to the verification values and concatenates them separately to generate the verification values of the parent nodes, Hvi,j=Hvi‖Hvj. Finally, the root node verifier vR is generated by working up layer by layer. CSP will generate a validator vR and return to DU.Figure 3
Process of validator generation.DO generates local verification valuevi′=σiσi′sigi′ by concatenating locally reserved index of σ1,σ2,…,σn, digital signature sig1,sig2,…,sign, and index σ1′,σ2′,…,σm′ returned by CSP. Furthermore, DO calculates a local validator vR′ by MHT algorithm and compares it with the returned vR from CSP. If the two validators are inconsistent, this indicates that the verification value of the leaf node is incorrect, so CSP does not overwrite the partially expired ciphertext. Otherwise, it indicates that CSP completely overwrites the expired ciphertext. This process is shown in Algorithm 2.Algorithm 2: Data deletion and verification process.
input: random data block and its index, expired ciphertext and its index, sigioutput: the verification result(1)
Cloud service provider:(2)
fori←0 to mdo(3)
vi=σi′σisigi;(4)
Overwrifri,CTi;(5)
end for(6)
vR=MHTv1,v2,…,vm;(7)
SentvR and σ1′,σ2′,…,σm′ to data owners;(8)
Data owner:(9)
TransposefR,rule⟶fri′;(10)
σi=Hfri′;(11)
ifσi=σi′then(12)
flag=1;(13)
end if(14)
ifflag=1then(15)
fori←0 to numdo(16)
vi′=σi′σisigi;(17)
end for(18)
vR′=MHTv1′,v2′,…,vm′;(19)
end if(20)
ifvR′=vRthen(21)
returnTRUE;(22)
else(23)
returnFALSE;(24)
end if


## 5.1. Data Encryption and Decryption Stage

### 5.1.1. Data Encryption

Firstly, fileF is divided into n subfile data blocks f1,f2,…,fn, and the hash value of each subfile is calculated as the index value σ1,σ2,…,σn, with each index value pointing to a subfile. To achieve fine-grained deletion of files, file encryption operations are performed in units of data blocks. In order to get block of ciphertext cti, DO generates a symmetric key dki through security parameters λ and separately encrypts fi by AES-256 algorithm. After encryption, DU saves σ1,σ2,…,σn and other metadata, and DO generates all possible attribute sets A1,A2,…,An and sets the attribute weight value. Attributes have different values Ai=ai,1,ai,2,…,ai,n; according to different sensitivity levels, the data blocks are arranged in different attribute sets. Attribute value set a1,a2,…,am is mapped to hash set h1,h2,…,hm satisfying finite field by using anticollision hash function H:0,1∗←ℤP. Then, the access policy is constructed by the hash set and DO requests public key of CP-ABE from TA. TA selects two multiplicative cyclic groups G1 and G2 with big prime order p, for which there exists a bilinear map e:G1×G1⟶G2, and the generator of G1 is g. Indexes α, β (αβ∈ℤP, and ℤP is a finite field with prime order p) are selected randomly and gα,gβ, and eg,gα are calculated. Then, TA calculates the public key PK = e,g,gβ,eg,gα and the master key MK. After that, TA securely stores MK and sends PK to DO.


### 5.1.2. Key Encryption

When encrypting symmetric keydk, the attribute set h1,h2,…,hm is used to build access policies A=Λ,ρ. To get ciphertext CTdk, dk is encrypted by using public key PK and A=Λ,ρ through CP-ABE algorithm. The equations for the encryption process of dk are as follows:(3)υ⟶=s,y1,y2,…,yn∈ℤp,λi=υ⟶⋅Λii=1,…,l,r1,…,rl∈ℤp,CTdk=ct=dk⋅eg,gαs,c′=gs,c1=gαλ1hρ1−r1,θ1=gr1,…,cn=gαλlhρl−rl,θl=grl.In fact, theυ⟶=s,y1,y2,…,yn is used to split the encryption index s and then distribute a random index s∈ℤP according to Λ, λi=υ⟶⋅Λii=1,…,l is the i-th share of the splits, and cii=1,2,…,l associates λi with the ρi property value. Symmetric keys dk1,dk2,…,dkn are encrypted into ciphertext CTdk1,CTdk2,…,CTdkn by the above encryption process and generate the corresponding digital signature SIG=sig1,sig2,…,sign. DO encapsulates the file ciphertext, index value, and digital signature CT1,σ1,sig1,CT2,σ2,sig2,…,CTn,σn,sign and uploads them to CSP for storage. Meanwhile, the ciphertext of the symmetric key CTdk1,CTdk2,…,CTdkn is uploaded to TA.


### 5.1.3. Data Decryption

DU sends its own attribute set to the TA to request the private key of CP-AES. TA takes as input the master keyMK, public key PK, and attribute set ψ; selects index φ∈ℤP randomly; calculates δ=gαgβφ, L=gφ, δx=hxφ (∀x∈ψ); and then generates a private key SK=δ,L,δxx∈ψ. If the attribute set of DU is satisfied with the access policy corresponding to the CTdk, the ciphertext CTdk can be decrypted by the SK. Define I=i:ρi∈ψ⊂1,2,…,l; let ωi∈Zq|i∈I; if λi is the effective share in the matrix Λ corresponding to random indexes, then ∑i∈Iωiλi=s. If the attribute set ψ of DU does not meet the access policy, you cannot get the real dk. The decryption process is represented as follows:(4)DesCTdk=ct⋅∏i∈Ieci,γ⋅eθi,δρiωiec′,δ,(5)∏i∈Ieci,γ⋅eθi,δρiωiec′,δ=∏i∈Ieg,gφβλiωieg,gαs⋅eg,gβsφ=1eg,gαs.


### 5.1.4. The Decryption of File Ciphertext

The DU is authorized to request the file ciphertext within the range of permission from CSP. After downloading the ciphertext, DU uses the symmetric keydk to get the file f obtained by decrypting the ciphertext through AES-256 algorithm, and finally gets the original file F.


## 5.1.1. Data Encryption

Firstly, fileF is divided into n subfile data blocks f1,f2,…,fn, and the hash value of each subfile is calculated as the index value σ1,σ2,…,σn, with each index value pointing to a subfile. To achieve fine-grained deletion of files, file encryption operations are performed in units of data blocks. In order to get block of ciphertext cti, DO generates a symmetric key dki through security parameters λ and separately encrypts fi by AES-256 algorithm. After encryption, DU saves σ1,σ2,…,σn and other metadata, and DO generates all possible attribute sets A1,A2,…,An and sets the attribute weight value. Attributes have different values Ai=ai,1,ai,2,…,ai,n; according to different sensitivity levels, the data blocks are arranged in different attribute sets. Attribute value set a1,a2,…,am is mapped to hash set h1,h2,…,hm satisfying finite field by using anticollision hash function H:0,1∗←ℤP. Then, the access policy is constructed by the hash set and DO requests public key of CP-ABE from TA. TA selects two multiplicative cyclic groups G1 and G2 with big prime order p, for which there exists a bilinear map e:G1×G1⟶G2, and the generator of G1 is g. Indexes α, β (αβ∈ℤP, and ℤP is a finite field with prime order p) are selected randomly and gα,gβ, and eg,gα are calculated. Then, TA calculates the public key PK = e,g,gβ,eg,gα and the master key MK. After that, TA securely stores MK and sends PK to DO.


## 5.1.2. Key Encryption

When encrypting symmetric keydk, the attribute set h1,h2,…,hm is used to build access policies A=Λ,ρ. To get ciphertext CTdk, dk is encrypted by using public key PK and A=Λ,ρ through CP-ABE algorithm. The equations for the encryption process of dk are as follows:(3)υ⟶=s,y1,y2,…,yn∈ℤp,λi=υ⟶⋅Λii=1,…,l,r1,…,rl∈ℤp,CTdk=ct=dk⋅eg,gαs,c′=gs,c1=gαλ1hρ1−r1,θ1=gr1,…,cn=gαλlhρl−rl,θl=grl.In fact, theυ⟶=s,y1,y2,…,yn is used to split the encryption index s and then distribute a random index s∈ℤP according to Λ, λi=υ⟶⋅Λii=1,…,l is the i-th share of the splits, and cii=1,2,…,l associates λi with the ρi property value. Symmetric keys dk1,dk2,…,dkn are encrypted into ciphertext CTdk1,CTdk2,…,CTdkn by the above encryption process and generate the corresponding digital signature SIG=sig1,sig2,…,sign. DO encapsulates the file ciphertext, index value, and digital signature CT1,σ1,sig1,CT2,σ2,sig2,…,CTn,σn,sign and uploads them to CSP for storage. Meanwhile, the ciphertext of the symmetric key CTdk1,CTdk2,…,CTdkn is uploaded to TA.


## 5.1.3. Data Decryption

DU sends its own attribute set to the TA to request the private key of CP-AES. TA takes as input the master keyMK, public key PK, and attribute set ψ; selects index φ∈ℤP randomly; calculates δ=gαgβφ, L=gφ, δx=hxφ (∀x∈ψ); and then generates a private key SK=δ,L,δxx∈ψ. If the attribute set of DU is satisfied with the access policy corresponding to the CTdk, the ciphertext CTdk can be decrypted by the SK. Define I=i:ρi∈ψ⊂1,2,…,l; let ωi∈Zq|i∈I; if λi is the effective share in the matrix Λ corresponding to random indexes, then ∑i∈Iωiλi=s. If the attribute set ψ of DU does not meet the access policy, you cannot get the real dk. The decryption process is represented as follows:(4)DesCTdk=ct⋅∏i∈Ieci,γ⋅eθi,δρiωiec′,δ,(5)∏i∈Ieci,γ⋅eθi,δρiωiec′,δ=∏i∈Ieg,gφβλiωieg,gαs⋅eg,gβsφ=1eg,gαs.


## 5.1.4. The Decryption of File Ciphertext

The DU is authorized to request the file ciphertext within the range of permission from CSP. After downloading the ciphertext, DU uses the symmetric keydk to get the file f obtained by decrypting the ciphertext through AES-256 algorithm, and finally gets the original file F.


## 5.2. Secure Data Deletion Phase

The secure data deletion phase is completed by the attribute revocation of the CP-ABE algorithm and random overwriting algorithm.Attribute revocation implements the fine-grained, timely, and logical secure deletion for the expired data in CSP. SDVC scheme constructs an AAT and assumes thatn DUs uid1,uid2,…,uidn have different attribute sets ψ1,ψ2,…,ψn, and each attribute set has multiple attribute values ψi=h1,h2,…,hl. The amount of data in CSP is relatively large, and, usually, different file data blocks will be accessed by different DUs. To achieve efficient attribute revocation, the association form of each attribute value of DU is formally described as an AAT based on multibranch tree in the data structure. The highest level of attribute value in the attribute set is selected as a root node of the AAT. The main attributes usually have a high level; for example, H (“Group 1”) or H (“Group 2”)… is the root node; H (“Subsidiary 1”) or H (“Subsidiary 2”)…, H (“Department 1”) or H (“Department 2”)…, and H (“Group 1”) or H (“Group 2”)… are child nodes. The AAT is established through the relationship among the attributes, assuming that the data block is d1,d2,…,d9, as shown in Figure 2. The attribute revocation is divided into two cases: the leaf nodes of the attribute set share the same parent node; the leaf nodes of the attribute set are associated with different parent nodes, respectively.(1)
The leaf nodes of AAT share the same attribute of parent node, and there exists the expired datad1,d2,d3. The attribute set of the access policy related to data block d1 is h1,h2,h5, and the attribute set corresponding to d2 is h1,h2,h6, while the attribute set of d3 is h1,h2,h7. Because the leaf nodes of the attributes of d1,d2,d3 share the same parent node, we update the attribute of parent node h2 to implement the attribute revocation of the expired data d1,d2,d3.(2)
The leaf nodes of AAT do not share the same attribute of parent node, and there exists the expired datad1,d4,d7. The attribute set of the access policy related to data block d1 is h1,h2,h5, the attribute set of d4 is h1,h3,h8, and the attribute set of d7 is h1,h4,h11. Because the leaf nodes of the attributes of d1,d4,d7 are associated with different parent node, respectively, the attribute values of the three leaf nodes need to be updated separately to implement the attribute revocation of the expired data d1,d4,d7.Figure 2
Attribute association tree (AAT).DO reencrypts the symmetric keydk to obtain the ciphertext CTdk′ and the digital signature sig′ using new access policy constructed by the updated attribute, uploads CTdk′ to TA, and deletes CTdk. Therefore, the original attributes of the DU cannot be satisfied with the access structure of CTdk′, so DU is unable to decrypt CTdk′ and cannot decrypt the file ciphertext.Random overwriting implements assured deletion for the expired data in CSP. In order to completely delete cloud data and prevent the privacy leakage caused by key leakage or brute force attack [55], the expired data is randomly overwritten by random data of the same size as the expired data, thereby achieving complete data deletion. In order to reduce the computational cost of the DO to generate random data blocks and the communication overhead of uploading them, a rule transposition algorithm (RTA) is designed based on transposition algorithm [56, 57]. The implementation process of RTA is described as follows. Firstly, the DO generates a random data block fR and a transposing rule which is called “rule.” Rule contains parameters l1,S,l2,m, among which, l1 represents a subblock with l1-bit sizes divided from fR, S indicates the initial value of the interval between subblocks transposed, l2 represents a fixed length value, and m is the number of overwriting data blocks. σ1,σ2,…,σm is the index value of the expired data block. Let fR and l1,S,l2,m be the input of the RTA, and let data blocks fr1,fr2,…,frm equaling to expired data and generated by fR in sequence be the output.The process of generation of data blockfr1 is described as follows. fR is divided into n subblocks dr1,dr2,…,drn with the equal size of l1 bits. The n subblocks dr1,dr2,…,drn are transposed successively to construct a data block fr1 according to the value interval S+l2. For example, when S0=0 and l2=1, let S1=S0+l2; we exchange di,di+S1 in terms of subblocks to get d2,d1,d4,d3,…,dn,dn−1 and reconstitute the data block fr1. When we transpose fr2, let S2=S1+l2, and transpose the subblocks of fR to generate fr2 according to the value interval S2. In a similar way, data block fri is generated from the subblocks dr1,dr2,…,drn according to the value interval Si=Si−1+l2. Therefore, we get TransposefR,rule⟶fr1,fr2,…,frm. The RTA generates the same amount of data blocks with the equal size to the expired ciphertext and obtains an index σ1′,σ2′,…,σm′ of the data block by hash algorithm.DO uploadsfRσ1,σ2,…,σm and rule to CSP to request deleting expired data and save the fR and rule. After receiving the request, CSP generates a series of random data blocks using RTA triggered by fR and rule. The expired data blocks with an index of σ1,σ2,…,σm are randomly overwritten multiple times by means of bitstream overwriting using new random data blocks with σ1′,σ2′,…,σm′, thereby implementing the secure deletion of the expired ciphertext. The brief workflow is shown in Algorithm 1.Algorithm 1: Rule transposition process.
input:random data blockfRtranspose ruleoutput:a series of random data blocks(1)
Begin;(2)
forj←0 to mdo(3)
DivideFilefR,l1⟶dr1,dr2,…,drn;(4)
fori←1 to ⌈n/2⌉do(5)
Si=Si−1+l2;(6)
di=di⊕di+Si;(7)
di+S1=di+Si⊕di;(8)
di=di⊕di+Si;(9)
end for(10)
Mergerd1+Si,d2+Si,…,dn−Si⟶frj;(11)
σj′=Hashfrj;(12)
end for


## 5.3. Data Deletion Verification Phase

The data deletion verification method is used to verify whether the “honest but curious” CSP actually deleted the expired ciphertext. When CSP overwrites the expired ciphertext, there is a risk of forging an index or not generating corresponding random data according to a givenrule due to the fact that the index σ1′,σ2′,…,σm′ is generated by CSP. After the expired ciphertext CT1,CT2,…,CTm is overwritten by fr1,fr2,…,frm successively, DO promptly gets the random data from CSP based on σ1′,σ2′,…,σm′; for example, σ2′,σ5′ corresponds to fr2,fr5; then, DO locally generates the random data blocks fr2′,fr5′ by fR and rule via RTA and uses the hash algorithm to calculate the hash value Hfr2′,Hfr5′ of fr2′,fr5′, respectively. If CSP does not generate data according to the specified transposition rule, σ2′=Hfr2′, σ5′=Hfr5′, fr2=fr2′, and fr5=fr5′ cannot be satisfied at the same time. Otherwise, the random data blocks and indexes σ1′,σ2′,…,σm′ generated by CSP are real.Furthermore, for the next step of verification, CSP successively concatenates the indexσi of the expired ciphertext block, index σi′ of fri, and digital signature sigi′ of CTdki to generate deletion verification value vi, vi=σiσi′sigi′, which is used to generate the root node value vR as a validator by MHT, as shown in Figure 3. Assuming that the expired ciphertext is CT1,CT2,…,CT8 and the generated verification value is v1,v2,…,v8, CSP makes hash to the verification values and concatenates them separately to generate the verification values of the parent nodes, Hvi,j=Hvi‖Hvj. Finally, the root node verifier vR is generated by working up layer by layer. CSP will generate a validator vR and return to DU.Figure 3
Process of validator generation.DO generates local verification valuevi′=σiσi′sigi′ by concatenating locally reserved index of σ1,σ2,…,σn, digital signature sig1,sig2,…,sign, and index σ1′,σ2′,…,σm′ returned by CSP. Furthermore, DO calculates a local validator vR′ by MHT algorithm and compares it with the returned vR from CSP. If the two validators are inconsistent, this indicates that the verification value of the leaf node is incorrect, so CSP does not overwrite the partially expired ciphertext. Otherwise, it indicates that CSP completely overwrites the expired ciphertext. This process is shown in Algorithm 2.Algorithm 2: Data deletion and verification process.
input: random data block and its index, expired ciphertext and its index, sigioutput: the verification result(1)
Cloud service provider:(2)
fori←0 to mdo(3)
vi=σi′σisigi;(4)
Overwrifri,CTi;(5)
end for(6)
vR=MHTv1,v2,…,vm;(7)
SentvR and σ1′,σ2′,…,σm′ to data owners;(8)
Data owner:(9)
TransposefR,rule⟶fri′;(10)
σi=Hfri′;(11)
ifσi=σi′then(12)
flag=1;(13)
end if(14)
ifflag=1then(15)
fori←0 to numdo(16)
vi′=σi′σisigi;(17)
end for(18)
vR′=MHTv1′,v2′,…,vm′;(19)
end if(20)
ifvR′=vRthen(21)
returnTRUE;(22)
else(23)
returnFALSE;(24)
end if


## 6. Security Analysis

In SDVC scheme, the AES-256 algorithm is used to encrypt the plaintext, and then the symmetric key is encrypted by the CP-ABE algorithm. The fine-grained security deletion is implemented by the attribute revocation of CP-ABE, and the overwriting algorithm is used to completely delete the expired data and verify the deletion result. Currently, the AES-256 algorithm is recognized as unable to attack in PPT. Therefore, based on the security model described in Section4.3, the security of the SDVC is reduced to the attacker Att trying to orchestrate the attribute set to challenge TA for obtaining the symmetric key. An attribute in the CP-ABE is associated with multiple lines in access policy; that is, an attribute may exist on multiple access policies.Theorem 1.
Under the security model, if the advantage of being successful, that is, the attacker achieves as many queries as possible in all games, is negligible within the PPT, the SDVC scheme is secure.Proof.
Under the selected access policy model, if there is an attackerAtt1 takes the advantage Advatt to attack the ciphertext in PPT, the security of the SDVC scheme can be guaranteed by the challenger with the advantage Advatt′ to solve the deterministic DBDH problem. The proof process consists of the following four phases.Initialization phase: challenger selects multiplication cycle groupG1 with G2, chooses a bilinear mapping e:G1×G1⟶G2, and chooses randomly α,s,β1,β2,…,βq←ℤp and η←0,1. Challenger gets access to strategy A=Λ,ρ which Att1 wants to challenge.Inquiry phase:Att1 provides an attribute set A that does not satisfy matrix Λ and asks for the private key. Challenger takes the vector ω⟶=ω1,ω2,…,ωn∈ℤpn∗; when ω1=−1 and all i satisfied ρi∈A, we have ω⟶⋅Λi=0.Challenge phase:Att1 submits two challenge ciphertexts M0 and M1 to the challenger, who randomly selects b←0,1 and calculates the ciphertext Mb.Guess phase:Att1’s guess on b is b′. If b′=b, challenger outputs η′=0; if b′≠b, challenger outputs η′=1. When η=1, Att1 cannot obtains any of b’s information, so that Prβ′≠β|η=1=1/2. When b′≠b, the challenger guesses η′=1, so Prη′≠η|η=1=1/2. When η=0, Att1 obtains ciphertext Mb, due to the advantage of Att1 being ε, Prβ′≠β|η=1=1/2+ε. When β′≠β, the challenger guesses η′=0, so Prη′≠η|η=1=1/2+ε.
In summary, the challenger’s advantage is(6)12Prη′≠η|η=0−12Prη′≠η|η=1=1212+ε−12×12=ε2.
Therefore, the challenger’s advantage in the DBDH hypothesis isε/2. The advantage of the attacker is ε. The advantage of attacking success is negligible in PPT.


## 7. Theoretical Analysis and Performance Evaluation

Firstly, the theoretical complexity of the SDVC scheme is analyzed, and then the effectiveness of the SDVC scheme is verified by simulation experiments.


### 7.1. Theoretical Analysis

The theoretical analysis in this section mainly analyzes the computational cost, communication overhead, and storage overhead of each step of the SDVC scheme, as shown in Table3.Table 3
Complexity analysis of the SDVC.
Computational costEncryption and decryption phaseKey encryptionm⋅OlfAES+m⋅OdkABE+m⋅OldkHashKey updatingOldkABE+OldkHashData decryptionm⋅OldkABE+m⋅OlfAESSecure data deletion phaseRequest deletionOfRRandomSecure data deletionm⋅OldkABE+m⋅OlfrTrans+m⋅OlfrOWProof deletion phaseValidator generatingm⋅OlfrHash+2OvMHTDeletion verificationO1Communication overheadGetting the keym⋅OlPKUploading the filem⋅OzVerifying the resultO1Storage overheadData ownerm⋅Oldk+A+OfR+ruleKey management centerm⋅OldkCloud storage serverm⋅OlfNote.m represents the number of data blocks, lf represents the length of the data block, lfr represents random block length, ldk represents key length, AES represents AES-256 encryption function, hash represents SHA-256, ABE represents CP-ABE encryption function, MHT represents Merkle hash tree, OW represents overwrite function, Random represents random number generation function, and Trans represents replacement function.The computational cost will be analyzed from the following three phases. Data encryption and decryption phase: We firstly encrypt the plaintext through AES-256 algorithm and encrypt the symmetric keydk using the CP-ABE algorithm. Furthermore, we calculate the digital signature of the ciphertext of dk by SHA-256. When the key needs to be updated, we should reencrypt the encryption key using CP-ABE and make a new signature of the new ciphertext of symmetric key. When the data needs to be decrypted, we get the symmetric key decrypted by CP-ABE and use this key to decrypt the file ciphertext by AES-256. Secure data deletion phase: The data owner revokes the attributes and reconstructs the access policy to encrypt the symmetric key and request the trusted authority to delete the original key. Data owner generates a random data block fR, and CSP performs transposition operations m times to generate random data and overwrite the expired ciphertext. Data deletion verification phase: The validator is calculated by MHT from m verification values. Finally, the data owner compares the validator returned by the CSP with the locally generated validator to determine whether the ciphertext in the CSP is actually deleted.Communication overhead mainly occurs in the DO’s acquisition keys, verification, and uploading data. The acquisition key is mainly for the DO to request the key from the TA, who returns the generated public key, and the communication overhead ism⋅OlPK. The communication overhead required to upload ciphertext to the CSP is m⋅Olf. The communication of the deletion verification is mainly reflected in the CSP sending the validator to the DO. In this paper, we employ SHA-256 to calculate the validator, so the length of validator is 256 bits and the communication overhead is O1.Storage overhead mainly considers the storage of data and keys. Firstly, the DO stores a random block of datafR and replacement rules. The TA needs to store the ciphertext of m symmetric keys, so the storage overhead is m⋅Oldk+lMK. The CSP only stores the ciphertext, the file is divided into m subfiles of lf in length, the storage overhead is m⋅Olf.


### 7.2. Performance Evaluation

We conducted a number of simulation experiments with Ubuntu 14.04 test computer with the following configuration: Intel Core (TM) i5-4539 @3.30 GHz CPU, 8 GB RAM, and 1024 GB hard disk. In order to demonstrate the effectiveness and efficiency of the SDVC scheme, we organize the following simulation experiments, the time cost of encrypting and decrypting different size of data blocks by AES-256 algorithm, the time cost of encrypting symmetric key by CP-ABE setting different number of attributes, the time cost of overwriting data by the rule transposition algorithm during secure data deletion phase, and the time cost of MHT generating the root node.From the data set MSR-Cambridge, we select 9 groups of experimental data with different sizes: 2 MB, 4 MB, 8 MB, 16 MB, 32 MB, 64 MB, 128 MB, 256 MB, and 512 MB. We test the running time in the phases of encryption and decryption when encrypting data blocks with different sizes and compare the SDVC scheme with Du et al. [31] scheme and Xue et al. [35] scheme. Each experiment runs 100 times to obtain an average value as the final result. The time cost of encryption (Encrypt) with different sizes of data block is shown in Figure 4, and that of decryption (Decrypt) with different sizes of data block is shown in Figure 5. As the size of the data increases, the time cost of encryption and decryption also increases in a nearly linear relationship. In terms of these two figures, it can be found that, compared with Du et al. [31] scheme and Xue et al. [35] scheme, the time cost for encryption and decryption of our scheme is significantly less than that of the other two schemes. The main reason is that our scheme employs AES-256 to encrypt and decrypt data; hence, it is very efficient. On the other hand, Du et al. [31] scheme uses CP-ABE algorithm to encrypt data, and the ciphertext needs to be associated with the access policy; Xue et al. [35] scheme uses KP-ABE algorithm to encrypt data, and the ciphertext is related to the attribute set. As the data size increases, the number of attributes associated with data also increases, so the time cost of encryption and decryption increases significantly.Figure 4
Time cost of encryption with different sizes of data blocks.Figure 5
Time cost of decryption with different sizes of data blocks.In the SDVC scheme, the CP-ABE algorithm is used to encrypt the symmetric key with 256 bits. Therefore, for the fixed data size, we test the time cost of data encryption and decryption by setting the number of different attributes in the access policy. Literature [31] shows that when the number of attributes reaches 15, it can meet the security requirements of the scheme; accordingly, the number of attributes is selected from 5 to 15, and one attribute is added in turn, as shown in Figure 6. Experimental results show that the encryption time cost increases as the number of attributes increases. During the decryption process, the number of attributes increases, and the time cost of decryption also increases. In the case where only the symmetric key is encrypted, when the number of attributes associated with ciphertext is set to 15, the time costs of encryption and decryption are 226 ms and 255 ms, respectively.Figure 6
Time cost of encryption and decryption with different numbers of attributes.We test the efficiency of overwriting by the time cost of overwriting the ciphertext blocks with different sizes of random data blocks, and we set 8 groups of data blocks with different sizes from 1 MB to 128 MB as experimental data: 1 MB, 2 MB, 4 MB, 8 MB, 16 MB, 32 MB, 64 MB, and 128 MB. The time costs of all-zero overwriting and random overwriting for data blocks with different sizes are tested, respectively, as shown in Figure7. As the size of data block increases, the time cost of data block overwriting also increases. The time cost of all-zero overwriting increases with the increasing of the data size, and the time cost increases faster than that of random overwriting time. The random overwriting method selected in our scheme has better efficiency.Figure 7
Time cost of overwriting with different sizes of data blocks.The MHT experiment mainly tests the time cost of calculating the root node of MHT with different heights. The file sizes are different in the phase of secure data deletion, which causes the number of data blocks to be different too, and consequently the constructed MHT height is different. We test the running time of data deletion verification with different numbers of data blocks, assuming that each data block is 4 MB in size, and the data owner deletes a maximum file size of 16384 MB (16 GB) each time; accordingly, the maximum leaf nodes of MHT is 256 and their height is 14. Therefore, in our experiment, we set the height of the MHT increasing from 2 to 14 to test the time cost of generating the root node (validator). As can be seen from Figure8, as the height of the MHT increases, the initial time cost increases slowly, and when the height is 5, the time cost no longer has a linear relationship.Figure 8
Time cost of generating validator.


## 7.1. Theoretical Analysis

The theoretical analysis in this section mainly analyzes the computational cost, communication overhead, and storage overhead of each step of the SDVC scheme, as shown in Table3.Table 3
Complexity analysis of the SDVC.
Computational costEncryption and decryption phaseKey encryptionm⋅OlfAES+m⋅OdkABE+m⋅OldkHashKey updatingOldkABE+OldkHashData decryptionm⋅OldkABE+m⋅OlfAESSecure data deletion phaseRequest deletionOfRRandomSecure data deletionm⋅OldkABE+m⋅OlfrTrans+m⋅OlfrOWProof deletion phaseValidator generatingm⋅OlfrHash+2OvMHTDeletion verificationO1Communication overheadGetting the keym⋅OlPKUploading the filem⋅OzVerifying the resultO1Storage overheadData ownerm⋅Oldk+A+OfR+ruleKey management centerm⋅OldkCloud storage serverm⋅OlfNote.m represents the number of data blocks, lf represents the length of the data block, lfr represents random block length, ldk represents key length, AES represents AES-256 encryption function, hash represents SHA-256, ABE represents CP-ABE encryption function, MHT represents Merkle hash tree, OW represents overwrite function, Random represents random number generation function, and Trans represents replacement function.The computational cost will be analyzed from the following three phases. Data encryption and decryption phase: We firstly encrypt the plaintext through AES-256 algorithm and encrypt the symmetric keydk using the CP-ABE algorithm. Furthermore, we calculate the digital signature of the ciphertext of dk by SHA-256. When the key needs to be updated, we should reencrypt the encryption key using CP-ABE and make a new signature of the new ciphertext of symmetric key. When the data needs to be decrypted, we get the symmetric key decrypted by CP-ABE and use this key to decrypt the file ciphertext by AES-256. Secure data deletion phase: The data owner revokes the attributes and reconstructs the access policy to encrypt the symmetric key and request the trusted authority to delete the original key. Data owner generates a random data block fR, and CSP performs transposition operations m times to generate random data and overwrite the expired ciphertext. Data deletion verification phase: The validator is calculated by MHT from m verification values. Finally, the data owner compares the validator returned by the CSP with the locally generated validator to determine whether the ciphertext in the CSP is actually deleted.Communication overhead mainly occurs in the DO’s acquisition keys, verification, and uploading data. The acquisition key is mainly for the DO to request the key from the TA, who returns the generated public key, and the communication overhead ism⋅OlPK. The communication overhead required to upload ciphertext to the CSP is m⋅Olf. The communication of the deletion verification is mainly reflected in the CSP sending the validator to the DO. In this paper, we employ SHA-256 to calculate the validator, so the length of validator is 256 bits and the communication overhead is O1.Storage overhead mainly considers the storage of data and keys. Firstly, the DO stores a random block of datafR and replacement rules. The TA needs to store the ciphertext of m symmetric keys, so the storage overhead is m⋅Oldk+lMK. The CSP only stores the ciphertext, the file is divided into m subfiles of lf in length, the storage overhead is m⋅Olf.


## 7.2. Performance Evaluation

We conducted a number of simulation experiments with Ubuntu 14.04 test computer with the following configuration: Intel Core (TM) i5-4539 @3.30 GHz CPU, 8 GB RAM, and 1024 GB hard disk. In order to demonstrate the effectiveness and efficiency of the SDVC scheme, we organize the following simulation experiments, the time cost of encrypting and decrypting different size of data blocks by AES-256 algorithm, the time cost of encrypting symmetric key by CP-ABE setting different number of attributes, the time cost of overwriting data by the rule transposition algorithm during secure data deletion phase, and the time cost of MHT generating the root node.From the data set MSR-Cambridge, we select 9 groups of experimental data with different sizes: 2 MB, 4 MB, 8 MB, 16 MB, 32 MB, 64 MB, 128 MB, 256 MB, and 512 MB. We test the running time in the phases of encryption and decryption when encrypting data blocks with different sizes and compare the SDVC scheme with Du et al. [31] scheme and Xue et al. [35] scheme. Each experiment runs 100 times to obtain an average value as the final result. The time cost of encryption (Encrypt) with different sizes of data block is shown in Figure 4, and that of decryption (Decrypt) with different sizes of data block is shown in Figure 5. As the size of the data increases, the time cost of encryption and decryption also increases in a nearly linear relationship. In terms of these two figures, it can be found that, compared with Du et al. [31] scheme and Xue et al. [35] scheme, the time cost for encryption and decryption of our scheme is significantly less than that of the other two schemes. The main reason is that our scheme employs AES-256 to encrypt and decrypt data; hence, it is very efficient. On the other hand, Du et al. [31] scheme uses CP-ABE algorithm to encrypt data, and the ciphertext needs to be associated with the access policy; Xue et al. [35] scheme uses KP-ABE algorithm to encrypt data, and the ciphertext is related to the attribute set. As the data size increases, the number of attributes associated with data also increases, so the time cost of encryption and decryption increases significantly.Figure 4
Time cost of encryption with different sizes of data blocks.Figure 5
Time cost of decryption with different sizes of data blocks.In the SDVC scheme, the CP-ABE algorithm is used to encrypt the symmetric key with 256 bits. Therefore, for the fixed data size, we test the time cost of data encryption and decryption by setting the number of different attributes in the access policy. Literature [31] shows that when the number of attributes reaches 15, it can meet the security requirements of the scheme; accordingly, the number of attributes is selected from 5 to 15, and one attribute is added in turn, as shown in Figure 6. Experimental results show that the encryption time cost increases as the number of attributes increases. During the decryption process, the number of attributes increases, and the time cost of decryption also increases. In the case where only the symmetric key is encrypted, when the number of attributes associated with ciphertext is set to 15, the time costs of encryption and decryption are 226 ms and 255 ms, respectively.Figure 6
Time cost of encryption and decryption with different numbers of attributes.We test the efficiency of overwriting by the time cost of overwriting the ciphertext blocks with different sizes of random data blocks, and we set 8 groups of data blocks with different sizes from 1 MB to 128 MB as experimental data: 1 MB, 2 MB, 4 MB, 8 MB, 16 MB, 32 MB, 64 MB, and 128 MB. The time costs of all-zero overwriting and random overwriting for data blocks with different sizes are tested, respectively, as shown in Figure7. As the size of data block increases, the time cost of data block overwriting also increases. The time cost of all-zero overwriting increases with the increasing of the data size, and the time cost increases faster than that of random overwriting time. The random overwriting method selected in our scheme has better efficiency.Figure 7
Time cost of overwriting with different sizes of data blocks.The MHT experiment mainly tests the time cost of calculating the root node of MHT with different heights. The file sizes are different in the phase of secure data deletion, which causes the number of data blocks to be different too, and consequently the constructed MHT height is different. We test the running time of data deletion verification with different numbers of data blocks, assuming that each data block is 4 MB in size, and the data owner deletes a maximum file size of 16384 MB (16 GB) each time; accordingly, the maximum leaf nodes of MHT is 256 and their height is 14. Therefore, in our experiment, we set the height of the MHT increasing from 2 to 14 to test the time cost of generating the root node (validator). As can be seen from Figure8, as the height of the MHT increases, the initial time cost increases slowly, and when the height is 5, the time cost no longer has a linear relationship.Figure 8
Time cost of generating validator.


## 8. Conclusion

With the rapid development of mobile Internet and cloud technologies, we proposed a secure data deletion and verification (SDVC) scheme based on CP-ABE to effectively address the issues of unauthorized access, privacy leakage, and verifying deletion result in cloud computing. We constructed an AAT to implement fast attribute revocation and reencryption of keys, employed CP-ABE algorithm to achieve fine-grained and secure data deletion for cloud data, and verified the data deletion result by constructing a random overwriting algorithm and a validator generated by MHT. The security of the SDVC scheme is proved under the standard model. The complexity analysis and ample simulation experiments are carried out, and the results indicate that the SDVC scheme is practical and effective. The future work is to design effective method to implement secure data deletion and verification for mobile devices under 5G environment.



---

*Source: 8855341-2021-03-28.xml*