Рональд Линн Ривест ( / r ɪ ˈ v ɛ s t / ; [3] [4] родился 6 мая 1947 года) — американский криптограф и учёный-компьютерщик, чья работа охватывает области алгоритмов и комбинаторики, криптографии, машинного обучения и честности выборов. Он является профессором Массачусетского технологического института (MIT), [5] и членом кафедры электротехники и компьютерных наук MIT и его лаборатории компьютерных наук и искусственного интеллекта .
Наряду с Ади Шамиром и Леном Адлеманом , Ривест является одним из изобретателей алгоритма RSA . Он также является изобретателем алгоритмов шифрования с симметричным ключом RC2 , RC4 и RC5 , а также соавтором RC6 . ( RC означает «Rivest Cipher».) Он также разработал криптографические хэш-функции MD2 , MD4 , MD5 и MD6 .
Ривест получил степень бакалавра по математике в Йельском университете в 1969 году и степень доктора философии по информатике в Стэнфордском университете в 1974 году за исследования под руководством Роберта У. Флойда . [1]
В Массачусетском технологическом институте Ривест является членом группы теории вычислений и основателем группы криптографии и информационной безопасности MIT CSAIL.
Ривест был основателем RSA Data Security (теперь объединенной с Security Dynamics в RSA Security ), Verisign и Peppercoin .
Среди его бывших докторантов были Аврим Блум , Бенни Чор , Салли Голдман , Берт Калиски , Анна Лысянская , Рон Пинтер , Роберт Шапир , Алан Шерман [1] и Мона Сингх . [ 2]
Ривест особенно известен своими исследованиями в области криптографии . Он также внес значительный вклад в разработку алгоритмов , вычислительную сложность машинного обучения и безопасность выборов .
Публикация криптосистемы RSA Ривестом, Ади Шамиром и Леонардом Адлеманом в 1978 году [C1] произвела революцию в современной криптографии, предоставив первый пригодный для использования и публично описанный метод криптографии с открытым ключом . За эту работу три автора получили премию Тьюринга 2002 года , высшую награду в области компьютерных наук. Награда отмечала «их гениальный вклад в то, чтобы сделать криптографию с открытым ключом полезной на практике». [6] В той же статье, которая представила эту криптосистему, также были представлены Алиса и Боб , вымышленные герои многих последующих криптографических протоколов . [7] В том же году Ривест, Адлеман и Майкл Дертузос впервые сформулировали гомоморфное шифрование и его приложения в безопасных облачных вычислениях , [C2] идея, которая не была реализована до тех пор, пока более 40 лет спустя не были наконец разработаны безопасные алгоритмы гомоморфного шифрования. [8]
Ривест был одним из изобретателей схемы публичной подписи GMR , опубликованной совместно с Шафи Голдвассером и Сильвио Микали в 1988 году, [C3] [9] и кольцевых подписей , анонимизированной формы групповых подписей, изобретенных совместно с Шамиром и Яэль Тауман Калаи в 2001 году. [C7] Он разработал криптографические хэш-функции MD4 и MD5 , опубликованные в 1990 и 1992 годах соответственно, [C4] [C5] и последовательность симметричных блочных шифров , включающих RC2 , RC4 , RC5 и RC6 . [C6] [C8]
Другие вклады Ривеста в криптографию включают в себя chaffing and winnowing , протокол блокировки для аутентификации анонимного обмена ключами , криптографические капсулы времени , такие как LCS35, основанные на ожидаемых улучшениях скорости вычислений с помощью закона Мура , отбеливание ключей и его применение через режим ключа xor–encrypt–xor при расширении стандарта шифрования данных до DES-X , а также систему Peppercoin для криптографических микроплатежей .
В 1973 году Ривест и его соавторы опубликовали первый алгоритм выбора , который достиг линейного времени без использования рандомизации . [A1] [10] Их алгоритм, метод медианы медиан , обычно преподается на курсах по алгоритмам. [11] Ривест также является одним из двух тезок алгоритма Флойда–Ривеста , алгоритма рандомизированного выбора, который достигает почти оптимального числа сравнений. [A2] [12]
Докторская диссертация Ривеста 1974 года была посвящена использованию хэш-таблиц для быстрого сопоставления частичных слов в документах; позже он опубликовал эту работу в журнале. [A3] Его исследования с этого времени по самоорганизующимся спискам [A4] стали одним из важных предшественников развития конкурентного анализа для онлайн-алгоритмов . [13] В начале 1980-х годов он также опубликовал хорошо цитируемые исследования по проблемам двумерной упаковки контейнеров [A5] и по маршрутизации каналов в проектировании СБИС . [A6]
Он является соавтором Introduction to Algorithms (также известного как CLRS ), стандартного учебника по алгоритмам, совместно с Thomas H. Cormen , Charles E. Leiserson и Clifford Stein . Впервые опубликованный в 1990 году, он был расширен до четырех изданий, последнее из которых вышло в 2022 году. [A7]
В задаче обучения дерева решений Ривест и Лоран Хайафил доказали, что NP-полной задачей является нахождение дерева решений, которое идентифицирует каждый из набора объектов с помощью вопросов с двоичными значениями (как в салонной игре из двадцати вопросов ) и которое минимизирует ожидаемое количество вопросов, которые будут заданы. [L1] Совместно с Авримом Блюмом Ривест также показал, что даже для очень простых нейронных сетей может быть NP-полной задача обучения сети путем нахождения весов, которые позволяют ей правильно решать заданную задачу классификации. [L3] Несмотря на эти отрицательные результаты, он также нашел методы для эффективного вывода списков решений , [L2] деревьев решений, [L4] и конечных автоматов . [L5]
Значимой темой в более поздних исследованиях Ривеста была безопасность выборов , основанная на принципе независимости программного обеспечения : безопасность выборов должна быть основана на физических записях, так что скрытые изменения в программном обеспечении, используемом в системах голосования, не могут привести к необнаружимым изменениям результатов выборов. Его исследования в этой области включают повышение надежности смешанных сетей в этом приложении, [V1] изобретение в 2006 году системы голосования на основе бумажных бюллетеней ThreeBallot , сквозной проверяемой системы (которую он передал в общественное достояние в интересах продвижения демократии), [V2] [6] и разработку системы безопасности Scantegrity для систем голосования с оптическим сканированием . [V3]
Он был членом Комитета по разработке технических рекомендаций Комиссии по содействию проведению выборов . [14]
Ривест является членом Национальной академии инженерии , Национальной академии наук , а также членом Ассоциации вычислительной техники , Международной ассоциации криптологических исследований и Американской академии искусств и наук . Вместе с Ади Шамиром и Леном Адлеманом он был награжден премией IEEE Koji Kobayashi Computers and Communications Award 2000 года и премией Secure Computing Lifetime Achievement Award. Он также разделил с ними премию Тьюринга . Ривест получил почетную степень («laurea honoris causa») от Римского университета Ла Сапиенца . [15] В 2005 году он получил премию MITX Lifetime Achievement Award. В 2007 году Ривест был назван стипендиатом Маркони, а 29 мая 2008 года он также прочитал лекцию Чесли в Карлтонском колледже . В июне 2015 года он был назначен профессором Массачусетского технологического института. [16]
Публикации Ривеста включают:
Его сын — Крис Ривест , предприниматель и соучредитель компании. [17]
