Communications of the ACM

Communications of the ACM

Enabling Crypto: How Radical Innovations Occur

By Arnd Weber
Communications of the ACM, April 2002, Vol. 45 No. 4, Pages 103-107
10.1145/505248.505253
Comments

In electronic commerce and communication, encryption and digital signatures are being increasingly used between people who have never met before. Businesses and private individuals encrypt their communication without prior exchange of secret keys. Industry sets up key certification services for handling digitally signed electronic business documents. In these situations, the relying party does not need the signer's secret key and also cannot counterfeit the signature. These security features are only possible due to public key cryptography, which solved seemingly insoluble problems. How did such an effective technical solution develop? The answer is relevant to anyone interested in radically new solutions. The roles of enabling structures and vocational ethics and how they led to such radical crypto innovation are examined here.

What exactly was the nature of the problem? Consider the case of exchanging confidential correspondence with someone you have not met previously. One could use a key distribution center, but it would be possible to eavesdrop on any communication via the center. One could use secure channels as a courier for communicating secrets, but these channels are expensive to operate. A similar problem is that of a digital signature. How can one replace the signed paper document? Usage of passwords does not provide any evidence and is inconvenient when dozens of business partners are involved. A solution seems unlikely. One reason for this is that every record can easily be copied. Another reason is that one would assume a secret key will be used for signing, which the verifying party needs for verification and thus the latter would be able to generate the signature itself.

In order to solve both problems, public key cryptography was invented. It uses two keys, a public one and a secret one. The secret key can be used to sign, and the public key to verify a signature. A public key can also be used to encrypt a message to be sent to someone and the recipient can then use the secret key to decrypt it. Such algorithms avoid negative effects of traditional communication. Usually, no evidence of transactions exists or the evidence is limited to what the verifying party could have generated itself. Or, regarding encryption, confidential information can easily be communicated without the costs and risks of prior key exchange over a trusted channel. Today, there are numerous products using public key cryptography. But how were these seemingly insoluble problems originally addressed and effectively resolved?

Tools from the sociological analysis of technical change are used here in order to analyze how a solution was found. Since 1960, many technology assessments have identified undesired consequences. This happened frequently, however, after the technologies had already been deployed. Therefore, interest rose in research on the development of technologies. It was concluded that it can be understood as an interaction of economic, social, political, and cultural determinants. According to these findings, the development of technology is a result of different orientations, not of economics alone, nor of a technical momentum of its own. Studies made in fields as diverse as work organization or energy production revealed that such sociocultural factors exercise an influence and sometimes even contribute to abolishing negative effects [11]. The question thus becomes: How can actors avoid undesired consequences of technological change? The development of public key cryptography can be regarded as an example.

Back to Top

Serious Libertarianism

Public key cryptography results from the interaction of a few individuals in specific settings. The foundation of liberal communities in New England and the libertarian traditions in the U.S. have been important starting points. One of the developers is Whitfield Diffie, who grew up in a libertarian and leftist tradition: "I had come from the environment of New York City, a very left, politically active environment. I grew up among what were called red diaper babies."¹ Diffie remained in a leftist environment while studying mathematics in the early 1960s in Berkeley when the free speech movement and the student movement emerged.

Another factor that influenced the development is self-confidence, particularly manifest at the Massachusetts Institute of Technology. Here Diffie adopted the attitude of being able to change society: "Some years ago I was sitting at lunch with the people in my department and they were talking about intellectual sort of social problems. It was clear to me that they regarded this as casual conversation. They just took it for granted, they couldn't do anything about this. And it struck me that that was in very sharp contrast to the style of conversation, particularly at MIT, I had grown up in, in which we didn't take ourselves lightly. The things talked about in conversation at MIT, the people who were talking about them took themselves seriously. If they had good ideas on them they would recognize them and work on these things."

Here we see self-confidence as an enabling structure [4] in which one of the main actors in the development of cryptography was involved. The Californian electronics industry provided a favorable environment—an enabling structure—for attracting developers like Diffie and other scientists who were involved in the development of cryptography.

Back to Top

How Can All Citizens Make Confidential Calls?

In 1965, Diffie heard the incorrect information that the National Security Agency intended to encrypt its telephone communications: "Somebody told me that NSA encrypted the telephones within its own building. That turns out that was not true but I began to try to figure out what good it would do. Because I had this view of cryptography in which the critical value of cryptography was that you didn't have to trust other people. And so I never understood the classical notion of a key distribution center." Diffie wondered if it were possible for all U.S. citizens to make confidential calls via telephone, a question of immediate relevance for the political movement in California.

Independently of Diffie, Ralph Merkle, a student in Berkeley, analyzed the operation of time sharing systems "and found that quite fascinating."² Here, Merkle's interest in technology becomes apparent (see www.merkle.com). In 1974, he enrolled in a course on computer security engineering taught by Lance Hoffman. Merkle was analyzing how to restart secure operation of a compromised system. His starting point was: "The computer security has been compromised and has since been sealed up again. I was trying to figure out how to reestablish secure communications. I began trying to figure out whether you could prove that in the absence of some secure channel like a courier, security had been compromised." This is how Merkle arrived at the question of secure communication between two computers. The question could be called a technical one, but is actually one of eliminating the costs of operating secure channels.

