Ronald Linn Rivest ( / rɪˈvɛst / ; * 6. Mai 1947 ) ist ein US-amerikanischer Kryptograph und Informatiker , dessen Arbeit die Bereiche Algorithmen und Kombinatorik , Kryptographie , maschinelles Lernen und Wahlintegrität umfasst. Er ist Professor am Massachusetts Institute of Technology ( MIT) [ 5 ] und Mitglied des Fachbereichs Elektrotechnik und Informatik sowie des Labors für Informatik und Künstliche Intelligenz des MIT .

Zusammen mit Adi Shamir und Len Adleman ist Rivest einer der Erfinder des RSA -Algorithmus, für den sie 2002 den ACM Turing Award erhielten . Er ist außerdem Erfinder der symmetrischen Verschlüsselungsalgorithmen RC2 , RC4 und RC5 sowie Miterfinder von RC6 . ( RC steht für „Rivest Cipher“.) Darüber hinaus entwickelte er die kryptografischen Hashfunktionen MD2 , MD4 , MD5 und MD6 .

Ausbildung

Rivest erwarb 1969 einen Bachelor-Abschluss in Mathematik an der Yale University und 1974 einen Doktortitel in Informatik an der Stanford University für Forschungsarbeiten unter der Betreuung von Robert W. Floyd . [ 1 ]

Karriere

Am MIT ist Rivest Mitglied der Theory of Computation Group und Gründer der Cryptography and Information Security Group des MIT CSAIL.

Rivest war Mitbegründer von RSA Data Security (das inzwischen mit Security Dynamics zu RSA Security fusioniert hat ), Verisign und Peppercoin .

Zu seinen ehemaligen Doktoranden zählen Avrim Blum , Benny Chor , Sally Goldman , Burt Kaliski , Anna Lysyanskaya , Margrit Betke , Ron Pinter , Robert Schapire , Alan Sherman [ 1 ] und Mona Singh [ 2 ] .

Forschung

Rivest ist insbesondere für seine Forschung auf dem Gebiet der Kryptographie bekannt . Er hat außerdem bedeutende Beiträge zum Algorithmenentwurf , zur Rechenkomplexität des maschinellen Lernens und zur Wahlsicherheit geleistet .

Kryptographie

Rivest führte 1978 gemeinsam mit Adi Shamir und Leonard Adleman das RSA-Kryptosystem ein [C1], das die moderne Kryptographie revolutionierte, indem es die erste nutzbare und öffentlich beschriebene Methode für Public-Key-Kryptographie bereitstellte . Rivest soll die Kernidee des Kryptosystems nach einem ausgiebigen Weingenuss während der Pessachfeierlichkeiten mit Shamir und Adleman im Haus eines Studenten entwickelt haben. [ 6 ] [ 7 ] Die drei erhielten 2002 den Turing Award für ihren genialen Beitrag zur praktischen Anwendbarkeit der Public-Key-Kryptographie. [ 8 ] In derselben Veröffentlichung wurden auch Alice und Bob , die fiktiven Helden vieler nachfolgender kryptographischer Protokolle, erstmals vorgestellt . [ 9 ] Im selben Jahr formulierten Rivest, Adleman und Michael Dertouzos erstmals die homomorphe Verschlüsselung und ihre Anwendungen im sicheren Cloud Computing [C2] – eine Idee, die erst über 40 Jahre später mit der Entwicklung sicherer homomorpher Verschlüsselungsalgorithmen Realität werden sollte. [ 10 ]

Rivest war einer der Erfinder des GMR-Signaturverfahrens , das er 1988 zusammen mit Shafi Goldwasser und Silvio Micali veröffentlichte [C3] [ 11 ] , sowie der Ringsignaturen , einer anonymisierten Form von Gruppensignaturen , die er 2001 zusammen mit Shamir und Yael Tauman Kalai entwickelte [C7 ]. Er entwarf die kryptografischen Hashfunktionen MD4 und MD5 , die 1990 bzw. 1992 veröffentlicht wurden [C4] [C5 ] , und eine Folge symmetrischer Blockchiffren , darunter RC2 , RC4 , RC5 und RC6 [C6] [C8 ] .

