Theorem~\ref{thm_key_access} shows that if the goal is to achieve the privacy required by \eqref{Eq_Dec},
then, in all but trivial cases, we need to distribute keys among the users. In this section, we consider a model 
without the extra resource of keys. In the absence of keys, we aim to achieve \emph{weak privacy}. 
An $(n,R)$ scheme consists of an encoding function $\phi$ and $N$ decoding functions $\{\psi_i\}_{i \in [N]}$. The encoding function 
\begin{align}
	\label{Eq_encod}
	\phi: \prod_{i \in [N]} \mathbb{F}^n  \longrightarrow [|\mathbb{F}|^{n\Rm}],
\end{align}
outputs the random variable $\mv = \phi\left(\xv_{[N]}\right)$. For $i \in [N]$, the decoding function
\begin{align}
	\label{Eq_decod}
	\psi_i: [|\mathbb{F}|^{n\Rm}] \times \prod_{j \in \s_i} \mathbb{F}^n  \longrightarrow  \mathbb{F}^n
\end{align}
maps the message received from the transmission and the side information data to an estimate of the file needed at user $i$
\begin{align}
	\widehat{\xv_i} := \psi_i\left(\mv, \xv_{\s_i} \right).
\end{align} 
 Rate $R$ is said to be \emph{achievable} under weak privacy, if for each $\epsilon>0$ there exists an $(n,R)$ scheme for some large enough $n$ such that the following conditions are satisfied: 
\begin{align}
\label{Eq_Dec_1b}
\pr{\psi_i\left(\mv, \xv_{\s_i}\right) = \xv_i, \forall i \in [N]} \ge 1 - \epsilon,
\end{align}
and
\begin{align}
\label{Eq_Priv_1b}
I \left( \mv;\xv_{j} \middle | \xv_{\s_i} \right) \leq n \epsilon \mbox{ for all } i \in [N], j \in [N] \setminus \a_i.
\end{align}

Observe that under weak privacy defined by~\eqref{Eq_Priv_1b}, if user $i$ does not have $X_j$ and $X_k$ as side information, where $i\neq j\neq k$, then user $i$ must not learn anything about $X_j$ or $X_k$ individually, but the user may gain some information about the pair $(X_j,X_k)$.
\subsection{Feasibility of Weak Privacy}
It is not possible to achieve weak privacy for all index coding problems. For example, Fig.~\ref{Fig_feasible} shows a feasible index coding problem
and an infeasible index coding problem under weak privacy. For the 4 user network in the left, transmitting $X_1 \oplus X_2$  and $X_3 \oplus X_4$ is a scheme under weak privacy.
For the 3 user network in the right, decodability at user 3 implies that for all $\epsilon >0$ and for large enough $n$, we have $H\left(\xv_{3}|\mv,\xv_{1},\xv_{2}\right) \leq n \epsilon$. But from the privacy condition at user 2, we have $ I\left(\mv,\xv_{1},\xv_{2};\xv_{3}\right) \leq n \epsilon$  which further implies that $H \left(\xv_{3}|\mv,\xv_{1}, \xv_{2} \right) \geq n (1-\epsilon)$. So, there is no scheme for this network.
\begin{figure}[h]
\centering
\includegraphics[scale=0.44]{Feasble_Infeasble_1b_secrecy.pdf}
\caption{Figure $(a)$ shows a feasible index coding instance under weak privacy along with a code that achieves weak privacy. Figure $(b)$ shows an index coding instance where the weak privacy condition at user 2 cannot be met for any code that allows all users to decode their requested file.
}
\label{Fig_feasible}
\end{figure}
Next we study the feasibility of index coding under weak privacy. We first give some necessary conditions that the network
should satisfy in order to be feasible. We start with a simple subset condition that any pair of nodes should satisfy
in order to be feasible. 


\begin{lemma}[Subset Condition]
\label{Lem_Subset}
An index coding problem under weak privacy is not feasible  if the following holds:\\
There exist users $i,j \in[N], i\neq j$ such that  $i \notin \s_j$ and $\s_i \subseteq \a_j$.
\end{lemma}
The proof of Lemma~\ref{Lem_Subset} follows from the fact that if $\s_i \subseteq \a_j$,
then user $j$ can obtain $X_i$ using the broadcast message and the side information since user $i$ obtains $X_i$ and user knows/recovers everything that user $i$ knows. Thus, weak privacy is violated if $i \notin \s_j$. The proof is given in Appendix~\ref{Sec_proof_subset}.
\begin{figure}[h]
	\centering
	\includegraphics[scale=0.5]{Subset.pdf}
	\caption{A private index coding instance that is infeasible although  it satisfies the condition in Lemma~\ref{Lem_Subset}.}
	\label{Fig_subset}
\end{figure}
Even if there are no two users $i,j \in[N]$ for which the condition in Lemma~\ref{Lem_Subset} is satisfied, weak privacy may not be feasible. We show this using the example depicted in Fig.~\ref{Fig_subset}. In this example, there are  $6$ users and the side information for users 1,3 and 6 are shown. Further, let $\s_i = [N]\setminus \{i\}$ for $i=2,4,5$. It is easy to verify that for any two users $i,j \in[6]$, the condition in Lemma~\ref{Lem_Subset} does not hold.
However,  in Appendix~\ref{Sec_proof_example}, we show the following.
\begin{claim}
	\label{Clm_subset}
	There is no scheme under weak privacy for the private coding instance in Fig.~\ref{Fig_subset}.
\end{claim}
Next we give an improved necessary condition for feasibility.
\begin{theorem}
	\label{prop_neces}
	If there exists a user $i \in [N]$ such that the following condition holds, then index coding under weak privacy is not feasible:\\
