MD-POR: Multisource and Direct Repair for Network Coding-Based Proof of Retrievability

Abstract

When data owners publish their data to a cloud storage, data integrity and availability become typical problems because the cloud servers are never trusted. To address these problems, researchers proposed the Proof of Retrievability (POR) protocol which allows a verifier to check and repair the data stored in the cloud servers. Based on the POR protocol, the network coding technique is commonly applied to increase the efficiency in data transmission and data repair. However, most previous schemes neither consider a practical scenario nor use the network coding efficiently. In this paper, a lightweight network coding-based POR scheme, called MD-POR (Multisource and Direct Repair for Proof of Retrievability) is proposed. Unlike previous schemes, the proposed MD-POR scheme allows multiple clients who have different secret keys to participate in the scheme. Moreover, the MD-POR scheme supports the direct repair feature in which a corrupted data can be recovered by the servers without burdening the clients. The MD-POR scheme also supports public authentication feature in which a third party auditor is employed to check the servers, and the client is thus free of the responsibility of periodically checking the servers. Furthermore, the MD-POR scheme is constructed based on a symmetric key setting.

1. Introduction

Since data is increasing exponentially, database owners trend to publish their data to storage providers called clouds in order to reduce the burden of data storage and maintenance. Clients can thus access, manage, and share their data from anywhere via the Internet. However, such service providers are untrustworthy and present three basic challenges to data security: (i) integrity, (ii) availability, and (iii) confidentiality. In confidentiality, there are two research approaches: the cryptographic approach (e.g., RSA) and the information-theoretic approach (e.g., secret sharing scheme). Compared to the cryptographic confidentiality approach, the information-theoretic confidentiality approach achieves a security level determined by a threshold. We choose the information-theoretic approach because our security analysis derives purely from information theory. In this paper, we deal with integrity, availability and information-theoretic confidentiality.

To check the cloud servers, researchers proposed the Proof of Retrievability (POR) protocol [1–3] that enables the servers (provers) to demonstrate to the verifier whether the data stored in the servers is intact and available and enables the clients to recover the data when an error is detected. Based on the POR protocol, the integrity and availability assurance are mainly based on three techniques: replication [4], erasure coding [5], and network coding [6–9]. In the replication technique, the client stores file replicas in each server. When a corrupted server is detected, the client uses one of the healthy replicas to repair it. However, the drawback of this technique is high storage cost because the client must store a whole file in each server. Erasure coding technique is then applied to reduce the storage cost. Erasure coding allows the client to store file blocks in each server redundantly instead of file replica as replication. However, when the corrupted data is repaired, the client has to retrieve the entire original file before the client generates new coded blocks. Therefore, its computation and communication costs are increased during data repair. Network coding technique is then applied to improve the efficiency in the data repair. The main advantage of network coding is that the client does not need to retrieve the entire file before the client generates new coded blocks. Consequently, in this paper, we focus on the network coding technique. Our goal is to construct a network-coding POR which satisfies the following aims.

• (i)

Practical scenario: the system should consist of multiple clients, each client keeps a different secret key. This is because in many distributed storage systems today such as Dropbox, each client has a personal data; and hence, each client should use his own secret key to satisfy integrity and confidentiality.

(ii)

Lightweight: firstly, the clients should be free of two heaviest tasks: periodically checking the servers and repairing the corrupted servers. Secondly, the system should be constructed in a symmetric key setting which is a well-known lightweight cryptography rather than an asymmetric key setting.

Network Coding-Based POR Schemes. A few notable network-coding PORs were proposed. Dimakis et al. [10] were the first applying network coding to the distributed storage system. Li et al. [11] proposes a tree-structure data regeneration for the network coding to optimize network bandwidth by using a maximum spanning tree. Chen et al. [12] then adapted the scheme of Dimakis et al. to propose the Remote Data Checking for Network Coding-based distributed storage system (RDC-NC) scheme which provides an elegant data repair by recoding encoded blocks in healthy servers during repair. Cao et al. [13] applied the Luby transform (LT) code for reducing the computation cost because the LT code is a special network code which works in the finite field of order two and only uses exclusive-OR (XOR) operation. Chen et al. [14] proposed the NC-Cloud scheme to improve the cost-effectiveness of repair using the functional minimum storage regenerating (FMSR) code and lighten the encoding requirement of storage nodes during repair. However, all these schemes cannot hold our aims. These system models only have a single client. Furthermore, the check and repair phases in these schemes bring a lot of burden to the client because (i) the client has to periodically check the servers and (ii) when a corrupted server is detected, the healthy servers provide their blocks to the client; the client then has to verifies them, computes the new blocks, and sends these new blocks to the new server. Le and Markopoulou after that proposed the NC-Audit scheme [15] in which a third party auditor is employed and is delegated the responsibility to check the servers instead of the client. The authors also discussed a new repair mechanism in which the new server can compute the new blocks by itself without the need of the client. We call that mechanism as direct repair. Unfortunately, their direct repair is not completed because they mainly focused on how to prevent the data leakage from the third party auditor. Furthermore, their scheme is constructed in an asymmetric key setting and does not deal with multiple clients.

Contribution. In this paper, a new network-coding POR named as MD-POR is proposed. To the best of our knowledge, we are the first to propose a symmetric key setting-based direct repair for the POR; furthermore, the proposed MD-POR scheme also supports multiclient and public authentication.

• (i)

Direct Repair. If a corrupted server is detected, the healthy servers are required to provide their coded blocks directly to the new server instead of sending these coded blocks back to the client. Afterwards, the new server verifies the coded blocks it received and computes the new coded blocks for itself without disturbing the client. This mechanism can reduce the communication cost and the burden for the client.

(ii)

Multiclient. To enable multiple clients, our method does not simply duplicate the process of a single client to multiple parallel processes for multiple clients. Instead, in the proposed MD-POR scheme, the processes of multiple clients are mixed together without loosing the data confidentiality of individual clients. To enable such a multiclient setting, we employ the InterMac technique [16] which was proposed for network scenario. The InterMac technique allows multiple sources to send their packages to the network using different secret keys and allows the recipients to verify the packages they received.

(iii)

Symmetric Key Setting. The MD-POR scheme uses only secret keys without any public key, unlike an asymmetric key setting.

(iv)

Public Authentication. Not only the client but also any entity who has a given information can check the cloud servers while learning nothing about the secret key of each client. We employ a third party auditor (TPA) on behalf of the clients to check the servers periodically. By delegating the responsibility of checking the servers to the TPA, the clients are free of the burden of checking the servers. Otherwise, for the nonexistence of TPA, the clients have to periodically check the servers, and the public authentication feature cannot be supported because only the clients can check the servers. Although the MD-POR scheme supports public authentication, our method does not use an asymmetric key setting.

Organization. The system model, the backgrounds of the Proof of Retrievability, the network coding technique, the InterMac technique, the notations, and definitions are described in Section 2. The adversarial model is presented in Section 3. The MD-POR scheme is proposed in Section 4. The security analysis and efficiency analysis are given in Section 5 and Section 6, respectively. The performance evaluation of the MD-POR scheme is shown in Section 7. The conclusion and future work are drawn in Section 8.

2. Preliminaries

2.1. System Model

The system model of the MD-POR scheme is depicted in Figure 1. There are three types of entities.

• (i)

Clients: these entities have data to be stored in the cloud and rely on the cloud for data storage, computation, and maintenance. These clients can be either enterprises or individual customers.

(ii)

Cloud servers: the cloud servers are managed and monitored by a cloud service provider to accommodate a service of data storage and have significant and unlimited storage space and computation resources. In the cloud storage service, the clients can store their data into a set of servers in a simultaneous and distributed manner.

(iii)

Third party auditor (TPA): this entity is delegated the responsibility to check the servers on behalf of the clients. The TPA is assumed to be trusted to perform the task of periodically checking the servers.

Figure 1

System model.

Originally, the system model which consists of only the client and the servers without the TPA is enough for data check. To enable the public authentication feature, the TPA is employed with an assumption that the TPA is a honest-but-curious entity. Several previous papers also use the same assumption of the TPA, for example, [15, 17–19].

2.2. Proof of Retrievability (POR)

To check the servers, researchers proposed the Proof of Retrievability (POR) [1–3] which is a challenge-response protocol between a verifier (client) and a prover (server). The POR has four phases as follows.

• (1)

keygen $({\mathrm{1}}^{\lambda })$ : given a security parameter λ, the client runs this algorithm to generate a secret key ( $\mathrm{s}\mathrm{k}$ ) and a public key ( $\mathrm{p}\mathrm{k}$ ). For the symmetric key setting, $\mathrm{p}\mathrm{k}$ is set to be  $\mathrm{n}\mathrm{u}\mathrm{l}\mathrm{l}$ .

(2)

encode $(\mathrm{s}\mathrm{k},F)$ : the client runs this algorithm to encode an original file (F) to an encoded file ( $F^{\prime }$ ) and then sends $F^{\prime }$ to the server to store.

(3)

$\mathrm{c}\mathrm{h}\mathrm{e}\mathrm{c}\mathrm{k}(\mathrm{s}\mathrm{k})$ : the client uses his secret key $\mathrm{s}\mathrm{k}$ to generate a challenge (c) and sends c to the server. The server then computes a response (r) and sends r back to the client. Finally, the client verifies whether the file F is intact based on c and r.

(4)

