Secure Source Coding With a Helper
We consider a secure lossless source coding problem with a rate-limited helper. In particular, Alice observes an independent and identically distributed (i.i.d.) source <formula formulatype="inline"> <tex Notation="TeX">$X^{n}$</tex></formula> and wishes to transmit this source losslessly to Bob over a rate-limited link of capacity not exceeding <formula formulatype="inline"><tex Notation="TeX">$R_{x}$</tex> </formula>. A helper, say Helen, observes an i.i.d. correlated source <formula formulatype="inline"><tex Notation="TeX">$Y^{n}$</tex></formula> and can transmit information to Bob over another link of capacity not exceeding <formula formulatype="inline"><tex Notation="TeX">$R_{y}$</tex></formula>. A passive eavesdropper (say Eve) can observe the coded output of Alice, i.e., the link from Alice to Bob is public. The uncertainty about the source <formula formulatype="inline"><tex Notation="TeX">$X^{n}$</tex> </formula> at Eve (denoted by <formula formulatype="inline"><tex Notation="TeX">$\Delta$</tex></formula>) is measured by the conditional entropy <formula formulatype="inline"><tex Notation="TeX">${{H(X^{n}\vert J_{x})}\over{n}}$</tex> </formula>, where <formula formulatype="inline"> <tex Notation="TeX">$J_{x}$</tex></formula> is the coded output of Alice and <formula formulatype="inline"> <tex Notation="TeX">$n$</tex></formula> is the block length. We completely characterize the rate-equivocation region for this secure source coding model, where we show that Slepian–Wolf binning of <formula formulatype="inline"> <tex Notation="TeX">$X^{n}$</tex></formula> with respect to the coded side information received at Bob is optimal. We next consider a modification of this model in which Alice also has access to the coded output of Helen. We call this model as the two-sided helper model. For the two-sided helper model, we characterize the rate-equivocation region. While the availability of side information at Alice does not reduce the rate of transmission from Alice, it significantly enhances the resulting equivocation at Eve. In particular, the resulting equivocation for the two-sided helper case is shown to be <formula formulatype="inline"><tex Notation="TeX">$\min (H(X),R_{y})$</tex></formula>, i.e., one bit from the two-sided helper provides one bit of uncertainty at Eve. From this result, we infer that Slepian–Wolf binning of <formula formulatype="inline"><tex Notation="TeX">$X$</tex></formula> is suboptimal and one can further decrease the information leakage to the eavesdropper by utilizing the side information at Alice. We, finally, generalize both of these results to the case in which there is additional uncoded side information <formula formulatype="inline"><tex Notation="TeX">$W^{n}$</tex> </formula> available at Bob and characterize the rate-equivocation regions under the assumption that <formula formulatype="inline"><tex Notation="TeX">$Y^{n}\rightarrow X^{n}\rightarrow W^{n}$</tex></formula> forms a Markov chain.