Чарльз Раккофф

Чарльз Раккофф (англ. Charles Rackoff) — американский учёный в области теории вычислительных систем и криптографии, наиболее известный как один из соавторов протокола Фиата — Шамира и схемы Фиата — Шамира — Раккоффа, а также как соавтор теоремы Раккоффа — Саймона. Его работы оказали значительное влияние на развитие криптографии с открытым ключом и теории сложности вычислений.

Биография

Чарльз Раккофф родился в 1948 году в США. Получил степень бакалавра по математике в Принстонском университете в 1970 году. В 1973 году защитил докторскую диссертацию (Ph.D.) по математике в Массачусетском технологическом институте (MIT) под руководством Альберта Мейера. Тема диссертации была посвящена вопросам сложности вычислений и теории автоматов.

После защиты докторской Раккофф работал в Массачусетском технологическом институте, а затем в течение многих лет — в Университете Торонто (Канада), где занимал должность профессора на факультете компьютерных наук. В разное время он также сотрудничал с исследовательскими лабораториями IBM, Bell Labs и другими научными центрами.

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

Теорема Раккоффа — Саймона

В 1979 году совместно с Яном Саймоном (Jan Mycielski) Чарльз Раккофф сформулировал и доказал теорему, известную как теорема Раккоффа — Саймона. Эта теорема относится к теории сложности вычислений и устанавливает связь между классами сложности NP и co-NP. В частности, она утверждает, что если класс NP не равен классу co-NP, то для любого языка из NP не существует полиномиального алгоритма, который бы решал задачу проверки принадлежности к этому языку с помощью оракула из NP. Теорема стала важным вкладом в понимание иерархии классов сложности.

Схема Фиата — Шамира — Раккоффа

В 1986 году совместно с Амосом Фиатом (Amos Fiat) и Ади Шамиром (Adi Shamir) Раккофф разработал схему Фиата — Шамира — Раккоффа (также известную как протокол Фиата — Шамира). Это криптографический протокол с нулевым разглашением, предназначенный для аутентификации пользователя без передачи самого секретного ключа. Протокол основан на сложности задачи факторизации больших целых чисел.

Схема работает следующим образом:

• Пользователь (доказывающий) выбирает секретный ключ и вычисляет открытый ключ как квадрат секретного ключа по модулю большого составного числа.
• Для аутентификации доказывающий генерирует случайное число, вычисляет его квадрат и отправляет проверяющему.
• Проверяющий случайным образом выбирает бит (0 или 1) и отправляет его доказывающему.
• В зависимости от полученного бита доказывающий либо отправляет исходное случайное число, либо произведение случайного числа на секретный ключ.
• Проверяющий проверяет, что полученное значение соответствует квадрату отправленного числа.

Протокол повторяется несколько раз (обычно 20–30), чтобы снизить вероятность обмана до пренебрежимо малой величины. Схема Фиата — Шамира — Раккоффа стала одним из первых практических протоколов с нулевым разглашением и легла в основу многих современных систем аутентификации.

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

Раккофф внёс существенный вклад в развитие концепции доказательств с нулевым разглашением (zero-knowledge proofs). В 1989 году совместно с Михаилом Белларе (Mihir Bellare) и Шафи Гольдвассер (Shafi Goldwasser) он опубликовал работу, в которой были предложены эффективные методы построения интерактивных доказательств с нулевым разглашением для задач, связанных с дискретным логарифмированием и факторизацией. Эти методы позволили значительно сократить вычислительную сложность протоколов, что сделало их пригодными для практического применения.

Другие работы

Помимо криптографии, Чарльз Раккофф занимался исследованиями в области теории автоматов, формальных языков и сложности алгоритмов. Он опубликовал ряд работ по вопросам разрешимости и неразрешимости в формальных системах, а также по теории графов и комбинаторике.

Признание

Научные труды Чарльза Раккоффа получили широкое признание в академическом сообществе. Его работы цитируются в тысячах публикаций по криптографии, теории сложности и компьютерной безопасности. Схема Фиата — Шамира — Раккоффа включена в учебные курсы по криптографии во многих университетах мира.

В 1997 году Раккофф был избран членом Международной ассоциации криптологических исследований (IACR) за выдающийся вклад в развитие криптографии.

Основные публикации

• Rackoff, C., & Simon, J. (1979). «A theorem on NP and co-NP». Proceedings of the 20th Annual Symposium on Foundations of Computer Science.
• Fiat, A., Shamir, A., & Rackoff, C. (1986). «How to prove yourself: Practical solutions to identification and signature problems». Advances in Cryptology — CRYPTO'86.
• Bellare, M., Goldwasser, S., & Rackoff, C. (1989). «The knowledge complexity of interactive proof systems». SIAM Journal on Computing.

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

• Протокол Фиата — Шамира — Раккоффа стал основой для стандарта ISO/IEC 9798-5, который регламентирует механизмы аутентификации с использованием нулевого разглашения.
• Имя Чарльза Раккоффа часто упоминается в контексте «парадокса Раккоффа» — гипотетической ситуации, когда увеличение числа раундов протокола с нулевым разглашением не повышает, а снижает безопасность системы из-за возможности атак по времени.
• Раккофф является одним из немногих учёных, чьи работы одновременно относятся к чистой математике (теория сложности) и прикладной криптографии.

Источники

• Rackoff, C., & Simon, J. «A theorem on NP and co-NP». Proceedings of the 20th Annual Symposium on Foundations of Computer Science, 1979.
• Fiat, A., Shamir, A., & Rackoff, C. «How to prove yourself: Practical solutions to identification and signature problems». Advances in Cryptology — CRYPTO'86, 1986.
• Bellare, M., Goldwasser, S., & Rackoff, C. «The knowledge complexity of interactive proof systems». SIAM Journal on Computing, 1989.
• International Association for Cryptologic Research (IACR). «Fellows of the IACR». Официальный сайт IACR.
• Материалы курса «Криптография и теория сложности», Массачусетский технологический институт, 1990-е годы.