repair(): the client runs this algorithm only when a failure is detected in the check phase. The technique of the repair phase depends on each specific technique, for example, replication, erasure coding, or network coding.

To be suitable for our system model, we modify the POR such that the verifier is the TPA and there are multiple clients as follows.

• (1)

keygen $({\mathrm{1}}^{\lambda })$ : given a security parameter λ, the algorithm generates a set of secret keys $\{{\mathrm{s}\mathrm{k}}_i{\}}_{i\in \{\mathrm{1},\dots ,s\}}$ for s clients and a secret key κ for the TPA.

(2)

encode $({\mathrm{s}\mathrm{k}}_i,F_i)$ : each client i uses his secret key ${\mathrm{s}\mathrm{k}}_i$ to encode his original file $F_i$ to an encoded file $F_i^{\prime }$ and then sends $F_i^{\prime }$ to the servers. Each server then linearly combines all $F_i^{\prime }$ ( $i\in \{\mathrm{1},\dots ,s\}$ ) and stores the combined blocks.

(3)

check $(\kappa )$ : the TPA uses his key κ to generate a challenge c and sends c to the servers. Each server then computes a response r and sends r back to the TPA. Finally, the TPA verifies whether each $F_i$ is intact or not.

(4)

repair(): this algorithm is executed when a failure is detected in the check phase. The technique of the repair phase depends on each specific scheme.

2.3. Network Coding

Network coding [6–9] is commonly used in network transmission to obtain a good trade-off in term of bandwidth and data repair. Network coding is proposed firstly for the network scenario. It then is applied to the distributed storage system scenario.

Fundamental Concept. In the network scenario, suppose that a source node C wants to send its message to a receiver node R. Before transmitting, C breaks the message into m blocks $v_{\mathrm{1}},\dots ,v_m$ ; each file block belongs to ${\mathbb{F}}_q^n$ where ${\mathbb{F}}_q^n$ denotes a n-dimensional vector space over a finite field $\mathbb{F}$ with a prime q. C augments each file block $v_i$ ( $i\in \{\mathrm{1},\dots ,m\}$ ) with a vector of length m in which a single “1” is in the ith position and “0's are elsewhere. Let $w_{\mathrm{1}},\dots ,w_m$ be the augmented blocks. Each augmented block has the following form:

$$\begin{array}{cc}& w_i=\left(v_i,\stackrel{m}{\overbrace{\underset{i}{\underbrace{\mathrm{0},\dots ,\mathrm{0,1}}},\mathrm{0},\dots ,\mathrm{0}}}\right)\in {\mathbb{F}}_q^{n+m}.\end{array}$$

(1)

These augmented blocks are then sent as packets to the network. When an intermediate node I in the network receives t packets, I will generates t coefficients, linearly combines t packets using the generated coefficients, and transmits the result to its adjacent nodes. Consequently, the receiver node R can receive combinations of all augmented blocks. R can recover m augmented blocks using any set of m combinations. Suppose that R receives m packages $y_{\mathrm{1}},\dots ,y_m\in {\mathbb{F}}_q^{n+m}$ , and R solves all m augmented blocks $w_{\mathrm{1}},\dots ,w_m\in {\mathbb{F}}_q^{n+m}$ using the accumulated coefficients which are contained in the last m coordinates of each package y. Afterwards, the file blocks $v_{\mathrm{1}},\dots ,v_m$ can be obtained from the first coordinate of each augmented block. Finally, the original message can be reconstructed by concatenating all file blocks.

Application in Distributed Storage System. In the network scenario as described above, there are multiple types of entities: source node, intermediate nodes, and receiver node. However, when the network coding is applied to the distributed storage system scenario, there are two types of entities: a client and servers. Suppose that a client has the original file F which consists of m file blocks ( $v_{\mathrm{1}},\dots ,v_m$ ). The client wants to store redundantly encoded blocks in the servers in a way that the client can reconstruct the original file F and can repair the encoded blocks in a corrupted server. From these file blocks, the client firstly creates m augmented blocks ( $w_{\mathrm{1}},\dots ,w_m$ ). The client then chooses m coding coefficients ( ${\alpha }_{\mathrm{1}},\dots ,{\alpha }_m\in {\mathbb{F}}_q$ ) and computes coded blocks using the linear combination as $c={\sum }_{i=\mathrm{1}}^m‍{\alpha }_i·w_i$ and then stores these coded blocks in the servers. To reconstruct the original file F, any m coded blocks are required to solve m augmented blocks $w_{\mathrm{1}},\dots ,w_m$ using the accumulated coefficients contained in the last m coordinates of each coded block. After these m augmented blocks are solved, m file blocks $v_{\mathrm{1}},\dots ,v_m$ are obtained from the first coordinate of each augmented block. Finally, the original file F is reconstructed by concatenating the file blocks. Note that the matrix consisting of the coefficients used to construct any m coded blocks should have full rank. Koetter and Medard [20] proved that if the prime q is chosen large enough and the coefficients are chosen randomly, the probability for the matrix having full rank is high. Once a corrupted server is detected, the client repairs it as follows: the client retrieves coded blocks from the healthy servers and linearly combines them to regenerate new coded blocks. An example about the data repair of network coding is given in Figure 2.

Figure 2

From three augmented blocks $\{w_{\mathrm{1}},w_{\mathrm{2}},w_{\mathrm{3}}\}$ , the client computes six coded blocks and stores two coded blocks in each of servers $S_{\mathrm{1}}$ , $S_{\mathrm{2}}$ , $S_{\mathrm{3}}$ . Suppose that $S_{\mathrm{3}}$ is corrupted, the client requires $S_{\mathrm{1}}$ and $S_{\mathrm{2}}$ to create new blocks using linear combination, and then the client mixes them using linear combination to obtain two new coded blocks and stores them in the new server.

2.4. InterMac

Before describing how the InterMac works, we explain why it is used in our proposed MD-POR scheme as follows. We consider a network in which multiple sources are simultaneously supported and each source owns a different secret key. The data of each source cannot be checked alone. Instead, each source uses the secret key to compute an additional information which is Message Authentication Code (MAC) for each data block. A MAC is also called as tag. Each source then transmits the packets consisting of the data blocks and the corresponding tags to the next adjacent node in the network. A node in the network will linearly combine the received blocks and the homomorphic tags. Herein lies the difficulty of the task: when a recipient node receives a packet, how can this node verify the received linear blocks based on the linear homomorphic tags without any information about any of the secret keys. The traditional methods, that is, MAC or HMAC, are inadequate to solve this task. Some recent schemes related to this problem have been proposed, for example, [21–23]; unfortunately, they all use an asymmetric key setting, which is not our aim.

The InterMac technique [16] is a suitable technique to generate such secret keys for multiple sources. The characteristic of this technique is that the key of the source ${\mathcal{C}}_p$ ( $p\in \{\mathrm{1},\dots ,s\}$ where s denotes the number of sources) is orthogonal to all the augmented blocks which do not belong to ${\mathcal{C}}_p$ . This characteristic can help the verifier check the received packets without needing the information on any of the secret keys.

Construction. Let $w_{\mathrm{11}},\dots ,w_{sg}\in {\mathbb{F}}_q^{n+m}$ be the augmented blocks that have span π, and let them represent as row vectors (where s denotes the number of sources, g denotes the number of file blocks per source, and $m=s·g$ ). For each $p\in \{\mathrm{1},\dots ,s\}$ , let $M_p$ be the matrix whose rows are vectors in the following set:

$$\begin{array}{cc}& \left\{w_{ij}\hspace{0.17em}|\hspace{0.17em}i=\mathrm{1},\dots ,s;\hspace{0.17em}\hspace{0.17em}i\ne p;\hspace{0.17em}\hspace{0.17em}j=\mathrm{1},\dots ,g\right\}.\end{array}$$

(2)

In other words, $M_p$ is the matrix consisting of the augmented blocks of all other sources except ${\mathcal{C}}_p$ .  $\mathsf{r}\mathsf{a}\mathsf{n}\mathsf{k}(M_p)=m-g$ . Let ${\pi }_{M_p}$ denote the space spanned by the rows of $M_p$ .

The null space of $M_p$ , denoted as ${\pi }_{M_p}^{\perp }$ , is the set of all row vectors $z\in {\mathbb{F}}_q^{n+m}$ for which $M_p{z}^T=\mathrm{0}$ . For any $(m-g)\times (n+m)$ matrix $M_p$ , we have

$$\begin{array}{cc}& \mathsf{r}\mathsf{a}\mathsf{n}\mathsf{k}\left(M_p\right)+\mathsf{n}\mathsf{u}\mathsf{l}\mathsf{l}\mathsf{i}\mathsf{t}\mathsf{y}\left(M_p\right)=n+m\end{array}$$

(3)

known as rank-nullity theorem, where  $\mathrm{n}\mathrm{u}\mathrm{l}\mathrm{l}\mathrm{i}\mathrm{t}\mathrm{y}(M_p)$ is the dimension of ${\pi }_{M_p}^{\perp }$ . Hence,

$$\begin{array}{cc}& \mathsf{d}\mathsf{i}\mathsf{m}\left({\pi }_{M_p}^{\perp }\right)=n+m-\left(m-g\right)=n+g.\end{array}$$

(4)

