# Assured Deletion: A Scheme Based on Strong Nonseparability

Authors: Zhenjie Xie; Wei Fu; Jianqiao Xu; Tingting Zhu
Journal: Journal of Sensors
 (2022)

---

## Abstract

Cloud storage services bring great convenience to users, but also make data owners lose direct control of their data. How to ensure that deleted cloud data can never be recovered by cloud servers or attackers is a key issue in the field of cloud storage security, which is important to protect user privacy and data confidentiality in the cloud environment. Most existing schemes have the drawbacks of overreliance on key destruction and having the ability to decrypt part of the ciphertext after cracking the key. To solve these problems, a novel cloud data assured deletion scheme based on strong nonseparability is presented. By combining XOR operation with the block cipher, the cipher data become strongly nonseparable; thus, destroying any piece of cipher data will result in unrecoverable original data. Theoretical analysis and experimental results both show that the scheme achieves the expected goals of assured deletion, which has obvious performance advantages and stronger security compared with similar schemes.


---

## Body

## 1. Introduction

In cloud storage application mode, users enjoy the benefits of flexible space, real-time sharing, disaster tolerance, and other benefits. However, they lose direct control over the data they own. When users want to delete data stored in the cloud, how to ensure that the deleted data will not be recovered by the cloud server or attackers, that is, assured deletion of cloud data, is a key issue to be solved in the field of cloud storage security. Because the cloud storage services are completely out of the direct control of users, there is no technical solution to ensure the direct destruction of cloud data at present; only the idea of “encrypt data, destroy key” [1] can indirectly achieve the assured deletion of cloud data.The assured deletion schemes based on the above ideas destroy the key, but there are still complete cipher data on the cloud server. If the key is compromised or the cipher is violently cracked, the deleted original data is still at risk of being recovered. Even if it cannot be decrypted, the complete cipher data can still be used for ciphertext analysis. In addition, under the common working mode of block ciphers (e.g., ECB and CBC), if an attacker has the key, the intercepted cipher fragments can be decrypted. To deal with these threats, this paper presents a cloud data assured deletion scheme based on strong nonseparability. By combining XOR operation with the block cipher, the cipher data are strongly nonseparable [2], that is, destroying any part of the whole cipher data will result in the original data not being recovered. Users host the key and some cipher data to a trusted third party, which destroys these cipher data and the key when the deletion operation is initiated. The strong nonseparability ensures that recovering any part of the original data without the complete cipher data is computationally infeasible, thus significantly enhancing the nonrecoverability of the data after the deletion operation. This scheme achieves the strong nonseparability by confusing data blocks directly participating in cryptographic operations through XOR operation, which reduces the number of cryptography computations. Therefore, it has obvious performance advantages and stronger security over existing similar assured deletion schemes.


## 2. Related Works

To realize the assured deletion of cloud data, Perlman first proposed the idea of “encrypt data, destroy key” [1]. Firstly, the user encrypts the original data by generating a random key, then uploads the ciphertext to the remote server, and hosts the encryption key to a trusted third party. When performing data deletion, the trusted third party destroys the key to ensure that the cipher data on the remote server cannot be decrypted, thus achieving assured deletion. Tang et al. proposed FADE system [3, 4], which implements a policy-based assured deletion mechanism for cloud data. Mo et al. proposed a user-based assured deletion scheme [5] that does not rely on third parties; users only need to keep a small number of keys to achieve fine-grained assured deletion. Geambasu et al. proposed a scheme [6] which uses a threshold secret sharing mechanism to divide the encryption key and save it on a DHT (Distributed Hash Table) node, using the automatic update mechanism of DHT to delete the encryption key regularly. Feng and Tan proposed a data assured deletion scheme [7] based on trust value for cloud storage; the core is to evaluate the trustworthiness of DHT nodes, selecting a node with higher trustworthiness to store the key component, and reduce the probability that users cannot access their sensitive data during the authorized time.Rivest pointed out that for existing encryption systems, as long as the key is mastered, part of the cipher data obtained can be decrypted [2]. This facilitates the attacker. On the one hand, any cipher fragments have a direct value because they can be decrypted to obtain the corresponding plaintext. On the other hand, any cipher fragment can provide useful information for cracking the key. To address these issues, Rivest proposed the concept of strongly nonseparable and proposed a way to construct a strongly nonseparable encryption scheme by existing cryptography technology and AONT (All-Or-Nothing-Transform) and an implementation scheme called Package Transform to accommodate scenarios with higher security requirements.On the basis of Rivest’s Package Transform scheme, Luo proposed a strongly nonseparable encryption scheme [8]. Luo’s scheme first converts the original message sequence into a strongly inseparable pseudomessage sequence using AONT conversion and then encrypts the pseudomessage sequence using a random key to generate a cipher sequence. To improve the computational efficiency, Luo’s scheme uses pseudorandom function (PRF) and hash operation to, respectively, replace two times block encryption in the Package Transform scheme. It is important to note that the Package Transform scheme implements AONT, which is a preprocessing process used to achieve strong nonseparability and cannot replace encryption operations by itself, while Luo’s scheme is a complete encryption scheme which implements strong nonseparability. The scheme proposed by Zhang et al. [9, 10] uses a similar approach, but the use of bilinear mapping may result in high computational overhead.Liu et al. proposed a blockchain-based verification scheme for deletion operation in the cloud [11]. Users invoke smart contracts to prove identity to the cloud server, and then, the cloud server deletes the data and generates a blockchain with deletion evidence embedded, while users can verify the results of data deletion without a trusted third party. Du et al. proposed a cloud data assured deletion scheme based on cipher reencryption combined with override verification [12]. By reencrypting and changing the access control strategy corresponding to the ciphertext, data fine-grained deletion can be achieved. A searchable path hash binary tree based on dirty data block override is constructed to verify the correctness of the data to be deleted after overwriting. Zhang proposed an instantaneous deterministic deletion method of cloud storage data based on feature iteration [13], which extracts and classifies the features of redundant data in cloud storage data, iterates until convergence, and achieves high-performance deletion of redundant data. In addition, some assured deletion or self-destruction schemes for cloud data based on DHT [10, 14], attribute-based encryption [15–18], and identity-based encryption [19, 20] are proposed in recent years. Xiong et al. [21] made an in-depth analysis and comments on the related research work in recent years from three aspects: trusted execution environment, key management, and access control strategy.The above schemes use some new technologies, but require considerable changes to the cloud storage service framework, making it difficult to directly apply them to existing cloud storage systems, complex to implementation, and significantly increasing the computational time cost or number of interactions, while the scheme in this paper does not change the existing system architecture, but fully exploits the mature cryptography technology, which achieves the goals of assured deletion by making the ciphertext strongly nonseparable.


