Oral-History:Martin Hellman

About Martin Hellman

Martin Hellman

Martin Hellman received his Ph.D. from Stanford University in 1969. From 1968-1969, he was at the IBM Thomas J. Watson Research Center. From 1969 to 1971, he was an Assistant Professor at MIT. He then became an Associate Professor of Electrical Engineering at Stanford University, doing research in cryptography and information theory.

The interview covers his research in these fields, focusing on projects supported by the National Science Foundation (NSF). He describes his initial move into cryptography from information theory – which he surmises had its origins in cryptography – and points out the opposition he faced from the National Security Agency. He describes the useful applications of his work, concentrating on public key encryption systems. He describes work in related fields such as computational complexity. He also describes the guidance provided by the NSF for the work it supported and the generally low level of interference.

About the Interview

MARTIN HELLMAN: An Interview Conducted by Andrew Goldstein, IEEE History Center, July 31, 1991

Interview #121 for the The IEEE History Center, The Institute of Electrical and Electronics Engineers, Inc.

Copyright Statement

This manuscript is being made available for research purposes only. All literary rights in the manuscript, including the right to publish, are reserved to the IEEE History Center. No part of the manuscript may be quoted for publication without the written permission of the Director of IEEE History Center.

Request for permission to quote for publication should be addressed to the IEEE History Center Oral History Program, IEEE History Center at Stevens Institute of Technology, Castle Point on Hudson, Hoboken, NJ 07030 USA. It should include identification of the specific passages to be quoted, anticipated use of the passages, and identification of the user.

It is recommended that this oral history be cited as follows:

Martin Hellman, an oral history conducted in 1991 by Andrew Goldstein, IEEE History Center, Hoboken, NJ, USA.

Interview

INTERVIEW: Dr. Martin Hellman

INTERVIEWER: Andy Goldstein

DATE: 31 July 1991

PLACE: Telephone interview

NSF Grants and Cryptography

Goldstein:

We have been commissioned by the National Science Foundation to write a book on their role in the development and support of computer science in America. In this portion I am working on a chapter describing the research that the NSF supported, and I am contacting a number of researchers who benefitted from NSF support, and I am just trying to get a sense of what it was that your research entailed, what you were after, what results you achieved, what impact it has had, that sort of thing. What I did was I went through the lists of awards granted by the NSF, and I saw that you received substantial grants in 1977. I do not know if that is complete, but could you tell me something about the work you were doing then?

Hellman:

Sure. And actually I think you will find that I had NSF support probably ranging all the way from 1971 or 1973, somewhere around there, when I first came back to Stanford all the way up through the middle 1980s, although there was a gap in there when I was on a leave of absence.

Goldstein:

I did not look past 1980, and I will have to look again for the early 1970s then.

Hellman:

The work that I think you want to talk mostly about is the work in cryptography.

Goldstein:

That is right.

Hellman:

Also interesting, that one of the things that made my work in cryptography possible was the fact that in NSF grants, when you find a new area that you did not anticipate or a new direction of research that is related to the primary one, you can proceed to a certain extent on your own discretion, but then if it is more of a major change you must check with the monitor and ask if you can work on that work. And whenever you come up with something really new, that is the way it works. Having that flexibility and being able to go back to the NSF. In this case I did because cryptography was a sensitive enough issue politically that I am sure I went back and checked with the person I was dealing with there, even though the work I was supporting was information theory, of which cryptography is a part.

Work in Information Theory

Goldstein:

That is interesting. Tell me what you started out to investigate and how you moved into cryptography.

Hellman:

All the work related to information theory. Information theory is basically signal processing to make information either smaller for transmission so you have to [inaudible word] to send, or to correct for errors in case errors occur during the transmission. Those were the two primary areas that have been worked on. And then there was this other area, coding information to keep it private against a wire tapper, or, and also to guarantee its authenticity against what sometimes is called an active wire tap, or someone who injects messages into the system. If you think in terms of electronic banking, that is a good example. You obviously are concerned both with privacy, so someone listening in does not know what your transactions are, and you are also even more concerned with what are called the active wiretap where someone injects a message, trying to make it look like I wrote a check on my account to him.

Goldstein:

When you say you started out working in information science with transmission of information, were you working in hardware or were you working encoding routines?

Hellman:

It was all paper and pencil and computers, no hardware. All of these things have hardware implementations, but the group I worked with at Stanford and the group supporting us at the NSF, I think, if you look into what they did, they supported the theoretical research that then would lead eventually to hardware implementations. But it was really applied mathematics.