Let $b_{\mathrm{1}},\dots ,b_{n+g}\in {\mathbb{F}}_q^{n+m}$ be a basis of ${\pi }_{M_p}^{\perp }$ . This basis can be found by solving $M_p{z}^T=\mathrm{0}$ . Let F be a pseudorandom function (PRF): $\bar{\mathcal{K}}\times ([\mathrm{1},s]\times [\mathrm{1},n+g])\to {\mathbb{F}}_q$ . A key $k_p$ for the source ${\mathcal{C}}_p$ is computed as follows:

• (i)

$r_i\leftarrow F(k,p,i)\in {\mathbb{F}}_q,\hspace{0.17em}\hspace{0.17em}\forall i\in \{\mathrm{1},\dots ,n+g\}$ ;

(ii)

$k_p\leftarrow {\sum }_{i=\mathrm{1}}^{n+g}‍r_i{b}_i\in {\mathbb{F}}_q^{n+m}$ .

Eventually, a key set $\{k_{\mathrm{1}},\dots ,k_s\}$ is generated in which each key $k_p$ where $p\in \{\mathrm{1},\dots ,s\}$ is constructed as above.

2.5. Notations and Definitions

Throughout this paper, the list of notations and definitions is given in Notation section.

3. Adversarial Model

In the MD-POR scheme, only the clients are trusted because they are the data owners. The following entities are untrusted and considered to be adversaries:

• (i)

attackers outside the system;

(ii)

the cloud servers in the system;

(iii)

the TPA in the system (the TPA is assumed not to collude with the servers. We explained about this assumption in Section 2.1).

Concretely, the adversaries can perform the following the attacks.

3.1. Mobile Attack

This attack is performed by an adversary $\mathcal{A}$ outside the system. $\mathcal{A}$ potentially corrupts all the servers across the full system lifetime. A restriction on $\mathcal{A}$ is that he/she can control only ( $h-l$ ) out of h servers in any given time step. Let epoch denote a given time step. In each epoch, the servers are checked. If a corruption is detected on a certain server, the blocks stored in that corrupted server will be repaired from redundancy in the intact servers. Without the server checks, the adversary $\mathcal{A}$ can corrupt all the servers of the system in $h/\left(h-l\right)$ epochs.

3.2. Curious Adversary

This attack is performed by the TPA or a new server. In the check phase, the TPA is given a key κ which is constructed from all the secret keys of the clients. In the repair phase, a new server is given another key ${\kappa }^{\prime }$ which is also constructed from all the secret keys of the clients. When they are given their keys, these adversaries try to learn the secret keys because once all secret keys are obtained, these adversaries can fake a valid response when they are checked.

3.3. Response Forgery

This forgery is performed by the servers. In the check phase, the verifier checks all the servers to ensure that they are not corrupted. Each server has to send a response to the verifier in order to demonstrate that the server is healthy. However, a checked server may forge the response to deceive the verifier. If the forged response from the adversarial server satisfies the verification, that server can pass the check phase.

3.4. Pollution Attack

This attack is performed by the servers. The purpose of this attack is to break the linear independence of the encoded blocks. In a network, if a node is malicious and forward invalid package, receivers then obtain multiple packets and cannot tell which of their received packets are corrupt. In other words, the purpose of this attack is to inject invalid packets to prevent data recover. In the POR, this attack happens when a malicious server uses correct data to pass the check phase but then provides invalid data in the repair phase. For example, the client encodes the augmented blocks $w_{\mathrm{1}}$ , $w_{\mathrm{2}}$ , and $w_{\mathrm{3}}$ to six coded blocks: $c_{\mathrm{11}}$ , $c_{\mathrm{12}}$ (stored in the server $S_{\mathrm{1}}$ ), $c_{\mathrm{21}}$ , $c_{\mathrm{22}}$ (stored in the server $S_{\mathrm{2}}$ ), and $c_{\mathrm{31}},c_{\mathrm{32}}$ (stored in the server $S_{\mathrm{3}}$ ). In the check phase, suppose that $S_{\mathrm{3}}$ is detected as being corrupted. Then, in the repair phase, $S_{\mathrm{3}}$ should be repaired using two coded blocks: $c_{\mathrm{31}}^{\prime }$ (which is a linear combination of $c_{\mathrm{11}}$ and $c_{\mathrm{12}}$ ) and $c_{\mathrm{32}}^{\prime }$ (which is a linear combination of $c_{\mathrm{21}}$ and $c_{\mathrm{22}}$ ). However, at this time, $S_{\mathrm{1}}$ is malicious without being detected because this time is the repair phase, not the check phase any more. The client still thinks $S_{\mathrm{1}}$ is healthy; thus, to recover $S_{\mathrm{3}}$ , the client requests coded blocks from $S_{\mathrm{1}}$ and $S_{\mathrm{2}}$ but $S_{\mathrm{1}}$ will provide an invalid coded blocks $c_{\mathrm{31}}^{\prime \prime }$ to the client instead of $c_{\mathrm{31}}^{\prime }$ .

4. The Proposed MD-POR Scheme

Before describing the proposed MD-POR scheme in detail, the technical roadmap is depicted in Figure 3. The file blocks are used to generate the augmented blocks. Then, the augmented blocks are combined with random values to compute the keys. Meanwhile, the augmented blocks are linearly combined into the coded blocks using the network coding. Finally, the coded blocks are tagged using the keys. The coded blocks and the tags are the outputs. The network coding is used because it is related to the repair feature (Section 2.3). The InterMac is used because it is related to the multiuser feature (Section 2.4). Both the network coding and the InterMac are constructed based on linear combinations; therefore, they are suitable to combine together in the proposed scheme.

Figure 3

Technical roadmap.

Let ${\mathcal{C}}_{\mathrm{1}},\dots ,{\mathcal{C}}_s$ be the set of s clients. Each client ${\mathcal{C}}_i$ ( $i\in \{\mathrm{1},\dots ,s\}$ ) keeps a secret key $k_i$ and has a file $F_i=(v_{i\mathrm{1}},\dots ,v_{ig})$ where g is the number of file blocks. Each file block $v_{ij}\in {\mathbb{F}}_q^n$ ( $j\in \{\mathrm{1},\dots ,g\})$ . ${\mathcal{C}}_i$ creates g augmented blocks ( $w_{i\mathrm{1}},\dots ,w_{ig}$ ) from g file blocks ( $v_{i\mathrm{1}},\dots ,v_{ig}$ ). Each augmented block $w_{ij}$ has the form as in [16]

$$\begin{array}{cc}& w_{ij}=\left(v_{ij},\underset{m=sg}{\underbrace{\underset{g\left(i-\mathrm{1}\right)}{\underbrace{\mathrm{0},\dots ,\mathrm{0}}},\underset{g}{\underbrace{\stackrel{j}{\overbrace{\mathrm{0},\dots ,\mathrm{0,1}}},\mathrm{0},\dots ,\mathrm{0}}},\underset{g\left(s-i\right)}{\underbrace{\mathrm{0},\dots ,\mathrm{0}}}}}\right)\in {\mathbb{F}}_q^{n+m},\end{array}$$

(5)

where $i\in \{\mathrm{1},\dots ,s\}$ , $j\in \{\mathrm{1},\dots ,g\}$ , and $m=sg$ .

Each client ${\mathcal{C}}_i$ uses his secret key $k_i$ to compute the tag $t_{ij}$ for each augmented blocks $w_{ij}$ . The augmented blocks and the tags are then linearly combined and transmitted to all the servers. In every epoch, when the servers are checked by the TPA, the servers have to combine the coded blocks and the tags again and send them back to the TPA. The TPA can finally verify the aggregated coded blocks and the tags even though the TPA does not know any secret key $\{k_i\}$ ( $i\in \{\mathrm{1},\dots ,s\}$ ).

The proposed MD-POR scheme is now described in detail via each phase of the POR as follows.

4.1. Keygen

4.1.1. Keys for the Clients (Keygen1)

Each key $k_p$ of the client ${\mathcal{C}}_p$ ( $p\in \{\mathrm{1},\dots ,s\}$ ) is constructed in such a way that $k_p$ is orthogonal to all the augmented blocks which do not belong to ${\mathcal{C}}_p$ . In a formal statement, $k_p$ is constructed as

$$\begin{array}{cc}& \forall i\in \left\{\mathrm{1},\dots ,s\right\},\hspace{0.17em}\hspace{0.17em}i\ne p,\hspace{0.17em}\hspace{0.17em}p\in \left\{\mathrm{1},\dots ,s\right\},\hspace{1em}{w}_{ij}·k_p=\mathrm{0}.\end{array}$$

(6)

Using the InterMac (Section 2.4), a key set $\{k_{\mathrm{1}},\dots ,k_s\}$ is created. Then, each $k_p\in {\mathbb{F}}_q^{n+m}$ is assigned to the client ${\mathcal{C}}_p$ as the secret key, and the sum of all the keys $\kappa =k_{\mathrm{1}}+\cdots +k_s\in {\mathbb{F}}_q^{n+m}$ are assigned to the TPA via a secure channel. The security of the secret keys will be proved later.

4.1.2. Dynamic Keys for a New Server (Keygen2)