## 3. Assured Deletion Scheme Based on Strong Nonseparability

The cloud storage system in reality is full of various security threats. To achieve assured deletion of cloud data, an efficient assured deletion scheme for cloud data based on strong nonseparability is proposed. This section first describes the assured deletion system from the perspective of the model, combs the real threats and proposes the expected design goals, then introduces the concept of strongly nonseparable, next describes the main algorithms, processes, and assured deletion mechanisms in detail, and finally gives the performance analysis of the scheme.


### 3.1. System Model

#### 3.1.1. System Composition

To illustrate the assured deletion of cloud data, an assured deletion system with four entities is introduced, as Figure1 illustrated.Figure 1
Assured deletion system model.Among them, the cloud storage server (CSS) provides users with cloud storage and data sharing services. Trusted third party (TTP) is the entity trusted by users, which is responsible for hosting keys and partial cipher data and for completely destroying the corresponding key and cipher data when performing the deletion operation. Data owner (DO) performs a specific encryption algorithm on the original data, uploads the output to CSS and TTP, and authorizes access for some users. Authorized users (AU) are those who are allowed to download and decrypt specific data. Assured deletion can be initiated by the DO or triggered by a strategy such as shelf life.In fact, there is no credible third-party entity in some cloud storage systems. At this time, DO can retain the partial cipher data and destroy it when performing deletion.


#### 3.1.2. Reality Threats

For traditional cloud storage systems, cloud data may still be retained after a deletion request, which poses a threat to user privacy and data confidentiality. Specifically, the implementation of assured deletion faces the following security threats:(a)
CSS does not perform data deletion operations, but only prohibits user access(b)
Attackers or malicious cloud service providers attempt to decrypt or mine the user data they hold(c)
Attackers intercept or crack the data encryption key to decrypt the acquired cipher data


#### 3.1.3. Expected Goals

Within the framework of this system, in order to respond to these real threats and be operable, assured deletion should meet the following objectives:(a)
Assured deletion must be valid, that is, no one (including the DO) can recover all or part of the original data with limited computing resources after performing the data deletion(b)
Even if an attacker acquires all data stored by the CSS or if the cloud service provider itself is malicious, it cannot restore any of the original data(c)
Even if an attacker has the data encryption key, he cannot decrypt incomplete cipher data fragments(d)
The algorithm introduced by assured deletion must be easy to implement and will not significantly burden users


#### 3.1.4. Safety Assumptions

To make the scheme feasible, the following assumptions need to be made:(a)
TTP is trustworthy and technically can ensure that the corresponding keys and data are securely destroyed(b)
The temporary data blocks generated by users will not be saved, that is, attackers cannot obtain the decrypted plaintext through the users


### 3.2. Strongly Nonseparable

