Turing Award Winner: NSA, Public Key Cryptography, Crypto Wars | Martin Hellman

28:56One is the privacy half of public key cryptography and the other is something much more mundane. And I have the professor's handwriting in blue scanned. I've scanned this across the top that idea number two, the mundane idea looks much better than idea number one, maybe because his description of idea number one is so muddled. But Ralph had major problems. So he drops the course. The professor says, see me today about this. Ralph, instead of seeing the professor drops the course and goes and does it on his own. He then submits a paper to the CACM, the communications of the ACM, the primary journal of the ACM, and it's rejected.

29:40I have the rejection letter. Susan Graham, who was the editor who rejected it based on a referee's report, writes, it bothers her that there are no references in the paper. Has no one thought of doing anything like this before? The answer is no. Now, he still should have had references. Ralph didn't know how to write a paper at that point. I helped him rewrite the paper and it was later accepted, but it was actually submitted before, a little before ours. So Witt and I came up with public key cryptography. Ralph came up with public key distribution. We eventually learned about one another afterward.

30:16And I bring him here in the summer of 76. and I talked to Ralph and I say, have you ever thought of coming to Stanford to do your PhD? And Ralph says, I can't afford it. I said, yes, you can. How much are you making at Berkeley as a TA? And I said, I pay you roughly the same as an RA here at Stanford and your tuition would be covered. So he came to Stanford, he did his PhD under my supervision, supposedly, although we really worked together. OpenAI, Anthropic, Cursor, and Vercel all use this product to make their lives better. And the problem it solves is when you're building SaaS or an AI product and you wanna sell to other companies, there's all these requirements you need to meet.

30:58There's SSO, there's SCIM, there's RBAC, there's audit logs. These are all things that take time to integrate, but aren't the main focus of your app. WorkOS is an API layer that lets you meet all of these requirements in just a few lines of code. So let's say you have a new SaaS product and you wanna sell to other companies, WorkOS will solve all of these critical feature gaps for you. You can check them out at workos.com to learn more and get started. And I appreciate them for supporting my work and sponsoring this podcast. It seems like this cryptography space was not so well resourced. I mean, Diffy is kind of going couch to couch to kind of support himself on this.

31:41ralph's also kind of doing this in his own um you know fully his own initiative and people aren't really supporting him throughout is that was that common in cryptography at that time yeah i told you all my all my colleagues and it's not an exaggeration told me i was crazy to work in cryptography and one of their reasons was nsa has a huge budget and decades multi-decade head start one of them jim omura who passed away about a year two years ago he was a professor at ucla way, I mentioned him to you earlier, Jim told me I was crazy. And the best ideas often seem crazy ahead of time. So I was at Tom Kailath 10 years ago, I was at Tom Kailath's 80th birthday celebration.

32:23He won the National Medal of Technology and Science, I think, given to him by President Obama for his work, keeping Moore's Law going for 10 years, according to the former Dean of Engineering at Stanford at the time. Jim Omora is standing six feet away. I motioned over, I said, Jim, tell this woman what you told me when I first started working in cryptography. And I just won the Turing Award, the top prize in computer science for that work. And Jim said, oh, I told Marty he was crazy. And I knew he would do that because he'd given me permission to quote him on this. And the best work often appears crazy a priori.

32:59GPS, which we use daily, Brad Parkinson, who won the top prize from the IEEE for that work, says that the Air Force thought GPS was crazy initially.

33:11High-speed internet access, I won't go into details there. And I've spoken to a number of Nobel laureates, and almost all of them had the same reaction from people that I did. One of them, I'll tell you one story, Lou Ingaro, who won the Nobel Prize in Physiology or Medicine, I think in 1998, told me that the dean of his medical school came to him and said, Lou, why are you doing this crazy stuff? We hired you because you do good work. Crazy stuff that won him a Nobel Prize. It makes sense. But I guess the unique aspect is I think a lot of people would receive that pushback and everyone thinks they're foolish and they wouldn't go for it.