When a repair phase is executed, the new server will be given a key ${\kappa }^{\prime }=(k_{\mathrm{1}}+\cdots +k_s)+k_{\mathrm{r}\mathrm{e}\mathrm{p}\mathrm{a}\mathrm{i}\mathrm{r}}=\kappa +k_{\mathrm{r}\mathrm{e}\mathrm{p}\mathrm{a}\mathrm{i}\mathrm{r}}$ . The new server will use the key ${\kappa }^{\prime }$ to check pollution attack during the repair phase. κ is already computed in Keygen1. Only $k_{\mathrm{r}\mathrm{e}\mathrm{p}\mathrm{a}\mathrm{i}\mathrm{r}}$ is different in each repair time. This is to ensure that an adversary cannot attack the new server to obtain $k_{\mathrm{r}\mathrm{e}\mathrm{p}\mathrm{a}\mathrm{i}\mathrm{r}}$ for passing the pollution attack check in the later repair phases (we thereafter explain in Section 5.4). When $k_{\mathrm{r}\mathrm{e}\mathrm{p}\mathrm{a}\mathrm{i}\mathrm{r}}$ is constructed in the first time, the basis of $b_{\mathrm{1}},\dots ,b_{n+g}$ is computed and saved for the later times. In the next repair times, the basis will be reused to save the computation cost, and only the random coefficients $r_i$ are regenerated again to compute $k_p$ .

$r_{\mathrm{r}\mathrm{e}\mathrm{p}\mathrm{a}\mathrm{i}\mathrm{r}}$ has to be orthogonal to all augmented blocks of all the clients. Keygen2 is quite similar to Keygen1. However, the different thing is that $p\notin \{\mathrm{1},\dots ,s\}$ , p is randomly chosen in ${\mathbb{F}}_q$ such that $p>s$ in every repair time. Since $r_{\mathrm{r}\mathrm{e}\mathrm{p}\mathrm{a}\mathrm{i}\mathrm{r}}$ is orthogonal to all augmented blocks of all the clients, $M_p$ is now the matrix consisting of all the augmented blocks of all the clients. Put differently, the rows of $M_p$ are vectors in the following set:

$$\begin{array}{cc}& \left\{w_{ij}\hspace{0.17em}|\hspace{0.17em}i=\mathrm{1},\dots ,s;\hspace{0.17em}\hspace{0.17em}j=\mathrm{1},\dots ,g\right\}.\end{array}$$

(7)

The set consists of $m=sg$ augmented blocks and each augmented block belongs to ${\mathbb{F}}_q^{n+m}$ . For the $m\times (n+m)$ matrix $M_p$ , the rank-nullity theorem yields

$$\begin{array}{cc}& \mathsf{r}\mathsf{a}\mathsf{n}\mathsf{k}\left(M_p\right)+\mathsf{n}\mathsf{u}\mathsf{l}\mathsf{l}\mathsf{i}\mathsf{t}\mathsf{y}\left(M_p\right)=n+m.\end{array}$$

(8)

Since   $\mathsf{r}\mathsf{a}\mathsf{n}\mathsf{k}(M_p)=m$ , the  $\mathrm{n}\mathrm{u}\mathrm{l}\mathrm{l}\mathrm{i}\mathrm{t}\mathrm{y}(M_p)$ is  $\mathrm{n}\mathrm{u}\mathrm{l}\mathrm{l}\mathrm{i}\mathrm{t}\mathrm{y}(M_p)=n+m-m=n$ . The basis of the null space of $M_p$ is now $\{b_{\mathrm{1}},\dots ,b_n\}$ . Let $F^{\prime }$ be another PRF: $\bar{\mathcal{K}}\times (\mathcal{P}\times [\mathrm{1},n])\to {\mathbb{F}}_q$ , where $\mathcal{P}$ denotes the domain of p's space. The following steps are used to generate the key $k_p$ :

• (i)

$r_i\leftarrow F(k,p,i)\in {\mathbb{F}}_q,\hspace{0.17em}\hspace{0.17em}\forall i\in \{\mathrm{1},\dots ,n\}$ ;

(ii)

$k_p\leftarrow {\sum }_{i=\mathrm{1}}^n‍r_i{b}_i\in {\mathbb{F}}_q^{n+m}$ .

Let $k_{\mathrm{r}\mathrm{e}\mathrm{p}\mathrm{a}\mathrm{i}\mathrm{r}}$ denote $k_p$ (to distinguish with the notation $k_p$ from the Keygen1). The Keygen2 is only executed and ${\kappa }^{\prime }=\kappa +k_{\mathrm{r}\mathrm{e}\mathrm{p}\mathrm{a}\mathrm{i}\mathrm{r}}$ is given to a new server only if a repair phase happens. The key κ is already computed in the Keygen1 as a static information, and only $k_{\mathrm{r}\mathrm{e}\mathrm{p}\mathrm{a}\mathrm{i}\mathrm{r}}$ is different in each repair time.

4.2. Encode

Step 1.

Each client ${\mathcal{C}}_i\hspace{0.17em}\hspace{0.17em}(i\in \{\mathrm{1},\dots ,s\})$ computes g tags for g augmented blocks:

$$\begin{array}{cc}& \forall i\in \left\{\mathrm{1},\dots ,s\right\},\hspace{0.17em}\hspace{0.17em}\forall j\in \left\{\mathrm{1},\dots ,g\right\}:t_{ij}=w_{ij}·k_i.\end{array}$$

(9)

Step 2.

Each client ${\mathcal{C}}_i\hspace{0.17em}\hspace{0.17em}(i\in \{\mathrm{1},\dots ,s\})$ linearly combines the augmented blocks and the corresponding tags:

$\forall i\in \{\mathrm{1},\dots ,s\}$ :

• (i)

$\forall j\in \{\mathrm{1},\dots ,g\}$ , generate g coefficients: ${\alpha }_{ij}\stackrel{\mathrm{r}\mathrm{a}\mathrm{n}\mathrm{d}}{\leftarrow }{\mathbb{F}}_q$ ;

(ii)

compute coded block: $w_{{\mathcal{C}}_i}={\sum }_{j=\mathrm{1}}^g‍{\alpha }_{ij}·w_{ij}$ ;

(iii)

compute tag: $t_{{\mathcal{C}}_i}={\sum }_{j=\mathrm{1}}^g‍{\alpha }_{ij}·t_{ij}$ .

Step 3.

Each client ${\mathcal{C}}_i$ sends the pair of $(w_{{\mathcal{C}}_i},t_{{\mathcal{C}}_i})$ to all h servers ( $S_{\mathrm{1}},\dots ,S_h$ ). Each server $S_x$ where $x\in \{\mathrm{1},\dots ,h\}$ creates d pairs of coded block $c_{xy}$ and corresponding tag $t_{xy}$ where $y\in \{\mathrm{1},\dots ,d\}$ :

$\forall x\in \{\mathrm{1},\dots ,h\},y\in \{\mathrm{1},\dots ,d\}$ , $S_x$ computes:

• (i)

$\forall i\in \{\mathrm{1},\dots ,s\}$ , generate s coefficients: ${\beta }_{xyi}\stackrel{\mathrm{r}\mathrm{a}\mathrm{n}\mathrm{d}}{\leftarrow }{\mathbb{F}}_q$ ;

(ii)

compute coded block: $c_{xy}={\sum }_{i=\mathrm{1}}^s‍{\beta }_{xyi}·w_{{\mathcal{C}}_i}$ ;

(iii)

compute tag: $t_{xy}={\sum }_{i=\mathrm{1}}^s‍{\beta }_{xyi}·t_{{\mathcal{C}}_i}$ .

4.3. Check

The TPA is assigned the check responsibility. The TPA uses the key $\kappa =k_{\mathrm{1}}+\cdots +k_s$ to check h servers periodically. Note that the TPA is only given the sum κ without learning each component $k_i$ where $i=\{\mathrm{1},\cdots ,s\}$ . Assume that the TPA does not collude with any server:

$\forall x\in \{\mathrm{1},\dots ,h\}$ :

• (i)

$S_x$ computes:

• (a)

$\forall y\in \{\mathrm{1},\dots ,d\}$ ; generate d coefficients ${\gamma }_{xy}\stackrel{\mathrm{r}\mathrm{a}\mathrm{n}\mathrm{d}}{\leftarrow }{\mathbb{F}}_q$ ;

(b)

combine coded blocks: $c_x={\sum }_{y=\mathrm{1}}^d‍c_{xy}·{\gamma }_{xy}$ ;

(c)

combine tags: $t_x={\sum }_{y=\mathrm{1}}^d‍t_{xy}·{\gamma }_{xy}$ ;

(ii)

$S_x$ sends $\{c_x,t_x\}$ to the TPA;

(iii)

TPA computes $t_x^{\prime }=c_x·\kappa$ ;

(iv)

TPA verifies: $t_x=t_x^{\prime }$ (∗), and then returns  $\mathrm{t}\mathrm{r}\mathrm{u}\mathrm{e}$ (this means that $S_x$ is healthy), otherwise returns  $\mathrm{f}\mathrm{a}\mathrm{l}\mathrm{s}\mathrm{e}$ .

Correctness of the Verification (∗). Consider

