Мануэль Блум

Мануэль Блум (исп. Manuel Blum; род. 26 апреля 1938, Каракас, Венесуэла) — американский учёный в области теории вычислительных систем, криптографии и теории сложности вычислений. Лауреат премии Тьюринга (1995) за вклад в основы теории сложности и её применение в криптографии и верификации программ. Профессор Университета Карнеги — Меллона (с 2001 года), ранее — Массачусетского технологического института (MIT) и Калифорнийского университета в Беркли.

Биография

Мануэль Блум родился в семье еврейских иммигрантов из Европы. В 1950-х годах его семья переехала в США. Он получил степень бакалавра в Массачусетском технологическом институте (MIT) в 1959 году, а затем степень доктора философии (Ph.D.) по математике там же в 1964 году под руководством Марвина Мински. Диссертация Блума была посвящена теории машин с произвольным доступом к памяти и заложила основы для его дальнейших работ в области теории сложности.

После защиты Блум работал в Калифорнийском университете в Беркли (1964–1974), затем вернулся в MIT (1974–2001). С 2001 года является профессором Школы компьютерных наук Университета Карнеги — Меллона. За свою карьеру он подготовил множество учеников, среди которых — известные учёные, такие как Леонард Адлеман (соавтор RSA), Шафи Голдвассер, Сильвио Микали и другие.

Основные научные достижения

Аксиомы Блума для мер сложности

В 1967 году Мануэль Блум предложил аксиоматический подход к измерению сложности алгоритмов. Он сформулировал набор аксиом (аксиомы Блума), которым должна удовлетворять любая «разумная» мера сложности (например, время работы или объём используемой памяти). Эти аксиомы легли в основу так называемой теории сложности Блума, которая позволила доказывать общие теоремы о существовании функций с определёнными свойствами сложности, не привязываясь к конкретной модели вычислений. Ключевым результатом стала теорема Блума об ускорении, утверждающая, что существуют вычислимые функции, для которых не существует оптимального (самого быстрого) алгоритма — любой алгоритм можно ускорить сколь угодно сильно.

Криптография: Blowfish и другие алгоритмы

В 1993 году Блум совместно с Брюсом Шнайером разработал симметричный блочный шифр Blowfish. Алгоритм был спроектирован как быстрая и безопасная альтернатива существовавшим на тот момент шифрам (DES, IDEA). Blowfish отличается переменной длиной ключа (от 32 до 448 бит) и использует сеть Фейстеля. Шифр получил широкое распространение в программном обеспечении, особенно в системах VPN и файловых архиваторах (например, в TrueCrypt). Позднее, на основе Blowfish был создан алгоритм Twofish — один из финалистов конкурса AES.

Блум также внёс вклад в развитие криптографии с открытым ключом. Совместно с Шафи Голдвассер и Сильвио Микали он разработал криптосистему Блума — Голдвассер — Микали (1982), основанную на сложности задачи квадратичного вычета. Эта система стала одной из первых, обладающих свойством семантической безопасности (стойкость против атак по выбранному открытому тексту).

Верификация программ и «Странные машины»

Блум известен своими работами в области верификации программного обеспечения. В 1990-х годах он предложил концепцию «Странных машин» (англ. Strange Machines) — вычислительных моделей, которые могут выполнять программы, не соответствующие традиционным архитектурам (например, основанные на химических реакциях или квантовых эффектах). Эта работа была направлена на изучение фундаментальных ограничений верификации и тестирования.

Капча и человеко-машинное взаимодействие

В 2000 году Мануэль Блум совместно с Луисом фон Аном, Николасом Хоппером и Джоном Лэнгфордом изобрёл CAPTCHA (Completely Automated Public Turing test to tell Computers and Humans Apart) — полностью автоматизированный публичный тест Тьюринга для различения компьютеров и людей. Идея заключалась в создании задач, которые легко решаются человеком, но сложны для компьютерных алгоритмов (например, искажённый текст или распознавание объектов). Капча стала стандартным средством защиты веб-сайтов от автоматических регистраций и спама.

В 2003 году Блум предложил более сложный вариант — reCAPTCHA, который, помимо защиты, использовался для оцифровки книг (пользователи, вводя искажённые слова, помогали распознавать текст из старых сканов). В 2009 году reCAPTCHA была приобретена компанией Google.

Теория чисел и случайность

Блум внёс вклад в теорию псевдослучайных чисел. Совместно с Леонардом Адлеманом и Шафи Голдвассер он разработал генератор псевдослучайных чисел Блума — Адлемана — Голдвассер (также известный как BBS-генератор). Этот генератор основан на сложности факторизации целых чисел и считается криптографически стойким при условии, что задача факторизации остаётся трудноразрешимой.

Награды и признание

• Премия Тьюринга (1995) — за вклад в теорию сложности и её применение в криптографии и верификации.
• Премия Парижа Канеллакиса (2008) — за разработку CAPTCHA и reCAPTCHA.
• Член Национальной академии наук США (с 1995).
• Член Американской академии искусств и наук (с 1996).
• Член Ассоциации вычислительной техники (ACM) (с 1994).

Семья

Мануэль Блум женат на Леноре Блум (урождённая Эпштейн), также известной как Ленора Карол Блум — американской учёной в области компьютерных наук, специализирующейся на теории игр и алгоритмической теории игр. У них трое детей, двое из которых — Авраам Блум и Майкл Блум — также стали известными учёными в области компьютерных наук.

Критика и ограничения

Несмотря на значительный вклад, некоторые работы Блума подвергались критике. В частности, алгоритм Blowfish, хотя и оставался безопасным в течение многих лет, к началу 2020-х годов считается устаревшим из-за небольшого размера блока (64 бита), что делает его уязвимым для атак с использованием коллизий в современных условиях (например, в протоколах шифрования больших объёмов данных). Однако сам Блум неоднократно отмечал, что Blowfish был разработан как временное решение, и рекомендовал использовать Twofish или AES.

Также высказывались сомнения в практической применимости некоторых теоретических результатов Блума, таких как теорема об ускорении, из-за их «экзистенциального» характера (существование функций доказывается, но конкретные примеры для реальных задач часто оказываются искусственными).

Интересные факты

• Блум является автором термина «капча» (CAPTCHA), который он придумал как аббревиатуру.
• Его сын, Авраам Блум, также является профессором компьютерных наук в Университете Карнеги — Меллона и известен работами в области машинного обучения и теории игр.
• В 2010 году Блум опубликовал статью, в которой предложил «интуитивную капчу» (Intuitive CAPTCHA), основанную на распознавании изображений, а не искажённого текста.

Источники

• Blum, M. (1967). A Machine-Independent Theory of the Complexity of Recursive Functions. Journal of the ACM, 14(2), 322–336.
• Blum, M., & Goldwasser, S. (1982). An Efficient Probabilistic Public-Key Encryption Scheme Which Hides All Partial Information. Proceedings of CRYPTO 82.
• Blum, M., & Micali, S. (1984). How to Generate Cryptographically Strong Sequences of Pseudorandom Bits. SIAM Journal on Computing, 13(4), 850–864.
• Blum, M., & Shneier, B. (1993). Blowfish: A 64-bit Block Cipher. Dr. Dobb's Journal.
• Von Ahn, L., Blum, M., Hopper, N., & Langford, J. (2000). CAPTCHA: Using Hard AI Problems for Security. Proceedings of EUROCRYPT 2000.
• Официальная страница Мануэля Блума на сайте Университета Карнеги — Меллона.