Delegated integrity check for hierarchical cloud data

Abstract

In cloud storage, a data owner can store his data in a cloud and authorize some users to access his data. Since the data are outsourced to the cloud, the authorized users should check the data to assure integrity. The data owner does not allow unauthorized users to check integrity of his data. There are many private and public integrity check schemes. Nevertheless, this paper concerns the verification key spread problem. Delegated integrity check deals with the verification key spread problem and provides effective management of verifiers. A data owner can delegate a verifier to check his data and revoke the right of the verifier later. The verifier cannot re-delegate his integrity check capability to someone else. Delegated integrity check guarantees that only the delegated verifier can check integrity of data.

This paper provides the model of delegated integrity check, an application scenario of personal health records, and two delegated integrity check schemes for hierarchical cloud data. The first scheme allows a verifier to check data possession of a storage server. The second scheme allows a verifier to check data retrievability from a storage server. The schemes achieve proof unforgeability, proof indistinguishability and delegation key unforgeability in the random oracle model.

Keywords

Delegated provable data possession delegated proofs of retrievability proxy re-encryption

1. Introduction

By cloud storage, a user can store his data into a cloud for convenient data access, data sharing, etc. Nevertheless, security issues are the main concern for cloud data. When outsourcing the data to a cloud service provider, the user is concerned about data confidentiality, availability, integrity, etc. There have been many solutions to these issues. For example, private and public key encryption schemes protect data confidentiality, fault tolerance and data replica mechanisms enhance data availability, and private and public integrity check schemes assure data integrity.

Although private and public integrity check schemes are suitable for wide applications, there still are situations that need more delicate types of integrity check schemes. Consider that a user stores his data in a cloud and shares the data with his friends via the cloud. His friends should check the data to assure integrity because the cloud service provider could modify the data without the user’s permission. The user allows only his friends to check his data, and his friends are not allowed to delegate the integrity check capability to someone else. Neither private nor public integrity check schemes satisfy this type of requirement. Public integrity check schemes allow everyone with the public key to check data. The user cannot restrict the verifiers to his friends because he cannot control the spread of his public key. On the other hand, private integrity check schemes allow someone with the secret key to generate integrity tags and then check data. If the user provides his secret key to his friends, his friends can delegate someone else to check the data by providing the secret key. Furthermore, the friends can modify the data without the user’s awareness by generating new integrity tags. The failure of private and public integrity check schemes in this application scenario is due to the verification key spread problem.

The user needs a new type of integrity check schemes to satisfy the above-discussed scenario. This paper considers the delegated integrity check model. Figure 1 illustrates the system model. User $U$ is a data owner. He stores his data in a storage server and delegates verifier $V$ to check the data. The three parties communicate with each other via public channels, but the connection between $U$ and $V$ in the delegation phase is a secure channel. $U$ has to use his secret key ${sk}_{U}$ to verify an integrity proof. He can also delegate this capability to $V$ . $U$ generates delegation key ${dk}_{U \to V}$ and stores it in the storage server. The storage server uses ${dk}_{U \to V}$ to transform an integrity proof for $V$ . Thus, $V$ can use his secret key ${sk}_{V}$ to verify the proof. There are three phases in the delegated integrity check model. In the setup phase, $U$ uses ${sk}_{U}$ to generate integrity tags for his data. Then, $U$ stores the data and tags in the storage server. In the delegation phase, $V$ uses ${sk}_{V}$ to generate key token ${kt}_{V}$ . Then, $V$ sends ${kt}_{V}$ to $U$ via a secure channel. $U$ verifies ${kt}_{V}$ using $V$ ’s public key ${pk}_{V}$ and generates delegation key ${dk}_{U \to V}$ using $({sk}_{U}, {kt}_{V})$ . Then, $U$ stores ${dk}_{U \to V}$ in the storage server. The storage server uses $U$ ’s and $V$ ’s public keys $({pk}_{U}, {pk}_{V})$ to verify ${dk}_{U \to V}$ . In the integrity check phase, $V$ sends a challenge to the storage server. The storage server uses the data, tags, ${dk}_{U \to V}$ , and challenge to generate an integrity proof. Then, the storage server sends the proof to $V$ . $V$ uses ${sk}_{V}$ to verify the proof. If $U$ would like to revoke $V$ ’s integrity check capability, he can ask the storage server to remove ${dk}_{U \to V}$ . Delegated integrity check provides an effective method to revoke the integrity check capability. If $U$ reveals ${kt}_{V}$ to the storage server, the storage server can use ${kt}_{V}$ to forge integrity proofs which can pass $V$ ’s verification. Thus, $V$ no longer trusts the verification of integrity proofs and loses the privilege of integrity check.

Fig. 1.

System model of delegated integrity check. Delegated integrity check is an analogous notion to proxy re-encryption.

Delegated integrity check solves the verification key spread problem. A verifier has to use his secret key to verify an integrity proof. The proof has been transformed and cannot be transformed again. Thus, the verifier cannot re-delegate his integrity check capability unless he is willing to reveal his secret key. Delegated integrity check provides effective management of verifiers and mitigates the risk of entirely trusting a third-party verifier. Thus, delegated integrity check is suitable for users who do not allow the public to check their data.

Table 1

Comparison with related work

Scheme	PPDP [51]	OPOR [1]	Delegated integrity check
Storage server	Malicious	Malicious	Malicious
			Verify delegation key
			Verify integrity challenge
Verifier	Honest	Malicious	Malicious
Verifier	Honest	Malicious	Verify integrity proof
Delegation method	Integrity tag	Integrity tag	Delegation key
Re-delegation prevention	×	×	∘
Revocation	×	∘	⊚
Validation	×	∘	×
Tag information	$Σ : M + U + V + S$	$Σ_{U} : M + U$	$Σ : M + U$
Tag information	$Σ : M + U + V + S$	$Σ_{V} : M + V$	$Σ : M + U$
Storage cost	$S : \| M \| + v \| Σ \|$	$S : \| M \| + \| Σ_{U} \| + v \| Σ_{V} \|$	$S : \| M \| + \| Σ \| + v \| {dk}_{U \to V} \|$
Communication cost (setup phase)	$U \to S : \| M \| + v \| Σ \|$	$U \to S : \| M \| + \| Σ_{U} \|$	$U \to S : \| M \| + \| Σ \|$
Communication cost (setup phase)	$U \to S : \| M \| + v \| Σ \|$	$(\begin{matrix} S \to V : \| M \| + \| Σ_{U} \| \\ V \to S : \| Σ_{U} \| + \| Σ_{V} \| \\ V \to U : \| Σ_{U} \| + \| Σ_{V} \| \end{matrix}) \times v$	$U \to S : \| M \| + \| Σ \|$
Communication cost (delegation phase)	ϕ	ϕ	$(\begin{matrix} V \to U : \| {kt}_{V} \| \\ U \to S : \| {dk}_{U \to V} \| \end{matrix}) \times v$
Dynamic group	×	×	∘
Large-scale delegation	×	×	∘

Notes: $U$ is a user; $V$ is a verifier; $S$ is a storage server; M are data; Σ are integrity tags; ${kt}_{V}$ is $V$ ’s key token; ${dk}_{U \to V}$ is the delegation key; v is the number of verifiers.

The properties of delegated integrity check are summarized as follows:

Effective management of verifiers. A user can delegate a verifier to check his data by generating the delegation key. The storage server can use the user’s and the verifier’s public keys to verify the delegation key. The verifier cannot re-delegate this integrity check capability to someone else unless he is willing to reveal his secret key. The user can revoke the verifier later by revealing the verifier’s key token.

No prior knowledge of verifiers for integrity tags. A user can generate integrity tags of his data without any information about verifiers. The integrity tags are independent of the verifiers. The user does not need to decide whom he will delegate in advance. He can delegate a verifier at any time and revoke the verifier later. Delegated integrity check supports a dynamic group of verifiers efficiently.

Efficient delegation for users and verifiers. In the delegation phase, a verifier generates his key token to a user (data owner). The user verifies the key token and generates the delegation key to the storage server. Neither of them need to access the stored data. The computation complexity is independent of the amount of stored data and the number of delegated verifiers. Delegated integrity check achieves large-scale delegation.

Efficient proof transformation for storage servers. A storage server can transform an integrity proof with a delegation key just in time. The computation complexity is independent of the amount of stored data and the number of delegated verifiers.

There are some related works, where a verifier can check data on behalf of a user. Table 1 provides the comparison with these works. In the proxy provable data possession (PPDP) model [51], user $U$ can delegate verifier $V$ to check his data. In the setup phase, $U$ uses his secret key ${sk}_{U}$ to generate integrity tags for his data. A pseudorandom function is used to output the indexes of integrity tags, and the seed is related to the secret keys of $U$ , $V$ and storage server $S$ . $U$ can use ${sk}_{U}$ to compute seed $\hat{e} {({pk}_{V}, {pk}_{S})}^{{sk}_{U}}$ . In the integrity check phase, $V$ uses $U$ ’s public key ${pk}_{U}$ to verify integrity proofs. $V$ can use his secret key ${sk}_{V}$ to compute seed $\hat{e} {({pk}_{U}, {pk}_{S})}^{{sk}_{V}}$ . PPDP could not prevent re-delegation. $V$ can provide $\hat{e} {({pk}_{U}, {pk}_{S})}^{{sk}_{V}}$ to someone else. $U$ cannot revoke $V$ ’s integrity check capability. If the integrity tags are removed, data integrity is not assured anymore. In the outsourced proofs of retrievability (OPOR) model [1], user $U$ can outsource integrity check tasks to verifier $V$ and validate the integrity check results. In the setup phase, both $U$ and $V$ generate integrity tags for the data. $U$ chooses secret token $τ_{U}$ to generate integrity tags $Σ_{U}$ for his data M. Then, $U$ stores $(M, Σ_{U})$ in the storage server. $V$ retrieves $(M, Σ_{U})$ from the storage server. He chooses secret token $τ_{V}$ to generate integrity tags $Σ_{V}$ for M. Then, $V$ uploads $(Σ_{U}, Σ_{V})$ to the storage server and $U$ , respectively. $V$ will prove the correctness of $Σ_{V}$ via a non-interactive zero-knowledge proof system. $U$ will use M to verify the proof. In the integrity check phase, the storage server provides two integrity proofs to $V$ . One is verified by $V$ using $τ_{V}$ , and the other is verified by $U$ using $τ_{U}$ . $U$ can validate $V$ ’s result by asking $V$ to provide $τ_{V}$ . OPOR could not prevent re-delegation. $V$ can retrieve M back and choose another secret token $τ^{'}$ to generate integrity tags $Σ^{'}$ . Then, $V$ uploads $Σ^{'}$ to the storage server and provides $τ^{'}$ to someone else. $U$ can revoke $V$ ’s integrity check capability by asking the storage server to remove $V$ ’s integrity tags.

This paper is an extension of the work on the delegable provable data possession (delegable PDP) model [44]. Delegated integrity check is a stronger model, which provides users with the capability to revoke delegated verifiers. This paper proposes the formal model of delegated integrity check and provides an application scenario of personal health records in Section 4. This paper proposes two delegated integrity check schemes for hierarchical cloud data. The scheme in Section 5 allows a user to check data possession of a storage server. The scheme in Section 6 allows a user to check data retrievability from a storage server. The schemes achieve proof unforgeability, proof indistinguishability and delegation key unforgeability in the random oracle model. Some related issues of delegated integrity check are discussed in Section 7, which provides further insight into curve selection, random sampling and dynamic data.

2. Related work

Ateniese et al. [2,3] defined the provable data possession (PDP) model, which ensures that stored data are intact in a storage server. Later on, Ateniese et al. [5] proposed the proof of storage (POS) framework to construct public PDP schemes. Their framework builds linear authenticators from homomorphic identification schemes. Purushothama and Amberker [41] proposed a public PDP scheme via polynomial interpolations. The integrity proof consists of one group element only, but the size of public information is linear to the size of data. Mohan and Katti [39] proposed a private PDP scheme via Sigma-protocols. They greatly reduced the number of exponentiations in an integrity proof.

Juels and Kaliski [33] defined the proofs of retrievability (POR) model, which ensures that stored data are retrievable from a storage server. Shacham and Waters [43] proposed two POR schemes which enable an unlimited number of verifications. They left the open problem of constructing a provably secure POR scheme which has linear communication complexity without using the random oracle model. Dodis et al. [22] solved the problem via the notion of hardness amplification in complexity theory. Bowers et al. [12] proposed a theoretical framework to construct POR schemes. Their framework is secure in the fully Byzantine adversarial model. Chang and Xu [15] proposed the remote integrity check (RIC) model, where stored data are not necessary to be retrievable from integrity proofs. They introduced the notion of trapdoor compression to capture the fundamental difference between the RIC model and the POR model. Xu and Chang [55] and Yuan and Yu [56] used constant size polynomial commitments to construct private and public POR schemes with constant communication complexity. Li et al. [34] proposed a public POR scheme, where a semi-honest verifier can generate integrity tags. Guang et al. [28] proposed a private POR scheme for fully homomorphic encrypted data. The integrity proof has constant size via securely outsourcing the operations of data blocks and private generators. Azraoui et al. [6] proposed StealthGuard, which is a POR scheme with hidden watchdogs. They used a privacy-preserving word search algorithm to protect the queried sentinels and achieve an unlimited number of verifications.

Since a user can perform dynamic operations on his data, integrity check schemes for dynamic data are considered. Ateniese et al. [4] proposed a private PDP scheme for dynamic data. The number of verifications is limited to the number of embedded tokens. The Merkle hash tree [36], authenticated hash table [40], and authenticated skip list [27] can be used to support dynamic data efficiently. Wang et al. [52,53], Zhu et al. [59] and Heitzmann et al. [30] used the above dynamic data structures to construct integrity check schemes for dynamic data. Erway et al. [24] proposed the dynamic provable data possession (DPDP) model. They also proposed the rank-based authenticated skip list. Huang et al. [31] proposed a systematic exact minimum bandwidth re-generating (SEMBR) code which can transform a dynamic PDP scheme into a dynamic POR scheme. Integrity check schemes for file systems are also considered. Goodrich et al. [26] and Stefanov et al. [46] proposed Athos and Iris, respectively. In recent years, efficiency of dynamic PDP/POR schemes has been improved. Mo et al. [38] proposed the cloud Merkle B+ tree (CMBT) to reduce the worst-cast communication complexity. The communication complexity is logarithmic in the size of data. Zhang and Blanton [57] proposed the balanced update tree, where each node is a range of data blocks that are applied to a dynamic operation. A user maintains his update tree so that he does not need to verify each dynamic operation. Cash et al. [14] and Shi et al. [45] proposed private and public POR schemes with polylogarithmic computation complexity and communication complexity.

To achieve data integrity and availability simultaneously, multiple replicas or coding methods are used with integrity check schemes. Curtmola et al. [20] proposed the multiple-replica provable data possession (MR-PDP) scheme, which ensures that each replica is stored in a storage server. Curtmola et al. [19] used forward error correction (FEC) codes to construct a robust RIC scheme. Bowers et al. [11] proposed the high-availability and integrity layer (HAIL), which uses an erasure code to ensure data retrievability among distributed storage servers. Chen et al. [18] proposed an integrity check scheme for network coding-based storage systems. Their scheme provides a data repair mechanism, but it needs a user to be involved. Cao et al. [13] proposed an integrity check scheme for Luby transform (LT) code-based storage systems. Their scheme provides a data repair mechanism, but it needs an extra backup server to recover the corrupted data. Sarkar and Safavi-Naini [42] and Han et al. [29] proposed POR schemes via fountain codes and maximum rank distance (MRD) codes, respectively. The integrity tags can be efficiently aggregated via XOR operations. High availability for dynamic data is also considered. Wang et al. [48,49] proposed a robust dynamic POR scheme via erasure codes. Chen and Curtmola [16,17] proposed the robust dynamic provable data possession (R-DPDP) model, which applies error correcting codes to dynamic data. Etemad and Küpçü [25] and Barsoum and Hasan [8] proposed dynamic PDP schemes for data replicas.

In recent years, various applications for integrity check schemes are considered. Zhu et al. [60,61] proposed the cooperative provable data possession (CPDP) scheme for hybrid clouds, where multiple clouds store data cooperatively. Wang et al. [47,50] proposed a privacy-preserving public integrity check scheme. They used a blinding technique to hide data information in integrity proofs. Shen and Tzeng [44] defined the delegable provable data possession (delegable PDP) model, where a user can authorize a verifier to check data integrity. The computation complexity of delegation is independent of the data size. Wang [51] proposed the proxy provable data possession (PPDP) model, where a verifier can check data on behalf of a user. Armknecht et al. [1] proposed the outsourced proofs of retrievability (OPOR) model, where a user can outsource integrity check tasks to a verifier. The user can validate the integrity check results. Zheng and Xu [58] and Du et al. [23] integrated the proofs of ownership (PoW) model with the POR model. They proposed public and private POR schemes with data deduplication, respectively.

3. Preliminary

Notation. Let $x \in_{R} X$ denote that element x is chosen from set $X$ randomly and uniformly. Let $| x |$ denote the bit length of element x. Let $| X |$ denote the size of set $X$ . Let $x ∥ y$ denote the concatenation of string x and string y.

Bilinear map. Let q be a large prime. Let $G = ⟨ g ⟩$ and $G_{T} = ⟨ g_{T} ⟩$ be two multiplicative cyclic groups of prime order q. Bilinear map $\hat{e} : G \times G \to G_{T}$ should satisfy the following properties:

Bilinearity: $\forall x, y \in Z_{q}$ , $\hat{e} (g^{x}, g^{y}) = \hat{e} {(g, g)}^{x y}$ .

Non-degeneration: $\hat{e} (g, g) = g_{T}$ .

Computability: $\forall x, y \in Z_{q}$ , $\hat{e} (g^{x}, g^{y})$ is computed in polynomial time.

3.1. Complexity assumption

