The indistinguishability experiment

You pick two messages. A hidden coin decides which one gets encrypted, and you see only the ciphertext. A scheme is perfectly indistinguishable when no strategy, on any pair of messages, beats a coin flip.

Scheme Length n

Message m₀

Message m₁

Adversary Speed

0rounds

The challenge

m₀	····
m₁	····
ciphertext	····

Press “One round” to get a ciphertext.

What the ciphertext looks like under each coin

P(c | b = 0)

P(c | b = 1)

Success rate as rounds accumulate

Rounds on a log axis. The grey envelope is two standard deviations around a coin flip.

your success rate best possible for this pair coin-flip envelope