Рон Ривест
Американский криптограф

Рон Ривест
Ривест в 2012 году
Рожденный( 1947-05-06 )6 мая 1947 г. (77 лет)
Скенектади, Нью-Йорк , США
Национальностьамериканский
Альма-матерЙельский университет ( бакалавр )
Стэнфордский университет ( доктор философии )
ИзвестныйОткрытый ключ
RSA , RC2 , RC4 , RC5 , RC6
MD2 , MD4 , MD5 , MD6 , кольцевая подпись
Награды
Научная карьера
Поля
УчрежденияМассачусетский технологический институт
ТезисАнализ алгоритмов ассоциативного поиска  (1974)
научный руководительРоберт У. Флойд
Докторанты
Веб-сайтлюди.csail.mit.edu/rivest/

Рональд Линн Ривест ( / 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]

Избранные публикации

Публикации Ривеста включают:

Алгоритмы

А1.
Блюм, Мануэль ; Флойд, Роберт В .; Пратт, Воган ; Ривест, Рональд Л.; Тарьян, Роберт Э. (1973). «Временные рамки для выбора» (PDF) . Журнал компьютерных и системных наук . 7 (4): 448–461. doi : 10.1016/S0022-0000(73)80033-9 . MR  0329916.Ранее анонсировано как «Линейные временные границы для вычислений медианы», STOC 1972.
А2.
Флойд, Роберт В.; Ривест, Рональд Л. (март 1975 г.). «Ожидаемые временные рамки для отбора». Сообщения ACM . 18 (3): 165–172. doi : 10.1145/360680.360691 . S2CID  3064709.См. также «Алгоритм 489: алгоритм SELECT — для нахождения наименьшего из элементов», стр. 173, doi :10.1145/360680.360694. я {\displaystyle я} н {\displaystyle n}
А3.
Ривест, Рональд Л. (1976). «Алгоритмы частичного поиска совпадений». Журнал SIAM по вычислениям . 5 (1): 19–50. doi :10.1137/0205003. MR  0395398.Ранее анонсировано на 15-м ежегодном симпозиуме по теории коммутации и автоматов, 1974 г.
А4.
Ривест, Рональд (1976). «О самоорганизующихся эвристиках последовательного поиска». Сообщения ACM . 19 (2): 63–67. doi : 10.1145/359997.360000 . MR  0408303. S2CID  498886.Ранее анонсировано на 15-м ежегодном симпозиуме по теории коммутации и автоматов, 1974 г.
А5.
Бейкер, Бренда С.; Коффман , Э. Г. Мл .; Ривест, Рональд Л. (1980). «Ортогональные упаковки в двух измерениях». SIAM Journal on Computing . 9 (4): 846–855. CiteSeerX  10.1.1.309.8883 . doi :10.1137/0209064. MR  0592771.
А6.
Rivest, Ronald L.; Fiduccia, Charles M. (1982). «A „gredy“ channel router» („жадный“ маршрутизатор каналов). В Crabbe, James S.; Radke, Charles E.; Ofek, Hillel (ред.). Труды 19-й конференции по автоматизации проектирования, DAC '82, Лас-Вегас, Невада, США, 14–16 июня 1982 г. ACM и IEEE. стр. 418–424. doi :10.1145/800263.809239.
А7.
Кормен, Томас Х .; Лейзерсон, Чарльз Э .; Ривест, Рональд Л. (1990). Введение в алгоритмы (1-е изд.). MIT Press и McGraw-Hill. ISBN 0-262-03141-8.2-е издание, совместно с Клиффордом Стайном , 2001 г. 3-е издание, 2009 г. 4-е издание, 2022 г.

Криптография

