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 the O’Reilly learning platform.

O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.