About this video
Through a game where Bob must hide a card from Eve, the video shows that locks are a decoy: removing the card leaks information, but shuffling it back into the deck leaves Eve nothing better than a guess, even with unlimited computing power. This is perfect secrecy, which Claude Shannon proved for the one-time pad by showing the message space, key space and ciphertext space are all the same size. The catch is that long keys must be shared in advance.
You'll be able to
- explain why shuffling hides Bob's card better than locking it in a box.
- define perfect secrecy.
- describe the message space, key space and cipher text space and why their sizes matter.
- explain the main practical problem with the one-time pad.
Key words
- perfect secrecy
- When an attacker, even with unlimited computing power, can do no better than a blind guess.
- message space
- The collection of all possible messages of a given length.
- key space
- The collection of all possible keys, such as every list of 20 random shifts.
- cipher text space
- The collection of all possible results of an encryption.
- pseudo-randomness
- Something that looks random but is generated by a predictable process; introduced to relax perfect secrecy.
Transcript
(tranquil music) - [Voiceover] Consider the following game. Eve instructs Bob to go into a room. (door creaks shut) 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 he can.
The rules are simple. Bob cannot leave the room with anything, cards and keys all stay 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. (box clicks shut) First he considered the different types of locks. Maybe he should lock the card in the box with the key. Though, she could 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 realizes 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. (metal jangles) 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 has 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 first, 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 the following way. Imagine Alice writes a message to Bob, 20 letters long. (paper ruffling) 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.
(paper ruffling) 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 one and 26. The key space is the complete collection of all possible outcomes, so generating a key is equivalent to selecting a page from this stack at random.
When she applies the shift to encrypt the message, she ends up with a 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 time pad, is we have 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. (white noise)
Video © Khan Academy, used under CC BY-NC-SA. Watch on Khan Academy. Puzzicle is not affiliated with Khan Academy.