Strongly nonseparable [2] introduced by Rivest guarantees that any missing cipher data will result in the failure to decrypt any part of the plaintext, as defined below.HypothesisΓ is a block cipher mechanism used to convert s plaintext sequence m1,m2,⋯,ms to t cipher sequence c1,c2,⋯,ct. If it is satisfied that restoring any plaintext data before obtaining and decrypting all t cipher blocks is computationally infeasible, it is called the encryption mechanism Γ can make a sequence strongly nonseparable.In the face of a strongly nonseparable encryption mechanism, the cipher fragments obtained by the attacker no longer have the value of direct decryption, nor can they provide a useful reference for cracking the key, so the security is significantly enhanced. Based on the definition of strongly nonseparable, we can use existing cryptographic technology to construct encryption schemes that satisfy the strong nonseparability.


### 3.3. Scheme Implementation

This section describes in detail the algorithms and processes for data encryption and data decryption of the scheme and gives the mechanism and security analysis of data deletion. MakeEnc a block encryption algorithm, Dec the corresponding decryption algorithm for Enc, and F=m1,m2,⋯,mn the original message sequence.


#### 3.3.1. Data Encryption

The pseudocode for the data encryption algorithm is as follows.Algorithm 1
Input:FOutput:K,C′Randomly generate an initial vectorm0′Randomly generate a data encryption keyKfori in 1,n:mi′=mi⊕mi−1′ci′=EncKmi′⊕mi−1′end forc0′=m0′⊕c1′⊕c2′⊕⊕cn′MakeC′=c0′,c1′,c2′,⋯,cn′The data encryption algorithm is executed by the DO. The execution process is shown in Figure2. After execution, the DO randomly selects some data blocks in the cipher sequence C′ to form a set Ψ. Specifically, makeΨ=c0′; DO hosts Ψ and key K together to a TTP. The remaining data blocks of cipher sequence C′ form a set Ω and DO sends it to the CSS. DO grants access to some users.Figure 2
Data encryption process.


#### 3.3.2. Data Decryption

The pseudocode for the data decryption algorithm is as follows.Algorithm 2
Input:K,C′Output:Fm0′=c0′⊕c1′⊕c2′⊕⋯⊕cn′fori in 1,n:mi′=DecKci′⊕mi−1′mi=mi′⊕mi−1′end forMakeF=m1,m2,⋯,mnData decryption algorithm is executed by AU when accessing cloud data. The execution process is shown in Figure3. AU first retrieves the key K and the partial cipher data set Ψ from the TTP, then retrieves the remaining cipher data set Ω from the CSS, merges Ψ and Ω to get the complete cipher sequence C′, and then executes the data decryption algorithm to recover the original message sequence F.Figure 3
Data decryption process.It is worth mentioning that if allmi−1′ appearing in the above algorithms are fixed to the initial vector m0′, the expected security characteristics can also be achieved. This simplifies the scheme representation further, but may result in the same plaintext blocks being converted to the same cipher blocks. Therefore, it is necessary to use the block cipher working mode other than ECB to hide the formatting rules and statistical characteristics of the plaintext. Experiments show that this simplification does not achieve performance improvement, so it will not be repeated later.


#### 3.3.3. Data Delete Mechanism

When performing the deletion operation, the keyK and the partial cipher data set Ψ are destroyed by the TTP. Due to the strong nonseparability of cipher data, any missing cipher data will result in the failure to decrypt any part of the plaintext.The following security description analyzes whether the scheme achieves the expected security goals after performing deletion operations from the point of view of the strongest attacker.TTP destroys the keyK and the partial cipher data set Ψ (make Ψ=c0′) after deletion. Assume that the strongest attacker A gets all remaining data Ω (make Ω=c1′,c2′,⋯,cn′) stored by CSS and has the key K. However, A is infeasible to recover m0′ without c0′; thus, no fragment of the original message F can be recovered. Even if the attacker A gets part of the plaintext blocks (make it mi), because A does not know mi′, it is not possible to compute m0′ contained in it; thus, no more plaintext blocks can be obtained.In Luo’s scheme [8], mi′=mi⊕frki; f is a pseudorandom function. Attacker A can get mi′ by decrypting ci′. In the case of obtaining the plaintext block mi, frki can be obtained. Pseudorandom functions usually do not satisfy the characteristics of cryptographic algorithms. As long as the seed rk is calculated inversely, other plaintext blocks can be restored.To sum up, with limited computing resources and existing technology, an attacker cannot obtain any plaintext after performing the deletion operation under the assumptions. Therefore, the scheme achieves data assured deletion and has higher security than Luo’s scheme.


### 3.4. Performance Analysis

This section makes a theoretical analysis of the scheme performance from three aspects: storage, calculation, and communication. Table1 shows the performance analysis results of encryption only, Package Transform [2], Luo’s scheme [8], and this scheme.Table 1
Performance analysis of schemes.
SchemeStorage overheadCalculation overheadCommunication overheadStrong nonseparabilityConfidentialityEncryption onlynβ+knENCnβ+kNoYesPackage Transform [2]n+1β3nXOR+2nENCn+1βYesNoLuo’s scheme [8]n+1β+k2nXOR+nHASH+n+1ENC+nPRFn+1β+kYesYesThis schemen+1β+kEnc:3nXOR+nENC+1PRFDec: 3nXOR+nENCn+1β+kYesYes


