Ronald Linn Rivest (born May 6, 1947) is an American expert in secret codes and computer science. His work includes areas like algorithms, cryptography, machine learning, and ensuring fair elections. He is a professor at the Massachusetts Institute of Technology (MIT) and part of MIT's Department of Electrical Engineering and Computer Science, as well as its Computer Science and Artificial Intelligence Laboratory.
Along with Adi Shamir and Len Adleman, Rivest helped create the RSA algorithm, for which they received the 2002 ACM Turing Award. He also developed symmetric key encryption algorithms such as RC2, RC4, and RC5, and co-created RC6. (RC stands for "Rivest Cipher.") Additionally, he designed cryptographic hash functions called MD2, MD4, MD5, and MD6.
Education
Rivest received a bachelor's degree in mathematics from Yale University in 1969. He also earned a Ph.D. in computer science from Stanford University in 1974. His research was supervised by Robert W. Floyd.
Career
At MIT, Rivest is part of the Theory of Computation Group and started the Cryptography and Information Security Group at MIT CSAIL.
Rivest helped create RSA Data Security (which later combined with Security Dynamics to become RSA Security), Verisign, and Peppercoin.
Some of his former doctoral students are Avrim Blum, Benny Chor, Sally Goldman, Burt Kaliski, Anna Lysyanskaya, Margrit Betke, Ron Pinter, Robert Schapire, Alan Sherman, and Mona Singh.
Research
Rivest is especially known for his work in cryptography. He also contributed to algorithm design, the computational complexity of machine learning, and election security.
In 1978, Rivest, along with Adi Shamir and Leonard Adleman, created the RSA cryptosystem. This system changed modern cryptography by offering the first practical and publicly described method for public-key cryptography. Rivest reportedly thought of the main idea for the system after drinking a lot of wine during a Passover celebration with Shamir and Adleman at a student’s home. Rivest, Shamir, and Adleman won the 2002 Turing Award for their work in making public-key cryptography useful in practice. Their paper also introduced Alice and Bob, fictional characters used in many cryptographic examples. In the same year, Rivest, Adleman, and Michael Dertouzos first described homomorphic encryption and its use in secure cloud computing. This idea became practical more than 40 years later when secure homomorphic encryption methods were finally developed.
Rivest helped create the GMR public signature scheme, published with Shafi Goldwasser and Silvio Micali in 1988. He also developed ring signatures, a type of group signature that protects anonymity, with Shamir and Yael Tauman Kalai in 2001. Rivest designed the MD4 and MD5 cryptographic hash functions, published in 1990 and 1992, and created a series of symmetric key block ciphers, including RC2, RC4, RC5, and RC6.
Other contributions include chaffing and winnowing, the interlock protocol for authenticating anonymous key exchanges, cryptographic time capsules like LCS35 based on Moore’s law, key whitening, and the Peppercoin system for secure micropayments.
In 1973, Rivest and his coauthors published the first selection algorithm that worked in linear time without using randomization. This method, called the median of medians, is often taught in algorithms classes. Rivest is also one of the names behind the Floyd–Rivest algorithm, a randomized selection method that uses close to the best number of comparisons.
Rivest’s 1974 doctoral dissertation focused on using hash tables to quickly match partial words in documents. He later published this work as a journal article. His research on self-organizing lists helped develop competitive analysis for online algorithms. In the early 1980s, he published important research on two-dimensional bin packing problems and channel routing in VLSI design.
He is a co-author of Introduction to Algorithms (also called CLRS), a widely used textbook on algorithms, with Thomas H. Cormen, Charles E. Leiserson, and Clifford Stein. First published in 1990, the book has had four editions, with the latest in 2022.
In the study of decision tree learning, Rivest and Laurent Hyafil proved that finding a decision tree to identify objects using binary questions (like in the game of twenty questions) is NP-complete, meaning it is extremely difficult to solve efficiently. With Avrim Blum, Rivest also showed that training simple neural networks can be NP-complete. Despite these challenges, he developed efficient methods for creating decision lists, decision trees, and finite automata.
More recently, Rivest has focused on election security, emphasizing software independence. This principle states that election security should rely on physical records to prevent undetectable changes to election results caused by hidden software changes. His work includes improving mix networks, inventing the ThreeBallot paper ballot system (released publicly to support democracy), and creating the Scantegrity system for secure optical scan voting.
Rivest was a member of the Election Assistance Commission’s Technical Guidelines Development Committee.
Honors and awards
Rivest is a member of the National Academy of Engineering and the National Academy of Sciences. He is also a Fellow of the Association for Computing Machinery, the International Association for Cryptologic Research, and the American Academy of Arts and Sciences. He was awarded the 2000 IEEE Koji Kobayashi Computers and Communications Award and the Secure Computing Lifetime Achievement Award, along with Adi Shamir and Len Adleman. He shared the Turing Award with them as well. Rivest received an honorary degree, called the "laurea honoris causa," from the Sapienza University of Rome. In 2005, he was given the MITX Lifetime Achievement Award. In 2007, he was named a Marconi Fellow. On May 29, 2008, he delivered the Chesley lecture at Carleton College. In June 2015, he was named an Institute Professor at MIT.
Personal life
Rivest is married to Gail Rivest, and they have two sons: Alex Rivest, filmmaker, and Chris Rivest, entrepreneur and company co-founder.