If you're seeing this message, it means we're having trouble loading external resources on our website.

If you're behind a web filter, please make sure that the domains ***.kastatic.org** and ***.kasandbox.org** are unblocked.

Main content

Current time:0:00Total duration:4:13

consider the following game even structs 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 he can the rules are simple Bob cannot leave the room with anything cards and keys I'll 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 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 leaked information about his choice since it's now missing from the deck the locks are a decoy shouldn't separate his card from the deck he returns his car to the deck but can't remember the position of his card so he shuffles the deck to randomize it shuffling is the best log 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 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 the 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 this stack at random when she applies the shifts to encrypt the message she ends up with a ciphertext the ciphertext 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 ciphertext space this defines what we call perfect secrecy for if someone has access to a page of ciphertext 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 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 [Applause]