Editing Ron Rivest (section)

==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===
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 name=turing>{{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 same paper that introduced this cryptosystem also introduced [[Alice and Bob]], the fictional heroes of many subsequent [[cryptographic protocol]]s.<ref>{{cite journal
 | last = Hayes | first = Brian | author-link = Brian Hayes (scientist)
 | date = September–October 2012
 | department = Computing science
 | doi = 10.1511/2012.98.362
 | issue = 5
 | journal = [[American Scientist]]
 | jstor = 43707638
 | page = 362
 | publisher = Sigma Xi
 | title = Alice and Bob in cipherspace
 | volume = 100}}</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 | author3-link = Elisa Bertino
 | 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| isbn = 978-3-319-12228-1
 | s2cid = 11182158
 }} 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|C3}}<ref>{{cite book
 | last1 = Menezes | first1 = Alfred J. | author1-link = Alfred Menezes
 | last2 = van Oorschot | first2 = Paul C. | author2-link = Paul van Oorschot
 | last3 = Vanstone | first3 = Scott A. | author3-link = Scott Vanstone
 | chapter = 11.6.4 The GMR one-time signature scheme
 | chapter-url = https://cacr.uwaterloo.ca/hac/about/chap11.pdf
 | isbn = 0-8493-8523-7
 | pages = 468–471
 | publisher = CRC Press
 | title = Handbook of Applied Cryptography
 | year = 1996}}</ref>
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}}

Other contributions of Rivest to cryptography include [[chaffing and winnowing]], the [[interlock protocol]] for authenticating [[Key-agreement protocol|anonymous key-exchange]], cryptographic [[time capsule]]s 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 [[micropayment]]s.

===Algorithms===
In 1973, Rivest and his coauthors published the first [[selection algorithm]] that achieved [[linear time]] without using [[randomization]].{{ran|A1}}<ref>{{cite conference
 | last = Paterson | first = Mike | author-link = Mike Paterson
 | editor1-last = Karlsson | editor1-first = Rolf G.
 | editor2-last = Lingas | editor2-first = Andrzej
 | contribution = Progress in selection
 | doi = 10.1007/3-540-61422-2_146
 | pages = 368–379
 | publisher = Springer
 | series = Lecture Notes in Computer Science
 | title = Algorithm Theory – SWAT '96, 5th Scandinavian Workshop on Algorithm Theory, Reykjavík, Iceland, July 3–5, 1996, Proceedings
 | volume = 1097
 | year = 1996| isbn = 978-3-540-61422-7 }}</ref> Their algorithm, the [[median of medians]] method, is commonly taught in algorithms courses.<ref>{{cite journal
 | last = Gurwitz | first = Chaya
 | doi = 10.1109/13.144650
 | issue = 3
 | journal = IEEE Transactions on Education
 | pages = 230–232
 | title = On teaching median-finding algorithms
 | volume = 35
 | year = 1992| bibcode = 1992ITEdu..35..230G
 }}</ref> 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.{{ran|A2}}<ref>{{cite journal
 | last1 = Cunto | first1 = Walter
 | last2 = Munro | first2 = J. Ian | author2-link = Ian Munro (computer scientist)
 | doi = 10.1145/62044.62047
 | issue = 2
 | journal = [[Journal of the ACM]]
 | mr = 1072421
 | pages = 270–279
 | title = Average case selection
 | volume = 36
 | year = 1989| s2cid = 10947879
 | doi-access = free
 }}</ref>

Rivest's 1974 doctoral dissertation concerned the use of [[hash table]]s to quickly match [[partial word]]s in documents; he later published this work as a journal paper.{{ran|A3}} His research from this time on [[self-organizing list]]s{{ran|A4}} became one of the important precursors to the development of [[Competitive analysis (online algorithm)|competitive analysis]] for [[online algorithm]]s.<ref>{{cite journal
 | last1 = Sleator | first1 = Daniel D. | author1-link = Daniel Sleator
 | last2 = Tarjan | first2 = Robert E. | author2-link = Robert Tarjan
 | doi = 10.1145/2786.2793
 | issue = 2
 | journal = [[Communications of the ACM]]
 | mr = 777385
 | pages = 202–208
 | title = Amortized efficiency of list update and paging rules
 | volume = 28
 | year = 1985| s2cid = 2494305 | doi-access = free
 }}</ref> In the early 1980s, he also published well-cited research on two-dimensional [[bin packing problem]]s,{{ran|A5}} and on [[channel routing]] in [[VLSI design]].{{ran|A6}}

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.{{ran|A7}}

===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 value|expected number]] of questions that will be asked.{{ran|L1}} With [[Avrim Blum]], Rivest also showed that even for very simple [[Artificial neural network|neural networks]] it can be NP-complete to train the network by finding weights that allow it to solve a given classification task correctly.{{ran|L3}} Despite these negative results, he also found methods for efficiently inferring [[decision list]]s,{{ran|L2}} decision trees,{{ran|L4}} and [[finite automaton|finite automata]].{{ran|L5}}

===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 network]]s in this application,{{ran|V1}} the 2006 invention of the [[ThreeBallot]] paper ballot based [[End-to-end auditable voting systems|end-to-end auditable voting system]] (which he released into [[public domain]] in the interest of promoting democracy),{{ran|V2}}<ref name=turing/> and the development of the [[Scantegrity]] security system for [[optical scan voting system]]s.{{ran|V3}}

He was a member of the [[Technical Guidelines Development Committee|Election Assistance Commission's Technical Guidelines Development Committee]].<ref name="NIST">{{cite web|url=http://vote.nist.gov/tgdcmem.htm|title=TGDC members |archive-url=https://web.archive.org/web/20070608071658/http://vote.nist.gov/tgdcmem.htm |archive-date=2007-06-08 |publisher=[[National Institute of Standards and Technology]]|date=2009-05-06 }}</ref>