Information Theory and Perfect Secrecy

Overview of Information Theory Concepts

Entropy

• Definition. The Entropy $H(X)$ of a discrete random variable $X$ is defined as

  $$H(X)=-\sum_{x \in \mathscr{X}} \operatorname{Pr}[X=x] \log _{2} \operatorname{Pr}[X=x]$$

  The entropy is equivalently stated as $H(X) = \mathbb{E} \left(-\log_2 \Pr[X]\right)$.

• Entropy is a measure of the uncertainty of a random variable and is expressed in bits. We use the convention that $0 \log_2 0 = 0$.

• In general, we note that $H(X) \le \log_2 |\mathscr{X}|$.

Conditional Entropy

• Definition. The Conditional Entropy $H(X \mid Y)$ of a discrete random variable $X$ conditioned on another random variable $Y$ is defined as

  $$H(X \mid Y)=-\sum_{x \in \mathscr{X}, y \in \mathscr{Y}} \operatorname{Pr}[X=x, Y=y] \log _{2} \operatorname{Pr}[X=x \mid Y=y]$$

  The conditional entropy is equivalently stated as $H(X \mid Y) = \mathbb{E}(-\log_2 \Pr[X \mid Y])$.

• We observe that

  $$H(X \mid Y):=-\sum_{y \in \mathscr{Y}} \operatorname{Pr}[Y=y] H(X \mid Y=y)$$

Chain Rule and other entropy relations

• The following Chain Rule holds

  $$H(XY) = H(X) + H(Y \mid X) = H(Y) + H(X \mid Y)$$

  Here $H(X Y)=H(X, Y)=-\sum_{x \in \mathscr{X}, y \in \mathscr{Y}} \operatorname{Pr}[X=x, Y=y] \log _{2} \operatorname{Pr}[X=x, Y=y]$ denotes the entropy of the joint random variable $(X, Y)$.

• In general, we have $H\left(X_{1} X_{2} \ldots X_{n}\right)=H\left(X_{1}\right)+H\left(X_{2} \mid X_{1}\right)+H\left(X_{3} \mid X_{1} X_{2}\right)+\ldots+H\left(X_{n} \mid X_{1} X_{2} \ldots X_{n-1}\right)$.

• The uncertainty of a random variable $X$ can never increase by knowledge of the outcome of another random variable $Y$, i.e. $H(X \mid Y) \le H(X)$ with equality iff $X, Y$ are independent.

  We thus have $H(XY) \le H(Y) + H(X)$ with equality iff $X, Y$ are independent.

Relative Entropy

• Definition. The relative entropy $D(p(X) \Vert q(X))$ between two probability distributions $p(X), q(X)$ of a random variable $X$ is defined as

  $$D(p(X) \| q(X))=\sum_{x \in \mathscr{X}} p(X=x) \log _{2}\left(\frac{p(X=x)}{q(X=x)}\right)$$

• The relative entropy is a measure of the distance between two probability distributions. It can be thought of as the inefficiency of assuming distribution $q(X)$ when the correct distribution is $p(X)$.

• Note $D(p(X) \| q(X))=\mathbb{E}_{P}\left(\log _{2} \frac{p(X)}{q(X)}\right)$.

• In general $D(p(X) \| q(X)) \neq D(q(X) \| p(X))$.

Mutual Information

• Definition. The Mutual Information $I(X; Y)$ between random variables $X$ and $Y$ is defined as

  $$\begin{aligned} I(X ; Y) & =D(\operatorname{Pr}[X, Y] \| \operatorname{Pr}[X] \operatorname{Pr}[Y]) \\ & =\sum_{x \in \mathscr{X}, y \in \mathscr{Y} } \operatorname{Pr}[X=x, Y=y] \log _{2} \frac{\operatorname{Pr}[X=x, Y=y]}{\operatorname{Pr}[X=x] \operatorname{Pr}[Y=y]} \end{aligned}$$

• The mutual information $I(X; Y)$ measures the information (in bits) we receive about the random variable $X$ when observing the outcome of the random variable $Y$.

  It also describes the information we receive about the random variable $Y$ when observing the outcome of the random variable $X$.

• Mutual Information is also the a measure of the price for encoding $(X, Y)$ as a pair of independent random variables, when in reality they are not.

• The Mutual Information obeys the following properties

  $$\begin{array}{c} I(X ; Y)=H(X)-H(X \mid Y)=H(Y)-H(Y \mid X) \\ I(X ; Y)=H(X)+H(Y)-H(X, Y)=I(Y ; X) \\ I(X ; X)=H(X) \end{array}$$

  We have that $I(X; Y) \ge 0$ with equality if and only if $X, Y$ are independent.

  The Conditional Mutual Information $I(X ; Y \mid Z):=D(\operatorname{Pr}[X, Y \mid Z] \| \operatorname{Pr}[X \mid Z] \operatorname{Pr}[Y \mid Z])$ where $D(p[X \mid Z] \| q[X \mid Z]):=\sum_{z \in \mathscr{X}} p(Z=z) \sum_{x \in \mathscr{X}} p(X=x \mid Z=z) \log _{2} \frac{p(X=x \mid Z=z)}{q(X=x \mid Z=z)}$ is the conditional relative entropy.

Perfect Secrecy in Information-Theoretic Terms

Message and Key Entropies

• We have the key entropy

  $$H(K \mid C)=-\sum_{k \in \mathscr{K}, c \in \mathscr{C}} \operatorname{Pr}[K=k, C=c] \log _{2} \operatorname{Pr}[K=k \mid C=c]$$

  and the message entropy

  $$H(M)=-\sum_{m \in \mathscr{M}} \operatorname{Pr}[M=m] \log _{2} \operatorname{Pr}[M=m]$$

• The key entropy describes the uncertainty Eve faces regarding the unknown key a priori and the message entropy describes the uncertainty regarding the transmitted message.

• The key equivocation

  $$H(K \mid C)=-\sum_{k \in \mathscr{K}, c \in \mathscr{C}} \operatorname{Pr}[K=k, C=c] \log _{2} \operatorname{Pr}[K=k \mid C=c]$$

  and the message equivocation

  $$H(M \mid C)=-\sum_{m \in \mathscr{M}, c \in \mathscr{C}} \operatorname{Pr}[M=m, C=c] \log _{2} \operatorname{Pr}[M=m \mid C=c]$$

  describe the remaining uncertainty after Eve observes the transmitted ciphertext.

Perfect Secrecy in Information-Theoretic terms

• We have that $H(K\mid C) \le H(K)$ and $H(M\mid C) \le H(M)$.

  This reflects the fact that the uncertainties never increase by knowledge of the ciphertext.

• An encryption scheme is said to have perfect secrecy if $I(M; C) = 0$.

• In a system with perfect secrecy, the plaintext and the ciphertext are independent. When Eve observes the ciphertext, she obtains no information at all about the plaintext,
  i.e., $H(M \mid C) = H(M)$.

• Theorem. For an encryption scheme with perfect secrecy we have $H(M) \le H(K)$.

— Mar 1, 2023

Information Theory and Perfect Secrecy by Lu Meng is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License. Permissions beyond the scope of this license may be available at About.