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

II. Warmup

• 24:42 : Substitution ciphers

III. Private Key Cryptography: Perfect Secrecy

• 34:32 : Valid encryption scheme

IV. Computational Secrecy

• 1:32:52 : Relax perfect secrecy to computational secrecy

V. Public Key Cryptography

• 2:00:32 : Limitations of private key cryptography

VI. Applications

• 2:14:39 : Bitcoin

Further reading: Boaz Barak. An Intensive Introduction to Cryptography

Twitter: @iamtimnguyen

Webpage: http://www.timothynguyen.org