С1.
Ривест, Р. Л.; Шамир, А.; Адлеман , Л. (1978). «Метод получения цифровых подписей и криптосистем с открытым ключом». Сообщения ACM . 21 (2): 120–126. doi : 10.1145/359340.359342 . hdl : 1721.1/148910 . MR  0700103. S2CID  2873616.
С2.
Ривест, Р.; Адлеман, Л .; Дертузос, М. (1978). «О банках данных и гомоморфизмах конфиденциальности». В DeMillo, Ричард А. (ред.). Основы безопасных вычислений . Academic Press. стр. 169–177.
С3.
Goldwasser, Shafi ; Micali, Silvio ; Rivest, Ronald L. (1988). «Схема цифровой подписи, защищенная от атак с адаптивным выбором сообщений». SIAM Journal on Computing . 17 (2): 281–308. doi :10.1137/0217017. MR  0935341. S2CID  1715998.Ранее анонсировано как «Парадоксальное» решение проблемы подписи, FOCS 1984 и CRYPTO 1984.
С4.
Ривест, Рональд Л. (октябрь 1990 г.). Алгоритм дайджеста сообщений MD4. Сетевая рабочая группа. doi : 10.17487/RFC1186 . RFC 1186.
С5.
Ривест, Рональд Л. (апрель 1992 г.). Алгоритм MD5 Message-Digest. Сетевая рабочая группа. doi : 10.17487/RFC1321 . RFC 1321.
С6.
Ривест, Рональд Л. (март 1998 г.). Описание алгоритма шифрования RC2(r). Сетевая рабочая группа. doi : 10.17487/RFC2268 . RFC 2268.
С7.
Rivest, Ronald L.; Shamir, Adi ; Tauman, Yael (2001). «Как раскрыть секрет». В Boyd, Colin (ред.). Advances in Cryptology – ASIACRYPT 2001, 7-я Международная конференция по теории и применению криптологии и информационной безопасности, Голд-Кост, Австралия, 9–13 декабря 2001 г., Труды . Lecture Notes in Computer Science. Vol. 2248. Springer. pp. 552–565. doi : 10.1007/3-540-45682-1_32 .
С8.
Rivest, Ronald L. (1994). "Алгоритм шифрования RC5". В Preneel, Bart (ред.). Fast Software Encryption: Second International Workshop. Лёвен, Бельгия, 14–16 декабря 1994 г., Труды . Lecture Notes in Computer Science. Vol. 1008. Springer. pp. 86–96. doi : 10.1007/3-540-60590-8_7 .

Обучение

Л1.
Хиафил, Лоран; Ривест, Рональд Л. (май 1976 г.). «Построение оптимальных бинарных деревьев решений является NP-полным». Information Processing Letters . 5 (1): 15–17. doi :10.1016/0020-0190(76)90095-8. MR  0413598.
Л2.
Ривест, Рональд Л. (1987). «Обучение спискам решений». Машинное обучение . 2 (3): 229–246. doi : 10.1007/BF00058680 . S2CID  2840541.
Л3.
Блюм, Аврим ; Ривест, Рональд Л. (1992). «Обучение нейронной сети с тремя узлами является NP-полным». Нейронные сети . 5 (1): 117–127. doi :10.1016/S0893-6080(05)80010-3. S2CID  8567973.Ранее в NIPS 1988.
Л4.
Куинлан, Дж. Росс ; Ривест, Рональд Л. (1989). «Вывод деревьев решений с использованием принципа минимальной длины описания». Информация и вычисления . 80 (3): 227–248. doi :10.1016/0890-5401(89)90010-2. MR  0984483.
Л5.
Ривест, Рональд Л.; Шапир, Роберт Э. (1993). «Вывод конечных автоматов с использованием последовательностей самонаведения». Информация и вычисления . 103 (2): 299–347. doi : 10.1006/inco.1993.1021 . MR  1216458.Ранее анонсировано на STOC 1989.

Выборы и голосование

В1.
Якобссон, Маркус; Джулс, Ари; Ривест, Рональд Л. (2002). «Создание надежных смешанных сетей для электронного голосования путем рандомизированной частичной проверки». В Boneh, Dan (ред.). Труды 11-го симпозиума по безопасности USENIX, Сан-Франциско, Калифорния, США, 5-9 августа 2002 г. Бостон, Массачусетс: Ассоциация USENIX. стр. 339–353.
В2.
Ривест, Рональд Л.; Смит, Уоррен Д. (август 2007 г.). «Три протокола голосования: ThreeBallot, VAV и Twin» (PDF) . Семинар по технологиям электронного голосования USENIX/ACCURATE 2007 г. (EVT 07) . Бостон, Массачусетс: Ассоциация USENIX.
В3.
Чаум, Дэвид ; Карбэк, Ричард; Кларк, Джереми; Эссекс, Александр; Поповенюк, Стефан; Ривест, Рональд Л.; Райан, Питер YA; Шен, Эмили; Шерман, Алан Т. (2008). "Scantegrity II: сквозная верификация для систем оптического сканирования выборов с использованием невидимых кодов подтверждения чернилами" (PDF) . В Дилл, Дэвид Л.; Коно, Тадаёши (ред.). Семинар по электронному голосованию USENIX/ACCURATE 2008, EVT 2008, 28-29 июля 2008 г., Сан-Хосе, Калифорния, США, Труды . Бостон, Массачусетс: Ассоциация USENIX.

