Boaz Barak | Cryptography: The Art of Mathematical Secrecy

The Cartesian Cafe

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