Coding theorems for Shannon's cipher system with correlated source outputs, and common information
- 1 January 1994
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 40 (1), 85-95
- https://doi.org/10.1109/18.272457
Abstract
Source coding problems are treated for Shannon's (1949) 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 (1/KH(XK|W), (1/KH(YK|W)) or 1/K H(XKYK|W) 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 C1(X;Y) and C2(X;Y), are considered. C1(X;Y) is defined as the rate of the attainable minimum core of (XK,YK) by removing each private information from (XK,YK) as much as possible, while C2(X;Y) is defined as the rate of the attainable maximum core VC such that if one loses VC , then each uncertainty of XK and YK becomes H(VC). It is proved that C1(X;Y)=I(X;Y) and C2(X;Y)=min {H(X), H(Y)}. C1(X;Y) justifies the author's intuitive feeling that the mutual information represents a common information of X and YKeywords
This publication has 9 references indexed in Scilit:
- Common randomness in information theory and cryptography. I. Secret sharingIEEE Transactions on Information Theory, 1993
- Secret key agreement by public discussion from common informationIEEE Transactions on Information Theory, 1993
- An Upper Bound on the Key Equivocation for Pure CiphersIEEE Transactions on Information Theory, 1984
- Error probabilities for simple substitution ciphersIEEE Transactions on Information Theory, 1983
- Bounds on message equivocation for simple substitution ciphersIEEE Transactions on Information Theory, 1980
- Sounds on key equivocation for simple substitution ciphersIEEE Transactions on Information Theory, 1979
- An extension of the Shannon theory approach to cryptographyIEEE Transactions on Information Theory, 1977
- The common information of two dependent random variablesIEEE Transactions on Information Theory, 1975
- Communication Theory of Secrecy Systems*Bell System Technical Journal, 1949