#### 3.4.1. Storage Overhead

As mentioned earlier, for the original message sequenceF with n blocks, the cipher sequence C′ generated by the encryption algorithm has n+1 blocks. Assuming that the size of each plaintext and cipher data block is β, the size of key K is k, and the partial cipher data set Ψ stored by TTP includes only one block. Thus, for each file stored, the storage overhead of CSS is nβ, while it is β+k for TTP. The overall storage overhead of the scheme is n+1β+k. The DO does not need to save any data locally after uploading.


#### 3.4.2. Calculation Overhead

The DO of this scheme needs3n·XOR+n·ENC+1·PRF operations to perform the data encryption algorithm, while AU needs 3n·XOR+n·ENC operations to perform the data decryption algorithm. Among them, XOR stands for data block XOR operation, ENC means block encryption/decryption operation, and PRF stands for pseudorandom operation (including randomly generating an initial vector). Luo’s scheme [8] requires 2n·XOR+n·HASH+n+1·ENC+n·PRF operations to perform file upload or download algorithms, where HASH refers to the hash operation. It can be seen that, compared with Luo’s scheme, this scheme significantly reduces pseudorandom operations and avoids hash operations, thus significantly improving the computational efficiency.


#### 3.4.3. Communication Overhead

After performing the data encryption algorithm, the DO uploadsnβ data to CSS and β+k data to TTP. Accordingly, AU downloads nβ data from CSS and β+k data from TTP. The total communication overhead for a complete file upload or file access is n+1β+k regardless of the handshake cost required to establish the communication channel.


## 3.1. System Model

### 3.1.1. System Composition

To illustrate the assured deletion of cloud data, an assured deletion system with four entities is introduced, as Figure1 illustrated.Figure 1
Assured deletion system model.Among them, the cloud storage server (CSS) provides users with cloud storage and data sharing services. Trusted third party (TTP) is the entity trusted by users, which is responsible for hosting keys and partial cipher data and for completely destroying the corresponding key and cipher data when performing the deletion operation. Data owner (DO) performs a specific encryption algorithm on the original data, uploads the output to CSS and TTP, and authorizes access for some users. Authorized users (AU) are those who are allowed to download and decrypt specific data. Assured deletion can be initiated by the DO or triggered by a strategy such as shelf life.In fact, there is no credible third-party entity in some cloud storage systems. At this time, DO can retain the partial cipher data and destroy it when performing deletion.


### 3.1.2. Reality Threats

For traditional cloud storage systems, cloud data may still be retained after a deletion request, which poses a threat to user privacy and data confidentiality. Specifically, the implementation of assured deletion faces the following security threats:(a)
CSS does not perform data deletion operations, but only prohibits user access(b)
Attackers or malicious cloud service providers attempt to decrypt or mine the user data they hold(c)
Attackers intercept or crack the data encryption key to decrypt the acquired cipher data


### 3.1.3. Expected Goals

Within the framework of this system, in order to respond to these real threats and be operable, assured deletion should meet the following objectives:(a)
Assured deletion must be valid, that is, no one (including the DO) can recover all or part of the original data with limited computing resources after performing the data deletion(b)
Even if an attacker acquires all data stored by the CSS or if the cloud service provider itself is malicious, it cannot restore any of the original data(c)
Even if an attacker has the data encryption key, he cannot decrypt incomplete cipher data fragments(d)
The algorithm introduced by assured deletion must be easy to implement and will not significantly burden users


### 3.1.4. Safety Assumptions

To make the scheme feasible, the following assumptions need to be made:(a)
TTP is trustworthy and technically can ensure that the corresponding keys and data are securely destroyed(b)
The temporary data blocks generated by users will not be saved, that is, attackers cannot obtain the decrypted plaintext through the users


## 3.1.1. System Composition

To illustrate the assured deletion of cloud data, an assured deletion system with four entities is introduced, as Figure1 illustrated.Figure 1
Assured deletion system model.Among them, the cloud storage server (CSS) provides users with cloud storage and data sharing services. Trusted third party (TTP) is the entity trusted by users, which is responsible for hosting keys and partial cipher data and for completely destroying the corresponding key and cipher data when performing the deletion operation. Data owner (DO) performs a specific encryption algorithm on the original data, uploads the output to CSS and TTP, and authorizes access for some users. Authorized users (AU) are those who are allowed to download and decrypt specific data. Assured deletion can be initiated by the DO or triggered by a strategy such as shelf life.In fact, there is no credible third-party entity in some cloud storage systems. At this time, DO can retain the partial cipher data and destroy it when performing deletion.


## 3.1.2. Reality Threats

