Gambling with Secrets: Part 6/8 (Perfect Secrecy & Pseudorandomness)

Channel:
Canada Art of the Problem
Subscribers:
175,000
Published on ● Video Link: https://www.youtube.com/watch?v=FfZurPKYM2w


Duration: 10:30
31,917 views
321

This chapter introduces why random shifts result in perfect secrecy. We explore hardware random number generators vs. pseudorandom number generators which expand a short random seed into a long sequences of "random looking" numbers. If used in cryptography, can offer "practical security" which is based on the secrecy of the random seed only. Alice and Bob can safely assume that the "enemy knows the system" (one-time pad + pseudorandom generator), and focus on assuring their seed is shared in secret & generated randomly.

If you are still wondering: how exactly would Eve break a ciphertext encrypted with a pseudorandom list of shifts? Remember: the pseudorandom generator can only produce a tiny (0.0000...1%) fraction of all possible shift sequences. Eve could program a computer to generate all possible sequences (starting from seed 0, 1, 2, 3.....) and reverse all of these shifts. When the computer hits a seed which decrypts the ciphertext into an "English looking" sentence, she can be 99.999% sure it is the message. All of the other seeds will decrypt into unreadable (jumbled looking) messages.



Other Videos By Art of the Problem


2012-09-26Algorithmic Efficiency (Prime Adventure part 3)
2012-09-26What is a computer? (Prime Adventure part 2)
2012-09-14What is Information Theory? (Information Entropy)
2012-09-11Computational Number Theory (Prime Adventure part 1)
2012-07-30Public key cryptography - Diffie-Hellman Key Exchange (full version)
2012-07-30Public Key Cryptography: RSA Encryption Algorithm
2012-07-29Gambling with Secrets: 8/8 (RSA Encryption)
2012-07-25Information Theory - Teaser
2012-06-03Gambling with Secrets: Part 7/8 (Diffie-Hellman Key Exchange)
2012-05-07Random vs. Pseudorandom Number Generators
2012-05-04Gambling with Secrets: Part 6/8 (Perfect Secrecy & Pseudorandomness)
2012-04-24The Enigma Machine (how it worked & why it was cracked)
2012-04-17Claude Shannon's Perfect Secrecy
2012-03-12Gambling with Secrets: Part 5/8 (Encryption Machines)
2012-02-24Public Key Cryptography: Diffie-Hellman Key Exchange (short version)
2012-02-14Gambling with Secrets: Part 4/8 (Private Key Cryptography)
2012-01-13Gambling with Secrets: Part 3/8 (Probability Theory & Randomness)
2011-12-12Gambling with Secrets: Part 2/8 (Prime Factorization)
2011-12-12Gambling with Secrets: Part 1/8 (What is Cryptography?)
2011-10-23Art of the Problem.
2011-10-23How Machines Generate Random Numbers with Time


Tags:
pseudorandom number generator
pseudorandomness
deterministic
random walk
nondeterministic
perfect secrecy
john von neumann