Ron Rivest

Education

Rivest earned a bachelor's degree in mathematics from Yale University in 1969, and a Ph.D. degree in computer science from Stanford University in 1974 for research supervised by Robert W. Floyd.

Career

At MIT, Rivest is a member of the Theory of Computation Group, and founder of MIT CSAIL's Cryptography and Information Security Group.

Rivest was a founder of RSA Data Security (now merged with Security Dynamics to form RSA Security), Verisign, and of Peppercoin.

His former doctoral students include 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 research in cryptography. He has also made significant contributions to algorithm design, to the computational complexity of machine learning, and to election security.

Cryptography

Rivest, jointly with Adi Shamir and Leonard Adleman, introduced the RSA cryptosystem in 1978, which revolutionized modern cryptography by providing the first usable and publicly described method for public-key cryptography. Rivest had reportedly thought of the key idea behind the cryptosystem after having drunk large amounts of wine while celebrating Passover with Shamir and Adleman at a student's house. The three won the 2002 Turing Award for "their ingenious contribution to making public-key cryptography useful in practice." The same paper was also the first to introduce Alice and Bob, the fictional heroes of many subsequent cryptographic protocols.{{cite journal

Rivest was one of the inventors of the GMR public signature scheme, published with Shafi Goldwasser and Silvio Micali in 1988,{{cite book | chapter-url = https://cacr.uwaterloo.ca/hac/about/chap11.pdf and of ring signatures, an anonymized form of group signatures invented with Shamir and Yael Tauman Kalai in 2001. He designed the MD4 and MD5 cryptographic hash functions, published in 1990 and 1992 respectively, and a sequence of symmetric key block ciphers that include RC2, RC4, RC5, and RC6.

Other contributions of Rivest to cryptography include chaffing and winnowing, the interlock protocol for authenticating anonymous key-exchange, cryptographic time capsules such as LCS35 based on anticipated improvements to computation speed through Moore's law, key whitening and its application through the xor–encrypt–xor key mode in extending the Data Encryption Standard to DES-X, and the Peppercoin system for cryptographic micropayments.

Algorithms

In 1973, Rivest and his coauthors published the first selection algorithm that achieved linear time without using randomization.{{cite conference | editor1-last = Karlsson | editor1-first = Rolf G. | editor2-last = Lingas | editor2-first = Andrzej | doi-access = free

Rivest's 1974 doctoral dissertation concerned the use of hash tables to quickly match partial words in documents; he later published this work as a journal paper. His research from this time on self-organizing lists became one of the important precursors to the development of competitive analysis for online algorithms.{{cite journal

He is a co-author of Introduction to Algorithms (also known as CLRS), a standard textbook on algorithms, with Thomas H. Cormen, Charles E. Leiserson and Clifford Stein. First published in 1990, it has extended into four editions, the latest in 2022.

Learning

In the problem of decision tree learning, Rivest and Laurent Hyafil proved that it is NP-complete to find a decision tree that identifies each of a collection of objects through binary-valued questions (as in the parlor game of twenty questions) and that minimizes the expected number of questions that will be asked. With Avrim Blum, Rivest also showed that even for very simple neural networks it can be NP-complete to train the network by finding weights that allow it to solve a given classification task correctly. Despite these negative results, he also found methods for efficiently inferring decision lists, decision trees, and finite automata.

Elections

A significant topic in Rivest's more recent research has been election security, based on the principle of software independence: that the security of elections should be founded on physical records, so that hidden changes to software used in voting systems cannot result in undetectable changes to election outcomes. His research in this area includes improving the robustness of mix networks in this application, the 2006 invention of the ThreeBallot paper ballot based end-to-end auditable voting system (which he released into public domain in the interest of promoting democracy), and the development of the Scantegrity security system for optical scan voting systems.

He 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, the National Academy of Sciences, and is a Fellow of the Association for Computing Machinery, the International Association for Cryptologic Research, and the American Academy of Arts and Sciences. Together with Adi Shamir and Len Adleman, he has been awarded the 2000 IEEE Koji Kobayashi Computers and Communications Award and the Secure Computing Lifetime Achievement Award. He also shared with them the Turing Award. Rivest has received an honorary degree (the "laurea honoris causa") from the Sapienza University of Rome. In 2005, he received the MITX Lifetime Achievement Award. Rivest was named in 2007 the Marconi Fellow, and on May 29, 2008, he also gave the Chesley lecture at Carleton College. He was named an Institute Professor at MIT in June 2015.

Selected publications

Rivest's publications include:

Algorithms

| doi-access = free

| editor1-last = Crabbe | editor1-first = James S. | editor2-last = Radke | editor2-first = Charles E. | editor3-last = Ofek | editor3-first = Hillel

Cryptography

| doi-access = free | hdl-access = free

| editor-last = DeMillo | editor-first = Richard A.

| editor-last = Boyd | editor-first = Colin

| editor-last = Preneel | editor-first = Bart

Learning

| doi-access = free

Elections and voting

| editor-last = Boneh | editor-first = Dan | contribution-url = https://www.usenix.org/publications/library/proceedings/sec02/jakobsson.html

| contribution-url = https://www.usenix.org/legacy/events/evt07/tech/full_papers/rivest/rivest.pdf

| editor1-last = Dill | editor1-first = David L. | editor2-last = Kohno | editor2-first = Tadayoshi | contribution-url = https://www.usenix.org/events/evt08/tech/full_papers/chaum/chaum.pdf

Personal life

Rivest is married to Gail Rivest with whom he has two sons, Alex Rivest, filmmaker, and Chris Rivest, entrepreneur and company co-founder.

References

References

1. Singh, Mona. (1996). "Learning algorithms with applications to robot navigation and protein folding". Massachusetts Institute of Technology.
2. RSA Conference. (25 February 2014). "The Cryptographers' Panel".
3. (October 15, 2015). "Faculty Forum Online: Ron Rivest".
4. Dizikes, Peter. (June 29, 2015). "Chisholm, Rivest, and Thompson appointed as new Institute Professors: Biologist, computer scientist, and musician awarded MIT's highest faculty honor". Massachusetts Institute of Technology.
5. {{MathGenealogy
6. Calderbank, Michael. (2007-08-20). "The RSA Cryptosystem: History, Algorithm, Primes".
7. Singh, Simon. (2000). "The Code Book". Fourth Estate (GB).
8. "Ronald (Ron) Linn Rivest". Association for Computing Machinery.
9. (2009-05-06). "TGDC members". [[National Institute of Standards and Technology]].
10. [https://web.archive.org/web/20120105044726/http://people.csail.mit.edu/rivest/bio.html Biography]. Archived from [http://people.csail.mit.edu/rivest/bio.html the original] on 2011-12-06.
11. (June 29, 2015). "Chisholm, Rivest, and Thompson appointed as new Institute Professors".
12. Cf. Acknowledgements, p.xxi, in Cormen, Rivest, et al., [https://books.google.com/books?id=NLngYyWFl_YC ''Introduction to Algorithms''], MIT Press 3rd edition