$$\begin{array}{l}{t}_x={\displaystyle \sum }_{y=\mathrm{1}}^d‍t_{xy}·{\gamma }_{xy}\\ ={\displaystyle \sum }_{y=\mathrm{1}}^d‍\hspace{0.17em}{\displaystyle \sum }_{i=\mathrm{1}}^s‍{\gamma }_{xy}{\beta }_{xyi}{t}_{{\mathcal{C}}_i}\\ ={\displaystyle \sum }_{y=\mathrm{1}}^d‍\hspace{0.17em}{\displaystyle \sum }_{i=\mathrm{1}}^s‍\hspace{0.17em}{\displaystyle \sum }_{j=\mathrm{1}}^g‍{\gamma }_{xy}{\beta }_{xyi}{\alpha }_{ij}{t}_{ij}\\ ={\displaystyle \sum }_{y=\mathrm{1}}^d‍\hspace{0.17em}{\displaystyle \sum }_{i=\mathrm{1}}^s‍\hspace{0.17em}{\displaystyle \sum }_{j=\mathrm{1}}^g‍{\gamma }_{xy}{\beta }_{xyi}{\alpha }_{ij}{w}_{ij}{k}_i,\\ t_x^{\prime }=c_x·\kappa \\ ={\displaystyle \sum }_{y=\mathrm{1}}^d‍{\gamma }_{xy}{c}_{xy}\left(k_{\mathrm{1}}+\cdots +k_s\right)\\ ={\displaystyle \sum }_{y=\mathrm{1}}^d‍\hspace{0.17em}{\displaystyle \sum }_{i=\mathrm{1}}^s‍{\gamma }_{xy}{\beta }_{xyi}{w}_{{\mathcal{C}}_i}\left(k_{\mathrm{1}}+\cdots +k_s\right)\\ ={\displaystyle \sum }_{y=\mathrm{1}}^d‍\hspace{0.17em}{\displaystyle \sum }_{i=\mathrm{1}}^s‍\hspace{0.17em}{\displaystyle \sum }_{j=\mathrm{1}}^g‍{\gamma }_{xy}{\beta }_{xyi}{\alpha }_{ij}{w}_{ij}\left(k_{\mathrm{1}}+\cdots +k_s\right).\end{array}$$

(10)

As described in Section 4.1.1 (Keygen 1), the property of $k_p$ is that $\forall i\in \{\mathrm{1},\dots ,s\}$ , $i\ne p$ , $p\in \{\mathrm{1},\dots ,s\}$ , $w_{ij}·k_p=\mathrm{0}$ . As a result, $t_x^{\prime }={\sum }_{y=\mathrm{1}}^d‍{\sum }_{i=\mathrm{1}}^s‍{\sum }_{j=\mathrm{1}}^g‍{\gamma }_{xy}{\beta }_{xyi}{\alpha }_{ij}{w}_{ij}{k}_i$ . Therefore, $t_x=t_x^{\prime }$ .

4.4. Repair

Suppose that the server $S_r$ is detected as corrupted in the check phase. $S_r$ is replaced by a new server $S_r^{\prime }$ . The server $S_r^{\prime }$ requires l healthy servers $S_{x_{\mathrm{1}}},\dots ,S_{x_l}$ to provide their combined packets consisting of the coded blocks and the tags. $S_r^{\prime }$ is given the key ${\kappa }^{\prime }=\kappa +k_{\mathrm{r}\mathrm{e}\mathrm{p}\mathrm{a}\mathrm{i}\mathrm{r}}$ , where $k_{\mathrm{r}\mathrm{e}\mathrm{p}\mathrm{a}\mathrm{i}\mathrm{r}}$ is generated from the Keygen2, to check the provided packets.

Step 1.

Each server $S_x$ where $x\in \{x_{\mathrm{1}},\dots ,x_l\}$ linearly combines its d coded blocks and linearly combines its d tags. $S_x$ then sends the aggregated coded block and aggregated tag to the new server $S_r^{\prime }$ :

$\forall x\in \{x_{\mathrm{1}},\dots ,x_l\}$ , $S_x$ performs:

• (i)

$\forall y\in \{\mathrm{1},\dots ,d\}$ , generates d coefficients ${\gamma }_{xy}\stackrel{\mathrm{r}\mathrm{a}\mathrm{n}\mathrm{d}}{\leftarrow }{\mathbb{F}}_q$ ;

(ii)

combine coded blocks: $c_x={\sum }_{y=\mathrm{1}}^d‍c_{xy}·{\gamma }_{xy}$ ;

(iii)

combine tags: $t_x={\sum }_{y=\mathrm{1}}^d‍t_{xy}·{\gamma }_{xy}$ ;

(iv)

send the package consisting of $\{c_x,t_x\}$ to $S_r^{\prime }$ .

Step 2.

The new server $S_r^{\prime }$ checks whether each server $S_x$ where $x\in \{x_{\mathrm{1}},\dots ,x_l\}$ provides a valid packet (pollution attack), using the key ${\kappa }^{\prime }=(k_{\mathrm{1}}+\cdots +k_s)+k_{\mathrm{r}\mathrm{e}\mathrm{p}\mathrm{a}\mathrm{i}\mathrm{r}}$ .

Given ${\kappa }^{\prime }=(k_{\mathrm{1}}+\cdots +k_s)+k_{\mathrm{r}\mathrm{e}\mathrm{p}\mathrm{a}\mathrm{i}\mathrm{r}}$ , $S_r^{\prime }$ computes:

• (i)

compute $t_x^{\prime }=c_x·{\kappa }^{\prime }$ ;

(ii)

check $t_x=t_x^{\prime }$ ( $\ast \ast$ ).

Step 3.

The new server $S_r^{\prime }$ computes d coded blocks and d tags for itself:

$\forall y\in \{\mathrm{1},\dots ,d\}$ , $S_r^{\prime }$ computes:

• (i)

$\forall x\in \{x_{\mathrm{1}},\dots ,x_l\}$ , generate l coefficients ${\theta }_{xy}\stackrel{\mathrm{r}\mathrm{a}\mathrm{n}\mathrm{d}}{\leftarrow }{\mathbb{F}}_q$ ;

(ii)

new coded blocks $c_{ry}={\sum }_{x=x_{\mathrm{1}}}^{x_l}‍c_x·{\theta }_{xy}$ ;

(iii)

new tags $t_{ry}={\sum }_{x=x_{\mathrm{1}}}^{x_l}‍t_x·{\theta }_{xy}$ .

Correctness of the Verification ( $\ast \ast$ ) in Step 2. The way to prove the correctness of this verification is similar to the correctness of the verification (∗) in the check phase. The only different thing is that not only $k_{\mathrm{1}},\dots ,k_s$ but also $k_{\mathrm{r}\mathrm{e}\mathrm{p}\mathrm{a}\mathrm{i}\mathrm{r}}$ participates in combining the coded blocks and homomorphic tags. As described in the Keygen2 (Section 4.1.2), $\forall i\in \{\mathrm{1},\dots ,s\},\hspace{0.17em}\hspace{0.17em}p\stackrel{\mathrm{r}\mathrm{a}\mathrm{n}\mathrm{d}}{\leftarrow }{\mathbb{F}}_q,\hspace{0.17em}\hspace{0.17em}p>s$ , and we have $w_{ij}·k_p=\mathrm{0}$ .

5. Security Analysis

5.1. Security against Mobile Adversaries

To prevent mobile adversaries, a data repair threshold is given as follows.

Theorem 1.

The original files $F_{\mathrm{1}},\dots ,F_s$ of the clients can be recovered if in any epoch, at least l out of h servers collectively store $m=sg$ coded blocks which are linearly independent combinations of m original file blocks; and the matrix consisting of the accumulated coefficients has full rank (i.e., rank m).

Proof.

Each server $S_x$ where $x\in \{\mathrm{1},\dots ,h\}$ contains d coded blocks: $\{c_{xy}\}\hspace{0.17em}\hspace{0.17em}(y\in \{\mathrm{1},\dots ,d\})$ . Each coded block $c_{xy}$ is computed from $m=sg$ augmented blocks $w_{ij}$ ( $i\in \{\mathrm{1},\dots ,s\},j\in \{\mathrm{1},\dots ,g\}$ ) as $c_{xy}={\sum }_{i=\mathrm{1}}^s‍{\sum }_{j=\mathrm{1}}^g‍{\beta }_{xyi}·{\alpha }_{ij}·w_{ij}$ . To recover the original files, m augmented blocks ( $w_{\mathrm{11}},\dots ,w_{\mathrm{1}g},\dots ,w_{s\mathrm{1}},\dots ,w_{sg}$ ) are viewed as the variables that need to be solved. To solve such m variables, at least m coded blocks are needed such that the coefficient matrix has full rank because the number of variables in an equation system has to be less than or equal to the number of independent equations:

$$\begin{array}{cc}& c_{x{y}_{\mathrm{1}}}={\displaystyle \sum }_{i=\mathrm{1}}^s‍{\displaystyle \sum }_{j=\mathrm{1}}^g‍{\beta }_{xy{i}_{\mathrm{1}}}·{\alpha }_{i{j}_{\mathrm{1}}}·w_{ij}\\ c_{x{y}_{\mathrm{2}}}={\displaystyle \sum }_{i=\mathrm{1}}^s‍{\displaystyle \sum }_{j=\mathrm{1}}^g‍{\beta }_{xy{i}_{\mathrm{2}}}·{\alpha }_{i{j}_{\mathrm{2}}}·w_{ij}\\ ⋮\\ c_{x{y}_m}={\displaystyle \sum }_{i=\mathrm{1}}^s‍{\displaystyle \sum }_{j=\mathrm{1}}^g‍{\beta }_{xy{i}_m}·{\alpha }_{i{j}_m}·w_{ij}.\end{array}$$

(11)

Therefore, at least l servers which collectively store $m=s·g$ coded blocks in each epoch are required. $⌈m/d⌉\le l<h$ .

5.2. Security against Curious Adversaries