For traditional cloud storage systems, cloud data may still be retained after a deletion request, which poses a threat to user privacy and data confidentiality. Specifically, the implementation of assured deletion faces the following security threats:(a)
CSS does not perform data deletion operations, but only prohibits user access(b)
Attackers or malicious cloud service providers attempt to decrypt or mine the user data they hold(c)
Attackers intercept or crack the data encryption key to decrypt the acquired cipher data


## 3.1.3. Expected Goals

Within the framework of this system, in order to respond to these real threats and be operable, assured deletion should meet the following objectives:(a)
Assured deletion must be valid, that is, no one (including the DO) can recover all or part of the original data with limited computing resources after performing the data deletion(b)
Even if an attacker acquires all data stored by the CSS or if the cloud service provider itself is malicious, it cannot restore any of the original data(c)
Even if an attacker has the data encryption key, he cannot decrypt incomplete cipher data fragments(d)
The algorithm introduced by assured deletion must be easy to implement and will not significantly burden users


## 3.1.4. Safety Assumptions

To make the scheme feasible, the following assumptions need to be made:(a)
TTP is trustworthy and technically can ensure that the corresponding keys and data are securely destroyed(b)
The temporary data blocks generated by users will not be saved, that is, attackers cannot obtain the decrypted plaintext through the users


## 3.2. Strongly Nonseparable

Strongly nonseparable [2] introduced by Rivest guarantees that any missing cipher data will result in the failure to decrypt any part of the plaintext, as defined below.HypothesisΓ is a block cipher mechanism used to convert s plaintext sequence m1,m2,⋯,ms to t cipher sequence c1,c2,⋯,ct. If it is satisfied that restoring any plaintext data before obtaining and decrypting all t cipher blocks is computationally infeasible, it is called the encryption mechanism Γ can make a sequence strongly nonseparable.In the face of a strongly nonseparable encryption mechanism, the cipher fragments obtained by the attacker no longer have the value of direct decryption, nor can they provide a useful reference for cracking the key, so the security is significantly enhanced. Based on the definition of strongly nonseparable, we can use existing cryptographic technology to construct encryption schemes that satisfy the strong nonseparability.


## 3.3. Scheme Implementation

This section describes in detail the algorithms and processes for data encryption and data decryption of the scheme and gives the mechanism and security analysis of data deletion. MakeEnc a block encryption algorithm, Dec the corresponding decryption algorithm for Enc, and F=m1,m2,⋯,mn the original message sequence.


### 3.3.1. Data Encryption

The pseudocode for the data encryption algorithm is as follows.Algorithm 1
Input:FOutput:K,C′Randomly generate an initial vectorm0′Randomly generate a data encryption keyKfori in 1,n:mi′=mi⊕mi−1′ci′=EncKmi′⊕mi−1′end forc0′=m0′⊕c1′⊕c2′⊕⊕cn′MakeC′=c0′,c1′,c2′,⋯,cn′The data encryption algorithm is executed by the DO. The execution process is shown in Figure2. After execution, the DO randomly selects some data blocks in the cipher sequence C′ to form a set Ψ. Specifically, makeΨ=c0′; DO hosts Ψ and key K together to a TTP. The remaining data blocks of cipher sequence C′ form a set Ω and DO sends it to the CSS. DO grants access to some users.Figure 2
Data encryption process.


### 3.3.2. Data Decryption

The pseudocode for the data decryption algorithm is as follows.Algorithm 2
Input:K,C′Output:Fm0′=c0′⊕c1′⊕c2′⊕⋯⊕cn′fori in 1,n:mi′=DecKci′⊕mi−1′mi=mi′⊕mi−1′end forMakeF=m1,m2,⋯,mnData decryption algorithm is executed by AU when accessing cloud data. The execution process is shown in Figure3. AU first retrieves the key K and the partial cipher data set Ψ from the TTP, then retrieves the remaining cipher data set Ω from the CSS, merges Ψ and Ω to get the complete cipher sequence C′, and then executes the data decryption algorithm to recover the original message sequence F.Figure 3
Data decryption process.It is worth mentioning that if allmi−1′ appearing in the above algorithms are fixed to the initial vector m0′, the expected security characteristics can also be achieved. This simplifies the scheme representation further, but may result in the same plaintext blocks being converted to the same cipher blocks. Therefore, it is necessary to use the block cipher working mode other than ECB to hide the formatting rules and statistical characteristics of the plaintext. Experiments show that this simplification does not achieve performance improvement, so it will not be repeated later.


### 3.3.3. Data Delete Mechanism

