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

4.4 Perfect Secrecy of the One-Time Pad

Everyone knows that the one-time pad provides perfect secrecy. But what does this mean? In this section, we make this concept precise. Also, we know that it is very difficult in practice to produce a truly random key for a one-time pad. In the next section, we show quantitatively how biases in producing the key affect the security of the encryption.

In Section 20.4, we repeat some of the arguments of the present section and phrase them in terms of entropy and information theory.

The topics of this section and the next are part of the subject known as Provable Security. Rather than relying on intuition that a cryptosystem is secure, the goal is to isolate exactly what fundamental problems are the basis for its security. The result of the next section shows that the security of a one-time pad is based on the quality of the random number generator. In Section 10.5, we will show that the security of the ElGamal public key cryptosystem reduces to the difficulty of the Computational Diffie-Hellman problem, one of the fundamental problems related to discrete logarithms. In Section 12.3, we will use the Random Oracle Model to relate the security of a simple cryptosystem to the noninvertibility of a one-way function. Since these fundamental problems have been well studied, it is easier to gauge the security levels of the cryptosystems.

First, we need to define conditional probability. Let’s consider an example. We know that if it rains Saturday, then there is a reasonable chance that it will rain on Sunday. To make this more precise, we want to compute the probability that it rains on Sunday, given that it rains on Saturday. So we restrict our attention to only those situations where it rains on Saturday and count how often this happens over several years. Then we count how often it rains on both Saturday and Sunday. The ratio gives an estimate of the desired probability. If we call $A$ $A$ the event that it rains on Saturday and $B$ $B$ the event that it rains on Sunday, then the conditional probability of $B$ $B$ given $A$ $A$ is

P (B ∣ A) = \frac{P (A \cap B)}{P (A)},

$P (B ∣ A) = \frac{P (A \cap B)}{P (A)},$ (4.1)

where $P (A)$ $P (A)$ denotes the probability of the event $A$ $A$ . This formula can be used to define the conditional probability of one event given another for any two events $A$ $A$ and $B$ $B$ that have probabilities (we implicitly assume throughout this discussion that any probability that occurs in a denominator is nonzero).

Events $A$ $A$ and $B$ $B$ are independent if $P (A \cap B) = P (A) P (B)$ $P (A \cap B) = P (A) P (B)$ . For example, if Alice flips a fair coin, let $A$ $A$ be the event that the coin ends up Heads. If Bob rolls a fair six-sided die, let $B$ $B$ be the event that he rolls a 3. Then $P (A) = 1 / 2$ $P (A) = 1 / 2$ and $P (B) = 1 / 6$ $P (B) = 1 / 6$ . Since all 12 combinations of ${H e a d, T a i l}$ ${H e a d, T a i l}$ and ${1, 2, 3, 4, 5, 6}$ ${1, 2, 3, 4, 5, 6}$ are equally likely, $P (A \cap B) = 1 / 12$ $P (A \cap B) = 1 / 12$ , which equals $P (A) P (B)$ $P (A) P (B)$ . Therefore, $A$ $A$ and $B$ $B$ are independent.

If $A$ $A$ and $B$ $B$ are independent, then

P (B ∣ A) = \frac{P (A \cap B)}{P (A)} = \frac{P (A) P (B)}{P (A)} = P (B),

$P (B ∣ A) = \frac{P (A \cap B)}{P (A)} = \frac{P (A) P (B)}{P (A)} = P (B),$

which means that knowing that $A$ $A$ happens does not change the probability that $B$ $B$ happens. By reversing the steps in the above equation, we see that

A and B are independent ⟺ P (B ∣ A) = P (B) .

$A and B are independent ⟺ P (B ∣ A) = P (B) .$

An example of events that are not independent is the original example, where $A$ $A$ is the event that it rains on Saturday and $B$ $B$ is the event that it rains on Sunday, since $P (B ∣ A) > P (B)$ $P (B ∣ A) > P (B)$ . (Unfortunately, a widely used high school algebra text published around 2005 gave exactly one example of independent events: $A$ $A$ and $B$ $B$ .)

How does this relate to cryptography? In a cryptosystem, there is a set of possible keys. Let’s say we have $N$ $N$ keys. If we have a perfect random number generator to choose the keys, then the probability that the key is $k$ $k$ is $P (K = k) = 1 / N$ $P (K = k) = 1 / N$ . In this case we say that the key is chosen uniformly randomly. In any case, we assume that each key has a certain probability of being chosen. We also have various possible plaintexts $m$ $m$ and each one has a certain probability $P (M = m)$ $P (M = m)$ . These probably do not all have the same probability. For example, the message attack at noon is usually more probable than two plus two equals seven. Finally, each possible ciphertext $c$ $c$ has a probability $P (C = c)$ $P (C = c)$ .

We say that a cryptosystem has perfect secrecy if

P (M = m ∣ C = c) = P (M = m)

$P (M = m ∣ C = c) = P (M = m)$

for all possible plaintexts $m$ $m$ and all possible ciphertexts $c$ $c$ . In other words, knowledge of the ciphertext never changes the probability that a given plaintext occurs. This means that eavesdropping gives no advantage to Eve if she wants to guess the message.

We can now formalize what we claimed about the one-time pad.

Theorem

If the key is chosen uniformly randomly, then the one-time pad has perfect secrecy.

Proof. We need to show that $P (M = m ∣ C = c) = P (M = m)$ $P (M = m ∣ C = c) = P (M = m)$ for each pair $m, c$ $m, c$ .