The following theorem gives the probability of the adversary to recover the secret keys and shows that the probability is negligible.

Theorem 2.

The secret keys of the clients are secured from the TPA and the new server.

Proof.

The TPA checks h servers ( $S_{\mathrm{1}},\dots ,S_h$ ) in the check phase using the key $\kappa =k_{\mathrm{1}}+\cdots +k_s$ . Similarly, the new servers $S_r^{\prime }$ check l healthy servers in the repair phase using the key ${\kappa }^{\prime }=(k_{\mathrm{1}}+\cdots +k_s)+k_{\mathrm{r}\mathrm{e}\mathrm{p}\mathrm{a}\mathrm{i}\mathrm{r}}$ . The problem of security is now the problem of solving s variables (in the case of the TPA) and $s+\mathrm{1}$ variables (in the case of $S_r^{\prime }$ ) given one equation. The only method to solve these variables is to try all possible variable sets and test whether they satisfy this equation by using trial-and-error method with brute-force search. Let $\mathcal{K}$ denote the key space. Each $k_i\hspace{0.17em}\hspace{0.17em}(i\in \{\mathrm{1},\dots ,s\})$ , $k_{\mathrm{r}\mathrm{e}\mathrm{p}\mathrm{a}\mathrm{i}\mathrm{r}}$ , κ, and ${\kappa }^{\prime }$ belong to the finite field ${\mathbb{F}}_q^{n+m}$ (which has $(n+m){\mathrm{l}\mathrm{o}\mathrm{g}}_{\mathrm{2}}q$ bit-length), and therefore $\mathcal{K}=q^{n+m}$ . The number of testing times is $(\mathcal{K}{)}^{s-\mathrm{1}}$ in the case of the TPA and $(\mathcal{K}{)}^s$ in the case of $S_r^{\prime }$ . Therefore, the probability for choosing s variables is $\mathrm{1}/q^{(n+m)(s-\mathrm{1})}$ in the case of the TPA and the probability for choosing $s+\mathrm{1}$ variables is $\mathrm{1}/q^{(n+m)s}$ in the case of $S_r^{\prime }$ . If q is chosen as a large prime (e.g., 160 bits), $k_{\mathrm{1}},\dots ,k_s$ , and $k_{\mathrm{r}\mathrm{e}\mathrm{p}\mathrm{a}\mathrm{i}\mathrm{r}}$ cannot be solved in a polynomial time. Ergo, the probability of TPA and $S_r^{\prime }$ are negligible.

5.3. Security against Response Forgeries

After controlling $S_x$ , suppose that, in the check phase, the adversary $\mathcal{A}$ sends a pair of forged coded block and forged tag $(c_x^{\prime \prime },t_x^{\prime \prime })$ to the TPA, instead of a valid pair of $(c_x,t_x)$ .

Theorem 3.

The advantage of a forgery adversary to pass the check phase is

$$\begin{array}{cc}& {\mathsf{A}\mathsf{d}\mathsf{v}}_{\mathcal{A}}\left(\mathsf{v}\mathsf{e}\mathsf{r}\mathsf{i}\mathsf{f}\mathsf{y}\right)={\mathsf{A}\mathsf{d}\mathsf{v}}_{\mathcal{A}}\left(\mathsf{P}\mathsf{R}\mathsf{F}\right)+\frac{\mathrm{1}}{q^{\left(n+m\right)s}}.\end{array}$$

(12)

Proof.

To be able to generate $(c_x^{\prime \prime },t_x^{\prime \prime })$ which holds the verification $t_x^{\prime \prime }=c_x^{\prime \prime }·\kappa$ , the adversary $\mathcal{A}$ has to obtain κ. Since the TPA is assumed not to collude with any server and κ is sent to $\mathcal{A}$ though a secure channel, a possible way for $\mathcal{A}$ is to attack the Keygen1 in which the key $k_p$ of ${\mathcal{C}}_p\hspace{0.17em}\hspace{0.17em}(p\in \{\mathrm{1},\dots ,s\})$ is computed as

• (i)

$r_i\leftarrow F(k,p,i)\in {\mathbb{F}}_q,\hspace{0.17em}\hspace{0.17em}\forall i\in \{\mathrm{1},\dots ,n+g\}$ ;

(ii)

$k_p\leftarrow {\sum }_{i=\mathrm{1}}^{n+g}‍r_i{b}_i\in {\mathbb{F}}_q^{n+m}$ .

The advantage of $\mathcal{A}$ on $r_i$ is  ${\mathrm{A}\mathrm{d}\mathrm{v}}_{\mathcal{A}}(\mathrm{P}\mathrm{R}\mathrm{F})$ . Since $k_p\in {\mathbb{F}}_q^{n+m}$ , the advantage of $\mathcal{A}$ on $k_p$ is $\mathrm{1}/q^{n+m}$ . The advantage of $\mathcal{A}$ on $\kappa ={\sum }_{i=\mathrm{1}}^s‍k_i$ is $\mathrm{1}/q^{(n+m)s}$ . Therefore,  ${\mathrm{A}\mathrm{d}\mathrm{v}}_{\mathcal{A}}(\mathrm{v}\mathrm{e}\mathrm{r}\mathrm{i}\mathrm{f}\mathrm{y})={\mathrm{A}\mathrm{d}\mathrm{v}}_{\mathcal{A}}(\mathrm{P}\mathrm{R}\mathrm{F})+\mathrm{1}/q^{(n+m)s}$ . If F is unforgeable and q is chosen large enough, for example, 160 bits, the advantage of $\mathcal{A}$ is negligible:  ${\mathrm{A}\mathrm{d}\mathrm{v}}_{\mathcal{A}}(\mathrm{v}\mathrm{e}\mathrm{r}\mathrm{i}\mathrm{f}\mathrm{y})<ϵ$ .

5.4. Security against Pollution Attack

Suppose that the server $S_r$ is checked as a corrupted server and $S_{x_{\mathrm{1}}},\dots ,S_{x_l}$ are checked as healthy servers in the check phase. Then, $S_{x_{\mathrm{1}}},\dots ,S_{x_l}$ are required to repair $S_r$ by providing their coded blocks and tags to the new server $S_r^{\prime }$ . In the repair phase, the adversary $\mathcal{A}$ attacks $S_{x_p}\hspace{0.17em}(x_p\in \{x_{\mathrm{1}},\dots ,x_l\})$ and then provides an invalid packet to the new server $S_r^{\prime }$ (pollution attack). Similar to Theorem 2, the advantage of $\mathcal{A}$ to pass the pollution attack check (Step 2 in the repair phase) is

$$\begin{array}{cc}& {\mathsf{A}\mathsf{d}\mathsf{v}}_{\mathcal{A}}\left(\mathsf{p}\mathsf{o}\mathsf{l}\mathsf{l}\mathsf{u}\mathsf{t}\mathsf{i}\mathsf{o}\mathsf{n}\right)={\mathsf{A}\mathsf{d}\mathsf{v}}_{\mathcal{A}}\left(\mathsf{P}\mathsf{R}\mathsf{F}\right)+\frac{\mathrm{1}}{q^{\left(n+m\right)\left(s+\mathrm{1}\right)}}.\end{array}$$

(13)

The different thing is that the advantage of $\mathcal{A}$ on ${\kappa }^{\prime }=k_{\mathrm{r}\mathrm{e}\mathrm{p}\mathrm{a}\mathrm{i}\mathrm{r}}+{\sum }_{i=\mathrm{1}}^s‍k_i$ is $\mathrm{1}/q^{(n+m)(s+\mathrm{1})}$ , not $\mathrm{1}/q^{(n+m)s}$ as Theorem 2 because the adversary does not own ${\kappa }^{\prime }$ .

We also consider a stronger adversary $\mathcal{A}$ who attacks $S_r^{\prime }$ right after the repair phase to steal ${\kappa }^{\prime }$ from $S_r^{\prime }$ . $\mathcal{A}$ then uses ${\kappa }^{\prime }$ to pass pollution attack check in another later repair phases. However, since $k_{\mathrm{r}\mathrm{e}\mathrm{p}\mathrm{a}\mathrm{i}\mathrm{r}}$ is different in each repair time as explained in the Keygen2 (Section 4.1.2), the advantage for $\mathcal{A}$ to guess $k_{\mathrm{r}\mathrm{e}\mathrm{p}\mathrm{a}\mathrm{i}\mathrm{r}}$ is  ${\mathrm{A}\mathrm{d}\mathrm{v}}_{\mathcal{A}}(\mathrm{P}\mathrm{R}\mathrm{F})+\mathrm{1}/q^{(n+m)}$ .

6. Efficiency Analysis

Table 1 compares the features and efficiency of the proposed MD-POR scheme with some previous schemes. The RDC-NC [12] and NC-Audit [15] schemes are chosen for the comparison because they have the same scenario as the MD-POR scheme at most. One notable thing is that because the RDC-NC and NC-Audit schemes only consider a single client unlike the MD-POR scheme, we assume that s clients participate in the RDC-NC and NC-Audit schemes so that the comparisons are fair. However, these s clients in the RDC-NC and NC-Audit schemes can only perform in parallel instead of simultaneously combination as the MD-POR scheme. That parameter s in the RDC-NC and NC-Audit schemes does not affect the checking and repairing complexity because only one client can check and repair the servers. That s only affects the storage cost on server-side and the communication cost of the encode phase in the RDC-NC and NC-Audit schemes.

Table 1