When performing the deletion operation, the keyK and the partial cipher data set Ψ are destroyed by the TTP. Due to the strong nonseparability of cipher data, any missing cipher data will result in the failure to decrypt any part of the plaintext.The following security description analyzes whether the scheme achieves the expected security goals after performing deletion operations from the point of view of the strongest attacker.TTP destroys the keyK and the partial cipher data set Ψ (make Ψ=c0′) after deletion. Assume that the strongest attacker A gets all remaining data Ω (make Ω=c1′,c2′,⋯,cn′) stored by CSS and has the key K. However, A is infeasible to recover m0′ without c0′; thus, no fragment of the original message F can be recovered. Even if the attacker A gets part of the plaintext blocks (make it mi), because A does not know mi′, it is not possible to compute m0′ contained in it; thus, no more plaintext blocks can be obtained.In Luo’s scheme [8], mi′=mi⊕frki; f is a pseudorandom function. Attacker A can get mi′ by decrypting ci′. In the case of obtaining the plaintext block mi, frki can be obtained. Pseudorandom functions usually do not satisfy the characteristics of cryptographic algorithms. As long as the seed rk is calculated inversely, other plaintext blocks can be restored.To sum up, with limited computing resources and existing technology, an attacker cannot obtain any plaintext after performing the deletion operation under the assumptions. Therefore, the scheme achieves data assured deletion and has higher security than Luo’s scheme.


## 3.3.1. Data Encryption

The pseudocode for the data encryption algorithm is as follows.Algorithm 1
Input:FOutput:K,C′Randomly generate an initial vectorm0′Randomly generate a data encryption keyKfori in 1,n:mi′=mi⊕mi−1′ci′=EncKmi′⊕mi−1′end forc0′=m0′⊕c1′⊕c2′⊕⊕cn′MakeC′=c0′,c1′,c2′,⋯,cn′The data encryption algorithm is executed by the DO. The execution process is shown in Figure2. After execution, the DO randomly selects some data blocks in the cipher sequence C′ to form a set Ψ. Specifically, makeΨ=c0′; DO hosts Ψ and key K together to a TTP. The remaining data blocks of cipher sequence C′ form a set Ω and DO sends it to the CSS. DO grants access to some users.Figure 2
Data encryption process.


## 3.3.2. Data Decryption

The pseudocode for the data decryption algorithm is as follows.Algorithm 2
Input:K,C′Output:Fm0′=c0′⊕c1′⊕c2′⊕⋯⊕cn′fori in 1,n:mi′=DecKci′⊕mi−1′mi=mi′⊕mi−1′end forMakeF=m1,m2,⋯,mnData decryption algorithm is executed by AU when accessing cloud data. The execution process is shown in Figure3. AU first retrieves the key K and the partial cipher data set Ψ from the TTP, then retrieves the remaining cipher data set Ω from the CSS, merges Ψ and Ω to get the complete cipher sequence C′, and then executes the data decryption algorithm to recover the original message sequence F.Figure 3
Data decryption process.It is worth mentioning that if allmi−1′ appearing in the above algorithms are fixed to the initial vector m0′, the expected security characteristics can also be achieved. This simplifies the scheme representation further, but may result in the same plaintext blocks being converted to the same cipher blocks. Therefore, it is necessary to use the block cipher working mode other than ECB to hide the formatting rules and statistical characteristics of the plaintext. Experiments show that this simplification does not achieve performance improvement, so it will not be repeated later.


## 3.3.3. Data Delete Mechanism

When performing the deletion operation, the keyK and the partial cipher data set Ψ are destroyed by the TTP. Due to the strong nonseparability of cipher data, any missing cipher data will result in the failure to decrypt any part of the plaintext.The following security description analyzes whether the scheme achieves the expected security goals after performing deletion operations from the point of view of the strongest attacker.TTP destroys the keyK and the partial cipher data set Ψ (make Ψ=c0′) after deletion. Assume that the strongest attacker A gets all remaining data Ω (make Ω=c1′,c2′,⋯,cn′) stored by CSS and has the key K. However, A is infeasible to recover m0′ without c0′; thus, no fragment of the original message F can be recovered. Even if the attacker A gets part of the plaintext blocks (make it mi), because A does not know mi′, it is not possible to compute m0′ contained in it; thus, no more plaintext blocks can be obtained.In Luo’s scheme [8], mi′=mi⊕frki; f is a pseudorandom function. Attacker A can get mi′ by decrypting ci′. In the case of obtaining the plaintext block mi, frki can be obtained. Pseudorandom functions usually do not satisfy the characteristics of cryptographic algorithms. As long as the seed rk is calculated inversely, other plaintext blocks can be restored.To sum up, with limited computing resources and existing technology, an attacker cannot obtain any plaintext after performing the deletion operation under the assumptions. Therefore, the scheme achieves data assured deletion and has higher security than Luo’s scheme.


## 3.4. Performance Analysis

This section makes a theoretical analysis of the scheme performance from three aspects: storage, calculation, and communication. Table1 shows the performance analysis results of encryption only, Package Transform [2], Luo’s scheme [8], and this scheme.Table 1
Performance analysis of schemes.
SchemeStorage overheadCalculation overheadCommunication overheadStrong nonseparabilityConfidentialityEncryption onlynβ+knENCnβ+kNoYesPackage Transform [2]n+1β3nXOR+2nENCn+1βYesNoLuo’s scheme [8]n+1β+k2nXOR+nHASH+n+1ENC+nPRFn+1β+kYesYesThis schemen+1β+kEnc:3nXOR+nENC+1PRFDec: 3nXOR+nENCn+1β+kYesYes