Weitere Beiträge von Rivest zur Kryptographie sind Chaffing und Winnowing , das Interlock-Protokoll zur Authentifizierung des anonymen Schlüsselaustauschs , kryptographische Zeitkapseln wie LCS35 , die auf erwarteten Verbesserungen der Rechengeschwindigkeit durch das Mooresche Gesetz basieren , Key Whitening und seine Anwendung durch den XOR-Verschlüsselungs-XOR- Schlüsselmodus bei der Erweiterung des Data Encryption Standard auf DES-X sowie das Peppercoin -System für kryptographische Mikrozahlungen .

Algorithmen

1973 veröffentlichten Rivest und seine Koautoren den ersten Selektionsalgorithmus , der ohne Randomisierung lineare Laufzeit erreichte . [A1] [ 12 ] Ihr Algorithmus, die Median-von-Medianen -Methode, wird häufig in Algorithmenkursen gelehrt. [ 13 ] Rivest ist außerdem einer der beiden Namensgeber des Floyd-Rivest-Algorithmus , eines randomisierten Selektionsalgorithmus, der eine nahezu optimale Anzahl an Vergleichen erreicht. [A2] [ 14 ]

Rivests Dissertation von 1974 befasste sich mit der Verwendung von Hashtabellen zum schnellen Auffinden von Wortfragmenten in Dokumenten; später veröffentlichte er diese Arbeit als Zeitschriftenartikel. [A3] Seine Forschung zu selbstorganisierenden Listen [A4] wurde zu einem wichtigen Vorläufer der Entwicklung der Wettbewerbsanalyse für Online-Algorithmen . [ 15 ] Anfang der 1980er Jahre veröffentlichte er außerdem vielzitierte Arbeiten zu zweidimensionalen Bin-Packing-Problemen [ A5] und zum Kanalrouting im VLSI-Design . [A6]

Er ist Mitautor von Introduction to Algorithms (auch bekannt als CLRS ), einem Standardlehrbuch über Algorithmen, zusammen mit Thomas H. Cormen , Charles E. Leiserson und Clifford Stein . Es erschien erstmals 1990 und wurde in vier Auflagen erweitert, die letzte im Jahr 2022. [A7]

Lernen

Im Bereich des Lernens von Entscheidungsbäumen bewiesen Rivest und Laurent Hyafil, dass die Suche nach einem Entscheidungsbaum, der jedes Objekt einer Menge mittels binärer Fragen identifiziert (ähnlich dem Gesellschaftsspiel „20 Fragen “) und die erwartete Anzahl der zu stellenden Fragen minimiert , NP-vollständig ist. [L1] Zusammen mit Avrim Blum zeigte Rivest außerdem, dass selbst für sehr einfache neuronale Netze die Suche nach Gewichten, die eine korrekte Lösung einer gegebenen Klassifizierungsaufgabe ermöglichen, NP-vollständig sein kann. [L3] Trotz dieser negativen Ergebnisse fand er auch Methoden zur effizienten Ableitung von Entscheidungslisten , [L2] Entscheidungsbäumen [L4] und endlichen Automaten . [L5]

Wahlen

Ein wichtiger Schwerpunkt von Rivests jüngerer Forschung liegt auf der Wahlsicherheit , basierend auf dem Prinzip der Softwareunabhängigkeit : Die Sicherheit von Wahlen sollte auf physischen Aufzeichnungen beruhen, sodass verdeckte Änderungen an der in Wahlsystemen verwendeten Software keine unbemerkten Auswirkungen auf das Wahlergebnis haben können. Seine Forschung in diesem Bereich umfasst die Verbesserung der Robustheit von Mixed Networks in dieser Anwendung [V1] , die 2006 entwickelte, auf Papierstimmzetteln basierende , durchgängig überprüfbare Wahlmethode ThreeBallot (die er im Interesse der Demokratieförderung der Öffentlichkeit zur Verfügung stellte) [V2] [ 8 ] sowie die Entwicklung des Scantegrity- Sicherheitssystems für optische Scan-Wahlsysteme [V3] .

Er war Mitglied des Technischen Richtlinienentwicklungsausschusses der Wahlhilfekommission . [ 16 ]

Ehrungen und Auszeichnungen

