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 m0 and m1 and gives them to Bob. Bob randomly chooses b=0 or 1. He encrypts mb to get a ciphertext c, which he gives to Alice. Alice then guesses whether m0 or m1 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 ...

Get Introduction to Cryptography with Coding Theory, 3rd Edition now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.