### 3.4.1. Storage Overhead

As mentioned earlier, for the original message sequenceF with n blocks, the cipher sequence C′ generated by the encryption algorithm has n+1 blocks. Assuming that the size of each plaintext and cipher data block is β, the size of key K is k, and the partial cipher data set Ψ stored by TTP includes only one block. Thus, for each file stored, the storage overhead of CSS is nβ, while it is β+k for TTP. The overall storage overhead of the scheme is n+1β+k. The DO does not need to save any data locally after uploading.


### 3.4.2. Calculation Overhead

The DO of this scheme needs3n·XOR+n·ENC+1·PRF operations to perform the data encryption algorithm, while AU needs 3n·XOR+n·ENC operations to perform the data decryption algorithm. Among them, XOR stands for data block XOR operation, ENC means block encryption/decryption operation, and PRF stands for pseudorandom operation (including randomly generating an initial vector). Luo’s scheme [8] requires 2n·XOR+n·HASH+n+1·ENC+n·PRF operations to perform file upload or download algorithms, where HASH refers to the hash operation. It can be seen that, compared with Luo’s scheme, this scheme significantly reduces pseudorandom operations and avoids hash operations, thus significantly improving the computational efficiency.


### 3.4.3. Communication Overhead

After performing the data encryption algorithm, the DO uploadsnβ data to CSS and β+k data to TTP. Accordingly, AU downloads nβ data from CSS and β+k data from TTP. The total communication overhead for a complete file upload or file access is n+1β+k regardless of the handshake cost required to establish the communication channel.


## 3.4.1. Storage Overhead

As mentioned earlier, for the original message sequenceF with n blocks, the cipher sequence C′ generated by the encryption algorithm has n+1 blocks. Assuming that the size of each plaintext and cipher data block is β, the size of key K is k, and the partial cipher data set Ψ stored by TTP includes only one block. Thus, for each file stored, the storage overhead of CSS is nβ, while it is β+k for TTP. The overall storage overhead of the scheme is n+1β+k. The DO does not need to save any data locally after uploading.


## 3.4.2. Calculation Overhead

The DO of this scheme needs3n·XOR+n·ENC+1·PRF operations to perform the data encryption algorithm, while AU needs 3n·XOR+n·ENC operations to perform the data decryption algorithm. Among them, XOR stands for data block XOR operation, ENC means block encryption/decryption operation, and PRF stands for pseudorandom operation (including randomly generating an initial vector). Luo’s scheme [8] requires 2n·XOR+n·HASH+n+1·ENC+n·PRF operations to perform file upload or download algorithms, where HASH refers to the hash operation. It can be seen that, compared with Luo’s scheme, this scheme significantly reduces pseudorandom operations and avoids hash operations, thus significantly improving the computational efficiency.


## 3.4.3. Communication Overhead

After performing the data encryption algorithm, the DO uploadsnβ data to CSS and β+k data to TTP. Accordingly, AU downloads nβ data from CSS and β+k data from TTP. The total communication overhead for a complete file upload or file access is n+1β+k regardless of the handshake cost required to establish the communication channel.


## 4. Experiments and Analysis

To verify the validity of this scheme, the main algorithms and processes of this scheme are implemented using Python programming; also, the schemes of encryption only, Package Transform [2], and Luo’s [8] are implemented. The computational efficiency of the data encryption/decryption algorithms of each scheme is expected to be compared through comparative experiments.


### 4.1. Environment and Parameters

The configuration of the experimental computer is listed as Table2.Table 2
The configuration of experimental computer.
ItemConfigurationMachine typePCOperation systemWindows 10 64-bitCPUIntel Core i7-10710UCPU quantity6Memory16 GB LPDDR3 2133 MHzHard diskSAMSUNG MZVLB512HBJQ-000L7128-bit key (k=16B) was used in the experiments. The original file size was 10 MB (using 1 MB, 100 MB, 1 GB, and other sizes will get similar results; we use 10 MB file as an example), and the data block size β was 1 KB, 2 KB, 4 KB, 8 KB, and 16 KB in turn. Experiments with the same parameters were repeated 50 times, and their average values were taken as the final results.Some Python libraries are used for key operations such as block encryption, hash, and pseudorandom involved in the algorithm. The specific implementation method is shown in Table3.Table 3
The key operation implementation.
OperationImplementationBlock encryptionPython-Crypto.Cipher.AESPseudorandomPython-randomHashPython-hashlib.md5Data block XORPython large integer bitwise XOR (“^”)To ensure the accuracy of the comparison, each scheme should be as consistent as possible in programming style, be optimized as possible in its own scheme framework, and use the same parameters.


### 4.2. Data Encryption Test