Goldstein:

So that original work was trying to develop routines to compress data, that sort of thing?

Hellman:

Actually, there were several areas that I worked on. I would have to go back and look at the exact time frame, but there were some papers that came out on error correcting, actually error-detecting codes, which I am almost sure had NSF support. I am sure they did. And then there were some on multi-access channels. They are called aloha-type channels. They are like an ethernet. These were predecessors to ethernet. We have done some work there. And also I was doing work on data compression. That is, compressing the amount of information down. And then cryptography was growing out of my interest in those areas as well.

Goldstein:

When you say that the research that you were working with, who else was in your group?

Hellman:

When I was talking about the group at Stanford working at information theory, we were all on separate grants. Like Professor Thomas Cover, Robert Gray, to some extent Thomas Kailath. [inaudible word] had a very active information theory group, still does. My grant supported me and my students. Some of the students I had working in that time frame were Aydano, Carlisle, and I had Charles Davis. These were students working with me on various Ph.D. theses. And then as I moved into cryptography, the two people who became very key in these contributions — and both were supported under the NSF grant — were Whitfield Diffie and Ralph Merkle. Ralph was a graduate student at Berkeley and came down to Stanford for the summer. He had done some really good things up there that impressed me in cryptography. There were no people working in cryptography at Berkeley. So he came down for the summer, worked with us, and I was so excited, and he was too, that he transferred to Stanford after he finished his master’s degree at Berkeley and did his Ph.D. here.

National Security & Cryptography Research

Goldstein:

And you were receiving funds from the NSF. Did you have any other funders?

Hellman:

I had other funding. I had some Air Force support, from the Air Force Office of Scientific Research. They supported the work on information theory, but it was a little more difficult, particularly at first, in terms of the flexibility that I had to move into cryptography, because the National Security Agency actually felt that they had a monopoly on cryptographic research within the government and maybe in the whole country. Within AFOSR and the other military funding organizations, it would have been much more difficult if not impossible to move the work early. Although later I was able to work on some aspects of mathematics related to cryptography under AFOSR support, I could not work on cryptography itself. But I could work on some related areas.

Goldstein:

This is interesting, and I want to come back to your work on information science, but the OSR, do they actually provide funds, or did they just want to monitor the NSF in supporting your work?

Hellman:

No, the Office of Scientific Research was actually providing funds at the same time that the NSF was for different projects within information theory, and then when the work in cryptography started to develop from that, it was clear that it had to be the NSF rather than the military support organizations that I could turn to for the initial funding.

Goldstein:

You mean because the National Security Agency could mandate that?

Hellman:

Well, they felt they could. And within the military, they probably could. There was actually some question within the NSF whether they could.

Hellman:

Fred Weingarten got a phone call from the NSA saying that the NSF was not allowed to support this work. And he said they felt that they could, but he would be happy to consider their opinion on that if they would send him a letter. He would give it to the NSF counsel. And to my knowledge he never did receive any such letter. It was more of an attempt to stop the NSF from doing this, and because he stood up to it, it did not happen.

Information Theory to Cryptography

Goldstein:

Describe how your work in information theory transformed into cryptography. What was the specific research problem that caused you to drift over?

Hellman:

Well, actually it was not a specific research problem. I taught at the Massachusetts Institute of Technology for two years, 1969 to 1971, before coming back to Stanford to teach. I had done my Ph.D. here.

Goldstein:

When did you receive the Ph.D.?

Hellman:

Well, I received it in 1969. I actually did my work, 1966 to 1968, and then I was at IBM Europetown Heights for a year’s time. But the degree was not granted until 1969.

Goldstein:

So then you say you came back to Stanford after being at MIT?

Hellman:

Yes. When I was at MIT, Peter Olias gave me a copy of Claude Shannon’s 1949 paper relating information theory in cryptography. You have heard of Claude Shannon?

Goldstein:

Sure. That is the seminal paper. I am familiar with that one.

Hellman:

Right. The seminal paper on information theory in 1948. Well, this was a paper in 1949, which makes it looks like his work in cryptography followed his work in information theory. It is almost surely the other way around. Because the work he did in cryptography was done during the war at Bell Labs and was classified. And the 1949 paper even has a footnote indicating that it is a declassified version of a 1945 report. So in many ways information theory appears to have grown out of cryptography.

Goldstein:

Really?

Hellman:

