© ICST Institute for Computer Sciences, Social Informatics and Telecommunications Engineering 2019
Jin Li, Zheli Liu and Hao Peng (eds.)Security and Privacy in New Computing EnvironmentsLecture Notes of the Institute for Computer Sciences, Social Informatics and Telecommunications Engineering284https://doi.org/10.1007/978-3-030-21373-2_61

A Non-repudiable Dynamic Provable Data Possession

Jun-Feng Tian1, 2, Rui-Fang Guo1, 2   and Xuan Jing1, 2
(1)
School of Cyberspace Security and Computer Institute, Hebei University, Baoding, 071000, China
(2)
Hebei Key Laboratory of High Confidence Information Systems, Hebei University, Baoding, 071000, China
 
 
Rui-Fang Guo
Email: grf.skzxc@gmail.com

Abstract

With the widespread popularity of cloud storage, cloud storage security issues have also received much attention. A provable data possession (PDP) scheme can effectively help users to verify the integrity of data stored remotely in the cloud. For this reason, the client’s PDP scheme is constantly improving and developing. In view of the problem that the existing PDP scheme pays less attention to the clients deceiving the cloud server, a non-repudiable dynamic PDP scheme based on the Stern-Brocot tree (SB-NR-DPDP) is proposed. We put forward a dynamic storage structure and dynamic operation algorithm based on the Stern-Brocot tree, so that it can satisfy the client’s dynamic data operations and realize the non-repudiation feature of the scheme. This scheme can resist hash value attacks, delete-insert attacks and tamper with cloud return value attacks. The theoretical analysis shows that the proposed scheme has less computing and storage overhead than other schemes.

Keywords

Cloud storageProvable data possessionStern-brocotDynamic operation

1 Introduction

As cloud storage can provide users with high-quality data storage and computing services [1], cloud storage has gradually gained wide popularity among users. Cloud storage not only provides convenience for users but also raises serious security problems for them. Cloud storage not only makes users relinquish physical control of the data but also increases the risk of data being leaked by, tampered with and deleted by cloud service providers. In addition, the security of cloud storage is threatened by external attackers, hardware failures and other factors. Therefore, research on the integrity verification of users’ cloud data is urgently needed.

A provable data possession (PDP) scheme can effectively help users to verify the integrity of data stored remotely in the cloud. However, research on PDP has paid little attention to user deception by cloud service providers. For example, a user once issued an order to delete a certain piece of data to the cloud service provider, but the user denied that order when authenticating the integrity and blamed the cloud service provider, resulting in disputes between the user and the cloud service provider. For this reason, by introducing the Stern-Brocot tree type of dynamic data structure, this paper proposes a non-repudiable dynamic provable data possession scheme (SB-NR-DPDP).

2 Related Work

To solve the problem of users checking cloud data integrity, researchers have proposed a provable data possession (PDP) scheme. In 2007, Ateniese et al. [2] first proposed the PDP scheme. To support user dynamic operations and to improve the scheme’s flexibility of the scheme, the researchers proposed dynamic PDP scheme. For example, [1, 3, 4]. To eliminate complex key and certificate management and to improve PDP scheme efficiency, Zhao et al. [5] proposed the first identity-based PDP scheme in 2013. To solve the problem of user unreliability and improve the credibility of both parties in a PDP scheme, in 2014, Mo et al. [6] proposed a non-repudiation PDP scheme based on the Merkle hash tree and timestamps. Feng [7] et al. found that the existing dynamic data structure could not satisfy the non-repudiation feature of the PDP scheme very well. By introducing a logical index table (ILT), they proposed the non-repudiation and identity-based, non-repudiable dynamic PDP scheme (ID-NR-DPDP) in cloud storage.

3 The System Model

An SB-NR-DPDP scheme model contains four primary entities: the private key generator (PKG), the data owner (User), the cloud server provider (CSP), and the unbiased judge. As shown in Fig. 1, their functions are as follows.
../images/485150_1_En_61_Chapter/485150_1_En_61_Fig1_HTML.png
Fig. 1.

SB-NR-DPDP scheme model

  • PKG: A trusted third party, which is called the private key generator. It can help users generate private keys.

  • User: The data owner who uses cloud storage services to outsource data to remote clouds.

  • Cloud server: A semi-trusted entity that stores and processes the user’s data. It can prove data integrity to clients, but sometimes the cloud server can destroy data integrity and trick clients into believing that the data are still intact in the cloud.

  • Judge: A trusted third party that resolves disputes when they arise between the user and the cloud service provider.

