WEBVTT

00:00:01.034 --> 00:00:02.378
(tranquil music)

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

00:00:06.165 --> 00:00:09.626
Eve instructs Bob to go into
a room. (door creaks shut)

00:00:09.626 --> 00:00:12.838
Bob finds the room empty,
except for some locks,

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

00:00:16.508 --> 00:00:18.511
Eve tells Bob to select a card

00:00:18.511 --> 00:00:22.800
from the deck and hide it as best he can.

00:00:22.800 --> 00:00:24.891
The rules are simple.

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

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

00:00:30.021 --> 00:00:34.735
and he can put, at most,
one card in the box.

00:00:34.735 --> 00:00:38.363
Eve agrees that she has
never seen the locks.

00:00:38.363 --> 00:00:42.784
He wins the game if Eve is
unable to determine his card.

00:00:42.784 --> 00:00:45.120
So what is his best strategy?

00:00:45.120 --> 00:00:48.123
Well, Bob selected a
card, six of diamonds,

00:00:48.123 --> 00:00:50.834
and threw it in the box. (box clicks shut)

00:00:50.834 --> 00:00:53.628
First he considered the
different types of locks.

00:00:53.628 --> 00:00:58.133
Maybe he should lock the
card in the box with the key.

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

00:01:00.636 --> 00:01:03.180
considers the combination lock.

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

00:01:05.223 --> 00:01:08.977
and scratches it off, it
seems like the best choice.

00:01:08.977 --> 00:01:12.063
But suddenly he realizes the problem.

00:01:12.063 --> 00:01:13.815
The remaining cards on the table

00:01:13.815 --> 00:01:15.984
leak information about his choice,

00:01:15.984 --> 00:01:18.487
since it's now missing from the deck.

00:01:18.487 --> 00:01:20.989
The locks are a decoy. (metal jangles)

00:01:20.989 --> 00:01:23.992
He shouldn't separate
his card from the deck.

00:01:23.992 --> 00:01:25.494
He returns his card to the deck

00:01:25.494 --> 00:01:28.123
but can't remember the
position of his card.

00:01:28.123 --> 00:01:31.998
So he shuffles the deck to randomize it.

00:01:32.244 --> 00:01:34.711
Shuffling is the best
lock, because it leaves

00:01:34.711 --> 00:01:37.631
no information about his choice.

00:01:37.631 --> 00:01:42.631
His card is now equally likely
to be any card in the deck.

00:01:42.678 --> 00:01:47.402
He can now leave the cards
openly, in confidence.

00:01:48.183 --> 00:01:51.061
Bob wins the game, because
the best Eve can do

00:01:51.061 --> 00:01:53.731
is simply guess, as he has left

00:01:53.731 --> 00:01:56.942
no information about his choice.

00:01:56.942 --> 00:01:58.998
Most importantly, even if we give Eve

00:01:58.998 --> 00:02:01.405
unlimited computational power,

00:02:01.405 --> 00:02:04.200
she can't do any better than a guess.

00:02:04.200 --> 00:02:08.502
This defines what we
call "perfect secrecy."

00:02:08.662 --> 00:02:13.500
On September first, 1945,
29-year-old Claude Shannon

00:02:13.500 --> 00:02:17.504
published a classified paper on this idea.

00:02:17.504 --> 00:02:20.215
Shannon gave the first mathematical proof

00:02:20.215 --> 00:02:24.719
for how and why the one time
pad is perfectly secret.

00:02:24.719 --> 00:02:27.430
Shannon thinks about encryption schemes

00:02:27.430 --> 00:02:29.850
in the following way.

00:02:29.850 --> 00:02:33.104
Imagine Alice writes a message
to Bob, 20 letters long.

00:02:33.104 --> 00:02:34.021
(paper ruffling)

00:02:34.021 --> 00:02:35.522
This is equivalent to picking

00:02:35.522 --> 00:02:40.110
one specific page from the message space.

00:02:40.110 --> 00:02:42.863
The message space can be
thought of as a complete

00:02:42.863 --> 00:02:47.117
collection of all possible
20 letter messages.

00:02:47.117 --> 00:02:47.826
(paper ruffling)

00:02:47.826 --> 00:02:49.119
Anything you can think of that's

00:02:49.119 --> 00:02:52.497
20 letters long is a page in this stack.

00:02:52.497 --> 00:02:55.792
Next, Alice applies a
shared key, which is a list

00:02:55.792 --> 00:03:00.380
of 20 randomly generated
shifts between one and 26.

00:03:00.380 --> 00:03:02.675
The key space is the complete collection

00:03:02.675 --> 00:03:06.511
of all possible outcomes,
so generating a key is

00:03:06.511 --> 00:03:10.765
equivalent to selecting a page
from this stack at random.

00:03:10.765 --> 00:03:13.810
When she applies the shift
to encrypt the message,

00:03:13.810 --> 00:03:16.479
she ends up with a cipher text.

00:03:16.479 --> 00:03:18.607
The cipher text space represents

00:03:18.607 --> 00:03:22.697
all possible results of an encryption.

00:03:22.697 --> 00:03:25.030
When she applies the key, it maps

00:03:25.030 --> 00:03:28.617
to a unique page in this stack.

00:03:28.617 --> 00:03:30.785
Notice that the size of the message space

00:03:30.785 --> 00:03:32.537
equals the size of the key space

00:03:32.537 --> 00:03:35.790
equals the size of the cipher text space.

00:03:35.790 --> 00:03:38.501
This defines what we
call "perfect secrecy,"

00:03:38.501 --> 00:03:42.506
for if someone has access to
a page of cipher text only,

00:03:42.506 --> 00:03:44.883
the only thing that they know is that

00:03:44.883 --> 00:03:48.387
every message is equally likely.

00:03:48.387 --> 00:03:50.555
So no amount of computational power

00:03:50.555 --> 00:03:54.017
could ever help improve a blind guess.

00:03:54.017 --> 00:03:56.636
Now the big problem, you're
wondering, with the time pad,

00:03:56.645 --> 00:04:00.231
is we have to share these
long keys in advance.

00:04:00.231 --> 00:04:03.360
To solve this problem, we
need to relax our definition

00:04:03.360 --> 00:04:07.656
of secrecy by developing a
definition of pseudo-randomness.

00:04:07.656 --> 00:04:09.123
(white noise)