[email protected]). A. S. Rawat and S. Vishwanath are with the Department of Electrical and Computer Engineering, The University of Texas at Aust...

0 downloads 54 Views 658KB Size

No documents

Secure Cooperative Regenerating Codes for Distributed Storage Systems O. Ozan Koyluoglu, Ankit Singh Rawat, and Sriram Vishwanath

arXiv:1210.3664v2 [cs.IT] 9 Jul 2014

Abstract Regenerating codes enable trading off repair bandwidth for storage in distributed storage systems (DSS). Due to their distributed nature, these systems are intrinsically susceptible to attacks, and they may also be subject to multiple simultaneous node failures. Cooperative regenerating codes allow bandwidth efficient repair of multiple simultaneous node failures. This paper analyzes storage systems that employ cooperative regenerating codes that are robust to (passive) eavesdroppers. The analysis is divided into two parts, studying both minimum bandwidth and minimum storage cooperative regenerating scenarios. First, the secrecy capacity for minimum bandwidth cooperative regenerating codes is characterized. Second, for minimum storage cooperative regenerating codes, a secure file size upper bound and achievability results are provided. These results establish the secrecy capacity for the minimum storage scenario for certain special cases. In all scenarios, the achievability results correspond to exact repair, and secure file size upper bounds are obtained using min-cut analyses over a suitable secrecy graph representation of DSS. The main achievability argument is based on an appropriate pre-coding of the data to eliminate the information leakage to the eavesdropper.

I. I NTRODUCTION A. Background Distributed storage systems (DSS) are designed to store data over a distributed network of nodes. DSS have become increasingly important given the growing volumes of data being generated, analyzed, and archived. OceanStore [1], Google File System (GFS) [2], and TotalRecall [3] are a few examples of storage systems employed today. Data to be stored is more than doubling every two years, and efficiency in storage and data recovery is particularly critical today. The coding schemes employed by DSS are designed to provide efficient storage while ensuring resilience against node failures in order to prevent the permanent loss of the data stored on the system. In a majority of existing literature, the analysis of DSS focuses primarily on isolated node failures. In our work, we study a more general scenario of DSS that can suffer from multiple simultaneous node failures. In addition to multiple node failures, DSS systems are also inherently susceptible to adversarial attacks such as one from eavesdroppers aiming to gain access to the stored data. Therefore, it is desirable to have DSS that meet certain security requirements while performing efficient repairs even in the case of multiple simultaneous node failures. In [4], Dimakis et al. present a class of regenerating codes, which efficiently trade off per node storage and repair bandwidth for single node repair. These codes are designed to possess a property of maximum distance separable (MDS) codes, referred to as ‘any k out of n’ property, wherein the entire data can be reconstructed by contacting to any k storage nodes out of n nodes in the storage system. By utilizing a network coding approach, the notion of functional repair is developed in [4]. Here, the original failed node may not be replicated exactly after node repair, but can be repaired such that the data stored on the repaired node is functionally equivalent to that stored on the failed node. On the other hand, exact repair requires that the regeneration process results in an exact replica of the data stored on the failed node. This is essential due to the ease of maintenance and other practical requirements such as maintaining a code in its systematic form. Exact repair may also prove to be advantageous compared to functional repair in the presence of eavesdroppers, as the latter scheme requires updating the coding coefficients, which in turn may leak additional information to eavesdroppers [5]. The design of exact regenerating codes achieving one of the two ends of the trade off between storage and repair bandwidth has recently been investigated by researchers. In particular, Rashmi et al. [6] propose codes that are optimal for all parameters at the minimum bandwidth regeneration (MBR) point. For the minimum storage regeneration (MSR) point, on the other hand, 1 the codes presented in [6] have their rate upper bounded by 21 + 2n . In high rate regime (i.e., nk > 12 ), the codes at the MSR point have recently been proposed under various restrictions on per node storage α (see e.g., [7]–[10] and references therein). Some of these codes at the MSR point allow for bandwidth efficient repair of only systematic nodes, e.g., [8], [9]. B. Cooperative repair As discussed above, DSS can also exhibit multiple simultaneous node failures, and it is desirable that these be repaired simultaneously. It is not uncommon that multiple failures occur in DSS, especially for large-scale systems. In addition, some O. O. Koyluoglu is with the Department of Electrical and Computer Engineering, The University of Arizona, Tucson, AZ 85721, USA (e-mail: [email protected]). A. S. Rawat and S. Vishwanath are with the Department of Electrical and Computer Engineering, The University of Texas at Austin, Austin, TX 78712, USA (e-mail: [email protected], [email protected]).

2

DSS administrators may choose to wait to initiate a repair process after a critical number of failures has occurred (say t of them) in order to render the entire process more efficient and less frequent. For example, TotalRecall [3] currently executes a node repair process only after a certain threshold on the number of failures is reached. In such multiple failure scenarios, each new node replacing a failed one can still contact d remaining (surviving) nodes to download data for the repair process. In addition, replacement nodes, after downloading data from surviving nodes, can also exchange data within themselves to complete the repair process. This repair process is referred to as cooperative repair in [11], which presents network coding techniques to enable such repairs. Cooperative repair is shown to be essential as it can help in lowering the total repair bandwidth compared to the t = 1 case. Flexibility of the choice on download nodes during the repair process is analyzed in [12]. [13], focusing on functional repair, shows that under the constraint n = d + t, deliberately delaying repairs (and thus increasing t) does not result in gains in terms of MBR/MSR optimality. [13] and [14] utilize a cut-set bound argument and derive cooperative counterparts of the end points of the trade off curve between repair bandwidth and per node storage for regenerating codes. These two points are named as the minimum bandwidth cooperative regenerating (MBCR) point and the minimum storage cooperative regenerating (MSCR) point (see also [15]). The work in [14] shows the existence of cooperative regenerating codes with optimal repair bandwidth. Explicit code constructions for exact repair in this setup are presented in [16], for the MBCR point, and in [17], for the MSCR point. These constructions are designed for the setting of d = k. (See also [18].) Interference alignment is used in [19] to construct codes to operate at the MSCR point. This construction is limited to the case k = 2 with d ≥ k, and does not generalize to k ≥ 3 with d > k. An explicit construction for the MBCR point, with the restriction that n = d + t for any t ≥ 1, is presented in [20]. Finally, the reference [21] presents codes for the MBCR point for all possible parameter values. Noting the significance of cooperative repair in DSS, regenerating codes that have resilience to eavesdropping attacks will have greater value if they also have efficient cooperative repair mechanisms. C. Security in distributed storage systems The security of systems can be understood in terms of their resilience to either (or both) active or passive attacks [22], [23]. Active attacks include settings where the attacker modifies existing packets or injects new ones into the system, whereas passive attacks include eavesdroppers observing the information being stored/transmitted. For DSS, cryptographic approaches like private-key cryptography are often logistically prohibitive as the secret key distribution between each pair of nodes and its renewal are highly challenging, especially for large-scale systems. In addition, most cryptographic approaches are typically based on certain hardness results, which, if repudiated, could leave the system vulnerable to attacks. On the other hand, information theoretic security, see, e.g., [24], [25], presents secrecy guarantees even with infinite computational power at eavesdroppers without requiring the sharing and/or distribution of keys. This approach is based on the design of secrecyachieving coding schemes by taking into account the amount of information leaked to eavesdroppers, and can offer new solutions to security challenges in DSS. In its simplest form, the security can be achieved with the one-time pad scheme [26], which claims the security of the data in a ciphertext, which is obtained by XOR of the data and a uniform key. This approach is of significant value to DSS. For example, consider a system storing the key at a node, and the ciphertext at another node. Then, the eavesdropper can not obtain any information regarding the data by observing one of these two nodes, whereas the data collector can contact to both nodes and decipher the data. The problem of designing secure DSS against eavesdropping attacks has recently been studied by Pawar et al. [5], where the authors consider a passive eavesdropper model by allowing an eavesdropper to observe the data stored on any ` (< k) storage nodes in a DSS employing an MBR code. The proposed schemes are designed for the ‘bandwidth limited regime’, and shown to achieve an upper bound on the secure file size, establishing its optimality. Shah et al. [27] consider the design of secure MSR codes. They point out that the eavesdropper model for an MSR code should be extended compared to that of an MBR code. The underlying reason is that at the MSR point of operation, an eavesdropper may obtain additional information by observing the data downloaded during a node repair (as compared to just observing the stored content). Thus, at the MSR point, the eavesdropper is modeled with a pair (`1 , `2 ) with `1 + `2 < k specifying the eavesdropper that has knowledge of the content of an `1 number of nodes, and, in addition, has knowledge of the downloaded information (and hence also the stored content) of an `2 number of nodes. We note that, as the amount of the data downloaded during a node repair and per node storage for MBR codes are the same, the two notions are different only at the MSR point. Considering such an eavesdropper model, Shah et al. present coding schemes utilizing product matrix codes [6], and show that the bound on secrecy capacity in [5] at the MBR point is achievable. They further use product matrix based codes for the MSR point as well, and show that the bound in [5] is achievable only when `2 = 0. More recently, based on appropriate maximum rank distance pre-coding of Zigzag codes [9] and their variants [10], secure codes for the MSR point are proposed in [28]. This construction is shown to achieve the secrecy capacity for a class of systems where only the downloads of the systematic nodes are observed by the eavesdropper in [29] for d = n − 1 for any (`1 , `2 ). Besides this classical MBR/MSR setting, the security aspects of locally repairable codes (see, e.g., [30]–[35]) are studied in [28]; and, security of DSS against active eavesdroppers is investigated in [36]–[39].

3

