Сильвио Микали: Доказательство без раскрытия

До того как за дело взялись Сильвио Микали (Silvio Micali) и его соратники, криптография была ремеслом хитроумных уловок, ценность которых определялась лишь тем, смог ли их хоть кто-нибудь взломать. Карьера Микали, посвященная превращению этого ремесла в дисциплину с реальными математическими доказательствами в основе, породила одну из самых странных и изящных идей в этой области: способ убедить кого-то в истинности утверждения, не сообщая ему никакой дополнительной информации о причинах этой истинности.

Из Рима в Беркли

Сильвио Микали родился 13 октября 1954 года в Италии. Он получил степень по математике в Римском университете Ла Сапиенца (La Sapienza University of Rome) в 1978 году, после чего пересек Атлантику, чтобы получить степень доктора философии (Ph.D.) по компьютерным наукам в Калифорнийском университете в Беркли, которую завершил в 1982 году под руководством Мануэля Блюма (Manuel Blum) — будущего лауреата премии Тьюринга, работавшего на переднем крае криптографической теории. В 1983 году Микали вошел в состав преподавателей факультета электротехники и компьютерных наук Массачусетского технологического института (MIT) и с тех пор остается там, работая в Лаборатории компьютерных наук и искусственного интеллекта MIT, а также преподавая в Пенсильванском университете, Университете Торонто и Университете Цинхуа.

Делаем безопасность доказуемой

Центральный научный проект Микали, осуществленный в основном в партнерстве с Шафи Голдвассер (Shafi Goldwasser), заключался в замене традиционного для криптографии стандарта безопасности — «это еще никто не взломал» — на математический стандарт: доказательство того, что для взлома схемы потребовалось бы решить задачу, которая считается вычислительно неразрешимой. Вместе с Голдвассер он разработал вероятностное шифрование — метод, который шифрует одно и то же сообщение по-разному при каждой отправке, исключая класс атак, при которых противник мог получить информацию просто заметив совпадение двух шифротекстов. Ассоциация вычислительной техники (ACM) в своем описании их совместной премии Тьюринга отдает им должное за создание области доказуемой безопасности и формализацию идеи о том, что криптографическая безопасность «должна быть вычислительной, а не абсолютной», — переосмысление, которое дало всей дисциплине строгий фундамент, которого ей не хватало. Предложенные ими интерактивные и вероятностные системы доказательств также внесли прямой вклад в теорию вычислительной сложности далеко за пределами криптографии.

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

Самая известная идея, ассоциирующаяся с Микали, — это доказательство с нулевым разглашением (Zero-Knowledge Proof), разработанное совместно с Голдвассер и Чарльзом Ракоффом (Charles Rackoff). Это протокол, в котором «доказывающий» убеждает «проверяющего» в истинности утверждения — что они знают пароль, что транзакция действительна или что граф имеет определенную раскраску, — не раскрывая никакой другой информации о том, почему это истинно, и даже не раскрывая информацию, которая позволила бы проверяющему самому воссоздать доказательство. При первом прослушивании это звучит парадоксально, и при своем появлении эта концепция воспринималась как математическое диковинное увлечение; однако с тех пор она стала рабочим компонентом систем аутентификации и, десятилетия спустя, технологий конфиденциальности блокчейна. Более широкие работы Микали распространяются на генерацию псевдослучайных функций, безопасные многопартийные вычисления (позволяющие нескольким сторонам совместно вычислять результат, не раскрывая друг другу свои закрытые входные данные) и протоколы с ненаблюдаемой передачей (oblivious transfer), каждый из которых стал строительным блоком современной криптографической инженерии.

От теории к стартапам

В отличие от многих теоретиков, довольных тем, что их идеи остаются на бумаге, Микали не ограничивал свою работу академическими журналами. В 2001 году он стал соучредителем компании CoreStreet Ltd, занимающейся вопросами безопасности и проданной в 2009 году компании ActivIdentity, а в начале 2000-х помог создать Peppercoin — раннюю систему цифровых микроплатежей. В 2017 году он основал Algorand, блокчейн-платформу на базе доказательства доли владения (Proof-of-Stake), предназначенную для применения его многолетних теоретических разработок в области криптографии к публичному децентрализованному реестру. Этот поворот на позднем этапе карьеры привел лауреата премии Тьюринга прямо в центр индустрии криптовалют, для которой он, в некотором смысле, тридцать лет закладывал математический фундамент.

Признание

Микали и Голдвассер совместно получили премию Тьюринга ACM A.M. Turing Award за 2012 год (вручена в 2013 году) «за революционную работу, заложившую основы теории сложности для науки криптографии». Ранее Микали был удостоен премии Гёделя (Gödel Prize) в 1993 году за теорию интерактивных систем доказательств и премии RSA за выдающиеся достижения в области математики (RSA Award for Excellence in Mathematics) в 2004 году. Он является членом Национальной академии наук США и Национальной инженерной академии США, а в 2017 году стал феллоу ACM.

Почему Сильвио называют гением

Самое веское доказательство того, что Микали можно назвать гением, носит концептуальный, а не анекдотический характер: доказательства с нулевым разглашением относятся к числу тех идей, которые, однажды увидев их, кажутся очевидно необходимыми, и в то же время для их первоначального замысла потребовался настоящий творческий скачок — доказательство, которое не доказывает ничего, кроме самого себя. Превращение «безопасности» из неформального ремесла в дисциплину с теоремами и редукциями, достижение, которое особо отмечается в представлении к премии Тьюринга, потребовало не только технического мастерства, но и концептуальной дерзости задаться вопросом о том, как вообще должно выглядеть математическое определение секретности. Честность здесь заключается в том, что все это не было сольной работой. Премия Тьюринга была присуждена совместно Микали и Шафи Голдвассер, а в самой статье о доказательствах с нулевым разглашением указаны три автора — Голдвассер, Микали и Чарльз Ракоффи, что делает это хрестоматийным примером фундаментальной идеи, созданной благодаря долгосрочному партнерству, а не изолированному озарению одного человека. Последующие сольные предприятия Микали, CoreStreet и Algorand, демонстрируют личную готовность поставить свою собственную теорию на кон коммерческой и промышленной реальности, но теоретическое ядро, заслужившее ему звание «гения», было, по всем отзывам, включая формулировку награды, общим достижением.

Наследие

Работа Микали пересмотрела стандарты того, что значит называть криптографическую систему безопасной, а доказательства с нулевым разглашением в особенности вышли за рамки своей первоначальной малоизвестности и стали инфраструктурой, используемой в протоколах аутентификации, блокчейн-системах с сохранением конфиденциальности и схемах верификации, которых не существовало, когда они с Голдвассер впервые описали эту идею. Лишь немногие криптографические концепции прошли столь долгий путь от чистой теории до повсеместно развернутых технологий. То, что дисциплина, некогда отвергаемая математиками как второстепенная инженерная задумка, теперь имеет собственный фундамент теории сложности и преподается наряду с вычислимостью и алгоритмическим анализом в любой серьезной учебной программе по информатике, во многом является прямым результатом переосмысления, которое Микали и Голдвассер протолкнули в начале 1980-х годов, — сдвига от вопросов о том, была ли схема уже взломана, к вопросам о том, что именно должно быть истинным во Вселенной, чтобы ее в принципе можно было взломать.