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 : Kerckhoff 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

III. 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

IV. 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

V. 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