D. Contributions and organization In this paper, we analyze and design secure and cooperative regenerating codes for DSS. In terms of security requirements, we utilize a passive and colluding eavesdropper model as presented in [27]. In this model, during the entire life span of the DSS, the eavesdropper can gain access to data stored on an `1 number of nodes, and, in addition, it observes both the stored content and the data downloaded (for repair) on an additional `2 number of nodes. Given this eavesdropper model, we focus on the problem of designing secure cooperative regenerating codes in the context of DSS that perform multiple simultaneous node repairs. This scenario generalizes the single node repair setting considered in earlier works to multiple node failures. In this paper, we establish the secrecy capacity for the MBCR point, and propose some secure codes for the MSCR point that are optimal for some special cases. In all scenarios, the achievability results allow for exact repair. The main secrecy achievability coding argument in this paper is obtained by utilizing a secret pre-coding (randomization) scheme to obtain secure coding schemes for DSS. In some cases, this pre-coding is established simply with the one-time pad scheme, and in others maximum rank distance (MRD) codes are utilized similar to the classical work of [40]. We remark that utilization of such pre-coding mechanisms is critical in showing the security of the proposed schemes. In particular, our security proofs are based on an oracle-type proof, where the eavesdropper is asked to decode the random symbols given the secure data symbols in addition to its observations. We design the pre-coding mechanisms to allow for such a security analysis. For example, when we utilize MRD pre-coding, we show that the eavesdropper has enough number of evaluations of an underlying polynomial (used in MRD pre-coding) at linearly independent points to resolve for the random symbols. We summarize our contributions in the following. • We present an upper bound on the secrecy capacity for MBCR codes. This bound follows from the information theoretic analysis of counting the secure flow for a particular repair instance in DSS employing an MBCR code. • We present a secure MBCR code for n = d + t by employing a maximum rank distance pre-coding of the codes proposed in [20]. By comparing the secure file size of this code with the upper bound obtained, we characterize the secrecy capacity for MBCR codes for n = d + t (for any `1 ). • For n > d + t, we present secrecy capacity achieving codes (for any `1 ) by utilizing the bivariate polynomial proposed in [21]. In particular, our construction is based on randomizing some appropriate coefficients of the underlying bivariate polynomial. • For MSCR codes, we obtain an upper bound on the secrecy capacity against a passive eavesdropper that takes into account the amount of information leaked to the download-observing eavesdroppers. • We present a secure MSCR code for k = t = 2 based on the code proposed in [19]. In particular, we place random symbols on some nodes in DSS in addition to utilizing an appropriate one-time pad scheme for securing the data stored on other nodes. This construction is shown to achieve optimal secure file size. (Note that, for the case where k = t = 2, under the restriction that `1 + `2 < k a non-trivial eavesdropper can only be associated with (`1 , `2 ) = (1, 0) or (`1 , `2 ) = (0, 1).) • Finally, we construct secure MSCR codes when d = k and characterize achievable secure file size using such codes for any (`1 , `2 ). This construction is based on maximum rank distance pre-coding of the codes proposed in [17]. We show that this construction achieves the secrecy capacity of MSCR codes for a restrictive eavesdropper model specified by (`1 , `2 ) with `2 ≤ 1. The rest of the paper is organized as follows. In Section II, we provide the general system model together with some preliminary results utilized throughout the text. Section III provides the analysis of secure MBCR codes, and Section IV is devoted to the secure MSCR codes. The paper is concluded in Section V. Some of the results and proofs are relegated to appendices to enhance the flow of the paper. II. S YSTEM M ODEL AND P RELIMINARIES Consider a DSS consisting of n live nodes (at a given time) and a file f of size M over a finite field F that needs to be stored on the DSS1 . The file f is encoded into n data blocks x = (x1 , . . . , xn ), each of length α over F with α ≥ M k . Given the codeword x, node i in an n-node DSS stores encoded block xi . (In this paper, we use xi to represent both block xi and a storage node storing this encoded block interchangeably.) Motivated by the MDS property of the codes that are traditionally proposed to store data in centralized storage systems [41]–[43], the works on regenerating codes focus on storage schemes that have ‘any k out of n’ property, i.e., the contents of any k nodes suffice to recover the file. We focus on codes with this property2 . We use the following notation throughout the text. We usually stick with the notation of having vectors denoted by lowercase bold letters; sets and subspaces are denoted by calligraphic fonts. For a < b, [a : b] represents the set of numbers {a, a+1, · · · , b}. Similarly, ai1 :i2 ,j1 :j2 denotes the set {ai1 ,j1 , . . . , ai2 ,j1 , . . . , ai1 ,j2 , . . . , ai2 ,j2 }. In addition, ai1 :i2 ,j and ai,j1 :j2 denote {ai1 ,j , . . . , ai2 ,j } and {ai,j1 , . . . , ai,j2 }, respectively. The symbols stored at node i is represented by the vector si , the 1 The

size of F is specified later in the context of specific coding schemes. that having ‘any k out of n’ property does not necessarily imply that the code is an MDS code. A vector code C defined over Fq with symbols in logq |C| is said to be MDS if α| logq |C| and dmin = n − + 1. α

2 Note

Fα q

4

α xout β 1

β

α S

α α α

xout 2

xin 6

β β β

xin 7

β

∞

β

′

α xco 6 β′

∞

xco 7 α

xout 3 xout 4 xout 5

xout 6 xout 7

∞ ∞ DC ∞

Fig. 1: Information flow graph of DSS implementing cooperative repair. In this representative example, we have n = 5, d = k = 3, and t = 2. Accordingly, after a failure of two nodes, namely node 1 and node 2, the system cooperatively repairs these two nodes as node 6 and node 7. Downloads from live nodes (blue) and from cooperative repair pairs (green) are shown. Due to exact repair, the network will repair the nodes to satisfy xout = xout and xout = xout 6 1 7 2 . symbols transmitted from node i to node j is denoted as di,j , and the set dj is used to denote all of the symbols downloaded at node j. DSS is initialized with the n nodes containing encoded symbols, i.e., si = xi for i = 1, · · · , n. A. Cooperative repair in DSS In most of the studies on DSS, exact repair for regenerating codes is analyzed in the context of single node failure. However, it is not uncommon to see simultaneous multiple node failures in storage networks, especially for large ones. The basic setup involves the simultaneous repair of t (greater than one) failed nodes. After the failure of t storage nodes, the same number of newcomer nodes are introduced to the system. Each newcomer node connects to d arbitrary live storage nodes and downloads β symbols from each of these nodes. In addition, utilizing a cooperative approach, each newcomer node also contacts other newcomer nodes involved in node repair process and downloads β 0 symbols from each of these nodes. Hence, the total repair cost is given by γ = dβ + (t − 1)β 0 . Each newcomer node, to repair the ith node of the original network, uses these dβ + (t − 1)β 0 number of downloaded symbols to regenerate α symbols, xi , and stores these symbols. The t nodes simultaneously repaired in a cooperative manner constitute a repair group. This exact repair process preserves the ‘k out of n property’, i.e., data stored on any k nodes (potentially including the nodes that are repaired) allows the original file f to be reconstructed. See Fig. 1. We remark that, as also argued in [21], d ≥ k can be assumed without loss of generality. (Earlier papers on the subject assumed d ≥ k for simplicity. See, e.g., [16]–[20].) Remarkably, if d < k, a data collector can reconstruct the whole file by contacting only d nodes, as from these nodes the other nodes can be repaired in groups of size t. Thus, any (n, k, d) code with d < k can be reduced to (n, k 0 = d, d) code. Therefore, without loss of generality, we will assume d ≥ k. B. Information flow graph In their seminal work [4], Dimakis et al. model the operation of DSS using a multicasting problem over an information flow graph. (See Figs. 1 and 2 for the flow graph in the cooperative setting.) An information flow graph representation of a DSS consists of three types of nodes: • Source node (S): Source node contains M symbols long original file f . The source node is connected to n nodes. in co out • Storage nodes ((xi , xi , xi )): In an information flow graph associated with cooperative repairs, we represent each node with a combination of three sub-nodes: xin , xco , and xout . Here, xin is the sub-node having the connections from the live nodes, xco is the sub-node having the connections from the nodes under repair in the same repair group, and xout is the storage sub-node which represents the content stored on the corresponding node in DSS. xout is contacted by a data collector or other nodes during node repairs. xin is connected to xco with a link of infinite capacity, xco is connected to xout with a link of capacity α. We represent cuts using a notation with bars as in (xin , xco |xout ), meaning the cut is passing through the link between xco and xout . (See Fig. 2.) The nodes on the right hand side of the cuts belong to

5

DC

S

Fig. 2: Information flow graph of DSS implementing cooperative repair under security constraints. In this representative example, we have n = 5, d = k = 3, and t = 2. Multiple repair stages and a cut, represented by dashed line, through the nodes connected to the DC are shown. The figure has different cut types: The first repaired node has a cut of type (|xin , xco , xout ) and the second has a cut of type (xin , xco |xout ). Nodes that are being eavesdropped are indicated with dashed-dotted lines. Here, both the content and the downloads of the first repaired node is observed by the eavesdropper (`2 = 1), and only the content of the last repaired node is observed by the eavesdropper (`1 = 1). Accordingly, eavesdropper has observations of dβ + (t − 1)β 0 downloaded symbols from the first repaired node, and has α number of symbols from the last repaired node.

•

data collector side, represented by the set D, whereas the nodes belonging to the left hand side of the cuts belong to out Dc , the source side. For a newcomer node i, xin sub-nodes of d live nodes with links of capacity i is connected to x β symbols each, representing the data downloaded during node repair. xco i sub node associated with this newcomer node also connects to xin sub-nodes of (t − 1) remaining nodes that are being repaired in the same group, and each link of these connections has a capacity of β 0 . Data collector node(s) (DC): Each data collector contacts xout sub-node of k live nodes with edges of ∞-link capacity.

C. MBCR and MSCR points With the aforementioned values of capacities of various edges in the information flow graph, the DSS is said to employ an (n, k, d, α, β, β 0 ) code. For a given graph G and data collectors DCi , the file size that can be stored in such a DSS can be bounded using the max flow-min cut theorem for multicasting utilized in network coding [44], [45]. Lemma 1 (Max-flow min-cut theorem for multicasting [4], [44], [45]). M ≤ min min maxflow(S → DCi , G), G

DCi

where flow(S → DCi , G) represents the flow from the source node S to data collector DCi over the graph G. Therefore, e.g., for the graph in Fig. 2, M symbol long file can be delivered to a data collector DC, only if the min cut is at least M. Dimakis et al. [4] obtain the following bound (for t = 1 case) by considering k successive node failures and evaluating the min-cut over all possible graphs. M≤

k−1 X i=0

min{α, (d − i)β}

(1)

We emphasize that the min-cut for this (t = 1) case is given by the scenario where k successively repaired nodes are connected to DC, and for each successive repair, the repaired node i + 1 also connects to i number of previously repaired nodes. Hence, for each DC-connected node, its contribution to the value of a cut from S to DC is equal to (d − i)β if the cut through the node is of type (|xin , xout ), and is equal to α if the cut separates two sub-nodes, i.e., the cut through the node is of type (xin |xout ). (Note that, xco does not appear here as the model considered in [4] does not involve cooperative repair.) The codes that attain the bound in (1) are named as regenerating codes [4]. Analysis of the cut-set bounds for cooperative regenerating codes are provided in [13], [14]. (See also the arguments given in [11], [15]. Here, we follow the notations of [13], [15].) Consider a scenario where groups of nodes (each group having t nodes) are consecutively repaired in DSS. Let us enumerate the groups that are consecutively repaired as i = 0, · · · , µ−1. There are in total µt number of nodes in this repair process, and consider that DC contacts k out of these µt nodes. Let us denote

6

MBCR Storage (α)

2d+t−1 α= M k 2d+t−k 2 β=M k 2d+t−k 1 β′ = M k 2d+t−k

MSCR α= M k β = β′ =

M 1 k d+t−k

Repair bandwidth (γ) Fig. 3: Storage vs. repair bandwidth trade off for cooperative regenerating codes. The repair bandwidth is given by γ = dβ + (t − 1)β 0 . the number of nodes in repair group i that are contacted by the DC as ni such that ni ∈ [0 : t], for all i ∈ {0, 1, . . . , µ − 1}, µ−1 P and ni = k. i=0

The cut-set bound for this scenario is given by the following. ( ) µ−1 i−1 X X 0 M≤ ni min α, d − nj β + (t − ni ) β . i=0

(2)

j=0

Similar to the t = 1 case described above, the cut of type (xin , xco |xout ) has a value of α. The cut of type (|xin , xco , xout ), on the other hand, has a value of (t − ni ) β 0 due to the links coming from the nodes under repair that are not connected to i−1 P DC and additional value of (d − nj )β due to the connections to the previously repaired live nodes that are not contacted j=0

by DC. (Here, we again subtract the values of the flows from the nodes already belonging to the data collector side, D.) The cut of type (xin |xco , xout ) has value of ∞ and hence, does not appear in the min-cut. Note that, given a file size M, there is an inherent trade off between storage per node α and repair bandwidth γ , dβ + (t − 1)β 0 . This trade off, for the cooperative setting, can be established using a similar analyses leading to the MBR/MSR points from the equation (1). Two classes of codes that achieve two extreme points of this trade off are named as minimum bandwidth cooperative regenerating (MBCR) codes and minimum storage cooperative regenerating (MSCR) codes. The former is obtained by first finding the minimum possible γ and then finding the minimum α satisfying (2). This point is given by the following. M 2d + t − 1 , k 2d + t − k M 2 = , k 2d + t − k

αMBCR =

γMBCR = αMBCR ,

βMBCR

0 βMBCR =

M 1 k 2d + t − k

(3)

The MSCR point, on the other hand, is obtained by first choosing a minimum storage per node (i.e., α = M/k), and then minimizing γ (via choosing minimum possible β-β 0 pair) satisfying the min cut (2). M Md+t−1 , γMSCR = , k k d+t−k M 1 M 1 0 βMSCR = , βMSCR = (4) k d+t−k k d+t−k We depict these two trade off points, which are directly computable from (2), in Fig. 3. Note that, when t = 1, these two points correspond to the MBR/MSR points characterized in [4]. (We refer reader to [13], [14] for a detailed derivation of these two points. See also [15] for an analysis for the simplified case of when t|k, i.e., the number of groups satisfies µ = k/t.) We note that, in the next section, we consider secure file size upper bound using similar min cut arguments in the presence of eavesdroppers. αMSCR =

7

D. Eavesdropper model and Security in DSS We consider an (`1 , `2 ) eavesdropper, which has access to the stored data of any `1 number of nodes, and additionally has access to both the stored and downloaded data of any `2 number of nodes. Therefore, (`1 , `2 ) eavesdropper has access to xout i co out for i ∈ E1 and xin for j ∈ E2 for some E1 , E2 such that E1 , E2 ⊂ [1 : n], |E1 | = `1 , |E2 | = `2 , and E1 ∩ E2 = ∅. j , xj , xj (See Fig. 2.) This is the eavesdropper model defined in [27] (adapted here to the cooperative repair setting), which generalizes the eavesdropper model considered in [5]. The eavesdropper is assumed to know the coding scheme employed by the DSS. At the MBCR point, a newcomer downloads αMBCR = γMBCR amount of data. Thus, allowing an eavesdropper to access the data downloaded during a node repair besides the content stored on the node does not provide the eavesdropper with any additional information. However, at the MSCR point, repair bandwidth is strictly greater than the per node storage αMSCR and an eavesdropper potentially gains more information if in addition to content stored on a node it also has access to the data downloaded during repair of the same node. We summarize the eavesdropper model together with the definition of achievability of a secure file size in the following. Definition 2 (Security against an (`1 , `2 ) eavesdropper). A DSS is said to achieve a secure file size of Ms against an (`1 , `2 ) eavesdropper, if for any sets E1 and E2 of size `1 and `2 , respectively, I(f s ; e) = 0. Here, f s is the secure file of size Ms , which is first encoded to file f of size M before storing it on DSS, and e is the eavesdropper observation vector given by in co out e , {xout : i ∈ E1 , j ∈ E2 }. We use I(·; ·) to denote mutual information. i , xj , xj , xj We remark that, as it will be clear from the following sections, when a file f (of size M) which contains a secure file (of size Ms ) is stored on a DSS, the remaining M − Ms symbols of f can be utilized as an additional data, which does not have security constraints. Yet, noting the possibility of storing this insecure data, we will refer to this uniformly distributed part as the random data, which is utilized to achieve security. Thus, we consider files of form f = (f s , r), where r can represent random/insecure data. (We remark that DSS properties such as repair bandwidth and per node storage at the MBCR/MSCR point are defined over the file size M.) Here, we note the following lemma, which will be used in the following parts of the sequel. Lemma 3 (Secrecy Lemma [25], [27]). Consider a system with secure file symbols f s , random symbols r (independent of f s ), and an eavesdropper with observations given by e. If H(e) ≤ H(r) and H(r|f s , e) = 0, then I(f s ; e) = 0. Proof: See Appendix A. Finally, we provide a lemma summarizing how the cut values (from source to data collector DC) in the flow graph can be computed while some of the nodes are eavesdropped in the network. Lemma 4. [File size upper bound under secrecy constraints [28]] Consider a secure file f s of size Ms , i.e., Ms = H(f s ). Consider an (`1 , `2 ) eavesdropper observing the nodes in the sets E1 , E2 for some E1 , E2 ⊂ {1, · · · , n} as defined in Definition 2. Consider also that the data collector DC contacts to nodes in the set K = E10 ∪ E20 ∪ R for some E10 ⊆ E1 , E20 ⊆ E2 , and |K| = k. (We assume `1 + `2 < k, as otherwise the secrecy capacity of the network is zero.) Enumerating the nodes in K as {1, · · · , k}, we have k X s M ≤ H(sj |s1 , · · · , sj−1 , sE10 , dE20 ). (5) j=1

Proof: The proof is summarized in Appendix B. (See also [28].) We use (5) (in some cases with a loose bound on the conditional entropy term) in the the following sections to obtain bounds on the secure file size. We remark that in addition to discounting for the previously contacted nodes s1 , · · · , si−1 , this bound also discounts for the leakage to the eavesdropper, by taking into account the leakage to the set {sE10 , dE20 }. Here, the minimum bound on the file size occurs when E10 = E1 and E20 = E2 in the lemma above. Hence, in order to obtain tighter upper bounds on secure file size, we consider only the scenarios for which the data collector connects to all the nodes being eavesdropped. E. Maximum rank distance (MRD) codes via Gabidulin construction In some of the following sections of the sequel, we consider maximum rank distance (MRD) pre-coding of the data at hand before storing it on DSS by using cooperative regenerating codes. Here, we introduce the Gabidulin construction of MRD codes [46]–[49]. First, we introduce some notation. In vector representation, the norm of a vector v ∈ FN q m is the column rank of v over the base field Fq , denoted by Rk(v|Fq ). (This is the maximum number of linearly independent coordinates of v over the base field Fq , for a given basis of Fqm over Fq . A basis also establishes an isomorphism between N -length vectors, in FN qm , to m × N matrices, in Fm×N . Then, Rk(v|F ) = rank(V), where V is the corresponding matrix of v for the given basis.) q q Rank distance between two vectors v1 , v2 ∈ FN q m is defined as d(v1 , v2 ) = Rk(v1 − v2 |Fq ). (In matrix representation, this is equivalent to the rank of the difference of the two corresponding matrices of the vectors, i.e., rank(V1 − V2 ).) Codes utilizing this distance metric are referred to as rank metric codes.

8

An [N, K, D] rank metric code over the extension field Fqm achieving the maximum rank distance D = N − K + 1 (for m ≥ N ) can be constructed with the following linearized polynomial. (This is referred to as the Gabidulin construction of MRD codes, or Gabidulin codes [46]–[49].) f (g) =

K−1 X

ui g [i] ,

(6)

i=0

where [i] , q i , ui ∈ Fqm , and g is an indeterminate which takes value in Fqm . Given N linearly independent (over Fq ) points, {g1 , g2 , . . . , gN } ⊂ Fqm , the codeword c = (c1 , c2 , . . . , cN ) for a given set of K message (information) symbols K−1 P [i] ui gj for j = [1 : N ]. With generator matrix representation, u = (u0 , u2 , . . . , uK−1 ) ∈ FK q m is obtained as cj = f (gj ) = i=0 [K−1]

[K−1]

we have c = uG, where G = [g1 , · · · , gN ; · · · ; g1 , · · · , gN ]. We remark that a linearized polynomial f (·) satisfies f (a1 g1 + a2 g2 ) = a1 f (g1 ) + a2 f (g2 ), for any a1 , a2 ∈ Fq and g1 , g2 ∈ Fqm . This property is utilized in our code constructions. III. S ECURE MBCR CODES In this section, we study secure minimum bandwidth cooperative regenerating codes. We first present an upper bound on the secure file size that can be supported by an MBCR code. Then, we present exact repair coding schemes achieving the derived bound. In addition, we analyze how the cooperation affects the penalty paid in securing storage systems. A. Upper bound on secure file size of MBCR codes We have the following result for upper bound on secure file size for a DSS employing MBCR codes. Proposition 5. Cooperative regenerating codes operating at the MBCR point with a secure file size of Ms satisfy Ms

≤

=

k(2d − k + t)β 0 − `1 (2d − `1 + t)β 0

(k − `1 )(2d + t − k − `1 )β 0 ,

(7)

and the MBCR point is given by β = 2β 0 , α = γ = (2d + t − 1)β 0 for a file size of M = k(2d − k + t)β 0 . Proof: We consider the scenario where µ groups of nodes (each group having t nodes) are consecutively repaired in DSS as introduced in Section II-C. Accordingly, the data collector DC contacts ni ∈ [0 : t] nodes in the ith repair group such that µ−1 P ni = k. Without loss of generality we index these nodes as K = {1, . . . , k}. We consider two types of cuts in each group i=0

contacted by the DC: mi number of nodes have the first cut type (xin , xco |xout ), and ni − mi number of nodes have the second cut type (|xin , xco , xout ), 0 ≤ i ≤ µ − 13 . We consider `1 number of colluding eavesdroppers, each observing the contents of different nodes. Note that, for MBCR point analysis, we can consider `2 = 0 without loss of generality, as the amount of the data a particular node stores is equal to the amount of the data it downloads during its repair. We denote the number of eavesdroppers on the nodes in the first cut type as l1i,1 , 0 ≤ i ≤ µ − 1, and the number of eavesdroppers on the nodes in the second cut type as l1i,2 , 0 ≤ i ≤ µ − 1, such that l1i,1 ≤ mi ,

l1i,2 ≤ ni − mi , and µ−1 X i=0

l1i ≤ `1 ,

where l1i = l1i,1 + l1i,2 . We consider the repair scenario represented in Fig. 4 and utilize Lemma 4 to obtain the desired bound. Here, for repair group i, due to the eavesdroppers, the nodes that belong to the first type can only add the value of (mi − l1i,1 )α to the cut. That is, the right hand side of (5) evaluates to 0 for the l1i,1 number of eavesdropped nodes, and evaluates to α for the remaining mi − l1i,1 number of nodes of first type in ith repair group. The second type, on the other hand, consists of ni − mi nodes in repair group i, out of which l1i,2 of them are eavesdropped. As the amount of the data downloaded during a node repair is equal to per node storage at the MBCR point, the nodes that are eavesdropped do not add a value to the cut. (For node j in ith repair group, if j ∈ K and j is an eavesdropped node of second type, then right hand side of (5) evaluates 3 Note that the cuts of the form (xin , xco |xout ) give a cut value of α as opposed to (xin |xco , xout ), which has cut value larger than α. Since we are interested in the cuts of smaller size, we do not consider the cuts (xin |xco , xout ).

9

t − ni l1i,1 mi − l1i,1

DC l1i,2 ni − mi − l1i,2 Fig. 4: The repair scenario considered to obtain an upper bound on secure file size for MBCR codes. Only a single repair group with t number of nodes is shown. First t − ni nodes are not contacted by DC. The following l1i,1 nodes are eavesdropped, mi − l1i,1 nodes are contacted by DC with a cut of type (xin , xco |xout ), l1i,2 nodes are eavesdropped, and ni − mi − l1i,2 nodes are contacted by DC with a cut of type (|xin , xco , xout ). For the last ni − mi nodes, only the symbols downloaded from the first t − ni nodes contribute to the flow. as H(sj |s1 , · · · , sj−1 , sE1 ) = H(dj |s1 , · · · , sj−1 , sE1 ) = 0. This follows as one can get sj from dj and vice versa for the MBCR point, and sj ⊆ sE1 . Therefore, the contribution of these nodes to the cut through their download links evaluates to zero in value.) Consider the remaining ni − mi − l1i,2 number of nodes in the repair group i, denoted as Ni . These nodes contact d i−1 P live nodes, nr number of these contacted nodes belong to the previously repaired groups. In addition, these nodes contact r=0

t − ni nodes that are previously repaired but not contacted by DC. For these nodes, the right hand side of (5) can be evaluated as X j∈Ni

(a)

H(sj |s1 , · · · , sj−1 , sE1 ) =

X j∈Ni

H(dj |s1 , · · · , sj−1 , sE1 )

(b)

= H(dNi |sP , sE1 )

(c)

≤ |Ni | (d −

i−1 X r=0

nr )β + (t − ni )β 0

! ,

where (a) follows as one can get sj from dj and vice versa for the MBCR point, (b) follows by summing the conditional entropy terms over j ∈ Ni where sP denotes the set of nodes that are repaired before repairing the ones in Ni , and (c) follows by upper bounding H(dNi |sP , sE1 ) by assuming each node in Ni receives independent symbols from the previously repaired nodes and from the first t − ni nodes of this repair group. With |Ni | = ni − mi − l1i,2 , we have s

M ≤ where

µ−1 X i=0

mi − l1i,1 α + ni − mi − l1i,2 Ci ,

(8)

10

Ci =

d−

i−1 X

! nr

r=0

β + (t − ni ) β 0 .

(9)

We remark that the cut-value, i.e., the right hand side of (8), is minimized when we have µ−1 X

(l1i,1 + l1i,2 ) = `1 .

i=0

= 0, l1i,2 = l1i (for which the right hand side of (8) evaluates to (ni − l1i )Ci ) We consider two scenarios in (8), (i) mi = i,1 i i,2 and (ii) mi = ni , l1 = l1 , l1 = 0 (for which the right hand side of (8) evaluates to (ni − l1i )α). Hence, we obtain ( )! ! µ−1 i−1 X X s i 0 M ≤ (ni − l1 ) × min α, d − nr β + (t − ni ) β , (10) 0, l1i,1

r=0

i=0

where

µ−1 P i=0

l1i = `1 .

Note that, at the MBCR point, we have α = dβ + (t − 1)β 0 .

(11)

Utilizing this, we consider the following case for (10). Case 1: µ = k, ni = 1, ∀i = 0, · · · , k − 1. This case corresponds to a repair scenario where the data collector contacts only one node from each repair group. Accordingly, we have the following bound.

Ms

≤

k−1 X i=0

(1 − l1i ) ((d − i)β + (t − 1)β 0 )

Here, the minimum cut value corresponds to having l1i = 1 for i = 0, 1, · · · , `1 − 1, and l1i = 0 for i = `1 , . . . , k − 1. Hence, we get Ms

≤

k−1 X i=`1

(d − i)β + (t − 1)β 0 ,

from which we obtain (k − `1 )(2d − k − `1 + 1) β + (k − `1 )(t − 1)β 0 . 2 The bound in (12) evaluates to the stated bound at the MBCR point. Ms ≤

(12)

Remark 6. One can also consider the following repair scenarios in (10). Case 2: If t ≥ k, µ = 1, n0 = k. Here, data collector contacts to nodes belonging to a single repair group. Accordingly, we have Ms

≤ (k − `1 ) (dβ + (t − k)β 0 ) .

(13)

Case 3: If t < k, µ = bk/tc + 1, ni = t for i = 0, · · · , µ − 2, and nµ−1 = k − bk/tc t. Here, data collector contacts to every node in every repair group (except for the last repair group). Denoting a , bk/tc and b , k − at, so that k = at + b, from (10), we obtain Ms ≤

min a

l1i ≤t s.t.

P i=0

a−1 X l1i =`1 i=0

(t − l1i )(d − it)β + (b − l1a ) {(d − at)β + (t − b)β 0 } .

(14)

We observe that both (13) and (14) evaluate to loose bounds compared to that of (12). (For some parameters, Case 2/3 provides the same bound as that in Case 1. But, in general, Case 2/3 gives loose bound compared to Case 1. Details of this analysis are omitted for brevity.) In the following sections, we show that the bound given by (12) is achievable, and hence it is the best bound that one can obtain for the MBCR point. That is, the repair scenario considered for Case 1 above is one of the worst cases and results in the tightest bound for the MBCR point under the secrecy constraints for all parameters. (For some parameters, Case 2/3 above represents an equivalently challenging bottleneck repair scenario for security in MBCR codes as well.)

11

c¯1

Ψ

c¯d−k

Ψ Φ

r fs

MRD

c1

...

cnk+k(d−k)

c1 ck+1 c(n−1)k+1

··· ···

ck c2k

z1,2 · · · z1,n y1,1 · · · yd−k,1 y1,2 · · · yd−k,2 z2,1 · · · z2,n

···

cnk

y1,n · · · yd−k,n zn,1 zn,2 · · ·

...

zn−1,n

Fig. 5: The data (r, f s ) is encoded with MRD coding into codeword symbols c1 , · · · , cnk+k(d−k) . Each row on the right represents a node in DSS, and the first nk symbols are placed to n nodes uniformly without additional coding. The remaining ¯j = (cnk+(j−1)k+1 , . . . , cnk+jk ) for j = 1, · · · , d − k. Then, c ¯j , of length-k, is encoded into yj = symbols are represented as c (yj,1 , . . . , yj,n ) using an MDS code, generator matrix of which is denoted by Ψ. Finally, d primary symbols of node i, given by {c(i−1)k+1 , . . . , cik , y1,i , . . . yd−k,i }, is encoded into (n − 1) symbols long codeword zi = (z1,i , . . . , zi−1,i , zi+1,i , . . . , zn,i ) using Φ as a generator matrix; and zj,i is placed at node j 6= i. B. Code construction for secure MBCR when n = d + t In this section, we focus on the special case n = d + t. (The case of n > d + t will be considered in the following section.) We consider secrecy pre-coding of the data at hand before storing it to DSS using an MBCR code. We establish this pre-coding with maximum rank distance (MRD) codes introduced in Section II-E. (Please refer to Fig. 5.) Consider the normalized MBCR point given by M = k(2d − k + t), β 0 = 1, β = 2, α = γ = 2d + t − 1, Ms = k(2d − k + t) − `1 (2d − `1 + t), and n = d + t. (The case of β 0 > 1 can be obtained by implementing independent codes parallelly in the system.) We use MRD codes with N = K = M; hence, the rank distance bound D ≤ N − K + 1 is saturated at D = 1. Accordingly, we utilize [M, M, 1] MRD codes over Fqm , which maps length M vectors (each element of it being in Fqm ) to length M codewords in FM q m (with m ≥ N = M). The coefficients of the underlying linearized polynomial (f (g)) s s s and Ms secure data symbols denoted by f s ∈ FM are chosen by M − M random symbols denoted by r ∈ FM−M qm qm . (That is, u = (r, f s ) in (6).) The corresponding linearized polynomial f (g) is evaluated at M points {g1 ,. . . , gM }, which are linearly independent over Fq . We denote these as cj = f (gj ) for j = 1, · · · , M. This finalizes the secrecy pre-coding step. The second encoding step is based on the encoding scheme for cooperative repair proposed in [20]. (Here, we will summarize file recovery and node repair processes for the case of MRD pre-coding, and provide the proof of security.) Split the M symbols into two parts a) c1 to cnk , and b) cnk+1 to cnk+k(d−k) . (Note that n = d + t and M = nk + k(d − k).) The first part is divided into n groups of k symbols, and stored in n nodes. Here, node i stores c(i−1)k+1 to cik . The second part is divided into d − k groups of k symbols. These symbols are encoded with an (n, k) MDS code, and stored on n nodes. In particular, ¯j = (cnk+(j−1)k+1 , . . . , cnk+jk ) by utilizing some MDS encoding matrix Ψ yj = (yj,1 , . . . , yj,n ) is generated from symbols c of size k × n; then, yj,i is stored at node i, for j = 1, · · · , d − k. Node i, having stored {c(i−1)k+1 , . . . , cik , y1,i , . . . yd−k,i }, which is referred to as the primary data of node i, encodes these symbols using an (n − 1, d) MDS code that has a generator matrix given by a (generalized) Cauchy matrix Φ of size d × (n − 1). (This choice of Φ ensures that [Id Φ] is a generator matrix for an (n + d − 1, d) MDS code [50].) Let zi = (z1,i , . . . , zi−1,i , zi+1,i , . . . , zn,i ) denote the (n − 1) symbols long codeword obtained by encoding the primary data of node i. These n − 1 symbols are stored in every other node one-by-one. In particular, node j 6= i stores zj,i . We call {zj,i : i ∈ [1 : n], i 6= j} as the secondary data. This procedure is repeated for every node, so that each node i stores {c(i−1)k+1 , . . . , cik , y1,i , . . . , yd−k,i , zi,1 , . . . , zi,i−1 , zi,i+1 , . . . , zi,n }, and hence total number of symbols stored at each node is k + (d − k) + (n − 1) = d + n − 1 = 2d + t − 1 = α. File recovery at DC: DC connects to any k nodes, without loss of generality we assume the first k nodes. From yj,1:k , DC can obtain cnk+(j−1)k+1 , · · · , cnk+jk , for each j = [1 : d − k]. It can re-encode these into yj,1:n using the MDS code, and obtain the other y symbols at the remaining nodes. Then, for each i ∈ [k + 1 : n], DC can use the MDS property of [Id Φ], to obtain c(i−1)k+1 , · · · , cik symbols of node i from the k secondary data symbols of the contacted nodes, i.e., zj,i for j = [1 : k], and additional d − k symbols, yj,i for j = [1 : d − k]. Having obtained c1 , · · · , cM , DC can perform interpolation to solve for both data and random coefficients. Node repair: Assume that the first t nodes fail. From the secondary data stored in the remaining d = n − t nodes, zt+1,i , · · · , zn,i , one can recover c(i−1)k+1 , · · · , cik and y1,i , · · · , yd−k,i for node i = 1, · · · , t. (This corresponds to sending 1 symbol from each of d nodes to each of the t nodes.) Then, to recover the secondary data stored at each node under repair, say for the node j = 1, · · · , t, every other node, i.e., nodes i 6= j, including the nodes under repair, computes and sends its corresponding encoded primary data, i.e., zj,i , to node j. (This corresponds to sending 1 symbol from each node to each of the t nodes.) This achieves β = 2 and β 0 = 1 symbols for the repair procedure. Security: Consider that the eavesdropper is observing the first `1 nodes. (See Fig. 6.) Let C , {c1 , . . . , c`1 k }, Y , {y1,1 , . . . , yd−k,1 , · · · , y1,`1 , . . . , yd−k,`1 }, Z , {zj,i for j = 1, . . . , `1 , and i = `1 + 1, · · · , n}. Due to the coding scheme, the symbols {zj,i } for j = 1, · · · , `1 ; i = 1, · · · , `1 ; and j 6= i are linear combinations of the symbols in C ∪ Y. In addition, the symbols in the sets C, Y, Z correspond to linearly independent evaluation points. This follows due to the code construction as detailed in the following. We remark that symbols in C are clearly independent of the