4 The Dynamic Operation Algorithm of the Stern-Brocot Tree

The Stern-Brocot tree [8] is a binary tree used to construct a set consisting of all non-negative minimal fractions. It was discovered independently by German mathematician Moritz Stern and French watchmaker Achille Brocot. The dynamic operation algorithm in the Stern-Brocot tree includes an insert, delete and modify algorithm. Users and the cloud server initialize the tree: the root node is $$ \frac{1}{1} $$ and is used to form a tree structure that is symmetric to the root node. The left child of the root node is $$ \frac{N}{M} $$, which is the seed node. The right child is $$ \frac{M}{N} $$. Using a seed, a Stern-Brocot tree with a symmetric root node can be established. As shown in Fig. 2, all the fractions in the tree are in the simplest form.
../images/485150_1_En_61_Chapter/485150_1_En_61_Fig2_HTML.png
Fig. 2.

Partial Stern-Brocot tree with seed (N, M)

The algorithm calculates the height of the tree that needs to be established according to the number of seeds and the number of data blocks n. Each leaf node in the tree corresponds to a unique pointer variable, and each pointer variable points to the user’s corresponding data block $$ F_{wx} $$.

Insert algorithm: When data blocks $$ F_{wx} $$ need to be inserted, an update from the most recent operation starts after the largest leaf node. The pointer variable $$ {\text{wx}} $$ corresponding to the appropriate insert block position is found. It then points to the file block $$ F_{wx}^{{\prime }} $$. The number of blocks is updated at the same time.

Deletion algorithm: To delete the correspondence between pointer variables and file blocks, it needs to delete the $$ {\text{wx}} $$ pointer to $$ F_{wx} $$, and let $$ {\text{wx}} = 1 $$ as failure node that is to add $$ {\text{wx}} $$ as a global pointer variable for the dynamic operation algorithm. Finally, update the number of blocks at the same time, $$ {\text{n}} = {\text{n}} - 1 $$. The purpose of marking the failure node is that when the tree is built again, $$ {\text{wx}} $$ conflicts with the global variable value, indicating that the position is the failure position. Continue to look for the insertion position, so as to prevent the deletion - insertion attack. If the deleted position is at the last block, a new block will be inserted after the newly deleted position to avoid the delete - insert attack. When there are not enough leaves in the tree, a row will be generated again and the global variable will be cleared after initialization.

Modify algorithm: First, it removes the relationship between the pointer variable $$ {\text{wx}} $$ and the file block $$ F_{wx} $$, and makes pointer variable value $$ {\text{wx}} = 1 $$. It then adds $$ {\text{wx}} $$ as a global pointer variable for the dynamic operation algorithm. Then, it follows the insertion algorithm to find pointer variable $$ {\text{wx}}^{{\prime }} $$ corresponding to the insertion location, and points to modify the file.

5 Details of the SB-NR-DPDP Scheme

The SB-NR-DPDP scheme include six algorithms: $$ {\text{Setup}} $$, $$ {\text{Extraction}} $$, $$ {\text{Tagging}} $$, $$ {\text{Processing}} $$, $$ {\text{Proof}} $$, and $$ {\text{Judgement}} $$, which are described in detail in the following sections.

5.1 Setup