The truncated (decisional) bilinear Diffie–Hellman exponent assumption. Boneh et al. [9,10] introduced the bilinear Diffie–Hellman exponent (BDHE) problem. The ℓ-BDHE problem is to compute $\hat{e} {(g, g^{'})}^{α^{ℓ + 1}} \in G_{T}$ from a given vector $(g, g^{'}, g^{α}, g^{α^{2}}, \dots, g^{α^{ℓ}}, g^{α^{ℓ + 2}}, g^{α^{ℓ + 3}}, \dots, g^{α^{2 ℓ}}) \in G^{2 ℓ + 1} .$ The truncated version of the ℓ-BDHE problem is to compute $\hat{e} {(g, g^{'})}^{α^{ℓ + 1}} \in G_{T}$ from a given vector $(g, g^{'}, g^{α}, g^{α^{2}}, \dots, g^{α^{ℓ}}) \in G^{ℓ + 2} .$ The advantage for an algorithm $A$ to solve the truncated ℓ-BDHE problem is defined as $Pr [A (g, g^{'}, g^{α}, g^{α^{2}}, \dots, g^{α^{ℓ}}) = \hat{e} {(g, g^{'})}^{α^{ℓ + 1}} : g, g^{'} \in_{R} G, α \in_{R} Z_{q}] .$

The decisional version of the truncated ℓ-BDHE problem is to distinguish $Z = \hat{e} {(g, g^{'})}^{α^{ℓ + 1}}$ from $Z \in_{R} G_{T}$ for a given vector $(g, g^{'}, g^{α}, g^{α^{2}}, \dots, g^{α^{ℓ}}, Z) \in G^{ℓ + 2} \times G_{T} .$ The advantage for an algorithm $A$ to solve the truncated decisional ℓ-BDHE problem is defined as $|\begin{matrix} Pr [A (g, g^{'}, g^{α}, g^{α^{2}}, \dots, g^{α^{ℓ}}, \hat{e} {(g, g^{'})}^{α^{ℓ + 1}}) = 0 : g, g^{'} \in_{R} G, α \in_{R} Z_{q}] \\ - Pr [A (g^{'}, g, g^{α}, g^{α^{2}}, \dots, g^{α^{ℓ}}, Z) = 0 : g, g^{'} \in_{R} G, α \in_{R} Z_{q}, Z \in_{R} G_{T}] \end{matrix}| .$

Definition 1.
The truncated (decisional) BDHE assumption is $(t, ϵ, ℓ)$ -secure if no t-time algorithm has advantage over ϵ in solving the truncated (decisional) ℓ-BDHE problem.

The inverse computational Diffie–Hellman assumption. The inverse computational Diffie–Hellman (InvCDH) problem [7] is to compute $g^{\frac{1}{α}} \in G$ from a given vector $(g, g^{α}) \in G^{2}$ . The advantage for an algorithm $A$ to solve the InvCDH problem is defined as $Pr [A (g, g^{α}) = g^{\frac{1}{α}} : g \in G, α \in_{R} Z_{q}] .$
Definition 2.
The InvCDH assumption is $(t, ϵ)$ -secure if no t-time algorithm has advantage over ϵ in solving the InvCDH problem.

The knowledge of exponent assumption. Damgård [21] introduced the knowledge of exponent assumption (KEA1). The problem is to output $(C, Y) \in G^{2}$ from a given vector $(g, g^{α}) \in G^{2}$ such that $Y = C^{α}$ . A solution of the problem is to choose $c \in_{R} Z_{q}$ and output $(C, Y) = (g^{c}, g^{α c})$ . The KEA1 states that this is the only way to solve the problem in polynomial time. If an algorithm $A$ takes $(g, g^{α})$ as the input and outputs $(C, Y)$ such that $Y = C^{α}$ , there exists an extractor $\overline{A} (g, g^{α}, A)$ who extracts the exponent c such that $C = g^{c}$ .
4. Delegated integrity check model

Delegated integrity check includes the notions of delegated PDP and delegated POR. The formal model and the threat model of delegated PDP/POR are defined in this section. An application scenario for personal health records (PHRs) is also provided in this section.

4.1. Formal model

Let $U$ denote a user (data owner), $V$ denote a verifier and $S$ denote a storage server. In the setup phase, the system manager runs algorithm Setup to generate the system parameter. $U$ runs algorithm KeyGen to generate his secret-public key pair. Then, $U$ registers his public key to the system manager. $V$ generates his secret-public key pair and registers his public key in the same way. $U$ runs algorithm TagGen to generate the data identifier and integrity tags for his data. Then, $U$ stores his data, data identifier, and integrity tags in $S$ .

$Setup (1^{k}) \to π$ : It is a probabilistic polynomial-time algorithm. Setup takes security parameter k as the input and outputs public parameter π.

$KeyGen (π, I) \to ({sk}_{I}, {pk}_{I})$ : It is a probabilistic polynomial-time algorithm. KeyGen takes public parameter π and identity $I$ as inputs and outputs secret-public key pair $({sk}_{I}, {pk}_{I})$ .

$TagGen (π, {sk}_{U}, M) \to (h_{M}, Σ)$ : It is a probabilistic polynomial-time algorithm. TagGen takes public parameter π, secret key ${sk}_{U}$ , and data M as inputs and outputs data identifier $h_{M}$ and integrity tags Σ.

In the delegation phase, $U$ and $V$ establish a secure channel between them to start a delegation process. $V$ runs algorithm GenKT to generate his key token for $U$ ’s data. Then, $V$ sends his key token to $U$ via the secure channel. $U$ runs algorithm GenDK to verify the key token and generate the delegation key. Then, $U$ sends the delegation key to $S$ if the key token is valid. $S$ runs algorithm VrfyDK to verify the delegation key. The delegation process is successful if the delegation key is valid. If $U$ would like to revoke $V$ ’s integrity check capability, he can provide the key token to $S$ or ask $S$ to remove the delegation key.

$GenKT (π, {sk}_{V}, {pk}_{V}, h_{M}) \to {kt}_{V, M}$ : It is a deterministic polynomial-time algorithm. GenKT takes public parameter π, secret-public key pair $({sk}_{V}, {pk}_{V})$ , and data identifier $h_{M}$ as inputs and outputs key token ${kt}_{V, M}$ .

$GenDK (π, {sk}_{U}, {kt}_{V, M}, {pk}_{V}, h_{M}) \to {{dk}_{U \to V, M}, ⊥}$ : It is a deterministic polynomial-time algorithm. GenDK takes public parameter π, secret key ${sk}_{U}$ , key token ${kt}_{V, M}$ , public key ${pk}_{V}$ , and data identifier $h_{M}$ as inputs. If ${kt}_{V, M}$ is consistent with $({pk}_{V}, h_{M})$ , GenDK outputs delegation key ${dk}_{U \to V, M}$ .

$VrfyDK (π, {dk}_{U \to V, M}, {pk}_{U}, {pk}_{V}, h_{M}) \to {true, false}$ : It is a deterministic polynomial-time algorithm. VrfyDK takes public parameter π, delegation key ${dk}_{U \to V, M}$ , public key ${pk}_{U}$ , public key ${pk}_{V}$ , and data identifier $h_{M}$ as inputs and outputs whether ${dk}_{U \to V, M}$ is consistent with $({pk}_{U}, {pk}_{V}, h_{M})$ .

In the integrity check phase, $V$ checks $U$ ’s data on behalf of $U$ . $V$ and $S$ interact with each other in the challenge-and-response manner. $V$ runs algorithm GenChal to generate a challenge for $U$ ’s data. Then, $V$ sends the challenge to $S$ . If $V$ is not revoked by $U$ , $S$ runs algorithm GenProof to verify the challenge and generate an integrity proof. Otherwise, $S$ runs algorithm ForgeProof to verify the challenge and forge an integrity proof. Then, $S$ sends the integrity proof to $V$ if the challenge is valid. $V$ runs algorithm VrfyProof to verify the integrity proof. $V$ will alert $U$ if the integrity proof is not valid. In the delegated POR model, $V$ can run algorithm Extract to extract the data from integrity proofs if the integrity proofs include enough knowledge of the data.

$GenChal (π, h_{M}) \to {chal}_{M}$ . It is a probabilistic polynomial-time algorithm. GenChal takes public parameter π and data identifier $h_{M}$ as inputs and outputs challenge ${chal}_{M}$ .

$GenProof (π, M, Σ, {dk}_{U \to V, M}, {chal}_{M}, h_{M}) \to {{pf}_{{chal}_{M}, V}, ⊥}$ . It is a probabilistic polynomial-time algorithm. GenProof takes public parameter π, data M, integrity tags Σ, delegation key ${dk}_{U \to V, M}$ , challenge ${chal}_{M}$ , and data identifier $h_{M}$ as inputs. If ${chal}_{M}$ is consistent with $h_{M}$ , GenProof outputs integrity proof ${pf}_{{chal}_{M}, V}$ .

$ForgeProof (π, M^{*}, {kt}_{V, M}, {chal}_{M}, h_{M}) \to {{pf}_{{chal}_{M}, V}, ⊥}$ . It is a probabilistic polynomial-time algorithm. ForgeProof takes public parameter π, altered data $M^{*}$ , key token ${kt}_{V, M}$ , challenge ${chal}_{M}$ , and data identifier $h_{M}$ as inputs. If ${chal}_{M}$ is consistent with $h_{M}$ , ForgeProof outputs forged proof ${pf}_{{chal}_{M}, V}$ .

$VrfyProof (π, {chal}_{M}, {pf}_{{chal}_{M}, V}, h_{M}, {sk}_{V}) \to {true, false}$ . It is a deterministic polynomial-time algorithm. VrfyProof takes public parameter π, challenge ${chal}_{M}$ , integrity proof ${pf}_{{chal}_{M}, V}$ , data identifier $h_{M}$ , and secret key ${sk}_{V}$ as inputs and outputs whether ${pf}_{{chal}_{M}, V}$ is consistent with $({chal}_{M}, h_{M}, {sk}_{V})$ .

$Extract (π, {{chal}_{M}}, {{pf}_{{chal}_{M}, V}}, h_{M}, {sk}_{V}) \to {M, ⊥}$ . It is a deterministic polynomial-time algorithm. Extract takes public parameter π, challenges ${{chal}_{M}}$ , integrity proofs ${{pf}_{{chal}_{M}, V}}$ , data identifier $h_{M}$ , and secret key ${sk}_{V}$ as inputs. If data M is extractable from ${{pf}_{{chal}_{M}, V}}$ , Extract outputs M.

4.2. Threat model

Delegated integrity check assumes that a verifier will not collude with a storage server. This assumption is natural because a verifier is in an opposite position to a storage server in an integrity check scheme. Delegated integrity check models the verifier and the storage server as follows:

A storage server rejects malformed delegation keys and malformed integrity challenges. The storage server may not store data and integrity tags correctly and will try to forge an integrity proof to pass the verification.

A verifier rejects invalid integrity proofs. The verifier may want to re-delegate his integrity check capability and will provide a malformed delegation key or a malformed integrity challenge to a storage server.

A delegated PDP/POR scheme is secure against the verifier and storage server if it satisfies the requirements of proof unforgeability, proof indistinguishability and delegation key unforgeability simultaneously.

4.2.1. Proof unforgeability

The proof unforgeability game models the notion that a storage server cannot modify stored data without being detected by a verifier. Challenger $C$ plays the role of a verifier, and adversary $A$ plays the role of a storage server. $A$ can choose data and obtain the integrity tags adaptively. $A$ can also choose verifiers and obtain the delegation keys adaptively. Once $A$ decides the target data $M^{*}$ , he modifies $M^{*}$ to $M^{'}$ and receives an integrity challenge from $C$ . $A$ no longer possesses $M^{*}$ . If $A$ can forge an integrity proof that passes the verification, he wins this game.

The proof unforgeability game ${Game}^{PF - UF}$ is as follows:

Setup. $C$ generates public parameter π, user $U$ ’s key pair $({sk}_{U}, {pk}_{U})$ , and verifier $V$ ’s key pair $({sk}_{V}, {pk}_{V})$ . Then, $C$ sends $(π, {pk}_{U}, {pk}_{V})$ to $A$ .

Query. $A$ queries oracle $O_{Tag}$ to obtain integrity tags. $A$ also queries oracle $O_{DK}$ to obtain delegation keys.

$O_{Tag}$ : $A$ chooses data M. $O_{Tag}$ returns integrity tags Σ and data identifier $h_{M}$ .

$O_{DK}$ : $A$ chooses verifier $W$ and data identifier $h_{M}$ . $O_{DK}$ returns delegation key ${dk}_{U \to W, M}$ .

Challenge. $A$ indicates which $O_{Tag}$ -query is the target. The target is denoted as $(M^{*}, Σ^{*}, h_{M^{*}})$ . $A$ modifies $M^{*}$ to $M^{'}$ so that he no longer possesses $M^{*}$ . $C$ gives $A$ delegation key ${dk}_{U \to V, M^{*}}$ and challenge ${chal}_{M^{*}}$ .

Answer. $A$ generates integrity proof ${pf}_{{chal}_{M^{*}}, V}$ without the possession of $M^{*}$ . $A$ wins ${Game}^{PF - UF}$ if $VrfyProof (π, {chal}_{M^{*}}, {pf}_{{chal}_{M^{*}}, V}, h_{M^{*}}, {sk}_{V}) = true$ . The advantage ${Adv}_{A}^{PF - UF}$ is defined as $Pr [A wins {Game}^{PF - UF}]$ .

Definition 3.
A delegated PDP/POR scheme Π satisfies the requirement of proof unforgeability if no probabilistic polynomial-time adversary has non-negligible advantage to win the proof unforgeability game ${Game}_{Π}^{PF - UF}$ .

4.2.2. Proof indistinguishability

The proof indistinguishability game models the notion that only the verifiers can verify integrity proofs even if the network communication is eavesdropped. Challenger $C$ plays the role of a storage server, and adversary $A$ plays the role of a revoked verifier (a third party). $A$ can choose integrity challenges and obtain the integrity proofs adaptively. $A$ can also choose verifiers and obtain the delegation keys adaptively. Once $A$ is ready, he obtains the target proof and tries to verify it. If $A$ can answer validity of the proof correctly, he wins this game.

The proof indistinguishability game ${Game}^{PF - IND}$ is as follows:

Setup. $C$ generates public parameter π, user $U$ ’s key pair $({sk}_{U}, {pk}_{U})$ , and verifier $V$ ’s key pair $({sk}_{V}, {pk}_{V})$ . $C$ chooses data M. Then, $C$ generates data identifier $h_{M}$ , integrity tags Σ, key token ${kt}_{V, M}$ , and delegation key ${dk}_{U \to V, M}$ . $C$ sends $(π, {pk}_{U}, {pk}_{V}, M, Σ, h_{M}, {kt}_{V, M}, {dk}_{U \to V, M})$ to $A$ .

Query-1. $A$ queries oracle $O_{DK}$ to obtain delegation keys. $A$ also queries oracle $O_{Proof}$ to obtain integrity proofs.

$O_{DK}$ : $A$ chooses verifier $W$ . $O_{DK}$ returns delegation key ${dk}_{U \to W, M}$ .

$O_{Proof}$ : $A$ chooses challenge ${chal}_{M}$ . $O_{Proof}$ returns integrity proof ${pf}_{{chal}_{M}, V}$ .

Challenge. $A$ chooses challenge ${chal}_{M}^{*}$ . $C$ gives $A$ the target proof ${pf}_{{chal}_{M}^{*}, V}$ . Validity of ${pf}_{{chal}_{M}^{*}, V}$ depends on an uniform bit b. If $b = 1$ , ${pf}_{{chal}_{M}^{*}, V}$ is valid. Otherwise, ${pf}_{{chal}_{M}^{*}, V}$ is invalid.

Query-2. It is the same as the query-1 phase.

Answer. $A$ answers validity $b^{'}$ of ${pf}_{{chal}_{M}^{*}, V}$ . $A$ wins ${Game}^{PF - IND}$ if $b^{'} = b$ . The advantage ${Adv}_{A}^{PF - IND}$ is defined as $| Pr [A wins {Game}^{PF - IND}] - \frac{1}{2} |$ .

Definition 4.
A delegated PDP/POR scheme Π satisfies the requirement of proof indistinguishability if no probabilistic polynomial-time adversary has non-negligible advantage to win the proof indistinguishability game ${Game}_{Π}^{PF - IND}$ .

4.2.3. Delegation key unforgeability

The delegation key unforgeability game models the notion that only the user can generate delegation keys even if a verifier is corrupted. Challenger $C$ plays the role of a storage server, and adversary $A$ plays the role of a revoked verifier (a third party). $A$ can choose verifiers adaptively and obtain the delegation keys. If $A$ can forge a delegation key that passes the verification, he wins this game.

The delegation key unforgeability game ${Game}^{DK - UF}$ is as follows:

Setup. $C$ generates public parameter π and user $U$ ’s key pair $({sk}_{U}, {pk}_{U})$ . Then, $C$ sends $(π, {pk}_{U})$ to $A$ .

Query. $A$ queries oracle $O_{DK}$ to obtain delegation keys.

$O_{DK}$ : $A$ chooses verifier $W$ and data identifier $h_{M}$ . $O_{DK}$ returns delegation key ${dk}_{U \to W, M}$ .

Answer. $A$ chooses verifier $W^{*}$ and data identifier $h_{M}^{*}$ as the target. $A$ generates delegation key ${dk}_{U \to W^{*}, M}$ and returns $({sk}_{W^{*}}, {pk}_{W^{*}}, h_{M}^{*}, {dk}_{U \to W^{*}, M})$ . $A$ wins ${Game}^{DK - UF}$ if $VrfyDK (π, {dk}_{U \to W^{*}, M}, {pk}_{U}, {pk}_{W^{*}}, h_{M}^{*}) = true$ and $({sk}_{W^{*}}, {pk}_{W^{*}})$ is valid. The advantage ${Adv}_{A}^{DK - UF}$ is defined as $Pr [A wins {Game}^{DK - UF}]$ .

Definition 5.
A delegated PDP/POR scheme Π satisfies the requirement of delegation key unforgeability if no probabilistic polynomial-time adversary has non-negligible advantage to win the delegation key unforgeability game ${Game}_{Π}^{DK - UF}$ .

4.3. Application scenario: Clouds for personal health records

A patient’s personal health records (PHRs) contain systematic documentation of the patient’s medical histories and self-reporting data. The medical histories are provided by clinics and hospitals. The self-reporting data include daily physiological readings, drug-reaction records, etc. A patient has to share his PHRs among doctors in medical institutes for medical referral or research. PHRs are personal data and should not be checked by the public. A patient maintains his PHRs by himself, and he manages the verifiers of his PHRs. The patient can organize his PHRs in a hierarchical tree structure and categorize the PHRs according to the divisions of medical institutes (Fig. 2). The patient can authorize a doctor to access his PHRs in some categories. For example, the patient will authorize a dentist to access the PHRs in category $⟨ Dentistry ⟩$ and category $⟨ X-ray ⟩$ . The doctor has to make sure that he gets the correct PHRs before he uses them with confidence. The patient can also delegate a verifier to check his PHRs. The verifier should check integrity periodically to make sure that the PHRs are not altered. Many countries are digitizing the medical records of their people [54]. The international organization for standardization (ISO) has already developed standard ISO/HL7 10781:2009 [32] for digitized health records. Furthermore, many medical clouds are now being developed. For example, Microsoft’s HealthVault [37]. Delegating the integrity check capability for the health records will be a need in the future.

Fig. 2.

Example of the hierarchical structure for personal health records. A health record is stored in the category that the health record belongs to.

Consider that patient $U$ stores his PHRs in a medical cloud. Figure 3 illustrates the storing process of the PHRs. When $U$ comes to see doctor $V$ at time $T$ , $V$ gives $U$ the medical examination and drug treatment. $V$ creates medical record ${MR}_{U, V, T}$ of this clinic visit and uses his secret key ${sk}_{V}$ to sign ${MR}_{U, V, T}$ . Then, $V$ gives $U$ the health record ${HR}_{U, V, T} = ({MR}_{U, V, T}, Sig ({sk}_{V}, {MR}_{U, V, T}))$ . $U$ uses his public key ${pk}_{U}$ to encrypt ${HR}_{U, V, T}$ into ciphertext M. Then, $U$ uses his secret key ${sk}_{U}$ to generate data identifier $h_{M}$ and integrity tags Σ. Finally, $U$ uploads $(M, Σ, h_{M})$ to the storage server. $U$ also uploads his self-reporting physiological data. The medical cloud organizes $U$ ’s health records and self-reporting data to form the PHRs.

Fig. 3.

The storing process of personal health records. $V$ ’s signature and $U$ ’s integrity tag prevent any single party’s modification to the health records.

Figure 4 illustrates the delegation process of the PHRs. When $U$ comes to see doctor $W$ at time $T^{'}$ , he authorizes $W$ to access his PHR M for consultation. $W$ uses $h_{M}$ and his secret key ${sk}_{W}$ to generate his key token ${kt}_{W, M}$ . Then, $W$ gives ${kt}_{W, M}$ to $U$ via a secure channel. $U$ uses $h_{M}$ and $W$ ’s public key ${pk}_{W}$ to verify ${kt}_{W, M}$ . If ${kt}_{W, M}$ is valid, $U$ uses ${sk}_{U}$ to generate delegation key ${dk}_{U \to W, M}$ . $U$ sends ${dk}_{U \to W, M}$ to the storage server. The storage server uses ${pk}_{U}$ , ${pk}_{W}$ , and $h_{M}$ to verify ${dk}_{U \to W, M}$ . If ${dk}_{U \to W, M}$ is valid, $U$ uses ${sk}_{U}$ and ${kt}_{W, M}$ to generate re-encryption key ${rk}_{U \to W, M}$ . $U$ gives ${rk}_{U \to W, M}$ to $W$ . $W$ can use ${sk}_{W}$ to check M. $W$ can also use ${sk}_{W}$ and ${rk}_{U \to W, M}$ to decrypt M.

Fig. 4.

The delegation process of personal health records.

Figure 5 illustrates the integrity check process of the PHRs. When $W$ would like to check M, he sends challenge ${chal}_{M}$ to the storage server. The storage server uses M, Σ, ${dk}_{U \to W, M}$ , and ${chal}_{M}$ to generate integrity proof ${pf}_{{chal}_{M}}$ . Then, the storage server returns ${pf}_{{chal}_{M}}$ to $W$ . $W$ uses ${sk}_{W}$ and ${chal}_{M}$ to verify ${pf}_{{chal}_{M}}$ .

Fig. 5.

The integrity check process of personal health records.

Figure 6 illustrates the retrieval process of the PHRs. When $W$ would like to access M, he sends challenge ${chal}_{M}$ to the storage server. The storage server uses M, Σ, ${dk}_{U \to W, M}$ , and ${chal}_{M}$ to generate integrity proof ${pf}_{{chal}_{M}}$ . Then, the storage server returns M and ${pf}_{{chal}_{M}}$ to $W$ . $W$ uses ${sk}_{W}$ and ${chal}_{M}$ to verify M and ${pf}_{{chal}_{M}}$ . If M and ${pf}_{{chal}_{M}}$ are valid, $W$ uses ${rk}_{U \to W, M}$ to re-encrypt M into $M^{'}$ . Then, $W$ uses ${sk}_{W}$ to decrypt $M^{'}$ and obtain HR.

Fig. 6.

The retrieval process of personal health records.

5. Delegated provable data possession scheme

A delegated PDP scheme for hierarchical data is provided in this section. The security of the scheme is based on the truncated (decisional) bilinear Diffie–Hellman exponent assumption, the inverse computation Diffie–Hellman assumption, and the knowledge of exponent assumption in the random oracle model.

5.1. Construction

System setup. Let k be the security parameter, q be a k-bit prime, $G = ⟨ g ⟩$ and $G_{T} = ⟨ g_{T} ⟩$ be two q-order multiplicative groups, and $\hat{e} : G \times G \to G_{T}$ be a bilinear map. The system manager chooses a large space $K$ of hierarchical keys and a degree d of hierarchical data, where $| K | = Exp (k)$ . The system manager also chooses four cryptographic hash functions $H_{1} : K \times {0, 1}^{*} \to G$ , $H_{2} : G^{*} \times {0, 1}^{*} \to G$ , $H_{3} : {(Z_{q})}^{*} \to G$ and $H_{4} : K \times {1, 2, \dots, d} \to K$ . The public parameter is $π = (q, G, g, G_{T}, g_{T}, \hat{e}, K, d, H_{1}, H_{2}, H_{3}, H_{4})$ .

Key generation. User $U$ chooses his secret key ${sk}_{U} = x \in_{R} Z_{q}$ and computes his public key ${pk}_{U} = g^{x}$ . Then, $U$ registers ${pk}_{U}$ to the system manager. Verifier $V$ also computes his secret-public key pair $({sk}_{V}, {pk}_{V})$ and registers ${pk}_{V}$ to the system manager.

Fig. 7.

Example of two-degree hierarchical data. An internal node is a category, and an external node is a file.

Tag generation. Hierarchical data M are organized in a tree structure. An internal node is a category. An external node is a file. Without loss of generality, assume that a category has at most d sub-categories. The number of files in a category is not limited. Figure 7 illustrates an example of two-degree hierarchical data. Let $D_{0}$ denote the root category. The jth sub-category of category $D_{i}$ can be denoted as $D_{d i + j}$ , where $1 ⩽ j ⩽ d$ . Each category $D_{i}$ is associated with a hierarchical key $K_{i}$ . The key of a category can derive the keys of the sub-categories. To set up the hierarchical keys for M, $U$ chooses root key $K_{M} = K_{0} \in_{R} K$ . Then, $U$ can derive key $K_{d i + j}$ from key $K_{i}$ recursively: $K_{d i + j} = H_{4} (K_{i}, j) .$ Figure 8 illustrates an example of key derivation for two-degree hierarchical data. Category $D_{3}$ is the first sub-category of category $D_{1}$ so key $K_{3}$ is derived from key $K_{1}$ as $K_{3} = H_{4} (K_{1}, 1)$ .

Fig. 8.

Example of key derivation for two-degree hierarchical data.

To generate integrity tags Σ for M, $U$ decides the number b of data blocks which are protected by an integrity tag. Then, $U$ chooses b data identifiers $H_{M} = (h_{M, 1}, h_{M, 2}, \dots, h_{M, b}) \in_{R} G^{b}$ . Let $F_{i, j}$ denote the jth file in category $D_{i}$ . $U$ divides each file $F_{i, j}$ into $n \times b$ blocks of k bits. That is, $F_{i, j} = [\begin{matrix} f_{i, j}^{(1, 1)} & f_{i, j}^{(1, 2)} & \dots & f_{i, j}^{(1, b)} \\ f_{i, j}^{(2, 1)} & f_{i, j}^{(2, 2)} & \dots & f_{i, j}^{(2, b)} \\ ⋮ & ⋮ & ⋱ & ⋮ \\ f_{i, j}^{(n, 1)} & f_{i, j}^{(n, 2)} & \dots & f_{i, j}^{(n, b)} \end{matrix}] .$ Then, $U$ generates integrity tag $σ_{i, j}^{(w)}$ for blocks $(f_{i, j}^{(w, 1)}, f_{i, j}^{(w, 2)}, \dots, f_{i, j}^{(w, b)})$ as follows: $σ_{i, j}^{(w)} = {[H_{1} (K_{i}, i ∥ j ∥ w) \cdot \prod_{ℓ = 1}^{b} h_{M, ℓ}^{f_{i, j}^{(w, ℓ)}}]}^{{sk}_{U}} .$

After generating the integrity tags for all files, $U$ uploads $(M, Σ, H_{M}, K_{M})$ to storage server $S$ , where $Σ = {σ_{i, j}^{(w)}}$ . $U$ keeps $(H_{M}, K_{M})$ locally to identify and check M.

Delegation. $U$ can delegate verifier $V$ to check the files in category $D_{i}$ and the sub-categories. $U$ gives $H_{M}$ to $V$ . $V$ generates his key token ${kt}_{V, D_{i}}$ as follows: ${kt}_{V, D_{i}} = H_{2} {({pk}_{V}, H_{M}, D_{i})}^{{sk}_{V}} .$ Then, $V$ sends ${kt}_{V, D_{i}}$ to $U$ via a secure channel.

$U$ verifies ${kt}_{V, D_{i}}$ by checking whether $\hat{e} (g, {kt}_{V, D_{i}}) = \hat{e} ({pk}_{V}, H_{2} ({pk}_{V}, H_{M}, D_{i}))$ . If ${kt}_{V, D_{i}}$ is valid, $U$ generates the delegation key ${dk}_{U \to V, D_{i}}$ as follows: ${dk}_{U \to V, D_{i}} = {kt}_{V, D_{i}}^{1 / {sk}_{U}} .$ Then, $U$ sends ${dk}_{U \to V, D_{i}}$ to $S$ .

$S$ verifies ${dk}_{U \to V, D_{i}}$ by checking whether $\hat{e} ({pk}_{U}, {dk}_{U \to V, D_{i}}) = \hat{e} ({pk}_{V}, H_{2} ({pk}_{V}, H_{M}, D_{i}))$ . If ${dk}_{U \to V, D_{i}}$ is valid, $U$ keeps ${kt}_{V, D_{i}}$ secretly and sends $K_{i}$ to $V$ via the secure channel.

Integrity check. To check integrity of file $F_{i^{*}, j} = {[f_{i^{*}, j}^{(w, ℓ)}]}_{1 ⩽ w ⩽ n, 1 ⩽ ℓ ⩽ b}$ , $V$ chooses n coefficients $(c_{1}, c_{2}, \dots, c_{n}) \in_{R} {(Z_{q})}^{n}$ . Coefficient $c_{w} = 0$ means that blocks $(f_{i^{*}, j}^{(w, 1)}, f_{i^{*}, j}^{(w, 2)}, \dots, f_{i^{*}, j}^{(w, b)})$ are not chosen to be checked. $V$ can sample a relatively small portion of $F_{i^{*}, j}$ to check integrity more efficiently, which is discussed in Section 7.2. $V$ chooses $s \in_{R} Z_{q}$ and generates challenge ${chal}_{i^{*}, j} = (C, C_{1}^{'}, C_{2}^{'}, \dots, C_{b}^{'}, C^{″})$ as follows: $\begin{array}{rcl} C = (c_{1}, c_{2}, \dots, c_{n}), \\ C_{ℓ}^{'} = h_{M, ℓ}^{s}, 1 ⩽ ℓ ⩽ b, \\ C^{″} = H_{3} {(C)}^{s} . \end{array}$ Then, $V$ sends ${chal}_{i^{*}, j}$ to $S$ .

$S$ verifies ${chal}_{i^{*}, j}$ by checking whether $\hat{e} (\prod_{ℓ = 1}^{b} C_{ℓ}^{'}, H_{3} (C)) = \hat{e} (\prod_{ℓ = 1}^{b} h_{M, ℓ}, C^{″})$ . If ${chal}_{i^{*}, j}$ is valid, $S$ chooses $t \in_{R} Z_{q}$ and generates integrity proof ${pf}_{{chal}_{i^{*}, j}, V} = (ρ, V_{1}, V_{2}, \dots, V_{b}, V_{1}^{'}, V_{2}^{'}, \dots, V_{b}^{'}, V^{″}, V^{‴})$ as follows: $\begin{array}{rcl} ρ = \hat{e} {(\prod_{w = 1}^{n} σ_{i^{*}, j}^{(w) c_{w}}, {dk}_{U \to V, D_{i}})}^{t}, \\ V_{ℓ} = C_{ℓ}^{' \sum_{w = 1}^{n} c_{w} f_{i^{*}, j}^{(w, ℓ)}}, 1 ⩽ ℓ ⩽ b, \\ V_{ℓ}^{'} = g^{\sum_{w = 1}^{n} c_{w} f_{i^{*}, j}^{(w, ℓ)}}, 1 ⩽ ℓ ⩽ b, \\ V^{″} = H_{2} {({pk}_{V}, H_{M}, D_{i})}^{t}, \\ V^{‴} = C^{'' t} . \end{array}$ Then, $S$ sends ${pf}_{{chal}_{i^{*}, j}, V}$ to $V$ .

$V$ derives key $K_{i^{*}}$ from $K_{i}$ recursively. Then, $V$ verifies ${pf}_{{chal}_{i^{*}, j}, V}$ by checking whether

$ρ^{s} = \hat{e} {(\prod_{w = 1}^{n} H_{1} {(K_{i^{*}}, i^{*} ∥ j ∥ w)}^{s c_{w}} \cdot \prod_{ℓ = 1}^{b} V_{ℓ}, V^{″})}^{{sk}_{V}}$ ,

$\hat{e} (V_{ℓ}, g) = \hat{e} (C_{ℓ}^{'}, V_{ℓ}^{'})$ , $1 ⩽ ℓ ⩽ b$ ,

$\hat{e} (V^{″}, C^{″}) = \hat{e} (H_{2} ({pk}_{V}, H_{M}, D_{i}), V^{‴})$ .

$V$ can check multiple files in different categories at the same time because they share the same data identifiers $H_{M} = (h_{M, 1}, h_{M, 2}, \dots, h_{M, b})$ .

Revocation. If $U$ would like to revoke $V$ ’s integrity check capability, he can ask $S$ to remove ${dk}_{U \to V, D_{i}}$ directly. A more effective solution is that $U$ reveals ${kt}_{V, D_{i}}$ to $S$ . $S$ can use ${kt}_{V, D_{i}}$ to forge ${pf}_{{chal}_{i^{*}, j}, V}$ for corrupted file $F_{i^{*}, j}^{'} = {[f_{i^{*}, j}^{' (w, ℓ)}]}_{1 ⩽ w ⩽ n, 1 ⩽ ℓ ⩽ b}$ in the following way. $S$ chooses $t \in_{R} Z_{q}$ and computes $(V_{1}, V_{2}, \dots, V_{b}, V_{1}^{'}, V_{2}^{'}, \dots, V_{b}^{'}, V^{″}, V^{‴})$ as usual, but he derives $K_{i^{*}}$ from $K_{M}$ and computes ρ as follows: $ρ = \hat{e} {(\prod_{w = 1}^{n} {[H_{1} (K_{i^{*}}, i^{*} ∥ j ∥ w) \cdot \prod_{ℓ = 1}^{b} h_{M, ℓ}^{f_{i^{*}, j}^{' (w, ℓ)}}]}^{c_{w}}, {kt}_{V, D_{i}})}^{t} .$

5.1.1. Correctness

The integrity tags are aggregately verifiable. They can be aggregated together and verified at the same time. Nevertheless, the integrity tags are not homomorphically combinable. Combing tag $σ_{i, j}^{(w_{1})} = {[H_{1} (K_{i}, i ∥ j ∥ w_{1}) \cdot \prod_{ℓ = 1}^{b} h_{M, ℓ}^{f_{i, j}^{(w_{1}, ℓ)}}]}^{{sk}_{U}}$ and tag $σ_{i, j}^{(w_{2})} = {[H_{1} (K_{i}, i ∥ j ∥ w_{2}) \cdot \prod_{ℓ = 1}^{b} h_{M, ℓ}^{f_{i, j}^{(w_{2}, ℓ)}}]}^{{sk}_{U}}$ together results in $σ^{'} = {[H_{1} (K_{i}, i ∥ j ∥ w_{1}) \cdot H_{1} (K_{i}, i ∥ j ∥ w_{2}) \cdot \prod_{ℓ = 1}^{b} h_{M, ℓ}^{f_{i, j}^{(w_{1}, ℓ)} + f_{i, j}^{(w_{2}, ℓ)}}]}^{{sk}_{U}},$ which is not an integrity tag for block $f_{i, j}^{(w_{1}, ℓ)} + f_{i, j}^{(w_{2}, ℓ)}$ . Section 5.2.1 shows that the integrity tags are unforgeable without the knowledge of secret key ${sk}_{U}$ .

To check integrity, $V$ chooses n coefficients $(c_{1}, c_{2}, \dots, c_{n})$ . $S$ combines integrity tags ${σ_{i^{*}, j}^{(w)}}$ into $\prod_{w = 1}^{n} σ_{i^{*}, j}^{(w) c_{w}} = {[\prod_{w = 1}^{n} H_{1} {(K_{i^{*}}, i^{*} ∥ j ∥ w)}^{c_{w}} \cdot \prod_{ℓ = 1}^{b} h_{M, ℓ}^{\sum_{w = 1}^{n} c_{w} f_{i^{*}, j}^{(w, ℓ)}}]}^{{sk}_{U}} .$ If $S$ deviates, the combination is not identical to $\prod_{w = 1}^{n} H_{1} {(K_{i^{*}}, i^{*} ∥ j ∥ w)}^{c_{w}}$ . Once $S$ combines these tags correctly, $\sum_{w = 1}^{n} c_{w} f_{i^{*}, j}^{(w, ℓ)}$ is in the exponent of $h_{M, ℓ}$ . By KEA1, $S$ has to use blocks $(f_{i^{*}, j}^{(1, ℓ)}, f_{i^{*}, j}^{(2, ℓ)}, \dots, f_{i^{*}, j}^{(n, ℓ)})$ to compute $V_{ℓ} = C_{ℓ}^{' \sum_{w = 1}^{n} c_{w} f_{i^{*}, j}^{(w, ℓ)}}$ and $V_{ℓ}^{'} = g^{\sum_{w = 1}^{n} c_{w} f_{i^{*}, j}^{(w, ℓ)}}$ . Verification equation $ρ^{s} = \hat{e} {(\prod_{w = 1}^{n} H_{1} {(K_{i^{*}}, i^{*} ∥ j ∥ w)}^{s c_{w}} \cdot \prod_{ℓ = 1}^{b} V_{ℓ}, V^{″})}^{{sk}_{V}}$ checks whether ρ includes the correct combination $\prod_{w = 1}^{n} H_{1} {(K_{i^{*}}, i^{*} ∥ j ∥ w)}^{c_{w}}$ and whether $V_{ℓ}$ includes the same exponent $\sum_{w = 1}^{n} c_{w} f_{i^{*}, j}^{(w, ℓ)}$ as ρ includes. If $S$ passes this verification, he possesses $(f_{i^{*}, j}^{(1, ℓ)}, f_{i^{*}, j}^{(2, ℓ)}, \dots, f_{i^{*}, j}^{(n, ℓ)})$ .

Assume that ${pf}_{{chal}_{i^{*}, j}, V} = (ρ, V_{1}, V_{2}, \dots, V_{b}, V_{1}^{'}, V_{2}^{'}, \dots, V_{b}^{'}, V^{″}, V^{‴})$ is well formed and ${chal}_{i^{*}, j} = (C, C_{1}^{'}, C_{2}^{'}, \dots, C_{b}^{'}, C^{″}) = ((c_{1}, c_{2}, \dots, c_{n}), h_{M, 1}^{s}, h_{M, 2}^{s}, \dots, h_{M, b}^{s}, H_{3} {(C)}^{s})$ . That is, $\begin{array}{rclr} ρ = \hat{e} {(\prod_{w = 1}^{n} σ_{i^{*}, j}^{(w) c_{w}}, {dk}_{U \to V, D_{i}})}^{t}, & (1) \\ V_{ℓ} = C_{ℓ}^{' \sum_{w = 1}^{n} c_{w} f_{i^{*}, j}^{(w, ℓ)}} = h_{M, ℓ}^{s \sum_{w = 1}^{n} c_{w} f_{i^{*}, j}^{(w, ℓ)}}, 1 ⩽ ℓ ⩽ b, & (2) \\ V_{ℓ}^{'} = g^{\sum_{w = 1}^{n} c_{w} f_{i^{*}, j}^{(w, ℓ)}}, 1 ⩽ ℓ ⩽ b, & (3) \\ V^{″} = H_{2} {({pk}_{V}, H_{M}, D_{i})}^{t}, & (4) \\ V^{‴} = C^{'' t} = H_{3} {(C)}^{s t} . & (5) \end{array}$

Thus, the three verification equations are derived as follows:

$ρ^{s} = \hat{e} {(\prod_{w = 1}^{n} H_{1} {(K_{i^{*}}, i^{*} ∥ j ∥ w)}^{s c_{w}} \cdot \prod_{ℓ = 1}^{b} V_{ℓ}, V^{″})}^{{sk}_{V}}$ by (1), (2) and (4): $\begin{array}{rcl} ρ^{s} & = & \hat{e} {(\prod_{w = 1}^{n} σ_{i^{*}, j}^{(w) c_{w}}, {dk}_{U \to V, D_{i}})}^{t s} \\ = & \hat{e} {(\prod_{w = 1}^{n} {[H_{1} (K_{i^{*}}, i^{*} ∥ j ∥ w) \cdot \prod_{ℓ = 1}^{b} h_{M, ℓ}^{f_{i^{*}, j}^{(w, ℓ)}}]}^{{sk}_{U} c_{w}}, H_{2} {({pk}_{V}, H_{M}, D_{i})}^{{sk}_{V} / {sk}_{U}})}^{t s} \\ = & \hat{e} {(\prod_{w = 1}^{n} H_{1} {(K_{i^{*}}, i^{*} ∥ j ∥ w)}^{s c_{w}} \cdot \prod_{ℓ = 1}^{b} h_{M, ℓ}^{s \sum_{w = 1}^{n} c_{w} f_{i^{*}, j}^{(w, ℓ)}}, H_{2} {({pk}_{V}, H_{M}, D_{i})}^{t})}^{{sk}_{V}} \\ = & \hat{e} {(\prod_{w = 1}^{n} H_{1} {(K_{i^{*}}, i^{*} ∥ j ∥ w)}^{s c_{w}} \cdot \prod_{ℓ = 1}^{b} V_{ℓ}, V^{″})}^{{sk}_{V}} . \end{array}$

$\hat{e} (V_{ℓ}, g) = \hat{e} (C_{ℓ}^{'}, V_{ℓ}^{'})$ by (2) and (3): $\begin{array}{rcl} \hat{e} (V_{ℓ}, g) & = & \hat{e} (C_{ℓ}^{' \sum_{w = 1}^{n} c_{w} f_{i^{*}, j}^{(w, ℓ)}}, g) \\ = & \hat{e} (C_{ℓ}^{'}, g^{\sum_{w = 1}^{n} c_{w} f_{i^{*}, j}^{(w, ℓ)}}) \\ = & \hat{e} (C_{ℓ}^{'}, V_{ℓ}^{'}) . \end{array}$

$\hat{e} (V^{″}, C^{″}) = \hat{e} (H_{2} ({pk}_{V}, H_{M}, D_{i}), V^{‴})$ by (4) and (5): $\begin{array}{rcl} \hat{e} (V^{″}, C^{″}) & = & \hat{e} (H_{2} {({pk}_{V}, H_{M}, D_{i})}^{t}, C^{″}) \\ = & \hat{e} (H_{2} ({pk}_{V}, H_{M}, D_{i}), C^{'' t}) \\ = & \hat{e} (H_{2} ({pk}_{V}, H_{M}, D_{i}), V^{‴}) . \end{array}$

5.1.2. Performance

The performance of the construction is analyzed in three aspects: the computation cost of each algorithm, the storage cost of each party, and the communication cost of each phase. The computation cost is measured by the numbers of addition in

Z_{q}

(Add), multiplication in

G

(Mul), scalar exponentiation in

G

(Exp), cryptographic hash (Hash) and bilinear map (Pairing). Table 2 shows the computation cost of each algorithm. A verifier can choose binary coefficients

c_{w} \in_{R} {0, 1}

to reduce the computation cost of multiplication and scalar exponentiation. In algorithm

GenProof

, it does not need to do scalar exponentiation on

σ_{i, j}^{(w)}

for

σ_{i, j}^{(w) c_{w}}

and multiplication on

f_{i, j}^{(w, ℓ)}

for

c_{w} f_{i, j}^{(w, ℓ)}

. Thus, it reduces n multiplications in

G

and n scalar exponentiations in

G

for

GenProof

. In algorithm

VrfyProof

, it does not need to do scalar exponentiation on

H_{1} (K_{i}, i ∥ j ∥ w)

for

H_{1} {(K_{i}, i ∥ j ∥ w)}^{c_{w}}

. Thus, it reduces n scalar exponentiations in

G

for

VrfyProof

Table 2
Computation cost

Algorithm	Add	Mul	Exp	Hash	Pairing
KeyGen	0	0	1	0	0
TagGen	0	$n b$	$n b + n$	$n + l - 1$	0
GenKT	0	0	1	1	0
GenDK	0	0	1	1	2
VrfyDK	0	0	0	1	2
GenChal	0	0	$b + 1$	1	0
GenProof	$n b - b$	$n b + n + 2 b - 3$	$n + 2 b + 3$	2	3
ForgeProof	$n b - b$	$2 n b + n + 2 b - 3$	$n b + n + 2 b + 3$	$n + 2$	3
VrfyProof	0	$n + b - 1$	$n + 3$	$n + 1$	5

Notes: n is the number of integrity tags; b is the number of data identifiers; l is the number of categories.

Table 3 shows the storage cost of each party. User

U

stores his secret-public key pair

({sk}_{U}, {pk}_{U})

, data identifiers

H_{M}

, root key

K_{M}

, and key tokens

{{kt}_{V, D_{i}}}

. Delegated verifier

V

stores his secret-public key pair

({sk}_{V}, {pk}_{V})

H_{M}

and category key

K_{i}

. Storage server

S

stores data M, integrity tags Σ,

H_{M}

K_{M}

, and delegation keys

{{dk}_{U \to V, D_{i}}}

. Table 4 shows the communication cost of each phase. In the setup phase,

U

uploads

(M, Σ, H_{M}, K_{M})

S

. In the delegation phase,

V

gives

U

his key token

{kt}_{V, D_{i}}

U

gives the delegation key

{dk}_{U \to V, D_{i}}

S

U

also gives

(H_{M}, K_{i})

V

. In the integrity check phase,

V

gives

S

challenge

{chal}_{i, j}

S

gives

V

integrity proof

{pf}_{{chal}_{i, j}, V}

. To reduce the communication cost of transmitting

{chal}_{i, j}

, a verifier can choose a random seed c of size

ℓ^{'}

and send c to

S

S

can compute coefficients

c_{w} = H (c, w)

, where

1 ⩽ w ⩽ n

. Thus, it reduces

n k - ℓ^{'} bits

of communication cost in the integrity check phase.

Table 3

Storage cost

Party	Bits
User	$k + (b + v + 1) p + ℓ$
Delegated	$k + (b + 1) p + ℓ$
Verifier	$k + (b + 1) p + ℓ$
Storage server	$n b k + (n + b + v) p + ℓ$

Notes: k is the security parameter; p is the size of an element in $G$ ; ℓ is the size of an element in $K$ ; n is the number of integrity tags; b is the number of data identifiers; v is the number of delegated verifiers.

Table 4

Communication cost

Phase	Bits
Setup	$U \to S : n b k + (n + b) p + ℓ$
Delegation	$V \leftrightarrow U : (b + 1) p + ℓ$
Delegation	$U \to S : p$
Integrity check	$V \leftrightarrow S : n k + (3 b + 3) p + p_{T}$

Notes: k is the security parameter; p is the size of an element in $G$ ; $p_{T}$ is the size of an element in $G_{T}$ ; ℓ is the size of an element in $K$ ; n is the number of integrity tags; b is the number of data identifiers.

To measure the performance of the delegated PDP scheme, we provide simulations for different data size. The small data size is 10 MB, the medium data size is 100 MB, and the large data size is 1000 MB. We choose system parameter

k = 512

. Let

n^{'}

be the number of k-bit data blocks and b be the number of data identifiers. We choose

b \approx \sqrt{n^{'} / 4}

b \approx \sqrt{n^{'} / 8}

and

b \approx \sqrt{n^{'} / 16}

, respectively. We use the GNU multiple precision (GMP) arithmetic library of version 6.0.0a and the pairing-based cryptography (PBC) library of version 0.5.14 to implement the scheme. We use an AMD Opteron 6128 processor with 32 GB RAM to perform the simulations, but only one core is used in the same time. We perform each simulation for 10 times and take the average of the results. Table 5 provides the simulation results. In the setup phase, a user (algorithm TagGen) takes about 4.5 hours to generate integrity tags for data of 1000 MB. The computation in the delegation phase is lightweight. A delegation process (algorithm GenKT, algorithm GenDK and algorithm VrfyDK) can be completed in 100 ms. The computation in the integrity check phase is efficient. A verifier (algorithm GenChal and algorithm VrfyProof) takes no more than 40 s to check data of 1000 MB. A storage server (algorithm GenProof) takes less than one minute to generate an integrity proof for data of 1000 MB.

Table 5

Simulation result of the delegated PDP scheme

Data size (MB)	b	TagGen (s)	GenKT (ms)	GenDK (ms)	VrfyDK (ms)	GenChal (s)	GenProof (s)	VrfyProof (s)
10	102	174.184	11.329	26.556	19.487	0.883	1.694	1.512
10	144	175.400	23.192	37.301	21.291	1.206	1.981	1.640
10	202	177.920	11.316	26.066	17.682	1.681	2.491	1.967
100	320	1670.304	18.896	38.105	31.266	2.678	7.926	4.636
100	452	1660.652	14.095	35.599	28.221	3.789	8.591	5.098
100	640	1663.375	15.712	30.300	26.676	5.314	10.073	6.155
1000	1012	16,279.388	21.920	41.029	25.993	8.472	50.261	14.628
1000	1432	16,250.004	14.113	32.773	28.116	11.968	53.622	15.969
1000	2024	16,237.705	12.841	34.462	27.697	16.913	58.967	19.363

Notes: Security parameter $k = 512$ ; b is the number of data identifiers.

The number b of data identifiers affects the efficiency of the integrity check phase. If b is small, there will be too many integrity tags. Thus, computing the hash values of tag indexes will be a heavy duty. The user has to compute more hash values to generate integrity tags. The verifier has to compute more hash values to verify an integrity proof. If b is large, there will be too many data identifiers. Thus, the computation in the integrity check process will be inefficient. The verifier has to do more scalar exponentiations to generate an integrity challenge. The storage server has to do more scalar exponentiations to generate an integrity proof. The verifier has to do more bilinear maps to verify the integrity proof. We suggest that a user choose $b = Θ (\sqrt{n^{'}})$ to balance the effect of the two extreme cases. From the simulation results, the integrity check phase is more efficient when choosing $b \approx \sqrt{n^{'} / 16}$ instead of choosing $b \approx \sqrt{n^{'} / 4}$ .

5.2. Security analysis

The delegated PDP scheme satisfies the requirements of proof unforgeability, proof indistinguishability and delegation key unforgeability.

5.2.1. Proof unforgeability

The delegated PDP scheme is proof unforgeable under the truncated 1-BDHE assumption and the KEA1 in the random oracle model.

Theorem 1.
Let $O_{H_{1}}$ and $O_{H_{2}}$ be the random oracles for hash functions $H_{1}$ and $H_{2}$ . An adversary can issue at most $q_{1}$ queries to $O_{H_{1}}$ , $q_{2}$ queries to $O_{H_{2}}$ , $q_{T}$ queries to $O_{Tag}$ , and $q_{K}$ queries to $O_{DK}$ . Let $t_{1}$ , $t_{2}$ , $t_{T}$ and $t_{K}$ be the time taken by $O_{H_{1}}$ , $O_{H_{2}}$ , $O_{Tag}$ and $O_{DK}$ to respond an oracle query. The KEA1 extractor $\overline{A}$ takes time $t_{\overline{A}}$ to extract an exponent. Let k be the security parameter, b be the number of data identifiers, l be the number of categories, and $K$ be a large space of hierarchical keys such that $| K | ⩾ 2 (l q_{1} + l^{2} q_{T})$ . If the truncated BDHE problem is $(t, ϵ, 1)$ -secure, the delegated PDP scheme is $(t - q_{1} t_{1} - q_{2} t_{2} - 2 q_{T} t_{T} - q_{K} t_{K} - (b + 1) t_{\overline{A}}, \frac{2^{k - 2}}{2^{k - 2} - 1} ϵ)$ -proof unforgeable in the random oracle model.
Proof.
Let $A$ be a probabilistic black-box adversary who wins the proof unforgeability game ${Game}^{PF - UF}$ with advantage $ϵ^{'}$ in time $t^{'}$ . An algorithm $B$ that uses $A$ to solve the truncated 1-BDHE problem is constructed as follows:

Setup. Given an instance $(g, g^{α}, g^{'})$ of the truncated 1-BDHE problem, $B$ chooses the public parameter $π = (q, G, g, G_{T}, g_{T}, \hat{e}, K, d, H_{1}, H_{2}, H_{3}, H_{4})$ . $B$ chooses user $U$ ’s key pair $({sk}_{U}, {pk}_{U}) = (α u, g^{α u})$ and verifier $V$ ’s key pair $({sk}_{V}, {pk}_{V}) = (α v, g^{α v})$ , where $u, v \in_{R} Z_{q}$ . Then, $B$ invokes $A$ as a subroutine: $A^{O_{H_{1}}, O_{H_{2}}, O_{Tag}, O_{DK}} (π, {pk}_{U}, {pk}_{V})$ .

Query. $A$ can query oracles $O_{H_{1}}$ , $O_{H_{2}}$ , $O_{Tag}$ and $O_{DK}$ during his execution. $B$ handles these oracles as follows:
$O_{H_{1}}$ : $B$ maintains a table $T_{H_{1}} = {(K, x, H_{1} (K, x), r)}$ to record the $O_{H_{1}}$ -queries. $B$ takes $K \in K$ and $x \in {0, 1}^{}$ as inputs. If record $(K, x, y, )$ exists in $T_{H_{1}}$ , $B$ outputs $H_{1} (K, x) = y$ . Otherwise, $B$ outputs $H_{1} (K, x) = g^{r}$ and inserts $(K, x, g^{r}, r)$ into $T_{H_{1}}$ , where $r \in_{R} Z_{q}$ .

$O_{H_{2}}$ : $B$ maintains a table $T_{H_{2}} = {(h, h^{'}, x, H_{2} (h, h^{'}, x), r)}$ to record the $O_{H_{2}}$ -queries. $B$ takes $h, h^{'} \in G$ and $x \in {0, 1}^{}$ as inputs. If record $(h, h^{'}, x, y, )$ exists in $T_{H_{2}}$ , $B$ outputs $H_{2} (h, h^{'}, x) = y$ . Otherwise, $B$ outputs $H_{2} (h, h^{'}, x) = g^{α r}$ and inserts $(h, h^{'}, x, g^{α r}, r)$ into $T_{H_{2}}$ , where $r \in_{R} Z_{q}$ .

$O_{Tag}$ : $B$ maintains a table $T_{Tag} = {(M, H_{M}, R, K_{M}, Σ)}$ to record the $O_{Tag}$ -queries. $B$ takes hierarchical data M as the input. Then, $B$ chooses $R = (r_{1}, r_{2}, \dots, r_{b}) \in_{R} {(Z_{q})}^{b}$ and computes data identifiers $H_{M} = (h_{M, 1}, h_{M, 2}, \dots, h_{M, b}) = (g^{' r_{1}}, g^{' r_{2}}, \dots, g^{' r_{b}})$ . $B$ chooses root key $K_{M} = K_{0} \in_{R} K$ for root category $D_{0}$ and derives key $K_{i}$ for category $D_{i}$ recursively. If any index $(K_{i}, i ∥ j ∥ w)$ has been queried to $O_{H_{1}}$ before, $B$ re-chooses $K_{0}$ . That is, $B$ chooses $K_{0}$ such that ${(K_{i}, i ∥ j ∥ w, , )} \cap T_{H_{1}} = ϕ$ . For each tag $σ_{i, j}^{(w)}$ , $B$ inserts $(K_{i}, i ∥ j ∥ w, g^{r_{i, j}^{(w)}} / \prod_{ℓ = 1}^{b} h_{M, ℓ}^{f_{i, j}^{(w, ℓ)}}, r_{i, j}^{(w)})$ into $T_{H_{1}}$ , where $r_{i, j}^{(w)} \in_{R} Z_{q}$ . Then, $B$ computes each $σ_{i, j}^{(w)}$ as follows: $\begin{array}{rcl} σ_{i, j}^{(w)} & = & {[H_{1} (K_{i}, i ∥ j ∥ w) \cdot \prod_{ℓ = 1}^{b} h_{M, ℓ}^{f_{i, j}^{(w, ℓ)}}]}^{{sk}_{U}} \\ = & {[(g^{r_{i, j}^{(w)}} / \prod_{ℓ = 1}^{b} h_{M, ℓ}^{f_{i, j}^{(w, ℓ)}}) \cdot \prod_{ℓ = 1}^{b} h_{M, ℓ}^{f_{i, j}^{(w, ℓ)}}]}^{α u} \\ = & g^{α u r_{i, j}^{(w)}} . \end{array}$ $B$ outputs $(H_{M}, K_{M}, Σ)$ and inserts $(M, H_{M}, R, K_{M}, Σ)$ into $T_{Tag}$ , where $Σ = {σ_{i, j}^{(w)}}$ .

$O_{DK}$ : $B$ takes data identifiers $H_{M}$ , category $D_{i}$ , public key ${pk}_{W}$ and key token ${kt}_{W, D_{i}}$ as inputs. Then, $B$ checks whether $({pk}_{W}, H_{M}, D_{i}, , ) \in T_{H_{2}}$ and $\hat{e} (g, {kt}_{W, D_{i}}) = \hat{e} ({pk}_{W}, H_{2} ({pk}_{W}, H_{M}, D_{i}))$ . If not, $B$ rejects this $O_{DK}$ -query. Otherwise, $B$ has $({pk}_{W}, H_{M}, D_{i}, g^{α r}, r) \in T_{H_{2}}$ and outputs delegation key ${dk}_{U \to W, D_{i}}$ as follows: $\begin{array}{rcl} {dk}_{U \to W, D_{i}} & = & {kt}_{W, D_{i}}^{1 / {sk}_{U}} \\ = & H_{2} {({pk}_{W}, H_{M}, D_{i})}^{{sk}_{W} / {sk}_{U}} \\ = & {(g^{α r})}^{{sk}_{W} / α u} \\ = & {pk}_{W}^{r / u} . \end{array}$

Challenge. $A$ indicates which $O_{Tag}$ -query is the target and which file is going to be challenged. The target is denoted as $(M^{}, H_{M^{}}, R^{}, K_{M^{}} = K_{0}^{}, Σ^{})$ , and the file is denoted as $F_{i, j}^{} = [\begin{matrix} f_{i, j}^{ (1, 1)} & f_{i, j}^{* (1, 2)} & \dots & f_{i, j}^{* (1, b)} \\ f_{i, j}^{* (2, 1)} & f_{i, j}^{* (2, 2)} & \dots & f_{i, j}^{* (2, b)} \\ ⋮ & ⋮ & ⋱ & ⋮ \\ f_{i, j}^{* (n, 1)} & f_{i, j}^{* (n, 2)} & \dots & f_{i, j}^{* (n, b)} \end{matrix}] .$ Let $D_{i}^{}$ be the category, $K_{i}^{}$ be the key, and ${(K_{i}^{}, i ∥ j ∥ w, g^{r_{i, j}^{ (w)}} / \prod_{ℓ = 1}^{b} h_{M^{}, ℓ}^{f_{i, j}^{ (w, ℓ)}}, r_{i, j}^{* (w)})}$ be the records of $O_{H_{1}}$ -queries. $A$ modifies $F_{i, j}^{} = {[f_{i, j}^{ (w, ℓ)}]}_{1 ⩽ w ⩽ n, 1 ⩽ ℓ ⩽ b}$ to $F_{i, j}^{'} = {[f_{i, j}^{' (w, ℓ)}]}_{1 ⩽ w ⩽ n, 1 ⩽ ℓ ⩽ b}$ such that at least one $f_{i, j}^{' (w, ℓ)} \neq f_{i, j}^{* (w, ℓ)}$ . $B$ checks whether $({pk}_{V}, H_{M^{}}, D_{i}^{}, , ) \in T_{H_{2}}$ . If not, $B$ inserts $({pk}_{V}, H_{M^{}}, D_{i}^{}, g^{α v^{'}}, v^{'})$ into $T_{H_{2}}$ , where $v^{'} \in_{R} Z_{q}$ . Otherwise, $B$ has $({pk}_{V}, H_{M^{}}, D_{i}^{}, g^{α v^{'}}, v^{'}) \in T_{H_{2}}$ . $B$ computes delegation key ${dk}_{U \to V, D_{i}^{}}$ as follows: $\begin{array}{rcl} {dk}_{U \to V, D_{i}^{}} & = & H_{2} {({pk}_{V}, H_{M^{}}, D_{i}^{})}^{{sk}_{V} / {sk}_{U}} \\ = & {(g^{α v^{'}})}^{α v / α u} \\ = & g^{α v v^{'} / u} . \end{array}$ Then, $B$ chooses $c_{1}, c_{2}, \dots, c_{n}, s \in_{R} Z_{q}$ and computes challenge ${chal}_{i, j} = (C, C_{1}^{'}, C_{2}^{'}, \dots, C_{b}^{'}, C^{″})$ as follows: $\begin{array}{rcl} C = (c_{1}, c_{2}, \dots, c_{n}), \\ C_{ℓ}^{'} = h_{M^{}, ℓ}^{s}, 1 ⩽ ℓ ⩽ b, \\ C^{″} = H_{3} {(C)}^{s} . \end{array}$ $B$ provides ${dk}_{U \to V, D_{i}^{}}$ and ${chal}_{i, j}$ to $A$ .

Answer. $A$ returns proof ${pf}_{{chal}_{i, j}, V} = (ρ, V_{1}, V_{2}, \dots, V_{b}, V_{1}^{'}, V_{2}^{'}, \dots, V_{b}^{'}, V^{″}, V^{‴})$ . If ${pf}_{{chal}_{i, j}, V}$ passes the verification, $B$ has $\begin{array}{rclr} ρ^{s} = \hat{e} {(\prod_{w = 1}^{n} H_{1} {(K_{i}^{}, i ∥ j ∥ w)}^{s c_{w}} \cdot \prod_{ℓ = 1}^{b} V_{ℓ}, V^{″})}^{{sk}_{V}}, & (6) \\ \hat{e} (V_{ℓ}, g) = \hat{e} (h_{M^{}, ℓ}^{s}, V_{ℓ}^{'}), 1 ⩽ ℓ ⩽ b, & (7) \\ \hat{e} (V^{″}, H_{3} {(C)}^{s}) = \hat{e} (H_{2} ({pk}_{V}, H_{M^{}}, D_{i}^{}), V^{‴}) . & (8) \end{array}$

$B$ can compute $\hat{e} {(g, g^{'})}^{α^{2}}$ as follows:
Because (7) holds, $B$ has that $h_{M^{}, ℓ}^{s} = g^{Δ_{ℓ}}$ and $V_{ℓ} = V_{ℓ}^{' Δ_{ℓ}}$ for some $Δ_{ℓ} \in_{R} Z_{q}$ , where $1 ⩽ ℓ ⩽ b$ . Thus, $B$ can use the KEA1 extractor $\overline{A}$ to extract $\sum_{w = 1}^{n} c_{w} f_{i, j}^{' (w, ℓ)} = \overline{A} (g, h_{M^{}, ℓ}^{s}, A)$ such that $V_{ℓ} = {(h_{M^{}, ℓ}^{s})}^{\sum_{w = 1}^{n} c_{w} f_{i, j}^{' (w, ℓ)}}$ and $V_{ℓ}^{'} = g^{\sum_{w = 1}^{n} c_{w} f_{i, j}^{' (w, ℓ)}}$ . $B$ has that $\prod_{ℓ = 1}^{b} {(h_{M^{}, ℓ}^{s})}^{\sum_{w = 1}^{n} c_{w} f_{i, j}^{' (w, ℓ)}} \neq \prod_{ℓ = 1}^{b} {(h_{M^{}, ℓ}^{s})}^{\sum_{w = 1}^{n} c_{w} f_{i, j}^{ (w, ℓ)}}$ except for a negligible probability. That is, $\begin{array}{rcl} Pr [\prod_{ℓ = 1}^{b} {(h_{M^{}, ℓ}^{s})}^{\sum_{w = 1}^{n} c_{w} f_{i, j}^{' (w, ℓ)}} = \prod_{ℓ = 1}^{b} {(h_{M^{}, ℓ}^{s})}^{\sum_{w = 1}^{n} c_{w} f_{i, j}^{* (w, ℓ)}} : \exists (w^{'}, ℓ^{'}), f_{i, j}^{' (w^{'}, ℓ^{'})} \neq f_{i, j}^{* (w^{'}, ℓ^{'})}] \\ = Pr [c_{w^{'}} = 0 \cap \prod_{ℓ = 1}^{b} {(h_{M^{}, ℓ}^{s})}^{\sum_{w = 1}^{n} c_{w} f_{i, j}^{' (w, ℓ)}} = \prod_{ℓ = 1}^{b} {(h_{M^{}, ℓ}^{s})}^{\sum_{w = 1}^{n} c_{w} f_{i, j}^{* (w, ℓ)}} : c_{w} \in_{R} Z_{q}] \\ + Pr [c_{w^{'}} \neq 0 \cap \prod_{ℓ = 1}^{b} {(h_{M^{}, ℓ}^{s})}^{\sum_{w = 1}^{n} c_{w} f_{i, j}^{' (w, ℓ)}} = \prod_{ℓ = 1}^{b} {(h_{M^{}, ℓ}^{s})}^{\sum_{w = 1}^{n} c_{w} f_{i, j}^{* (w, ℓ)}} : c_{w} \in_{R} Z_{q}] \\ ⩽ \frac{2}{q} . \end{array}$ Otherwise, $A$ has the knowledge of $F_{i, j}^{} = [f_{i, j}^{ (w, ℓ)}]$ .1
¹
$B$ can extract $F_{i, j}^{} = {[f_{i, j}^{ (w, ℓ)}]}_{1 ⩽ w ⩽ n, 1 ⩽ ℓ ⩽ b}$ by choosing n linearly independent coefficient vectors ${C_{z}}_{1 ⩽ z ⩽ n} = {(c_{z, 1}, c_{z, 2}, \dots, c_{z, n})}_{1 ⩽ z ⩽ n}$ adaptively until collecting n valid proofs ${{pf}_{{chal}_{i, j}, V}^{(z)}}_{1 ⩽ z ⩽ n} = {{(ρ^{(z)}, V_{1}^{(z)}, V_{2}^{(z)}, \dots, V_{b}^{(z)}, V_{1}^{' (z)}, V_{2}^{' (z)}, \dots, V_{b}^{' (z)}, V^{'' (z)}, V^{''' (z)})}}_{1 ⩽ z ⩽ n}$ from $A$ . Let $C = {[c_{z, w}]}_{1 ⩽ z ⩽ n, 1 ⩽ w ⩽ n}$ be the $n \times n$ invertible matrix formed by ${C_{z}}_{1 ⩽ z ⩽ n}$ . For each $ℓ \in {1, 2, \dots, b}$ , $B$ has that $C \cdot X_{ℓ} = Y_{ℓ}$ , where $X_{ℓ} = {[f_{i, j}^{* (1, ℓ)} f_{i, j}^{* (2, ℓ)} \dots f_{i, j}^{* (n, ℓ)}]}^{T}$ and $Y_{ℓ} = {[\sum_{w = 1}^{n} c_{1, w} f_{i, j}^{* (w, ℓ)} \sum_{w = 1}^{n} c_{2, w} f_{i, j}^{* (w, ℓ)} \dots \sum_{w = 1}^{n} c_{n, w} f_{i, j}^{* (w, ℓ)}]}^{T}$ . $B$ uses the KEA1 extractor $\overline{A}$ to extract $Y_{ℓ}$ , where $\sum_{w = 1}^{n} c_{z, w} f_{i, j}^{* (w, ℓ)} = \overline{A} (g, C_{ℓ}^{' (z)}, V_{ℓ}^{' (z)}, V_{ℓ}^{(z)})$ . Then, $B$ solves the system of linear equations to obtain $X_{ℓ}$ . Finally, $B$ extracts $F_{i, j}^{} = [X_{1} X_{2} \dots X_{b}]$ .

Because (8) holds, $B$ has that $H_{3} {(C)}^{s} = H_{2} {({pk}_{V}, H_{M^{}}, D_{i}^{})}^{Δ}$ and $V^{‴} = V^{'' Δ}$ for some $Δ \in_{R} Z_{q}$ . Thus, $B$ can use the KEA1 extractor $\overline{A}$ to extract $t = \overline{A} (H_{2} ({pk}_{V}, H_{M^{}}, D_{i}^{}), H_{3} {(C)}^{s}, A)$ such that $V^{″} = H_{2} {({pk}_{V}, H_{M^{}}, D_{i}^{})}^{t}$ and $V^{‴} = H_{3} {(C)}^{s t}$ .

Because (6) and $\prod_{ℓ = 1}^{b} {(h_{M^{}, ℓ}^{s})}^{\sum_{w = 1}^{n} c_{w} f_{i, j}^{' (w, ℓ)}} \neq \prod_{ℓ = 1}^{b} {(h_{M^{}, ℓ}^{s})}^{\sum_{w = 1}^{n} c_{w} f_{i, j}^{ (w, ℓ)}}$ hold, $B$ can compute $\hat{e} {(g, g^{'})}^{α^{2}}$ as follows: $\begin{array}{rcl} ρ^{s} = \hat{e} {(\prod_{w = 1}^{n} H_{1} {(K_{i}^{}, i ∥ j ∥ w)}^{s c_{w}} \cdot \prod_{ℓ = 1}^{b} V_{ℓ}, V^{″})}^{{sk}_{V}} \\ \Rightarrow ρ^{s} = \hat{e} {(\prod_{w = 1}^{n} {(g^{r_{i, j}^{ (w)}} / \prod_{ℓ = 1}^{b} h_{M^{}, ℓ}^{f_{i, j}^{ (w, ℓ)}})}^{s c_{w}} \cdot \prod_{ℓ = 1}^{b} h_{M^{}, ℓ}^{s \sum_{w = 1}^{n} c_{w} f_{i, j}^{' (w, ℓ)}}, H_{2} {({pk}_{V}, H_{M^{}}, D_{i}^{})}^{t})}^{α v} \\ \Rightarrow ρ = \hat{e} {(g^{\sum_{w = 1}^{n} c_{w} r_{i, j}^{ (w)}} / \prod_{ℓ = 1}^{b} g^{' r_{ℓ}^{} \sum_{w = 1}^{n} c_{w} f_{i, j}^{ (w, ℓ)}} \cdot \prod_{ℓ = 1}^{b} g^{' r_{ℓ}^{} \sum_{w = 1}^{n} c_{w} f_{i, j}^{' (w, ℓ)}}, g^{α v^{'} t})}^{α v} \\ \Rightarrow ρ = \hat{e} {(g^{\sum_{w = 1}^{n} c_{w} r_{i, j}^{ (w)}} \cdot g^{' \sum_{ℓ = 1}^{b} r_{ℓ}^{} (\sum_{w = 1}^{n} c_{w} f_{i, j}^{' (w, ℓ)} - \sum_{w = 1}^{n} c_{w} f_{i, j}^{ (w, ℓ)})}, g^{α v^{'} t})}^{α v} \\ \Rightarrow ρ = \hat{e} {(g^{α v}, g^{α v^{'} t})}^{\sum_{w = 1}^{n} c_{w} r_{i, j}^{* (w)}} \cdot \hat{e} {(g^{' α v}, g^{α v^{'} t})}^{\sum_{ℓ = 1}^{b} r_{ℓ}^{} (\sum_{w = 1}^{n} c_{w} f_{i, j}^{' (w, ℓ)} - \sum_{w = 1}^{n} c_{w} f_{i, j}^{ (w, ℓ)})} \\ \Rightarrow \hat{e} {(g^{' α}, g^{α})}^{v v^{'} t \sum_{ℓ = 1}^{b} r_{ℓ}^{} (\sum_{w = 1}^{n} c_{w} f_{i, j}^{' (w, ℓ)} - \sum_{w = 1}^{n} c_{w} f_{i, j}^{ (w, ℓ)})} = \frac{ρ}{\hat{e} {(g^{α}, g^{α})}^{v v^{'} t \sum_{w = 1}^{n} c_{w} r_{i, j}^{* (w)}}} \\ \Rightarrow \hat{e} {(g, g^{'})}^{α^{2}} = {(\frac{ρ}{\hat{e} {(g^{α}, g^{α})}^{v v^{'} t \sum_{w = 1}^{n} c_{w} r_{i, j}^{* (w)}}})}^{1 / (v v^{'} t \sum_{ℓ = 1}^{b} r_{ℓ}^{} (\sum_{w = 1}^{n} c_{w} f_{i, j}^{' (w, ℓ)} - \sum_{w = 1}^{n} c_{w} f_{i, j}^{ (w, ℓ)}))} . \end{array}$

In the above reduction, $B$ loses a negligible portion of ${Adv}_{A}^{PF - UF}$ when $\prod_{ℓ = 1}^{b} {(h_{M^{}, ℓ}^{s})}^{\sum_{w = 1}^{n} c_{w} f_{i, j}^{' (w, ℓ)}} = \prod_{ℓ = 1}^{b} {(h_{M^{}, ℓ}^{s})}^{\sum_{w = 1}^{n} c_{w} f_{i, j}^{* (w, ℓ)}}$ . Therefore, the reduced advantage is $ϵ = (1 - \frac{2}{q}) ϵ^{'} ⩾ (1 - \frac{1}{2^{k - 2}}) ϵ^{'}$ . $B$ handles $O_{H_{1}}$ , $O_{H_{2}}$ , $O_{Tag}$ and $O_{DK}$ . To respond an $O_{Tag}$ -query, $B$ chooses $K_{M} = K_{0} \in_{R} K$ such that ${(K_{i}, i ∥ j ∥ w, , )} \cap T_{H_{1}} = ϕ$ . $B$ can choose such $K_{0}$ with probability greater than half: $\begin{array}{rcl} Pr [{(K_{i}, i ∥ j ∥ w, , )} \cap T_{H_{1}} = ϕ : K_{0} \in_{R} K] \\ ⩾ Pr [{(K_{i}, , , *)} \cap T_{H_{1}} = ϕ : K_{0} \in_{R} K] \\ = {(1 - \frac{| T_{H_{1}} |}{| K |})}^{l} \\ ⩾ 1 - \frac{l | T_{H_{1}} |}{| K |} by Bernoulli’s inequality \\ = 1 - \frac{l (q_{1} + l q_{T})}{| K |} \\ ⩾ \frac{1}{2} by | K | ⩾ 2 (l q_{1} + l^{2} q_{T}) . \end{array}$ Thus, the expected time of responding an $O_{Tag}$ -query is $2 t_{T}$ . $B$ uses the $KEA 1$ extractor $\overline{A}$ to extract $b + 1$ exponents. Therefore, the reduced time is $t = t^{'} + q_{1} t_{1} + q_{2} t_{2} + 2 q_{T} t_{T} + q_{K} t_{K} + (b + 1) t_{\overline{A}}$ . By choosing appropriate $q_{1}, q_{2}, q_{T}, q_{K}, b, l \in Poly (k)$ and $| K | ⩾ 2 (l q_{1} + l^{2} q_{T}) \in Exp (k)$ , $B$ has $1 / 2^{k - 2} \in negl (k)$ and $q_{1} t_{1} + q_{2} t_{2} + 2 q_{T} t_{T} + q_{K} t_{K} + (b + 1) t_{\overline{A}} \in Poly (k)$ . □

5.2.2. Proof indistinguishability

The delegated PDP scheme is proof indistinguishable under the truncated decisional 1-BDHE assumption in the random oracle model.

Theorem 2.
Let $O_{H_{1}}$ , $O_{H_{2}}$ and $O_{H_{3}}$ be the random oracles for hash functions $H_{1}$ , $H_{2}$ and $H_{3}$ . An adversary can issue at most $q_{1}$ queries to $O_{H_{1}}$ , $q_{2}$ queries to $O_{H_{2}}$ , $q_{3}$ queries to $O_{H_{3}}$ , $q_{K}$ queries to $O_{DK}$ , and $q_{P}$ queries to $O_{Proof}$ . Let $t_{1}$ , $t_{2}$ , $t_{3}$ , $t_{K}$ and $t_{P}$ be the time taken by $O_{H_{1}}$ , $O_{H_{2}}$ , $O_{H_{3}}$ , $O_{DK}$ and $O_{Proof}$ to respond an oracle query. If the truncated decisional BDHE problem is $(t, ϵ, 1)$ -secure, the delegated PDP scheme is $(t - q_{1} t_{1} - q_{2} t_{2} - q_{3} t_{3} - q_{K} t_{K} - q_{P} t_{P}, ϵ)$ -proof indistinguishable in the random oracle model.
Proof.
Let $A$ be a probabilistic black-box adversary who wins the proof indistinguishability game ${Game}^{PF - IND}$ with advantage $ϵ^{'}$ in time $t^{'}$ . An algorithm $B$ that uses $A$ to solve the truncated decisional 1-BDHE problem is constructed as follows:

Setup. Given an instance $(g, g^{α}, g^{'}, Z)$ of the truncated decisional 1-BDHE problem, $B$ chooses the public parameter $π = (q, G, g, G_{T}, g_{T}, \hat{e}, K, d, H_{1}, H_{2}, H_{3}, H_{4})$ . $B$ chooses user $U$ ’s key pair $({sk}_{U}, {pk}_{U}) = (u, g^{u})$ and verifier $V$ ’s key pair $({sk}_{V}, {pk}_{V}) = (Δ v, g^{' v})$ , where $u, v \in_{R} Z_{q}$ and $Δ = {log}_{g} g^{'}$ . $B$ chooses hierarchical data M. Then, $B$ chooses $R = (r_{1}, r_{2}, \dots, r_{b}) \in_{R} {(Z_{q})}^{b}$ and computes data identifiers $H_{M} = (h_{M, 1}, h_{M, 2}, \dots, h_{M, b}) = (g^{α r_{1}}, g^{α r_{2}}, \dots, g^{α r_{b}})$ . $B$ chooses root key $K_{M} = K_{0} \in_{R} K$ for root category $D_{0}$ and derives key $K_{i}$ for category $D_{i}$ recursively. For each tag $σ_{i, j}^{(w)}$ , $B$ sets $H_{1} (K_{i}, i ∥ j ∥ w) = g^{r_{i, j}^{(w)}}$ , where $r_{i, j}^{(w)} \in_{R} Z_{q}$ . Then, $B$ computes each $σ_{i, j}^{(w)}$ as follows: $\begin{array}{rcl} σ_{i, j}^{(w)} & = & {(H_{1} (K_{i}, i ∥ j ∥ w) \cdot \prod_{ℓ = 1}^{b} h_{M, ℓ}^{f_{i, j}^{(w, ℓ)}})}^{{sk}_{U}} \\ = & {(g^{r_{i, j}^{(w)}} \cdot \prod_{ℓ = 1}^{b} g^{α r_{ℓ} f_{i, j}^{(w, ℓ)}})}^{u} \\ = & {(g^{r_{i, j}^{(w)}} \cdot g^{α \sum_{ℓ = 1}^{b} r_{ℓ} f_{i, j}^{(w, ℓ)}})}^{u} . \end{array}$ $B$ sets $H_{2} ({pk}_{V}, H_{M}, D_{0}) = g^{v^{'}}$ , where $v^{'} \in_{R} Z_{q}$ . Then, $B$ computes key token ${kt}_{V, D_{0}}$ as follows: $\begin{array}{rcl} {kt}_{V, D_{0}} & = & H_{2} {({pk}_{V}, H_{M}, D_{0})}^{{sk}_{V}} \\ = & {(g^{v^{'}})}^{Δ v} \\ = & g^{' v v^{'}} . \end{array}$ $B$ computes delegation key ${dk}_{U \to V, D_{0}}$ as follows: $\begin{array}{rcl} {dk}_{U \to V, D_{0}} & = & {kt}_{V, D_{0}}^{1 / {sk}_{U}} \\ = & g^{' v v^{'} / u} . \end{array}$ Then, $B$ invokes $A$ as a subroutine: $A^{O_{H_{1}}, O_{H_{2}}, O_{H_{3}}, O_{DK}, O_{Proof}} (π, {pk}_{U}, {pk}_{V}, M, Σ, H_{M}, K_{M}, {kt}_{V, D_{0}}, {dk}_{U \to V, D_{0}})$ , where $Σ = {σ_{i, j}^{(w)}}$ .

Query-1. $A$ can query oracles $O_{H_{1}}$ , $O_{H_{2}}$ , $O_{H_{3}}$ , $O_{DK}$ and $O_{Proof}$ during his execution. $B$ handles these oracles as follows:
$O_{H_{1}}$ : $B$ maintains a table $T_{H_{1}} = {(K, x, H_{1} (K, x), r)}$ to record the $O_{H_{1}}$ -queries. $B$ takes $K \in K$ and $x \in {0, 1}^{}$ as inputs. If record $(K, x, y, )$ exists in $T_{H_{1}}$ , $B$ outputs $H_{1} (K, x) = y$ . Otherwise, $B$ outputs $H_{1} (K, x) = g^{r}$ and inserts $(K, x, g^{r}, r)$ into $T_{H_{1}}$ , where $r \in_{R} Z_{q}$ .

$O_{H_{2}}$ : $B$ maintains a table $T_{H_{2}} = {(h, h^{'}, x, H_{2} (h, h^{'}, x), r)}$ to record the $O_{H_{2}}$ -queries. $B$ takes $h, h^{'} \in G$ and $x \in {0, 1}^{}$ as inputs. If record $(h, h^{'}, x, y, )$ exists in $T_{H_{2}}$ , $B$ outputs $H_{2} (h, h^{'}, x) = y$ . Otherwise, $B$ outputs $H_{2} (h, h^{'}, x) = g^{r}$ and inserts $(h, h^{'}, x, g^{r}, r)$ into $T_{H_{2}}$ , where $r \in_{R} Z_{q}$ .

$O_{H_{3}}$ : $B$ maintains a table $T_{H_{3}} = {(C, H_{3} (C), r)}$ to record the $O_{H_{3}}$ -queries. $B$ takes $C \in {(Z_{q})}^{}$ as the input. If record $(C, y, )$ exists in $T_{H_{3}}$ , $B$ outputs $H_{3} (C) = y$ . Otherwise, $B$ outputs $H_{3} (C) = g^{r}$ and inserts $(C, g^{r}, r)$ into $T_{H_{3}}$ , where $r \in_{R} Z_{q}$ .

$O_{DK}$ : $B$ takes data identifiers $H_{M}$ , category $D_{i}$ , public key ${pk}_{W}$ and key token ${kt}_{W, D_{i}}$ as inputs. Then, $B$ checks whether $({pk}_{W}, H_{M}, D_{i}, , ) \in T_{H_{2}}$ and $\hat{e} (g, {kt}_{W, D_{i}}) = \hat{e} ({pk}_{W}, H_{2} ({pk}_{W}, H_{M}, D_{i}))$ . If not, $B$ rejects this $O_{DK}$ -query. Otherwise, $B$ outputs delegation key ${dk}_{U \to W, D_{i}}$ as follows: $\begin{array}{rcl} {dk}_{U \to W, D_{i}} & = & {kt}_{W, D_{i}}^{1 / {sk}_{U}} \\ = & {kt}_{W, D_{i}}^{1 / u} . \end{array}$

$O_{Proof}$ : $B$ takes challenge ${chal}_{i, j} = (C, C_{1}^{'}, C_{2}^{'}, \dots, C_{b}^{'}, C^{″})$ as the input, where $C = (c_{1}, c_{2}, \dots, c_{n})$ . Then, $B$ checks whether $\hat{e} (\prod_{ℓ = 1}^{b} C_{ℓ}^{'}, H_{3} (C)) = \hat{e} (\prod_{ℓ = 1}^{b} h_{M, ℓ}, C^{″})$ . If not, $B$ rejects this $O_{Proof}$ -query. Otherwise, $B$ chooses $t \in_{R} Z_{q}$ and outputs valid proof ${pf}_{{chal}_{i, j}, V} = (ρ, V_{1}, V_{2}, \dots, V_{b}, V_{1}^{'}, V_{2}^{'}, \dots, V_{b}^{'}, V^{″}, V^{‴})$ as below: $\begin{array}{rcl} ρ = \hat{e} {(\prod_{w = 1}^{n} σ_{i, j}^{(w) c_{w}}, {dk}_{U \to V, D_{0}})}^{t}, \\ V_{ℓ} = C_{ℓ}^{' \sum_{w = 1}^{n} c_{w} f_{i, j}^{(w, ℓ)}}, 1 ⩽ ℓ ⩽ b, \\ V_{ℓ}^{'} = g^{\sum_{w = 1}^{n} c_{w} f_{i, j}^{(w, ℓ)}}, 1 ⩽ ℓ ⩽ b, \\ V^{″} = H_{2} {({pk}_{V}, H_{M}, D_{0})}^{t}, \\ V^{‴} = C^{'' t} . \end{array}$

Challenge. $B$ takes challenge ${chal}_{i, j}^{} = (C, C_{1}^{'}, C_{2}^{'}, \dots, C_{b}^{'}, C^{″})$ as the input, where $C = (c_{1}, c_{2}, \dots, c_{n})$ . Then, $B$ checks whether $\hat{e} (\prod_{ℓ = 1}^{b} C_{ℓ}^{'}, H_{3} (C)) = \hat{e} (\prod_{ℓ = 1}^{b} h_{M, ℓ}, C^{″})$ . If not, $B$ rejects ${chal}_{i, j}^{}$ . Otherwise, $B$ has $(C, g^{r^{†}}, r^{†}) \in T_{H_{3}}$ and $C^{″} = {(\prod_{ℓ = 1}^{b} C_{ℓ}^{'})}^{r^{†} / (α \sum_{ℓ = 1}^{b} r_{ℓ})}$ . $B$ chooses $t = α$ and outputs proof ${pf}_{{chal}_{i, j}^{}, V} = (ρ, V_{1}, V_{2}, \dots, V_{b}, V_{1}^{'}, V_{2}^{'}, \dots, V_{b}^{'}, V^{″}, V^{‴})$ as follows: $\begin{array}{rcl} ρ = \hat{e} {(\prod_{w = 1}^{n} σ_{i, j}^{(w) c_{w}}, {dk}_{U \to V, D_{0}})}^{t} \\ = \hat{e} {(\prod_{w = 1}^{n} {(g^{r_{i, j}^{(w)}} \cdot g^{α \sum_{ℓ = 1}^{b} r_{ℓ} f_{i, j}^{(w, ℓ)}})}^{u c_{w}}, g^{' v v^{'} / u})}^{α} \\ = \hat{e} {(g^{\sum_{w = 1}^{n} c_{w} r_{i, j}^{(w)}} \cdot g^{α \sum_{ℓ = 1}^{b} (r_{ℓ} \sum_{w = 1}^{n} c_{w} f_{i, j}^{(w, ℓ)})}, g^{' v v^{'}})}^{α} \\ = \hat{e} {(g^{α}, g^{'})}^{v v^{'} \sum_{w = 1}^{n} c_{w} r_{i, j}^{(w)}} \cdot \hat{e} {(g, g^{'})}^{α^{2} v v^{'} \sum_{ℓ = 1}^{b} (r_{ℓ} \sum_{w = 1}^{n} c_{w} f_{i, j}^{(w, ℓ)})} \\ = \hat{e} {(g^{α}, g^{'})}^{v v^{'} \sum_{w = 1}^{n} c_{w} r_{i, j}^{(w)}} \cdot Z^{v v^{'} \sum_{ℓ = 1}^{b} (r_{ℓ} \sum_{w = 1}^{n} c_{w} f_{i, j}^{(w, ℓ)})}, \\ V_{ℓ} = C_{ℓ}^{' \sum_{w = 1}^{n} c_{w} f_{i, j}^{(w, ℓ)}}, 1 ⩽ ℓ ⩽ b, \\ V_{ℓ}^{'} = g^{\sum_{w = 1}^{n} c_{w} f_{i, j}^{(w, ℓ)}}, 1 ⩽ ℓ ⩽ b, \\ V^{″} = H_{2} {({pk}_{V}, H_{M}, D_{0})}^{α} = g^{α v^{'}}, \\ V^{‴} = C^{'' α} = {(\prod_{ℓ = 1}^{b} C_{ℓ}^{'})}^{r^{†} / \sum_{ℓ = 1}^{b} r_{ℓ}} . \end{array}$ If $Z = \hat{e} {(g, g^{'})}^{α^{2}}$ , ${pf}_{{chal}_{i, j}^{}, V}$ is valid. Otherwise, ${pf}_{{chal}_{i, j}^{}, V}$ is invalid.

Query-2. This phase is the same as the query-1 phase.

Answer. $A$ answers validity $b^{'}$ of ${pf}_{{chal}_{i, j}^{}, V}$ . $B$ uses $b^{'}$ to answer the truncated decisional 1-BDHE problem directly.

In the above reduction, $B$ can use $A$ ’s answer directly. Therefore, the reduced advantage is $ϵ = ϵ^{'}$ . $B$ handles $O_{H_{1}}$ , $O_{H_{2}}$ , $O_{H_{3}}$ , $O_{DK}$ and $O_{Proof}$ . Therefore, the reduced time is $t = t^{'} + q_{1} t_{1} + q_{2} t_{2} + q_{3} t_{3} + q_{K} t_{K} + q_{P} t_{P}$ . By choosing appropriate $q_{1}, q_{2}, q_{3}, q_{K}, q_{P} \in Poly (k)$ , $B$ has $q_{1} t_{1} + q_{2} t_{2} + q_{3} t_{3} + q_{K} t_{K} + q_{P} t_{P} \in Poly (k)$ . □

5.2.3. Delegation key unforgeability

The delegated PDP scheme is delegation key unforgeable under the InvCDH assumption in the random oracle model.

Theorem 3.
Let $O_{H_{2}}$ be the random oracle for hash function $H_{2}$ . An adversary can issue at most $q_{2}$ queries to $O_{H_{2}}$ and $q_{K}$ queries to $O_{DK}$ . Let $t_{2}$ and $t_{K}$ be the time taken by $O_{H_{2}}$ and $O_{DK}$ to respond an oracle query. Let e be the Euler’s number. If the InvCDH problem is $(t, ϵ)$ -secure, the delegated PDP scheme is $(t - q_{2} t_{2} - q_{K} t_{K}, e (q_{K} + 1) ϵ)$ -delegation key unforgeable in the random oracle model.
Proof.
Let $A$ be a probabilistic black-box adversary who wins the delegation key unforgeability game ${Game}^{DK - UF}$ with advantage $ϵ^{'}$ in time $t^{'}$ . An algorithm $B$ that uses $A$ to solve the InvCDH problem is constructed as follows:

Setup. Given an instance $(g, g^{α})$ of the InvCDH problem, $B$ chooses the public parameter $π = (q, G, g, G_{T}, g_{T}, \hat{e}, K, d, H_{1}, H_{2}, H_{3}, H_{4})$ . $B$ chooses user $U$ ’s key pair $({sk}_{U}, {pk}_{U}) = (α, g^{α})$ . Then, $B$ invokes $A$ as a subroutine: $A^{O_{H_{2}}, O_{DK}} (π, {pk}_{U})$ .

Query. $A$ can query oracles $O_{H_{2}}$ and $O_{DK}$ during his execution. $B$ chooses probability $δ = \frac{q_{K}}{q_{K} + 1}$ and handles these oracles as follows:
$O_{H_{2}}$ : $B$ maintains a table $T_{H_{2}} = {(h, h^{'}, x, H_{2} (h, h^{'}, x), r)}$ to record the $O_{H_{2}}$ -queries. $B$ takes $h, h^{'} \in G$ and $x \in {0, 1}^{}$ as inputs. If record $(h, h^{'}, x, y, )$ exists in $T_{H_{2}}$ , $B$ outputs $H_{2} (h, h^{'}, x) = y$ . Otherwise, $B$ chooses $r \in_{R} Z_{q}$ and computes $H_{2} (h, h^{'}, x)$ as follows: $H_{2} (h, h^{'}, x) = \{\begin{matrix} g^{α r} & with probability δ, \\ g^{r} & with probability 1 - δ . \end{matrix}$ $B$ outputs $H_{2} (h, h^{'}, x)$ and inserts $(h, h^{'}, x, H_{2} (h, h^{'}, x), r)$ into $T_{H_{2}}$ .

$O_{DK}$ : $B$ takes data identifiers $H_{M}$ , category $D_{i}$ , public key ${pk}_{W}$ , and key token ${kt}_{W, D_{i}}$ as inputs. Then, $B$ checks whether $({pk}_{W}, H_{M}, D_{i}, , ) \in T_{H_{2}}$ and $\hat{e} (g, {kt}_{W, D_{i}}) = \hat{e} ({pk}_{W}, H_{2} ({pk}_{W}, H_{M}, D_{i}))$ . If not, $B$ rejects this $O_{DK}$ -query. Otherwise, $B$ has $({pk}_{W}, H_{M}, D_{i}, H_{2} ({pk}_{W}, H_{M}, D_{i}), r) \in T_{H_{2}}$ . If $H_{2} ({pk}_{W}, H_{M}, D_{i}) = g^{r}$ , $B$ aborts. Otherwise, $B$ has $H_{2} ({pk}_{W}, H_{M}, D_{i}) = g^{α r}$ and outputs delegation key ${dk}_{U \to W, D_{i}}$ as follows: $\begin{array}{rcl} {dk}_{U \to W, D_{i}} & = & {kt}_{W, D_{i}}^{1 / {sk}_{U}} \\ = & H_{2} {({pk}_{W}, H_{M}, D_{i})}^{{sk}_{W} / {sk}_{U}} \\ = & {(g^{α r})}^{{sk}_{W} / α} \\ = & {pk}_{W}^{r} . \end{array}$

Answer. $A$ returns $({sk}_{W^{}}, {pk}_{W^{}}, H_{M}^{}, D_{i}^{}, {dk}_{U \to W^{}, D_{i}^{}})$ , where $({sk}_{W^{}}, {pk}_{W^{}})$ is the key pair of third party $W^{}$ . $B$ checks whether $({pk}_{W^{}}, H_{M}^{}, D_{i}^{}, , ) \in T_{H_{2}}$ and $\hat{e} ({pk}_{U}, {dk}_{U \to W^{}, D_{i}^{}}) = \hat{e} ({pk}_{W^{}}, H_{2} ({pk}_{W^{}}, H_{M}^{}, D_{i}^{}))$ . If not, $B$ rejects ${dk}_{U \to W^{}, D_{i}^{}}$ . Otherwise, $B$ has $({pk}_{W^{}}, H_{M}^{}, D_{i}^{}, H_{2} ({pk}_{W^{}}, H_{M}^{}, D_{i}^{}), r^{}) \in T_{H_{2}}$ . If $H_{2} ({pk}_{W^{}}, H_{M}^{}, D_{i}^{}) = g^{α r^{}}$ , $B$ aborts. Otherwise, $B$ has $H_{2} ({pk}_{W^{}}, H_{M}^{}, D_{i}^{}) = g^{r^{}}$ and computes $g^{1 / α}$ as follows: $\begin{array}{rcl} \hat{e} ({pk}_{U}, {dk}_{U \to W^{}, D_{i}^{}}) = \hat{e} ({pk}_{W^{}}, H_{2} ({pk}_{W^{}}, H_{M}^{}, D_{i}^{})) \\ \Rightarrow \hat{e} (g^{α}, {dk}_{U \to W^{}, D_{i}^{}}) = \hat{e} (g^{{sk}_{W^{}}}, g^{r^{}}) \\ \Rightarrow {dk}_{U \to W^{}, D_{i}^{}} = g^{{sk}_{W^{}} r^{} / α} \\ \Rightarrow g^{1 / α} = {({dk}_{U \to W^{}, D_{i}^{}})}^{1 / ({sk}_{W^{}} r^{*})} . \end{array}$

In the above reduction, $B$ does not abort with probability $δ^{q_{K}} (1 - δ)$ . When choosing $δ = \frac{q_{K}}{q_{K} + 1}$ , $B$ has $\begin{array}{rcl} δ^{q_{K}} (1 - δ) \\ = {(\frac{q_{K}}{q_{K} + 1})}^{q_{K}} (1 - \frac{q_{K}}{q_{K} + 1}) \\ = {(1 - \frac{1}{q_{K} + 1})}^{q_{K}} \frac{1}{q_{K} + 1} \\ ⩾ \frac{1}{e (q_{K} + 1)} . \end{array}$ Therefore, the reduced advantage is $ϵ = \frac{ϵ^{'}}{e (q_{K} + 1)}$ . $B$ handles $O_{H_{2}}$ and $O_{DK}$ . Therefore, the reduced time is $t = t^{'} + q_{2} t_{2} + q_{K} t_{K}$ . By choosing appropriate $q_{2}, q_{K} \in Poly (k)$ , $B$ has $e (q_{K} + 1)$ , $q_{2} t_{2} + q_{K} t_{K} \in Poly (k)$ . □

6. Delegated proofs of retrievability scheme

A delegated POR scheme for hierarchical data is provided in this section. The security of the scheme is based on the truncated (decisional) bilinear Diffie–Hellman exponent assumption, the inverse computation Diffie–Hellman assumption, and the knowledge of exponent assumption in the random oracle model.

6.1. Construction

The delegated POR scheme is based on the delegated PDP scheme in Section 5.1, but it has two major differences:

To enable data to be retrievable from integrity proofs, an integrity proof includes a linear combination of data. Storage server $S$ computes $V_{ℓ} = \sum_{w = 1}^{n} c_{w} f_{i, j}^{(w, ℓ)}$ , where $1 ⩽ ℓ ⩽ b$ . $S$ does not need to generate $V_{ℓ}^{'} = g^{\sum_{w = 1}^{n} c_{w} f_{i, j}^{(w, ℓ)}}$ , where $1 ⩽ ℓ ⩽ b$ .

To retrieve data from integrity proofs, an extraction method is provided. Verifier $V$ can extract data from the linear combinations which are included in the integrity proofs.

The complete description of the integrity check phase is provided:

$S$ verifies ${chal}_{i^{*}, j}$ by checking whether $C^{'} = H_{3} (C)$ . If ${chal}_{i^{*}, j}$ is valid, $S$ chooses $t \in_{R} Z_{q}$ and generates integrity proof ${pf}_{{chal}_{i^{*}, j}, V} = (ρ, V_{1}, V_{2}, \dots, V_{b}, V^{'}, V^{″})$ as follows: $\begin{array}{rcl} ρ = \hat{e} {(\prod_{w = 1}^{n} σ_{i^{*}, j}^{(w) c_{w}}, {dk}_{U \to V, D_{i}})}^{t}, \\ V_{ℓ} = \sum_{w = 1}^{n} c_{w} f_{i^{*}, j}^{(w, ℓ)}, 1 ⩽ ℓ ⩽ b, \\ V^{'} = H_{2} {({pk}_{V}, H_{M}, D_{i})}^{t}, \\ V^{″} = C^{' t} . \end{array}$ Then, $S$ sends ${pf}_{{chal}_{i^{*}, j}, V}$ to $V$ .

$V$ derives key $K_{i^{*}}$ from $K_{i}$ recursively. Then, $V$ verifies ${pf}_{{chal}_{i^{*}, j}, V}$ by checking whether

$ρ = \hat{e} {(\prod_{w = 1}^{n} H_{1} {(K_{i^{*}}, i^{*} ∥ j ∥ w)}^{c_{w}} \cdot \prod_{ℓ = 1}^{b} h_{M, ℓ}^{V_{ℓ}}, V^{'})}^{{sk}_{V}}$ ,

$\hat{e} (V^{'}, C^{'}) = \hat{e} (H_{2} ({pk}_{V}, H_{M}, D_{i}), V^{″})$ .

Data extraction. To extract $F_{i, j} = {[f_{i, j}^{(w, ℓ)}]}_{1 ⩽ w ⩽ n, 1 ⩽ ℓ ⩽ b}$ , $V$ chooses n linearly independent coefficient vectors ${C_{z}}_{1 ⩽ z ⩽ n} = {(c_{z, 1}, c_{z, 2}, \dots, c_{z, n})}_{1 ⩽ z ⩽ n}$ adaptively until he collects n valid proofs ${{pf}_{{chal}_{i^{*}, j}, V}^{(z)}}_{1 ⩽ z ⩽ n} = {(ρ^{(z)}, V_{1}^{(z)}, V_{2}^{(z)}, \dots, V_{b}^{(z)}, V^{' (z)}, V^{'' (z)})}_{1 ⩽ z ⩽ n}$ from $S$ . Let $C = {[c_{z, w}]}_{1 ⩽ z ⩽ n, 1 ⩽ w ⩽ n}$ be the $n \times n$ invertible matrix formed by ${C_{z}}_{1 ⩽ z ⩽ n}$ . For each $ℓ \in {1, 2, \dots, b}$ , $V$ has that $C \cdot X_{ℓ} = Y_{ℓ}$ , where $X_{ℓ} = {[f_{i, j}^{(1, ℓ)} f_{i, j}^{(2, ℓ)} \dots f_{i, j}^{(n, ℓ)}]}^{T}$ and $Y_{ℓ} = {[V_{ℓ}^{(1)} V_{ℓ}^{(2)} \dots V_{ℓ}^{(n)}]}^{T}$ . $V$ solves the system of linear equations to obtain $X_{ℓ}$ . Finally, $V$ extracts $F_{i, j} = [X_{1} X_{2} \dots X_{b}]$ .

6.1.1. Correctness

Assume that ${pf}_{{chal}_{i^{*}, j}, V} = (ρ, V_{1}, V_{2}, \dots, V_{b}, V^{'}, V^{″})$ is well formed and ${chal}_{i^{*}, j} = (C, C^{'}) = ((c_{1}, c_{2}, \dots, c_{n}), H_{3} (C))$ . That is, $\begin{array}{rclr} ρ = \hat{e} {(\prod_{w = 1}^{n} σ_{i^{*}, j}^{(w) c_{w}}, {dk}_{U \to V, D_{i}})}^{t}, & (9) \\ V_{ℓ} = \sum_{w = 1}^{n} c_{w} f_{i^{*}, j}^{(w, ℓ)}, 1 ⩽ ℓ ⩽ b, & (10) \\ V^{'} = H_{2} {({pk}_{V}, H_{M}, D_{i})}^{t}, & (11) \\ V^{″} = C^{' t} = H_{3} {(C)}^{t} . & (12) \end{array}$

Thus, the two verification equations are derived as follows:

$ρ = \hat{e} {(\prod_{w = 1}^{n} H_{1} {(K_{i^{*}}, i^{*} ∥ j ∥ w)}^{c_{w}} \cdot \prod_{ℓ = 1}^{b} h_{M, ℓ}^{V_{ℓ}}, V^{'})}^{{sk}_{V}}$ by (9), (10) and (11): $\begin{array}{rcl} ρ & = & \hat{e} {(\prod_{w = 1}^{n} σ_{i^{*}, j}^{(w) c_{w}}, {dk}_{U \to V, D_{i}})}^{t} \\ = & \hat{e} {(\prod_{w = 1}^{n} {[H_{1} (K_{i^{*}}, i^{*} ∥ j ∥ w) \cdot \prod_{ℓ = 1}^{b} h_{M, ℓ}^{f_{i^{*}, j}^{(w, ℓ)}}]}^{{sk}_{U} c_{w}}, H_{2} {({pk}_{V}, H_{M}, D_{i})}^{{sk}_{V} / {sk}_{U}})}^{t} \\ = & \hat{e} {(\prod_{w = 1}^{n} H_{1} {(K_{i^{*}}, i^{*} ∥ j ∥ w)}^{c_{w}} \cdot \prod_{ℓ = 1}^{b} h_{M, ℓ}^{\sum_{w = 1}^{n} c_{w} f_{i^{*}, j}^{(w, ℓ)}}, H_{2} {({pk}_{V}, H_{M}, D_{i})}^{t})}^{{sk}_{V}} \\ = & \hat{e} {(\prod_{w = 1}^{n} H_{1} {(K_{i^{*}}, i^{*} ∥ j ∥ w)}^{c_{w}} \cdot \prod_{ℓ = 1}^{b} h_{M, ℓ}^{V_{ℓ}}, V^{'})}^{{sk}_{V}} . \end{array}$

$\hat{e} (V^{'}, C^{'}) = \hat{e} (H_{2} ({pk}_{V}, H_{M}, D_{i}), V^{″})$ by (11) and (12): $\begin{array}{rcl} \hat{e} (V^{'}, C^{'}) & = & \hat{e} (H_{2} {({pk}_{V}, H_{M}, D_{i})}^{t}, C^{'}) \\ = & \hat{e} (H_{2} ({pk}_{V}, H_{M}, D_{i}), C^{' t}) \\ = & \hat{e} (H_{2} ({pk}_{V}, H_{M}, D_{i}), V^{″}) . \end{array}$

6.1.2. Performance

The performance of the construction is analyzed in three aspects: the computation cost of each algorithm, the storage cost of each party, and the communication cost of each phase. Table 6 shows the computation cost of each algorithm. The delegated POR scheme is more efficient than the delegated PDP scheme. Algorithm GenChal has

b + 1

fewer scalar exponentiations. Algorithm GenProof has

2 b - 2

fewer multiplications,

2 b

fewer scalar exponentiations, and 2 fewer bilinear maps. Algorithm ForgeProof has

2 b - 2

fewer multiplications,

2 b

fewer scalar exponentiations, and 2 fewer bilinear maps. Algorithm VrfyProof has 2 fewer bilinear maps, but it has

b - 2

more scalar exponentiations.

Table 6
Computation cost

Algorithm	Add	Mul	Exp	Hash	Pairing
KeyGen	0	0	1	0	0
TagGen	0	$n b$	$n b + n$	$n + l - 1$	0
GenKT	0	0	1	1	0
GenDK	0	0	1	1	2
VrfyDK	0	0	0	1	2
GenChal	0	0	0	1	0
GenProof	$n b - b$	$n b + n - 1$	$n + 3$	2	1
ForgeProof	$n b - b$	$2 n b + n - 1$	$n b + n + 3$	$n + 2$	1
VrfyProof	0	$n + b - 1$	$n + b + 1$	$n + 1$	3

Notes: n is the number of integrity tags; b is the number of data identifiers; l is the number of categories.

Table 7 shows the storage cost of each party. The delegated POR scheme has the same storage complexity as the delegated PDP scheme. Table 8 shows the communication cost of each phase. In the integrity check phase, the delegated POR scheme has less communication cost than the delegated PDP scheme. Each challenge

{chal}_{i, j}

has b fewer elements in

G

. Each integrity proof

{pf}_{{chal}_{i, j}, V}

has

2 b

fewer elements in

G

, but it has b more elements in

Z_{q}

Table 7

Storage cost

Party	Bits
User	$k + (b + v + 1) p + ℓ$
Delegated	$k + (b + 1) p + ℓ$
Verifier	$k + (b + 1) p + ℓ$
Storage server	$n b k + (n + b + v) p + ℓ$

Table 8

Communication cost

Phase	Bits
Setup	$U \to S : n b k + (n + b) p + ℓ$
Delegation	$V \leftrightarrow U : (b + 1) p + ℓ$
Delegation	$U \to S : p$
Integrity check	$V \leftrightarrow S : (n + b) k + 3 p + p_{T}$

k is the security parameter; p is the size of an element in $G$ ; $p_{T}$ is the size of an element in $G_{T}$ ; ℓ is the size of an element in $K$ ; n is the number of integrity tags; b is the number of data identifiers.

To measure the performance of the delegated POR scheme, we provide simulations for different data size. The simulation settings are the same as the settings for the simulations in Section 5.1.2. Table 9 provides the simulation results. The computation in the integrity check phase is more efficient. A verifier (algorithm GenChal and algorithm VrfyProof) takes no more than 20 s to check data of 1000 MB. A storage server (algorithm GenProof) takes less than 50 s to generate an integrity proof for data of 1000 MB.

Table 9

Simulation result of the delegated POR scheme

Data size (MB)	b	TagGen (s)	GenKT (ms)	GenDK (ms)	VrfyDK (ms)	GenChal (ms)	GenProof (s)	VrfyProof (s)
10	102	174.184	11.329	26.556	19.487	6.426	0.664	1.516
10	144	175.400	23.192	37.301	21.291	3.484	0.572	1.672
10	202	177.920	11.316	26.066	17.682	2.484	0.528	2.014
100	320	1670.304	18.896	38.105	31.266	4.517	4.467	4.689
100	452	1660.652	14.095	35.599	28.221	5.942	4.241	5.214
100	640	1663.375	15.712	30.300	26.676	2.885	4.320	6.293
1000	1012	16,279.388	21.920	41.029	25.993	5.155	41.192	14.731
1000	1432	16,250.004	14.113	32.773	28.116	3.111	40.346	16.308
1000	2024	16,237.705	12.841	34.462	27.697	3.659	38.119	19.948

Notes: Security parameter $k = 512$ ; b is the number of data identifiers.

The number b of data identifiers affects the efficiency of the integrity check phase. If b is small, the verifier has to compute more hash values to verify an integrity proof. The delegated POR scheme will have similar efficiency to the delegated PDP scheme. If b is large, the verifier has to do more scalar exponentiations to verify an integrity proof. Nevertheless, the delegated POR scheme will still be more efficient then the delegated PDP scheme. We suggest that a user choose $b = Θ (\sqrt{n^{'}})$ to balance the effect of the two extreme cases. From the simulation results, GenChal and GenProof are more efficient when choosing $b \approx \sqrt{n^{'} / 4}$ . In contrast, VrfyProof is more efficient when choosing $b \approx \sqrt{n^{'} / 16}$ .

6.2. Security analysis

The delegated POR scheme satisfies the requirements of proof unforgeability, proof indistinguishability and delegation key unforgeability.

6.2.1. Proof unforgeability

The delegated POR scheme is proof unforgeable under the truncated 1-BDHE assumption and the KEA1 in the random oracle model.

Theorem 4.
Let $O_{H_{1}}$ and $O_{H_{2}}$ be the random oracles for hash functions $H_{1}$ and $H_{2}$ . An adversary can issue at most $q_{1}$ queries to $O_{H_{1}}$ , $q_{2}$ queries to $O_{H_{2}}$ , $q_{T}$ queries to $O_{Tag}$ , and $q_{K}$ queries to $O_{DK}$ . Let $t_{1}$ , $t_{2}$ , $t_{T}$ and $t_{K}$ be the time taken by $O_{H_{1}}$ , $O_{H_{2}}$ , $O_{Tag}$ and $O_{DK}$ to respond an oracle query. The KEA1 extractor $\overline{A}$ takes time $t_{\overline{A}}$ to extract an exponent. Let k be the security parameter, b be the number of data identifiers, l be the number of categories, and $K$ be a large space of hierarchical keys such that $| K | ⩾ 2 (l q_{1} + l^{2} q_{T})$ . If the truncated BDHE problem is $(t, ϵ, 1)$ -secure, the delegated POR scheme is $(t - q_{1} t_{1} - q_{2} t_{2} - 2 q_{T} t_{T} - q_{K} t_{K} - t_{\overline{A}}, \frac{2^{k - 2}}{2^{k - 2} - 1} ϵ)$ -proof unforgeable in the random oracle model.
Proof.
This proof is similar to the proof of Theorem 1, but it has two differences:
In the challenge phase, $B$ provides challenge ${chal}_{i, j} = (C, C^{'}) = ((c_{1}, c_{2}, \dots, c_{n}), H_{3} (C))$ to $A$ . In the answer phase, $A$ returns proof ${pf}_{{chal}_{i, j}, V} = (ρ, V_{1}, V_{2}, \dots, V_{b}, V^{'}, V^{″})$ . Thus, the verification equation becomes $ρ = \hat{e} {(\prod_{w = 1}^{n} H_{1} {(K_{i}^{}, i ∥ j ∥ w)}^{c_{w}} \cdot \prod_{ℓ = 1}^{b} h_{M^{}, ℓ}^{V_{ℓ}}, V^{'})}^{{sk}_{V}},$ which indeed is equivalent to $ρ^{s} = \hat{e} {(\prod_{w = 1}^{n} H_{1} {(K_{i}^{*}, i ∥ j ∥ w)}^{s c_{w}} \cdot \prod_{e l l = 1}^{b} V_{ℓ}, V^{″})}^{{sk}_{V}} .$

Integrity proof ${pf}_{{chal}_{i, j}, V} = (ρ, V_{1}, V_{2}, \dots, V_{b}, V^{'}, V^{″})$ includes $V_{ℓ} = \sum_{w = 1}^{n} c_{w} f_{i, j}^{' (w, ℓ)}$ . Thus, $B$ does not need to use the KEA1 extractor $\overline{A}$ to extract $\sum_{w = 1}^{n} c_{w} f_{i, j}^{' (w, ℓ)}$ , where $1 ⩽ ℓ ⩽ b$ .

The reduced advantage is still $ϵ = (1 - \frac{1}{2^{k - 2}}) ϵ^{'}$ , but the reduced time becomes $t = t^{'} + q_{1} t_{1} + q_{2} t_{2} + 2 q_{T} t_{T} + q_{K} t_{K} + t_{\overline{A}}$ . □

6.2.2. Proof indistinguishability

The delegated POR scheme is proof indistinguishable under the truncated decisional 1-BDHE assumption in the random oracle model.

Theorem 5.
Let $O_{H_{1}}$ , $O_{H_{2}}$ and $O_{H_{3}}$ be the random oracles for hash functions $H_{1}$ , $H_{2}$ and $H_{3}$ . An adversary can issue at most $q_{1}$ queries to $O_{H_{1}}$ , $q_{2}$ queries to $O_{H_{2}}$ , $q_{3}$ queries to $O_{H_{3}}$ , $q_{K}$ queries to $O_{DK}$ , and $q_{P}$ queries to $O_{Proof}$ . Let $t_{1}$ , $t_{2}$ , $t_{3}$ , $t_{K}$ and $t_{P}$ be the time taken by $O_{H_{1}}$ , $O_{H_{2}}$ , $O_{H_{3}}$ , $O_{DK}$ and $O_{Proof}$ to respond an oracle query. If the truncated decisional BDHE problem is $(t, ϵ, 1)$ -secure, the delegated POR scheme is $(t - q_{1} t_{1} - q_{2} t_{2} - q_{3} t_{3} - q_{K} t_{K} - q_{P} t_{P}, ϵ)$ -proof indistinguishable in the random oracle model.
Proof.
This proof is similar to the proof of Theorem 2, but it has two differences:
The integrity challenge is in the form of ${chal}_{i, j} = (C, C^{'})$ , where $C^{'} = H_{3} (C)$ . Thus, $B$ can compute $V^{″} = C^{' t}$ by handling $O_{H_{3}}$ .

The integrity proof is in the form of ${pf}_{{chal}_{i, j}, V} = (ρ, V_{1}, V_{2}, \dots, V_{b}, V^{'}, V^{″})$ , where $V_{ℓ} = \sum_{w = 1}^{n} c_{w} f_{i, j}^{(w, ℓ)}$ . $B$ can still compute ${pf}_{{chal}_{i, j}, V}$ even in the challenge phase.

The reduced advantage is still $ϵ = ϵ^{'}$ , and the reduced time is still $t = t^{'} + q_{1} t_{1} + q_{2} t_{2} + q_{3} t_{3} + q_{K} t_{K} + q_{P} t_{P}$ . □

6.2.3. Delegation key unforgeability

The delegated POR scheme is delegation key unforgeable under the InvCDH assumption in the random oracle model.

Theorem 6.
Let $O_{H_{2}}$ be the random oracle for hash function $H_{2}$ . An adversary can issue at most $q_{2}$ queries to $O_{H_{2}}$ , and $q_{K}$ queries to $O_{DK}$ . Let $t_{2}$ and $t_{K}$ be the time taken by $O_{H_{2}}$ and $O_{DK}$ to respond an oracle query. Let e be the Euler’s number. If the InvCDH problem is $(t, ϵ)$ -secure, the delegated POR scheme is $(t - q_{2} t_{2} - q_{K} t_{K}, e (q_{K} + 1) ϵ)$ -delegation key unforgeable in the random oracle model.
Proof.
This proof is the same as the proof of Theorem 3. □

7. Discussion

The issues of curve suggestion, random sampling and dynamic data are discussed in this section.

7.1. Elliptic curve and block size

Suppose that element size $| g | = 160$ is sufficient to withstand generic discrete logarithm attacks in $G$ . Suppose that pairing size $| g_{T} | = 1024$ is sufficient to resist the index calculus attack (finite field discrete logarithm attack) in $G_{T}$ . To achieve better performance, we suggest choosing the type D curves [35] for block size smaller than 512 bits and the type A curves [35] for block size greater than 512 bits. The type D curves have embedding degree six. Thus, the type D curves can have smaller element size and the pairing size is still large enough. The type A curves have embedding degree two. Thus, the type A curves have element size at least 512 bits.

Table 10 provides the suggested curves for various block sizes. The suggested curves are optimal for tag overhead

\frac{element size}{block size}

. We use an Intel Xeon E5430 processor with 4 GB RAM to perform the pairing operations, but only one core is used in the same time. The type A curve for 512-bit block size has the fastest pairing operations.

Table 10
Elliptic curve suggestion

Block size (bits)	Group size (bits)	Element size (bits)	Pairing size (bits)	Tag overhead	Pairing time (ms)
256	259	259	1554	1.011719	23.413
512	513	519	1038	1.0136719	13.942
1024	1026	1032	2064	1.00781	84.215
2048	2050	2056	4112	1.003906	589.657
4096	4098	4104	8208	1.0019531	4429.413

Notes: A type D curve is used for 256-bit block size, and the discriminant of the type D curve is 104,826,427; type A curves are used for the other block sizes.

7.2. Random sampling rate and error correcting code

In the integrity check phase, a verifier checks all data blocks to detect errors. The storage server has to access all data blocks to generate an integrity proof. The verifier has to compute all hash values of tag indexes to verify the integrity proof. The computation complexity is $O (n)$ , where n is the number of data blocks. Ateniese et al. [2,3] studied the random sampling technique to reduce the computation cost in the integrity check phase. A verifier can randomly sample a relatively small portion of data blocks and assure data integrity with high confidence. Many integrity check schemes [1,11,12,23,39,48,49,51,55,56,58,61] use the random sampling technique to check data efficiently.

The random sampling technique is a trade-off between efficiency and efficacy. Assume that there are n data blocks. Let α be the proportion of corrupted blocks, where $0 < α ⩽ 1$ . If a verifier randomly samples t blocks to check, the false negative rate (probability of detecting no corrupted blocks) is $\begin{array}{rcl} Pr [FN] \\ = Pr [Detecting no corrupted blocks | α n blocks are corrupted] \\ = \prod_{i = 1}^{t} \frac{n - α n - i + 1}{n - i + 1} \\ ⩽ {(\frac{n - α n}{n})}^{t} \\ = {(1 - α)}^{t} . \end{array}$ Figure 9 illustrates the false negative rates for various settings of $(n, α, t)$ , where $n = 10^{6}$ . When $α = 1 %$ , a verifier has to sample $t ⩾ 1000$ data blocks to get 99.995% confidence. When $α = 0.1 %$ , a verifier has to sample $t ⩾ 10, 000$ data blocks for the same confidence level.

Fig. 9.

False negative rate of checking t-out-of-n data blocks. α is the proportion of corrupted blocks.

A verifier has to check a large number of data blocks when α is very small. For example, the verifier has to check $t ⩾ n / 2 = 500, 000$ data blocks when $α = 0.001 %$ for the confidence level at least 99.9%. Thus, detecting corrupted blocks for a small α becomes a heavy work. We use an error correcting code (ECC) to solve this problem. An $(n^{'}, k^{'}, d^{'})$ -ECC encodes a message of $k^{'}$ symbols into a codeword of $n^{'}$ symbols. The codewords have minimum distance $d^{'}$ such that a codeword of $\frac{d^{'} - 1}{2}$ errors can be corrected.

Given the number n of data blocks and the proportion β of error correcting, an $(\frac{n}{1 - 2 β}, n, \frac{2 β n}{1 - 2 β} + 1)$ -ECC can be applied to the data, where $0 < β < 0.5$ . In the setup phase, a user encodes his data $M = (m_{1}, m_{2}, \dots, m_{n})$ into codeword $M^{'} = (m_{1}^{'}, m_{2}^{'}, \dots, m_{\frac{n}{1 - 2 β}}^{'})$ . Then, the user generates integrity tags $Σ = (σ_{1}, σ_{2}, \dots, σ_{\frac{n}{1 - 2 β}})$ for $M^{'}$ . In the integrity check phase, a verifier can randomly sample $t ⩾ 6 ({log}_{1 / (1 - α)} 10)$ data blocks to detect errors of proportion α with confidence at least 99.9999%. On the other hand, the $(\frac{n}{1 - 2 β}, n, \frac{2 β n}{1 - 2 β} + 1)$ -ECC can correct errors of proportion β. If $α ⩽ β$ , the errors which are not detected by the user can be corrected by the ECC. In the progressive error model, errors increase by proportion γ for each time period. When the errors accumulate up to proportion α, the verifier can detect the errors with high probability. The user can check data for every $⌊ \frac{β - α}{γ} ⌋$ time periods. As a result, a user can use an ECC to reduce the computation cost in the integrity check phase. Although the ECC increases extra storage cost, the benefit is still considerable.

7.3. Dynamic data

A user will update his data in many situations, and he has to update the integrity tags for the updated data. When the user inserts or deletes a data block, he has to maintain the tag indexes. When the user modifies a data block, he has to update the version number. Many integrity check schemes [8,16,17,24–26,30,31,38,45,46,52,53,57] use dynamic data structures to reduce the computation cost and the storage cost. The delegated PDP/POR scheme can use either the Merkle hash tree [36] or the authenticated skip list [27] to support dynamic data. We adapt the delegated PDP scheme for dynamic data via the Merkle hash tree as follows:

To reduce the computation cost of updating tag indexes, integrity tags do not include tag indexes anymore. User $U$ generates integrity tag $σ_{i, j}^{(w)}$ for blocks $(f_{i, j}^{(w, 1)}, f_{i, j}^{(w, 2)}, \dots, f_{i, j}^{(w, b)})$ as follows: $σ_{i, j}^{(w)} = {(\prod_{ℓ = 1}^{b} h_{M, ℓ}^{f_{i, j}^{(w, ℓ)}})}^{{sk}_{U}} .$

To assure integrity of the tags, a Merkle hash tree is built for each category. Let $H : K \times {0, 1}^{*} \to {0, 1}^{*}$ be a cryptographic hash function. $U$ uses $H (K_{i}, \cdot)$ to build Merkle hash tree $T_{i}$ from the tags in category $D_{i}$ . Then, $U$ signs the root of $T_{i}$ into signature $σ_{i} = Sign ({sk}_{U}, R (T_{i}))$ . Finally, $U$ stores $(M, Σ, H_{M}, K_{M}, {T_{i}}, {σ_{i}})$ in storage server $S$ .

To check integrity of data, a verifier has to make sure that an integrity proof is generated with correct integrity tags. To check file $F_{i^{*}, j}$ , verifier $V$ retrieves integrity tags $(σ_{i^{*}, j}^{(1)}, σ_{i^{*}, j}^{(2)}, \dots, σ_{i^{*}, j}^{(n)})$ , the siblings of the verification path in Merkle hash tree $T_{i^{*}}$ , and signature $σ_{i^{*}}$ from $S$ . Then, $V$ builds Merkle hash tree $T_{i^{*}}^{'}$ from the tags and the siblings. $V$ verifies the tags by checking whether $Verify ({pk}_{U}, R (T_{i^{*}}^{'}), σ_{i^{*}}) = true$ . If the tags are correct, $V$ gives $S$ challenge ${chal}_{i^{*}, j}$ . $S$ chooses $t \in_{R} Z_{q}$ and generates integrity proof ${pf}_{{chal}_{i^{*}, j}, V} = (ρ, V_{1}, V_{2}, \dots, V_{b}, V_{1}^{'}, V_{2}^{'}, \dots, V_{b}^{'}, V^{″}, V^{‴})$ as the scheme specifies, but it also provides $V_{d k} = {({dk}_{U \to V, D_{i}})}^{t}$ to $V$ . $V$ checks whether

$ρ = \hat{e} (\prod_{w = 1}^{n} σ_{i^{*}, j}^{(w) c_{w}}, V_{d k})$ ,

$ρ^{s} = \hat{e} {(\prod_{ℓ = 1}^{b} V_{ℓ}, V^{″})}^{{sk}_{V}}$

and verifies

(V_{1}, V_{2}, \dots, V_{b}, V_{1}^{'}, V_{2}^{'}, \dots, V_{b}^{'}, V^{″}, V^{‴})

as the scheme specifies.

To prevent re-delegation, delegation keys have to be protected from leaks. $U$ sends delegation keys to $S$ via a secure channel, and $S$ will not reveal the delegation keys.

If $V$ knows delegation key ${dk}_{U \to V, D_{i}}$ , he can re-delegate his integrity check capability to third party $W$ in the following way. $V$ chooses $t_{W} \in_{R} Z_{q}$ to compute delegation key $d k_{U \to V, D_{i}}^{'} = {({dk}_{U \to V, D_{i}})}^{t_{W}}$ and secret key ${sk}_{V}^{'} = {sk}_{V} t_{W}$ . Then, $V$ gives $(H_{M}, K_{i}, d k_{U \to V, D_{i}}^{'}, {sk}_{V}^{'})$ to $W$ . To check file $F_{i^{*}, j}$ , $W$ retrieves and verifies integrity tags $(σ_{i^{*}, j}^{(1)}, σ_{i^{*}, j}^{(2)}, \dots, σ_{i^{*}, j}^{(n)})$ . If the tags are correct, $W$ gives $S$ challenge ${chal}_{i^{*}, j}$ and obtains integrity proof ${pf}_{{chal}_{i^{*}, j}, V} = (ρ, V_{1}, V_{2}, \dots, V_{b}, V_{1}^{'}, V_{2}^{'}, \dots, V_{b}^{'}, V^{″}, V^{‴})$ from $S$ . $W$ replaces ρ with $ρ^{'}$ , where $ρ^{'} = \hat{e} (\prod_{w = 1}^{n} σ_{i^{*}, j}^{(w) c_{w}}, d k_{U \to V, D_{i}}^{'})$ . Then, $W$ checks whether

$ρ^{' s} = \hat{e} {(\prod_{ℓ = 1}^{b} V_{ℓ}, H_{2} ({pk}_{V}, H_{M}, D_{i}))}^{{sk}_{V}^{'}}$

and verifies

(V_{1}, V_{2}, \dots, V_{b}, V_{1}^{'}, V_{2}^{'}, \dots, V_{b}^{'}, V^{″}, V^{‴})

as the scheme specifies.

To modify data, integrity tags and Merkle hash trees have to be updated accordingly. To insert file $F_{i, j}$ , $U$ generates integrity tags $Σ_{i, j}$ and updates Merkle hash tree $T_{i}$ . To delete file $F_{i, j}$ , $U$ removes integrity tags $Σ_{i, j}$ and updates Merkle hash tree $T_{i}$ . To modify file $F_{i, j}$ , $U$ updates integrity tags $Σ_{i, j}$ and Merkle hash tree $T_{i}$ .

8. Conclusion

Delegated integrity check is an efficient solution for a user to control the subject who can check his data. Delegated integrity check provides effective management of verifiers. A user can delegate a verifier to check his data and revoke the verifier later. The verifier cannot re-delegate his integrity check capability to other people. Delegated integrity check supports dynamic group of verifiers. A user can delegate a verifier to check his data. Delegated integrity check achieves large-scale delegation. The delegation process is lightweight and independent of the data size. The integrity check process is efficient.

This paper proposes the delegated integrity check model. This paper provides two delegated integrity check schemes for hierarchical data. The first scheme assures data possession of a storage server. The second scheme assures data retrievability from a storage server. The related issues of the delegated integrity check model are discussed.

Footnotes

Acknowledgments

This research is supported by parts of MOST projects MOST-101-2221-E-009-074-MY3, MOST-101-2219-E-009-016 and MOST-102-2219-E-009-010, Taiwan.

References

[1]

Armknecht,

J.-M.

Bohli,

G.O.

Karame,

Liu and

C.A.

Reuter, Outsourced proofs of retrievability, in: Proceedings of the 2014 ACM SIGSAC Conference on Computer and Communications Security, CCS’14, ACM, New York, NY, USA, 2014, pp. 831–843.

[2]

Ateniese,

Burns,

Curtmola,

Herring,

Khan,

Kissner,

Peterson and

Song, Remote data checking using provable data possession, ACM Transactions on Information and System Security 14(1) (2011), Article No. 12.

[3]

Ateniese,

Burns,

Curtmola,

Herring,

Kissner,

Peterson and

Song, Provable data possession at untrusted stores, in: Proceedings of the 14th ACM Conference on Computer and Communications Security, CCS’07, ACM, New York, NY, USA, 2007, pp. 598–609.

[4]

Ateniese,

Di Pietro,

L.V.

Mancini and

Tsudik, Scalable and efficient provable data possession, in: Proceedings of the 4th International Conference on Security and Privacy in Communication Networks, SecureComm’08, ACM, New York, NY, USA, 2008, Article No. 9.

[5]

Ateniese,

Kamara and

Katz, Proofs of storage from homomorphic identification protocols, in: Proceedings of the 15th International Conference on the Theory and Application of Cryptology and Information Security: Advances in Cryptology, ASIACRYPT’09, Springer, Berlin, Heidelberg, 2009, pp. 319–333.

[6]

Azraoui,

Elkhiyaoui,

Molva and

Önen, StealthGuard: Proofs of retrievability with hidden watchdogs, in: Computer Security – ESORICS 2014 – 19th European Symposium on Research in Computer Security, Proceedings, Part I, Wroclaw, Poland, 7–11 September 2014, 2014, pp. 239–256.

[7]

Bao,

Deng and

Zhu, Variations of Diffie–Hellman problem, in: Information and Communications Security, Lecture Notes in Computer Science, Vol. 2836, Springer, Berlin, Heidelberg, 2003, pp. 301–312.

[8]

A.F.

Barsoum and

M.A.

Hasan, Provable multicopy dynamic data possession in cloud computing systems, IEEE Transactions on Information Forensics and Security 10(3) (2015), 485–497.

[9]

Boneh,

Boyen and

E.-J.

Goh, Hierarchical identity based encryption with constant size ciphertext, in: Proceedings of the 24th Annual International Conference on Theory and Applications of Cryptographic Techniques, EUROCRYPT’05, Springer, Berlin, Heidelberg, 2005, pp. 440–456.

10.

[10]

Boneh,

Gentry and

Waters, Collusion resistant broadcast encryption with short ciphertexts and private keys, in: Proceedings of the 25th Annual International Conference on Advances in Cryptology, CRYPTO’05, Springer, Berlin, Heidelberg, 2005, pp. 258–275.

11.

[11]

K.D.

Bowers,

Juels and

Oprea, HAIL: A high-availability and integrity layer for cloud storage, in: Proceedings of the 16th ACM Conference on Computer and Communications Security, CCS’09, ACM, New York, NY, USA, 2009, pp. 187–198.

12.

[12]

K.D.

Bowers,

Juels and

Oprea, Proofs of retrievability: Theory and implementation, in: Proceedings of the 2009 ACM Workshop on Cloud Computing Security, CCSW’09, ACM, New York, NY, USA, 2009, pp. 43–54.

13.

[13]

Cao,

Yu,

Yang,

Lou and

Y.T.

Hou, Lt codes-based secure and reliable cloud storage service, in: INFOCOM, 2012, pp. 693–701.

14.

[14]

Cash,

Küpçü and

Wichs, Dynamic proofs of retrievability via oblivious RAM, in: Advances in Cryptology – EUROCRYPT 2013, 32nd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Proceedings, Athens, Greece, 26–30 May 2013, 2013, pp. 279–295.

15.

[15]

E.-C.

Chang and

Xu, Remote integrity check with dishonest storage server, in: Proceedings of the 13th European Symposium on Research in Computer Security – ESORICS’08, Springer, 2008, pp. 223–237.

16.

[16]

Chen and

Curtmola, Robust dynamic provable data possession, in: ICDCS Workshops, 2012, pp. 515–525.

17.

[17]

Chen and

Curtmola, Robust dynamic remote data checking for public clouds, in: ACM Conference on Computer and Communications Security, 2012, pp. 1043–1045.

18.

[18]

Chen,

Curtmola,

Ateniese and

Burns, Remote data checking for network coding-based distributed storage systems, in: Proceedings of the 2010 ACM Workshop on Cloud Computing Security Workshop, CCSW’10, ACM, New York, NY, USA, 2010, pp. 31–42.

19.

[19]

Curtmola,

Khan and

Burns, Robust remote data checking, in: Proceedings of the 4th ACM International Workshop on Storage Security and Survivability, StorageSS’08, ACM, New York, NY, USA, 2008, pp. 63–68.

20.

[20]

Curtmola,

Khan,

Burns and

Ateniese, MR-PDP: Multiple-replica provable data possession, in: Proceedings of the 2008 the 28th International Conference on Distributed Computing Systems, ICDCS’08, IEEE Computer Society, Washington, DC, USA, 2008, pp. 411–420.

21.

[21]

Damgård, Towards practical public key systems secure against chosen ciphertext attacks, in: Proceedings of the 11th Annual International Cryptology Conference on Advances in Cryptology, CRYPTO’91, Springer, London, UK, 1992, pp. 445–456.

22.

[22]

Dodis,

Vadhan and

Wichs, Proofs of retrievability via hardness amplification, in: Proceedings of the 6th Theory of Cryptography Conference on Theory of Cryptography, TCC’09, Springer, Berlin, Heidelberg, 2009, pp. 109–127.

23.

[23]

Du,

Deng,

Chen,

He and

Zheng, Proofs of ownership and retrievability in cloud storage, in: 13th IEEE International Conference on Trust, Security and Privacy in Computing and Communications, TrustCom 2014, Beijing, China, 24–26 September 2014, 2014, pp. 328–335.

24.

[24]

Erway,

Küpçü,

Papamanthou and

Tamassia, Dynamic provable data possession, in: Proceedings of the 16th ACM Conference on Computer and Communications Security, CCS’09, ACM, New York, NY, USA, 2009, pp. 213–222.

25.

[25]

Etemad and

Küpçü, Transparent, distributed, and replicated dynamic provable data possession, in: Proceedings of the 11th International Conference on Applied Cryptography and Network Security, ACNS’13, Springer, Berlin, Heidelberg, 2013, pp. 1–18.

26.

[26]

M.T.

Goodrich,

Papamanthou,

Tamassia and

Triandopoulos, Athos: Efficient authentication of outsourced file systems, in: Proceedings of the 11th International Conference on Information Security, ISC’08, Springer, Berlin, Heidelberg, 2008, pp. 80–96.

27.

[27]

M.T.

Goodrich,

Tamassia and

Schwerin, Implementation of an authenticated dictionary with skip lists and commutative hashing, in: DARPA Information Survivability Conference & Exposition II, 2001, DISCEX’01, Proceedings, Vol. 2, 2001, pp. 68–82.

28.

[28]

Guang,

Y.-F.

Zhu,

C.-X.

Gu,

Y.-H.

Zheng and

J.-l.

Fei, An efficient proof of retrievability scheme for fully homomorphic encrypted data, Journal of Networks 8(2) (2013), 339–344.

29.

[29]

Han,

Liu,

Chen and

Gu, Proofs of retrievability based on MRD codes, in: Information Security Practice and Experience – 10th International Conference, ISPEC 2014, Proceedings, Fuzhou, China, 5–8 May 2014, 2014, pp. 330–345.

30.

[30]

Heitzmann,

Palazzi,

Papamanthou and

Tamassia, Efficient integrity checking of untrusted network storage, in: Proceedings of the 4th ACM International Workshop on Storage Security and Survivability, StorageSS’08, ACM, New York, NY, USA, 2008, pp. 43–54.

31.

[31]

Huang,

Liu,

Xian,

Wang and

Fu, Enabling dynamic proof of retrievability in regenerating-coding-based cloud storage, in: IEEE International Conference on Communications, ICC 2014, Sydney, Australia, 10–14 June 2014, Workshops Proceedings, 2014, pp. 712–717.

32.

[32]ISO, ISO/HL7 10781:2009 – Electronic health record-system functional model, Release 1.1, 2009.

33.

[33]

Juels and

B.S.

KaliskiJr., PORs: Proofs of retrievability for large files, in: Proceedings of the 14th ACM Conference on Computer and Communications Security, CCS’07, ACM, New York, NY, USA, 2007, pp. 584–597.

34.

[34]

Li,

Tan,

Chen and

D.S.

Wong, An efficient proof of retrievability with public auditing in cloud computing, in: Proceedings of the 2013 5th International Conference on Intelligent Networking and Collaborative Systems, INCOS’13, IEEE Computer Society, Washington, DC, USA, 2013, pp. 93–98.

35.

[35]

Lynn, On the implementation of pairing-based cryptosystems, PhD dissertation, Stanford University, 2007.

36.

[36]

R.C.

Merkle, A digital signature based on a conventional encryption function, in: A Conference on the Theory and Applications of Cryptographic Techniques on Advances in Cryptology, CRYPTO’87, Springer, London, UK, 1988, pp. 369–378.

37.

[37]Microsoft, HealthVault, available at: https://www.healthvault.com/.

38.

[38]

Mo,

Zhou and

Chen, A dynamic proof of retrievability (PoR) scheme with O(logn) complexity, in: 2012 IEEE International Conference on Communications (ICC), June 2012, 2012, pp. 912–916.

39.

[39]

Mohan and

Katti, Provable data possession using sigma-protocols, in: Proceedings of the 2012 IEEE 11th International Conference on Trust, Security and Privacy in Computing and Communications, TRUSTCOM’12, IEEE Computer Society, Washington, DC, USA, 2012, pp. 565–572.

40.

[40]

Papamanthou,

Tamassia and

Triandopoulos, Authenticated hash tables, in: Proceedings of the 15th ACM Conference on Computer and Communications Security, CCS’08, ACM, New York, NY, USA, 2008, pp. 437–448.

41.

[41]

B.R.

Purushothama and

B.B.

Amberker, Publicly auditable provable data possession scheme for outsourced data in the public cloud using polynomial interpolation, in: Recent Trends in Computer Networks and Distributed Systems Security, Springer, 2012, pp. 11–22.

42.

[42]

Sarkar and

Safavi-Naini, Proofs of retrievability via fountain code, in: Proceedings of the 5th International Conference on Foundations and Practice of Security, FPS’12, Springer, Berlin, Heidelberg, 2013, pp. 18–32.

43.

[43]

Shacham and

Waters, Compact proofs of retrievability, Journal of Cryptology 26(3) (2013), 442–483.

44.

[44]

S.-T.

Shen and

W.-G.

Tzeng, Delegable provable data possession for remote data in the clouds, in: Proceedings of the 13th International Conference on Information and Communications Security, ICICS’11, Springer, Berlin, Heidelberg, 2011, pp. 93–111.

45.

[45]

Shi,

Stefanov and

Papamanthou, Practical dynamic proofs of retrievability, in: Proceedings of the 2013 ACM SIGSAC Conference on Computer & Communications Security, CCS’13, ACM, New York, NY, USA, 2013, pp. 325–336.

46.

[46]

Stefanov,

van Dijk,

Juels and

Oprea, Iris: A scalable cloud file system with efficient integrity checks, in: Proceedings of the 28th Annual Computer Security Applications Conference, ACSAC’12, ACM, New York, NY, USA, 2012, pp. 229–238.

47.

[47]

Wang,

S.S.M.

Chow,

Wang,

Ren and

Lou, Privacy-preserving public auditing for secure cloud storage, IEEE Transactions on Computers 62(2) (2013), 362–375.

48.

[48]

Wang,

Ren,

Cao and

Lou, Toward secure and dependable storage services in cloud computing, IEEE Transactions on Services Computing 5(2) (2012), 220–232.

49.

[49]

Wang,

Ren and

Lou, Ensuring data storage security in cloud computing, in: Proceedings of the 17th International Workshop on Quality of Service – IWQoS’09, July 2009, 2009, pp. 1–9.

50.

[50]

Wang,

Ren and

Lou, Privacy-preserving public auditing for data storage security in cloud computing, in: Proceedings of the 29th Conference on Information Communications, INFOCOM’10, IEEE Press, Piscataway, NJ, USA, 2010, pp. 525–533.

51.

[51]

Wang, Proxy provable data possession in public clouds, IEEE Transactions on Services Computing 6(4) (2013), 551–559.

52.

[52]

Wang,

Li,

Ren and

Lou, Enabling public verifiability and data dynamics for storage security in cloud computing, in: Proceedings of the 14th European Conference on Research in Computer Security, ESORICS’09, Springer, Berlin, Heidelberg, 2009, pp. 355–370.

53.

[53]

Wang,

Ren,

Lou and

Li, Enabling public auditability and data dynamics for storage security in cloud computing, IEEE Transactions on Parallel and Distributed Systems 22(5) (2011), 847–859.

54.

[54]WHO, Medical records manual – A guide for developing countries, 2001.

55.

[55]

Xu and

E.-C.

Chang, Towards efficient proofs of retrievability, in: Proceedings of the 7th ACM Symposium on Information, Computer and Communications Security, ASIACCS’12, ACM, New York, NY, USA, 2012, pp. 79–80.

56.

[56]

Yuan and

Yu, Proofs of retrievability with public verifiability and constant communication cost in cloud, in: Proceedings of the 2013 International Workshop on Security in Cloud Computing, Cloud Computing’13, ACM, New York, NY, USA, 2013, pp. 19–26.

57.

[57]

Zhang and

Blanton, Efficient dynamic provable possession of remote data via balanced update trees, in: Proceedings of the 8th ACM SIGSAC Symposium on Information, Computer and Communications Security, ASIACCS’13, ACM, New York, NY, USA, 2013, pp. 183–194.

58.

[58]

Zheng and

Xu, Secure and efficient proof of storage with deduplication, in: Proceedings of the Second ACM Conference on Data and Application Security and Privacy, CODASPY’12, ACM, New York, NY, USA, 2012, pp. 1–12.

59.

[59]

Zhu,

G.-J.

Ahn,

Hu,

S.S.

Yau,

H.G.

An and

C.-J.

Hu, Dynamic audit services for outsourced storages in clouds, IEEE Transactions on Services Computing 6(2) (2013), 227–238.

60.

[60]

Zhu,

Hu,

G.-J.

Ahn and

Yu, Cooperative provable data possession for integrity verification in multicloud storage, IEEE Transactions on Parallel and Distributed Systems 23(12) (2012), 2231–2244.

61.

[61]

Zhu,

Wang,

Hu,

G.-J.

Ahn,

Hu and

S.S.

Yau, Efficient provable data possession for hybrid clouds, in: Proceedings of the 17th ACM Conference on Computer and Communications Security, CCS’10, ACM, New York, NY, USA, 2010, pp. 756–758.

Delegated integrity check for hierarchical cloud data

Abstract

Keywords

1. Introduction

3. Preliminary

3.1. Complexity assumption

4.1. Formal model

4.2. Threat model

4.2.1. Proof unforgeability

Definition 3. A delegated PDP/POR scheme Π satisfies the requirement of proof unforgeability if no probabilistic polynomial-time adversary has non-negligible advantage to win the proof unforgeability game Game Π PF − UF . 4.2.2. Proof indistinguishability

Definition 4. A delegated PDP/POR scheme Π satisfies the requirement of proof indistinguishability if no probabilistic polynomial-time adversary has non-negligible advantage to win the proof indistinguishability game Game Π PF − IND . 4.2.3. Delegation key unforgeability

5.1. Construction

5.1.2. Performance

Table 2 Computation cost

5.2.1. Proof unforgeability

6.1. Construction

6.1.1. Correctness

6.1.2. Performance

Table 6 Computation cost

6.2.1. Proof unforgeability

7.1. Elliptic curve and block size

Table 10 Elliptic curve suggestion

8. Conclusion

Footnotes

Acknowledgments

References

Definition 3.
A delegated PDP/POR scheme Π satisfies the requirement of proof unforgeability if no probabilistic polynomial-time adversary has non-negligible advantage to win the proof unforgeability game ${Game}_{Π}^{PF - UF}$ .

4.2.2. Proof indistinguishability

Definition 4.
A delegated PDP/POR scheme Π satisfies the requirement of proof indistinguishability if no probabilistic polynomial-time adversary has non-negligible advantage to win the proof indistinguishability game ${Game}_{Π}^{PF - IND}$ .

4.2.3. Delegation key unforgeability

Table 2
Computation cost

Table 6
Computation cost

Table 10
Elliptic curve suggestion