Where do you expect the next breakthrough in computer science?
Where you least expect it. No one expected a breakthrough in cryptography. People thought it was crazy to even work in it. Breakthroughs are unexpected both in space and in time — “space” meaning “area of research”.
With the connections that I had, I probably could have invested in Google while it was still private if I had asked that question as a question, rather than disguising it as a statement of disbelief.
What field would you say is the modern ‘cryptography’?
If I told you what it is, I wouldn’t be right. It’s the one that sounds crazy to work in. I’ll give you an example that has to do with business, rather than research. The Google guys, Sergey and Larry, were graduate students in computer science at Stanford, and they came up with this great search algorithm. Faculty in EE and CS, like myself, were the first ones to use the Google search engine. A professor of computer science, Dan Boneh, who’s a brilliant cryptographer — and I were using the Google search engine before it’s a big business, when they had no business model for how to make money. Dan and I said to each other, ‘It’s a great search engine, but how are they ever going to make money from free search.’ Even though we like to look at things differently, we sometimes make the same mistakes that my colleagues did.
The other advice I’d give young researchers is when you ask a question like, ‘How are they ever going to make money from free search?’, treat it as a question, not a statement. How could they make money from free search? With the connections that I had, I probably could have invested in Google while it was still private if I had asked that question as a question, rather than disguising it as a statement of disbelief.
The same thing happened with public key cryptography. At first, people who worked in cryptography, when we only had a concept, people would look at it and say, ‘How can you do that? How can you have secrecy with a public key?’
There are two ways of doing public key cryptography and I’m going to tell you the simpler one. What’s called the Diffie-Hellman algorithm works somewhat this way. Let’s imagine we’re in a physical room instead of talking on the phone, and I want to send you a message in a strong box, but I can’t tell you the combination to it because everyone else would hear it— you’re at the other end of the room. I have to pass the strongbox through a whole bunch of people that would love to see what’s inside. So I write out my message, I lock it up in the strongbox with a lock to which only I know the combination, and I pass it through all those people to you. None of those intermediate people know my combination and can open the box. When you get the box, you can’t open it either, but I’ve made the hasp where the lock goes on big enough for two locks. When you get the box, you put a second combination lock on that only you know the combination to. You then pass that doubly-locked box back through all those people to me. They obviously can’t open it now, there are two locks on it. When I get it, what do you think I do? I take my combination lock off. What does that leave? Only your combination lock on the box. I pass it back, they still can’t open it because they don’t know your combination, but you do and you can open it. So, it does what seems impossible.
I’m sitting at the same desk where forty years ago, in May 1976, I came up with that algorithm. I was working here late one night just like now.
What’s critical in that analogy is that the hasp is big enough for two locks, which makes it commutative. It doesn’t matter what order you do the operations in. It didn’t matter which lock went on first and which came off first, it’s commutative. If I had made the hasp only big enough for one lock, when you got the locked up box, here’s what you might have tried; you might have had a bigger strong box and put my small strong box in the big strong box and then put your lock on the outer one. Now it’s doubly-locked but not on the same hasp. When you pass that back through all those people, I can’t get inside your locked box to get to mine. It’s not commutative. The locks have to come off in the reverse order that they went on, whereas with the hasp that is big enough for two locks, it’s commutative. The function that I came up with was a commutative function, and that was the key to whole thing. Incidentally, as you conduct this interview, I’m sitting at the same desk where forty years ago, in May 1976, I came up with that algorithm. I was working here late one night just like now.
One other piece of advice to young researchers, and this relates to the book Dorothie and I are writing. If you’re married or in a serious relationship, it’s really important not to have that go sour, because it usually takes a year out of a person’s research life when that happens. Pay some attention to the interpersonal things that we talk about. It will actually help your mathematical research as well.