Rivest ist Mitglied der National Academy of Engineering und der National Academy of Sciences sowie Fellow der Association for Computing Machinery , der International Association for Cryptologic Research und der American Academy of Arts and Sciences . Zusammen mit Adi Shamir und Len Adleman erhielt er 2000 den IEEE Koji Kobayashi Computers and Communications Award und den Secure Computing Lifetime Achievement Award. Mit ihnen wurde ihm auch der Turing Award verliehen . Rivest erhielt die Ehrendoktorwürde (Laurea honoris causa) der Sapienza-Universität Rom . [ 17 ] 2005 wurde ihm der MITX Lifetime Achievement Award verliehen. 2007 wurde Rivest zum Marconi Fellow ernannt und hielt am 29. Mai 2008 die Chesley Lecture am Carleton College . Im Juni 2015 wurde er zum Institute Professor am MIT berufen. [ 18 ]

Ausgewählte Publikationen

Zu Rivests Veröffentlichungen gehören:

Algorithmen

A1.
Blum, Manuel ; Floyd, Robert W .; Pratt, Vaughan ; Rivest, Ronald L.; Tarjan , Robert E. (1973). „Zeitgrenzen für die Selektion“ (PDF) . Journal of Computer and System Sciences . 7 (4): 448–461 . doi : 10.1016/S0022-0000(73)80033-9 . MR  0329916 .Zuvor angekündigt unter dem Titel „Lineare Zeitschranken für Medianberechnungen“, STOC 1972.
A2.
Floyd, Robert W.; Rivest , Ronald L. (März 1975). „Erwartete Zeitgrenzen für die Selektion“ . Communications of the ACM . 18 (3): 165–172 . doi : 10.1145/360680.360691 . S2CID  3064709 .Siehe auch „Algorithmus 489: der Algorithmus SELECT – zum Finden des kleinsten Elements “, S. 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 .Bereits angekündigt auf dem 15. jährlichen Symposium über Schalt- und Automatentheorie, 1974.
A4.
Rivest, Ronald (1976). „ Über selbstorganisierende sequentielle Suchheuristiken“ . Communications of the ACM . 19 (2): 63–67 . doi : 10.1145/359997.360000 . MR  0408303. S2CID  498886 .Bereits angekündigt auf dem 15. jährlichen Symposium über Schalt- und Automatentheorie, 1974.
A5.
Baker, Brenda S.; Coffman , E. G. Jr .; Rivest, Ronald L. (1980). „Orthogonale Packungen in zwei Dimensionen“. 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). „Ein ‚gieriger‘ Kanalrouter“. In: Crabbe, James S.; Radke, Charles E.; Ofek, Hillel (Hrsg.). Proceedings of the 19th Design Automation Conference, DAC '82, Las Vegas, Nevada, USA, 14.–16. Juni 1982. ACM und IEEE. S.  418–424 . doi : 10.1145/800263.809239 . ISBN 0-89791-020-6Die
A7.
Cormen, Thomas H. ; Leiserson, Charles E. ; Rivest, Ronald L. (1990). Einführung in Algorithmen (1. Aufl.). MIT Press und McGraw-Hill. ISBN 0-262-03141-8Die2. Auflage, mit Clifford Stein , 2001. 3. Auflage, 2009. 4. Auflage, 2022.

Kryptographie

