Ron Rivest: Difference between revisions

From Wikipedia, the free encyclopedia
Browse history interactively
← Previous editNext edit →
Content deleted Content added
VisualWikitext
→‎Research: parallel grammar
Line 101: Line 101:
===Crytography===
===Crytography===
The publication of the [[RSA (cryptosystem)|RSA cryptosystem]] by Rivest, [[Adi Shamir]], and [[Leonard Adleman]] in 1978{{ran|C1}} revolutionized modern cryptography by providing the first usable and publicly described method for [[public-key cryptography]]. The three authors won the 2002 [[Turing Award]], the top award in computer science, for this work. The award cited "their ingenious contribution to making public-key cryptography useful in practice".<ref>{{cite web|url=https://amturing.acm.org/award_winners/rivest_1403005.cfm|title=Ronald (Ron) Linn Rivest|work=ACM Turing Award laureates|publisher=Association for Computing Machinery|access-date=2023-04-15}}</ref>
The publication of the [[RSA (cryptosystem)|RSA cryptosystem]] by Rivest, [[Adi Shamir]], and [[Leonard Adleman]] in 1978{{ran|C1}} revolutionized modern cryptography by providing the first usable and publicly described method for [[public-key cryptography]]. The three authors won the 2002 [[Turing Award]], the top award in computer science, for this work. The award cited "their ingenious contribution to making public-key cryptography useful in practice".<ref>{{cite web|url=https://amturing.acm.org/award_winners/rivest_1403005.cfm|title=Ronald (Ron) Linn Rivest|work=ACM Turing Award laureates|publisher=Association for Computing Machinery|access-date=2023-04-15}}</ref>
In the same year, Rivest, Adleman, and [[Michael Dertouzos]] first formulated [[homomorphic encryption]] and its applications in secure [[cloud computing]],{{ran|C2}} an idea that would not come to fruition until over 40 years later when secure homomorphic encryption algorithms were finally developed.<ref>{{cite book
| last1 = Yi | first1 = Xun
| last2 = Paulet | first2 = Russell
| last3 = Bertino | first3 = Elisa
| doi = 10.1007/978-3-319-12229-8
| publisher = Springer International Publishing
| series = Springer Briefs in Computer Science
| title = Homomorphic Encryption and Applications
| year = 2014}} See especially p. 47: "The concept of FHE was introduced by Rivest under the name privacy homomorphisms. The problem of constructing a scheme with these properties remained unsolved until 2009, when Gentry presented his breakthrough result."</ref>


Rivest was one of the inventors of the [[GMR (cryptography)|GMR public signature scheme]], published with [[Shafi Goldwasser]] and [[Silvio Micali]] in 1988,{{ran|C2}}
Rivest was one of the inventors of the [[GMR (cryptography)|GMR public signature scheme]], published with [[Shafi Goldwasser]] and [[Silvio Micali]] in 1988,{{ran|C3}}
and of [[ring signature]]s, an anonymized form of [[group signature]]s invented with Shamir and [[Yael Tauman Kalai]] in 2001.{{ran|C6}} He designed the [[MD4]] and [[MD5]] [[cryptographic hash function]]s, published in 1990 and 1992 respectively,{{ran|C3}}{{ran|C4}} and a sequence of [[symmetric key]] [[block cipher]]s that include [[RC2]], [[RC4]], [[RC5]], and [[RC6]].{{ran|C5}}{{ran|C7}}
and of [[ring signature]]s, an anonymized form of [[group signature]]s invented with Shamir and [[Yael Tauman Kalai]] in 2001.{{ran|C7}} He designed the [[MD4]] and [[MD5]] [[cryptographic hash function]]s, published in 1990 and 1992 respectively,{{ran|C4}}{{ran|C5}} and a sequence of [[symmetric key]] [[block cipher]]s that include [[RC2]], [[RC4]], [[RC5]], and [[RC6]].{{ran|C6}}{{ran|C8}}


==Honors and awards==
==Honors and awards==
Line 201: Line 210:
| year = 1978}}}}
| year = 1978}}}}


{{rma|C2|{{cite journal
{{rma|C2|{{cite book
| last1 = Rivest | first1 = R.
| last2 = Adleman | first2 = L. | author2-link = Leonard Adleman
| last3 = Dertouzos | first3 = M. | author3-link = Michael Dertouzos
| editor-last = DeMillo | editor-first = Richard A.
| chapter = On data banks and privacy homomorphisms
| pages = 169–177
| publisher = Academic Press
| title = Foundations of Secure Computation
| year = 1978}}}}

{{rma|C3|{{cite journal
| last1 = Goldwasser | first1 = Shafi | author1-link = Shafi Goldwasser
| last1 = Goldwasser | first1 = Shafi | author1-link = Shafi Goldwasser
| last2 = Micali | first2 = Silvio | author2-link = Silvio Micali
| last2 = Micali | first2 = Silvio | author2-link = Silvio Micali
Line 214: Line 234:
| year = 1988}}}}
| year = 1988}}}}