33:57What is it that gave you the confidence to continue when everyone was saying this is foolish? two reasons one is i got beaten up as a christ killer as a kid that's and that's a little bit of a joke but not totally as a kid we moved to an irish catholic neighborhood i'm jewish we moved there when i was four and a half years old i went to my parents i said i want the pretty tree that the other kids have the christmas tree i want the presents under the tree i want to go to the same school as the other kids in the neighborhood saint nicholas of tallentine in parochial school, I was telling my parents I didn't want to be Jewish.

34:35And so in self-defense, I adopted the attitude of who would want to be like anybody else. That is a very simple answer, me. I would have given my eye teeth to have been like everybody else. But in time I came to believe my own bullshit. And so when my colleagues said I was crazy to work in cryptography, instead of scaring me off, it actually attracted me. so that's one reason and the other reason i think it runs in my family i have an uncle who in 1940 with his wife a jew took trains across the country with bicycles bicycling through national parks i mean who but a crazy person would do that i come from a crazy family we've done crazy things.

35:21And this was a crazy thing to do. When you put out that paper in 1976, what was the problem you were trying to solve? Or what was guiding your research direction at that time? Well, it started as trying to develop a theory of cryptography. And Jim Massey, who was the editor at the time of the IEEE Transactions on Information Theory, of which I was on the Board of Governors, as I mentioned. Jim said, invited me to write a paper on that. I mean, this was beginning to get some traction. And I asked if Witt could be included. And he said, absolutely. And so Witt and I were working on this paper. We had several drafts.

36:04And then in May 76, I come up with now Diffie-Hellman Key Exchange. And I include that, I throw that into a paper I'm giving in June 76, a month later at the IEEE symposium on information theory in Ranaby, Sweden. Jim Massey's there, of course. And he says, you get that into the paper, I'll have it out in the November issue, which he did. Now, the November issue, Witt is fond of pointing out, did not come out until February 1977, was usually late, but that's how it worked. And Ralph, unfortunately, as I said, had his idea rejected, his paper rejected. And so his paper did not appear until 1978, even though it was submitted slightly before ours.

36:47I see. I think in this conversation, you mentioned key exchange, also signatures. It seems like there's these components of a full cryptographic system. Could you explain each of these? Key exchange is how do you and your bank exchange a key to protect your banking transactions, to use a modern example? with somebody listening in on the internet. And so you use public key cryptography to do that. Ralph had a puzzle method. Ralph Merkel had a puzzle method where he generated a sequence of puzzles and you solved, your bank would solve one of them and it would then use that key and you could quickly tell which key it was using.

37:33But somebody else had to solve half the puzzles on average before it could do it. And so it took a lot more effort on the part of an opponent. I'll explain Diffie-Hellman key exchange very briefly. And that is only key exchange. It's not yet signatures. You and I want to exchange physical messages. I want to write them out to you and pass them to you. But my wife, who is not supposed to see them, is sitting between us and has to hand them to you. So what do I do? I put my message in a strong box. I put a lock on that strong box. I'd like to tell you the combination to that lock but if I tell you how to open it I'm also telling my wife how to open it so I don't tell anybody how to open it I pass it to my wife she can't open it, she passes it to you you can't open it you put a second lock on the strong box you then pass you don't tell me the combination you don't tell Dorothy the combination only you know the combination you pass it to Dorothy, she can't take either lock off she passes it to me, what can I do?

38:39take off my lock, leaving only your lock. I pass it back to Dorothy. She can't take off your lock, but when you get it, you can. You get the message inside. That's basically how Diffie-Hellman or Diffie-Hellman-Merkel key exchange works. Now, what's critical about this is that I made the strong box big enough for you to put a second lock on it. If I hadn't done that, if I'd only made it big enough for one lock, you could have taken the strong box that you got and put it in a bigger strong box. But now there's a problem. When I get it, I can't get inside to take my lock off. It has to be what's called commutative.

39:16And everybody knows what commutative means, although they may have forgotten it. Addition is commutative. Three plus five is the same as five plus three. It doesn't matter which order you do the operations in. You get eight. Three, five minus three is two. Three minus five is minus two. You get a different answer. It's not commutative. Subtraction is not commutative. And what I had to do was find a commutative one-way function, although I didn't know that at the time. And the function I used is a commutative one-way function. It's exponentiation and module arithmetic. It doesn't matter whether you first raise alpha to the x1 power and then to the x2 power or raise it to the x2 power and then to the x1 power, you get the same result.