This algorithm is executed by the PKG. Let $$ G_{1} ,G_{2} $$ be a cyclic multiplication groups with prime order, and $$ {\text{g}} $$ be a generator of $$ G_{1} $$. The map $$ {\text{e}}:G_{1} \times G_{1} \to G_{2} $$ is a bilinear pairing. The PKG defines three hash functions: $$ {\text{H}}:\left\{ {0,1} \right\}^{ *} \to G_{1} $$, $$ {\text{h}}:\left\{ {0,1} \right\}^{ *} \to Z_{q}^{ *} $$, $$ h_{1} :\left\{ {0,1} \right\}^{ *} \to Z_{q}^{ *} $$; a pseudo-random function: $$ \varnothing_{key} :key \times \left\{ {0,1} \right\}^{ *} \to Z_{q}^{ *} $$; and a pseudo-random permutation: $$ \uppi_{key} :key \times \left\{ {0,1} \right\}^{{{ \log }\left( \theta \right)}} \to \left\{ {0,1} \right\}^{{{ \log }\left( \theta \right)}} $$. The PKG then selects a random number $$ {\text{c}} \in Z_{q}^{ *} $$ and computes $$ {\text{C}} = {\text{c}} \cdot {\text{g}} $$. The identity-based signature algorithm of Galindo and Garcia [9] where $$ {\text{sign}}\left( {sk_{ID} ,{\text{f}}} \right) \to \ell $$ generates the signature for the message, and $$ {\text{verify}}\left( {{\text{ID}},{\text{f}},\ell } \right) $$ is used to verify the signature validity. PKG publishes the public parameters $$ G_{g} = \{ G_{1} ,G_{2} ,q,g,e,H,h,h_{1} ,C,\pi ,\phi ,sign(),verify()\} $$ and keeps the $$ {\text{msk}} = {\text{c }} $$ secret.

5.2 Extraction

The PKG selects a random number $$ j \in_{R} Z_{q}^{ *} $$ and computes $$ {\text{R}} = {\text{j}} \cdot {\text{g}} $$, $$ {\text{Z}} = {\text{j}} + {\text{c}} \cdot {\text{h}}({\text{ID}}| | {\text{R)mod q}} $$; therefore, $$ sk_{ID} = \left( {R,Z} \right) $$. The PKG uses this algorithm to generate the client’s secret key, $$ sk_{c} $$, or the cloud server’s secret key, $$ sk_{s} $$.

5.3 Tagging

Given an F, the client chooses a random file name NI from some large domain and splits the file into n blocks, $$ {\text{F}} = F_{1} \left\| {F_{2} } \right\| \ldots F_{n} $$, given $$ F_{x} ,1 \le {\text{x}} \le {\text{n}} $$, $$ F_{x} = F_{x1} \left| {\left| { F_{x2} } \right|} \right| \ldots F_{xs} $$. Then, the client selects s random values $$ u_{1} ,u_{2} , \ldots u_{s} \in G_{1} ,U = \left( {u_{1} ,u_{2} , \ldots u_{s} } \right) $$, and then initializes the tree by the dynamic operation algorithm of the Stern-Brocot tree to obtain $$ {\text{wx}} $$. It then calculates the signature $$ \ell_{c} $$ and label $$ T_{wx} $$, where $$ \ell_{c} = sign\left( {sk_{c} ,NI\left| {\left| U \right|\left| n \right|} \right|\left( {N,M} \right)} \right) $$ and $$ T_{wx} = Z_{c} \cdot \left( {H\left( {NI\left| {\left| {wx} \right|} \right|U} \right) + \sum\nolimits_{K = 1}^{S} {F_{wx,k} \cdot u_{k} } } \right) $$. Then, the client uploads $$ \left\{ {F_{wx} ,\,T_{wx} ,\,{\text{NI,}}\,{\text{U,}}\,{\text{n,}}\,\left( {\text{N,M}} \right)} \right\} $$ to the cloud server. Next, the cloud server uses equations $$ {\text{e}}\left( {\sum\nolimits_{x = 1}^{n} {T_{wx} , {\text{g}}} } \right) = {\text{e}}(\sum\nolimits_{x = 1}^{n} {H\left( {NI\left| {\left| {wx} \right|} \right|U} \right)} + \sum\nolimits_{K = 1}^{s} {\left( {\sum\nolimits_{x = 1}^{n} {F_{wx} } } \right)} \cdot u_{k} ,R_{c} + {\text{h}}(ID_{c} ||R_{c} ) \cdot {\text{C}}) $$ and $$ 1 = {\text{verify}}\left( {ID_{c} ,{\text{NI}}\left| {\left| {\text{U}} \right|\left| {\text{n}} \right|} \right|\left( {{\text{N}},{\text{M}}} \right),\ell_{C} } \right) $$ to check the validity of $$ T_{wx} $$, $$ \left( {1 \le {\text{x}} \le {\text{n}}} \right) $$ and $$ \text{ }\ell_{c} $$. If one of them does not hold, the operation stops. Otherwise, the cloud server stores them, computes the signature $$ \ell_{s} = sign\left( {ID_{s} ,\ell_{c} } \right) $$, and returns $$ \ell_{s} $$ as a receipt to the client. The client receives the receipt from the cloud server, and then checks the validity of the receipt $$ \ell_{s} $$ by using the equation $$ 1 = {\text{verify}}\left( {ID_{s} ,\ell_{s} ,\ell_{c} } \right) $$. If it is invalid, the operation stops. Otherwise, the client stores $$ \left\{ {{\text{NI}},{\text{n}},\left( {\text{N,M}} \right),\ell_{s} ,\ell_{c} } \right\} $$ and deletes data blocks and tags from local storage.