Let’s say that there are $N$ $N$ keys, each of which has probability $1 / N$ $1 / N$ . We start by showing that each possible ciphertext $c$ $c$ also has probability $1 / N$ $1 / N$ . Start with any plaintext $m$ $m$ . If $c$ $c$ is the ciphertext, then the key is $k = m \oplus c$ $k = m \oplus c$ . Therefore, the probability that $c$ $c$ is the ciphertext is the probability that $m \oplus c$ $m \oplus c$ is the key, namely $1 / N$ $1 / N$ , since all keys have this probability. Therefore, we have proved that

P (C = c ∣ M = m) = 1 / N

$P (C = c ∣ M = m) = 1 / N$

for each $c$ $c$ and $m$ $m$ .

We now combine the contributions from the various possibilities for $m$ $m$ . Note that if we sum $P (M = m)$ $P (M = m)$ over all possible $m$ $m$ , then

\sum_{m} P (M = m) = 1

$\sum_{m} P (M = m) = 1$ (4.2)

since this is the probability of the plaintext existing. Similarly, the event $C = c$ $C = c$ can be split into the disjoint sets $(C = c ⋂ M = m)$ $(C = c ⋂ M = m)$ , which yields

\begin{array}{l} P (C = c) & = & \sum_{m} P (C = c \cap M = m) \\ = & \sum_{m} P (C = c | M = m) P (M = m) (by (4.1)) \\ = & \sum_{m} \frac{1}{N} P (M = m) \\ = & \frac{1}{N} (by (4.2)) . \end{array}

$\begin{array}{l} P (C = c) & = & \sum_{m} P (C = c \cap M = m) \\ = & \sum_{m} P (C = c | M = m) P (M = m) (by (4.1)) \\ = & \sum_{m} \frac{1}{N} P (M = m) \\ = & \frac{1}{N} (by (4.2)) . \end{array}$

Applying Equation (4.1) twice yields

\begin{aligned} P (M = m ∣ C = c) P (C = c) & = P (C = c ⋂ M = m) \\ = P (C = c ∣ M = m) P (M = m) . \end{aligned}

$\begin{aligned} P (M = m ∣ C = c) P (C = c) & = P (C = c ⋂ M = m) \\ = P (C = c ∣ M = m) P (M = m) . \end{aligned}$

Since we have already proved that $P (C = c) = 1 / N = P (C = c ∣ M = m)$ $P (C = c) = 1 / N = P (C = c ∣ M = m)$ , we can multiply by $N$ $N$ to obtain

P (M = m ∣ C = c) = P (M = m),

$P (M = m ∣ C = c) = P (M = m),$

which says that the one-time pad has perfect secrecy.

One of the difficulties with using the one-time pad is that the number of possible keys is as least as large the number of possible messages. Unfortunately, this is required for perfect secrecy:

Proposition

If a cryptosystem has perfect secrecy, then the number of possible keys is greater than or equal to the number of possible plaintexts.

Proof. Let $M$ $M$ be the number of possible plaintexts and let $N$ $N$ be the number of possible keys. Suppose $M > N$ $M > N$ . Let $c$ $c$ be a ciphertext. For each key $k$ $k$ , decrypt $c$ $c$ using the key $k$ $k$ . This gives $N$ $N$ possible plaintexts, and these are the only plaintexts that can encrypt to $c$ $c$ . Since $M > N$ $M > N$ , there is some plaintext $m$ $m$ that is not a decryption of $c$ $c$ . Therefore,

P (M = m ∣ C = c) = 0 \neq P (M = m) .

$P (M = m ∣ C = c) = 0 \neq P (M = m) .$

This contradicts the assumption that the system has perfect secrecy. Therefore, $M \leq N$ $M \leq N$ .

Example

Suppose a parent goes to the pet store to buy a pet for a child’s birthday. The store sells 30 different pets with 3-letter names (ant, bat, cat, dog, eel, elk, ...). The parent chooses a pet at random, encrypts its name with a shift cipher, and sends the ciphertext to let the other parent know what has been bought. The child intercepts the message, which is ZBL. The child hopes the present is a dog. Since DOG is not a shift of ZBL, the child realizes that the conditional probability

P (M = d o g ∣ C = Z B L) = 0

$P (M = d o g ∣ C = Z B L) = 0$

and is disappointed. Since $P (M = d o g) = 1 / 30$ $P (M = d o g) = 1 / 30$ (because there are 30 equally likely possibilities), we have $P (M = d o g ∣ C = Z B L) \neq P (M = d o g)$ $P (M = d o g ∣ C = Z B L) \neq P (M = d o g)$ , so there is not perfect secrecy. This is because a given ciphertext has at most 26 possible corresponding plaintexts, so knowledge of the ciphertext restricts the possibilities for the decryption. Then the child realizes that YAK is the only possible shift of ZBL, so $P (M = y a k ∣ C = Z B L) = 1$ $P (M = y a k ∣ C = Z B L) = 1$ . This does not equal $P (M = y a k)$ $P (M = y a k)$ , so again we see that we don’t have perfect secrecy. But now the child is happy, being the only one in the neighborhood who will have a yak as a pet.

..................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 4.4 Perfect Secrecy of the One-Time Pad

Create new playlist

Sign In

Sign Up

Table of Contents for
4.4 Perfect Secrecy of the One-Time Pad