12

c1 ck+1

··· ···

c(ℓ1 −1)k+1 · · · c(n−1)k+1

···

ck c2k

y1,1 · · · yd−k,1 z1,2 · · · z1,ℓ1 z1,ℓ1 +1 · · · y1,2 · · · yd−k,2 z2,1 · · · z2,ℓ1 z2,ℓ1 +1 · · ·

cℓ1 k y1,ℓ1 cnk

... ··· ...

yd−k,ℓ1 zℓ1 ,1 zℓ1 ,2 · · ·

z1,n z2,n

zℓ1 ,ℓ1 +1 · · · zℓ1 ,n

y1,n · · · yd−k,n

Fig. 6: The eavesdropped nodes are represented by the first `1 rows, each row corresponding to a node. The symbols in the dashed-dotted (green) box are linear combinations of the symbols in C = {c1 , . . . , c`1 k } and Y = {y1,1 , . . . , yd−k,1 , · · · , y1,`1 , . . . , yd−k,`1 }. The remaining symbols denoted with z1:`1 ,`1 +1:n are linearly independent of X and Y due to encoding with the matrix Φ, where z1:`1 ,i is generated from {c(i−1)k+1 , . . . , cik , y1,i , . . . yd−k,i } for i = `1 , · · · , n. For example, the last row, primary symbols of node n generates the last column, i.e., the eavesdropped symbols z1:`1 ,n . (See Fig. 5 for details of the encoding steps.)

ones in Y ∪ Z. However, it is not clear at first sight whether the symbols in Y and Z are independent. Note that, for example, the symbols y1,1:n are dependent, i.e., each one can be uniquely determined by any other k of them due to MDS coding by Ψ. And, symbols y1:d−k,`+1:n generates Z. But, the generation of Z is together with the symbols in c`1 k+1:nk . (See Fig. 6.) In particular, we have the following, ˜ = Z, [C˜ Y˜ ]Φ where C˜ =

c`1 k+1 .. . c(n−1)k+1