39:59You get alpha to the x1, x2. Multiplication in the exponent is commutative. And we did this over a finite field where exponentiation is not a smooth function, which would be easy to invert. It jumps all over the place. But it turns out it still works that way. So that is public key exchange, public key distribution. Digital signatures are more complicated. That's something that Witt came up with. It's called a public key crypto system. and then RSA, Raveshmeir and Adelman came up with the first instance of that. There you have a public key and a secret key and it doesn't matter which order you operate on them, whether you first use the public key and then the secret key or the secret key and then the public key, you get the initial result.

40:45They undo one another. There, if I use my secret key, I can sign a message because there's no privacy, but I send the encrypted message to you using my secret key. You use my public key, which you get from a public file, to verify it. That's how my phone works. It's got a public key built into it. Apple knows the secret key. Apple can sign software updates. People can take my phone apart and get the public key, but that doesn't give them the secret key that allows them to sign software updates. I see. So in that case, Apple is signing their updates to your phone. Right. So I also was reading about symmetric versus asymmetric.

41:29And what you're describing sounds like asymmetric. Yes. Asymmetric cryptography uses a public key and a secret key. It's asymmetric. Conventional cryptography uses the same secret key to encrypt and decrypt. And that requires a courier, which is what was required before public key cryptography. If you were a general in another division, I could send you a key. I would send a messenger with a key locked to his wrist. And when you got it, you could open it up and get the key. And then you and I could use a radio channel to communicate very cheaply and very fast. But you can't use couriers to communicate keys between a bank and a client.

42:11Yeah, so I saw modern systems. It's almost like multiple different mechanisms where there's this asymmetric key exchange at the beginning to establish the connection. and then that gets you that key symmetric thing. Exactly. It's just like I described for Apple signing the software update. They don't sign the whole thing. They only sign a hash. In the same way, we could use a public key crypto system like RSA to exchange messages, but it's too slow. So what I do is I send you one message, use the following key in AES, the advanced encryption standard, and then we use AES very quickly to exchange messages.

42:50And that's the difference between asymmetric encryption, which we use at first, where I use the public key to incypher the message and use the secret key to get the key. And then we use a symmetric system to very quickly communicate afterward. I was reading about RSA versus the Diffie-Hellman key exchange, and it seems like there was a lot of patents or something like that, patent wars. What's the context behind that? I didn't know how patents worked when we wrote the first patent on public key cryptography. If I'd known, we could have covered RSA. We would have made a lot of money. Basically, RSA sold their company for$250 million.

43:33We made nothing, virtually nothing from our patents in cryptography. There was a patent fight between RSA and us, MIT and Stanford, or between their licensees. And basically, MIT won that fight.

43:54And I was pissed at RSA for a long time. And I was pissed with Jim Bidzos, the president of RSA Data Security. And around 1990, around 2000, sometime around there, I realized it was inconsistent with my approach to life to be pissed at RSA. They'd won. The fight was over. And so I approached Jim Bidzos and I said, look, Jim, I told him that. And I said, let's be friends. Let's bury the hatchet. And we essentially have. And friends are better than enemies. I'm not sure, but I think Ron Revest might have actually nominated Whitney for the Turing Award. Now, he wouldn't have done that if he didn't think we deserve it, but he wouldn't do it if he was pissed at us.

44:38And friends are better than enemies. And that's not why I did it. That's not why I became friends with them. But again, it worked out very well. How did they win the patent war if your ideas came first? I remember I told you I didn't know how patents worked. It's only the claims that matter. And so if I'd known that, we could have written a claim that would have covered RSA easily, but we didn't. And so the patent was written very badly. Stanford didn't want to invest a lot of money in this patent, so it had a law school intern write the patent instead of a patent attorney. We made a lot of mistakes.

