YouTube

Got a YouTube account?

Νέο: ενεργοποιείστε μεταφράσεις και λεζάντες που δημιουργήθηκαν από θεατές στο κανάλι σας στο YouTube!

English υπότιτλους

← Claude Shannon's Perfect Secrecy

Πάρτε τον Κωδικό ενσωμάτωσης
12 Γλώσσες

Showing Revision 1 created 10/21/2014 by Amara Bot.

  1. (tranquil music)

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