Return to Video

Claude Shannon's Perfect Secrecy

  • 0:01 - 0:02
    (tranquil music)
  • 0:04 - 0:06
    - [Voiceover] Consider the following game.
  • 0:06 - 0:10
    Eve instructs Bob to go into
    a room. (door creaks shut)
  • 0:10 - 0:13
    Bob finds the room empty,
    except for some locks,
  • 0:13 - 0:17
    an empty box, and a single deck of cards.
  • 0:17 - 0:19
    Eve tells Bob to select a card
  • 0:19 - 0:23
    from the deck and hide it as best he can.
  • 0:23 - 0:25
    The rules are simple.
  • 0:25 - 0:27
    Bob cannot leave the room with anything,
  • 0:27 - 0:30
    cards and keys all stay in the room,
  • 0:30 - 0:35
    and he can put, at most,
    one card in the box.
  • 0:35 - 0:38
    Eve agrees that she has
    never seen the locks.
  • 0:38 - 0:43
    He wins the game if Eve is
    unable to determine his card.
  • 0:43 - 0:45
    So what is his best strategy?
  • 0:45 - 0:48
    Well, Bob selected a
    card, six of diamonds,
  • 0:48 - 0:51
    and threw it in the box. (box clicks shut)
  • 0:51 - 0:54
    First he considered the
    different types of locks.
  • 0:54 - 0:58
    Maybe he should lock the
    card in the box with the key.
  • 0:58 - 1:01
    Though, she could pick locks, so he
  • 1:01 - 1:03
    considers the combination lock.
  • 1:03 - 1:05
    The key is on the back, so if he locks it
  • 1:05 - 1:09
    and scratches it off, it
    seems like the best choice.
  • 1:09 - 1:12
    But suddenly he realizes the problem.
  • 1:12 - 1:14
    The remaining cards on the table
  • 1:14 - 1:16
    leak information about his choice,
  • 1:16 - 1:18
    since it's now missing from the deck.
  • 1:18 - 1:21
    The locks are a decoy. (metal jangles)
  • 1:21 - 1:24
    He shouldn't separate
    his card from the deck.
  • 1:24 - 1:25
    He returns his card to the deck
  • 1:25 - 1:28
    but can't remember the
    position of his card.
  • 1:28 - 1:32
    So he shuffles the deck to randomize it.
  • 1:32 - 1:35
    Shuffling is the best
    lock, because it leaves
  • 1:35 - 1:38
    no information about his choice.
  • 1:38 - 1:43
    His card is now equally likely
    to be any card in the deck.
  • 1:43 - 1:47
    He can now leave the cards
    openly, in confidence.
  • 1:48 - 1:51
    Bob wins the game, because
    the best Eve can do
  • 1:51 - 1:54
    is simply guess, as he has left
  • 1:54 - 1:57
    no information about his choice.
  • 1:57 - 1:59
    Most importantly, even if we give Eve
  • 1:59 - 2:01
    unlimited computational power,
  • 2:01 - 2:04
    she can't do any better than a guess.
  • 2:04 - 2:09
    This defines what we
    call "perfect secrecy."
  • 2:09 - 2:14
    On September first, 1945,
    29-year-old Claude Shannon
  • 2:14 - 2:18
    published a classified paper on this idea.
  • 2:18 - 2:20
    Shannon gave the first mathematical proof
  • 2:20 - 2:25
    for how and why the one time
    pad is perfectly secret.
  • 2:25 - 2:27
    Shannon thinks about encryption schemes
  • 2:27 - 2:30
    in the following way.
  • 2:30 - 2:33
    Imagine Alice writes a message
    to Bob, 20 letters long.
  • 2:33 - 2:34
    (paper ruffling)
  • 2:34 - 2:36
    This is equivalent to picking
  • 2:36 - 2:40
    one specific page from the message space.
  • 2:40 - 2:43
    The message space can be
    thought of as a complete
  • 2:43 - 2:47
    collection of all possible
    20 letter messages.
  • 2:47 - 2:48
    (paper ruffling)
  • 2:48 - 2:49
    Anything you can think of that's
  • 2:49 - 2:52
    20 letters long is a page in this stack.
  • 2:52 - 2:56
    Next, Alice applies a
    shared key, which is a list
  • 2:56 - 3:00
    of 20 randomly generated
    shifts between one and 26.
  • 3:00 - 3:03
    The key space is the complete collection
  • 3:03 - 3:07
    of all possible outcomes,
    so generating a key is
  • 3:07 - 3:11
    equivalent to selecting a page
    from this stack at random.
  • 3:11 - 3:14
    When she applies the shift
    to encrypt the message,
  • 3:14 - 3:16
    she ends up with a cipher text.
  • 3:16 - 3:19
    The cipher text space represents
  • 3:19 - 3:23
    all possible results of an encryption.
  • 3:23 - 3:25
    When she applies the key, it maps
  • 3:25 - 3:29
    to a unique page in this stack.
  • 3:29 - 3:31
    Notice that the size of the message space
  • 3:31 - 3:33
    equals the size of the key space
  • 3:33 - 3:36
    equals the size of the cipher text space.
  • 3:36 - 3:39
    This defines what we
    call "perfect secrecy,"
  • 3:39 - 3:43
    for if someone has access to
    a page of cipher text only,
  • 3:43 - 3:45
    the only thing that they know is that
  • 3:45 - 3:48
    every message is equally likely.
  • 3:48 - 3:51
    So no amount of computational power
  • 3:51 - 3:54
    could ever help improve a blind guess.
  • 3:54 - 3:57
    Now the big problem, you're
    wondering, with the time pad,
  • 3:57 - 4:00
    is we have to share these
    long keys in advance.
  • 4:00 - 4:03
    To solve this problem, we
    need to relax our definition
  • 4:03 - 4:08
    of secrecy by developing a
    definition of pseudo-randomness.
  • 4:08 - 4:09
    (white noise)
Τίτλος:
Claude Shannon's Perfect Secrecy
Video Language:
English
Duration:
04:13

English subtitles

Αναθεωρήσεις