Back to Top

Signatures for E-Commerce on the ARPANET

How to conduct secret communication over open networks was one issue; another question was that of non-repudiation. In 1969 Diffie worked for John McCarthy at the Stanford Artificial Intelligence Laboratory. The Laboratory was working on the question of whether it would be possible to encrypt the communication on the ARPANET. Thus, Diffie was working on cryptography. McCarthy had a workstation at his home with a connection to his laboratory. The trigger for working on the question of a digital signature was McCarthy's proposal for home shopping: "John McCarthy had just written a paper on the subject of home terminals. And he envisioned people buying and selling and booking through home terminals." As early as 1970, McCarthy envisaged sales of custom-made, high-value goods: "Candidates for individual design include clothing, furniture, boats, electronic equipment, houses, and even cars" [6]. Such sales would only be possible, Diffie reasoned, if there were a digital signature. The methods of classical cryptography seemed to be insufficient. With these, the signatory would use a secret key to make a sort of pseudo signature out of the plaintext. The verifying party, however, would need the same secret key for verification and thus could counterfeit the signature. Diffie: "I couldn't understand what you would do to replace the signed document. So that's when I began thinking about what we now call the problem of digital signature. Because I reasoned that since written signatures depend critically on the fact that it is so hard to copy the document, but since digital documents are always exactly copyable, how could you have a signature?"

Back to Top

A Trapdoor is the Solution

From 1973 on, Diffie tried to collect all publicly available knowledge about cryptography through extensive traveling. This demonstrates his intrinsic motivation. He wanted to build artifacts: "I decided I was an engineer. Now I continued to do work that was almost entirely mathematical, but I just realized that what I was basically interested in was building things."

While traveling, Diffie learned about one-way functions, which are difficult to invert, such as exponentiation. In 1974, he tried to explain to Bill Mann what a one-way function is, but he misunderstood it and imagined having a one-way function that can only be reversed with additional information (information that makes it possible to get back through a sort of trapdoor). Precisely such a function could be used for encryption—everyone could encrypt a text using the one-way function, but only the recipient would be able to decrypt the encrypted text using the trapdoor function, that is, the secret key. Similarly, it would be possible to sign using the secret key and everyone could verify the signature using the one-way function. Thus, the principle of public key cryptography was described without the central participants being aware of it.

Independently of Diffie, Merkle continued to work on his question of how to exchange a new session key between a computer and a user at a remote terminal if both were compromised. It was believed that a secure channel was needed for such an exchange. Merkle: "I realized that not only could I not prove it, it was not even clear that it was correct. Over the next few days I figured out the puzzles technique" (see the sidebar "Merkle's Puzzle System"). "Once I realized the problem was in fact soluble, at least that it was clear that there was no proof that it was insoluble, things fell into place fairly quickly. I concluded that there had to be some random component. And then it was simply a question of how to utilize that random component in a way which would provide confusion to the eavesdropper that would grow more rapidly than the confusion of either the two parties communicating."

Merkle, however, was alone with his solution: "There was no one to talk with. No one had any idea that this problem even existed. It was simply, you know, stare at the ceiling and say 'Oh, this looks interesting. I think I'll think about it'." This also reveals that he had no particular political or social motivation. Merkle submitted his solution in a course paper: "One of the people who was very instrumental in my continuing the work was Bob Fabry who was on the faculty at that time. I showed him a paper describing the concept and said: 'Here's an idea I had. What do you think about it?' And he said: 'This is wonderful. Why don't you submit it for publication and win fame and fortune?'" [7] So, in point of fact, Fabry's encouragement in the winter of 1974–1975 was a critical element. Merkle submitted his paper in the summer of 1975 to Communications of the ACM, but it was rejected for publication after review.

Back to Top

The Vocational Network

In 1974, Diffie continued to improve his personal vocational network. He met cryptographers at IBM who were the only significant nongovernmental cryptographic group in the country at the time. Diffie learned about the Identification Friend or Foe problem (IFF) of telling hostile from friendly aircraft. In order to make a determination, one transmits data via radar. Only an airplane possessing a secret key can encrypt the data properly and send the result back. This would be a sort of signature. Anyone, however, who has the secret key, such as the verifying ground station, would be able to fake the response. Thus, the IFF procedure is not suitable for making signatures but was another relevant concept Diffie was exposed to.

Diffie was then advised to contact Martin Hellman at Stanford. Thus, he returned to Palo Alto and finally met someone willing to talk about the subject. In the end, it was Hellman with whom he published the concept of public key cryptography. Thus, Diffie obtained the building blocks for his later developments through creating a personal network: "So I went around doing one of the things I am good at, which is digging up rare manuscripts in libraries, driving around, visiting friends at universities. When I made my first talk at Stanford after I got back, Hellman described me in the flyer as an 'itinerant cryptographer'."