5.4 Processing

  • Insert

The client wants to insert a new block $$ {\text{F}}^{{\prime }} $$. First, the client obtains the pointer variable $$ {\text{wx}}^{{\prime }} $$ corresponding to the new insertion location and the number of file blocks n by using the dynamic operation algorithm. Then, the file $$ {\text{F}}^{{\prime }} $$ is divided into s sections, $$ {\text{F}}^{{\prime }} = \left( {F_{1}^{{\prime }} \left\| {F_{2}^{{\prime }} } \right\| \ldots F_{s}^{{\prime }} } \right) $$. The client computes the new label $$ T_{wx}^{{\prime }} $$ and signature $$ \ell_{c}^{{\prime }} $$, by using the equations $$ T_{wx}^{{\prime }} = Z_{c} \cdot \left( {H\left( {NI\left| {\left| {wx^{\prime}} \right|} \right|U} \right) + \sum\nolimits_{k = 1}^{s} {F_{k}^{{\prime }} \cdot u_{k} } } \right) $$ and $$ \ell_{c}^{ '} = sign(sk_{c} ,IN\left| {\left| {NI} \right|} \right|wx^{{\prime }} ||n) $$. Next, the client uploads $$ \left\{ {{\text{IN}},{\text{F}}^{{\prime }} ,T_{wx}^{{\prime }} ,{\text{U,}}\,{\text{n,}}\,\ell_{c}^{{\prime }} } \right\} $$, to the cloud server. Then, the cloud server checks the validity $$ T_{wx}^{{\prime }} $$ and $$ \text{ }\ell_{c}^{{\prime }} $$, by using the equations $$ 1 = {\text{verify}}(ID_{c} ,{\text{IN}}\left| {\left| {\text{U}} \right|} \right|{\text{wx}}^{{\prime }} ||{\text{n}},\ell_{c}^{{\prime }} ) $$ and $$ {\text{e}}\left( {T_{wx}^{{\prime }} ,{\text{g}}} \right) = {\text{e}}({\text{H}}\left( {{\text{NI}}\left| {\left| {{\text{wx}}^{{\prime }} } \right|} \right|{\text{U}}} \right) + \sum\nolimits_{k = 1}^{s} {F_{k}^{{\prime }} \cdot u_{k} ,R_{c} + {\text{h}}(ID_{C} ||R_{c} ) \cdot {\text{C}})} $$. If one of them does not hold, the operation stops; otherwise, the cloud server updates n, $$ \text{ }\ell_{c}^{{\prime }} $$. Then, the signature $$ \text{ }\ell_{s}^{{\prime }} = sign\left( {ID_{s} ,\ell_{c}^{{\prime }} } \right) $$ is computed and $$ \text{ }\ell_{s}^{{\prime }} $$ is returned as a receipt to the client. The client receives the receipt from the cloud server and then checks the validity of the receipt $$ \text{ }\ell_{s}^{{\prime }} $$ by using the equation $$ 1 = {\text{verify}}\left( {ID_{s} ,\ell_{s}^{{\prime }} ,\ell_{c}^{{\prime }} } \right) $$. If it is invalid, the operation stops; otherwise, the client updates n,$$ \text{ }\ell_{c}^{{\prime }} ,\text{ }\,\ell_{s}^{{\prime }} $$, and deletes $$ {\text{F}}^{{\prime }} ,T_{wx}^{{\prime }} $$ from local storage.

  • Delete

The client wants to delete block $$ F_{wx} $$. First, the client obtains the pointer variable $$ {\text{wx}} $$ corresponding to the delete location, and the number of file blocks n by using the dynamic operation algorithm. The client computes the signature $$ \text{ }\ell_{c}^{{\prime }} $$, by using the equation $$ \ell_{c}^{{\prime }} = sign\left( {sk_{c} ,NI\left| {\left| U \right|\left| {wx} \right|} \right|n} \right) $$. Then, the client uploads $$ \left\{ {{\text{NI}},{\text{U}},{\text{n}}, {\text{wx}},\ell_{c}^{{\prime }} } \right\} $$ to the cloud server. Next, the cloud server checks the validity by using the equation $$ 1 = {\text{verify}}\left( {ID_{c} ,{\text{NI}}\left| {\left| {\text{U}} \right|\left| {\text{wx}} \right|} \right|{\text{n}},\ell_{c}^{{\prime }} } \right) $$. If it holds, the cloud server updates n, $$ \ell_{c}^{{\prime }} $$. Then, the signature $$ \ell_{s}^{{\prime }} = sign\left( {ID_{s} ,\ell_{c}^{{\prime }} } \right) $$ is computed and $$ \ell_{s}^{{\prime }} $$ is returned as a receipt to the client. The client receives the receipt from the cloud server and then checks the validity of the receipt $$ \ell_{s}^{'} $$ by using the equation $$ 1 = {\text{verify}}\left( {ID_{s} ,\ell_{s}^{{\prime }} ,\ell_{c}^{{\prime }} } \right) $$. If it is invalid, the operation stops; otherwise, the client updates n, $$ \ell_{c}^{{\prime }} ,\ell_{s}^{{\prime }} $$.

  • Modify

The client wants to modify the file block value into $$ {\text{F}}^{{\prime }} $$. First, the client obtains the pointer variable $$ {\text{wx}}^{{\prime }} $$ corresponding to the new insertion location of the new block by using the dynamic operation algorithm. Then, the file $$ {\text{F}}^{{\prime }} $$ is divided into s sections - $$ {\text{F}}^{{\prime }} = \left( {F_{1}^{{\prime }} \left| {\left| {F_{2}^{{\prime }} } \right|\left| \ldots \right|} \right|F_{S}^{{\prime }} } \right) $$. The client computes the new label $$ T_{wx}^{{\prime }} $$ and signature $$ \text{ }\ell_{c}^{{\prime }} $$, by using the equations $$ T_{wx}^{{\prime }} = Z_{c} \cdot \left( {H\left( {NI\left| {\left| {wx^{\prime}} \right|} \right|U} \right) + \sum\nolimits_{k = 1}^{s} {F_{k}^{{\prime }} } \cdot u_{k} } \right) $$ and $$ \ell_{c}^{{\prime }} = sign(sk_{c} ,NI\left| {\left| U \right|} \right|wx^{{\prime }} ||n) $$. Then, the client uploads $$ \left\{ {{\text{F}}^{{\prime }} ,T_{wx}^{{\prime }} ,NI,U,wx^{{\prime }} ,n,\ell_{c}^{{\prime }} } \right\} $$ to the cloud server. The cloud server checks the validity $$ T_{wx}^{{\prime }} $$ and $$ \ell_{c}^{{\prime }} $$, by using the equations $$ 1 = {\text{verify}}(ID_{c} ,{\text{NI}}\left| {\left| {\text{U}} \right|} \right|{\text{wx}}^{{\prime }} ||{\text{n}},\ell_{c}^{{\prime }} ) $$ and $$ {\text{e}}\left( {T_{wx}^{{\prime }} ,{\text{g}}} \right) = {\text{e}}\left( {{\text{H}}\left( {{\text{NI}}\left| {\left| {{\text{wx}}^{{\prime }} } \right|} \right|{\text{U}}} \right) + \sum\nolimits_{k = 1}^{s} {F_{k}^{{\prime }} \cdot u_{k} ,R_{c} + h(ID_{c} ||R_{C} ) \cdot C} } \right) $$. If one of them does not hold, the operation stops; otherwise, the cloud server updates $$ \text{ }\ell_{c}^{{\prime }} $$. Then, the signature $$ \ell_{s}^{{\prime }} = sign\left( {ID_{s} ,\text{ }\ell_{c}^{{\prime }} } \right) $$ is computed and $$ \ell_{s}^{{\prime }} $$ is returned as a receipt to the client. The client receives the receipt from the cloud server and checks the validity of the receipt $$ \ell_{s}^{{\prime }} $$ by using the equation $$ 1 = {\text{verify}}\left( {ID_{s} ,\text{ }\ell_{s}^{{\prime }} ,\text{ }\ell_{c}^{{\prime }} } \right) $$. If it is invalid, the operation stops; otherwise, the client updates $$ \ell_{c}^{{\prime }} ,\text{ }\ell_{s}^{{\prime }} $$, and deletes the file block and its labels.

5.5 Proof

The client wants to verify the integrity of the file NI. First, the client selects a random number $$ {\text{i}} $$, where $$ 1 \le {\text{i}} \le {\text{n}} $$ and $$ s_{1} ,s_{2} \in \,_{R} Z_{q}^{*} $$. The client computes $$ S_{2} = s_{2} \cdot g, \hat{\ell }_{c} = sign(sk_{c} ,NI\left| {\left| {s_{1} } \right|} \right|S_{2} ||i) $$ and sends the challenge $$ {\text{chal}} = \left( {{\text{i}},s_{1} ,S_{2} ,{\text{NI}},\hat{\ell }_{c} } \right) $$ to the cloud server. Upon receiving the challenge, the cloud server stops the dynamic operations of

this file, selects $$ s_{3} \in \, _{R} Z_{q}^{*} $$, computes $$ S_{3} = s_{3} \cdot g $$, $$ {\text{S}} = s_{3} \cdot S_{2} $$, $$ {\text{Y}} = \{ {\text{y}}\left( {\pi_{{s_{1} }} \left(\uprho \right)} \right)|1 \le\uprho \le {\text{i}}\} $$, $$ a_{y} = \phi_{S} \left( y \right) $$, $$ {\text{y}} \in {\text{Y}} $$, $$ \hat{F}_{k} = \sum\nolimits_{y} {a_{y} F_{yk} } $$, $$ 1 \le {\text{k}} \le {\text{s}} $$, $$ {\text{T}} = \sum\nolimits_{y \in Y} {a_{y} \cdot T_{y} } $$, $$ \hat{\ell }_{s} = sign\left( {sk_{s} ,S_{3} \left| {\left| n \right|\left| {\left( {N,M} \right)} \right|\left| {\hat{F}_{1} } \right|} \right|\hat{F}_{2} \left| {\left| \ldots \right|\left| {\hat{F}_{S} } \right|} \right|\hat{T}} \right) $$, and sends $$ {\text{re}} = \left\{ {S_{3} ,{\text{n}},\left( {{\text{N}},{\text{M}}} \right),\hat{F}_{1} , \hat{F}_{2} , \ldots \hat{F}_{s} ,\hat{T},\hat{\ell }_{s} } \right\} $$ to the client as a response. Then, the client computes $$ {\text{S}} = s_{2} \cdot S_{3} $$, $$ {\text{Y}} = \{ {\text{y}}\left( {\pi_{{s_{1} }} \left(\uprho \right)} \right)|1 \le\uprho \le {\text{i}}\} $$, $$ a_{y} = \phi_{S} \left( y \right) $$, and $$ {\text{y}} \in {\text{Y}} $$, and then checks the validity of response by using the equations $$ {\text{e}}\left( {\hat{T},{\text{g}}} \right) = {\text{e}}\left( {\sum\nolimits_{y \in Y} {a_{y} \cdot {\text{H}}\left( {{\text{NI}}\left| {\left| {\text{y}} \right|} \right|{\text{U}}} \right)} + \sum\nolimits_{k = 1}^{s} {\hat{F}_{k} \cdot u_{k} ,R_{c} + h(ID_{c} ||R_{c} ) \cdot C} } \right) $$ and $$ 1 = {\text{verify}}\left( {ID_{s} ,S_{3} ,{\text{n}},\left( {{\text{N}},{\text{M}}} \right),\hat{F}_{1} ,\hat{F}_{2} , \ldots \hat{F}_{s} ,{\hat{\text{T}}},\hat{\ell }_{s} } \right) $$. When the equations are true, the data are proven to be complete.

5.6 Judgement

When there is a dispute between the client and the cloud server, they each send the latest data information to the judge. The cloud server sends the latest $$ {\text{chal}} = \left( {{\text{i}},s_{1} ,S_{2} ,{\text{NI}},\hat{\ell }_{c} } \right) $$ and response $$ {\text{re}} = \left\{ {S_{3} ,{\text{n}},\left( {{\text{N}},{\text{M}}} \right),{\text{wx}}^{{\prime }} ,\hat{F}_{1} ,\hat{F}_{2} , \ldots ,\hat{F}_{s} ,{\hat{\text{T}}},\hat{\ell }_{s} } \right\} $$, $$ s_{3} ,\ell_{c} $$ to the judge. Then, the judge checks the validity of $$ \text{ }\ell_{s} $$. If it is invalid, the cloud server is the winner. Otherwise, the judge checks the validity of $$ \ell_{c} $$ and $$ {\text{re}} $$. If one of them is winner, the client is the winner.

6 Efficiency Analysis

We perform an efficiency analysis of the storage and computational overhead of the scheme, and compare it with two of the best alternative schemes. Let $$ T_{H} ,T_{add} ,T_{mul} ,T_{p} ,T_{exp} $$ denote the running time of a hash function instruction, an addition instruction in $$ G_{1} $$, a multiplication instruction, a bilinear pairing instruction, and an exponentiation instruction. The PRF, PRP and other operations are omitted in our evaluation, because their computational costs are negligible. Suppose the data are split into n blocks. Each block of data is divided into s parts, and the number of challenge blocks is c. Table 1 presents the comparisons between our scheme and two other schemes [1, 7].
Table 1.

Comparison with other schemes.

Schemes

 

Ref. [7]

Ref. [1]

Ours

Computational cost in tag generation phase

Client side

$$ \left( {{\text{ns}} + 2} \right)T_{mul} + nsT_{add} + \left( {n + 1} \right)T_{Hash} $$

$$ nsT_{mul} + nT_{Hash} + {\text{n}}\left( {{\text{s}} + 1} \right)T_{exp} $$

$$ \left( {{\text{ns}} + 2} \right)T_{mul} + nsT_{add} + \left( {n + 1} \right)T_{Hash} $$

Computational cost at generates proof

Cloud side

$$ \left( {2{\text{c}} + 4} \right)T_{mul} + \left( {c - 1} \right)T_{add} + T_{Hash} $$

$$ \left( {2{\text{c}} - 1} \right)T_{mul} + \left( {c - 1} \right)T_{add} + cT_{exp} $$

$$ \left( {2{\text{c}} + 4} \right)T_{mul} + \left( {c - 1} \right)T_{add} + T_{Hash} $$

Computational cost at verifying the proof

Client side

$$ \left( {{\text{c}} + {\text{s}} + 4} \right)T_{mul} + \left( {c + s + 2} \right)T_{add} + 3T_{Hash} + T_{p} $$

$$ \left( {{\text{c}} + {\text{s}} - 1} \right)T_{mul} + cT_{Hash} + \left( {c + s + 1} \right)T_{exp} $$

$$ \left( {{\text{c}} + {\text{s}} + 4} \right)T_{mul} + \left( {c + s + 2} \right)T_{add} + 3T_{Hash} + T_{p} $$

Storage cost

 

ITL list

ORT list

Fixed

From Table 1, we can see that our scheme’s computational overhead is the same as scheme [7], so the computational cost is mainly compared with scheme [1]. Our scheme is more efficient because we use a bilinear pairing operation with less computational overhead instead of using exponential operations, and the time expended by $$ T_{H} ,T_{add} ,T_{mul} ,T_{p} $$ is less than $$ T_{exp} . $$ On the other hand, we can see that when the value of n is fixed, the computational cost of the two schemes is linear with the number of s. Moreover, as the s grows, the growth rate of tag generation computational overhead in scheme [1] is significantly higher than ours. Though comparison, we found that the computational overhead of our scheme is reduced, so our scheme is more efficient. Since both schemes [1, 7] need to maintain the table structure, the scheme, the clients and cloud server do not need to maintain the table structure, and the storage overhead is fixed. Only the number of data blocks n and the seed of the tree can be stored, and the storage overhead is independent of the file size. For this reason, the storage overhead of our scheme is significantly lower than that of the schemes [1, 7], which reduces the storage overhead of the clients and the cloud server.

7 Summary

The scheme enables the clients and the cloud server to dynamically manipulate outsourced files, making the PDP solution more suitable for practical application. The program supports identity authentication, enabling the PDP solution to eliminate complex certificate management. The program supports non-repudiation and solves the disputes between the client and the cloud server. the proposed scheme has less computing and storage overhead than other schemes. As such, it has high efficiency.