I believe it was probably Shannon’s work in cryptography that gave him some of the key insights that led to that seminal 1948 paper. There are certain concepts, like the idea of a random code. Have you heard of that at all?

Goldstein:

Yes.

Hellman:

Random error correcting code is kind of intuitively unobvious. Who would think of using a random that looks like a noisy code to correct errors? And yet a random cipher, which he uses in the 1949 and presumably in a classified 1945 paper, makes perfect sense. If you apply the wrong key to a cryptogram, you get gibberish coming out, random working data. And there were some other connections, basically exponential bounds, which figure prominently in the 1948 paper, also coming in cryptography. So there are two problems that are very closely related actually. They are almost duals to each other. That is error correcting codes and cryptography. So when Olias gave me this paper when I was teaching at MIT — he had known Shannon over many, many years — I saw that information theory, which I was working in, had actually come out of cryptography probably. And it was an interesting area. In fact, I played with it, kept it in the back of my mind, and then my playing in my off hours on it led to a small publishable result. I began to think maybe I could do more work in this area, maybe I could actually do this during the day, so to speak, rather than just on the weekend, divide our time up that way.

Goldstein:

Give up your day job, so to speak?

Hellman:

Well, I worked during the week

Goldstein:

I understand.

Hellman:

You know how it works. But I could actually put more time in on it and ask the NSF whether they would be willing to shift some of the support to this area. And so that is how it came to be.

Goldstein:

And was the NSF receptive before they encountered any entanglements with bureaucracy?

Hellman:

They were receptive even after they encountered entanglements with bureaucracy.

Results & Applications of Research

Goldstein:

What results did you achieve in cryptography?

Hellman:

There were a couple of things. I would say, in the way of the most important, maybe the invention of public key or a trapdoor digital signatures, which is becoming very important in terms of our moving to electronic mail, electronic banking, things of that nature. Without the digital signature, you would not have the equivalent of a written signature on a check. So it is going to be very important there. It is being used in smart cards for banking in Europe already.

Goldstein:

There has been some interesting questions about the degree to which the NSF should fund work that has obvious and definite applications as opposed to pure science. When you were working on this was that an issue?

Hellman:

No, it was not. We were not actually implementing these things in hardware. We developed a theory to the systems. And if you look at the theory behind it, it uses number theory, which is the purest of pure mathematics. In fact, I had to learn a little bit about number theory because I had never studied it in my graduate work. It was not relevant to the other things I had studied. Actually I bought a book on number theory, and it was really interesting to read in the preface that the author was almost boasting about how it has no application.

Goldstein:

So all of your work resulted in published papers that may have later been utilized by developers or some other manufacturer?

Hellman:

Right. I mean a good analogy would be the original work on the transistor which involved solid-state physics. In fact, even today proving transistors and integrated circuits involves very deep scientific work in the physics of surfaces and solid state, and all these things; there is no question but that it is fine university research. And then out of it comes these personal computers and things like that, which are commercial applications. So no, there was no problem like that at all. It is the other way around if anything. It was one of the most beautiful examples of pure math, pure science leading to something that has tremendous commercial applications. Some of the systems that were developed by us and then by people at MIT and elsewhere depended on, for example, the difficulty of factoring a large integer into its prime components. That was a problem that has interested theoretical mathematicians for a long time, but they often had difficulty justifying why they would work on such a thing. I mean, what are the applications? Your math, but who is ever going to be interested in this? We gave them very good reasons. Because the security of one of these systems is widely used. Depends on how hard it is to factor.

Goldstein:

That is a famous example of determining if a number is prime or resolving it into its factors. What other areas were you looking into in cryptography?

Hellman:

The whole area of provable security, which is still an open area. I mean, if you read some of the press reports, some of the popular press items on the work we did, they give the misimpression that we invented the unbreakable code. We proposed two problems actually in one of the key papers we published. One was the development of public key crypto systems which we partly solved in that paper. And then the other one was the development of provably secure cryptographic systems, which is still an open problem, although some progress is being made and we are better understanding it.

Goldstein:

Who else is working on it? Are you still working on that, or have other groups taken it up?

Hellman:

Actually there is a conference later in August that is going to probably have 200 people at it on cryptography. There is one in Europe every year also. Eurocrypt is the European one, and Crypto is the one here in Santa Barbara. Every August each of those attracts a hundred, two hundred, or more people. When Whit and I started working cryptography, and Ralph was working up at Berkeley, we were pretty much the only ones. So yes, people have picked up on it.

Goldstein:

