20.6 Exercises – Introduction to Cryptography with Coding Theory, 3rd Edition

20.6 Exercises

  1. Let X1 and X2 be two independent tosses of a fair coin. Find the entropy H(X1) and the joint entropy H(X1, X2). Why is H(X1, X2)=H(X1)+H(X2)?

  2. Consider an unfair coin where the two outcomes, heads and tails, have probabilities p(heads)=p and p(tails)=1p.

    1. If the coin is flipped two times, what are the possible outcomes along with their respective probabilities?

    2. Show that the entropy in part (a) is 2plog2(p)2(1p)log2(1p). How could this have been predicted without calculating the probabilities in part (a)?

  3. A random variable X takes the values 1, 2, , n,  with probabilities 12, 122, , 12n, . Calculate the entropy H(X).

  4. Let X be a random variable taking on integer values. The probability is 1/2 that X is in the range [0, 281], with all such values being equally likely, and the probability is 1/2 that the value is in the range [28, 2321], with all such values being equally likely. Compute H(X).

  5. Let X be a random event taking on the values 2, 1, 0, 1, 2, all with positive probability. What is the general inequality/equality between H(X) and H(Y), where Y is the following?

    1. Y=2X

    2. Y=X2

    1. In this problem we explore the relationship between the entropy of a random variable X and the entropy of a function f(X) of the random variable. The following is a short proof that shows H(f(X))H(X). Explain what principles are used in each of the steps.

      H(X, f(X))=H(X)+H(f(X)|X)=H(X), H(X, f(X))=H(f(X))+H(X|f(X))H(f(X)).
    2. Letting X take on the values ±1 and letting f(x)=x2, show that it is possible to have H(f(X))<H(X).

    3. In part (a), show that you have equality if and only if f is a one-to-one function (more precisely, f is one-to-one on the set of outputs of X that have nonzero probability).

    4. The preceding results can be used to study the behavior of the run length coding of a sequence. Run length coding is a technique that is commonly used in data compression. Suppose that X1, X2, , Xn are random variables that take the values 0 or 1. This sequence of random variables can be thought of as representing the output of a binary source. The run length coding of X1, X2, , Xn is a sequence L=(L1, L2, , Lk) that represents the lengths of consecutive symbols with the same value. For example, the sequence 110000100111 has a run length sequence of L=(2, 4, 1, 2, 3). Observe that L is a function of X1, X2, , Xn. Show that L and X1 uniquely determine X1, X2, , Xn. Do L and Xn determine X1, X2, , Xn? Using these observations and the preceding results, compare H(X1, X2, , Xn), H(L), and H(L, X1).

  6. A bag contains five red balls, three white balls, and two black balls that are identical to each other in every manner except color.

    1. Choose two balls from the bag with replacement. What is the entropy of this experiment?

    2. What is the entropy of choosing two balls without replacement? (Note: In both parts, the order matters; i.e., red then white is not the same as white then red.)

  7. We often run into situations where we have a sequence of n random events. For example, a piece of text is a long sequence of letters. We are concerned with the rate of growth of the joint entropy as n increases. Define the entropy rate of a sequence X={Xk} of random events as

    H(X)=limn1nH(X1, X2, Xn).
    1. A very crude model for a language is to assume that subsequent letters in a piece of text are independent and come from identical probability distributions. Using this, show that the entropy rate equals H(X1).

    2. In general, there is dependence among the random variables. Assume that X1, X2, Xn have the same probability distribution but are somehow dependent on each other (for example, if I give you the letters TH you can guess that the next letter is E). Show that

      H(X1, X2, Xn)kH(Xk)

      and thus that

      H(X)H(X1)

      (if the limit defining H exists).

  8. Suppose we have a cryptosystem with only two possible plaintexts. The plaintext a occurs with probability 1/3 and b occurs with probability 2/3. There are two keys, k1 and k2, and each is used with probability 1/2. Key k1 encrypts a to A and b to B. Key k2 encrypts a to B and b to A.

    1. Calculate H(P), the entropy for the plaintext.

    2. Calculate H(P|C), the conditional entropy for the plaintext given the ciphertext. (Optional hint: This can be done with no additional calculation by matching up this system with another well-known system.)

  9. Consider a cryptosystem {P, K, C}.

    1. Explain why H(P, K)=H(C, P, K)=H(P)+H(K).

    2. Suppose the system has perfect secrecy. Show that

      H(C, P)=H(C)+H(P)

      and

      H(C)=H(K)H(K|C, P).

    3. Suppose the system has perfect secrecy and, for each pair of plaintext and ciphertext, there is at most one corresponding key that does the encryption. Show that H(C)=H(K).

  10. Prove that for a cryptosystem {P, K, C} we have

    H(C|P)=H(P, K, C)H(P)H(K|C, P)=H(K)H(K|C, P).
  11. Consider a Shamir secret sharing scheme where any five people of a set of 20 can determine the secret K, but no fewer can do so. Let H(K) be the entropy of the choice of K, and let H(K|S1) be the conditional entropy of K, given the information supplied to the first person. What are the relative sizes of H(K) and H(K|S1)? (Larger, smaller, equal?)

  12. Let X be a random event taking on the values 1, 2, 3, , 36, all with equal probability.

    1. What is the entropy H(X)?

    2. Let Y=X36(mod37). What is H(Y)?

    1. Show that the maximum of plog2p(1p)log2(1p) for 0p1 occurs when p=1/2.

    2. Let pi0 for 1in. Show that the maximum of

      ipilog2pi, 

      subject to the constraint ipi=1, occurs when p1==pn. (Hint: Lagrange multipliers could be useful in this problem.)

    1. Suppose we define H˜(Y|X)=x, ypY(y|x)log2pY(y|x). Show that if X and Y are independent, and X has |X| possible outputs, then H˜(Y|X)=|X|H(Y)H(Y).

    2. Use (a) to show that H˜(Y|X) is not a good description of the uncertainty of Y given X.