1
00:00:01,034 --> 00:00:02,378
(tranquil music)

2
00:00:04,121 --> 00:00:06,165
- [Voiceover] Consider the following game.

3
00:00:06,165 --> 00:00:09,626
Eve instructs Bob to go into
a room. (door creaks shut)

4
00:00:09,626 --> 00:00:12,838
Bob finds the room empty,
except for some locks,

5
00:00:12,838 --> 00:00:16,508
an empty box, and a single deck of cards.

6
00:00:16,508 --> 00:00:18,511
Eve tells Bob to select a card

7
00:00:18,511 --> 00:00:22,800
from the deck and hide it as best he can.

8
00:00:22,800 --> 00:00:24,891
The rules are simple.

9
00:00:24,891 --> 00:00:27,060
Bob cannot leave the room with anything,

10
00:00:27,060 --> 00:00:30,021
cards and keys all stay in the room,

11
00:00:30,021 --> 00:00:34,735
and he can put, at most,
one card in the box.

12
00:00:34,735 --> 00:00:38,363
Eve agrees that she has
never seen the locks.

13
00:00:38,363 --> 00:00:42,784
He wins the game if Eve is
unable to determine his card.

14
00:00:42,784 --> 00:00:45,120
So what is his best strategy?

15
00:00:45,120 --> 00:00:48,123
Well, Bob selected a
card, six of diamonds,

16
00:00:48,123 --> 00:00:50,834
and threw it in the box. (box clicks shut)

17
00:00:50,834 --> 00:00:53,628
First he considered the
different types of locks.

18
00:00:53,628 --> 00:00:58,133
Maybe he should lock the
card in the box with the key.

19
00:00:58,133 --> 00:01:00,636
Though, she could pick locks, so he

20
00:01:00,636 --> 00:01:03,180
considers the combination lock.

21
00:01:03,180 --> 00:01:05,223
The key is on the back, so if he locks it

22
00:01:05,223 --> 00:01:08,977
and scratches it off, it
seems like the best choice.

23
00:01:08,977 --> 00:01:12,063
But suddenly he realizes the problem.

24
00:01:12,063 --> 00:01:13,815
The remaining cards on the table

25
00:01:13,815 --> 00:01:15,984
leak information about his choice,

26
00:01:15,984 --> 00:01:18,487
since it's now missing from the deck.

27
00:01:18,487 --> 00:01:20,989
The locks are a decoy. (metal jangles)

28
00:01:20,989 --> 00:01:23,992
He shouldn't separate
his card from the deck.

29
00:01:23,992 --> 00:01:25,494
He returns his card to the deck

30
00:01:25,494 --> 00:01:28,123
but can't remember the
position of his card.

31
00:01:28,123 --> 00:01:31,998
So he shuffles the deck to randomize it.

32
00:01:32,244 --> 00:01:34,711
Shuffling is the best
lock, because it leaves

33
00:01:34,711 --> 00:01:37,631
no information about his choice.

34
00:01:37,631 --> 00:01:42,631
His card is now equally likely
to be any card in the deck.

35
00:01:42,678 --> 00:01:47,402
He can now leave the cards
openly, in confidence.

36
00:01:48,183 --> 00:01:51,061
Bob wins the game, because
the best Eve can do

37
00:01:51,061 --> 00:01:53,731
is simply guess, as he has left

38
00:01:53,731 --> 00:01:56,942
no information about his choice.

39
00:01:56,942 --> 00:01:58,998
Most importantly, even if we give Eve

40
00:01:58,998 --> 00:02:01,405
unlimited computational power,

41
00:02:01,405 --> 00:02:04,200
she can't do any better than a guess.

42
00:02:04,200 --> 00:02:08,502
This defines what we
call "perfect secrecy."

43
00:02:08,662 --> 00:02:13,500
On September first, 1945,
29-year-old Claude Shannon

44
00:02:13,500 --> 00:02:17,504
published a classified paper on this idea.

45
00:02:17,504 --> 00:02:20,215
Shannon gave the first mathematical proof

46
00:02:20,215 --> 00:02:24,719
for how and why the one time
pad is perfectly secret.

47
00:02:24,719 --> 00:02:27,430
Shannon thinks about encryption schemes

48
00:02:27,430 --> 00:02:29,850
in the following way.

49
00:02:29,850 --> 00:02:33,104
Imagine Alice writes a message
to Bob, 20 letters long.

50
00:02:33,104 --> 00:02:34,021
(paper ruffling)

51
00:02:34,021 --> 00:02:35,522
This is equivalent to picking

52
00:02:35,522 --> 00:02:40,110
one specific page from the message space.

53
00:02:40,110 --> 00:02:42,863
The message space can be
thought of as a complete

54
00:02:42,863 --> 00:02:47,117
collection of all possible
20 letter messages.

55
00:02:47,117 --> 00:02:47,826
(paper ruffling)

56
00:02:47,826 --> 00:02:49,119
Anything you can think of that's

57
00:02:49,119 --> 00:02:52,497
20 letters long is a page in this stack.

58
00:02:52,497 --> 00:02:55,792
Next, Alice applies a
shared key, which is a list

59
00:02:55,792 --> 00:03:00,380
of 20 randomly generated
shifts between one and 26.

60
00:03:00,380 --> 00:03:02,675
The key space is the complete collection

61
00:03:02,675 --> 00:03:06,511
of all possible outcomes,
so generating a key is

62
00:03:06,511 --> 00:03:10,765
equivalent to selecting a page
from this stack at random.

63
00:03:10,765 --> 00:03:13,810
When she applies the shift
to encrypt the message,

64
00:03:13,810 --> 00:03:16,479
she ends up with a cipher text.

65
00:03:16,479 --> 00:03:18,607
The cipher text space represents

66
00:03:18,607 --> 00:03:22,697
all possible results of an encryption.

67
00:03:22,697 --> 00:03:25,030
When she applies the key, it maps

68
00:03:25,030 --> 00:03:28,617
to a unique page in this stack.

69
00:03:28,617 --> 00:03:30,785
Notice that the size of the message space

70
00:03:30,785 --> 00:03:32,537
equals the size of the key space

71
00:03:32,537 --> 00:03:35,790
equals the size of the cipher text space.

72
00:03:35,790 --> 00:03:38,501
This defines what we
call "perfect secrecy,"

73
00:03:38,501 --> 00:03:42,506
for if someone has access to
a page of cipher text only,

74
00:03:42,506 --> 00:03:44,883
the only thing that they know is that

75
00:03:44,883 --> 00:03:48,387
every message is equally likely.

76
00:03:48,387 --> 00:03:50,555
So no amount of computational power

77
00:03:50,555 --> 00:03:54,017
could ever help improve a blind guess.

78
00:03:54,017 --> 00:03:56,636
Now the big problem, you're
wondering, with the time pad,

79
00:03:56,645 --> 00:04:00,231
is we have to share these
long keys in advance.

80
00:04:00,231 --> 00:04:03,360
To solve this problem, we
need to relax our definition

81
00:04:03,360 --> 00:04:07,656
of secrecy by developing a
definition of pseudo-randomness.

82
00:04:07,656 --> 00:04:09,123
(white noise)