Anybody notable that you can think of.

Hellman:

First of all, the group at MIT. Revest, who is still at MIT, and then Shamir who is in Israel now, and Engleman at USC. Manuel Blum at Berkeley. There is a good group at Bell Laboratories, Andy Odlyzko, IBM, Nick Pippinger. So there is quite a bit going on.

Computational Complexity Research

Hellman:

The other thing is people who are working in computational complexity, which is a very theoretical area of computer science. They had some difficulty justifying their work, because they were concerned with two things. One was finding fasting algorithms to do what seemed to be difficult problems.

Goldstein:

By this you mean the set of problems that are NP?

Hellman:

Related to NP complete and things like that. There are two areas. One is finding ways to do what appear to be hard problems faster, like the FFT would be a good example of that. But they were more interested, from a theoretical point of view, in proving that certain problems were difficult. And people used to ask them, “Well, what good does that do?” Now, I personally think it is worthwhile to know that we should not waste more effort on trying to do something faster if you have a lower bound on computation. But cryptography and the relation that we made between cryptography and computational complexity gave new life, I think, to computational complexity, and gave them a good reason for being concerned with trying to prove these lower bounds. So it is a symbiotic relationship. I think we probably helped them maintain their support by being able to justify why they would be interested in this theoretical work, and we benefit because as they do work in computational complexity to help us understand what makes a good cryptographic system.

Goldstein:

I do not understand the relationship between cryptography and computational complexity.

Hellman:

Okay. Like taking the NP complete problems or the class of NP, in a weird sense you could say the class NP is the class of problems that is easily checked. Okay?

Goldstein:

That is right.

Hellman:

And you could say loosely that the class P is the class of problems that is easily solved.

Goldstein:

Alright.

Hellman:

Now the big open question in computational complexity is N equal to NP. Well, another way of putting that is all problems that are easily solved are also easily checked.

Goldstein:

Right.

Hellman:

The real question is, are there some problems that are easily checked but not easily solved? Well, every cryptographic problem is hopefully of that nature. It is always easy if you are a cryptanalyst trying to break a system — it is always easy to check whether or not you found the right solution. You just try it and see whether reasonable data comes out. On the other hand it is hopefully very difficult to actually find the solution. So if P equals NP in a loose sense there are no secure cryptographic systems.

Goldstein:

And where does research on that stand now? What is the popular view on it?

Hellman:

I am not the best one to really ask about that. It would probably be better to talk to someone like Manuel Blum at Berkeley.

Public Key Systems

Goldstein:

You mentioned the signatures on bank cards, that sort of thing. Can you think of any other? They do not necessarily have to be common.

Hellman:

There is a very exciting application that Gus Simmons at Sandia Institute created soon after we came out with these public key concepts. Sandia is one of the nuclear weapons labs, but they are also concerned not only with building weapons but with treaty compliance. And this was in the late 1970s, and we were negotiating a conference on a test ban treaty to stop all nuclear explosions. And one of the big questions was could you monitor it adequately. And there had been agreement reached on planting seismic sensors in the Soviet Union and in our country. But then there are problems.

Let’s look at it from the United States’ point of view, although obviously the Soviets have a mirror image concern. Let’s say they let us put these sensors in the Soviet Union. The communication channels over which the data comes out is controlled by the Soviets. Who's to stop them from setting off a nuclear explosion and playing back over the seismic line, over the communication line, an earthquake signal. This was a problem. The Americans suggested an approach that, whereby we would be allowed to encrypt the signals coming out using the convention crypto system, not public key. Because, as I indicated, conventional encryption provides both privacy and authentication. And we are concerned with the authentication. The trouble is the Soviets were unhappy with this because they were worried that we would sneak other data out. That is, even though they are allowing us to sneak out the seismic information, they are worried that we will sneak out radar data, because once it is encrypted they cannot see what it is. So the problem was that you wanted authentication, so we could authenticate the data when we got it, without privacy, so we could not hide anything from the Soviets. And Gus Simmons pointed out that the digital signature provided exactly that capability. Do you know how it works roughly?

Goldstein:

I am afraid I do not.

Hellman:

Do you want me to give you a 2-minute explanation?

Goldstein:

Sure.

Hellman:

In a conventional crypto system, first of all, before public key, if you and I want to talk we have to exchange a secret key that we then use to encrypt and decrypt data, the same secret key. Clearly that has got to be kept secret, because anyone else who learns it then has the same capability.

Goldstein:

And this is nothing more sophisticated than a code book?

