Ralph Merkle
Abstract
Ralph Merkle (born 1952) had the idea of public-key cryptography as an undergraduate at Berkeley in the fall of 1974, in a project proposal for a computer security course. The instructor rejected the proposal, and the journal he sent the paper to rejected it too; it appeared in 1978, after Diffie and Hellman’s paper had made the idea famous. His later inventions carry his name: the Merkle tree, which now underlies Git, BitTorrent, and every blockchain, and the Merkle–Damgård construction behind MD5, SHA-1, and SHA-2. From the late 1980s he turned to molecular nanotechnology and cryonics.
CS244
Merkle was born in Berkeley on 2 February 1952. His father, Theodore Merkle, ran Project Pluto, the Livermore program to build a nuclear-powered ramjet; his great-uncle was the baseball player Fred Merkle. He studied computer science at the University of California, Berkeley.
In the fall of 1974 he enrolled in CS244, the computer security course taught by Lance Hoffman. Students had to submit two proposals for a term project. Merkle’s first one addressed a problem that the cryptography of the time treated as unsolvable: how two people who have never met, and who can talk only over a line that an eavesdropper hears in full, can agree on a secret key.
His method is now called Merkle’s Puzzles. Alice creates a large number of puzzles, say a million, each of which takes a moderate amount of work to solve and contains a serial number and a key. She sends them all to Bob. Bob picks one at random, solves it, and tells Alice the serial number in the clear. Both now know the key. The eavesdropper, who has seen every puzzle and the serial number, does not know which puzzle that number is hidden in and must solve half a million of them on average to find out. The legitimate parties do work proportional to N; the attacker does work proportional to N squared. It is a modest advantage and an impractical scheme, but it showed that key agreement over an open channel was possible at all.
Hoffman did not see the point. Merkle rewrote the proposal in a shorter and simpler form and submitted it again, with no more success, then dropped the course and kept working on the idea alone. He lost the original proposal, with Hoffman’s handwritten comments, and found it again on 8 September 2005; it is on his website.
“Not in the Main Stream”
A Berkeley faculty member, Bob Fabry, read a draft and told him: “Publish it, win fame and fortune!” In August 1975 Merkle sent the paper to the Communications of the ACM. The editor, Susan Graham, sent it to a reviewer described as an experienced cryptography expert, whose verdict Merkle has preserved: “I am sorry to have to inform you that the paper is not in the main stream of present cryptography thinking.” The reviewer added that “experience shows that it is extremely dangerous to transmit key information in the clear.” Graham rejected the paper and noted that it had no references to the literature. There was no literature to refer to.
Merkle revised and resubmitted. Meanwhile, at Stanford, Whitfield Diffie and Martin Hellman had been working toward the same idea, and in November 1976 they published “New Directions in Cryptography”, with a far more efficient key exchange based on modular exponentiation. Their paper credits Merkle’s independent work. Merkle’s own paper, “Secure Communications over Insecure Channels”, appeared in the Communications in April 1978, after what he calls “almost three years of delay”.
By then he had moved to Stanford as Hellman’s doctoral student. Hellman has said that the key exchange should be called Diffie–Hellman–Merkle. The first US patent on public-key cryptography names all three as inventors.
Misconception: Merkle withdrew his paper
Some retellings say that Merkle gave up on the paper or withdrew it. By his own documented account he did neither: Hoffman turned down the course proposal, the Communications of the ACM rejected the first submission in 1975, and Merkle revised and resubmitted until it was printed in 1978. See Myths and Misconceptions.
Knapsacks, Trees, and Hash Functions
With Hellman, Merkle designed one of the first public-key encryption systems, the knapsack cryptosystem of 1978. It was fast and it was broken: Adi Shamir found an attack in 1982 (see Rivest, Shamir, Adleman, and RSA).
His 1979 Stanford thesis, Secrecy, Authentication, and Public Key Systems, contained two ideas that lasted. The first was the Merkle tree. Take a large set of data blocks, hash each one, then hash the hashes in pairs, and repeat until a single root hash remains. Anyone who trusts the root can check that a given block belongs to the set by recomputing only the hashes along one path from leaf to root, a number of steps that grows with the logarithm of the set’s size. Merkle invented it to make digital signatures out of hash functions alone. It turned out to be the general answer to the question of how to verify a piece of a large body of data without holding all of it, and it is how Git identifies a repository’s state, how BitTorrent checks downloaded pieces, and how Bitcoin lets a light client confirm that a transaction is in a block (see The Cryptocurrency Revolution). Hash-based signatures of the kind he proposed returned in the 2020s as one of the standardized defences against quantum computers (see Post-Quantum Cryptography).
The second was a method for building a hash function for messages of any length out of a compression function with fixed-size input, by chaining the blocks and padding the message with its length. Merkle published a proof of its security in 1989, as did the Danish cryptographer Ivan Damgård independently, and the Merkle–Damgård construction became the skeleton of MD5, SHA-1, and SHA-2 (see Hashing).
PARC, Nanotechnology, and Alcor
After his doctorate Merkle managed compiler development at the minicomputer maker Elxsi from 1980, and in 1988 he joined Xerox PARC, where he designed the ciphers Khufu and Khafre and the hash function Snefru. At PARC his interest shifted to molecular nanotechnology, the proposal that machines could be built atom by atom. He did computational work on molecular machine parts, won the Feynman Prize in Nanotechnology in 1998, and in 1999 left for the nanotechnology company Zyvex. From 2003 he was a professor at Georgia Tech and directed its information security centre, and in 2006 he returned to California as a fellow of the Institute for Molecular Manufacturing. Neal Stephenson put him by name into the novel The Diamond Age.
Merkle is also a director of the Alcor Life Extension Foundation, which stores the bodies and brains of its members in liquid nitrogen in the hope of later revival, and he has written and lectured in its defence for decades (see The Singularity and Superintelligence). In 1983 he married Carol Shaw, who had been one of the first women to design video games for Atari and wrote River Raid for Activision.
The honours for the 1974 idea came late: the ACM’s Kanellakis Award in 1996, the IEEE Hamming Medal in 2010, and the National Inventors Hall of Fame and a Computer History Museum fellowship in 2011.
📚 Sources
- Merkle, Ralph C.: “Publishing a new idea” (the 1974 CS244 project proposal, with facsimiles and correspondence) (CS244 with Lance Hoffman in fall 1974, the two proposals, dropping the course, rediscovery on 8 September 2005, Fabry’s remark, submission to Susan Graham in August 1975, the reviewer’s letter, “almost three years of delay”)
- Merkle, Ralph C.: “Secure Communications over Insecure Channels”, Communications of the ACM 21(4), 294–299 (April 1978)
- Merkle, Ralph C.: Secrecy, Authentication, and Public Key Systems, PhD thesis, Stanford University (1979)
- Merkle, Ralph C.: “A Digital Signature Based on a Conventional Encryption Function”, Advances in Cryptology: CRYPTO ‘87, LNCS 293, 369–378 (1988) (the tree-based signature)
- Merkle, Ralph C.: “One Way Hash Functions and DES”, Advances in Cryptology: CRYPTO ‘89, LNCS 435, 428–446 (1990)
- Diffie, Whitfield & Hellman, Martin E.: “New Directions in Cryptography”, IEEE Transactions on Information Theory 22(6), 644–654 (1976)
- Computer History Museum: “Martin Hellman: 2011 Fellows Interview”, interviewed by Jon Plutte (11 March 2011) (Hellman’s argument for the name Diffie–Hellman–Merkle)
- Wikipedia: Ralph Merkle (finding aid: birth date, Theodore and Fred Merkle, Carol Shaw, Elxsi, Xerox PARC, Zyvex, Georgia Tech, IMM, Alcor, awards, The Diamond Age)
- Image: Ralph Merkle.png by david.orban (CC BY 2.0), via Wikimedia Commons