Consider the following game,

Eve instructs Bob to go into a room,

Bob finds the room empty,

except for some locks, an empty box,

and a single deck of cards.

Eve tells Bob to select a card from the deck,

and hide it as best as he can.

The rules are simple,

Bob cannot leave the room with anything,

cards and keys all stayed in the room,

and he can put at most one card in the box,

Eve agrees that she has never seen the locks.

He wins the game if Eve is unable to determine his card,

So what is his best strategy?

Well, Bob selected a card, six of diamonds,

and threw it in the box.

First, he considered the different types of locks.

Maybe he should lock the card in the box with the key.

Though she can pick locks,

so he considers the combination lock,

The key is on the back,

so if he locks it and scratches it off,

it seems like the best choice.

But suddenly he realized the problem.

The remaining cards on the table

leak information about his choice,

since it's now missing from the deck.

The locks are a decoy.

He shouldn't separate his card from the deck.

He returns his card to the deck.

But can't remember the position of his card.

So he shuffles the deck to randomize it.

Shuffling is the best lock,

because it leaves no information about his choice.

His card is now equally likely to be any card in the deck.

He can now leave the cards openly in confidence.

Bob wins the game,

because the best Eve can do is simply guess,

as he'd left no information about his choice,

Most importantly,

even if we give Eve unlimited computational power,

she can't do any better than a guess.

This defines what we call perfect secrecy.

On September 1st, 1945, 29 year old Claude Shannon

published a classified paper on this idea.

Shannon gave the first mathematical proof

for how and why the one time pad is perfectly secret.

Shannon thinks about encryption schemes in a following way:

Imagine Alice writes a message to Bob, 20 letters long.

This is equivalent to picking one specific page

from the message space.

The message space can be thought of as

a complete collection of all possible 20-letter messages.

Anything you can think of that's 20 letters long

is a page in this stack.

Next Alice applies a shared key,

which is a list of 20 randomly generated shifts

between 1 and 26.

The key space is the complete collection of all possible outcomes.

So generating a key is equivalent to

selecting a page from the stack at random.

When she applies the shifts to encrypt the message,

she ends up with the cipher text.

The cipher text space represents

all possible results of an encryption.

When she applies the key,

it maps to a unique page in this stack.

Notice that the size of the message space

equals the size of the key space,

equals the size of the cipher text space.

This defines what we call perfect secrecy,

for if someone has access to a page of cipher text only,

the only thing that they know is

that every message is equally likely.

So no amount of computational power

could ever help improve a blind guess.

Now the big problem,

you're wondering with the one time pad

is that we've to share these long keys in advance.

To solve this problem,

we need to relax our definition of secrecy,

by developing a definition of pseudo-randomness.

Mind=blown

When a human shuffles a deck of cards, the result usually is a lot less random than, e.g., a computer that shuffles a virtual deck of cards. Reasons for this include the fact that the initial distribution of the cards may be partially sorted, e.g., when they come from a previous game, then the impatience of the shuffling human who tends to shuffle only for a short amount of time, and cards that may stick together. I have heard of one occasion where this became very noticeable: when, for the first time, Bridge tournaments where held with cards that where shuffled by a computer. The experienced Bridge players immediately protested and claimed that the computer generated predominantly "unlikely" distributions. However, it turned out that there was nothing wrong with the computer, but that human shuffling resulted in quite distinct distributions.