Hellman:

No, the key is a number. Basically, we have got an algorithm that does the encryption and the decryption — has a switch on it that says whether to encrypt or decrypt, and it has two inputs. One input is a key. It is like a combination to a lock. And once that is in there, it modifies the algorithm so the encrypting is done differently with each different key. Because we are assuming that the hardware is available to everyone. In fact, it would be in a large commercial network. You and I using this hardware, our friends who also are our opponents, and certainly certain other business situations, are using the same hardware. So you load in a key, and you probably have done simple substitutions, ciphers in newspapers?

Goldstein:

Sure.

Hellman:

Okay. The key there is just the scrambled alphabet.

Goldstein:

Right.

Hellman:

Okay, so the general system is, we are going to substitute a letter for A, another letter for B, and so on.

Goldstein:

For instance, a very simple example would be the key could be 6, and that means shift every letter over six positions.

Hellman:

That could be, but right now if we are going to allow an arbitrary simple substitution, you could pick any scrambled alphabet you want. You could map A into R, B into F. And once you and I know that key, let’s say you pick the key, once you have communicated it to me somehow, you could then encipher messages and I could then decipher messages using that key.

This is actually a weak system that anyone else could break. But if it was a strong system, then without knowledge of the key, even though people knew that that is what we are doing, they — just intercepting the cipher text, the scrambled message — they would be unable to recover the key, therefore unable to recover the message. Notice that this provides both privacy and authentication, assuming again that this system was secure, which it is not. Obviously, because anyone who intercepts the message cannot understand it. They do not have the key.

Goldstein:

Right.

Hellman:

Anyone who wants to inject a message to me and make it look like it came from you does not know how to do it either, because he needs to know the key to how to. Because I expect every message to be properly enciphered. And how can you do that unless you know the key?

Goldstein:

Exactly.

Hellman:

There are two problems with this the public key solves. First of all, how do you communicate the key to me in the first place once you have picked it? The military traditionally used courier service, which is expensive and slow. That is a key distribution problem, which I will come back to in a minute. Then the second problem has to do with authentication. While it is true a third party cannot send a message to me and make it look like it came from you, he does not know the key. I could send a message to me and make it look like it came from you. Because we both know the same secret key.

Now why would I want to do that? Let’s say I am a stock broker and you are my client and I have been messing around with your account for personal gain and I made a mistake and lost money instead of making money, or siphoning off the profits. Instead I lost money. Now I want to make it look like you sent me this order. I can do that. Or, if I am the bank, I could forge messages, checks from you to me saying to pay me money.

Goldstein:

It lacks a signature.

Hellman:

<flashmp3>121_-_hellman_-_clip_1.mp3</flashmp3>

It lacks the true quality. It protects it as the third party forgery, but it does not protect against what we call disputes between the sender and receiver, because they are sharing the same secret key. Now, the basic idea, the insight in a public key system, is why use the same key to encipher and decipher? Why not have a pair of keys that are obviously related, because they will be inverse to one another, where one key enciphers and the other key deciphers, and where it is impossible to compute one from the other. It has got to be easy to generate a pair of these, but it has got to be computational impossible, meaning taking, let’s say, millions of years to compute one of these keys from the other. You could then make one of these public and keep one of them secret. That is what I call the public key system; one of the keys is public. Now, once you have generated such a pair and I have generated such a pair, you could make one of your keys public and I make one of my keys public, and we keep the other one secret. We put the public keys in a telephone book, something akin to a telephone book. When I want to send you a message, I look up your public key, I act on my message with that key. Notice you did not have to send it to me by courier. It is a public key. When you get it, you use your secret key, which is the inverse key, to decipher it. And only you can do that, because only you know your secret key. We have eliminated the key distribution problem, one of the major impediments to the use of cryptography in any system, but particularly in a large commercial system.

Goldstein:

And these pairs are not hard to find?

Hellman:

No. That, of course, was a lot of the research, to find systems that could do it. And systems have been developed where it is easy to find such pairs.

Goldstein:

Are there an infinite number of them?

Hellman:

There is an infinite number of them, right. I mean because the obvious thing, if there are only ten of them, just try all ten pairs. But if you are got twenty quadrillion pairs to try, that is a little bit of a problem. And you can make the set as big as you want. And that is where the difficulty of factoring comes in. This is not exactly right, but you can think of the public key as being the product of the two numbers, and the secret key as being the factorization. It is very easy given two numbers to multiply them together, so if you generate the secret key first, prime numbers, you can multiply them together in a fraction of a second on a computer to produce the result.

