Ralph Merkle

Ralph C. Merkle (born February 2, 1952) is an American computer scientist. He co-invented public-key cryptography and invented cryptographic hashing, and has worked on molecular nanotechnology and cryonics.

As an undergraduate at the University of California, Berkeley, Merkle devised Merkle's Puzzles, an early scheme for public-key key exchange. He completed his Ph.D. at Stanford University in 1979 under Martin Hellman, with whom he co-invented the Merkle–Hellman knapsack cryptosystem. He later introduced the Merkle–Damgård construction, which underlies many cryptographic hash algorithms, and Merkle trees, which are widely used in distributed systems. Merkle held research positions at Xerox PARC and Zyvex and was a Distinguished Professor at the Georgia Institute of Technology; he is a senior research fellow at the Institute for Molecular Manufacturing and a board member of the Alcor Life Extension Foundation. He received the IEEE Richard W. Hamming Medal in 2010 and was inducted into the National Inventors Hall of Fame in 2011.

Early life and education

Merkle graduated from Livermore High School in Livermore, California in 1970. He received a B.A. in Computer Science from the University of California, Berkeley in 1974 and an M.S. in Computer Science from the same institution in 1977, with a thesis titled "Evaluators for Attribute Grammars". He received a Ph.D. in Electrical Engineering from Stanford University on June 17, 1979, with the thesis "Secrecy, Authentication, and Public Key Systems".

Research

Early work and Merkle's Puzzles

As an undergraduate at UC Berkeley, Merkle developed a scheme that would allow two parties to communicate securely over an insecure channel without first sharing a secret key. He submitted the work as a course project, and after the course continued refining the idea on his own. The scheme, later named Merkle's Puzzles, was first described in a manuscript Merkle submitted in 1975 and published in 1978 in Communications of the ACM.

In the scheme, the sender generates a large set of encrypted "puzzles" and transmits them; the receiver chooses one at random, solves it, and uses the contained value as a shared key. An eavesdropper unable to distinguish the chosen puzzle must, on average, solve half the set, producing a quadratic gap in work between legitimate parties and attackers.

Merkle's manuscript circulated while Whitfield Diffie and Martin Hellman were preparing the 1976 paper "New Directions in Cryptography", which formalized the public-key paradigm and credited Merkle's puzzles as a precursor. Merkle entered graduate study at Stanford under Hellman, and the two co-authored the Merkle–Hellman knapsack cryptosystem, one of the earliest concrete public-key encryption schemes. Merkle's 1979 Stanford doctoral thesis collected this body of work.

Hashing, signatures, and ciphers

Binary tree diagram with leaf-level hashes labeled L1 through L4 and parent nodes containing concatenated hashes

A Merkle tree, used to authenticate large data sets by hashing data in pairs up to a single root hash

Merkle invented cryptographic hashing, formalized as the Merkle–Damgård construction in a pair of articles published a decade later, and introduced Merkle trees as a method for efficiently authenticating large data sets. The Merkle–Damgård construction underlies many subsequent hashing algorithms.

At Xerox PARC, Merkle designed the Khufu and Khafre block ciphers and the Snefru hash function.

Career

Merkle managed compiler development at Elxsi from 1980. In 1988, he became a research scientist at Xerox PARC. In 1999, he became a nanotechnology theorist at Zyvex. In 2003, he was named a Distinguished Professor at Georgia Tech, where he led the Georgia Tech Information Security Center. In 2006, he returned to the San Francisco Bay Area, where he is a senior research fellow at the Institute for Molecular Manufacturing, a faculty member at Singularity University, and a board member of the Alcor Life Extension Foundation.

He has published works on molecular manipulation and self-replicating machines. Merkle appears in the science fiction novel The Diamond Age, which involves nanotechnology.

Personal life

Merkle is the son of Theodore Charles Merkle, director of Project Pluto, and the brother of historical novelist Judith Merkle Riley. He is a grandnephew of baseball player Fred Merkle. He is married to video game designer Carol Shaw, known for the 1982 Atari 2600 game River Raid.

Awards

• 1996: Paris Kanellakis Award (from the ACM) for the invention of public-key cryptography
• 1998: Feynman Prize in Nanotechnology for computational modeling of molecular tools for atomically-precise chemical reactions
• 1999: IEEE Koji Kobayashi Computers and Communications Award
• 2000: RSA Award for Excellence in Mathematics for the invention of public-key cryptography
• 2008: International Association for Cryptologic Research (IACR) Fellow for the invention of public-key cryptography
• 2010: IEEE Richard W. Hamming Medal for the invention of public-key cryptography
• 2011: Computer History Museum Fellow, "for his work, with Whitfield Diffie and Martin Hellman, on public key cryptography"
• 2011: National Inventors Hall of Fame, for the invention of public-key cryptography
• 2012: National Cyber Security Hall of Fame inductee
• 2020: Levchin Prize, "for fundamental contributions to the development of public key cryptography, hash algorithms, Merkle trees, and digital signatures"

Further reading

• Merkle, Ralph C. (1982). Secrecy, Authentication, and Public Key Systems. Computer Science series. UMI Research Press. Template:ISBN.
• Freitas, Robert A., Jr.; Merkle, Ralph C. (2004). Kinematic Self-Replicating Machines. Landes Bioscience. Template:ISBN.
• Kantor, Paul; Mureşan, Gheorghe; Roberts, Fred; Zeng, Daniel; Wang, Frei-Yue; Chen, Hsinchun; Merkle, Ralph, eds. (2005). Intelligence and Security Informatics: IEEE International Conference on Intelligence and Security Informatics, ISI 2005, Atlanta, GA, US, May 19–20. Lecture Notes in Computer Science. Springer. Template:ISBN.

External links

• Oral history interview with Martin Hellman from 2004, Palo Alto, California. Charles Babbage Institute, University of Minnesota, Minneapolis. Hellman describes his invention of public-key cryptography with collaborators Whitfield Diffie and Ralph Merkle at Stanford University in the mid-1970s.