text:
\section{Introduction}
Secret sharing \cite{S79,McESa81} consists of a dealer who wants to share a secret with $n$ parties such that any subset of $z<n$ parties eavesdropping on their shares obtain no information about the secret. Besides its application to privately storing information in a distributed storage system, e.g., \cite{PRR11}, secret sharing is the main tool used in several applications of distributed systems such as private coded computing, e.g., \cite{AF10,BPR17}, private information retrieval \cite{chor1998private} and secure multi-party computations \cite{SMPCbook}. The main challenge arising in distributed systems is tolerating the presence of slow or unresponsive nodes, referred to as stragglers in the distributed computing community \cite{DB13}. Classical secret sharing \cite{S79,McESa81} mitigates the stragglers by allowing a legitimate user to decode the stored information from any subset of nodes of a predetermined size $k$, $z<k\leq n$.

However, in many applications the number of stragglers is not know a priori. Therefore, communication efficient secret sharing is a better fit for this problem. Communication efficient secret sharing (CE-SS) introduced in \cite{WW08} allows a user to decode the secret from any $d$, $k\leq d \leq n$ parties while communicating the minimum amount of information needed to decode the secret. The amount of information communicated to the user using CE-SS is always less than or equal to the amount of information communicated when using classical secret sharing. As a direct application, CE-SS reduces the aggregate delays experienced by the dealer in private coded computing \cite{BPR17}.

We are interested in communication efficient secret sharing schemes that tolerate the presence of malicious parties trying to actively corrupt the data stored in the distributed system. One direct solution is to use CE-SS Reed-Solomon type codes such as the codes introduced in \cite{BRIT18,HLKBtrans}. However, such error-correction codes assume that the malicious parties are omniscient and know the secret stored in the system. This assumption does not hold in this setting where the goal is to maintain the privacy of the dealer's data. This type of adversary is known as limited-knowledge adversary in the literature \cite{PRR11,JLKHKME08}.

\noindent{\em Related works:} Communication efficient secret sharing problem is introduced in \cite{WW08}. The minimum communication cost as function of the number of stragglers is derived in \cite{WW08,HLKBtrans} and codes achieving the bound are given in \cite{WW08,ZYSMH12,BRIT18,HLKBtrans}. On the other hand, protecting distributed systems from limited-knowledge malicious adversary is studied in different settings. In \cite{JLKHKME08,yao2014network} the authors consider a network coding setting in which the adversary can corrupt the data sent through some of the network's nodes and derive the capacity of such system. Reliable distributed storage system under repair dynamics is studied in \cite{PRR11,bitar2015securing}. The authors of \cite{PRR11} derive the capacity of reliable and secure distributed storage systems under the repair dynamics. Capacity-achieving codes are provided in \cite{PRR11,bitar2015securing}. The introduced codes are based on codes for non-reliable storage systems coupled with the pairwise hashing scheme introduced in \cite{yao2014network}. In both settings, it is shown that leveraging the limitation of the adversary's knowledge leads to increasing the capacity of the system \cite{PRR11,JLKHKME08,bitar2015securing,schaefer2017information}.

\noindent{\em Contributions:} We study the problem of reliable communication efficient secret sharing. We derive the capacity of such systems, {i.e., } the maximum size of the secret that can be reliably and privately stored in a distributed system in the presence of an unknown number of stragglers and a limited-knowledge adversary eavesdropping on the data and actively trying to corrupt the stored data. We characterize the minimum amount of information that the user has to download to decode the secret as a function of the number of stragglers, number of eavesdropped nodes, and number of corrupted nodes. We provide codes that achieve capacity and the minimum communication cost for any number of stragglers. Our codes are based on the use of Staircase codes and a pairwise hashing scheme that allows the user to detect the malicious parties. We compare the derived capacity to the error-correction capacity of the system with privacy constraints, {i.e., } assuming the adversary corrupting the contents of the shares is omniscient. As a result, we show that leveraging the limitation of the adversary's knowledge increases the capacity of the system. We illustrate the ideas in the following Example.