45:23You mentioned friends are better than enemies. I think, yeah, a lot of people would agree with you. But I also think most people wouldn't be able to get over losing a$250 million outcome. How did you kind of get over that and kind of establish friendship? Well, some of it is in my genes, but some of it, a lot of it comes from my wife. Basically, my wife and I have been married 59 years last March. and we were madly in love when we met. We followed society's rules and we developed a toxic relationship 10 years later. My wife was ready to leave me, but I didn't know it because I had blinders on the way many husbands do.

46:08And fortunately, when she met me, she decided I was the one. And 10, 15 years after we're married, roughly 50 years ago, she says, he's still the one, although life with him is impossible and life with her was no picnic. So she went around looking for catalysts, ways to improve our relationship. And she eventually found a group, I won't go into all the details there, I tend to do that, that worked on the international and the interpersonal at the same time. It was founded by Professor Harry Rathbun, who was a professor here at Stanford, born in the 1890s, so he's no longer alive. I knew him late in his life.

46:48And that's how I, it was based on the teachings of Jesus which was a problem for me as a Jew because it was okay not to go to synagogue which I didn't do but it was not okay to study the teachings of Jesus that was traitorous but eventually Dorothy dragged me to enough meetings that over a year's time I came to see that these people creative initiative as the group was called at the time knew something I had to learn if my marriage was going to survive. And I surprised myself by being willing to do things that seem crazy to me. The most important things were accepting ideas that Dorothy had that seemed crazy to me that weren't crazy.

47:31Because what happened when she had an idea that seemed crazy to me? I treat her like she was crazy. What did that do? It drove her crazy. What did that do? It convinced me I was right that she was crazy. Kept the whole cycle going. By the way, the same happens internationally. We treat countries in ways that they don't like. They react in ways that seem crazy to us. We treat them like they're crazy and it keeps the whole cycle going. So that's how I came. And so it's based on the gospels. And while I'm not a Christian, I see Jesus as a Jewish reformer rather than as a Christian Messiah. I view myself as a follower of Jesus.

48:08When I was researching the discovery that you had, it seems like all of a sudden, many of the similar discoveries were happening all at the same time. So, for instance, you mentioned... Ralph Merkle and us. Oh, and GCHQ claims that they invented it just a couple of years before us, but they only have half of it, if they're right, which is the privacy part. They didn't have anything on digital signatures, but they claim everything. Right. And then there's also the MIT folks. The MIT folks. Yeah. So I have a theory about that. I'm going to tell it as a joke, but it is more to this joke than I think is just a joke.

48:48There's a muse that whispers in our ears. There's a muse of poetry. There's a muse of calculus who whispered in Newton's ear and Leibniz's ear about the same time. There's a muse that whispered in Ralph's ear about the same time that she whispered in our ears. most people don't pay attention to this muse because she sounds crazy a few people do and so that's why I think there's something in the air I mean it's not necessarily a muse this but there's something in the air that comes to people but why you know why didn't it come 50 years earlier or what like how come it seemed like they all came very similar I noticed I interviewed Barbara Liskow as well, who did a lot in like data abstraction and modularity.

49:38And there also, it was like on the West Coast and the East Coast without even communicating, they had the same discovery, very similar. I think my joke might actually have something to say about that. But also there's something that goes on technologically. We didn't have the computing power to do public key cryptography. If someone had come up with it 50 years before, it would have been a nice idea that couldn't be implemented. So there's like a logistical part to this, which is just the tools weren't there. And once they were there, it kind of inspired the right thinking. Yeah, but calculus, I mean, why that occurred to Leibniz and Newton about the same time.

50:15Oh, and Darwin and someone else thought of evolution about the same time. So I don't know. It is mystical. And maybe we should treat it as that. Even though I'm a scientist, I believe in the mystical side of life. There's a cryptography work that you're doing. And then I think later in your career, I saw this rethinking national security. And I was curious how you got into this, I guess, area, this body of work. And, you know, what's the problem you're trying to solve? Well, the problem we're trying to solve is simple. We're going to kill ourselves. uh i mean right now i estimate that a child born today uh has probably worse than even odds of living out his or her natural life as a result of nuclear weapons all by themselves without climate change without ai without any of this other stuff what are you talking about with this ai threat well there's debate on that uh jeffrey hinton uh yashua bengio uh think that who won the the Turing Award for their work in artificial intelligence think that AI may actually kill human beings off, something like that.

