The lectures of this course are based on the first 11 chapters of Prof. Raymond Yeung’s textbook entitled Information Theory and Network Coding (Springer 2008). This book and its predecessor, A First Course in Information Theory (Kluwer 2002, essentially the first edition of the 2008 book), have been adopted by over 60 universities around the world as either a textbook or reference text. At the completion of this course, the student should be able to: 1) Demonstrate knowledge and understanding of the fundamentals of information theory. 2) Appreciate the notion of fundamental limits in communication systems and more generally all systems. 3) Develop deeper understanding of communication systems. 4) Apply the concepts of information theory to various disciplines in information science.
Chapter 3 - Section 3.6 B
Loading...
審閱
4.7（19 個評分）
- 5 stars16 ratings
- 4 stars2 ratings
- 1 star1 ratings
教學方
Prof. Raymond W. Yeung
Choh-Ming Li Professor of Information Engineering, and Co-Director, Institute of Network Coding
Next, we are going to study a result called Shannon's
Perfect Secrecy Theorem, which is a very important result in cryptography.
In this system, X denotes the plain text, which
is a message that we want to transmit in secrecy.
Y denotes the ciphertext, that is the encryption of the message.
The message is encrypted by means of using a key denoted by Z,
where this key is available to both the transmitter and the receiver.
Now, it is possible that the adversary can intercept Y. To achieve
perfect secrecy, we need to ensure that from Y, nothing can be known about X.
That is, X and Y are statistically independent, or the
mutual information between X and Y is equal to 0.
We also require decipherability, that is the receiver upon receiving
Y and also Z would be able to recover X.
In other words, X is a function of Y and Z, or
the conditional entropy of X given Y and Z is equal to 0.
We are going to show that these two requirements imply that
entropy of Z is greater than or equal to entropy of X.
That is the length of the key is at least the same as the length of the plain text.
In the work by Shannon in 1949, he gave a combinatorial proof of this result.
We are going to prove this result by using an information diagram.
First, perfect secrecy requires I(X;Y) equals 0.
So in the information diagram, We let I(X;Y|Z) be
a, and I(X;Y;Z) be minus a.
Decipherability
requires H(X|Y,Z) equal zero.
Since I(Y;Z) is greater than or equal to 0, we
have I(Y;Z|X) is at least equal to a.
We also have the conditional entropy of Z given X, Y is greater than or equal to 0.
We need to show that mu star tilda{Z} is greater than or equal to mu star tilda{X}.
Compare in information diagram at the bottom,
the atoms of tilda{X} and the atoms of tilda{Z}.
Now we see that the atoms in tilda{X} intersect
tilda{Z} are common to both tilda{X} and tilda{Z}.
So their measures cancel with each other, and
so these atoms do not need to be considered.
Only the atoms in tilda{X} minus tilda{Z}
and tilda{Z} minus tilda{X} need to be compared.
From the information diagram at the top, it is evident that mu star tilda{Z}
minus tilda{X} is greater than or equal to mu star tilda{X} minus tilda{Z},
because this atom has measure at least the measure of this
atom, and this atom has measure at least the measure of this atom.
Therefore, we conclude that entropy of Z is at least equal to the entropy of X,
as is to be shown.
Example 3.15 is the Imperfect
Secrecy Theorem, which is a generalization of Shannon's Perfect Secrecy Theorem.
Let X be the plain
text, Y be the cipher text, and Z be the key in a secret key cryptosystem.
Since X can be recovered from Y and Z, we
have entropy of X given Y and Z equal to 0.
We can show that this constraint implies the mutual information between X
and Y is lower bounded by entropy of X minus entropy of Z.
For the details, please study example 3.15.
The interpretation of the imperfect secrecy theorem is the following.
The mutual information between X and Y measures the leakage of information,
that is, the amount of information about X that a adversary can learn by knowing Y.
The Imperfect Secrecy Theorem says that the leakage of information
is at least equal to the deficiency of the key length,
that is entropy
of X minus entropy of Z.
When I(X;Y) is equal to 0, that is, no leakage of
information is allowed, the Imperfect Secrecy
Theorem reduces to Shannon's perfect secrecy theorem.
The next example is the Data Processing
Theorem that we have discussed in chapter two.
It says that if X Y Z T forms a Markov chain, then the mutual information
between X T is less than or equal to the mutual information between Y and Z.
This is readily seen in the information diagram for the Markov chain X, Y, Z, T,
because the mutual information between X and T corresponds to
the atom marked in red in the information diagram,
and the mutual information between Y and Z corresponds to
the four atoms marked in blue in the information diagram.
In fact, from the information diagram, it can readily be seen that I(Y;Z)
is equal to I(X;T) plus I(X;Z|T)
plus I(Y;T|X) plus I(Y;Z|X,T).
Example 3.18 is a more elaborate example. It
says that, if we have a Markov chain X Y Z T U consisting of
five random variables, then entropy of Y plus entropy
of T is equal to the mutual information between Z
and X, Y, T, U plus the mutual information between (X,Y)
and (T,U),
plus the entropy of Y given Z, plus the entropy of T given Z.
This identity is very difficult to discover without an information diagram.
And it is instrumental in proving an outer bound,
for problem in information theory called the multiple description problem.
As an exercise, verify the following
information diagram for the above equality.
Information inequalities that are implied by
the basic inequalities are called Shannon-type inequalities.
They can be proved by means of a linear program called ITIP,
which stands for Information Theoretic Inequality Prover,
developed on Matlab at CUHK back in 1996.
A version running on C called Xitip,
which is more portable, was developed
at EPFL in 2007. See Chapter 13
and 14 for discussion on this topic.
Here are some examples of ITIP.
In the first example, we want to prove that entropy of X Y Z is less
than or equal to entropy of X plus entropy of Y, plus entropy of Z,
namely, the independence bound for entropy.
Upon hitting the Return key, the program returns true,
which means that this is a Shannon-type inequality.
In the second example, we want to verify whether I(X;Z) is equal to 0
conditioning on I(X;Z|Y) equals 0 and I(X;Y) equals 0.
Upon hitting the Return key, the program returns true.
In the third example, we want to verify whether X Y Z T forms
a Markov chain, conditioning on two Markov sub-chains,
namely X Y Z and Y Z T, and this cannot be proved by ITIP.
In this case, it can be shown that given the two Markov subchains, X Y Z
and Y Z T, it is indeed the case that the long Markov chain X Y Z T does not hold.
In the last example, we want to verify the inequality for four
random variables X, Y, Z and U. The inequality says that
I(Z;U) minus I(Z;U|X) minus I(Z;U|Y)
is less than or equal to one half of
I(X;Y) plus one quarter of
I(X;Z,U) plus one quarter of I(Y;Z,U).
This is not provable by ITIP but in fact this is true.
The last inequality is a so called non-Shannon-type inequality, which is valid
but not implied by the basic inequalities. See Chapter 15 for a discussion.