{{rma|C3|{{cite RFC|last=Rivest|first=Ronald L.|rfc=1186|title=The MD4 Message Digest Algorithm|publisher=Network Working Group|date=October 1990}}}}
{{rma|C4|{{cite RFC|last=Rivest|first=Ronald L.|rfc=1186|title=The MD4 Message Digest Algorithm|publisher=Network Working Group|date=October 1990}}}}


{{rma|C4|{{cite RFC|last=Rivest|first=Ronald L.|rfc=1321|title=The MD5 Message-Digest Algorithm|publisher=Network Working Group|date=April 1992}}}}
{{rma|C5|{{cite RFC|last=Rivest|first=Ronald L.|rfc=1321|title=The MD5 Message-Digest Algorithm|publisher=Network Working Group|date=April 1992}}}}


{{rma|C5|{{cite RFC|last=Rivest|first=Ronald L.|rfc=2268|title=A Description of the RC2(r) Encryption Algorithm|publisher=Network Working Group|date=March 1998}}}}
{{rma|C6|{{cite RFC|last=Rivest|first=Ronald L.|rfc=2268|title=A Description of the RC2(r) Encryption Algorithm|publisher=Network Working Group|date=March 1998}}}}


{{rma|C6|{{cite conference
{{rma|C7|{{cite conference
| last1 = Rivest | first1 = Ronald L.
| last1 = Rivest | first1 = Ronald L.
| last2 = Shamir | first2 = Adi | author2-link = Adi Shamir
| last2 = Shamir | first2 = Adi | author2-link = Adi Shamir
Line 234: Line 254:
| year = 2001}}}}
| year = 2001}}}}


