logo

SCIENCE CHINA Information Sciences, Volume 61, Issue 10: 100307(2018) https://doi.org/10.1007/s11432-018-9517-9

New results on multilevel diversity coding with secure regeneration$^\dagger$

More info
  • ReceivedMar 9, 2018
  • AcceptedJul 13, 2018
  • PublishedSep 5, 2018

Abstract

The problem of multilevel diversity coding with secure regeneration is revisited. Under the assumption that the eavesdropper can access the repair data for all compromised storage nodes, Shao et al. provided a precise characterization of the minimum-bandwidth-regeneration (MBR) point of the achievable normalized storage-capacity repair-bandwidth tradeoff region. In this paper, it is shown that the MBR point of the achievable normalized storage-capacity repair-bandwidth tradeoff region remains the same even if we assume that the eavesdropper can access the repair data for some compromised storage nodes (defined as the type II compromised nodes) but only the data contents of the remaining compromised nodes (defined as the type I compromised nodes), as long as the number of type I compromised nodes is no greater than that of type II compromised nodes.


Acknowledgment

This work was supported by National Natural Science Foundation of China (Grant No. 61631017) and National Science Foundation of USA (Grant Nos. CCF-15-24839, CCF-15-26095).


Supplement

Appendix

Proof of the exchange Lemma 2

First note that $d-\ell_1~>~d-\ell$, so we may write $d-\ell_1=s(d-\ell)+r$ for some integer $s\geq~1$ and $r\in[1:d-\ell]$. Next, let

