Boaz Barak | Cryptography: The Art of Mathematical Secrecy | The Cartesian Cafe with Timothy Nguyen

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.
#computerscience #mathematics #machinelearning #crypto #security
Patreon: / 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:
www.timothynguyen.org
Apple Podcasts:
podcasts.apple.com/us/podcast...
Spotify:
open.spotify.com/show/1X5asAB...

[@eismscience]

I like the way you begin by asking for a personal take and overview. Very interesting and useful, Tim.

[@jimmyt_1988]

For goodness sake. {0, 1}^n is a set theory convention. I, did not know this. I was pretty confused for a good 10 mins before I had to confirm with GPT-4. Amazing talk as always! I'm at a pub in a harbour in UK, really enjoying scribbling on my notebook and understanding things mentioned here.

[@MisterDan]

What security is proven safe from future quantum computers and advanced AIs outside of OTP encryption?

[@TimothyNguyen]

OTP is perfectly secure and not much else (by the Shannon Impossibility Theorem we discuss). So you have to go with computational secrecy which leaves you “vulnerable” to brute force if you have enough force. Not sure if that answers your question.

[@portport]

​@@TimothyNguyen Once you have quantum computers, you can just use quantum encryption which is basically a physically secure OTP

[@chinisa.innukshopa]

Je suis indechiffrable?

[@jack4q2]

Translates OK ☑️