Terence Tao explains public key cryptography

Northwestern University awarded Terence Tao the 2010 Nemmers Prize in Mathematics, and, as a result, he gave a public lecture here last week.  The material was similar to the content of a presentation he gave a couple years ago that is on Youtube.  I attended the lecture at Northwestern, not so much for the material per se, but because I wanted to see how he explained mathematical concepts to a general audience.  You can’t see the effect of his words in the Youtube video, because the camera is focused on him.  I wanted to understand his interaction with the other people in the room.

My favorite slide of the talk was one that showed a three-pass cryptography protocol.  Tao gently asked the audience how Alice might send Bob a treasure chest so the eavesdropper Eve could not get to the treasure inside, even though Alice and Bob don’t share a secret lock or key.  He didn’t wait for an answer, but it was clear a lot of people had no idea how to solve this problem.  So he explained: Alice locks the treasure chest $g$ with her lock $a$, creating what we could call $g^a$, a chest with Alice’s lock on it.  She then sends $g^a$ to Bob, who puts his own lock on it as well, creating $g^{ab}$.  He sends $g^{ab}$ to Alice, who removes her lock ($g^b$ now), and she sends $g^b$ to Bob.  Bob removes his lock, obtaining $g$, and can open the treasure chest.  During this entire process, Eve has only been able to see a chest with one or more locks on it.

This is a simple cryptographic protocol (formally, the Massey-Omura Cryptosystem), but it had a profound effect on the audience, more than any other single slide.  People started nodding, and it was clear that several people suddenly understood something that was brand new to them.  It’s definitely an explanatory technique I intend to use myself.

I’ll mention one other thing about Tao’s lecture.  He wanted to give the audience a sense of the difference between an ancient proof and a modern proof.  To do this, he proved that there are infinitely many primes.  (This was the only complete proof he presented — “complete” in the sense that he assumed the truth of the Fundamental Theorem of Arithmetic, and then proved by contradiction that finitely many primes would violate the Fundamental Theorem.)  Later in the talk, he gave an artistic sketch of a proof of the Prime Number Theorem, for example, by saying the von Mangoldt Function was like a sound wave that grew louder when it struck a prime.  He left the audience with the impression that modern proofs — even 100-year-old modern proofs — are more complicated, and use continuous phenomena, as opposed to the simpler, discrete proofs of the Ancient Greeks.