In the data encryption test, each scheme executes the encryption algorithm for a random file of 10 MB in size, outputs a 10 MB file to upload to CSS, and also uploads a data block to TTP (except for encryption only). The time cost of performing the encryption algorithm of each scheme at different block sizes is shown in Figure4.Figure 4
The data encryption time cost.Figure4 shows that this scheme takes significantly less time cost to execute the encryption algorithm than Package Transform and Luo’s scheme (about 2/3 to 3/4 of Luo’s), which is about two to three times as long as encryption only. In addition, the time cost of each scheme decreases as the block size increases, because an increase in the block size means a decrease in the total number of blocks, so the number of operations performed decreases.


### 4.3. Data Decryption Test

In the data decryption test, each scheme executes the decryption algorithm on the 10 MB file generated by its own execution of the encryption algorithm. The output file of each scheme is consistent with the original file through hash verification. The time cost of performing the decryption algorithm of each scheme at different block sizes is shown in Figure5.Figure 5
The data decryption time cost.As can be seen from Figure5, the decryption algorithm time consumed by each scheme is essentially the same as the encryption algorithm.Combining the above test results, this scheme is an assured deletion encryption scheme based on strong nonseparability. It achieves greater security with only two to three times the computation overhead of encryption only. Because the hash operation is avoided and pseudorandom operation is reduced, the computation overhead is about 2/3 to 3/4 of Luo’s scheme.


## 4.1. Environment and Parameters

The configuration of the experimental computer is listed as Table2.Table 2
The configuration of experimental computer.
ItemConfigurationMachine typePCOperation systemWindows 10 64-bitCPUIntel Core i7-10710UCPU quantity6Memory16 GB LPDDR3 2133 MHzHard diskSAMSUNG MZVLB512HBJQ-000L7128-bit key (k=16B) was used in the experiments. The original file size was 10 MB (using 1 MB, 100 MB, 1 GB, and other sizes will get similar results; we use 10 MB file as an example), and the data block size β was 1 KB, 2 KB, 4 KB, 8 KB, and 16 KB in turn. Experiments with the same parameters were repeated 50 times, and their average values were taken as the final results.Some Python libraries are used for key operations such as block encryption, hash, and pseudorandom involved in the algorithm. The specific implementation method is shown in Table3.Table 3
The key operation implementation.
OperationImplementationBlock encryptionPython-Crypto.Cipher.AESPseudorandomPython-randomHashPython-hashlib.md5Data block XORPython large integer bitwise XOR (“^”)To ensure the accuracy of the comparison, each scheme should be as consistent as possible in programming style, be optimized as possible in its own scheme framework, and use the same parameters.


## 4.2. Data Encryption Test

In the data encryption test, each scheme executes the encryption algorithm for a random file of 10 MB in size, outputs a 10 MB file to upload to CSS, and also uploads a data block to TTP (except for encryption only). The time cost of performing the encryption algorithm of each scheme at different block sizes is shown in Figure4.Figure 4
The data encryption time cost.Figure4 shows that this scheme takes significantly less time cost to execute the encryption algorithm than Package Transform and Luo’s scheme (about 2/3 to 3/4 of Luo’s), which is about two to three times as long as encryption only. In addition, the time cost of each scheme decreases as the block size increases, because an increase in the block size means a decrease in the total number of blocks, so the number of operations performed decreases.


## 4.3. Data Decryption Test

In the data decryption test, each scheme executes the decryption algorithm on the 10 MB file generated by its own execution of the encryption algorithm. The output file of each scheme is consistent with the original file through hash verification. The time cost of performing the decryption algorithm of each scheme at different block sizes is shown in Figure5.Figure 5
The data decryption time cost.As can be seen from Figure5, the decryption algorithm time consumed by each scheme is essentially the same as the encryption algorithm.Combining the above test results, this scheme is an assured deletion encryption scheme based on strong nonseparability. It achieves greater security with only two to three times the computation overhead of encryption only. Because the hash operation is avoided and pseudorandom operation is reduced, the computation overhead is about 2/3 to 3/4 of Luo’s scheme.


## 5. Conclusion

Aiming at the assured deletion of cloud data, a novel scheme based on strong nonseparability is presented. Compared with the traditional schemes of “encrypt data, destroy key,” making the ciphertext strongly nonseparable is a promising way to achieve the assured deletion. By destroying the key and part of the cipher data through a TTP, the nonrecoverability of the original data after deletion operation is significantly enhanced. Compared with the existing similar schemes, this scheme achieves strong nonseparability by adding XOR operation instead of hash operation. The theoretical analysis and experimental results show that the proposed scheme achieves the expected design goals of assured deletion with less computation overhead, having obvious performance advantages and stronger security in similar schemes.In fact, refining key management and realizing strong nonseparability of ciphertext are two ideas to realize assured deletion, which are not exclusive. If the two ideas are combined, the “credibility” of cloud data deletion will be further improved.



---

*Source: 9691724-2022-03-16.xml*