$$ a_t:=\left\{ \begin{array}{lcl} t , & & {t \in [1:\ell_1 ], }\\ t+\ell_1, & & {t \in [\ell_1+1: \ell-\ell_1],}\\ t+\ell+1 , & & {t \in [\ell-\ell_1+1: d-\ell]}. \end{array} \right. $$

Finally, let $\tau_0:=\{a_t:~t\in~[1:~r]\}$ and

\begin{align*}\tau_q:=\{a_t: t\in [r+1+(q-1)(d-\ell):r+q(d-\ell)]\} \end{align*}

for any $q\in[1:s]$. It is straightforward to verify that:

  • $\tau_q~\cap~\tau_{q'}~=\emptyset$ for any $q\neq~q'$;

  • $\bigcup_{q=0}^{s-1}\tau_q~=[1:\ell_1]\cup~[2\ell_1+1:\ell]$;

  • $\tau_s=[\ell+2:d+1]$.

Consider a symmetrical $(n=d+1,d,N_1,\ldots,N_d,T,R)$ code that satisfies the node regeneration requirement (3). Let us show by induction that for any $p\in[1:s]$, we have

\begin{align}&pH(U^{(\ell_1,\ell)}|M^{(\ell)})+H(U^{(\ell_1,\ell_1+1)}|M^{(\ell)}) \\ & \geq pH(U^{(\ell_1,\ell+1)}|M^{(\ell)})+ H\Big(W_{[\ell_1+1:2\ell_1]},S_{\ell_1 \rightarrow [ \ell_1+1:2\ell_1]},S_{\bigcup_{q=0}^{s-p}\tau_q\rightarrow \ell+1}|M^{(\ell)}\Big). \tag{31} \end{align}

To prove the base case of $p=1$, first note that

\begin{align*}H(U^{(\ell_1,\ell)}|M^{(\ell)}) &\stackrel{\rm (a)}{=} H(U^{(\ell_1,\ell)},W_{[1:\ell_1]},\underline{S}_{\rightarrow [\ell_1+1:\ell]}|M^{(\ell)}) \\ &\,= H(W_{[1:\ell_1]},S_{\rightarrow [\ell_1+1:\ell]}|M^{(\ell)}) \\ &\stackrel{\rm (b)}{=} H(W_{[1:\ell]},S_{\rightarrow [\ell_1+1:\ell]},S_{[1:\ell]\rightarrow \ell+1}|M^{(\ell)}), \end{align*}

where (a) follows from the fact that $(W_{[\ell_1:\ell]},\underline{S}_{\rightarrow~[\ell_1+1:\ell]})$ is a function of $U^{(\ell_1,\ell)}$ by Lemma lemma1, and (b) follows from the fact that $S_{[1:\ell]\rightarrow~\ell+1}$ is a function of $W_{[1:\ell]}$. Furthermore,

\begin{align*}H(U^{(\ell_1,\ell_1+1)}|M^{(\ell)}) &\stackrel{\rm (a)}{=} H(U^{(\ell_1,\ell_1+1)},\underline{S}_{\rightarrow \ell_1+1}|M^{(\ell)}) \\ &\,= H(W_{[1:\ell_1]},S_{\rightarrow \ell_1+1}|M^{(\ell)}) \\ &\stackrel{\rm (b)}{=} H(W_{[\ell_1+1:2\ell_1]},S_{\rightarrow 2\ell_1+1}|M^{(\ell)}) \\ &\stackrel{\rm (c)}{=} H(W_{[\ell_1+1:2\ell_1]},S_{\rightarrow \ell+1}|M^{(\ell)}) \\ &\stackrel{\rm (d)}{=} H(W_{[\ell_1+1:2\ell_1]},S_{[1:\ell_1]\rightarrow \ell+1},S_{[2\ell_1+1:\ell]\rightarrow \ell+1}, S_{[\ell+2:d+1]\rightarrow \ell+1},S_{\ell+1\rightarrow [\ell_1+1:2\ell_1]}|M^{(\ell)}), \end{align*}

where (a) follows from the fact that $\underline{S}_{\rightarrow\ell_1+1}$ is a function of $U^{(\ell_1,\ell_1+1)}$ by Lemma lemma1, and (b) and (c) follow from the symmetrical code that we consider; (d) follows that $S_{\ell+1\rightarrow~[\ell_1+1:2\ell_1]}$ is a function of $S_{\rightarrow~\ell+1}$. It follows that

\begin{align*}&H(U^{(\ell_1,\ell)}|M^{(\ell)})+H(U^{\ell_1,\ell_1+1}|M^{(\ell)}) \\ &\geq H(W_{[1:\ell]},S_{\rightarrow [\ell_1+1:\ell]},S_{[1:\ell]\rightarrow \ell+1}|M^{(\ell)})+ H(W_{[\ell_1+1:2\ell_1]},S_{[1:\ell_1]\rightarrow \ell+1},S_{[2\ell_1:\ell]\rightarrow \ell+1}, S_{[\ell+2:d+1]\rightarrow \ell+1}, S_{\ell+1\rightarrow [\ell_1+1:2\ell_1]}|M^{(\ell)}) \\ &\!\stackrel{\rm (a)}{\geq}\!H(W_{[1:\ell]},S_{\rightarrow [\ell_1+1:\ell]}, S_{[1:\ell]\rightarrow \ell+1},S_{[\ell+2:d+1]\rightarrow \ell+1}|M^{(\ell)})+ H(W_{[\ell_1+1:2\ell_1]},S_{[1:\ell_1]\rightarrow \ell+1},S_{[2\ell_1:\ell]\rightarrow \ell+1}, S_{\ell+1\rightarrow [\ell_1+1:2\ell_1]}|M^{(\ell)}) \\ & = H(U^{(\ell_1,\ell)},\underline{S}_{\rightarrow \ell+1}|M^{(\ell)})+ H\Big(W_{[\ell_1+1:2\ell_1]},S_{\ell+1\rightarrow [\ell_1+1:2\ell_1]},S_{\bigcup_{q=0}^{s-1}\tau_q\rightarrow \ell+1}|M^{(\ell)}\Big) \\ & = H(U^{(\ell_1,\ell+1)}|M^{(\ell)})+ H\Big(W_{[\ell_1+1:2\ell_1]},S_{\ell+1\rightarrow [\ell_1+1:2\ell_1]},S_{\bigcup_{q=0}^{s-1}\tau_q\rightarrow \ell+1}|M^{(\ell)}\Big), \end{align*}

where (a) follows from the submodularity of the entropy function. This completes the proof of the base case of $p=1$.

Assume that (31) holds for some $p\in[1:s-1]$. We have

\begin{align}&(p+1)H(U^{(\ell_1,\ell)}|M^{(\ell)})+H(U^{(\ell_1,\ell_1+1)}|M^{(\ell)}) \\ & = H(U^{(\ell_1,\ell)}|M^{(\ell)})+(pH(U^{(\ell_1,\ell)}|M^{(\ell)}) +H(U^{(\ell_1,\ell_1+1)}|M^{(\ell)})) \\ & \geq H(U^{(\ell_1,\ell)}|M^{(\ell)})+pH(U^{(\ell_1,\ell+1)}|M^{(\ell)})+ H\Big(W_{[\ell_1+1:2\ell_1]},S_{\ell+1 \rightarrow [\ell_1+1:2\ell_1]},S_{\bigcup_{q=0}^{s-p}\tau_q\rightarrow \ell+1}|M^{(\ell)}\Big). \tag{32} \end{align}

Note that both $S_{\ell+1~\rightarrow[\ell_1+1:2\ell_1]}$ and $S_{\bigcup_{q=0}^{s-(p+1)}\tau_q\rightarrow~\ell+1}$ are functions of $W_{[1:\ell]}$, which is in turn a function of $U^{(\ell_1,\ell)}$ by Lemma lemma1. We thus have

\begin{align*}H(U^{(\ell_1,\ell)}|M^{(\ell)}) =H\Big(U^{(\ell_1,\ell)},S_{\ell+1 \rightarrow[\ell_1+1:2\ell_1]}, S_{\bigcup_{q=0}^{s-(p+1)}\tau_q\rightarrow \ell+1}|M^{(\ell)}\Big). \end{align*}

Furthermore, by the symmetrical code that we consider we have

\begin{align*}&H\Big(W_{[\ell_1+1:2\ell_1]},S_{\ell+1 \rightarrow [\ell_1+1:2\ell_1]},S_{\bigcup_{q=0}^{s-p}\tau_q\rightarrow \ell+1}|M^{(\ell)}\Big) \\ & = H\Big(W_{[\ell_1+1:2\ell_1]},S_{\ell+1 \rightarrow [\ell_1+1:2\ell_1]}, S_{\bigcup_{q=0}^{s-(p+1)}\tau_q\rightarrow \ell+1},S_{[\ell+2:d+1]\rightarrow \ell+1}|M^{(\ell)}\Big). \end{align*}

It follows that

\begin{align}&H(U^{(\ell_1,\ell)}|M^{(\ell)})+ H\Big(W_{[\ell_1+1:2\ell_1]},S_{\ell+1 \rightarrow [\ell_1+1:2\ell_1]},S_{\bigcup_{q=0}^{s-p}\tau_q\rightarrow \ell+1}|M^{(\ell)}\Big) \\ & = H\Big(U^{(\ell_1,\ell)}, S_{\ell+1 \rightarrow [\ell_1+1,2\ell_1]},S_{\bigcup_{q=0}^{s-(p+1)}\tau_q\rightarrow \ell+1}|M^{(\ell)}\Big)+ H\Big(W_{[\ell_1+1:2\ell_1]},S_{\ell+1 \rightarrow [\ell_1+1:2\ell_1]}, \\ & S_{\bigcup_{q=0}^{s-(p+1)}\tau_q\rightarrow \ell+1},S_{[\ell+2:d+1]\rightarrow \ell+1}|M^{(\ell)}\Big) \\ & \stackrel{\rm (a)}{\geq} H\Big(U^{(\ell_1,\ell)}, S_{\ell+1 \rightarrow [\ell_1+1,2\ell_1]},S_{\bigcup_{q=0}^{s-(p+1)}\tau_q\rightarrow \ell+1}, S_{[\ell+2:d+1]\rightarrow \ell+1}|M^{(\ell)}\Big) \\ & +H\Big(W_{[\ell_1+1:2\ell_1]},S_{\ell+1 \rightarrow [\ell_1+1:2\ell_1]}, S_{\bigcup_{q=0}^{s-(p+1)}\tau_q\rightarrow \ell+1}|M^{(\ell)}\Big) \\ & = H(U^{(\ell_1,\ell+1)}|M^{(\ell)})+ H\Big(W_{[\ell_1+1:2\ell_1]},S_{\ell+1 \rightarrow [\ell_1+1:2\ell_1]},S_{\bigcup_{q=0}^{s-(p+1)}\tau_q\rightarrow \ell+1}|M^{(m)}\Big), \tag{33} \end{align}

where (a) follows from the submodularity of the entropy function. Substituting (33) into (32) gives

\begin{align*}&(p+1)H(U^{(\ell_1,\ell)}|M^{(\ell)})+H(U^{(\ell_1,\ell_1+1)}|M^{(\ell)}) \\ & \geq (p+1)H(U^{(\ell_1,\ell+1)}|M^{(\ell)})+ H\Big(W_{[\ell_1+1:2\ell_1]},S_{\ell+1\rightarrow [\ell_1+1:2\ell_1]},S_{\bigcup_{q=0}^{s-(p+1)}\tau_q\rightarrow \ell+1}|M^{(\ell)}\Big), \end{align*}

which completes the induction step and hence the proof of (31).

Setting $p=s$ in (31), we have

\begin{align}&sH(U^{(\ell_1,\ell)}|M^{(\ell)})+H(U^{(\ell_1,\ell_1+1)}|M^{(\ell)}) \\ & \geq sH(U^{(\ell_1,\ell+1)}|M^{(\ell)})+ H(W_{[\ell_1+1:2\ell_1]},S_{\ell+1\rightarrow [\ell_1+1:2\ell_1]},S_{\tau_0\rightarrow \ell+1}|M^{(\ell)}) \\ & = sH(U^{(\ell_1,\ell+1)}|M^{(\ell)})+H(W_{[\ell_1+1:2\ell_1]},S_{\ell+1\rightarrow [\ell_1+1:2\ell_1]}|M^{(\ell)})+ H(S_{\tau_0\rightarrow \ell+1}|W_{[\ell_1+1:2\ell_1]},S_{\ell+1\rightarrow [\ell_1+1:2\ell_1]},M^{(\ell)}). \tag{34} \end{align}

By the symmetrical codes that we consider, we have

\begin{align}H(W_{[\ell_1+1:2\ell_1]},S_{\ell+1\rightarrow [\ell_1+1:2\ell_1]}|M^{(\ell)}) =H(W_{[1:\ell_1]},S_{\ell+1\rightarrow [1:\ell_1]}|M^{(\ell)}) =H(W_{[1:\ell_1]},S_{\ell_1+1\rightarrow [1:\ell_1]}|M^{(\ell)}) \tag{35} \end{align}

and

\begin{align*}H(S_{\tau_0\rightarrow \ell+1}|W_{[\ell_1+1:2\ell_1]},S_{\ell+1\rightarrow [\ell_1+1:2\ell_1]},M^{(\ell)}) =H(S_{\tau\rightarrow \ell+1}|W_{[\ell_1+1:2\ell_1]},S_{\ell+1\rightarrow [\ell_1+1:2\ell_1]},M^{(\ell)}) \end{align*}

for any subset $\tau~\subseteq~[\ell+2:d+1]$ such that $|\tau|=r$. By Han's subset inequality 1), we have

\begin{align}&H(S_{\tau_0\rightarrow \ell+1}|W_{[\ell_1+1:2\ell_1]},S_{\ell+1\rightarrow [\ell_1+1:2\ell_1]},M^{(\ell)}) \\ & \geq \frac{r}{d-\ell}H(S_{[\ell+2:d+1]\rightarrow \ell+1}|W_{[\ell_1+1:2\ell_1]}, S_{\ell+1\rightarrow [\ell_1+1:2\ell_1]},M^{(\ell)}) \\ & \geq \frac{r}{d-\ell}H(S_{[\ell+2:d+1]\rightarrow \ell+1}|W_{[\ell_1+1:2\ell_1]}, S_{\ell+1\rightarrow [\ell_1+1:2\ell_1]},M^{(\ell)},U^{(\ell_1,\ell)}) \\ &\! \stackrel{\rm (a)}{=} \frac{r}{d-\ell}H(S_{[\ell+2:d+1]\rightarrow \ell+1}|U^{(\ell_1,\ell)},M^{(\ell)}) \\ & = \frac{r}{d-\ell}(H(S_{[\ell+2:d+1]\rightarrow \ell+1},U^{(\ell_1,\ell)}|M^{(\ell)})- H(U^{(\ell_1,\ell)}|M^{(\ell)})) \\ & = \frac{r}{d-\ell}(H(U^{(\ell_1,\ell+1)}|M^{(\ell)})-H(U^{(\ell_1,\ell)}|M^{(\ell)})), \tag{36} \end{align}

where (a) follows from the fact that $(W_{[\ell_1+1:2\ell_1]},~S_{\ell+1\rightarrow~[\ell_1+1:2\ell_1]})$ is a function of $U^{(\ell_1,\ell)}$ by Lemma lemma1. Substituting (35) and (36) into (34) gives

\begin{align*}\left(s+\frac{r}{d-\ell}\right)H(U^{(\ell_1,\ell)}|M^{(\ell)})+H(U^{(\ell_1,\ell_1+1)}|M^{(\ell)}) \geq \left(s+\frac{r}{d-\ell}\right)H(U^{(\ell_1,\ell+1)}|M^{(\ell)})+H(U^{(\ell_1,\ell_1)}|M^{(\ell)}), \end{align*}

which is equivalent to (11) by noting that

\begin{align*}s+\frac{r}{d-\ell}=\frac{s(d-\ell)+r}{d-\ell}=\frac{d-\ell_1}{d-\ell}. \end{align*}

This completes the proof of the exchange lemma.

Han T S. Nonnegative entropy measures of multivariate symmetric correlations. Inf Control, 1978, 36: 133–156


References

[1] Shao S, Liu T, Tian C, et al. Multilevel diversity coding with secure regeneration: separate coding achieves the MBR point. 2017,. arXiv Google Scholar

[2] Tian C, Liu T. Multilevel diversity coding with regeneration. IEEE Trans Inf Theory, 2016, 62: 4833-4847 CrossRef Google Scholar

[3] Shao S, Liu T, Tian C. Multilevel diversity coding with regeneration: separate coding achieves the MBR point. In: Proceedings of Annual Conference on Information Science and Systems, Princeton, 2016. 602--607. Google Scholar

[4] Pawar S, Rouayheb S E, Ramchandran K. On secure distributed data storage under repair dynamics. In: Proceedings of IEEE International Symposium on Information Theory, Austin, 2010. 2543--2547. Google Scholar

[5] Pawar S, El Rouayheb S, Ramchandran K. Securing dynamic distributed storage systems against eavesdropping and adversarial attacks. IEEE Trans Inf Theory, 2011, 57: 6734-6753 CrossRef Google Scholar

[6] Shah N B, Rashmi K V, Kumar P V. Information-theoretically secure regenerating codes for distributed storage. In: Proceedings of IEEE Global Telecommunications Conference, Kathmandu, 2011. Google Scholar

[7] Goparaju S, Rouayheb S E, Calderbank R, et al. Data secrecy in distributed storage systems under exact repair. In: Proceedings of IEEE International Symposium on Network Coding (NetCod), Calgary, 2013. Google Scholar

[8] Rawat A S, Koyluoglu O O, Silberstein N. Optimal locally repairable and secure codes for distributed storage systems. IEEE Trans Inf Theory, 2014, 60: 212-236 CrossRef Google Scholar

[9] Tandon R, Amuru S D, Clancy T C. Toward optimal secure distributed storage systems with exact repair. IEEE Trans Inf Theory, 2016, 62: 3477-3492 CrossRef Google Scholar

[10] Ye F, Shum K W, Yeung R W. The rate region for secure distributed storage systems. IEEE Trans Inf Theory, 2017, 63: 7038-7051 CrossRef Google Scholar

[11] Shao S, Liu T, Tian C. On the tradeoff region of secure exact-repair regenerating codes. IEEE Trans Inf Theory, 2017, 63: 7253-7266 CrossRef Google Scholar

[12] Tian C. Characterizing the rate region of the (4,3,3) exact-repair regenerating codes. IEEE J Sel Areas Commun, 2014, 32: 967-975 CrossRef Google Scholar

  • Figure 1

    (Color online) The optimal tradeoff region for $(4,3,0,0)$ MDC-SR problem when $(\bar{B}_1,\bar{B}_2,\bar{B}_3)=(0,1/3,2/3)$. $(\bar{\alpha},\bar{\beta})$ are defined in 1. The outer bounds 8, 10and 6are evaluated as $\bar{\beta}\geq~8/45$, $\bar{\alpha}+3\bar{\beta}\geq~16/15$, and $\bar{\alpha}+9\bar{\beta}\geq~32/15$, respectively. When set as equalities, they intersect precisely at the MBR point $(8/15,8/45)$.

Copyright 2019 Science China Press Co., Ltd. 《中国科学》杂志社有限责任公司 版权所有

京ICP备18024590号-1