C1.
C2.
Rivest, R.; Adleman, L .; Dertouzos, M. (1978). „Über Datenbanken und Datenschutzhomomorphismen“. In: DeMillo, Richard A. (Hrsg.). Grundlagen sicherer Berechnungen . Academic Press. S.  169–177 .
C3.
Goldwasser, Shafi ; Micali, Silvio ; Rivest, Ronald L. (1988). „Ein digitales Signaturverfahren, das gegen adaptive Angriffe mit gewählter Nachricht sicher ist“. SIAM Journal on Computing . 17 (2): 281–308 . doi : 10.1137/0217017 . MR  0935341. S2CID  1715998 .Zuvor angekündigt als „Eine ‚paradoxe‘ Lösung für das Signaturproblem“, FOCS 1984 und CRYPTO 1984.
C4.
Rivest, Ronald L. (Oktober 1990). Der MD4 Message Digest-Algorithmus . Network Working Group. doi : 10.17487/RFC1186 . RFC 1186 .
C5.
Rivest, Ronald L. (April 1992). Der MD5 Message-Digest-Algorithmus . Network Working Group. doi : 10.17487/RFC1321 . RFC 1321 .
C6.
Rivest, Ronald L. (März 1998). Eine Beschreibung des RC2(r)-Verschlüsselungsalgorithmus . Network Working Group. doi : 10.17487/RFC2268 . RFC 2268 .
C7.
Rivest, Ronald L.; Shamir, Adi ; Tauman, Yael (2001). „Wie man ein Geheimnis preisgibt“. In: Boyd, Colin (Hrsg.). Fortschritte in der Kryptologie – ASIACRYPT 2001, 7. Internationale Konferenz zur Theorie und Anwendung der Kryptologie und Informationssicherheit, Gold Coast, Australien, 9.–13. Dezember 2001, Tagungsband . Lecture Notes in Computer Science. Band 2248. Springer. S.  552–565 . doi : 10.1007/3-540-45682-1_32 . ISBN 978-3-540-42987-6Die
C8.
Rivest, Ronald L. (1994). „Der RC5-Verschlüsselungsalgorithmus“. In: Preneel, Bart (Hrsg.). Schnelle Softwareverschlüsselung: Zweiter Internationaler Workshop. Leuven, Belgien, 14.–16. Dezember 1994, Tagungsband . Lecture Notes in Computer Science. Band 1008. Springer. S.  86–96 . doi : 10.1007/3-540-60590-8_7 . ISBN 978-3-540-60590-4Die

Lernen

L1.
Hyafil, Laurent; Rivest, Ronald L. (Mai 1976). „Die Konstruktion optimaler binärer Entscheidungsbäume ist NP-vollständig“. Information Processing Letters . 5 (1): 15–17 . doi : 10.1016/0020-0190(76)90095-8 . MR  0413598 .
L2.
Rivest, Ronald L. (1987). „Lernen von Entscheidungslisten“ . Machine Learning . 2 (3): 229–246 . doi : 10.1007/BF00058680 . S2CID  2840541 .
L3.
Blum, Avrim ; Rivest, Ronald L. (1992). „Das Training eines neuronalen Netzes mit 3 Knoten ist NP-vollständig“. Neural Networks . 5 (1): 117–127 . doi : 10.1016/S0893-6080(05)80010-3 . S2CID  8567973 .Zuvor erschienen 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 . Bibcode : 1989InCo...80..227R . doi : 10.1016/0890-5401(89)90010-2 . MR  0984483 .
L5.
Rivest, Ronald L.; Schapire, Robert E. (1993). „Inferenz endlicher Automaten mittels Homing-Sequenzen“ . Information and Computation . 103 (2): 299–347 . doi : 10.1006/inco.1993.1021 . MR  1216458 .Bereits auf der STOC 1989 angekündigt.

Wahlen und Abstimmungen

V1.
Jakobsson, Markus; Juels, Ari; Rivest, Ronald L. (2002). „Making mix nets robust for electronic voting by randomized partial checking“ . In: Boneh, Dan (Hrsg.). Proceedings of the 11th USENIX Security Symposium, San Francisco, CA, USA, 5.–9 . August 2002. Boston, Massachusetts: USENIX Association. S.  339–353 .
V2.
Rivest, Ronald L.; Smith, Warren D. (August 2007). „Drei Wahlprotokolle: ThreeBallot, VAV und 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 YA; Shen, Emily; Sherman, Alan T. (2008). „Scantegrity II: End-to-End-Verifizierbarkeit für optische Wahlsysteme mittels Bestätigungscodes mit unsichtbarer Tinte“ (PDF) . In: Dill, David L.; Kohno, Tadayoshi (Hrsg.). 2008 USENIX/ACCURATE Electronic Voting Workshop, EVT 2008, 28.–29. Juli 2008, San Jose, CA, USA, Tagungsband . Boston, Massachusetts: USENIX Association.

Privatleben

Rivest ist mit Gail Rivest verheiratet, mit der er zwei Söhne hat: Alex Rivest, Filmemacher, und Chris Rivest , Unternehmer und Mitbegründer eines Unternehmens. [ 19 ]

Siehe auch

