Search in book...
Toggle Font Controls
Create new playlist

Name your new playlist

Playlist description (optional)
Sign In

Email address

Password

Forgot Password?

or

Continue with Facebook

Continue with Google
Sign Up

Full Name

Email address

Confirm Email Address

Password

or

Continue with Facebook

Continue with Google

20.4 Perfect Secrecy

Intuitively, the one-time pad provides perfect secrecy. In Section 4.4, we gave a mathematical meaning to this statement. In the present section, we repeat some of the arguments of that section and phrase some of the ideas in terms of entropy.

Suppose we have a cipher system with possible plaintexts $P$ $P$ , ciphertexts $C$ $C$ , and keys $K$ $K$ . Each plaintext in $P$ $P$ has a certain probability of occurring; some are more likely than others. The choice of a key in $K$ $K$ is always assumed to be independent of the choice of plaintext. The possible ciphertexts in $C$ $C$ have various probabilities, depending on the probabilities for $P$ $P$ and $K$ $K$ .

If Eve intercepts a ciphertext, how much information does she obtain for the key? In other words, what is $H (K | C)$ $H (K | C)$ ? Initially, the uncertainty in the key was $H (K)$ $H (K)$ . Has the knowledge of the ciphertext decreased the uncertainty?

Example

Suppose we have three possible plaintexts: $a, b, c$ $a, b, c$ with probabilities .5, .3, .2 and two keys $k_{1}, k_{2}$ $k_{1}, k_{2}$ with probabilities .5 and .5. Suppose the possible ciphertexts are $U, V, W$ $U, V, W$ . Let $e_{k}$ $e_{k}$ be the encryption function for the key $k$ $k$ . Suppose

\begin{array}{rcl} e_{k_{1}} (a) = U, e_{k_{1}} (b) = V, e_{k_{1}} (c) = W \\ e_{k_{2}} (a) = U, e_{k_{2}} (b) = W, e_{k_{2}} (c) = V . \end{array}

$\begin{array}{rcl} e_{k_{1}} (a) = U, e_{k_{1}} (b) = V, e_{k_{1}} (c) = W \\ e_{k_{2}} (a) = U, e_{k_{2}} (b) = W, e_{k_{2}} (c) = V . \end{array}$

Let $p_{P} (a)$ $p_{P} (a)$ denote the probability that the plaintext is $a$ $a$ , etc. The probability that the ciphertext is $U$ $U$ is

\begin{array}{rcl} p_{C} (U) & = & p_{K} (k_{1}) p_{P} (a) + p_{K} (k_{2}) p_{P} (a) \\ = & (.5) (.5) + (.5) (.5) = .50 . \end{array}

$\begin{array}{rcl} p_{C} (U) & = & p_{K} (k_{1}) p_{P} (a) + p_{K} (k_{2}) p_{P} (a) \\ = & (.5) (.5) + (.5) (.5) = .50 . \end{array}$

Similarly, we calculate $p_{C} (V) = .25$ $p_{C} (V) = .25$ and $p_{C} (W) = .25$ $p_{C} (W) = .25$ .

Suppose someone intercepts a ciphertext. This gives some information on the plaintext. For example, if the ciphertext is $U$ $U$ , then it can be deduced immediately that the plaintext was $a$ $a$ . If the ciphertext is $V$ $V$ , the plaintext was either $b$ $b$ or $c$ $c$ .

We can even say more: The probability that a ciphertext is $V$ $V$ is .25, so the conditional probability that the plaintext was $b$ $b$ , given that the ciphertext is $V$ $V$ is

p (b | V) = \frac{p_{(P, C)} (b, V)}{p_{C} (V)} = \frac{p_{(P, K)} (b, k_{1})}{p_{C} (V)} = \frac{(.3) (.5)}{.25} = .6 .

$p (b | V) = \frac{p_{(P, C)} (b, V)}{p_{C} (V)} = \frac{p_{(P, K)} (b, k_{1})}{p_{C} (V)} = \frac{(.3) (.5)}{.25} = .6 .$

Similarly, $p (c | V) = .4$ $p (c | V) = .4$ and $p (a | V) = 0$ $p (a | V) = 0$ . We can also calculate

p (a | W) = 0, p (b | W) = .6, p (c | W) = .4 .

$p (a | W) = 0, p (b | W) = .6, p (c | W) = .4 .$

Note that the original probabilities of the plaintexts were .5, .3, and .2; knowledge of the ciphertext allows us to revise the probabilities. Therefore, the ciphertext gives us information about the plaintext. We can quantify this via the concept of conditional entropy. First, the entropy of the plaintext is

H (P) = - (.5 {log}_{2} (.5) + .3 {log}_{2} (.3) + .2 {log}_{2} (.2)) = 1.485.

$H (P) = - (.5 {log}_{2} (.5) + .3 {log}_{2} (.3) + .2 {log}_{2} (.2)) = 1.485.$

The conditional entropy of $P$ $P$ given $C$ $C$ is

H (P | C) = - \sum_{x \in {a, b, c}} \sum_{Y \in {U, V, W}} p (Y) p (x | Y) {log}_{2} (p (x | Y)) = .485 .

$H (P | C) = - \sum_{x \in {a, b, c}} \sum_{Y \in {U, V, W}} p (Y) p (x | Y) {log}_{2} (p (x | Y)) = .485 .$

Therefore, in the present example, the uncertainty for the plaintext decreases when the ciphertext is known.

On the other hand, we suspect that for the one-time pad the ciphertext yields no information about the plaintext that was not known before. In other words, the uncertainty for the plaintext should equal the uncertainty for the plaintext given the ciphertext. This leads us to the following definition and theorem.

Definition