51:24I mean, because it'll say, why do I need these stupid people? Whereas Ed Feigenbaum and Raj Reddy, who won the Turing Award 30 years ago for their work in artificial intelligence, have both told me and given me permission to quote them, so I'm not giving any secrets away, that calling AI an existential threat is ridiculous. It's science fiction. I don't know who's right, but I do know we need to build a more cooperative world for a number of other reasons, even if not that one. So why not solve that one at the same time? We're likely to build AI into our nuclear command and control system. I mean, God, what a mess.

52:02So right now, I'm working on a bill. It's H.R. 3564. And we have 25, on paper, 24 co-sponsors. The bill is so bad it's passable, but so good that it's a game changer. Why is it so bad that it's passable? It has an exception for launch on warning. If our warning systems show a bunch of ICBMs coming our way, the president doesn't need a second opinion to launch our nuclear weapons. He can do so all on his own. There have been mistakes in our warning system, so I don't like that. But that's why it's so bad it's passable. This makes it easy for people to get on board. Most people don't realize that the president can launch a nuclear war all on his own right now.

52:48A president could be awakened at 3 a.m. in the morning during a crisis, too drunk to legally drive a car, asked what to do. He might say drunkenly, ah, nuke him. And right now, theoretically, the military is supposed to do that. I didn't consider that AI could be coupled with the nuclear bombs, too. I guess AI could. Oh, it's likely to be. I mean, we have this problem that we have just minutes of decision time. Do you not think we're going to use computers to help us there? Looking back on your career, I mean, being at Stanford during the growth of computing, I imagine you had a lot of opportunities to work with other famous folks in the industry.

53:30For instance, Don Knuth. Don Knuth is a good friend. Don Knuth doesn't use email. I mean, I think he does, but I have, whenever I want to reach him, I have to call his home and talk to his wife, Jill. That's the other, the other stories that I have. John McCarthy at artificial intelligence up the hill where Whit, Whit, Whit stayed there, by the way, when we came, when we were working on public key cryptography, because, um, uh, John was away and Whit and Mary were taking care of his daughter, driving her to her, uh, writing lessons. And so Whit just walked down the hill to talk to me. But John McCarthy, there's a meeting at the faculty club maybe 45 years ago.

54:12And Bob Floyd, who many of your people will know, who's a famous, he died, but a famous computer scientist here at Stanford. John McCarthy comes in, Bob Floyd's in the meeting. He goes over to Bob Floyd. I say, hi, John. He doesn't pay any attention to me because everybody knows that IO is a waste of time. And so he's not going to waste time on IO. So he has a very rapid exchange with Bob Floyd and he leaves. Well, I'll tell you another thing. I'm finishing my, it's 1968. I've just, several months early in 68, I thought, who am I to think I can make an original contribution to knowledge, which is the definition of a PhD thesis.

54:56I'm thinking of dropping out of the program. Over spring break, I basically solved my thesis. It's that quick. And so I go to Tom Culver, who's since died, my advisor, and very famous information theorist. And I go to Tom and I say, I just have barely enough units, but I have enough units to meet the course requirements for the PhD, but I don't have enough units to meet the PhD requirements. I'm going to have to take units of research. If I work at IBM Research, would you give me credit for my units of research? Because my wife was pregnant with our first child then. We'd been married roughly a year, year and a half.

55:39And so I'm being concerned about money. And he says, sure. And so I go to IBM Research, Yorktown Heights. Oh, Tom wants to have me come teach at Stanford, which I've done. but he says you really should leave for a couple of years because Stanford, I sometimes joke that I had to leave for several years to lose the taint of the Stanford PhD. Why is that? Stanford was worried about inbreeding. If they hired me, I was just going to be doing research like Tom Cover and they don't need two of them. They need somebody different. And so I went away to IBM for a year because my thesis broke very suddenly.

