0:00:01.034,0:00:02.378
(tranquil music)

0:00:04.121,0:00:06.165
- [Voiceover] Consider the following game.

0:00:06.165,0:00:09.626
Eve instructs Bob to go into[br]a room. (door creaks shut)

0:00:09.626,0:00:12.838
Bob finds the room empty,[br]except for some locks,

0:00:12.838,0:00:16.508
an empty box, and a single deck of cards.

0:00:16.508,0:00:18.511
Eve tells Bob to select a card

0:00:18.511,0:00:22.800
from the deck and hide it as best he can.

0:00:22.800,0:00:24.891
The rules are simple.

0:00:24.891,0:00:27.060
Bob cannot leave the room with anything,

0:00:27.060,0:00:30.021
cards and keys all stay in the room,

0:00:30.021,0:00:34.735
and he can put, at most,[br]one card in the box.

0:00:34.735,0:00:38.363
Eve agrees that she has[br]never seen the locks.

0:00:38.363,0:00:42.784
He wins the game if Eve is[br]unable to determine his card.

0:00:42.784,0:00:45.120
So what is his best strategy?

0:00:45.120,0:00:48.123
Well, Bob selected a[br]card, six of diamonds,

0:00:48.123,0:00:50.834
and threw it in the box. (box clicks shut)

0:00:50.834,0:00:53.628
First he considered the[br]different types of locks.

0:00:53.628,0:00:58.133
Maybe he should lock the[br]card in the box with the key.

0:00:58.133,0:01:00.636
Though, she could pick locks, so he

0:01:00.636,0:01:03.180
considers the combination lock.

0:01:03.180,0:01:05.223
The key is on the back, so if he locks it

0:01:05.223,0:01:08.977
and scratches it off, it[br]seems like the best choice.

0:01:08.977,0:01:12.063
But suddenly he realizes the problem.

0:01:12.063,0:01:13.815
The remaining cards on the table

0:01:13.815,0:01:15.984
leak information about his choice,

0:01:15.984,0:01:18.487
since it's now missing from the deck.

0:01:18.487,0:01:20.989
The locks are a decoy. (metal jangles)

0:01:20.989,0:01:23.992
He shouldn't separate[br]his card from the deck.

0:01:23.992,0:01:25.494
He returns his card to the deck

0:01:25.494,0:01:28.123
but can't remember the[br]position of his card.

0:01:28.123,0:01:31.998
So he shuffles the deck to randomize it.

0:01:32.244,0:01:34.711
Shuffling is the best[br]lock, because it leaves

0:01:34.711,0:01:37.631
no information about his choice.

0:01:37.631,0:01:42.631
His card is now equally likely[br]to be any card in the deck.

0:01:42.678,0:01:47.402
He can now leave the cards[br]openly, in confidence.

0:01:48.183,0:01:51.061
Bob wins the game, because[br]the best Eve can do

0:01:51.061,0:01:53.731
is simply guess, as he has left

0:01:53.731,0:01:56.942
no information about his choice.

0:01:56.942,0:01:58.998
Most importantly, even if we give Eve

0:01:58.998,0:02:01.405
unlimited computational power,

0:02:01.405,0:02:04.200
she can't do any better than a guess.

0:02:04.200,0:02:08.502
This defines what we[br]call "perfect secrecy."

0:02:08.662,0:02:13.500
On September first, 1945,[br]29-year-old Claude Shannon

0:02:13.500,0:02:17.504
published a classified paper on this idea.

0:02:17.504,0:02:20.215
Shannon gave the first mathematical proof

0:02:20.215,0:02:24.719
for how and why the one time[br]pad is perfectly secret.

0:02:24.719,0:02:27.430
Shannon thinks about encryption schemes

0:02:27.430,0:02:29.850
in the following way.

0:02:29.850,0:02:33.104
Imagine Alice writes a message[br]to Bob, 20 letters long.

0:02:33.104,0:02:34.021
(paper ruffling)

0:02:34.021,0:02:35.522
This is equivalent to picking

0:02:35.522,0:02:40.110
one specific page from the message space.

0:02:40.110,0:02:42.863
The message space can be[br]thought of as a complete

0:02:42.863,0:02:47.117
collection of all possible[br]20 letter messages.

0:02:47.117,0:02:47.826
(paper ruffling)

0:02:47.826,0:02:49.119
Anything you can think of that's

0:02:49.119,0:02:52.497
20 letters long is a page in this stack.

0:02:52.497,0:02:55.792
Next, Alice applies a[br]shared key, which is a list

0:02:55.792,0:03:00.380
of 20 randomly generated[br]shifts between one and 26.

0:03:00.380,0:03:02.675
The key space is the complete collection

0:03:02.675,0:03:06.511
of all possible outcomes,[br]so generating a key is

0:03:06.511,0:03:10.765
equivalent to selecting a page[br]from this stack at random.

0:03:10.765,0:03:13.810
When she applies the shift[br]to encrypt the message,

0:03:13.810,0:03:16.479
she ends up with a cipher text.

0:03:16.479,0:03:18.607
The cipher text space represents

0:03:18.607,0:03:22.697
all possible results of an encryption.

0:03:22.697,0:03:25.030
When she applies the key, it maps

0:03:25.030,0:03:28.617
to a unique page in this stack.

0:03:28.617,0:03:30.785
Notice that the size of the message space

0:03:30.785,0:03:32.537
equals the size of the key space

0:03:32.537,0:03:35.790
equals the size of the cipher text space.

0:03:35.790,0:03:38.501
This defines what we[br]call "perfect secrecy,"

0:03:38.501,0:03:42.506
for if someone has access to[br]a page of cipher text only,

0:03:42.506,0:03:44.883
the only thing that they know is that

0:03:44.883,0:03:48.387
every message is equally likely.

0:03:48.387,0:03:50.555
So no amount of computational power

0:03:50.555,0:03:54.017
could ever help improve a blind guess.

0:03:54.017,0:03:56.636
Now the big problem, you're[br]wondering, with the time pad,

0:03:56.645,0:04:00.231
is we have to share these[br]long keys in advance.

0:04:00.231,0:04:03.360
To solve this problem, we[br]need to relax our definition

0:04:03.360,0:04:07.656
of secrecy by developing a[br]definition of pseudo-randomness.

0:04:07.656,0:04:09.123
(white noise)