Личная жизнь

Его сын — Крис Ривест , предприниматель и соучредитель компании. [17]

Ссылки

  1. ^ abcdefghijk Рон Ривест в проекте «Генеалогия математики»
  2. ^ ab Singh, Mona (1996). Алгоритмы обучения с применением к навигации роботов и сворачиванию белков (диссертация на степень доктора философии). Массачусетский технологический институт. hdl :1721.1/40579. OCLC  680493381. Значок свободного доступа
  3. ↑ Архивировано в Ghostarchive и Wayback Machine: RSA Conference (25 февраля 2014 г.). «The Cryptographers' Panel» – через YouTube.
  4. ↑ Архивировано в Ghostarchive и Wayback Machine: «Интернет-форум факультета: Рон Ривест». YouTube .
  5. ^ Дизикес, Питер (29 июня 2015 г.). «Чизхолм, Ривест и Томпсон назначены новыми профессорами института: биолог, ученый-компьютерщик и музыкант удостоены высшей награды факультета MIT». Новости MIT . Массачусетский технологический институт.
  6. ^ ab "Ronald (Ron) Linn Rivest". Лауреаты премии ACM Turing Award . Association for Computing Machinery . Получено 15 апреля 2023 г.
  7. ^ Хейс, Брайан (сентябрь–октябрь 2012 г.). «Алиса и Боб в шифрпространстве». Вычислительная наука. American Scientist . 100 (5). Sigma Xi: 362. doi :10.1511/2012.98.362. JSTOR  43707638.
  8. ^ Yi, Xun; Paulet, Russell; Bertino, Elisa (2014). Гомоморфное шифрование и приложения . Springer Briefs in Computer Science. Springer International Publishing. doi :10.1007/978-3-319-12229-8. ISBN 978-3-319-12228-1. S2CID  11182158.См. особенно стр. 47: «Концепция FHE была введена Ривестом под названием гомоморфизмы приватности. Проблема построения схемы с этими свойствами оставалась нерешенной до 2009 года, когда Джентри представил свой прорывной результат».
  9. ^ Менезес, Альфред Дж .; Ван Ооршот, Пол К .; Ванстоун, Скотт А. (1996). "11.6.4 Схема одноразовой подписи GMR" (PDF) . Справочник по прикладной криптографии . CRC Press. стр. 468–471. ISBN 0-8493-8523-7.
  10. ^ Патерсон, Майк (1996). «Прогресс в отборе». В Карлссон, Рольф Г.; Лингас, Анджей (ред.). Теория алгоритмов – SWAT '96, 5-й Скандинавский семинар по теории алгоритмов, Рейкьявик, Исландия, 3–5 июля 1996 г., Труды . Конспект лекций по информатике. Том 1097. Springer. стр. 368–379. doi :10.1007/3-540-61422-2_146.
  11. ^ Гурвиц, Чайя (1992). «Об обучении алгоритмам поиска медианы». Труды IEEE по образованию . 35 (3): 230–232. Bibcode : 1992ITEdu..35..230G. doi : 10.1109/13.144650.
  12. ^ Cunto, Walter; Munro, J. Ian (1989). «Средний выбор случая». Journal of the ACM . 36 (2): 270–279. doi : 10.1145/62044.62047 . MR  1072421. S2CID  10947879.
  13. ^ Sleator, Daniel D. ; Tarjan, Robert E. (1985). "Амортизированная эффективность правил обновления списка и страничного обмена". Communications of the ACM . 28 (2): 202–208. doi : 10.1145/2786.2793 . MR  0777385. S2CID  2494305.
  14. ^ "TGDC members". Национальный институт стандартов и технологий . 6 мая 2009 г. Архивировано из оригинала 8 июня 2007 г.
  15. ↑ Биография. Архивировано из оригинала 2011-12-06.
  16. ^ "Чизхолм, Ривест и Томпсон назначены новыми профессорами института". Новости MIT | Массачусетский технологический институт . 29 июня 2015 г.
  17. ^ См. Благодарности, стр. xxi, в Cormen, Rivest, et al., Introduction to Algorithms, MIT Press
На Викискладе есть медиафайлы по теме Рон Ривест .
  • Список патентов Рона Ривеста на IPEXL
  • Домашняя страница Рональда Л. Ривеста
  • Официальный сайт RSA Security Inc.
  • Рон Ривест исследовательские работы по выборам
  • Публикации Рона Ривеста, проиндексированные Google Scholar
Взято с "https://en.wikipedia.org/w/index.php?title=Рон_Ривест&oldid=1245869789"