Ronald Linn Rivest ( nacido el 6 de mayo de 1947 ) es un criptógrafo y científico informático estadounidense cuyo trabajo ha abarcado los campos de algoritmos y combinatoria, criptografía, aprendizaje automático e integridad electoral. Es profesor de instituto en el Instituto Tecnológico de Massachusetts (MIT), [5] y miembro del Departamento de Ingeniería Eléctrica y Ciencias de la Computación del MIT y de su Laboratorio de Ciencias de la Computación e Inteligencia Artificial .
Junto con Adi Shamir y Len Adleman , Rivest es uno de los inventores del algoritmo RSA . También es el inventor de los algoritmos de cifrado de clave simétrica RC2 , RC4 y RC5 , y coinventor de RC6 ( RC significa "Cifrado Rivest"). También ideó las funciones hash criptográficas MD2 , MD4 , MD5 y MD6 .
Rivest obtuvo una licenciatura en matemáticas de la Universidad de Yale en 1969 y un doctorado en informática de la Universidad de Stanford en 1974 por una investigación supervisada por Robert W. Floyd . [1]
En el MIT, Rivest es miembro del Grupo de Teoría de la Computación y fundador del Grupo de Criptografía y Seguridad de la Información del MIT CSAIL.
Rivest fue uno de los fundadores de RSA Data Security (ahora fusionada con Security Dynamics para formar RSA Security ), Verisign y de Peppercoin .
Entre sus antiguos estudiantes de doctorado se incluyen Avrim Blum , Benny Chor , Sally Goldman , Burt Kaliski , Anna Lysyanskaya , Ron Pinter , Robert Schapire , Alan Sherman , [1] y Mona Singh . [2]
Rivest es especialmente conocido por sus investigaciones en criptografía . También ha realizado importantes contribuciones al diseño de algoritmos , a la complejidad computacional del aprendizaje automático y a la seguridad electoral .
La publicación del criptosistema RSA por Rivest, Adi Shamir y Leonard Adleman en 1978 [C1] revolucionó la criptografía moderna al proporcionar el primer método utilizable y descrito públicamente para la criptografía de clave pública . Los tres autores ganaron el Premio Turing de 2002 , el máximo galardón en informática, por este trabajo. El premio citó "su ingeniosa contribución para hacer que la criptografía de clave pública sea útil en la práctica". [6] El mismo artículo que presentó este criptosistema también presentó a Alice y Bob , los héroes ficticios de muchos protocolos criptográficos posteriores . [7] En el mismo año, Rivest, Adleman y Michael Dertouzos formularon por primera vez el cifrado homomórfico y sus aplicaciones en la computación segura en la nube , [C2] una idea que no se haría realidad hasta más de 40 años después, cuando finalmente se desarrollaron algoritmos de cifrado homomórfico seguro. [8]
Rivest fue uno de los inventores del esquema de firma pública GMR , publicado con Shafi Goldwasser y Silvio Micali en 1988, [C3] [9] y de las firmas de anillo , una forma anónima de firmas de grupo inventada con Shamir y Yael Tauman Kalai en 2001. [C7] Diseñó las funciones hash criptográficas MD4 y MD5 , publicadas en 1990 y 1992 respectivamente, [C4] [C5] y una secuencia de cifrados de bloques de clave simétrica que incluyen RC2 , RC4 , RC5 y RC6 . [C6] [C8]
Otras contribuciones de Rivest a la criptografía incluyen el chaffing y winnowing , el protocolo de interbloqueo para autenticar el intercambio de claves anónimos , cápsulas de tiempo criptográficas como LCS35 basadas en mejoras anticipadas en la velocidad de cálculo a través de la ley de Moore , el blanqueamiento de claves y su aplicación a través del modo de clave xor–encrypt–xor para extender el estándar de cifrado de datos a DES-X , y el sistema Peppercoin para micropagos criptográficos .
En 1973, Rivest y sus coautores publicaron el primer algoritmo de selección que logró un tiempo lineal sin utilizar la aleatorización . [A1] [10] Su algoritmo, el método de la mediana de las medianas , se enseña comúnmente en los cursos de algoritmos. [11] Rivest es también uno de los dos homónimos del algoritmo Floyd-Rivest , un algoritmo de selección aleatoria que logra un número casi óptimo de comparaciones. [A2] [12]
La tesis doctoral de Rivest de 1974 se centró en el uso de tablas hash para hacer coincidir rápidamente palabras parciales en documentos; más tarde publicó este trabajo como artículo de revista. [A3] Su investigación de esta época sobre listas autoorganizadas [A4] se convirtió en uno de los precursores importantes para el desarrollo del análisis competitivo para algoritmos en línea . [13] A principios de la década de 1980, también publicó una investigación muy citada sobre problemas de empaquetamiento de contenedores bidimensionales , [A5] y sobre el enrutamiento de canales en el diseño VLSI . [A6]
Es coautor de Introduction to Algorithms (también conocido como CLRS ), un libro de texto estándar sobre algoritmos, junto con Thomas H. Cormen , Charles E. Leiserson y Clifford Stein . Publicado por primera vez en 1990, se ha ampliado a cuatro ediciones, la última en 2022. [A7]
En el problema del aprendizaje de árboles de decisión , Rivest y Laurent Hyafil demostraron que es NP-completo encontrar un árbol de decisión que identifique cada uno de una colección de objetos a través de preguntas con valores binarios (como en el juego de salón de veinte preguntas ) y que minimice el número esperado de preguntas que se harán. [L1] Con Avrim Blum , Rivest también demostró que incluso para redes neuronales muy simples puede ser NP-completo entrenar la red al encontrar pesos que le permitan resolver correctamente una tarea de clasificación dada. [L3] A pesar de estos resultados negativos, también encontró métodos para inferir eficientemente listas de decisiones , [L2] árboles de decisión, [L4] y autómatas finitos . [L5]
Un tema importante en la investigación más reciente de Rivest ha sido la seguridad electoral , basada en el principio de independencia del software : que la seguridad de las elecciones debe basarse en registros físicos, de modo que los cambios ocultos en el software utilizado en los sistemas de votación no puedan dar lugar a cambios indetectables en los resultados electorales. Su investigación en esta área incluye la mejora de la robustez de las redes mixtas en esta aplicación, [V1] la invención en 2006 del sistema de votación auditable de extremo a extremo basado en papeletas ThreeBallot (que publicó en el dominio público con el interés de promover la democracia), [V2] [6] y el desarrollo del sistema de seguridad Scantegrity para sistemas de votación con escaneo óptico . [V3]
Fue miembro del Comité de Desarrollo de Directrices Técnicas de la Comisión de Asistencia Electoral . [14]
Rivest es miembro de la Academia Nacional de Ingeniería , la Academia Nacional de Ciencias y es miembro de la Asociación de Maquinaria Computacional , la Asociación Internacional de Investigación Criptológica y la Academia Estadounidense de Artes y Ciencias . Junto con Adi Shamir y Len Adleman , ha sido galardonado con el Premio IEEE Koji Kobayashi de Computadoras y Comunicaciones de 2000 y el Premio a la Trayectoria en Computación Segura. También compartió con ellos el Premio Turing . Rivest ha recibido un título honorario (el "laurea honoris causa") de la Universidad La Sapienza de Roma . [15] En 2005, recibió el Premio a la Trayectoria del MITX. Rivest fue nombrado en 2007 Marconi Fellow, y el 29 de mayo de 2008, también dio la conferencia Chesley en Carleton College . Fue nombrado Profesor de Instituto en el MIT en junio de 2015. [16]
Las publicaciones de Rivest incluyen:
Su hijo es Chris Rivest , empresario y cofundador de la empresa. [17]
