Introduction to Cryptography with Coding Theory, 3rd Edition

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 $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 ...