Referenzen

  1. ^ a b c d e f g h i j k l m Ron Rivest beim Mathematics Genealogy Project
  2. ^ a b Singh, Mona (1996). Lernalgorithmen mit Anwendungen in der Roboternavigation und Proteinfaltung (Dissertation). Massachusetts Institute of Technology. hdl : 1721.1/40579 . OCLC 680493381 . Symbol für freien Zugang
  3. ^ Archiviert bei Ghostarchive und der Wayback Machine : RSA-Konferenz (25. Februar 2014). „Das Kryptographen-Panel“ – via YouTube.
  4. ^ Archiviert bei Ghostarchive und der Wayback Machine : „Faculty Forum Online: Ron Rivest“ . YouTube . 15. Oktober 2015.
  5. ^ Dizikes, Peter (29. Juni 2015). „Chisholm, Rivest und Thompson zu neuen Professoren des MIT ernannt: Biologe, Informatiker und Musiker erhalten die höchste Auszeichnung der MIT-Fakultät“ . MIT News . Massachusetts Institute of Technology.
  6. ^ Calderbank, Michael (20. August 2007). „Das RSA-Kryptosystem: Geschichte, Algorithmus, Primzahlen“ (PDF) .
  7. ^ Singh, Simon (2000). „Kapitel 5: Alice und Bob gehen an die Öffentlichkeit“. In: The Code Book . London: Fourth Estate (GB). ISBN 978-1-85702-889-8Die
  8. ^ a b „Ronald (Ron) Linn Rivest“ . ACM Turing Award-Preisträger . Association for Computing Machinery . Abgerufen am 15. April 2023 .
  9. ^ Hayes, Brian (September–Oktober 2012). „Alice und Bob im Chiffrierraum“. Computing Science. American Scientist . 100 (5). Sigma Xi: 362. doi : 10.1511/2012.98.362 . JSTOR 43707638 . 
  10. Yi , Xun; Paulet, Russell; Bertino, Elisa (2014). Homomorphe Verschlüsselung und Anwendungen . Springer Briefs in Computer Science. Springer International Publishing. doi : 10.1007/978-3-319-12229-8 . ISBN 978-3-319-12228-1. S2CID  11182158 .Siehe insbesondere S. 47: „Das Konzept der FHE wurde von Rivest unter dem Namen Privacy-Homomorphismen eingeführt. Das Problem der Konstruktion eines Schemas mit diesen Eigenschaften blieb bis 2009 ungelöst, als Gentry sein bahnbrechendes Ergebnis präsentierte.“
  11. ^ Menezes, Alfred J .; van Oorschot, Paul C .; Vanstone, Scott A. (1996). „11.6.4 Das GMR-Einmalsignaturverfahren“ (PDF) . Handbuch der angewandten Kryptographie . CRC Press. S.  468–471 . ISBN 0-8493-8523-7Die
  12. ^ Paterson, Mike (1996). „Fortschritte bei der Selektion“. In: Karlsson, Rolf G.; Lingas, Andrzej (Hrsg.). Algorithm Theory – SWAT '96, 5. Skandinavischer Workshop zur Algorithmentheorie, Reykjavík, Island, 3.–5. Juli 1996, Tagungsband . Lecture Notes in Computer Science. Band 1097. Springer. S.  368–379 . doi : 10.1007/3-540-61422-2_146 . ISBN 978-3-540-61422-7Die
  13. ^ Gurwitz, Chaya (1992). „Über das Lehren von Medianfindungsalgorithmen“. IEEE Transactions on Education . 35 (3): 230–232 . Bibcode : 1992ITEdu..35..230G . doi : 10.1109/13.144650 .
  14. ^ 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 .  
  15. ^ Sleator, Daniel D .; Tarjan, Robert E. (1985). „Amortisierte Effizienz von Listenaktualisierungs- und Paging-Regeln“ . Communications of the ACM . 28 (2): 202–208 . doi : 10.1145/2786.2793 . MR 0777385. S2CID 2494305 .  
  16. ^ „TGDC-Mitglieder“ . Nationales Institut für Standards und Technologie . 6. Mai 2009. Archiviert vom Original am 8. Juni 2007.
  17. ^ Biografie . Archiviert vom Original am 06.12.2011.
  18. ^ „Chisholm, Rivest und Thompson zu neuen Professoren des Instituts ernannt“ . MIT News | Massachusetts Institute of Technology . 29. Juni 2015.
  19. ^ Vgl. Danksagungen, S. xxi, in: Cormen, Rivest et al., Introduction to Algorithms , MIT Press, 3. Auflage