# 4.5 Indistinguishability and Security

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

CI Game: Alice chooses two messages  and  and gives them to Bob. Bob randomly chooses  or 1. He encrypts  to get a ciphertext , which he gives to Alice. Alice then guesses whether  or  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  randomly,



From the previous section, we know that



and



Therefore, when Alice receives , 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  possible keys, with each possible key  having a probability . 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  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  uniformly randomly from the keyspace. If it’s Tails, he chooses a pseudorandom key . Bob sends  to Alice. Alice guesses whether  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  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  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  (if this happens, then Charles’s implementation is not very good). We’ll show that, under these assumptions, Alice can play the  game with Bob and win with probability .

For example, suppose that the pseudorandom number generator is such that Alice has probability at most  of winning the R Game. Then we must have , so . This means that the probability that Charles wins the CI game is at most . 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  game. Alice and Bob do the following:

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

2. Alice uses  to play the  game with Charles.

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

2. Alice chooses  or 1 randomly.

3. She encrypts  using the key  to obtain the ciphertext .

4. She sends  to Charles.

5. Charles makes his guess for  and succeeds with probability .

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

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

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

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

The probability that Charles is correct when  is pseudorandom is , by assumption. This means that



If  is random, then Alice encrypted  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].