Coding Theorems for Shannon's Cipher System with Correlated Source Outputs,and Common Information

Hirosuke Yamamoto

IEEE Trans. on Information Theory, Vol. 40, No.1, pp.85-95, JANUARY 1994

  • Source coding problems are treated for Shannon's cipher system with correlated source outputs $(X,Y)$. Several cases are considered based on whether both $X$ and $Y$, only $X$, or only $Y$ must be transmitted to the receiver, whether both $X$ and $Y$, only $X$, or only $Y$ must be kept secret, or whether the security level is measured by where $W$ is a cryptogram. The admissible region of cryptogram rate and key rate for a given security level is derived for each case. Furthermore, two new kinds of common information of $X$ and $Y$, say $C_1(X;Y)$ and $C_2(X;Y)$, are considered. $C_1(X;Y)$ is defined as the rate of the attainable minimum core of $(X^K,Y^K)$ by removing each private information from $(X^K,Y^K)$ as much as possible, while $C_2(X;Y)$ is defined as the rate of the attainable maximum core $V_C$ such that if we lose $V_C$, then each uncertainty of $X^K$ and $Y^K$ becomes $H(V_C)$. It is proved that justifies our intuitive feeling that the mutual information represents a common information of $X$ and $Y$.
  • Index Terms: Shannon's cipher system, common information, coding theorem, correlated source, cryptology
  • DOI: 10.1109/18.272457