Ralph Merkle

Early life and education

Ralph C. Merkle was born on 2 February 1952 in Berkeley, California. He studied at the University of California, Berkeley, where he earned a bachelor's degree and a master's degree, and afterwards completed a doctorate at Stanford University under the supervision of Martin Hellman. His graduate work at Stanford placed him at the centre of the small group of researchers then reconstructing cryptography as an open academic discipline rather than a government speciality.

The 1974 proposal and Merkle's Puzzles

As an undergraduate at Berkeley in the autumn of 1974, Merkle enrolled in a computer security course, CS244, and submitted a project proposal describing a method by which two people who had never met could establish a shared secret while an eavesdropper listened to everything they said. The instructor, Lance Hoffman, rejected the proposal. Merkle continued the work on his own; he later recovered the original seven-page document in 2005 and published it on his website. The proposal sketched two approaches, the first based on what became known as "puzzles" and the second on converting a two-way encryption function into an apparently one-way one.

Merkle submitted a written version of the idea to Communications of the ACM in August 1975. An anonymous reviewer with cryptographic expertise rejected it, writing that "the paper is not in the main stream of present cryptography thinking" and objecting that it cited no prior literature, a difficulty inherent to a genuinely novel idea. After roughly three years of delay the paper finally appeared as "Secure Communications Over Insecure Channels" in Communications of the ACM, volume 21, issue 4, April 1978, pages 294-299. The scheme is now generally called Merkle's Puzzles and is regarded as the first published construction of what became public key cryptography.

Work with Diffie and Hellman

In 1976 Merkle began working with Whitfield Diffie and Martin Hellman at Stanford, and the three are jointly credited with establishing public key cryptography in the open literature. Their work is covered by U.S. Patent 4,200,770, "Cryptographic apparatus and method," which names Hellman, Diffie and Merkle and was cited by the National Inventors Hall of Fame on Merkle's induction. Merkle also collaborated with Hellman on the Merkle-Hellman knapsack cryptosystem, an early public key encryption scheme based on the subset-sum problem.

Merkle trees and hashing

Merkle's doctoral and subsequent work introduced the hash tree, or Merkle tree, a structure in which each leaf holds the hash of a data block and each internal node holds the hash of its children. Verifying that a particular block belongs to the tree requires work proportional to the logarithm of the number of blocks rather than to the whole data set. He filed for a patent on the technique in 1979; U.S. Patent 4,309,569, "Method of providing digital signatures," issued on 5 January 1982 and was assigned to the Board of Trustees of the Leland Stanford Junior University. Merkle also developed the iterated design for building collision-resistant hash functions from compression functions that is now known as the Merkle-Damgard construction, after his work and independent work by Ivan Damgard.

Hash trees have since become standard infrastructure. They are used in the Bitcoin and Ethereum peer-to-peer networks, in the ZFS and OpenZFS file systems to detect data degradation, in IPFS, BitTorrent and Tahoe-LAFS, in the Git and Mercurial version control systems, in the Certificate Transparency framework, in distributed databases such as Apache Cassandra, Riak and Dynamo, and in the Nix and GNU Guix package managers.

Industry research

Merkle managed compiler development at Elxsi from 1980. In 1988 he became a research scientist at Xerox PARC, where he designed the Khufu and Khafre block ciphers and the Snefru cryptographic hash function, all named after Egyptian pharaohs. He moved to the nanotechnology company Zyvex as a theorist in 1999. From 2003 he was a Distinguished Professor at the Georgia Institute of Technology, where he led the Georgia Tech Information Security Center, and from 2006 a senior research fellow at the Institute for Molecular Manufacturing. He has also taught at Singularity University and co-founded the Nanofactory Collaboration.

Nanotechnology and cryonics

Merkle's second research career concerns molecular manufacturing, the design of systems that would fabricate products with atomic precision. He served as executive editor of the journal Nanotechnology and chaired Foresight Conferences on Molecular Nanotechnology, and he received the 1998 Feynman Prize in Nanotechnology in the theory category. He is a long-standing advocate of cryonics, which he describes as a bridge to a future in which nanomedicine could repair present-day injury and disease; he joined the Alcor Life Extension Foundation in 1989 and has served as an Alcor director since 1998.

Recognition and legacy

Merkle received the ACM Paris Kanellakis Theory and Practice Award in 1996, the IEEE Koji Kobayashi Computers and Communications Award in 1999, the RSA Award for Excellence in Mathematics in 2000, and the IEEE Richard W. Hamming Medal in 2010. In 2011 he was named a Fellow of the Computer History Museum "for his work, with Whitfield Diffie and Martin Hellman, on public key cryptography," and was inducted into the National Inventors Hall of Fame for public-key cryptography. He received the Levchin Prize for real-world cryptography in 2020. His name is attached to more everyday computing infrastructure than almost any other cryptographer's, chiefly through the hash tree that carries it.

Timeline

• 1952-02-02Ralph C. Merkle born in Berkeley, California.
• 1974As a Berkeley undergraduate in the CS244 computer security course, Merkle proposes a method for two parties to establish a shared secret over an insecure channel; the project proposal is rejected by instructor Lance Hoffman.
• 1975-08Merkle submits the idea to Communications of the ACM; a reviewer rejects it as "not in the main stream of present cryptography thinking."
• 1976Merkle begins working with Whitfield Diffie and Martin Hellman at Stanford on public key cryptography.
• 1978-04"Secure Communications Over Insecure Channels" published in Communications of the ACM 21(4):294-299, introducing what became known as Merkle's Puzzles.
• 1979Merkle files a patent application on hash trees and hash-based digital signatures.
• 1980Becomes manager of compiler development at Elxsi.
• 1982-01-05U.S. Patent 4,309,569, "Method of providing digital signatures," issues to Merkle and is assigned to Stanford University.
• 1988Joins Xerox PARC as a research scientist; designs the Khufu and Khafre block ciphers and the Snefru hash function.
• 1989Joins the Alcor Life Extension Foundation.
• 1996Receives the ACM Paris Kanellakis Theory and Practice Award.
• 1998Receives the Feynman Prize in Nanotechnology (theory); becomes a director of Alcor.
• 1999Receives the IEEE Koji Kobayashi Computers and Communications Award; joins Zyvex as a nanotechnology theorist.
• 2000Receives the RSA Award for Excellence in Mathematics.
• 2003Becomes a Distinguished Professor at the Georgia Institute of Technology and leads the Georgia Tech Information Security Center.
• 2005Recovers and publishes the original seven-page 1974 CS244 project proposal describing public key cryptography.
• 2006Becomes a senior research fellow at the Institute for Molecular Manufacturing.
• 2010Receives the IEEE Richard W. Hamming Medal.
• 2011Named a Fellow of the Computer History Museum and inducted into the National Inventors Hall of Fame for public-key cryptography.
• 2020Receives the Levchin Prize for real-world cryptography.