Введение

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

Рональд Линн Ривест (/rɪ/'v/ɛ//s//t/; родился 6 мая 1947 года) — криптограф и учёный в области компьютерных наук, чьи работы охватывают алгоритмы и комбинаторику, криптографию, машинное обучение и обеспечение честности выборов. Он является профессором Института в Массачусетском технологическом институте (MIT) и членом Департамента электротехники и компьютерных наук MIT и Лаборатории компьютерных наук и искусственного интеллекта. Вместе с Ади Шамиром и Леном Адлеманом Ривест является одним из создателей алгоритма RSA. Он также является изобретателем алгоритмов симметричного шифрования RC2, RC4 и RC5 и соавтором RC6. (RC расшифровывается как "Шифр Ривеста".) Он также разработал криптографические хеш-функции MD2, MD4, MD5 и MD6.

Образование

Ривест получил степень бакалавра математики в Йельском университете в 1969 году и степень доктора философии по информатике в Стэнфордском университете в 1974 году за исследования под руководством Роберта У. Флойда.

Алгоритмы

В 1973 году Ривест и его соавторы опубликовали первый алгоритм отбора, достигающий линейного времени без использования рандомизации. Их алгоритм, метод медиан медиан, широко преподается на курсах по алгоритмам. Ривест также является одним из двух авторов, давших имя алгоритму Флойда — Ривеста, рандомизированному алгоритму отбора, достигающему почти оптимального числа сравнений. Докторская диссертация Ривеста 1974 года была посвящена использованию хеш-таблиц для быстрого поиска частичных совпадений слов в документах; позже он опубликовал эту работу в виде статьи в научном журнале. Его исследования того времени по самоорганизующимся спискам стали одним из важных предшественников разработки конкурентного анализа для онлайн-алгоритмов. В начале 1980-х годов он также опубликовал широко цитируемые работы по задачам двумерной упаковки в контейнеры и по трассировке каналов в проектировании ВЛСИ. Он является соавтором книги «Введение в алгоритмы» (также известной как CLRS), стандартного учебника по алгоритмам, вместе с Томасом Х. Корменом, Чарльзом Э. Лейзерсоном и Клиффордом Стейн. Впервые опубликованная в 1990 году, она была переиздана четыре раза, последний раз — в 2022 году.

Учиться

В проблеме обучения деревьев решений Ривест и Лоран Хайафил доказали, что задача нахождения дерева решений, идентифицирующего каждый объект из заданной коллекции посредством вопросов с бинарными ответами (как в игре «двадцать вопросов»), и минимизирующего ожидаемое число задаваемых вопросов, является NP-полной. Вместе с Авримом Блумом Ривест также показал, что даже для очень простых нейронных сетей обучение сети, то есть поиск весов, позволяющих ей корректно решать данную задачу классификации, может быть NP-полной задачей. Несмотря на эти негативные результаты, он также разработал методы эффективного построения списков решений, деревьев решений и конечных автоматов.

Выборы

Важной темой в более поздних исследованиях Ривеста стала безопасность выборов, основанная на принципе независимости от программного обеспечения: безопасность выборов должна базироваться на физических носителях информации, чтобы скрытые изменения в программном обеспечении, используемом в системах голосования, не могли привести к незаметному искажению результатов выборов. Его исследования в этой области включают повышение устойчивости смешанных сетей в данном контексте, а также изобретение в 2006 году системы голосования ThreeBallot, основанной на бумажных бюллетенях и обеспечивающей сквозную проверяемость (которую он передал в общественное достояние в целях укрепления демократии).

Почести и награды

Ривест является членом Национальной инженерной академии, Национальной академии наук, а также действительным членом Ассоциации вычислительной техники, Международной ассоциации криптологических исследований и Американской академии искусств и наук. Вместе с Ади Шамиром и Леном Адлеманом он был удостоен премии IEEE Koji Kobayashi Computers and Communications Award 2000 года и премии Secure Computing Lifetime Achievement Award. Он также разделил с ними премию Тьюринга. Ривест получил почетную степень (laurea honoris causa) от Университета Сапиенца в Риме. В 2005 году он получил премию MITX Lifetime Achievement Award. В 2007 году Ривест был удостоен звания стипендиата Маркони, а 29 мая 2008 года он также прочитал лекцию Чесли в Карлтонском колледже. В июне 2015 года он был назначен профессором Института в МТИ.

Личная жизнь

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