A cryptosystem has perfect secrecy if $H (P | C) = H (P)$ $H (P | C) = H (P)$ .

Theorem

The one-time pad has perfect secrecy.

Proof. Recall that the basic setup is the following: There is an alphabet with $Z$ $Z$ letters (for example, $Z$ $Z$ could be 2 or 26). The possible plaintexts consist of strings of characters of length $L$ $L$ . The ciphertexts are strings of characters of length $L$ $L$ . There are $Z^{L}$ $Z^{L}$ keys, each consisting of a sequence of length $L$ $L$ denoting the various shifts to be used. The keys are chosen randomly, so each occurs with probability $1 / Z^{L}$ $1 / Z^{L}$ .

Let $c \in C$ $c \in C$ be a possible ciphertext. As before, we calculate the probability that $c$ $c$ occurs:

p_{C} (c) = \sum_{\begin{matrix} x \in P, k \in K \\ e_{k} (x) = c \end{matrix}} p_{P} (x) p_{K} (k) .

$p_{C} (c) = \sum_{\begin{matrix} x \in P, k \in K \\ e_{k} (x) = c \end{matrix}} p_{P} (x) p_{K} (k) .$

Here $e_{k} (x)$ $e_{k} (x)$ denotes the ciphertext obtained by encrypting $x$ $x$ using the key $k$ $k$ . The sum is over those pairs $x, k$ $x, k$ such that $k$ $k$ encrypts $x$ $x$ to $c$ $c$ . Note that we have used the independence of $P$ $P$ and $K$ $K$ to write joint probability $p_{(P, K)} (x, k)$ $p_{(P, K)} (x, k)$ as the product of the individual probabilities.

In the one-time pad, every key has equal probability $1 / Z^{L}$ $1 / Z^{L}$ , so we can replace $p_{K} (k)$ $p_{K} (k)$ in the above sum by $1 / Z^{L}$ $1 / Z^{L}$ . We obtain

p_{C} (c) = \frac{1}{Z^{L}} \sum_{\begin{matrix} x \in P, k \in K \\ e_{k} (x) = c \end{matrix}} p_{P} (x) .

$p_{C} (c) = \frac{1}{Z^{L}} \sum_{\begin{matrix} x \in P, k \in K \\ e_{k} (x) = c \end{matrix}} p_{P} (x) .$

We now use another important feature of the one-time pad: For each plaintext $x$ $x$ and each ciphertext $c$ $c$ , there is exactly one key $k$ $k$ such that $e_{k} (x) = c$ $e_{k} (x) = c$ . Therefore, every $x \in P$ $x \in P$ occurs exactly once in the preceding sum, so we have $Z^{- L} \sum_{x \in P} p_{P} (x)$ $Z^{- L} \sum_{x \in P} p_{P} (x)$ . But the sum of the probabilities of all possible plaintexts is 1, so we obtain

p_{C} (c) = \frac{1}{Z^{L}} .

$p_{C} (c) = \frac{1}{Z^{L}} .$

This confirms what we already suspected: Every ciphertext occurs with equal probability.

Now let’s calculate some entropies. Since $K$ $K$ and $C$ $C$ each have equal probabilities for all $Z^{L}$ $Z^{L}$ possibilities, we have

H (K) = H (C) = {log}_{2} (Z^{L}) .

$H (K) = H (C) = {log}_{2} (Z^{L}) .$

We now calculate $H (P, K, C)$ $H (P, K, C)$ in two different ways. Since knowing $(P, K, C)$ $(P, K, C)$ is the same as knowing $(P, K)$ $(P, K)$ , we have

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

$H (P, K, C) = H (P, K) = H (P) + H (K) .$

The last equality is because $P$ $P$ and $K$ $K$ are independent. Also, knowing $(P, K, C)$ $(P, K, C)$ is the same as knowing $(P, C)$ $(P, C)$ since $C$ $C$ and $P$ $P$ determine $K$ $K$ for the one-time pad. Therefore,

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

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

The last equality is the chain rule. Equating the two expressions, and using the fact that $H (K) = H (C)$ $H (K) = H (C)$ , we obtain $H (P | C) = H (P)$ $H (P | C) = H (P)$ . This proves that the one-time pad has perfect secrecy.

The preceding proof yields the following more general result. Let $# K$ $# K$ denote the number of possible keys, etc.

Theorem

Consider a cryptosystem such that

Every key has probability $1 / # K$ $1 / # K$ .
For each $x \in P$ $x \in P$ and $c \in C$ $c \in C$ there is exactly one $k \in K$ $k \in K$ such that $e_{k} (x) = c$ $e_{k} (x) = c$ .

Then this cryptosystem has perfect secrecy.

It is easy to deduce from condition (2) that $# C = # K$ $# C = # K$ . Conversely, it can be shown that if $# P = # C = # K$ $# P = # C = # K$ and the system has perfect secrecy, then (1) and (2) hold (see [Stinson, Theorem 2.4]).

It is natural to ask how the preceding concepts apply to RSA. The possibly surprising answer is that $H (P | C) = 0$ $H (P | C) = 0$ ; namely, the ciphertext determines the plaintext. The reason is that entropy does not take into account computation time. The fact that it might take billions of years to factor $n$ $n$ is irrelevant. What counts is that all the information needed to recover the plaintext is contained in the knowledge of $n$ $n$ , $e$ $e$ , and $c$ $c$ .

The more relevant concept for RSA is the computational complexity of breaking the system.

..................Content has been hidden....................

You can't read the all page of ebook, please click here login for view all page.

Table of Contents for 20.4 Perfect Secrecy

Create new playlist

Sign In

Sign Up

Table of Contents for
20.4 Perfect Secrecy