This shows Diffie was highly motivated to find suitable information and knowledgeable people to talk to. Hellman, for example, had worked on building blocks like the one-way functions suggested by his colleague John Gill. Hellman also recalls having discussions with Diffie about trapdoors, which the U.S. military was considering incorporating into crypto tools. In 1974, Diffie thought the problem of a signature was insoluble. He learned, however, there was someone working on the problem of key exchange—that was Merkle, living in Berkeley. Because of this, Diffie said he began thinking about the problem again.

Back to Top

Political Consciousness as the Final Trigger

In 1975, the Data Encryption Standard (DES) was proposed as a U.S. government encryption standard. Diffie did not understand how the government could propose such a standard: "I did not understand how those people dared either standardize a secure system or standardize a nonsecure system, because if it was secure—since they were primarily an intelligence agency—they would be afraid they wouldn't be able to read other people's traffic. If it was not secure, since they had certified it for the use of U.S. government organizations, they risk having a tremendous black eye if it were broken."

When the proposal was made, Diffie wondered whether DES was a trapdoor cryptosystem: "And the minute it appeared, I envisioned what I called a trapdoor cryptosystem. What people usually mean by trapdoor—that there was some secret information remembered in the design process—that may be even the good ones are breakable by the people who knew how they were designed."

Shortly after, he developed the idea that such a trapdoor function could make digital signatures possible. "I thought this way of having an enhanced IFF so that the responder could answer in such a way that the challenger could judge the answer but could not have constructed the answer." That is, the trapdoor information, which has to be kept secret, could be used for making a signature. It would depend on the text, so that the document and its signature can be copied, but the signature cannot be attached to a different text. Thus, in the end, Diffie's politically motivated doubts regarding DES led to spelling out the principle of the solution. Such a function could also be used for encryption: "If I had this public key of yours, it could be turned round, so I can send you a message, even though I have never talked to you before." This concept originated in approximately May 1975. Diffie: "The discovery consisted not of a solution, but of the recognition that the two problems, each of which seemed unsolvable by definition, could be solved at all and that the solutions to both problems came in one package." [1]

Back to Top

Pushing the Approach into the Establishment

Diffie explained his approach to Hellman, who was in contact with Jim Massey of the IEEE Transactions on Information Theory, and they prepared a paper for submission to that journal. A preversion reached Merkle's friend Blatman. Thus, Merkle and Diffie got to know each other. Merkle approached Diffie and Hellman in order to escape from the loneliness of his efforts. Diffie, Hellman, and Merkle then discussed the capabilities and problems of the public key approach. In 1976, the Diffie-Hellman paper was published [2]. Merkle's approach was published in 1978 as "Secure Communications Over Insecure Channels" in Communications of the ACM [8]; at the time of publication, the concept had been established.

Thus, it was Diffie's social motivation that gave him the power to build a vocational network. And it was he who, through Hellman, created relationships with the establishment. It is possible that Merkle might have succeeded somehow and at some point in time. But this is not how it happened, on the contrary. Diffie about Merkle: "The most original person I can identify in this case is Merkle. Merkle had the earliest claim. Merkle had the first thing that is really any sort of a solution to the problem: the Merkle Puzzle System."

But Merkle remained in his rather isolated situation. Also, in our interviews no political motivation of his became apparent. It was Diffie's articulation in his personal network and his political motivation that led to a publicly known solution. Merkle rather solved a technical security problem that resulted from the economics of key exchange but was not able to develop a successful network. Subsequently, Diffie and Hellman developed their approach for exponential key exchange [2], and as early as 1977, Rivest, Shamir, and Adleman at MIT developed their algorithm [10].

Back to Top

Outlook: Secure Systems Ahead?

Public key cryptography has been developed in an enabling structure by highly motivated individuals. The enabling structures consisted of the libertarian and leftist traditions in the U.S., social movements, a tradition of self-confidence, and an innovative industry. Diffie played the main role in communicating the principle successfully; his motivation can be interpreted as socially oriented vocational ethics [5]. Personal networks were essential for working out the approach and making it known. I am optimistic that similar conditions will lead to similarly beneficial results in other fields of technology.

In the field of digital signatures and encryption, some innovations may be needed for obtaining secure computing environments. With computers running complex code from open networks, we risk our privacy and our business secrets by running hacked, flawed, or fake code. Also, real Trojan horses producing counterfeit digital signatures can become as bad as falsely claimed ones. New solutions will then be needed—systems that remain secure in the hands of laypersons, protecting security applications while running legacy applications as well as untrusted code [9].

Back to Top

Back to Top

Back to Top

Back to Top

The Digital Library is published by the Association for Computing Machinery. Copyright © 2002 ACM, Inc.