··· .. . ···

c(`1 +1)k .. , . cnk

y1,`1 +1 · · · yd−k,`1 +1 .. .. .. Y˜ = , . . . y1,n ··· yd−k,n z1,`1 +1 · · · z`1 ,`1 +1 .. .. .. Z= , . . . z1,n ··· z`1 ,n

˜ is the corresponding `1 columns of Φ. (In the example above, we consider the first `1 columns.) Consider and Φ u ˜ Φ ˜ Φ= ˜l Φ ˜ u , and, accordingly, C˜ Φ ˜ u + Y˜ Φ ˜ l = Z. Here, the symbols in C˜ Φ ˜ u are linearly independent. (This follows, with k × `1 matrix Φ ˜ u will constitute a k × k submatrix of Φ, as appending upper k rows of any k − `1 number of remaining columns of Φ to Φ 0 u ˜ · · · ], where · · · representing the added elements of Φ, we observe that which is non-singular. Denoting this matrix as Φ = [Φ ˜ 0 are linearly independent, which implies the linear independence of symbols in C˜ Φ ˜ u .) Then, as the symbols all symbols in CΦ ˜ u + Y˜ Φ ˜ l, in the matrix C˜ are independent of the ones in the set {y1:d−k,1:n }, it follows that symbols in the matrix Z = C˜ Φ i.e., the symbols in the set Z, and the symbols in the set Y are linearly independent. Therefore, due to the linearized property of the code, the eavesdropper, observing `1 α = `1 (2d + t − 1) symbols, has evaluations of the polynomial f (·) at `1 (2d + t − `1 ) linearly independent points. Using the secure data symbols, together with interpolation from these `1 (2d+t−`1 ) symbols, the eavesdropper can solve for `1 (2d+t−`1 ) random symbols. Then, denoting the eavesdroppers’ observation as e, we have H(r|e, f s ) = 0. Since H(e) = H(r), from Lemma 3, we obtain I(f s ; e) = 0. Now, using the upper bound given in Proposition 5, we obtain the following result. Proposition 7. The secrecy capacity at the MBCR point for a file size of M = k(2d − k + t)β 0 is given by Ms = k(2d − k + t)β 0 − `1 (2d − `1 + t)β 0 , if n = d + t.

13

C. Does cooperation enhance/degrade security at MBCR? The repair bandwidth for cooperative regenerating codes is defined by γ = dβ + (t − 1)β 0 . In this section, we analyze γ γ¯ = M s , the ratio of repair bandwidth to the secure file size, referred to as the normalized repair bandwidth (NRBW). Without the security constraints, for which `1 = 0 in Proposition 5, we observe that, at the MBCR point, NRBW is given by 2d + t − 1 , γ¯ (`1 = 0) = k(2d − k + t) which is equal to

γ¯ (`1 = 0, n = d + t) =

2n − t − 1 k(2n − k − t)

for a system with n = d + t. Here, the classical (i.e., non-cooperative) scenario corresponds to t = 1 case, which has an NRBW of 2n − 2 γ¯ (`1 = 0, n = d + t, t = 1) = . k(2n − k − 1) Comparing the last two equations, we see that

γ¯ (`1 = 0, n = d + t) ≥ γ¯ (`1 = 0, n = d + t, t = 1), with equality iff t = 1 (for k > 1). Therefore, without the security constraints, having simultaneous repairs of size greater than 1 actually increases the normalized repair bandwidth. This nature of cooperation also results in the conclusion that deliberately delaying the repairs does not bring additional savings [13]. (This observation is proposed for both MBCR and MSCR points in [13] with an analysis of derivative of γ with respect to t. Here, we provide an analysis with NRBW.) We revisit the above conclusion under security constraints. The question is whether the cooperation (i.e., having a system with multiple failures, or deliberately delaying the repairs) results in a loss/gain in secure DSS. We have γ¯ (n = d + t) = and

2n − t − 1 , k(2n − k − t) − `1 (2n − `1 − t)

γ¯ (n = d + t, t = 1) =

2n − 2 . k(2n − k − 1) − `1 (2n − `1 − 1)

A calculation similar to above shows that γ¯ (n = d + t) ≥ γ¯ (n = d + t, t = 1) with equality if and only if t = 1 (for k > `1 ≥ 0). This shows that NRBW for the case t > 1 is strictly greater than that of t = 1 when n = d + t for `1 < k. The MBCR points given in Proposition 5 for codes satisfying 0 ≤ `1 < k < n, d ≥ k, and d = n − t are given in Table I in Appendix C. As evident from the table, we see that cooperation does not bring additional savings for secure DSS at the MBCR point when d + t = n. This in turn means that one may not delay the repairs to achieve a better performance than that of single failure-repair if d is chosen such that n = d + t for a given t, n. However, if the downloads within the cooperative group are less costly compared to the downloads from the live nodes, then delaying repairs would be beneficial in reducing the total cost. We will revisit this analysis for codes having n > d + t in the next subsection. D. General code construction for secure MBCR The code construction presented in Section III-B has the requirement of d = n − t. However, for practical systems, it may not be possible that a failed node connects to all the remaining nodes. This brings the necessity of code constructions for d < n − t. Remarkably, for a fixed (n, k, d, M), increasing t can reduce the repair bandwidth in the secrecy scenario we consider here. This is reported in [16] for DSS without secrecy constraints. Hence, for a fixed d, delaying the repairs can be advantageous, e.g., when there is a limit on the number of live nodes that can be contacted for a node repair. In the following, we present a general construction which works for any parameters, in particular for n > d + t. The construction is based on the MBCR code proposed in [21]. In [21], a bivariate polynomial is constructed using M = k(2d + t − k) message symbols (over Fq ) as the coefficients of the polynomial: X X X F (Y, Z) = aij Y i Z j + bij Y i Z j + cij Y i Z j (15) 0≤i

0≤i

k≤i

Here, {aij }, {bij }, and {cij } denote M message symbols. Given q > n, two set of n distinct points, {y1 , y2 , . . . , yn } and {z1 , z2 , . . . , zn }, are chosen. The ith node in the DSS store the following 2d + t − 1 evaluations of polynomial F (Y, Z). F (yi , zi ), F (yi , zi⊕1 ), . . . , F (yi , zi⊕(d+t−1) ) F (yi⊕1 , zi ), F (yi⊕2 , zi ), . . . , F (yi⊕(d−1) , zi ),

(16)

14

F (y1 , z1 ) F (y2 , z1 ) ··· F (y`1 , z1 ) ··· F (yd , z1 )

F (y1 , z2 ) F (y2 , z2 )

··· ···

F (y1 , z`1 ) F (y2 , z`1 )

··· ···

F (y1 , zd+t ) F (y2 , zd+t )

F (y2 , zd+t+1 )

F (y`1 , z2 )

···

F (y`1 , z`1 )

···

F (y`1 , zd+t )

F (y`1 , zd+t+1 )

F (yd , z2 ) F (yd+1 , z2 )

··· ··· ···

F (yd , z`1 ) F (yd+1 , z`1 ) · F (yd+`1 −1 , z`1 )

···

F (y`1 , zd+t−1+`1 )

Fig. 7: Observed symbols at the eavesdroppers for a given `1 . where ⊕ denotes addition modulo n. The first d + t evaluations at node i can be seen as the evaluations of the univariate polynomial fi (Z) = F (yi , Z) of degree at most d + t − 1 at d + t points. This uniquely defines the polynomial fi (Z). Similarly, the first evaluation in (16), F (yi , zi ), along with last d − 1 evaluations, F (yi⊕1 , zi ), . . . , F (yi⊕(d−1) , zi ), uniquely define the univariate polynomial gi (Y ) = F (Y, zi ) of degree at most d − 1. This property of the proposed bivariate polynomial based coding scheme is utilized for the exact node repair and data reconstruction processes at the MBCR point. (We refer to [21] for details.) In order to get an (`1 , 0)-secure code at the MBCR point, we rewrite the polynomial in (15) as follows: X X aij Y i Z j + aij Y i Z j F (Y, Z) = 0≤i<`1 , 0≤j<`1

+

X

aij Y i Z j +

`1 ≤i

+

bij Y i Z j +

aij Y i Z j

X

bij Y i Z j

`1 ≤i

0≤i<`1 , k≤j

+

X

`1 ≤i

X

X

0≤i<`1 , `1 ≤j

X

cij Y i Z j +

cij Y i Z j

(17)

k≤i

k≤i

Next, we choose `21 + `1 (k − `1 ) + (k − `1 )`1 + `1 (d + t − k) + (d − k)`1 = `1 (2d + t − `1 ) coefficients of F (Y, Z), a0:`1 −1,0:`1 −1 ∪ a0:`1 −1,`1 :k−1 ∪ a`1 :k−1,0:`1 −1 ∪ b0:`1 −1,k:d+t−1 ∪ ck:d−1,0:`1 −1 , to be symbols drawn uniformly at random from Fq in an i.i.d. manner. Remaining k(2d + t − k) − `1 (2d + t − `1 ) = Ms coefficients of F (Y, Z) are chosen to be the data symbols f s that need to be stored on the DSS. Each node i ∈ [n] stores the evaluation of F (Y, Z) as illustrated in (16). It follows from the description of the coding scheme of [21] in the beginning of this subsection that the resulting coding scheme is an exact repairable code at the MBCR point. Next, we show that the proposed scheme is indeed (`1 , 0)-secure. Let e, f s , and r denote the data observed by an eavesdropper, the original data to be stored, and the randomness added to the original data before encoding, respectively. It is sufficient to show (i) H(e) ≤ H(r) and (ii) H(r|f s , e) = 0 in order to establish the secrecy claim (see Lemma 3). To argue the first requirement, noting that number of eavesdropped symbols are `1 α = `1 (2d + t − 1), we will show that `21 − `1 number of these are linearly dependent on the remaining ones. The eavesdropper, without loss of generality considering the first `1 nodes as eavesdropped nodes, observes the symbols given in Fig. 7. Due to the code construction, each row above represents evaluations of a polynomial of degree less than d + t and each column represents a polynomial of degree less than d. Hence, we observe that each of the symbols denoted with a colored font in the matrix of Fig. 7 is a linear combination of the remaining ones. Therefore, H(e) ≤ `1 α − `1 (`1 − 1) = H(r). In order to show that second requirement also holds, we present a method to decode randomness r given f s and data stored on any `1 nodes. Once we know the data symbols f s , we can remove the monomials associated to data symbols in F (Y, Z) and the contribution of these monomials from the polynomial evaluations stored on DSS. Let Fb(Y, Z) denote the bivariate polynomial that we obtain by removing the data monomials: X X Fb(Y, Z) = aij Y i Z j + aij Y i Z j 0≤i<`1 , 0≤j<`1

+

X

aij Y i Z j +

`1 ≤i

+

X k≤i

cij Y i Z j

0≤i<`1 , `1 ≤j

X

bij Y i Z j

0≤i<`1 , k≤j

(18)

15

Fb(Y, Z) can be rewritten as: Fb(Y, Z) =

X

X

a ˆij Y i Z j +

0≤i<`1 , 0≤j<`1

ˆbij Y i Z j +

0≤i<`1 , `1 ≤j

X

cˆij Y i Z j

(19)

`1 ≤i

where a ˆ0:`1 −1,0:`1 −1 = a0:`1 −1,0:`1 −1 , ˆb0:`1 −1,`1 :k−1 = a0:`1 −1,`1 :k−1 , ˆb0:`1 −1,k:d+t−1 = b0:`1 −1,k:d+t−1 , cˆ`1 :k−1,0:`1 −1 = a`1 :k−1,0:`1 −1 , cˆk:d−1,0:`1 −1 = ck:d−1,0:`1 −1 . Fb(Y, Z) in (19) takes the same form as F (Y, Z) in (15) with k replaced with `1 . Now, the randomness r, coefficients of Fb(Y, Z) in (19), can be decoded from the data observed on `1 nodes using the data reconstruction method described in [21]. Thus, we obtain the following result. Proposition 8. The secrecy capacity at the MBCR point for a file size of M = k(2d − k + t) is given by Ms = k(2d − k + t) − `1 (2d − `1 + t) for any n ≥ d + t. We list some instances of this construction in Table II in Appendix C. As evident from the table, cooperation helps to reduce the repair bandwidth if d < n − t. Thus, (secure) coding schemes for the case of n > d + t are of significant interest in order to reduce the repair bandwidth in cooperative repair. IV. S ECURE MSCR C ODES We first consider an upper bound on the secure file size for DSS employing minimum storage cooperative regenerating (MSCR) codes. We then utilize appropriate secrecy pre-coding mechanisms to construct achievable schemes for the upper bound. A. Upper bound on the secure file size At the MSCR point, nodes have minimum possible storage, i.e., α = M k . Using the cut-set analysis given in Section II, α M one can obtain that the minimum repair bandwidth can be attained with β = β 0 = d−k+t = k(d−k+t) . (See also [13], [15].) Therefore, the amount of data downloaded during a node repair is larger than per node storage α at the MSCR point. Keeping this in mind, we consider two kinds of eavesdropped nodes for security constraints: storage-eavesdropped nodes (E1 ) and download-eavesdropped nodes (E2 ). Using the size of these sets we denote the eavesdropper setting with (`1 , `2 ) as introduced in Section II. Here, for a node in E2 , an eavesdropper observes both the data downloaded from live nodes and from cooperating nodes (other nodes in the same repair group). Similar to the analysis given in Section III-A, and utilizing Lemma 4, we obtain the following bound on the secure file size at the MSCR point.

Ms ≤

k−1 X i=0

n o (1 − l1i − l2i ) × min α − I(si ; di,E2 ), (d − i)β + (t − 1)β 0 ,

(20)

where si and di,E2 denote the data stored on node i and data downloaded from node i for repair of nodes in set E2 , respectively. Here, for ith repair group, we consider ni = 1 number of nodes to be contacted by DC. We assume that we have l1i number of storage-eavesdropped nodes (from E1 ) and l2i number of download-eavesdroppers (from E2 ) in repair group i. Compared to the MBCR bounds, due to eavesdroppers in E2 , nodes that are not eavesdropped may leak information during their participation in the repair of a node having an download-observing eavesdropper. Thus, the values of the cuts of type 1 include additional penalty terms I(si ; di,E2 ), counting the leakage from the storage at the ith node to nodes indexed with E2 . (That is, we consider a loose bound compared to that of (5), i.e., H(si |s1 , · · · , si−1 , sE1 , dE2 ) = H(si ) − I(si ; s1 , · · · , si−1 , sE1 , dE2 ) ≤ α − I(si ; di,E2 ), as di,E2 ⊂ dE2 .) Considering the MSCR point values of α, β, and β 0 given above, the second term inside each min{} in (20) is larger than the first term. Hence, considering that the first k − `1 − `2 repairs are eavesdropper-free, (20) evaluates to the following bound. Proposition 9. Cooperative regenerating codes operating at the MSCR point with a secure file size of Ms satisfy Ms ≤

k−`X 1 −`2 −1 i=0

α − I(si ; di,E2 ),

where the MSCR point is given by β = β 0 , α = (d − k + t)β, for a file size of M = k(d − k + t)β. In addition, at the MSCR point, one can bound I(si ; di,E2 ) ≥ β 0 = β and obtain the bound Ms ≤ (k − `1 − `2 )(α − β).

16

B. Code construction for secure MSCR when k = t = 2 We consider an interference alignment approach based on the one proposed in [19] with k = t = 2. For any (n, k, d, t) with d ≥ k and n = d + t, we have α = d − k + t = n − 2 and M = k(d − k + t) = 2(d − k + t) = 2α at the normalized MSCR point, i.e., β = β 0 = 1. (The general case of β > 1 can be obtained by a parallel utilization of independent codes with β = 1.) For k = 2, the bound given in Proposition 9 implies that the achievability of positive secure file size in the presence of an eavesdropper is possible only when (`1 , `2 ) = (1, 0) or (`1 , `2 ) = (0, 1). Corresponding bounds are given by Ms ≤ α and Ms ≤ α − 1, respectively. (For the bound corresdpoing to `2 = |E2 | = 1, di,E2 necessarily consists of one symbol as β = β 0 = 1, and the non-eavesdropped node participates in the repair of the eavesdropped node by sending β or β 0 symbols. Note that DC contacts only k = 2 nodes, and one of them is eavesdropped for the purpose of obtaining the upper bound here.) In the following, we construct codes achieving the stated bounds for both cases, hence establishing the secrecy capacity when k = t = 2. We show this with codes having n = d + t, i.e., all the surviving nodes participate in a node repair. The construction can be extended to cases with n > d + t by following a similar approach and choosing a larger field size. Case 1: Ms = α when (`1 , `2 ) = (1, 0) Consider a large enough finite field Fq (conditions on the required field will be given later) which has ω as its generator, α number of random symbols r1 , · · · , rα , and α number of secure information symbols s1 , · · · , sα . Both information and random symbols are uniformly distributed over the field. We construct a file f = (a1 , . . . , aα , b1 , . . . , bα ) = (r1 , . . . , rα , r1 + s1 , . . . , rα + sα ) of size M over Fq . Our coding scheme is described by the following placement. • Store a = (a1 , · · · , aα ) at the first node, • Store b = (b1 , · · · , bα ) at the second node, and (i−1) mod α • Store ri = (a1 + ω b1 , · · · , aα + ω (i+α−2) mod α bα ) at ith parity node, i ∈ {1, · · · , α = n − 2}. Note that we implement one-time pad scheme of Vernam [26] for the symbols represented as bi in this construction. We represent the stored symbols of ith parity node as rTi = aT + Bi bT , where Bi is a diagonal matrix with its diagonal elements given by {ω (i−1) mod α , . . . , ω (i+α−2) mod α }. Data collector DC can reconstruct the file f by contacting to any of the k = 2 nodes, and solving α groups of 2 equations over 2 unknowns. (Each group gives 2 equations over 2 unknowns. For example, the first symbols for the systematic nodes are a1 = r1 and b1 = r1 + s1 , and these two equations can be solved to obtain (r1 , s1 ).) From file f , it can then obtain the secure symbols s1 , · · · , sα . This establishes data reconstruction property of the code. Cooperative repair process is similar to that of the code proposed in [19], as summarized in the following. Without loss of generality, we consider cooperative repair of two systematic nodes. Repairs of stages involving parity nodes can be performed as that of the systematic nodes after change of variables [19]. The first systematic node downloads v1,i rTi = v1,i aT + zbT from ith parity node which stores rTi = aT + Bi bT . Here, v1,i = zB−1 and z , (1, · · · , 1). After i this step, the first systematic node has the symbols −1 T T T T c1 = {zB−1 1 a + zb , · · · , zBd a + zb }.

Note that the repair process is such that the interference is aligned by having terms zbT in each of the symbols downloaded by the first systematic node. The second systematic node obtains d = n − 2 symbols c2 = {v2,1 rT1 , · · · , v2,d rTd } from d parity nodes. Here, the repair process is such that the interference is aligned by having terms zaT in each of the symbol in c2 . Accordingly, we have v2,i = z, which gives v2,i rTi = zaT + zBi bT and c2 = {zaT + zB1 bT , · · · , zaT + zBd bT }. Now, the second systematic node chooses the repair vector v1,0 = (ω 0 + · · · + ω α−1 )−1 z and sends v1,0 cT2 = νv1,0 aT + zbT to the first systematic node. Here ν denotes the sum of α ones over Fq , which depends on the characteristics of the field Fq . Then, the first systematic node solves d + 1 equations {νv1,0 aT + zbT , v1,1 aT + zbT , · · · , v1,d aT + zbT } in d + 1 unknowns {a1 , · · · , aα , zbT } [19]. This follows if the matrix M = [νv1,0 , 1; v1,1 , 1; · · · ; v1,d , 1] is invertible, when we represent the observed symbols at the first systematic node as M[a1 , · · · , aα , zbT ]. (Invertibility of this matrix is stated in [19]. Our analysis shows that this holds if q > n − 1 is a sufficiently large prime number such that the generator w of Fq used above satisfies (ω 0 + · · · + ω α−1 )2 w−(α−1) ∈ / {0, α2 }. Details are omitted for brevity.) The second systematic node can be repaired in a similar manner. It remains to show the secrecy of the file. Here, regardless of eavesdropped node being a systematic or a parity node, given the secure symbols, f s = {s1 , · · · , sα }, the eavesdropper can obtain α equations in α unknowns r = r1 , · · · , rα . This allows the eavesdropper to solve for r, and shows that H(r|f s , e) = 0, where the eavesdropper observes the content of the eavesdropped node, i.e., e = sE1 . We see that, at the eavesdropped node, the content of the stored data necessarily satisfies H(e) = H(sE1 ) = α. Then, as the code satisfies both H(e) ≤ H(r) and H(r|f s , e) = 0, we obtain from Lemma 3 that I(f s ; e) = I(s1 , · · · , sα ; sE1 ) = 0. Case 2: Ms = α − 1 when (`1 , `2 ) = (0, 1) We modify the above construction by considering the file given by M = {a1 , r1 , · · · , aα , rα , b1 , r1 + s1 , · · · , bα−1 , rα−1 + sα−1 , bα , rα+1 }. The reconstruction and cooperative repair processes are the same as that of the previous case. We

17

r fs

MRD

m1

c1

...

...

mt

ckt

V V

node 1

node n

T m1 v1T , · · · , m1 vn T mt v1T , · · · , mt vn

Fig. 8: MRD codeword is c1:kt . MDS input vector is mj = (c(j−1)k+1 , . . . , cjk ) for j = 1, · · · , t. Vandermonde matrix is represented with V, columns of which are {v1T , · · · , vnT }. The placement of the symbols on different nodes is shown on the right. show that the secrecy constraint is satisfied here. The content of the eavesdropped node sE2 is generated from the downloaded data dE2 . Thus, we need to show I(f s ; e) = 0 with f s = {s1 , · · · , sα−1 } and e = dE2 . Without loss generality, we assume that the eavesdropper observes the first systematic node. Considering the repair process described above, we have e = dE2 = {v1,0 aT + zbT , v1,1 aT + zbT , · · · , v1,d aT + zbT }, from which we obtain that H(e) ≤ α + 1. In addition, as the eavesdropper can solve for (a, zbT ), it can solve for r = {r1 , · · · , rα+1 } from the α + 1 number of equations in (a, zbT ), after canceling out the contribution of secure symbols f s = {s1 , · · · , sα−1 } from zbT . This shows that H(r|f s , e) = 0. Using this, together with H(r) = α + 1 and Lemma 3, we obtain that I(f s ; e) = I(s1 , · · · , sα−1 ; dE2 ) = 0. As a result of the above construction of secure MSCR codes with k = t = 2, we obtain the following result. Proposition 10. The secrecy capacity at the MSCR point for a file size of M = k(d − k + t)β is given by Ms = αβ, if (`1 , `2 ) = (1, 0) and k = t = 2; and by Ms = (α − 1)β, if (`1 , `2 ) = (0, 1) and k = t = 2. C. Code construction for secure MSCR when d = k The above construction is limited to the k = 2 case. Here, we provide secure MSCR code when d = k, and hence allowing k > 2. (Note that as d ≥ k > `1 + `2 , we necessarily have `1 + `2 < d = k here.) Here, we apply a two-stage encoding, where we utilize an MRD code for pre-coding to achieve secrecy. Consider M = k(d−k+t) = kt, β = β 0 = 1, α = d−k+t = t, Ms = (k−`1 −`2 )(t−`2 ) = kt−(`1 +`2 )t−`2 (k−`1 −`2 ), and n ≥ d+t. (The general case of β > 1 can be obtained by a parallel utilization of independent codes with β = 1.) We encode M−1 P i the data using the linearized polynomial f (g) = ui g q . (This is the Gabidulin construction of MRD codes summarized in i=0

Section II-E.) The coefficients of f (g) is chosen by M − Ms number of random symbols denoted by r and Ms data symbols denoted by f s . The function f (g) is evaluated at M points in Fqm , {g1 , . . . , gM }, that are linearly independent over Fq . (Here, the data and random symbols belong to Fqm with m ≥ M.) We denote these evaluations as ci = f (gi ) for i = 1, · · · , M = kt. We consider the code provided in [17] for the secrecy setting here. We place these M = kt symbols into vectors m1 , · · · , mt , each having k symbols. We encode these vectors with a Vandermonde matrix of size k × n, whose columns are represented as viT for i = 1, · · · , n. We store {m1 viT , . . . , mt viT } at node i. (See Fig. 8.) Data collector DC, by contacting any k nodes, can obtain k equations for each of mj , and solve them to obtain ci for i = 1, · · · , M = kt. It can then obtain the secure data symbols by performing interpolation for the underlying linearized polynomial f (g) [46]. Next, we briefly describe the cooperative node repair process for the codes under consideration. For node repair, consider that node jl ∈ {j1 , j2 , . . . , jt } contacts d = k live nodes, referred to as {i1 , i2 , . . . , ik }. It downloads ml viTr from live node ir for r = 1, · · · , k. Node jl then obtains ml by solving these k equations. It stores ml vjTl , and sends ml vjTl0 to node jl0 ∈ {j1 , j2 , . . . , jt }, l0 6= l, i.e., the remaining nodes under repair. Each node jl ∈ {j1 , j2 , . . . , jt } repeats this procedure. As a result, node jl recovers its ml0 vjTl for l0 ∈ [1 : t], l0 6= l by downloading a symbol from each node under repair. We show the secrecy constraint has met assuming `2 ≤ t here. (Otherwise, this construction can not achieve a positive secure file size as an eavesdropper obtains all m1:t symbols from download-eavesdropped nodes.) We note that an eavesdropper obtain `2 k equations from the d = k live nodes by observing repair of `2 nodes (the observed symbols reveal `2 number of mj s), and an additional `2 (t − `2 ) = `2 (α − `2 ) symbols from the remaining nodes under repair. Besides this, the eavesdropper gets `1 α number of symbols from the content stored on `1 storage-eavesdropped nodes. However, `1 `2 of these symbols are linearly dependent to the ones downloaded by nodes in E2 (as the nodes in E2 recover `2 number of mj s during node repair). (See Fig. 9.) Therefore, using the given polynomial and the secure data of length Ms , the eavesdropper can solve for the random symbols using these `2 (k + α − `2 ) + `1 (α − `2 ) = `2 (k + t − `2 ) + `1 (t − `2 ) = (k − `1 − `2 )`2 + (`1 + `2 )t = M − Ms linearly independent evaluations of the polynomial f (g). This implies that we have H(r|f s , e) = 0, where e denotes the observations of the eavesdropper associated with E1 and E2 . This construction also satisfies H(e) = `2 k + `2 (α − `2 ) + `1 (α − `2 ) = H(r) as argued above, and it follows from Lemma 3 that we have I(f s ; e) = 0. Thus, the proposed coding scheme achieves the secure file size of kt − (`1 + `2 )t − `2 (k − `1 − `2 ) when `2 ≤ t; consequently, we have the following.

18

node 1

node ℓ2 + ℓ1

m1 v1T ...

m2 v1T

···

mℓ2 v1T

mℓ2 +1 v1T

···

mt v1T

T m1 v1(1)

T m1 v1(2)

···

T m1 v1(k)

m1 vℓT2

m2 vℓT2

···

mℓ2 vℓT2

mℓ2 +1 vℓT2

···

mt vℓT2

mℓ2 vℓT2 (1)

mℓ2 vℓT2 (2)

···

mℓ2 vℓT2 (k)

m1 vℓT2 +1 ...

m2 vℓT2 +1

···

mℓ2 vℓT2 +1

mℓ2 +1 vℓT2 +1

···

mt vℓT2 +1

m1 vℓT2 +ℓ1

m2 vℓT2 +ℓ1

···

mℓ2 vℓT2 +ℓ1

mℓ2 +1 vℓT2 +ℓ1

···

mt vℓT2 +ℓ1

Fig. 9: The observed symbols at the eavesdropper. Without loss of generality we assume first `2 nodes belong to E2 and the T following `1 nodes belong to E1 . We denote the symbols downloaded at i ∈ E2 from live node xi(j) as mi vi(j) for j = [1 : d], where i(j) denotes the jth contacted live node for repair of node i. For the nodes in E2 , we indicate these downloaded symbols on the right hand side of the figure, within the box with solid lines. (On the left hand side, we have the stored content of each T node.) From downloaded symbols to E2 nodes, the eavesdropper observes dE2 = {mi vi(j) : i = 1, · · · , `2 ; j = 1, · · · , k}. (Here, T T d = k.) The symbols in the first `2 columns, i.e., {m1 v1 , . . . , m1 v`2 +`1 , · · · , m`2 v1T , . . . , m`2 v`T2 +`1 }, are functions of the symbols in dE2 due to the construction (i.e., MDS coding). These `2 k symbols in dE2 in addition to the (`1 +`2 )(t−`2 ) symbols located in the middle, i.e., {m`2 +1 v1T , . . . , m`2 +1 v`T2 +`1 , · · · , mt v1T , . . . , mt v`T2 +`1 }, correspond to `2 k + (`1 + `2 )(t − `2 ) linearly independent evaluations of the linearized polynomial f (g). Proposition 11. The secure file size of Ms = (k − `1 − `2 )[t − `2 ]+ β is achievable at the MSCR point for a file size of M = k(d − k + t)β when d = k. Note that this achieves the secrecy capacity when `2 ≤ 1 for any `1 as can be observed from the bound given by Proposition 9. V. C ONCLUSION Distributed storage systems (DSS) store data on multiple nodes. These systems not only require resilience against node failures, but also have to satisfy security constraints and to perform multiple node repairs. Regenerating codes proposed for DSS address the node failure resilience while efficiently trading off storage vs. repair bandwidth. In this paper, we considered secure cooperative regenerating codes for DSS against passive eavesdropping attacks. The eavesdropper model analyzed in this paper belongs to the class of passive attack models, where the eavesdroppers observe the content of the nodes in the system. Accordingly, we considered an (`1 , `2 )-eavesdropper, where the stored content at any `1 nodes, and the downloaded content at any `2 nodes are leaked to the eavesdropper. With such an eavesdropper model, we studied the security for the multiple repair scenario, in particular secure cooperative regenerating codes. For the minimum bandwidth cooperative regenerating (MBCR) point, we established a bound on the secrecy capacity, and by modifying the existing coding schemes in the literature, devised new codes achieving the secrecy capacity. For the minimum storage cooperative regenerating (MSCR) point, on the other hand, we proposed an upper bound and lower bounds on the secure file size, which match under special cases. The results show that it is possible to design regenerating codes that not only efficiently trades storage for repair bandwidth, but are also resilient against security attacks in a cooperative repair scenario. Finally, as evident from some of our secrecy-achieving constructions, we would like to emphasize the role that the maximum rank distance (MRD) codes can take in secrecy problems. In particular, we have utilized the Gabidulin construction [46] of MRD codes and properties of linearized polynomials in obtaining some of the results. Similar properties of such codes have been utilized to achieve secrecy in earlier works [53]–[56], and they proved their potential again here as an essential component for achieving secrecy in DSS. (See also [38] for utilization of these codes in active eavesdropper settings, and [28] for constructing locally repairable codes with and without secrecy constraints.) We list some avenues for further research here. The secrecy capacity of MSCR codes remains as an open problem, as we have established the optimal codes under some parameter settings. To attempt solving this problem, codes for MSCR without security constraints have to be further investigated. One can also consider cooperative repair in a DSS having locally repairable structure. As other distributed systems, DSS may exhibit simultaneous node failures that need to be recovered with local connections. According to our best knowledge, this setting has not been studied (even without security constraints). Our ongoing efforts are on the design of coding schemes for DSS satisfying these properties. ACKNOWLEDGEMENT The authors would like to thank the reviewers for their insightful comments and suggestions.

19

A PPENDIX A P ROOF OF L EMMA 3 Proof: The proof follows from the classical techniques given by [25], where instead of 0-leakage, -leakage rate is considered. The application of this technique in DSS is considered in [27], as summarized below. We have I(f s ; e)

= (a)

H(e) − H(e|f s )

≤

H(e) − H(e|f s ) + H(e|f s , r)

≤

H(r) − I(e; r|f s )

(b) (c)

=

(d)

=

H(r|f s , e) 0,

where (a) follows by non-negativity of H(e|f s , r), (b) is the condition H(e) ≤ H(r), (c) is due to H(r|f s ) = H(r) as r and f s are independent, (d) is the condition H(r|f s , e) = 0. Remark 12. If the eavesdropper has a vanishing probability of error in decoding r given e and f s , then, by Fano’s inequality, one can write H(r|f s , e) ≤ |r|, and, by following the above steps, can show the bound I(f s ; e) ≤ |r|, where |r| is the number of random bits, and can be made small if the probability of error is vanishing. This shows that the leakage rate I(f s ; e)/|e| is vanishing. (See, e.g., [25].)

A PPENDIX B P ROOF OR L EMMA 4 We summarize the steps given in [28]. Ms

=

H(f s )

(a)

H(f s ) − I(f s ; sE10 , dE20 )

=

= (b)

=

(c)

=

≤ ≤ =

H(f s |sE10 , dE20 )

H(f s |sE10 , dE20 ) − H(f s |sK ) H(f s |sE10 , dE20 ) − H(f s |sE10 , dE20 , sK ) I(f s ; sK |sE10 , dE20 ) H(sK |sE10 , dE20 ) k X j=1

H(sj |s1 , · · · , sj−1 , sE10 , dE20 ),

where (a) follows by the security constraint, i.e., 0 ≤ I(f s ; sE10 , dE20 ) ≤ I(f s ; sE1 , dE2 ) = 0, (b) is due to the data construction property, i.e., H(f s |sK ) = 0, (c) is due to 0 ≤ H(f s |sE10 , dE20 , sK ) ≤ H(f s |sK ) = 0. A PPENDIX C NRBW VALUES FOR MBCR POINT IN DSS The parameters of Proposition 5 are given in the following tables. `1 = 0 case corresponds to the systems without security constraints. t = 1 case corresponds to non-cooperative case. Red (green) font highlights cases with greater (respectively, smaller) cooperative NRBW (γ/Ms ) compared to that for t = 1. We observed that the same trend continues for higher n values.

20

TABLE I: NRBW for n = 4, 5, d ≥ k, d + t = n. n 4 4 4 4 4 4 4 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5

k 2 2 2 2 3 3 3 2 2 2 2 2 2 3 3 3 3 3 3 4 4 4 4

l 0 0 1 1 0 1 2 0 0 0 1 1 1 0 0 1 1 2 2 0 1 2 3

t 1 2 1 2 1 1 1 1 2 3 1 2 3 1 2 1 2 1 2 1 1 1 1

d 3 2 3 2 3 3 3 4 3 2 4 3 2 4 3 4 3 4 3 4 4 4 4

β/Ms 0.2000 0.2500 0.5000 0.6667 0.1667 0.3333 1.0000 0.1429 0.1667 0.2000 0.3333 0.4000 0.5000 0.1111 0.1333 0.2000 0.2500 0.5000 0.6667 0.1000 0.1667 0.3333 1.0000

β 0 /Ms 0.1000 0.1250 0.2500 0.3333 0.0833 0.1667 0.5000 0.0714 0.0833 0.1000 0.1667 0.2000 0.2500 0.0556 0.0667 0.1000 0.1250 0.2500 0.3333 0.0500 0.0833 0.1667 0.5000

γ/Ms 0.6000 0.6250 1.5000 1.6667 0.5000 1.0000 3.0000 0.5714 0.5833 0.6000 1.3333 1.4000 1.5000 0.4444 0.4667 0.8000 0.8750 2.0000 2.3333 0.4000 0.6667 1.3333 4.0000

M 10 8 10 8 12 12 12 14 12 10 14 12 10 18 15 18 15 18 15 20 20 20 20

Ms 10 8 4 3 12 6 2 14 12 10 6 5 4 18 15 10 8 4 3 20 12 6 2

TABLE II: NRBW for n = 4, 5, d ≥ k, d + t ≤ n. n 4 4 4 4 4 4 4 4 4 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5

k 2 2 2 2 2 2 3 3 3 2 2 2 2 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 3 4 4 4 4

l 0 0 0 1 1 1 0 1 2 0 0 0 0 0 0 1 1 1 1 1 1 0 0 0 1 1 1 2 2 2 0 1 2 3

t 1 1 2 1 1 2 1 1 1 1 1 2 1 2 3 1 1 2 1 2 3 1 1 2 1 1 2 1 1 2 1 1 1 1

d 3 2 2 3 2 2 3 3 3 4 3 3 2 2 2 4 3 3 2 2 2 4 3 3 4 3 3 4 3 3 4 4 4 4

β/Ms 0.2000 0.3333 0.2500 0.5000 1.0000 0.6667 0.1667 0.3333 1.0000 0.1429 0.2000 0.1667 0.3333 0.2500 0.2000 0.3333 0.5000 0.4000 1.0000 0.6667 0.5000 0.1111 0.1667 0.1333 0.2000 0.3333 0.2500 0.5000 1.0000 0.6667 0.1000 0.1667 0.3333 1.0000

β 0 /Ms 0.1000 0.1667 0.1250 0.2500 0.5000 0.3333 0.0833 0.1667 0.5000 0.0714 0.1000 0.0833 0.1667 0.1250 0.1000 0.1667 0.2500 0.2000 0.5000 0.3333 0.2500 0.0556 0.0833 0.0667 0.1000 0.1667 0.1250 0.2500 0.5000 0.3333 0.0500 0.0833 0.1667 0.5000

γ/Ms 0.6000 0.6667 0.6250 1.5000 2.0000 1.6667 0.5000 1.0000 3.0000 0.5714 0.6000 0.5833 0.6667 0.6250 0.6000 1.3333 1.5000 1.4000 2.0000 1.6667 1.5000 0.4444 0.5000 0.4667 0.8000 1.0000 0.8750 2.0000 3.0000 2.3333 0.4000 0.6667 1.3333 4.0000

M 10 6 8 10 6 8 12 12 12 14 10 12 6 8 10 14 10 12 6 8 10 18 12 15 18 12 15 18 12 15 20 20 20 20

Ms 10 6 8 4 2 3 12 6 2 14 10 12 6 8 10 6 4 5 2 3 4 18 12 15 10 6 8 4 2 3 20 12 6 2

21

R EFERENCES [1] S. Rhea, P. Eaton, D. Geels, H. Weatherspoon, B. Zhao, and J. Kubiatowicz, “Pond: The OceanStore Prototype,” in Proc. of the 2nd USENIX Conference on File and Storage Technologies (FAST’03), San Francisco, CA, Mar. 2003. [2] S. Ghemawat, H. Gobioff, and S.-T. Leung, “The Google file system,” in Proc. of the Nineteenth ACM Symposium on Operating Systems Principles (SOSP’03), New York, NY, Oct. 2003. [3] R. Bhagwan, K. Tati, Y.-C. Cheng, S. Savage, and G. M. Voelker, “Total Recall: System support for automated availability management,” in Proc. of the First ACM/USENIX Symposium on Networked Systems Design and Implementation (NSDI’04), Berkeley, CA, Mar. 2004. [4] A. G. Dimakis, P. B. Godfrey, Y. Wu, M. J. Wainwright, and K. Ramchandran, “Network coding for distributed storage systems,” IEEE Trans. Inf. Theory, vol. 56, no. 9, pp. 4539–4551, Sep. 2010. [5] S. Pawar, S. El Rouayheb, and K. Ramchandran, “Securing dynamic distributed storage systems against eavesdropping and adversarial attacks,” IEEE Trans. Inf. Theory, vol. 57, no. 10, pp. 6734–6753, Oct. 2011. [6] K. V. Rashmi, N. B. Shah, and P. V. Kumar, “Optimal exact-regenerating codes for distributed storage at the MSR and MBR points via a product-matrix construction,” IEEE Trans. Inf. Theory, vol. 57, no. 8, pp. 5227–5239, Aug. 2011. [7] D. S. Papailiopoulos, A. G. Dimakis, and V. R. Cadambe, “Repair optimal erasure codes through hadamard designs,” in IEEE Trans. Inf. Theory, vol. 59, no. 5, pp. 3021–3037, May 2013. [8] V. R. Cadambe, C. Huang, and J. Li, “Permutation code: Optimal exact-repair of a single failed node in MDS code based distributed storage systems,” in Proc. 2011 IEEE International Symposium on Information Theory (ISIT 2011), Saint Petersburg, Russia, Jul. 31-Aug. 5 2011. [9] I. Tamo, Z. Wang, and J. Bruck, “Zigzag codes: MDS array codes with optimal rebuilding,” IEEE Trans. Inf. Theory, vol. 59, no. 3, pp. 1597–1616, Mar. 2013. [10] Z. Wang, I. Tamo, and J. Bruck, “On codes for optimal rebuilding access,” in Proc. 49th Annual Allerton Conference on Communication, Control, and Computing (Allerton 2011), Monticello, IL, Sep. 2011. [11] Y. Hu, Y. Xu, X. Wang, C. Zhan, and P. Li, “Cooperative recovery of distributed storage systems from multiple losses with network coding,” IEEE J. Sel. Areas Commun., vol. 28, no. 2, pp. 268–276, Feb. 2010. [12] X. Wang, Y. Xu, Y. Hu, and K. Ou, “MFR: Multi-loss flexible recovery in distributed storage systems,” in Proc. 2010 IEEE International Conference on Communications (ICC 2010), Cape Town, South Africa, May 2010. [13] A.-M. Kermarrec, N. Le Scouarnec, and G. Straub, “Repairing multiple failures with coordinated and adaptive regenerating codes,” in Proc. 2011 International Symposium on Network Coding (NetCod 2001), Beijing, China, Jul. 2011. [14] K. W. Shum and Y. Hu, “Existence of minimum-repair-bandwidth cooperative regenerating codes,” in Proc. 2011 International Symposium on Network Coding (NetCod 2011), Beijing, China, Jul. 2011. [15] F. Oggier and A. Datta, “Coding techniques for repairability in networked distributed storage systems,” Foundations and Trends in Communications and Information Theory, vol. 9, no. 4, pp. 383–466, Jun. 2013. [16] K. W. Shum and Y. Hu, “Exact minimum-repair-bandwidth cooperative regenerating codes for distributed storage systems,” in Proc. 2011 IEEE International Symposium on Information Theory (ISIT 2011), Saint Petersburg, Russia, Jul. 31-Aug. 5 2011. [17] K. W. Shum, “Cooperative regenerating codes for distributed storage systems,” in Proc. 2011 IEEE International Conference on Communications (ICC 2011), Kyoto, Japan, Jun. 2011. [18] K. W. Shum and Y. Hu, “Cooperative regenerating codes,” IEEE Trans. Inf. Theory, vol. 59, no. 11, pp. 7229–7258, Nov. 2013. [19] N. Le Scouarnec, “Exact scalar minimum storage coordinated regenerating codes,” in Proc. 2012 IEEE International Symposium on Information Theory (ISIT 2012), Cambridge, MA, Jul. 2012. [20] S. Jiekak and N. Le Scouarnec, “CROSS-MBCR: Exact minimum bandwith coordinated regenerating codes,” CoRR, vol. abs/1207.0854, Jul. 2012. [21] A. Wang and Z. Zhang, “Exact cooperative regenerating codes with minimum-repair-bandwidth for distributed storage,” in Proc. IEEE INFOCOM 2013, Turin, Italia, Apr. 2013. [22] O. Goldreich, Foundations of Cryptography: Volume II, Basic Applications. Cambridge University Press, 2004. [23] H. Delfs and H. Knebl, Introduction to Cryptography: Principles and Applications, 2nd ed. Springer, 2007. [24] C. E. Shannon, “Communication theory of secrecy systems,” The Bell System Technical Journal, vol. 28, no. 4, pp. 656–715, Oct. 1949. [25] A. Wyner, “The wire-tap channel,” The Bell System Technical Journal, vol. 54, no. 8, pp. 1355–1387, Oct. 1975. [26] G. S. Vernam, “Cipher printing telegraph systems for secret wire and radio telegraphic communications,” J. Amer. Inst. Elect. Eng., vol. 45, pp. 295–301, Jan. 1926. [27] N. B. Shah, K. V. Rashmi, and P. V. Kumar, “Information-theoretically secure regenerating codes for distributed storage,” in Proc. 2011 IEEE Global Telecommunications Conference (GLOBECOM 2011), Houston, TX, Dec. 2011. [28] A. S. Rawat, O. O. Koyluoglu, N. Silberstein, and S. Vishwanath, “Optimal locally repairable and secure codes for distributed storage systems,” IEEE Trans. Inf. Theory, vol. 60, no. 1, pp. 212–236, Jan. 2014. [29] S. Goparaju, S. El Rouayheb, R. Calderbank, and H. V. Poor, “Data secrecy in distributed storage systems under exact repair,” in Proc. 2013 International Symposium on Network Coding (NetCod 2013), Calgary, Canada, June 2013. [30] F. Oggier and A. Datta, “Self-repairing homomorphic codes for distributed storage systems,” in Proc. IEEE INFOCOM 2011, Shanghai, China, Apr. 2011. [31] ——, “Self-repairing codes for distributed storage - A projective geometric construction,” in Proc. 2011 IEEE Information Theory Workshop (ITW 2011), Paraty, Brazil, May 2011. [32] P. Gopalan, C. Huang, H. Simitci, and S. Yekhanin, “On the locality of codeword symbols,” IEEE Trans. Inf. Theory, vol. 58, no. 11, pp. 6925–6934, Nov. 2012. [33] C. Huang, M. Chen, and J. Li, “Pyramid codes: Flexible schemes to trade space for access efficiency in reliable data storage systems,” in Proc. Sixth IEEE International Symposium on Network Computing and Applications (NCA 2007), Cambridge, MA, Jul. 2007. [34] N. Prakash, G. M. Kamath, V. Lalitha, and P. V. Kumar, “Optimal linear codes with a local-error-correction property,” in Proc. 2012 IEEE International Symposium on Information Theory (ISIT 2012), Cambridge, MA, Jul. 2012. [35] D. S. Papailiopoulos and A. G. Dimakis, “Locally repairable codes,” in Proc. 2012 IEEE International Symposium on Information Theory (ISIT 2012), Cambridge, MA, Jul. 2012. [36] F. Oggier and A. Datta, “Byzantine fault tolerance of regenerating codes,” in Proc. 2011 IEEE International Conference on Peer-to-Peer Computing (P2P), Kyoto, Japan, Aug. 31 - Sep. 2, 2011. [37] K. V. Rashmi, N. B. Shah, K. Ramchandran, and P. V. Kumar, “Regenerating codes for errors and erasures in distributed storage,” in Proc. 2012 IEEE International Symposium on Information Theory (ISIT 2012), Cambridge, MA, Jul. 2012. [38] N. Silberstein, A. S. Rawat, and S. Vishwanath, “Error resilience in distributed storage via rank-metric codes,” in Proc. 50th Annual Allerton Conference on Communication, Control, and Computing, Monticello, IL, Oct. 2012. [39] Y. S. Han, H. T. Pai, R. Zheng, and P. K. Varshney, “Update-efficient regenerating codes with minimum per-node storage,” in Proc. 2013 IEEE International Symposium on Information Theory (ISIT 2013), Istanbul, Turkey, Jul. 2013. [40] A. Shamir, “How to share a secret,” Communications of the ACM, vol. 22, no. 11, pp. 612–613, Nov. 1979. [41] D. A. Patterson, G. Gibson, and R. H. Katz, “A case for redundant arrays of inexpensive disks (RAID),” in Proc. 1988 ACM SIGMOD international conference on Management of data (SIGMOD’88) New York, NY, USA: ACM, 1988, pp. 109–116.

22

[42] M. Blaum, J. Brady, J. Bruck, and J. Menon, “EVENODD: An efficient scheme for tolerating double disk failures in RAID architectures,” IEEE Transactions on Computers, vol. 44, no. 2, pp. 192–202, Feb. 1995. [43] M. Blaum, J. Bruck, and A. Vardy, “MDS array codes with independent parity symbols,” IEEE Trans. Inf. Theory, vol. 42, no. 2, pp. 529–542, Mar. 1996. [44] R. Ahlswede, N. Cai, S.-Y. R. Li, and R. W. Yeung, “Network information flow,” IEEE Trans. Inf. Theory, vol. 46, no. 4, pp. 1204–1216, Jul. 2000. [45] T. Ho, M. Medard, R. Koetter, D. R. Karger, M. Effros, J. Shi, and B. Leong, “A random linear network coding approach to multicast,” IEEE Trans. Inf. Theory, vol. 52, no. 10, pp. 4413–4430, Oct. 2006. [46] E. M. Gabidulin, “Theory of codes with maximum rank distance,” Probl. Peredachi Inf., vol. 21, no. 1, pp. 3–16, Jul. 1985. [47] P. Delsarte, “Bilinear forms over a finite field, with applications to coding theory,” Journal of Combinatorial Theory, Series A, vol. 25, no. 3, pp. 226–241, Nov. 1978. [48] R. Roth, “Maximum-rank array codes and their application to crisscross error correction,” IEEE Trans. Inf. Theory, vol. 37, no. 2, pp. 328–336, Mar. 1991. [49] F. J. MacWilliams and N. J. A. Sloane, The Theory of Error-Correcting Codes, ser. North-Holland Mathematical Library. Elsevier, 1977. [50] R. M. Roth and G. Seroussi, “On generator matrices of MDS codes,” IEEE Trans. Inf. Theory, vol. 31, no. 6, pp. 826–830, Nov. 1985. [51] N. B. Shah, K. V. Rashmi, P. V. Kumar, and K. Ramchandran, “Interference alignment in regenerating codes for distributed storage: Necessity and code constructions,” IEEE Trans. Inf. Theory, vol. 58, no. 4, pp. 2134–2158, Apr. 2012. [52] C. Suh and K. Ramchandran, “Exact-repair MDS codes for distributed storage using interference alignment,” in Proc. 2010 IEEE International Symposium on Information Theory (ISIT 2010), Austin, TX, Jun. 2010. [53] E. M. Gabidulin, A. V. Paramonov, and O. V. Tretjakov, “Ideals over a non-commutative ring and their application in cryptology,” in Advances in Cryptology - EUROCRYPT ’91, ser. Lecture Notes in Computer Science, vol. 547. Berlin, Heidelberg: Springer-Verlag, 1991, pp. 482–489. [54] K. Gibson, “The security of the Gabidulin public key cryptosystem,” in Advances in Cryptology - EUROCRYPT ’96, ser. Lecture Notes in Computer Science, vol. 1070. Springer, 1996, pp. 212–223. [55] R. Koetter and F. R. Kschischang, “Coding for errors and erasures in random network coding,” IEEE Trans. Inf. Theory, vol. 54, no. 8, pp. 3579–3591, Aug. 2008. [56] D. Silva, F. R. Kschischang, and R. Koetter, “A rank-metric approach to error control in random network coding,” IEEE Trans. Inf. Theory, vol. 54, no. 9, pp. 3951–3967, Sep. 2008.