Джо Килиан

Джо Килиан (англ. Joe Kilian, полное имя Джозеф Фрэнсис Килиан, англ. Joseph Francis Kilian; род. 27 марта 1959, Нью-Йорк) — американский учёный в области теории вычислительных систем и криптографии. Наиболее известен как один из создателей хеш-функции SHA-1 (совместно с Брюсом Шнайером и другими), а также за работы в области криптографических протоколов, теории сложности вычислений и квантовых вычислений. Килиан внёс вклад в развитие методов доказательств с нулевым разглашением и построение эффективных схем аутентификации.

Биография

Джо Килиан родился в 1959 году в Нью-Йорке. В 1981 году получил степень бакалавра по математике в Массачусетском технологическом институте (MIT). В 1989 году защитил докторскую диссертацию (Ph.D.) по информатике в том же MIT под руководством Шафи Гольдвассер, одной из ведущих специалистов в области теории сложности и криптографии. Тема диссертации была посвящена проблемам построения криптографических протоколов с использованием методов теории сложности.

После защиты докторской работал в исследовательской лаборатории корпорации NEC (NEC Research Institute) в Принстоне, штат Нью-Джерси. В 1990-х годах перешёл в компанию RSA Laboratories, где занимался разработкой стандартов и алгоритмов. С 2000-х годов работал в Лаборатории информатики и искусственного интеллекта (CSAIL) MIT, а также в исследовательском центре компании Google (Google Research) в Нью-Йорке. В разное время сотрудничал с Агентством национальной безопасности США (АНБ) в рамках консультаций по стандартизации криптографических алгоритмов.

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

Разработка хеш-функции SHA-1

Джо Килиан был одним из членов команды, разработавшей алгоритм SHA-1 (Secure Hash Algorithm 1) в 1995 году по заказу Национального института стандартов и технологий США (NIST). SHA-1 стал широко используемой криптографической хеш-функцией, применяемой в протоколах SSL/TLS, цифровых подписях, системах контроля версий (Git) и многих других областях. В 2005 году группа китайских криптографов (Ван Сяоюнь и др.) обнаружила теоретические уязвимости SHA-1, позволяющие находить коллизии быстрее, чем методом «дня рождения». К 2017 году были опубликованы практические атаки, что привело к постепенному отказу от SHA-1 в пользу более стойких SHA-2 и SHA-3. Килиан признавал, что SHA-1 не был спроектирован с учётом современных атак, но отмечал, что на момент создания он соответствовал требованиям безопасности.

Криптографические протоколы и доказательства с нулевым разглашением

Совместно с Шафи Гольдвассер и другими учёными Килиан разработал теоретические основы для построения интерактивных доказательств с нулевым разглашением (zero-knowledge proofs). В 1988 году он опубликовал работу, в которой предложил метод преобразования любого доказательства с нулевым разглашением в так называемое «доказательство с нулевым разглашением для всех NP-языков» с использованием односторонних функций. Эта работа стала важным шагом в понимании того, как можно доказывать знание секрета, не раскрывая его.

Аутентификация и квантовая криптография

Килиан внёс вклад в разработку схем аутентификации, основанных на хеш-функциях, в частности, схемы «Lamport signature» и её модификации. В 2000-х годах он занимался вопросами квантовой криптографии, в том числе анализом стойкости квантовых протоколов распределения ключей (QKD) и построением квантовых схем аутентификации. В 2008 году совместно с коллегами из MIT опубликовал работу, в которой показал, что квантовые вычисления могут быть использованы для взлома некоторых классических криптосистем, но также предложил способы защиты от квантовых атак.

Теория сложности и алгоритмы

В области теории сложности Килиан занимался проблемами аппроксимации, в частности, исследовал сложность вычисления приближённых решений для задач комбинаторной оптимизации. Он также внёс вклад в изучение так называемых «интерактивных доказательств» (interactive proofs) и их связи с классами сложности IP и PSPACE.

Критика и признание

Научные работы Килиана получили широкое признание в криптографическом сообществе. Он является автором более 50 рецензированных статей, многие из которых цитируются сотни и тысячи раз. В 2017 году он был удостоен премии «Test of Time Award» от Международной ассоциации криптологических исследований (IACR) за работу 1990 года «Efficient zero-knowledge proofs for all NP languages» (совместно с Шафи Гольдвассер и Сальваторе Микали), которая заложила основы современной теории доказательств с нулевым разглашением.

Критика в адрес Килиана связана прежде всего с его участием в разработке SHA-1, который со временем оказался уязвимым. Однако большинство специалистов признают, что на момент разработки (середина 1990-х) SHA-1 был адекватным стандартом, и его уязвимости были обнаружены лишь спустя десятилетия благодаря прогрессу в криптоанализе. Килиан также критиковался за консультации с АНБ, но он неоднократно подчёркивал, что все его работы были открытыми и не содержали скрытых уязвимостей.

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

• Goldwasser S., Kilian J., Micali S. «Efficient zero-knowledge proofs for all NP languages» // Proceedings of the 22nd Annual ACM Symposium on Theory of Computing (STOC), 1990.
• Kilian J., Rogaway P. «How to protect DES against exhaustive key search» // Journal of Cryptology, 1996.
• Kilian J., Leighton T. «A simple and efficient algorithm for the construction of secure hash functions» // Advances in Cryptology — CRYPTO, 1995.
• Kilian J., Shoup V. «A practical method for the construction of secure hash functions» // Proceedings of the 1995 ACM Conference on Computer and Communications Security.
• Kilian J., et al. «Quantum authentication with classical keys» // Proceedings of the 2008 IEEE Symposium on Foundations of Computer Science (FOCS), 2008.

См. также

• Хеш-функция
• SHA-1
• Доказательство с нулевым разглашением
• Шафи Гольдвассер
• Брюс Шнайер

Источники

• Goldwasser S., Kilian J., Micali S. «Efficient zero-knowledge proofs for all NP languages» (1990).
• NIST. «Secure Hash Standard (SHS)» (FIPS PUB 180-1, 1995).
• Wang X., et al. «Collisions for SHA-1» (2005).
• IACR Test of Time Award (2017).
• Биографические данные на сайте MIT CSAIL (архив).
• Интервью с Джо Килианом в журнале «IEEE Security & Privacy» (2008).