Going back from the result to the two factors. If you are dealing with a couple of hundred digits, it would take millions of years. Now the second problem that this solves is the dispute problem. If you want to send me a message that is signed by you, you have to have it with your secret key. Then, when I get it, how do I verify what the content of the message is, and if this is really a signed version of the message that you said you were going to send me? I have done it with your public key, which is its inverse. And I get back the message saying Andy Goldstein agrees to pay Martin Hellman a hundred dollar honorarium for giving a seminar at Rutgers on such and such a date.

Goldstein:

And there is no problem of uniqueness. Two keys will not map to a different one.

Hellman:

That is right. So there is no problem with that. Now the thing is, if you later disclaim having sent me that message, I take the scrambled message that was scrambled with your secret key, so only you could have done it, to a judge, he acts on it with your public key, and says, “Sorry, Andy. You agreed to this.”

Goldstein:

Is that happening, or have there been cases where it has revealed fraud?

Hellman:

These are just coming into use. I think in terms of how far these are coming into commercial use, a really good person to talk to would be Jim Omura at Cylink.

Goldstein:

Okay.

Hellman:

He used to be a professor at UCLA and, in fact, probably had NSF support. And he now is, I think, vice president of a company that works primarily in cryptography. He could give you an idea as to the extent of the use of these systems. I think it is something where we expect them to be used right away. It actually took about five, maybe even ten, years for them to come and begin to be used in any reasonable amount, and it is going to take more like 10 or 15 before they are as widespread as we thought they would be, but they are certainly going to be used. And they already are being used, but how widely you would have to check with him.

Relations with NSA

Goldstein:

In the development of cryptography in the mid-1970s, were you a pioneer in pursuing these research goals, or was the wind blowing in that direction?

Hellman:

No. I would say, rather than a pioneer, most people would have called me, most people in fact did call me, foolish.

Goldstein:

What was the objection?

Hellman:

The standard objection I got from almost everyone was that the NSA had a huge budget on the order of a billion dollars a year for work in this and related areas. How can you ever hope? And they have been doing this for 35 years. How can you hope to ever catch up? You will just be reproducing what is known in the classified literature. And the second objection was if you do anything good, they will classify it.

Goldstein:

Do you know what directions they were pursuing? Why they were less productive?

Hellman:

I think people thought that way, and so they did not pursue it. They looked into other areas of information theory or whatever they were working on. They felt that this would be a dead end.

Goldstein:

No, I mean in the NSA. People were concerned that you would be competing with the NSA?

Hellman:

No, we do not know what they worked on. I had a logical answer and then I had another answer which was not logical, just within me. But the logical answer was, I do not care if we just reproduce what is in there in the classified literature. If it is not available in the open literature for commercial applications, it is not available. And there are commercial applications that need this. And then the answer to the second one was, I will cross the classification issue, I will cross that bridge, when I come to it. And actually the second issue became the major one, in even whether the NSF could support my work, as I indicated.

Goldstein:

You started to tell me about how Weingarten got involved. Were there any more? Because the NSA did not pursue it, was it just dropped?

Hellman:

Well, I do not know what went on behind the scenes. But I have indications that there were a fair number of attempts made by the NSA or by individuals within the NSA. I do not know to what extent this was an agency policy and to what extent it was individuals within the NSA who were upset by this. One guy who worked at the NSA sent a threatening letter to the IEEE that they were in violation of the law by publishing these papers.

Goldstein:

I could probably talk to people in publishing and see if they remember that. Were you involved with that?

Hellman:

Yes. It was my papers he was referring to.

Goldstein:

Right, but I just wonder whether you had to come in and defend the publication.

Hellman:

I guess the short answer, and in fact under, I think, NSF support, a group was set up at the NSA to request the study of this issue as to how to deal with unclassified academic research in cryptography. And I became a member of that group, although I was not at first. And we were able to reach, I think, a pretty good understanding.

Goldstein:

What decision finally emerged?

Hellman:

Most of it was that legislative approaches would not work. In theory they might work. Even if the NSA could get the kind of legislation it wanted through Congress, which was questionable, that if they did not have the support of the researchers, if they did not have the active support and cooperation of the researchers it would not work. Because you might be able to limit publication, but it is very hard to limit [Inaudible words.]

Goldstein:

You were saying that without the support of the researchers, no kind of moratorium could work?

Hellman:

People might obey the letter of the law, although even that was questionable, because there were constitutional questions if the law they wanted would be passed. But even if people obeyed the letter of the law, there was lots of opportunity for working around the spirit of it, and they really needed our cooperation. And going for a legislative solution basically trying to force cooperation, would actually produce non-cooperation. And Admiral Inman, who came in as director of the NSA, seemed to understand this and be a very clever, open, intelligent person.

Goldstein:

You say that you served on this community, but not originally. Who organized the committee, and who spearheaded it?

Hellman:

I am pretty sure that it was the NSA that requested it, the NSF funded it, and the American Council on Education, the ACE, actually administered it. They had representatives from different professional societies that were involved, and the IEEE was one of these. And Elwin Burroughcamp was the first representative that they appointed. I forget whether they asked me and I was too busy, or I forget what, but Elwin was the first representative. He resigned, I think, partly because people felt he had a conflict of interest because he consulted for one of the NSA’s subsidiaries, so to speak. And so they then asked me if I would serve, and I agreed to do that. I had been making the point even informally before serving, that we needed a voluntary system where the researchers felt that their interests were taken into account.

And so what came out of it was the agreement that they would try a voluntary system and set up an appeals board. We would send in our papers voluntarily to the NSA for review without any promise that we would abide by their decision. On the other hand, it gave them a chance to seek a court order if something really damaging from their perspective came out. And the other thing was that if you voluntarily sent it in and they said “We do not want you publishing this,” you would have the right to go to a group which was cleared to the levels required to actually assess how damaging this would be. Because up to that point it appeared to me that the NSA was saying anything relating to cryptography is extremely damaging. Much too broad. Keep it all undercover approach. And so that was the agreement. I do not think that group was ever set up, however. I do not know that any need really arose for it.

Goldstein:

I am actually a little surprised that there was that degree of cooperation in the beginning, that the NSA proposed this committee.

Hellman:

There was a question as to how much cooperation they would get, cooperation on the part of the NSA or on the part of the researchers? Which one?

Goldstein:

Cooperation on the part of NSA.

Hellman:

As I said, Inman was a guy who actually cared about results, not about what it said on paper. On the paper it says you are going to pay me a million dollars, but if there is no way you are ever going to pay it to me it does not do me much good, right?

Goldstein:

That is true.

Hellman:

What I think he saw as a result of our conversations and probably others was that if they got this very stringent law through it would probably just alienate the whole academic community and we would challenge the law, and, even if we could not challenge it in the courts, we would probably work with it begrudgingly and try to work around it as much as possible.

Goldstein:

So, it was a very pragmatic move.

Hellman:

Yes. Actually, it was in the NSA’s interest to gain our friendship. Unless we felt friendly toward them it was not going to work. And at that point not only was there not a lot of friendliness, there was a lot of animosity on the part of the academic community, a lot of mistrust, some of it very, I think, for good reasons, of the NSA. Like the call to Weingarten, the threat to IEEE, stuff like that. And so they had to build some bridges to us, and Inman tried to do that, and I think he did it very successfully. The big question was how much the academic community would reciprocate. And I think they got pretty good cooperation from us. Not 100%. I certainly tried making the system work.

National Data Encryption Standard (DES)

Goldstein:

I want to return to your research. Have you covered it, do you think?

Hellman:

There were many aspects to it.

The public key was certainly the most important. Another that was very important was looking at cryptanalysis, trying to get a feeling for the security level of systems. That was motivated by something we were not able to work on even under NSF support, which was a national data encryption standard that came out, DES. Have you heard of that?

Goldstein:

No. Promulgated by whom?

Hellman:

Promulgated by, at that time, the National Bureau of Standards, now NIST, National Institute for Standards in Technology. It was developed by IBM. My position, and that of Diffie, was that it was not adequately secure and that it had probably been weakened, as we discovered later, by the NSA, because they did not want a public available cryptographic system they could not break. Because this was political and because it involved standards, my understanding was we could not work on this under NSF support. But some of the related questions as to how there are shortcuts to exhaustive search, that is are there shortcuts to trying one key after the other for an arbitrary cryptographic system, was a general problem we could work on which was related to this. And we did. I came up with a cryptanalytic time memory tradeoff, and then later came up with a cryptanalytic time memory processor tradeoff. Basically, a way to cut the overall cost down compared to exhaustive search.

Goldstein:

And that was successful?

Hellman:

It was successful in the sense that it cut the cost tremendously compared to exhaustive search.

Goldstein:

