Шафи Гольдвассер

Шафи Гольдвассер (англ. Shafi Goldwasser, род. 14 ноября 1958, Нью-Йорк, США) — американский и израильский учёный в области теории вычислительных систем и криптографии. Лауреат премии Тьюринга (2012, совместно с Силвио Микали) за новаторские работы, заложившие основы современной теории криптографии с открытым ключом и интерактивных доказательств. Профессор Массачусетского технологического института (MIT) и Института Вейцмана (Израиль).

Биография

Шафи Гольдвассер родилась в семье еврейских эмигрантов из России. Её отец, Самуил Гольдвассер, был инженером, мать — домохозяйкой. Детство провела в Нью-Йорке, где окончила среднюю школу. В 1979 году получила степень бакалавра по математике в Университете Карнеги-Меллона. В 1981 году — степень магистра по информатике в Калифорнийском университете в Беркли. В 1984 году под руководством Мануэля Блюма защитила докторскую диссертацию (Ph.D.) по информатике в том же университете.

С 1983 года работает на факультете компьютерных наук Массачусетского технологического института (MIT), где в 1997 году получила звание профессора. Одновременно с 1990 года является профессором Института Вейцмана (Реховот, Израиль). В 2005 году основала и возглавила лабораторию криптографии и теории сложности в Институте Вейцмана.

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

Шафи Гольдвассер внесла фундаментальный вклад в несколько областей теоретической информатики, включая криптографию, теорию сложности вычислений и теорию доказательств.

Криптография с открытым ключом

В 1984 году совместно с Силвио Микали Гольдвассер предложила концепцию вероятностного шифрования. В отличие от детерминированных схем (например, RSA), вероятностное шифрование использует случайные числа для генерации шифротекста, что делает невозможным получение какой-либо информации об открытом тексте из шифротекста даже при многократном шифровании одного и того же сообщения. Это стало основой для построения семантически безопасных криптосистем. В 1984 году они также представили первую схему вероятностного шифрования, основанную на задаче квадратичного вычета.

Интерактивные доказательства и доказательства с нулевым разглашением

В 1985 году Гольдвассер, Микали и Чарльз Ракофф ввели понятие интерактивных доказательств — протоколов, в которых доказывающий (Prover) и проверяющий (Verifier) обмениваются сообщениями, чтобы убедить проверяющего в истинности некоторого утверждения. В 1989 году совместно с Микали и Ави Вайгерсоном Гольдвассер разработала концепцию доказательств с нулевым разглашением (zero-knowledge proofs). Это протоколы, позволяющие доказывающему убедить проверяющего в истинности утверждения, не раскрывая никакой дополнительной информации, кроме самого факта истинности. Эта работа легла в основу многих современных криптографических протоколов, включая аутентификацию, цифровые подписи и системы электронного голосования.

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

Гольдвассер внесла вклад в теорию сложности вычислений, в частности в изучение классов сложности, связанных с интерактивными доказательствами (классы IP, AM). Она также исследовала природу случайности в вычислениях, показав, что многие задачи, считавшиеся неразрешимыми, могут быть решены с использованием случайных оракулов.

Основные работы

• Probabilistic Encryption (1984, совместно с С. Микали) — введение вероятностного шифрования.
• The Knowledge Complexity of Interactive Proof Systems (1989, совместно с С. Микали и А. Вайгерсоном) — определение доказательств с нулевым разглашением.
• Interactive Proofs and the Hardness of Approximating Cliques (1998, совместно с С. Микали и А. Вайгерсоном) — связь интерактивных доказательств с задачами аппроксимации.
• On the (Im)possibility of Obfuscating Programs (2001, совместно с Б. Барраком, Р. Импальяццо, А. Вайгерсоном и др.) — доказательство невозможности универсального обфускатора программ.

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

• Премия Тьюринга (2012) — совместно с Силвио Микали «за новаторские работы, заложившие основы современной теории криптографии с открытым ключом и интерактивных доказательств».
• Премия Гёделя (1993, 2001) — за работы по интерактивным доказательствам и доказательствам с нулевым разглашением.
• Премия Франклина (2007) — за вклад в теорию сложности и криптографию.
• Премия Эмануэля Пиора (2011) — от Израильского научного фонда.
• Член Национальной академии наук США (2013), Американской академии искусств и наук (2005), Израильской академии наук (2011).
• Почётный доктор нескольких университетов, включая Оксфордский (2015) и Швейцарскую высшую техническую школу Цюриха (2016).

Влияние на науку и технологии

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

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

• Шафи Гольдвассер — одна из двух женщин, получивших премию Тьюринга (наряду с Фрэнсис Аллен).
• Её имя (Shafi) происходит от арабского слова «шафи» (شفيع), означающего «заступник» или «целитель».
• В 2015 году она выступила с лекцией на конференции TEDx, посвящённой будущему криптографии и приватности.

Источники

• Goldwasser, S., Micali, S. (1984). Probabilistic Encryption. Journal of Computer and System Sciences.
• Goldwasser, S., Micali, S., Rackoff, C. (1985). The Knowledge Complexity of Interactive Proof Systems. SIAM Journal on Computing.
• Goldwasser, S., Micali, S., Wigderson, A. (1989). Proofs that Yield Nothing But Their Validity. Journal of the ACM.
• ACM Turing Award 2012: Shafi Goldwasser and Silvio Micali. Association for Computing Machinery.
• Shafi Goldwasser — Biography. National Academy of Sciences.
• Shafi Goldwasser — Faculty Profile. Massachusetts Institute of Technology.