On Block Security of Regenerating Codes at the Mbr Point for Distributed Storage Systems
In:
Submitted By hoang84 Words 4963 Pages 20
On Block Security of Regenerating Codes at the MBR Point for Distributed Storage Systems
Son Hoang Dau∗ , Wentu Song† , Chau Yuen‡
Singapore University of Technology and Design, Singapore Emails: {∗ sonhoang dau, † wentu song, ‡ yuenchau}@sutd.edu.sg
Abstract—A passive adversary can eavesdrop stored content or downloaded content of some storage nodes, in order to learn illegally about the file stored across a distributed storage system (DSS). Previous work in the literature focuses on code constructions that trade storage capacity for perfect security. In other words, by decreasing the amount of original data that it can store, the system can guarantee that the adversary, which eavesdrops up to a certain number of storage nodes, obtains no information (in Shannon’s sense) about the original data. In this work we introduce the concept of block security for DSS and investigate minimum bandwidth regenerating (MBR) codes that are block secure against adversaries of varied eavesdropping strengths. Such MBR codes guarantee that no information about any group of original data units up to a certain size is revealed, without sacrificing the storage capacity of the system. The size of such secure groups varies according to the number of nodes that the adversary can eavesdrop. We show that code constructions based on Cauchy matrices provide block security. The opposite conclusion is drawn for codes based on Vandermonde matrices.
I. I NTRODUCTION A. Background In recent years, the demand for large-scale data storage has grown explosively, due to numerous applications including large files and video sharing, social networks, and back-up systems. Distributed Storage Systems (DSS) store a tremendous amount of data using a massive collection of distributed storage nodes. Applications of DSS include large data centers and P2P storage systems such as OceanStore [1], Total Recall [2], and Dhash++ [3] that deploy a huge number of storage nodes spread widely over the Internet. Since any storage device is individually unreliable and subject to failure, redundancy must be introduced to provide the much-needed system-level protection against data loss due to storage node failure. The simplest form of redundancy is replication. By storing n identical copies of a file at n distributed nodes, one copy per node, an n-duplication system can guarantee the data availability as long as no more than (n − 1) nodes fail. Such systems are very easy to implement and maintain, but extremely inefficient in storage space utilization, incurring tremendous waste in equipment, building space, and cost for powering and cooling. More sophisticated systems employing erasure coding based on maximum distance separable (MDS) codes [4] can expect to considerably improve the storage efficiency. However, a DSS based on MDS codes often incurs considerable communication bandwidth during node repair: a replacement node has to download the whole file to recover
the content of just one node. To overcome the disadvantages of both replication and erasure codes, regenerating codes were proposed for DSS in the groundbreaking work of Dimakis et al. [5]. In this work, we only consider regenerating codes for homogeneous DSS and limit ourselves to minimum bandwidth regenerating (MBR) codes with exact repair [5]. (For regenerating codes for non-homogeneous DSS, the reader may refer to [6], [7], for instance. For another important notion of node repair, please refer to [8] and references therein.) In practice, one important aspect in the design of a DSS code is its security. As the storage nodes can well be located at different places, and new nodes join the network all the time to replace failing nodes, it is possible that at a certain point, some nodes might be compromised by some unauthorized party, referred to as an adversary. The adversary can be either • active, i.e. controlling the node, modifying the data, and sending erroneous data to other nodes [9]–[11], or • passive, i.e. knowing the data stored in the node and observing all communication between this node and the other nodes, in order to learn illegally the content of the file stored by the DSS [9], [12]–[14]. In this work, we focus on the security of DSS codes against the second type of adversary, the passive adversary. We also refer to this type of adversary as eavesdropper. We illustrate in Fig. 1 a scenario where the adversary can observe all data stored in one storage node. The data file is split into five data units f = (f1 , f2 , f3 , f4 , f5 ). Originally there are four storage nodes. At a certain time, Node 4 fails. Node 5 comes in to replace Node 4 (repair). If the content of this node is eavesdropped by Eve, then Eve can obtain the values of two units f4 and f5 explicitly. Similar scenarios occur when Eve eavesdrops any node among the three nodes 1, 2, and 3. Therefore the system is not secure against an adversary who can eavesdrop one storage node. B. Related Work Hereafter we follow the standard notation in the regenerating code literature (see Section II). In their pioneering work, Dimakis et al. [5] established that the maximum file size to be stored in a DSS D(n, k, d) must satisfy the following k M≤
A construction of optimal regenerating codes with exact repair at the MBR point for all n, k, d was proposed by Rashmi et al. [15]. When the stored contents of some nodes are
Fig. 1: Example of a DSS with an eavesdropper. observed by an adversary Eve, Pawar et al. [9] showed that the maximum file size to be stored satisfies k Ms ≤
i= +1
min{(d − i + 1)β, α},
(2)
provided that Eve gains no information (in Shannon’s sense) about the file. This type of security is often referred to as perfect security or strong security in the literature. The parameter is called the adversarial strength. The authors [9] also provided an optimal code construction, based on complete graphs, for the case d = n − 1 that attains the bound (2). We later argue that an extension of their construction based on regular graphs [16] also produces optimal perfectly secure codes for all d with nd even (see Remark 6). Under the same adversary model, Shah et al. [12] constructed optimal codes that attain the bound (2) for all d. The authors used productmatrix codes in their construction. Comparing (1) and (2), it is clear that in order to achieve the perfect security against an adversary which eavesdrops storage nodes, the storage capacity of the system has to be decreased by an amount of ∆M = M − Ms = i=1 min{(d − i + 1)β, α}.
Therefore, perfect security is obtained at the cost of lowering the storage capacity. Additionally, according to the security scheme studied thereof, one has to specify beforehand the strength of the adversary, i.e. the number of storage nodes it can eavesdrop, and then modify the input accordingly to obtain the perfect security. When the strength of the adversary exceeds the specified threshold, nothing is guaranteed on the security of the system. In many practical storage systems, perfect security is either too strict and might not be even necessary, or too costly (too much wasted space in the system) and might not be affordable. Hence weaker security levels at lower costs would be preferred in many practical scenarios. C. Our Contribution In order to address the aforementioned issues with perfect security, we propose to use a broader concept of security from the network coding literature, namely, block security [17]– [19] (also known as security against guessing). A code is b-block secure against an adversary of strength , if the adversary, which accesses at most storage nodes, gains no information about any group of b data units. In the language 2
of information theory, the mutual information between the eavesdropped content and any group of b original data units is zero. The concept of block security describes nicely a hierarchy of different levels of security against eavesdropping. Depending on the adversarial strength, a block secure system can provide a range of different levels of security, from the weakest level to the strongest level: • 1-block security (also referred to as weak security) implies that no individual data unit is revealed, • 2-block security implies that no information on any group of two data units is revealed, • ···, • M-block security, where M is the total number of data units (the file size), implies the perfect security, i.e. no information about the original data is revealed. If the system is weakly secure, although the adversary gains some information about the file, it cannot determine each particular data unit. For instance, if the file is a movie and the data units are movie chunks, then the adversary obtains no information about each individual chunk, and hence cannot play the movie. Furthermore, if the system is b-block secure against an adversary of strength , even when the adversary can access some storage nodes and on top of that, gain knowledge on some other b − 1 data units via some side channel, it still cannot determine each particular data unit. We investigate the security of the two main existing MBR code constructions [15], [16], [20]. Recall that either Vandermonde matrices or Cauchy matrices are often used in these constructions. We prove the following • Vandermonde-based codes are not block secure, • Cauchy-based regular-graph codes [16], [20] are inherently block secure, • Cauchy-based product-matrix codes [15] are inherently block secure. Based on these results, we are able to conclude that using Cauchy matrices rather than Vandermonde in these constructions of MBR codes automatically guarantees weaker levels of security compared with perfect security, but most importantly, without any loss on the storage capacity of the system. We also show that with Cauchy-based constructions of perfectly secure codes [9], [12], certain security level is still guaranteed even when the adversarial strength surpasses the security threshold. More specifically, in addition to being perfectly secure against adversaries of strength not exceeding a specified threshold λ, the codes remain to be block secure against an adversary of strength > λ as long as < k (Fig. 2). The level b of block security gradually decreases as the adversarial strength increases. When ≥ k, the whole file is revealed. perfect 0 λ block k whole file revealed n
Fig. 2: Security of a Cauchy-based system as the adversarial strength varies. The paper is organized as follows. In Section II, we discuss the concept of block security for distributed storage systems.
We analyze the security of regular-graph codes and productmatrix codes in Section III and Section IV, respectively. II. B LOCK S ECURITY FOR D ISTRIBUTED S TORAGE S YSTEMS We denote by Fq the finite field with q elements. Let [n] denote the set {1, 2, . . . , n}. The (Hamming) weight of a vector u ∈ Fn is the number of the nonzero coordinates of u. Apart q from Hamming weight, we also use other standard notions from coding theory such as minimum distance, linear [n, k]q and [n, k, d]q codes, MDS codes, and generator matrices (for instance, see [21]). Let ut denotes the transpose of a vector u. For an m × n matrix M , for i ∈ [m] and j ∈ [n], let M i and M [j] denote the row i and the column j of M , respectively. Let F = (F1 , F2 , . . . , FM ), where Fi ’s (i ∈ [M]) are independent and identically uniformly distributed random variables over Fq . We assume that the file to be stored in the system is f = (f1 , f2 , . . . , fM ) ∈ FM , a realization of F . q We call M the file size and each fi a (original) data unit. We denote by D(n, k, d) a typical DSS with n storage nodes where the file can be recovered from the contents of any k out of n nodes, and to repair a failed node, a new node (referred to as a newcomer) can contact any d nodes to regenerate the content of the failed node. We refer to d as the repair degree. Additionally, each node stores α coded units, i.e. α linear combinations of data units fi ’s. In the repair process, a newcomer downloads β coded units from each of d live nodes. Suppose that β = 1 (data striping is used for larger β). At the MBR point, we have [15], [20] k M = kd − , α = d. 2 Following the adversarial attack model proposed by Pawar et al. [9], we suppose that the adversary can observe the stored contents of some nodes. Let C i denote the random vector over Fα that represents the stored content at Node i. q Definition 1 ( [9]). A DSS D(n, k, d) together with its coding scheme is called perfectly secure against an adversary of strength λ (λ < k) if the mutual information I(F , ∪i∈E C i ) = 0, for all subsets E ⊆ [n], |E| ≤ λ.
stored content of only one node, it cannot deduce any linear combination of two units. Therefore, the system is 2-block secure against an adversary of strength one. In Fig. 3(d), by using a randomly generated variable r, as long as the adversary accesses the stored content of only one node, it cannot deduce any linear combination of the data units, and hence gains no information at all about the stored file. Hence in this case, the system is perfectly secure against an adversary of strength one. It is straightforward that M-block security is equivalent to perfect security, where M is the file size. Hence, perfect security can well be regarded as the highest level of block security. However, perfect security is not given for free. One has to trade some storage capacity for perfect security (see Section I-B). In fact, in the perfectly secure code constructions presented in [9], [12], part of the file has to be replaced by randomly generated variables, hence reducing the useful storage space of the system. By contrast, lower levels of block security can be achieved at essentially no cost, as we later present in Section III and IV. This advantage of block security makes the concept attractive to practical storage systems, where the storage redundancy has to be minimized to maintain a competitive price for the storage service. The following lemma specifies a necessary and sufficient condition for the security of DSS (see [22] for a proof). Lemma 3. Let f = (f1 , f2 , . . . , fM ) ∈ FM be the stored file q and Ef t represent the coded units that the adversary obtains by observing storage nodes. Let C E be the linear errorcorrecting code generated by the rows of the matrix E, and d(C E ) be its minimum distance. Then the adversary cannot deduce any nontrivial linear combination of any group of b data units if and only if b ≤ d(C E ) − 1. III. O N THE S ECURITY OF R EGULAR -G RAPH C ODES We briefly describe the regular-graph codes constructed by Rashmi et al. [20] and El Rouayheb et al. [16] below. Let G be a d-regular graph on n vertices u1 , u2 , . . . , un . Then each vertex of G is adjacent to d edges. Therefore, let e1 , e2 , . . . , end/2 be all nd/2 edges of G. Let G be an (nd/2) × M matrix over Fq satisfying the MDS property: any M rows of G are linearly independent. Then M data units f1 , f2 , . . . , fM are encoded into nd/2 coded units by the transformation ct = (c1 , . . . , cnd/2 ) = Gf t . Node i stores cj if and only if the edge ej is adjacent to the vertex ui . As G is d-regular, each node stores exactly α = d coded units cj ’s. Any set of k nodes together provide kd − k = M distinct 2 coded units cj ’s, hence can recover the whole file thank to the MDS property of the encoding matrix G. When Node i fails (i ∈ [n]), the newcomer contacts Node j if ui and uj are adjacent in G. Since G is d-regular, there are d such nodes. For such a Node j, the newcomer downloads β = 1 coded unit cs if es is the edge connected ui and uj . These d coded units cs are distinct as they correspond to d distinct edges adjacent to ui , and form the content of the failed node. The newcomer simply stores these d coded units and the repair process for Node i is done.
Definition 2. A DSS D(n, k, d) together with its coding scheme is called b-block secure against an adversary of strength λ (λ < k) if the mutual information I(∪j∈B Fj , ∪i∈E C i ) = 0, for all subsets B ⊆ [M], |B| ≤ b, and for all subsets E ⊆ [n], |E| ≤ λ.
Node 1 Node 2 Node 3 f1 f2 f3 (a) Insecure f1+f2 f2+f3 f4+f5 (b) 1-block secure f1+f2+f3 f2+f3+f4 f3+f4+f5 f1+r f2+r f1+f2+r
(c) 2-block secure (d) Perfectly secure
Fig. 3: Different levels of security. We illustrate in Fig. 3 different levels of security for DSS. For instance, in Fig. 3(c), as long as the adversary accesses the 3
A. Cauchy-Based Regular-Graph Codes Are Block Secure A Cauchy matrix is a matrix of form (xi + yj ) , where xi ’s and yj ’s are elements of Fq that satisfy xi + yj = 0 for all i and j. A Cauchy matrix has a special property that any submatrix is again a Cauchy matrix. It is well known that any square Cauchy matrix is invertible. Therefore, any square submatrix of a Cauchy matrix is invertible. This is a crucial property that makes codes based on Cauchy encoding matrices block secure. All missing proofs can be found in [22]. Theorem 4. A DSS D(n, k, d) equipped with a regular-graph code [16] based on a Cauchy encoding matrix is b-block secure against an adversary of strength ( < k), where k k+ −1 . b = kd − − d− = (k − ) d − 2 2 2 Note that nd must be even according to the code construction. For instance, according to Theorem 4, for n = 7, k = 5, d = 6, the degradation of the block security level of a Cauchybased regular-graph code is illustrated in Fig. 4. Note that the file size is M = 5 × 6 − 5 = 20. The corresponding 2
−1
For example, for a DSS D(7, 5, 6) as in Fig. 4, suppose that the specified security threshold is λ = 2, then the degradation of the security is depicted in Fig. 5. Note that now the file size has to be decreased to Ms = 9, according to (2). b security level
9 5 2 O
n = 7, k = 5, d = 6, Ms = 9 perfect threshold λ = 2
blo
ck
1
2 3 4 adversarial strength
5
b 20 n = 7, k = 5, d = 6, M = 20
14 9 5 2 O 1
bl oc
ks ec
ur
ity
2 3 4 adversarial strength
5
Fig. 4: Degradation of the security level for D(7, 5, 6) with a Cauchy-based regular-graph code as the adversarial strength increases. construction of perfectly secure codes [9] is completely the same as the one described at the beginning of this section, except that a subset of data units has to be replaced by a subset of randomly generated variables and that the encoding matrix G has to be either Vandermonde or Cauchy (or more generally, a (transposed) generator matrix of a nested MDS code). Suppose that the Cauchy matrix is used in this construction. Treating the random variables as data units, we can apply Theorem 4 and show that even when the adversarial strength surpasses the specified threshold, although the code is no longer perfectly secure, it is still block secure. Hence we have the following. Corollary 5. Consider a DSS D(n, k, d) equipped with the regenerating code proposed in [9], [16], which is perfectly secure against an adversary of strength at most λ. Suppose that in the construction of the regenerating code, a Cauchy matrix is used. Then when the adversarial strength ( < k) surpasses the threshold λ, the code is no longer perfectly secure, but is still b-block secure, where k k+ −1 b = kd − − d− = (k − ) d − . 2 2 2 4
Fig. 5: Degradation of the security level for D(7, 5, 6) with a perfectly secure Cauchy-based regular-graph code as the adversarial strength increases. Remark 6. The construction of optimal perfectly secure codes with uncoded exact repair was proposed by Pawar et al. [9] for the case d = n − 1. It can be shown [22] that the same construction, i.e. replacing data units by random units and using nested MDS codes, based on regular-graphs [16] also provides optimal perfectly secure codes for all d with nd even. That is why we mention both constructions in Corollary 5. B. Vandermonde-Based Regular-Graph Codes Are Not Block Secure In the extended version of our work [22], an example of a Vandermonde-based regular-graph code which is not even weakly secure against an adversary of strength one is given. The reason behind this unwanted behavior of Vandermondebased codes is due to the fact that not all square submatrices of a Vandermonde matrix are invertible. Further details on this issue can be found in [22]. IV. O N THE S ECURITY OF P RODUCT-M ATRIX C ODES We first briefly describe the MBR product-matrix codes constructed by Rashmi et al. [15]. The file size is M = kd − k = k+1 − k(d − k). Let M be the message matrix 2 2 of the following form S T M= , Tt 0 where S is a k × k symmetric matrix and T is a k × (d − k) matrix. The k+1 entries in the upper-triangular half of S 2 are filled up by k+1 distinct data units drawn from the set 2 {fi }i∈[M] . The remaining k(d − k) data units are used to fill up the second k × (d − k) matrix T . The encoding matrix is Ψ = [Φ ∆], where Φ and ∆ are n × k and n × (d − k) matrices, respectively, chosen in such a way that 1) any d rows of Ψ are linearly independent, 2) any k rows of Φ are linearly independent. Then Node i stores d entries of row i of the matrix ΨM . The encoding matrix Ψ is often chosen as a Vandermonde matrix or a Cauchy matrix. Details on the file reconstruction and node repair processes can be found in [15]. A. Cauchy-Based Product-Matrix Codes Are Block Secure We prove in this section that the Cauchy-based productmatrix code [15] is (k− )-block secure against an adversary of strength at most < k. Note that if k nodes are eavesdropped,
security level
the whole file will be reconstructed. Thus the block security level of the Cauchy-based product-matrix codes is d−(k + − 1)/2 times lower than that of the Cauchy-based regular graphcodes (Theorem 4). The missing proof can be found in [22]. Theorem 7. In the construction of an MBR product-matrix code [15] for a DSS D(n, k, d), if the encoding matrix Ψ is a Cauchy matrix then the code is (k − )-block secure against an adversary of strength ( < k). For instance, according to Theorem 7, for n = 7, k = 5, d = 6, the degradation of the block security level of a Cauchybased product-matrix code is illustrated in Fig. 6. Note that the file size is M = 5×6− 5 = 20. Similar to Corollary 5, 2 b 20 n = 7, k = 5, d = 6, M = 20
f8 . Hence, the code used in this example, which is based on a Vandermonde matrix, is not weakly secure against an adversary of strength two. The Cauchy-based code, however, is weakly secure against an adversary of strength two. R EFERENCES
[1] S. Rhea, C. Wells, P. Eaton, D. Geels, B. Zhao, H. Weatherspoon, and J. Kubiatowicz, “Maintenance-free global data storage,” IEEE Internet Computing, vol. 5, no. 5, pp. 40–49, 2001. [2] R. Bhagwan, K. Tati, Y.-C. Cheng, S. Savage, and G. M. Voelker, “Total recall: system support for automated availability management,” in Proc. 1st ACM/USENIX Symp. Networked Syst. Des. Implementation (NSDI), 2004, pp. 25–25. [3] F. Dabek, J. Li, E. Sit, J. Robertson, M. Kaashoek, and R. Morris, “Designing a DHT for low latency and high throughput,” in Proc. 1st ACM/USENIX Symp. Networked Syst. Des. Implementation (NSDI), 2004, pp. 7–7. [4] H. Weatherspoon and J. Kubiatowicz, “Erasure coding vs. replication: A quantitative comparison,” in Proc. 1st Int. Workshop Peer-to-Peer Syst. (IPTPS), 2001, pp. 328–338. [5] A. Dimakis, P. Godfrey, M. Wainwright, and K. Ramchandran, “Network Coding for distributed storage systems,” in Proc. 26th IEEE Conf. Comput. Commun. (INFOCOM), 2007, pp. 2000–2008. [6] J. Pernas, C. Yuen, B. Gaston, and J. Pujol, “Non-homogeneous tworack model for distributed storage systems,” in Proc. IEEE Int. Symp. Inform. Theory (ISIT), 2013, pp. 1237–1241. [7] V. T. Van, C. Yuen, and J. L. (Tiffany), “Non-homogeneous distributed storage systems,” in Allerton Conference, 2012, pp. 1133–1140. [8] W. Song, S. H. Dau, C. Yuen, and J. L. (Tiffany), “Optimal locally repairable linear codes,” IEEE Journal on Seclected Areas in Communications (JSAC), (accepted) 2013. [9] S. Pawar, S. E. Rouayheb, and K. Ramchandran, “Securing dynamic distributed storage systems against eavesdropping and adversarial attacks,” IEEE Trans. Inform. Theory, vol. 57, no. 10, pp. 6734–6753, 2011. [10] K. V. Rashmi, N. B. Shah, and P. V. Kumar, “Regenerating codes for errors and erasures in distributed storage,” in Proc. IEEE Int. Symp. Inform. Theory (ISIT), 2012, pp. 1202–1206. [11] T. K. Dikaliotis, A. G. Dimakis, and T. Ho, “Security in distributed storage systems by communicating a logarithmic number of bits,” in Proc. IEEE Int. Symp. Inform. Theory (ISIT), 2010, pp. 1948–1952. [12] N. B. Shah, K. V. Rashmi, and P. V. Kumar, “Information-theoretically secure regenerating codes for distributed storage,” in Proc. Glob. Telecommunications Conf. (GLOBECOM), 2011, pp. 1–5. [13] A. S. Rawat, O. O. Koyluoglu, N. Silberstein, and S. Vishwanath, “Secure locally repairable codes for distributed storage systems,” in Proc. IEEE Int. Symp. Inform. Theory (ISIT), 2013, pp. 2224–2228. [14] S. Goparaju, S. E. Rouayheb, R. Calderbank, and H. V. Poor, “Data secrecy in distributed storage systems under exact repair,” in Proc. Int. Symp. Network Coding (NetCod), 2013, pp. 1–6. [15] 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 productmatrix construction,” IEEE Trans. Inform. Theory, vol. 57, no. 8, pp. 5227–5239, 2011. [16] S. E. Rouayheb and K. Ramchandran, “Fractional repetition codes for repair in distributed storage systems,” in Proc. Annu. Allerton Conf. Commun., Control, and Comput. (Allerton), 2010, pp. 1510–1517. [17] K. Bhattad and K. R. Narayanan, “Weakly secure network coding,” in Proc. 1st Workshop on Network Coding, Theory, and Application (NetCod), 2005. [18] D. Silva and F. R. Kschischang, “Universal weakly secure network coding,” in Proc. IEEE Inform. Theory Workshop (ITW), 2009, pp. 281– 285. [19] S. H. Dau, V. Skachek, and Y. M. Chee, “On the security of index coding with side information,” IEEE Trans. Inform. Theory, vol. 58, no. 6, pp. 3975–3988, 2012. [20] K. V. Rashmi, N. B. Shah, P. V. Kumar, and K. Ramchandran, “Explicit construction of optimal exact regenerating codes for distributed storage,” in Proc. 47th Annu. Allerton Conf. Commun., Control, and Comput. (Allerton), 2009, pp. 1243–1249. [21] F. J. MacWilliams and N. J. A. Sloane, The Theory of Error-Correcting Codes. Amsterdam: North-Holland, 1977. [22] Extended version, http://arxiv.org/abs/1309.2712.
security level
5 2 O 1
block
securit y
5
2 3 4 adversarial strength
Fig. 6: Degradation of the security level for D(7, 5, 6) with a Cauchy-based product-matrix code as the adversarial strength increases. b security level
9 5 2 O
n = 7, k = 5, d = 6, Ms = 9 perfect threshold λ = 2
block
1
2 3 4 adversarial strength
5
Fig. 7: Degradation of the security level for D(7, 5, 6) with a perfectly secure Cauchy-based product-matrix code as the adversarial strength increases. we can establish that if Cauchy matrices are used in the construction of perfectly secure product-matrix codes [12], the codes remain (k − )-block secure even when the adversarial strength surpasses the specified threshold for perfect security. For example, for a DSS D(7, 5, 6) as in Fig. 6, suppose that the specified security threshold is λ = 2, then the degradation of the security is depicted in Fig. 7. The file size now is decreased to Ms = 9. B. Vandermonde-Based Product-Matrix Codes Are Not Block Secure The Vandermonde-based product-matrix codes are not 1block (weakly) secure against an adversary of strength k − 1. Indeed, consider the example from the original paper on product-matrix codes in [15, Fig. 1, Section IV]. In that example, k = 3. By observing two nodes, Node 1 and Node 6, the adversary obtains two linear combinations f7 + f8 + f9 and f7 + 6f8 + f9 . From these two, the adversary can deduce 5