Are you saying that you could not work on this under NSF support?

Hellman:

I could not work on the specific application to DES, which was motivating me a lot. DES was a standard. Apparently the NSF cannot fund work that is designed to affect the standards making process.

Goldstein:

Did you approach them for funding and they told you that?

Hellman:

I forget how I found that out. And I even could, I mean, try to remember back ten years ago, and more than ten years ago. That was my understanding. And so we were very careful not to do any of the specific work on DES under NSF support, but we could work on the general problem under NSF support, and did do that.

Discrete Logarithms & RSA Systems

Goldstein:

I am curious about your relations with the NSF, the sort of information that you would give them, progress reports, and how much interaction there was. But, if you have more interesting stuff to say about to your research, then I would just as soon continue.

Hellman:

Let me do one other thing. Let me get out a copy of my résumé and go through my publications. That would probably help.

Goldstein:

Okay.

Hellman:

We developed a conventional cryptographic system, not a public key system, that was based on a very nice mathematical problem called discrete logarithm.

Goldstein:

I am not familiar with that.

Hellman:

Well, you know what logarithms are?

Goldstein:

Sure.

Hellman:

Discrete logarithms are logarithms in modular arithmetic. You know what modular arithmetic is?

Goldstein:

Clocks.

Hellman:

That is right. So when you do arithmetic modular with some other number, everything has integers, and so you no longer have algorithms [correct word?] like 2.3. Every, for example if you are doing mod 7 arithmetic, 2 to the 4th power is 16, which in mod 7 arithmetic is 2.

Goldstein:

Comes back to 2.

Hellman:

So 2 to the 4th equals 2, right? So what is the log of 2 to the base 2. It is not only 1, but it is also 4. You see it? Because 2 to the 4th equals 2.

Goldstein:

Right. It sounds like I can recall branch cut problems or like normal square roots have a plus or minus.

Hellman:

Okay. It might be multiple solutions, but there are some really funny ones here. Anyway, we developed a conventional cryptographic system based on that kind of mathematics which was then, I am almost sure, an important step in the development of the RSA public key crypter system. This was the MIT system. There was that.

Goldstein:

What is the RSA system? What does that stand for?

Hellman:

That is Revess, Shamir and Adelman at MIT. That is the one they based on difficulty of factoring. Because it turns out those two problems are related.

Goldstein:

And when did you do that?

Hellman:

The paper came out in 1978, but the work would have predated it by a couple of years, probably 1975. I did some work on the security of multiple encryption. This relates again to cryptanalysis. As I said, we did some general work. We could not work on DES specifically, but we came up with what is called a “meet in the middle attack.” There have been a number of papers that have taken it much further. So it developed a basic idea that has been used extensively.

Goldstein:

Who is working in that area?

Hellman:

I saw a paper by Nick Pippinger, for example, at IBM Research on it. It crops up a lot of places.

Degree of NSF Input

Goldstein:

Did the NSF offer much guidance or input for you?

Hellman:

No, I would say the basic approach I felt with the NSF was they review the proposal, they review the qualifications, and once you have their support, unless you are making a major change in direction other than the annual reports, you are pretty much free to — The guidance comes more from your peers than from the foundation itself.

Goldstein:

So if you have a strong reputation, then you are in fairly good shape.

Hellman:

Once you are funded, you have said what you are going to work on, I think the basic philosophy is, and I think it is a good one, that the researcher knows best what to work on.

Goldstein:

I thought that was a characteristic more of the DARPA or some of the military funding, who tend to pump a lot of money and give the research free reign.

Hellman:

Right. In a way, within the military organizations, you do have a little more freedom that way. But within the NSF, once you have told them what you are going to work on, as long as you were sticking to that, they did not try to direct the research one way or another. It’s almost impossible to do. It would hard for me to do that with one of my colleagues, to tell them how they are going to do research. [inaudible word] working in an area, I think it is worthwhile, and [inaudible word] besides that, basically got to leave him on his own, because he is trying to do something that has not been done before. So how could I tell him how to do it? Any other questions?

Goldstein:

No. I want to give you an opportunity to say anything that you feel ought to be included in a section on yourself. If you are interested, when I am done with this I expect to write three or four pages, and then I can send them to you and you can review them for technical accuracy.

Hellman:

That would be a good thing to do. Okay. No, I think that is it, and I think I have probably given you more than enough at this point.

Goldstein:

Alright, thanks, bye.

Hellman:

Okay. Good luck with it. Bye now.