{{rma|C7|{{cite conference
{{rma|C8|{{cite conference
| last = Rivest | first = Ronald L.
| last = Rivest | first = Ronald L.
| editor-last = Preneel | editor-first = Bart
| editor-last = Preneel | editor-first = Bart

Revision as of 07:31, 16 April 2023

"Rivest" redirects here. For other people with the same name, see Rivest (surname).
Ron Rivest
Rivest in 2012
Born (1947-05-06) May 6, 1947 (age 77)
Schenectady, New York, U.S.
NationalityAmerican
Alma materStanford University (PhD)
Yale University
Known forPublic-key[4]
RSA, RC2, RC4, RC5, RC6
MD2, MD4, MD5, MD6, Ring signature
Awards
Scientific career
Fields
InstitutionsMassachusetts Institute of Technology
ThesisAnalysis of associative retrieval algorithms (1974)
Doctoral advisorRobert W. Floyd
Doctoral students
Websitepeople.csail.mit.edu/rivest/

Ronald Linn Rivest (/rɪˈvɛst/;[5][6] born May 6, 1947) is a cryptographer and whose work has spanned the fields of algorithms and combinatorics, cryptography, machine learning, and election integrity. He is an Institute Professor at the Massachusetts Institute of Technology (MIT),[1][better source needed] and a member of MIT's Department of Electrical Engineering and Computer Science and its Computer Science and Artificial Intelligence Laboratory.

Along with Adi Shamir and Len Adleman, Rivest is one of the inventors of the RSA algorithm.[4] He is also the inventor of the symmetric key encryption algorithms RC2, RC4, and RC5, and co-inventor of RC6. (RC stands for "Rivest Cipher". RC3 was broken at RSA Security during development; similarly,[further explanation needed] RC1 was never published.)[citation needed] He also devised the MD2, MD4, MD5 and MD6 cryptographic hash functions.

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.[2]

Career

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

In the interest of promoting and protecting democracy, he released the system into public domain. He was a member of the Election Assistance Commission's Technical Guidelines Development Committee.[7]

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, Burt Kaliski, Anna Lysyanskaya, Ron Pinter, Robert Schapire, Alan Sherman,[2] and Mona Singh.[3]

Research

Rivest has made significant contributions to algorithm design, to the computational complexity of machine learning, and especially to cryptography.

Algorithms

In 1973, Rivest and his coauthors published the first selection algorithm that achieved linear time without using randomization.[A1] Their algorithm, the median of medians method, is commonly taught in algorithms courses.[8] Rivest is also one of the two namesakes of the Floyd–Rivest algorithm, a randomized selection algorithm that achieves a near-optimal number of comparisons.[A2][9]

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.[A3]

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.[L1] 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.[L3] Despite these negative results, he also found methods for efficiently inferring decision lists and decision trees.[L2][L4]

Crytography

The publication of the RSA cryptosystem by Rivest, Adi Shamir, and Leonard Adleman in 1978[C1] revolutionized modern cryptography by providing the first usable and publicly described method for public-key cryptography. The three authors won the 2002 Turing Award, the top award in computer science, for this work. The award cited "their ingenious contribution to making public-key cryptography useful in practice".[10] In the same year, Rivest, Adleman, and Michael Dertouzos first formulated homomorphic encryption and its applications in secure cloud computing,[C2] an idea that would not come to fruition until over 40 years later when secure homomorphic encryption algorithms were finally developed.[11]

Rivest was one of the inventors of the GMR public signature scheme, published with Shafi Goldwasser and Silvio Micali in 1988,[C3] and of ring signatures, an anonymized form of group signatures invented with Shamir and Yael Tauman Kalai in 2001.[C7] He designed the MD4 and MD5 cryptographic hash functions, published in 1990 and 1992 respectively,[C4][C5] and a sequence of symmetric key block ciphers that include RC2, RC4, RC5, and RC6.[C6][C8]

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.[12] 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.[13]

Selected publications

Rivest's publications include:

Algorithms

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.
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 the th smallest of elements", p. 173, doi:10.1145/360680.360694.
A3.
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, with Clifford Stein, 2001. 3rd edition, 2009. 4th edition, 2022.

Learning

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.
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. 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.

Cryptography

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. MR 0700103.
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.
C4.
Rivest, Ronald L. (October 1990). The MD4 Message Digest Algorithm. Network Working Group. doi:10.17487/RFC1186. RFC 1186.
C5.
Rivest, Ronald L. (April 1992). The MD5 Message-Digest Algorithm. Network Working Group. doi:10.17487/RFC1321. RFC 1321.
C6.
Rivest, Ronald L. (March 1998). A Description of the RC2(r) Encryption Algorithm. Network Working Group. doi:10.17487/RFC2268. RFC 2268.
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.
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.

References

  1. ^ a b c d Ron Rivest publications indexed by Google Scholar Edit this at Wikidata
  2. ^ a b c d e f g h i j Ron Rivest at the Mathematics Genealogy Project
  3. ^ a b Singh, Mona (1996). Learning algorithms with applications to robot navigation and protein folding (PhD thesis). Massachusetts Institute of Technology. hdl:1721.1/40579. OCLC 680493381. Free access icon
  4. ^ a b 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. CiteSeerX 10.1.1.607.2677. doi:10.1145/359340.359342. ISSN 0001-0782. S2CID 2873616. Closed access icon
  5. ^ Archived at Ghostarchive and the Wayback Machine: RSA Conference (25 February 2014). "The Cryptographers' Panel" – via YouTube.
  6. ^ Archived at Ghostarchive and the Wayback Machine: "Faculty Forum Online: Ron Rivest". YouTube.
  7. ^ "TGDC members". National Institute of Standards and Technology. 2009-05-06. Archived from the original on 2007-06-08.
  8. ^ Gurwitz, Chaya (1992). "On teaching median-finding algorithms". IEEE Transactions on Education. 35 (3): 230–232. Bibcode:1992ITEdu..35..230G. doi:10.1109/13.144650.
  9. ^ Cunto, Walter; Munro, J. Ian (1989). "Average case selection". Journal of the ACM. 36 (2): 270–279. doi:10.1145/62044.62047. MR 1072421. S2CID 10947879.
  10. ^ "Ronald (Ron) Linn Rivest". ACM Turing Award laureates. Association for Computing Machinery. Retrieved 2023-04-15.
  11. ^ Yi, Xun; Paulet, Russell; Bertino, Elisa (2014). Homomorphic Encryption and Applications. Springer Briefs in Computer Science. Springer International Publishing. doi:10.1007/978-3-319-12229-8. See especially p. 47: "The concept of FHE was introduced by Rivest under the name privacy homomorphisms. The problem of constructing a scheme with these properties remained unsolved until 2009, when Gentry presented his breakthrough result."
  12. ^ Biography. Archived from the original on 2011-12-06.
  13. ^ "Chisholm, Rivest, and Thompson appointed as new Institute Professors". MIT News | Massachusetts Institute of Technology.

External links

Wikimedia Commons has media related to Ron Rivest.
Retrieved from "https://en.wikipedia.org/w/index.php?title=Ron_Rivest&oldid=1150088412"