Comparison.

		RDC-NC [12]	NC-Audit [15]	MD-POR (our scheme)
Feature	Multiclient	No	No	Yes
	Direct repair	No	Not completed	Yes
	Symmetric key	Yes	Yes	Yes
	public authentication	No	Yes	Yes
Storage complexity	Client-side	$$O(\mathrm{5}(n+g){\text{log}}_{\mathit{2}}q)$$	$$O((n+g){\text{log}}_{\mathit{2}}q)$$	$$O((n+sg){\text{log}}_{\mathit{2}}q)$$
	Server-side	$$O(sdh(\left(\left|F\right|/g\right)+g))$$	$$O(sdh(\left(\left|F\right|/g\right)+g))$$	$$O(dh(\left(\left|F\right|/g\right)+sg))$$
	TPA-side	N/A	$$O((n+g+gdh){\text{log}}_{\mathit{2}}q)$$	$$O((n+sg){\text{log}}_{\mathit{2}}q)$$ .
Encoding complexity	Computation (client)	$$O(gdh)$$	$$O(gdh)$$	$$O(g)$$
	Computation (server)	$$O(\mathrm{1})$$	$$O(\mathrm{1})$$	$$O(sdh)$$
	Computation (TPA)	N/A	$$O(\mathrm{1})$$	$$O(\mathrm{1})$$
	Communication	$$O(sdh(\left(\left|F\right|/g\right)+g))$$	$$O(sdh(\left(\left|F\right|/g\right)+g)+sgdh)$$	$$O(hs(\left(\left|F\right|/g\right)+sg))$$
Checking complexity	Computation (client)	$$O(h)$$	$$O(\mathrm{1})$$	$$O(\mathrm{1})$$
	Computation (server)	$$O(hd)$$	$$O(hd)$$	$$O(hd)$$
	Computation (TPA)	N/A	$$O(h)$$	$$O(h)$$
	Communication	$$O(h((|F|/g)+g))$$	$$O(h(\left(\left|F\right|/g\right)+g))$$	$$O(h(\left(\left|F\right|/g\right)+sg))$$
Repairing complexity	Computation (client)	$$O((l+\mathrm{1})d)$$	$$O(\mathrm{1})$$	$$O(\mathrm{1})$$
	Computation (server)	$$O(dl)$$	$$O(dl)$$	$$O(dl)$$
	Computation (new server)	N/A	$$O(dl)$$	$$O(dl)$$
	Computation (TPA)	N/A	$$O(l)$$	$$O(\mathrm{1})$$
	Communication	$$O((l+d)(\left(\left|F\right|/g\right)+g))$$	$$O(l(\left(\left|F\right|/g\right)+g)+ld)$$	$$O(l(\left(\left|F\right|/g\right)+sg))$$

6.1. Storage Cost

6.1.1. Client-Side

In the RDC-NC scheme, because the client keeps five secret keys in ${\mathbb{F}}_q^{n+g}$ , the client storage is $O(\mathrm{5}(n+g){\mathrm{l}\mathrm{o}\mathrm{g}}_{\mathrm{2}}q)$ . In the NC-Audit scheme, because the client keeps only one secret key in ${\mathbb{F}}_q^{n+g}$ , the client storage is $O((n+g){\mathrm{l}\mathrm{o}\mathrm{g}}_{\mathrm{2}}q)$ . Meanwhile, the MD-POR scheme has s keys for s clients, each in ${\mathbb{F}}_q^{n+sg}$ , and thus the storage cost per client is $O((n+sg){\mathrm{l}\mathrm{o}\mathrm{g}}_{\mathrm{2}}q)$ .

6.1.2. Server-Side

The size of a file block is $\left|v\right|=\left|F\right|/g$ . The form of an augmented block is $w_i=(v_i,\stackrel{m=sg}{\overbrace{\underset{i}{\underbrace{\mathrm{0},\dots ,\mathrm{0,1}}},\mathrm{0},\dots ,\mathrm{0}}})$ as indicated in Section 2.3. In the RDC-NC and NC-Audit schemes, since $s=\mathrm{1}$ , the size of an augmented block is $\left|w\right|=\left|F\right|/g+g$ . In the MD-POR scheme, since $s=g$ , the size of an augmented block is $\left|w\right|=\left|F\right|/g+sg$ . Furthermore, the size of a coded block is $\left|c\right|=\left|w\right|$ because each coded block is a linear combination of augmented blocks. The number of servers is h. Each server stores d coded blocks. s clients are assumed to participate in the RDC-NC and NC-Audit schemes in parallel. Therefore, the server storage in the RDC-NC and NC-Audit schemes is $O(sdh(\left|F\right|/g+g))$ . The server storage in the MD-POR scheme is $O(dh(\left|F\right|/g+sg))$ .

6.1.3. TPA-Side

The RDC-NC scheme does not have a TPA. In the NC-Audit scheme, the TPA not only keeps a key in ${\mathbb{F}}_q^{n+g}$ for verification (which is $O(\left(n+g\right){\mathrm{l}\mathrm{o}\mathrm{g}}_{\mathrm{2}}q)$ ) but also stores the coding coefficients in ${\mathbb{F}}_q$ which are used to compute all coded blocks (which is $O(gdh{\mathrm{l}\mathrm{o}\mathrm{g}}_{\mathrm{2}}q)$ ). Hence, the total TPA storage in the NC-Audit scheme is $O((n+g+gdh){\mathrm{l}\mathrm{o}\mathrm{g}}_{\mathrm{2}}q)$ . In the MD-POR scheme, the TPA is given $\kappa =k_{\mathrm{1}}+\cdots +k_s\in {\mathbb{F}}_q^{n+m}$ (Section 4.1.1). In other words, $\kappa \in {\mathbb{F}}_q^{n+sg}$ . The TPA storage in the MD-POR scheme is thus $O((n+sg){\mathrm{l}\mathrm{o}\mathrm{g}}_{\mathrm{2}}q)$ .

6.2. Encoding Cost

6.2.1. Computation on Client-Side

In the RDC-NC and NC-Audit schemes, during the encode phase, each client combines g augmented blocks (which is $O(g)$ ) to create $dh$ coded blocks in order to store d coded blocks in each of h servers. The cost in these schemes is thus $O(gdh)$ . In the MD-POR scheme, each client only needs to combine g augmented blocks (which is $O(g)$ ) and distributes the result to all the servers. The servers will create coded blocks by themselves. The cost in the MD-POR is thus $O(g)$ .

6.2.2. Computation on Server-Side

In the RDC-NC and NC-Audit schemes, the servers do not need to do anything and only need to receive the coded blocks computed by the clients. The cost in these schemes is thus $O(\mathrm{1})$ . In the MD-POR scheme, each of h servers combines s coded blocks from the clients and computes d coded blocks for itself. The cost in the MD-POR is thus $O(sdh)$ .

6.2.3. Computation on TPA-Side

In the RDC-NC scheme, the TPA does not exist. In the NC-Audit and MD-POR schemes, the TPA does nothing during the encode phase; and the costs are thus $O(\mathrm{1})$ .

6.2.4. Communication

In the RDC-NC scheme, the client creates $dh$ coded blocks and sends d coded blocks to each of h servers. The size of a coded block in these scheme is ( $\left|F\right|/g+g$ ) as mentioned in Section 6.1.2. The number of clients is s. Therefore, the communication cost is $O(sdh(\left|F\right|/g+g))$ . In the NC-Audit scheme, the communication is also similar to the RDC-NC scheme. However, the difference is that the client in the NC-Audit scheme not only sends the coded blocks to the servers, but also sends all $sgdh$ coefficients which are used to create the coded blocks to the servers. The cost in the NC-Audit scheme is thus $O(sdh(\left|F\right|/g+g)+sgdh)$ . In the MD-POR scheme, each of s clients sends the aggregated coded block to each of h servers. The size of a coded block in the MD-POR scheme is ( $\left|F\right|/g+sg$ ) (see (5)). The cost in the MD-POR scheme is thus $O(hs(\left|F\right|/g+sg))$ .

6.3. Checking Cost

6.3.1. Computation on Client-Side

In the RDC-NC scheme, the client receives the aggregated coded block from each of h servers and verifies each of them using his/her secret key; the cost is thus $O(h)$ . In the NC-Audit and MD-POR schemes, the TPA will check the servers instead of the client. The cost in the NC-Audit and MD-POR schemes is thus $O(\mathrm{1})$ on the client-side.

6.3.2. Computation on Server-Side

In all three schemes, each of h servers combines its d coded blocks to send the result (an aggregated coded block) back to the verifier. The verifier is the client in the case of the RDC-NC scheme and is the TPA in the case of the NC-Audit and MD-POR schemes. The cost in all three schemes is $O(hd)$ .

6.3.3. Computation on TPA-Side

In the RDC-NC scheme, the TPA does not exist. In the NC-Audit and MD-POR schemes, the TPA verifies the aggregated coded block which is accommodated from each of h servers. Each verification only takes one operation. The cost in the NC-Audit and MD-POR schemes is $O(h)$ .

6.3.4. Communication

In the RDC-NC and NC-Audit schemes, during the check phase, each of h servers sends its aggregated coded block to the client. The size of that coded block is ( $\left|F\right|/g+g$ ). The cost in these schemes is thus $O(h(\left|F\right|/g+g))$ . In the MD-POR scheme, the mechanism is the same as the RDC-NC and NC-Audit scheme, but the different thing is that the size of a coded block in the MD-POR scheme is ( $\left|F\right|/g+sg$ ). The cost in the MD-POR scheme is thus $O(h(\left|F\right|/g+sg))$ .

