Рональд Линн Ривест ( / r ɪ ˈ v ɛ s t / ; [3] [4] родился 6 мая 1947 г.) — криптограф и ученый-компьютерщик, чья работа охватывает области алгоритмов и комбинаторики, криптографии, машинного обучения и выборов. честность. Он является профессором Массачусетского технологического института (MIT) [5] и членом кафедры электротехники и информатики Массачусетского технологического института , а также его лаборатории компьютерных наук и искусственного интеллекта .
Наряду с Ади Шамиром и Леном Адлеманом Ривест является одним из изобретателей алгоритма 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] В том же году Ривест, Адлеман и Майкл Дертузос впервые сформулировали гомоморфное шифрование и его применение в безопасных облачных вычислениях . развитый. [8]
Ривест был одним из изобретателей схемы публичной подписи GMR , опубликованной совместно с Шафи Голдвассером и Сильвио Микали в 1988 году, [C3] [9] и кольцевых подписей , анонимной формы групповых подписей , изобретенной Шамиром и Яэль Тауман Калаи в 2001 году. [C7] Он разработал криптографические хеш-функции MD4 и MD5 , опубликованные в 1990 и 1992 годах соответственно, [C4] [C5] и последовательность блочных шифров с симметричными ключами , которые включают RC2 , RC4 , RC5 и RC6 . [С6] [С8]
Другие вклады Ривеста в криптографию включают в себя растирание и отсеивание , протокол блокировки для аутентификации анонимного обмена ключами , криптографические капсулы времени , такие как LCS35 , основанные на ожидаемом улучшении скорости вычислений благодаря закону Мура , отбеливание ключей и его применение через xor-encrypt-xor. ключевой режим в расширении стандарта шифрования данных до DES-X и системы Peppercoin для криптографических микроплатежей .
В 1973 году Ривест и его соавторы опубликовали первый алгоритм отбора , который достигал линейного времени без использования рандомизации . [A1] [10] Их алгоритм, метод медианы медиан , обычно преподается на курсах по алгоритмам. [11] Ривест также является одним из двух тезок алгоритма Флойда-Ривеста , алгоритма рандомизированного выбора, который обеспечивает почти оптимальное количество сравнений. [А2] [12]
Докторская диссертация Ривеста 1974 года касалась использования хэш-таблиц для быстрого сопоставления части слов в документах; Позже он опубликовал эту работу в журнальной статье. [A3] Его исследования по самоорганизующимся спискам [A4] стали одним из важных предшественников разработки конкурентного анализа для онлайн-алгоритмов . [13] В начале 1980-х годов он также опубликовал широко цитируемое исследование по проблемам двумерной упаковки ячеек , [A5] и по маршрутизации каналов в конструкции СБИС . [А6]
Он является соавтором стандартного учебника по алгоритмам «Введение в алгоритмы » (также известного как CLRS ) вместе с Томасом Х. Корменом , Чарльзом Э. Лейзерсоном и Клиффордом Стейном . Впервые опубликованный в 1990 году, он выдержал четыре издания, последнее из которых вышло в 2022 году. [A7]
В задаче обучения дерева решений Ривест и Лоран Хьяфил доказали, что NP-полно найти дерево решений, которое идентифицирует каждый из набора объектов с помощью двоичных вопросов (как в салонной игре из двадцати вопросов ) и которое минимизирует ожидаемое количество вопросов, которые будут заданы. [L1] Вместе с Авримом Блюмом Ривест также показал, что даже для очень простых нейронных сетей может быть NP-полным обучение сети путем поиска весов, которые позволяют ей правильно решать заданную задачу классификации. [L3] Несмотря на эти отрицательные результаты, он также нашел методы эффективного вывода списков решений , [L2] деревьев решений, [L4] и конечных автоматов . [Л5]
Важной темой недавних исследований Ривеста была безопасность выборов , основанная на принципе независимости программного обеспечения : безопасность выборов должна быть основана на физических записях, чтобы скрытые изменения в программном обеспечении, используемом в системах голосования, не могли привести к необнаружимым изменениям в выборах. результаты. Его исследования в этой области включают повышение надежности смешанных сетей в этом приложении, [V1] изобретение в 2006 году системы сквозного проверяемого голосования на основе бумажных бюллетеней ThreeBallot (которую он опубликовал в общественном достоянии в интересах продвижения демократии). , [V2] [6] и разработка системы безопасности Scantegrity для систем голосования с оптическим сканированием . [В3]
Он был членом Комитета по разработке технических руководств Комиссии по содействию выборам . [14]
Ривест является членом Национальной инженерной академии , Национальной академии наук , а также членом Ассоциации вычислительной техники , Международной ассоциации криптологических исследований и Американской академии искусств и наук . Вместе с Ади Шамиром и Леном Адлеманом он был награжден премией IEEE Кодзи Кобаяши в области компьютеров и коммуникаций 2000 года и премией за выдающиеся достижения в области безопасных вычислений. Он также разделил с ними премию Тьюринга . Ривест получил почетную степень («laurea Honoris Causa») Римского университета Сапиенца . [15] В 2005 году он получил премию MITX за заслуги перед жанром. В 2007 году Ривест был назван стипендиатом Маркони, а 29 мая 2008 года он также прочитал лекцию Чесли в Карлтон-колледже . В июне 2015 года он был назначен профессором Массачусетского технологического института. [16]
Публикации Ривеста включают:
Его сын — Крис Ривест , предприниматель и соучредитель компании. [17]