\begin{example}
We construct a reliable communication efficient secret sharing with $n=4$ parties. Assume that at most $1$ party can be a straggler, {i.e., } $k=3$ and that the adversary can spy and corrupt the content of $1$ party, {i.e., } $z=1$. Let $\mathbf{s}}%{\bm{y}=(\mathbf{s}}%{\bm{y}_1,\mathbf{s}}%{\bm{y}_2) \in  {\mathbb F}_q^2$, $q\geq 4,$ be the secret to be stored. The dealer generates two random numbers $\mathbf{r}_1$ and $\mathbf{r}_2$ drawn independently and uniformly at random from ${\mathbb F}_q$ and independently from $\mathbf{s}}%{\bm{y}$. The shares given to the parties are computed using Staircase codes \cite{BRIT18} and are shown in table~\ref{tab:cess}.

For each party $i$ we denote by $\mathbf{w}_{i1}$ and $\mathbf{w}_{i2}$ the first and second part of the share given to that party. We view $\mathbf{w}_{i1}$ and $\mathbf{w}_{i2}$ as vectors in some finite field  ${\mathbb F}_{q_1}^v$ and denote by $\langle\mathbf{w}_{i1},\mathbf{w}_{j1}\rangle$ the dot product of two vectors $\mathbf{w}_{i1}$ and $\mathbf{w}_{j1}$. The dealer computes the following pairwise hashes $\mathbf{h}_{i1} = (\langle\mathbf{w}_{i1},\mathbf{w}_{j1}\rangle)$ for all $i \neq j \in \{1,\dots,4\}$ and $\mathbf{h}_{i2} = (\langle\mathbf{w}_{i2},\mathbf{w}_{j2}\rangle)$ for all $i\neq j\in \{1,\dots,4\}$ and sends $\mathbf{h}_{i1}$ and $\mathbf{h}_{i2}$ to party $i$.

\begin{table}[t!]
\centering
\begin{tabular}[h!]{c|c|c|c}
Party 1& Party 2 & Party 3 & Party 4\\ \hline
\color{blue} $\mathbf{s}}%{\bm{y}_1+\mathbf{s}}%{\bm{y}_2+ \mathbf{r}_1$ & \color{blue} $\mathbf{s}}%{\bm{y}_1+2\mathbf{s}}%{\bm{y}_2+4\mathbf{r}_1$& \color{blue} $\mathbf{s}}%{\bm{y}_1+3\mathbf{s}}%{\bm{y}_2+ 4\mathbf{r}_1$& \color{blue} $\mathbf{s}}%{\bm{y}_1+4\mathbf{s}}%{\bm{y}_2+\mathbf{r}_1$ \\
$\mathbf{r}_1+\mathbf{r}_2$ & $\mathbf{r}_1+2\mathbf{r}_2$ & $ \mathbf{r}_1+3\mathbf{r}_2$ & $ \mathbf{r}_1+4\mathbf{r}_2$ \\
\end{tabular}
\caption{The Staircase secret sharing code for $n=4$, $k=3$, $z=1$ and achieves minimum communication cost for $d'=2$ and $d'=3$ over ${\mathbb F}_5^2$.}
\label{tab:cess}
\end{table}

Without loss of generality assume that party~$1$ is controlled by the adversary. A user contacting $d=4$ parties downloads the first half of each share and all the hashes $\mathbf{h}_{i1}$. Assuming that the size of the hash is negligible compared to the size of the shares, the communication cost is equal to $4$ units of information. Note that the adversary only observes the share of party~$1$ and therefore the other shares are uniformly distributed over ${\mathbb F}_{q_1}^{v}$ from his perspective. The user computes $\hat{\mathbf{h}}_{i1}$ for $i=1,2,3,4$ and compares them to the downloaded hash $\mathbf{h}_{i1}$. The only corrupted packet here is $\hat{\mathbf{w}}_{11}$ and can be written as $\hat{\mathbf{w}}_{11}={\mathbf{w}_{11}}+\mathbf{e}$ for a given error vector $\mathbf{e}$. Since $\mathbf{w}_{i1}$ is independent from the adversary's observation, therefore
\begin{align*}
\Pr(\hat{\mathbf{h}}_{11}  = \mathbf{h}_{11}) &= \Pr(\mathbf{e} \bot \mathbf{w}_{21}, \mathbf{e} \bot \mathbf{w}_{31}, \mathbf{e} \bot \mathbf{w}_{41})\\
& = \Pr(\mathbf{e} \bot \mathbf{w}_{21}) \Pr( \mathbf{e} \bot \mathbf{w}_{31}|\mathbf{e} \bot \mathbf{w}_{21}) \Pr( \mathbf{e} \bot \mathbf{w}_{41}|\mathbf{e} \bot \mathbf{w}_{21},\mathbf{e} \bot \mathbf{w}_{31})\\
& \leq \Pr(\mathbf{e} \bot \mathbf{w}_{21})\\
& = \dfrac{1}{q^{v}}.
\end{align*}

With high probability, the user can construct the following hash comparison table where $\times$ denotes that $\hat{\mathbf{h}}_{i1}\neq \mathbf{h}_{i1}$ and $\checkmark$ denotes equality. The user looks at the row with the most number of $\times$ and declares the party corresponding to this row as corrupted. Note that if the first row had just one $\times$, say $\hat{\mathbf{h}_{11}}\neq \mathbf{h}_{21}$, the user cannot know whether party $1$ or party $2$ is corrupted. This happens with probability at most $q^{-v}$.

\begin{table}[h!]
\centering
\begin{tabular}{c|c|c|c|c}
~ & $\hat{\mathbf{h}}_{11}$ & $\hat{\mathbf{h}}_{21}$ & $\hat{\mathbf{h}}_{31}$ & $\hat{\mathbf{h}}_{41}$\\ \cline{1-5}
${\mathbf{h}_{11}}$ & $\checkmark$ & $\times$ & $\times$ & $\times$ \\ \hline
${\mathbf{h}_{21}}$ & $\times$ & $\checkmark$ & $\checkmark$ & $\checkmark$\\ \hline
${\mathbf{h}_{31}}$ & $\times$ & $\checkmark$ & $\checkmark$ & $\checkmark$\\ \hline
${\mathbf{h}_{41}}$ & $\times$ & $\checkmark$ & $\checkmark$ & $\checkmark$\\
\end{tabular}
\end{table}

The user deletes the data downloaded from party~$1$ and decodes the secret using the other downloaded shares. Similarly, a user contacting any $d=k=3$ parties downloads all their shares and does the same as above. The communication cost is $6$ units of information and the probability of error is upper bounded by $q^{-v}$.

In this example, the size of the secret is equal to $2$ symbols. A user contacting $d=4$ parties reads and downloads $4$ units of information and a user contacting $d=3$ parties reads and downloads $6$ units of information. The user can detect the corrupted node and decode the secret with high probability. We show in the sequel that this code is optimal, i.e., the secret size achieves capacity and the minimum download costs for $d=4$ and $d=3$ are $4$ and $6$ units of information, respectively.

Note that the error correction capacity of the system, {i.e., } if the adversary were omniscient, reduces to $0$. From the singleton bound we know that the amount of information that can be reliably stored in the system is equal to one share. However, this is exactly the amount of randomness needed to maintain privacy of the data, and therefore the secret can be of size $0$.
\end{example}

\section{Problem Formulation}
We consider the problem of communication efficient secret sharing in the presence of a malicious adversary. In classical secret sharing setting, the dealer wants to share a secret $\mathbf{s}}%{\bm{y}$ with $n$ parties such that a user can decode the secret from any subset of $k\leq n$ parties by downloading all their shares. In addition, any subset of $z_r<k$ parties should not obtain any information about the secret. We assume that the share given to each party consists of $\alpha$ symbols each being an element of a finite field ${\mathbb F}_q$, where $q\geq n$ is a power of a prime. For the scheme to be communication efficient, we require that a user contacting $d$, $k\leq d\leq n$ parties can decode the secret by downloading less then $k$ shares. The minimum communication cost as function of $d$ is given by \cite{WW08,HLKBtrans} ${\fontfamily{qcr}\selectfont\text{CC}}(d) = d\dfrac{(k-z_r)\alpha}{d-z_r}$. This implies that the user can tolerate the presence of $n-d$ stragglers for $k\leq d \leq n$.

The new constraint that we impose here is that up to $z_w$ parties can be malicious and can send corrupted data to a user reconstructing the secret. The adversary James has different control level on the parties. It can eavesdrop on $z_{ro}$ parties, blindly corrupt (jam) the content of $z_{wo}$ parties, and eavesdrop and corrupt the content of $z_{rw}$ parties. Let $\mathbf{z} \triangleq (z_{ro}, z_{wo},z_{rw})$. Note that by definition $z_r=z_{ro}+z_{rw}$ and $z_w = z_{wo} + z_{rw}$. We study distributed storage systems that satisfy the following properties.

\paragraph{Perfect privacy}
Let $\mathbf{s}$ be the secret and let $S$ be the random variable denoting the secret. Let $\mathbf{w}_i$ be the share given to party $i$ and let $W_i$ denote the random variable representing $\mathbf{w}_i$. For any set $\mathcal{B} \subset \{1,\dots,n\}$, let $W_\mathcal{B}$ denote the shares given to the parties indexed by $\mathcal{B}$, {i.e., } $W_\mathcal{B} =\{W_i; i\in \mathcal{B}\}$. The privacy constraint is expressed as
\begin{equation}\label{eq:privacy}
H(S|W_\mathcal{Z}) = H(S), \quad \forall \mathcal{Z} \subset [n], |\mathcal{Z}|=z_r.
\end{equation}
Here $H$ is the entropy function and all logarithms are base $q$.
\paragraph{Resiliency}
A user contacting $k$ parties and downloading all their shares can decode the secret. The resiliency requirement can be expressed as
\begin{equation}\label{eq:resiliency}
H(S|W_\mathcal{A}) = 0, \quad \forall \mathcal{A} \subseteq [n], |\mathcal{A}|=k.
\end{equation}

Let $\hat{\mathbf{s}}$ be the secret reconstructed by the user. We relax the condition of zero-error reconstruction and allow a small probability of error, {i.e., } for all $\varepsilon>0$, $\Pr_e \triangleq \Pr \left( \hat{\mathbf{s}} \neq \mathbf{s}}%{\bm{y} \right) < \varepsilon$.

\paragraph{Communication efficiency}
A user contacting any $d$ parties, $k\leq d \leq n$, decodes the secret by reading and downloading the minimum amount of information.

Note that the read cost is upper bounded by the communication cost since the parties must at least read the amount of information communicated to the user.

In the sequel, we denote by $(n,k,\mathbf{z})$ a reliable communication efficient secret sharing (R-CE-SS) with $n$ parties, a threshold on the stragglers equal to $n-k$ and an adversary controlling $\mathbf{z}}%{\bm{y}$ parties as defined above. Our goal is to derive the capacity of an $(n,k,\mathbf{z})$ R-CE-SS. In other words, we want to find the maximum size of the secret $\mathbf{s}}%{\bm{y}$ that can be stored in the distributed system using an $(n,k,\mathbf{z})$ R-CE-SS and provide codes that achieve capacity and minimum download cost for all number of stragglers. We consider two types of adversaries: limited knowledge adversaries and omniscient adversaries. The former adversary only observes the information shared with $z_r$ parties and corrupt the content of $z_w$ shares. Whereas, the latter has full knowledge of all the shares information and can corrupt the content of $z_w$ shares. We consider omniscient adversary to model the worst case error correction capacity.

\section{Main Results}
\noindent{\em Limited knowledge adversary:} We characterize the capacity $C^\text{LK}(n,k,\mathbf{z}}%{\bm{y})$ of an $(n,k,\mathbf{z}}%{\bm{y})$ R-CE-SS scheme and derive the minimum communication and read costs, ${\fontfamily{qcr}\selectfont\text{CC}}(d)$ and ${\fontfamily{qcr}\selectfont\text{RC}}(d)$ incurred by a user contacting $d$ parties to decode the secret.

\begin{theorem}\label{thm:main}
The capacity of an $(n,k,\mathbf{z}}%{\bm{y})$ R-CE-SS, where $\mathbf{z}}%{\bm{y}= (z_{ro}, z_{wo},z_{rw})$,  in the presence of a limited knowledge adversary eavesdropping on $z_{ro}$ shares, blindly corrupting the content of $z_{wo}$ shares and eavesdropping and corrupting the content of $z_{rw}$ shares is given by
\begin{equation}\label{eq:capacity}
C^\text{LK}(n,k,\mathbf{z}}%{\bm{y}) = \begin{cases}
\hfill (k-z_r-z_w)\alpha & \hfill \text{if    }  k> 2z_{rw}+2z_{wo} + z_{ro},\\
\hfill 0 & \hfill \text{otherwise}.
\end{cases}
\end{equation}

The communication and read costs ${\fontfamily{qcr}\selectfont\text{CC}}(d)$ and ${\fontfamily{qcr}\selectfont\text{RC}}(d)$ incurred by a user contacting $d$ parties to decode the secret are
\begin{equation}\label{eq:cc}
{\fontfamily{qcr}\selectfont\text{RC}}(d) = {\fontfamily{qcr}\selectfont\text{CC}}(d) = d\dfrac{(k-2z_{rw}-z_{wo}-z_{ro})\alpha}{d-2z_{rw}-z_{wo}-z_{ro}}.
\end{equation}
\end{theorem}

We construct R-CE-SS codes that achieve $C^\text{LK}(n,k,\mathbf{z}}%{\bm{y})$ and the minimum costs simultaneously for all values of $d$, $k\leq q\leq n$. Our codes are based on the use of Staircase codes \cite{BRIT18} and pairwise hash \cite{yao2014network,PRR11}.

\vspace{0.2cm}

\noindent{\em Omniscient adversary:} We derive the capacity $C^\text{O}(n,k,\mathbf{z}}%{\bm{y})$ of an $(n,k,\mathbf{z}}%{\bm{y})$ R-CE-SS scheme to show that  $C^\text{LK}(n,k,\mathbf{z}}%{\bm{y}) > C^\text{O}(n,k,\mathbf{z}}%{\bm{y})$. The capacity in this setting follows from Singleton-type bounds with privacy constrains. We also derive the minimum communication and read costs, ${\fontfamily{qcr}\selectfont\text{CC}}(d)$ and ${\fontfamily{qcr}\selectfont\text{RC}}(d)$ incurred by a user contacting $d$ parties to decode the secret.

\begin{theorem}\label{thm:main}
The capacity of an $(n,k,\mathbf{z}}%{\bm{y})$ R-CE-SS, where $\mathbf{z}}%{\bm{y}= (z_{ro}, z_{wo},z_{rw})$, in the presence of an adversary eavesdropping on $z_{ro}+z_{rw}$ shares and an omniscient adversary corrupting the content of $z_{wo}+z_{rw}$ shares is given by
\begin{equation}\label{eq:capacity}
C^\text{O}(n,k,\mathbf{z}}%{\bm{y}) = \begin{cases}
\hfill (k-z_r-2z_w)\alpha & \hfill \text{if    }  k> 3z_{rw}+2z_{wo} + z_{ro},\\
\hfill 0 & \hfill \text{otherwise}.
\end{cases}
\end{equation}

The communication and read costs ${\fontfamily{qcr}\selectfont\text{CC}}(d)$ and ${\fontfamily{qcr}\selectfont\text{RC}}(d)$ incurred by a user contacting $d$ parties to decode the secret are
\begin{equation}\label{eq:cc}
{\fontfamily{qcr}\selectfont\text{RC}}(d) = {\fontfamily{qcr}\selectfont\text{CC}}(d) = d\dfrac{(k-3z_{rw}-2z_{wo}-z_{ro})\alpha}{d-3z_{rw}-2z_{wo}-z_{ro}}.
\end{equation}
\end{theorem}

Staircase codes \cite{BRIT18} and the codes presented in~\cite{HLKBtrans} are R-CE-SS codes that achieve $C^\text{O}(n,k,\mathbf{z}}%{\bm{y})$ and the minimum costs simultaneously for all values of $d$, $k\leq q\leq n$.

\begin{figure}[b!]
\centering
\resizebox{!}{6cm}{
\begin{tikzpicture}
    \tikzstyle{stealth} = [draw=none,text=black]
    \tikzstyle{source}  = [draw=gray,fill=black!5,circle, minimum width=1.5cm]
    \tikzstyle{storage} = [draw=blue!50,fill=blue!5,thin, circle, minimum width=1.5 cm,font=\small]
    \tikzstyle{user} = [draw=green!50!black, thin, minimum width =1.5cm, minimum height = 1cm, rounded corners = 3mm, fill=green!5]
    \tikzstyle{snode} = [draw=blue!50, thin, minimum width =1.5cm, minimum height= 0.8cm, fill=blue!5,rounded corners=3mm]
    \tikzstyle{rnode} = [draw=red!50, dashed,thin, minimum width =1.5cm, minimum height= 0.8cm, fill=red!5,rounded corners=3mm]

\node[source] at (0,0) (d) {$D$};

\node[storage, below = 2cm of d, xshift = -3cm] (p1i) {$P_1^\text{in}$};
\node[storage, right = 0.6cm of p1i] (p2i) {$P_2^\text{in}$};
\node[storage, right = 0.6 cm of p2i] (p3i) {$P_3^\text{in}$};
\node[storage, right = 0.6 cm of p3i] (p4i) {$P_4^\text{in}$};

\node[storage, below = 1cm of p1i] (p1o) {$P_1^\text{out}$};
\node[storage, right = 0.6cm of p1o] (p2o) {$P_2^\text{out}$};
\node[storage, right = 0.6 cm of p2o] (p3o) {$P_3^\text{out}$};
\node[storage, right = 0.6 cm of p3o] (p4o) {$P_n^\text{out}$};

\node[user, below = 2cm of p1o] (u1) {$U_1$};
\node[user, right = 3cm of u1] (u2) {$U_2$};

\path[->]
(d) edge node[above, midway, sloped] {$\infty$} (p1i)
edge node[above, midway, sloped] {$\infty$} (p2i)
edge node[above, midway, sloped] {$\infty$} (p3i)
edge node[above, midway, sloped] {$\infty$} (p4i);

\path[->]
(p1i) edge node[left, midway] (a1) {$\alpha$} (p1o)
(p2i) edge node[left, midway] (a2) {$\alpha$} (p2o)
(p3i) edge node[left, midway] {$\alpha$} (p3o)
(p4i) edge node[left, midway] {$\alpha$} (p4o);

\path[->]
(p1o) edge node[above, midway, sloped] {$\infty$} (u1)
(p2o) edge node[above, midway, sloped] {$\infty$} (u1)

(p2o) edge node[above, midway, sloped] {$\infty$} (u2)
(p3o) edge node[above, midway, sloped] (i1) {$\infty$} (u2)
(p4o) edge node[above, midway] (i2) {$\infty$} (u2)
;

  \draw[->,thin] (u1) [yshift = 1cm, xshift = -0.75cm] arc (135:0:1cm) node[below right=0.1cm and -0.2cm] {\small $d_1=2$};
  \draw[->,thin] (u2) [yshift = 0.6cm, xshift = 1cm] arc (45:135:1.7cm) node[below=0.1cm] {\small $d_2=3$};

\node[below left = -0.1cm and 0.4 cm of a1] (a1){};
\node[below right = -0.1cm and 0.4 of a2] (a2) {};

    \draw[red, dashed] plot [smooth, tension=0.5] coordinates {(a1) (a2)};
        \node[stealth,red, left = 0.1 of a1] {\small $C(\mathcal{V}_1,\mathcal{V}_2)$};

\end{tikzpicture}
}
\caption{A depiction of the graph representation of the reliable communication efficient secret sharing problem with $n=4$ workers and two values of $d$, $d_1=2$ and $d_2 = 3$. The dealer is the source represented by a vertex $D$. Each party $i$ is represented by two vertices $P_i^\text{in}$ and $P_i^\text{out}$. A user $j$ is a terminal $U_j$ connected to $d$ parties for different values of $d$. All edges are directed and the capacity is mentioned on the edge. A cut between the dealer and user $1$ is shown where $\mathcal{V}_2 =\{P_1^\text{out}, P_2^\text{out}, U_1\}$ and $\mathcal{V}_1 = \mathcal{V} \setminus \mathcal{V}_2$. The value of this cut is $2\alpha$.}
\label{fig:network}
\end{figure}

\section{Flow Graph Representation}
We look at the problem at hand as a multicast problem on parallel edges. We model the network using a flow graph $\mathcal{G}(\mathcal{V},\mathcal{E})$ with $\mathcal{V}$ being the set of vertices and $\mathcal{E}$ the set of edges. This representation is introduced in \cite{DGWWR07}. The dealer ${D}$ is the source of the network and each user $j$ is a terminal ${U_j}$. We view each party as being two vertices in the graph, a vertex $\mathcal{P}^\text{in}$ and $\mathcal{P}^\text{out}$. The vertex $D$ is connected to $P_i^\text{in}$ with an edge $D \to P_i^\text{in}$ of infinite capacity for all $i = 1,\dots,n$. For all $i = 1,\dots,n$, the vertex  $P_i^\text{out}$ is connected to $P_i\text{in}$ with an edge $P_i^\text{in} \to P_i^\text{out}$ of capacity equal to $\alpha$, the storage capacity of each party. A vertex $U_j$ is connected to any set of $d$ vertices $P_i^\text{out}$, indexed by $\mathcal{I}_j\subseteq [n]$, with edges of infinite capacity $P_i^{out} \to U_j$ for all $i\in \mathcal{I}_j$. We depict this network in Figure~\ref{fig:network}.

A cut $C(\mathcal{V}_1,\mathcal{V}_2)$ between $D$ and a given user $U_j$ in the network is defined as a partition of the set of vertices $\mathcal{V}$ into two sets $\mathcal{V}_1$ and $\mathcal{V}_2$ such that:
\begin{enumerate}
\item By definition of a partition, $\mathcal{V}= \mathcal{V}_1 \cup \mathcal{V}_2$ and $\mathcal{V}_1 \cap \mathcal{V}_2 = \emptyset$.
\item The source $D$ is in $\mathcal{V}_1$ and $U_j$ is in $\mathcal{V}_2$.
\item There is no edge in the network that connects any vertex in $\mathcal{V}_1$ to the user $U_j$.
\end{enumerate}

The value of a cut $C(\mathcal{V}_1,\mathcal{V}_2)$ is defined as the sum of the capacities of the edges going from a vertex in $\mathcal{V}_1$ to a vertex in $\mathcal{V}_2$.  The idea is to use the min-cut max-flow to bound the capacity of the network. For example, in the network shown in Figure~\ref{fig:network} the dealer can send at most $2\alpha$ units of information to user $1$. This amount is equal to the value of the cut $C(\mathcal{V}_1,\mathcal{V}_2)$.

\section{Converses}
Let $\alpha$ be the amount of information given to each party. We show that $H(S)\leq (k- 2z_{rw} - z_{ro} - z_{wo})\alpha$ using standard information theoretic inequalities. Then, we use the flow graph information representation of the reliable communication efficient secret sharing system to show the following.
\begin{equation}\label{eq:capacity}
C(n,k,\mathbf{z}}%{\bm{y}) \leq \begin{cases}
\hfill k-2z_{rw}-z_{wo} - z_{ro} & \hfill \text{if    } k> 2z_{rw}+2z_{wo} + z_{ro},\\
\hfill 0 & \hfill \text{otherwise}.
\end{cases}
\end{equation}

\subsection{Bound on the Entropy of the Secret}\label{sec:bound}
Let $W_i^j$ $, i<j$, denote the set of random variables $W_i, \dots, W_j$ and recall that $z_w = z_{wo}+ r_{rw}$ and $z_r = z_{ro}+ r_{rw}$. For any collection of $k$ shares we can write the following using~\eqref{eq:resiliency}
\begin{align}
H(S) &=  I(S; W_1^k) \label{eq:mutual}\\
 & = I(S; W_1^{z_{w}}) + I(S; W_{z_{w}+1}^{k}| W_1^{z_{w}}) \label{eq:chain}\\
 & = I(S; W_{z_{w}+1}^{k}| W_1^{z_{w}}) \label{eq:pri}\\
 & = H(W_{z_{w}+1}^{k}| W_1^{z_{w}}) - H(W_{z_{w}+1}^{k} | S,W_1^{z_{w}}) \nonumber\\
 & = H(W_{z_{w}+z_{r}+1}^{k}| W_1^{z_{w}}) \nonumber \\
 & ~~ +  H(W_{z_{w}+1}^{z_{w}+z_{r}}| W_1^{z_{w}}, W_{z_{w}+z_{r}+1}^{k}) - H(W_{z_{w}+1}^{k} | S,W_1^{z_{w}}) \label{eq:chain2} \\
 & \leq H(W_{z_{w}+z_{r}+1}^{k}) \label{eq:dpi} \\
 & \leq (k-2z_{rw}-z_{wo} - z_{ro})H(W_i) \label{eq:ind}\\
 & = (k-2z_{rw}-z_{wo} - z_{ro})\alpha. \label{eq:alpha}
\end{align}

Equation~\eqref{eq:chain} follows from the chain rule of mutual information. Equation~\eqref{eq:pri} follows from the privacy constraint given in~\eqref{eq:privacy}. In~\eqref{eq:pri} we removed the first $z_{ro}$ shares which does not incur loss of generality. Equation~\eqref{eq:chain2} follows from the chain rule of entropy. Equation~\eqref{eq:dpi} follows from the data processing inequality as we shall show next. Equation~\eqref{eq:ind} follows from the chain rule of entropy and~\eqref{eq:alpha} follows because $H(W_i) = \alpha$.

To show that~\eqref{eq:dpi} holds we use the non-negativity of the entropy and write the following.
\begin{align}
H(W_{z_{w}+1}^{k} | S,W_1^{z_{w}}) & = H(W_{z_{w}+1}^{z_{w}+z_{r}}| S,W_1^{z_{w}}) +   H(W_{z_{w}+z_{r}}^{k}| S,W_1^{z_{w}}, W_{z_{w}+1}^{z_{w}+z_{r}}) \nonumber \\
& \geq H(W_{z_{w}+1}^{z_{w}+ z_{r}}| S,W_1^{z_{w}}).\label{eq:greater}
\end{align}

Note that~\eqref{eq:greater} holds with equality because all the shares are a deterministic function of the secret and the randomness that can be extracted from any $z_r$ shares. Let $$Q\triangleq H(W_{z_{w}+1}^{z_{w}+z_{r}}| W_1^{z_{w}},W_{z_{w}+z_{r}+1}^{k}) - H(W_{z_{w}+1}^{k} | S,W_1^{z_{w}}),$$ we use~\eqref{eq:greater} to bound $Q$ as follows.
\begin{align}
Q &\leq H(W_{z_{w}+1}^{z_{w}+z_{r}}| W_1^{z_{w}},W_{z_{w}+ z_{r}+1}^{k}) - H(W_{z_{w}+ 1}^{z_{w}+z_{r}}| S,W_1^{z_{w}}) \nonumber \\
& =I(W_{z_{w}+1}^{z_{w}+z_{r}}; S,W_1^{z_{w}}) - I(W_{z_{w}+1}^{z_{w}+z_{r}}; W_1^{z_{w}},W_{z_{w}+z_{r}+1}^{k})\label{eq:defi}\\
& \geq 0.\label{eq:dpi1}
\end{align}

Equation~\eqref{eq:defi} follows from the definition of mutual information $I(A;B) = H(A) - H(A|B)$ and~\eqref{eq:dpi1} holds because $S\to W_{z_{w}+z_{r}+1}^{k}$ forms a Markov chain and we can use the data processing inequality.

\begin{figure}[t!]
\centering
\resizebox{!}{6cm}{
\begin{tikzpicture}
    \tikzstyle{stealth} = [draw=none,text=black]
    \tikzstyle{source}  = [draw=gray,fill=black!5,circle, minimum width=1.5cm]
    \tikzstyle{storage} = [draw=blue!50,fill=blue!5,thin, circle, minimum width=2 cm,font=\small]
    \tikzstyle{user} = [draw=green!50!black, thin, minimum width =1.5cm, minimum height = 1cm, rounded corners = 3mm, fill=green!5]
    \tikzstyle{rwstorage} = [draw=red!50,fill=red!5,thin, circle, dashed, minimum width=2 cm,font=\small]

\node[source] at (0,0) (d) {$D$};

\node[rwstorage, below = 1cm of d, xshift = -9cm] (p1i) {$P_1^\text{in}$};
\node[right = 0.5 cm of p1i] (dots) {$\cdots$};
\node[rwstorage, right = 0.5cm of dots] (p2i) {$P_{z_{ro}}^\text{in}$};
\node[rwstorage, right = 0.6 cm of p2i] (p3i) {$P_{z_{ro}+1}^\text{in}$};
\node[right = 0.5 cm of p3i] (dots) {$\cdots$};
\node[storage, right = 0.5 cm of dots] (p4i) {$P_{z_{w}+z_{ro}}^\text{in}$};
\node[storage, right = 0.6 cm of p4i] (p5i) {$P_{z_{w}+z_{ro}+1}^\text{in}$};
\node[right = 0.5 cm of p5i] (dots) {$\cdots$};
\node[storage, right = 0.6 cm of dots] (pni) {$P_n^\text{in}$};

\node[storage, below = 1cm of p1i] (p1o) {$P_1^\text{out}$};
\node[right = 0.5 cm of p1o] (dots) {$\cdots$};
\node[storage, right = 0.5cm of dots] (p2o) {$P_{z_{ro}}^\text{out}$};
\node[rwstorage, right = 0.6 cm of p2o] (p3o) {$P_{z_{ro}+1}^\text{out}$};
\node[right = 0.5 cm of p3o] (dots) {$\cdots$};
\node[rwstorage, right = 0.5 cm of dots] (p4o) {$P_{z_{w}+z_{ro}}^\text{out}$};
\node[storage, right = 0.6 cm of p4o] (p5o) {$P_{z_{w}+z_{ro}+1}^\text{out}$};
\node[right = 0.5 cm of p5o] (dots) {$\cdots$};
\node[storage, right = 0.6 cm of dots] (pno) {$P_n^\text{out}$};

\node[user, below = 8.5cm of d] (u1) {$U$};

\path[->]
(d) edge node[above, midway, sloped] {} (p1i)
edge node[above, midway, sloped] {} (p2i)
edge node[above, midway, sloped] {} (p3i)
edge node[above, midway, sloped] {} (p4i)
edge node[above, midway, sloped] {} (p5i)
edge node[above, midway, sloped] {} (pni);

\path[->]
(p1i) edge node[left, midway] (a1) {$\alpha$} (p1o)
(p2i) edge node[left, midway] {$\alpha$} (p2o)
(p3i) edge node[left, midway] {$\alpha$} (p3o)
(p4i) edge node[left, midway] {$\alpha$} (p4o)
(p5i) edge node[left, midway] (a2) {$\alpha$} (p5o)
(pni) edge node[left, midway] {$\alpha$} (pno);

\path[->]
(p1o) edge node[above, midway, sloped] {} (u1)
(p2o) edge node[above, midway, sloped] {} (u1)
(p3o) edge [dashed] node[above, midway, sloped] {} (u1)
(p4o) edge [dashed] node[above, midway, sloped] {} (u1)
(p5o) edge node[above, midway, sloped] {} (u1)
(dots) + (0,-0.5) edge node[above, midway, sloped] {} (u1)

;

  \draw[->,thin] (u1) [yshift = 0.5cm, xshift = -2.25cm] arc (135:45:3cm) node[below right=0.1cm and -0.2cm] {$k$};

\node[below left = -0.1cm and 0.4 cm of a1] (a1){};
\node[below right = -0.1cm and 1 of a2] (a2) {};

    \draw[red, dashed] plot [smooth, tension=0.5] coordinates {(a1) (a2)};
        \node[stealth,red, left = 0.1 of a1] {\small $C(\mathcal{V}_1,\mathcal{V}_2)$};

\end{tikzpicture}
}
\caption{Flow graph representation of the reliable communication efficient secret sharing problem. Edges with no capacity are infinite capacity edges. A dashed $P_i^\text{in}$ means that the adversary can read the share of party $i$.A dashed $P_i^\text{out}$ means that the adversary can change the data sent from party $i$ to the user. We split the parties into $3$ sets, a read-only set (on the left), a write set (in the middle) and a set where the adversary has no control (on the right). The value of the considered cut is $k\alpha$.}
\label{fig:network2}
\end{figure}

\subsection{Limited Knowledge Adversary}
\paragraph{Capacity} We quantify the amount of information that the dealer can send to a user contacting any $k$ parties. We do so by finding a cut in the network between the dealer and such a user. By the min-cut max-flow argument the capacity of the system is upper bounded by the value of this cut. We partition the contacted parties into three disjoint sets. Let $\mathcal{R}$, $\mathcal{W}$ and $\mathcal{H}$ be three disjoint subsets of $[n]$ such that $|\mathcal{R}|=z_{ro}$, $|\mathcal{W}|=z_{rw}+z_{wo}$ and $|\mathcal{H}|=k-z_{ro} - z_{wo} - z_{rw}$. We denote by $P_{\mathcal{R}}$, $P_{\mathcal{W}}$, $P_{\mathcal{H}}$ the set of parties indexed by $\mathcal{R}$, ${\mathcal{W}}$ and ${\mathcal{H}}$, respectively. Let $P_{\mathcal{R}}$ be the set of parties on which the adversary can eavesdrop (read only), $P_{\mathcal{W}}$ be the set of parties which shares can be corrupted by the adversary (write only and read write) and  $P_{\mathcal{H}}$ be the set of parties not controlled by the adversary. A cut between the dealer and the user is $\mathcal{V}_2 = \{U,P_{\mathcal{R}}^\text{out}, P_{\mathcal{W}}^\text{out}, P_{\mathcal{H}}^\text{out}\}$ and $\mathcal{V}_2 = \mathcal{V} \setminus \mathcal{V}_1$. The value of this cut is $k\alpha$. We divide the set of outgoing edges to the user into three sets (see Figure~\ref{fig:network2} for a pictorial representation):
\begin{enumerate}
\item $\mathcal{E}_1$: the set of outgoing edges from the parties indexed by $\mathcal{R}$, {i.e., } the set of edges $P_i^\text{in}\to P_i^\text{out}$ for all $i\in \mathcal{R}$.
\item $\mathcal{E}_2$: the set of outgoing edges from the parties indexed by $\mathcal{W}$, {i.e., } the set of edges $P_i^\text{in}\to P_i^\text{out}$ for all $i\in \mathcal{W}$.
\item $\mathcal{E}_3$: the set of outgoing edges from the parties indexed by $\mathcal{H}$, {i.e., } the set of edges $P_i^\text{in}\to P_i^\text{out}$ for all $i\in \mathcal{H}$.
\end{enumerate}

Let $X_{\mathcal{E}_i}(\mathbf{s}}%{\bm{y})$ be the symbols sent to the user on the set of edges $\mathcal{E}_i$ when a secret $\mathbf{s}$ is being transmitted from the dealer. The information sent to the user on $P_i^\text{out}\to U$ depends only on the information sent on $P_i^\text{in}\to P_i^\text{out}$. Therefore we focus on the links $P_i^\text{in}\to P_i^\text{out}$. We consider two cases depending on the value of $k$: %
\begin{enumerate*}[label={\textit{(\roman*)}}]
\item $k \leq 2z_{rw} + 2 z_{wo} + z_{ro}$; and
\item $k > 2z_{rw} + 2 z_{wo} + z_{ro}$.
\end{enumerate*}

\noindent{\em Case 1:} First consider $k = 2z_{rw} + 2 z_{wo} + z_{ro}$. The adversary James can decide on a given secret $\mathbf{s}}%{\bm{y}_{J}$ of his choice independently from the true secret being sent by the dealer and send $X_{\mathcal{E}_2}(\mathbf{s}}%{\bm{y}_J)$ on the set of links he controls. The user now observes $X_{\mathcal{E}_1}(\mathbf{s}}%{\bm{y})$, $X_{\mathcal{E}_2}(\mathbf{s}}%{\bm{y}_J)$ and $X_{\mathcal{E}_3}(\mathbf{s}}%{\bm{y})$. From the user's perspective all secrets are equally likely because the dealer is choosing a secret uniformly at random and sending it to the user. Using the upper bound on $H(S)$ we can verify that the uncertainty of the message to the user and to the adversary is the same and is equal $z_{wo}\alpha$. Therefore, since $|\mathcal{E}_2| = |\mathcal{E}_3|$ and both $X_{\mathcal{E}_2}(\mathbf{s}}%{\bm{y}_J)$ and $X_{\mathcal{E}_3}(\mathbf{s}}%{\bm{y})$ are consistent with $X_{\mathcal{E}_1}(\mathbf{s}}%{\bm{y})$ and both uniformly distributed over the same alphabet the user cannot decide wether $\mathbf{s}}%{\bm{y}$ or $\mathbf{s}}%{\bm{y}_J$ is the true message and must decode the message using only $X_{\mathcal{E}_1}(\mathbf{s}}%{\bm{y})$. We formalize this intuition as follows. We assume that the secret $\mathbf{s}}%{\bm{y}$ is uniformly distributed over ${\mathbb F}_q^{z_{wo}\alpha}$. Let $\mathbf{r}$ and $\mathbf{r}_J$ be the values of the random numbers chosen by the dealer and James respectively. We can write the following.
\begin{align}
\Pr \left( X_{\mathcal{E}_2}(\mathbf{s}}%{\bm{y}_J) = x_2, X_{\mathcal{E}_3}(\mathbf{s}}%{\bm{y}) = x_3  | X_{\mathcal{E}_1}(\mathbf{s}}%{\bm{y}) = x_1 \right) & = \Pr \left (X_{\mathcal{E}_3}(\mathbf{s}}%{\bm{y}) = x_3\right) \Pr \left (X_{\mathcal{E}_2}(\mathbf{s}}%{\bm{y}_J) = x_2| X_{\mathcal{E}_1}(\mathbf{s}}%{\bm{y}) = x_1, X_{\mathcal{E}_3}(\mathbf{s}}%{\bm{y}) = x_3\right) \nonumber \\
& = \Pr \left (X_{\mathcal{E}_3}(\mathbf{s}}%{\bm{y}) = x_3\right) \Pr \left (X_{\mathcal{E}_2}(\mathbf{s}}%{\bm{y}_J) = x_2| X_{\mathcal{E}_1}(\mathbf{s}}%{\bm{y}) = x_1\right) \label{eq:nob}\\
& = \Pr \left(S = \mathbf{s}}%{\bm{y}, R=\mathbf{r}   \right) \Pr \left(S = \mathbf{s}}%{\bm{y}_J, R=\mathbf{r}_J | X_{\mathcal{E}_1}(\mathbf{s}}%{\bm{y}) = x_1   \right) \nonumber \\
& = \Pr \left(S = \mathbf{s}}%{\bm{y} \right)  \Pr \left(R = \mathbf{r} \right) \Pr \left(S = \mathbf{s}}%{\bm{y}_J\right) \Pr \left(R = \mathbf{r}_J| X_{\mathcal{E}_1}(\mathbf{s}}%{\bm{y}) = x_1   \right) \label{eq:secret_random} \\
& = \dfrac{1}{q^{z_{wo}\alpha}}  \Pr \left(R = \mathbf{r} \right) \dfrac{1}{q^{z_{wo}\alpha}}  \Pr \left(R = \mathbf{r}_J| X_{\mathcal{E}_1}(\mathbf{s}}%{\bm{y}) = x_1   \right) \label{eq:secret_uni}\\
& =  \Pr \left(S = \mathbf{s}}%{\bm{y}_J \right)  \Pr \left(R = \mathbf{r} \right) \Pr \left(S = \mathbf{s}}%{\bm{y} \right) \Pr \left(R = \mathbf{r}_J| X_{\mathcal{E}_1}(\mathbf{s}}%{\bm{y}) = x_1   \right) \nonumber \\
& = \Pr \left (X_{\mathcal{E}_3}(\mathbf{s}}%{\bm{y}_J) = x_3\right) \Pr \left (X_{\mathcal{E}_2}(\mathbf{s}}%{\bm{y}) = x_2| X_{\mathcal{E}_1}(\mathbf{s}}%{\bm{y}) = x_1\right) \nonumber \\
& = \Pr \left( X_{\mathcal{E}_2}(\mathbf{s}}%{\bm{y}) = x_2, X_{\mathcal{E}_3}(\mathbf{s}}%{\bm{y}_J) = x_3  | X_{\mathcal{E}_1}(\mathbf{s}}%{\bm{y}) = x_1 \right). \nonumber
\end{align}

Equation~\eqref{eq:nob} holds because the adversary does not observe the information sent on $\mathcal{E}_3$. Equation~\eqref{eq:secret_random} follows because the dealer chooses the random numbers independently from the secret to ensure privacy. In addition, the information on sent on $\mathcal{E}_1$ contains no information about the secret and James chooses $\mathbf{s}}%{\bm{y}_J$ independently from the information sent on $\mathcal{E}_1$ and from the randomness. Equation~\eqref{eq:secret_uni} holds because from the user's perspective the secret is drawn uniformly at random from ${\mathbb F}_q^{z_{wo}\alpha}$.

This equality implies that the user cannot distinguish whether $\mathcal{E}_2$ or $\mathcal{E}_3$ are sending information belonging to the true secret. The user must therefore decode the secret using only $X_{\mathcal{E}_1}(\mathbf{s}}%{\bm{y})$, otherwise the user would be making an error with probability $1/2(1-1/q^{z_{wo}\alpha})$. However, due to the privacy constraint any set of less than $z_{ro}+z_{rw}$ shares contain no information about the secret. Therefore, the capacity of the system is $0$.
A similar argument follows if $k< 2z_{rw} + 2 z_{wo} + z_{ro}$. The adversary sends no information on $\mathcal{B} \subset \mathcal{E}_2$ of size $|\mathcal{E}_2|-|\mathcal{E}_3|$ links and the rest follows.

\noindent{\em Case 2:} This case is straightforward.
Assume that the dealer is storing a secret of maximal size $H(S) = (k- 2z_{rw} - z_{ro} - z_{wo})\alpha> z_{wo}\alpha$. James can choose a fake secret $\mathbf{s}}%{\bm{y}_J$ of size at most $z_{wo} = |\mathcal{E}_2|-z_{rw}$. The user observes $X_{\mathcal{E}_1}(\mathbf{s}}%{\bm{y})$, $X_{\mathcal{E}_2}(\mathbf{s}}%{\bm{y}_J)$ and $X_{\mathcal{E}_3}(\mathbf{s}}%{\bm{y})$. Due to privacy constraints, all true messages are equally likely from James' perspective. Thus, Jame's best strategy is to pick $\mathbf{s}}%{\bm{y}_J$ at random. Since James observes the information sent on the links of $\mathcal{E}_1$, the information $X_{\mathcal{E}_2}(\mathbf{s}}%{\bm{y}_J)$ will be consistent with $X_{\mathcal{E}_1}(\mathbf{s}}%{\bm{y})$. However, with high probability $X_{\mathcal{E}_2}(\mathbf{s}}%{\bm{y}_J)$ is not consistent with $X_{\mathcal{E}_3}(\mathbf{s}}%{\bm{y})$ for all $\mathbf{s}}%{\bm{y}_J\neq \mathbf{s}}%{\bm{y}$. Therefore, the best the user can do is to detect that the information sent on $X_{\mathcal{E}_2}(\mathbf{s}}%{\bm{y}_J)$ is independent from the true secret $\mathbf{s}}%{\bm{y}$ and use the remaining information to decode.

Hence, the amount of information the user can use to decode $\mathbf{s}}%{\bm{y}$ is upper bounded by the amount of information sent on $\mathcal{E}_1$ and $\mathcal{E}_3$. Due to privacy constraints, any collection of $z_{ro}+z_{rw}$ parties obtain no information about the secret. Thus, the capacity of the system is upper bounded by
\begin{equation*}
C \leq |\mathcal{E}_1|+|\mathcal{E}_3| - z_{ro} - z_{rw} = (k- 2z_{rw} - z_{ro} - z_{wo})\alpha.
\end{equation*}

Note that in this case the user knows that $X_{\mathcal{E}_2}(\mathbf{s}}%{\bm{y}_J)$ is the set of corrupted parties with high probability. An error occurs if there exists a subset $\mathcal{A}\subset \mathcal{E}_3$ of size $H(S) -z_{rw}- z_{wo}$ links such that $X_{\mathcal{E}_2}(\mathbf{s}}%{\bm{y}_J)\neq X_{\mathcal{A}}(\mathbf{s}}%{\bm{y})$ are both consistent with $X_{\mathcal{E}_3\setminus \mathcal{A}}(\mathbf{s}}%{\bm{y})$. In this case, the user cannot decide whether $X_{\mathcal{E}_2}(\mathbf{s}}%{\bm{y}_J)$ or $X_{\mathcal{A}}(\mathbf{s}}%{\bm{y})$ are information that belong to the true secret because all secrets are also equally distributed from his perspective. The best strategy of the user here is to decode only from $\mathcal{E}_1$ and $\mathcal{E}_3\setminus\mathcal{A}$. Hence, the user cannot decode the secret if $(k- 3z_{rw} -2z_{wo} - z_{ro})\alpha<H(S)$ because out of the $|\mathcal{E}_1|+|\mathcal{E}_3|-|\mathcal{A}| = k- 2z_{rw} -2z_{wo}$ links any $z_{ro}+z_{rw}$ links cannot have any information about the secret. This case happens with probability bounded by $q^{-H(S)+z_{wo}+z_{rw}}$. If the user wants to always decode the right message, then the capacity becomes the same as the capacity of error correction codes with privacy constraints, {i.e., } $H(S)\leq (k- 2(z_{rw}+z_{wo}) - (z_{ro}+r_{rw}))\alpha$.

\paragraph{Minimum Download Cost}
To obtain an upper bound on the the minimum communication cost between any $d\leq n $ parties and the user we assume that each party can communicate at most $\beta\leq \alpha$ units of information to the user. We consider the case where $k>2z_{rw} + 2 z_{wo} + z_{ro}$. The user downloads $d\beta$ units of information from the parties. In a similar argument to the one used in the converse, the user cannot use the information sent from the $z_{wo}+z_{rw}$ parties because they send information independent from the secret $\mathbf{s}}%{\bm{y}$. Again, from the privacy constraint the information stored on (therefore sent from) any collection of $z_{ro}+z_{rw}$ parties does not contain any information about the secret $\mathbf{s}}%{\bm{y}$. Thus, the user can only use the remaining $(d-2z_{rw} - z_{ro} - z_{wo})\beta$ units of information to decode the secret. The useful information must be at least equal to size of the secret therefore
\begin{align}
(d-2z_{rw} - z_{ro} - z_{wo})\beta & \leq (k-2z_{rw} - z_{ro} - z_{wo})\alpha, \nonumber\\
{\fontfamily{qcr}\selectfont\text{CC}}(d) = d\beta &\leq d \dfrac{(k-2z_{rw} - z_{ro} - z_{wo})\alpha}{d-2z_{rw} - z_{ro} - z_{wo}}\label{eq:ccproof}
\end{align}

We defer the proof using information theoretic inequalities, following the same steps of Section~\ref{sec:bound}, to the appendix.

\begin{comment}
\begin{figure}[t!]
\centering
\resizebox{!}{6cm}{
\begin{tikzpicture}
    \tikzstyle{stealth} = [draw=none,text=black]
    \tikzstyle{source}  = [draw=gray,fill=black!5,circle, minimum width=1.5cm]
    \tikzstyle{storage} = [draw=blue!50,fill=blue!5,thin, circle, minimum width=2 cm,font=\small]
    \tikzstyle{user} = [draw=green!50!black, thin, minimum width =1.5cm, minimum height = 1cm, rounded corners = 3mm, fill=green!5]
    \tikzstyle{rwstorage} = [draw=red!50,fill=red!5,thin, circle, dashed, minimum width=2 cm,font=\small]

\node[source] at (0,0) (d) {$D$};

\node[rwstorage, below = 1cm of d, xshift = -9cm] (p1i) {$P_1^\text{in}$};
\node[right = 0.5 cm of p1i] (dots) {$\cdots$};
\node[rwstorage, right = 0.5cm of dots] (p2i) {$P_{z_{ro}}^\text{in}$};
\node[rwstorage, right = 0.6 cm of p2i] (p3i) {$P_{z_{ro}+1}^\text{in}$};
\node[right = 0.5 cm of p3i] (dots) {$\cdots$};
\node[storage, right = 0.5 cm of dots] (p4i) {$P_{z_{w}+z_{ro}}^\text{in}$};
\node[storage, right = 0.6 cm of p4i] (p5i) {$P_{z_{w}+z_{ro}+1}^\text{in}$};
\node[right = 0.5 cm of p5i] (dots) {$\cdots$};
\node[storage, right = 0.6 cm of dots] (pni) {$P_n^\text{in}$};

\node[storage, below = 1cm of p1i] (p1o) {$P_1^\text{out}$};
\node[right = 0.5 cm of p1o] (dots) {$\cdots$};
\node[storage, right = 0.5cm of dots] (p2o) {$P_{z_{ro}}^\text{out}$};
\node[rwstorage, right = 0.6 cm of p2o] (p3o) {$P_{z_{ro}+1}^\text{out}$};
\node[right = 0.5 cm of p3o] (dots) {$\cdots$};
\node[rwstorage, right = 0.5 cm of dots] (p4o) {$P_{z_{w}+z_{ro}}^\text{out}$};
\node[storage, right = 0.6 cm of p4o] (p5o) {$P_{z_{w}+z_{ro}+1}^\text{out}$};
\node[right = 0.5 cm of p5o] (dots) {$\cdots$};
\node[storage, right = 0.6 cm of dots] (pno) {$P_n^\text{out}$};

\node[user, below = 8.5cm of d] (u1) {$U$};

\path[->]
(d) edge node[above, midway, sloped] {} (p1i)
edge node[above, midway, sloped] {} (p2i)
edge node[above, midway, sloped] {} (p3i)
edge node[above, midway, sloped] {} (p4i)
edge node[above, midway, sloped] {} (p5i)
edge node[above, midway, sloped] {} (pni);

\path[->]
(p1i) edge node[left, midway] {$\alpha$} (p1o)
(p2i) edge node[left, midway] {$\alpha$} (p2o)
(p3i) edge node[left, midway] {$\alpha$} (p3o)
(p4i) edge node[left, midway] {$\alpha$} (p4o)
(p5i) edge node[left, midway] {$\alpha$} (p5o)
(pni) edge node[left, midway] {$\alpha$} (pno);

\path[->]
(p1o) edge node[above, midway] (a1) {$\beta$} (u1)
(p2o) edge node[above, midway] {$\beta$} (u1)
(p3o) edge [dashed] node[above, midway] {$\beta$} (u1)
(p4o) edge [dashed] node[left, near start] {$\beta$} (u1)
(p5o) edge node[below, near start] {$\beta$} (u1)
(dots) + (0,-0.5) edge node[below, near start] (a2) {$\beta$} (u1)

;

  \draw[->,thin] (u1) [yshift = 0.5cm, xshift = -2.25cm] arc (135:45:3cm) node[below right=0.1cm and -0.2cm] {$d$};

\node[below left = -0.1cm and 0.4 cm of a1] (a1){};
\node[below right = -0.3cm and 1 of a2] (a2) {};

    \draw[red, dashed] (a1) -- +(10,0);
        \node[stealth,red, left = 0.1 of a1] {\small $C(\mathcal{V}_1,\mathcal{V}_2)$};

\end{tikzpicture}
}
\caption{Flow graph representation of the reliable communication efficient secret sharing problem. To compute the minimum communication cost we assume that each party can send at most $\beta \leq \alpha$ units of information to the user. The value of the considered cut is $d\beta$. The goal is to find a bound on $d\beta$.}
\label{fig:network2}
\end{figure}
\end{comment}

\subsection{Omniscient Adversary}
\paragraph{Capacity} We quantify the amount of information that the dealer can send to a user contacting any $k$ parties. We do so by finding a cut in the network between the dealer and such a user. By the min-cut max-flow argument the capacity of the system is upper bounded by the value of this cut. We partition the contacted parties into three disjoint sets. Let $\mathcal{W}$, $\mathcal{H}_1$ and $\mathcal{H}_2$ be three disjoint subsets of $\{1,\dots,n\}$ such that $|\mathcal{W}|=z_{rw}+z_{wo}$, $|\mathcal{H}_1|= z_{rw} + z_{wo}$ and $|\mathcal{H}_2|=k- 2(z_{rw} - z_{wo)}$. We denote by $P_{\mathcal{W}}$, $P_{\mathcal{H}_1}$, $P_{\mathcal{H}_2}$ the set of parties indexed by $\mathcal{R}$, ${\mathcal{W}}$ and ${\mathcal{H}}$, respectively. A cut between the dealer and the user is $\mathcal{V}_2 = \{U,P_{\mathcal{W}}^\text{out}, P_{\mathcal{H}_1}^\text{out}, P_{\mathcal{H}_2}^\text{out}\}$ and $\mathcal{V}_2 = \mathcal{V} \setminus \mathcal{V}_1$. The value of this cut is $k\alpha$.

Let $X_{\mathcal{W}}(\mathbf{s}}%{\bm{y}), \ X_{\mathcal{H}_1}(\mathbf{s}}%{\bm{y}), \ X_{\mathcal{H}_2}(\mathbf{s}}%{\bm{y})$ be the symbols sent to the user from the set of parties indexing $X$ when a secret $\mathbf{s}$ is being transmitted from the dealer. The adversary decides on a given secret $\mathbf{s}}%{\bm{y}_{J}$ of his choice independently from the true secret being sent by the dealer and sends $X_{\mathcal{W}}(\mathbf{s}}%{\bm{y}_J)$ on the set of links he controls. Since the adversary is omniscient, he can always choose a secret $\mathbf{s}}%{\bm{y}_J$ such that both $X_{\mathcal{W}}(\mathbf{s}}%{\bm{y}_J)$ and $X_{\mathcal{H}_1}(\mathbf{s}}%{\bm{y})$ are consistent with $X_{\mathcal{H}_2}(\mathbf{s}}%{\bm{y})$. The user cannot decide wether $\mathbf{s}}%{\bm{y}$ or $\mathbf{s}}%{\bm{y}_J$ is the true message and must decode the message using only $X_{\mathcal{H}_2}(\mathbf{s}}%{\bm{y})$. We formalize this intuition as follows. We assume that the secret $\mathbf{s}}%{\bm{y}$ is uniformly distributed over ${\mathbb F}_q^{H(S)}$. Let $\mathbf{r}$ and $\mathbf{r}_J$ be the values of the random numbers chosen by the dealer and the adversary respectively. We can write the following.
\begin{align}
\Pr \left( X_{\mathcal{W}}(\mathbf{s}}%{\bm{y}_J) = x_1, X_{\mathcal{H}_1}(\mathbf{s}}%{\bm{y}) = x_2  | X_{\mathcal{H}_2}(\mathbf{s}}%{\bm{y}) = x_3 \right) & = \Pr \left (X_{\mathcal{H}_1}(\mathbf{s}}%{\bm{y}) = x_2\right) \Pr \left (X_{\mathcal{W}}(\mathbf{s}}%{\bm{y}_J) = x_1| X_{\mathcal{H}_1}(\mathbf{s}}%{\bm{y}) = x_2, X_{\mathcal{H}_2}(\mathbf{s}}%{\bm{y}) = x_3\right) \nonumber \\
& = \Pr \left(S = \mathbf{s}}%{\bm{y}, R=\mathbf{r}   \right) \Pr \left(S = \mathbf{s}}%{\bm{y}_J, R=\mathbf{r}_J | X_{\mathcal{H}_1}(\mathbf{s}}%{\bm{y}) = x_2, X_{\mathcal{H}_2}(\mathbf{s}}%{\bm{y}) = x_3  \right) \nonumber \\
& = \Pr \left(S = \mathbf{s}}%{\bm{y} \right)  \Pr \left(R = \mathbf{r} \right) \Pr \left(S = \mathbf{s}}%{\bm{y}_J\right) \Pr \left(R = \mathbf{r}_J|X_{\mathcal{H}_1}(\mathbf{s}}%{\bm{y}) = x_2, X_{\mathcal{H}_2}(\mathbf{s}}%{\bm{y}) = x_3   \right) \nonumber \\
& = \dfrac{1}{q^{H(S)}}  \Pr \left(R = \mathbf{r} \right) \dfrac{1}{q^{H(S)}}  \Pr \left(R = \mathbf{r}_J|X_{\mathcal{H}_1}(\mathbf{s}}%{\bm{y}) = x_2, X_{\mathcal{H}_2}(\mathbf{s}}%{\bm{y}) = x_3  \right) \label{eq:osecret_uni}\\
& =  \Pr \left(S = \mathbf{s}}%{\bm{y}_J \right)  \Pr \left(R = \mathbf{r} \right) \Pr \left(S = \mathbf{s}}%{\bm{y} \right) \Pr \left(R = \mathbf{r}_J| X_{\mathcal{H}_1}(\mathbf{s}}%{\bm{y}) = x_2, X_{\mathcal{H}_2}(\mathbf{s}}%{\bm{y}) = x_3  \right) \nonumber \\
& = \Pr \left( X_{\mathcal{W}}(\mathbf{s}}%{\bm{y}) = x_1, X_{\mathcal{H}_1}(\mathbf{s}}%{\bm{y}_J) = x_2  | X_{\mathcal{H}_2}(\mathbf{s}}%{\bm{y}) = x_3 \right). \nonumber
\end{align}

Equation~\eqref{eq:osecret_uni} holds because from the user's perspective the secret is drawn uniformly at random from ${\mathbb F}_q^{H(S)}$. This equality implies that the user cannot distinguish whether $\mathcal{W}$ or $\mathcal{H}_1$ are sending information belonging to the true secret. The user must therefore decode the secret using only $X_{\mathcal{H}_2}(\mathbf{s}}%{\bm{y})$, otherwise the user would be making an error with probability $1/2$. However, due to the privacy constraint any set of less than $z_{ro}+z_{rw}$ shares contain no information about the secret. Therefore, the capacity of the system is less than or equal to $\left(|\mathcal{H}_2|- z_{ro}+z_{rw}\right)\alpha = (k- 3z_{rw} - 2z_{wo} - z_{ro})\alpha$.

\paragraph{Minimum download} We follow the same argument above. Consider a user contacting $d$ parties and consider the trivial cut $\mathcal{V}_2 = \{U\}$, $\mathcal{V}_1 = \mathcal{V}\setminus \mathcal{V}_2$. Each party sends $\beta$ units of information to the dealer, which we want to minimize. The value of the cut is $d\beta$. Following the same reasoning as above, we know that the user can use at most $(d- 3z_{rw} - 2z_{wo} - z_{ro})\beta$ units of information. In order to decode the secret the total amount of useful downloaded information must be greater than or equal to $H(S) = (k- 3z_{rw} - 2z_{wo} - z_{ro})\alpha$. Therefore, we obtain
\begin{align*}
(d- 3z_{rw} - 2z_{wo} - z_{ro})\beta & \geq (k- 3z_{rw} - 2z_{wo} - z_{ro})\alpha, \\
{\fontfamily{qcr}\selectfont\text{CC}}(d) = d\beta & \geq d\dfrac{ (k- 3z_{rw} - 2z_{wo} - z_{ro})\alpha}{d- 3z_{rw} - 2z_{wo} - z_{ro}}.
\end{align*}

\section{Achievability}

\subsection{Limited Knowledge Adversary}
\subsubsection{Capacity achieving codes}
To achieve capacity and minimum communication cost we use Staircase codes \cite{BRIT18} with a pairwise hash \cite{yao2014network,PRR11} added to the data given to the parties. Staircase codes is a family of communication efficient secret sharing that achieves capacity and minimum communication cost for all values of $k\leq d \leq n$ when $z_{w} = z_{wo}+z_{rw} = 0$. To construct an $(n,k,\mathbf{z}}%{\bm{y})$ R-CE-SS, we need an $(n,k' = k-z_w, z'=z_r)$ Staircase code that achieves the minimum communication cost for $d'\in \{k',\dots,n-z_w\}$. The idea is for the user to contact $d=d'+z_w$ parties, use the pairwise hash to detect which $z_w$ parties are sending corrupted information and decode from the remaining parties. Note that from Staircase codes we get $$H(S) = (k'-z_r)\alpha = (k-z_w-z_r)\alpha = (k-2z_{rw}- z_{wo}- z_{ro})\alpha$$ and when contacting $d'$ parties each party sends $$\dfrac{CC(d')}{d'} = \dfrac{(k'-z_r)\alpha}{d'-z_r} = \dfrac{(k-2z_{rw}- z_{wo}- z_{ro})\alpha}{d-2z_{rw}- z_{wo}- z_{ro}}$$ units of information. Therefore, the capacity, privacy constraints and minimum communication cost and read costs are achieved. We need to prove that the hash can be used to catch the corrupted parties with high probability.

The secret $\mathbf{s}}%{\bm{y}$ is a symbol drawn from a finite field ${\mathbb F}_q^\alpha$ for a power of a prime $q$ and an integer parameter $\alpha\triangleq \text{LCM}(n-z_w-z_r, \dots, k-z_w-z_r+1)$ of Staircase codes. Staircase code requires dividing each share $\mathbf{w}_i$ into $\alpha$ symbols, $\mathbf{w}_{i1},\dots, \mathbf{w}_{i\alpha}$. We group the symbols of $\mathbf{w}_i$ into $n-k+1$ vectors each of size $\gamma_\ell \triangleq \alpha_{k+\ell-1} - \alpha_{k+\ell}$ for $\ell=n-k+1,\dots,0$ (take $\alpha_{n+1} = 0$), such that a user contacting $d$ parties downloads the first group of symbols $\mathbf{w}_{i\ell}$, $\ell = n-k+1,\dots, d-k+1$, of size $\alpha_d$ from each party. We view each symbol $\mathbf{w}_{i\ell}$ as a vector over some finite field ${\mathbb F}_{q_1}^{\gamma_\ell}$. We construct the following hashes $h_{i\ell} = (\langle \mathbf{w}_{i\ell}, \mathbf{w}_{j\ell})$ for all $i \neq j \in \{1,\dots,n\}$. Each party $i$ stores $\alpha$ symbols $\mathbf{w}_{i\ell}$ and $\alpha$ hash symbols $\mathbf{h}_{i\ell}$ for $\ell=n-k+1,\dots,0$. Note that $\mathbf{w}_{i\ell} \in{\mathbb F}_{q_1^v}$, whereas $\mathbf{h}_\ell \in {\mathbb F}_{q_1}$ which can be made arbitrarily small. Therefore we assume that the size of the hash is negligible compared to the size of the secret.

\begin{table}[t!]
\renewcommand{\arraystretch}{1.2}
\centering
\begin{tabular}{l|c|c|c|c|c|c|c|c|c}
  \multicolumn{1}{c}{~}   &      \multicolumn{3}{c}{\small \em Read only}           & \multicolumn{3}{c}{\small \em Write}   & \multicolumn{3}{c}{\small \em Honest}   \\
  \multicolumn{1}{c}{~}   &      \multicolumn{3}{l}{\raisebox{0ex}{\smash{$\overbrace{\makebox[9em]{}}_{}$}}} & \multicolumn{3}{l}{\raisebox{0ex}{\smash{$\overbrace{\makebox[15em]{}}_{}$}}} & \multicolumn{3}{l}{\raisebox{0ex}{\smash{$\overbrace{\makebox[18em]{}}_{}$}}} \\
~ & $\hat{\mathbf{h}}_{1}$ & $\cdots $& $\hat{\mathbf{h}}_{z_{ro}}$ & $\hat{\mathbf{h}}_{z_{ro}+1}$ & $\cdots$ & $\hat{\mathbf{h}}_{z_{ro}+z_{rw}+z_{wo}}$&  $\hat{\mathbf{h}}_{z_{ro}+z_{rw}+z_{wo} +1}$&$\cdots$ & $\hat{\mathbf{h}}_{d}$\\ \hline
${\mathbf{h}_{1}}$ & $\checkmark$ & $\cdots$ & \checkmark &  $\checkmark$ & $\cdots$ & $\checkmark$ & $\checkmark$ &  $\cdots$ &$\checkmark$ \\ \hline
$\vdots$ & $\vdots$ &$\vdots$  & $\vdots$ &  $\vdots$ & $\vdots$ &$\vdots$  & $\vdots$ &  $\vdots$ & $\vdots$  \\  \hline
${\mathbf{h}_{z_{ro}}}$ & $\checkmark$ & $\cdots$ & \checkmark &  $\checkmark$ & $\cdots$ & $\checkmark$ & $\checkmark$ & $\cdots$ &$\checkmark$ \\ \hline

${\mathbf{h}_{z_{ro}+1}}$& $\checkmark$ & $\cdots$ & \checkmark &  $\checkmark$ & $\cdots$ & $\checkmark$ & \cellcolor{green!25}$\times$ &\cellcolor{green!25} $\cdots$ & \cellcolor{green!25} $\times$ \\ \hline
$\vdots$ & $\vdots$ &$\vdots$  & $\vdots$ &  $\vdots$ & $\vdots$ &$\vdots$  & \cellcolor{green!25}$\vdots$ &  \cellcolor{green!25}$\vdots$ &\cellcolor{green!25} $\vdots$  \\  \hline
${\mathbf{h}_{z_{ro}+z_{rw}+z_{wo}}}$& $\checkmark$ & $\cdots$ & \checkmark &  $\checkmark$ & $\cdots$ & $\checkmark$ &\cellcolor{green!25} $\times$ & \cellcolor{green!25}$\cdots$ & \cellcolor{green!25}$\times$ \\ \hline

${\mathbf{h}_{z_{ro}+z_{rw}+z_{wo} +1} }$& $\checkmark$ & $\cdots$ & \checkmark & \cellcolor{red!25} $\times$ &\cellcolor{red!25} $\cdots$ & \cellcolor{red!25}$\times$ & $\checkmark$ & $\cdots$ &$\checkmark$ \\ \hline
$\vdots$ & $\vdots$ &$\vdots$  & $\vdots$ &  \cellcolor{red!25}$\vdots$ & \cellcolor{red!25}$\vdots$ &\cellcolor{red!25} $\vdots$  & $\vdots$ &  $\vdots$ & $\vdots$  \\  \hline
${\mathbf{h}_{d} }$& $\checkmark$ & $\cdots$ & \checkmark & \cellcolor{red!25} $\times$ & \cellcolor{red!25}$\cdots$ & \cellcolor{red!25} $\times$ & $\checkmark$ & $\cdots$ &$\checkmark$ \\  \hline
\end{tabular}
\caption{The hash comparison table assuming that the first $z_{ro}+z_{wo}+z_{rw}$ parties are controlled by the adversary.}
\label{tab:hashgeneral}
\end{table}

Assume for now that James can neither observe nor corrupt the hash. We will show in the next Section how the hash can be made secure and private from James. A user contacting $d$ parties, reads and downloads the first $\alpha_d\triangleq\dfrac{(k-2z_{rw}- z_{wo}- z_{ro})\alpha}{d-2z_{rw}- z_{wo}- z_{ro}}$ symbols from each share and the corresponding hashes. Assume without loss of generality that the first $z_{wo}+z_{rw}$ parties are controlled by the adversary. The user concatenates the downloaded hashes of each share into one vector $\mathbf{h}_i$ and computes $\hat{\mathbf{h}}_i$ using the shares he downloaded to constructs the hash comparison table given in Table~\ref{tab:hashgeneral}. A $\checkmark$ means that the computed hash matches the downloaded hash and a $\times$ means the opposite.

As long as the number of columns in the green part of the table is greater than the number of columns in the red part the user can successfully detect which parties are sending corrupted data. The number of columns in the green part is $d-z_{rw}-z_{wo}- z_{ro}$ and the number of columns in the red part is $z_{rw}+ z_{wo}$. Therefore, the adversary has to introduce errors orthogonal to at least $f=d-2z_{rw}-2z_{wo}- z_{ro}>1$ columns. Thus the probability of error is bounded by
\begin{align*}
\Pr(\text{error}) &= \Pr(\text{flipping  $f$ ``$\times$'' to ``$\checkmark$''})\\
& = \Pr(\mathbf{e} \bot \mathbf{w}_{i_1}) \Pr(\mathbf{e} \bot \mathbf{w}_{i_2}| \mathbf{e} \bot \mathbf{w}_{i_1}) \cdots \Pr(\mathbf{e} \bot \mathbf{w}_{i_f}| \mathbf{e} \bot \mathbf{w}_{i_1}, \dots,  \mathbf{e} \bot \mathbf{w}_{i_{f-1}})\\
& \leq \Pr(\mathbf{e} \bot \mathbf{w}_{i_1})\\
&\stackrel{(a)}{=} \left(\dfrac{q_1^{\gamma_\ell -1}}{q_1^{\gamma_\ell}} \right)^{n-d+1}\\
& = \dfrac{1}{q_1^{n-d+1}}.
\end{align*}

The equality (a) follows because by construction each $w_i$ consists of the concatenation of $n-d+1$ independent vectors of size $\gamma_\ell$ each. Therefore the adversary wants to find $n-d+1$ error vectors, each being orthogonal to the corresponding part of $\mathbf{w}_i$. The probability of finding such a vector is the probability of finding a vector that lies in the space of dimension $q^{\gamma_\ell -1}$ orthogonal to the corresponding part of $\mathbf{w}_i$.

\subsubsection{Securely Storing the Hash}
We show how to store the has securely and privately from the adversary and analyze the overhead required to store the hash. Recall that each party stores $n-k+1$ hash vectors $\mathbf{h}_{i\ell}$, $\ell = n-k+1,\dots, 0$. We slightly modify the creation of the hash. For each value of $\ell$ we create $\mathbf{h}_{\ell} = (\langle \mathbf{w}_{i\ell}, \mathbf{w}_{j\ell}\rangle)$ for all $n\neq j \in \{1,\dots,n\}$. Note that this $\mathbf{h}_{\ell}$ is indeed the concatenation of the hashes created in the previous section. We encode each $\mathbf{h}_{\ell}$ using an $(n,k_h = z_{ro}+z_{rw}+1,z_h=z_{ro}+z_{rw})$ secret sharing code and distributed the resulting shares to the parties.

\paragraph{Privacy and security of the hash}
As a result of the use of secret sharing the values of the hash are private from an adversary observing any $z_r=z_h$ shares. We want to show that a user contacting $d$ parties can obtain the correct values of the hash vectors. The user downloads any $k_h$ shares of the hash secret sharing code. Out of these $k_h$ shares at most $z_w = z_{wo}+ z_{rw}$ values are corrupted by James. The minimum distance of the hash secret sharing is $d_{\min} = n-k_h+1 = n-z_{ro}-z_{rw}+1 > z_{rw}+z_{wo} + 2$, because $n\geq k>2z_{rw}+z_{ro}+z_{wo}$. Therefore, as a property of secret sharing, which are maximum distance separable codes, the user can detect any $d_{\min} - 1 > z_{rw}+z_{wo} + 1$ errors. To that end, the user checks the $\binom{d}{k_h}$ possible values of the hash shares and decodes from a set that has no errors. Note that since $d\geq k > 2z_{rw}+z_{ro}+z_{wo} = k_h + z_{rw}+z_{wo} - 1$ there is always a set of $k_h$ uncorrupted hash shares that the user can decode from.

\paragraph{Rate analysis}
We analyze the overhead of storing the hash on the parties. Each vector $\mathbf{h}_{\ell}$ is of length $\gamma_\ell n(n-1)/2$ and so is the length of each hash secret share. The total length of the hash secret shares stored on one parties is $\sum_{\ell} \gamma_\ell n(n-1)/2 = \alpha n(n-1)/2$ over ${\mathbb F}_{q_1}$. Therefore, the overhead of the hash vectors is equal to
\begin{align*}
\log\left(\dfrac{q_1^{\alpha n (n-1)/2}}{q_1^{v\alpha}}\right) = \dfrac{n(n-1)}{2v}.
\end{align*}

The overhead of the hash can be made arbitrarily small by increasing $v$.

\paragraph{Reducing the hash overhead}
While computing the hash values we assumed that we want to cross check the information sent from party $i$ with all the other $n-1$ parties so that the user can find a set of $k-z_w$ parties that have sent consistent information to the user. This assumption lead to the overhead of hash being $n(n-1)/2$.

First observe that we can model this problem using a graph. The parties are represented using $n$ vertices. An edge is drawn between a pair of vertices $i$ and $j$ if there exists a hash value $\mathbf{h}_{i,j}$ comparing the consistency of the information sent from parties $i$ and $j$. In our initial setting we assumed that the graph is a complete graph. When downloading information from $d$ parties, the user looks at the subgraph induced by the vertices corresponding to the contacted parties. The user compares the computed hashes to the downloaded hashes and deletes all the edges where the computed hash is different from the downloaded hash. The goal of the user is to find a connected component of size $d-z_{w}$ representing the parties that sent uncorrupted information. We showed that this is possible with high probability when the graph is a complete graph.

To reduce the overhead of the hash, notice that the graph on $n$ vertices must only be connected. Therefore, a user contacting any $d$ parties can look at the induced subgraph on the $d$ vertices corresponding to the contacted parties and repeat the same process described above. It can be shown that a graph on $n$ vertices is connected almost surely if a vertex $i$ is connected to a vertex $j\neq i$, $j\in \{1,\dots,n\},$ with probability $p=(\log(n) + \log(\log(n)))/n$. Let $\mathcal{N}(i)$ be the set of vertices connected to vertex $i$, we have $\mathbb{E}|\mathcal{N}| = \log(n) + \log(\log(n))$. Thus, in our setting, each hash vector becomes $\mathbf{h}_\ell = (\langle \mathbf{w}_i, \mathbf{w}_j \rangle)$ for all $i=1,\dots,n$, $j=\mathcal{N}(i)$. This reduces the hash overhead to $\dfrac{n(\log (n)+\log(\log(n))}{v}.$

\subsection{Omniscient Adversary}
Capacity achieving codes that achieve minimum communication and read costs for this case are based on Staircase codes \cite{BRIT18}. To construct an $(n,k,\mathbf{z}}%{\bm{y})$ R-CE-SS code, we need an $(n,k'=k-2z_w, z=z_r)$ Staircase code. that achieves minimum read and communication costs for all $d'\in \Delta$ where $\Delta = \{k-2z_w,\dots, n-2z_w\}$. The idea is for the user to contact $d=d'+2z_w$ parties and correct the worst case errors. Note that from Staircase codes we get $$H(S) = (k'-z_r)\alpha = (k-2z_w-z_r)\alpha = (k-3z_{rw}-2 z_{wo}- z_{ro})\alpha$$ and when contacting $d'$ parties each party sends $$\dfrac{CC(d')}{d'} = \dfrac{(k'-z_r)\alpha}{d'-z_r} = \dfrac{(k-3z_{rw}- 2z_{wo}- z_{ro})\alpha}{d-3z_{rw}-2 z_{wo}- z_{ro}}$$ units of information. Therefore, the capacity, privacy constraints and minimum communication cost and read costs are achieved. Since Staircase codes can be viewed as a collection of concatenated Reed-Solomon codes, the error correction capability of those codes follow immediately from the error correction capability of Reed-Solomon codes.

\section{Conclusion}
We studied communication efficient secret sharing schemes that tolerate the presence of malicious parties trying to actively corrupt the data stored in the distributed system. We assume the knowledge of the adversary is restricted to the information given to the compromised parties. We show that leveraging the limitation of the knowledge of the adversary allows an increase in the size of the shared secret. We use flow graph representation of the R-CE-SS setting to characterize the capacity, {i.e., } maximum size of the secret that can be shared, when the adversary has limited and full knowledge of the shared information. We also characterize the minimum amount of information, as a function of the number of stragglers, needed to to be read and communicated to a legitimate user to decode the secret. We construct codes that achieve capacity in both settings. In addition, the constructed codes achieve minimum read and communication costs for any number of stragglers, up to a given threshold. Our codes are based on Staircase codes previously introduced for communication efficient secret sharing and the use of a pairwise hashing scheme used in distributed data storage and network coding settings to detect the presence of a limited knowledge adversary.

\noindent{\em Open problem:} Our main motivation for studying secret sharing stems from its application to several other settings. One can prove that the capacity of distributed storage system, private information retrieval and minimum communication cost of distributed computing are the same. However, it is not clear how to extended R-CE-SS codes to work in the other settings. For instance, in private information retrieval, the hash used by the user must be a function of the stored data (to be retrieved) as well as the encoding scheme used to retrieve the data. A similar argument holds for distributed computing.

\bibliographystyle{IEEEtran}

redpajama_set_name: RedPajamaArXiv


While it is assumed that most flying saucers are of alien, or perhaps Governmental Military origin, another possible origin of UFOs is Atlantis. What we know about ancient flying vehicles comes from ancient Indian sources. There is no doubt that most of these texts are authentic; many are the well known ancient Indian Epics themselves, and there are literally hundreds of them. Most of them have not even been translated into English yet from the old Sanskrit.
The original designation of the flying machine was "Ratha" which gave way for the term "Vimana". The design of the flying machine was imitated in the construction of the palaces, built by the Rbhus for the gods who came from remote space in the sky above. The Rig Veda texts (ranging from the 1st-10th Manadal) reference the aerial flying machines as Ratha. In the Yajurveda which is considered chronologically later than the Rig Veda followed by other Brahmanas, the name "Vimanas" occurs.
Those that travel between planets.
Of special concern among these were the military planes whose functions were delineated in some very considerable detail and which read today like something clean out of science fiction. For instance, they had to be: Impregnable, unbreakable, non-combustible and indestructible capable of coming to a dead stop in the twinkling of an eye; invisible to enemies; capable of listening to the conversations and sounds in hostile planes; technically proficient to see and record things, persons, incidents and situations going on inside enemy planes; know at every stage the direction of the movement of other aircraft in the vicinity; capable of rendering the enemy crew into a state of suspended animation, intellectual torpor or complete loss of consciousness; capable of destruction; manned by pilots and co-travelers who could adapt in accordance with the climate in which they moved; temperature regulated inside; constructed of very light and heat absorbing metals; provided with mechanisms that could enlarge or reduce images and enhance or diminish sounds.
T he "Rama Empire" of Northern India and Pakistan developed at least fifteen thousand years ago on the Indian subcontinent was a nation of many large, sophisticated cities, many of which are still to be found in the deserts of Pakistan, northern, and western India. Rama existed parallel to the Atlantean civilization and was ruled by "enlightened Priest-Kings" who governed the cities. The seven greatest capital cities of Rama were known in classical Hindu texts as the Seven Rishi Cities and the people had flying machines called "Vimanas." The ancient Indian epic describes a Vimana as a double deck, circular aircraft with portholes and a dome, much as we would imagine a flying saucer. It flew with the "speed of the wind" and gave forth a "melodious sound." There were at least four different types of Vimanas; some saucer shaped and others like long cylinders (cigar shaped airships). The ancient Indian texts on Vimanas are so numerous that it would take volumes to relate what they had to say. The ancient Indians, who manufactured these ships themselves, wrote entire flight manuals on the control of the various types of Vimanas, many of which are still in existence and some have even been translated into English.
1 . Goodha: As explained in 'Vaayutatva-Prakarana', by harnessing the powers, Yaasaa, Viyaasaa, Prayaasaa in the 8th atmospheric layer covering the earth, to attract the dark content of the solar ray, and use it to hide the Vimana from the enemy.
3. Vimukha: As mentioned in "Rig-hridaya", by projecting the force of Kubera, Vimukha and Vyshawaanara poison powder through the third tube of the roudree mirror and turning the switch of the air mechanism, produce wholesale insensibility and coma.
(image source: Vymaanika Shaastra Aeronautics of Maharshi Bharadwaaja - By G. R. Josyer).
4. Roopaakarshana: By means of the photographic yantra in the Vimana to obtain a television view of things inside an enemy's plane.
7. Parashabda Graahaka: As explained in the "Sowdaaminee Kalaa: or science of electronics, by means of the sound capturing yantra in the Vimana, to hear the talks and sound in enemy planes flying in the sky.
According to Shownaka, the regions of the sky are 5, named, Rekhaapathaha, Mandala, Kakshaya, shakti and Kendra. In these 5 atmospheric regions, there are 5,19,800 air ways traversed by Vimanas of the Seven Lokas or worlds, known as Bhooloka, Bhuvarloka, Suvarloka, Maholoka, Janoloka, Tapoloka and Satyaloka. Dhundinaatha and "Valalmeeki Ganita" state that Rekha has 7,03,00,800 air routes. Mandala has 20,08,00200 air routes, Kakshya has 2,09,00,300 air routes, Shakti has 10,01,300 air routes, and Kendra has 30,08,200 air routes.
It discusses what kind of food to eat, clothing to wear, metals for vimanas, purification of metals, deals with mirrors and lenses which are required to be installed in the vimaanas, mechanical contrivances or yantras and protecting and different types of vimaanas.
(source: Vymaanika Shaastra Aeronautics of Maharshi Bharadwaaja - By G. R. Josyer International Academy of Sanskrit Research 1973). Also Refer to Vymanika Shashtra - Aeronautical Society of India.
*Stealth bomber from Shastra - A glass-like material based on technology found in an ancient Sanskrit text that could ultimately be used in a stealth bomber (the material cannot be detected by radar) has been developed by a research scholar of Benaras Hindu University. Prof M A Lakshmithathachar, Director of the Academy of Sanskrit Research in Melkote, near Mandya, told Deccan Herald that tests conducted with the material showed radars could not detect it. "The unique material cannot be traced by radar and so a plane coated with it cannot be detected using radar," he said.
"In the Vedic literature of India, there are many descriptions of flying machines that are generally called vimanas. These fall into two categories: (1) manmade craft that resemble airplanes and fly with the aid of birdlike wings, and (2) unstreamlined structures that fly in a mysterious manner and are generally not made by human beings. The machines in category (1) are described mainly in medieval, secular Sanskrit works dealing with architecture, automata, military siege engines, and other mechanical contrivances. Those in category (2) are described in ancient works such as the Rig Veda, the Mahabharata, the Ramayana, and the Puranas and have many features reminiscent of UFOs." "There are ancient Indian accounts of manmade wooden vehicles that flew with wings in the manner of modern airplanes. Although these wooden vehicles were also called vimanas, most vimanas were not at all like airplanes.
It is possible that knowledge of this previous highly advanced civilization may have been preserved by ancient secret Brotherhoods. When Alexander the Great invaded India, over two thousand years ago, his scribes chronicled an attack by 'flying fiery shields' that panicked the horses. These flying vehicles did not deploy any weapons against the invading army, which marched on to conquer the country. It has been speculated in many books that secret Brotherhoods have preserved and maintained Vimanas for many thousands of years. They are alleged to keep them hidden in caverns and underground bases.
Mahavira of Bhavabhuti (A Jain text of the eighth century culled from older texts and traditions) describes aerial chariots, known as the Pushpakas that conveyed many people to the capital of Ayodhya. "The sky was full of stupendous flying-machines, dark as night, but picked out by lights with a yellowish glare." There is a passage in the Ramayana which reads: "The Puspaka car that resembles the Sun and belongs to my brother was brought by the powerful Ravan; that aerial and excellent car going everywhere at will.... that car resembling a bright cloud in the sky."... and the King [Rama] got in, and the excellent car at the command of the Raghira, rose up into the higher atmosphere."
India, according to Dr. V. Raghavan, retired head of the Sanskrit department of India's prestigious University of Madras, was playing host to extraterrestrials in prehistory. He contends that centuries-old documents in Sanskrit (the classical language of India and Hinduism) prove that aliens from outer space visited his nation. "Fifty years of researching this ancient works convinces me that there are livings beings on other planets and that they visited earth as far back as 4,000 B.C.," The scholar says. "There's just a mass of fascinating information about flying machines, even fantastic science fiction weapons that can be found in translations of the Vedas (scriptures), Indian epics, and other ancient Sanskrit texts. "In the Mahabharata there is mention of divine lighting and ray weapons, even a kind of hypnotic weapon. And in the Ramayana, there is a description of Vimanas, or flying machines that navigated at great heights with the aid of quicksilver and a great propulsive wind." The Ramayana describes a beautiful aerial chariot which 'arrived shining…a wonderful divine car that sped through the air'. In another passage, there is mention of a chariot being seen 'sailing overhead like a moon.' The Mahabharata describes "At Rama's behest, the magnificent chariot rose up to a mountain of clouds" Another passage reads: "Bhima flew with his Vimana on an enormous ray which was as brilliant as the sun and made a noise like the thunder of a storm." In the ancient Vymanka-Shastra (science of aeronautics), there is a description of a Vimana: "An apparatus which can go by its own force, from place to place or globe to globe." Dr. Raghavan points out, "The text's revelations become even more astounding. Thirty-one parts-of which the machine consists, are described, including a photographing mirror underneath. The text also enumerates 16 kinds of metal that are needed to construct the flying vehicle, But only three of them are known to us today. The rest remain untranslatable."
Dr. A. V. Krishna Murty, professor of aeronautics at the Indian Institute of Science in Bangalore says, "the ancient Indian Vedas and other text refer to aeronautics, spaceships, flying machines, and even astronauts. A study of the Sanskrit texts has convinced me that ancient India did know the secret of building flying machines-and that those machines were patterned after spaceships coming from other planets."
In the Mahabharatra, we learn that an individual named Asura Maya had a Vimana measuring twelve cubits in circumference, with four strong wheels. The poem is a veritable gold mine of information relating to conflicts between gods who settled their differences apparently using weapons as lethal as the ones we are capable of deploying. Apart from 'blazing missiles', the poem records the use of other deadly weapons. 'Indra's Dart' operated via a circular 'reflector'. When switched on, it produced a 'shaft of light' which, when focused on any target, immediately 'consumed it with its power'. In one particular exchange, the hero, Krishna, is pursuing his enemy, Salva, in the sky, when Salva's Vimana, the Saubha is made invisible in some way. Undeterred, Krishna immediately fires off a special weapon: 'I quickly laid on an arrow, which killed by seeking out sound'. Many other terrible weapons are described in the Mahabharata, but the most fearsome of all is the one used against the Vrishis. The narrative records Gurkha flying in his swift and powerful Vimana hurled against the three cities of the Vrishis and Andhakas a single projectile charged with all the power of the Universe. An incandescent column of smoke and fire, as brilliant as ten thousands suns, rose in its entire splendor. It was the unknown weapon, the Iron Thunderbolt, a gigantic messenger of death which reduced to ashes the entire race of the Vrishnis and Andhakas. The after-affects of this Iron Thunderbolt have an ominously recognizable ring. Apparently, those killed by it were so burnt that their corpses were unidentifiable. The survivor's fared little better, as it caused their hair and nails to fall out. Perhaps the most disturbing and challenging, information about these allegedly mythical Vihmanas in the ancient records is that there are some matter-of-fact records, describing how to build one. In their way, the instructions are quite precise.
The Indian Emperor Ashoka started a "Secret Society of the Nine Unknown Men": great Indian scientists who were supposed to catalogue the many sciences. Ashoka kept their work secret because he was afraid that the advanced science catalogued by these men, culled from ancient Indian sources, would be used for the evil purpose of war. The" Nine Unknown Men" wrote a total of nine books, presumably one each. One of the books was "The Secrets of Gravitation", which dealt chiefly with "gravity control." It is presumably still around somewhere, kept in a secret library in India, Tibet or perhaps even in North America somewhere.
Years ago, the Chinese discovered some Sanskrit documents in Lhasa, Tibet and sent them to the University of Chandrigarh to be translated. According to Dr. Ruth Reyna of the University the documents contain directions for building interstellar spaceships! Their method of propulsion, she said, was "anti- gravitational" and was based upon a system analogous to that of "laghima," the unknown power of the ego existing in man's physiological makeup, "a centrifugal force strong enough to counteract all gravitational pull." According to Hindu Yogis, it is this same "laghima" which enables a person to levitate. Dr. Reyna said that on board these machines, called "Astras" by the ancient Indian text could send a detachment of men onto any planet. The manuscripts were also said to reveal the secret of "antima"; "the cap of invisibility" and "garima"; "how to become as heavy as a mountain of lead." The Ramayana contains a highly detailed story about a trip to the moon in a Vimana (Astra), and in fact describes a battle on the moon with an "Asvin" (or Atlantean") airship.
At least 20 passages in the Rigveda (1028 hymns to the gods) refer exclusively to the flying vehicle of the Asvins. This flying machine is represented as three-storied, triangular and three –wheeled. It could carry at least three passengers. According to tradition the machine was made of gold, silver and iron, and had two wings. With this flying machine the Asvins saved King Bhujyu who was in distress at sea.
The description of these ancient flying machines in old Indian texts are amazingly precise. The difficulty we are faced with today is basically that the texts mention various metals and alloys which we have no understanding of. In the Amarangasutradhara five flying machines were originally built for the gods Brahma, Vishnu, Yama, Kuvera and Indra. Later there were some additions. Four main types of flying Vimanas are described: Rukma, Sundara, Tripura and Sakuna. The Rukma were conical in shape and dyed gold, whereas the Sundata were like rockets and had a silver sheen. The Tripura were three-storied and the Sakuna looked like birds. There were 113 subdivisions of these four main types that differed only in minor details. The position and functioning of the solar energy collectors are described in the Vaimanika Shastra. It says that eight tubes had to be made of special glass absorbing the sun's ray. A whole series of details are listed, some of which we do not understand. The Amaranganasutradhara even explains the drive, the controls and the fuel for the flying machine. It says that quicksilver and 'Rasa' were used. Unfortunately we do not yet know what "Rasa' was. Ten sections deal with themes such as pilot training, flight paths, the individual parts of flying machines, as well as clothing for pilots and passengers, and the food recommended for long flights. There was much technical detail: the metals used, heat-absorbing metals and their melting point, the propulsion units and various types of flying machines. The information about metals used in construction name three sorts, somala, soundaalika and mourthwika. If they were mixed in the right proportions, the result was 16 kinds of heat-absorbing metals with names like ushnambhara, ushnapaa, raajaamlatrit, etc. which cannot be translated into English. The texts also explained how to clean metals, the acids such as lemon or apple to be used and the correct mixture, the right oils to work with and the correct temperature for them. Seven types of engine are described with the special functions for which they are suited and the altitudes at which they work best. The catalogue is not short of data about the size of the machines, which had stories, nor of their suitability for various purposes.
The Samara Sutradhara is a scientific treatise dealing with every possible angle of air travel in a Vimana. There are 230 stanzas dealing with the construction, take-off, cruising for thousand of miles, normal and forced landings and even possible collisions with birds. In 1875, the Vaimanika Sastra, (or Vymaanika-Shaastra) a fourth century B.C. text written by Bharadvajy the Wise, using even older texts as his source, was rediscovered in a temple in India. It dealt with the operation of Vimanas and included information on the steering, precautions for long flights, protection of the airships from storms and lightning and how to switch the drive to "solar energy" from a free energy source which sounds like "anti-gravity." The text has eight chapters with diagrams, describing three types of aircraft, including apparatuses that could neither catch on fire nor break. It also mentions 31 essential parts of these vehicles and 16 materials from which they are constructed, which absorb light and heat; for which reason they were considered suitable for the construction of Vimanas. (This document has been translated into English and is available by writing the publisher: "Vymaanidashaastra Aeronautics" by Maharishi Bharadwaaja, translated into English and edited, printed and published by Mr. G. R.Josyer, Mysore, India, 1979. Mr. Josyer is the director of the International Academy of Sanskrit Investigation, located in Mysore.) Bharadvajy the Wise refers to no less than seventy authorities and 10 experts of air travel in antiquity. (These sources are now lost.) Vimanas were kept in a Vimana Griha, a kind of hanger, and were sometimes said to be propelled by a yellowish-white liquid and sometimes by some sort of mercury compound, though writers seem confused in this matter. It is most likely that the later writers on Vimanas, wrote as observers and from earlier texts, and were understandably confused on the principle of their propulsion. The "yellowish- white liquid" sounds suspiciously like gasoline, and perhaps Vimanas had a number of different propulsion sources, including combustion engines and even "pulse-jet" engines.
It is interesting to note, that the Nazis developed the first practical pulse-jet engines for their V-8 rocket "buzz bombs." Hitler and the Nazi staff were exceptionally interested in ancient India and Tibet and sent expeditions to both these places yearly, starting in the 30's, in order to gather esoteric evidence that they did so, and perhaps it was from these people that the Nazis gained some of their scientific information. According to the Dronaparva, part of the Mahabharata, and the Ramayana, one Vimana described was shaped like a sphere and born along at great speed on a mighty wind generated by mercury. It moved like a UFO, going up, down, backwards and forwards as the pilot desired. In another Indian source, the Samar, Vimanas were "iron machines, well-knit and smooth, with a charge of mercury that shot out of the back in the form of a roaring flame." It is possible that mercury did have something to do with the propulsion, or more possibly, with the guidance system. Curiously, Soviet scientists have discovered what they call "age-old instruments used in navigating cosmic vehicles" in caves in Turkestan and the Gobi Desert. The" devices" are hemispherical objects of glass or porcelain, ending in a cone with a drop of mercury inside.
The Vedas, thought to be the oldest of all the Indian texts, describe Vimanas of various shapes and sizes: the "ahnihotravimana" with two engines, the"elephant-vimana" with more engines, and other types named after the kingfisher, ibis and other animals. Unfortunately, Vimanas, like most scientific discoveries, were ultimately used for war. The Atlanteans, known as "Asvins" in the Indian writings, were more advanced technologically than the Indians. Some information has come down through esoteric, "occult" sources which describe their flying machines as similar, if not identical to Vimanas. The Atlantean Vailixi were generally "cigar shaped" and had the capability of maneuvering underwater as well as in the atmosphere or even outer space. Other vehicles, like the Vimanas, were saucer shaped, and could also be submerged. In a 1966 article, Eklal Kueshana (author of "The Ultimate Frontier") wrote that the Vailixi were first developed in Atlantis 20,000 years ago, and the most common ones were "saucer shaped of generally trapezoidal cross- section with three hemispherical engine pods on the underside. They used a mechanical antigravity device driven by engines developing approximately 80,000 horsepower.
According to the Indian texts, the Atlanteans used their flying machines, "the Vailixi," to subjugate the world. The Ramayana, Mahabarata and other texts speak of the hideous war that took place, some ten or twelve thousand years ago between Atlantis and Rama using weapons of destruction that could not be imagined by readers until the second half of this century. The Mahabharata goes on to tell the awesome destructiveness of the war: "...(the weapon was) a single projectile charged with all the power of the Universe. An incandescent column of smoke and flame as bright as the thousand suns rose in its entire splendor. An iron thunderbolt, a gigantic messenger of death, reduced to ashes the entire race of the Vrishnis and the Andhakas. The corpses were so burned as to be unrecognizable. The hair and nails fell out; pottery broke without apparent cause, and the birds turned white.... after a few hours all foodstuffs were infected.... to escape from this fire, the soldiers threw themselves in streams to wash themselves and their equipment..." It would seem that the Mahabharata is describing an atomic war! References like this one are not isolated; but battles, using a fantastic array of weapons and aerial vehicles are common in all the epic Indian books.
One even describes a Vimana-Vailix battle on the Moon! The above section very accurately describes what an atomic explosion would look like and the effects of the radioactivity on the population. Jumping into water is the only respite. When the Rishi City of Mohenjodaro was excavated by archaeologists in the last century, they found skeletons just lying in the streets, some of them holding hands, as if some great doom had suddenly overtaken them. These skeletons are among the most radioactive ever found, on a par with those found at Hiroshima and Nagasaki. Ancient cities whose brick and stonewalls have literally been vitrified, that is-fused together, can be found in India, Ireland, Scotland, France, Turkey and other places. There is no logical explanation for the vitrification of stone forts and cities, except from an atomic blast. Furthermore, the streets of Mohenjo-Daro, a well planned city laying on a grid, with a plumbing system superior to those used in Pakistan and India today, were found littered with "black lumps of glass." These globs of glass were discovered to be clay pots that had melted under intense heat!
With the cataclysmic sinking of Atlantis and the wiping out of Rama with atomic weapons, the world collapsed into a "dark age" of sorts. Yet, it would seem that not all the Vimanas and Vailixi of Rama and Atlantis were lost or destroyed. Built to last for thousands of years, many of them may still be in use, as evidenced by Ashoka's "Nine Unknown Men" and the Lhasa manuscript. That secret societies or "Brotherhoods" of exceptional, "enlightened" human beings would have preserved these inventions and the knowledge of science, history, etc., does not seem surprising. Many well known historical personages including Jesus, Buddah, Lao Tzu, Confucius, Krishna, Zoroaster, Mahavira, Quetzalcoatl, Akhenaton, Moses, and more recent inventors and of course many other people who will probably remain anonymous, were probably members of such a secret organization. It has been suggested by many writers that these "Brotherhoods" keep some of their Vimanas and Vailixi in secret caverns in Tibet or some other place is Central Asia, and the Lop Nor Desert in western China is known to be the center of a great UFO mystery. Perhaps it is here that many of the airships are still kept, in underground bases much as the Americans, British and Soviets have built around the world in the past few decades.
Still, not all UFO activity can be accounted for by old Vimanas making trips to the Moon for some reason. Unknown alloys have been revealed in the ancient palm leaf manuscripts. The writer and Sanskrit scholar Subramanyam Iyer has spent many years of his life deciphering old collections of palm leaves found in the villages of his native Karnataka in southern India. One of the palm leaf manuscripts they intend to decipher is the Amsu Bodhini, which, according to an anonymous text of 1931, contains information about the planets; the different kinds of light, heat, color, and electromagnetic fields; the methods used to construct machines capable of attracting solar rays and, in turn, of analyzing and separating their energy components; the possibility of conversing with people in remote places and sending messages by cable; and the manufacture of machines to transport people to other planets!
Flying machines are commonplace in the ancient Indian texts and several popular epics describe their use in warfare. Depending on one's point of view, either it contains some of the earliest known science fiction, or it records conflict between beings with weapons as powerful and advanced as anything used today.
"The Saubha is at once Shalva's city, flagship and battle headquarters. In it, he can fly wherever he chooses. Fortunately, the Vrishni heroes are similarly well equipped and at one point have Shalva at their mercy. The hero Pradyumna is about to finish him off with a "special weapon" when the highest gods intervened. They stopped him from using it, saying "Not a man in battle is safe from this arrow. "
Eluding Arjuna's pursuit, the space city abandoned its position in outer space and took shelter on Earth. Resembling the reported behavior of modern UFO, the besieged flying city attempted to escape underwater. It also fled underground. Arjuna was able to follow the Daitya space station wherever it tried to escape on Earth. Then, as the city took off for outer space again, he blasted it – breaking it apart. When debris and bodies fell to the Earth, the Mahabharata describes that Arjuna landed to make sure there were no survivors.
D avid W. Davenport, author of "2000 AC Diztruzione Atomica, Atomic Destruction 2000. BC." claimed to have proof that Mohenjo Daro, one of the oldest cities in the history of human civilization, had been destroyed by an atomic bomb. Originally Mohenjo Daro, which is more than 5000 years old, lay on two islands in the Indus. Within a radius of 1.5 km Davenport demonstrates three different degrees of devastation which spread from the center outwards. Enormous heat unleashed total destruction at the center. Thousands of lumps, christened 'black stones' by archaeologists, turned out to be fragments of clay vessels which had melted into each other in the extreme heat. The possibility of a volcanic eruption is excluded because there is no hardened lava or volcanic ash in or near Mohenjo Daro. Davenport assumed that the brief intensive heat reached 2000 degree C. causing the ceramic vessels to melt. Iin the suburbs of Mohenjo Daro skeletons of people lying flat on the ground, often hand in hand were found, as if the living had been suddenly overcome by an unexpected catastrophe.
In these series of wars thermonuclear devices were used, and when it was over and the dust cleared, there was no winner. The Outback in Australia, the Mojave Desert, parts of the Gobi Desert and the Sahara are a reminder of the futility of this type of war.


The storm churned up the mahi! Anglers brought in near limits today on several boats as well as some yellow-fin, good numbers of black-fin, and some shark.
Anglers on the Near-Shore boats had good bluefish today, spanish macs, triggerfish, and a few amberjack.
Anglers fly-fishing on In-Shore boats were seeing some hot action on the specks again today, as well as some sound striper! There were also catches of tilefish and albi's, as well as red drum.
Anglers aboard the Miss Oregon Inlet enjoyed good fishing, with flounder, puffers, bluefish, pigs, pins, and sea bass. The Miss Oregon Inlet schedule changes on Labor Day and will be sailing at 8 a.m. Monday through Saturday through Veteran's Day. The boat is available for private charter any afternoon through Veteran's Day. Call for more information.
Let us get you booked for your day on the water 1-800-272-5199! You know you need it!