Boaz Barak | Cryptography: The Art of Mathematical Secrecy

Boaz Barak is a professor of computer science at Harvard University, having previously been a principal researcher at Microsoft Research and a professor at Princeton University. His research interests span many areas of theoretical computer science including cryptography, computational complexity, and the foundations of machine learning. Boaz serves on the scientific advisory boards for Quanta Magazine and the Simons Institute for the Theory of Computing and he was selected for Foreign Policy magazine’s list of 100 leading global thinkers for 2014. www.patreon.com/timothynguyen Cryptography is about maintaining the privacy and security of communication. In this episode, Boaz and I go through the fundamentals of cryptography from a foundational mathematical perspective. We start with some historical examples of attempts at encrypting messages and how they failed. After some guesses as to how one might mathematically define security, we arrive at the one due to Shannon. The resulting definition of perfect secrecy turns out to be too rigid, which leads us to the notion of computational secrecy that forms the foundation of modern cryptographic systems. We then show how the existence of pseudorandom generators (which remains a conjecture) ensures that such computational secrecy is achievable, assuming P does not equal NP. Having covered private key cryptography in detail, we then give a brief overview of public key cryptography. We end with a brief discussion of Bitcoin, machine learning, deepfakes, and potential doomsday scenarios. I. Introduction 00:17 : Biography: Academia vs Industry 10:07 : Military service 12:53 : Technical overview 17:01 : Whiteboard outline II. Warmup 24:42 : Substitution ciphers 27:33 : Viginere cipher 29:35 : Babbage and Kasiski 31:25 : Enigma and WW2 33:10 : Alan Turing III. Private Key Cryptography: Perfect Secrecy 34:32 : Valid encryption scheme 40:14 : Kerckhoffs's Principle 42:41 : Cryptography = steelman your adversary 44:40 : Attempt #1 at perfect secrecy 49:58 : Attempt #2 at perfect secrecy 56:02 : Definition of perfect secrecy (Shannon) 1:05:56 : Enigma was not perfectly secure 1:08:51 : Analogy with differential privacy 1:11:10 : Example: One-time pad (OTP) 1:20:07 : Drawbacks of OTP and Soviet KGB misuse 1:21:43 : Important: Keys cannot be reused! 1:27:48 : Shannon's Impossibility Theorem IV. Computational Secrecy 1:32:52 : Relax perfect secrecy to computational secrecy 1:41:04 : What computational secrecy buys (if P is not NP) 1:44:35 : Pseudorandom generators (PRGs) 1:47:03 : PRG definition 1:52:30 : PRGs and P vs NP 1:55:47: PRGs enable modifying OTP for computational secrecy V. Public Key Cryptography 2:00:32 : Limitations of private key cryptography 2:09:25 : Overview of public key methods 2:13:28 : Post quantum cryptography VI. Applications 2:14:39 : Bitcoin 2:18:21 : Digital signatures (authentication) 2:23:56 : Machine learning and deepfakes 2:30:31 : A conceivable doomsday scenario: P = NP Further reading: Boaz Barak. An Intensive Introduction to Cryptography Twitter: @iamtimnguyen Webpage: http://www.timothynguyen.org