56:18And I then taught at MIT for two years before coming back on the faculty in 71. And this seemed like just a stupid hoop I had to jump through. But it actually turned out to be very important because when I was at IBM, Horst Feistel, who many people's name may recognize, he was really the father of IBM's research in cryptography. He was hired in 68. He was in the same department as me. I didn't work in cryptography, but I had lunch with Horst, and he told me some of the amazing things that got me started. And then when I'm at MIT, Peter Elias, whose name many people today will not recognize, but he was one of the original contributors to information theory.

57:00Peter gives me a paper by Claude Shannon, whose name your audience probably will recognize, written in 1949, I'm sorry, published in 1949 in the bell system technical journal connecting information theory to cryptography which is when i realized that oh i've already done a phd in information theory maybe i can do something worthwhile in cryptography so that stupid hoop i had to jump through was actually very important because when i got back to stanford i started working in cryptography among other things i think at the beginning of the conversation you said something you know quickly that you said you had thoughts on death and I was curious like you know what are your thoughts on on on death and you know how does it impact you I got an email from somebody at the New York Times about a month ago saying that he's working my obituary and it made me macabre but he was wondering if I could read it over and if I have any comments uh and so the two things that I'm 80 years old so uh my older brother died just after he turned 80.

58:04My mother died at 70. My father lived to 98. I hope I'll have more years. But if I don't, that's okay. I've had a great ride. But the two things that concern me about dying are the people I'll leave behind who I think are dependent on me, but probably aren't, and the work I do. Because very few people are working on the nuclear issue, the growth of humanity as a whole to save itself, that we're headed for disaster. Very few people realize that. And very few people put it in terms of a process of change. We can't stay where we are. We're going to kill ourselves. We're going to die. We can't jump to where we need to go.

58:43The world is too dangerous. But we can get there via a process of change. I'll tell you one other thing. Humanity is going to die. I've come to this real, I mean, it's clear. I mean, we might last a million years, but at some point, it might last a billion years, but at some point the sun's going to burn out. Maybe we'll move to other galaxies and we'll find ways to cheat death for a while. But eventually humanity is likely to die. But if humanity were to die now, it would be infant mortality. It would be really sad. If we've lived a full life, that's something else. Like if I had died when I was a child, people would say, oh, what have we missed?

59:24If I die at 80, people will say, some people will be saddened by it, but they'll feel like I've lived a full life. We need to save humanity from an infant death. We've only been around about 100 ,000 years. With all the experience that you have now, if you could go back to when you had just graduated college and give yourself some advice, what would you say? If when I was just graduating college and I was interested in saving the world, which I was not, I might have gone up to the top of a mountain to a guru and asked him what to do. Imagine what you'd say. You'd expect him to tell you work for the UN or something like that.

1:00:03Imagine what you'd say if he told you, if he told me, forget about saving the world, which was not a problem because I didn't think about saving the world. Go out and become as famous as you can, make as much money as you can. Come back in 10 years and I'll tell you what to do. That would have seemed like a detour. But it was actually the shortest distance between two points. Because 10 years later, when I was 30, 35 years old, and I was interested in saving the world, I had a reputation, I had money, and I had to screw up to get where I am. I had to not be concerned with the world to become concerned with the world, to be able to do what I can do about it.

1:00:41Awesome. Well, thank you so much for your time today. I really appreciate it. You're welcome, and thank you. Hey, thank you for watching this podcast. If you liked it and you want to see the show grow, please support with a comment or a like. Also, if you have any recommendations for people you want me to bring on, please drop a comment. Guests like Barbara Liskov, Mike Stonebreaker, Mark Brooker, these were all people that I brought on because someone left a comment. On another note, aside from the podcast, I'm working on building the ergonomic keyboard that I wish existed. Here's a glance at the prototype.

1:01:13It's a split keyboard. So there's two sides. this is in the case but yeah we launched on kickstarter and we hit our goal within eight hours of launching i really appreciate it if you were one of the people who grabbed one of the early units we're now working on the long journey of building the tooling now and so if you still want to pick one up i've left the late pledges open on kickstarter so you can grab one there i'll put a link in the description thank you again for watching the podcast and i'll see you in the next episode