For any $S \subseteq \a_i$ such that $i \in S$, there exists a user $j\in [N], i \neq j$ and a $k \in S$ such that $k \notin \a_j$ and $S\setminus \{k\} \subseteq \a_j$.
\end{theorem}
Theorem~\ref{prop_neces} subsumes Lemma~\ref{Lem_Subset} as explained next. Suppose there exist $i,j \in [N]$ for which the condition in  Lemma~\ref{Lem_Subset} holds. Then for any $S \subseteq \a_i$ such that $i \in S$, it holds that for user $j$ and $k =i$, $k \notin \a_j$ and $S\setminus k \subseteq \a_j$.
The proof of Theorem~\ref{prop_neces} uses the following idea. If the condition in Theorem~\ref{prop_neces} is satisfied, then there exists a $j\in[N]$ such that $ i \notin \a_j$ which follows by taking $S=\{i\}$. Then we cannot transmit $X_i$ without any coding since it violates weak privacy at user $j$. If $X_i$ is conveyed to user $i$ by encoding $X_i$ using some side information of user $i$, then by the given condition, we can show that it violates the weak privacy at some user. The formal proof is given in Appendix~\ref{Sec_proof_prop}. 


\begin{figure}[h]
	\centering
	\includegraphics[scale=0.4]{Side-info.pdf}
	\caption{For the graph, $\{\{1,2,4\},\{3,5\}\}$ is a secure clique cover, i.e., $\{1,2,4\}$ and $\{3,5\}$ are cliques which together contains all the vertices such that the vertices $3$ and $5$ have only one outgoing edge to $\{1,2,4\}$, and the vertices $1,2$ and $4$ have two outgoing edges to $\{3,5\}$.}
	\label{Fig_sec_cliq}
\end{figure}

Next we give a sufficient condition to achieve weak privacy. 
Towards that, we first give the definition of a secure clique cover. A \emph{clique} is a subset of vertices where every two vertices within which are adjacent, and 
a {\em clique cover} is a set of cliques which cover all the vertices, i.e., each vertex is in at least one of the cliques.
\begin{definition}[Secure clique cover]
	\label{Def_sec_cliq}
A clique cover $\cC_{G}$ of $G$ is said to be {\em secure} if it satisfies the condition that any $v \in V(G)$ is in exactly one of the cliques in $\cC_G$ and
 for any $c \in \cC_{G}$ with $|c| =k$, there does not exist a  $v \in V(G)\setminus c$ such that $v$ has exactly $k-1$ outgoing edges to the nodes in $c$.
\end{definition}
 Observe that $\{\{1,2,4\},\{3,5\}\}$ is a clique cover for the graph shown in Fig.~\ref{Fig_sec_cliq}. It is also a secure clique cover since nodes $3$ and $5$ do not have two edges to the clique $\{1,2,4\}$, and  the nodes $1,2$ and $4$ have two edges to the clique $\{3,5\}$. Transmission of $X_1\oplus X_2 \oplus X_4$ and $ X_3\oplus X_5$ gives a scheme under weak privacy for this example. We have the following theorem.
 \begin{theorem}
  \label{Thm_Sec_Cliq}
  For the index coding problem represented by $G$,  weak privacy is feasible if $G$ has a secure clique cover.
 \end{theorem}   
 \begin{figure}[h]
	\centering
	\includegraphics[scale=0.4]{Linear.pdf}
	\caption{A private index coding instance that is feasible using  a linear scheme but it has no secure clique cover.}
	\label{Fig_linear}
\end{figure}
 The achievability scheme to show Theorem~\ref{Thm_Sec_Cliq}  is linear and the proof is given in Appendix~\ref{Proof_prop_cliq_covr}. In the next subsection, we study linear coding schemes to achieve weak privacy. A characterization of all linear schemes which achieve weak privacy is given in Theorem~\ref{Thm_1b_linear}.  We show using an example (Fig.~\ref{Fig_linear}) that having a secure clique cover  is not a necessary condition to obtain weak privacy. For this example,  we give a linear scheme which satisfies the conditions in Theorem~\ref{Thm_1b_linear}. But it can be verified that the example shown in Fig.~\ref{Fig_linear} has no secure clique cover. 
 Details are given in Appendix~\ref{Sec_linear_schm}.
\subsection{Perfect Linear Index Coding under Weak Privacy}
We consider linear coding schemes under weak privacy which satisfies \eqref{Eq_Dec_1b} and \eqref{Eq_Priv_1b} with $\epsilon =0$. Then, linear encoding for weak privacy is similar to \eqref{Eq_lin_encd} with only the first term involving $\bG_i$s.
In Theorem~\ref{Thm_1b_linear}, we characterize the linear schemes that satisfy the perfect decoding and weak privacy conditions. We use the same notations that we used to describe linear coding in Section~\ref{sec_linear}.
The proof of Theorem~\ref{Thm_1b_linear} is along similar lines as that of Theorem~\ref{Thm_linear}, hence it is omitted.
\begin{theorem}
\label{Thm_1b_linear}
The matrices $(\bG_i)_{i \in [N]}$ is a valid encoding scheme under weak privacy if and only if they satisfy the following conditions for each $i \in [N]$,
\begin{enumerate}
\item $g_i^{k} \notin \langle \{\bG_j\}_{j \notin \a_i} \rangle, \mbox{ for }1 \le k \le n,$
\item For $j \notin \a_i, \; \langle \bG_j \rangle \subseteq \langle \{\bG_k\}_{k \notin \a_i} \rangle$.
\end{enumerate}
\end{theorem}
{"config": "arxiv", "file": "2006.00257/1b-privacy.tex"}