6.4. Repairing Cost

6.4.1. Computation on Client-Side

In the RDC-NC scheme, in the repair phase, the client firstly has to check pollution attack in l coded blocks which are provided from l healthy servers (which is $O(l)$ ). Thereafter, the client computes d new coded blocks for the new server by combining l provided coded blocks (which is $O(ld)$ ). Hence, the computation cost on the client-side in the RDC-NC scheme is $O((l+\mathrm{1})d)$ . In the NC-Audit and MD-POR schemes, the client(s) does nothing.

6.4.2. Computation on Server-Side

In the RDC-NC scheme, each of l healthy servers is required to combine its d coded blocks. Therefore, the computation cost on the server-side is $O(dl)$ . The cost in the new server is N/A because the direct repair feature is not supported in the RDC-NC scheme. In the NC-Audit and MD-POR schemes, not only l healthy servers combine their coded blocks (which is $O(dl)$ ) but also the new server computes its d new coded blocks by combining l provided coded blocks (which is $O(dl)$ ).

6.4.3. Computation on TPA-Side

The RDC-NC scheme does not have a TPA. In the NC-Audit scheme, the TPA has to check pollution attack in l provided coded blocks (which is $O(l)$ ). In the MD-POR scheme, the TPA does nothing because the new server will check pollution attack, not the TPA as the NC-Audit scheme. Therefore, the computation cost on the TPA-side in the MD-POR scheme is $O(\mathrm{1})$ .

6.4.4. Communication

In the RDC-NC scheme, each of l healthy servers sends an aggregated coded block whose size is $\left|F\right|/g+g$ to the client (which is $O(l(\left|F\right|/g+g))$ ). After computing d new coded blocks, the client sends them to the new server (which is $O(d(\left|F\right|/g+g))$ ). As a result, the communication cost in the RDC-NC scheme is $O((l+d)(\left|F\right|/g+g))$ . In the NC-Audit scheme, each of l healthy servers also sends an aggregated coded block to the new server (which is $O(l(\left|F\right|/g+g))$ ). Then, the new server sends its linear coefficients which are used to compute d new coded blocks from l provided coded blocks to the TPA (which is $O(ld)$ ). Therefore, the communication cost in the NC-Audit scheme is $O(l(\left|F\right|/g+g)+ld)$ . In the MD-POR scheme, only each of l healthy servers sends an aggregated coded block to the new server (each coded block has the size $\left|F\right|/g+sg$ ). Therefore, the communication cost in the MD-POR scheme is $O(l(\left|F\right|/g+sg))$ .

In summary, although the MD-POR scheme supports many heavy features, its cost of the whole scheme is still better than the previous schemes. Let $O_p(A)$ , $O_p(B)$ , and $O_p(C)$ denote the whole computation costs of the RDC-NC, NC-Audit, and MD-POR schemes, respectively. Let $O_m(A)$ , $O_m(B)$ , and $O_m(C)$ denote the whole communication costs of the RDC-NC, NC-Audit, and MD-POR schemes, respectively. Let $O_s(A)$ , $O_s(B)$ , and $O_s(C)$ denote the whole storage costs of the RDC-NC, NC-Audit, and MD-POR schemes, respectively. In reality, d and g are far larger than s and h ( $d,g\gg s,h$ ), $l\in \{\mathrm{1},\dots ,h\}$ , and $d>g$ . From Table 1, the following results are obtained. $O_p(A)-O_p(C)=(gdh+d)-(sdh+g)>\mathrm{0}$ because $g\gg s$ . $O_p(B)-O_p(C)=(gdh+l)-(sdh+g)>\mathrm{0}$ because $g\gg s$ . $O_m(A)-O_m(C)=(dhs+d-hs)\left(\left|F\right|/g\right)+g(sdh+h+l+d-h{s}^{\mathrm{2}}-hs-ls)>\mathrm{0}$ because $d\gg s$ and $\mathrm{1}\le l\le h$ . $O_m(B)-O_m(C)=(dhs-hs)\left(\left|F\right|/g\right)+g(\mathrm{2}sdh+h+l-h{s}^{\mathrm{2}}-hs-ls)+ld>\mathrm{0}$ because $d\gg s$ and $\mathrm{1}\le l\le h$ . $O_s(A)-O_s(C)=(\mathrm{3}n+\mathrm{5}g){\mathrm{l}\mathrm{o}\mathrm{g}}_{\mathrm{2}}q+(s-\mathrm{1})dh\left(\left|F\right|/g\right)-\mathrm{2}sg{\mathrm{l}\mathrm{o}\mathrm{g}}_{\mathrm{2}}q>\mathrm{0}$ because $\left|F\right|/g=n{\mathrm{l}\mathrm{o}\mathrm{g}}_{\mathrm{2}}q$ and $d>g$ . $O_s(B)-O_s(C)=(s-\mathrm{1})dh\left(\left|F\right|/g\right)+g{\mathrm{l}\mathrm{o}\mathrm{g}}_{\mathrm{2}}q(dh-\mathrm{2}s+\mathrm{2})>\mathrm{0}$ because $d\gg s$ .

7. Performance Evaluation

This section evaluates the computation and communication performances of the proposed MD-POR scheme to show that it is applicable for a real system. A program written by Python 2.7.3 is executed using a computer with Intel Core i5 processor, 2.4 GHz, 4 GB of RAM, and Windows 7 64-bit OS. The length of the prime q is set to be 160 bits. The number of clients is set to be 5 ( $s=\mathrm{5}$ ) which is also the parameter used in the performance evaluation of the InterMac in the paper [16]. The number of servers is set to be 10 ( $h=\mathrm{10}$ ). The number of coded blocks stored in each server is set to be 100 ( $d=\mathrm{100}$ ). The number of healthy servers which are used for repairing is set to be 3 ( $l=\mathrm{3}$ ). The size of each file block is set to be ${\mathrm{2}}^{\mathrm{23}}$ bits (1MB). Each result is the average of 100 runs.

The experiment results are observed with three sets of computation performance and a set of communication performance by varying the file size of each client. The computation results are depicted in Figure 4 (encode), Figure 5 (check), and Figure 6 (repair). The communication result is depicted in Figure 7 (encode, check, and repair).

Figure 4

The computation time performance of the encode algorithm.

Figure 5

The computation time performance of the check algorithm.

Figure 6

The computation time performance of the repair algorithm.

Figure 7

The communication time performance.

Computation Performance. The experiment results reveal that the computation time increases almost linearly as the file size increases, and each graph has a different slope. Only the computation time of TPA-side in the check phase is almost constant. In the encode phase, the slopes of increment in the graphs of client-side and server-side are approximately 0.04 and 0.002, respectively. Therefore, if the file size is 1 GB, the computation time on client-side and server-side is estimated as 41 seconds and 2 seconds, respectively. Note that the encode phase only is executed one time in the beginning; meanwhile, the check phase is executed many times during system lifetime and the repair phase is executed once a corruption is detected in the check phase. Consequently, the check and repair phases are more important than the encode phase. In the check phase, the slopes of increment in the graphs of server-side and TPA-side are approximately 0.0005 and 0, respectively. Therefore, if the file size is 1 GB, the computation time on server-side and TPA-side is estimated as 0.52 seconds and 0.02 seconds, respectively. Similarly, in the repair phase, the slopes of increment in the graphs of healthy server-side and new server-side are approximately 0.0005 and 0.0014, respectively. Therefore, if the file size is 1 GB, the computation time on healthy server-side and new server-side is estimated as 0.52 seconds and 1.47 seconds, respectively.

Communication Performance. The MD-POR scheme is performed with the bandwidth of 300 Mbps. The experiment results reveal that the communication time increases almost linearly as the file size increases, and each graph in Figure 7 has a different slope. The slopes of increment in the graphs of the encode phase, the check phase, and the repair phase are approximately 0.048, 0.008, and 0.006, respectively. Therefore, if the file size is 1 GB, the communication time of the encode phase, check phase, and repair phase is estimated as 49.27 seconds, 7.86 seconds, and 5.83 seconds, respectively. In addition, the size of the response from each server is given as follows. The response size of 50 MB, 75 MB, 100 MB, 125 MB, and 150 MB file size is 13 KB, 19 KB, 26 KB, 32 KB, and 38 KB, respectively. Therefore, if the file size is 1 GB, the response size is estimated as 264.87 KB.

The above results indicate that the computation and communication performances are very fast even when the file size is 1 GB.

8. Conclusion and Future Work

In this paper, a network coding-based POR scheme named MD-POR has been proposed. The MD-POR scheme supports multiclient, symmetric key-based direct repair and public authentication features. Moreover, the MD-POR scheme can protect against a strong adversary who can perform mobile attack, curious attack, response forgery, and pollution attack. Furthermore, the efficiency analysis based on the complexity theory shows that although the MD-POR scheme supports many features, its costs are not bad compared with the previous schemes. The experiment results reveal that the computation time increases as the file size increases. However, the graphs show that the slope of increment for the MD-POR scheme increases merely. Future work is invested to implement two previous RDC-NC and NC-Audit schemes in order to compare with the MD-POR scheme. This paper have implemented only the MD-POR scheme to show that its computation cost is applicable for a real system.