A basic requirement for a secure cryptosystem is ciphertext indistinguishability. This can be described by the following game:

CI Game: Alice chooses two messages $m_0$ and $m_1$ and gives them to Bob. Bob randomly chooses $b=0$ or 1. He encrypts $m_b$ to get a ciphertext $c$, which he gives to Alice. Alice then guesses whether $m_0$ or $m_1$ was encrypted.

By randomly guessing, Alice can guess correctly about 1/2 of the time. If there is no strategy where she guesses correctly significantly more than 1/2 the time, then we say the cryptosystem has the ciphertext indistinguishability property.

For example, the shift cipher does not have this property. Suppose Alice chooses the two messages to be CAT and DOG. Bob randomly chooses one of them and sends back the ciphertext PNG. Alice observes that this cannot be a shift of DOG and thus concludes that Bob encrypted CAT.

When implemented in the most straightforward fashion, the RSA cryptosystem (see Chapter 9) also does not have the property. Since the encryption method is public, Alice can simply encrypt the two messages and compare with what Bob sends her. However, if Bob pads the messages with random bits before encryption, using a good pseudorandom number generator, then Alice should not be able to guess correctly significantly more than 1/2 the time because she will not know the random bits used in the padding.

The one-time pad where the key is chosen randomly has ciphertext indistinguishability. Because Bob chooses $b$ randomly,

From the previous section, we know that

and

Therefore, when Alice receives $c$, the two possibilities are equally likely, so the probability she guesses correctly is 1/2.

Because the one-time pad is too unwieldy for many applications, pseudorandom generators are often used to generate substitutes for one-time pads. In Chapter 5, we discuss some possibilities. For the present, we analyze how much such a choice can affect the security of the system.

A pseudorandom key generator produces $N$ possible keys, with each possible key $k$ having a probability $P(K=k)$. Usually, it takes an input, called a seed, and applies some algorithm to produce a key that “looks random.” The seed is transmitted to the decrypter of the ciphertext, who uses the seed to produce the key and then decrypt. The seed is significantly shorter than the length of the key. While the key might have, for example, 1 million bits, the seed could have only 100 bits, which makes transmission much more efficient, but this also means that there are fewer keys than with the one-time pad. Therefore, Proposition 4.4 says that perfect secrecy is not possible.

If the seed had only 20 bits, it would be possible to use all of the seeds to generate all possible keys. Then, given a ciphertext and a plaintext, it would be easy to see if there is a key that encrypts the plaintext to the ciphertext. But with a seed of 100 bits, it is infeasible to list all $2^{100}$ seeds and find the corresponding keys. Moreover, with a good pseudorandom key generator, it should be difficult to see whether a given key is one that could be produced from some seed.

To evaluate a pseudorandom key generator, Alice (the adversary) and Bob play the following game:

R Game: Bob flips a fair coin. If it’s Heads, he chooses a number $r$ uniformly randomly from the keyspace. If it’s Tails, he chooses a pseudorandom key $r$. Bob sends $r$ to Alice. Alice guesses whether $r$ was chosen randomly or pseudorandomly.

Of course, Alice could always guess that it’s random, for example, or she could flip her own coin and use that for her guess. In these cases, her probability of guessing correctly is 1/2. But suppose she knows something about the pseudorandom generator (maybe she has analyzed its inner workings, for example). Then she might be able to recognize sometimes that $r$ looks like something the pseudorandom generator could produce (of course, the random generator could also produce it, but with lower probability since it has many more possible outputs). This could occasionally give Alice a slight edge in guessing. So Alice’s overall probability of winning could increase slightly.

In an extreme case, suppose Alice knows that the pseudorandom number generator always has a 1 at the beginning of its output. The true random number generator will produce such an output with probability 1/2. If Alice sees this initial 1, she guesses that the output is from the pseudorandom generator. And if this 1 is not present, Alice knows that $r$ is random. Therefore, Alice guesses correctly with probability 3/4. (This is Exercise 9.)

We write

A good pseudorandom generator should have $ϵ$ very small, no matter what strategy Alice uses.

But will a good pseudorandom key generator work in a one-time pad? Let’s test it with the CI Game. Suppose Charles is using a pseudorandom key generator for his one-time pad and he is going to play the CI game with Alice. Moreover, suppose Alice has a strategy for winning this CI Game with probability ${\displaystyle \frac{1}{2}}+ϵ$ (if this happens, then Charles’s implementation is not very good). We’ll show that, under these assumptions, Alice can play the $R$ game with Bob and win with probability ${\displaystyle \frac{1}{2}}+{\displaystyle \frac{ϵ}{2}}$.

For example, suppose that the pseudorandom number generator is such that Alice has probability at most $0.51$ of winning the R Game. Then we must have $ϵ/2\le .01$, so $ϵ\le .02$. This means that the probability that Charles wins the CI game is at most $0.52$. In this way, we conclude that if the random number generator is good, then its use in a one-time pad is good.

Here is Alice’s strategy for the $R$ game. Alice and Bob do the following:

1. Bob flips a fair coin, as in the $R$ game, and gives $r$ to Alice. Alice wants to guess whether $r$ is random or pseudorandom.

2. Alice uses $r$ to play the $CI$ game with Charles.

   1. She calls up Charles, who chooses messages $m_0$ and $m_1$ and gives them to Alice.

   2. Alice chooses $b=0$ or 1 randomly.

   3. She encrypts $m_b$ using the key $r$ to obtain the ciphertext $c=m_b\oplus r$.

   4. She sends $c$ to Charles.

   5. Charles makes his guess for $b$ and succeeds with probability ${\displaystyle \frac{1}{2}}+ϵ$.

3. Alice now uses Charles’s guess to finish playing the $R$ Game.

4. If Charles guessed $b$ correctly, her guess to Bob is that $r$ was pseudorandom.

5. If Charles guessed incorrectly, her guess to Bob is that $r$ was random.

There are two ways that Alice wins the R Game. One is when Charles is correct and $r$ is pseudorandom, and the other is when Charles is incorrect and $r$ is random.

The probability that Charles is correct when $r$ is pseudorandom is ${\displaystyle \frac{1}{2}}+ϵ$, by assumption. This means that

If $r$ is random, then Alice encrypted $m_b$ with a true one-time pad, so Charles succeeds half the time and fails half the time. Therefore,

Putting the previous two calculations together, we see that the probability that Alice wins the R Game is

as we claimed.

The preceding shows that if we design a good random key generator, then an adversary can gain only a very slight advantage in using a ciphertext to distinguish between two plaintexts. Unfortunately, there are not good ways to prove that a given pseudorandom number generator is good (this would require solving some major problems in complexity theory), but knowledge of where the security of the system lies is significant progress.

For a good introduction to cryptography via the language of computational security and proofs of security, see [Katz and Lindell].