Ron Rivest | |
|---|---|
 Rivest in 2012 | |
| Born | (1947-05-06)May 6, 1947 (age 78) Schenectady, New York, U.S. |
| Education | Yale University (BA) Stanford University (MS,PhD) |
| Known for | Public-key RSA,RC2,RC4,RC5,RC6 MD2,MD4,MD5,MD6,Ring signature |
| Awards |
|
| Scientific career | |
| Fields | |
| Institutions | Massachusetts Institute of Technology |
| Thesis | Analysis of associative retrieval algorithms (1974) |
| Doctoral advisor | Robert W. Floyd |
| Doctoral students | |
| Website | people |
Ronald Linn Rivest (/rɪˈvɛst/;[3][4]born May 6, 1947) is an Americancryptographer and computer scientist whose work has spanned the fields of algorithms and combinatorics, cryptography, machine learning, and election integrity.He is anInstitute Professor at theMassachusetts Institute of Technology (MIT),[5]and a member of MIT'sDepartment of Electrical Engineering and Computer Science and itsComputer Science and Artificial Intelligence Laboratory.
Along withAdi Shamir andLen Adleman, Rivest is one of the inventors of theRSA algorithm.He is also the inventor of thesymmetric key encryption algorithmsRC2,RC4, andRC5, and co-inventor ofRC6. (RC stands for "Rivest Cipher".) He also devised theMD2,MD4,MD5 andMD6cryptographic hash functions.
Rivest earned abachelor's degree in mathematics fromYale University in 1969, and aPh.D. degree in computer science fromStanford University in 1974 for research supervised byRobert W. Floyd.[1]
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 ofRSA Data Security (now merged with Security Dynamics to formRSA Security),Verisign, and ofPeppercoin.
His former doctoral students includeAvrim Blum,Benny Chor,Sally Goldman,Burt Kaliski,Anna Lysyanskaya,Margrit Betke,Ron Pinter,Robert Schapire,Alan Sherman,[1]andMona Singh.[2]
Rivest is especially known for his research incryptography. He has also made significant contributions toalgorithm design, to thecomputational complexity ofmachine learning, and toelection security.
Rivest, jointly withAdi Shamir andLeonard Adleman, introduced theRSA cryptosystem in 1978,[C1] which revolutionized modern cryptography by providing the first usable and publicly described method forpublic-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.[6][7] The three won the 2002Turing Award for "their ingenious contribution to making public-key cryptography useful in practice."[8] The same paper was also the first to introduceAlice and Bob, the fictional heroes of many subsequentcryptographic protocols.[9] In the same year, Rivest, Adleman, andMichael Dertouzos first formulatedhomomorphic encryption and its applications in securecloud computing,[C2] an idea that would not come to fruition until over 40 years later when secure homomorphic encryption algorithms were finally developed.[10]
Rivest was one of the inventors of theGMR public signature scheme, published withShafi Goldwasser andSilvio Micali in 1988,[C3][11]and ofring signatures, an anonymized form ofgroup signatures invented with Shamir andYael Tauman Kalai in 2001.[C7] He designed theMD4 andMD5cryptographic hash functions, published in 1990 and 1992 respectively,[C4][C5] and a sequence ofsymmetric keyblock ciphers that includeRC2,RC4,RC5, andRC6.[C6][C8]
Other contributions of Rivest to cryptography includechaffing and winnowing, theinterlock protocol for authenticatinganonymous key-exchange, cryptographictime capsules such asLCS35 based on anticipated improvements to computation speed throughMoore's law,key whitening and its application through thexor–encrypt–xor key mode in extending the Data Encryption Standard toDES-X, and thePeppercoin system for cryptographicmicropayments.
In 1973, Rivest and his coauthors published the firstselection algorithm that achievedlinear time without usingrandomization.[A1][12] Their algorithm, themedian of medians method, is commonly taught in algorithms courses.[13] Rivest is also one of the two namesakes of theFloyd–Rivest algorithm, a randomized selection algorithm that achieves a near-optimal number of comparisons.[A2][14]
Rivest's 1974 doctoral dissertation concerned the use ofhash tables to quickly matchpartial words in documents; he later published this work as a journal paper.[A3] His research from this time onself-organizing lists[A4] became one of the important precursors to the development ofcompetitive analysis foronline algorithms.[15] In the early 1980s, he also published well-cited research on two-dimensionalbin packing problems,[A5] and onchannel routing inVLSI design.[A6]
He is a co-author ofIntroduction to Algorithms (also known asCLRS), a standard textbook on algorithms, withThomas H. Cormen,Charles E. Leiserson andClifford Stein. First published in 1990, it has extended into four editions, the latest in 2022.[A7]
In the problem ofdecision tree learning, Rivest and Laurent Hyafil proved that it isNP-complete to find a decision tree that identifies each of a collection of objects through binary-valued questions (as in theparlor game oftwenty questions) and that minimizes theexpected number of questions that will be asked.[L1] WithAvrim Blum, Rivest also showed that even for very simpleneural networks it can be NP-complete to train the network by finding weights that allow it to solve a given classification task correctly.[L3] Despite these negative results, he also found methods for efficiently inferringdecision lists,[L2] decision trees,[L4] andfinite automata.[L5]
A significant topic in Rivest's more recent research has beenelection security, based on the principle ofsoftware 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 ofmix networks in this application,[V1] the 2006 invention of theThreeBallot paper ballot basedend-to-end auditable voting system (which he released intopublic domain in the interest of promoting democracy),[V2][8] and the development of theScantegrity security system foroptical scan voting systems.[V3]
He was a member of theElection Assistance Commission's Technical Guidelines Development Committee.[16]
Rivest is a member of theNational Academy of Engineering, theNational Academy of Sciences, and is a Fellow of theAssociation for Computing Machinery, theInternational Association for Cryptologic Research, and theAmerican Academy of Arts and Sciences. Together withAdi Shamir andLen Adleman, he has been awarded the 2000IEEE Koji Kobayashi Computers and Communications Award and the Secure Computing Lifetime Achievement Award. He also shared with them theTuring Award. Rivest has received an honorary degree (the "laurea honoris causa") from theSapienza University of Rome.[17] 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 atCarleton College. He was named an Institute Professor at MIT in June 2015.[18]
Rivest's publications include:
| A1. | Blum, Manuel;Floyd, Robert W.;Pratt, Vaughan;Rivest, Ronald L.;Tarjan, Robert E. (1973)."Time bounds for selection"(PDF).Journal of Computer and System Sciences.7 (4):448–461.doi:10.1016/S0022-0000(73)80033-9.MR 0329916. Previously announced as "Linear time bounds for median computations", STOC 1972. |
| A2. | Floyd, Robert W.;Rivest, Ronald L. (March 1975)."Expected time bounds for selection".Communications of the ACM.18 (3):165–172.doi:10.1145/360680.360691.S2CID 3064709. See also "Algorithm 489: the algorithm SELECT—for finding theth smallest of elements", p. 173,doi:10.1145/360680.360694. |
| A3. | Rivest, Ronald L. (1976). "Partial-match retrieval algorithms".SIAM Journal on Computing.5 (1):19–50.doi:10.1137/0205003.MR 0395398. Previously announced at the 15th Annual Symposium on Switching and Automata Theory, 1974. |
| A4. | Rivest, Ronald (1976)."On self-organizing sequential search heuristics".Communications of the ACM.19 (2):63–67.doi:10.1145/359997.360000.MR 0408303.S2CID 498886. Previously announced at the 15th Annual Symposium on Switching and Automata Theory, 1974. |
| A5. | Baker, Brenda S.;Coffman, E. G. Jr.; Rivest, Ronald L. (1980). "Orthogonal packings in two dimensions".SIAM Journal on Computing.9 (4):846–855.CiteSeerX 10.1.1.309.8883.doi:10.1137/0209064.MR 0592771. |
| A6. | Rivest, Ronald L.; Fiduccia, Charles M. (1982). "A "greedy" channel router". In Crabbe, James S.; Radke, Charles E.; Ofek, Hillel (eds.).Proceedings of the 19th Design Automation Conference, DAC '82, Las Vegas, Nevada, USA, June 14–16, 1982. ACM and IEEE. pp. 418–424.doi:10.1145/800263.809239.ISBN 0-89791-020-6. |
| A7. | Cormen, Thomas H.;Leiserson, Charles E.;Rivest, Ronald L. (1990).Introduction to Algorithms (1st ed.). MIT Press and McGraw-Hill.ISBN 0-262-03141-8. 2nd edition, withClifford Stein, 2001. 3rd edition, 2009. 4th edition, 2022. |
| C1. | Rivest, R. L.;Shamir, A.;Adleman, L. (1978)."A method for obtaining digital signatures and public-key cryptosystems".Communications of the ACM.21 (2):120–126.doi:10.1145/359340.359342.hdl:1721.1/148910.MR 0700103.S2CID 2873616. |
| C2. | Rivest, R.;Adleman, L.;Dertouzos, M. (1978). "On data banks and privacy homomorphisms". In DeMillo, Richard A. (ed.).Foundations of Secure Computation. Academic Press. pp. 169–177. |
| C3. | Goldwasser, Shafi;Micali, Silvio; Rivest, Ronald L. (1988). "A digital signature scheme secure against adaptive chosen-message attacks".SIAM Journal on Computing.17 (2):281–308.doi:10.1137/0217017.MR 0935341.S2CID 1715998. Previously announced as "A 'paradoxical' solution to the signature problem", FOCS 1984 and CRYPTO 1984. |
| C4. | Rivest, Ronald L. (October 1990).The MD4 Message Digest Algorithm. Network Working Group.doi:10.17487/RFC1186.RFC1186. |
| C5. | Rivest, Ronald L. (April 1992).The MD5 Message-Digest Algorithm. Network Working Group.doi:10.17487/RFC1321.RFC1321. |
| C6. | Rivest, Ronald L. (March 1998).A Description of the RC2(r) Encryption Algorithm. Network Working Group.doi:10.17487/RFC2268.RFC2268. |
| C7. | Rivest, Ronald L.;Shamir, Adi;Tauman, Yael (2001). "How to Leak a Secret". In Boyd, Colin (ed.).Advances in Cryptology – ASIACRYPT 2001, 7th International Conference on the Theory and Application of Cryptology and Information Security, Gold Coast, Australia, December 9–13, 2001, Proceedings. Lecture Notes in Computer Science. Vol. 2248. Springer. pp. 552–565.doi:10.1007/3-540-45682-1_32.ISBN 978-3-540-42987-6. |
| C8. | Rivest, Ronald L. (1994). "The RC5 encryption algorithm". In Preneel, Bart (ed.).Fast Software Encryption: Second International Workshop. Leuven, Belgium, 14–16 December 1994, Proceedings. Lecture Notes in Computer Science. Vol. 1008. Springer. pp. 86–96.doi:10.1007/3-540-60590-8_7.ISBN 978-3-540-60590-4. |
| L1. | Hyafil, Laurent; Rivest, Ronald L. (May 1976). "Constructing optimal binary decision trees is NP-complete".Information Processing Letters.5 (1):15–17.doi:10.1016/0020-0190(76)90095-8.MR 0413598. |
| L2. | Rivest, Ronald L. (1987)."Learning decision lists".Machine Learning.2 (3):229–246.doi:10.1007/BF00058680.S2CID 2840541. |
| L3. | Blum, Avrim; Rivest, Ronald L. (1992). "Training a 3-node neural network is NP-complete".Neural Networks.5 (1):117–127.doi:10.1016/S0893-6080(05)80010-3.S2CID 8567973. Previously in NIPS 1988. |
| L4. | Quinlan, J. Ross; Rivest, Ronald L. (1989). "Inferring decision trees using the minimum description length principle".Information and Computation.80 (3):227–248.doi:10.1016/0890-5401(89)90010-2.MR 0984483. |
| L5. | Rivest, Ronald L.;Schapire, Robert E. (1993)."Inference of finite automata using homing sequences".Information and Computation.103 (2):299–347.doi:10.1006/inco.1993.1021.MR 1216458. Previously announced at STOC 1989. |
| V1. | Jakobsson, Markus; Juels, Ari; Rivest, Ronald L. (2002)."Making mix nets robust for electronic voting by randomized partial checking". In Boneh, Dan (ed.).Proceedings of the 11th USENIX Security Symposium, San Francisco, CA, USA, August 5-9, 2002. Boston, Massachusetts: USENIX Association. pp. 339–353. |
| V2. | Rivest, Ronald L.; Smith, Warren D. (August 2007)."Three voting protocols: ThreeBallot, VAV, and Twin"(PDF).2007 USENIX/ACCURATE Electronic Voting Technology Workshop (EVT 07). Boston, Massachusetts: USENIX Association. |
| V3. | Chaum, David; Carback, Richard; Clark, Jeremy; Essex, Aleksander; Popoveniuc, Stefan; Rivest, Ronald L.; Ryan, Peter Y. A.; Shen, Emily; Sherman, Alan T. (2008)."Scantegrity II: end-to-end verifiability for optical scan election systems using invisible ink confirmation codes"(PDF). In Dill, David L.; Kohno, Tadayoshi (eds.).2008 USENIX/ACCURATE Electronic Voting Workshop, EVT 2008, July 28-29, 2008, San Jose, CA, USA, Proceedings. Boston, Massachusetts: USENIX Association. |
His son isChris Rivest, entrepreneur and company co-founder.[19]
| International | |
|---|---|
| National | |
| Academics | |
| People | |
| Other | |
